summaryrefslogtreecommitdiff
path: root/src/core
diff options
context:
space:
mode:
authorfonsinchen <fonsinchen@openttd.org>2013-06-09 12:52:11 +0000
committerfonsinchen <fonsinchen@openttd.org>2013-06-09 12:52:11 +0000
commit4fd57501bbc914eb973a397b24be0d2dbe51d007 (patch)
tree52f90a356dee0081c8ac7be3a8131f44c21febe8 /src/core
parentdfad8317aa566efffb971455b42bfdecbaee5985 (diff)
downloadopenttd-4fd57501bbc914eb973a397b24be0d2dbe51d007.tar.xz
(svn r25348) -Add: multimap implementation with guaranteed order between equal keys
Diffstat (limited to 'src/core')
-rw-r--r--src/core/multimap.hpp388
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 */