# HG changeset patch
# User alpar
# Date 1126503115 0
# Node ID a9f923a4d998dcc8cb91e87abb9f34976df70160
# Parent  c3e4165147591bacf3d2b09e64a5257aeb825435
iterable_maps.h header hes been added. Up to now it contains an iterable bool
map and specialized versions for Node and Edge maps.

diff -r c3e416514759 -r a9f923a4d998 lemon/Makefile.am
--- a/lemon/Makefile.am	Thu Sep 08 14:35:22 2005 +0000
+++ b/lemon/Makefile.am	Mon Sep 12 05:31:55 2005 +0000
@@ -35,6 +35,7 @@
 	graph_utils.h \
 	graph_to_eps.h \
 	invalid.h \
+	iterable_maps.h \
 	kruskal.h \
 	list_graph.h \
 	lp.h \
diff -r c3e416514759 -r a9f923a4d998 lemon/iterable_maps.h
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/lemon/iterable_maps.h	Mon Sep 12 05:31:55 2005 +0000
@@ -0,0 +1,250 @@
+/* -*- 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 <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!
+  ///\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);}
+
+    ///\e
+    class FalseIt
+    {
+      const IterableBoolMap &M;
+      int i;
+    public:
+      explicit FalseIt(const IterableBoolMap &_M) : M(_M), i(0) { }
+      FalseIt(Invalid)
+	: M(*((IterableBoolMap*)(0))), i(std::numeric_limits<int>::max()) { }
+      FalseIt &operator++() { ++i; return *this;}
+      operator Key() const { return i<M.sep ? M.vals[i] : INVALID; }
+      bool operator !=(Invalid) const { return i<M.sep; }
+      bool operator ==(Invalid) const { return i>=M.sep; }
+    };
+    ///\e
+    class TrueIt
+    {
+      const IterableBoolMap &M;
+      int i;
+    public:
+      explicit TrueIt(const IterableBoolMap &_M)
+	: M(_M), i(M.vals.size()-1) { }
+      TrueIt(Invalid)
+	: M(*((IterableBoolMap*)(0))), i(-1) { }
+      TrueIt &operator++() { --i; return *this;}
+      operator Key() const { return i>=M.sep ? M.vals[i] : INVALID; }
+      bool operator !=(Invalid) const { return i>=M.sep; }
+      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::MapSet::iterator i=cref.mapSet().begin();
+	  i!=cref.mapSet().end();
+	  ++i) {
+	i->second=sep;
+	vals.push_back(i->first);
+	sep++;
+      }
+      if(init) sep=0;
+    }
+    RefType operator[] (Key k) { return RefType(*this,k);}  
+    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::NodeMap<int> cmap;
+  
+  public:
+  
+    typedef IterableBoolMap<typename Graph::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);}
+#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:
+      explicit FalseIt(const IterableBoolNodeMap &m)
+	: BimType::FalseIt(m.imap) { }
+      FalseIt(Invalid i) : BimType::FalseIt(i) { }
+    };
+    ///Iterator for the "true" nodes
+    class TrueIt : public BimType::TrueIt
+    {
+    public:
+      explicit TrueIt(const IterableBoolNodeMap &m)
+	: BimType::TrueIt(m.imap) { }
+      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::EdgeMap<int> cmap;
+  
+  public:
+  
+    typedef IterableBoolMap<typename Graph::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);}
+#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:
+      explicit FalseIt(const IterableBoolEdgeMap &m)
+	: BimType::FalseIt(m.imap) { }
+      FalseIt(Invalid i) : BimType::FalseIt(i) { }
+    };
+    ///Iterator for the "true" edges
+    class TrueIt : public BimType::TrueIt
+    {
+    public:
+      explicit TrueIt(const IterableBoolEdgeMap &m)
+	: BimType::TrueIt(m.imap) { }
+      TrueIt(Invalid i) : BimType::TrueIt(i) { }
+    };  
+  };
+
+  /// @}
+}