monotone

monotone Mtn Source Tree

Root/src/hybrid_map.hh

1// Copyright (C) 2007 Timothy Brownawell <tbrownaw@gmail.com>
2//
3// This program is made available under the GNU GPL version 2.0 or
4// greater. See the accompanying file COPYING for details.
5//
6// This program is distributed WITHOUT ANY WARRANTY; without even the
7// implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
8// PURPOSE.
9
10#ifndef __HYBRID_MAP_HH__
11#define __HYBRID_MAP_HH__
12
13#include "sanity.hh"
14#include "hash_map.hh"
15#include <map>
16
17template<typename Key, typename Val>
18class hybrid_map
19{
20 typedef std::map<Key, Val> omap;
21 typedef hashmap::hash_map<Key, Val> umap;
22 omap ordered;
23 umap unordered;
24public:
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
249
250// Local Variables:
251// mode: C++
252// fill-column: 76
253// c-file-style: "gnu"
254// indent-tabs-mode: nil
255// End:
256// vim: et:sw=2:sts=2:ts=2:cino=>2s,{s,\:s,+s,t0,g0,^-2,e-2,n-2,p2s,(0,=s:

Archive Download this file

Branches

Tags

Quick Links:     www.monotone.ca    -     Downloads    -     Documentation    -     Wiki    -     Code Forge    -     Build Status