COIN-OR::LEMON - Graph Library

Changeset 320:12626fc94ccf in lemon-1.0 for lemon/maps.h


Ignore:
Timestamp:
10/09/08 15:37:44 (11 years ago)
Author:
Alpar Juttner <alpar@…>
Branch:
1.0
Parents:
303:de38fca76780 (diff), 319:c175e387da19 (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.
Phase:
public
Message:

Merge from trunk

Files:
2 edited

Legend:

Unmodified
Added
Removed
  • lemon/maps.h

    r301 r320  
    4444  class MapBase {
    4545  public:
    46     /// \biref The key type of the map.
     46    /// \brief The key type of the map.
    4747    typedef K Key;
    4848    /// \brief The value type of the map.
     
    7474  };
    7575
    76   /// Returns a \ref NullMap class
    77 
    78   /// This function just returns a \ref NullMap class.
     76  /// Returns a \c NullMap class
     77
     78  /// This function just returns a \c NullMap class.
    7979  /// \relates NullMap
    8080  template <typename K, typename V>
     
    8989  /// value to each key.
    9090  ///
    91   /// In other aspects it is equivalent to \ref NullMap.
     91  /// In other aspects it is equivalent to \c NullMap.
    9292  /// So it conforms the \ref concepts::ReadWriteMap "ReadWriteMap"
    9393  /// concept, but it absorbs the data written to it.
     
    134134  };
    135135
    136   /// Returns a \ref ConstMap class
    137 
    138   /// This function just returns a \ref ConstMap class.
     136  /// Returns a \c ConstMap class
     137
     138  /// This function just returns a \c ConstMap class.
    139139  /// \relates ConstMap
    140140  template<typename K, typename V>
     
    157157  /// value to each key.
    158158  ///
    159   /// In other aspects it is equivalent to \ref NullMap.
     159  /// In other aspects it is equivalent to \c NullMap.
    160160  /// So it conforms the \ref concepts::ReadWriteMap "ReadWriteMap"
    161161  /// concept, but it absorbs the data written to it.
     
    183183  };
    184184
    185   /// Returns a \ref ConstMap class with inlined constant value
    186 
    187   /// This function just returns a \ref ConstMap class with inlined
     185  /// Returns a \c ConstMap class with inlined constant value
     186
     187  /// This function just returns a \c ConstMap class with inlined
    188188  /// constant value.
    189189  /// \relates ConstMap
     
    213213  };
    214214
    215   /// Returns an \ref IdentityMap class
    216 
    217   /// This function just returns an \ref IdentityMap class.
     215  /// Returns an \c IdentityMap class
     216
     217  /// This function just returns an \c IdentityMap class.
    218218  /// \relates IdentityMap
    219219  template<typename T>
     
    229229  /// values to integer keys from the range <tt>[0..size-1]</tt>.
    230230  /// It can be used with some data structures, for example
    231   /// \ref UnionFind, \ref BinHeap, when the used items are small
     231  /// \c UnionFind, \c BinHeap, when the used items are small
    232232  /// integers. This map conforms the \ref concepts::ReferenceMap
    233233  /// "ReferenceMap" concept.
     
    269269      : _vector(vector.begin(), vector.end()) {}
    270270
    271     /// Constructs the map from another \ref RangeMap.
     271    /// Constructs the map from another \c RangeMap.
    272272    template <typename V1>
    273273    RangeMap(const RangeMap<V1> &c)
     
    312312  };
    313313
    314   /// Returns a \ref RangeMap class
    315 
    316   /// This function just returns a \ref RangeMap class.
     314  /// Returns a \c RangeMap class
     315
     316  /// This function just returns a \c RangeMap class.
    317317  /// \relates RangeMap
    318318  template<typename V>
     
    321321  }
    322322
    323   /// \brief Returns a \ref RangeMap class created from an appropriate
     323  /// \brief Returns a \c RangeMap class created from an appropriate
    324324  /// \c std::vector
    325325
    326   /// This function just returns a \ref RangeMap class created from an
     326  /// This function just returns a \c RangeMap class created from an
    327327  /// appropriate \c std::vector.
    328328  /// \relates RangeMap
     
    389389      : _map(map.begin(), map.end()), _value(value) {}
    390390
    391     /// \brief Constructs the map from another \ref SparseMap.
     391    /// \brief Constructs the map from another \c SparseMap.
    392392    template<typename V1, typename Comp1>
    393393    SparseMap(const SparseMap<Key, V1, Comp1> &c)
     
    434434  };
    435435
    436   /// Returns a \ref SparseMap class
    437 
    438   /// This function just returns a \ref SparseMap class with specified
     436  /// Returns a \c SparseMap class
     437
     438  /// This function just returns a \c SparseMap class with specified
    439439  /// default value.
    440440  /// \relates SparseMap
     
    449449  }
    450450
    451   /// \brief Returns a \ref SparseMap class created from an appropriate
     451  /// \brief Returns a \c SparseMap class created from an appropriate
    452452  /// \c std::map
    453453
    454   /// This function just returns a \ref SparseMap class created from an
     454  /// This function just returns a \c SparseMap class created from an
    455455  /// appropriate \c std::map.
    456456  /// \relates SparseMap
     
    502502  };
    503503
    504   /// Returns a \ref ComposeMap class
    505 
    506   /// This function just returns a \ref ComposeMap class.
     504  /// Returns a \c ComposeMap class
     505
     506  /// This function just returns a \c ComposeMap class.
    507507  ///
    508508  /// If \c m1 and \c m2 are maps and the \c Value type of \c m2 is
     
    557557  };
    558558
    559   /// Returns a \ref CombineMap class
    560 
    561   /// This function just returns a \ref CombineMap class.
     559  /// Returns a \c CombineMap class
     560
     561  /// This function just returns a \c CombineMap class.
    562562  ///
    563563  /// For example, if \c m1 and \c m2 are both maps with \c double
     
    626626  };
    627627
    628   /// Returns a \ref FunctorToMap class
    629 
    630   /// This function just returns a \ref FunctorToMap class.
     628  /// Returns a \c FunctorToMap class
     629
     630  /// This function just returns a \c FunctorToMap class.
    631631  ///
    632632  /// This function is specialized for adaptable binary function
     
    685685  };
    686686
    687   /// Returns a \ref MapToFunctor class
    688 
    689   /// This function just returns a \ref MapToFunctor class.
     687  /// Returns a \c MapToFunctor class
     688
     689  /// This function just returns a \c MapToFunctor class.
    690690  /// \relates MapToFunctor
    691691  template<typename M>
     
    724724  };
    725725
    726   /// Returns a \ref ConvertMap class
    727 
    728   /// This function just returns a \ref ConvertMap class.
     726  /// Returns a \c ConvertMap class
     727
     728  /// This function just returns a \c ConvertMap class.
    729729  /// \relates ConvertMap
    730730  template<typename V, typename M>
     
    764764  };
    765765
    766   /// Returns a \ref ForkMap class
    767 
    768   /// This function just returns a \ref ForkMap class.
     766  /// Returns a \c ForkMap class
     767
     768  /// This function just returns a \c ForkMap class.
    769769  /// \relates ForkMap
    770770  template <typename M1, typename M2>
     
    808808  };
    809809
    810   /// Returns an \ref AddMap class
    811 
    812   /// This function just returns an \ref AddMap class.
     810  /// Returns an \c AddMap class
     811
     812  /// This function just returns an \c AddMap class.
    813813  ///
    814814  /// For example, if \c m1 and \c m2 are both maps with \c double
     
    856856  };
    857857
    858   /// Returns a \ref SubMap class
    859 
    860   /// This function just returns a \ref SubMap class.
     858  /// Returns a \c SubMap class
     859
     860  /// This function just returns a \c SubMap class.
    861861  ///
    862862  /// For example, if \c m1 and \c m2 are both maps with \c double
     
    905905  };
    906906
    907   /// Returns a \ref MulMap class
    908 
    909   /// This function just returns a \ref MulMap class.
     907  /// Returns a \c MulMap class
     908
     909  /// This function just returns a \c MulMap class.
    910910  ///
    911911  /// For example, if \c m1 and \c m2 are both maps with \c double
     
    953953  };
    954954
    955   /// Returns a \ref DivMap class
    956 
    957   /// This function just returns a \ref DivMap class.
     955  /// Returns a \c DivMap class
     956
     957  /// This function just returns a \c DivMap class.
    958958  ///
    959959  /// For example, if \c m1 and \c m2 are both maps with \c double
     
    10391039  };
    10401040
    1041   /// Returns a \ref ShiftMap class
    1042 
    1043   /// This function just returns a \ref ShiftMap class.
     1041  /// Returns a \c ShiftMap class
     1042
     1043  /// This function just returns a \c ShiftMap class.
    10441044  ///
    10451045  /// For example, if \c m is a map with \c double values and \c v is
     
    10531053  }
    10541054
    1055   /// Returns a \ref ShiftWriteMap class
    1056 
    1057   /// This function just returns a \ref ShiftWriteMap class.
     1055  /// Returns a \c ShiftWriteMap class
     1056
     1057  /// This function just returns a \c ShiftWriteMap class.
    10581058  ///
    10591059  /// For example, if \c m is a map with \c double values and \c v is
     
    11411141  };
    11421142
    1143   /// Returns a \ref ScaleMap class
    1144 
    1145   /// This function just returns a \ref ScaleMap class.
     1143  /// Returns a \c ScaleMap class
     1144
     1145  /// This function just returns a \c ScaleMap class.
    11461146  ///
    11471147  /// For example, if \c m is a map with \c double values and \c v is
     
    11551155  }
    11561156
    1157   /// Returns a \ref ScaleWriteMap class
    1158 
    1159   /// This function just returns a \ref ScaleWriteMap class.
     1157  /// Returns a \c ScaleWriteMap class
     1158
     1159  /// This function just returns a \c ScaleWriteMap class.
    11601160  ///
    11611161  /// For example, if \c m is a map with \c double values and \c v is
     
    12411241  };
    12421242
    1243   /// Returns a \ref NegMap class
    1244 
    1245   /// This function just returns a \ref NegMap class.
     1243  /// Returns a \c NegMap class
     1244
     1245  /// This function just returns a \c NegMap class.
    12461246  ///
    12471247  /// For example, if \c m is a map with \c double values, then
     
    12541254  }
    12551255
    1256   /// Returns a \ref NegWriteMap class
    1257 
    1258   /// This function just returns a \ref NegWriteMap class.
     1256  /// Returns a \c NegWriteMap class
     1257
     1258  /// This function just returns a \c NegWriteMap class.
    12591259  ///
    12601260  /// For example, if \c m is a map with \c double values, then
     
    12971297  };
    12981298
    1299   /// Returns an \ref AbsMap class
    1300 
    1301   /// This function just returns an \ref AbsMap class.
     1299  /// Returns an \c AbsMap class
     1300
     1301  /// This function just returns an \c AbsMap class.
    13021302  ///
    13031303  /// For example, if \c m is a map with \c double values, then
     
    13461346  };
    13471347
    1348   /// Returns a \ref TrueMap class
    1349 
    1350   /// This function just returns a \ref TrueMap class.
     1348  /// Returns a \c TrueMap class
     1349
     1350  /// This function just returns a \c TrueMap class.
    13511351  /// \relates TrueMap
    13521352  template<typename K>
     
    13831383  };
    13841384
    1385   /// Returns a \ref FalseMap class
    1386 
    1387   /// This function just returns a \ref FalseMap class.
     1385  /// Returns a \c FalseMap class
     1386
     1387  /// This function just returns a \c FalseMap class.
    13881388  /// \relates FalseMap
    13891389  template<typename K>
     
    14301430  };
    14311431
    1432   /// Returns an \ref AndMap class
    1433 
    1434   /// This function just returns an \ref AndMap class.
     1432  /// Returns an \c AndMap class
     1433
     1434  /// This function just returns an \c AndMap class.
    14351435  ///
    14361436  /// For example, if \c m1 and \c m2 are both maps with \c bool values,
     
    14781478  };
    14791479
    1480   /// Returns an \ref OrMap class
    1481 
    1482   /// This function just returns an \ref OrMap class.
     1480  /// Returns an \c OrMap class
     1481
     1482  /// This function just returns an \c OrMap class.
    14831483  ///
    14841484  /// For example, if \c m1 and \c m2 are both maps with \c bool values,
     
    15451545  };
    15461546
    1547   /// Returns a \ref NotMap class
    1548 
    1549   /// This function just returns a \ref NotMap class.
     1547  /// Returns a \c NotMap class
     1548
     1549  /// This function just returns a \c NotMap class.
    15501550  ///
    15511551  /// For example, if \c m is a map with \c bool values, then
     
    15581558  }
    15591559
    1560   /// Returns a \ref NotWriteMap class
    1561 
    1562   /// This function just returns a \ref NotWriteMap class.
     1560  /// Returns a \c NotWriteMap class
     1561
     1562  /// This function just returns a \c NotWriteMap class.
    15631563  ///
    15641564  /// For example, if \c m is a map with \c bool values, then
     
    16061606  };
    16071607
    1608   /// Returns an \ref EqualMap class
    1609 
    1610   /// This function just returns an \ref EqualMap class.
     1608  /// Returns an \c EqualMap class
     1609
     1610  /// This function just returns an \c EqualMap class.
    16111611  ///
    16121612  /// For example, if \c m1 and \c m2 are maps with keys and values of
     
    16541654  };
    16551655
    1656   /// Returns an \ref LessMap class
    1657 
    1658   /// This function just returns an \ref LessMap class.
     1656  /// Returns an \c LessMap class
     1657
     1658  /// This function just returns an \c LessMap class.
    16591659  ///
    16601660  /// For example, if \c m1 and \c m2 are maps with keys and values of
     
    16831683
    16841684  }
     1685
     1686  /// @}
     1687
     1688  /// \addtogroup maps
     1689  /// @{
    16851690
    16861691  /// \brief Writable bool map for logging each \c true assigned element
     
    17461751  };
    17471752
    1748   /// Returns a \ref LoggerBoolMap class
    1749 
    1750   /// This function just returns a \ref LoggerBoolMap class.
     1753  /// Returns a \c LoggerBoolMap class
     1754
     1755  /// This function just returns a \c LoggerBoolMap class.
    17511756  ///
    17521757  /// The most important usage of it is storing certain nodes or arcs
     
    17681773  /// \note LoggerBoolMap is just \ref concepts::WriteMap "writable", so
    17691774  /// it cannot be used when a readable map is needed, for example as
    1770   /// \c ReachedMap for \ref Bfs, \ref Dfs and \ref Dijkstra algorithms.
     1775  /// \c ReachedMap for \c Bfs, \c Dfs and \c Dijkstra algorithms.
    17711776  ///
    17721777  /// \relates LoggerBoolMap
     
    17751780    return LoggerBoolMap<Iterator>(it);
    17761781  }
     1782
     1783  /// @}
     1784
     1785  /// \addtogroup graph_maps
     1786  /// @{
    17771787
    17781788  /// Provides an immutable and unique id for each item in the graph.
     
    18621872    ///
    18631873    /// Constructor
    1864     /// \param _digraph The digraph that the map belongs to.
     1874    /// \param digraph The digraph that the map belongs to.
    18651875    explicit SourceMap(const Digraph& digraph) : _digraph(digraph) {}
    18661876
     
    18781888  };
    18791889
    1880   /// \brief Returns a \ref SourceMap class.
    1881   ///
    1882   /// This function just returns an \ref SourceMap class.
     1890  /// \brief Returns a \c SourceMap class.
     1891  ///
     1892  /// This function just returns an \c SourceMap class.
    18831893  /// \relates SourceMap
    18841894  template <typename Digraph>
     
    19011911    ///
    19021912    /// Constructor
    1903     /// \param _digraph The digraph that the map belongs to.
     1913    /// \param digraph The digraph that the map belongs to.
    19041914    explicit TargetMap(const Digraph& digraph) : _digraph(digraph) {}
    19051915
     
    19171927  };
    19181928
    1919   /// \brief Returns a \ref TargetMap class.
    1920   ///
    1921   /// This function just returns a \ref TargetMap class.
     1929  /// \brief Returns a \c TargetMap class.
     1930  ///
     1931  /// This function just returns a \c TargetMap class.
    19221932  /// \relates TargetMap
    19231933  template <typename Digraph>
     
    19401950    ///
    19411951    /// Constructor
    1942     /// \param _graph The graph that the map belongs to.
     1952    /// \param graph The graph that the map belongs to.
    19431953    explicit ForwardMap(const Graph& graph) : _graph(graph) {}
    19441954
     
    19561966  };
    19571967
    1958   /// \brief Returns a \ref ForwardMap class.
    1959   ///
    1960   /// This function just returns an \ref ForwardMap class.
     1968  /// \brief Returns a \c ForwardMap class.
     1969  ///
     1970  /// This function just returns an \c ForwardMap class.
    19611971  /// \relates ForwardMap
    19621972  template <typename Graph>
     
    19791989    ///
    19801990    /// Constructor
    1981     /// \param _graph The graph that the map belongs to.
     1991    /// \param graph The graph that the map belongs to.
    19821992    explicit BackwardMap(const Graph& graph) : _graph(graph) {}
    19831993
     
    19952005  };
    19962006
    1997   /// \brief Returns a \ref BackwardMap class
    1998 
    1999   /// This function just returns a \ref BackwardMap class.
     2007  /// \brief Returns a \c BackwardMap class
     2008
     2009  /// This function just returns a \c BackwardMap class.
    20002010  /// \relates BackwardMap
    20012011  template <typename Graph>
  • lemon/maps.h

    r318 r320  
    18561856    InverseMap inverse() const { return InverseMap(*_graph);}
    18571857
    1858   };
    1859 
    1860 
    1861   /// \brief General invertable graph-map type.
    1862 
    1863   /// This type provides simple invertable graph-maps.
    1864   /// The InvertableMap wraps an arbitrary ReadWriteMap
    1865   /// and if a key is set to a new value then store it
    1866   /// in the inverse map.
    1867   ///
    1868   /// The values of the map can be accessed
    1869   /// with stl compatible forward iterator.
    1870   ///
    1871   /// \tparam _Graph The graph type.
    1872   /// \tparam _Item The item type of the graph.
    1873   /// \tparam _Value The value type of the map.
    1874   ///
    1875   /// \see IterableValueMap
    1876   template <typename _Graph, typename _Item, typename _Value>
    1877   class InvertableMap
    1878     : protected ItemSetTraits<_Graph, _Item>::template Map<_Value>::Type {
    1879   private:
    1880 
    1881     typedef typename ItemSetTraits<_Graph, _Item>::
    1882     template Map<_Value>::Type Map;
    1883     typedef _Graph Graph;
    1884 
    1885     typedef std::map<_Value, _Item> Container;
    1886     Container _inv_map;
    1887 
    1888   public:
    1889 
    1890     /// The key type of InvertableMap (Node, Arc, Edge).
    1891     typedef typename Map::Key Key;
    1892     /// The value type of the InvertableMap.
    1893     typedef typename Map::Value Value;
    1894 
    1895     /// \brief Constructor.
    1896     ///
    1897     /// Construct a new InvertableMap for the graph.
    1898     ///
    1899     explicit InvertableMap(const Graph& graph) : Map(graph) {}
    1900 
    1901     /// \brief Forward iterator for values.
    1902     ///
    1903     /// This iterator is an stl compatible forward
    1904     /// iterator on the values of the map. The values can
    1905     /// be accessed in the [beginValue, endValue) range.
    1906     ///
    1907     class ValueIterator
    1908       : public std::iterator<std::forward_iterator_tag, Value> {
    1909       friend class InvertableMap;
    1910     private:
    1911       ValueIterator(typename Container::const_iterator _it)
    1912         : it(_it) {}
    1913     public:
    1914 
    1915       ValueIterator() {}
    1916 
    1917       ValueIterator& operator++() { ++it; return *this; }
    1918       ValueIterator operator++(int) {
    1919         ValueIterator tmp(*this);
    1920         operator++();
    1921         return tmp;
    1922       }
    1923 
    1924       const Value& operator*() const { return it->first; }
    1925       const Value* operator->() const { return &(it->first); }
    1926 
    1927       bool operator==(ValueIterator jt) const { return it == jt.it; }
    1928       bool operator!=(ValueIterator jt) const { return it != jt.it; }
    1929 
    1930     private:
    1931       typename Container::const_iterator it;
    1932     };
    1933 
    1934     /// \brief Returns an iterator to the first value.
    1935     ///
    1936     /// Returns an stl compatible iterator to the
    1937     /// first value of the map. The values of the
    1938     /// map can be accessed in the [beginValue, endValue)
    1939     /// range.
    1940     ValueIterator beginValue() const {
    1941       return ValueIterator(_inv_map.begin());
    1942     }
    1943 
    1944     /// \brief Returns an iterator after the last value.
    1945     ///
    1946     /// Returns an stl compatible iterator after the
    1947     /// last value of the map. The values of the
    1948     /// map can be accessed in the [beginValue, endValue)
    1949     /// range.
    1950     ValueIterator endValue() const {
    1951       return ValueIterator(_inv_map.end());
    1952     }
    1953 
    1954     /// \brief The setter function of the map.
    1955     ///
    1956     /// Sets the mapped value.
    1957     void set(const Key& key, const Value& val) {
    1958       Value oldval = Map::operator[](key);
    1959       typename Container::iterator it = _inv_map.find(oldval);
    1960       if (it != _inv_map.end() && it->second == key) {
    1961         _inv_map.erase(it);
    1962       }
    1963       _inv_map.insert(make_pair(val, key));
    1964       Map::set(key, val);
    1965     }
    1966 
    1967     /// \brief The getter function of the map.
    1968     ///
    1969     /// It gives back the value associated with the key.
    1970     typename MapTraits<Map>::ConstReturnValue
    1971     operator[](const Key& key) const {
    1972       return Map::operator[](key);
    1973     }
    1974 
    1975     /// \brief Gives back the item by its value.
    1976     ///
    1977     /// Gives back the item by its value.
    1978     Key operator()(const Value& key) const {
    1979       typename Container::const_iterator it = _inv_map.find(key);
    1980       return it != _inv_map.end() ? it->second : INVALID;
    1981     }
    1982 
    1983   protected:
    1984 
    1985     /// \brief Erase the key from the map.
    1986     ///
    1987     /// Erase the key to the map. It is called by the
    1988     /// \c AlterationNotifier.
    1989     virtual void erase(const Key& key) {
    1990       Value val = Map::operator[](key);
    1991       typename Container::iterator it = _inv_map.find(val);
    1992       if (it != _inv_map.end() && it->second == key) {
    1993         _inv_map.erase(it);
    1994       }
    1995       Map::erase(key);
    1996     }
    1997 
    1998     /// \brief Erase more keys from the map.
    1999     ///
    2000     /// Erase more keys from the map. It is called by the
    2001     /// \c AlterationNotifier.
    2002     virtual void erase(const std::vector<Key>& keys) {
    2003       for (int i = 0; i < int(keys.size()); ++i) {
    2004         Value val = Map::operator[](keys[i]);
    2005         typename Container::iterator it = _inv_map.find(val);
    2006         if (it != _inv_map.end() && it->second == keys[i]) {
    2007           _inv_map.erase(it);
    2008         }
    2009       }
    2010       Map::erase(keys);
    2011     }
    2012 
    2013     /// \brief Clear the keys from the map and inverse map.
    2014     ///
    2015     /// Clear the keys from the map and inverse map. It is called by the
    2016     /// \c AlterationNotifier.
    2017     virtual void clear() {
    2018       _inv_map.clear();
    2019       Map::clear();
    2020     }
    2021 
    2022   public:
    2023 
    2024     /// \brief The inverse map type.
    2025     ///
    2026     /// The inverse of this map. The subscript operator of the map
    2027     /// gives back always the item what was last assigned to the value.
    2028     class InverseMap {
    2029     public:
    2030       /// \brief Constructor of the InverseMap.
    2031       ///
    2032       /// Constructor of the InverseMap.
    2033       explicit InverseMap(const InvertableMap& inverted)
    2034         : _inverted(inverted) {}
    2035 
    2036       /// The value type of the InverseMap.
    2037       typedef typename InvertableMap::Key Value;
    2038       /// The key type of the InverseMap.
    2039       typedef typename InvertableMap::Value Key;
    2040 
    2041       /// \brief Subscript operator.
    2042       ///
    2043       /// Subscript operator. It gives back always the item
    2044       /// what was last assigned to the value.
    2045       Value operator[](const Key& key) const {
    2046         return _inverted(key);
    2047       }
    2048 
    2049     private:
    2050       const InvertableMap& _inverted;
    2051     };
    2052 
    2053     /// \brief It gives back the just readable inverse map.
    2054     ///
    2055     /// It gives back the just readable inverse map.
    2056     InverseMap inverse() const {
    2057       return InverseMap(*this);
    2058     }
    2059 
    2060   };
    2061 
    2062   /// \brief Provides a mutable, continuous and unique descriptor for each
    2063   /// item in the graph.
    2064   ///
    2065   /// The DescriptorMap class provides a unique and continuous (but mutable)
    2066   /// descriptor (id) for each item of the same type (e.g. node) in the
    2067   /// graph. This id is <ul><li>\b unique: different items (nodes) get
    2068   /// different ids <li>\b continuous: the range of the ids is the set of
    2069   /// integers between 0 and \c n-1, where \c n is the number of the items of
    2070   /// this type (e.g. nodes) (so the id of a node can change if you delete an
    2071   /// other node, i.e. this id is mutable).  </ul> This map can be inverted
    2072   /// with its member class \c InverseMap, or with the \c operator() member.
    2073   ///
    2074   /// \tparam _Graph The graph class the \c DescriptorMap belongs to.
    2075   /// \tparam _Item The Item is the Key of the Map. It may be Node, Arc or
    2076   /// Edge.
    2077   template <typename _Graph, typename _Item>
    2078   class DescriptorMap
    2079     : protected ItemSetTraits<_Graph, _Item>::template Map<int>::Type {
    2080 
    2081     typedef _Item Item;
    2082     typedef typename ItemSetTraits<_Graph, _Item>::template Map<int>::Type Map;
    2083 
    2084   public:
    2085     /// The graph class of DescriptorMap.
    2086     typedef _Graph Graph;
    2087 
    2088     /// The key type of DescriptorMap (Node, Arc, Edge).
    2089     typedef typename Map::Key Key;
    2090     /// The value type of DescriptorMap.
    2091     typedef typename Map::Value Value;
    2092 
    2093     /// \brief Constructor.
    2094     ///
    2095     /// Constructor for descriptor map.
    2096     explicit DescriptorMap(const Graph& _graph) : Map(_graph) {
    2097       Item it;
    2098       const typename Map::Notifier* nf = Map::notifier();
    2099       for (nf->first(it); it != INVALID; nf->next(it)) {
    2100         Map::set(it, _inv_map.size());
    2101         _inv_map.push_back(it);
    2102       }
    2103     }
    2104 
    2105   protected:
    2106 
    2107     /// \brief Add a new key to the map.
    2108     ///
    2109     /// Add a new key to the map. It is called by the
    2110     /// \c AlterationNotifier.
    2111     virtual void add(const Item& item) {
    2112       Map::add(item);
    2113       Map::set(item, _inv_map.size());
    2114       _inv_map.push_back(item);
    2115     }
    2116 
    2117     /// \brief Add more new keys to the map.
    2118     ///
    2119     /// Add more new keys to the map. It is called by the
    2120     /// \c AlterationNotifier.
    2121     virtual void add(const std::vector<Item>& items) {
    2122       Map::add(items);
    2123       for (int i = 0; i < int(items.size()); ++i) {
    2124         Map::set(items[i], _inv_map.size());
    2125         _inv_map.push_back(items[i]);
    2126       }
    2127     }
    2128 
    2129     /// \brief Erase the key from the map.
    2130     ///
    2131     /// Erase the key from the map. It is called by the
    2132     /// \c AlterationNotifier.
    2133     virtual void erase(const Item& item) {
    2134       Map::set(_inv_map.back(), Map::operator[](item));
    2135       _inv_map[Map::operator[](item)] = _inv_map.back();
    2136       _inv_map.pop_back();
    2137       Map::erase(item);
    2138     }
    2139 
    2140     /// \brief Erase more keys from the map.
    2141     ///
    2142     /// Erase more keys from the map. It is called by the
    2143     /// \c AlterationNotifier.
    2144     virtual void erase(const std::vector<Item>& items) {
    2145       for (int i = 0; i < int(items.size()); ++i) {
    2146         Map::set(_inv_map.back(), Map::operator[](items[i]));
    2147         _inv_map[Map::operator[](items[i])] = _inv_map.back();
    2148         _inv_map.pop_back();
    2149       }
    2150       Map::erase(items);
    2151     }
    2152 
    2153     /// \brief Build the unique map.
    2154     ///
    2155     /// Build the unique map. It is called by the
    2156     /// \c AlterationNotifier.
    2157     virtual void build() {
    2158       Map::build();
    2159       Item it;
    2160       const typename Map::Notifier* nf = Map::notifier();
    2161       for (nf->first(it); it != INVALID; nf->next(it)) {
    2162         Map::set(it, _inv_map.size());
    2163         _inv_map.push_back(it);
    2164       }
    2165     }
    2166 
    2167     /// \brief Clear the keys from the map.
    2168     ///
    2169     /// Clear the keys from the map. It is called by the
    2170     /// \c AlterationNotifier.
    2171     virtual void clear() {
    2172       _inv_map.clear();
    2173       Map::clear();
    2174     }
    2175 
    2176   public:
    2177 
    2178     /// \brief Returns the maximal value plus one.
    2179     ///
    2180     /// Returns the maximal value plus one in the map.
    2181     unsigned int size() const {
    2182       return _inv_map.size();
    2183     }
    2184 
    2185     /// \brief Swaps the position of the two items in the map.
    2186     ///
    2187     /// Swaps the position of the two items in the map.
    2188     void swap(const Item& p, const Item& q) {
    2189       int pi = Map::operator[](p);
    2190       int qi = Map::operator[](q);
    2191       Map::set(p, qi);
    2192       _inv_map[qi] = p;
    2193       Map::set(q, pi);
    2194       _inv_map[pi] = q;
    2195     }
    2196 
    2197     /// \brief Gives back the \e descriptor of the item.
    2198     ///
    2199     /// Gives back the mutable and unique \e descriptor of the map.
    2200     int operator[](const Item& item) const {
    2201       return Map::operator[](item);
    2202     }
    2203 
    2204     /// \brief Gives back the item by its descriptor.
    2205     ///
    2206     /// Gives back th item by its descriptor.
    2207     Item operator()(int id) const {
    2208       return _inv_map[id];
    2209     }
    2210 
    2211   private:
    2212 
    2213     typedef std::vector<Item> Container;
    2214     Container _inv_map;
    2215 
    2216   public:
    2217     /// \brief The inverse map type of DescriptorMap.
    2218     ///
    2219     /// The inverse map type of DescriptorMap.
    2220     class InverseMap {
    2221     public:
    2222       /// \brief Constructor of the InverseMap.
    2223       ///
    2224       /// Constructor of the InverseMap.
    2225       explicit InverseMap(const DescriptorMap& inverted)
    2226         : _inverted(inverted) {}
    2227 
    2228 
    2229       /// The value type of the InverseMap.
    2230       typedef typename DescriptorMap::Key Value;
    2231       /// The key type of the InverseMap.
    2232       typedef typename DescriptorMap::Value Key;
    2233 
    2234       /// \brief Subscript operator.
    2235       ///
    2236       /// Subscript operator. It gives back the item
    2237       /// that the descriptor belongs to currently.
    2238       Value operator[](const Key& key) const {
    2239         return _inverted(key);
    2240       }
    2241 
    2242       /// \brief Size of the map.
    2243       ///
    2244       /// Returns the size of the map.
    2245       unsigned int size() const {
    2246         return _inverted.size();
    2247       }
    2248 
    2249     private:
    2250       const DescriptorMap& _inverted;
    2251     };
    2252 
    2253     /// \brief Gives back the inverse of the map.
    2254     ///
    2255     /// Gives back the inverse of the map.
    2256     const InverseMap inverse() const {
    2257       return InverseMap(*this);
    2258     }
    22591858  };
    22601859
Note: See TracChangeset for help on using the changeset viewer.