package Current.search.basic;

import java.awt.geom.GeneralPath;
import java.util.ListIterator;

import Current.basic.*;

/**
 * This class stores the information necessary to run the
 * search algorithm for periodic billiard paths in triangles.
 */
public class MarkedSlalomHull{
    /** possible return value for call to merge() */
    public static final int SUCCESS=0;
    /** possible return value for call to merge() */
    public static final int BENDS_LEFT=1;
    /** possible return value for call to merge() */
    public static final int BENDS_RIGHT=2;
    
    // left side and right side of the hull
    // both of these will be lists containing Complex numbers
    MarkedComplexList ls,rs;
    
    public static class DataBackup {
        public MarkedComplex [] left,right;
        public DataBackup(MarkedComplex []l, MarkedComplex []r){
            left=l;
            right=r;
        }
    }
    
    
    /** Constuct a SlalomHull with one point on the left and one
     * on the right.
     */
    public MarkedSlalomHull(MarkedComplex left, MarkedComplex right){
        ls=new MarkedComplexList();
        ls.addLast(left);
        rs=new MarkedComplexList();
        rs.addLast(right);
    }
    
    public final DataBackup backup(){
        return new DataBackup(ls.extractData(), rs.extractData());
    }
    
    public final void recover(DataBackup db) {
        ls.replaceData(db.left);
        rs.replaceData(db.right);
    }
    
    /** return the number of vertices in the hull */
    public final int size(){
        return ls.size()+rs.size();
    }
    
    public final int leftSize(){
        return ls.size();
    }
    
    public final int rightSize(){
        return ls.size();
    }
    
    
//    /** remove the last left element from the hull */
//    private final boolean removeLastLeft() {
//        return ls.removeLast();
//    }
//    
//    /** remove the right left element from the hull */
//    private final boolean removeLastRight() {
//        return rs.removeLast();
//    }
//    
//    /** remove the first left element from the hull */
//    private final boolean removeFirstLeft() {
//        return ls.removeFirst();
//    }
//    
//    /** remove the right left element from the hull */
//    private final boolean removeFirstRight() {
//        return rs.removeFirst();
//    }
    
    /** Return false if adding z to the left will result in the hull being destroyed. Otherwise
     * return true;
     */
    public final boolean survivesLeftLastAdd(Complex z){
        return !(TriangleGeometry.sign(rs.getLast(),ls.getFirst(),z)==1);
    }
    
    /** Return false if adding z to the left will result in the hull being destroyed. Otherwise
     * return true;
     */
    public final boolean survivesLeftFirstAdd(Complex z){
        return !(TriangleGeometry.sign(rs.getFirst(),ls.getLast(),z)==-1);
    }
    
    
    /** Return false if adding z to the right will result in the hull being destroyed. Otherwise
     * return true;
     */
    public final boolean survivesRightLastAdd(Complex z){
        return !(TriangleGeometry.sign(ls.getLast(),rs.getFirst(),z)==-1);
    }
    
    /** Return false if adding z to the right will result in the hull being destroyed. Otherwise
     * return true;
     */
    public final boolean survivesRightFirstAdd(Complex z){
        return !(TriangleGeometry.sign(ls.getFirst(),rs.getLast(),z)==1);
    }    
    
    
    
    /** Add a point to the left side of the hull.
     * <br><br>
     * If the function returns false, adding further points
     * to the hull will result in errors.
     *
     * @return true if succeeds, false if the hull is destroyed or if a marked point is removed
     * (that is, there is no line which stays to left of the points
     * in the left side of the hull and right of the ones on the right)
     */
    public final boolean addToLeftLast(Complex z) {
        //System.out.println("rs_first x="+rs.getFirst().x+" y="+rs.getFirst().y);
        //System.out.println("ls_last x="+ls.getLast().x+" y="+ls.getLast().y);
        
        if (TriangleGeometry.sign(rs.getFirst(),z,ls.getLast())==1) {
            // the point belongs in the hull
            
            // first try to remove vertices from the hull on the right side
            while ((rs.size()>1)&&(TriangleGeometry.sign(rs.getFirst(),z,
            rs.getSecond())==1))
                // permenantly remove the first on the right side
                if (rs.removeFirst()) 
                    return false;
            
            if ((rs.size()==1)&&(TriangleGeometry.sign(ls.getFirst(),z,
            rs.getFirst())==1))
                // rs.getFirst() should also be removed
                // now the right side contains no elements.
                // thus the hull has degenerated
                return false;
            
            
            // now look at the left
            while ((ls.size()>1)&&(TriangleGeometry.sign(ls.getSecondToLast(),z,
            ls.getLast())==1))
                // remove the last point from the left side permenently, and move on.
                if (ls.removeLast())
                    return false;
            
            if ((ls.size()==1)&&(TriangleGeometry.sign(z,rs.getLast(),ls.getFirst())==1)) {
                // we should remo0ve the last remaining point on the left
                // this means that the only remaining point on the left is z itself
                // Actually- this should never happen
                return false;
            }
            
            // finally add z to the left side.
            ls.addLast(z);
            return true; // the hull is fine
        }
        // no modification needed
        // the point does not belong in the hull
        return true;
    }
    
    /** Add a point to the left side of the hull.
     * <br><br>
     * If the function returns false, adding further points
     * to the hull will result in errors.
     *
     * @return true if succeeds, false if the hull is destroyed
     * (that is, there is no line which stays to left of the points
     * in the left side of the hull and right of the ones on the right)
     */
    public final boolean addToLeftFirst(Complex z) {
        //System.out.println("rs_first x="+rs.getFirst().x+" y="+rs.getFirst().y);
        //System.out.println("ls_last x="+ls.getLast().x+" y="+ls.getLast().y);
        
        if (TriangleGeometry.sign(rs.getLast(),z,ls.getFirst())==-1) {
            // the point belongs in the hull
            
            // first try to remove vertices from the hull on the right side
            while ((rs.size()>1)&&(TriangleGeometry.sign(rs.getLast(),z,
            rs.getSecondToLast())==-1))
                // permenantly remove the first on the right side
                if (rs.removeLast())
                    return false;
            
            if ((rs.size()==1)&&(TriangleGeometry.sign(ls.getLast(),z,
            rs.getLast())==-1))
                // rs.getFirst() should also be removed
                // now the right side contains no elements.
                // thus the hull has degenerated
                return false;
            
            
            // now look at the left
            while ((ls.size()>1)&&(TriangleGeometry.sign(ls.getSecond(),z,
            ls.getFirst())==-1))
                // remove the last point from the left side permenently, and move on.
                if (ls.removeFirst())
                    return false;
            
            if ((ls.size()==1)&&(TriangleGeometry.sign(z,rs.getFirst(),ls.getLast())==-1)) {
                // we should remo0ve the last remaining point on the left
                // this means that the only remaining point on the left is z itself
                // Actually- this should never happen
                return false;
            }
            
            // finally add z to the left side.
            ls.addFirst(z);
            return true; // the hull is fine
        }
        // no modification needed
        // the point does not belong in the hull
        return true;
    }
    
    
    /** Add a point to the right side of the hull.
     * <br><br>
     * If the function returns false, adding further points
     * to the hull will result in errors.
     *
     * @return true if succeeds, false if the hull is destroyed
     * (that is, there is no line which stays to left of the points
     * in the left side of the hull and right of the ones on the right)
     */
    public final boolean addToRightLast(Complex z) {
        if (TriangleGeometry.sign(ls.getFirst(),z,rs.getLast())==-1) {
            // the point belongs in the hull
            
            // first try to remove vertices from the hull on the right side
            while ((ls.size()>1)&&(TriangleGeometry.sign(ls.getFirst(),z,
            ls.getSecond())==-1))
                // permenantly remove the first on the right side
                if (ls.removeFirst())
                    return false;
            
            if ((ls.size()==1)&&(TriangleGeometry.sign(rs.getFirst(),z,
            ls.getFirst())==-1))
                // ls.getFirst() should also be removed
                // now the right side contains no elements.
                // thus the hull has degenerated
                return false;
            
            
            // now look at the left
            while ((rs.size()>1)&&(TriangleGeometry.sign(rs.getSecondToLast(),z,
            rs.getLast())==-1))
                // remove the last point from the left side permenently, and move on.
                if (rs.removeLast())
                    return false;
            
            if ((rs.size()==1)&&(TriangleGeometry.sign(z,ls.getLast(),rs.getFirst())==-1)) {
                // we should remo0ve the last remaining point on the left
                // this means that the only remaining point on the left is z itself
                // Actually- this should never happen
                return false;
            }
            
            // finally add z to the left side.
            rs.addLast(z);
            return true; // the hull is fine
        }
        // no modification needed
        // the point does not belong in the hull
        return true;
    }

        /** Add a point to the right side of the hull.
     * <br><br>
     * If the function returns false, adding further points
     * to the hull will result in errors.
     *
     * @return true if succeeds, false if the hull is destroyed
     * (that is, there is no line which stays to left of the points
     * in the left side of the hull and right of the ones on the right)
     */
    public final boolean addToRightFirst(Complex z) {
        if (TriangleGeometry.sign(ls.getLast(),z,rs.getFirst())==1) {
            // the point belongs in the hull
            
            // first try to remove vertices from the hull on the right side
            while ((ls.size()>1)&&(TriangleGeometry.sign(ls.getLast(),z,
            ls.getSecondToLast())==1))
                // permenantly remove the first on the right side
                if (ls.removeLast())
                    return false;
            
            if ((ls.size()==1)&&(TriangleGeometry.sign(rs.getLast(),z,
            ls.getLast())==1))
                // ls.getFirst() should also be removed
                // now the right side contains no elements.
                // thus the hull has degenerated
                return false;
            
            
            // now look at the left
            while ((rs.size()>1)&&(TriangleGeometry.sign(rs.getSecond(),z,
            rs.getFirst())==1))
                // remove the last point from the left side permenently, and move on.
                if (rs.removeFirst())
                    return false;
            
            if ((rs.size()==1)&&(TriangleGeometry.sign(z,ls.getFirst(),rs.getLast())==1)) {
                // we should remo0ve the last remaining point on the left
                // this means that the only remaining point on the left is z itself
                // Actually- this should never happen
                return false;
            }
            
            // finally add z to the left side.
            rs.addFirst(z);
            return true; // the hull is fine
        }
        // no modification needed
        // the point does not belong in the hull
        return true;
    }

    
    /** z is a vector pointing in the direction of holonomy of the unfolding */
    public final boolean strongTest(Complex z){
        return (
        (z.times(rs.getLast().minus(ls.getFirst()).conjugate()).y>0) &&
        (z.times(ls.getLast().minus(rs.getFirst()).conjugate()).y<0));
    }
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    /** The left side must have 3 vertices. We demote it to two.
     * Replace the latter two vertices with the point obtained by
     * intersecting the following line segments:
     * 1) ls.first -> ls.second
     * 2) ls.last -> rs.first
     */
    public final void fix() {
        
        Complex ll=ls.getLast();
        ls.removeLast();
        Complex l2=ls.getLast();
        ls.removeLast();
        
        ls.addLast(Complex.intersect(ls.getFirst(),l2,ll,rs.getFirst()));
    }
    
    public void printDebug() {
        System.out.println("Left side is");
        ls.printDebug();
        System.out.println("Right side is");
        rs.printDebug();        
    }
}