aboutsummaryrefslogtreecommitdiff
path: root/externals/grill/flext/source
diff options
context:
space:
mode:
Diffstat (limited to 'externals/grill/flext/source')
-rw-r--r--externals/grill/flext/source/flmap.cpp249
1 files changed, 0 insertions, 249 deletions
diff --git a/externals/grill/flext/source/flmap.cpp b/externals/grill/flext/source/flmap.cpp
deleted file mode 100644
index 117f0896..00000000
--- a/externals/grill/flext/source/flmap.cpp
+++ /dev/null
@@ -1,249 +0,0 @@
-/*
-
-flext - C++ layer for Max/MSP and pd (pure data) externals
-
-Copyright (c) 2001-2005 Thomas Grill (gr@grrrr.org)
-For information on usage and redistribution, and for a DISCLAIMER OF ALL
-WARRANTIES, see the file, "license.txt," in this distribution.
-
-*/
-
-/*! \file flmap.cpp
- \brief flext container classes.
-*/
-
-#include "flext.h"
-#include "flmap.h"
-
-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;
- }
- }
- }
- }
- }
-}