lemon/bits/array_map.h
author Peter Kovacs <kpeter@inf.elte.hu>
Wed, 15 Apr 2009 12:01:14 +0200
changeset 590 b61354458b59
parent 440 88ed40ad0d4f
child 617 4137ef9aacc6
permissions -rw-r--r--
Imporvements for the matching algorithms (#264)
     1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
     2  *
     3  * This file is a part of LEMON, a generic C++ optimization library.
     4  *
     5  * Copyright (C) 2003-2009
     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     8  *
     9  * Permission to use, modify and distribute this software is granted
    10  * provided that this copyright notice appears in all copies. For
    11  * precise terms see the accompanying LICENSE file.
    12  *
    13  * This software is provided "AS IS" with no warranty of any kind,
    14  * express or implied, and with no claim as to its suitability for any
    15  * purpose.
    16  *
    17  */
    18 
    19 #ifndef LEMON_BITS_ARRAY_MAP_H
    20 #define LEMON_BITS_ARRAY_MAP_H
    21 
    22 #include <memory>
    23 
    24 #include <lemon/bits/traits.h>
    25 #include <lemon/bits/alteration_notifier.h>
    26 #include <lemon/concept_check.h>
    27 #include <lemon/concepts/maps.h>
    28 
    29 // \ingroup graphbits
    30 // \file
    31 // \brief Graph map based on the array storage.
    32 
    33 namespace lemon {
    34 
    35   // \ingroup graphbits
    36   //
    37   // \brief Graph map based on the array storage.
    38   //
    39   // The ArrayMap template class is graph map structure that automatically
    40   // updates the map when a key is added to or erased from the graph.
    41   // This map uses the allocators to implement the container functionality.
    42   //
    43   // The template parameters are the Graph, the current Item type and
    44   // the Value type of the map.
    45   template <typename _Graph, typename _Item, typename _Value>
    46   class ArrayMap
    47     : public ItemSetTraits<_Graph, _Item>::ItemNotifier::ObserverBase {
    48   public:
    49     // The graph type.
    50     typedef _Graph Graph;
    51     // The item type.
    52     typedef _Item Item;
    53     // The reference map tag.
    54     typedef True ReferenceMapTag;
    55 
    56     // The key type of the map.
    57     typedef _Item Key;
    58     // The value type of the map.
    59     typedef _Value Value;
    60 
    61     // The const reference type of the map.
    62     typedef const _Value& ConstReference;
    63     // The reference type of the map.
    64     typedef _Value& Reference;
    65 
    66     // The notifier type.
    67     typedef typename ItemSetTraits<_Graph, _Item>::ItemNotifier Notifier;
    68 
    69     // The MapBase of the Map which imlements the core regisitry function.
    70     typedef typename Notifier::ObserverBase Parent;
    71 
    72   private:
    73     typedef std::allocator<Value> Allocator;
    74 
    75   public:
    76 
    77     // \brief Graph initialized map constructor.
    78     //
    79     // Graph initialized map constructor.
    80     explicit ArrayMap(const Graph& graph) {
    81       Parent::attach(graph.notifier(Item()));
    82       allocate_memory();
    83       Notifier* nf = Parent::notifier();
    84       Item it;
    85       for (nf->first(it); it != INVALID; nf->next(it)) {
    86         int id = nf->id(it);;
    87         allocator.construct(&(values[id]), Value());
    88       }
    89     }
    90 
    91     // \brief Constructor to use default value to initialize the map.
    92     //
    93     // It constructs a map and initialize all of the the map.
    94     ArrayMap(const Graph& graph, const Value& value) {
    95       Parent::attach(graph.notifier(Item()));
    96       allocate_memory();
    97       Notifier* nf = Parent::notifier();
    98       Item it;
    99       for (nf->first(it); it != INVALID; nf->next(it)) {
   100         int id = nf->id(it);;
   101         allocator.construct(&(values[id]), value);
   102       }
   103     }
   104 
   105   private:
   106     // \brief Constructor to copy a map of the same map type.
   107     //
   108     // Constructor to copy a map of the same map type.
   109     ArrayMap(const ArrayMap& copy) : Parent() {
   110       if (copy.attached()) {
   111         attach(*copy.notifier());
   112       }
   113       capacity = copy.capacity;
   114       if (capacity == 0) return;
   115       values = allocator.allocate(capacity);
   116       Notifier* nf = Parent::notifier();
   117       Item it;
   118       for (nf->first(it); it != INVALID; nf->next(it)) {
   119         int id = nf->id(it);;
   120         allocator.construct(&(values[id]), copy.values[id]);
   121       }
   122     }
   123 
   124     // \brief Assign operator.
   125     //
   126     // This operator assigns for each item in the map the
   127     // value mapped to the same item in the copied map.
   128     // The parameter map should be indiced with the same
   129     // itemset because this assign operator does not change
   130     // the container of the map.
   131     ArrayMap& operator=(const ArrayMap& cmap) {
   132       return operator=<ArrayMap>(cmap);
   133     }
   134 
   135 
   136     // \brief Template assign operator.
   137     //
   138     // The given parameter should conform to the ReadMap
   139     // concecpt and could be indiced by the current item set of
   140     // the NodeMap. In this case the value for each item
   141     // is assigned by the value of the given ReadMap.
   142     template <typename CMap>
   143     ArrayMap& operator=(const CMap& cmap) {
   144       checkConcept<concepts::ReadMap<Key, _Value>, CMap>();
   145       const typename Parent::Notifier* nf = Parent::notifier();
   146       Item it;
   147       for (nf->first(it); it != INVALID; nf->next(it)) {
   148         set(it, cmap[it]);
   149       }
   150       return *this;
   151     }
   152 
   153   public:
   154     // \brief The destructor of the map.
   155     //
   156     // The destructor of the map.
   157     virtual ~ArrayMap() {
   158       if (attached()) {
   159         clear();
   160         detach();
   161       }
   162     }
   163 
   164   protected:
   165 
   166     using Parent::attach;
   167     using Parent::detach;
   168     using Parent::attached;
   169 
   170   public:
   171 
   172     // \brief The subscript operator.
   173     //
   174     // The subscript operator. The map can be subscripted by the
   175     // actual keys of the graph.
   176     Value& operator[](const Key& key) {
   177       int id = Parent::notifier()->id(key);
   178       return values[id];
   179     }
   180 
   181     // \brief The const subscript operator.
   182     //
   183     // The const subscript operator. The map can be subscripted by the
   184     // actual keys of the graph.
   185     const Value& operator[](const Key& key) const {
   186       int id = Parent::notifier()->id(key);
   187       return values[id];
   188     }
   189 
   190     // \brief Setter function of the map.
   191     //
   192     // Setter function of the map. Equivalent with map[key] = val.
   193     // This is a compatibility feature with the not dereferable maps.
   194     void set(const Key& key, const Value& val) {
   195       (*this)[key] = val;
   196     }
   197 
   198   protected:
   199 
   200     // \brief Adds a new key to the map.
   201     //
   202     // It adds a new key to the map. It is called by the observer notifier
   203     // and it overrides the add() member function of the observer base.
   204     virtual void add(const Key& key) {
   205       Notifier* nf = Parent::notifier();
   206       int id = nf->id(key);
   207       if (id >= capacity) {
   208         int new_capacity = (capacity == 0 ? 1 : capacity);
   209         while (new_capacity <= id) {
   210           new_capacity <<= 1;
   211         }
   212         Value* new_values = allocator.allocate(new_capacity);
   213         Item it;
   214         for (nf->first(it); it != INVALID; nf->next(it)) {
   215           int jd = nf->id(it);;
   216           if (id != jd) {
   217             allocator.construct(&(new_values[jd]), values[jd]);
   218             allocator.destroy(&(values[jd]));
   219           }
   220         }
   221         if (capacity != 0) allocator.deallocate(values, capacity);
   222         values = new_values;
   223         capacity = new_capacity;
   224       }
   225       allocator.construct(&(values[id]), Value());
   226     }
   227 
   228     // \brief Adds more new keys to the map.
   229     //
   230     // It adds more new keys to the map. It is called by the observer notifier
   231     // and it overrides the add() member function of the observer base.
   232     virtual void add(const std::vector<Key>& keys) {
   233       Notifier* nf = Parent::notifier();
   234       int max_id = -1;
   235       for (int i = 0; i < int(keys.size()); ++i) {
   236         int id = nf->id(keys[i]);
   237         if (id > max_id) {
   238           max_id = id;
   239         }
   240       }
   241       if (max_id >= capacity) {
   242         int new_capacity = (capacity == 0 ? 1 : capacity);
   243         while (new_capacity <= max_id) {
   244           new_capacity <<= 1;
   245         }
   246         Value* new_values = allocator.allocate(new_capacity);
   247         Item it;
   248         for (nf->first(it); it != INVALID; nf->next(it)) {
   249           int id = nf->id(it);
   250           bool found = false;
   251           for (int i = 0; i < int(keys.size()); ++i) {
   252             int jd = nf->id(keys[i]);
   253             if (id == jd) {
   254               found = true;
   255               break;
   256             }
   257           }
   258           if (found) continue;
   259           allocator.construct(&(new_values[id]), values[id]);
   260           allocator.destroy(&(values[id]));
   261         }
   262         if (capacity != 0) allocator.deallocate(values, capacity);
   263         values = new_values;
   264         capacity = new_capacity;
   265       }
   266       for (int i = 0; i < int(keys.size()); ++i) {
   267         int id = nf->id(keys[i]);
   268         allocator.construct(&(values[id]), Value());
   269       }
   270     }
   271 
   272     // \brief Erase a key from the map.
   273     //
   274     // Erase a key from the map. It is called by the observer notifier
   275     // and it overrides the erase() member function of the observer base.
   276     virtual void erase(const Key& key) {
   277       int id = Parent::notifier()->id(key);
   278       allocator.destroy(&(values[id]));
   279     }
   280 
   281     // \brief Erase more keys from the map.
   282     //
   283     // Erase more keys from the map. It is called by the observer notifier
   284     // and it overrides the erase() member function of the observer base.
   285     virtual void erase(const std::vector<Key>& keys) {
   286       for (int i = 0; i < int(keys.size()); ++i) {
   287         int id = Parent::notifier()->id(keys[i]);
   288         allocator.destroy(&(values[id]));
   289       }
   290     }
   291 
   292     // \brief Builds the map.
   293     //
   294     // It builds the map. It is called by the observer notifier
   295     // and it overrides the build() member function of the observer base.
   296     virtual void build() {
   297       Notifier* nf = Parent::notifier();
   298       allocate_memory();
   299       Item it;
   300       for (nf->first(it); it != INVALID; nf->next(it)) {
   301         int id = nf->id(it);;
   302         allocator.construct(&(values[id]), Value());
   303       }
   304     }
   305 
   306     // \brief Clear the map.
   307     //
   308     // It erase all items from the map. It is called by the observer notifier
   309     // and it overrides the clear() member function of the observer base.
   310     virtual void clear() {
   311       Notifier* nf = Parent::notifier();
   312       if (capacity != 0) {
   313         Item it;
   314         for (nf->first(it); it != INVALID; nf->next(it)) {
   315           int id = nf->id(it);
   316           allocator.destroy(&(values[id]));
   317         }
   318         allocator.deallocate(values, capacity);
   319         capacity = 0;
   320       }
   321     }
   322 
   323   private:
   324 
   325     void allocate_memory() {
   326       int max_id = Parent::notifier()->maxId();
   327       if (max_id == -1) {
   328         capacity = 0;
   329         values = 0;
   330         return;
   331       }
   332       capacity = 1;
   333       while (capacity <= max_id) {
   334         capacity <<= 1;
   335       }
   336       values = allocator.allocate(capacity);
   337     }
   338 
   339     int capacity;
   340     Value* values;
   341     Allocator allocator;
   342 
   343   };
   344 
   345 }
   346 
   347 #endif