RhodeCode

#ifndef LEMON_MAPS_H

#define LEMON_MAPS_H

#include <iterator>

#include <functional>

#include <vector>

#include <lemon/core.h>

///\file

///\ingroup maps

///\brief Miscellaneous property maps

namespace lemon {

  /// \addtogroup maps

  /// @{

  /// Base class of maps.

  /// \brief General cross reference graph map type.

  /// This class provides simple invertable graph maps.

  /// It wraps an arbitrary \ref concepts::ReadWriteMap "ReadWriteMap"

  /// and if a key is set to a new value then store it

  /// in the inverse map.

  /// The values of the map can be accessed

  /// with stl compatible forward iterator.

  ///

  /// \tparam GR The graph type.

  /// \tparam K The key type of the map (\c GR::Node, \c GR::Arc or

  /// \c GR::Edge).

  /// \tparam V The value type of the map.

  ///

  /// \see IterableValueMap

    /// Gives back the inverse of the map.

    const InverseMap inverse() const {

      return InverseMap(*this);

    }

  };

  ///

  ///

  class IterableBoolMap

  private:

    typedef GR Graph;

    int _sep;

  public:

    typedef True ReferenceMapTag;

    /// The key type

    /// The value type

    typedef bool Value;

    /// The const reference type.

    typedef const Value& ConstReference;

  private:

    int position(const Key& key) const {

      return Parent::operator[](key);

    }

  public:

    ///

    class Reference {

      friend class IterableBoolMap;

    private:

      Reference(IterableBoolMap& map, const Key& key)

        : _key(key), _map(map) {}

    public:

    /// Set all items in the map.

    /// \note Constant time operation.

    void setAll(bool value) {

      _sep = (value ? _array.size() : 0);

    }

    ///

    int trueNum() const {

      return _sep;

    }

    ///

    int falseNum() const {

      return _array.size() - _sep;

    }

    ///

    /// the key type of the map, incremented with \c ++ operator, and

    /// \c INVALID.

    class TrueIt : public Key {

    public:

      typedef Key Parent;

      /// \brief Creates an iterator.

      ///

      /// Creates an iterator. It iterates on the

      explicit TrueIt(const IterableBoolMap& map)

        : Parent(map._sep > 0 ? map._array[map._sep - 1] : INVALID),

          _map(&map) {}

      /// \brief Invalid constructor \& conversion.

      ///

      /// \sa Invalid for more details.

      TrueIt(Invalid) : Parent(INVALID), _map(0) {}

      /// \brief Increment operator.

      ///

      TrueIt& operator++() {

        int pos = _map->position(*this);

        Parent::operator=(pos > 0 ? _map->_array[pos - 1] : INVALID);

        return *this;

      }

    private:

      const IterableBoolMap* _map;

    };

    ///

    /// the key type of the map, incremented with \c ++ operator, and

    /// \c INVALID.

    class FalseIt : public Key {

    public:

      typedef Key Parent;

      /// \brief Creates an iterator.

      ///

      /// Creates an iterator. It iterates on the

      explicit FalseIt(const IterableBoolMap& map)

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

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

      /// \brief Invalid constructor \& conversion.

      ///

      /// \sa Invalid for more details.

      FalseIt(Invalid) : Parent(INVALID), _map(0) {}

      /// \brief Increment operator.

      ///

      FalseIt& operator++() {

        int pos = _map->position(*this);

        Parent::operator=(pos > _map->_sep ? _map->_array[pos - 1] : INVALID);

        return *this;

      }

      const IterableBoolMap* _map;

    };

    /// \brief Iterator for the keys mapped to a given value.

    ///

    /// Iterator for the keys mapped to a given value. It works

    /// the key type of the map, incremented with \c ++ operator, and

    /// \c INVALID.

    class ItemIt : public Key {

    public:

      typedef Key Parent;

      ///

      ItemIt(const IterableBoolMap& map, bool value)

        : Parent(value ? 

                 (map._sep > 0 ?

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

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

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

      /// \brief Invalid constructor \& conversion.

      ///

      /// \sa Invalid for more details.

      ItemIt(Invalid) : Parent(INVALID), _map(0) {}

      /// \brief Increment operator.

      ///

      ItemIt& operator++() {

        int pos = _map->position(*this);

        int _sep = pos >= _map->_sep ? _map->_sep : 0;

        Parent::operator=(pos > _sep ? _map->_array[pos - 1] : INVALID);

        return *this;

      }

      IterableIntMapNode(int _value) : value(_value) {}

      Item prev, next;

      int value;

    };

  }

  /// \brief Dynamic iterable integer map.

  ///

  ///

  /// value in the map.

  ///

  class IterableIntMap

  public:

    /// The key type

    /// The value type

    typedef int Value;

    /// The graph type

    typedef GR Graph;

    /// \brief Constructor of the map.

    ///

    explicit IterableIntMap(const Graph& graph)

      : Parent(graph) {}

    /// \brief Constructor of the map with a given value.

    ///

    /// Constructor of the map with a given value.

    explicit IterableIntMap(const Graph& graph, int value)

      if (value >= 0) {

        for (typename Parent::ItemIt it(*this); it != INVALID; ++it) {

          lace(it);

        }

      }

    }

      }

      _first[node.value] = key;

    }

  public:

    typedef True ReferenceMapTag;

    ///

    class Reference {

      friend class IterableIntMap;

    private:

      Reference(IterableIntMap& map, const Key& key)

        : _key(key), _map(map) {}

    public:

      return Reference(*this, key);

    }

    /// \brief Iterator for the keys with the same value.

    ///

    /// Iterator for the keys with the same value. It works

    /// the item type of the map, incremented with \c ++ operator, and

    /// \c INVALID.

    public:

      /// \brief Invalid constructor \& conversion.

      ///

      /// \sa Invalid for more details.

      ItemIt(Invalid) : Parent(INVALID), _map(0) {}

      /// \brief Creates an iterator with a value.

      ///

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

      ItemIt(const IterableIntMap& map, int value) : _map(&map) {

        if (value < 0 || value >= int(_map->_first.size())) {

          Parent::operator=(INVALID);

        } else {

          Parent::operator=(_map->_first[value]);

        }

      }

      /// \brief Increment operator.

      ///

      ItemIt& operator++() {

        Parent::operator=(_map->IterableIntMap::Parent::

                          operator[](static_cast<Parent&>(*this)).next);

        return *this;

      }

    private:

      const IterableIntMap* _map;

    };

  protected:

    virtual void clear() {

      _first.clear();

      Parent::clear();

    }

  private:

  };

  namespace _maps_bits {

    template <typename Item, typename Value>

    struct IterableValueMapNode {

      IterableValueMapNode(Value _value = Value()) : value(_value) {}

      Item prev, next;

      Value value;

    };

  }

  /// \brief Dynamic iterable map for comparable values.

  ///

  /// the items which mapped to the value, and the values are stored

  /// in balanced binary tree. The values of the map can be accessed

  /// with stl compatible forward iterator.

  ///

  /// the subscription operator.

  ///

  ///

  class IterableValueMap

  public:

    /// The key type

    /// The value type

    /// The graph type

    typedef GR Graph;

  public:

    ///

    explicit IterableValueMap(const Graph& graph,

                              const Value& value = Value())

      for (typename Parent::ItemIt it(*this); it != INVALID; ++it) {

        lace(it);

      }

    }

  protected:

    void lace(const Key& key) {

      typename Parent::Value& node = Parent::operator[](key);

      typename std::map<Value, Key>::iterator it = _first.find(node.value);

      if (it == _first.end()) {

        node.prev = node.next = INVALID;

        _first.insert(std::make_pair(node.value, key));

      } else {

        node.prev = INVALID;

        node.next = it->second;

        if (node.next != INVALID) {

          Parent::operator[](node.next).prev = key;

  public:

    /// \brief Forward iterator for values.

    ///

    /// This iterator is an stl compatible forward

    /// iterator on the values of the map. The values can

    class ValueIterator

      : public std::iterator<std::forward_iterator_tag, Value> {

      friend class IterableValueMap;

    private:

      ValueIterator(typename std::map<Value, Key>::const_iterator _it)

        : it(_it) {}

    };

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

    ///

    /// Returns an stl compatible iterator to the

    /// first value of the map. The values of the

    /// range.

    ValueIterator beginValue() const {

      return ValueIterator(_first.begin());

    }

    /// \brief Returns an iterator after the last value.

    ///

    /// Returns an stl compatible iterator after the

    /// last value of the map. The values of the

    /// range.

    ValueIterator endValue() const {

      return ValueIterator(_first.end());

    }

    /// \brief Set operation of the map.

      return Parent::operator[](key).value;

    }

    /// \brief Iterator for the keys with the same value.

    ///

    /// Iterator for the keys with the same value. It works

    /// the item type of the map, incremented with \c ++ operator, and

    /// \c INVALID.

    public:

      /// \brief Invalid constructor \& conversion.

      ///

      /// \sa Invalid for more details.

      ItemIt(Invalid) : Parent(INVALID), _map(0) {}

      /// \brief Creates an iterator with a value.

      ///

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

#include <deque>

#include <set>

#include <lemon/concept_check.h>

#include <lemon/concepts/maps.h>

#include <lemon/maps.h>

#include "test_tools.h"

using namespace lemon;

using namespace lemon::concepts;

  // Iterable bool map

  {

    typedef SmartGraph Graph;

    typedef SmartGraph::Node Item;

    typedef IterableBoolMap<SmartGraph, SmartGraph::Node> Ibm;

    const int num = 10;

    Graph g;

    std::vector<Item> items;

    for (int i = 0; i < num; ++i) {

      items.push_back(g.addNode());

  // Iterable int map

  {

    typedef SmartGraph Graph;

    typedef SmartGraph::Node Item;

    typedef IterableIntMap<SmartGraph, SmartGraph::Node> Iim;

    const int num = 10;

    Graph g;

    std::vector<Item> items;

    for (int i = 0; i < num; ++i) {

      items.push_back(g.addNode());

      map1[items[i]] = i % 2;

    }

    check(map1.size() == 2, "Wrong size");

    int n = 0;

    for (Iim::ItemIt it(map1, 0); it != INVALID; ++it) {

      ++n;

    }

    check(n == (num + 1) / 2, "Wrong number");

    for (Iim::ItemIt it(map1, 1); it != INVALID; ++it) {

      ++n;

    }

    check(n == num, "Wrong number");

  }

      map1.set(items[i], static_cast<double>(i % 2));

    }

    check(distance(map1.beginValue(), map1.endValue()) == 2, "Wrong size");

    int n = 0;

    for (Ivm::ItemIt it(map1, 0.0); it != INVALID; ++it) {

      ++n;

    }

    check(n == (num + 1) / 2, "Wrong number");

    for (Ivm::ItemIt it(map1, 1.0); it != INVALID; ++it) {

      ++n;

    }

    check(n == num, "Wrong number");

  }

  return 0;