COIN-OR::LEMON - Graph Library

Changeset 1280:f2255b96c19c in lemon-0.x


Ignore:
Timestamp:
03/31/05 11:33:52 (15 years ago)
Author:
Alpar Juttner
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1712
Message:

It works again

File:
1 edited

Legend:

Unmodified
Added
Removed
  • src/work/alpar/boolmap_iter.cc

    r987 r1280  
    11#include <iostream>
    22#include <vector>
    3 #include <smart_graph.h>
     3#include <lemon/smart_graph.h>
     4#include <limits>
    45
    56using namespace lemon;
    67
    78///\todo This is only a static map!
    8 ///
    9 template<class GG>
    10 class BoolIterEdgeMap
     9///\param BaseMap is an interger map.
     10template<class BaseMap>
     11class BoolIterMap
    1112{
    1213public:
    13   typedef GG Graph;
    14   typedef typename GG::Edge Edge;
    1514 
    16   typedef Edge Key;
     15  typedef typename BaseMap::Key Key;
    1716  typedef bool Value;
    1817 
    1918  friend class RefType;
    20   friend class FalseIterator;
    21   friend class TrueIterator;
     19  friend class FalseIt;
     20  friend class TrueIt;
    2221
    2322private:
    24   Graph &G;
    25   typename Graph::EdgeMap<int> cref;
    26   std::vector<Edge> vals;
     23  BaseMap &cref;
     24  std::vector<Key> vals;
    2725  int sep;           //map[e] is true <=> cref[e]>=sep
    2826 
    29   bool isTrue(Edge e) {return cref[e]>=sep;}
    30   void swap(Edge e, int s)
     27  bool isTrue(Key k) {return cref[k]>=sep;}
     28  void swap(Key k, int s)
    3129  {
    32     int ti=cref[e];
    33     Edge te=vals[s];
    34     cref[e]=s; vals[s]=e;
    35     cref[te]=ti; vals[ti]=te;
     30    int ti=cref[k];
     31    Key tk=vals[s];
     32    cref[k]=s; vals[s]=k;
     33    cref[tk]=ti; vals[ti]=tk;
    3634  } 
    3735
    38   void setTrue(Edge e) { if(cref[e]<sep) { sep--; swap(e,sep); } }
    39   void setFalse(Edge e) { if(cref[e]>=sep) { swap(e,sep); sep++; } }
     36  void setTrue(Key k) { if(cref[k]<sep) { sep--; swap(k,sep); } }
     37  void setFalse(Key k) { if(cref[k]>=sep) { swap(k,sep); sep++; } }
    4038 
    4139public:
    42   class FalseIterator
     40  ///\e
     41  void set(Key k,Value v) { if(v) setTrue(k); else setFalse(k);}
     42
     43  ///\e
     44  class FalseIt
    4345  {
    44     BoolIterEdgeMap &M;
     46    const BoolIterMap &M;
    4547    int i;
    4648  public:
    47     FalseIterator(BoolIterEdgeMap &_M) : M(_M), i(0) { }
    48     FalseIterator &operator++() { ++i; return *this;}
    49     operator Edge() { return i<M.sep ? M.vals[i] : INVALID; }
    50     operator bool() { return i<M.sep; }
     49    explicit FalseIt(const BoolIterMap &_M) : M(_M), i(0) { }
     50    FalseIt(Invalid)
     51      : M(*((BoolIterMap*)(0))), i(std::numeric_limits<int>::max()) { }
     52    FalseIt &operator++() { ++i; return *this;}
     53    operator Key() { return i<M.sep ? M.vals[i] : INVALID; }
     54    bool operator !=(Invalid) { return i<M.sep; }
     55    bool operator ==(Invalid) { return i>=M.sep; }
    5156  };
    52   class TrueIterator
     57  ///\e
     58  class TrueIt
    5359  {
    54     BoolIterEdgeMap &M;
     60    BoolIterMap &M;
    5561    int i;
    5662  public:
    57     TrueIterator(BoolIterEdgeMap &_M) : M(_M), i(M.vals.size()-1) { }
    58     TrueIterator &operator++() { --i; return *this;}
    59     operator Edge() { return i>=M.sep ? M.vals[i] : INVALID; }
    60     operator bool() { return i>=M.sep; }
     63    explicit TrueIt(BoolIterMap &_M) : M(_M), i(M.vals.size()-1) { }
     64    TrueIt(Invalid)
     65      : M(*((BoolIterMap*)(0))), i(-1) { }
     66    TrueIt &operator++() { --i; return *this;}
     67    operator Key() { return i>=M.sep ? M.vals[i] : INVALID; }
     68    bool operator !=(Invalid) { return i>=M.sep; }
     69    bool operator ==(Invalid) { return i<M.sep; }
    6170  };
    6271 
    63   class RefType
     72  ///\e
     73  class RefType
    6474  {
    65     BoolIterEdgeMap &M;
    66     Edge e;
     75    BoolIterMap &M;
     76    Key k;
    6777  public:
    68     RefType(BoolIterEdgeMap &_M,Edge _e) : M(_M), e(_e) { }
     78    RefType(BoolIterMap &_M,Key _k) : M(_M), k(_k) { }
    6979   
    7080    operator Value() const
    7181    {
    72       return M.isTrue(e);
    73      
     82      return M.isTrue(k);
    7483    }
    75     Value operator = (Value v) const
    76     {
    77       if(v) M.setTrue(e);
    78       else M.setFalse(e);
    79       return v;
    80     }
     84    Value operator = (Value v) const { M.set(k,v); return v; }
    8185  };
    8286 
    8387public:
    84   BoolIterEdgeMap(Graph &_G) : G(_G), cref(G)
     88  explicit BoolIterMap(BaseMap &_m) : cref(_m)
    8589  {
    8690    sep=0;
    87     for(typename Graph::EdgeIt e(G);G.valid(e);G.next(e)) {
    88       cref[e]=sep;
    89       vals.push_back(e);
     91    for(typename BaseMap::MapSet::iterator i=cref.mapSet().begin();
     92        i!=cref.mapSet().end();
     93        ++i) {
     94      i->second=sep;
     95      vals.push_back(i->first);
    9096      sep++;
    9197    }
    9298  }
    93   RefType operator[] (Edge e) { return RefType(*this,e);} 
     99  RefType operator[] (Key k) { return RefType(*this,k);} 
     100  Value operator[] (Key k) const { return isTrue(k);} 
    94101};
    95102
     
    105112  for(int i=0;i<3;i++) G.addNode();
    106113
    107   for(NodeIt n(G);G.valid(n);G.next(n))
    108     for(NodeIt m(G);G.valid(m);G.next(m)) if(n!=m)
     114  for(NodeIt n(G);n!=INVALID;++n)
     115    for(NodeIt m(G);m!=INVALID;++m) if(n!=m)
    109116      G.addEdge(n,m);
    110117
    111118  //for(OutEdgeIt e(G,NodeIt(G));G.valid(e);G.next(e))
    112119   
    113   BoolIterEdgeMap<Graph> map(G);
     120  Graph::EdgeMap<int> tem(G);
     121  typedef BoolIterMap<Graph::EdgeMap<int> > BoolIterEdgeMap;
     122  BoolIterEdgeMap map(tem);
    114123
    115124  bool b=true;
    116125 
    117   for(EdgeIt e(G);G.valid(e);G.next(e)) {map[e]=b;b=!b;}
     126  for(EdgeIt e(G);e!=INVALID;++e) {map[e]=b;b=!b;}
    118127 
    119128  std::cout << true << '\n';
    120129
    121   for(EdgeIt e(G);G.valid(e);G.next(e))
     130  for(EdgeIt e(G);e!=INVALID;++e)
    122131    std::cout << G.id(G.source(e)) << "->" << G.id(G.target(e))
    123132      << ": " << map[e] << '\n';
    124133  std::cout << "True Edges:\n";
    125   for(BoolIterEdgeMap<Graph>::TrueIterator i(map);i;++i)
     134  for(BoolIterEdgeMap::TrueIt i(map);i!=INVALID;++i)
    126135    std::cout << G.id(G.source(i)) << "->" << G.id(G.target(i)) << '\n';
    127136  std::cout << "False Edges:\n";
    128   for(BoolIterEdgeMap<Graph>::FalseIterator i(map);i;++i)
     137  for(BoolIterEdgeMap::FalseIt i(map);i!=INVALID;++i)
    129138    std::cout << G.id(G.source(i)) << "->" << G.id(G.target(i)) << '\n';
    130139}
Note: See TracChangeset for help on using the changeset viewer.