--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/anagram/support/agbaltree-imp.h	Sat Dec 22 17:52:45 2007 -0500
@@ -0,0 +1,590 @@
+/**********************************************************
+
+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 */