source: lemon-0.x/src/work/deba/array_map_factory.h @ 963:5a7556e9e340

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

#include <memory>

#include "extended_pair.h"

namespace lemon {
        
  template <typename MapRegistry> class ArrayMapFactory {
                
  public:
                
    typedef typename MapRegistry::Graph Graph;
    typedef typename MapRegistry::Key Key;
    typedef typename MapRegistry::KeyIt KeyIt;

    typedef typename MapRegistry::MapBase MapBase;
                
    template <typename V, typename A = std::allocator<V> > 
    class Map : public MapBase {
    
      public:

      typedef V Value;
      typedef A Allocator;

        
      Map() : values(0), capacity(0) {}
                        
      Map(const Graph& g, MapRegistry& r) : MapBase(g, r) {
        allocate_memory();
        for (KeyIt it(*getGraph()); getGraph()->valid(it); getGraph()->next(it)) {
          int id = getGraph()->id(it);
          allocator.construct(&(values[id]), Value());
        }                                                               
      }

      Map(const Graph& g, MapRegistry& r, const Value& v) : MapBase(g, r) {
        allocate_memory();
        for (KeyIt it(*getGraph()); getGraph()->valid(it); getGraph()->next(it)) {
          int id = getGraph()->id(it);
          allocator.construct(&(values[id]), v);
        }                                                               
      }

      Map(const Map& copy) : MapBase(*copy.graph, *copy.registry) {
        capacity = copy.capacity;
        if (capacity == 0) return;
        values = allocator.allocate(capacity);
        for (KeyIt it(*getGraph()); getGraph()->valid(it); getGraph()->next(it)) {
          int id = getGraph()->id(it);
          allocator.construct(&(values[id]), copy.values[id]);
        }
      }

      template <typename CMap> Map(const CMap& copy) 
        : capacity(0), values(0), MapBase(copy) {
        if (getGraph()) {
          allocate_memory();
          for (KeyIt it(*getGraph()); getGraph()->valid(it); getGraph()->next(it)) {
            set(it, copy[it]);
          }
        }
      }

      Map& operator=(const Map& copy) {
        if (&copy == this) return;
        if (capacity != 0) {
          destroy();
          allocator.deallocate(values, capacity);
        }
        capacity = copy.capacity;
        if (capacity == 0) return;
        values = allocator.allocate(capacity);
        for (KeyIt it(getGraph()); getGraph()->valid(it); getGraph()->next(it)) {
          int id = getGraph()->id(it);
          allocator.construct(&(values[id]), copy.values[id]);
        }
      }

      template <typename CMap> Map& operator=(const CMap& copy) {
        if (getGraph()) {
          destroy();
        } 
        this->MapBase::operator=(copy);
        if (getGraph()) {
          allocate_memory();
          for (KeyIt it(*getGraph()); getGraph()->valid(it); getGraph()->next(it)) {
            set(it, copy[it]);
          }
        }
      }
                                
      virtual ~Map() {
        if (capacity != 0) {
          destroy();
          allocator.deallocate(values, capacity);
        }
      }
        
        
      Value& operator[](const Key& key) {
        int id = getGraph()->id(key);
        return values[id];
      } 
                
      const Value& operator[](const Key& key) const {
        int id = getGraph()->id(key);
        return values[id];
      }
        
      const Value& get(const Key& key) const {
        int id = getGraph()->id(key);
        return values[id];
      } 
                
      void set(const Key& key, const Value& val) {
        int id = getGraph()->id(key);
        values[id] = val;
      }
                
      void add(const Key& key) {
        int id = getGraph()->id(key);
        if (id >= capacity) {
          int new_capacity = (capacity == 0 ? 1 : capacity);
          while (new_capacity <= id) {
            new_capacity <<= 1;
          }
          Value* new_values = allocator.allocate(new_capacity);;
          for (KeyIt it(*getGraph()); getGraph()->valid(it); getGraph()->next(it)) {
            int jd = getGraph()->id(it);
            if (id != jd) {
              allocator.construct(&(new_values[jd]), values[jd]);
              allocator.destroy(&(values[jd]));
            }
          }
          if (capacity != 0) allocator.deallocate(values, capacity);
          values = new_values;
          capacity = new_capacity;
        }
        allocator.construct(&(values[id]), Value());
      }
                
      void erase(const Key& key) {
        int id = getGraph()->id(key);
        allocator.destroy(&(values[id]));
      }
        
      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 Key&, const Key&, 
                              Value&, Value&> Reference;

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

        class Pointer {
          friend class iterator;
        private:
          Reference data;
          Pointer(const Key& key, Value& 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++() { 
          map->getGraph()->next(it); 
          return *this; 
        }

        /** The post increment operator of the map.
         */
        iterator operator++(int) { 
          iterator tmp(it); 
          map.getGraph()->next(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 Key&, const Key&, 
          const Value&, const Value&> Reference;

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


        class Pointer {
          friend class const_iterator;
        private:
          Reference data;
          Pointer(const Key& key, const Value& 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++() { 
          map->getGraph()->next(it); 
          return *this; 
        }

        /** The post increment operator of the map.
         */
        const_iterator operator++(int) { 
          const_iterator tmp(it); 
          map->getGraph()->next(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:
      
      void allocate_memory() {
        int max_id = -1;
        for (KeyIt it(*getGraph()); getGraph()->valid(it); getGraph()->next(it)) {
          int id = getGraph()->id(it);
          if (id > max_id) {
            max_id = id;
          }                     
        }
        if (max_id == -1) {
          capacity = 0;
          values = 0;
          return;
        }
        capacity = 1;
        while (capacity <= max_id) {
          capacity <<= 1;
        }
        values = allocator.allocate(capacity);  
      }      
      int capacity;
      Value* values;
      Allocator allocator;
    };          
  };
}

#endif