Mercurial > ~dholland > hg > ag > index.cgi
view anagram/support/agbaltree-imp.h @ 17:12171da8943f
Don't refer to CVS.
author | David A. Holland |
---|---|
date | Tue, 31 May 2022 01:56:37 -0400 |
parents | 13d2b8934445 |
children |
line wrap: on
line source
/********************************************************** The AnaGram Class Library The AgBalancedTree Class Copyright 1997 Parsifal Software. All Rights Reserved. See the file COPYING for license and usage terms. ***********************************************************/ #ifndef AGBALTREE_IMP_H #define AGBALTREE_IMP_H #include "minmax.h" template <class T> void *AgBalancedTree<T>::Node::operator new(size_t n) { return malloc(n); } template <class T> void AgBalancedTree<T>::Node::operator delete(void *p) { free(p); } template <class T> AgBalancedTree<T>::Node::Node (const T &t) : left(0), right(0), data(t), count(1) { } template <class T> AgBalancedTree<T>::~AgBalancedTree() { delete root; } template <class T> AgBalancedTree<T>::Node::~Node() { //nodesDeleted++; //LOGV(nodesDeleted); delete left; delete right; } template <class T> AgBalancedTree<T> &AgBalancedTree<T>::reset() { delete root; root = 0; return *this; } template <class T> int AgBalancedTree<T>::operator < (const AgBalancedTree<T> &t) const { int n = min(size(), t.size()); int i = 0; while (i < n) { if ((*this)[i] < t[i]) { return 1; } if (t[i] < (*this)[i]) { return 0; } i++; } return size() < t.size(); } template <class T> void AgBalancedTree<T>::Node::resetCount() { count = 1; if (left) { count += left->count; } if (right) { count += right->count; } } template <class T> T &AgBalancedTree<T>::Node::locate(const unsigned x) const { //LOGSECTION("AgBalancedTree<T>::Node::locate"); unsigned leftCount = left ? left->count : 0; //LOGV(x) LCV(count) LCV(leftCount); if (x == leftCount) { return (T &) data; } if (x < leftCount) { return left->locate(x); } return right->locate(x - leftCount - 1); } template <class T> int AgBalancedTree<T>::compare(const T &x, const T &y) const { if (x < y) { return -1; } return y < x; } template <class T> unsigned AgBalancedTree<T>::size() const { return root != 0 ? root->count : 0; } template <class T> int AgBalancedTree<T>::includes(const T &t) const { if (root) { return includes(t, root); } else { return 0; } } template <class T> int AgBalancedTree<T>::lookup(T &t) const { if (root) { return lookup(t, root); } else { return 0; } } template <class T> int AgBalancedTree<T>::insert(const T &t) { if (root) { return insert(t, root); } root = new Node(t); return 0; } template <class T> int AgBalancedTree<T>::identify(T &t) { //LOGSECTION("AgBalancedTree::identify"); if (root) { return identify(t, root); } root = new Node(t); t = root->data; return 0; } template <class T> int AgBalancedTree<T>::identify(T *&t) { if (root) { return identify(t, root); } root = new Node(*t); t = &root->data; return 0; } template <class T> int AgBalancedTree<T>::remove(const T &t) { if (root) { return remove(t, root); } else { return 0; } } template <class T> int AgBalancedTree<T>::includes(const T &target, AgBalancedTree<T>::Node *node) const { int flag = compare(target, node->data); if (flag == 0) { return 1; } if (flag < 0 && node->left) { return includes(target, node->left); } if (flag > 0 && node->right) { return includes(target, node->right); } return 0; } template <class T> int AgBalancedTree<T>::lookup(T &target, AgBalancedTree<T>::Node *node) const { int flag = compare(target, node->data); if (flag == 0) { target = node->data; return 1; } if (flag < 0 && node->left) { return lookup(target, node->left); } if (flag > 0 && node->right) { return lookup(target, node->right); } return 0; } template <class T> AgBalancedTree<T> AgBalancedTree<T>::operator + (AgBalancedTree<T> &x) { AgBalancedTree<T> setUnion; int n = size(); while (n--) { setUnion.insert((*this)[n]); } n = x.size(); while (n--) { setUnion.insert(x[n]); } return setUnion; } template <class T> AgBalancedTree<T> AgBalancedTree<T>::operator - (AgBalancedTree<T> &x) { AgBalancedTree<T> difference; int n = size(); while (n--) { difference.insert((*this)[n]); } n = x.size(); while (n--) { difference.remove(x[n]); } return difference; } template <class T> AgBalancedTree<T> AgBalancedTree<T>::operator * (AgBalancedTree<T> &x) { AgBalancedTree<T> intersection; int n = size(); while (n--) { T &element = (*this)[n]; if (x.includes(element)) { intersection.insert(element); } } return intersection; } template <class T> AgBalancedTree<T> &AgBalancedTree<T>::operator *= (AgBalancedTree<T> &x) { int n = size(); while (n--) { T &element = (*this)[n]; if (!x.includes(element)) { remove(element); } } return *this; } template <class T> int AgBalancedTree<T>::insert(const T &target, AgBalancedTree<T>::Node *&node){ int flag = compare(target, node->data); if (flag == 0) { return 1; } if (flag < 0 && node->left == 0) { node->left = new Node(target); node->count++; return 0; } if (flag > 0 && node->right == 0) { node->right = new Node(target); node->count++; return 0; } if (flag < 0) { if (insert(target, node->left)) { return 1; } node->count++; unsigned newCount = node->left->count; unsigned oldCount = newCount-1; if ((oldCount^newCount) != (oldCount|newCount)) { return 0; } unsigned rightCount = node->right ? node->right->count : 0; if (newCount/2 > rightCount) { rotateRight(node); } } else { if (insert(target, node->right)) { return 1; } node->count++; unsigned newCount = node->right->count; unsigned oldCount = newCount-1; if ((oldCount^newCount) != (oldCount|newCount)) { return 0; } unsigned leftCount = node->left ? node->left->count : 0; if (newCount/2 > leftCount) { rotateLeft(node); } } return 0; } template <class T> int AgBalancedTree<T>::identify(T &target, Node *&node) { //LOGSECTION("AgBalancedTree::identify"); int flag = compare(target, node->data); if (flag == 0) { target = node->data; return 1; } if (flag < 0 && node->left == 0) { node->left = new Node(target); node->count++; target = node->left->data; return 0; } if (flag > 0 && node->right == 0) { node->right = new Node(target); node->count++; target = node->right->data; return 0; } if (flag < 0) { if (identify(target, node->left)) { return 1; } node->count++; unsigned newCount = node->left->count; unsigned oldCount = newCount-1; if ((oldCount^newCount) != (oldCount|newCount)) { return 0; } unsigned rightCount = node->right ? node->right->count : 0; if (newCount/2 > rightCount) { rotateRight(node); } } else { if (identify(target, node->right)) { return 1; } node->count++; unsigned newCount = node->right->count; unsigned oldCount = newCount-1; if ((oldCount^newCount) != (oldCount|newCount)) { return 0; } unsigned leftCount = node->left ? node->left->count : 0; if (newCount/2 > leftCount) { rotateLeft(node); } } return 0; } template <class T> int AgBalancedTree<T>::identify(T *&target, AgBalancedTree<T>::Node *&node) { int flag = compare(*target, node->data); if (flag == 0) { target = &node->data; return 1; } if (flag < 0 && node->left == 0) { node->left = new Node(*target); node->count++; target = &node->left->data; return 0; } if (flag > 0 && node->right == 0) { node->right = new Node(*target); node->count++; target = &node->right->data; return 0; } if (flag < 0) { if (identify(target, node->left)) { return 1; } node->count++; unsigned newCount = node->left->count; unsigned oldCount = newCount-1; if ((oldCount^newCount) != (oldCount|newCount)) { return 0; } unsigned rightCount = node->right ? node->right->count : 0; if (newCount/2 > rightCount) { rotateRight(node); } } else { if (identify(target, node->right)) { return 1; } node->count++; unsigned newCount = node->right->count; unsigned oldCount = newCount-1; if ((oldCount^newCount) != (oldCount|newCount)) { return 0; } unsigned leftCount = node->left ? node->left->count : 0; if (newCount/2 > leftCount) { rotateLeft(node); } } return 0; } template <class T> int AgBalancedTree<T>::remove(const T &target, AgBalancedTree<T>::Node *&node){ int flag = compare(target, node->data); if (flag < 0 && node->left) { unsigned oldCount = node->left->count; if (remove(target, node->left) == 0) { return 0; } node->count--; unsigned newCount = oldCount - 1; if ((oldCount^newCount) != (oldCount|newCount)) { return 1; } unsigned rightCount = node->right ? node->right->count : 0; if (rightCount/2 > newCount) { rotateLeft(node); } return 1; } if (flag > 0 && node->right) { unsigned oldCount = node->right->count; if (remove(target, node->right) == 0) { return 0; } node->count--; unsigned newCount = oldCount - 1; if ((oldCount^newCount) != (oldCount|newCount)) { return 1; } unsigned leftCount = node->left ? node->left->count : 0; if (leftCount/2 > newCount) { rotateRight(node); } return 1; } if (flag) { return 0; } if (node->count == 1) { delete node; node = 0; return 1; } unsigned leftCount = node->left ? node->left->count : 0; unsigned rightCount = node->right ? node->right->count : 0; Node *replacement; if (rightCount > leftCount) { replacement = extractMin(node->right); } else { replacement = extractMax(node->left); } replacement->left = node->left; replacement->right = node->right; node->left = node->right = 0; delete node; replacement->resetCount(); node = replacement; return 1; } template <class T> void AgBalancedTree<T>::rotateLeft(AgBalancedTree<T>::Node *&node) { Node *nRL = node->right->left; Node *nRR = node->right->right; unsigned leftCount = nRL ? nRL->count : 0; unsigned rightCount = nRR ? nRR->count : 0; if (leftCount < rightCount) { Node *replacement = node->right; Node *orphan = replacement->left; replacement->left = node; node->right = orphan; node->resetCount(); node = replacement; node->resetCount(); return; } Node *replacement = nRL; Node *leftOrphan = replacement->left; Node *rightOrphan = replacement->right; replacement->right = node->right; replacement->right->left = rightOrphan; replacement->right->resetCount(); replacement->left = node; replacement->left->right = leftOrphan; replacement->left->resetCount(); node = replacement; node->resetCount(); } template <class T> void AgBalancedTree<T>::rotateRight(AgBalancedTree<T>::Node *&node) { Node *nLR = node->left->right; Node *nLL = node->left->left; unsigned leftCount = nLL ? nLL->count : 0; unsigned rightCount = nLR ? nLR->count : 0; if (rightCount < leftCount) { Node *replacement = node->left; Node *orphan = replacement->right; replacement->right = node; node->left = orphan; node->resetCount(); node = replacement; node->resetCount(); return; } Node *replacement = nLR; Node *leftOrphan = replacement->left; Node *rightOrphan = replacement->right; replacement->left = node->left; replacement->left->right = leftOrphan; replacement->left->resetCount(); replacement->right = node; replacement->right->left = rightOrphan; replacement->right->resetCount(); node = replacement; node->resetCount(); } template <class T> typename AgBalancedTree<T>::Node * AgBalancedTree<T>::extractMin(typename AgBalancedTree<T>::Node *&node) { Node *result; if (node->left) { unsigned oldCount = node->left->count; result = extractMin(node->left); node->count--; unsigned newCount = oldCount - 1; if ((oldCount^newCount) != (oldCount|newCount)) { return result; } unsigned rightCount = node->right ? node->right->count : 0; if (rightCount/2 > newCount) { rotateLeft(node); } return result; } result = node; node = node->right; return result; } template <class T> typename AgBalancedTree<T>::Node * AgBalancedTree<T>::extractMax(typename AgBalancedTree<T>::Node *&node) { Node *result; if (node->right) { unsigned oldCount = node->right->count; result = extractMax(node->right); node->count--; unsigned newCount = oldCount - 1; if ((oldCount^newCount) != (oldCount|newCount)) { return result; } unsigned leftCount = node->left ? node->left->count : 0; if (leftCount/2 > newCount) { rotateRight(node); } return result; } result = node; node = node->left; return result; } #endif /* AGBALTREE_IMP_H */