lemon/iterable_maps.h
author alpar
Wed, 16 Nov 2005 13:26:04 +0000
changeset 1807 5f2f3d982eba
parent 1759 0bb3fb3baffd
child 1810 474d093466a5
permissions -rw-r--r--
Empty graph is (strongly) connected.
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@1805
    33
  ///\todo Undocumented.
alpar@1677
    34
  ///\param BaseMap is an interger map.
alpar@1677
    35
  template<class BaseMap>
alpar@1677
    36
  class IterableBoolMap
alpar@1677
    37
  {
alpar@1677
    38
  public:
alpar@1677
    39
  
alpar@1677
    40
    typedef typename BaseMap::Key Key;
alpar@1677
    41
    typedef bool Value;
alpar@1677
    42
  
alpar@1677
    43
    friend class RefType;
alpar@1677
    44
    friend class FalseIt;
alpar@1677
    45
    friend class TrueIt;
alpar@1677
    46
alpar@1677
    47
  private:
alpar@1677
    48
    BaseMap &cref;
alpar@1677
    49
    std::vector<Key> vals;
alpar@1677
    50
    int sep;           //map[e] is true <=> cref[e]>=sep
alpar@1677
    51
  
alpar@1677
    52
    bool isTrue(Key k) {return cref[k]>=sep;}
alpar@1677
    53
    void swap(Key k, int s) 
alpar@1677
    54
    {
alpar@1677
    55
      int ti=cref[k];
alpar@1677
    56
      Key tk=vals[s];
alpar@1677
    57
      cref[k]=s; vals[s]=k;
alpar@1677
    58
      cref[tk]=ti; vals[ti]=tk;
alpar@1677
    59
    }  
alpar@1677
    60
alpar@1677
    61
    void setTrue(Key k) { if(cref[k]<sep) { sep--; swap(k,sep); } }
alpar@1677
    62
    void setFalse(Key k) { if(cref[k]>=sep) { swap(k,sep); sep++; } }
alpar@1677
    63
  
alpar@1677
    64
  public:
alpar@1677
    65
    ///\e
alpar@1677
    66
    void set(Key k,Value v) { if(v) setTrue(k); else setFalse(k);}
alpar@1805
    67
    ///Number of \c true items in the map
alpar@1805
    68
alpar@1805
    69
    ///Returns the number of \c true values in the map.
alpar@1805
    70
    ///This is a constant time operation.
alpar@1805
    71
    int countTrue() { return vals.size()-sep; }
alpar@1805
    72
    ///Number of \c false items in the map
alpar@1805
    73
alpar@1805
    74
    ///Returns the number of \c false values in the map.
alpar@1805
    75
    ///This is a constant time operation.
alpar@1805
    76
    int countFalse() { return sep; }
alpar@1677
    77
alpar@1677
    78
    ///\e
alpar@1677
    79
    class FalseIt
alpar@1677
    80
    {
alpar@1677
    81
      const IterableBoolMap &M;
alpar@1677
    82
      int i;
alpar@1677
    83
    public:
alpar@1805
    84
      ///\e
alpar@1677
    85
      explicit FalseIt(const IterableBoolMap &_M) : M(_M), i(0) { }
alpar@1805
    86
      ///\e
alpar@1677
    87
      FalseIt(Invalid)
alpar@1677
    88
	: M(*((IterableBoolMap*)(0))), i(std::numeric_limits<int>::max()) { }
alpar@1805
    89
      ///\e
alpar@1677
    90
      FalseIt &operator++() { ++i; return *this;}
alpar@1805
    91
      ///\e
alpar@1677
    92
      operator Key() const { return i<M.sep ? M.vals[i] : INVALID; }
alpar@1805
    93
      ///\e
alpar@1677
    94
      bool operator !=(Invalid) const { return i<M.sep; }
alpar@1805
    95
      ///\e
alpar@1677
    96
      bool operator ==(Invalid) const { return i>=M.sep; }
alpar@1677
    97
    };
alpar@1677
    98
    ///\e
alpar@1677
    99
    class TrueIt
alpar@1677
   100
    {
alpar@1677
   101
      const IterableBoolMap &M;
alpar@1677
   102
      int i;
alpar@1677
   103
    public:
alpar@1805
   104
      ///\e
alpar@1677
   105
      explicit TrueIt(const IterableBoolMap &_M)
alpar@1677
   106
	: M(_M), i(M.vals.size()-1) { }
alpar@1805
   107
      ///\e
alpar@1677
   108
      TrueIt(Invalid)
alpar@1677
   109
	: M(*((IterableBoolMap*)(0))), i(-1) { }
alpar@1805
   110
      ///\e
alpar@1677
   111
      TrueIt &operator++() { --i; return *this;}
alpar@1805
   112
      ///\e
alpar@1677
   113
      operator Key() const { return i>=M.sep ? M.vals[i] : INVALID; }
alpar@1805
   114
      ///\e
alpar@1677
   115
      bool operator !=(Invalid) const { return i>=M.sep; }
alpar@1805
   116
      ///\e
alpar@1677
   117
      bool operator ==(Invalid) const { return i<M.sep; }
alpar@1677
   118
    };
alpar@1677
   119
  
alpar@1677
   120
    ///\e
alpar@1677
   121
    class RefType
alpar@1677
   122
    {
alpar@1677
   123
      IterableBoolMap &M;
alpar@1677
   124
      Key k;
alpar@1677
   125
    public:
alpar@1677
   126
      RefType(IterableBoolMap &_M,Key _k) : M(_M), k(_k) { }
alpar@1677
   127
    
alpar@1677
   128
      operator Value() const 
alpar@1677
   129
      {
alpar@1677
   130
	return M.isTrue(k);
alpar@1677
   131
      }
alpar@1677
   132
      Value operator = (Value v) const { M.set(k,v); return v; }
alpar@1677
   133
    };
alpar@1677
   134
  
alpar@1677
   135
  public:
alpar@1677
   136
    explicit IterableBoolMap(BaseMap &_m,bool init=false) : cref(_m)
alpar@1677
   137
    {
alpar@1677
   138
      sep=0;
alpar@1677
   139
      for(typename BaseMap::MapSet::iterator i=cref.mapSet().begin();
alpar@1677
   140
	  i!=cref.mapSet().end();
alpar@1677
   141
	  ++i) {
alpar@1677
   142
	i->second=sep;
alpar@1677
   143
	vals.push_back(i->first);
alpar@1677
   144
	sep++;
alpar@1677
   145
      }
alpar@1677
   146
      if(init) sep=0;
alpar@1677
   147
    }
alpar@1805
   148
    ///\e
alpar@1677
   149
    RefType operator[] (Key k) { return RefType(*this,k);}  
alpar@1805
   150
    ///\e
alpar@1677
   151
    Value operator[] (Key k) const { return isTrue(k);}  
alpar@1677
   152
  };
alpar@1677
   153
alpar@1677
   154
alpar@1677
   155
alpar@1677
   156
alpar@1677
   157
  /// \addtogroup graph_maps
alpar@1677
   158
  /// @{
alpar@1677
   159
alpar@1677
   160
  /// Iterable bool NodeMap
alpar@1677
   161
alpar@1677
   162
  /// This map can be used in the same way
alpar@1677
   163
  /// as the standard NodeMap<bool> of the
alpar@1677
   164
  /// given graph \c Graph. 
alpar@1677
   165
  /// In addition, this class provides two iterators called \ref TrueIt
alpar@1677
   166
  /// and \ref FalseIt to iterate through the "true" and "false" nodes.
alpar@1677
   167
  template <class Graph>
alpar@1677
   168
  class IterableBoolNodeMap
alpar@1677
   169
  {
deba@1685
   170
    typename Graph::template NodeMap<int> cmap;
alpar@1677
   171
  
alpar@1677
   172
  public:
alpar@1677
   173
  
deba@1685
   174
    typedef IterableBoolMap<typename Graph::template NodeMap<int> > BimType;
alpar@1677
   175
    BimType imap;
alpar@1677
   176
alpar@1677
   177
alpar@1677
   178
    typedef typename BimType::RefType RefType;
alpar@1677
   179
    typedef typename Graph::Node Key;
alpar@1677
   180
    typedef bool Value;
alpar@1677
   181
  
alpar@1677
   182
    friend class FalseIt;
alpar@1677
   183
    friend class TrueIt;
alpar@1677
   184
  
alpar@1677
   185
    ///\e
alpar@1677
   186
    IterableBoolNodeMap(const Graph &g,bool b=false) : cmap(g), imap(cmap,b) {}
alpar@1677
   187
alpar@1677
   188
  public:
alpar@1677
   189
    ///\e
alpar@1677
   190
    void set(Key k, bool v) { imap.set(k,v);}
alpar@1805
   191
    ///Number of \c true items in the map
alpar@1805
   192
alpar@1805
   193
    ///Returns the number of \c true values in the map.
alpar@1805
   194
    ///This is a constant time operation.
alpar@1805
   195
    int countTrue() { return imap.countTrue(); }
alpar@1805
   196
    ///Number of \c false items in the map
alpar@1805
   197
alpar@1805
   198
    ///Returns the number of \c false values in the map.
alpar@1805
   199
    ///This is a constant time operation.
alpar@1805
   200
    int countFalse() { return imap.countFalse(); }
alpar@1677
   201
#ifdef DOXYGEN
alpar@1677
   202
    ///\e
alpar@1677
   203
    bool &operator[](Key k) { return imap[k];}  
alpar@1677
   204
    ///\e
alpar@1677
   205
    const bool &operator[](Key k) const { return imap[k];}  
alpar@1677
   206
#else
alpar@1677
   207
    Value operator[](Key k) const { return imap[k];}  
alpar@1677
   208
    RefType operator[](Key k) { return imap[k];}  
alpar@1677
   209
#endif
alpar@1677
   210
    ///Iterator for the "false" nodes
alpar@1677
   211
    class FalseIt : public BimType::FalseIt
alpar@1677
   212
    {
alpar@1677
   213
    public:
alpar@1805
   214
      ///\e
alpar@1677
   215
      explicit FalseIt(const IterableBoolNodeMap &m)
alpar@1677
   216
	: BimType::FalseIt(m.imap) { }
alpar@1805
   217
      ///\e
alpar@1677
   218
      FalseIt(Invalid i) : BimType::FalseIt(i) { }
alpar@1677
   219
    };
alpar@1677
   220
    ///Iterator for the "true" nodes
alpar@1677
   221
    class TrueIt : public BimType::TrueIt
alpar@1677
   222
    {
alpar@1677
   223
    public:
alpar@1805
   224
      ///\e
alpar@1677
   225
      explicit TrueIt(const IterableBoolNodeMap &m)
alpar@1677
   226
	: BimType::TrueIt(m.imap) { }
alpar@1805
   227
      ///\e
alpar@1677
   228
      TrueIt(Invalid i) : BimType::TrueIt(i) { }
alpar@1677
   229
    };  
alpar@1677
   230
  };
alpar@1677
   231
alpar@1677
   232
  /// Iterable bool EdgeMap
alpar@1677
   233
alpar@1677
   234
  /// This map can be used in the same way
alpar@1677
   235
  /// as the standard EdgeMap<bool> of the
alpar@1677
   236
  /// given graph \c Graph. 
alpar@1677
   237
  /// In addition, this class provides two iterators called \ref TrueIt
alpar@1677
   238
  /// and \ref FalseIt to iterate through the "true" and "false" edges.
alpar@1677
   239
  template <class Graph>
alpar@1677
   240
  class IterableBoolEdgeMap
alpar@1677
   241
  {
deba@1685
   242
    typename Graph::template EdgeMap<int> cmap;
alpar@1677
   243
  
alpar@1677
   244
  public:
alpar@1677
   245
  
deba@1685
   246
    typedef IterableBoolMap<typename Graph::template EdgeMap<int> > BimType;
alpar@1677
   247
    BimType imap;
alpar@1677
   248
alpar@1677
   249
alpar@1677
   250
    typedef typename BimType::RefType RefType;
alpar@1677
   251
    typedef typename Graph::Edge Key;
alpar@1677
   252
    typedef bool Value;
alpar@1677
   253
  
alpar@1677
   254
    friend class FalseIt;
alpar@1677
   255
    friend class TrueIt;
alpar@1677
   256
  
alpar@1677
   257
    ///\e
alpar@1677
   258
    IterableBoolEdgeMap(const Graph &g,bool b=false) : cmap(g), imap(cmap,b) {}
alpar@1677
   259
alpar@1677
   260
  public:
alpar@1677
   261
    ///\e
alpar@1677
   262
    void set(Key k, bool v) { imap.set(k,v);}
alpar@1805
   263
    ///Returns the number of \c true values in the map.
alpar@1805
   264
    ///This is a constant time operation.
alpar@1805
   265
    int countTrue() { return imap.countTrue(); }
alpar@1805
   266
    ///Number of \c false items in the map
alpar@1805
   267
alpar@1805
   268
    ///Returns the number of \c false values in the map.
alpar@1805
   269
    ///This is a constant time operation.
alpar@1805
   270
    int countFalse() { return imap.countFalse(); }
alpar@1677
   271
#ifdef DOXYGEN
alpar@1677
   272
    ///\e
alpar@1677
   273
    bool &operator[](Key k) { return imap[k];}  
alpar@1677
   274
    ///\e
alpar@1677
   275
    const bool &operator[](Key k) const { return imap[k];}  
alpar@1677
   276
#else
alpar@1677
   277
    Value operator[](Key k) const { return imap[k];}  
alpar@1677
   278
    RefType operator[](Key k) { return imap[k];}  
alpar@1677
   279
#endif
alpar@1677
   280
    ///Iterator for the "false" edges
alpar@1677
   281
    class FalseIt : public BimType::FalseIt
alpar@1677
   282
    {
alpar@1677
   283
    public:
alpar@1805
   284
      ///\e
alpar@1677
   285
      explicit FalseIt(const IterableBoolEdgeMap &m)
alpar@1677
   286
	: BimType::FalseIt(m.imap) { }
alpar@1805
   287
      ///\e
alpar@1677
   288
      FalseIt(Invalid i) : BimType::FalseIt(i) { }
alpar@1677
   289
    };
alpar@1677
   290
    ///Iterator for the "true" edges
alpar@1677
   291
    class TrueIt : public BimType::TrueIt
alpar@1677
   292
    {
alpar@1677
   293
    public:
alpar@1805
   294
      ///\e
alpar@1677
   295
      explicit TrueIt(const IterableBoolEdgeMap &m)
alpar@1677
   296
	: BimType::TrueIt(m.imap) { }
alpar@1805
   297
      ///\e
alpar@1677
   298
      TrueIt(Invalid i) : BimType::TrueIt(i) { }
alpar@1677
   299
    };  
alpar@1677
   300
  };
alpar@1677
   301
deba@1752
   302
deba@1752
   303
  namespace _iterable_maps_bits {
deba@1752
   304
    template <typename Item>
deba@1752
   305
    struct IterableIntMapNode {
deba@1752
   306
      IterableIntMapNode() : value(-1) {}
deba@1752
   307
      Item prev, next;
deba@1752
   308
      int value;
deba@1752
   309
    };
deba@1752
   310
  }
deba@1752
   311
deba@1752
   312
  ///\ingroup maps
deba@1752
   313
  ///
deba@1752
   314
  /// \brief Dynamic iterable integer map.
deba@1752
   315
  ///
deba@1752
   316
  /// \todo Document please
deba@1752
   317
  template <typename _Graph, typename _Item>
deba@1752
   318
  class IterableIntMap : protected ItemSetTraits<_Graph, _Item> 
deba@1752
   319
  ::template Map<_iterable_maps_bits::IterableIntMapNode<_Item> >::Parent {
deba@1752
   320
  public:
deba@1752
   321
    typedef typename ItemSetTraits<_Graph, _Item> 
deba@1752
   322
    ::template Map<_iterable_maps_bits::IterableIntMapNode<_Item> >
deba@1752
   323
    ::Parent Parent;
deba@1752
   324
deba@1752
   325
    typedef _Item Key;
deba@1752
   326
    typedef int Value;
deba@1752
   327
    typedef _Graph Graph;
deba@1752
   328
deba@1759
   329
    explicit IterableIntMap(const Graph& graph) : Parent(graph) {}
deba@1752
   330
deba@1752
   331
  private:
deba@1752
   332
    
deba@1752
   333
    void unlace(const Key& key) {
deba@1752
   334
      typename Parent::Value& node = Parent::operator[](key);
deba@1752
   335
      if (node.value < 0) return;
deba@1752
   336
      if (node.prev != INVALID) {
deba@1752
   337
	Parent::operator[](node.prev).next = node.next;	
deba@1752
   338
      } else {
deba@1752
   339
	first[node.value] = node.next;
deba@1752
   340
      }
deba@1752
   341
      if (node.next != INVALID) {
deba@1752
   342
	Parent::operator[](node.next).prev = node.prev;
deba@1752
   343
      }
deba@1752
   344
      while (!first.empty() && first.back() == INVALID) {
deba@1752
   345
	first.pop_back();
deba@1752
   346
      }
deba@1752
   347
    }
deba@1752
   348
deba@1752
   349
    void lace(const Key& key) {
deba@1752
   350
      typename Parent::Value& node = Parent::operator[](key);
deba@1752
   351
      if (node.value < 0) return;
deba@1752
   352
      if (node.value >= (int)first.size()) {
deba@1752
   353
	first.resize(node.value + 1, INVALID);
deba@1752
   354
      } 
deba@1752
   355
      node.prev = INVALID;
deba@1752
   356
      node.next = first[node.value];
deba@1752
   357
      if (node.next != INVALID) {
deba@1752
   358
	Parent::operator[](node.next).prev = key;	
deba@1752
   359
      }
deba@1752
   360
      first[node.value] = key;
deba@1752
   361
    }
deba@1752
   362
deba@1752
   363
  public:
deba@1752
   364
deba@1752
   365
    typedef True ReferenceMapTag;
deba@1752
   366
deba@1752
   367
    class Reference {
deba@1752
   368
      friend class IterableIntMap;
deba@1752
   369
    private:
deba@1752
   370
      Reference(IterableIntMap& map, const Key& key) 
deba@1752
   371
	: _key(key), _map(map) {} 
deba@1752
   372
    public:
deba@1752
   373
deba@1752
   374
      Reference& operator=(const Reference& value) {
deba@1752
   375
	_map.set(_key, (const int&)value);
deba@1752
   376
 	return *this;
deba@1752
   377
      }
deba@1752
   378
deba@1752
   379
      operator const int&() const { 
deba@1752
   380
	return static_cast<const IterableIntMap&>(_map)[_key]; 
deba@1752
   381
      }
deba@1752
   382
deba@1752
   383
      Reference& operator=(int value) { 
deba@1752
   384
	_map.set(_key, value); 
deba@1752
   385
	return *this; 
deba@1752
   386
      }
deba@1759
   387
      Reference& operator++() {
deba@1759
   388
	_map.set(_key, _map[_key] + 1); 
deba@1759
   389
	return *this; 	
deba@1759
   390
      }
deba@1759
   391
      int operator++(int) {
deba@1759
   392
	int value = _map[_key];
deba@1759
   393
	_map.set(_key, value + 1); 
deba@1759
   394
	return value; 	
deba@1759
   395
      }
deba@1759
   396
      Reference& operator--() {
deba@1759
   397
	_map.set(_key, _map[_key] - 1); 
deba@1759
   398
	return *this; 	
deba@1759
   399
      }
deba@1759
   400
      int operator--(int) {
deba@1759
   401
	int value = _map[_key];
deba@1759
   402
	_map.set(_key, value - 1); 
deba@1759
   403
	return value; 	
deba@1759
   404
      }
deba@1752
   405
      Reference& operator+=(int value) { 
deba@1752
   406
	_map.set(_key, _map[_key] + value); 
deba@1752
   407
	return *this;
deba@1752
   408
      }
deba@1752
   409
      Reference& operator-=(int value) { 
deba@1752
   410
	_map.set(_key, _map[_key] - value); 
deba@1752
   411
	return *this;
deba@1752
   412
      }
deba@1752
   413
      Reference& operator*=(int value) { 
deba@1752
   414
	_map.set(_key, _map[_key] * value); 
deba@1752
   415
	return *this;
deba@1752
   416
      }
deba@1752
   417
      Reference& operator/=(int value) { 
deba@1752
   418
	_map.set(_key, _map[_key] / value); 
deba@1752
   419
	return *this;
deba@1752
   420
      }
deba@1752
   421
      Reference& operator%=(int value) { 
deba@1752
   422
	_map.set(_key, _map[_key] % value); 
deba@1752
   423
	return *this;
deba@1752
   424
      }
deba@1752
   425
      Reference& operator&=(int value) { 
deba@1752
   426
	_map.set(_key, _map[_key] & value); 
deba@1752
   427
	return *this;
deba@1752
   428
      }
deba@1752
   429
      Reference& operator|=(int value) { 
deba@1752
   430
	_map.set(_key, _map[_key] | value); 
deba@1752
   431
	return *this;
deba@1752
   432
      }
deba@1752
   433
      Reference& operator^=(int value) { 
deba@1752
   434
	_map.set(_key, _map[_key] ^ value); 
deba@1752
   435
	return *this;
deba@1752
   436
      }
deba@1752
   437
      Reference& operator<<=(int value) { 
deba@1752
   438
	_map.set(_key, _map[_key] << value); 
deba@1752
   439
	return *this;
deba@1752
   440
      }
deba@1752
   441
      Reference& operator>>=(int value) { 
deba@1752
   442
	_map.set(_key, _map[_key] >> value); 
deba@1752
   443
	return *this;
deba@1752
   444
      }
deba@1752
   445
deba@1752
   446
    private:
deba@1752
   447
      Key _key;
deba@1752
   448
      IterableIntMap& _map; 
deba@1752
   449
    };
deba@1752
   450
    
deba@1752
   451
    typedef const Value& ConstReference;
deba@1752
   452
deba@1752
   453
    int size() const {
deba@1752
   454
      return (int)first.size();
deba@1752
   455
    }
deba@1752
   456
    
deba@1752
   457
    void set(const Key& key, const Value& value) {
deba@1752
   458
      unlace(key);
deba@1752
   459
      Parent::operator[](key).value = value;
deba@1752
   460
      lace(key);
deba@1752
   461
    }
deba@1752
   462
deba@1752
   463
    const Value& operator[](const Key& key) const {
deba@1752
   464
      return Parent::operator[](key).value;
deba@1752
   465
    }
deba@1752
   466
deba@1752
   467
    Reference operator[](const Key& key) {
deba@1752
   468
      return Reference(*this, key);
deba@1752
   469
    }
deba@1752
   470
deba@1752
   471
    class ItemIt : public _Item {
deba@1752
   472
    public:
deba@1752
   473
      typedef _Item Parent;
deba@1752
   474
deba@1752
   475
      ItemIt(Invalid) : Parent(INVALID), _map(0) {}
deba@1752
   476
deba@1752
   477
      ItemIt(const IterableIntMap& map, int value) : _map(&map) {
deba@1752
   478
	if (value < 0 || value >= (int)_map->first.size()) {	  
deba@1752
   479
	  Parent::operator=(INVALID);
deba@1752
   480
	} else {
deba@1752
   481
	  Parent::operator=(_map->first[value]);
deba@1752
   482
	}
deba@1752
   483
      } 
deba@1752
   484
deba@1752
   485
      ItemIt& operator++() {
deba@1752
   486
	Parent::operator=(_map->IterableIntMap::Parent::
deba@1752
   487
			  operator[](static_cast<Parent&>(*this)).next);
deba@1752
   488
	return *this;
deba@1752
   489
      }
deba@1752
   490
deba@1752
   491
deba@1752
   492
    private:
deba@1752
   493
      const IterableIntMap* _map;
deba@1752
   494
    };
deba@1752
   495
deba@1752
   496
  protected:
deba@1752
   497
    
deba@1752
   498
    virtual void erase(const Key& key) {
deba@1752
   499
      unlace(key);
deba@1752
   500
      Parent::erase(key);
deba@1752
   501
    }
deba@1752
   502
deba@1752
   503
    virtual void clear() {
deba@1752
   504
      first.clear();
deba@1752
   505
      Parent::clear();
deba@1752
   506
    }
deba@1752
   507
deba@1752
   508
  private:
deba@1752
   509
    std::vector<_Item> first;
deba@1752
   510
  };
deba@1752
   511
alpar@1677
   512
  /// @}
alpar@1677
   513
}