/* -*- mode: C++; indent-tabs-mode: nil; -*-

 /* -*- mode: C++; indent-tabs-mode: nil; -*-

  *

  *

  * This file is a part of LEMON, a generic C++ optimization library.

  * This file is a part of LEMON, a generic C++ optimization library.

  *

  *

  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

  * (Egervary Research Group on Combinatorial Optimization, EGRES).

  * (Egervary Research Group on Combinatorial Optimization, EGRES).

  *

  *

  * Permission to use, modify and distribute this software is granted

  * Permission to use, modify and distribute this software is granted

  * provided that this copyright notice appears in all copies. For

  * provided that this copyright notice appears in all copies. For

   /// This map is essentially a wrapper for \c std::vector. It assigns

   /// This map is essentially a wrapper for \c std::vector. It assigns

   /// values to integer keys from the range <tt>[0..size-1]</tt>.

   /// values to integer keys from the range <tt>[0..size-1]</tt>.

   /// It can be used together with some data structures, e.g.

   /// It can be used together with some data structures, e.g.

   /// heap types and \c UnionFind, when the used items are small

   /// heap types and \c UnionFind, when the used items are small

   /// integers. This map conforms to the \ref concepts::ReferenceMap

   /// integers. This map conforms to the \ref concepts::ReferenceMap

   ///

   ///

   /// The simplest way of using this map is through the rangeMap()

   /// The simplest way of using this map is through the rangeMap()

   /// function.

   /// function.

   template <typename V>

   template <typename V>

   class RangeMap : public MapBase<int, V> {

   class RangeMap : public MapBase<int, V> {

   /// It wraps a standard graph map (\c NodeMap, \c ArcMap or \c EdgeMap)

   /// It wraps a standard graph map (\c NodeMap, \c ArcMap or \c EdgeMap)

   /// and if a key is set to a new value, then stores it in the inverse map.

   /// and if a key is set to a new value, then stores it in the inverse map.

   /// The graph items can be accessed by their values either using

   /// The graph items can be accessed by their values either using

   /// \c InverseMap or \c operator()(), and the values of the map can be

   /// \c InverseMap or \c operator()(), and the values of the map can be

   /// accessed with an STL compatible forward iterator (\c ValueIt).

   /// accessed with an STL compatible forward iterator (\c ValueIt).

   /// This map is intended to be used when all associated values are

   /// This map is intended to be used when all associated values are

   /// different (the map is actually invertable) or there are only a few

   /// different (the map is actually invertable) or there are only a few

   /// items with the same value.

   /// items with the same value.

   /// suitable and more efficient for such cases. It provides iterators

   /// suitable and more efficient for such cases. It provides iterators

   /// to traverse the items with the same associated value, but

   /// to traverse the items with the same associated value, but

   /// it does not have \c InverseMap.

   /// it does not have \c InverseMap.

   ///

   ///

   /// This type is not reference map, so it cannot be modified with

   /// This type is not reference map, so it cannot be modified with

       bool operator!=(ValueIt jt) const { return it != jt.it; }

       bool operator!=(ValueIt jt) const { return it != jt.it; }

     private:

     private:

       typename Container::const_iterator it;

       typename Container::const_iterator it;

     };

     };

     /// Alias for \c ValueIt

     /// Alias for \c ValueIt

     typedef ValueIt ValueIterator;

     typedef ValueIt ValueIterator;

     /// \brief Returns an iterator to the first value.

     /// \brief Returns an iterator to the first value.

     ///

     ///

     /// only one of them is returned.

     /// only one of them is returned.

     Key operator()(const Value& val) const {

     Key operator()(const Value& val) const {

       typename Container::const_iterator it = _inv_map.find(val);

       typename Container::const_iterator it = _inv_map.find(val);

       return it != _inv_map.end() ? it->second : INVALID;

       return it != _inv_map.end() ? it->second : INVALID;

     }

     }

     /// \brief Returns the number of items with the given value.

     /// \brief Returns the number of items with the given value.

     ///

     ///

     /// This function returns the number of items with the given value

     /// This function returns the number of items with the given value

     /// associated with it.

     /// associated with it.

     int count(const Value &val) const {

     int count(const Value &val) const {

   /// \relates RangeIdMap

   /// \relates RangeIdMap

   template <typename K, typename GR>

   template <typename K, typename GR>

   inline RangeIdMap<GR, K> rangeIdMap(const GR& graph) {

   inline RangeIdMap<GR, K> rangeIdMap(const GR& graph) {

     return RangeIdMap<GR, K>(graph);

     return RangeIdMap<GR, K>(graph);

   }

   }

   /// \brief Dynamic iterable \c bool map.

   /// \brief Dynamic iterable \c bool map.

   ///

   ///

   /// This class provides a special graph map type which can store a

   /// This class provides a special graph map type which can store a

   /// \c bool value for graph items (\c Node, \c Arc or \c Edge).

   /// \c bool value for graph items (\c Node, \c Arc or \c Edge).

   /// For both \c true and \c false values it is possible to iterate on

   /// For both \c true and \c false values it is possible to iterate on

       /// Creates an iterator with a value. It iterates on the

       /// Creates an iterator with a value. It iterates on the

       /// keys mapped to the given value.

       /// keys mapped to the given value.

       /// \param map The IterableBoolMap.

       /// \param map The IterableBoolMap.

       /// \param value The value.

       /// \param value The value.

       ItemIt(const IterableBoolMap& map, bool value)

       ItemIt(const IterableBoolMap& map, bool value)

                  (map._sep > 0 ?

                  (map._sep > 0 ?

                   map._array[map._sep - 1] : INVALID) :

                   map._array[map._sep - 1] : INVALID) :

                  (map._sep < int(map._array.size()) ?

                  (map._sep < int(map._array.size()) ?

                   map._array.back() : INVALID)), _map(&map) {}

                   map._array.back() : INVALID)), _map(&map) {}

   /// It must conform to the \ref concepts::WriteMap "WriteMap" concept.

   /// It must conform to the \ref concepts::WriteMap "WriteMap" concept.

   template <typename GR, typename From, typename To>

   template <typename GR, typename From, typename To>

   void mapCopy(const GR& gr, const From& from, To& to) {

   void mapCopy(const GR& gr, const From& from, To& to) {

     typedef typename To::Key Item;

     typedef typename To::Key Item;

     typedef typename ItemSetTraits<GR, Item>::ItemIt ItemIt;

     typedef typename ItemSetTraits<GR, Item>::ItemIt ItemIt;

     for (ItemIt it(gr); it != INVALID; ++it) {

     for (ItemIt it(gr); it != INVALID; ++it) {

       to.set(it, from[it]);

       to.set(it, from[it]);

     }

     }

   }

   }

   /// \brief Compare two graph maps.

   /// \brief Compare two graph maps.

   ///

   ///

   /// \c true if the maps assign the same value for all items in the graph.

   /// \c true if the maps assign the same value for all items in the graph.

   /// The \c Key type of the maps (\c Node, \c Arc or \c Edge) must be equal

   /// The \c Key type of the maps (\c Node, \c Arc or \c Edge) must be equal

   /// and their \c Value types must be comparable using \c %operator==().

   /// and their \c Value types must be comparable using \c %operator==().

   ///

   ///

   /// \param gr The graph for which the maps are defined.

   /// \param gr The graph for which the maps are defined.

   /// \param map2 The second map.

   /// \param map2 The second map.

   template <typename GR, typename Map1, typename Map2>

   template <typename GR, typename Map1, typename Map2>

   bool mapCompare(const GR& gr, const Map1& map1, const Map2& map2) {

   bool mapCompare(const GR& gr, const Map1& map1, const Map2& map2) {

     typedef typename Map2::Key Item;

     typedef typename Map2::Key Item;

     typedef typename ItemSetTraits<GR, Item>::ItemIt ItemIt;

     typedef typename ItemSetTraits<GR, Item>::ItemIt ItemIt;

     for (ItemIt it(gr); it != INVALID; ++it) {

     for (ItemIt it(gr); it != INVALID; ++it) {

       if (!(map1[it] == map2[it])) return false;

       if (!(map1[it] == map2[it])) return false;

     }

     }

     return true;

     return true;

   }

   }