1 | #ifndef __HYBRID_MAP_HH__␊ |
2 | #define __HYBRID_MAP_HH__␊ |
3 | ␊ |
4 | // Copyright 2007 Timothy Brownawell <tbrownaw@gmail.com>␊ |
5 | //␊ |
6 | // This program is made available under the GNU GPL version 2.0 or␊ |
7 | // greater. See the accompanying file COPYING for details.␊ |
8 | //␊ |
9 | // This program is distributed WITHOUT ANY WARRANTY; without even the␊ |
10 | // implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR␊ |
11 | // PURPOSE.␊ |
12 | ␊ |
13 | ␊ |
14 | #include "hash_map.hh"␊ |
15 | #include <map>␊ |
16 | ␊ |
17 | template<typename Key, typename Val>␊ |
18 | class hybrid_map␊ |
19 | {␊ |
20 | typedef std::map<Key, Val> omap;␊ |
21 | typedef hashmap::hash_map<Key, Val> umap;␊ |
22 | omap ordered;␊ |
23 | umap unordered;␊ |
24 | public:␊ |
25 | typedef typename omap::value_type value_type;␊ |
26 | typedef typename omap::key_type key_type;␊ |
27 | typedef typename omap::mapped_type mapped_type;␊ |
28 | typedef typename omap::size_type size_type;␊ |
29 | class const_iterator;␊ |
30 | class iterator␊ |
31 | {␊ |
32 | friend class hybrid_map<Key, Val>;␊ |
33 | bool ordered;␊ |
34 | bool valid;␊ |
35 | typename omap::iterator o;␊ |
36 | typename umap::iterator u;␊ |
37 | hybrid_map<Key, Val> * n;␊ |
38 | friend class const_iterator;␊ |
39 | public:␊ |
40 | iterator(hybrid_map<Key, Val> * n, typename omap::iterator const & i)␊ |
41 | : ordered(true), valid(i != n->ordered.end()), o(i), n(n)␊ |
42 | {}␊ |
43 | iterator(hybrid_map<Key, Val> * n, typename umap::iterator const & i)␊ |
44 | : ordered(false), valid(i != n->unordered.end()), u(i), n(n)␊ |
45 | {}␊ |
46 | iterator()␊ |
47 | : valid(false)␊ |
48 | {}␊ |
49 | iterator & operator++()␊ |
50 | {␊ |
51 | I(valid);␊ |
52 | if (!ordered)␊ |
53 | {␊ |
54 | ordered = true;␊ |
55 | o = n->ordered.find(u->first);␊ |
56 | }␊ |
57 | ++o;␊ |
58 | valid = (o != n->ordered.end());␊ |
59 | return *this;␊ |
60 | }␊ |
61 | iterator operator++(int)␊ |
62 | {␊ |
63 | iterator out = *this;␊ |
64 | ++*this;␊ |
65 | return out;␊ |
66 | }␊ |
67 | value_type & operator*()␊ |
68 | {␊ |
69 | I(valid);␊ |
70 | if (ordered)␊ |
71 | return *o;␊ |
72 | else␊ |
73 | return *u;␊ |
74 | }␊ |
75 | value_type const & operator*() const␊ |
76 | {␊ |
77 | I(valid);␊ |
78 | if (ordered)␊ |
79 | return *o;␊ |
80 | else␊ |
81 | return *u;␊ |
82 | }␊ |
83 | value_type * operator->()␊ |
84 | {␊ |
85 | I(valid);␊ |
86 | if (ordered)␊ |
87 | return o.operator->();␊ |
88 | else␊ |
89 | return u.operator->();␊ |
90 | }␊ |
91 | value_type const * operator->() const␊ |
92 | {␊ |
93 | I(valid);␊ |
94 | if (ordered)␊ |
95 | return o.operator->();␊ |
96 | else␊ |
97 | return u.operator->();␊ |
98 | }␊ |
99 | bool operator==(iterator const & other) const␊ |
100 | {␊ |
101 | return (valid == other.valid) && (!valid || (*this)->first == other->first);␊ |
102 | }␊ |
103 | bool operator!=(iterator const & other) const␊ |
104 | {␊ |
105 | return !(*this == other);␊ |
106 | }␊ |
107 | };␊ |
108 | class const_iterator␊ |
109 | {␊ |
110 | friend class hybrid_map<Key, Val>;␊ |
111 | bool ordered;␊ |
112 | bool valid;␊ |
113 | typename omap::const_iterator o;␊ |
114 | typename umap::const_iterator u;␊ |
115 | hybrid_map<Key, Val> const * n;␊ |
116 | public:␊ |
117 | const_iterator(hybrid_map<Key, Val> const * n,␊ |
118 | ␉␉ typename omap::const_iterator const & i)␊ |
119 | : ordered(true), valid(i != n->ordered.end()), o(i), n(n)␊ |
120 | {}␊ |
121 | const_iterator(hybrid_map<Key, Val> const * n,␊ |
122 | ␉␉ typename umap::const_iterator const & i)␊ |
123 | : ordered(false), valid(i != n->unordered.end()), u(i), n(n)␊ |
124 | {}␊ |
125 | const_iterator(iterator const & i)␊ |
126 | : ordered(i.ordered), valid(i.valid), o(i.o), u(i.u), n(i.n)␊ |
127 | {}␊ |
128 | const_iterator()␊ |
129 | : valid(false)␊ |
130 | {}␊ |
131 | const_iterator & operator++()␊ |
132 | {␊ |
133 | I(valid);␊ |
134 | if (!ordered)␊ |
135 | {␊ |
136 | ordered = true;␊ |
137 | o = n->ordered.find(u->first);␊ |
138 | }␊ |
139 | ++o;␊ |
140 | valid = (o != n->ordered.end());␊ |
141 | return *this;␊ |
142 | }␊ |
143 | const_iterator operator++(int)␊ |
144 | {␊ |
145 | const_iterator out = *this;␊ |
146 | ++*this;␊ |
147 | return out;␊ |
148 | }␊ |
149 | value_type const & operator*() const␊ |
150 | {␊ |
151 | I(valid);␊ |
152 | if (ordered)␊ |
153 | return *o;␊ |
154 | else␊ |
155 | return *u;␊ |
156 | }␊ |
157 | value_type const * operator->() const␊ |
158 | {␊ |
159 | I(valid);␊ |
160 | if (ordered)␊ |
161 | return o.operator->();␊ |
162 | else␊ |
163 | return u.operator->();␊ |
164 | }␊ |
165 | bool operator==(const_iterator const & other) const␊ |
166 | {␊ |
167 | return (valid == other.valid) && (!valid || (*this)->first == other->first);␊ |
168 | }␊ |
169 | bool operator!=(const_iterator const & other) const␊ |
170 | {␊ |
171 | return !(*this == other);␊ |
172 | }␊ |
173 | };␊ |
174 | friend class iterator;␊ |
175 | friend class const_iterator;␊ |
176 | iterator begin()␊ |
177 | {␊ |
178 | return iterator(this, ordered.begin());␊ |
179 | }␊ |
180 | iterator end()␊ |
181 | {␊ |
182 | return iterator(this, ordered.end());␊ |
183 | }␊ |
184 | iterator find(key_type const & k)␊ |
185 | {␊ |
186 | return iterator(this, unordered.find(k));␊ |
187 | }␊ |
188 | const_iterator begin() const␊ |
189 | {␊ |
190 | return const_iterator(this, ordered.begin());␊ |
191 | }␊ |
192 | const_iterator end() const␊ |
193 | {␊ |
194 | return const_iterator(this, ordered.end());␊ |
195 | }␊ |
196 | const_iterator find(key_type const & k) const␊ |
197 | {␊ |
198 | return const_iterator(this, unordered.find(k));␊ |
199 | }␊ |
200 | size_t size() const␊ |
201 | {␊ |
202 | return ordered.size();␊ |
203 | }␊ |
204 | std::pair<iterator, bool> insert(value_type const & x)␊ |
205 | {␊ |
206 | std::pair<typename omap::iterator, bool> o = ordered.insert(x);␊ |
207 | unordered.insert(x);␊ |
208 | std::pair<iterator, bool> out;␊ |
209 | out.first = iterator(this, o.first);␊ |
210 | out.second = o.second;␊ |
211 | return out;␊ |
212 | }␊ |
213 | iterator insert(iterator const & where, value_type const & what)␊ |
214 | {␊ |
215 | unordered.insert(what);␊ |
216 | if (where.valid && where.ordered)␊ |
217 | {␊ |
218 | return iterator(this, ordered.insert(where.o, what));␊ |
219 | }␊ |
220 | else if (!where.valid)␊ |
221 | {␊ |
222 | return iterator(this, ordered.insert(ordered.end(), what));␊ |
223 | }␊ |
224 | else␊ |
225 | {␊ |
226 | std::pair<typename omap::iterator, bool> o = ordered.insert(what);␊ |
227 | return iterator(this, o.first);␊ |
228 | }␊ |
229 | }␊ |
230 | size_t erase(key_type const & x)␊ |
231 | {␊ |
232 | size_t out = ordered.erase(x);␊ |
233 | unordered.erase(x);␊ |
234 | return out;␊ |
235 | }␊ |
236 | bool empty() const␊ |
237 | {␊ |
238 | return ordered.empty();␊ |
239 | }␊ |
240 | void clear()␊ |
241 | {␊ |
242 | ordered.clear();␊ |
243 | unordered.clear();␊ |
244 | }␊ |
245 | };␊ |
246 | ␊ |
247 | ␊ |
248 | #endif␊ |