/*
Copyright (C) 1997, 1998, 1999, 2000 by Alex Pfaffe
(Digital Dawn Graphics Inc)
This library is free software; you can redistribute it and/or
modify it under the terms of the GNU Library General Public
License as published by the Free Software Foundation; either
version 2 of the License, or (at your option) any later version.
This library is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
Library General Public License for more details.
You should have received a copy of the GNU Library General Public
License along with this library; if not, write to the Free
Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
*/
#ifndef _ddgSplay_Class_
#define _ddgSplay_Class_
#include "util/ddgerror.h"
class WEXP ddgSplayKey
{
unsigned int _key;
union {
unsigned int _value;
struct {
unsigned short _tree;
unsigned short _index;
} _ti;
};
public:
inline ddgSplayKey( void ) : _key(0), _value(0) { }
inline ddgSplayKey( unsigned int tree, unsigned int tindex, unsigned int priority )
{_key = priority; _ti._index = tindex; _ti._tree = tree; }
inline void set( ddgSplayKey sk )
{ _key = sk._key; _ti._index = sk._ti._index; _ti._tree = sk._ti._tree; }
inline int compare( ddgSplayKey sk )
{
if (_key < sk._key) return -1;
if (_key > sk._key) return 1;
if (_value < sk._value) return -1;
if (_value > sk._value) return 1;
// They are equal.
return 0;
}
inline unsigned int index(void)
{
return _ti._index;
}
inline unsigned int tree(void)
{
return _ti._tree;
}
inline unsigned int key(void)
{
return _key;
}
};
// 16 bit index allows for ddgSplay trees to maintain up to ~65000 entries.
class ddgSplayTree;
class ddgSplayIterator;
class ddgSplayNode;
typedef ddgSplayNode *ddgSplayIndex;
class WEXP ddgSplayNode
{
friend ddgSplayTree;
friend ddgSplayIterator;
ddgSplayKey _key;
ddgSplayIndex _left;
ddgSplayIndex _right;
public:
inline void set( ddgSplayKey k ) { _key.set(k); }
};
class WEXP ddgSplayTree
{
static ddgSplayIndex _nList;
static ddgSplayIndex _fList;
static unsigned int _refCount;
static unsigned int _maxSize;
static ddgSplayKey _minNode;
static ddgSplayKey _maxNode;
ddgSplayIndex _nullNode;
ddgSplayIndex _header;
unsigned int _size;
static unsigned int _totalSize;
ddgSplayIndex ddgSplay( ddgSplayKey Item, ddgSplayIndex n );
ddgSplayIndex SingleRotateWithLeft( ddgSplayIndex n );
ddgSplayIndex SingleRotateWithRight( ddgSplayIndex n );
public:
ddgSplayTree(void);
~ddgSplayTree(void);
ddgSplayIndex clear( ddgSplayIndex n );
inline ddgSplayIndex find( ddgSplayKey k, ddgSplayIndex n )
{ return ddgSplay( k, n ); }
inline ddgSplayIndex findMin( ddgSplayIndex n );
inline ddgSplayIndex findMax( ddgSplayIndex n );
ddgSplayIndex insert( ddgSplayKey k, ddgSplayIndex n );
ddgSplayIndex remove( ddgSplayKey k, ddgSplayIndex n );
private:
ddgSplayIndex _root;
public:
inline void clear( void ) { _root = clear(_root); }
inline void find( ddgSplayKey ti ) { _root = find(ti,_root); }
inline void findMin( void ) { _root = findMin(_root); }
inline void findMax( void ) { _root = findMax(_root); }
inline void insert( ddgSplayKey k ) { _root = insert(k,_root); }
inline void remove( ddgSplayKey k ) { _root = remove(k,_root); }
inline void insert( unsigned int tree, unsigned int tindex, unsigned int priority )
{ _root = insert(ddgSplayKey(tree,tindex,priority),_root); }
inline void remove( unsigned int tree, unsigned int tindex, unsigned int priority )
{ _root = remove(ddgSplayKey(tree,tindex,priority),_root); }
inline ddgSplayIndex root(void) { return _root; }
inline ddgSplayKey * retrieve(void) { return &(_root->_key); }
inline void data(ddgSplayKey k ) { _root->set(k); }
inline ddgSplayIndex left(ddgSplayIndex si)
{ return si->_left; }
inline ddgSplayIndex right(ddgSplayIndex si)
{ return si->_right; }
inline void left(ddgSplayIndex si, ddgSplayIndex sil)
{ si->_left = sil; }
inline void right(ddgSplayIndex si, ddgSplayIndex sir)
{ si->_right = sir; }
inline ddgSplayKey key(ddgSplayIndex si)
{ return si->_key; }
inline void key(ddgSplayIndex si, ddgSplayKey sk)
{ si->_key.set(sk); }
inline ddgSplayKey * retrieve(ddgSplayIndex si)
{ return &(si->_key); }
inline void data(ddgSplayKey k, ddgSplayIndex si )
{ si->set(k); }
ddgSplayIndex allocNode(void);
void freeNode(ddgSplayIndex n);
unsigned int size(void);
inline ddgSplayIndex null(void) { return _nullNode; }
inline bool isnull(ddgSplayIndex n) { return _nullNode == n; }
#ifdef _DEBUG
int printTree( ddgSplayIndex n );
#endif
};
class WEXP ddgSplayIterator
{
#define stackMax 10000
ddgSplayTree *_ddgSplaytree;
ddgSplayIndex _stack[stackMax];
ddgSplayIndex _current;
unsigned int _depth;
#ifdef _DEBUG
unsigned int _maxDepth;
#endif
public:
void reset(bool reverse = false)
{
#ifdef _DEBUG
_maxDepth = 0;
#endif
_depth = 0;
_current = _ddgSplaytree->root();
// find smallest (leftmost) or largest (rightmost) entry.
while (_current != _ddgSplaytree->null()) {
ddgAsserts(_depth < stackMax, "ddgSplay Iterator ran out of stack space");
#ifdef _DEBUG
if (_depth > _maxDepth) _maxDepth = _depth;
#endif
_stack[_depth] = _current;
_depth++;
_current = reverse ? _ddgSplaytree->right(_current) : _ddgSplaytree->left(_current);
}
if (_depth)
{
_depth--;
_current = _stack[_depth];
}
}
ddgSplayIterator( ddgSplayTree *st, bool reverse = false)
{
_ddgSplaytree = st;
reset(reverse);
}
inline void next(void)
{
if (_current != _ddgSplaytree->null())
{
_current = _ddgSplaytree->right(_current);
while (true)
{ // we'll use break to exit the loop
// If there is a left child, go to it.
if (_current != _ddgSplaytree->null())
{
ddgAsserts(_depth < stackMax, "ddgSplay Iterator ran out of stack space");
#ifdef _DEBUG
if (_depth > _maxDepth) _maxDepth = _depth;
#endif
_stack[_depth] = _current;
_depth++;
_current = _ddgSplaytree->left(_current);
}
else
{ // backtrack
if (_depth)
{
_depth--;
_current = _stack[_depth];
break;
}
else // stack is empty; done
{
_current = _ddgSplaytree->null();
break;
}
}
}
}
}
inline void prev(void)
{
if (_current != _ddgSplaytree->null())
{
_current = _ddgSplaytree->left(_current);
while (true)
{ // we'll use break to exit the loop
// If there is a right child, go to it.
if (_current != _ddgSplaytree->null())
{
ddgAsserts(_depth < stackMax, "ddgSplay Iterator ran out of stack space");
#ifdef _DEBUG
if (_depth > _maxDepth) _maxDepth = _depth;
#endif
_stack[_depth] = _current;
_depth++;
_current = _ddgSplaytree->right(_current);
}
else
{ // backtrack
if (_depth)
{
_depth--;
_current = _stack[_depth];
break;
}
else // stack is empty; done
{
_current = _ddgSplaytree->null();
break;
}
}
}
}
}
inline ddgSplayIndex current(void) { return _current; }
inline bool end(void) { return (_current == _ddgSplaytree->null()) ? true : false; }
};
#endif
