[PD-cvs] externals/grill/flext/source flsupport.cpp,1.51,1.52

[Thomas Grill]

Update of /cvsroot/pure-data/externals/grill/flext/source
In directory sc8-pr-cvs1.sourceforge.net:/tmp/cvs-serv23666/source

Modified Files:
	flsupport.cpp 
Log Message:


Index: flsupport.cpp
===================================================================
RCS file: /cvsroot/pure-data/externals/grill/flext/source/flsupport.cpp,v
retrieving revision 1.51
retrieving revision 1.52
diff -C2 -d -r1.51 -r1.52
*** flsupport.cpp	23 Apr 2005 09:06:25 -0000	1.51
--- flsupport.cpp	23 Apr 2005 09:14:20 -0000	1.52
***************
*** 327,562 ****
  }
  
- 
- TableAnyMap::~TableAnyMap() { clear(); }
- 
- void TableAnyMap::clear() 
- {
-     if(left) { _delmap(left); left = NULL; }
-     if(right) { _delmap(right); right = NULL; }
-     n = 0;
- }
- 
- 
- void *TableAnyMap::_set(int tsize,size_t k,void *t)
- {
-     FLEXT_ASSERT(n);
- 
-     if(n < tsize) {
-         // fall through
-     }
-     else if(k < data[0].key)
-         return _toleft(tsize,k,t);
-     else if(k > data[tsize-1].key)
-         return _toright(tsize,k,t);
- 
-     int ix = _tryix(k);
-     if(ix >= n) {
-         FLEXT_ASSERT(ix == n);
-         // after last entry
-         data[n++](k,t);
-         return NULL;
-     }
- 
-     size_t dk = data[ix].key;
-     if(k == dk) {
-         // update data in existing slot (same key)
-         void *a = data[ix].value;
-         data[ix] = t;
-         return a;
-     }
-     else {
-         // insert new slot by shifting the higher ones
-         FLEXT_ASSERT(k < dk);
-         void *a;
-         if(n == tsize)
-             a = _toright(tsize,data[tsize-1]);
-         else {
-             ++n;
-             a = NULL;
-         }
- 
-         Data *tg = data+ix;
-         for(Data *d = data+n-1; d > tg; d--) d[0] = d[-1];
-         (*tg)(k,t);
-         return a;
-     }
- }
- 
- void *TableAnyMap::_find(int tsize,size_t k) const
- {
-     FLEXT_ASSERT(n);
-     if(n < tsize) {
-         // fall through
-     }
-     else if(k < data[0].key)
-         return left?left->_find(tsize,k):NULL;
-     else if(k > data[n-1].key)
-         return right?right->_find(tsize,k):NULL;
- 
-     const int ix = _tryix(k);
-     return ix < n && data[ix].key == k?data[ix].value:NULL;
- }
- 
- #ifdef FLEXT_DEBUG
- void TableAnyMap::_check(int tsize)
- {
-     FLEXT_ASSERT(n);
- 
-     size_t k = data[0].key;
-     for(int i = 1; i < n; ++i) {
-         size_t k2 = data[i].key;
-         FLEXT_ASSERT(k < k2);
-         k = k2;
-     }
- 
-     if(left || right) FLEXT_ASSERT(n == tsize);
- 
-     if(left) { 
-         FLEXT_ASSERT(flext::MemCheck(left)); 
-         left->_check(tsize); 
-     }
-     if(right) { 
-         FLEXT_ASSERT(flext::MemCheck(right)); 
-         right->_check(tsize); 
-     }
- }
- #endif
- 
- void *TableAnyMap::_remove(int tsize,size_t k)
- {
-     FLEXT_ASSERT(n);
-     if(n < tsize) {
-         // fall through
-     }
-     else if(k < data[0].key) {
-         void *r = left?left->_remove(tsize,k):NULL;
-         if(r) _eraseempty(left);
-         return r;
-     }
-     else if(k > data[n-1].key) {
-         void *r = right?right->_remove(tsize,k):NULL;
-         if(r) _eraseempty(right);
-         return r;
-     }
- 
-     const int ix = _tryix(k);
-     if(ix >= n || data[ix].key != k)
-         return NULL;
-     else {
-         // found key in this map
-         void *ret = data[ix].value;
- 
-         Data dt;
-         bool fnd,ins = false;
-         if(n >= tsize) {
-             // if this table is full get fill-in elements from branches
-             if(left) {
-                 // try to get biggest element from left branch
-                 left->_getbig(dt);
-                 _eraseempty(left);
-                 fnd = true,ins = true;
-             }
-             else if(right) {
-                 // try to get smallest element from right branch
-                 right->_getsmall(dt);
-                 _eraseempty(right);
-                 fnd = true;
-             }
-             else
-                 fnd = false;
-         }
-         else fnd = false;
- 
-         if(ins) {
-             // insert smaller element from left
-             for(int i = ix; i; --i) data[i] = data[i-1];
-             data[0] = dt;
-         }
-         else {
-             // shift elements
-             for(int i = ix+1; i < n; ++i) data[i-1] = data[i];
-             // insert bigger element from right or reduce table size
-             if(fnd)
-                 data[n-1] = dt;
-             else
-                 --n;
-         }
- 
-         return ret;
-     }
- }
- 
- void TableAnyMap::_getbig(Data &dt)
- {
-     FLEXT_ASSERT(n);
- 
-     if(right) {
-         right->_getbig(dt);
-         _eraseempty(right);
-     }
-     else {
-         dt = data[n-1];
-         if(left) {
-             for(int i = n-1; i; --i) data[i] = data[i-1];
-             left->_getbig(data[0]);
-             _eraseempty(left);
-         }
-         else
-             --n;
-     }
- }
- 
- void TableAnyMap::_getsmall(Data &dt)
- {
-     FLEXT_ASSERT(n);
- 
-     if(left) {
-         left->_getsmall(dt);
-         _eraseempty(left);
-     }
-     else {
-         dt = data[0];
-         for(int i = 1; i < n; ++i) data[i-1] = data[i];
-         if(right) {
-             right->_getsmall(data[n-1]);
-             _eraseempty(right);
-         }
-         else
-             --n;
-     }
- }
- 
- void TableAnyMap::iterator::forward() 
- { 
-     if(map || ix >= map->n) {
-         if(++ix >= map->n) {
-             TableAnyMap *nmap;
- 
-             // we reached the end of the slots
-             if(map->right) {
-                 // climb up one
-                 map = map->right;
-                 leftmost();
-                 ix = 0;
-             }
-             else {
-                 // fall back
-                 for(;;) {
-                     nmap = map->parent;
-                     if(!nmap) break; // no parent
-                     if(nmap->left == map) {
-                         // ok, we are in front of the slots now
-                         ix = 0;
-                         map = nmap;
-                         break;
-                     }
-                     else {
-                         FLEXT_ASSERT(nmap->right == map);
-                         ix = (map = nmap)->n;
-                     }
-                 }
-             }
-         }
-     }
- }
- 
--- 327,328 ----