/*
 * @(#)SegmentTree.java  1.0  2010-12-25
 *
 * Copyright (c) 2000-2010 Werner Randelshofer, Immensee, Switzerland.
 * All rights reserved.
 *
 * You may not use, copy or modify this file, except in compliance with the
 * license agreement you entered into with Werner Randelshofer.
 * For details see accompanying license terms.
 */
package ch.randelshofer.segmenttree;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.Hashtable;
import java.util.LinkedList;
import java.util.ListIterator;
import java.util.Queue;
import java.util.Set;
import java.util.Stack;


/**
 * SegmentTree.
 */
public class SegmentTree<T extends Segment> {

    protected ArrayList<T> edges = null;
    protected SegmentNode<T> root = null;
    protected ArrayList<Integer> sortedEndpoints = null;

    /**
     * Constructore for T tree
     * @param edges all edges in the "world" the tree might contain
     */
    public SegmentTree(ArrayList<T> edges) {
        this.edges = edges;
        if (!buildEmptyTree(this.edges)) {
            System.err.println("Error in intializing empty segment tree");
        }
    }

    //Asuming edges are sorted
    //Creating sorted enpoints
    private ArrayList<Integer> sortEndpoints(ArrayList<T> edges) {
        HashMap<Integer, Boolean> endpointsHash = new HashMap<Integer, Boolean>();

        for (int i = 0; i < edges.size(); i++) {
            T seg = edges.get(i);
            int point1 = getSegStart(seg);
            int point2 = getSegEnd(seg);

            endpointsHash.put(point1, true);
            endpointsHash.put(point2, true);


        }
        Set<Integer> keys = endpointsHash.keySet();

        ArrayList<Integer> endpointsList = new ArrayList<Integer>(keys);
        Collections.sort(endpointsList);
        return endpointsList;


    }

    private boolean buildEmptyTree(ArrayList<T> edges) {
        this.sortedEndpoints = sortEndpoints(edges);

        if (this.sortedEndpoints.size() <= 1) {
            System.err.println("Error, bad number of endpoints " + this.sortedEndpoints.size());

            return false;
        }
        Queue<SegmentNode<T>> q = new LinkedList<SegmentNode<T>>();
        int begin = this.sortedEndpoints.get(0);
        int end = this.sortedEndpoints.get(this.sortedEndpoints.size() - 1);
        this.root = createTreeNode(begin, end);
        q.add(this.root);

        // System.out.println("("+this.root.getStart()+"  "+this.root.getEnd()+")");

        while (!q.isEmpty()) {
            SegmentNode<T> parent = q.poll();
            // System.out.println("("+parent.getStart()+"  "+parent.getEnd());
            int beginIndex = this.sortedEndpoints.indexOf(parent.getStart());
            int endIndex = this.sortedEndpoints.indexOf(parent.getEnd());
            int median = (beginIndex + endIndex) / 2;
            if (endIndex == (beginIndex + 1)) {
                continue;
            }
            SegmentNode<T> leftSon = createTreeNode(parent.getStart(), this.sortedEndpoints.get(median));
            parent.setLeftSon(leftSon);
            SegmentNode<T> rightSon = createTreeNode(this.sortedEndpoints.get(median), parent.getEnd());
            parent.setRightSon(rightSon);
            q.add(leftSon);
            q.add(rightSon);

        }
        return true;
    }

    public boolean insert(T seg) {
        if (this.root == null) {
            System.err.println("Error, tree not initialized");
        }
        int b = getSegStart(seg);
        int e = getSegEnd(seg);

//		 if the seg is downward or backward direction
        if (b > e) {
            b = getSegEnd(seg);
            e = getSegStart(seg);
        }

        Stack<SegmentNode<T>> s = new Stack<SegmentNode<T>>();
        s.push(this.root);

        while (!s.isEmpty()) {
            SegmentNode<T> tNode = s.pop();

            if (b <= tNode.getStart() && tNode.getEnd() <= e) {
                tNode.insertData(seg);

                continue;
            }

            if (tNode.rightSon() != null) {
                if (tNode.rightSon().getStart() < e) {
                    s.push(tNode.rightSon());
                }
            }
            if (tNode.leftSon() != null) {
                if (b < tNode.leftSon().getEnd()) {
                    s.push(tNode.leftSon());
                }
            }
        }
        return true;
    }

    public boolean remove(T seg) {
        if (this.root == null) {
            System.err.println("Error, tree not initialized");
        }
        int b = getSegStart(seg);
        int e = getSegEnd(seg);

        // if the seg is downward or backward direction
        if (b > e) {
            b = getSegEnd(seg);
            e = getSegStart(seg);
        }

        Stack<SegmentNode<T>> s = new Stack<SegmentNode<T>>();
        s.push(this.root);

        while (!s.isEmpty()) {
            SegmentNode<T> tNode = s.pop();

            if (b <= tNode.getStart() && tNode.getEnd() <= e) {
                tNode.removeData(seg);
                continue;
            }

            if (tNode.rightSon() != null) {
                if (tNode.rightSon().getStart() < e) {
                    s.push(tNode.rightSon());
                }
            }
            if (tNode.leftSon() != null) {
                if (b < tNode.leftSon().getEnd()) {
                    s.push(tNode.leftSon());
                }
            }
        }

        return true;
    }

    public SegmentNode<T> getRoot() {
        return root;
    }

    private int getSegStart(T seg) {
        return seg.getStart();
    }

    private int getSegEnd(T seg) {
        return seg.getEnd();
    }

    protected SegmentNode<T> createTreeNode(int begin, int end) {
        SegmentNode<T> newNode = new SegmentNode<T>(begin, end);
        return newNode;

    }

    public ArrayList<Integer> stabbingQuery(int coord) {
        Hashtable<Integer, Boolean> res = new Hashtable<Integer, Boolean>();


        Stack<SegmentNode<T>> s = new Stack<SegmentNode<T>>();
        s.push(this.root);

        while (!s.isEmpty()) {
            SegmentNode<T> tNode = s.pop();
            for (int i = 0; i < tNode.getData().size(); i++) {
                res.put((Integer) tNode.getData().get(i), true);
            }

            if (tNode.rightSon() != null) {
                if (tNode.rightSon().getStart() <= coord) {
                    s.push(tNode.rightSon());
                }
            }
            if (tNode.leftSon() != null) {
                if (coord <= tNode.leftSon().getEnd()) {
                    s.push(tNode.leftSon());
                }
            }
        }

        return new ArrayList<Integer>(res.keySet());

    }

    public ArrayList<Integer> rangeQuery(int begin, int end) {
        Hashtable<Integer, Boolean> result = new Hashtable<Integer, Boolean>();
        int startPoint = sortedEndpoints.indexOf(begin);
        int endPoint = sortedEndpoints.indexOf(end);
        for (int i = startPoint; i <= endPoint; i++) {
            int qPoint = sortedEndpoints.get(i);
            ArrayList qEdges = stabbingQuery(qPoint);
            ListIterator it = qEdges.listIterator();
            while (it.hasNext()) {
                result.put((Integer) it.next(), true);
            }
        }
        return new ArrayList<Integer>(result.keySet());
    }

    public static <T extends Segment> void printSegmentTree(SegmentTree<T> t) {
        SegmentNode<T> root = t.getRoot();

        Queue<SegmentNode<T>> q = new LinkedList<SegmentNode<T>>();

        q.add(root);

        int i = 1;
        int level = 0;
        while (!q.isEmpty()) {
            i--;
            SegmentNode<T> current = q.poll();
            System.out.print("  (" + current.getStart() + " " + current.getEnd() + ") ");
            System.out.print("edges: " + current.getData().toString() + ".");
            if (i == 0) {
                System.out.print("\n");
                level++;
                i = (int) Math.pow(2, level);
            }
            if (current.leftSon() != null) {
                q.add(current.leftSon());
            }
            if (current.rightSon() != null) {
                q.add(current.rightSon());
            }
        }


    }
}		
