Changeset 1703:eb90e3d6bddc in lemon-0.x

Timestamp:

10/05/05 15:15:47 (17 years ago)

Author:

Balazs Dezso

Branch:

default

Phase:

public

Convert:

svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2230

Message:

Proper sized map type

Location:

lemon

Files:

• bits/array_map.h (modified) (11 diffs)
• bits/default_map.h (modified) (2 diffs)
• bits/static_map.h (added)
• bits/vector_map.h (modified) (10 diffs)
• full_graph.h (modified) (7 diffs)
• grid_graph.h (modified) (2 diffs)
• hypercube_graph.h (modified) (1 diff)

lemon/bits/array_map.h

@@ -49 +49 @@
     typedef _Item Item;
   public:
+    typedef True AdaptibleTag;
                 
     /// The graph type of the maps. 
@@ -70 +71 @@
   public:
 
+    /// \brief Graph and Registry initialized map constructor.
+    ///
     /// Graph and Registry initialized map constructor.
     ArrayMap(const Graph& _g) : graph(&_g) {
@@ -81 +84 @@
     }
 
-    /// Constructor to use default value to initialize the map. 
-
-    /// It constrates a map and initialize all of the the map. 
-
+    /// \brief Constructor to use default value to initialize the map. 
+    ///
+    /// It constructs a map and initialize all of the the map. 
     ArrayMap(const Graph& _g, const Value& _v) : graph(&_g) {
       Item it;
@@ -95 +97 @@
     }
 
-    /// Constructor to copy a map of the same map type.
-     
+    /// \brief Constructor to copy a map of the same map type.
+    ///
+    /// Constructor to copy a map of the same map type.     
     ArrayMap(const ArrayMap& copy) : Parent(), graph(copy.graph) {
       if (copy.attached()) {
@@ -138 +141 @@
   public:
 
-    ///The subscript operator. The map can be subscripted by the
-    ///actual keys of the graph. 
-     
+    /// \brief The subscript operator. 
+    ///
+    /// The subscript operator. The map can be subscripted by the
+    /// actual keys of the graph. 
     Value& operator[](const Key& key) {
       int id = graph->id(key);
@@ -146 +150 @@
     } 
                 
-
-    ///The const subscript operator. The map can be subscripted by the
-    ///actual keys of the graph. 
-     
+    /// \brief The const subscript operator.
+    ///
+    /// The const subscript operator. The map can be subscripted by the
+    /// actual keys of the graph. 
     const Value& operator[](const Key& key) const {
       int id = graph->id(key);
       return values[id];
     }
-        
+
+    /// \brief Setter function of the map.
+    /// 
     /// Setter function of the map. Equivalent with map[key] = val.
     /// This is a compatibility feature with the not dereferable maps.
-     
     void set(const Key& key, const Value& val) {
       (*this)[key] = val;
@@ -163 +168 @@
 
   protected:
-    
+
     /// Add a new key to the map. It called by the map registry.
-     
-    void add(const Key& key) {
+         
+    virtual void add(const Key& key) {
       int id = graph->id(key);
       if (id >= capacity) {
@@ -189 +194 @@
     }
 
-    void add(const std::vector<Key>& keys) {
+    virtual void add(const std::vector<Key>& keys) {
       int max_id = -1;
       for (int i = 0; i < (int)keys.size(); ++i) {
@@ -230 +235 @@
     /// Erase a key from the map. It called by the map registry.
      
-    void erase(const Key& key) {
+    virtual void erase(const Key& key) {
       int id = graph->id(key);
       allocator.destroy(&(values[id]));
     }
 
-    void erase(const std::vector<Key>& keys) {
+    virtual void erase(const std::vector<Key>& keys) {
       for (int i = 0; i < (int)keys.size(); ++i) {
         int id = graph->id(keys[i]);
@@ -242 +247 @@
     }
 
-    void build() {
+    virtual void build() {
       allocate_memory();
       Item it;
@@ -251 +256 @@
     }
 
-    void clear() {      
+    virtual void clear() {      
       if (capacity != 0) {
         Item it;

lemon/bits/default_map.h

@@ -29 +29 @@
 namespace lemon {
 
-  /// \addtogroup graphmapfactory
-  /// @{
 
   template <typename _Graph, typename _Item, typename _Value>
@@ -269 +267 @@
   };
 
-  /// @}
 }
 

lemon/bits/vector_map.h

@@ -45 +45 @@
   ///
   /// \param Registry The AlterationNotifier that will notify this map.
-  /// \param IdMap The IdMap type of the graph items.
+  /// \param Item The item type of the graph items.
   /// \param Value The value type of the map.
   /// 
   /// \author Balazs Dezso
         
-
   template <
     typename _Graph, 
@@ -58 +57 @@
   class VectorMap : public AlterationNotifier<_Item>::ObserverBase {
   public:
+
+    typedef True AdaptibleTag;
                 
     /// The graph type of the map. 
@@ -94 +95 @@
     typedef True FullTypeTag;
 
-    /// Constructor to attach the new map into the registry.
-
-    /// It construates a map and attachs it into the registry.
+    /// \brief Constructor to attach the new map into the registry.
+    ///
+    /// It constructs a map and attachs it into the registry.
     /// It adds all the items of the graph to the map.
-     
     VectorMap(const Graph& _g) : graph(&_g) {
       attach(_g.getNotifier(_Item()));
@@ -104 +104 @@
     }
 
-    /// Constructor uses given value to initialize the map. 
-
-    /// It construates a map uses a given value to initialize the map. 
+    /// \brief Constructor uses given value to initialize the map. 
+    ///
+    /// It constructs a map uses a given value to initialize the map. 
     /// It adds all the items of the graph to the map.
-     
     VectorMap(const Graph& _g, const Value& _v) : graph(&_g) { 
       attach(_g.getNotifier(_Item()));
@@ -114 +113 @@
     }
 
+    /// \brief Copy constructor
+    ///
+    /// Copy constructor.
     VectorMap(const VectorMap& _copy) 
       : Parent(), graph(_copy.getGraph()) {
@@ -122 +124 @@
     }
 
+    /// \brief Destrcutor
+    ///
+    /// Destructor.
     virtual ~VectorMap() {
       if (attached()) {
@@ -145 +150 @@
   public:
 
-    /// The subcript operator.
-
+    /// \brief The subcript operator.
+    ///
     /// The subscript operator. The map can be subscripted by the
-    /// actual items of the graph. 
-     
+    /// actual items of the graph.      
     Reference operator[](const Key& key) {
       return container[graph->id(key)];
     } 
                 
-    /// The const subcript operator.
-
+    /// \brief The const subcript operator.
+    ///
     /// The const subscript operator. The map can be subscripted by the
     /// actual items of the graph. 
-     
     ConstReference operator[](const Key& key) const {
       return container[graph->id(key)];
@@ -164 +167 @@
 
 
-    /// The setter function of the map.
-
+    /// \brief The setter function of the map.
+    ///
     /// It the same as operator[](key) = value expression.
-    ///
     void set(const Key& key, const Value& value) {
       (*this)[key] = value;
@@ -177 +179 @@
     ///         
     /// It adds a new key to the map. It called by the observer registry
-    /// and it overrides the add() member function of the observer base.
-     
-    void add(const Key& key) {
+    /// and it overrides the add() member function of the observer base.     
+    virtual void add(const Key& key) {
       int id = graph->id(key);
       if (id >= (int)container.size()) {
@@ -186 +187 @@
     }
 
-    /// Erases a key from the map.
-                
+    /// \brief Erase a key from the map.
+    ///
     /// Erase a key from the map. It called by the observer registry
     /// and it overrides the erase() member function of the observer base.     
-    void erase(const Key&) {}
-
-    /// Buildes the map.
-                
+    virtual void erase(const Key&) {}
+
+    /// \brief Buildes the map.
+    /// 
     /// It buildes the map. It called by the observer registry
     /// and it overrides the build() member function of the observer base.
-
-    void build() { 
+    virtual void build() { 
       container.resize(graph->maxId(_Item()) + 1);
     }
 
-    /// Clear the map.
-
+    /// \brief Clear the map.
+    ///
     /// It erase all items from the map. It called by the observer registry
     /// and it overrides the clear() member function of the observer base.     
-    void clear() { 
+    virtual void clear() { 
       container.clear();
     }

lemon/full_graph.h

@@ -23 +23 @@
 #include <lemon/bits/iterable_graph_extender.h>
 #include <lemon/bits/alteration_notifier.h>
-#include <lemon/bits/default_map.h>
+#include <lemon/bits/static_map.h>
 
 #include <lemon/bits/undir_graph_extender.h>
@@ -196 +196 @@
   typedef IterableGraphExtender<AlterableFullGraphBase> 
   IterableFullGraphBase;
-  typedef MappableGraphExtender<
+  typedef StaticMappableGraphExtender<
     IterableGraphExtender<
     AlterableGraphExtender<FullGraphBase> > > ExtendedFullGraphBase;
@@ -299 +299 @@
     /// the next edge from \c u to \c v after \c prev.
     /// \return The found edge or INVALID if there is no such an edge.
-    Edge findEdge(Node u,Node v, Edge prev = INVALID) 
-    {
-      return prev.id == -1 ? Edge(*this, u.id, v.id) : INVALID;
-    }
+    Edge findEdge(Node u, Node v, Edge prev = INVALID) const {
+      if (prev.id != -1 || u.id <= v.id) return -1;
+      return Edge(u.id * (u.id - 1) / 2 + v.id);
+    }
+
+    typedef True FindEdgeTag;
     
       
@@ -329 +331 @@
       Edge(int _id) : id(_id) {}
 
-      Edge(const UndirFullGraphBase& _graph, int source, int target) 
-        : id(_graph._nodeNum * target+source) {}
     public:
       Edge() { }
@@ -340 +340 @@
 
     void first(Node& node) const {
-      node.id = _nodeNum-1;
+      node.id = _nodeNum - 1;
     }
 
@@ -348 +348 @@
 
     void first(Edge& edge) const {
-      edge.id = _edgeNum-1;
+      edge.id = _edgeNum - 1;
     }
 
@@ -356 +356 @@
 
     void firstOut(Edge& edge, const Node& node) const {      
-      edge.id = node.id != 0 ? node.id * (node.id - 1) / 2 : -1;
+      int src = node.id;
+      int trg = 0;
+      edge.id = (trg < src ? src * (src - 1) / 2 + trg : -1);
     }
 
     /// \todo with specialized iterators we can make faster iterating
-    void nextOut(Edge& e) const {
-      int source = ((int)sqrt((double)(1 + 8 * e.id)) + 1) / 2;;
-      int target = e.id - (source) * (source - 1) / 2; 
-      ++target;
-      e.id = target < source ? source * (source - 1) / 2 + target : -1;
+    void nextOut(Edge& edge) const {
+      int src = source(edge).id;
+      int trg = target(edge).id;
+      ++trg;
+      edge.id = (trg < src ? src * (src - 1) / 2 + trg : -1);
     }
 
     void firstIn(Edge& edge, const Node& node) const {
-      edge.id = node.id * (node.id + 1) / 2 - 1;
-    }
-    
-    void nextIn(Edge& e) const {
-      int source = ((int)sqrt((double)(1 + 8 * e.id)) + 1) / 2;;
-      int target = e.id - (source) * (source - 1) / 2; ++target;
-      ++source;
-      e.id = source < _nodeNum ? source * (source - 1) / 2 + target : -1;
+      int src = node.id + 1;
+      int trg = node.id;
+      edge.id = (src < _nodeNum ? src * (src - 1) / 2 + trg : -1);
+    }
+    
+    void nextIn(Edge& edge) const {
+      int src = source(edge).id;
+      int trg = target(edge).id;
+      ++src;
+      edge.id = (src < _nodeNum ? src * (src - 1) / 2 + trg : -1);
     }
 
   };
 
-  typedef MappableUndirGraphExtender<
+  typedef StaticMappableUndirGraphExtender<
     IterableUndirGraphExtender<
     AlterableUndirGraphExtender<

lemon/grid_graph.h

@@ -24 +24 @@
 #include <lemon/bits/iterable_graph_extender.h>
 #include <lemon/bits/alteration_notifier.h>
-#include <lemon/bits/default_map.h>
+#include <lemon/bits/static_map.h>
 
 #include <lemon/bits/undir_graph_extender.h>
@@ -340 +340 @@
 
 
-  typedef MappableUndirGraphExtender<
+  typedef StaticMappableUndirGraphExtender<
     IterableUndirGraphExtender<
     AlterableUndirGraphExtender<

lemon/hypercube_graph.h

@@ -233 +233 @@
 
 
-  typedef MappableGraphExtender<
+  typedef StaticMappableGraphExtender<
     IterableGraphExtender<
     AlterableGraphExtender<