COIN-OR::LEMON - Graph Library

Changeset 1931:6abf67b02ff5 in lemon-0.x


Ignore:
Timestamp:
01/31/06 20:33:48 (14 years ago)
Author:
Balazs Dezso
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2506
Message:

New iterable map with comparable values

it uses linked lists and balanced binary tree

IterableBoolMap? has ItemIt? type as the other iterable maps

InvertableMap? got ValueIterator?

Location:
lemon
Files:
2 edited

Legend:

Unmodified
Added
Removed
  • lemon/graph_utils.h

    r1909 r1931  
    887887  /// and if a key is set to a new value then store it
    888888  /// in the inverse map.
     889  ///
     890  /// The values of the map can be accessed
     891  /// with stl compatible forward iterator.
     892  ///
    889893  /// \param _Graph The graph type.
    890894  /// \param _Item The item type of the graph.
    891895  /// \param _Value The value type of the map.
     896  ///
     897  /// \see IterableValueMap
    892898#ifndef DOXYGEN
    893899  /// \param _Map A ReadWriteMap mapping from the item type to integer.
     
    900906#endif
    901907  class InvertableMap : protected _Map {
    902 
    903   public:
    904  
    905     typedef _Map Map;
    906     typedef _Graph Graph;
     908  public:
    907909
    908910    /// The key type of InvertableMap (Node, Edge, UEdge).
     
    911913    typedef typename _Map::Value Value;
    912914
     915  private:
     916   
     917    typedef _Map Map;
     918    typedef _Graph Graph;
     919
     920    typedef std::map<Value, Key> Container;
     921    Container invMap;   
     922
     923  public:
     924 
     925
     926
    913927    /// \brief Constructor.
    914928    ///
     
    916930    ///
    917931    InvertableMap(const Graph& graph) : Map(graph) {}
     932
     933    /// \brief Forward iterator for values.
     934    ///
     935    /// This iterator is an stl compatible forward
     936    /// iterator on the values of the map. The values can
     937    /// be accessed in the [beginValue, endValue) range.
     938    ///
     939    class ValueIterator
     940      : public std::iterator<std::forward_iterator_tag, Value> {
     941      friend class InvertableMap;
     942    private:
     943      ValueIterator(typename Container::const_iterator _it)
     944        : it(_it) {}
     945    public:
     946     
     947      ValueIterator() {}
     948
     949      ValueIterator& operator++() { ++it; return *this; }
     950      ValueIterator operator++(int) {
     951        ValueIterator tmp(*this);
     952        operator++();
     953        return tmp;
     954      }
     955
     956      const Value& operator*() const { return it->first; }
     957      const Value* operator->() const { return &(it->first); }
     958
     959      bool operator==(ValueIterator jt) const { return it == jt.it; }
     960      bool operator!=(ValueIterator jt) const { return it != jt.it; }
     961     
     962    private:
     963      typename Container::const_iterator it;
     964    };
     965
     966    /// \brief Returns an iterator to the first value.
     967    ///
     968    /// Returns an stl compatible iterator to the
     969    /// first value of the map. The values of the
     970    /// map can be accessed in the [beginValue, endValue)
     971    /// range.
     972    ValueIterator beginValue() const {
     973      return ValueIterator(invMap.begin());
     974    }
     975
     976    /// \brief Returns an iterator after the last value.
     977    ///
     978    /// Returns an stl compatible iterator after the
     979    /// last value of the map. The values of the
     980    /// map can be accessed in the [beginValue, endValue)
     981    /// range.
     982    ValueIterator endValue() const {
     983      return ValueIterator(invMap.end());
     984    }
    918985   
    919986    /// \brief The setter function of the map.
     
    9331000    ///
    9341001    /// It gives back the value associated with the key.
    935     Value operator[](const Key& key) const {
     1002    typename MapTraits<Map>::ConstReturnValue
     1003    operator[](const Key& key) const {
    9361004      return Map::operator[](key);
    9371005    }
     
    9751043      Map::clear();
    9761044    }
    977 
    978   private:
    979    
    980     typedef std::map<Value, Key> Container;
    981     Container invMap;   
    9821045
    9831046  public:
     
    11411204  public:
    11421205
     1206    /// \brief Returns the maximal value plus one.
     1207    ///
     1208    /// Returns the maximal value plus one in the map.
     1209    unsigned int size() const {
     1210      return invMap.size();
     1211    }
     1212
    11431213    /// \brief Swaps the position of the two items in the map.
    11441214    ///
     
    11941264      ///
    11951265      /// Returns the size of the map.
    1196       int size() const {
     1266      unsigned int size() const {
    11971267        return inverted.invMap.size();
    11981268      }
     
    14481518        Parent::set(key, 0);
    14491519      }
     1520
    14501521      virtual void add(const std::vector<Key>& keys) {
    14511522        Parent::add(keys);
     
    14881559    }
    14891560
     1561    virtual void add(const std::vector<Edge>& edges) {
     1562      for (int i = 0; i < (int)edges.size(); ++i) {
     1563        ++deg[graph.target(edges[i])];
     1564      }
     1565    }
     1566
    14901567    virtual void erase(const Edge& edge) {
    14911568      --deg[graph.target(edge)];
     1569    }
     1570
     1571    virtual void erase(const std::vector<Edge>& edges) {
     1572      for (int i = 0; i < (int)edges.size(); ++i) {
     1573        --deg[graph.target(edges[i])];
     1574      }
    14921575    }
    14931576
     
    15921675    }
    15931676
     1677    virtual void add(const std::vector<Edge>& edges) {
     1678      for (int i = 0; i < (int)edges.size(); ++i) {
     1679        ++deg[graph.source(edges[i])];
     1680      }
     1681    }
     1682
    15941683    virtual void erase(const Edge& edge) {
    15951684      --deg[graph.source(edge)];
     1685    }
     1686
     1687    virtual void erase(const std::vector<Edge>& edges) {
     1688      for (int i = 0; i < (int)edges.size(); ++i) {
     1689        --deg[graph.source(edges[i])];
     1690      }
    15961691    }
    15971692
  • lemon/iterable_maps.h

    r1913 r1931  
    1717#include <lemon/traits.h>
    1818#include <lemon/invalid.h>
     19
    1920#include <vector>
     21#include <map>
     22
     23#include <iterator>
    2024#include <limits>
    2125
     
    3034namespace lemon {
    3135
    32   ///\ingroup maps
     36  ///\ingroup graph_maps
    3337  ///
    3438  /// \brief Dynamic iterable bool map.
     
    4650  private:
    4751    typedef _Graph Graph;
    48     typedef _Item Item;
    49    
    50     typedef typename ItemSetTraits<Graph, Item>::ItemIt ItemIt;
    51     typedef typename ItemSetTraits<Graph, Item>
     52   
     53    typedef typename ItemSetTraits<Graph, _Item>::ItemIt KeyIt;
     54    typedef typename ItemSetTraits<Graph, _Item>
    5255    ::template Map<int>::Parent Parent;
    5356   
    54     std::vector<Item> array;
     57    std::vector<_Item> array;
    5558    int sep;
    5659
    5760    const Graph& graph;
    58 
    59   private:
    60 
    61     int position(const Item& item) const {
    62       return Parent::operator[](item);
    63     }
    6461
    6562  public:
     
    6966
    7067    /// The key type
    71     typedef Item Key;
     68    typedef _Item Key;
    7269    /// The value type
    7370    typedef bool Value;
     
    7572    typedef const Value& ConstReference;
    7673
     74  private:
     75
     76    int position(const Key& key) const {
     77      return Parent::operator[](key);
     78    }
     79
     80  public:
    7781
    7882    /// \brief Refernce to the value of the map.
     
    122126    IterableBoolMap(const Graph& _graph, bool def = false)
    123127      : Parent(_graph), graph(_graph) {
    124       for (ItemIt it(graph); it != INVALID; ++it) {
     128      for (KeyIt it(graph); it != INVALID; ++it) {
    125129        Parent::set(it, array.size());
    126130        array.push_back(it);
     
    132136    ///
    133137    /// Const subscript operator of the map.
    134     bool operator[](const Item& item) const {
    135       return position(item) < sep;
     138    bool operator[](const Key& key) const {
     139      return position(key) < sep;
    136140    }
    137141
     
    139143    ///
    140144    /// Subscript operator of the map.
    141     Reference operator[](const Item& item) {
    142       return Reference(*this, item);
     145    Reference operator[](const Key& key) {
     146      return Reference(*this, key);
    143147    }
    144148
     
    146150    ///
    147151    /// Set operation of the map.
    148     void set(const Item& item, bool value) {
    149       int pos = position(item);
     152    void set(const Key& key, bool value) {
     153      int pos = position(key);
    150154      if (value) {
    151155        if (pos < sep) return;
    152         Item tmp = array[sep];
    153         array[sep] = item;
    154         Parent::set(item, sep);
     156        Key tmp = array[sep];
     157        array[sep] = key;
     158        Parent::set(key, sep);
    155159        array[pos] = tmp;
    156160        Parent::set(tmp, pos);
     
    159163        if (pos >= sep) return;
    160164        --sep;
    161         Item tmp = array[sep];
    162         array[sep] = item;
    163         Parent::set(item, sep);
     165        Key tmp = array[sep];
     166        array[sep] = key;
     167        Parent::set(key, sep);
    164168        array[pos] = tmp;
    165169        Parent::set(tmp, pos);
     
    167171    }
    168172
    169     /// \brief Returns the number of the items mapped to true.
    170     ///
    171     /// Returns the number of the items mapped to true.
     173    /// \brief Returns the number of the keys mapped to true.
     174    ///
     175    /// Returns the number of the keys mapped to true.
    172176    int trueNum() const {
    173177      return sep;
    174178    }
    175179   
    176     /// \brief Returns the number of the items mapped to false.
    177     ///
    178     /// Returns the number of the items mapped to false.
     180    /// \brief Returns the number of the keys mapped to false.
     181    ///
     182    /// Returns the number of the keys mapped to false.
    179183    int falseNum() const {
    180184      return array.size() - sep;
     
    185189    /// Iterator for the keys mapped to true. It works
    186190    /// like a graph item iterator in the map, it can be converted
    187     /// the item type of the map, incremented with \c ++ operator, and
    188     /// if the iterator leave the last valid item it will be equal to
     191    /// the key type of the map, incremented with \c ++ operator, and
     192    /// if the iterator leave the last valid key it will be equal to
    189193    /// \c INVALID.
    190     class TrueIt : public Item {
     194    class TrueIt : public Key {
    191195    public:
    192       typedef Item Parent;
     196      typedef Key Parent;
    193197     
    194198      /// \brief Creates an iterator.
     
    203207      /// \brief Invalid constructor \& conversion.
    204208      ///
    205       /// This constructor initializes the item to be invalid.
     209      /// This constructor initializes the key to be invalid.
    206210      /// \sa Invalid for more details.
    207211      TrueIt(Invalid) : Parent(INVALID), map(0) {}
     
    225229    /// Iterator for the keys mapped to false. It works
    226230    /// like a graph item iterator in the map, it can be converted
    227     /// the item type of the map, incremented with \c ++ operator, and
    228     /// if the iterator leave the last valid item it will be equal to
     231    /// the key type of the map, incremented with \c ++ operator, and
     232    /// if the iterator leave the last valid key it will be equal to
    229233    /// \c INVALID.
    230     class FalseIt : public Item {
     234    class FalseIt : public Key {
    231235    public:
    232       typedef Item Parent;
     236      typedef Key Parent;
    233237     
    234238      /// \brief Creates an iterator.
     
    238242      /// \param map The IterableIntMap
    239243      FalseIt(const IterableBoolMap& _map)
    240         : Parent(_map.sep < _map.array.size() ? _map.array.back() : INVALID),
    241           map(&_map) {}
     244        : Parent(_map.sep < (int)_map.array.size() ?
     245                 _map.array.back() : INVALID), map(&_map) {}
    242246
    243247      /// \brief Invalid constructor \& conversion.
    244248      ///
    245       /// This constructor initializes the item to be invalid.
     249      /// This constructor initializes the key to be invalid.
    246250      /// \sa Invalid for more details.
    247251      FalseIt(Invalid) : Parent(INVALID), map(0) {}
     
    260264    };
    261265
     266    /// \brief Iterator for the keys mapped to a given value.
     267    ///
     268    /// Iterator for the keys mapped to a given value. It works
     269    /// like a graph item iterator in the map, it can be converted
     270    /// the key type of the map, incremented with \c ++ operator, and
     271    /// if the iterator leave the last valid key it will be equal to
     272    /// \c INVALID.
     273    class ItemIt : public Key {
     274    public:
     275      typedef Key Parent;
     276     
     277      /// \brief Creates an iterator.
     278      ///
     279      /// Creates an iterator. It iterates on the
     280      /// keys which mapped to false.
     281      /// \param map The IterableIntMap
     282      /// \param value Which elements should be iterated.
     283      ItemIt(const IterableBoolMap& _map, bool value)
     284        : Parent(value ? (_map.sep > 0 ? _map.array[_map.sep - 1] : INVALID) :
     285                 (_map.sep < (int)_map.array.size() ?
     286                  _map.array.back() : INVALID)), map(&_map) {}
     287
     288      /// \brief Invalid constructor \& conversion.
     289      ///
     290      /// This constructor initializes the key to be invalid.
     291      /// \sa Invalid for more details.
     292      ItemIt(Invalid) : Parent(INVALID), map(0) {}
     293
     294      /// \brief Increment operator.
     295      ///
     296      /// Increment Operator.
     297      ItemIt& operator++() {
     298        int pos = map->position(*this);
     299        int sep = pos >= map->sep ? map->sep : 0;
     300        Parent::operator=(pos > sep ? map->array[pos - 1] : INVALID);
     301        return *this;
     302      }
     303
     304    private:
     305      const IterableBoolMap* map;
     306    };
     307
    262308  protected:
    263309   
    264     virtual void add(const Item& item) {
    265       Parent::add(item);
    266       Parent::set(item, array.size());
    267       array.push_back(item);
    268     }
    269 
    270     virtual void add(const std::vector<Item>& items) {
    271       Parent::add(items);
    272       for (int i = 0; i < (int)items.size(); ++i) {
    273         Parent::set(items[i], array.size());
    274         array.push_back(items[i]);
    275       }
    276     }
    277 
    278     virtual void erase(const Item& item) {
    279       int pos = position(item);
     310    virtual void add(const Key& key) {
     311      Parent::add(key);
     312      Parent::set(key, array.size());
     313      array.push_back(key);
     314    }
     315
     316    virtual void add(const std::vector<Key>& keys) {
     317      Parent::add(keys);
     318      for (int i = 0; i < (int)keys.size(); ++i) {
     319        Parent::set(keys[i], array.size());
     320        array.push_back(keys[i]);
     321      }
     322    }
     323
     324    virtual void erase(const Key& key) {
     325      int pos = position(key);
    280326      if (pos < sep) {
    281327        --sep;
     
    290336        array.pop_back();
    291337      }
    292       Parent::erase(item);
    293     }
    294 
    295     virtual void erase(const std::vector<Item>& items) {
    296       for (int i = 0; i < (int)items.size(); ++i) {
    297         int pos = position(items[i]);
     338      Parent::erase(key);
     339    }
     340
     341    virtual void erase(const std::vector<Key>& keys) {
     342      for (int i = 0; i < (int)keys.size(); ++i) {
     343        int pos = position(keys[i]);
    298344        if (pos < sep) {
    299345          --sep;
     
    309355        }
    310356      }
    311       Parent::erase(items);
     357      Parent::erase(keys);
    312358    }   
    313359
    314360    virtual void build() {
    315361      Parent::build();
    316       for (ItemIt it(graph); it != INVALID; ++it) {
     362      for (KeyIt it(graph); it != INVALID; ++it) {
    317363        Parent::set(it, array.size());
    318364        array.push_back(it);
     
    340386  }
    341387
    342   ///\ingroup maps
     388  ///\ingroup graph_maps
    343389  ///
    344390  /// \brief Dynamic iterable integer map.
     
    515561    ///
    516562    /// Gives back the maximal value plus one.
    517     int size() const {
    518       return (int)first.size();
     563    unsigned int size() const {
     564      return first.size();
    519565    }
    520566   
     
    595641
    596642    virtual void erase(const std::vector<Key>& keys) {
    597       for (int i = 0; i < keys.size(); ++i) {
     643      for (int i = 0; i < (int)keys.size(); ++i) {
    598644        unlace(keys[i]);
    599645      }
     
    610656  };
    611657
     658  namespace _iterable_maps_bits {
     659    template <typename Item, typename Value>
     660    struct IterableValueMapNode {
     661      IterableValueMapNode(Value _value = Value()) : value(_value) {}
     662      Item prev, next;
     663      Value value;
     664    };
     665  }
     666
     667  ///\ingroup graph_maps
     668  ///
     669  /// \brief Dynamic iterable map for comparable values.
     670  ///
     671  /// This class provides a special graph map type which can store
     672  /// for each graph item(node, edge, etc.) a value. For each
     673  /// value it is possible to iterate on the keys which mapped to the
     674  /// given value. The type stores for each value a linked list with
     675  /// the items which mapped to the value, and the values are stored
     676  /// in balanced binary tree. The values of the map can be accessed
     677  /// with stl compatible forward iterator.
     678  ///
     679  /// This type is not reference map so it cannot be modified with
     680  /// the subscription operator.
     681  ///
     682  /// \see InvertableMap
     683  ///
     684  /// \param _Graph The graph type.
     685  /// \param _Item One of the graph's item type, the key of the map.
     686  /// \param _Value Any comparable value type.
     687  template <typename _Graph, typename _Item, typename _Value>
     688  class IterableValueMap : protected ItemSetTraits<_Graph, _Item>
     689  ::template Map<_iterable_maps_bits::IterableValueMapNode<_Item, _Value> >
     690  ::Parent {
     691  public:
     692    typedef typename ItemSetTraits<_Graph, _Item>
     693    ::template Map<_iterable_maps_bits::IterableValueMapNode<_Item, _Value> >
     694    ::Parent Parent;
     695
     696    /// The key type
     697    typedef _Item Key;
     698    /// The value type
     699    typedef _Value Value;
     700    /// The graph type
     701    typedef _Graph Graph;
     702
     703    /// \brief Constructor of the Map with a given value.
     704    ///
     705    /// Constructor of the Map with a given value.
     706    explicit IterableValueMap(const Graph& graph,
     707                              const Value& value = Value())
     708      : Parent(graph, _iterable_maps_bits::IterableValueMapNode<_Item,
     709               _Value>(value)) {
     710      for (typename Parent::ItemIt it(*this); it != INVALID; ++it) {
     711        lace(it);
     712      }
     713    }
     714
     715  private:
     716   
     717    void unlace(const Key& key) {
     718      typename Parent::Value& node = Parent::operator[](key);
     719      if (node.prev != INVALID) {
     720        Parent::operator[](node.prev).next = node.next;
     721      } else {
     722        if (node.next != INVALID) {
     723          first[node.value] = node.next;
     724        } else {
     725          first.erase(node.value);
     726        }
     727      }
     728      if (node.next != INVALID) {
     729        Parent::operator[](node.next).prev = node.prev;
     730      }
     731    }
     732
     733    void lace(const Key& key) {
     734      typename Parent::Value& node = Parent::operator[](key);
     735      typename std::map<Value, Key>::iterator it = first.find(node.value);
     736      if (it == first.end()) {
     737        node.prev = node.next = INVALID;
     738        if (node.next != INVALID) {
     739          Parent::operator[](node.next).prev = key;     
     740        }
     741        first.insert(make_pair(node.value, key));
     742      } else {
     743        node.prev = INVALID;
     744        node.next = it->second;
     745        if (node.next != INVALID) {
     746          Parent::operator[](node.next).prev = key;     
     747        }
     748        it->second = key;
     749      }
     750    }
     751
     752  public:
     753
     754    /// \brief Forward iterator for values.
     755    ///
     756    /// This iterator is an stl compatible forward
     757    /// iterator on the values of the map. The values can
     758    /// be accessed in the [beginValue, endValue) range.
     759    ///
     760    class ValueIterator
     761      : public std::iterator<std::forward_iterator_tag, Value> {
     762      friend class IterableValueMap;
     763    private:
     764      ValueIterator(typename std::map<Value, Key>::const_iterator _it)
     765        : it(_it) {}
     766    public:
     767     
     768      ValueIterator() {}
     769
     770      ValueIterator& operator++() { ++it; return *this; }
     771      ValueIterator operator++(int) {
     772        ValueIterator tmp(*this);
     773        operator++();
     774        return tmp;
     775      }
     776
     777      const Value& operator*() const { return it->first; }
     778      const Value* operator->() const { return &(it->first); }
     779
     780      bool operator==(ValueIterator jt) const { return it == jt.it; }
     781      bool operator!=(ValueIterator jt) const { return it != jt.it; }
     782     
     783    private:
     784      typename std::map<Value, Key>::const_iterator it;
     785    };
     786
     787    /// \brief Returns an iterator to the first value.
     788    ///
     789    /// Returns an stl compatible iterator to the
     790    /// first value of the map. The values of the
     791    /// map can be accessed in the [beginValue, endValue)
     792    /// range.
     793    ValueIterator beginValue() const {
     794      return ValueIterator(first.begin());
     795    }
     796
     797    /// \brief Returns an iterator after the last value.
     798    ///
     799    /// Returns an stl compatible iterator after the
     800    /// last value of the map. The values of the
     801    /// map can be accessed in the [beginValue, endValue)
     802    /// range.
     803    ValueIterator endValue() const {
     804      return ValueIterator(first.end());
     805    }
     806
     807    /// \brief Set operation of the map.
     808    ///
     809    /// Set operation of the map.
     810    void set(const Key& key, const Value& value) {
     811      unlace(key);
     812      Parent::operator[](key).value = value;
     813      lace(key);
     814    }
     815
     816    /// \brief Const subscript operator of the map.
     817    ///
     818    /// Const subscript operator of the map.
     819    const Value& operator[](const Key& key) const {
     820      return Parent::operator[](key).value;
     821    }
     822
     823    /// \brief Iterator for the keys with the same value.
     824    ///
     825    /// Iterator for the keys with the same value. It works
     826    /// like a graph item iterator in the map, it can be converted
     827    /// the item type of the map, incremented with \c ++ operator, and
     828    /// if the iterator leave the last valid item it will be equal to
     829    /// \c INVALID.
     830    class ItemIt : public _Item {
     831    public:
     832      typedef _Item Parent;
     833
     834      /// \brief Invalid constructor \& conversion.
     835      ///
     836      /// This constructor initializes the item to be invalid.
     837      /// \sa Invalid for more details.
     838      ItemIt(Invalid) : Parent(INVALID), _map(0) {}
     839
     840      /// \brief Creates an iterator with a value.
     841      ///
     842      /// Creates an iterator with a value. It iterates on the
     843      /// keys which have the given value.
     844      /// \param map The IterableValueMap
     845      /// \param value The value
     846      ItemIt(const IterableValueMap& map, const Value& value) : _map(&map) {
     847        typename std::map<Value, Key>::const_iterator it =
     848          map.first.find(value);
     849        if (it == map.first.end()) {     
     850          Parent::operator=(INVALID);
     851        } else {
     852          Parent::operator=(it->second);
     853        }
     854      }
     855
     856      /// \brief Increment operator.
     857      ///
     858      /// Increment Operator.
     859      ItemIt& operator++() {
     860        Parent::operator=(_map->IterableValueMap::Parent::
     861                          operator[](static_cast<Parent&>(*this)).next);
     862        return *this;
     863      }
     864
     865
     866    private:
     867      const IterableValueMap* _map;
     868    };
     869
     870  protected:
     871   
     872    virtual void erase(const Key& key) {
     873      unlace(key);
     874      Parent::erase(key);
     875    }
     876
     877    virtual void erase(const std::vector<Key>& keys) {
     878      for (int i = 0; i < (int)keys.size(); ++i) {
     879        unlace(keys[i]);
     880      }
     881      Parent::erase(keys);
     882    }
     883
     884    virtual void clear() {
     885      first.clear();
     886      Parent::clear();
     887    }
     888
     889  private:
     890    std::map<Value, Key> first;
     891  };
     892
    612893  /// @}
    613894}
Note: See TracChangeset for help on using the changeset viewer.