/**********************************************************

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 */