Replace most uses of Map by HashMap

* Map is unnecessary and inefficient in almost every case.
* Replaced by the new HashMap.
* Renamed Map to RBMap and Set to RBSet for cases that still make sense
  (order matters) but use is discouraged.

There were very few cases where replacing by HashMap was undesired because
keeping the key order was intended.
I tried to keep those (as RBMap) as much as possible, but might have missed
some. Review appreciated!

10 files changed, 66 insertions, 59 deletions

diff --git a/core/math/a_star.cpp b/core/math/a_star.cpp
index 284b4294ea..a3ee259030 100644
--- a/core/math/a_star.cpp
+++ b/core/math/a_star.cpp
@@ -151,7 +151,7 @@ void AStar3D::connect_points(int p_id, int p_with_id, bool bidirectional) {
 		s.direction = Segment::BIDIRECTIONAL;
 	}
 
-	Set<Segment>::Element *element = segments.find(s);
+	RBSet<Segment>::Element *element = segments.find(s);
 	if (element != nullptr) {
 		s.direction |= element->get().direction;
 		if (s.direction == Segment::BIDIRECTIONAL) {
@@ -177,7 +177,7 @@ void AStar3D::disconnect_points(int p_id, int p_with_id, bool bidirectional) {
 	Segment s(p_id, p_with_id);
 	int remove_direction = bidirectional ? (int)Segment::BIDIRECTIONAL : s.direction;
 
-	Set<Segment>::Element *element = segments.find(s);
+	RBSet<Segment>::Element *element = segments.find(s);
 	if (element != nullptr) {
 		// s is the new segment
 		// Erase the directions to be removed
@@ -235,7 +235,7 @@ Vector<int> AStar3D::get_point_connections(int p_id) {
 
 bool AStar3D::are_points_connected(int p_id, int p_with_id, bool bidirectional) const {
 	Segment s(p_id, p_with_id);
-	const Set<Segment>::Element *element = segments.find(s);
+	const RBSet<Segment>::Element *element = segments.find(s);
 
 	return element != nullptr &&
 			(bidirectional || (element->get().direction & s.direction) == s.direction);
@@ -293,7 +293,7 @@ Vector3 AStar3D::get_closest_position_in_segment(const Vector3 &p_point) const {
 	real_t closest_dist = 1e20;
 	Vector3 closest_point;
 
-	for (const Set<Segment>::Element *E = segments.front(); E; E = E->next()) {
+	for (const RBSet<Segment>::Element *E = segments.front(); E; E = E->next()) {
 		Point *from_point = nullptr, *to_point = nullptr;
 		points.lookup(E->get().u, from_point);
 		points.lookup(E->get().v, to_point);
diff --git a/core/math/a_star.h b/core/math/a_star.h
index bb7112fb09..086be839b5 100644
--- a/core/math/a_star.h
+++ b/core/math/a_star.h
@@ -112,7 +112,7 @@ class AStar3D : public RefCounted {
 	uint64_t pass = 1;
 
 	OAHashMap<int, Point *> points;
-	Set<Segment> segments;
+	RBSet<Segment> segments;
 
 	bool _solve(Point *begin_point, Point *end_point);
 
diff --git a/core/math/color.cpp b/core/math/color.cpp
index e32f9147d9..74552a2894 100644
--- a/core/math/color.cpp
+++ b/core/math/color.cpp
@@ -33,7 +33,7 @@
 #include "color_names.inc"
 #include "core/math/math_funcs.h"
 #include "core/string/print_string.h"
-#include "core/templates/map.h"
+#include "core/templates/rb_map.h"
 
 uint32_t Color::to_argb32() const {
 	uint32_t c = (uint8_t)Math::round(a * 255);
diff --git a/core/math/disjoint_set.h b/core/math/disjoint_set.h
index 8657dc068e..d07c08e45e 100644
--- a/core/math/disjoint_set.h
+++ b/core/math/disjoint_set.h
@@ -31,11 +31,11 @@
 #ifndef DISJOINT_SET_H
 #define DISJOINT_SET_H
 
-#include "core/templates/map.h"
+#include "core/templates/rb_map.h"
 #include "core/templates/vector.h"
 
 /* This DisjointSet class uses Find with path compression and Union by rank */
-template <typename T, class C = Comparator<T>, class AL = DefaultAllocator>
+template <typename T, class H = HashMapHasherDefault, class C = HashMapComparatorDefault<T>, class AL = DefaultAllocator>
 class DisjointSet {
 	struct Element {
 		T object;
@@ -43,7 +43,7 @@ class DisjointSet {
 		int rank = 0;
 	};
 
-	typedef Map<T, Element *, C, AL> MapT;
+	typedef HashMap<T, Element *, H, C> MapT;
 
 	MapT elements;
 
@@ -65,15 +65,15 @@ public:
 
 /* FUNCTIONS */
 
-template <typename T, class C, class AL>
-DisjointSet<T, C, AL>::~DisjointSet() {
-	for (typename MapT::Element *itr = elements.front(); itr != nullptr; itr = itr->next()) {
-		memdelete_allocator<Element, AL>(itr->value());
+template <typename T, class H, class C, class AL>
+DisjointSet<T, H, C, AL>::~DisjointSet() {
+	for (KeyValue<T, Element *> &E : elements) {
+		memdelete_allocator<Element, AL>(E.value);
 	}
 }
 
-template <typename T, class C, class AL>
-typename DisjointSet<T, C, AL>::Element *DisjointSet<T, C, AL>::get_parent(Element *element) {
+template <typename T, class H, class C, class AL>
+typename DisjointSet<T, H, C, AL>::Element *DisjointSet<T, H, C, AL>::get_parent(Element *element) {
 	if (element->parent != element) {
 		element->parent = get_parent(element->parent);
 	}
@@ -81,11 +81,11 @@ typename DisjointSet<T, C, AL>::Element *DisjointSet<T, C, AL>::get_parent(Eleme
 	return element->parent;
 }
 
-template <typename T, class C, class AL>
-typename DisjointSet<T, C, AL>::Element *DisjointSet<T, C, AL>::insert_or_get(T object) {
-	typename MapT::Element *itr = elements.find(object);
+template <typename T, class H, class C, class AL>
+typename DisjointSet<T, H, C, AL>::Element *DisjointSet<T, H, C, AL>::insert_or_get(T object) {
+	typename MapT::Iterator itr = elements.find(object);
 	if (itr != nullptr) {
-		return itr->value();
+		return itr->value;
 	}
 
 	Element *new_element = memnew_allocator(Element, AL);
@@ -96,8 +96,8 @@ typename DisjointSet<T, C, AL>::Element *DisjointSet<T, C, AL>::insert_or_get(T
 	return new_element;
 }
 
-template <typename T, class C, class AL>
-void DisjointSet<T, C, AL>::create_union(T a, T b) {
+template <typename T, class H, class C, class AL>
+void DisjointSet<T, H, C, AL>::create_union(T a, T b) {
 	Element *x = insert_or_get(a);
 	Element *y = insert_or_get(b);
 
@@ -121,28 +121,28 @@ void DisjointSet<T, C, AL>::create_union(T a, T b) {
 	}
 }
 
-template <typename T, class C, class AL>
-void DisjointSet<T, C, AL>::get_representatives(Vector<T> &out_representatives) {
-	for (typename MapT::Element *itr = elements.front(); itr != nullptr; itr = itr->next()) {
-		Element *element = itr->value();
+template <typename T, class H, class C, class AL>
+void DisjointSet<T, H, C, AL>::get_representatives(Vector<T> &out_representatives) {
+	for (KeyValue<T, Element *> &E : elements) {
+		Element *element = E.value;
 		if (element->parent == element) {
 			out_representatives.push_back(element->object);
 		}
 	}
 }
 
-template <typename T, class C, class AL>
-void DisjointSet<T, C, AL>::get_members(Vector<T> &out_members, T representative) {
-	typename MapT::Element *rep_itr = elements.find(representative);
+template <typename T, class H, class C, class AL>
+void DisjointSet<T, H, C, AL>::get_members(Vector<T> &out_members, T representative) {
+	typename MapT::Iterator rep_itr = elements.find(representative);
 	ERR_FAIL_COND(rep_itr == nullptr);
 
-	Element *rep_element = rep_itr->value();
+	Element *rep_element = rep_itr->value;
 	ERR_FAIL_COND(rep_element->parent != rep_element);
 
-	for (typename MapT::Element *itr = elements.front(); itr != nullptr; itr = itr->next()) {
-		Element *parent = get_parent(itr->value());
+	for (KeyValue<T, Element *> &E : elements) {
+		Element *parent = get_parent(E.value);
 		if (parent == rep_element) {
-			out_members.push_back(itr->key());
+			out_members.push_back(E.key);
 		}
 	}
 }
diff --git a/core/math/geometry_3d.cpp b/core/math/geometry_3d.cpp
index f76de079e4..ec96753c79 100644
--- a/core/math/geometry_3d.cpp
+++ b/core/math/geometry_3d.cpp
@@ -36,7 +36,7 @@
 #include "thirdparty/misc/polypartition.h"
 
 void Geometry3D::MeshData::optimize_vertices() {
-	Map<int, int> vtx_remap;
+	HashMap<int, int> vtx_remap;
 
 	for (int i = 0; i < faces.size(); i++) {
 		for (int j = 0; j < faces[i].indices.size(); j++) {
diff --git a/core/math/octree.h b/core/math/octree.h
index 65ab9e2292..8dd103f109 100644
--- a/core/math/octree.h
+++ b/core/math/octree.h
@@ -36,7 +36,7 @@
 #include "core/math/vector3.h"
 #include "core/string/print_string.h"
 #include "core/templates/list.h"
-#include "core/templates/map.h"
+#include "core/templates/rb_map.h"
 #include "core/variant/variant.h"
 
 typedef uint32_t OctreeElementID;
@@ -151,8 +151,8 @@ private:
 		typename List<PairData *, AL>::Element *eA, *eB;
 	};
 
-	typedef Map<OctreeElementID, Element, Comparator<OctreeElementID>, AL> ElementMap;
-	typedef Map<PairKey, PairData, Comparator<PairKey>, AL> PairMap;
+	typedef HashMap<OctreeElementID, Element, Comparator<OctreeElementID>, AL> ElementMap;
+	typedef HashMap<PairKey, PairData, Comparator<PairKey>, AL> PairMap;
 	ElementMap element_map;
 	PairMap pair_map;
 
diff --git a/core/math/quick_hull.cpp b/core/math/quick_hull.cpp
index 3614bfadf8..43744deeb0 100644
--- a/core/math/quick_hull.cpp
+++ b/core/math/quick_hull.cpp
@@ -30,7 +30,7 @@
 
 #include "quick_hull.h"
 
-#include "core/templates/map.h"
+#include "core/templates/rb_map.h"
 
 uint32_t QuickHull::debug_stop_after = 0xFFFFFFFF;
 
@@ -52,7 +52,7 @@ Error QuickHull::build(const Vector<Vector3> &p_points, Geometry3D::MeshData &r_
 
 	Vector<bool> valid_points;
 	valid_points.resize(p_points.size());
-	Set<Vector3> valid_cache;
+	RBSet<Vector3> valid_cache;
 
 	for (int i = 0; i < p_points.size(); i++) {
 		Vector3 sp = p_points[i].snapped(Vector3(0.0001, 0.0001, 0.0001));
@@ -237,7 +237,7 @@ Error QuickHull::build(const Vector<Vector3> &p_points, Geometry3D::MeshData &r_
 		//find lit faces and lit edges
 		List<List<Face>::Element *> lit_faces; //lit face is a death sentence
 
-		Map<Edge, FaceConnect> lit_edges; //create this on the flight, should not be that bad for performance and simplifies code a lot
+		HashMap<Edge, FaceConnect, Edge> lit_edges; //create this on the flight, should not be that bad for performance and simplifies code a lot
 
 		for (List<Face>::Element *E = faces.front(); E; E = E->next()) {
 			if (E->get().plane.distance_to(v) > 0) {
@@ -248,15 +248,15 @@ Error QuickHull::build(const Vector<Vector3> &p_points, Geometry3D::MeshData &r_
 					uint32_t b = E->get().vertices[(i + 1) % 3];
 					Edge e(a, b);
 
-					Map<Edge, FaceConnect>::Element *F = lit_edges.find(e);
+					HashMap<Edge, FaceConnect, Edge>::Iterator F = lit_edges.find(e);
 					if (!F) {
 						F = lit_edges.insert(e, FaceConnect());
 					}
 					if (e.vertices[0] == a) {
 						//left
-						F->get().left = E;
+						F->value.left = E;
 					} else {
-						F->get().right = E;
+						F->value.right = E;
 					}
 				}
 			}
@@ -333,7 +333,7 @@ Error QuickHull::build(const Vector<Vector3> &p_points, Geometry3D::MeshData &r_
 	/* CREATE MESHDATA */
 
 	//make a map of edges again
-	Map<Edge, RetFaceConnect> ret_edges;
+	HashMap<Edge, RetFaceConnect, Edge> ret_edges;
 	List<Geometry3D::MeshData::Face> ret_faces;
 
 	for (const Face &E : faces) {
@@ -351,15 +351,15 @@ Error QuickHull::build(const Vector<Vector3> &p_points, Geometry3D::MeshData &r_
 			uint32_t b = E.vertices[(i + 1) % 3];
 			Edge e(a, b);
 
-			Map<Edge, RetFaceConnect>::Element *G = ret_edges.find(e);
+			HashMap<Edge, RetFaceConnect, Edge>::Iterator G = ret_edges.find(e);
 			if (!G) {
 				G = ret_edges.insert(e, RetFaceConnect());
 			}
 			if (e.vertices[0] == a) {
 				//left
-				G->get().left = F;
+				G->value.left = F;
 			} else {
-				G->get().right = F;
+				G->value.right = F;
 			}
 		}
 	}
@@ -374,10 +374,10 @@ Error QuickHull::build(const Vector<Vector3> &p_points, Geometry3D::MeshData &r_
 			int b = E->get().indices[(i + 1) % f.indices.size()];
 			Edge e(a, b);
 
-			Map<Edge, RetFaceConnect>::Element *F = ret_edges.find(e);
+			HashMap<Edge, RetFaceConnect, Edge>::Iterator F = ret_edges.find(e);
 
 			ERR_CONTINUE(!F);
-			List<Geometry3D::MeshData::Face>::Element *O = F->get().left == E ? F->get().right : F->get().left;
+			List<Geometry3D::MeshData::Face>::Element *O = F->value.left == E ? F->value.right : F->value.left;
 			ERR_CONTINUE(O == E);
 			ERR_CONTINUE(O == nullptr);
 
@@ -401,13 +401,13 @@ Error QuickHull::build(const Vector<Vector3> &p_points, Geometry3D::MeshData &r_
 							}
 							Edge e2(idx, idxn);
 
-							Map<Edge, RetFaceConnect>::Element *F2 = ret_edges.find(e2);
+							HashMap<Edge, RetFaceConnect, Edge>::Iterator F2 = ret_edges.find(e2);
 							ERR_CONTINUE(!F2);
 							//change faceconnect, point to this face instead
-							if (F2->get().left == O) {
-								F2->get().left = E;
-							} else if (F2->get().right == O) {
-								F2->get().right = E;
+							if (F2->value.left == O) {
+								F2->value.left = E;
+							} else if (F2->value.right == O) {
+								F2->value.right = E;
 							}
 						}
 
@@ -426,7 +426,7 @@ Error QuickHull::build(const Vector<Vector3> &p_points, Geometry3D::MeshData &r_
 					}
 				}
 
-				ret_edges.erase(F); //remove the edge
+				ret_edges.remove(F); //remove the edge
 				ret_faces.erase(O); //remove the face
 			}
 		}
diff --git a/core/math/quick_hull.h b/core/math/quick_hull.h
index b8d813c979..1c354880b4 100644
--- a/core/math/quick_hull.h
+++ b/core/math/quick_hull.h
@@ -34,7 +34,7 @@
 #include "core/math/aabb.h"
 #include "core/math/geometry_3d.h"
 #include "core/templates/list.h"
-#include "core/templates/set.h"
+#include "core/templates/rb_set.h"
 
 class QuickHull {
 public:
@@ -44,9 +44,16 @@ public:
 			uint64_t id = 0;
 		};
 
+		static uint32_t hash(const Edge &p_edge) {
+			return hash_one_uint64(p_edge.id);
+		}
+
 		bool operator<(const Edge &p_edge) const {
 			return id < p_edge.id;
 		}
+		bool operator==(const Edge &p_edge) const {
+			return id == p_edge.id;
+		}
 
 		Edge(int p_vtx_a = 0, int p_vtx_b = 0) {
 			if (p_vtx_a > p_vtx_b) {
diff --git a/core/math/static_raycaster.h b/core/math/static_raycaster.h
index 33254399c7..adc81906d7 100644
--- a/core/math/static_raycaster.h
+++ b/core/math/static_raycaster.h
@@ -102,7 +102,7 @@ public:
 	virtual void add_mesh(const PackedVector3Array &p_vertices, const PackedInt32Array &p_indices, unsigned int p_id) = 0;
 	virtual void commit() = 0;
 
-	virtual void set_mesh_filter(const Set<int> &p_mesh_ids) = 0;
+	virtual void set_mesh_filter(const RBSet<int> &p_mesh_ids) = 0;
 	virtual void clear_mesh_filter() = 0;
 
 	static Ref<StaticRaycaster> create();
diff --git a/core/math/triangle_mesh.cpp b/core/math/triangle_mesh.cpp
index e146c4a4e3..54461bf70f 100644
--- a/core/math/triangle_mesh.cpp
+++ b/core/math/triangle_mesh.cpp
@@ -122,7 +122,7 @@ void TriangleMesh::create(const Vector<Vector3> &p_faces) {
 
 		const Vector3 *r = p_faces.ptr();
 		Triangle *w = triangles.ptrw();
-		Map<Vector3, int> db;
+		HashMap<Vector3, int> db;
 
 		for (int i = 0; i < fc; i++) {
 			Triangle &f = w[i];
@@ -131,9 +131,9 @@ void TriangleMesh::create(const Vector<Vector3> &p_faces) {
 			for (int j = 0; j < 3; j++) {
 				int vidx = -1;
 				Vector3 vs = v[j].snapped(Vector3(0.0001, 0.0001, 0.0001));
-				Map<Vector3, int>::Element *E = db.find(vs);
+				HashMap<Vector3, int>::Iterator E = db.find(vs);
 				if (E) {
-					vidx = E->get();
+					vidx = E->value;
 				} else {
 					vidx = db.size();
 					db[vs] = vidx;