lemon/bits/vector_map.h
changeset 431 9dfaf6efc36f
parent 314 2cc60866a0c9
child 440 88ed40ad0d4f
equal deleted inserted replaced
7:6da6c2f394bf 8:455b9c3ddd8f
    36 
    36 
    37   // \ingroup graphbits
    37   // \ingroup graphbits
    38   //
    38   //
    39   // \brief Graph map based on the std::vector storage.
    39   // \brief Graph map based on the std::vector storage.
    40   //
    40   //
    41   // The VectorMap template class is graph map structure what
    41   // The VectorMap template class is graph map structure that automatically
    42   // automatically updates the map when a key is added to or erased from
    42   // updates the map when a key is added to or erased from the graph.
    43   // the map. This map type uses the std::vector to store the values.
    43   // This map type uses std::vector to store the values.
    44   //
    44   //
    45   // \tparam _Graph The graph this map is attached to.
    45   // \tparam _Graph The graph this map is attached to.
    46   // \tparam _Item The item type of the graph items.
    46   // \tparam _Item The item type of the graph items.
    47   // \tparam _Value The value type of the map.
    47   // \tparam _Value The value type of the map.
    48   template <typename _Graph, typename _Item, typename _Value>
    48   template <typename _Graph, typename _Item, typename _Value>
   167 
   167 
   168   protected:
   168   protected:
   169 
   169 
   170     // \brief Adds a new key to the map.
   170     // \brief Adds a new key to the map.
   171     //
   171     //
   172     // It adds a new key to the map. It called by the observer notifier
   172     // It adds a new key to the map. It is called by the observer notifier
   173     // and it overrides the add() member function of the observer base.
   173     // and it overrides the add() member function of the observer base.
   174     virtual void add(const Key& key) {
   174     virtual void add(const Key& key) {
   175       int id = Parent::notifier()->id(key);
   175       int id = Parent::notifier()->id(key);
   176       if (id >= int(container.size())) {
   176       if (id >= int(container.size())) {
   177         container.resize(id + 1);
   177         container.resize(id + 1);
   178       }
   178       }
   179     }
   179     }
   180 
   180 
   181     // \brief Adds more new keys to the map.
   181     // \brief Adds more new keys to the map.
   182     //
   182     //
   183     // It adds more new keys to the map. It called by the observer notifier
   183     // It adds more new keys to the map. It is called by the observer notifier
   184     // and it overrides the add() member function of the observer base.
   184     // and it overrides the add() member function of the observer base.
   185     virtual void add(const std::vector<Key>& keys) {
   185     virtual void add(const std::vector<Key>& keys) {
   186       int max = container.size() - 1;
   186       int max = container.size() - 1;
   187       for (int i = 0; i < int(keys.size()); ++i) {
   187       for (int i = 0; i < int(keys.size()); ++i) {
   188         int id = Parent::notifier()->id(keys[i]);
   188         int id = Parent::notifier()->id(keys[i]);
   193       container.resize(max + 1);
   193       container.resize(max + 1);
   194     }
   194     }
   195 
   195 
   196     // \brief Erase a key from the map.
   196     // \brief Erase a key from the map.
   197     //
   197     //
   198     // Erase a key from the map. It called by the observer notifier
   198     // Erase a key from the map. It is called by the observer notifier
   199     // and it overrides the erase() member function of the observer base.
   199     // and it overrides the erase() member function of the observer base.
   200     virtual void erase(const Key& key) {
   200     virtual void erase(const Key& key) {
   201       container[Parent::notifier()->id(key)] = Value();
   201       container[Parent::notifier()->id(key)] = Value();
   202     }
   202     }
   203 
   203 
   204     // \brief Erase more keys from the map.
   204     // \brief Erase more keys from the map.
   205     //
   205     //
   206     // Erase more keys from the map. It called by the observer notifier
   206     // It erases more keys from the map. It is called by the observer notifier
   207     // and it overrides the erase() member function of the observer base.
   207     // and it overrides the erase() member function of the observer base.
   208     virtual void erase(const std::vector<Key>& keys) {
   208     virtual void erase(const std::vector<Key>& keys) {
   209       for (int i = 0; i < int(keys.size()); ++i) {
   209       for (int i = 0; i < int(keys.size()); ++i) {
   210         container[Parent::notifier()->id(keys[i])] = Value();
   210         container[Parent::notifier()->id(keys[i])] = Value();
   211       }
   211       }
   212     }
   212     }
   213 
   213 
   214     // \brief Buildes the map.
   214     // \brief Build the map.
   215     //
   215     //
   216     // It buildes the map. It called by the observer notifier
   216     // It builds the map. It is called by the observer notifier
   217     // and it overrides the build() member function of the observer base.
   217     // and it overrides the build() member function of the observer base.
   218     virtual void build() {
   218     virtual void build() {
   219       int size = Parent::notifier()->maxId() + 1;
   219       int size = Parent::notifier()->maxId() + 1;
   220       container.reserve(size);
   220       container.reserve(size);
   221       container.resize(size);
   221       container.resize(size);
   222     }
   222     }
   223 
   223 
   224     // \brief Clear the map.
   224     // \brief Clear the map.
   225     //
   225     //
   226     // It erase all items from the map. It called by the observer notifier
   226     // It erases all items from the map. It is called by the observer notifier
   227     // and it overrides the clear() member function of the observer base.
   227     // and it overrides the clear() member function of the observer base.
   228     virtual void clear() {
   228     virtual void clear() {
   229       container.clear();
   229       container.clear();
   230     }
   230     }
   231 
   231