# HG changeset patch
# User deba
# Date 1089893758 0
# Node ID 32f280a5ed7ded5a27b8ecfe616747c8c57180d5
# Parent  4207f82a1778db1b2fd0b37698c4ccc3eb4225d8


diff -r 4207f82a1778 -r 32f280a5ed7d src/work/deba/array_map_factory.h
--- a/src/work/deba/array_map_factory.h	Wed Jul 14 21:16:10 2004 +0000
+++ b/src/work/deba/array_map_factory.h	Thu Jul 15 12:15:58 2004 +0000
@@ -1,11 +1,10 @@
+// -*- c++ -*-
 #ifndef ARRAY_MAP_H
 #define ARRAY_MAP_H
 
 #include <memory>
 
-
-#include <iostream>
-using namespace std;
+#include "extended_pair.h"
 
 namespace hugo {
 	
@@ -19,7 +18,8 @@
 
     typedef typename MapRegistry::MapBase MapBase;
 		
-    template <typename V, typename A = std::allocator<V> > class Map : public MapBase {
+    template <typename V, typename A = std::allocator<V> > 
+    class Map : public MapBase {
     
       public:
 
@@ -30,23 +30,7 @@
       Map() : values(0), capacity(0) {}
 			
       Map(const Graph& g, MapRegistry& r) : MapBase(g, r) {
-	int max_id = -1;
-	for (KeyIt it(*getGraph()); getGraph()->valid(it); getGraph()->next(it)) {
-	  int id = getGraph()->id(it);
-	  if (id > max_id) {
-	    max_id = id;
-	  }			
-	}
-	if (max_id == -1) {
-	  capacity = 0;
-	  values = 0;
-	  return;
-	}
-	capacity = 1;
-	while (capacity <= max_id) {
-	  capacity <<= 1;
-	}
-	values = allocator.allocate(capacity);
+	allocate_memory();
 	for (KeyIt it(*getGraph()); getGraph()->valid(it); getGraph()->next(it)) {
 	  int id = getGraph()->id(it);
 	  allocator.construct(&(values[id]), Value());
@@ -54,23 +38,7 @@
       }
 
       Map(const Graph& g, MapRegistry& r, const Value& v) : MapBase(g, r) {
-	int max_id = -1;
-	for (KeyIt it(*getGraph()); getGraph()->valid(it); getGraph()->next(it)) {
-	  int id = getGraph()->id(it);
-	  if (id > max_id) {
-	    max_id = id;
-	  }			
-	}
-	if (max_id == -1) {
-	  capacity = 0;
-	  values = 0;
-	  return;
-	}
-	capacity = 1;
-	while (capacity <= max_id) {
-	  capacity <<= 1;
-	}
-	values = allocator.allocate(capacity);
+	allocate_memory();
 	for (KeyIt it(*getGraph()); getGraph()->valid(it); getGraph()->next(it)) {
 	  int id = getGraph()->id(it);
 	  allocator.construct(&(values[id]), v);
@@ -87,9 +55,10 @@
 	}
       }
 
-      template <typename CMap> Map(const CMap& copy) : MapBase(copy) {
+      template <typename CMap> Map(const CMap& copy) 
+	: capacity(0), values(0), MapBase(copy) {
 	if (getGraph()) {
-	  init();
+	  allocate_memory();
 	  for (KeyIt it(*getGraph()); getGraph()->valid(it); getGraph()->next(it)) {
 	    set(it, copy[it]);
 	  }
@@ -117,14 +86,12 @@
 	} 
 	this->MapBase::operator=(copy);
 	if (getGraph()) {
-	  init();
+	  allocate_memory();
 	  for (KeyIt it(*getGraph()); getGraph()->valid(it); getGraph()->next(it)) {
 	    set(it, copy[it]);
 	  }
 	}
       }
-
-       
 				
       virtual ~Map() {
 	if (capacity != 0) {
@@ -181,36 +148,44 @@
 	allocator.destroy(&(values[id]));
       }
 	
-      /** Compatible iterator with the stl maps' iterators.
-       *  It iterates on pairs of a key and a value.
-       */
       class iterator {
 	friend class Map;
 	friend class const_iterator;
-	private:
+      private:
 
 	/** Private constructor to initalize the the iterators returned
 	 *  by the begin() and end().
 	 */
 	iterator (Map& pmap, const KeyIt& pit) : map(&pmap), it(pit) {}
 
-	public:
+      public:
 
 	/** Default constructor. 
 	 */
 	iterator() {}
 
+	typedef extended_pair<const Key&, const Key&, 
+			      Value&, Value&> Reference;
+
 	/** Dereference operator for map.
 	 */	 
-	std::pair<const Key, Value> operator*() {
-	  return std::pair<const Key, Value>(it, (*map)[it]);
+	Reference operator*() {
+	  return Reference(it, (*map)[it]);
 	}
 
+	class Pointer {
+	  friend class iterator;
+	private:
+	  Reference data;
+	  Pointer(const Key& key, Value& val) : data(key, val) {}
+	public:
+	  Reference* operator->() {return &data;}
+	};
+
 	/** Arrow operator for map.
 	 */	 
-	std::pair<const Key, Value>* operator->() {
-	  static std::pair<const Key, Value> tmp = operator*();
-	  return &tmp;
+	Pointer operator->() {
+	  return Pointer(it, ((*map)[it])); 
 	}
 
 	/** The pre increment operator of the map.
@@ -239,8 +214,9 @@
 	bool operator!=(const_iterator p_it) {
 	  return !(*this == p_it);
 	}
+
 	
-	private:
+      private:
 	Map* map;
 	KeyIt it;
       };
@@ -260,14 +236,15 @@
       class const_iterator {
 	friend class Map;
 	friend class iterator;
-	private:
+      private:
 
 	/** Private constructor to initalize the the iterators returned
 	 *  by the begin() and end().
 	 */
-	const_iterator (Map& pmap, const KeyIt& pit) : map(&pmap), it(pit) {}
+	const_iterator (const Map& pmap, const KeyIt& pit) 
+	  : map(&pmap), it(pit) {}
 
-	public:
+      public:
 
 	/** Default constructor. 
 	 */
@@ -275,21 +252,31 @@
 
 	/** Constructor to convert iterator to const_iterator.
 	 */
-	const_iterator(iterator p_it) {
-	  it = p_it.it;
-	}
+	const_iterator(iterator p_it) : map(p_it.map), it(p_it.it) {}
       
+	typedef extended_pair<const Key&, const Key&, 
+	  const Value&, const Value&> Reference;
+
 	/** Dereference operator for map.
 	 */	 
-	std::pair<const Key, const Value> operator*() const {
-	  return std::pair<const Key, const Value>(it, (*map)[it]);
+	Reference operator*() {
+	  return Reference(it, (*map)[it]);
 	}
 
+
+	class Pointer {
+	  friend class const_iterator;
+	private:
+	  Reference data;
+	  Pointer(const Key& key, const Value& val) : data(key, val) {}
+	public:
+	  Reference* operator->() {return &data;}
+	};
+
 	/** Arrow operator for map.
 	 */	 
-	std::pair<const Key, const Value>* operator->() const {
-	  static std::pair<const Key, const Value> tmp = operator*();
-	  return &tmp;
+	Pointer operator->() {
+	  return Pointer(it, ((*map)[it])); 
 	}
 
 	/** The pre increment operator of the map.
@@ -319,7 +306,8 @@
 	  return !(*this == p_it);
 	}
 	
-	private:
+
+      private:
 	const Map* map;
 	KeyIt it;
       };
@@ -336,7 +324,27 @@
 	return const_iterator(*this, INVALID);
       }
 
-      private:
+    private:
+      
+      void allocate_memory() {
+	int max_id = -1;
+	for (KeyIt it(*getGraph()); getGraph()->valid(it); getGraph()->next(it)) {
+	  int id = getGraph()->id(it);
+	  if (id > max_id) {
+	    max_id = id;
+	  }			
+	}
+	if (max_id == -1) {
+	  capacity = 0;
+	  values = 0;
+	  return;
+	}
+	capacity = 1;
+	while (capacity <= max_id) {
+	  capacity <<= 1;
+	}
+	values = allocator.allocate(capacity);	
+      }      
       int capacity;
       Value* values;
       Allocator allocator;
diff -r 4207f82a1778 -r 32f280a5ed7d src/work/deba/extended_pair.h
--- a/src/work/deba/extended_pair.h	Wed Jul 14 21:16:10 2004 +0000
+++ b/src/work/deba/extended_pair.h	Thu Jul 15 12:15:58 2004 +0000
@@ -1,3 +1,4 @@
+// -*- c++ -*-
 #ifndef EXTENDED_PAIR_H
 #define EXTENDED_PAIR_H
 
@@ -6,10 +7,59 @@
   typedef T1 first_type;
   typedef T2 second_type;
 
+  extended_pair() : first(), second() {}
+
   extended_pair(A1 f, A2 s) : first(f), second(s) {}
 
+  template <class Pair>
+  extended_pair(const Pair& pair) : first(pair.first), second(pair.second) {}
+
   T1 first;
   T2 second;
 };
 
+template <typename T1, typename T2, 
+	  typename LA1, typename LA2, typename RA1, typename RA2>
+bool operator==(const extended_pair<T1, LA1, T2, LA2>& left, 
+		const extended_pair<T1, RA1, T2, RA2>& right) {
+  return left.first == right.first && left.second == right.second;
+}
+
+template <typename T1, typename T2, 
+	  typename LA1, typename LA2, typename RA1, typename RA2>
+bool operator!=(const extended_pair<T1, LA1, T2, LA2>& left, 
+		const extended_pair<T1, RA1, T2, RA2>& right) {
+  return  !(left == right);
+}
+
+template <typename T1, typename T2, 
+	  typename LA1, typename LA2, typename RA1, typename RA2>
+bool operator<(const extended_pair<T1, LA1, T2, LA2>& left, 
+		const extended_pair<T1, RA1, T2, RA2>& right) {
+  if (left.first == right.first) return left.second == right.second;
+  return left.first < right.first;
+}
+
+template <typename T1, typename T2, 
+	  typename LA1, typename LA2, typename RA1, typename RA2>
+bool operator>(const extended_pair<T1, LA1, T2, LA2>& left, 
+		const extended_pair<T1, RA1, T2, RA2>& right) {
+  return right < left;
+}
+
+template <typename T1, typename T2, 
+	  typename LA1, typename LA2, typename RA1, typename RA2>
+bool operator<=(const extended_pair<T1, LA1, T2, LA2>& left, 
+		const extended_pair<T1, RA1, T2, RA2>& right) {
+  return !(right > left);
+}
+
+template <typename T1, typename T2, 
+	  typename LA1, typename LA2, typename RA1, typename RA2>
+bool operator>=(const extended_pair<T1, LA1, T2, LA2>& left, 
+		const extended_pair<T1, RA1, T2, RA2>& right) {
+  return !(right < left);
+}
+
+
 #endif
diff -r 4207f82a1778 -r 32f280a5ed7d src/work/deba/list_graph.h
--- a/src/work/deba/list_graph.h	Wed Jul 14 21:16:10 2004 +0000
+++ b/src/work/deba/list_graph.h	Thu Jul 15 12:15:58 2004 +0000
@@ -12,7 +12,7 @@
 
 #include "invalid.h"
 
-#include "vector_map_factory.h"
+#include "array_map_factory.h"
 #include "map_registry.h"
 
 #include "map_defines.h"
@@ -76,7 +76,7 @@
     class InEdgeIt;
     
     CREATE_MAP_REGISTRIES;
-    CREATE_MAPS(VectorMapFactory);
+    CREATE_MAPS(ArrayMapFactory);
   public:
 
     ListGraph() : nodes(), first_node(-1),
diff -r 4207f82a1778 -r 32f280a5ed7d src/work/deba/main.cpp
--- a/src/work/deba/main.cpp	Wed Jul 14 21:16:10 2004 +0000
+++ b/src/work/deba/main.cpp	Thu Jul 15 12:15:58 2004 +0000
@@ -1,3 +1,4 @@
+// -*- c++ -*-
 #include <iostream>
 #include <cstdlib>
 #include "list_graph.h"
@@ -6,6 +7,7 @@
 using namespace hugo;
 
 
+
 int main() {
   ListGraph g;
   for (int i = 0; i < 10; ++i) {
@@ -22,18 +24,15 @@
   ListGraph::NodeMap<int>::iterator pit;
   for (pit = map.begin(); pit != map.end(); ++pit) {
     cout << g.id(pit->first) << ' ' << pit->second << endl;
-  }
-  /*
-  ListGraph::NodeMap<double> ot_map = map;
-  for (ListGraph::NodeIt it(g); g.valid(it); g.next(it)) {
-    ot_map[it] *= 2.1;
-    cout << ot_map[it] << endl;
-  }
-  ot_map = map;
-  for (ListGraph::NodeIt it(g); g.valid(it); g.next(it)) {
-    ot_map[it] *= 3.1;
-    cout << ot_map[it] << endl;
-    }*/
+    (*pit).second = g.id(pit->first);
+    cout << g.id((*pit).first) << ' ' << (*pit).second << endl;
+  }  
+  const ListGraph::NodeMap<int> const_map = map;
+  ListGraph::NodeMap<int>::const_iterator cit;
+  for (cit = const_map.begin(); cit != const_map.end(); ++cit) {
+    cerr << g.id(cit->first) << ' ' << cit->second << endl;
+    cerr << g.id((*cit).first) << ' ' << (*cit).second << endl;
+  }  
   return 0;
 }
 
diff -r 4207f82a1778 -r 32f280a5ed7d src/work/deba/map_defines.h
--- a/src/work/deba/map_defines.h	Wed Jul 14 21:16:10 2004 +0000
+++ b/src/work/deba/map_defines.h	Thu Jul 15 12:15:58 2004 +0000
@@ -53,10 +53,11 @@
 NodeMap() {} \
 NodeMap(const Graph& g) : Factory::Map<V>(&g, &(g.node_maps)) {} \
 NodeMap(const Graph& g, const V& v) : Factory::Map<V>(g, g.node_maps, v) {} \
-NodeMap(const NodeMap& copy) : Factory::Map<V>(copy) {} \
+NodeMap(const NodeMap& copy) \
+  : Factory::Map<V>(static_cast<const Factory::Map<V>&>(copy)) {} \
 template <typename CMap> NodeMap(const CMap& copy) : Factory::Map<V>(copy) {} \
 NodeMap& operator=(const NodeMap& copy) { \
-  this->Factory::Map<V>::operator=(copy); \
+  this->Factory::Map<V>::operator=(static_cast<Factory::Map<V>&>(copy)); \
   return *this; \
 } \
 template <typename CMap>NodeMap& operator=(const CMap& copy) { \
@@ -78,10 +79,11 @@
 EdgeMap() {} \
 EdgeMap(const Graph& g) : Factory::Map<V>(g, g.edge_maps) {} \
 EdgeMap(const Graph& g, const V& v) : Factory::Map<V>(g, g.node_maps, v) {} \
-EdgeMap(const EdgeMap& copy) : Factory::Map<V>(copy) {} \
+EdgeMap(const EdgeMap& copy) \
+  : Factory::Map<V>(static_cast<Factory::Map<V>&>(copy)) {} \
 template <typename CMap> EdgeMap(const CMap& copy) : Factory::Map<V>(copy) {} \
 EdgeMap& operator=(const EdgeMap& copy) { \
-  this->Factory::Map<V>::operator=(copy); \
+  this->Factory::Map<V>::operator=(static_cast<Factory::Map<V>&>(copy)); \
   return *this; \
 } \
 template <typename CMap>EdgeMap& operator=(const CMap& copy) { \
diff -r 4207f82a1778 -r 32f280a5ed7d src/work/deba/map_registry.h
--- a/src/work/deba/map_registry.h	Wed Jul 14 21:16:10 2004 +0000
+++ b/src/work/deba/map_registry.h	Thu Jul 15 12:15:58 2004 +0000
@@ -91,9 +91,9 @@
 
       const Graph* getGraph() const { return graph; }
 	
-    private:
+    protected:
 		
-      const Graph* graph;
+      const Graph* graph;     
       Registry* registry;
 
       int registry_index;
diff -r 4207f82a1778 -r 32f280a5ed7d src/work/deba/vector_map_factory.h
--- a/src/work/deba/vector_map_factory.h	Wed Jul 14 21:16:10 2004 +0000
+++ b/src/work/deba/vector_map_factory.h	Thu Jul 15 12:15:58 2004 +0000
@@ -1,8 +1,8 @@
+// -*- c++ -*-
 #ifndef VECTOR_MAP_H
 #define VECTOR_MAP_H
 
 #include <vector>
-#include <iostream>
 
 #include "extended_pair.h"
 
@@ -55,9 +55,12 @@
       /** Constructor to use default value to initialize the map. 
        */
       Map(const Graph& g, MapRegistry& r, const Value& v) : MapBase(g, r) {
-	init();
 	for (KeyIt it(*getGraph()); getGraph()->valid(it); getGraph()->next(it)) {
-          set(it, v);
+          int id = getGraph->id(it);
+	  if (id >= container.size) {
+	    container.resize(id + 1);
+	  }
+	  set(it, v);
         }
       }
 
@@ -65,8 +68,11 @@
        */
       template <typename CMap> Map(const CMap& copy) : MapBase(copy) {
 	if (getGraph()) {
-	  init();
 	  for (KeyIt it(*getGraph()); getGraph()->valid(it); getGraph()->next(it)) {
+	    int id = getGraph->id(it);
+	    if (id >= container.size) {
+	      container.resize(id + 1);
+	    }
 	    set(it, copy[it]);
 	  }
 	}
@@ -80,8 +86,11 @@
 	} 
 	this->MapBase::operator=(copy);
 	if (getGraph()) {
-	  init();
 	  for (KeyIt it(*getGraph()); getGraph()->valid(it); getGraph()->next(it)) {
+	    int id = getGraph->id(it);
+	    if (id >= container.size) {
+	      container.resize(id + 1);
+	    }
 	    set(it, copy[it]);
 	  }
 	}
@@ -90,7 +99,6 @@
       /** The destructor of the map.
        */
       virtual ~Map() {
-	destroy();
       }
 		
       /**
@@ -151,21 +159,22 @@
 	 */
 	iterator() {}
 
+	typedef extended_pair<const Key&, const Key&, 
+			      Value&, Value&> Reference;
+
 	/** Dereference operator for map.
 	 */	 
-	std::pair<const Key, Value> operator*() {
-	  return std::pair<const Key, Value>(it, (*map)[it]);
+	Reference operator*() {
+	  return Reference(it, (*map)[it]);
 	}
 
-
 	class Pointer {
 	  friend class iterator;
 	private:
-	  typedef extended_pair<const Key&, const Key&, Value&, Value&> Pair;
-	  Pair data;
+	  Reference data;
 	  Pointer(const Key& key, Value& val) : data(key, val) {}
 	public:
-	  Pair* operator->() {return &data;}
+	  Reference* operator->() {return &data;}
 	};
 
 	/** Arrow operator for map.
@@ -227,7 +236,8 @@
 	/** Private constructor to initalize the the iterators returned
 	 *  by the begin() and end().
 	 */
-	const_iterator (Map& pmap, const KeyIt& pit) : map(&pmap), it(pit) {}
+	const_iterator (const Map& pmap, const KeyIt& pit) 
+	  : map(&pmap), it(pit) {}
 
       public:
 
@@ -237,29 +247,31 @@
 
 	/** Constructor to convert iterator to const_iterator.
 	 */
-	const_iterator(iterator p_it) {
-	  it = p_it.it;
-	}
+	const_iterator(iterator p_it) : map(p_it.map), it(p_it.it) {}
       
+	typedef extended_pair<const Key&, const Key&, 
+	  const Value&, const Value&> Reference;
+
 	/** Dereference operator for map.
 	 */	 
-	std::pair<const Key, const Value> operator*() const {
-	  return std::pair<const Key, const Value>(it, (*map)[it]);
+	Reference operator*() {
+	  return Reference(it, (*map)[it]);
 	}
 
+
 	class Pointer {
 	  friend class const_iterator;
 	private:
-	  typedef extended_pair<const Key&, const Key&, const Value&, const Value&> Pair;
-	  Pair data;
+	  Reference data;
 	  Pointer(const Key& key, const Value& val) : data(key, val) {}
 	public:
-	  Pair* operator->() {return &data;}
+	  Reference* operator->() {return &data;}
 	};
+
 	/** Arrow operator for map.
 	 */	 
-	Pointer operator->() const {
-	  return Pointer(it, (*map)[it]);
+	Pointer operator->() {
+	  return Pointer(it, ((*map)[it])); 
 	}
 
 	/** The pre increment operator of the map.