Merge pull request #10318 from endragor/ordered-hash-map

Implement OrderedHashMap

6 files changed, 592 insertions, 38 deletions

diff --git a/core/hash_map.h b/core/hash_map.h
index b22c6378b0..37391a4c83 100644
--- a/core/hash_map.h
+++ b/core/hash_map.h
@@ -102,17 +102,31 @@ public:
 		}
 	};
 
-private:
-	struct Entry {
+	struct Element {
+	private:
+		friend class HashMap;
 
 		uint32_t hash;
-		Entry *next;
+		Element *next;
+		Element() { next = 0; }
 		Pair pair;
 
-		Entry() { next = 0; }
+	public:
+		const TKey &key() const {
+			return pair.key;
+		}
+
+		TData &value() {
+			return pair.data;
+		}
+
+		const TData &value() const {
+			return pair.value();
+		}
 	};
 
-	Entry **hash_table;
+private:
+	Element **hash_table;
 	uint8_t hash_table_power;
 	uint32_t elements;
 
@@ -120,7 +134,7 @@ private:
 
 		ERR_FAIL_COND(hash_table);
 
-		hash_table = memnew_arr(Entry *, (1 << MIN_HASH_TABLE_POWER));
+		hash_table = memnew_arr(Element *, (1 << MIN_HASH_TABLE_POWER));
 
 		hash_table_power = MIN_HASH_TABLE_POWER;
 		elements = 0;
@@ -168,7 +182,7 @@ private:
 		if (new_hash_table_power == -1)
 			return;
 
-		Entry **new_hash_table = memnew_arr(Entry *, (1 << new_hash_table_power));
+		Element **new_hash_table = memnew_arr(Element *, (1 << new_hash_table_power));
 		if (!new_hash_table) {
 
 			ERR_PRINT("Out of Memory");
@@ -184,7 +198,7 @@ private:
 
 			while (hash_table[i]) {
 
-				Entry *se = hash_table[i];
+				Element *se = hash_table[i];
 				hash_table[i] = se->next;
 				int new_pos = se->hash & ((1 << new_hash_table_power) - 1);
 				se->next = new_hash_table[new_pos];
@@ -199,12 +213,12 @@ private:
 	}
 
 	/* I want to have only one function.. */
-	_FORCE_INLINE_ const Entry *get_entry(const TKey &p_key) const {
+	_FORCE_INLINE_ const Element *get_element(const TKey &p_key) const {
 
 		uint32_t hash = Hasher::hash(p_key);
 		uint32_t index = hash & ((1 << hash_table_power) - 1);
 
-		Entry *e = hash_table[index];
+		Element *e = hash_table[index];
 
 		while (e) {
 
@@ -221,10 +235,10 @@ private:
 		return NULL;
 	}
 
-	Entry *create_entry(const TKey &p_key) {
+	Element *create_element(const TKey &p_key) {
 
-		/* if entry doesn't exist, create it */
-		Entry *e = memnew(Entry);
+		/* if element doesn't exist, create it */
+		Element *e = memnew(Element);
 		ERR_FAIL_COND_V(!e, NULL); /* out of memory */
 		uint32_t hash = Hasher::hash(p_key);
 		uint32_t index = hash & ((1 << hash_table_power) - 1);
@@ -248,7 +262,7 @@ private:
 		if (!p_t.hash_table || p_t.hash_table_power == 0)
 			return; /* not copying from empty table */
 
-		hash_table = memnew_arr(Entry *, 1 << p_t.hash_table_power);
+		hash_table = memnew_arr(Element *, 1 << p_t.hash_table_power);
 		hash_table_power = p_t.hash_table_power;
 		elements = p_t.elements;
 
@@ -256,11 +270,11 @@ private:
 
 			hash_table[i] = NULL;
 
-			const Entry *e = p_t.hash_table[i];
+			const Element *e = p_t.hash_table[i];
 
 			while (e) {
 
-				Entry *le = memnew(Entry); /* local entry */
+				Element *le = memnew(Element); /* local element */
 
 				*le = *e; /* copy data */
 
@@ -274,30 +288,30 @@ private:
 	}
 
 public:
-	void set(const TKey &p_key, const TData &p_data) {
-
-		set(Pair(p_key, p_data));
+	Element *set(const TKey &p_key, const TData &p_data) {
+		return set(Pair(p_key, p_data));
 	}
 
-	void set(const Pair &p_pair) {
+	Element *set(const Pair &p_pair) {
 
-		Entry *e = NULL;
+		Element *e = NULL;
 		if (!hash_table)
 			make_hash_table(); // if no table, make one
 		else
-			e = const_cast<Entry *>(get_entry(p_pair.key));
+			e = const_cast<Element *>(get_element(p_pair.key));
 
 		/* if we made it up to here, the pair doesn't exist, create and assign */
 
 		if (!e) {
 
-			e = create_entry(p_pair.key);
+			e = create_element(p_pair.key);
 			if (!e)
-				return;
+				return NULL;
 			check_hash_table(); // perform mantenience routine
 		}
 
 		e->pair.data = p_pair.data;
+		return e;
 	}
 
 	bool has(const TKey &p_key) const {
@@ -335,7 +349,7 @@ public:
 		if (!hash_table)
 			return NULL;
 
-		Entry *e = const_cast<Entry *>(get_entry(p_key));
+		Element *e = const_cast<Element *>(get_element(p_key));
 
 		if (e)
 			return &e->pair.data;
@@ -348,7 +362,7 @@ public:
 		if (!hash_table)
 			return NULL;
 
-		const Entry *e = const_cast<Entry *>(get_entry(p_key));
+		const Element *e = const_cast<Element *>(get_element(p_key));
 
 		if (e)
 			return &e->pair.data;
@@ -370,7 +384,7 @@ public:
 		uint32_t hash = p_custom_hash;
 		uint32_t index = hash & ((1 << hash_table_power) - 1);
 
-		Entry *e = hash_table[index];
+		Element *e = hash_table[index];
 
 		while (e) {
 
@@ -396,7 +410,7 @@ public:
 		uint32_t hash = p_custom_hash;
 		uint32_t index = hash & ((1 << hash_table_power) - 1);
 
-		const Entry *e = hash_table[index];
+		const Element *e = hash_table[index];
 
 		while (e) {
 
@@ -425,8 +439,8 @@ public:
 		uint32_t hash = Hasher::hash(p_key);
 		uint32_t index = hash & ((1 << hash_table_power) - 1);
 
-		Entry *e = hash_table[index];
-		Entry *p = NULL;
+		Element *e = hash_table[index];
+		Element *p = NULL;
 		while (e) {
 
 			/* checking hash first avoids comparing key, which may take longer */
@@ -463,16 +477,16 @@ public:
 	}
 	inline TData &operator[](const TKey &p_key) { //assignment
 
-		Entry *e = NULL;
+		Element *e = NULL;
 		if (!hash_table)
 			make_hash_table(); // if no table, make one
 		else
-			e = const_cast<Entry *>(get_entry(p_key));
+			e = const_cast<Element *>(get_element(p_key));
 
 		/* if we made it up to here, the pair doesn't exist, create */
 		if (!e) {
 
-			e = create_entry(p_key);
+			e = create_element(p_key);
 			CRASH_COND(!e);
 			check_hash_table(); // perform mantenience routine
 		}
@@ -510,14 +524,14 @@ public:
 
 		} else { /* get the next key */
 
-			const Entry *e = get_entry(*p_key);
+			const Element *e = get_element(*p_key);
 			ERR_FAIL_COND_V(!e, NULL); /* invalid key supplied */
 
 			if (e->next) {
 				/* if there is a "next" in the list, return that */
 				return &e->next->pair.key;
 			} else {
-				/* go to next entries */
+				/* go to next elements */
 				uint32_t index = e->hash & ((1 << hash_table_power) - 1);
 				index++;
 				for (int i = index; i < (1 << hash_table_power); i++) {
@@ -552,7 +566,7 @@ public:
 
 				while (hash_table[i]) {
 
-					Entry *e = hash_table[i];
+					Element *e = hash_table[i];
 					hash_table[i] = e->next;
 					memdelete(e);
 				}
@@ -582,7 +596,7 @@ public:
 			return;
 		for (int i = 0; i < (1 << hash_table_power); i++) {
 
-			Entry *e = hash_table[i];
+			Element *e = hash_table[i];
 			while (e) {
 				*p_pairs = &e->pair;
 				p_pairs++;
@@ -596,7 +610,7 @@ public:
 			return;
 		for (int i = 0; i < (1 << hash_table_power); i++) {
 
-			Entry *e = hash_table[i];
+			Element *e = hash_table[i];
 			while (e) {
 				p_keys->push_back(e->pair.key);
 				e = e->next;
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
diff --git a/core/pair.h b/core/pair.h
index f780c79c81..535c3355b6 100644
--- a/core/pair.h
+++ b/core/pair.h
@@ -44,6 +44,16 @@ struct Pair {
 };
 
 template <class F, class S>
+bool operator==(const Pair<F, S> &pair, const Pair<F, S> &other) {
+	return (pair.first == other.first) && (pair.second == other.second);
+}
+
+template <class F, class S>
+bool operator!=(const Pair<F, S> &pair, const Pair<F, S> &other) {
+	return (pair.first != other.first) || (pair.second != other.second);
+}
+
+template <class F, class S>
 struct PairSort {
 
 	bool operator()(const Pair<F, S> &A, const Pair<F, S> &B) const {
diff --git a/main/tests/test_main.cpp b/main/tests/test_main.cpp
index 794bdb757b..645db2826e 100644
--- a/main/tests/test_main.cpp
+++ b/main/tests/test_main.cpp
@@ -37,6 +37,7 @@
 #include "test_image.h"
 #include "test_io.h"
 #include "test_math.h"
+#include "test_ordered_hash_map.h"
 #include "test_physics.h"
 #include "test_physics_2d.h"
 #include "test_render.h"
@@ -130,6 +131,11 @@ MainLoop *test_main(String p_test, const List<String> &p_args) {
 		return TestImage::test();
 	}
 
+	if (p_test == "ordered_hash_map") {
+
+		return TestOrderedHashMap::test();
+	}
+
 	return NULL;
 }
 
diff --git a/main/tests/test_ordered_hash_map.cpp b/main/tests/test_ordered_hash_map.cpp
new file mode 100644
index 0000000000..89f4bf8593
--- /dev/null
+++ b/main/tests/test_ordered_hash_map.cpp
@@ -0,0 +1,171 @@
+/*************************************************************************/
+/*  test_ordered_hash_map.cpp                                            */
+/*************************************************************************/
+/*                       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.                */
+/*************************************************************************/
+
+#include "ordered_hash_map.h"
+#include "os/os.h"
+#include "pair.h"
+#include "vector.h"
+
+namespace TestOrderedHashMap {
+
+bool test_insert() {
+	OrderedHashMap<int, int> map;
+	OrderedHashMap<int, int>::Element e = map.insert(42, 84);
+
+	return e && e.key() == 42 && e.get() == 84 && e.value() == 84 && map[42] == 84 && map.has(42) && map.find(42);
+}
+
+bool test_insert_overwrite() {
+	OrderedHashMap<int, int> map;
+	map.insert(42, 84);
+	map.insert(42, 1234);
+
+	return map[42] == 1234;
+}
+
+bool test_erase_via_element() {
+	OrderedHashMap<int, int> map;
+	OrderedHashMap<int, int>::Element e = map.insert(42, 84);
+
+	map.erase(e);
+	return !e && !map.has(42) && !map.find(42);
+}
+
+bool test_erase_via_key() {
+	OrderedHashMap<int, int> map;
+	map.insert(42, 84);
+	map.erase(42);
+	return !map.has(42) && !map.find(42);
+}
+
+bool test_size() {
+	OrderedHashMap<int, int> map;
+	map.insert(42, 84);
+	map.insert(123, 84);
+	map.insert(123, 84);
+	map.insert(0, 84);
+	map.insert(123485, 84);
+
+	return map.size() == 4;
+}
+
+bool test_iteration() {
+	OrderedHashMap<int, int> map;
+	map.insert(42, 84);
+	map.insert(123, 12385);
+	map.insert(0, 12934);
+	map.insert(123485, 1238888);
+	map.insert(123, 111111);
+
+	Vector<Pair<int, int> > expected;
+	expected.push_back(Pair<int, int>(42, 84));
+	expected.push_back(Pair<int, int>(123, 111111));
+	expected.push_back(Pair<int, int>(0, 12934));
+	expected.push_back(Pair<int, int>(123485, 1238888));
+
+	int idx = 0;
+	for (OrderedHashMap<int, int>::Element E = map.front(); E; E = E.next()) {
+		if (expected[idx] != Pair<int, int>(E.key(), E.value())) {
+			return false;
+		}
+		++idx;
+	}
+	return true;
+}
+
+bool test_const_iteration(const OrderedHashMap<int, int> &map) {
+	Vector<Pair<int, int> > expected;
+	expected.push_back(Pair<int, int>(42, 84));
+	expected.push_back(Pair<int, int>(123, 111111));
+	expected.push_back(Pair<int, int>(0, 12934));
+	expected.push_back(Pair<int, int>(123485, 1238888));
+
+	int idx = 0;
+	for (OrderedHashMap<int, int>::ConstElement E = map.front(); E; E = E.next()) {
+		if (expected[idx] != Pair<int, int>(E.key(), E.value())) {
+			return false;
+		}
+		++idx;
+	}
+	return true;
+}
+
+bool test_const_iteration() {
+	OrderedHashMap<int, int> map;
+	map.insert(42, 84);
+	map.insert(123, 12385);
+	map.insert(0, 12934);
+	map.insert(123485, 1238888);
+	map.insert(123, 111111);
+
+	return test_const_iteration(map);
+}
+
+typedef bool (*TestFunc)(void);
+
+TestFunc test_funcs[] = {
+
+	test_insert,
+	test_insert_overwrite,
+	test_erase_via_element,
+	test_erase_via_key,
+	test_size,
+	test_iteration,
+	test_const_iteration,
+	0
+
+};
+
+MainLoop *test() {
+
+	int count = 0;
+	int passed = 0;
+
+	while (true) {
+		if (!test_funcs[count])
+			break;
+		bool pass = test_funcs[count]();
+		if (pass)
+			passed++;
+		OS::get_singleton()->print("\t%s\n", pass ? "PASS" : "FAILED");
+
+		count++;
+	}
+
+	OS::get_singleton()->print("\n\n\n");
+	OS::get_singleton()->print("*************\n");
+	OS::get_singleton()->print("***TOTALS!***\n");
+	OS::get_singleton()->print("*************\n");
+
+	OS::get_singleton()->print("Passed %i of %i tests\n", passed, count);
+
+	return NULL;
+}
+} // namespace TestOrderedHashMap
\ No newline at end of file
diff --git a/main/tests/test_ordered_hash_map.h b/main/tests/test_ordered_hash_map.h
new file mode 100644
index 0000000000..0cde250f56
--- /dev/null
+++ b/main/tests/test_ordered_hash_map.h
@@ -0,0 +1,38 @@
+/*************************************************************************/
+/*  test_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 TEST_ORDERED_HASH_MAP_H
+#define TEST_ORDERED_HASH_MAP_H
+
+namespace TestOrderedHashMap {
+
+MainLoop *test();
+}
+
+#endif