package org.fda.intervaltree;

import java.io.Serializable;
import java.util.ArrayList;
import java.util.List;


public class IntervalSearchTree  implements Serializable{

    private static final long serialVersionUID = 112414357102382689L;
    
    protected Node root;   // root of the BST
   
    
    public Long inOrderPrint(){
        return inorderTraversal4Print(root);
        
    }
    private Long inorderTraversal4Print(Node n){
        long toRet = 0L;
        if(n!=null){
            toRet = toRet + inorderTraversal4Print(n.left);
            if(n.interval instanceof Interval)
                System.out.println(((Interval)n.interval).toStringWSubIntervals());
            else
                System.out.println(n.interval.toString());
            toRet = toRet + n.interval.getlength();            
            toRet = toRet + inorderTraversal4Print(n.right);
        }
        return toRet;
    }

    public List<Interval> inOrder(){
        List<Interval> list = new ArrayList();
        inorderTraversal(root, list);
        return list;
        
    }
    private void inorderTraversal(Node n, List<Interval> list){
        
        if(n!=null){
            inorderTraversal(n.left, list);
            
            list.add(n.interval);
            
            inorderTraversal(n.right, list);
        }
        //return toRet;
    }

    
   /***************************************************************************
    *  BST search
    ***************************************************************************/

    public boolean contains(Interval interval, List<Interval> emptyList) {
        return (get(interval, emptyList) != null);
    }

    // return the node with the given interval in the BST
    // if no such interval, return null
    private Node get(Interval interval, List<Interval> emptyList) {
        return get(root, interval, emptyList);
    }

    private Node get(Node x, Interval interval, List<Interval> emptyList) {
        if (x == null)                  return null;
        int cmp = interval.compareTo(x.interval);
        if      (cmp < 0) {
            return get(x.left, interval, emptyList);
        }
        else if (cmp > 0) {
            return get(x.right, interval, emptyList);
        }
        else{
            emptyList.add(x.interval);            
            return x;
        }
    }


    public synchronized boolean put(Interval interval) {
        List<Interval> lst=new ArrayList<>();
        if (!contains(interval, lst)) { 
            root = randomizedInsert(root, interval);
            return true;
        }
        else{
            return false;
        }
    }

    // make new node the root with uniform probability
    protected Node randomizedInsert(Node x, Interval interval) {
        if (x == null) return new Node(interval);
        if (Math.random() * size(x) < 1.0) return rootInsert(x, interval);
        int cmp = interval.compareTo(x.interval);
        if (cmp < 0)  x.left  = randomizedInsert(x.left,  interval);
        else          x.right = randomizedInsert(x.right, interval);
        fix(x);
        return x;
    }

    private Node rootInsert(Node x, Interval interval) {
        if (x == null) return new Node(interval);
        int cmp = interval.compareTo(x.interval);
        if (cmp < 0) { x.left  = rootInsert(x.left,  interval); x = rotR(x); }
        else         { x.right = rootInsert(x.right, interval); x = rotL(x); }
        return x;
    }


   /***************************************************************************
    *  deletion
    ***************************************************************************/
    private Node joinLR(Node a, Node b) { 
        if (a == null) return b;
        if (b == null) return a;

        if (Math.random() * (size(a) + size(b)) < size(a))  {
            a.right = joinLR(a.right, b);
            fix(a);
            return a;
        }
        else {
            b.left = joinLR(a, b.left);
            fix(b);
            return b;
        }
    }

    // remove and return value associated with given interval;
    // if no such interval exists return null
    public boolean remove(Interval interval) {
        List<Interval> lst = new ArrayList<>();
        Node n = get(interval, lst);
        root = remove(root, interval);
        return (n!= null);        
    }

    private Node remove(Node h, Interval interval) {
        if (h == null) return null;
        int cmp = interval.compareTo(h.interval);
        if      (cmp < 0) h.left  = remove(h.left,  interval);
        else if (cmp > 0) h.right = remove(h.right, interval);
        else              h = joinLR(h.left, h.right);
        fix(h);
        return h;
    }


   /***************************************************************************
    *  BasicInterval searching
    ***************************************************************************/

    // return an interval in data structure that intersects the given inteval;
    // return null if no such interval exists
    // running time is proportional to log N
    public Interval search(Interval interval) {
        return search(root, interval);
    }

    // look in subtree rooted at x
    private Interval search(Node x, Interval interval) {
        while (x != null) {
            if (interval.intersects(x.interval))  return x.interval;
            else if (x.left == null)             x = x.right;
            else if (x.left.max < interval.getlow())  x = x.right;
            else                                 x = x.left;
        }
        return null;
    }


    // return *all* intervals in data structure that intersect the given interval
    // running time is proportional to R log N, where R is the number of intersections
    public List<Interval> searchAll(Interval interval) {
        List<Interval> list = new ArrayList<>();
        searchAll(root, interval, list);
        return list;
    }

    // look in subtree rooted at x
    public boolean searchAll(Node x, Interval interval, List<Interval> list) {
         boolean found1 = false;
         boolean found2 = false;
         boolean found3 = false;
         if (x == null)
            return false;
        if (interval.intersects(x.interval)) {
            list.add(x.interval);
            found1 = true;
        }
        if (x.left != null && x.left.max >= interval.getlow())
            found2 = searchAll(x.left, interval, list);
        if (found2 || x.left == null || x.left.max < interval.getlow())
            found3 = searchAll(x.right, interval, list);
        return found1 || found2 || found3;
    }


   /***************************************************************************
    *  useful binary tree functions
    ***************************************************************************/

    // return number of nodes in subtree rooted at x
    public int size() { return size(root); }
    private int size(Node x) { 
        if (x == null) return 0;
        else           return x.N;
    }

    // height of tree (empty tree height = 0)
    public int height() { return height(root); }
    private int height(Node x) {
        if (x == null) return 0;
        return 1 + Math.max(height(x.left), height(x.right));
    }


   /***************************************************************************
    *  helper BST functions
    ***************************************************************************/

    // fix auxilliar information (subtree count and max fields)
    private void fix(Node x) {
        if (x == null) return;
        x.N = 1 + size(x.left) + size(x.right);
        x.max = max3(x.interval.gethigh(), max(x.left), max(x.right));
    }

    private int max(Node x) {
        if (x == null) return Integer.MIN_VALUE;
        return x.max;
    }

    // precondition: a is not null
    private int max3(int a, int b, int c) {
        return Math.max(a, Math.max(b, c));
    }

    // right rotate
    private Node rotR(Node h) {
        Node x = h.left;
        h.left = x.right;
        x.right = h;
        fix(h);
        fix(x);
        return x;
    }

    // left rotate
    private Node rotL(Node h) {
        Node x = h.right;
        h.right = x.left;
        x.left = h;
        fix(h);
        fix(x);
        return x;
    }


   /***************************************************************************
    *  Debugging functions that test the integrity of the tree
    ***************************************************************************/

    // check integrity of subtree count fields
    public boolean check() { return checkCount() && checkMax(); }

    // check integrity of count fields
    private boolean checkCount() { return checkCount(root); }
    private boolean checkCount(Node x) {
        if (x == null) return true;
        return checkCount(x.left) && checkCount(x.right) && (x.N == 1 + size(x.left) + size(x.right));
    }

    private boolean checkMax() { return checkMax(root); }
    private boolean checkMax(Node x) {
        if (x == null) return true;
        return x.max ==  max3(x.interval.gethigh(), max(x.left), max(x.right));
    }
    
    public static void main(String[] args){
        IntervalSearchTree bst = new IntervalSearchTree();
        try{
            Interval a = new Interval(10,20, false);
            Interval b = new Interval(10,20, false);
            Interval c = new Interval(1,2, false);
            bst.put(a);
            bst.put(b);
            bst.put(c);
            bst.remove(a);
            List<Interval> it = bst.searchAll(a);
            System.out.println(it.size());
        }
        catch(Exception e){e.printStackTrace();}
                
    }
}
