#ifndef PS_Tree_H
#define PS_Tree_H

// McCreights Radix Priority Search Tree (last updated Feb-21-2002
//
// only insert/delete/enumerate_rectangles implemented
//
// running times: insert pair O(log n)
//                remove pair O(log n)
//       enumerate rectangles O(log n + K)  (K hits)

/*
    (c) Michael Buro, mic@research.nj.nec.com
    NEC Research Institute
    4 Independence Way
    Princeton, NJ 08540, USA

    This program is free software; you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation; either version 2 of the License, or
    (at your option) any later version.

    This program 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 General Public License for more details.

    You should have received a copy of the GNU General Public License
    along with this program; if not, write to the Free Software
    Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
*/

#include "Global.H"

#define PS_TREE_STAT 0

#if PS_TREE_STAT
static uint4 ins_calls = 0;
static uint4 ins_n = 0;
static uint4 ins_nodes = 0;
#endif

template <class T> 
class Pair {
public:
  uint4 x, y;
  T data;

  void write(ostream &os = cout) const {
    os << "(" << x << "," << y << "| " << data << ")";
  }
};

template <class T>
class Node {
public:
  
  Pair<T> pair;
  Node *left, *right;

  Node() {
    left = right = 0;
  }

  virtual ~Node() {
    if (right) delete right;
    if (left)  delete left;
  }
};

template <class T>
class PS_Tree {

protected:

  Node<T> *root;
  uint4 ub; // upper bound for all values
  uint4 num;
  
public:

  PS_Tree(uint4 ub_ = 65536) {
    set_ub(ub_);
    root = 0;
    num = 0;
  }

  virtual ~PS_Tree() {
    if (root) { delete root; root = 0; }
  }

  // set upper bound for all values
  
  void set_ub(uint4 ub_) {
    assert(ub_ > 1);
    ub = ub_;
  }

  uint4 size() const { return num; }

  // insert pair stored in a node (complain if already there)
  // note: all x values have to be different!!!
  //       if you have pairs with equal x's you can add different
  //       epsilons to them for instance.

  void insert_node(Node<T> *node) {

    // cout << "insert: "; pair.write(cout); cout << endl;
    
    assert(node->pair.x >= 0 && node->pair.x < ub &&
	   node->pair.y >= 0 && node->pair.y <= ub);
    
    if (!insert_node(root, node, 0, ub)) ERR("insert_pair failed");
    num++;

#if PS_TREE_STAT    
    ins_n++; ins_nodes += num-1;
    if ((ins_n & 1023) == 0) {
      cout << ins_n << " "
	   << (real8(ins_calls)/ins_n) << " "
	   << (real8(ins_nodes)/ins_n) << " "
	   << endl;    
    }
#endif
    
  }

  
  // find and remove pair from tree (return 0 if it doesn't exist)
  // time O(log n) for tree size n
  
  Node<T> *remove_pair(const Pair<T> &pair) {
    assert(pair.x >= 0 && pair.x < ub && pair.y >= 0 && pair.y < ub);

    // cout << "delete: "; pair.write(cout); cout << endl;    

    Node<T> *p = remove_pair(root, pair, 0, ub);

    if (p) num--;
    return p;
  }

  // enumerate all pairs (x,y) with x0 <= x <= x1 and y <= y1
  // time:  O(log n) + K  (n pairs, K hits)
  
  void enumerate_rectangles(uint4 x0, uint4 x1, uint4 y1,
			    vector<Pair<T>*> &out)
  {
    assert(x0 >= 0 && x0 < ub && x1 >= 0 && x1 <= ub && y1 >= 0 && y1 <= ub);
    out.clear();
    enumerate_rectangles(root, x0, x1, y1, 0, ub, out);
  }

  void write(ostream &os = cout) const { write(root, os, 0); }
    
protected:
  
  Node<T> *insert_node(Node<T>* &t, Node<T> *node, uint4 lowerx, uint4 upperx)
  {
#if PS_TREE_STAT    
    ins_calls++;
#endif
    
    if (t == 0) { // empty tree -> insert
      t = node;
      t->left = t->right = 0;
      return t;
    }

    if (t->pair.x == node->pair.x) return 0; // equal x

    if (node->pair.y < t->pair.y) {

      // new pair is better -> push previous down

      Pair<T> temp = t->pair;
      t->pair = node->pair;
      node->pair = temp;
    }

    uint4 middlex = (lowerx + upperx) / 2;

    if (node->pair.x < middlex) // was pair.x
      return insert_node(t->left, node, lowerx, middlex);
    else
      return insert_node(t->right, node, middlex, upperx);
  }


  Node<T> *remove_pair(Node<T> *&t, const Pair<T> &old_pair,
		       uint4 lowerx, uint4 upperx)
  {
    if (t == 0) return 0; // not found

    if (t->pair.x == old_pair.x) {

      assert(t->pair.y == old_pair.y);
      
      // pair found -> move successors up
      
      if (t->left != 0) {
	
	if (t->right != 0) {
	  
	  if (t->left->pair.y < t->right->pair.y) {
	    
	    t->pair = t->left->pair;
	    return remove_pair(t->left, t->pair, lowerx, upperx);
	    
	  } else {
	    
	    t->pair = t->right->pair;
	    return remove_pair(t->right, t->pair, lowerx, upperx);
	  }
	  
	} else {
	  
	  t->pair = t->left->pair;
	  return remove_pair(t->left, t->pair, lowerx, upperx);
	}
	
      } else if (t->right != 0) {
	
	// only right subtree exists
	
	t->pair = t->right->pair;
	return remove_pair(t->right, t->pair, lowerx, upperx);
	
      } else {

	Node<T> *p = t;
	t = 0;
	return p;
      }

    } else {

      // pair to be deleted in a subtree

      uint4 middlex = (lowerx + upperx)/2;

      if (old_pair.x < middlex)
	return remove_pair(t->left, old_pair, lowerx, middlex);
      else
	return remove_pair(t->right, old_pair, middlex, upperx);
    }
  }


  void enumerate_rectangles(Node<T> *t, uint4 x0, uint4 x1, uint4 y1,
			    uint4 lowerx, uint4 upperx,
			    vector<Pair<T>*> &out)
  {
    if (t == 0) return;

    if (t->pair.y <= y1) {  // node within y1 constraint

      if (x0 <= t->pair.x && t->pair.x <= x1) {
	out.push_back(&t->pair);
      }

      uint4 middlex = (lowerx + upperx) / 2;
      if (x0 < middlex) enumerate_rectangles(t->left, x0, x1, y1,
					     lowerx, middlex, out);
      if (middlex <= x1) enumerate_rectangles(t->right, x0, x1, y1,
					      middlex, upperx, out);
    }
  }
  
  void write(Node<T> *t, ostream &os, sint4 depth) const {
    if (t == 0) return;
    write(t->left, os, depth+1);
    FORS (i, depth) { os << " "; }
    t->pair.write(os); os << endl;
    write(t->right, os, depth+1);    
  }

};

#endif