From 350411c85b234009b3d113f581a8f24e80ed31c2 Mon Sep 17 00:00:00 2001
From: Thomas Grill <xovo@users.sourceforge.net>
Date: Mon, 2 May 2005 22:07:18 +0000
Subject: use index bit-reversal to pseudo-balance the map tree

svn path=/trunk/externals/nusmuk/; revision=2883
---
 msd.h | 31 ++++++++++++++++++++++++++++---
 1 file changed, 28 insertions(+), 3 deletions(-)

diff --git a/msd.h b/msd.h
index 3964cdb..c08f15b 100644
--- a/msd.h
+++ b/msd.h
@@ -214,12 +214,21 @@ public:
 };
 
 
+template <typename T>
+inline T bitrev(T k) 
+{
+	T r = 0;
+	for(int i = 0; i < sizeof(k)*4; ++i) r = (r<<1)|(k&1),k >>= 1;
+	return r;
+}
+
+// use bit-reversed key to pseudo-balance the map tree
 template <typename T>
 class IndexMap
-	: public TablePtrMap<int,T,16>
+	: TablePtrMap<unsigned int,T,16>
 {
 public:
-	typedef TablePtrMap<int,T,16> Parent;
+	typedef TablePtrMap<unsigned int,T,16> Parent;
 	
     virtual ~IndexMap() { reset(); }
 
@@ -229,7 +238,23 @@ public:
 		for(typename Parent::iterator it(*this); it; ++it) delete it.data();
 		Parent::clear(); 
 	}
+	
+	inline size_t size() const { return Parent::size(); }
 
+	inline T insert(unsigned int k,T v) { return Parent::insert(bitrev(k),v); }	
+
+	inline T find(unsigned int k) { return Parent::find(bitrev(k)); }
+
+	inline T remove(unsigned int k) { return Parent::remove(bitrev(k)); }
+	
+	class iterator
+		: public Parent::iterator
+	{
+	public:
+		iterator() {}
+		iterator(IndexMap &m): Parent::iterator(m) {}
+		inline unsigned int key() const { return bitrev(Parent::key()); }
+	};
 };
 
 template <typename T>
@@ -321,7 +346,7 @@ protected:
 	IDMap<t_mass *> massids;		// masses by name
 	
 	t_float limit[N][2];			// Limit values
-	int id_mass, id_link;
+	unsigned int id_mass, id_link;
 
 // ---------------------------------------------------------------  RESET 
 // ----------------------------------------------------------------------
-- 
cgit v1.2.1