diff options
Diffstat (limited to 'core/ordered_hash_map.h')
| -rw-r--r-- | core/ordered_hash_map.h | 315 |
1 files changed, 315 insertions, 0 deletions
diff --git a/core/ordered_hash_map.h b/core/ordered_hash_map.h new file mode 100644 index 0000000000..3e619d2b2e --- /dev/null +++ b/core/ordered_hash_map.h @@ -0,0 +1,315 @@ +/*************************************************************************/ +/* ordered_hash_map.h */ +/*************************************************************************/ +/* This file is part of: */ +/* GODOT ENGINE */ +/* http://www.godotengine.org */ +/*************************************************************************/ +/* Copyright (c) 2007-2017 Juan Linietsky, Ariel Manzur. */ +/* Copyright (c) 2014-2017 Godot Engine contributors (cf. AUTHORS.md) */ +/* */ +/* Permission is hereby granted, free of charge, to any person obtaining */ +/* a copy of this software and associated documentation files (the */ +/* "Software"), to deal in the Software without restriction, including */ +/* without limitation the rights to use, copy, modify, merge, publish, */ +/* distribute, sublicense, and/or sell copies of the Software, and to */ +/* permit persons to whom the Software is furnished to do so, subject to */ +/* the following conditions: */ +/* */ +/* The above copyright notice and this permission notice shall be */ +/* included in all copies or substantial portions of the Software. */ +/* */ +/* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, */ +/* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF */ +/* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.*/ +/* IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY */ +/* CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, */ +/* TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE */ +/* SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. */ +/*************************************************************************/ +#ifndef ORDERED_HASH_MAP_H +#define ORDERED_HASH_MAP_H + +#include "hash_map.h" +#include "list.h" +#include "pair.h" + +/** + * A hash map which allows to iterate elements in insertion order. + * Insertion, lookup, deletion have O(1) complexity. + * The API aims to be consistent with Map rather than HashMap, because the + * former is more frequently used and is more coherent with the rest of the + * codebase. + * Deletion during iteration is safe and will preserve the order. + */ +template <class K, class V, class Hasher = HashMapHasherDefault, class Comparator = HashMapComparatorDefault<K>, uint8_t MIN_HASH_TABLE_POWER = 3, uint8_t RELATIONSHIP = 8> +class OrderedHashMap { + typedef List<Pair<const K *, V> > InternalList; + typedef HashMap<K, typename InternalList::Element *, Hasher, Comparator, MIN_HASH_TABLE_POWER, RELATIONSHIP> InternalMap; + + InternalList list; + InternalMap map; + +public: + class Element { + friend class OrderedHashMap<K, V, Hasher, Comparator, MIN_HASH_TABLE_POWER, RELATIONSHIP>; + + typename InternalList::Element *list_element; + typename InternalList::Element *next_element; + typename InternalList::Element *prev_element; + + Element(typename InternalList::Element *p_element) { + list_element = p_element; + + if (list_element) { + next_element = list_element->next(); + prev_element = list_element->prev(); + } + } + + public: + _FORCE_INLINE_ Element() + : list_element(NULL), next_element(NULL), prev_element(NULL) { + } + + Element next() const { + return Element(next_element); + } + + Element prev() const { + return Element(prev_element); + } + + Element(const Element &other) + : list_element(other.list_element), + prev_element(other.prev_element), + next_element(other.next_element) { + } + + Element &operator=(const Element &other) { + list_element = other.list_element; + next_element = other.next_element; + prev_element = other.prev_element; + return *this; + } + + friend bool operator==(const Element &, const Element &); + friend bool operator!=(const Element &, const Element &); + + operator bool() const { + return (list_element != NULL); + } + + const K &key() const { + CRASH_COND(!list_element); + return *(list_element->get().first); + }; + + V &value() { + CRASH_COND(!list_element); + return list_element->get().second; + }; + + const V &value() const { + CRASH_COND(!list_element); + return list_element->get().second; + }; + + V &get() { + CRASH_COND(!list_element); + return list_element->get().second; + }; + + const V &get() const { + CRASH_COND(!list_element); + return list_element->get().second; + }; + }; + + class ConstElement { + friend class OrderedHashMap<K, V, Hasher, Comparator, MIN_HASH_TABLE_POWER, RELATIONSHIP>; + + const typename InternalList::Element *list_element; + + ConstElement(const typename InternalList::Element *p_element) + : list_element(p_element) { + } + + public: + _FORCE_INLINE_ ConstElement() + : list_element(NULL) { + } + + ConstElement(const ConstElement &other) + : list_element(other.list_element) { + } + + ConstElement &operator=(const ConstElement &other) { + list_element = other.list_element; + return *this; + } + + ConstElement next() const { + return ConstElement(list_element ? list_element->next() : NULL); + } + + ConstElement prev() const { + return ConstElement(list_element ? list_element->prev() : NULL); + } + + friend bool operator==(const ConstElement &, const ConstElement &); + friend bool operator!=(const ConstElement &, const ConstElement &); + + operator bool() const { + return (list_element != NULL); + } + + const K &key() const { + CRASH_COND(!list_element); + return *(list_element->get().first); + }; + + const V &value() const { + CRASH_COND(!list_element); + return list_element->get().second; + }; + + const V &get() const { + CRASH_COND(!list_element); + return list_element->get().second; + }; + }; + + ConstElement find(const K &p_key) const { + typename InternalList::Element **list_element = map.getptr(p_key); + if (list_element) { + return ConstElement(*list_element); + } + return ConstElement(NULL); + } + + Element find(const K &p_key) { + typename InternalList::Element **list_element = map.getptr(p_key); + if (list_element) { + return Element(*list_element); + } + return Element(NULL); + } + + Element insert(const K &p_key, const V &p_value) { + typename InternalList::Element **list_element = map.getptr(p_key); + if (list_element) { + (*list_element)->get().second = p_value; + return Element(*list_element); + } + typename InternalList::Element *new_element = list.push_back(Pair<const K *, V>(NULL, p_value)); + typename InternalMap::Element *e = map.set(p_key, new_element); + new_element->get().first = &e->key(); + + return Element(new_element); + } + + void erase(Element &p_element) { + map.erase(p_element.key()); + list.erase(p_element.list_element); + p_element.list_element = NULL; + } + + bool erase(const K &p_key) { + typename InternalList::Element **list_element = map.getptr(p_key); + if (list_element) { + list.erase(*list_element); + map.erase(p_key); + return true; + } + return false; + } + + inline bool has(const K &p_key) const { + return map.has(p_key); + } + + const V &operator[](const K &p_key) const { + ConstElement e = find(p_key); + CRASH_COND(!e); + return e.value(); + } + + V &operator[](const K &p_key) { + Element e = find(p_key); + if (!e) { + // consistent with Map behaviour + e = insert(p_key, V()); + } + return e.value(); + } + + inline Element front() { + return Element(list.front()); + } + + inline Element back() { + return Element(list.back()); + } + + inline ConstElement front() const { + return ConstElement(list.front()); + } + + inline ConstElement back() const { + return ConstElement(list.back()); + } + + inline bool empty() const { return list.empty(); } + inline int size() const { return list.size(); } + + void clear() { + map.clear(); + list.clear(); + } + +private: + void _copy_from(const OrderedHashMap &p_map) { + for (ConstElement E = p_map.front(); E; E = E.next()) { + insert(E.key(), E.value()); + } + } + +public: + void operator=(const OrderedHashMap &p_map) { + _copy_from(p_map); + } + + OrderedHashMap(const OrderedHashMap &p_map) { + _copy_from(p_map); + } + + _FORCE_INLINE_ OrderedHashMap() { + } +}; + +template <class K, class V, class Hasher, class Comparator, uint8_t MIN_HASH_TABLE_POWER, uint8_t RELATIONSHIP> +bool operator==(const typename OrderedHashMap<K, V, Hasher, Comparator, MIN_HASH_TABLE_POWER, RELATIONSHIP>::Element &first, + const typename OrderedHashMap<K, V, Hasher, Comparator, MIN_HASH_TABLE_POWER, RELATIONSHIP>::Element &second) { + return (first.list_element == second.list_element); +} + +template <class K, class V, class Hasher, class Comparator, uint8_t MIN_HASH_TABLE_POWER, uint8_t RELATIONSHIP> +bool operator!=(const typename OrderedHashMap<K, V, Hasher, Comparator, MIN_HASH_TABLE_POWER, RELATIONSHIP>::Element &first, + const typename OrderedHashMap<K, V, Hasher, Comparator, MIN_HASH_TABLE_POWER, RELATIONSHIP>::Element &second) { + return (first.list_element != second.list_element); +} + +template <class K, class V, class Hasher, class Comparator, uint8_t MIN_HASH_TABLE_POWER, uint8_t RELATIONSHIP> +bool operator==(const typename OrderedHashMap<K, V, Hasher, Comparator, MIN_HASH_TABLE_POWER, RELATIONSHIP>::ConstElement &first, + const typename OrderedHashMap<K, V, Hasher, Comparator, MIN_HASH_TABLE_POWER, RELATIONSHIP>::ConstElement &second) { + return (first.list_element == second.list_element); +} + +template <class K, class V, class Hasher, class Comparator, uint8_t MIN_HASH_TABLE_POWER, uint8_t RELATIONSHIP> +bool operator!=(const typename OrderedHashMap<K, V, Hasher, Comparator, MIN_HASH_TABLE_POWER, RELATIONSHIP>::ConstElement &first, + const typename OrderedHashMap<K, V, Hasher, Comparator, MIN_HASH_TABLE_POWER, RELATIONSHIP>::ConstElement &second) { + return (first.list_element != second.list_element); +} + +#endif // ORDERED_HASH_MAP_H
\ No newline at end of file |