lemon/iterable_maps.h
author deba
Fri, 04 Nov 2005 16:10:23 +0000
changeset 1769 a67ec111236c
parent 1752 dce1f28ac595
child 1805 d284f81f02a5
permissions -rw-r--r--
Removed todo
Moved to topology module
alpar@1677
     1
/* -*- C++ -*-
alpar@1677
     2
 * lemon/iterable_maps.h - Part of LEMON, a generic C++ optimization library
alpar@1677
     3
 *
alpar@1677
     4
 * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
alpar@1677
     5
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
alpar@1677
     6
 *
alpar@1677
     7
 * Permission to use, modify and distribute this software is granted
alpar@1677
     8
 * provided that this copyright notice appears in all copies. For
alpar@1677
     9
 * precise terms see the accompanying LICENSE file.
alpar@1677
    10
 *
alpar@1677
    11
 * This software is provided "AS IS" with no warranty of any kind,
alpar@1677
    12
 * express or implied, and with no claim as to its suitability for any
alpar@1677
    13
 * purpose.
alpar@1677
    14
 *
alpar@1677
    15
 */
alpar@1677
    16
deba@1752
    17
#include <lemon/traits.h>
deba@1752
    18
#include <lemon/invalid.h>
alpar@1677
    19
#include <vector>
alpar@1677
    20
#include <limits>
alpar@1677
    21
alpar@1677
    22
///\ingroup maps
alpar@1677
    23
///\file
alpar@1677
    24
///\brief Maps that makes it possible to iterate through the keys having
alpar@1677
    25
///a certain value
alpar@1677
    26
///
alpar@1677
    27
///
alpar@1677
    28
alpar@1677
    29
alpar@1677
    30
namespace lemon {
alpar@1677
    31
  
alpar@1677
    32
  ///\todo This is only a static map!
alpar@1677
    33
  ///\param BaseMap is an interger map.
alpar@1677
    34
  template<class BaseMap>
alpar@1677
    35
  class IterableBoolMap
alpar@1677
    36
  {
alpar@1677
    37
  public:
alpar@1677
    38
  
alpar@1677
    39
    typedef typename BaseMap::Key Key;
alpar@1677
    40
    typedef bool Value;
alpar@1677
    41
  
alpar@1677
    42
    friend class RefType;
alpar@1677
    43
    friend class FalseIt;
alpar@1677
    44
    friend class TrueIt;
alpar@1677
    45
alpar@1677
    46
  private:
alpar@1677
    47
    BaseMap &cref;
alpar@1677
    48
    std::vector<Key> vals;
alpar@1677
    49
    int sep;           //map[e] is true <=> cref[e]>=sep
alpar@1677
    50
  
alpar@1677
    51
    bool isTrue(Key k) {return cref[k]>=sep;}
alpar@1677
    52
    void swap(Key k, int s) 
alpar@1677
    53
    {
alpar@1677
    54
      int ti=cref[k];
alpar@1677
    55
      Key tk=vals[s];
alpar@1677
    56
      cref[k]=s; vals[s]=k;
alpar@1677
    57
      cref[tk]=ti; vals[ti]=tk;
alpar@1677
    58
    }  
alpar@1677
    59
alpar@1677
    60
    void setTrue(Key k) { if(cref[k]<sep) { sep--; swap(k,sep); } }
alpar@1677
    61
    void setFalse(Key k) { if(cref[k]>=sep) { swap(k,sep); sep++; } }
alpar@1677
    62
  
alpar@1677
    63
  public:
alpar@1677
    64
    ///\e
alpar@1677
    65
    void set(Key k,Value v) { if(v) setTrue(k); else setFalse(k);}
alpar@1677
    66
alpar@1677
    67
    ///\e
alpar@1677
    68
    class FalseIt
alpar@1677
    69
    {
alpar@1677
    70
      const IterableBoolMap &M;
alpar@1677
    71
      int i;
alpar@1677
    72
    public:
alpar@1677
    73
      explicit FalseIt(const IterableBoolMap &_M) : M(_M), i(0) { }
alpar@1677
    74
      FalseIt(Invalid)
alpar@1677
    75
	: M(*((IterableBoolMap*)(0))), i(std::numeric_limits<int>::max()) { }
alpar@1677
    76
      FalseIt &operator++() { ++i; return *this;}
alpar@1677
    77
      operator Key() const { return i<M.sep ? M.vals[i] : INVALID; }
alpar@1677
    78
      bool operator !=(Invalid) const { return i<M.sep; }
alpar@1677
    79
      bool operator ==(Invalid) const { return i>=M.sep; }
alpar@1677
    80
    };
alpar@1677
    81
    ///\e
alpar@1677
    82
    class TrueIt
alpar@1677
    83
    {
alpar@1677
    84
      const IterableBoolMap &M;
alpar@1677
    85
      int i;
alpar@1677
    86
    public:
alpar@1677
    87
      explicit TrueIt(const IterableBoolMap &_M)
alpar@1677
    88
	: M(_M), i(M.vals.size()-1) { }
alpar@1677
    89
      TrueIt(Invalid)
alpar@1677
    90
	: M(*((IterableBoolMap*)(0))), i(-1) { }
alpar@1677
    91
      TrueIt &operator++() { --i; return *this;}
alpar@1677
    92
      operator Key() const { return i>=M.sep ? M.vals[i] : INVALID; }
alpar@1677
    93
      bool operator !=(Invalid) const { return i>=M.sep; }
alpar@1677
    94
      bool operator ==(Invalid) const { return i<M.sep; }
alpar@1677
    95
    };
alpar@1677
    96
  
alpar@1677
    97
    ///\e
alpar@1677
    98
    class RefType
alpar@1677
    99
    {
alpar@1677
   100
      IterableBoolMap &M;
alpar@1677
   101
      Key k;
alpar@1677
   102
    public:
alpar@1677
   103
      RefType(IterableBoolMap &_M,Key _k) : M(_M), k(_k) { }
alpar@1677
   104
    
alpar@1677
   105
      operator Value() const 
alpar@1677
   106
      {
alpar@1677
   107
	return M.isTrue(k);
alpar@1677
   108
      }
alpar@1677
   109
      Value operator = (Value v) const { M.set(k,v); return v; }
alpar@1677
   110
    };
alpar@1677
   111
  
alpar@1677
   112
  public:
alpar@1677
   113
    explicit IterableBoolMap(BaseMap &_m,bool init=false) : cref(_m)
alpar@1677
   114
    {
alpar@1677
   115
      sep=0;
alpar@1677
   116
      for(typename BaseMap::MapSet::iterator i=cref.mapSet().begin();
alpar@1677
   117
	  i!=cref.mapSet().end();
alpar@1677
   118
	  ++i) {
alpar@1677
   119
	i->second=sep;
alpar@1677
   120
	vals.push_back(i->first);
alpar@1677
   121
	sep++;
alpar@1677
   122
      }
alpar@1677
   123
      if(init) sep=0;
alpar@1677
   124
    }
alpar@1677
   125
    RefType operator[] (Key k) { return RefType(*this,k);}  
alpar@1677
   126
    Value operator[] (Key k) const { return isTrue(k);}  
alpar@1677
   127
  };
alpar@1677
   128
alpar@1677
   129
alpar@1677
   130
alpar@1677
   131
alpar@1677
   132
  /// \addtogroup graph_maps
alpar@1677
   133
  /// @{
alpar@1677
   134
alpar@1677
   135
  /// Iterable bool NodeMap
alpar@1677
   136
alpar@1677
   137
  /// This map can be used in the same way
alpar@1677
   138
  /// as the standard NodeMap<bool> of the
alpar@1677
   139
  /// given graph \c Graph. 
alpar@1677
   140
  /// In addition, this class provides two iterators called \ref TrueIt
alpar@1677
   141
  /// and \ref FalseIt to iterate through the "true" and "false" nodes.
alpar@1677
   142
  template <class Graph>
alpar@1677
   143
  class IterableBoolNodeMap
alpar@1677
   144
  {
deba@1685
   145
    typename Graph::template NodeMap<int> cmap;
alpar@1677
   146
  
alpar@1677
   147
  public:
alpar@1677
   148
  
deba@1685
   149
    typedef IterableBoolMap<typename Graph::template NodeMap<int> > BimType;
alpar@1677
   150
    BimType imap;
alpar@1677
   151
alpar@1677
   152
alpar@1677
   153
    typedef typename BimType::RefType RefType;
alpar@1677
   154
    typedef typename Graph::Node Key;
alpar@1677
   155
    typedef bool Value;
alpar@1677
   156
  
alpar@1677
   157
    friend class FalseIt;
alpar@1677
   158
    friend class TrueIt;
alpar@1677
   159
  
alpar@1677
   160
    ///\e
alpar@1677
   161
    IterableBoolNodeMap(const Graph &g,bool b=false) : cmap(g), imap(cmap,b) {}
alpar@1677
   162
alpar@1677
   163
  public:
alpar@1677
   164
    ///\e
alpar@1677
   165
    void set(Key k, bool v) { imap.set(k,v);}
alpar@1677
   166
#ifdef DOXYGEN
alpar@1677
   167
    ///\e
alpar@1677
   168
    bool &operator[](Key k) { return imap[k];}  
alpar@1677
   169
    ///\e
alpar@1677
   170
    const bool &operator[](Key k) const { return imap[k];}  
alpar@1677
   171
#else
alpar@1677
   172
    Value operator[](Key k) const { return imap[k];}  
alpar@1677
   173
    RefType operator[](Key k) { return imap[k];}  
alpar@1677
   174
#endif
alpar@1677
   175
    ///Iterator for the "false" nodes
alpar@1677
   176
    class FalseIt : public BimType::FalseIt
alpar@1677
   177
    {
alpar@1677
   178
    public:
alpar@1677
   179
      explicit FalseIt(const IterableBoolNodeMap &m)
alpar@1677
   180
	: BimType::FalseIt(m.imap) { }
alpar@1677
   181
      FalseIt(Invalid i) : BimType::FalseIt(i) { }
alpar@1677
   182
    };
alpar@1677
   183
    ///Iterator for the "true" nodes
alpar@1677
   184
    class TrueIt : public BimType::TrueIt
alpar@1677
   185
    {
alpar@1677
   186
    public:
alpar@1677
   187
      explicit TrueIt(const IterableBoolNodeMap &m)
alpar@1677
   188
	: BimType::TrueIt(m.imap) { }
alpar@1677
   189
      TrueIt(Invalid i) : BimType::TrueIt(i) { }
alpar@1677
   190
    };  
alpar@1677
   191
  };
alpar@1677
   192
alpar@1677
   193
  /// Iterable bool EdgeMap
alpar@1677
   194
alpar@1677
   195
  /// This map can be used in the same way
alpar@1677
   196
  /// as the standard EdgeMap<bool> of the
alpar@1677
   197
  /// given graph \c Graph. 
alpar@1677
   198
  /// In addition, this class provides two iterators called \ref TrueIt
alpar@1677
   199
  /// and \ref FalseIt to iterate through the "true" and "false" edges.
alpar@1677
   200
  template <class Graph>
alpar@1677
   201
  class IterableBoolEdgeMap
alpar@1677
   202
  {
deba@1685
   203
    typename Graph::template EdgeMap<int> cmap;
alpar@1677
   204
  
alpar@1677
   205
  public:
alpar@1677
   206
  
deba@1685
   207
    typedef IterableBoolMap<typename Graph::template EdgeMap<int> > BimType;
alpar@1677
   208
    BimType imap;
alpar@1677
   209
alpar@1677
   210
alpar@1677
   211
    typedef typename BimType::RefType RefType;
alpar@1677
   212
    typedef typename Graph::Edge Key;
alpar@1677
   213
    typedef bool Value;
alpar@1677
   214
  
alpar@1677
   215
    friend class FalseIt;
alpar@1677
   216
    friend class TrueIt;
alpar@1677
   217
  
alpar@1677
   218
    ///\e
alpar@1677
   219
    IterableBoolEdgeMap(const Graph &g,bool b=false) : cmap(g), imap(cmap,b) {}
alpar@1677
   220
alpar@1677
   221
  public:
alpar@1677
   222
    ///\e
alpar@1677
   223
    void set(Key k, bool v) { imap.set(k,v);}
alpar@1677
   224
#ifdef DOXYGEN
alpar@1677
   225
    ///\e
alpar@1677
   226
    bool &operator[](Key k) { return imap[k];}  
alpar@1677
   227
    ///\e
alpar@1677
   228
    const bool &operator[](Key k) const { return imap[k];}  
alpar@1677
   229
#else
alpar@1677
   230
    Value operator[](Key k) const { return imap[k];}  
alpar@1677
   231
    RefType operator[](Key k) { return imap[k];}  
alpar@1677
   232
#endif
alpar@1677
   233
    ///Iterator for the "false" edges
alpar@1677
   234
    class FalseIt : public BimType::FalseIt
alpar@1677
   235
    {
alpar@1677
   236
    public:
alpar@1677
   237
      explicit FalseIt(const IterableBoolEdgeMap &m)
alpar@1677
   238
	: BimType::FalseIt(m.imap) { }
alpar@1677
   239
      FalseIt(Invalid i) : BimType::FalseIt(i) { }
alpar@1677
   240
    };
alpar@1677
   241
    ///Iterator for the "true" edges
alpar@1677
   242
    class TrueIt : public BimType::TrueIt
alpar@1677
   243
    {
alpar@1677
   244
    public:
alpar@1677
   245
      explicit TrueIt(const IterableBoolEdgeMap &m)
alpar@1677
   246
	: BimType::TrueIt(m.imap) { }
alpar@1677
   247
      TrueIt(Invalid i) : BimType::TrueIt(i) { }
alpar@1677
   248
    };  
alpar@1677
   249
  };
alpar@1677
   250
deba@1752
   251
deba@1752
   252
  namespace _iterable_maps_bits {
deba@1752
   253
    template <typename Item>
deba@1752
   254
    struct IterableIntMapNode {
deba@1752
   255
      IterableIntMapNode() : value(-1) {}
deba@1752
   256
      Item prev, next;
deba@1752
   257
      int value;
deba@1752
   258
    };
deba@1752
   259
  }
deba@1752
   260
deba@1752
   261
  ///\ingroup maps
deba@1752
   262
  ///
deba@1752
   263
  /// \brief Dynamic iterable integer map.
deba@1752
   264
  ///
deba@1752
   265
  /// \todo Document please
deba@1752
   266
  template <typename _Graph, typename _Item>
deba@1752
   267
  class IterableIntMap : protected ItemSetTraits<_Graph, _Item> 
deba@1752
   268
  ::template Map<_iterable_maps_bits::IterableIntMapNode<_Item> >::Parent {
deba@1752
   269
  public:
deba@1752
   270
    typedef typename ItemSetTraits<_Graph, _Item> 
deba@1752
   271
    ::template Map<_iterable_maps_bits::IterableIntMapNode<_Item> >
deba@1752
   272
    ::Parent Parent;
deba@1752
   273
deba@1752
   274
    typedef _Item Key;
deba@1752
   275
    typedef int Value;
deba@1752
   276
    typedef _Graph Graph;
deba@1752
   277
deba@1759
   278
    explicit IterableIntMap(const Graph& graph) : Parent(graph) {}
deba@1752
   279
deba@1752
   280
  private:
deba@1752
   281
    
deba@1752
   282
    void unlace(const Key& key) {
deba@1752
   283
      typename Parent::Value& node = Parent::operator[](key);
deba@1752
   284
      if (node.value < 0) return;
deba@1752
   285
      if (node.prev != INVALID) {
deba@1752
   286
	Parent::operator[](node.prev).next = node.next;	
deba@1752
   287
      } else {
deba@1752
   288
	first[node.value] = node.next;
deba@1752
   289
      }
deba@1752
   290
      if (node.next != INVALID) {
deba@1752
   291
	Parent::operator[](node.next).prev = node.prev;
deba@1752
   292
      }
deba@1752
   293
      while (!first.empty() && first.back() == INVALID) {
deba@1752
   294
	first.pop_back();
deba@1752
   295
      }
deba@1752
   296
    }
deba@1752
   297
deba@1752
   298
    void lace(const Key& key) {
deba@1752
   299
      typename Parent::Value& node = Parent::operator[](key);
deba@1752
   300
      if (node.value < 0) return;
deba@1752
   301
      if (node.value >= (int)first.size()) {
deba@1752
   302
	first.resize(node.value + 1, INVALID);
deba@1752
   303
      } 
deba@1752
   304
      node.prev = INVALID;
deba@1752
   305
      node.next = first[node.value];
deba@1752
   306
      if (node.next != INVALID) {
deba@1752
   307
	Parent::operator[](node.next).prev = key;	
deba@1752
   308
      }
deba@1752
   309
      first[node.value] = key;
deba@1752
   310
    }
deba@1752
   311
deba@1752
   312
  public:
deba@1752
   313
deba@1752
   314
    typedef True ReferenceMapTag;
deba@1752
   315
deba@1752
   316
    class Reference {
deba@1752
   317
      friend class IterableIntMap;
deba@1752
   318
    private:
deba@1752
   319
      Reference(IterableIntMap& map, const Key& key) 
deba@1752
   320
	: _key(key), _map(map) {} 
deba@1752
   321
    public:
deba@1752
   322
deba@1752
   323
      Reference& operator=(const Reference& value) {
deba@1752
   324
	_map.set(_key, (const int&)value);
deba@1752
   325
 	return *this;
deba@1752
   326
      }
deba@1752
   327
deba@1752
   328
      operator const int&() const { 
deba@1752
   329
	return static_cast<const IterableIntMap&>(_map)[_key]; 
deba@1752
   330
      }
deba@1752
   331
deba@1752
   332
      Reference& operator=(int value) { 
deba@1752
   333
	_map.set(_key, value); 
deba@1752
   334
	return *this; 
deba@1752
   335
      }
deba@1759
   336
      Reference& operator++() {
deba@1759
   337
	_map.set(_key, _map[_key] + 1); 
deba@1759
   338
	return *this; 	
deba@1759
   339
      }
deba@1759
   340
      int operator++(int) {
deba@1759
   341
	int value = _map[_key];
deba@1759
   342
	_map.set(_key, value + 1); 
deba@1759
   343
	return value; 	
deba@1759
   344
      }
deba@1759
   345
      Reference& operator--() {
deba@1759
   346
	_map.set(_key, _map[_key] - 1); 
deba@1759
   347
	return *this; 	
deba@1759
   348
      }
deba@1759
   349
      int operator--(int) {
deba@1759
   350
	int value = _map[_key];
deba@1759
   351
	_map.set(_key, value - 1); 
deba@1759
   352
	return value; 	
deba@1759
   353
      }
deba@1752
   354
      Reference& operator+=(int value) { 
deba@1752
   355
	_map.set(_key, _map[_key] + value); 
deba@1752
   356
	return *this;
deba@1752
   357
      }
deba@1752
   358
      Reference& operator-=(int value) { 
deba@1752
   359
	_map.set(_key, _map[_key] - value); 
deba@1752
   360
	return *this;
deba@1752
   361
      }
deba@1752
   362
      Reference& operator*=(int value) { 
deba@1752
   363
	_map.set(_key, _map[_key] * value); 
deba@1752
   364
	return *this;
deba@1752
   365
      }
deba@1752
   366
      Reference& operator/=(int value) { 
deba@1752
   367
	_map.set(_key, _map[_key] / value); 
deba@1752
   368
	return *this;
deba@1752
   369
      }
deba@1752
   370
      Reference& operator%=(int value) { 
deba@1752
   371
	_map.set(_key, _map[_key] % value); 
deba@1752
   372
	return *this;
deba@1752
   373
      }
deba@1752
   374
      Reference& operator&=(int value) { 
deba@1752
   375
	_map.set(_key, _map[_key] & value); 
deba@1752
   376
	return *this;
deba@1752
   377
      }
deba@1752
   378
      Reference& operator|=(int value) { 
deba@1752
   379
	_map.set(_key, _map[_key] | value); 
deba@1752
   380
	return *this;
deba@1752
   381
      }
deba@1752
   382
      Reference& operator^=(int value) { 
deba@1752
   383
	_map.set(_key, _map[_key] ^ value); 
deba@1752
   384
	return *this;
deba@1752
   385
      }
deba@1752
   386
      Reference& operator<<=(int value) { 
deba@1752
   387
	_map.set(_key, _map[_key] << value); 
deba@1752
   388
	return *this;
deba@1752
   389
      }
deba@1752
   390
      Reference& operator>>=(int value) { 
deba@1752
   391
	_map.set(_key, _map[_key] >> value); 
deba@1752
   392
	return *this;
deba@1752
   393
      }
deba@1752
   394
deba@1752
   395
    private:
deba@1752
   396
      Key _key;
deba@1752
   397
      IterableIntMap& _map; 
deba@1752
   398
    };
deba@1752
   399
    
deba@1752
   400
    typedef const Value& ConstReference;
deba@1752
   401
deba@1752
   402
    int size() const {
deba@1752
   403
      return (int)first.size();
deba@1752
   404
    }
deba@1752
   405
    
deba@1752
   406
    void set(const Key& key, const Value& value) {
deba@1752
   407
      unlace(key);
deba@1752
   408
      Parent::operator[](key).value = value;
deba@1752
   409
      lace(key);
deba@1752
   410
    }
deba@1752
   411
deba@1752
   412
    const Value& operator[](const Key& key) const {
deba@1752
   413
      return Parent::operator[](key).value;
deba@1752
   414
    }
deba@1752
   415
deba@1752
   416
    Reference operator[](const Key& key) {
deba@1752
   417
      return Reference(*this, key);
deba@1752
   418
    }
deba@1752
   419
deba@1752
   420
    class ItemIt : public _Item {
deba@1752
   421
    public:
deba@1752
   422
      typedef _Item Parent;
deba@1752
   423
deba@1752
   424
      ItemIt(Invalid) : Parent(INVALID), _map(0) {}
deba@1752
   425
deba@1752
   426
      ItemIt(const IterableIntMap& map, int value) : _map(&map) {
deba@1752
   427
	if (value < 0 || value >= (int)_map->first.size()) {	  
deba@1752
   428
	  Parent::operator=(INVALID);
deba@1752
   429
	} else {
deba@1752
   430
	  Parent::operator=(_map->first[value]);
deba@1752
   431
	}
deba@1752
   432
      } 
deba@1752
   433
deba@1752
   434
      ItemIt& operator++() {
deba@1752
   435
	Parent::operator=(_map->IterableIntMap::Parent::
deba@1752
   436
			  operator[](static_cast<Parent&>(*this)).next);
deba@1752
   437
	return *this;
deba@1752
   438
      }
deba@1752
   439
deba@1752
   440
deba@1752
   441
    private:
deba@1752
   442
      const IterableIntMap* _map;
deba@1752
   443
    };
deba@1752
   444
deba@1752
   445
  protected:
deba@1752
   446
    
deba@1752
   447
    virtual void erase(const Key& key) {
deba@1752
   448
      unlace(key);
deba@1752
   449
      Parent::erase(key);
deba@1752
   450
    }
deba@1752
   451
deba@1752
   452
    virtual void clear() {
deba@1752
   453
      first.clear();
deba@1752
   454
      Parent::clear();
deba@1752
   455
    }
deba@1752
   456
deba@1752
   457
  private:
deba@1752
   458
    std::vector<_Item> first;
deba@1752
   459
  };
deba@1752
   460
alpar@1677
   461
  /// @}
alpar@1677
   462
}