source: lemon-0.x/src/work/deba/array_map_factory.h @ 689:e7cf90de549a

#ifndef ARRAY_MAP_H
#define ARRAY_MAP_H

#include <memory>


#include <iostream>
using namespace std;

namespace hugo {
        
  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(Graph& g, MapRegistry& r) : MapBase(g, r) {
          int max_id = -1;
          for (KeyIt it(*graph); graph->valid(it); graph->next(it)) {
            int id = graph->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);
          for (KeyIt it(*graph); graph->valid(it); graph->next(it)) {
            int id = graph->id(it);
            allocator.construct(&(values[id]), Value());
          }                                                             
        }

        Map(const Map& copy) : MapBase(*copy.graph, *copy.registry) {
          capacity = copy.capacity;
          values = allocator.allocate(capacity);
          for (KeyIt it(*graph); graph->valid(it); graph->next(it)) {
            int id = graph->id(it);
            allocator.construct(&(values[id]), copy.values[id]);
          }
        }
                                
        virtual ~Map() {
          destroy();
          allocator.deallocate(values, capacity);
        }
        
        
        Value& operator[](const Key& key) {
          int id = graph->id(key);
          return values[id];
        } 
                
        const Value& operator[](const Key& key) const {
          int id = graph->id(key);
          return values[id];
        }
        
        const Value& get(const Key& key) const {
          int id = graph->id(key);
          return values[id];
        } 
                
        void set(const Key& key, const Value& val) {
          int id = graph->id(key);
          values[id] = val;
        }
                
        void add(const Key& key) {
          int id = graph->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(*graph); graph->valid(it); graph->next(it)) {
              int jd = graph->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 = graph->id(key);
          allocator.destroy(&(values[id]));
        }
        
        private:
        int capacity;
        Value* values;
        Allocator allocator;
      };                
  };
}

#endif