Changeset 1913:49fe71fce7fb in lemon-0.x

Timestamp:

01/27/06 09:18:47 (17 years ago)

Author:

Balazs Dezso

Branch:

default

Phase:

public

Convert:

svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2488

Message:

Making iterable bool map dynamic
Changed interface

Files:

• demo/graph_orientation.cc (modified) (2 diffs)
• lemon/iterable_maps.h (modified) (3 diffs)

demo/graph_orientation.cc

@@ -71 +71 @@
   def = subMap(f,InDegMap<ListGraph>(g));
   
-  IterableBoolNodeMap<ListGraph> active(g,false);
+  IterableBoolMap<ListGraph, Node> active(g,false);
   for(NodeIt n(g);n!=INVALID;++n) active[n]=(def[n]>0);
   
@@ -80 +80 @@
   
   Node act;
-  while((act=IterableBoolNodeMap<ListGraph>::TrueIt(active))!=INVALID) {
+  while((act=IterableBoolMap<ListGraph, Node>::TrueIt(active))!=INVALID) {
     std::cout << "Process node " << label[act]
               << " (def=" << def[act]

lemon/iterable_maps.h

@@ -29 +29 @@
 
 namespace lemon {
+
+  ///\ingroup maps
+  ///
+  /// \brief Dynamic iterable bool map.
+  ///
+  /// This class provides a special graph map type which can store
+  /// for each graph item(node, edge, etc.) a bool value. For both 
+  /// the true and the false 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 IterableBoolMap 
+    : protected ItemSetTraits<_Graph, _Item>::template Map<int>::Parent {
+  private:
+    typedef _Graph Graph;
+    typedef _Item Item;
+    
+    typedef typename ItemSetTraits<Graph, Item>::ItemIt ItemIt;
+    typedef typename ItemSetTraits<Graph, Item>
+    ::template Map<int>::Parent Parent;
+    
+    std::vector<Item> array;
+    int sep;
+
+    const Graph& graph;
+
+  private:
+
+    int position(const Item& item) const {
+      return Parent::operator[](item);
+    }
+
+  public:
+
+    /// Indicates that the map if reference map.
+    typedef True ReferenceMapTag;
+
+    /// The key type
+    typedef Item Key;
+    /// The value type
+    typedef bool Value;
+    /// The const reference type.    
+    typedef const Value& ConstReference;
+
+
+    /// \brief Refernce to the value of the map.
+    ///
+    /// This class is near to similar to the bool type. It can
+    /// be converted to bool and it has the same operators.
+    class Reference {
+      friend class IterableBoolMap;
+    private:
+      Reference(IterableBoolMap& map, const Key& key) 
+        : _key(key), _map(map) {} 
+    public:
+
+      Reference& operator=(const Reference& value) {
+        _map.set(_key, (bool)value);
+        return *this;
+      }
+
+      operator bool() const { 
+        return static_cast<const IterableBoolMap&>(_map)[_key]; 
+      }
+
+      Reference& operator=(bool value) { 
+        _map.set(_key, value); 
+        return *this; 
+      }
+      Reference& operator&=(bool value) {
+        _map.set(_key, _map[_key] & value); 
+        return *this;   
+      }
+      Reference& operator|=(bool value) {
+        _map.set(_key, _map[_key] | value); 
+        return *this;   
+      }
+      Reference& operator^=(bool value) {
+        _map.set(_key, _map[_key] ^ value); 
+        return *this;   
+      }
+    private:
+      Key _key;
+      IterableBoolMap& _map; 
+    };
+    
+    /// \brief Constructor of the Map with a default value.
+    ///
+    /// Constructor of the Map with a default value.
+    IterableBoolMap(const Graph& _graph, bool def = false) 
+      : Parent(_graph), graph(_graph) {
+      for (ItemIt it(graph); it != INVALID; ++it) {
+        Parent::set(it, array.size());
+        array.push_back(it);
+      }
+      sep = (def ? array.size() : 0);
+    }
+
+    /// \brief Const subscript operator of the map.
+    ///
+    /// Const subscript operator of the map.
+    bool operator[](const Item& item) const {
+      return position(item) < sep;
+    }
+
+    /// \brief Subscript operator of the map.
+    ///
+    /// Subscript operator of the map.
+    Reference operator[](const Item& item) {
+      return Reference(*this, item);
+    }
+
+    /// \brief Set operation of the map.
+    ///
+    /// Set operation of the map.
+    void set(const Item& item, bool value) {
+      int pos = position(item);
+      if (value) {
+        if (pos < sep) return;
+        Item tmp = array[sep];
+        array[sep] = item;
+        Parent::set(item, sep);
+        array[pos] = tmp;
+        Parent::set(tmp, pos); 
+        ++sep;
+      } else {
+        if (pos >= sep) return;
+        --sep;
+        Item tmp = array[sep];
+        array[sep] = item;
+        Parent::set(item, sep);
+        array[pos] = tmp;
+        Parent::set(tmp, pos);
+      }
+    }
+
+    /// \brief Returns the number of the items mapped to true.
+    ///
+    /// Returns the number of the items mapped to true.
+    int trueNum() const {
+      return sep;
+    } 
+    
+    /// \brief Returns the number of the items mapped to false.
+    ///
+    /// Returns the number of the items mapped to false.
+    int falseNum() const {
+      return array.size() - sep;
+    }
+
+    /// \brief Iterator for the keys mapped to true.
+    ///
+    /// Iterator for the keys mapped to true. 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 TrueIt : public Item {
+    public:
+      typedef Item Parent;
+      
+      /// \brief Creates an iterator.
+      ///
+      /// Creates an iterator. It iterates on the 
+      /// keys which mapped to true.
+      /// \param map The IterableIntMap
+      TrueIt(const IterableBoolMap& _map) 
+        : Parent(_map.sep > 0 ? _map.array[_map.sep - 1] : INVALID), 
+          map(&_map) {}
+
+      /// \brief Invalid constructor \& conversion.
+      ///
+      /// This constructor initializes the item to be invalid.
+      /// \sa Invalid for more details.
+      TrueIt(Invalid) : Parent(INVALID), map(0) {}
+
+      /// \brief Increment operator.
+      ///
+      /// Increment Operator.
+      TrueIt& operator++() {
+        int pos = map->position(*this);
+        Parent::operator=(pos > 0 ? map->array[pos - 1] : INVALID);
+        return *this;
+      }
+
+      
+    private:
+      const IterableBoolMap* map;
+    };
+
+    /// \brief Iterator for the keys mapped to false.
+    ///
+    /// Iterator for the keys mapped to false. 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 FalseIt : public Item {
+    public:
+      typedef Item Parent;
+      
+      /// \brief Creates an iterator.
+      ///
+      /// Creates an iterator. It iterates on the 
+      /// keys which mapped to false.
+      /// \param map The IterableIntMap
+      FalseIt(const IterableBoolMap& _map) 
+        : Parent(_map.sep < _map.array.size() ? _map.array.back() : INVALID), 
+          map(&_map) {}
+
+      /// \brief Invalid constructor \& conversion.
+      ///
+      /// This constructor initializes the item to be invalid.
+      /// \sa Invalid for more details.
+      FalseIt(Invalid) : Parent(INVALID), map(0) {}
+
+      /// \brief Increment operator.
+      ///
+      /// Increment Operator.
+      FalseIt& operator++() {
+        int pos = map->position(*this);
+        Parent::operator=(pos > map->sep ? map->array[pos - 1] : INVALID);
+        return *this;
+      }
+
+    private:
+      const IterableBoolMap* map;
+    };
+
+  protected:
+    
+    virtual void add(const Item& item) {
+      Parent::add(item);
+      Parent::set(item, array.size());
+      array.push_back(item);
+    }
+
+    virtual void add(const std::vector<Item>& items) {
+      Parent::add(items);
+      for (int i = 0; i < (int)items.size(); ++i) {
+        Parent::set(items[i], array.size());
+        array.push_back(items[i]);
+      }
+    }
+
+    virtual void erase(const Item& item) {
+      int pos = position(item); 
+      if (pos < sep) {
+        --sep;
+        Parent::set(array[sep], pos);
+        array[pos] = array[sep];
+        Parent::set(array.back(), sep);
+        array[sep] = array.back();
+        array.pop_back();
+      } else {
+        Parent::set(array.back(), pos);
+        array[pos] = array.back();
+        array.pop_back();
+      }
+      Parent::erase(item);
+    }
+
+    virtual void erase(const std::vector<Item>& items) {
+      for (int i = 0; i < (int)items.size(); ++i) {
+        int pos = position(items[i]); 
+        if (pos < sep) {
+          --sep;
+          Parent::set(array[sep], pos);
+          array[pos] = array[sep];
+          Parent::set(array.back(), sep);
+          array[sep] = array.back();
+          array.pop_back();
+        } else {
+          Parent::set(array.back(), pos);
+          array[pos] = array.back();
+          array.pop_back();
+        }
+      }
+      Parent::erase(items);
+    }    
+
+    virtual void build() {
+      Parent::build();
+      for (ItemIt it(graph); it != INVALID; ++it) {
+        Parent::set(it, array.size());
+        array.push_back(it);
+      }
+      sep = 0;      
+    }
+
+    virtual void clear() {
+      array.clear();
+      sep = 0;
+      Parent::clear();
+    }
+    
+  };
   
-  ///\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 UpperNodeMap
-
-  /// This map can be used in the same way
-  /// as the standard UpperNodeMap<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 IterableBoolUpperNodeMap
-  {
-    typename Graph::template UpperNodeMap<int> cmap;
-  
-  public:
-  
-    typedef IterableBoolMap<typename Graph::template UpperNodeMap<int> > BimType;
-    BimType imap;
-
-
-    typedef typename BimType::RefType RefType;
-    typedef typename Graph::Node Key;
-    typedef bool Value;
-  
-    friend class FalseIt;
-    friend class TrueIt;
-  
-    ///\e
-    IterableBoolUpperNodeMap(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 IterableBoolUpperNodeMap &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 IterableBoolUpperNodeMap &m)
-        : BimType::TrueIt(m.imap) { }
-      ///\e
-      TrueIt(Invalid i) : BimType::TrueIt(i) { }
-    };  
-  };
-
-  /// Iterable bool LowerNodeMap
-
-  /// This map can be used in the same way
-  /// as the standard LowerNodeMap<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 IterableBoolLowerNodeMap
-  {
-    typename Graph::template LowerNodeMap<int> cmap;
-  
-  public:
-  
-    typedef IterableBoolMap<typename Graph::template LowerNodeMap<int> > BimType;
-    BimType imap;
-
-
-    typedef typename BimType::RefType RefType;
-    typedef typename Graph::Node Key;
-    typedef bool Value;
-  
-    friend class FalseIt;
-    friend class TrueIt;
-  
-    ///\e
-    IterableBoolLowerNodeMap(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 IterableBoolLowerNodeMap &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 IterableBoolLowerNodeMap &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() : value(-1) {}
       IterableIntMapNode(int _value) : value(_value) {}
       Item prev, next;
@@ -483 +370 @@
     /// Constructor of the Map. It set all values -1.
     explicit IterableIntMap(const Graph& graph) 
-      : Parent(graph, _iterable_maps_bits::IterableIntMapNode<_Item>(-1)) {}
+      : Parent(graph) {}
 
     /// \brief Constructor of the Map with a given value.
@@ -707 +594 @@
     }
 
+    virtual void erase(const std::vector<Key>& keys) {
+      for (int i = 0; i < keys.size(); ++i) {
+        unlace(keys[i]);
+      }
+      Parent::erase(keys);
+    }
+
     virtual void clear() {
       first.clear();