lemon/bits/array_map.h
changeset 330 5ba887b7def4
parent 263 be8a861d3bb7
child 361 f58410582b9b
equal deleted inserted replaced
3:68a69d1b2f60 4:e72a6a97b382
    24 #include <lemon/bits/traits.h>
    24 #include <lemon/bits/traits.h>
    25 #include <lemon/bits/alteration_notifier.h>
    25 #include <lemon/bits/alteration_notifier.h>
    26 #include <lemon/concept_check.h>
    26 #include <lemon/concept_check.h>
    27 #include <lemon/concepts/maps.h>
    27 #include <lemon/concepts/maps.h>
    28 
    28 
    29 /// \ingroup graphbits
    29 // \ingroup graphbits
    30 /// \file
    30 // \file
    31 /// \brief Graph map based on the array storage.
    31 // \brief Graph map based on the array storage.
    32 
    32 
    33 namespace lemon {
    33 namespace lemon {
    34 
    34 
    35   /// \ingroup graphbits
    35   // \ingroup graphbits
    36   ///
    36   //
    37   /// \brief Graph map based on the array storage.
    37   // \brief Graph map based on the array storage.
    38   ///
    38   //
    39   /// The ArrayMap template class is graph map structure what
    39   // The ArrayMap template class is graph map structure what
    40   /// automatically updates the map when a key is added to or erased from
    40   // automatically updates the map when a key is added to or erased from
    41   /// the map. This map uses the allocators to implement
    41   // the map. This map uses the allocators to implement
    42   /// the container functionality.
    42   // the container functionality.
    43   ///
    43   //
    44   /// The template parameters are the Graph the current Item type and
    44   // The template parameters are the Graph the current Item type and
    45   /// the Value type of the map.
    45   // the Value type of the map.
    46   template <typename _Graph, typename _Item, typename _Value>
    46   template <typename _Graph, typename _Item, typename _Value>
    47   class ArrayMap
    47   class ArrayMap
    48     : public ItemSetTraits<_Graph, _Item>::ItemNotifier::ObserverBase {
    48     : public ItemSetTraits<_Graph, _Item>::ItemNotifier::ObserverBase {
    49   public:
    49   public:
    50     /// The graph type of the maps.
    50     // The graph type of the maps.
    51     typedef _Graph Graph;
    51     typedef _Graph Graph;
    52     /// The item type of the map.
    52     // The item type of the map.
    53     typedef _Item Item;
    53     typedef _Item Item;
    54     /// The reference map tag.
    54     // The reference map tag.
    55     typedef True ReferenceMapTag;
    55     typedef True ReferenceMapTag;
    56 
    56 
    57     /// The key type of the maps.
    57     // The key type of the maps.
    58     typedef _Item Key;
    58     typedef _Item Key;
    59     /// The value type of the map.
    59     // The value type of the map.
    60     typedef _Value Value;
    60     typedef _Value Value;
    61 
    61 
    62     /// The const reference type of the map.
    62     // The const reference type of the map.
    63     typedef const _Value& ConstReference;
    63     typedef const _Value& ConstReference;
    64     /// The reference type of the map.
    64     // The reference type of the map.
    65     typedef _Value& Reference;
    65     typedef _Value& Reference;
    66 
    66 
    67     /// The notifier type.
    67     // The notifier type.
    68     typedef typename ItemSetTraits<_Graph, _Item>::ItemNotifier Notifier;
    68     typedef typename ItemSetTraits<_Graph, _Item>::ItemNotifier Notifier;
    69 
    69 
    70     /// The MapBase of the Map which imlements the core regisitry function.
    70     // The MapBase of the Map which imlements the core regisitry function.
    71     typedef typename Notifier::ObserverBase Parent;
    71     typedef typename Notifier::ObserverBase Parent;
    72 
    72 
    73   private:
    73   private:
    74     typedef std::allocator<Value> Allocator;
    74     typedef std::allocator<Value> Allocator;
    75 
    75 
    76   public:
    76   public:
    77 
    77 
    78     /// \brief Graph initialized map constructor.
    78     // \brief Graph initialized map constructor.
    79     ///
    79     //
    80     /// Graph initialized map constructor.
    80     // Graph initialized map constructor.
    81     explicit ArrayMap(const Graph& graph) {
    81     explicit ArrayMap(const Graph& graph) {
    82       Parent::attach(graph.notifier(Item()));
    82       Parent::attach(graph.notifier(Item()));
    83       allocate_memory();
    83       allocate_memory();
    84       Notifier* nf = Parent::notifier();
    84       Notifier* nf = Parent::notifier();
    85       Item it;
    85       Item it;
    87         int id = nf->id(it);;
    87         int id = nf->id(it);;
    88         allocator.construct(&(values[id]), Value());
    88         allocator.construct(&(values[id]), Value());
    89       }
    89       }
    90     }
    90     }
    91 
    91 
    92     /// \brief Constructor to use default value to initialize the map.
    92     // \brief Constructor to use default value to initialize the map.
    93     ///
    93     //
    94     /// It constructs a map and initialize all of the the map.
    94     // It constructs a map and initialize all of the the map.
    95     ArrayMap(const Graph& graph, const Value& value) {
    95     ArrayMap(const Graph& graph, const Value& value) {
    96       Parent::attach(graph.notifier(Item()));
    96       Parent::attach(graph.notifier(Item()));
    97       allocate_memory();
    97       allocate_memory();
    98       Notifier* nf = Parent::notifier();
    98       Notifier* nf = Parent::notifier();
    99       Item it;
    99       Item it;
   102         allocator.construct(&(values[id]), value);
   102         allocator.construct(&(values[id]), value);
   103       }
   103       }
   104     }
   104     }
   105 
   105 
   106   private:
   106   private:
   107     /// \brief Constructor to copy a map of the same map type.
   107     // \brief Constructor to copy a map of the same map type.
   108     ///
   108     //
   109     /// Constructor to copy a map of the same map type.
   109     // Constructor to copy a map of the same map type.
   110     ArrayMap(const ArrayMap& copy) : Parent() {
   110     ArrayMap(const ArrayMap& copy) : Parent() {
   111       if (copy.attached()) {
   111       if (copy.attached()) {
   112         attach(*copy.notifier());
   112         attach(*copy.notifier());
   113       }
   113       }
   114       capacity = copy.capacity;
   114       capacity = copy.capacity;
   120         int id = nf->id(it);;
   120         int id = nf->id(it);;
   121         allocator.construct(&(values[id]), copy.values[id]);
   121         allocator.construct(&(values[id]), copy.values[id]);
   122       }
   122       }
   123     }
   123     }
   124 
   124 
   125     /// \brief Assign operator.
   125     // \brief Assign operator.
   126     ///
   126     //
   127     /// This operator assigns for each item in the map the
   127     // This operator assigns for each item in the map the
   128     /// value mapped to the same item in the copied map.
   128     // value mapped to the same item in the copied map.
   129     /// The parameter map should be indiced with the same
   129     // The parameter map should be indiced with the same
   130     /// itemset because this assign operator does not change
   130     // itemset because this assign operator does not change
   131     /// the container of the map.
   131     // the container of the map.
   132     ArrayMap& operator=(const ArrayMap& cmap) {
   132     ArrayMap& operator=(const ArrayMap& cmap) {
   133       return operator=<ArrayMap>(cmap);
   133       return operator=<ArrayMap>(cmap);
   134     }
   134     }
   135 
   135 
   136 
   136 
   137     /// \brief Template assign operator.
   137     // \brief Template assign operator.
   138     ///
   138     //
   139     /// The given parameter should be conform to the ReadMap
   139     // The given parameter should be conform to the ReadMap
   140     /// concecpt and could be indiced by the current item set of
   140     // concecpt and could be indiced by the current item set of
   141     /// the NodeMap. In this case the value for each item
   141     // the NodeMap. In this case the value for each item
   142     /// is assigned by the value of the given ReadMap.
   142     // is assigned by the value of the given ReadMap.
   143     template <typename CMap>
   143     template <typename CMap>
   144     ArrayMap& operator=(const CMap& cmap) {
   144     ArrayMap& operator=(const CMap& cmap) {
   145       checkConcept<concepts::ReadMap<Key, _Value>, CMap>();
   145       checkConcept<concepts::ReadMap<Key, _Value>, CMap>();
   146       const typename Parent::Notifier* nf = Parent::notifier();
   146       const typename Parent::Notifier* nf = Parent::notifier();
   147       Item it;
   147       Item it;
   150       }
   150       }
   151       return *this;
   151       return *this;
   152     }
   152     }
   153 
   153 
   154   public:
   154   public:
   155     /// \brief The destructor of the map.
   155     // \brief The destructor of the map.
   156     ///
   156     //
   157     /// The destructor of the map.
   157     // The destructor of the map.
   158     virtual ~ArrayMap() {
   158     virtual ~ArrayMap() {
   159       if (attached()) {
   159       if (attached()) {
   160         clear();
   160         clear();
   161         detach();
   161         detach();
   162       }
   162       }
   168     using Parent::detach;
   168     using Parent::detach;
   169     using Parent::attached;
   169     using Parent::attached;
   170 
   170 
   171   public:
   171   public:
   172 
   172 
   173     /// \brief The subscript operator.
   173     // \brief The subscript operator.
   174     ///
   174     //
   175     /// The subscript operator. The map can be subscripted by the
   175     // The subscript operator. The map can be subscripted by the
   176     /// actual keys of the graph.
   176     // actual keys of the graph.
   177     Value& operator[](const Key& key) {
   177     Value& operator[](const Key& key) {
   178       int id = Parent::notifier()->id(key);
   178       int id = Parent::notifier()->id(key);
   179       return values[id];
   179       return values[id];
   180     }
   180     }
   181 
   181 
   182     /// \brief The const subscript operator.
   182     // \brief The const subscript operator.
   183     ///
   183     //
   184     /// The const subscript operator. The map can be subscripted by the
   184     // The const subscript operator. The map can be subscripted by the
   185     /// actual keys of the graph.
   185     // actual keys of the graph.
   186     const Value& operator[](const Key& key) const {
   186     const Value& operator[](const Key& key) const {
   187       int id = Parent::notifier()->id(key);
   187       int id = Parent::notifier()->id(key);
   188       return values[id];
   188       return values[id];
   189     }
   189     }
   190 
   190 
   191     /// \brief Setter function of the map.
   191     // \brief Setter function of the map.
   192     ///
   192     //
   193     /// Setter function of the map. Equivalent with map[key] = val.
   193     // Setter function of the map. Equivalent with map[key] = val.
   194     /// This is a compatibility feature with the not dereferable maps.
   194     // This is a compatibility feature with the not dereferable maps.
   195     void set(const Key& key, const Value& val) {
   195     void set(const Key& key, const Value& val) {
   196       (*this)[key] = val;
   196       (*this)[key] = val;
   197     }
   197     }
   198 
   198 
   199   protected:
   199   protected:
   200 
   200 
   201     /// \brief Adds a new key to the map.
   201     // \brief Adds a new key to the map.
   202     ///
   202     //
   203     /// It adds a new key to the map. It called by the observer notifier
   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.
   204     // and it overrides the add() member function of the observer base.
   205     virtual void add(const Key& key) {
   205     virtual void add(const Key& key) {
   206       Notifier* nf = Parent::notifier();
   206       Notifier* nf = Parent::notifier();
   207       int id = nf->id(key);
   207       int id = nf->id(key);
   208       if (id >= capacity) {
   208       if (id >= capacity) {
   209         int new_capacity = (capacity == 0 ? 1 : capacity);
   209         int new_capacity = (capacity == 0 ? 1 : capacity);
   224         capacity = new_capacity;
   224         capacity = new_capacity;
   225       }
   225       }
   226       allocator.construct(&(values[id]), Value());
   226       allocator.construct(&(values[id]), Value());
   227     }
   227     }
   228 
   228 
   229     /// \brief Adds more new keys to the map.
   229     // \brief Adds more new keys to the map.
   230     ///
   230     //
   231     /// It adds more new keys to the map. It called by the observer notifier
   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.
   232     // and it overrides the add() member function of the observer base.
   233     virtual void add(const std::vector<Key>& keys) {
   233     virtual void add(const std::vector<Key>& keys) {
   234       Notifier* nf = Parent::notifier();
   234       Notifier* nf = Parent::notifier();
   235       int max_id = -1;
   235       int max_id = -1;
   236       for (int i = 0; i < int(keys.size()); ++i) {
   236       for (int i = 0; i < int(keys.size()); ++i) {
   237         int id = nf->id(keys[i]);
   237         int id = nf->id(keys[i]);
   268         int id = nf->id(keys[i]);
   268         int id = nf->id(keys[i]);
   269         allocator.construct(&(values[id]), Value());
   269         allocator.construct(&(values[id]), Value());
   270       }
   270       }
   271     }
   271     }
   272 
   272 
   273     /// \brief Erase a key from the map.
   273     // \brief Erase a key from the map.
   274     ///
   274     //
   275     /// Erase a key from the map. It called by the observer notifier
   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.
   276     // and it overrides the erase() member function of the observer base.
   277     virtual void erase(const Key& key) {
   277     virtual void erase(const Key& key) {
   278       int id = Parent::notifier()->id(key);
   278       int id = Parent::notifier()->id(key);
   279       allocator.destroy(&(values[id]));
   279       allocator.destroy(&(values[id]));
   280     }
   280     }
   281 
   281 
   282     /// \brief Erase more keys from the map.
   282     // \brief Erase more keys from the map.
   283     ///
   283     //
   284     /// Erase more keys from the map. It called by the observer notifier
   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.
   285     // and it overrides the erase() member function of the observer base.
   286     virtual void erase(const std::vector<Key>& keys) {
   286     virtual void erase(const std::vector<Key>& keys) {
   287       for (int i = 0; i < int(keys.size()); ++i) {
   287       for (int i = 0; i < int(keys.size()); ++i) {
   288         int id = Parent::notifier()->id(keys[i]);
   288         int id = Parent::notifier()->id(keys[i]);
   289         allocator.destroy(&(values[id]));
   289         allocator.destroy(&(values[id]));
   290       }
   290       }
   291     }
   291     }
   292 
   292 
   293     /// \brief Buildes the map.
   293     // \brief Buildes the map.
   294     ///
   294     //
   295     /// It buildes the map. It called by the observer notifier
   295     // It buildes the map. It called by the observer notifier
   296     /// and it overrides the build() member function of the observer base.
   296     // and it overrides the build() member function of the observer base.
   297     virtual void build() {
   297     virtual void build() {
   298       Notifier* nf = Parent::notifier();
   298       Notifier* nf = Parent::notifier();
   299       allocate_memory();
   299       allocate_memory();
   300       Item it;
   300       Item it;
   301       for (nf->first(it); it != INVALID; nf->next(it)) {
   301       for (nf->first(it); it != INVALID; nf->next(it)) {
   302         int id = nf->id(it);;
   302         int id = nf->id(it);;
   303         allocator.construct(&(values[id]), Value());
   303         allocator.construct(&(values[id]), Value());
   304       }
   304       }
   305     }
   305     }
   306 
   306 
   307     /// \brief Clear the map.
   307     // \brief Clear the map.
   308     ///
   308     //
   309     /// It erase all items from the map. It called by the observer notifier
   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.
   310     // and it overrides the clear() member function of the observer base.
   311     virtual void clear() {
   311     virtual void clear() {
   312       Notifier* nf = Parent::notifier();
   312       Notifier* nf = Parent::notifier();
   313       if (capacity != 0) {
   313       if (capacity != 0) {
   314         Item it;
   314         Item it;
   315         for (nf->first(it); it != INVALID; nf->next(it)) {
   315         for (nf->first(it); it != INVALID; nf->next(it)) {