(svn r25348) -Add: multimap implementation with guaranteed order between equal keys

1 files changed, 388 insertions, 0 deletions

diff --git a/src/core/multimap.hpp b/src/core/multimap.hpp
new file mode 100644
index 000000000..e90667714
--- /dev/null
+++ b/src/core/multimap.hpp
@@ -0,0 +1,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 */