summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--core/hash_map.h90
-rw-r--r--core/ordered_hash_map.h315
-rw-r--r--core/pair.h10
-rw-r--r--main/tests/test_main.cpp6
-rw-r--r--main/tests/test_ordered_hash_map.cpp171
-rw-r--r--main/tests/test_ordered_hash_map.h38
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