[Scummvm-git-logs] scummvm master -> d49ed21b4b82373d033dfa1debde71585cfb59f9

[grisenti]

This automated email contains information about 1 new commit which have been
pushed to the 'scummvm' repo located at https://github.com/scummvm/scummvm .

Summary:
d49ed21b4b HPL1: generalize Std::Tree api and add new insert


Commit: d49ed21b4b82373d033dfa1debde71585cfb59f9
    https://github.com/scummvm/scummvm/commit/d49ed21b4b82373d033dfa1debde71585cfb59f9
Author: grisenti (emanuele at grisenti.net)
Date: 2023-03-02T11:26:30+01:00

Commit Message:
HPL1: generalize Std::Tree api and add new insert

Changed paths:
    engines/hpl1/std/map.h
    engines/hpl1/std/multimap.h
    engines/hpl1/std/tree.h


diff --git a/engines/hpl1/std/map.h b/engines/hpl1/std/map.h
index 14db26f9bda..bdece894bde 100644
--- a/engines/hpl1/std/map.h
+++ b/engines/hpl1/std/map.h
@@ -30,10 +30,11 @@ namespace Std {
 
 template<class Key, class Val, class CompFunc = Common::Less<Key> >
 class map {
+	using TreeT = Tree<pair<Key, Val>, Key, PairKey<Key, Val>, CompFunc>;
 public:
-	using value_type = typename Tree<Key, Val, CompFunc>::ValueType;
-	using iterator = typename Tree<Key, Val, CompFunc>::BasicIterator;
-	using const_iterator = typename Tree<Key, Val, CompFunc>::ConstIterator;
+	using value_type = pair<Key, Val>;
+	using iterator = typename TreeT::BasicIterator;
+	using const_iterator = typename TreeT::ConstIterator;
 
 	/**
 	 * Clears the map
@@ -167,7 +168,7 @@ private:
 		return !_comp(a, b) && !_comp(b, a);
 	}
 
-	Tree<Key, Val, CompFunc> _items;
+	TreeT _items;
 	CompFunc _comp;
 };
 
diff --git a/engines/hpl1/std/multimap.h b/engines/hpl1/std/multimap.h
index a20106c9132..2fe53cc7bd4 100644
--- a/engines/hpl1/std/multimap.h
+++ b/engines/hpl1/std/multimap.h
@@ -29,12 +29,13 @@ namespace Hpl1 {
 
 namespace Std {
 
-template<class Key, class Val, class CompFunc = Common::Less<Key> >
+template<class Key, class Val, class CompFunc = Common::Less<Key>>
 class multimap {
+	using TreeT = Tree<pair<Key, Val>, Key, PairKey<Key, Val>, CompFunc>;
 public:
-	using value_type = typename Tree<Key, Val, CompFunc>::ValueType;
-	using iterator = typename Tree<Key, Val, CompFunc>::BasicIterator;
-	using const_iterator = typename Tree<Key, Val, CompFunc>::ConstIterator;
+	using value_type = pair<Key, Val>;
+	using iterator = typename TreeT::BasicIterator;
+	using const_iterator = typename TreeT::ConstIterator;
 
 	/**
 	 * Clears the map
@@ -155,7 +156,7 @@ private:
 		return !_comp(a, b) && !_comp(b, a);
 	}
 
-	Tree<Key, Val, CompFunc> _items;
+	TreeT _items;
 	CompFunc _comp;
 };
 
diff --git a/engines/hpl1/std/tree.h b/engines/hpl1/std/tree.h
index 19c54b1f012..9cc70d439f1 100644
--- a/engines/hpl1/std/tree.h
+++ b/engines/hpl1/std/tree.h
@@ -30,11 +30,23 @@ namespace Hpl1 {
 
 namespace Std {
 
-template<class Key, class Val, class KeyComp = Common::Less<Key> >
+template<typename Key, typename Val>
+struct PairKey {
+	const Key &operator()(const pair<Key, Val> &p) {
+		return p.first;
+	}
+};
+
+template<typename T>
+struct Identity {
+	const T &operator()(const T &t) {
+		return t;
+	}
+};
+
+template<class ValueType, class Key, class KeyProj, class KeyComp = Common::Less<Key> >
 class Tree {
 public:
-	using ValueType = pair<Key, Val>;
-
 	struct Node {
 		Node *parent;
 		Node *left;
@@ -84,7 +96,7 @@ public:
 		}
 
 	private:
-		Iterator(Node *n) : _current(n) {}
+		explicit Iterator(Node *n) : _current(n) {}
 
 		Node *_current = nullptr;
 	};
@@ -139,7 +151,7 @@ public:
 		Node *it = _root;
 		Node *res = nullptr;
 		while (it) {
-			if (!_comp(it->value.first, key)) {
+			if (!_comp(KeyProj()(it->value), key)) {
 				res = it;
 				it = it->left;
 			} else {
@@ -153,7 +165,7 @@ public:
 		Node *it = _root;
 		Node *res = nullptr;
 		while (it) {
-			if (!_comp(it->value.first, key)) {
+			if (!_comp(KeyProj()(it->value), key)) {
 				res = it;
 				it = it->left;
 			} else {
@@ -167,7 +179,7 @@ public:
 		Node *it = _root;
 		Node *res = nullptr;
 		while (it) {
-			if (!_comp(key, it->value.first)) {
+			if (!_comp(key, KeyProj()(it->value))) {
 				it = it->right;
 			} else {
 				res = it;
@@ -181,7 +193,7 @@ public:
 		Node *it = _root;
 		Node *res = nullptr;
 		while (it) {
-			if (!_comp(key, it->value.first)) {
+			if (!_comp(key, KeyProj()(it->value))) {
 				it = it->right;
 			} else {
 				res = it;
@@ -194,7 +206,7 @@ public:
 	BasicIterator erase(BasicIterator it) {
 		auto const u = it._current;
 		if (!u)
-			return {nullptr};
+			return BasicIterator(nullptr);
 		auto v = merge(u->left, u->right);
 		if (u->parent) {
 			auto const p = u->parent;
@@ -222,23 +234,15 @@ public:
 	}
 
 	BasicIterator insert(const ValueType &val) {
-		auto it = &_root;
-		Node *parent = nullptr;
-		bool wentRight = false;
-		while (*it) {
-			parent = *it;
-			if (_comp((*it)->value.first, val.first)) {
-				it = &(*it)->right;
-				wentRight = true;
-			} else {
-				it = &(*it)->left;
-			}
-		}
-		*it = new Node{parent, nullptr, nullptr, val};
-		if (!wentRight)
-			_leftmost = *it;
-		++_size;
-		return BasicIterator{*it};
+		return internalInsert(&_root, val);
+	}
+
+  	// requires that either start is lowerbound of val or start is end()
+  	// otherwise the resulting tree could be unsorted
+	BasicIterator insert(BasicIterator start, const ValueType &val) {
+		if (start == end())
+			return insert(val);
+		return internalInsert(&start._current, val);
 	}
 
 	std::size_t size() const { return _size; }
@@ -266,6 +270,24 @@ private:
 		}
 	}
 
+	BasicIterator internalInsert(Node **starting_node, const ValueType &val) {
+		auto it = starting_node;
+		Node *parent = nullptr;
+		while (*it) {
+			parent = *it;
+			if (_comp(KeyProj()((*it)->value), KeyProj()(val))) {
+				it = &(*it)->right;
+			} else {
+				it = &(*it)->left;
+			}
+		}
+		*it = new Node{parent, nullptr, nullptr, val};
+		if (!_leftmost || (parent == _leftmost && _leftmost->left == *it))
+			_leftmost = *it;
+		++_size;
+		return BasicIterator(*it);
+	}
+
 	static Node *leftmost(Node *n) {
 		while (n->left)
 			n = n->left;