Mercuriallemon-0.x / comparison
summary | shortlog | changelog | graph | tags | bookmarks | branches | files | changeset | file | latest | revisions | annotate | diff | comparison | raw | help
lemon/iterable_maps.h
changeset 1991 d7442141d9ef
parent 1956 a055123339d5
child 1993 2115143eceea
equal deleted inserted replaced
11:4ed40a2b136b 12:149887012b87 
    17  */
 
    17  */
 
    18 
    18 
    19 #include <lemon/traits.h>
 
    19 #include <lemon/traits.h>
 
    20 #include <lemon/invalid.h>
 
    20 #include <lemon/invalid.h>
 
    21 
    21 
       
    22 #include <lemon/bits/default_map.h>
 
       
    23 
    22 #include <vector>
 
    24 #include <vector>
 
    23 #include <map>
 
    25 #include <map>
 
    24 
    26 
    25 #include <iterator>
 
    27 #include <iterator>
 
    26 #include <limits>
 
    28 #include <limits>
 
    45   /// mapped to the given value.
 
    47   /// mapped to the given value.
 
    46   /// 
    48   /// 
    47   /// \param _Graph The graph type.
 
    49   /// \param _Graph The graph type.
 
    48   /// \param _Item One of the graph's item type, the key of the map.
 
    50   /// \param _Item One of the graph's item type, the key of the map.
 
    49   template <typename _Graph, typename _Item>
 
    51   template <typename _Graph, typename _Item>
 
    50   class IterableBoolMap 
    52   class IterableBoolMap : protected DefaultMap<_Graph, _Item, int> {
 
    51     : protected ItemSetTraits<_Graph, _Item>::template Map<int>::Parent {
 
       
    52   private:
 
    53   private:
 
    53     typedef _Graph Graph;
 
    54     typedef _Graph Graph;
 
    54     
    55     
    55     typedef typename ItemSetTraits<Graph, _Item>::ItemIt KeyIt;
 
    56     typedef typename ItemSetTraits<Graph, _Item>::ItemIt KeyIt;
 
    56     typedef typename ItemSetTraits<Graph, _Item>
 
    57     typedef DefaultMap<_Graph, _Item, int> Parent;
 
    57     ::template Map<int>::Parent Parent;
 
       
    58     
    58     
    59     std::vector<_Item> array;
 
    59     std::vector<_Item> array;
 
    60     int sep;
 
    60     int sep;
 
    61 
    61 
    62     const Graph& graph;
 
    62     const Graph& graph;
 
   397   /// mapped to the given value.
 
   397   /// mapped to the given value.
 
   398   /// 
   398   /// 
   399   /// \param _Graph The graph type.
 
   399   /// \param _Graph The graph type.
 
   400   /// \param _Item One of the graph's item type, the key of the map.
 
   400   /// \param _Item One of the graph's item type, the key of the map.
 
   401   template <typename _Graph, typename _Item>
 
   401   template <typename _Graph, typename _Item>
 
   402   class IterableIntMap : protected ItemSetTraits<_Graph, _Item> 
   402   class IterableIntMap 
   403   ::template Map<_iterable_maps_bits::IterableIntMapNode<_Item> >::Parent {
 
   403     : protected DefaultMap<_Graph, _Item, _iterable_maps_bits::
 
       
   404                            IterableIntMapNode<_Item> > {
 
   404   public:
 
   405   public:
 
   405     typedef typename ItemSetTraits<_Graph, _Item> 
   406     typedef DefaultMap<_Graph, _Item, _iterable_maps_bits::
 
   406     ::template Map<_iterable_maps_bits::IterableIntMapNode<_Item> >
 
   407                        IterableIntMapNode<_Item> >
 
   407     ::Parent Parent;
 
   408     Parent;
 
   408 
   409 
   409     /// The key type
 
   410     /// The key type
 
   410     typedef _Item Key;
 
   411     typedef _Item Key;
 
   411     /// The value type
 
   412     /// The value type
 
   412     typedef int Value;
 
   413     typedef int Value;
 
   685   /// 
   686   /// 
   686   /// \param _Graph The graph type.
 
   687   /// \param _Graph The graph type.
 
   687   /// \param _Item One of the graph's item type, the key of the map.
 
   688   /// \param _Item One of the graph's item type, the key of the map.
 
   688   /// \param _Value Any comparable value type.
 
   689   /// \param _Value Any comparable value type.
 
   689   template <typename _Graph, typename _Item, typename _Value>
 
   690   template <typename _Graph, typename _Item, typename _Value>
 
   690   class IterableValueMap : protected ItemSetTraits<_Graph, _Item> 
   691   class IterableValueMap 
   691   ::template Map<_iterable_maps_bits::IterableValueMapNode<_Item, _Value> >
 
   692     : protected DefaultMap<_Graph, _Item, _iterable_maps_bits::
 
   692   ::Parent {
 
   693                            IterableValueMapNode<_Item, _Value> > {
 
   693   public:
 
   694   public:
 
   694     typedef typename ItemSetTraits<_Graph, _Item> 
   695     typedef DefaultMap<_Graph, _Item, _iterable_maps_bits::
 
   695     ::template Map<_iterable_maps_bits::IterableValueMapNode<_Item, _Value> >
 
   696                        IterableValueMapNode<_Item, _Value> > Parent;
 
   696     ::Parent Parent;
 
       
   697 
   697 
   698     /// The key type
 
   698     /// The key type
 
   699     typedef _Item Key;
 
   699     typedef _Item Key;
 
   700     /// The value type
 
   700     /// The value type
 
   701     typedef _Value Value;
 
   701     typedef _Value Value;
 
   702     /// The graph type
 
   702     /// The graph type
 
   703     typedef _Graph Graph;
 
   703     typedef _Graph Graph;
 
   704 
   704 
       
   705   protected:
 
       
   706 
       
   707     typedef typename ItemSetTraits<_Graph, Key>::ItemIt KeyIt; 
       
   708 
       
   709   public:
 
       
   710 
   705     /// \brief Constructor of the Map with a given value.
 
   711     /// \brief Constructor of the Map with a given value.
 
   706     ///
 
   712     ///
 
   707     /// Constructor of the Map with a given value.
 
   713     /// Constructor of the Map with a given value.
 
   708     explicit IterableValueMap(const Graph& graph, 
   714     explicit IterableValueMap(const Graph& graph, 
   709                               const Value& value = Value()) 
   715                               const Value& value = Value()) 
   710       : Parent(graph, _iterable_maps_bits::IterableValueMapNode<_Item, 
   716       : Parent(graph, _iterable_maps_bits::
 
   711                _Value>(value)) {
 
   717                IterableValueMapNode<_Item, _Value>(value)) {
 
   712       for (typename Parent::ItemIt it(*this); it != INVALID; ++it) {
 
   718       for (KeyIt it(*Parent::getGraph()); it != INVALID; ++it) {
 
   713         lace(it);
 
   719         lace(it);
 
   714       }
 
   720       }
 
   715     }
 
   721     }
 
   716 
   722 
   717   private:
 
   723   protected:
 
   718     
   724     
   719     void unlace(const Key& key) {
 
   725     void unlace(const Key& key) {
 
   720       typename Parent::Value& node = Parent::operator[](key);
 
   726       typename Parent::Value& node = Parent::operator[](key);
 
   721       if (node.prev != INVALID) {
 
   727       if (node.prev != INVALID) {
 
   722 	Parent::operator[](node.prev).next = node.next;	
   728 	Parent::operator[](node.prev).next = node.next;	
   869       const IterableValueMap* _map;
 
   875       const IterableValueMap* _map;
 
   870     };
 
   876     };
 
   871 
   877 
   872   protected:
 
   878   protected:
 
   873     
   879     
       
   880     virtual void add(const Key& key) {
 
       
   881       Parent::add(key);
 
       
   882       unlace(key);
 
       
   883     }
 
       
   884 
       
   885     virtual void add(const std::vector<Key>& keys) {
 
       
   886       Parent::add(keys);
 
       
   887       for (int i = 0; i < (int)keys.size(); ++i) {
 
       
   888         lace(keys[i]);
 
       
   889       }
 
       
   890     }
 
       
   891 
   874     virtual void erase(const Key& key) {
 
   892     virtual void erase(const Key& key) {
 
   875       unlace(key);
 
   893       unlace(key);
 
   876       Parent::erase(key);
 
   894       Parent::erase(key);
 
   877     }
 
   895     }
 
   878 
   896 
   881         unlace(keys[i]);
 
   899         unlace(keys[i]);
 
   882       }
 
   900       }
 
   883       Parent::erase(keys);
 
   901       Parent::erase(keys);
 
   884     }
 
   902     }
 
   885 
   903 
       
   904     virtual void build() {
 
       
   905       Parent::build();
 
       
   906       for (KeyIt it(*Parent::getGraph()); it != INVALID; ++it) {
 
       
   907         lace(it);
 
       
   908       }
 
       
   909     }
 
       
   910 
   886     virtual void clear() {
 
   911     virtual void clear() {
 
   887       first.clear();
 
   912       first.clear();
 
   888       Parent::clear();
 
   913       Parent::clear();
 
   889     }
 
   914     }
 
   890 
   915
lemon-0.x