1.1 --- a/src/lemon/bits/alteration_notifier.h	Wed May 11 17:36:25 2005 +0000
     1.2 +++ b/src/lemon/bits/alteration_notifier.h	Sat May 14 17:20:40 2005 +0000
     1.3 @@ -29,8 +29,9 @@
     1.4    /// \addtogroup graphmaps
     1.5    /// @{
     1.6  
     1.7 -  /// Registry class to register objects observes alterations in the graph.
     1.8 -
     1.9 +  /// \brief Registry class to register objects observes alterations in 
    1.10 +  /// the graph.
    1.11 +  ///
    1.12    /// This class is a registry for the objects which observe the
    1.13    /// alterations in a container. The alteration observers can be attached
    1.14    /// to and detached from the registry. The observers have to inherit
    1.15 @@ -38,8 +39,7 @@
    1.16    /// the virtual functions in that.
    1.17    ///
    1.18    /// The most important application of the alteration observing is the
    1.19 -  /// dynamic map implementation when the observers are observing the
    1.20 -  /// alterations in the graph.
    1.21 +  /// dynamic map implementation.
    1.22    ///
    1.23    /// \param _Item The item type what the observers are observing, usually
    1.24    /// edge or node.
    1.25 @@ -74,16 +74,16 @@
    1.26  
    1.27        friend class AlterationNotifier;
    1.28  
    1.29 -      /// Default constructor.
    1.30 -
    1.31 +      /// \brief Default constructor.
    1.32 +      ///
    1.33        /// Default constructor for ObserverBase.
    1.34        /// 
    1.35        ObserverBase() : registry(0) {}
    1.36  
    1.37        virtual ~ObserverBase() {}
    1.38  
    1.39 -      /// Attaches the observer into an AlterationNotifier.
    1.40 -
    1.41 +      /// \brief Attaches the observer into an AlterationNotifier.
    1.42 +      ///
    1.43        /// This member attaches the observer into an AlterationNotifier.
    1.44        ///
    1.45        void attach(AlterationNotifier& r) {
    1.46 @@ -91,8 +91,8 @@
    1.47  	registry->attach(*this);
    1.48        }
    1.49  
    1.50 -      /// Detaches the observer into an AlterationNotifier.
    1.51 -
    1.52 +      /// \brief Detaches the observer into an AlterationNotifier.
    1.53 +      ///
    1.54        /// This member detaches the observer from an AlterationNotifier.
    1.55        ///
    1.56        void detach() {
    1.57 @@ -131,8 +131,20 @@
    1.58        /// is added to the container. It have to be overrided in the
    1.59        /// subclasses.
    1.60  	
    1.61 -      virtual void add(const Item&) = 0;	
    1.62 +      virtual void add(const Item&) = 0;
    1.63  
    1.64 +      /// \brief The member function to notificate the observer about 
    1.65 +      /// simulitem is added to the container.
    1.66 +      ///
    1.67 +      /// The add() member function notificates the observer about an item
    1.68 +      /// is added to the container. It have to be overrided in the
    1.69 +      /// subclasses.
    1.70 +
    1.71 +      virtual void add(const std::vector<Item>& items) {
    1.72 +	for (int i = 0; i < (int)items.size(); ++i) {
    1.73 +	  add(items[i]);
    1.74 +	}
    1.75 +      }
    1.76  
    1.77        /// \brief The member function to notificate the observer about an
    1.78        /// item is erased from the container.
    1.79 @@ -143,6 +155,12 @@
    1.80  	
    1.81        virtual void erase(const Item&) = 0;
    1.82  
    1.83 +      virtual void erase(const std::vector<Item>& items) {
    1.84 +	for (int i = 0; i < (int)items.size(); ++i) {
    1.85 +	  add(items[i]);
    1.86 +	}
    1.87 +      }
    1.88 +
    1.89        /// \brief The member function to notificate the observer about the
    1.90        /// container is built.
    1.91        ///
    1.92 @@ -228,20 +246,37 @@
    1.93  
    1.94    public:
    1.95  	
    1.96 -    /// Notifies all the registered observers about an Item added to the container.
    1.97 -		
    1.98 -    /// It notifies all the registered observers about an Item added to the container.
    1.99 +    /// \brief Notifies all the registered observers about an Item added to 
   1.100 +    /// the container.
   1.101 +    ///
   1.102 +    /// It notifies all the registered observers about an Item added to 
   1.103 +    /// the container.
   1.104      /// 
   1.105 -    void add(const Item& key) {
   1.106 +    void add(const Item& item) {
   1.107        typename Container::iterator it;
   1.108        for (it = container.begin(); it != container.end(); ++it) {
   1.109 -	(*it)->add(key);
   1.110 +	(*it)->add(item);
   1.111        }
   1.112      }	
   1.113  
   1.114 -    /// Notifies all the registered observers about an Item erased from the container.
   1.115 -		
   1.116 -    /// It notifies all the registered observers about an Item erased from the container.
   1.117 +    /// \brief Notifies all the registered observers about more Item added to 
   1.118 +    /// the container.
   1.119 +    ///
   1.120 +    /// It notifies all the registered observers about more Item added to 
   1.121 +    /// the container.
   1.122 +    /// 
   1.123 +    void add(const std::vector<Item>& items) {
   1.124 +      typename Container::iterator it;
   1.125 +      for (it = container.begin(); it != container.end(); ++it) {
   1.126 +	(*it)->add(items);
   1.127 +      }
   1.128 +    }	
   1.129 +
   1.130 +    /// \brief Notifies all the registered observers about an Item erased from 
   1.131 +    /// the container.
   1.132 +    ///	
   1.133 +    /// It notifies all the registered observers about an Item erased from 
   1.134 +    /// the container.
   1.135      /// 
   1.136      void erase(const Item& key) {
   1.137        typename Container::iterator it;
   1.138 @@ -249,10 +284,24 @@
   1.139  	(*it)->erase(key);
   1.140        }
   1.141      }
   1.142 +
   1.143 +    /// \brief Notifies all the registered observers about more Item erased  
   1.144 +    /// from the container.
   1.145 +    ///	
   1.146 +    /// It notifies all the registered observers about more Item erased from 
   1.147 +    /// the container.
   1.148 +    /// 
   1.149 +    void erase(const std::vector<Item>& items) {
   1.150 +      typename Container::iterator it;
   1.151 +      for (it = container.begin(); it != container.end(); ++it) {
   1.152 +	(*it)->erase(items);
   1.153 +      }
   1.154 +    }
   1.155      
   1.156  
   1.157 -    /// Notifies all the registered observers about the container is built.
   1.158 -		
   1.159 +    /// \brief Notifies all the registered observers about the container is 
   1.160 +    /// built.
   1.161 +    ///		
   1.162      /// Notifies all the registered observers about the container is built
   1.163      /// from an empty container.
   1.164      void build() {
   1.165 @@ -263,8 +312,9 @@
   1.166      }
   1.167  
   1.168  
   1.169 -    /// Notifies all the registered observers about all Items are erased.
   1.170 -
   1.171 +    /// \brief Notifies all the registered observers about all Items are 
   1.172 +    /// erased.
   1.173 +    ///
   1.174      /// Notifies all the registered observers about all Items are erased
   1.175      /// from the container.
   1.176      void clear() {

     2.1 --- a/src/lemon/bits/array_map.h	Wed May 11 17:36:25 2005 +0000
     2.2 +++ b/src/lemon/bits/array_map.h	Sat May 14 17:20:40 2005 +0000
     2.3 @@ -1,5 +1,5 @@
     2.4  /* -*- C++ -*-
     2.5 - * src/lemon/array_map.h - Part of LEMON, a generic C++ optimization library
     2.6 + * src/lemon/bits/array_map.h - Part of LEMON, a generic C++ optimization library
     2.7   *
     2.8   * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     2.9   * (Egervary Research Group on Combinatorial Optimization, EGRES).
    2.10 @@ -31,14 +31,14 @@
    2.11    /// \addtogroup graphmaps
    2.12    /// @{
    2.13  	
    2.14 -  /** The ArrayMap template class is graph map structure what
    2.15 -   *  automatically updates the map when a key is added to or erased from
    2.16 -   *  the map. This map factory uses the allocators to implement 
    2.17 -   *  the container functionality.
    2.18 -   *
    2.19 -   *  The template parameter is the AlterationNotifier that the maps
    2.20 -   *  will belong to and the Value.
    2.21 -   */
    2.22 +  /// The ArrayMap template class is graph map structure what
    2.23 +  /// automatically updates the map when a key is added to or erased from
    2.24 +  /// the map. This map factory uses the allocators to implement 
    2.25 +  /// the container functionality.
    2.26 +  ///
    2.27 +  /// The template parameter is the AlterationNotifier that the maps
    2.28 +  /// will belong to and the Value.
    2.29 +   
    2.30  
    2.31    template <typename _Graph, 
    2.32  	    typename _Item,
    2.33 @@ -68,8 +68,8 @@
    2.34  
    2.35    public:
    2.36  
    2.37 -    /** Graph and Registry initialized map constructor.
    2.38 -     */
    2.39 +    /// Graph and Registry initialized map constructor.
    2.40 +     
    2.41      ArrayMap(const Graph& _g) : graph(&_g) {
    2.42        Item it;
    2.43        attach(_g.getNotifier(Item()));
    2.44 @@ -94,8 +94,8 @@
    2.45        }								
    2.46      }
    2.47  
    2.48 -    /** Constructor to copy a map of the same map type.
    2.49 -     */
    2.50 +    /// Constructor to copy a map of the same map type.
    2.51 +     
    2.52      ArrayMap(const ArrayMap& copy) : Parent() {
    2.53        if (copy.attached()) {
    2.54  	attach(*copy.getRegistry());
    2.55 @@ -114,8 +114,8 @@
    2.56      using Parent::detach;
    2.57      using Parent::attached;
    2.58  
    2.59 -    /** Assign operator to copy a map of the same map type.
    2.60 -     */
    2.61 +    /// Assign operator to copy a map of the same map type.
    2.62 +     
    2.63      ArrayMap& operator=(const ArrayMap& copy) {
    2.64        if (&copy == this) return *this;
    2.65        
    2.66 @@ -141,8 +141,8 @@
    2.67        return *this;
    2.68      }
    2.69  
    2.70 -    /** The destructor of the map.
    2.71 -     */
    2.72 +    /// The destructor of the map.
    2.73 +     
    2.74      virtual ~ArrayMap() {      
    2.75        if (attached()) {
    2.76  	clear();
    2.77 @@ -151,33 +151,32 @@
    2.78      }
    2.79  	
    2.80  	
    2.81 -    /**
    2.82 -     * The subscript operator. The map can be subscripted by the
    2.83 -     * actual keys of the graph. 
    2.84 -     */
    2.85 +    ///The subscript operator. The map can be subscripted by the
    2.86 +    ///actual keys of the graph. 
    2.87 +     
    2.88      Value& operator[](const Key& key) {
    2.89        int id = graph->id(key);
    2.90        return values[id];
    2.91      } 
    2.92  		
    2.93 -    /**
    2.94 -     * The const subscript operator. The map can be subscripted by the
    2.95 -     * actual keys of the graph. 
    2.96 -     */
    2.97 +
    2.98 +    ///The const subscript operator. The map can be subscripted by the
    2.99 +    ///actual keys of the graph. 
   2.100 +     
   2.101      const Value& operator[](const Key& key) const {
   2.102        int id = graph->id(key);
   2.103        return values[id];
   2.104      }
   2.105  	
   2.106 -    /** Setter function of the map. Equivalent with map[key] = val.
   2.107 -     *  This is a compatibility feature with the not dereferable maps.
   2.108 -     */
   2.109 +    /// Setter function of the map. Equivalent with map[key] = val.
   2.110 +    /// This is a compatibility feature with the not dereferable maps.
   2.111 +     
   2.112      void set(const Key& key, const Value& val) {
   2.113        (*this)[key] = val;
   2.114      }
   2.115  		
   2.116 -    /** Add a new key to the map. It called by the map registry.
   2.117 -     */
   2.118 +    /// Add a new key to the map. It called by the map registry.
   2.119 +     
   2.120      void add(const Key& key) {
   2.121        int id = graph->id(key);
   2.122        if (id >= capacity) {
   2.123 @@ -200,14 +199,60 @@
   2.124        }
   2.125        allocator.construct(&(values[id]), Value());
   2.126      }
   2.127 +
   2.128 +    void add(const std::vector<Key>& keys) {
   2.129 +      int max_id = -1;
   2.130 +      for (int i = 0; i < (int)keys.size(); ++i) {
   2.131 +	int id = graph->id(keys[i]);
   2.132 +	if (id > max_id) {
   2.133 +	  max_id = id;
   2.134 +	}
   2.135 +      }
   2.136 +      if (max_id >= capacity) {
   2.137 +	int new_capacity = (capacity == 0 ? 1 : capacity);
   2.138 +	while (new_capacity <= max_id) {
   2.139 +	  new_capacity <<= 1;
   2.140 +	}
   2.141 +	Value* new_values = allocator.allocate(new_capacity);
   2.142 +	Item it;
   2.143 +	for (graph->first(it); it != INVALID; graph->next(it)) {
   2.144 +	  int id = graph->id(it);
   2.145 +	  bool found = false;
   2.146 +	  for (int i = 0; i < (int)keys.size(); ++i) {
   2.147 +	    int jd = graph->id(keys[i]);
   2.148 +	    if (id == jd) {
   2.149 +	      found = true;
   2.150 +	      break;
   2.151 +	    }
   2.152 +	  }
   2.153 +	  if (found) continue;
   2.154 +	  allocator.construct(&(new_values[id]), values[id]);
   2.155 +	  allocator.destroy(&(values[id]));
   2.156 +	}
   2.157 +	if (capacity != 0) allocator.deallocate(values, capacity);
   2.158 +	values = new_values;
   2.159 +	capacity = new_capacity;
   2.160 +      }
   2.161 +      for (int i = 0; i < (int)keys.size(); ++i) {
   2.162 +	int id = graph->id(keys[i]);
   2.163 +	allocator.construct(&(values[id]), Value());
   2.164 +      }
   2.165 +    }
   2.166  		
   2.167 -    /** Erase a key from the map. It called by the map registry.
   2.168 -     */
   2.169 +    /// Erase a key from the map. It called by the map registry.
   2.170 +     
   2.171      void erase(const Key& key) {
   2.172        int id = graph->id(key);
   2.173        allocator.destroy(&(values[id]));
   2.174      }
   2.175  
   2.176 +    void erase(const std::vector<Key>& keys) {
   2.177 +      for (int i = 0; i < (int)keys.size(); ++i) {
   2.178 +	int id = graph->id(keys[i]);
   2.179 +	allocator.destroy(&(values[id]));
   2.180 +      }
   2.181 +    }
   2.182 +
   2.183      void build() {
   2.184        allocate_memory();
   2.185        Item it;
   2.186 @@ -221,7 +266,7 @@
   2.187        if (capacity != 0) {
   2.188  	Item it;
   2.189  	for (graph->first(it); it != INVALID; graph->next(it)) {
   2.190 -	  int id = graph->id(it);;
   2.191 +	  int id = graph->id(it);
   2.192  	  allocator.destroy(&(values[id]));
   2.193  	}								
   2.194  	allocator.deallocate(values, capacity);
   2.195 @@ -233,59 +278,6 @@
   2.196        return graph;
   2.197      }
   2.198  
   2.199 -//     /// The stl compatible pair iterator of the map.
   2.200 -//     typedef MapIterator<ArrayMap> Iterator;
   2.201 -//     /// The stl compatible const pair iterator of the map.
   2.202 -//     typedef MapConstIterator<ArrayMap> ConstIterator;
   2.203 -
   2.204 -//     /** Returns the begin iterator of the map.
   2.205 -//      */
   2.206 -//     Iterator begin() {
   2.207 -//       return Iterator(*this, KeyIt(*MapBase::getGraph()));
   2.208 -//     }
   2.209 -
   2.210 -//     /** Returns the end iterator of the map.
   2.211 -//      */
   2.212 -//     Iterator end() {
   2.213 -//       return Iterator(*this, INVALID);
   2.214 -//     }
   2.215 -
   2.216 -//     /** Returns the begin ConstIterator of the map.
   2.217 -//      */
   2.218 -//     ConstIterator begin() const {
   2.219 -//       return ConstIterator(*this, KeyIt(*MapBase::getGraph()));
   2.220 -//     }
   2.221 -
   2.222 -//     /** Returns the end const_iterator of the map.
   2.223 -//      */
   2.224 -//     ConstIterator end() const {
   2.225 -//       return ConstIterator(*this, INVALID);
   2.226 -//     }
   2.227 -
   2.228 -//     /// The KeySet of the Map.
   2.229 -//     typedef MapConstKeySet<ArrayMap> ConstKeySet;
   2.230 -
   2.231 -//     /// KeySet getter function.
   2.232 -//     ConstKeySet keySet() const {
   2.233 -//       return ConstKeySet(*this); 
   2.234 -//     }
   2.235 -
   2.236 -//     /// The ConstValueSet of the Map.
   2.237 -//     typedef MapConstValueSet<ArrayMap> ConstValueSet;
   2.238 -
   2.239 -//     /// ConstValueSet getter function.
   2.240 -//     ConstValueSet valueSet() const {
   2.241 -//       return ConstValueSet(*this);
   2.242 -//     }
   2.243 -
   2.244 -//     /// The ValueSet of the Map.
   2.245 -//     typedef MapValueSet<ArrayMap> ValueSet;
   2.246 -
   2.247 -//     /// ValueSet getter function.
   2.248 -//     ValueSet valueSet() {
   2.249 -//       return ValueSet(*this);
   2.250 -//     }
   2.251 -
   2.252    private:
   2.253        
   2.254      void allocate_memory() {

     3.1 --- a/src/lemon/bits/erasable_graph_extender.h	Wed May 11 17:36:25 2005 +0000
     3.2 +++ b/src/lemon/bits/erasable_graph_extender.h	Sat May 14 17:20:40 2005 +0000
     3.3 @@ -3,6 +3,8 @@
     3.4  #ifndef LEMON_ERASABLE_GRAPH_EXTENDER_H
     3.5  #define LEMON_ERASABLE_GRAPH_EXTENDER_H
     3.6  
     3.7 +#include <vector>
     3.8 +
     3.9  #include <lemon/invalid.h>
    3.10  
    3.11  
    3.12 @@ -67,8 +69,10 @@
    3.13      }
    3.14      
    3.15      void erase(const UndirEdge& uedge) {
    3.16 -      Parent::getNotifier(Edge()).erase(Edge(uedge,true));
    3.17 -      Parent::getNotifier(Edge()).erase(Edge(uedge,false));
    3.18 +      std::vector<Edge> edges;
    3.19 +      edges.push_back(Edge(uedge,true));
    3.20 +      edges.push_back(Edge(uedge,false));
    3.21 +      Parent::getNotifier(Edge()).erase(edges);
    3.22        Parent::getNotifier(UndirEdge()).erase(uedge);
    3.23        Parent::erase(uedge);
    3.24      }

     4.1 --- a/src/lemon/bits/extendable_graph_extender.h	Wed May 11 17:36:25 2005 +0000
     4.2 +++ b/src/lemon/bits/extendable_graph_extender.h	Sat May 14 17:20:40 2005 +0000
     4.3 @@ -50,10 +50,10 @@
     4.4        UndirEdge uedge = Parent::addEdge(from, to);
     4.5        Parent::getNotifier(UndirEdge()).add(uedge);
     4.6  
     4.7 -      Edge edge_forward(uedge, true);
     4.8 -      Edge edge_backward(uedge, false);
     4.9 -      Parent::getNotifier(Edge()).add(edge_forward);
    4.10 -      Parent::getNotifier(Edge()).add(edge_backward);
    4.11 +      std::vector<Edge> edges;
    4.12 +      edges.push_back(Edge(uedge, true));
    4.13 +      edges.push_back(Edge(uedge, false));
    4.14 +      Parent::getNotifier(Edge()).add(edges);
    4.15  
    4.16        return uedge;
    4.17      }