source: lemon-0.x/lemon/iterable_maps.h @ 1824:3a15b39a7c78

/* -*- C++ -*-
 * lemon/iterable_maps.h - Part of LEMON, a generic C++ optimization library
 *
 * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
 *
 * Permission to use, modify and distribute this software is granted
 * provided that this copyright notice appears in all copies. For
 * precise terms see the accompanying LICENSE file.
 *
 * This software is provided "AS IS" with no warranty of any kind,
 * express or implied, and with no claim as to its suitability for any
 * purpose.
 *
 */

#include <lemon/traits.h>
#include <lemon/invalid.h>
#include <vector>
#include <limits>

///\ingroup maps
///\file
///\brief Maps that makes it possible to iterate through the keys having
///a certain value
///
///


namespace lemon {
  
  ///\todo This is only a static map!
  ///\todo Undocumented.
  ///\param BaseMap is an interger map.
  template<class BaseMap>
  class IterableBoolMap
  {
  public:
  
    typedef typename BaseMap::Key Key;
    typedef bool Value;
  
    friend class RefType;
    friend class FalseIt;
    friend class TrueIt;

  private:
    BaseMap &cref;
    std::vector<Key> vals;
    int sep;           //map[e] is true <=> cref[e]>=sep
  
    bool isTrue(Key k) {return cref[k]>=sep;}
    void swap(Key k, int s) 
    {
      int ti=cref[k];
      Key tk=vals[s];
      cref[k]=s; vals[s]=k;
      cref[tk]=ti; vals[ti]=tk;
    }  

    void setTrue(Key k) { if(cref[k]<sep) { sep--; swap(k,sep); } }
    void setFalse(Key k) { if(cref[k]>=sep) { swap(k,sep); sep++; } }
  
  public:
    ///\e
    void set(Key k,Value v) { if(v) setTrue(k); else setFalse(k);}
    ///Number of \c true items in the map

    ///Returns the number of \c true values in the map.
    ///This is a constant time operation.
    int countTrue() { return vals.size()-sep; }
    ///Number of \c false items in the map

    ///Returns the number of \c false values in the map.
    ///This is a constant time operation.
    int countFalse() { return sep; }

    ///\e
    class FalseIt
    {
      const IterableBoolMap &M;
      int i;
    public:
      ///\e
      explicit FalseIt(const IterableBoolMap &_M) : M(_M), i(0) { }
      ///\e
      FalseIt(Invalid)
        : M(*((IterableBoolMap*)(0))), i(std::numeric_limits<int>::max()) { }
      ///\e
      FalseIt &operator++() { ++i; return *this;}
      ///\e
      operator Key() const { return i<M.sep ? M.vals[i] : INVALID; }
      ///\e
      bool operator !=(Invalid) const { return i<M.sep; }
      ///\e
      bool operator ==(Invalid) const { return i>=M.sep; }
    };
    ///\e
    class TrueIt
    {
      const IterableBoolMap &M;
      int i;
    public:
      ///\e
      explicit TrueIt(const IterableBoolMap &_M)
        : M(_M), i(M.vals.size()-1) { }
      ///\e
      TrueIt(Invalid)
        : M(*((IterableBoolMap*)(0))), i(-1) { }
      ///\e
      TrueIt &operator++() { --i; return *this;}
      ///\e
      operator Key() const { return i>=M.sep ? M.vals[i] : INVALID; }
      ///\e
      bool operator !=(Invalid) const { return i>=M.sep; }
      ///\e
      bool operator ==(Invalid) const { return i<M.sep; }
    };
  
    ///\e
    class RefType
    {
      IterableBoolMap &M;
      Key k;
    public:
      RefType(IterableBoolMap &_M,Key _k) : M(_M), k(_k) { }
    
      operator Value() const 
      {
        return M.isTrue(k);
      }
      Value operator = (Value v) const { M.set(k,v); return v; }
    };
  
  public:
    explicit IterableBoolMap(BaseMap &_m,bool init=false) : cref(_m)
    {
      sep=0;
      for(typename BaseMap::MapIt i(cref);i!=INVALID; ++i) {
        i.set(sep);
        vals.push_back(i);
        sep++;
      }
      if(init) sep=0;
    }
    ///\e
    RefType operator[] (Key k) { return RefType(*this,k);}  
    ///\e
    Value operator[] (Key k) const { return isTrue(k);}  
  };




  /// \addtogroup graph_maps
  /// @{

  /// Iterable bool NodeMap

  /// This map can be used in the same way
  /// as the standard NodeMap<bool> of the
  /// given graph \c Graph. 
  /// In addition, this class provides two iterators called \ref TrueIt
  /// and \ref FalseIt to iterate through the "true" and "false" nodes.
  template <class Graph>
  class IterableBoolNodeMap
  {
    typename Graph::template NodeMap<int> cmap;
  
  public:
  
    typedef IterableBoolMap<typename Graph::template NodeMap<int> > BimType;
    BimType imap;


    typedef typename BimType::RefType RefType;
    typedef typename Graph::Node Key;
    typedef bool Value;
  
    friend class FalseIt;
    friend class TrueIt;
  
    ///\e
    IterableBoolNodeMap(const Graph &g,bool b=false) : cmap(g), imap(cmap,b) {}

  public:
    ///\e
    void set(Key k, bool v) { imap.set(k,v);}
    ///Number of \c true items in the map

    ///Returns the number of \c true values in the map.
    ///This is a constant time operation.
    int countTrue() { return imap.countTrue(); }
    ///Number of \c false items in the map

    ///Returns the number of \c false values in the map.
    ///This is a constant time operation.
    int countFalse() { return imap.countFalse(); }
#ifdef DOXYGEN
    ///\e
    bool &operator[](Key k) { return imap[k];}  
    ///\e
    const bool &operator[](Key k) const { return imap[k];}  
#else
    Value operator[](Key k) const { return imap[k];}  
    RefType operator[](Key k) { return imap[k];}  
#endif
    ///Iterator for the "false" nodes
    class FalseIt : public BimType::FalseIt
    {
    public:
      ///\e
      explicit FalseIt(const IterableBoolNodeMap &m)
        : BimType::FalseIt(m.imap) { }
      ///\e
      FalseIt(Invalid i) : BimType::FalseIt(i) { }
    };
    ///Iterator for the "true" nodes
    class TrueIt : public BimType::TrueIt
    {
    public:
      ///\e
      explicit TrueIt(const IterableBoolNodeMap &m)
        : BimType::TrueIt(m.imap) { }
      ///\e
      TrueIt(Invalid i) : BimType::TrueIt(i) { }
    };  
  };

  /// Iterable bool EdgeMap

  /// This map can be used in the same way
  /// as the standard EdgeMap<bool> of the
  /// given graph \c Graph. 
  /// In addition, this class provides two iterators called \ref TrueIt
  /// and \ref FalseIt to iterate through the "true" and "false" edges.
  template <class Graph>
  class IterableBoolEdgeMap
  {
    typename Graph::template EdgeMap<int> cmap;
  
  public:
  
    typedef IterableBoolMap<typename Graph::template EdgeMap<int> > BimType;
    BimType imap;


    typedef typename BimType::RefType RefType;
    typedef typename Graph::Edge Key;
    typedef bool Value;
  
    friend class FalseIt;
    friend class TrueIt;
  
    ///\e
    IterableBoolEdgeMap(const Graph &g,bool b=false) : cmap(g), imap(cmap,b) {}

  public:
    ///\e
    void set(Key k, bool v) { imap.set(k,v);}
    ///Returns the number of \c true values in the map.
    ///This is a constant time operation.
    int countTrue() { return imap.countTrue(); }
    ///Number of \c false items in the map

    ///Returns the number of \c false values in the map.
    ///This is a constant time operation.
    int countFalse() { return imap.countFalse(); }
#ifdef DOXYGEN
    ///\e
    bool &operator[](Key k) { return imap[k];}  
    ///\e
    const bool &operator[](Key k) const { return imap[k];}  
#else
    Value operator[](Key k) const { return imap[k];}  
    RefType operator[](Key k) { return imap[k];}  
#endif
    ///Iterator for the "false" edges
    class FalseIt : public BimType::FalseIt
    {
    public:
      ///\e
      explicit FalseIt(const IterableBoolEdgeMap &m)
        : BimType::FalseIt(m.imap) { }
      ///\e
      FalseIt(Invalid i) : BimType::FalseIt(i) { }
    };
    ///Iterator for the "true" edges
    class TrueIt : public BimType::TrueIt
    {
    public:
      ///\e
      explicit TrueIt(const IterableBoolEdgeMap &m)
        : BimType::TrueIt(m.imap) { }
      ///\e
      TrueIt(Invalid i) : BimType::TrueIt(i) { }
    };  
  };


  namespace _iterable_maps_bits {
    template <typename Item>
    struct IterableIntMapNode {
      IterableIntMapNode() {}
      IterableIntMapNode(int _value) : value(_value) {}
      Item prev, next;
      int value;
    };
  }

  ///\ingroup maps
  ///
  /// \brief Dynamic iterable integer map.
  ///
  /// This class provides a special graph map type which can store
  /// for each graph item(node, edge, etc.) an integer value. For each
  /// non negative value it is possible to iterate on the keys which
  /// mapped to the given value.
  /// 
  /// \param _Graph The graph type.
  /// \param _Item One of the graph's item type, the key of the map.
  template <typename _Graph, typename _Item>
  class IterableIntMap : protected ItemSetTraits<_Graph, _Item> 
  ::template Map<_iterable_maps_bits::IterableIntMapNode<_Item> >::Parent {
  public:
    typedef typename ItemSetTraits<_Graph, _Item> 
    ::template Map<_iterable_maps_bits::IterableIntMapNode<_Item> >
    ::Parent Parent;

    /// The key type
    typedef _Item Key;
    /// The value type
    typedef int Value;
    /// The graph type
    typedef _Graph Graph;

    /// \brief Constructor of the Map.
    ///
    /// Constructor of the Map. It set all values -1.
    explicit IterableIntMap(const Graph& graph) 
      : Parent(graph, _iterable_maps_bits::IterableIntMapNode<_Item>(-1)) {}

    /// \brief Constructor of the Map with a given value.
    ///
    /// Constructor of the Map with a given value.
    explicit IterableIntMap(const Graph& graph, int value) 
      : Parent(graph, _iterable_maps_bits::IterableIntMapNode<_Item>(value)) {
      if (value >= 0) {
        for (typename Parent::ItemIt it(*this); it != INVALID; ++it) {
          lace(it);
        }
      }
    }

  private:
    
    void unlace(const Key& key) {
      typename Parent::Value& node = Parent::operator[](key);
      if (node.value < 0) return;
      if (node.prev != INVALID) {
        Parent::operator[](node.prev).next = node.next; 
      } else {
        first[node.value] = node.next;
      }
      if (node.next != INVALID) {
        Parent::operator[](node.next).prev = node.prev;
      }
      while (!first.empty() && first.back() == INVALID) {
        first.pop_back();
      }
    }

    void lace(const Key& key) {
      typename Parent::Value& node = Parent::operator[](key);
      if (node.value < 0) return;
      if (node.value >= (int)first.size()) {
        first.resize(node.value + 1, INVALID);
      } 
      node.prev = INVALID;
      node.next = first[node.value];
      if (node.next != INVALID) {
        Parent::operator[](node.next).prev = key;       
      }
      first[node.value] = key;
    }

  public:

    /// Indicates that the map if reference map.
    typedef True ReferenceMapTag;

    /// \brief Refernce to the value of the map.
    ///
    /// This class is near to similar to the int type. It can
    /// be converted to int and it has the same operators.
    class Reference {
      friend class IterableIntMap;
    private:
      Reference(IterableIntMap& map, const Key& key) 
        : _key(key), _map(map) {} 
    public:

      Reference& operator=(const Reference& value) {
        _map.set(_key, (const int&)value);
        return *this;
      }

      operator const int&() const { 
        return static_cast<const IterableIntMap&>(_map)[_key]; 
      }

      Reference& operator=(int value) { 
        _map.set(_key, value); 
        return *this; 
      }
      Reference& operator++() {
        _map.set(_key, _map[_key] + 1); 
        return *this;   
      }
      int operator++(int) {
        int value = _map[_key];
        _map.set(_key, value + 1); 
        return value;   
      }
      Reference& operator--() {
        _map.set(_key, _map[_key] - 1); 
        return *this;   
      }
      int operator--(int) {
        int value = _map[_key];
        _map.set(_key, value - 1); 
        return value;   
      }
      Reference& operator+=(int value) { 
        _map.set(_key, _map[_key] + value); 
        return *this;
      }
      Reference& operator-=(int value) { 
        _map.set(_key, _map[_key] - value); 
        return *this;
      }
      Reference& operator*=(int value) { 
        _map.set(_key, _map[_key] * value); 
        return *this;
      }
      Reference& operator/=(int value) { 
        _map.set(_key, _map[_key] / value); 
        return *this;
      }
      Reference& operator%=(int value) { 
        _map.set(_key, _map[_key] % value); 
        return *this;
      }
      Reference& operator&=(int value) { 
        _map.set(_key, _map[_key] & value); 
        return *this;
      }
      Reference& operator|=(int value) { 
        _map.set(_key, _map[_key] | value); 
        return *this;
      }
      Reference& operator^=(int value) { 
        _map.set(_key, _map[_key] ^ value); 
        return *this;
      }
      Reference& operator<<=(int value) { 
        _map.set(_key, _map[_key] << value); 
        return *this;
      }
      Reference& operator>>=(int value) { 
        _map.set(_key, _map[_key] >> value); 
        return *this;
      }

    private:
      Key _key;
      IterableIntMap& _map; 
    };

    /// The const reference type.    
    typedef const Value& ConstReference;

    /// \brief Gives back the maximal value plus one.
    ///
    /// Gives back the maximal value plus one.
    int size() const {
      return (int)first.size();
    }
    
    /// \brief Set operation of the map.
    ///
    /// Set operation of the map.
    void set(const Key& key, const Value& value) {
      unlace(key);
      Parent::operator[](key).value = value;
      lace(key);
    }

    /// \brief Const subscript operator of the map.
    ///
    /// Const subscript operator of the map.
    const Value& operator[](const Key& key) const {
      return Parent::operator[](key).value;
    }

    /// \brief Subscript operator of the map.
    ///
    /// Subscript operator of the map.
    Reference operator[](const Key& key) {
      return Reference(*this, key);
    }

    /// \brief Iterator for the keys with the same value.
    ///
    /// Iterator for the keys with the same value. It works
    /// like a graph item iterator in the map, it can be converted
    /// the item type of the map, incremented with \c ++ operator, and
    /// if the iterator leave the last valid item it will be equal to 
    /// \c INVALID.
    class ItemIt : public _Item {
    public:
      typedef _Item Parent;

      /// \brief Invalid constructor \& conversion.
      ///
      /// This constructor initializes the item to be invalid.
      /// \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 
      /// keys which have the given value.
      /// \param map The IterableIntMap
      /// \param value The value
      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.
      ///
      /// Increment Operator.
      ItemIt& operator++() {
        Parent::operator=(_map->IterableIntMap::Parent::
                          operator[](static_cast<Parent&>(*this)).next);
        return *this;
      }


    private:
      const IterableIntMap* _map;
    };

  protected:
    
    virtual void erase(const Key& key) {
      unlace(key);
      Parent::erase(key);
    }

    virtual void clear() {
      first.clear();
      Parent::clear();
    }

  private:
    std::vector<_Item> first;
  };

  /// @}
}