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

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_H
#define AGBALTREE_H

#include <stdlib.h>
#include "port.h"

#include "agcontainer.h"


template <class T>
class AgBalancedTree : public AgIndexedContainer<T> {
public:

  // Define Node
  class Node {
  public:
    Node *left, *right;
    T data;
    unsigned count;
    Node (const T &t);
    ~Node();
    void resetCount();
    T &locate(const unsigned x) const;
    void *operator new(size_t);
    void operator delete(void *);
  };

  Node *root;
  virtual int compare(const T &x, const T &y) const;

  // Process methods
  int insert(const T &target, Node *&node);
  int identify(T &target, Node *&node);
  int identify(T *&target, Node *&node);
  int remove(const T &target, Node *&node);
  int includes(const T &target, Node *node) const;
  int lookup(T &target, Node *node) const;

  void rotateLeft(Node *&node);
  void rotateRight(Node *&node);

  Node *extractMin(Node *&node);
  Node *extractMax(Node *&node);

  // default comparison function

public:
  AgBalancedTree() : AgIndexedContainer<T>(), root(0) {}
  virtual ~AgBalancedTree();
  int insert(const T &t);
  int identify(T &t);
  int identify(T *&t);
  int remove(const T &t);
  int includes(const T &t) const;
  int lookup(T &t) const;
  AgBalancedTree<T> &reset();
  unsigned size() const;
  void *operator new(size_t n) { return malloc(n); }
  void operator delete(void *p) { free(p); }
  const T &operator [] (const unsigned x) const { return root->locate(x); }
  T &operator [] (const unsigned x) { return root->locate(x); }
  AgBalancedTree<T> operator + (AgBalancedTree<T> &x);
  AgBalancedTree<T> operator * (AgBalancedTree<T> &x);
  AgBalancedTree<T> &operator *= (AgBalancedTree<T> &x);
  AgBalancedTree<T> operator - (AgBalancedTree<T> &x);
  int operator < (const AgBalancedTree<T> &) const;
};


#endif /* AGBALTREE_H */