summaryrefslogtreecommitdiff
path: root/src/core/multimap.hpp
blob: e90667714173be0310160265719ac899ac0f8748 (plain)
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
387
388
/* $Id$ */

/*
 * 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 */