source: lemon-0.x/src/hugo/vector_map_factory.h @ 816:a39579c35dd7

// -*- c++ -*-
#ifndef VECTOR_MAP_H
#define VECTOR_MAP_H

#include <vector>

#include <hugo/extended_pair.h>

///\ingroup graphmapfactory
///\file
///\brief Vector based graph maps.

namespace hugo {
  
  /// \addtogroup graphmapfactory
  /// @{
  
  /** The VectorMapFactory template class is a factory class
   *  to create maps for the edge and nodes. This map factory
   *  uses the std::vector to implement the container function.
   *
   *  The template parameter is the MapRegistry that the maps
   *  will belong to.
   * 
   * \todo It should use a faster initialization using the maxNodeId() or
   * maxEdgeId() function of the graph istead of iterating through each
   * edge/node.
   */
        
  template <typename MapRegistry>
  class VectorMapFactory {
  public:
                
    /// The graph type of the maps. 
    typedef typename MapRegistry::Graph Graph;
    /// The key type of the maps.
    typedef typename MapRegistry::KeyType KeyType;
    /// The iterator to iterate on the keys.
    typedef typename MapRegistry::KeyIt KeyIt;

    /// The MapBase of the Map which imlements the core regisitry function.
    typedef typename MapRegistry::MapBase MapBase;

                
    /** The template Map type.
     */
    template <typename V> 
    class Map : public MapBase {

      typedef std::vector<V> Container; 

    public:

      /// The value type of the map.
      typedef V ValueType;

      /// The value type of the map.
      typedef V Value;
      /// The reference type of the map;
      typedef typename Container::reference Reference;
      /// The pointer type of the map;
      typedef typename Container::pointer Pointer;

      /// The const value type of the map.
      typedef const Value ConstValue;
      /// The const reference type of the map;
      typedef typename Container::const_reference ConstReference;
      /// The pointer type of the map;
      typedef typename Container::const_pointer ConstPointer;

      /** Default constructor for the map.
       */
      Map() {}
                
      /** Graph and Registry initialized map constructor.
       */
      Map(const Graph& g, MapRegistry& r) : MapBase(g, r) {
        init();
      }

      /** Constructor to use default value to initialize the map. 
       */
      Map(const Graph& g, MapRegistry& r, const Value& v) : MapBase(g, r) {
        for (KeyIt it(*getGraph()); it != INVALID; ++it) {
          int id = getGraph()->id(it);
          if (id >= (int)container.size()) {
            container.resize(id + 1);
          }
          set(it, v);
        }
      }

      /** Constructor to copy a map of an other map type.
       */
      template <typename CMap> Map(const CMap& copy) : MapBase(copy) {
        if (getGraph()) {
          for (KeyIt it(*getGraph()); it != INVALID; ++it) {
            int id = getGraph()->id(it);
            if (id >= (int)container.size()) {
              container.resize(id + 1);
            }
            set(it, copy[it]);
          }
        }
      }

      /** Assign operator to copy a map an other map type.
       */
      template <typename CMap> Map& operator=(const CMap& copy) {
        if (getGraph()) {
          destroy();
        } 
        this->MapBase::operator=(copy);
        if (getGraph()) {
          for (KeyIt it(*getGraph()); it != INVALID; ++it) {
            int id = getGraph()->id(it);
            if (id >= (int)container.size()) {
              container.resize(id + 1);
            }
            set(it, copy[it]);
          }
        }
        return *this;
      }

      /** The destructor of the map.
       */
      virtual ~Map() {
      }
                
      /**
       * The subscript operator. The map can be subscripted by the
       * actual keys of the graph. 
       */
      Reference operator[](const KeyType& key) {
        int id = getGraph()->id(key);
        return container[id];
      } 
                
      /**
       * The const subscript operator. The map can be subscripted by the
       * actual keys of the graph. 
       */
      ConstReference operator[](const KeyType& key) const {
        int id = getGraph()->id(key);
        return container[id];
      }

      /** Setter function of the map. Equivalent with map[key] = val.
       *  This is a compatibility feature with the not dereferable maps.
       */
      void set(const KeyType& key, const Value& val) {
        int id = getGraph()->id(key);
        container[id] = val;
      }
                
      /** Add a new key to the map. It called by the map registry.
       */
      void add(const KeyType& key) {
        int id = getGraph()->id(key);
        if (id >= (int)container.size()) {
          container.resize(id + 1);
        }
      }
                
      /** Erase a key from the map. It called by the map registry.
       */
      void erase(const KeyType& key) {}

      /** Clear the data structure.
       */
      void clear() { 
        container.clear();
      }

      /** Compatible iterator with the stl maps' iterators.
       *  It iterates on pairs of a key and a value.
       */
      class iterator {
        friend class Map;
        friend class const_iterator;
      private:

        /** Private constructor to initalize the the iterators returned
         *  by the begin() and end().
         */
        iterator (Map& pmap, const KeyIt& pit) : map(&pmap), it(pit) {}

      public:

        /** Default constructor. 
         */
        iterator() {}

        typedef extended_pair<const KeyType&, const KeyType&, 
                              Map::Reference, Map::Reference> Reference;

        /** Dereference operator for map.
         */      
        Reference operator*() {
          return Reference(it, (*map)[it]);
        }

        class Pointer {
          friend class iterator;
        private:
          Reference data;
          Pointer(const KeyType& key, Map::Reference val) : data(key, val) {}
        public:
          Reference* operator->() {return &data;}
        };

        /** Arrow operator for map.
         */      
        Pointer operator->() {
          return Pointer(it, ((*map)[it])); 
        }

        /** The pre increment operator of the map.
         */
        iterator& operator++() { 
          ++it; 
          return *this; 
        }

        /** The post increment operator of the map.
         */
        iterator operator++(int) { 
          iterator tmp(it); 
          ++it; 
          return tmp; 
        }

        /** The equality operator of the map.
         */
        bool operator==(const_iterator p_it) {
          return p_it.it == it;
        }
        
        /** The not-equality operator of the map.
         */
        bool operator!=(const_iterator p_it) {
          return !(*this == p_it);
        }

        
      private:
        Map* map;
        KeyIt it;
      };

      /** Returns the begin iterator of the map.
       */
      iterator begin() {
        return iterator(*this, KeyIt(*getGraph()));
      }

      /** Returns the end iterator of the map.
       */
      iterator end() {
        return iterator(*this, INVALID);
      }

      class const_iterator {
        friend class Map;
        friend class iterator;
      private:

        /** Private constructor to initalize the the iterators returned
         *  by the begin() and end().
         */
        const_iterator (const Map& pmap, const KeyIt& pit) 
          : map(&pmap), it(pit) {}

      public:

        /** Default constructor. 
         */
        const_iterator() {}

        /** Constructor to convert iterator to const_iterator.
         */
        const_iterator(iterator p_it) : map(p_it.map), it(p_it.it) {}
      
        typedef extended_pair<const KeyType&, const KeyType&, 
          Map::ConstReference, Map::ConstReference> Reference;

        /** Dereference operator for map.
         */      
        Reference operator*() {
          return Reference(it, (*map)[it]);
        }


        class Pointer {
          friend class const_iterator;
        private:
          Reference data;
          Pointer(const KeyType& key, Map::ConstReference val) 
            : data(key, val) {}
        public:
          Reference* operator->() {return &data;}
        };

        /** Arrow operator for map.
         */      
        Pointer operator->() {
          return Pointer(it, ((*map)[it])); 
        }

        /** The pre increment operator of the map.
         */
        const_iterator& operator++() { 
          ++it; 
          return *this; 
        }

        /** The post increment operator of the map.
         */
        const_iterator operator++(int) { 
          const_iterator tmp(it); 
          ++it; 
          return tmp; 
        }

        /** The equality operator of the map.
         */
        bool operator==(const_iterator p_it) {
          return p_it.it == it;
        }
        
        /** The not-equality operator of the map.
         */
        bool operator!=(const_iterator p_it) {
          return !(*this == p_it);
        }
        

      private:
        const Map* map;
        KeyIt it;
      };

      /** Returns the begin const_iterator of the map.
       */
      const_iterator begin() const {
        return const_iterator(*this, KeyIt(*getGraph()));
      }

      /** Returns the end const_iterator of the map.
       */
      const_iterator end() const {
        return const_iterator(*this, INVALID);
      }

      private:
                
      Container container;

    };
                
  };

  
  /// @}
  

}

#endif