aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorThomas Grill <xovo@users.sourceforge.net>2005-05-02 22:07:18 +0000
committerThomas Grill <xovo@users.sourceforge.net>2005-05-02 22:07:18 +0000
commit350411c85b234009b3d113f581a8f24e80ed31c2 (patch)
tree204fd50369477230834cc7f238af480eb495cc73
parentbf1bd0b97f46224b8a639303919f191698771684 (diff)
use index bit-reversal to pseudo-balance the map tree
svn path=/trunk/externals/nusmuk/; revision=2883
-rw-r--r--msd.h31
1 files changed, 28 insertions, 3 deletions
diff --git a/msd.h b/msd.h
index 3964cdb..c08f15b 100644
--- a/msd.h
+++ b/msd.h
@@ -215,11 +215,20 @@ 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
// ----------------------------------------------------------------------