[PD-cvs] externals/nusmuk msd.h,1.1,1.2

Update of /cvsroot/pure-data/externals/nusmuk In directory sc8-pr-cvs1.sourceforge.net:/tmp/cvs-serv26016

Modified Files: msd.h Log Message: use index bit-reversal to pseudo-balance the map tree

Index: msd.h =================================================================== RCS file: /cvsroot/pure-data/externals/nusmuk/msd.h,v retrieving revision 1.1 retrieving revision 1.2 diff -C2 -d -r1.1 -r1.2 *** msd.h 2 May 2005 15:39:24 -0000 1.1 --- msd.h 2 May 2005 22:07:18 -0000 1.2 *************** *** 216,224 ****

template <typename T> class IndexMap ! : public TablePtrMap<int,T,16> { public: ! typedef TablePtrMap<int,T,16> Parent; virtual ~IndexMap() { reset(); } --- 216,233 ----

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 ! : TablePtrMap<unsigned int,T,16> { public: ! typedef TablePtrMap<unsigned int,T,16> Parent; virtual ~IndexMap() { reset(); } *************** *** 230,234 **** --- 239,259 ---- 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()); } + }; };

*************** *** 322,326 **** t_float limit[N][2]; // Limit values ! int id_mass, id_link;

// --------------------------------------------------------------- RESET --- 347,351 ---- t_float limit[N][2]; // Limit values ! unsigned int id_mass, id_link;

// --------------------------------------------------------------- RESET