From 83a55fa7e87bdf75c824f068dd0b2e49468dc6d7 Mon Sep 17 00:00:00 2001
From: Max Horn
Date: Fri, 7 Nov 2003 00:02:47 +0000
Subject: Introduce Comperator template parameter to Map -> this allows more
 flexible use of Map (in particular, I can now use a StringMap in
 ConfigManager which ignores case)

svn-id: r11170
---
 common/map.h | 45 +++++++++++++++++++++++++++++++--------------
 1 file changed, 31 insertions(+), 14 deletions(-)

(limited to 'common/map.h')

diff --git a/common/map.h b/common/map.h
index 94436eed94..df7f42740a 100644
--- a/common/map.h
+++ b/common/map.h
@@ -25,6 +25,18 @@
 
 namespace Common {
 
+/**
+ * Default comparison functor: compares to objects using their </==/> operators.
+ * Comparison functors ('comperators') are used by the Map template to
+ * compare keys. A non-standard comperator might e.g. be implemented to
+ * compare strings, ignoring the case.
+ */
+template <class T>
+struct DefaultComperator {
+  int operator()(const T& x, const T& y) const { return (x < y) ? -1 : (y < x) ? +1 : 0; }
+};
+
+
 /**
  * Template based map (aka dictionary) class which uniquely maps elements of
  * class Key to elements of class Value.
@@ -36,7 +48,7 @@ namespace Common {
  * @todo Having unit tests for this class would be very desirable. There are a 
  *       big number of things which can go wrong in this code.
  */
-template <class Key, class Value>
+template <class Key, class Value, class Comperator = DefaultComperator<Key> >
 class Map {
 protected:
 	struct Node {
@@ -52,12 +64,12 @@ protected:
 	Node *_header;
 
 private:
-	Map<Key, Value>(const Map<Key, Value> &map);
-	Map<Key, Value> &operator =(const Map<Key, Value> &map);
+	Map<Key, Value, Comperator>(const Map<Key, Value, Comperator> &map);
+	Map<Key, Value, Comperator> &operator =(const Map<Key, Value, Comperator> &map);
 
 public:
 	class ConstIterator {
-		friend class Map<Key, Value>;
+		friend class Map<Key, Value, Comperator>;
 	protected:
 		Node *_node;
 		ConstIterator(Node *node) : _node(node) {}
@@ -93,12 +105,12 @@ public:
 	};
 
 public:
-	Map<Key, Value>() : _root(0) {
+	Map<Key, Value, Comperator>() : _root(0) {
 		_header = new Node();
 		_header->_right = _header->_left = _header;
 	}
 	
-	~Map<Key, Value>() {
+	virtual ~Map<Key, Value, Comperator>() {
 		clearNodes(_root);
 		delete _header;
 		_root = _header = 0;
@@ -187,7 +199,7 @@ public:
 		delete node;
 	}
 
-	void merge(const Map<Key, Value> &map) {
+	void merge(const Map<Key, Value, Comperator> &map) {
 		merge(map._root);
 	}
 
@@ -216,24 +228,29 @@ protected:
 
 	/** Find and return the node matching the given key, if any. */
 	Node *findNode(Node *node, const Key &key) const {
-		while (node && (key != node->_key)) {
-			if (key < node->_key) {
+		Comperator cmp;
+		while (node) {
+			int val = cmp(key,node->_key);
+			if (val == 0)
+				return node;
+			else if (val < 0)
 				node = node->_left;
-			} else {
+			else
 				node = node->_right;
-			}
 		}
-		return node;
+		return 0;
 	}
 
 	Node *findOrCreateNode(Node *node, const Key &key) {
+		Comperator cmp;
 		Node *prevNode = 0;
 		bool left = true;
 		while (node) {
+			int val = cmp(key, node->_key);
 			prevNode = node;
-			if (key == node->_key) {
+			if (val == 0) {
 				return node;
-			} else if (key < node->_key) {
+			} else if (val < 0) {
 				left = true;
 				node = node->_left;
 			} else {
-- 
cgit v1.2.3