Files
@ r25339:28c15705f6a3
Branch filter:
Location: cpp/openttd-patchpack/source/src/core/multimap.hpp
r25339:28c15705f6a3
13.4 KiB
text/x-c++hdr
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 | /*
* This file is part of OpenTTD.
* OpenTTD is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, version 2.
* OpenTTD is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
* See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with OpenTTD. If not, see <http://www.gnu.org/licenses/>.
*/
/** @file multimap.hpp Multimap with deterministic ordering of items with equal keys. */
#ifndef MULTIMAP_HPP
#define MULTIMAP_HPP
#include <map>
#include <list>
template<typename Tkey, typename Tvalue, typename Tcompare>
class MultiMap;
/**
* STL-style iterator for MultiMap.
* @tparam Tmap_iter Iterator type for the map in the MultiMap.
* @tparam Tlist_iter Iterator type for the lists in the MultiMap.
* @tparam Tkey Key type of the MultiMap.
* @tparam Tvalue Value type of the MultMap.
* @tparam Tcompare Comparator type for keys of the MultiMap.
*/
template<class Tmap_iter, class Tlist_iter, class Tkey, class Tvalue, class Tcompare>
class MultiMapIterator {
protected:
friend class MultiMap<Tkey, Tvalue, Tcompare>;
typedef MultiMapIterator<Tmap_iter, Tlist_iter, Tkey, Tvalue, Tcompare> Self;
Tlist_iter list_iter; ///< Iterator pointing to current position in the current list of items with equal keys.
Tmap_iter map_iter; ///< Iterator pointing to the position of the current list of items with equal keys in the map.
/**
* Flag to show that the iterator has just "walked" a step in the map.
* We cannot check the current list for that as we might have reached end() of the map. In that case we'd need to
* set list_iter to some sort of "invalid" state, but that's impossible as operator== yields undefined behaviour
* if the iterators don't belong to the same list and there is no list at end(). So if we created a static empty
* list and an "invalid" iterator in that we could not determine if the iterator is invalid while it's valid. We
* can also not determine if the map iterator is valid while we don't have the map; so in the end it's easiest to
* just introduce an extra flag.
*/
bool list_valid;
public:
/**
* Simple, dangerous constructor to allow later assignment with operator=.
*/
MultiMapIterator() : list_valid(false) {}
/**
* Constructor to allow possibly const iterators to be assigned from possibly
* non-const map iterators. You can assign end() like this.
* @tparam Tnon_const Iterator type assignable to Tmap_iter (which might be const).
* @param mi One such iterator.
*/
template<class Tnon_const>
MultiMapIterator(Tnon_const mi) : map_iter(mi), list_valid(false) {}
/**
* Constructor to allow specifying an exact position in map and list. You cannot
* construct end() like this as the constructor will actually check li and mi->second
* for list_valid.
* @param mi Iterator in the map.
* @param li Iterator in the list.
*/
MultiMapIterator(Tmap_iter mi, Tlist_iter li) : list_iter(li), map_iter(mi)
{
this->list_valid = (this->list_iter != this->map_iter->second.begin());
}
/**
* Assignment iterator like constructor with the same signature.
* @tparam Tnon_const Iterator type assignable to Tmap_iter (which might be const).
* @param mi One such iterator.
* @return This iterator.
*/
template<class Tnon_const>
Self &operator=(Tnon_const mi)
{
this->map_iter = mi;
this->list_valid = false;
return *this;
}
/**
* Dereference operator. Works just like usual STL operator*() on various containers.
* Doesn't do a lot of checks for sanity, just like STL.
* @return The value associated with the item this iterator points to.
*/
Tvalue &operator*() const
{
assert(!this->map_iter->second.empty());
return this->list_valid ?
this->list_iter.operator*() :
this->map_iter->second.begin().operator*();
}
/**
* Same as operator*(), but returns a pointer.
* @return Pointer to the value this iterator points to.
*/
Tvalue *operator->() const
{
assert(!this->map_iter->second.empty());
return this->list_valid ?
this->list_iter.operator->() :
this->map_iter->second.begin().operator->();
}
inline const Tmap_iter &GetMapIter() const { return this->map_iter; }
inline const Tlist_iter &GetListIter() const { return this->list_iter; }
inline bool ListValid() const { return this->list_valid; }
const Tkey &GetKey() const { return this->map_iter->first; }
/**
* Prefix increment operator. Increment the iterator and set it to the
* next item in the MultiMap. This either increments the list iterator
* or the map iterator and sets list_valid accordingly.
* @return This iterator after incrementing.
*/
Self &operator++()
{
assert(!this->map_iter->second.empty());
if (this->list_valid) {
if (++this->list_iter == this->map_iter->second.end()) {
++this->map_iter;
this->list_valid = false;
}
} else {
this->list_iter = ++(this->map_iter->second.begin());
if (this->list_iter == this->map_iter->second.end()) {
++this->map_iter;
} else {
this->list_valid = true;
}
}
return *this;
}
/**
* Postfix increment operator. Same as prefix increment, but return the
* previous state.
* @param dummy param to mark postfix.
* @return This iterator before incrementing.
*/
Self operator++(int)
{
Self tmp = *this;
this->operator++();
return tmp;
}
/**
* Prefix decrement operator. Decrement the iterator and set it to the
* previous item in the MultiMap.
* @return This iterator after decrementing.
*/
Self &operator--()
{
assert(!this->map_iter->second.empty());
if (!this->list_valid) {
--this->map_iter;
this->list_iter = this->map_iter->second.end();
assert(!this->map_iter->second.empty());
}
this->list_valid = (--this->list_iter != this->map_iter->second.begin());
return *this;
}
/**
* Postfix decrement operator. Same as prefix decrement, but return the
* previous state.
* @param dummy param to mark postfix.
* @return This iterator before decrementing.
*/
Self operator--(int)
{
Self tmp = *this;
this->operator--();
return tmp;
}
};
/* Generic comparison functions for const/non-const MultiMap iterators and map iterators */
/**
* Compare two MultiMap iterators. Iterators are equal if
* 1. Their map iterators are equal.
* 2. They agree about list_valid.
* 3. If list_valid they agree about list_iter.
* Lots of template parameters to make all possible const and non-const types of MultiMap iterators
* (on maps with const and non-const values) comparable to each other.
* @param iter1 First iterator to compare.
* @param iter2 Second iterator to compare.
* @return If iter1 and iter2 are equal.
*/
template<class Tmap_iter1, class Tlist_iter1, class Tmap_iter2, class Tlist_iter2, class Tkey, class Tvalue1, class Tvalue2, class Tcompare>
bool operator==(const MultiMapIterator<Tmap_iter1, Tlist_iter1, Tkey, Tvalue1, Tcompare> &iter1, const MultiMapIterator<Tmap_iter2, Tlist_iter2, Tkey, Tvalue2, Tcompare> &iter2)
{
if (iter1.GetMapIter() != iter2.GetMapIter()) return false;
if (!iter1.ListValid()) return !iter2.ListValid();
return iter2.ListValid() ?
iter1.GetListIter() == iter2.GetListIter() : false;
}
/**
* Inverse of operator==().
* Lots of template parameters to make all possible const and non-const types of MultiMap iterators
* (on maps with const and non-const values) comparable to each other.
* @param iter1 First iterator to compare.
* @param iter2 Second iterator to compare.
* @return If iter1 and iter2 are not equal.
*/
template<class Tmap_iter1, class Tlist_iter1, class Tmap_iter2, class Tlist_iter2, class Tkey, class Tvalue1, class Tvalue2, class Tcompare>
bool operator!=(const MultiMapIterator<Tmap_iter1, Tlist_iter1, Tkey, Tvalue1, Tcompare> &iter1, const MultiMapIterator<Tmap_iter2, Tlist_iter2, Tkey, Tvalue2, Tcompare> &iter2)
{
return !(iter1 == iter2);
}
/**
* Check if a MultiMap iterator is at the begin of a list pointed to by the given map iterator.
* Lots of template parameters to make all possible const and non-const types of MultiMap iterators
* (on maps with const and non-const values) comparable to all possible types of map iterators.
* @param iter1 MultiMap iterator.
* @param iter2 Map iterator.
* @return If iter1 points to the begin of the list pointed to by iter2.
*/
template<class Tmap_iter1, class Tlist_iter1, class Tmap_iter2, class Tkey, class Tvalue, class Tcompare >
bool operator==(const MultiMapIterator<Tmap_iter1, Tlist_iter1, Tkey, Tvalue, Tcompare> &iter1, const Tmap_iter2 &iter2)
{
return !iter1.ListValid() && iter1.GetMapIter() == iter2;
}
/**
* Inverse of operator==() with same signature.
* @param iter1 MultiMap iterator.
* @param iter2 Map iterator.
* @return If iter1 doesn't point to the begin of the list pointed to by iter2.
*/
template<class Tmap_iter1, class Tlist_iter1, class Tmap_iter2, class Tkey, class Tvalue, class Tcompare >
bool operator!=(const MultiMapIterator<Tmap_iter1, Tlist_iter1, Tkey, Tvalue, Tcompare> &iter1, const Tmap_iter2 &iter2)
{
return iter1.ListValid() || iter1.GetMapIter() != iter2;
}
/**
* Same as operator==() with reversed order of arguments.
* @param iter2 Map iterator.
* @param iter1 MultiMap iterator.
* @return If iter1 points to the begin of the list pointed to by iter2.
*/
template<class Tmap_iter1, class Tlist_iter1, class Tmap_iter2, class Tkey, class Tvalue, class Tcompare >
bool operator==(const Tmap_iter2 &iter2, const MultiMapIterator<Tmap_iter1, Tlist_iter1, Tkey, Tvalue, Tcompare> &iter1)
{
return !iter1.ListValid() && iter1.GetMapIter() == iter2;
}
/**
* Same as operator!=() with reversed order of arguments.
* @param iter2 Map iterator.
* @param iter1 MultiMap iterator.
* @return If iter1 doesn't point to the begin of the list pointed to by iter2.
*/
template<class Tmap_iter1, class Tlist_iter1, class Tmap_iter2, class Tkey, class Tvalue, class Tcompare >
bool operator!=(const Tmap_iter2 &iter2, const MultiMapIterator<Tmap_iter1, Tlist_iter1, Tkey, Tvalue, Tcompare> &iter1)
{
return iter1.ListValid() || iter1.GetMapIter() != iter2;
}
/**
* Hand-rolled multimap as map of lists. Behaves mostly like a list, but is sorted
* by Tkey so that you can easily look up ranges of equal keys. Those ranges are
* internally ordered in a deterministic way (contrary to STL multimap). All
* STL-compatible members are named in STL style, all others are named in OpenTTD
* style.
*/
template<typename Tkey, typename Tvalue, typename Tcompare = std::less<Tkey> >
class MultiMap : public std::map<Tkey, std::list<Tvalue>, Tcompare > {
public:
typedef typename std::list<Tvalue> List;
typedef typename List::iterator ListIterator;
typedef typename List::const_iterator ConstListIterator;
typedef typename std::map<Tkey, List, Tcompare > Map;
typedef typename Map::iterator MapIterator;
typedef typename Map::const_iterator ConstMapIterator;
typedef MultiMapIterator<MapIterator, ListIterator, Tkey, Tvalue, Tcompare> iterator;
typedef MultiMapIterator<ConstMapIterator, ConstListIterator, Tkey, const Tvalue, Tcompare> const_iterator;
/**
* Erase the value pointed to by an iterator. The iterator may be invalid afterwards.
* @param it Iterator pointing at some value.
* @return Iterator to the element after the deleted one (or invalid).
*/
iterator erase(iterator it)
{
List &list = it.map_iter->second;
assert(!list.empty());
if (it.list_valid) {
it.list_iter = list.erase(it.list_iter);
/* This can't be the first list element as otherwise list_valid would have
* to be false. So the list cannot be empty here. */
if (it.list_iter == list.end()) {
++it.map_iter;
it.list_valid = false;
}
} else {
list.erase(list.begin());
if (list.empty()) this->Map::erase(it.map_iter++);
}
return it;
}
/**
* Insert a value at the end of the range with the specified key.
* @param key Key to be inserted at.
* @param val Value to be inserted.
*/
void Insert(const Tkey &key, const Tvalue &val)
{
List &list = (*this)[key];
list.push_back(val);
assert(!list.empty());
}
/**
* Count all items in this MultiMap. This involves iterating over the map.
* @return Number of items in the MultiMap.
*/
size_t size() const
{
size_t ret = 0;
for (ConstMapIterator it = this->Map::begin(); it != this->Map::end(); ++it) {
ret += it->second.size();
}
return ret;
}
/**
* Count the number of ranges with equal keys in this MultiMap.
* @return Number of ranges with equal keys.
*/
size_t MapSize() const
{
return this->Map::size();
}
/**
* Get a pair of iterators specifying a range of items with equal keys.
* @param key Key to look for.
* @return Range of items with given key.
*/
std::pair<iterator, iterator> equal_range(const Tkey &key)
{
MapIterator begin(this->lower_bound(key));
if (begin != this->Map::end() && begin->first == key) {
MapIterator end = begin;
return std::make_pair(begin, ++end);
}
return std::make_pair(begin, begin);
}
/**
* Get a pair of constant iterators specifying a range of items with equal keys.
* @param key Key to look for.
* @return Constant range of items with given key.
*/
std::pair<const_iterator, const_iterator> equal_range(const Tkey &key) const
{
ConstMapIterator begin(this->lower_bound(key));
if (begin != this->Map::end() && begin->first == key) {
ConstMapIterator end = begin;
return std::make_pair(begin, ++end);
}
return std::make_pair(begin, begin);
}
};
#endif /* MULTIMAP_HPP */
|