# HG changeset patch
# User deba
# Date 1084436439 0
# Node ID 6cc21a9c9fdaf679b72b827a0ef473eee6378620
# Parent  0015642b09902a66b82e9c1416e71f2e1ca7096c


diff -r 0015642b0990 -r 6cc21a9c9fda src/work/deba/array_map_factory.h
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/work/deba/array_map_factory.h	Thu May 13 08:20:39 2004 +0000
@@ -0,0 +1,123 @@
+#ifndef ARRAY_MAP_H
+#define ARRAY_MAP_H
+
+#include <memory>
+
+#include "map_base.h"
+
+#include <iostream>
+using namespace std;
+
+namespace hugo {
+	
+	template <typename G, typename K, typename KIt>
+	class ArrayMapFactory {
+	
+	
+	public:
+		
+		typedef G Graph;
+		typedef K Key;
+		typedef KIt KeyIt;
+		
+		template <typename V, typename A = allocator<V> > 
+		class Map : public MapBase<G, K, KIt> {
+		public:
+			typedef V Value;
+			typedef typename _Alloc_traits<V, A>::_Alloc_type _Alloc_type;
+
+	
+			Map() : values(0), capacity(0) {}
+			
+			Map(Graph& g, MapRegistry<G, K, KIt>& r) 
+				: MapBase<G, K, KIt>(g, r) {
+				int max_id = -1;
+				for (KeyIt it(*graph); graph->valid(it); graph->next(it)) {
+					int id = graph->id(it);
+					if (id > max_id) {
+						max_id = id;
+					}				
+				}
+				if (max_id == -1) {
+					capacity = 0;
+					values = 0;
+					return;
+				}
+				int capacity = 1;
+				while (capacity <= max_id) {
+					capacity <<= 1;
+				}
+				Value* values = reinterpret_cast<Value*>(new char[capacity*sizeof(Value)]);
+				for (KeyIt it(*graph); graph->valid(it); graph->next(it)) {
+					int id = graph->id(it);
+					new(&(values[id])) Value();
+				}								
+				cerr << capacity << endl;	
+			}
+				
+			virtual ~Map() {
+				destroy();
+				delete[] reinterpret_cast<char*>(values);
+				values = 0;
+				capacity = 0;
+			}
+	
+	
+			Value& operator[](const K& key) {
+				int id = graph->id(key);
+				return values[id];
+			} 
+		
+			const Value& operator[](const K& key) const {
+				int id = graph->id(key);
+				return values[id];
+			}
+	
+			const Value& get(const K& key) const {
+				int id = graph->id(key);
+				return values[id];
+			} 
+		
+			void set(const K& key, const Value& val) {
+				int id = graph->id(key);
+				values[id] = val;
+			}
+		
+			void add(const K& key) {
+				cerr << capacity << endl;
+				int id = graph->id(key);
+				if (id >= capacity) {
+					int new_capacity = (capacity == 0 ? 1 : capacity);
+					while (new_capacity <= id) {
+						new_capacity <<= 1;
+					}
+					Value* new_values = reinterpret_cast<Value*>(new char[new_capacity*sizeof(Value)]);;
+					for (KeyIt it(*graph); graph->valid(it); graph->next(it)) {
+						int jd = graph->id(it);
+						if (id != jd) {
+							new(&(new_values[jd])) Value(values[jd]);
+						}
+					}
+					if (capacity != 0) delete[] reinterpret_cast<char *>(values);
+					values = new_values;
+					capacity = new_capacity;
+				}
+				cerr << id << ' ' << capacity << endl;
+				new(&(values[id])) Value();
+			}
+		
+			void erase(const K& key) {
+				int id = graph->id(key);
+				values[id].~Value();
+			}
+	
+		private:
+			int capacity;
+			Value* values;
+								
+		};
+		
+	};
+}
+
+#endif
diff -r 0015642b0990 -r 6cc21a9c9fda src/work/deba/main.cpp
--- a/src/work/deba/main.cpp	Wed May 12 14:07:00 2004 +0000
+++ b/src/work/deba/main.cpp	Thu May 13 08:20:39 2004 +0000
@@ -7,18 +7,18 @@
 
 
 int main() {
-	ListGraph g;
-	for (int i = 0; i < 3; ++i) {
-		ListGraph::Node node = g.addNode();
-	}
-	ListGraph::NodeMapFactory::Map<int> map(g, g.node_maps);
-	for (int i = 0; i < 10; ++i) {
-		ListGraph::Node node = g.addNode();
-		map[node] = rand()%100;
-	}
-	for (ListGraph::NodeIt it(g); g.valid(it); g.next(it)) {
-		cout << map[it] << endl;
-	}
-	return 0;
+  ListGraph g;
+  for (int i = 0; i < 10; ++i) {
+    ListGraph::Node node = g.addNode();
+  }
+  ListGraph::NodeMapFactory::Map<int> map(g, g.node_maps);
+  for (int i = 0; i < 10; ++i) {
+    ListGraph::Node node = g.addNode();
+    map[node] = rand()%100;
+  }
+  for (ListGraph::NodeIt it(g); g.valid(it); g.next(it)) {
+    cout << map[it] << endl;
+  }
+  return 0;
 }
 
diff -r 0015642b0990 -r 6cc21a9c9fda src/work/deba/map_base.h
--- a/src/work/deba/map_base.h	Wed May 12 14:07:00 2004 +0000
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,133 +0,0 @@
-#ifndef MAP_BASE_H
-#define MAP_BASE_H
-
-using namespace std;
-
-/**
-	Template base class for implementing mapping on nodes and edges.
-	\param The first template parameter is the Graph class.
-	\param The second template parameter is the key type.
-	\param The third template parameter is an iterator on
-		the keys.
-*/
-
-
-namespace hugo {
-	template <typename G, typename K, typename KIt>
-	class MapBase;
-}
-
-#include "map_registry.h"
-
-namespace hugo {
-
-	template <typename G, typename K, typename KIt>
-	class MapBase {
-	public:
-		typedef G Graph;
-		typedef MapRegistry<G, K, KIt> Registry;
-		typedef K Key;
-		typedef KIt KeyIt;
-	
-		friend class Registry;
-		
-		/** 
-			Default constructor.
-		*/	
-		
-		MapBase() : graph(0), registry(0) {}
-
-		/** 
-			Simple constructor to register into a graph registry.
-		*/
-	
-		MapBase(Graph& g, Registry& r) : graph(&g), registry(0) {
-			r.attach(*this);
-		}
-
-		/** 
-			Copy constructor with registering into the map.
-		*/	
-	
-		MapBase(const MapBase& copy) : registry(0), graph(copy.graph) {
-			if (copy.registry) {
-				copy.registry->attach(*this);
-			}
-		} 
-	
-		/** 
-			Assign operator.
-		*/	
-
-		const MapBase& operator=(const MapBase& copy) {
-			if (registry) {
-				registry->detach(*this);
-			}
-			graph = copy.graph;
-			if (copy.registry) {
-				copy.registry->attach(*this);
-			}
-		}
-	
-
-		/** 
-			Destructor.
-		*/		
-
-		virtual ~MapBase() {
-			if (registry) {
-				registry->detach(*this);
-			}
-		}
-	
-	protected:
-		
-		Graph* graph;
-		Registry* registry;
-
-		int registry_index;
-	
-		/**
-			Helper function to implement constructors in the subclasses.
-		*/
-	
-		virtual void init() {
-			for (KeyIt it(*graph); graph->valid(it); graph->next(it)) {
-				add(it);
-			}
-		}
-	
-		/**
-			Helper function to implement the destructor in the subclasses.
-		*/
-	
-		virtual void destroy() {
-			for (KeyIt it(*graph); graph->valid(it); graph->next(it)) {
-				erase(it);
-			}
-		}
-	
-		/** 
-			The add member function should be overloaded in the subclasses.
-			\e Add extends the map with the new node.
-		*/
-	
-		virtual void add(const Key&) = 0;	
-		/** 
-			The erase member function should be overloaded in the subclasses.
-			\e Erase removes the node from the map.
-		*/
-	
-		virtual void erase(const Key&) = 0;
-	
-		/**
-			Exception class to throw at unsupported operation.
-		*/
-	
-		class NotSupportedOperationException {};
-
-	};
-	
-}
-
-#endif
diff -r 0015642b0990 -r 6cc21a9c9fda src/work/deba/map_registry.h
--- a/src/work/deba/map_registry.h	Wed May 12 14:07:00 2004 +0000
+++ b/src/work/deba/map_registry.h	Thu May 13 08:20:39 2004 +0000
@@ -5,91 +5,195 @@
 
 using namespace std;
 
-
-namespace hugo {
-	template <typename G, typename K, typename KIt>
-	class MapRegistry;
-}
-
-#include "map_base.h"
+/** 
+    Registry class to register edge or node maps in the graph. The
+    registry helps you to implement an observer pattern. If you add
+    or erase an edge or node you must notify all the maps about the
+    event.
+*/
 
 namespace hugo {
 
-	template <typename G, typename K, typename KIt>
-	class MapRegistry {
-	public:
-		typedef G Graph;
-		typedef K Key;
-		typedef KIt KeyIt;
+  template <typename G, typename K, typename KIt>
+  class MapRegistry {
+  public:
+    typedef G Graph;
+    typedef K Key;
+    typedef KIt KeyIt;
 	
-		typedef MapBase<Graph, Key, KIt> Map;
-		friend class Base;
+
+
+    class MapBase {
+    public:
+      typedef G Graph;
+      typedef MapRegistry<G, K, KIt> Registry;
+      typedef K Key;
+      typedef KIt KeyIt;
 	
-	protected:
+      friend class Registry;
+		
+      /** 
+	  Default constructor.
+      */	
+		
+      MapBase() : graph(0), registry(0) {}
+
+      /** 
+	  Simple constructor to register into a graph registry.
+      */
 	
-		typedef std::vector<Map*> Container; 
-	  Container container;
+      MapBase(Graph& g, Registry& r) : graph(&g), registry(0) {
+	r.attach(*this);
+      }
+
+      /** 
+	  Copy constructor with registering into the map.
+      */	
+	
+      MapBase(const MapBase& copy) : registry(0), graph(copy.graph) {
+	if (copy.registry) {
+	  copy.registry->attach(*this);
+	}
+      } 
+	
+      /** 
+	  Assign operator.
+      */	
+
+      const MapBase& operator=(const MapBase& copy) {
+	if (registry) {
+	  registry->detach(*this);
+	}
+	graph = copy.graph;
+	if (copy.registry) {
+	  copy.registry->attach(*this);
+	}
+      }
+	
+
+      /** 
+	  Destructor.
+      */		
+
+      virtual ~MapBase() {
+	if (registry) {
+	  registry->detach(*this);
+	}
+      }
+	
+    protected:
+		
+      Graph* graph;
+      Registry* registry;
+
+      int registry_index;
+	
+      /**
+	 Helper function to implement constructors in the subclasses.
+      */
+	
+      virtual void init() {
+	for (KeyIt it(*graph); graph->valid(it); graph->next(it)) {
+	  add(it);
+	}
+      }
+	
+      /**
+	 Helper function to implement the destructor in the subclasses.
+      */
+	
+      virtual void destroy() {
+	for (KeyIt it(*graph); graph->valid(it); graph->next(it)) {
+	  erase(it);
+	}
+      }
+	
+      /** 
+	  The add member function should be overloaded in the subclasses.
+	  \e Add extends the map with the new node.
+      */
+	
+      virtual void add(const Key&) = 0;	
+      /** 
+	  The erase member function should be overloaded in the subclasses.
+	  \e Erase removes the node from the map.
+      */
+	
+      virtual void erase(const Key&) = 0;
+	
+      /**
+	 Exception class to throw at unsupported operation.
+      */
+	
+      class NotSupportedOperationException {};
+
+    };
+	
+  protected:
+	
+    typedef std::vector<MapBase*> Container; 
+    Container container;
 
 		
-	public:
+    public:
 	
-		MapRegistry() {}
+    MapRegistry() {}
 	
-		MapRegistry(const MapRegistry&) {}
+    MapRegistry(const MapRegistry&) {}
 		
-		MapRegistry& operator=(const MapRegistry&) {
-			for (it = container.begin(); it != container.end(); ++it) {
-				(*it)->destroy();
-				(*it)->graph = 0;
-				(*it)->registry = 0;
-			}
-		}
+    MapRegistry& operator=(const MapRegistry&) {
+      for (it = container.begin(); it != container.end(); ++it) {
+	(*it)->destroy();
+	(*it)->graph = 0;
+	(*it)->registry = 0;
+      }
+    }
 				
-		~MapRegistry() {
-			typename Container::iterator it;
-			for (it = container.begin(); it != container.end(); ++it) {
-				(*it)->destroy();
-				(*it)->registry = 0;
-				(*it)->graph = 0;
-			}
-		}
+    ~MapRegistry() {
+      typename Container::iterator it;
+      for (it = container.begin(); it != container.end(); ++it) {
+	(*it)->destroy();
+	(*it)->registry = 0;
+	(*it)->graph = 0;
+      }
+    }
 	
 	
-	public:
+    public:
 	
-		void attach(Map& map) {
-			if (map.registry) {
-				map.registry->detach(map);
-			}
-			container.push_back(&map);
-			map.registry = this;
-			map.registry_index = container.size()-1;
-		} 
+    void attach(MapBase& map) {
+      if (map.registry) {
+	map.registry->detach(map);
+      }
+      container.push_back(&map);
+      map.registry = this;
+      map.registry_index = container.size()-1;
+    } 
 	
-		void detach(Map& map) {
-			container.back()->registry_index = map.registry_index; 
-			container[map.registry_index] = container.back();
-			container.pop_back();
-			map.registry = 0;
-			map.graph = 0;
-		}
+    void detach(MapBase& map) {
+      container.back()->registry_index = map.registry_index; 
+      container[map.registry_index] = container.back();
+      container.pop_back();
+      map.registry = 0;
+      map.graph = 0;
+    }
 	
 		
-		virtual void add(Key& key) {
-			typename Container::iterator it;
-			for (it = container.begin(); it != container.end(); ++it) {
-				(*it)->add(key);
-			}
-		}	
+    virtual void add(Key& key) {
+      typename Container::iterator it;
+      for (it = container.begin(); it != container.end(); ++it) {
+	(*it)->add(key);
+      }
+    }	
 		
-		virtual void erase(Key& key) {
-			typename Container::iterator it;
-			for (it = container.begin(); it != container.end(); ++it) {
-				(*it)->erase(key);
-			}
-		}
+    virtual void erase(Key& key) {
+      typename Container::iterator it;
+      for (it = container.begin(); it != container.end(); ++it) {
+	(*it)->erase(key);
+      }
+    }
 
-	};
+  };
 
 }
 
diff -r 0015642b0990 -r 6cc21a9c9fda src/work/deba/test_graph.h
--- a/src/work/deba/test_graph.h	Wed May 12 14:07:00 2004 +0000
+++ b/src/work/deba/test_graph.h	Thu May 13 08:20:39 2004 +0000
@@ -30,28 +30,26 @@
     class InEdgeIt;
     class SymEdgeIt;
     
-//    template <typename T> class NodeMap;
-//    template <typename T> class EdgeMap;
+    //    template <typename T> class NodeMap;
+    //    template <typename T> class EdgeMap;
   private:
-//    template <typename T> friend class NodeMap;
- //   template <typename T> friend class EdgeMap;
+    //    template <typename T> friend class NodeMap;
+    //   template <typename T> friend class EdgeMap;
  
   private:
 
  
-	public:
+  public:
 	
-		typedef MapBase<ListGraph, Node, NodeIt> NodeMapBase;
-		typedef MapRegistry<ListGraph, Node, NodeIt> NodeMapRegistry;
-		typedef VectorMapFactory<ListGraph, Node, NodeIt> NodeMapFactory;
-		NodeMapRegistry node_maps;
+    typedef MapRegistry<ListGraph, Node, NodeIt> NodeMapRegistry;
+    typedef VectorMapFactory<NodeMapRegistry> NodeMapFactory;
+    NodeMapRegistry node_maps;
 
 
 
-		typedef MapBase<ListGraph, Edge, EdgeIt> EdgeMapBase;
-		typedef MapRegistry<ListGraph, Edge, EdgeIt> EdgeMapRegistry;
-		typedef VectorMapFactory<ListGraph, Edge, EdgeIt> EdgeMapFactory;
-		EdgeMapRegistry edge_maps;
+    typedef MapRegistry<ListGraph, Edge, EdgeIt> EdgeMapRegistry;
+    typedef VectorMapFactory<EdgeMapRegistry> EdgeMapFactory;
+    EdgeMapRegistry edge_maps;
  
 
     int node_id;
@@ -302,27 +300,27 @@
     /* adding nodes and edges */
 
     Node addNode() { 
-			Node n = _add_node();
-			node_maps.add(n);
-			return n; 
-		}
+      Node n = _add_node();
+      node_maps.add(n);
+      return n; 
+    }
     Edge addEdge(Node u, Node v) {
-			Edge e = _add_edge(u.node, v.node);
-			edge_maps.add(e);
+      Edge e = _add_edge(u.node, v.node);
+      edge_maps.add(e);
       return e; 
     }
 
     void erase(Node i) { 
-			node_maps.erase(i);
+      node_maps.erase(i);
       while (first<OutEdgeIt>(i).valid()) erase(first<OutEdgeIt>(i));
       while (first<InEdgeIt>(i).valid()) erase(first<InEdgeIt>(i));
       _delete_node(i.node); 
     }
   
     void erase(Edge e) { 
-			edge_maps.erase(e);
-			_delete_edge(e.edge); 
-		}
+      edge_maps.erase(e);
+      _delete_edge(e.edge); 
+    }
 
     void clear() { 
       while (first<NodeIt>().valid()) erase(first<NodeIt>());
@@ -510,42 +508,42 @@
 
   };
 
-//   template< typename T >
-//   T ListGraph::first() const { 
-//     std::cerr << "Invalid use of template<typemane T> T ListGraph::first<T>();" << std::endl; 
-//     return T(); 
-//   }
+  //   template< typename T >
+  //   T ListGraph::first() const { 
+  //     std::cerr << "Invalid use of template<typemane T> T ListGraph::first<T>();" << std::endl; 
+  //     return T(); 
+  //   }
 
-//   template<>
-//   ListGraph::NodeIt ListGraph::first<ListGraph::NodeIt>() const { 
-//     return firstNode(); 
-//   }
+  //   template<>
+  //   ListGraph::NodeIt ListGraph::first<ListGraph::NodeIt>() const { 
+  //     return firstNode(); 
+  //   }
 
-//   template<>
-//   ListGraph::EdgeIt ListGraph::first<ListGraph::EdgeIt>() const { 
-//     return firstEdge(); 
-//   }
+  //   template<>
+  //   ListGraph::EdgeIt ListGraph::first<ListGraph::EdgeIt>() const { 
+  //     return firstEdge(); 
+  //   }
 
-//   template< typename T >
-//   T ListGraph::first(ListGraph::Node v) const {
-//     std::cerr << "Invalid use of template<typemane T> T ListGraph::first<T>(ListGRaph::Node);" << std::endl; 
-//     return T(); 
-//   } 
+  //   template< typename T >
+  //   T ListGraph::first(ListGraph::Node v) const {
+  //     std::cerr << "Invalid use of template<typemane T> T ListGraph::first<T>(ListGRaph::Node);" << std::endl; 
+  //     return T(); 
+  //   } 
 
-//   template<>
-//   ListGraph::OutEdgeIt ListGraph::first<ListGraph::OutEdgeIt>(const ListGraph::Node v) const { 
-//     return firstOutEdge(v); 
-//   }
+  //   template<>
+  //   ListGraph::OutEdgeIt ListGraph::first<ListGraph::OutEdgeIt>(const ListGraph::Node v) const { 
+  //     return firstOutEdge(v); 
+  //   }
 
-//   template<>
-//   ListGraph::InEdgeIt ListGraph::first<ListGraph::InEdgeIt>(const ListGraph::Node v) const { 
-//     return firstInEdge(v); 
-//   }
+  //   template<>
+  //   ListGraph::InEdgeIt ListGraph::first<ListGraph::InEdgeIt>(const ListGraph::Node v) const { 
+  //     return firstInEdge(v); 
+  //   }
 
-//   template<>
-//   ListGraph::SymEdgeIt ListGraph::first<ListGraph::SymEdgeIt>(const ListGraph::Node v) const { 
-//     return firstSymEdge(v); 
-//   }
+  //   template<>
+  //   ListGraph::SymEdgeIt ListGraph::first<ListGraph::SymEdgeIt>(const ListGraph::Node v) const { 
+  //     return firstSymEdge(v); 
+  //   }
 
 
 } //namespace hugo
diff -r 0015642b0990 -r 6cc21a9c9fda src/work/deba/vector_map_factory.h
--- a/src/work/deba/vector_map_factory.h	Wed May 12 14:07:00 2004 +0000
+++ b/src/work/deba/vector_map_factory.h	Thu May 13 08:20:39 2004 +0000
@@ -3,73 +3,73 @@
 
 #include <vector>
 
-#include "map_base.h"
+#include "map_registry.h"
 
 namespace hugo {
 	
-	template <typename G, typename K, typename KIt>
-	class VectorMapFactory {
+  template <typename MapRegistry>
+  class VectorMapFactory {
+  public:
+		
+    typedef typename MapRegistry::Graph Graph;
+    typedef typename MapRegistry::Key Key;
+    typedef typename MapRegistry::KeyIt KeyIt;
+
+    typedef typename MapRegistry::MapBase MapBase;
+		
+    template <typename V> 
+      class Map : public MapBase {
+      public:
+      typedef V Value;
 	
+      Map() {}
+			
+      Map(Graph& g, MapRegistry& r) : MapBase(g, r) {
+	init();
+      }
+			
+						
+      virtual ~Map() {
+	destroy();
+      }
 	
-	public:
+	
+      Value& operator[](const Key& key) {
+	int id = graph->id(key);
+	return container[id];
+      } 
 		
-		typedef G Graph;
-		typedef K Key;
-		typedef KIt KeyIt;
+      const Value& operator[](const Key& key) const {
+	int id = graph->id(key);
+	return container[id];
+      }
+	
+      const Value& get(const Key& key) const {
+	int id = graph->id(key);
+	return container[id];
+      } 
 		
-		template <typename V> 
-		class Map : public MapBase<G, K, KIt> {
-		public:
-			typedef V Value;
+      void set(const Key& key, const Value& val) {
+	int id = graph->id(key);
+	container[id] = val;
+      }
+		
+      void add(const Key& key) {
+	int id = graph->id(key);
+	if (id >= container.size()) {
+	  container.resize(id + 1);
+	}
+      }
+		
+      void erase(const Key& key) {}
 	
-			Map() {}
-			
-			Map(Graph& g, MapRegistry<G, K, KIt>& r) 
-				: MapBase<G, K, KIt>(g, r) {
-				init();
-			}
-				
-			virtual ~Map() {
-				destroy();
-			}
-	
-	
-			Value& operator[](const K& key) {
-				int id = graph->id(key);
-				return container[id];
-			} 
+      private:
+      typedef std::vector<Value> Container;
 		
-			const Value& operator[](const K& key) const {
-				int id = graph->id(key);
-				return container[id];
-			}
-	
-			const Value& get(const K& key) const {
-				int id = graph->id(key);
-				return container[id];
-			} 
+      Container container;
+    };
 		
-			void set(const K& key, const Value& val) {
-				int id = graph->id(key);
-				container[id] = val;
-			}
-		
-			void add(const K& key) {
-				int id = graph->id(key);
-				if (id >= container.size()) {
-					container.resize(id + 1);
-				}
-			}
-		
-			void erase(const K& key) {}
-	
-		private:
-			typedef std::vector<Value> Container;
-		
-			Container container;
-		};
-		
-	};
+  };
 }
 
 #endif