pd-flext-dev 0.6.0+git20161101.1.01318a94-2 / usr / include / flext / flmap.cpp

/*
flext - C++ layer for Max and Pure Data externals

Copyright (c) 2001-2015 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.
*/

#ifndef __FLEXT_MAP_CPP
#define __FLEXT_MAP_CPP

#include "flext.h"
#include "flmap.h"

#include "flpushns.h"

FLEXT_TEMPIMPL(TableAnyMap)::~TableAnyMap() { clear(); }

FLEXT_TEMPIMPL(void TableAnyMap)::clear()
{
    if(left) { _delmap(left); left = NULL; }
    if(right) { _delmap(right); right = NULL; }
    n = 0;
}

FLEXT_TEMPIMPL(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;
    }
}

FLEXT_TEMPIMPL(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
FLEXT_TEMPIMPL(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

FLEXT_TEMPIMPL(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;
    }
}

FLEXT_TEMPIMPL(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;
    }
}

FLEXT_TEMPIMPL(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;
    }
}

FLEXT_TEMPIMPL(void TableAnyMap)::iterator::forward()
{ 
    FLEXT_ASSERT(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;
				}
			}
		}
	}
}

#include "flpopns.h"

#endif // __FLEXT_MAP_CPP