iterable_maps.h

Go to the documentation of this file.
00001 /* -*- C++ -*-
00002  *
00003  * This file is a part of LEMON, a generic C++ optimization library
00004  *
00005  * Copyright (C) 2003-2006
00006  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
00007  * (Egervary Research Group on Combinatorial Optimization, EGRES).
00008  *
00009  * Permission to use, modify and distribute this software is granted
00010  * provided that this copyright notice appears in all copies. For
00011  * precise terms see the accompanying LICENSE file.
00012  *
00013  * This software is provided "AS IS" with no warranty of any kind,
00014  * express or implied, and with no claim as to its suitability for any
00015  * purpose.
00016  *
00017  */
00018 
00019 #include <lemon/traits.h>
00020 #include <lemon/invalid.h>
00021 
00022 #include <vector>
00023 #include <map>
00024 
00025 #include <iterator>
00026 #include <limits>
00027 
00034 
00035 
00036 namespace lemon {
00037 
00049   template <typename _Graph, typename _Item>
00050   class IterableBoolMap 
00051     : protected ItemSetTraits<_Graph, _Item>::template Map<int>::Parent {
00052   private:
00053     typedef _Graph Graph;
00054     
00055     typedef typename ItemSetTraits<Graph, _Item>::ItemIt KeyIt;
00056     typedef typename ItemSetTraits<Graph, _Item>
00057     ::template Map<int>::Parent Parent;
00058     
00059     std::vector<_Item> array;
00060     int sep;
00061 
00062     const Graph& graph;
00063 
00064   public:
00065 
00067     typedef True ReferenceMapTag;
00068 
00070     typedef _Item Key;
00072     typedef bool Value;
00074     typedef const Value& ConstReference;
00075 
00076   private:
00077 
00078     int position(const Key& key) const {
00079       return Parent::operator[](key);
00080     }
00081 
00082   public:
00083 
00088     class Reference {
00089       friend class IterableBoolMap;
00090     private:
00091       Reference(IterableBoolMap& map, const Key& key) 
00092         : _key(key), _map(map) {} 
00093     public:
00094 
00095       Reference& operator=(const Reference& value) {
00096         _map.set(_key, (bool)value);
00097         return *this;
00098       }
00099 
00100       operator bool() const { 
00101         return static_cast<const IterableBoolMap&>(_map)[_key]; 
00102       }
00103 
00104       Reference& operator=(bool value) { 
00105         _map.set(_key, value); 
00106         return *this; 
00107       }
00108       Reference& operator&=(bool value) {
00109         _map.set(_key, _map[_key] & value); 
00110         return *this;   
00111       }
00112       Reference& operator|=(bool value) {
00113         _map.set(_key, _map[_key] | value); 
00114         return *this;   
00115       }
00116       Reference& operator^=(bool value) {
00117         _map.set(_key, _map[_key] ^ value); 
00118         return *this;   
00119       }
00120     private:
00121       Key _key;
00122       IterableBoolMap& _map; 
00123     };
00124     
00128     IterableBoolMap(const Graph& _graph, bool def = false) 
00129       : Parent(_graph), graph(_graph) {
00130       for (KeyIt it(graph); it != INVALID; ++it) {
00131         Parent::set(it, array.size());
00132         array.push_back(it);
00133       }
00134       sep = (def ? array.size() : 0);
00135     }
00136 
00140     bool operator[](const Key& key) const {
00141       return position(key) < sep;
00142     }
00143 
00147     Reference operator[](const Key& key) {
00148       return Reference(*this, key);
00149     }
00150 
00154     void set(const Key& key, bool value) {
00155       int pos = position(key);
00156       if (value) {
00157         if (pos < sep) return;
00158         Key tmp = array[sep];
00159         array[sep] = key;
00160         Parent::set(key, sep);
00161         array[pos] = tmp;
00162         Parent::set(tmp, pos); 
00163         ++sep;
00164       } else {
00165         if (pos >= sep) return;
00166         --sep;
00167         Key tmp = array[sep];
00168         array[sep] = key;
00169         Parent::set(key, sep);
00170         array[pos] = tmp;
00171         Parent::set(tmp, pos);
00172       }
00173     }
00174 
00178     int trueNum() const {
00179       return sep;
00180     } 
00181     
00185     int falseNum() const {
00186       return array.size() - sep;
00187     }
00188 
00196     class TrueIt : public Key {
00197     public:
00198       typedef Key Parent;
00199       
00205       TrueIt(const IterableBoolMap& _map) 
00206         : Parent(_map.sep > 0 ? _map.array[_map.sep - 1] : INVALID), 
00207           map(&_map) {}
00208 
00213       TrueIt(Invalid) : Parent(INVALID), map(0) {}
00214 
00218       TrueIt& operator++() {
00219         int pos = map->position(*this);
00220         Parent::operator=(pos > 0 ? map->array[pos - 1] : INVALID);
00221         return *this;
00222       }
00223 
00224       
00225     private:
00226       const IterableBoolMap* map;
00227     };
00228 
00236     class FalseIt : public Key {
00237     public:
00238       typedef Key Parent;
00239       
00245       FalseIt(const IterableBoolMap& _map) 
00246         : Parent(_map.sep < (int)_map.array.size() ? 
00247                  _map.array.back() : INVALID), map(&_map) {}
00248 
00253       FalseIt(Invalid) : Parent(INVALID), map(0) {}
00254 
00258       FalseIt& operator++() {
00259         int pos = map->position(*this);
00260         Parent::operator=(pos > map->sep ? map->array[pos - 1] : INVALID);
00261         return *this;
00262       }
00263 
00264     private:
00265       const IterableBoolMap* map;
00266     };
00267 
00275     class ItemIt : public Key {
00276     public:
00277       typedef Key Parent;
00278       
00285       ItemIt(const IterableBoolMap& _map, bool value) 
00286         : Parent(value ? (_map.sep > 0 ? _map.array[_map.sep - 1] : INVALID) :
00287                  (_map.sep < (int)_map.array.size() ? 
00288                   _map.array.back() : INVALID)), map(&_map) {}
00289 
00294       ItemIt(Invalid) : Parent(INVALID), map(0) {}
00295 
00299       ItemIt& operator++() {
00300         int pos = map->position(*this);
00301         int sep = pos >= map->sep ? map->sep : 0;
00302         Parent::operator=(pos > sep ? map->array[pos - 1] : INVALID);
00303         return *this;
00304       }
00305 
00306     private:
00307       const IterableBoolMap* map;
00308     };
00309 
00310   protected:
00311     
00312     virtual void add(const Key& key) {
00313       Parent::add(key);
00314       Parent::set(key, array.size());
00315       array.push_back(key);
00316     }
00317 
00318     virtual void add(const std::vector<Key>& keys) {
00319       Parent::add(keys);
00320       for (int i = 0; i < (int)keys.size(); ++i) {
00321         Parent::set(keys[i], array.size());
00322         array.push_back(keys[i]);
00323       }
00324     }
00325 
00326     virtual void erase(const Key& key) {
00327       int pos = position(key); 
00328       if (pos < sep) {
00329         --sep;
00330         Parent::set(array[sep], pos);
00331         array[pos] = array[sep];
00332         Parent::set(array.back(), sep);
00333         array[sep] = array.back();
00334         array.pop_back();
00335       } else {
00336         Parent::set(array.back(), pos);
00337         array[pos] = array.back();
00338         array.pop_back();
00339       }
00340       Parent::erase(key);
00341     }
00342 
00343     virtual void erase(const std::vector<Key>& keys) {
00344       for (int i = 0; i < (int)keys.size(); ++i) {
00345         int pos = position(keys[i]); 
00346         if (pos < sep) {
00347           --sep;
00348           Parent::set(array[sep], pos);
00349           array[pos] = array[sep];
00350           Parent::set(array.back(), sep);
00351           array[sep] = array.back();
00352           array.pop_back();
00353         } else {
00354           Parent::set(array.back(), pos);
00355           array[pos] = array.back();
00356           array.pop_back();
00357         }
00358       }
00359       Parent::erase(keys);
00360     }    
00361 
00362     virtual void build() {
00363       Parent::build();
00364       for (KeyIt it(graph); it != INVALID; ++it) {
00365         Parent::set(it, array.size());
00366         array.push_back(it);
00367       }
00368       sep = 0;      
00369     }
00370 
00371     virtual void clear() {
00372       array.clear();
00373       sep = 0;
00374       Parent::clear();
00375     }
00376     
00377   };
00378   
00379 
00380   namespace _iterable_maps_bits {
00381     template <typename Item>
00382     struct IterableIntMapNode {
00383       IterableIntMapNode() : value(-1) {}
00384       IterableIntMapNode(int _value) : value(_value) {}
00385       Item prev, next;
00386       int value;
00387     };
00388   }
00389 
00401   template <typename _Graph, typename _Item>
00402   class IterableIntMap : protected ItemSetTraits<_Graph, _Item> 
00403   ::template Map<_iterable_maps_bits::IterableIntMapNode<_Item> >::Parent {
00404   public:
00405     typedef typename ItemSetTraits<_Graph, _Item> 
00406     ::template Map<_iterable_maps_bits::IterableIntMapNode<_Item> >
00407     ::Parent Parent;
00408 
00410     typedef _Item Key;
00412     typedef int Value;
00414     typedef _Graph Graph;
00415 
00419     explicit IterableIntMap(const Graph& graph) 
00420       : Parent(graph) {}
00421 
00425     explicit IterableIntMap(const Graph& graph, int value) 
00426       : Parent(graph, _iterable_maps_bits::IterableIntMapNode<_Item>(value)) {
00427       if (value >= 0) {
00428         for (typename Parent::ItemIt it(*this); it != INVALID; ++it) {
00429           lace(it);
00430         }
00431       }
00432     }
00433 
00434   private:
00435     
00436     void unlace(const Key& key) {
00437       typename Parent::Value& node = Parent::operator[](key);
00438       if (node.value < 0) return;
00439       if (node.prev != INVALID) {
00440         Parent::operator[](node.prev).next = node.next; 
00441       } else {
00442         first[node.value] = node.next;
00443       }
00444       if (node.next != INVALID) {
00445         Parent::operator[](node.next).prev = node.prev;
00446       }
00447       while (!first.empty() && first.back() == INVALID) {
00448         first.pop_back();
00449       }
00450     }
00451 
00452     void lace(const Key& key) {
00453       typename Parent::Value& node = Parent::operator[](key);
00454       if (node.value < 0) return;
00455       if (node.value >= (int)first.size()) {
00456         first.resize(node.value + 1, INVALID);
00457       } 
00458       node.prev = INVALID;
00459       node.next = first[node.value];
00460       if (node.next != INVALID) {
00461         Parent::operator[](node.next).prev = key;       
00462       }
00463       first[node.value] = key;
00464     }
00465 
00466   public:
00467 
00469     typedef True ReferenceMapTag;
00470 
00475     class Reference {
00476       friend class IterableIntMap;
00477     private:
00478       Reference(IterableIntMap& map, const Key& key) 
00479         : _key(key), _map(map) {} 
00480     public:
00481 
00482       Reference& operator=(const Reference& value) {
00483         _map.set(_key, (const int&)value);
00484         return *this;
00485       }
00486 
00487       operator const int&() const { 
00488         return static_cast<const IterableIntMap&>(_map)[_key]; 
00489       }
00490 
00491       Reference& operator=(int value) { 
00492         _map.set(_key, value); 
00493         return *this; 
00494       }
00495       Reference& operator++() {
00496         _map.set(_key, _map[_key] + 1); 
00497         return *this;   
00498       }
00499       int operator++(int) {
00500         int value = _map[_key];
00501         _map.set(_key, value + 1); 
00502         return value;   
00503       }
00504       Reference& operator--() {
00505         _map.set(_key, _map[_key] - 1); 
00506         return *this;   
00507       }
00508       int operator--(int) {
00509         int value = _map[_key];
00510         _map.set(_key, value - 1); 
00511         return value;   
00512       }
00513       Reference& operator+=(int value) { 
00514         _map.set(_key, _map[_key] + value); 
00515         return *this;
00516       }
00517       Reference& operator-=(int value) { 
00518         _map.set(_key, _map[_key] - value); 
00519         return *this;
00520       }
00521       Reference& operator*=(int value) { 
00522         _map.set(_key, _map[_key] * value); 
00523         return *this;
00524       }
00525       Reference& operator/=(int value) { 
00526         _map.set(_key, _map[_key] / value); 
00527         return *this;
00528       }
00529       Reference& operator%=(int value) { 
00530         _map.set(_key, _map[_key] % value); 
00531         return *this;
00532       }
00533       Reference& operator&=(int value) { 
00534         _map.set(_key, _map[_key] & value); 
00535         return *this;
00536       }
00537       Reference& operator|=(int value) { 
00538         _map.set(_key, _map[_key] | value); 
00539         return *this;
00540       }
00541       Reference& operator^=(int value) { 
00542         _map.set(_key, _map[_key] ^ value); 
00543         return *this;
00544       }
00545       Reference& operator<<=(int value) { 
00546         _map.set(_key, _map[_key] << value); 
00547         return *this;
00548       }
00549       Reference& operator>>=(int value) { 
00550         _map.set(_key, _map[_key] >> value); 
00551         return *this;
00552       }
00553 
00554     private:
00555       Key _key;
00556       IterableIntMap& _map; 
00557     };
00558 
00560     typedef const Value& ConstReference;
00561 
00565     unsigned int size() const {
00566       return first.size();
00567     }
00568     
00572     void set(const Key& key, const Value& value) {
00573       unlace(key);
00574       Parent::operator[](key).value = value;
00575       lace(key);
00576     }
00577 
00581     const Value& operator[](const Key& key) const {
00582       return Parent::operator[](key).value;
00583     }
00584 
00588     Reference operator[](const Key& key) {
00589       return Reference(*this, key);
00590     }
00591 
00599     class ItemIt : public _Item {
00600     public:
00601       typedef _Item Parent;
00602 
00607       ItemIt(Invalid) : Parent(INVALID), _map(0) {}
00608 
00615       ItemIt(const IterableIntMap& map, int value) : _map(&map) {
00616         if (value < 0 || value >= (int)_map->first.size()) {      
00617           Parent::operator=(INVALID);
00618         } else {
00619           Parent::operator=(_map->first[value]);
00620         }
00621       } 
00622 
00626       ItemIt& operator++() {
00627         Parent::operator=(_map->IterableIntMap::Parent::
                          operator[](static_cast<Parent&>(*this)).next);
00628         return *this;
00629       }
00630 
00631 
00632     private:
00633       const IterableIntMap* _map;
00634     };
00635 
00636   protected:
00637     
00638     virtual void erase(const Key& key) {
00639       unlace(key);
00640       Parent::erase(key);
00641     }
00642 
00643     virtual void erase(const std::vector<Key>& keys) {
00644       for (int i = 0; i < (int)keys.size(); ++i) {
00645         unlace(keys[i]);
00646       }
00647       Parent::erase(keys);
00648     }
00649 
00650     virtual void clear() {
00651       first.clear();
00652       Parent::clear();
00653     }
00654 
00655   private:
00656     std::vector<_Item> first;
00657   };
00658 
00659   namespace _iterable_maps_bits {
00660     template <typename Item, typename Value>
00661     struct IterableValueMapNode {
00662       IterableValueMapNode(Value _value = Value()) : value(_value) {}
00663       Item prev, next;
00664       Value value;
00665     };
00666   }
00667 
00688   template <typename _Graph, typename _Item, typename _Value>
00689   class IterableValueMap : protected ItemSetTraits<_Graph, _Item> 
00690   ::template Map<_iterable_maps_bits::IterableValueMapNode<_Item, _Value> >
00691   ::Parent {
00692   public:
00693     typedef typename ItemSetTraits<_Graph, _Item> 
00694     ::template Map<_iterable_maps_bits::IterableValueMapNode<_Item, _Value> >
00695     ::Parent Parent;
00696 
00698     typedef _Item Key;
00700     typedef _Value Value;
00702     typedef _Graph Graph;
00703 
00707     explicit IterableValueMap(const Graph& graph, 
00708                               const Value& value = Value()) 
00709       : Parent(graph, _iterable_maps_bits::IterableValueMapNode<_Item, 
00710                _Value>(value)) {
00711       for (typename Parent::ItemIt it(*this); it != INVALID; ++it) {
00712         lace(it);
00713       }
00714     }
00715 
00716   private:
00717     
00718     void unlace(const Key& key) {
00719       typename Parent::Value& node = Parent::operator[](key);
00720       if (node.prev != INVALID) {
00721         Parent::operator[](node.prev).next = node.next; 
00722       } else {
00723         if (node.next != INVALID) {
00724           first[node.value] = node.next;
00725         } else {
00726           first.erase(node.value);
00727         }
00728       }
00729       if (node.next != INVALID) {
00730         Parent::operator[](node.next).prev = node.prev;
00731       }
00732     }
00733 
00734     void lace(const Key& key) {
00735       typename Parent::Value& node = Parent::operator[](key);
00736       typename std::map<Value, Key>::iterator it = first.find(node.value);
00737       if (it == first.end()) {
00738         node.prev = node.next = INVALID;
00739         if (node.next != INVALID) {
00740           Parent::operator[](node.next).prev = key;     
00741         }
00742         first.insert(make_pair(node.value, key));
00743       } else {
00744         node.prev = INVALID;
00745         node.next = it->second;
00746         if (node.next != INVALID) {
00747           Parent::operator[](node.next).prev = key;     
00748         }
00749         it->second = key;
00750       }
00751     }
00752 
00753   public:
00754 
00761     class ValueIterator 
00762       : public std::iterator<std::forward_iterator_tag, Value> {
00763       friend class IterableValueMap;
00764     private:
00765       ValueIterator(typename std::map<Value, Key>::const_iterator _it) 
00766         : it(_it) {}
00767     public:
00768       
00769       ValueIterator() {}
00770 
00771       ValueIterator& operator++() { ++it; return *this; }
00772       ValueIterator operator++(int) { 
00773         ValueIterator tmp(*this); 
00774         operator++();
00775         return tmp; 
00776       }
00777 
00778       const Value& operator*() const { return it->first; }
00779       const Value* operator->() const { return &(it->first); }
00780 
00781       bool operator==(ValueIterator jt) const { return it == jt.it; }
00782       bool operator!=(ValueIterator jt) const { return it != jt.it; }
00783       
00784     private:
00785       typename std::map<Value, Key>::const_iterator it;
00786     };
00787 
00794     ValueIterator beginValue() const {
00795       return ValueIterator(first.begin());
00796     }
00797 
00804     ValueIterator endValue() const {
00805       return ValueIterator(first.end());
00806     }
00807 
00811     void set(const Key& key, const Value& value) {
00812       unlace(key);
00813       Parent::operator[](key).value = value;
00814       lace(key);
00815     }
00816 
00820     const Value& operator[](const Key& key) const {
00821       return Parent::operator[](key).value;
00822     }
00823 
00831     class ItemIt : public _Item {
00832     public:
00833       typedef _Item Parent;
00834 
00839       ItemIt(Invalid) : Parent(INVALID), _map(0) {}
00840 
00847       ItemIt(const IterableValueMap& map, const Value& value) : _map(&map) {
00848         typename std::map<Value, Key>::const_iterator it = 
00849           map.first.find(value); 
00850         if (it == map.first.end()) {      
00851           Parent::operator=(INVALID);
00852         } else {
00853           Parent::operator=(it->second);
00854         }
00855       } 
00856 
00860       ItemIt& operator++() {
00861         Parent::operator=(_map->IterableValueMap::Parent::
                          operator[](static_cast<Parent&>(*this)).next);
00862         return *this;
00863       }
00864 
00865 
00866     private:
00867       const IterableValueMap* _map;
00868     };
00869 
00870   protected:
00871     
00872     virtual void erase(const Key& key) {
00873       unlace(key);
00874       Parent::erase(key);
00875     }
00876 
00877     virtual void erase(const std::vector<Key>& keys) {
00878       for (int i = 0; i < (int)keys.size(); ++i) {
00879         unlace(keys[i]);
00880       }
00881       Parent::erase(keys);
00882     }
00883 
00884     virtual void clear() {
00885       first.clear();
00886       Parent::clear();
00887     }
00888 
00889   private:
00890     std::map<Value, Key> first;
00891   };
00892 
00894 }
00895 

Generated on Fri Feb 3 18:37:53 2006 for LEMON by  doxygen 1.4.6