lemon/bits/array_map.h
changeset 393 37054b67d807
parent 314 2cc60866a0c9
child 440 88ed40ad0d4f
equal deleted inserted replaced
4:e72a6a97b382 5:4fcbfa5d1335
    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 that automatically
    40   // automatically updates the map when a key is added to or erased from
    40   // updates the map when a key is added to or erased from the graph.
    41   // the map. This map uses the allocators to implement
    41   // This map uses the allocators to implement the container functionality.
    42   // the container functionality.
       
    43   //
    42   //
    44   // The template parameters are the Graph the current Item type and
    43   // The template parameters are the Graph, the current Item type and
    45   // the Value type of the map.
    44   // the Value type of the map.
    46   template <typename _Graph, typename _Item, typename _Value>
    45   template <typename _Graph, typename _Item, typename _Value>
    47   class ArrayMap
    46   class ArrayMap
    48     : public ItemSetTraits<_Graph, _Item>::ItemNotifier::ObserverBase {
    47     : public ItemSetTraits<_Graph, _Item>::ItemNotifier::ObserverBase {
    49   public:
    48   public:
    50     // The graph type of the maps.
    49     // The graph type.
    51     typedef _Graph Graph;
    50     typedef _Graph Graph;
    52     // The item type of the map.
    51     // The item type.
    53     typedef _Item Item;
    52     typedef _Item Item;
    54     // The reference map tag.
    53     // The reference map tag.
    55     typedef True ReferenceMapTag;
    54     typedef True ReferenceMapTag;
    56 
    55 
    57     // The key type of the maps.
    56     // The key type of the map.
    58     typedef _Item Key;
    57     typedef _Item Key;
    59     // The value type of the map.
    58     // The value type of the map.
    60     typedef _Value Value;
    59     typedef _Value Value;
    61 
    60 
    62     // The const reference type of the map.
    61     // The const reference type of the map.
   198 
   197 
   199   protected:
   198   protected:
   200 
   199 
   201     // \brief Adds a new key to the map.
   200     // \brief Adds a new key to the map.
   202     //
   201     //
   203     // It adds a new key to the map. It called by the observer notifier
   202     // It adds a new key to the map. It is called by the observer notifier
   204     // and it overrides the add() member function of the observer base.
   203     // and it overrides the add() member function of the observer base.
   205     virtual void add(const Key& key) {
   204     virtual void add(const Key& key) {
   206       Notifier* nf = Parent::notifier();
   205       Notifier* nf = Parent::notifier();
   207       int id = nf->id(key);
   206       int id = nf->id(key);
   208       if (id >= capacity) {
   207       if (id >= capacity) {
   226       allocator.construct(&(values[id]), Value());
   225       allocator.construct(&(values[id]), Value());
   227     }
   226     }
   228 
   227 
   229     // \brief Adds more new keys to the map.
   228     // \brief Adds more new keys to the map.
   230     //
   229     //
   231     // It adds more new keys to the map. It called by the observer notifier
   230     // It adds more new keys to the map. It is called by the observer notifier
   232     // and it overrides the add() member function of the observer base.
   231     // and it overrides the add() member function of the observer base.
   233     virtual void add(const std::vector<Key>& keys) {
   232     virtual void add(const std::vector<Key>& keys) {
   234       Notifier* nf = Parent::notifier();
   233       Notifier* nf = Parent::notifier();
   235       int max_id = -1;
   234       int max_id = -1;
   236       for (int i = 0; i < int(keys.size()); ++i) {
   235       for (int i = 0; i < int(keys.size()); ++i) {
   270       }
   269       }
   271     }
   270     }
   272 
   271 
   273     // \brief Erase a key from the map.
   272     // \brief Erase a key from the map.
   274     //
   273     //
   275     // Erase a key from the map. It called by the observer notifier
   274     // Erase a key from the map. It is called by the observer notifier
   276     // and it overrides the erase() member function of the observer base.
   275     // and it overrides the erase() member function of the observer base.
   277     virtual void erase(const Key& key) {
   276     virtual void erase(const Key& key) {
   278       int id = Parent::notifier()->id(key);
   277       int id = Parent::notifier()->id(key);
   279       allocator.destroy(&(values[id]));
   278       allocator.destroy(&(values[id]));
   280     }
   279     }
   281 
   280 
   282     // \brief Erase more keys from the map.
   281     // \brief Erase more keys from the map.
   283     //
   282     //
   284     // Erase more keys from the map. It called by the observer notifier
   283     // Erase more keys from the map. It is called by the observer notifier
   285     // and it overrides the erase() member function of the observer base.
   284     // and it overrides the erase() member function of the observer base.
   286     virtual void erase(const std::vector<Key>& keys) {
   285     virtual void erase(const std::vector<Key>& keys) {
   287       for (int i = 0; i < int(keys.size()); ++i) {
   286       for (int i = 0; i < int(keys.size()); ++i) {
   288         int id = Parent::notifier()->id(keys[i]);
   287         int id = Parent::notifier()->id(keys[i]);
   289         allocator.destroy(&(values[id]));
   288         allocator.destroy(&(values[id]));
   290       }
   289       }
   291     }
   290     }
   292 
   291 
   293     // \brief Buildes the map.
   292     // \brief Builds the map.
   294     //
   293     //
   295     // It buildes the map. It called by the observer notifier
   294     // It builds the map. It is called by the observer notifier
   296     // and it overrides the build() member function of the observer base.
   295     // and it overrides the build() member function of the observer base.
   297     virtual void build() {
   296     virtual void build() {
   298       Notifier* nf = Parent::notifier();
   297       Notifier* nf = Parent::notifier();
   299       allocate_memory();
   298       allocate_memory();
   300       Item it;
   299       Item it;
   304       }
   303       }
   305     }
   304     }
   306 
   305 
   307     // \brief Clear the map.
   306     // \brief Clear the map.
   308     //
   307     //
   309     // It erase all items from the map. It called by the observer notifier
   308     // It erase all items from the map. It is called by the observer notifier
   310     // and it overrides the clear() member function of the observer base.
   309     // and it overrides the clear() member function of the observer base.
   311     virtual void clear() {
   310     virtual void clear() {
   312       Notifier* nf = Parent::notifier();
   311       Notifier* nf = Parent::notifier();
   313       if (capacity != 0) {
   312       if (capacity != 0) {
   314         Item it;
   313         Item it;