lemon/bits/array_map.h
author Balazs Dezso <deba@inf.elte.hu>
Sun, 21 Dec 2008 20:45:25 +0100
changeset 438 81d40f1c850c
parent 263 be8a861d3bb7
child 361 f58410582b9b
permissions -rw-r--r--
Bug fix in heap unionfind (ticket #197)

The previous bugfix set the minimum value in internal nodes
wrongly. It corrects the problem.
     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-2008
     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 what
    40   // automatically updates the map when a key is added to or erased from
    41   // the map. This map uses the allocators to implement
    42   // the container functionality.
    43   //
    44   // The template parameters are the Graph the current Item type and
    45   // the Value type of the map.
    46   template <typename _Graph, typename _Item, typename _Value>
    47   class ArrayMap
    48     : public ItemSetTraits<_Graph, _Item>::ItemNotifier::ObserverBase {
    49   public:
    50     // The graph type of the maps.
    51     typedef _Graph Graph;
    52     // The item type of the map.
    53     typedef _Item Item;
    54     // The reference map tag.
    55     typedef True ReferenceMapTag;
    56 
    57     // The key type of the maps.
    58     typedef _Item Key;
    59     // The value type of the map.
    60     typedef _Value Value;
    61 
    62     // The const reference type of the map.
    63     typedef const _Value& ConstReference;
    64     // The reference type of the map.
    65     typedef _Value& Reference;
    66 
    67     // The notifier type.
    68     typedef typename ItemSetTraits<_Graph, _Item>::ItemNotifier Notifier;
    69 
    70     // The MapBase of the Map which imlements the core regisitry function.
    71     typedef typename Notifier::ObserverBase Parent;
    72 
    73   private:
    74     typedef std::allocator<Value> Allocator;
    75 
    76   public:
    77 
    78     // \brief Graph initialized map constructor.
    79     //
    80     // Graph initialized map constructor.
    81     explicit ArrayMap(const Graph& graph) {
    82       Parent::attach(graph.notifier(Item()));
    83       allocate_memory();
    84       Notifier* nf = Parent::notifier();
    85       Item it;
    86       for (nf->first(it); it != INVALID; nf->next(it)) {
    87         int id = nf->id(it);;
    88         allocator.construct(&(values[id]), Value());
    89       }
    90     }
    91 
    92     // \brief Constructor to use default value to initialize the map.
    93     //
    94     // It constructs a map and initialize all of the the map.
    95     ArrayMap(const Graph& graph, const Value& value) {
    96       Parent::attach(graph.notifier(Item()));
    97       allocate_memory();
    98       Notifier* nf = Parent::notifier();
    99       Item it;
   100       for (nf->first(it); it != INVALID; nf->next(it)) {
   101         int id = nf->id(it);;
   102         allocator.construct(&(values[id]), value);
   103       }
   104     }
   105 
   106   private:
   107     // \brief Constructor to copy a map of the same map type.
   108     //
   109     // Constructor to copy a map of the same map type.
   110     ArrayMap(const ArrayMap& copy) : Parent() {
   111       if (copy.attached()) {
   112         attach(*copy.notifier());
   113       }
   114       capacity = copy.capacity;
   115       if (capacity == 0) return;
   116       values = allocator.allocate(capacity);
   117       Notifier* nf = Parent::notifier();
   118       Item it;
   119       for (nf->first(it); it != INVALID; nf->next(it)) {
   120         int id = nf->id(it);;
   121         allocator.construct(&(values[id]), copy.values[id]);
   122       }
   123     }
   124 
   125     // \brief Assign operator.
   126     //
   127     // This operator assigns for each item in the map the
   128     // value mapped to the same item in the copied map.
   129     // The parameter map should be indiced with the same
   130     // itemset because this assign operator does not change
   131     // the container of the map.
   132     ArrayMap& operator=(const ArrayMap& cmap) {
   133       return operator=<ArrayMap>(cmap);
   134     }
   135 
   136 
   137     // \brief Template assign operator.
   138     //
   139     // The given parameter should be conform to the ReadMap
   140     // concecpt and could be indiced by the current item set of
   141     // the NodeMap. In this case the value for each item
   142     // is assigned by the value of the given ReadMap.
   143     template <typename CMap>
   144     ArrayMap& operator=(const CMap& cmap) {
   145       checkConcept<concepts::ReadMap<Key, _Value>, CMap>();
   146       const typename Parent::Notifier* nf = Parent::notifier();
   147       Item it;
   148       for (nf->first(it); it != INVALID; nf->next(it)) {
   149         set(it, cmap[it]);
   150       }
   151       return *this;
   152     }
   153 
   154   public:
   155     // \brief The destructor of the map.
   156     //
   157     // The destructor of the map.
   158     virtual ~ArrayMap() {
   159       if (attached()) {
   160         clear();
   161         detach();
   162       }
   163     }
   164 
   165   protected:
   166 
   167     using Parent::attach;
   168     using Parent::detach;
   169     using Parent::attached;
   170 
   171   public:
   172 
   173     // \brief The subscript operator.
   174     //
   175     // The subscript operator. The map can be subscripted by the
   176     // actual keys of the graph.
   177     Value& operator[](const Key& key) {
   178       int id = Parent::notifier()->id(key);
   179       return values[id];
   180     }
   181 
   182     // \brief The const subscript operator.
   183     //
   184     // The const subscript operator. The map can be subscripted by the
   185     // actual keys of the graph.
   186     const Value& operator[](const Key& key) const {
   187       int id = Parent::notifier()->id(key);
   188       return values[id];
   189     }
   190 
   191     // \brief Setter function of the map.
   192     //
   193     // Setter function of the map. Equivalent with map[key] = val.
   194     // This is a compatibility feature with the not dereferable maps.
   195     void set(const Key& key, const Value& val) {
   196       (*this)[key] = val;
   197     }
   198 
   199   protected:
   200 
   201     // \brief Adds a new key to the map.
   202     //
   203     // It adds a new key to the map. It called by the observer notifier
   204     // and it overrides the add() member function of the observer base.
   205     virtual void add(const Key& key) {
   206       Notifier* nf = Parent::notifier();
   207       int id = nf->id(key);
   208       if (id >= capacity) {
   209         int new_capacity = (capacity == 0 ? 1 : capacity);
   210         while (new_capacity <= id) {
   211           new_capacity <<= 1;
   212         }
   213         Value* new_values = allocator.allocate(new_capacity);
   214         Item it;
   215         for (nf->first(it); it != INVALID; nf->next(it)) {
   216           int jd = nf->id(it);;
   217           if (id != jd) {
   218             allocator.construct(&(new_values[jd]), values[jd]);
   219             allocator.destroy(&(values[jd]));
   220           }
   221         }
   222         if (capacity != 0) allocator.deallocate(values, capacity);
   223         values = new_values;
   224         capacity = new_capacity;
   225       }
   226       allocator.construct(&(values[id]), Value());
   227     }
   228 
   229     // \brief Adds more new keys to the map.
   230     //
   231     // It adds more new keys to the map. It called by the observer notifier
   232     // and it overrides the add() member function of the observer base.
   233     virtual void add(const std::vector<Key>& keys) {
   234       Notifier* nf = Parent::notifier();
   235       int max_id = -1;
   236       for (int i = 0; i < int(keys.size()); ++i) {
   237         int id = nf->id(keys[i]);
   238         if (id > max_id) {
   239           max_id = id;
   240         }
   241       }
   242       if (max_id >= capacity) {
   243         int new_capacity = (capacity == 0 ? 1 : capacity);
   244         while (new_capacity <= max_id) {
   245           new_capacity <<= 1;
   246         }
   247         Value* new_values = allocator.allocate(new_capacity);
   248         Item it;
   249         for (nf->first(it); it != INVALID; nf->next(it)) {
   250           int id = nf->id(it);
   251           bool found = false;
   252           for (int i = 0; i < int(keys.size()); ++i) {
   253             int jd = nf->id(keys[i]);
   254             if (id == jd) {
   255               found = true;
   256               break;
   257             }
   258           }
   259           if (found) continue;
   260           allocator.construct(&(new_values[id]), values[id]);
   261           allocator.destroy(&(values[id]));
   262         }
   263         if (capacity != 0) allocator.deallocate(values, capacity);
   264         values = new_values;
   265         capacity = new_capacity;
   266       }
   267       for (int i = 0; i < int(keys.size()); ++i) {
   268         int id = nf->id(keys[i]);
   269         allocator.construct(&(values[id]), Value());
   270       }
   271     }
   272 
   273     // \brief Erase a key from the map.
   274     //
   275     // Erase a key from the map. It called by the observer notifier
   276     // and it overrides the erase() member function of the observer base.
   277     virtual void erase(const Key& key) {
   278       int id = Parent::notifier()->id(key);
   279       allocator.destroy(&(values[id]));
   280     }
   281 
   282     // \brief Erase more keys from the map.
   283     //
   284     // Erase more keys from the map. It called by the observer notifier
   285     // and it overrides the erase() member function of the observer base.
   286     virtual void erase(const std::vector<Key>& keys) {
   287       for (int i = 0; i < int(keys.size()); ++i) {
   288         int id = Parent::notifier()->id(keys[i]);
   289         allocator.destroy(&(values[id]));
   290       }
   291     }
   292 
   293     // \brief Buildes the map.
   294     //
   295     // It buildes the map. It called by the observer notifier
   296     // and it overrides the build() member function of the observer base.
   297     virtual void build() {
   298       Notifier* nf = Parent::notifier();
   299       allocate_memory();
   300       Item it;
   301       for (nf->first(it); it != INVALID; nf->next(it)) {
   302         int id = nf->id(it);;
   303         allocator.construct(&(values[id]), Value());
   304       }
   305     }
   306 
   307     // \brief Clear the map.
   308     //
   309     // It erase all items from the map. It called by the observer notifier
   310     // and it overrides the clear() member function of the observer base.
   311     virtual void clear() {
   312       Notifier* nf = Parent::notifier();
   313       if (capacity != 0) {
   314         Item it;
   315         for (nf->first(it); it != INVALID; nf->next(it)) {
   316           int id = nf->id(it);
   317           allocator.destroy(&(values[id]));
   318         }
   319         allocator.deallocate(values, capacity);
   320         capacity = 0;
   321       }
   322     }
   323 
   324   private:
   325 
   326     void allocate_memory() {
   327       int max_id = Parent::notifier()->maxId();
   328       if (max_id == -1) {
   329         capacity = 0;
   330         values = 0;
   331         return;
   332       }
   333       capacity = 1;
   334       while (capacity <= max_id) {
   335         capacity <<= 1;
   336       }
   337       values = allocator.allocate(capacity);
   338     }
   339 
   340     int capacity;
   341     Value* values;
   342     Allocator allocator;
   343 
   344   };
   345 
   346 }
   347 
   348 #endif