COIN-OR::LEMON - Graph Library

Changeset 1752:dce1f28ac595 in lemon-0.x for lemon/iterable_maps.h


Ignore:
Timestamp:
11/02/05 16:25:13 (14 years ago)
Author:
Balazs Dezso
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2281
Message:

IterableIntMap?

todo: documentation need

File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/iterable_maps.h

    r1685 r1752  
    1515 */
    1616
     17#include <lemon/traits.h>
     18#include <lemon/invalid.h>
    1719#include <vector>
    1820#include <limits>
     
    247249  };
    248250
     251
     252  namespace _iterable_maps_bits {
     253    template <typename Item>
     254    struct IterableIntMapNode {
     255      IterableIntMapNode() : value(-1) {}
     256      Item prev, next;
     257      int value;
     258    };
     259  }
     260
     261  ///\ingroup maps
     262  ///
     263  /// \brief Dynamic iterable integer map.
     264  ///
     265  /// \todo Document please
     266  template <typename _Graph, typename _Item>
     267  class IterableIntMap : protected ItemSetTraits<_Graph, _Item>
     268  ::template Map<_iterable_maps_bits::IterableIntMapNode<_Item> >::Parent {
     269  public:
     270    typedef typename ItemSetTraits<_Graph, _Item>
     271    ::template Map<_iterable_maps_bits::IterableIntMapNode<_Item> >
     272    ::Parent Parent;
     273
     274    typedef _Item Key;
     275    typedef int Value;
     276    typedef _Graph Graph;
     277
     278    IterableIntMap(const Graph& graph) : Parent(graph) {}
     279
     280  private:
     281   
     282    void unlace(const Key& key) {
     283      typename Parent::Value& node = Parent::operator[](key);
     284      if (node.value < 0) return;
     285      if (node.prev != INVALID) {
     286        Parent::operator[](node.prev).next = node.next;
     287      } else {
     288        first[node.value] = node.next;
     289      }
     290      if (node.next != INVALID) {
     291        Parent::operator[](node.next).prev = node.prev;
     292      }
     293      while (!first.empty() && first.back() == INVALID) {
     294        first.pop_back();
     295      }
     296    }
     297
     298    void lace(const Key& key) {
     299      typename Parent::Value& node = Parent::operator[](key);
     300      if (node.value < 0) return;
     301      if (node.value >= (int)first.size()) {
     302        first.resize(node.value + 1, INVALID);
     303      }
     304      node.prev = INVALID;
     305      node.next = first[node.value];
     306      if (node.next != INVALID) {
     307        Parent::operator[](node.next).prev = key;       
     308      }
     309      first[node.value] = key;
     310    }
     311
     312  public:
     313
     314    typedef True ReferenceMapTag;
     315
     316    class Reference {
     317      friend class IterableIntMap;
     318    private:
     319      Reference(IterableIntMap& map, const Key& key)
     320        : _key(key), _map(map) {}
     321    public:
     322
     323      Reference& operator=(const Reference& value) {
     324        _map.set(_key, (const int&)value);
     325        return *this;
     326      }
     327
     328      operator const int&() const {
     329        return static_cast<const IterableIntMap&>(_map)[_key];
     330      }
     331
     332      Reference& operator=(int value) {
     333        _map.set(_key, value);
     334        return *this;
     335      }
     336      Reference& operator+=(int value) {
     337        _map.set(_key, _map[_key] + value);
     338        return *this;
     339      }
     340      Reference& operator-=(int value) {
     341        _map.set(_key, _map[_key] - value);
     342        return *this;
     343      }
     344      Reference& operator*=(int value) {
     345        _map.set(_key, _map[_key] * value);
     346        return *this;
     347      }
     348      Reference& operator/=(int value) {
     349        _map.set(_key, _map[_key] / value);
     350        return *this;
     351      }
     352      Reference& operator%=(int value) {
     353        _map.set(_key, _map[_key] % value);
     354        return *this;
     355      }
     356      Reference& operator&=(int value) {
     357        _map.set(_key, _map[_key] & value);
     358        return *this;
     359      }
     360      Reference& operator|=(int value) {
     361        _map.set(_key, _map[_key] | value);
     362        return *this;
     363      }
     364      Reference& operator^=(int value) {
     365        _map.set(_key, _map[_key] ^ value);
     366        return *this;
     367      }
     368      Reference& operator<<=(int value) {
     369        _map.set(_key, _map[_key] << value);
     370        return *this;
     371      }
     372      Reference& operator>>=(int value) {
     373        _map.set(_key, _map[_key] >> value);
     374        return *this;
     375      }
     376
     377    private:
     378      Key _key;
     379      IterableIntMap& _map;
     380    };
     381   
     382    typedef const Value& ConstReference;
     383
     384    int size() const {
     385      return (int)first.size();
     386    }
     387   
     388    void set(const Key& key, const Value& value) {
     389      unlace(key);
     390      Parent::operator[](key).value = value;
     391      lace(key);
     392    }
     393
     394    const Value& operator[](const Key& key) const {
     395      return Parent::operator[](key).value;
     396    }
     397
     398    Reference operator[](const Key& key) {
     399      return Reference(*this, key);
     400    }
     401
     402    class ItemIt : public _Item {
     403    public:
     404      typedef _Item Parent;
     405
     406      ItemIt(Invalid) : Parent(INVALID), _map(0) {}
     407
     408      ItemIt(const IterableIntMap& map, int value) : _map(&map) {
     409        if (value < 0 || value >= (int)_map->first.size()) {     
     410          Parent::operator=(INVALID);
     411        } else {
     412          Parent::operator=(_map->first[value]);
     413        }
     414      }
     415
     416      ItemIt& operator++() {
     417        Parent::operator=(_map->IterableIntMap::Parent::
     418                          operator[](static_cast<Parent&>(*this)).next);
     419        return *this;
     420      }
     421
     422
     423    private:
     424      const IterableIntMap* _map;
     425    };
     426
     427  protected:
     428   
     429    virtual void erase(const Key& key) {
     430      unlace(key);
     431      Parent::erase(key);
     432    }
     433
     434    virtual void clear() {
     435      first.clear();
     436      Parent::clear();
     437    }
     438
     439  private:
     440    std::vector<_Item> first;
     441  };
     442
    249443  /// @}
    250444}
Note: See TracChangeset for help on using the changeset viewer.