COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/deba/array_map_factory.h @ 698:625de6f1e766

Last change on this file since 698:625de6f1e766 was 674:7733d18de0e8, checked in by Balazs Dezso, 20 years ago
File size: 2.7 KB
Line 
1#ifndef ARRAY_MAP_H
2#define ARRAY_MAP_H
3
4#include <memory>
5
6
7#include <iostream>
8using namespace std;
9
10namespace hugo {
11       
12  template <typename MapRegistry> class ArrayMapFactory {
13               
14  public:
15               
16    typedef typename MapRegistry::Graph Graph;
17    typedef typename MapRegistry::Key Key;
18    typedef typename MapRegistry::KeyIt KeyIt;
19
20    typedef typename MapRegistry::MapBase MapBase;
21               
22    template <typename V, typename A = std::allocator<V> >
23      class Map : public MapBase {
24   
25        public:
26
27        typedef V Value;
28        typedef A Allocator;
29
30       
31        Map() : values(0), capacity(0) {}
32                       
33        Map(Graph& g, MapRegistry& r) : MapBase(g, r) {
34          int max_id = -1;
35          for (KeyIt it(*graph); graph->valid(it); graph->next(it)) {
36            int id = graph->id(it);
37            if (id > max_id) {
38              max_id = id;
39            }                   
40          }
41          if (max_id == -1) {
42            capacity = 0;
43            values = 0;
44            return;
45          }
46          capacity = 1;
47          while (capacity <= max_id) {
48            capacity <<= 1;
49          }
50          values = allocator.allocate(capacity);
51          for (KeyIt it(*graph); graph->valid(it); graph->next(it)) {
52            int id = graph->id(it);
53            allocator.construct(&(values[id]), Value());
54          }                                                             
55        }
56
57        Map(const Map& copy) : MapBase(*copy.graph, *copy.registry) {
58          capacity = copy.capacity;
59          values = allocator.allocate(capacity);
60          for (KeyIt it(*graph); graph->valid(it); graph->next(it)) {
61            int id = graph->id(it);
62            allocator.construct(&(values[id]), copy.values[id]);
63          }
64        }
65                               
66        virtual ~Map() {
67          destroy();
68          allocator.deallocate(values, capacity);
69        }
70       
71       
72        Value& operator[](const Key& key) {
73          int id = graph->id(key);
74          return values[id];
75        }
76               
77        const Value& operator[](const Key& key) const {
78          int id = graph->id(key);
79          return values[id];
80        }
81       
82        const Value& get(const Key& key) const {
83          int id = graph->id(key);
84          return values[id];
85        }
86               
87        void set(const Key& key, const Value& val) {
88          int id = graph->id(key);
89          values[id] = val;
90        }
91               
92        void add(const Key& key) {
93          int id = graph->id(key);
94          if (id >= capacity) {
95            int new_capacity = (capacity == 0 ? 1 : capacity);
96            while (new_capacity <= id) {
97              new_capacity <<= 1;
98            }
99            Value* new_values = allocator.allocate(new_capacity);;
100            for (KeyIt it(*graph); graph->valid(it); graph->next(it)) {
101              int jd = graph->id(it);
102              if (id != jd) {
103                allocator.construct(&(new_values[jd]), values[jd]);
104                allocator.destroy(&(values[jd]));
105              }
106            }
107            if (capacity != 0) allocator.deallocate(values, capacity);
108            values = new_values;
109            capacity = new_capacity;
110          }
111          allocator.construct(&(values[id]), Value());
112        }
113               
114        void erase(const Key& key) {
115          int id = graph->id(key);
116          allocator.destroy(&(values[id]));
117        }
118       
119        private:
120        int capacity;
121        Value* values;
122        Allocator allocator;
123      };               
124  };
125}
126
127#endif
Note: See TracBrowser for help on using the repository browser.