OpenTTD
multimap.hpp
Go to the documentation of this file.
1 /* $Id: multimap.hpp 25371 2013-06-09 13:18:37Z rubidium $ */
2 
3 /*
4  * This file is part of OpenTTD.
5  * 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.
6  * 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.
7  * 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/>.
8  */
9 
12 #ifndef MULTIMAP_HPP
13 #define MULTIMAP_HPP
14 
15 #include <map>
16 #include <list>
17 
18 template<typename Tkey, typename Tvalue, typename Tcompare>
19 class MultiMap;
20 
29 template<class Tmap_iter, class Tlist_iter, class Tkey, class Tvalue, class Tcompare>
31 protected:
32  friend class MultiMap<Tkey, Tvalue, Tcompare>;
34 
35  Tlist_iter list_iter;
36  Tmap_iter map_iter;
37 
47  bool list_valid;
48 
49 public:
53  MultiMapIterator() : list_valid(false) {}
54 
61  template<class Tnon_const>
62  MultiMapIterator(Tnon_const mi) : map_iter(mi), list_valid(false) {}
63 
71  MultiMapIterator(Tmap_iter mi, Tlist_iter li) : list_iter(li), map_iter(mi)
72  {
73  this->list_valid = (this->list_iter != this->map_iter->second.begin());
74  }
75 
82  template<class Tnon_const>
83  Self &operator=(Tnon_const mi)
84  {
85  this->map_iter = mi;
86  this->list_valid = false;
87  return *this;
88  }
89 
95  Tvalue &operator*() const
96  {
97  assert(!this->map_iter->second.empty());
98  return this->list_valid ?
99  this->list_iter.operator*() :
100  this->map_iter->second.begin().operator*();
101  }
102 
107  Tvalue *operator->() const
108  {
109  assert(!this->map_iter->second.empty());
110  return this->list_valid ?
111  this->list_iter.operator->() :
112  this->map_iter->second.begin().operator->();
113  }
114 
115  inline const Tmap_iter &GetMapIter() const { return this->map_iter; }
116  inline const Tlist_iter &GetListIter() const { return this->list_iter; }
117  inline bool ListValid() const { return this->list_valid; }
118 
119  const Tkey &GetKey() const { return this->map_iter->first; }
120 
127  Self &operator++()
128  {
129  assert(!this->map_iter->second.empty());
130  if (this->list_valid) {
131  if (++this->list_iter == this->map_iter->second.end()) {
132  ++this->map_iter;
133  this->list_valid = false;
134  }
135  } else {
136  this->list_iter = ++(this->map_iter->second.begin());
137  if (this->list_iter == this->map_iter->second.end()) {
138  ++this->map_iter;
139  } else {
140  this->list_valid = true;
141  }
142  }
143  return *this;
144  }
145 
152  Self operator++(int)
153  {
154  Self tmp = *this;
155  this->operator++();
156  return tmp;
157  }
158 
164  Self &operator--()
165  {
166  assert(!this->map_iter->second.empty());
167  if (!this->list_valid) {
168  --this->map_iter;
169  this->list_iter = this->map_iter->second.end();
170  assert(!this->map_iter->second.empty());
171  }
172 
173  this->list_valid = (--this->list_iter != this->map_iter->second.begin());
174  return *this;
175  }
176 
183  Self operator--(int)
184  {
185  Self tmp = *this;
186  this->operator--();
187  return tmp;
188  }
189 };
190 
191 /* Generic comparison functions for const/non-const MultiMap iterators and map iterators */
192 
204 template<class Tmap_iter1, class Tlist_iter1, class Tmap_iter2, class Tlist_iter2, class Tkey, class Tvalue1, class Tvalue2, class Tcompare>
206 {
207  if (iter1.GetMapIter() != iter2.GetMapIter()) return false;
208  if (!iter1.ListValid()) return !iter2.ListValid();
209  return iter2.ListValid() ?
210  iter1.GetListIter() == iter2.GetListIter() : false;
211 }
212 
221 template<class Tmap_iter1, class Tlist_iter1, class Tmap_iter2, class Tlist_iter2, class Tkey, class Tvalue1, class Tvalue2, class Tcompare>
223 {
224  return !(iter1 == iter2);
225 }
226 
235 template<class Tmap_iter1, class Tlist_iter1, class Tmap_iter2, class Tkey, class Tvalue, class Tcompare >
237 {
238  return !iter1.ListValid() && iter1.GetMapIter() == iter2;
239 }
240 
247 template<class Tmap_iter1, class Tlist_iter1, class Tmap_iter2, class Tkey, class Tvalue, class Tcompare >
249 {
250  return iter1.ListValid() || iter1.GetMapIter() != iter2;
251 }
252 
259 template<class Tmap_iter1, class Tlist_iter1, class Tmap_iter2, class Tkey, class Tvalue, class Tcompare >
261 {
262  return !iter1.ListValid() && iter1.GetMapIter() == iter2;
263 }
264 
271 template<class Tmap_iter1, class Tlist_iter1, class Tmap_iter2, class Tkey, class Tvalue, class Tcompare >
273 {
274  return iter1.ListValid() || iter1.GetMapIter() != iter2;
275 }
276 
277 
285 template<typename Tkey, typename Tvalue, typename Tcompare = std::less<Tkey> >
286 class MultiMap : public std::map<Tkey, std::list<Tvalue>, Tcompare > {
287 public:
288  typedef typename std::list<Tvalue> List;
289  typedef typename List::iterator ListIterator;
290  typedef typename List::const_iterator ConstListIterator;
291 
292  typedef typename std::map<Tkey, List, Tcompare > Map;
293  typedef typename Map::iterator MapIterator;
294  typedef typename Map::const_iterator ConstMapIterator;
295 
298 
304  iterator erase(iterator it)
305  {
306  List &list = it.map_iter->second;
307  assert(!list.empty());
308  if (it.list_valid) {
309  it.list_iter = list.erase(it.list_iter);
310  /* This can't be the first list element as otherwise list_valid would have
311  * to be false. So the list cannot be empty here. */
312  if (it.list_iter == list.end()) {
313  ++it.map_iter;
314  it.list_valid = false;
315  }
316  } else {
317  list.erase(list.begin());
318  if (list.empty()) this->Map::erase(it.map_iter++);
319  }
320  return it;
321  }
322 
328  void Insert(const Tkey &key, const Tvalue &val)
329  {
330  List &list = (*this)[key];
331  list.push_back(val);
332  assert(!list.empty());
333  }
334 
339  size_t size() const
340  {
341  size_t ret = 0;
342  for (ConstMapIterator it = this->Map::begin(); it != this->Map::end(); ++it) {
343  ret += it->second.size();
344  }
345  return ret;
346  }
347 
352  size_t MapSize() const
353  {
354  return this->Map::size();
355  }
356 
362  std::pair<iterator, iterator> equal_range(const Tkey &key)
363  {
364  MapIterator begin(this->lower_bound(key));
365  if (begin != this->Map::end() && begin->first == key) {
366  MapIterator end = begin;
367  return std::make_pair(begin, ++end);
368  }
369  return std::make_pair(begin, begin);
370  }
371 
377  std::pair<const_iterator, const_iterator> equal_range(const Tkey &key) const
378  {
379  ConstMapIterator begin(this->lower_bound(key));
380  if (begin != this->Map::end() && begin->first == key) {
381  ConstMapIterator end = begin;
382  return std::make_pair(begin, ++end);
383  }
384  return std::make_pair(begin, begin);
385  }
386 };
387 
388 #endif /* MULTIMAP_HPP */
Self & operator++()
Prefix increment operator.
Definition: multimap.hpp:127
STL-style iterator for MultiMap.
Definition: multimap.hpp:30
Self & operator=(Tnon_const mi)
Assignment iterator like constructor with the same signature.
Definition: multimap.hpp:83
Self & operator--()
Prefix decrement operator.
Definition: multimap.hpp:164
size_t size() const
Count all items in this MultiMap.
Definition: multimap.hpp:339
MultiMapIterator(Tnon_const mi)
Constructor to allow possibly const iterators to be assigned from possibly non-const map iterators...
Definition: multimap.hpp:62
bool list_valid
Flag to show that the iterator has just "walked" a step in the map.
Definition: multimap.hpp:47
Hand-rolled multimap as map of lists.
Definition: multimap.hpp:19
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:222
MultiMapIterator(Tmap_iter mi, Tlist_iter li)
Constructor to allow specifying an exact position in map and list.
Definition: multimap.hpp:71
Tvalue * operator->() const
Same as operator*(), but returns a pointer.
Definition: multimap.hpp:107
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:205
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:362
Self operator--(int)
Postfix decrement operator.
Definition: multimap.hpp:183
Tmap_iter map_iter
Iterator pointing to the position of the current list of items with equal keys in the map...
Definition: multimap.hpp:36
iterator erase(iterator it)
Erase the value pointed to by an iterator.
Definition: multimap.hpp:304
size_t MapSize() const
Count the number of ranges with equal keys in this MultiMap.
Definition: multimap.hpp:352
Tlist_iter list_iter
Iterator pointing to current position in the current list of items with equal keys.
Definition: multimap.hpp:35
Self operator++(int)
Postfix increment operator.
Definition: multimap.hpp:152
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:377
MultiMapIterator()
Simple, dangerous constructor to allow later assignment with operator=.
Definition: multimap.hpp:53
Tvalue & operator*() const
Dereference operator.
Definition: multimap.hpp:95
void Insert(const Tkey &key, const Tvalue &val)
Insert a value at the end of the range with the specified key.
Definition: multimap.hpp:328