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

[Thomas Grill]

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