OpenTTD Source  1.11.0-beta2
multimap.hpp
Go to the documentation of this file.
1 /*
2  * This file is part of OpenTTD.
3  * 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.
4  * 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.
5  * 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/>.
6  */
7 
10 #ifndef MULTIMAP_HPP
11 #define MULTIMAP_HPP
12 
13 #include <map>
14 #include <list>
15 
16 template<typename Tkey, typename Tvalue, typename Tcompare>
17 class MultiMap;
18 
27 template<class Tmap_iter, class Tlist_iter, class Tkey, class Tvalue, class Tcompare>
29 protected:
30  friend class MultiMap<Tkey, Tvalue, Tcompare>;
32 
33  Tlist_iter list_iter;
34  Tmap_iter map_iter;
35 
45  bool list_valid;
46 
47 public:
52 
59  template<class Tnon_const>
60  MultiMapIterator(Tnon_const mi) : map_iter(mi), list_valid(false) {}
61 
69  MultiMapIterator(Tmap_iter mi, Tlist_iter li) : list_iter(li), map_iter(mi)
70  {
71  this->list_valid = (this->list_iter != this->map_iter->second.begin());
72  }
73 
80  template<class Tnon_const>
81  Self &operator=(Tnon_const mi)
82  {
83  this->map_iter = mi;
84  this->list_valid = false;
85  return *this;
86  }
87 
93  Tvalue &operator*() const
94  {
95  assert(!this->map_iter->second.empty());
96  return this->list_valid ?
97  this->list_iter.operator*() :
98  this->map_iter->second.begin().operator*();
99  }
100 
105  Tvalue *operator->() const
106  {
107  assert(!this->map_iter->second.empty());
108  return this->list_valid ?
109  this->list_iter.operator->() :
110  this->map_iter->second.begin().operator->();
111  }
112 
113  inline const Tmap_iter &GetMapIter() const { return this->map_iter; }
114  inline const Tlist_iter &GetListIter() const { return this->list_iter; }
115  inline bool ListValid() const { return this->list_valid; }
116 
117  const Tkey &GetKey() const { return this->map_iter->first; }
118 
126  {
127  assert(!this->map_iter->second.empty());
128  if (this->list_valid) {
129  if (++this->list_iter == this->map_iter->second.end()) {
130  ++this->map_iter;
131  this->list_valid = false;
132  }
133  } else {
134  this->list_iter = ++(this->map_iter->second.begin());
135  if (this->list_iter == this->map_iter->second.end()) {
136  ++this->map_iter;
137  } else {
138  this->list_valid = true;
139  }
140  }
141  return *this;
142  }
143 
151  {
152  Self tmp = *this;
153  this->operator++();
154  return tmp;
155  }
156 
163  {
164  assert(!this->map_iter->second.empty());
165  if (!this->list_valid) {
166  --this->map_iter;
167  this->list_iter = this->map_iter->second.end();
168  assert(!this->map_iter->second.empty());
169  }
170 
171  this->list_valid = (--this->list_iter != this->map_iter->second.begin());
172  return *this;
173  }
174 
182  {
183  Self tmp = *this;
184  this->operator--();
185  return tmp;
186  }
187 };
188 
189 /* Generic comparison functions for const/non-const MultiMap iterators and map iterators */
190 
202 template<class Tmap_iter1, class Tlist_iter1, class Tmap_iter2, class Tlist_iter2, class Tkey, class Tvalue1, class Tvalue2, class Tcompare>
204 {
205  if (iter1.GetMapIter() != iter2.GetMapIter()) return false;
206  if (!iter1.ListValid()) return !iter2.ListValid();
207  return iter2.ListValid() ?
208  iter1.GetListIter() == iter2.GetListIter() : false;
209 }
210 
219 template<class Tmap_iter1, class Tlist_iter1, class Tmap_iter2, class Tlist_iter2, class Tkey, class Tvalue1, class Tvalue2, class Tcompare>
221 {
222  return !(iter1 == iter2);
223 }
224 
233 template<class Tmap_iter1, class Tlist_iter1, class Tmap_iter2, class Tkey, class Tvalue, class Tcompare >
235 {
236  return !iter1.ListValid() && iter1.GetMapIter() == iter2;
237 }
238 
245 template<class Tmap_iter1, class Tlist_iter1, class Tmap_iter2, class Tkey, class Tvalue, class Tcompare >
247 {
248  return iter1.ListValid() || iter1.GetMapIter() != iter2;
249 }
250 
257 template<class Tmap_iter1, class Tlist_iter1, class Tmap_iter2, class Tkey, class Tvalue, class Tcompare >
259 {
260  return !iter1.ListValid() && iter1.GetMapIter() == iter2;
261 }
262 
269 template<class Tmap_iter1, class Tlist_iter1, class Tmap_iter2, class Tkey, class Tvalue, class Tcompare >
271 {
272  return iter1.ListValid() || iter1.GetMapIter() != iter2;
273 }
274 
275 
283 template<typename Tkey, typename Tvalue, typename Tcompare = std::less<Tkey> >
284 class MultiMap : public std::map<Tkey, std::list<Tvalue>, Tcompare > {
285 public:
286  typedef typename std::list<Tvalue> List;
287  typedef typename List::iterator ListIterator;
288  typedef typename List::const_iterator ConstListIterator;
289 
290  typedef typename std::map<Tkey, List, Tcompare > Map;
291  typedef typename Map::iterator MapIterator;
292  typedef typename Map::const_iterator ConstMapIterator;
293 
296 
303  {
304  List &list = it.map_iter->second;
305  assert(!list.empty());
306  if (it.list_valid) {
307  it.list_iter = list.erase(it.list_iter);
308  /* This can't be the first list element as otherwise list_valid would have
309  * to be false. So the list cannot be empty here. */
310  if (it.list_iter == list.end()) {
311  ++it.map_iter;
312  it.list_valid = false;
313  }
314  } else {
315  list.erase(list.begin());
316  if (list.empty()) this->Map::erase(it.map_iter++);
317  }
318  return it;
319  }
320 
326  void Insert(const Tkey &key, const Tvalue &val)
327  {
328  List &list = (*this)[key];
329  list.push_back(val);
330  assert(!list.empty());
331  }
332 
337  size_t size() const
338  {
339  size_t ret = 0;
340  for (ConstMapIterator it = this->Map::begin(); it != this->Map::end(); ++it) {
341  ret += it->second.size();
342  }
343  return ret;
344  }
345 
350  size_t MapSize() const
351  {
352  return this->Map::size();
353  }
354 
360  std::pair<iterator, iterator> equal_range(const Tkey &key)
361  {
362  MapIterator begin(this->lower_bound(key));
363  if (begin != this->Map::end() && begin->first == key) {
364  MapIterator end = begin;
365  return std::make_pair(begin, ++end);
366  }
367  return std::make_pair(begin, begin);
368  }
369 
375  std::pair<const_iterator, const_iterator> equal_range(const Tkey &key) const
376  {
377  ConstMapIterator begin(this->lower_bound(key));
378  if (begin != this->Map::end() && begin->first == key) {
379  ConstMapIterator end = begin;
380  return std::make_pair(begin, ++end);
381  }
382  return std::make_pair(begin, begin);
383  }
384 };
385 
386 #endif /* MULTIMAP_HPP */
MultiMap::size
size_t size() const
Count all items in this MultiMap.
Definition: multimap.hpp:337
MultiMapIterator::operator->
Tvalue * operator->() const
Same as operator*(), but returns a pointer.
Definition: multimap.hpp:105
MultiMapIterator::map_iter
Tmap_iter map_iter
Iterator pointing to the position of the current list of items with equal keys in the map.
Definition: multimap.hpp:34
MultiMapIterator::operator--
Self operator--(int)
Postfix decrement operator.
Definition: multimap.hpp:181
MultiMapIterator::list_iter
Tlist_iter list_iter
Iterator pointing to current position in the current list of items with equal keys.
Definition: multimap.hpp:33
MultiMapIterator::operator++
Self & operator++()
Prefix increment operator.
Definition: multimap.hpp:125
MultiMap::erase
iterator erase(iterator it)
Erase the value pointed to by an iterator.
Definition: multimap.hpp:302
MultiMapIterator::operator*
Tvalue & operator*() const
Dereference operator.
Definition: multimap.hpp:93
MultiMap::MapSize
size_t MapSize() const
Count the number of ranges with equal keys in this MultiMap.
Definition: multimap.hpp:350
MultiMapIterator::operator++
Self operator++(int)
Postfix increment operator.
Definition: multimap.hpp:150
operator==
bool operator==(const MultiMapIterator< Tmap_iter1, Tlist_iter1, Tkey, Tvalue1, Tcompare > &iter1, const MultiMapIterator< Tmap_iter2, Tlist_iter2, Tkey, Tvalue2, Tcompare > &iter2)
Compare two MultiMap iterators.
Definition: multimap.hpp:203
MultiMap::equal_range
std::pair< const_iterator, const_iterator > equal_range(const Tkey &key) const
Get a pair of constant iterators specifying a range of items with equal keys.
Definition: multimap.hpp:375
MultiMapIterator::MultiMapIterator
MultiMapIterator()
Simple, dangerous constructor to allow later assignment with operator=.
Definition: multimap.hpp:51
MultiMap::equal_range
std::pair< iterator, iterator > equal_range(const Tkey &key)
Get a pair of iterators specifying a range of items with equal keys.
Definition: multimap.hpp:360
MultiMapIterator
STL-style iterator for MultiMap.
Definition: multimap.hpp:28
MultiMapIterator::operator--
Self & operator--()
Prefix decrement operator.
Definition: multimap.hpp:162
MultiMapIterator::operator=
Self & operator=(Tnon_const mi)
Assignment iterator like constructor with the same signature.
Definition: multimap.hpp:81
MultiMapIterator::MultiMapIterator
MultiMapIterator(Tnon_const mi)
Constructor to allow possibly const iterators to be assigned from possibly non-const map iterators.
Definition: multimap.hpp:60
operator!=
bool operator!=(const MultiMapIterator< Tmap_iter1, Tlist_iter1, Tkey, Tvalue1, Tcompare > &iter1, const MultiMapIterator< Tmap_iter2, Tlist_iter2, Tkey, Tvalue2, Tcompare > &iter2)
Inverse of operator==().
Definition: multimap.hpp:220
MultiMapIterator::MultiMapIterator
MultiMapIterator(Tmap_iter mi, Tlist_iter li)
Constructor to allow specifying an exact position in map and list.
Definition: multimap.hpp:69
MultiMap
Hand-rolled multimap as map of lists.
Definition: multimap.hpp:17
MultiMap::Insert
void Insert(const Tkey &key, const Tvalue &val)
Insert a value at the end of the range with the specified key.
Definition: multimap.hpp:326
MultiMapIterator::list_valid
bool list_valid
Flag to show that the iterator has just "walked" a step in the map.
Definition: multimap.hpp:45