COIN-OR::LEMON - Graph Library

Changeset 1931:6abf67b02ff5 in lemon-0.x for lemon/graph_utils.h


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?

File:
1 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
Note: See TracChangeset for help on using the changeset viewer.