COIN-OR::LEMON - Graph Library

Changeset 1999:2ff283124dfc in lemon-0.x for lemon/bits/array_map.h


Ignore:
Timestamp:
03/06/06 11:28:37 (14 years ago)
Author:
Balazs Dezso
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2609
Message:

Clarifing alteration observing system
It is directly connected now to a container

File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/bits/array_map.h

    r1996 r1999  
    2121
    2222#include <memory>
    23 #include <lemon/bits/map_extender.h>
     23
     24#include <lemon/bits/traits.h>
    2425#include <lemon/bits/alteration_notifier.h>
    25 #include <lemon/concept_check.h>
    26 #include <lemon/concept/maps.h>
    2726
    2827/// \ingroup graphbits
    2928/// \file
    30 /// \brief Graph maps that construct and destruct
    31 /// their elements dynamically.
     29/// \brief Graph map based on the array storage.
    3230
    3331namespace lemon {
     
    3836  ///
    3937  /// The ArrayMap template class is graph map structure what
    40   /// automatically indates the map when a key is added to or erased from
     38  /// automatically updates the map when a key is added to or erased from
    4139  /// the map. This map uses the allocators to implement
    4240  /// the container functionality.
    4341  ///
    44   /// The template parameter is the AlterationNotifier that the maps
    45   /// will belong to and the Value.
    46 
    47   template <typename _Graph,
    48             typename _Item,
    49             typename _Value>
    50   class ArrayMap : public AlterationNotifier<_Item>::ObserverBase {
    51 
    52     typedef _Item Item;
     42  /// The template parameter is the Graph the current Item type and
     43  /// the Value type of the map.
     44  template <typename _Graph, typename _Item, typename _Value>
     45  class ArrayMap
     46    : public ItemSetTraits<_Graph, _Item>::ItemNotifier::ObserverBase {
    5347  public:
    5448    /// The graph type of the maps.
    5549    typedef _Graph Graph;
     50    /// The item type of the map.
     51    typedef _Item Item;
    5652    /// The reference map tag.
    5753    typedef True ReferenceMapTag;
     
    6157    /// The value type of the map.
    6258    typedef _Value Value;
     59
    6360    /// The const reference type of the map.
    6461    typedef const _Value& ConstReference;
     
    6663    typedef _Value& Reference;
    6764
    68     typedef const Value ConstValue;
    69     typedef Value* Pointer;
    70     typedef const Value* ConstPointer;
    71 
    72     typedef AlterationNotifier<_Item> Registry;
     65    /// The notifier type.
     66    typedef typename ItemSetTraits<_Graph, _Item>::ItemNotifier Notifier;
    7367
    7468    /// The MapBase of the Map which imlements the core regisitry function.
    75     typedef typename Registry::ObserverBase Parent;
     69    typedef typename Notifier::ObserverBase Parent;
    7670               
    77 
    78 
    7971  private:
    8072    typedef std::allocator<Value> Allocator;
    8173
    82 
    8374  public:
    8475
     
    8677    ///
    8778    /// Graph initialized map constructor.
    88     ArrayMap(const Graph& _g) : graph(&_g) {
     79    ArrayMap(const Graph& graph) {
     80      Parent::attach(graph.getNotifier(Item()));
     81      allocate_memory();
     82      Notifier* notifier = Parent::getNotifier();
    8983      Item it;
    90       attach(_g.getNotifier(Item()));
    91       allocate_memory();
    92       for (graph->first(it); it != INVALID; graph->next(it)) {
    93         int id = graph->id(it);;
     84      for (notifier->first(it); it != INVALID; notifier->next(it)) {
     85        int id = notifier->id(it);;
    9486        allocator.construct(&(values[id]), Value());
    9587      }                                                         
     
    9991    ///
    10092    /// It constructs a map and initialize all of the the map.
    101     ArrayMap(const Graph& _g, const Value& _v) : graph(&_g) {
     93    ArrayMap(const Graph& graph, const Value& value) {
     94      Parent::attach(graph.getNotifier(Item()));
     95      allocate_memory();
     96      Notifier* notifier = Parent::getNotifier();
    10297      Item it;
    103       attach(_g.getNotifier(_Item()));
    104       allocate_memory();
    105       for (graph->first(it); it != INVALID; graph->next(it)) {
    106         int id = graph->id(it);;
    107         allocator.construct(&(values[id]), _v);
     98      for (notifier->first(it); it != INVALID; notifier->next(it)) {
     99        int id = notifier->id(it);;
     100        allocator.construct(&(values[id]), value);
    108101      }                                                         
    109102    }
     
    112105    ///
    113106    /// Constructor to copy a map of the same map type.     
    114     ArrayMap(const ArrayMap& copy) : Parent(), graph(copy.graph) {
     107    ArrayMap(const ArrayMap& copy) : Parent() {
    115108      if (copy.attached()) {
    116         attach(*copy.getRegistry());
     109        attach(*copy.getNotifier());
    117110      }
    118111      capacity = copy.capacity;
    119112      if (capacity == 0) return;
    120113      values = allocator.allocate(capacity);
     114      Notifier* notifier = Parent::getNotifier();
    121115      Item it;
    122       for (graph->first(it); it != INVALID; graph->next(it)) {
    123         int id = graph->id(it);;
     116      for (notifier->first(it); it != INVALID; notifier->next(it)) {
     117        int id = notifier->id(it);;
    124118        allocator.construct(&(values[id]), copy.values[id]);
    125119      }
     
    146140    using Parent::attached;
    147141
    148     const Graph* getGraph() {
    149       return graph;
    150     }
    151 
    152 
    153142  public:
    154143
     
    158147    /// actual keys of the graph.
    159148    Value& operator[](const Key& key) {
    160       int id = graph->id(key);
     149      int id = Parent::getNotifier()->id(key);
    161150      return values[id];
    162151    }
     
    167156    /// actual keys of the graph.
    168157    const Value& operator[](const Key& key) const {
    169       int id = graph->id(key);
     158      int id = Parent::getNotifier()->id(key);
    170159      return values[id];
    171160    }
     
    181170  protected:
    182171
    183     /// Add a new key to the map. It called by the map registry.
    184          
     172    /// \brief Adds a new key to the map.
     173    ///         
     174    /// It adds a new key to the map. It called by the observer notifier
     175    /// and it overrides the add() member function of the observer base.     
    185176    virtual void add(const Key& key) {
    186       int id = graph->id(key);
     177      Notifier* notifier = Parent::getNotifier();
     178      int id = notifier->id(key);
    187179      if (id >= capacity) {
    188180        int new_capacity = (capacity == 0 ? 1 : capacity);
     
    192184        Value* new_values = allocator.allocate(new_capacity);
    193185        Item it;
    194         for (graph->first(it); it != INVALID; graph->next(it)) {
    195           int jd = graph->id(it);;
     186        for (notifier->first(it); it != INVALID; notifier->next(it)) {
     187          int jd = notifier->id(it);;
    196188          if (id != jd) {
    197189            allocator.construct(&(new_values[jd]), values[jd]);
     
    206198    }
    207199
     200    /// \brief Adds more new keys to the map.
     201    ///         
     202    /// It adds more new keys to the map. It called by the observer notifier
     203    /// and it overrides the add() member function of the observer base.     
    208204    virtual void add(const std::vector<Key>& keys) {
     205      Notifier* notifier = Parent::getNotifier();
    209206      int max_id = -1;
    210207      for (int i = 0; i < (int)keys.size(); ++i) {
    211         int id = graph->id(keys[i]);
     208        int id = notifier->id(keys[i]);
    212209        if (id > max_id) {
    213210          max_id = id;
     
    221218        Value* new_values = allocator.allocate(new_capacity);
    222219        Item it;
    223         for (graph->first(it); it != INVALID; graph->next(it)) {
    224           int id = graph->id(it);
     220        for (notifier->first(it); it != INVALID; notifier->next(it)) {
     221          int id = notifier->id(it);
    225222          bool found = false;
    226223          for (int i = 0; i < (int)keys.size(); ++i) {
    227             int jd = graph->id(keys[i]);
     224            int jd = notifier->id(keys[i]);
    228225            if (id == jd) {
    229226              found = true;
     
    240237      }
    241238      for (int i = 0; i < (int)keys.size(); ++i) {
    242         int id = graph->id(keys[i]);
     239        int id = notifier->id(keys[i]);
    243240        allocator.construct(&(values[id]), Value());
    244241      }
    245242    }
    246243               
    247     /// Erase a key from the map. It called by the map registry.
    248      
     244    /// \brief Erase a key from the map.
     245    ///
     246    /// Erase a key from the map. It called by the observer notifier
     247    /// and it overrides the erase() member function of the observer base.     
    249248    virtual void erase(const Key& key) {
    250       int id = graph->id(key);
     249      int id = Parent::getNotifier()->id(key);
    251250      allocator.destroy(&(values[id]));
    252251    }
    253252
     253    /// \brief Erase more keys from the map.
     254    ///
     255    /// Erase more keys from the map. It called by the observer notifier
     256    /// and it overrides the erase() member function of the observer base.     
    254257    virtual void erase(const std::vector<Key>& keys) {
    255258      for (int i = 0; i < (int)keys.size(); ++i) {
    256         int id = graph->id(keys[i]);
     259        int id = Parent::getNotifier()->id(keys[i]);
    257260        allocator.destroy(&(values[id]));
    258261      }
    259262    }
    260263
     264    /// \brief Buildes the map.
     265    ///
     266    /// It buildes the map. It called by the observer notifier
     267    /// and it overrides the build() member function of the observer base.
    261268    virtual void build() {
     269      Notifier* notifier = Parent::getNotifier();
    262270      allocate_memory();
    263271      Item it;
    264       for (graph->first(it); it != INVALID; graph->next(it)) {
    265         int id = graph->id(it);;
     272      for (notifier->first(it); it != INVALID; notifier->next(it)) {
     273        int id = notifier->id(it);;
    266274        allocator.construct(&(values[id]), Value());
    267275      }                                                         
    268276    }
    269277
     278    /// \brief Clear the map.
     279    ///
     280    /// It erase all items from the map. It called by the observer notifier
     281    /// and it overrides the clear() member function of the observer base.     
    270282    virtual void clear() {     
     283      Notifier* notifier = Parent::getNotifier();
    271284      if (capacity != 0) {
    272285        Item it;
    273         for (graph->first(it); it != INVALID; graph->next(it)) {
    274           int id = graph->id(it);
     286        for (notifier->first(it); it != INVALID; notifier->next(it)) {
     287          int id = notifier->id(it);
    275288          allocator.destroy(&(values[id]));
    276289        }                                                               
     
    283296     
    284297    void allocate_memory() {
    285       int max_id = graph->maxId(_Item());
     298      int max_id = Parent::getNotifier()->maxId();
    286299      if (max_id == -1) {
    287300        capacity = 0;
     
    296309    }     
    297310
    298     const Graph* graph;
    299311    int capacity;
    300312    Value* values;
Note: See TracChangeset for help on using the changeset viewer.