| 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␊ |
