COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/deba/array_map_factory.h @ 627:6cc21a9c9fda

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