/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package shape;
import geomExtension.*;
import geomExtension.Vector2D;
import java.awt.geom.*;
import java.util.*;
import util.Util;

public class PathConnect {
    
    PathSegment[] PathSegments=null;
    JointList jointList=new JointList();
    Vector pathVector=new Vector();
    static double eps=1.0e-4;
    int debug=0;

    public PathSegment[][] findPaths(Point2D[][] endPs){
        this.PathSegments=this.createPathSegments(endPs);
        this.createJoints(this.PathSegments);
        PathSegment startSeg=null;
        int pathCount=0;
        PathSegment[][] paths=new PathSegment[this.PathSegments.length][];
        while(true){
            startSeg=this.searchStartPathSegment();
            if(startSeg==null) break;
            if(startSeg.closed){
                paths[pathCount]=new PathSegment[1];
                paths[pathCount][0]=startSeg;
                startSeg.passed=true;
                pathCount++;
            } else{
                paths[pathCount]=this.findPath(startSeg);
                pathCount++;
            }
        }
        PathSegment[][] outPaths=new PathSegment[pathCount][1];
        
        for(int i=0;i<pathCount;i++){
            int len=paths[i].length;
            outPaths[i]=new PathSegment[len];
            for(int j=0;j<len;j++){
                outPaths[i][j]=paths[i][j];
            }
        }
        
        return outPaths;
    }
    
    private PathSegment[] createPathSegments(Point2D[][] endPs){
        int numseg=endPs.length;
        PathSegment[] PathSegments=new PathSegment[numseg];
        for(int i=0;i<numseg;i++){
            PathSegments[i]=new PathSegment(i, endPs[i][0], endPs[i][1]);
            if(Vector2D.dist(PathSegments[i].startP, PathSegments[i].endP)<eps) PathSegments[i].closed=true;
        }
        String str="PathSegmentConnect PathSegment List";
        for(int i=0;i<numseg;i++){
            str+="\n -- PathSegment "+PathSegments[i].toString();
            PathSegments[i]=new PathSegment(i, endPs[i][0], endPs[i][1]);
        }
        if(debug>0) System.out.println(str);
        return PathSegments;
    }
    
    private void createJoints(PathSegment[] PathSegments){
        int numseg=PathSegments.length;
        boolean[] closed=new boolean[numseg];
        for(int i=0;i<numseg;i++){
            closed[i]=false;
            if(Vector2D.dist(PathSegments[i].startP, PathSegments[i].endP)<eps) closed[i]=true;
        }
        double dist=0.0;
        for(int i=0;i<numseg;i++){
            for(int j=i;j<numseg;j++){
                if(j==i) continue;
                dist=Vector2D.dist(PathSegments[i].startP, PathSegments[j].startP);
                if(dist<eps) {
                    Joint joint=new Joint(PathSegments[i], Joint.startP, 
                            PathSegments[j], Joint.startP);
                    this.jointList.addJoint(joint);
                }
                dist=Vector2D.dist(PathSegments[i].startP, PathSegments[j].endP);
                if(dist<eps) {
                    Joint joint=new Joint(PathSegments[i], Joint.startP, 
                            PathSegments[j], Joint.endP);
                    this.jointList.addJoint(joint);
                }
                dist=Vector2D.dist(PathSegments[i].endP, PathSegments[j].startP);
                if(dist<eps) {
                    Joint joint=new Joint(PathSegments[i], Joint.endP, 
                            PathSegments[j], Joint.startP);
                    this.jointList.addJoint(joint);
                }
                dist=Vector2D.dist(PathSegments[i].endP, PathSegments[j].endP);
                if(dist<eps) {
                    Joint joint=new Joint(PathSegments[i], Joint.endP , 
                            PathSegments[j], Joint.endP);
                    this.jointList.addJoint(joint);
                }
            }
        }
        String str=this.jointList.toString();
        if(debug>0) System.out.println(str);
    }
    
    private PathSegment searchStartPathSegment(){
        int numseg=this.PathSegments.length;
        PathSegment PathSegmentSave=null;
        for(int i=0;i<numseg;i++){
            if(!PathSegments[i].passed){
                PathSegmentSave=this.PathSegments[i];
                break;
            }
        }
        return PathSegmentSave;
    }

    private PathSegment[] findPath(PathSegment startSeg){
        this.pathVector.clear();
        this.pathVector.add(startSeg);
        startSeg.passed=true;
        PathSegment currentSeg=startSeg;
        PathSegment nextSeg=startSeg;
      //search backword
        while(true){
            nextSeg=this.searchBackward(currentSeg);
            if(nextSeg==null||nextSeg.id==startSeg.id) break;
            this.pathVector.add(nextSeg);
            nextSeg.passed=true;
            currentSeg=nextSeg;
        }
        while(true){
            currentSeg=startSeg;
            nextSeg=this.searchForward(currentSeg);
            if(nextSeg==null||nextSeg.id==startSeg.id) break;
            this.pathVector.add(0, nextSeg);
            nextSeg.passed=true;
            currentSeg=nextSeg;
        }
        int size=this.pathVector.size();
        PathSegment[] PathSegments=new PathSegment[size];
        for(int i=0;i<size;i++) PathSegments[i]=(PathSegment)this.pathVector.get(i);
        String str=" ** finedPath pathList numofsegs="+size;
        for(int i=0;i<size;i++){
            Point2D jointPoint=PathSegments[i].endP;
            if(PathSegments[i].reversed) jointPoint=PathSegments[i].startP;
            str+="\n  segmenId-"+PathSegments[i].id+", reversed="+PathSegments[i].reversed
                    +", passed="+PathSegments[i].passed
                    +", jointPoint="+Util.Pt(jointPoint);
        }
        if(debug>0) System.out.println(str);
        return PathSegments;
    }
    
    private PathSegment searchBackward(PathSegment PathSegment){
      PathSegment next=null;
      Joint[] joints=this.jointList.getJoints(PathSegment);
      int len=joints.length;
      int jointPos=Joint.endP;
      if(PathSegment.reversed) jointPos=Joint.startP;
      if(len==0) return null;
      Joint jointSave=null;
      for(int i=0; i<len;i++){
          if(joints[i].passed) continue;
          if(joints[i].PathSegment1.id==PathSegment.id&&joints[i].seg1_pos==jointPos){
              joints[i].passed=true;
              if(joints[i].seg2_pos==Joint.endP) joints[i].PathSegment2.reversed=true;
              next=joints[i].PathSegment2;
              next.passed=true;
              jointSave=joints[i];
              break;
          }
          if(joints[i].PathSegment2.id==PathSegment.id&&joints[i].seg2_pos==jointPos){
              joints[i].passed=true;
              if(joints[i].seg1_pos==Joint.endP) joints[i].PathSegment1.reversed=true;
              next=joints[i].PathSegment1;
              next.passed=true;
              jointSave=joints[i];
              break;
          }
      }
      String str=" searchBackward current: "+PathSegment.toShortString();
      if(next!=null) str+=", next: "+next.toShortString()+", "+jointSave.toShortString();
      else  str+=", next=null, joint=null";
      if(debug>0) System.out.println(str);
      return next;
    }
    
    private PathSegment searchForward(PathSegment PathSegment){
      PathSegment next=null;
      Joint[] joints=this.jointList.getJoints(PathSegment);
      int len=joints.length;
      int jointPos=Joint.startP;
      if(PathSegment.reversed) jointPos=Joint.endP;
      if(len==0) return null;
      Joint jointSave=null;
      for(int i=0; i<len;i++){
          if(joints[i].passed) continue;
          if(joints[i].PathSegment1.id==PathSegment.id&&joints[i].seg1_pos==jointPos){
              joints[i].passed=true;
              if(joints[i].seg2_pos==Joint.startP) joints[i].PathSegment2.reversed=true;
              next=joints[i].PathSegment2;
              next.passed=true;
              jointSave=joints[i];
              break;
          }
          if(joints[i].PathSegment2.id==PathSegment.id&&joints[i].seg2_pos==jointPos){
              joints[i].passed=true;
              if(joints[i].seg1_pos==Joint.startP) joints[i].PathSegment1.reversed=true;
              next=joints[i].PathSegment1;
              next.passed=true;
              jointSave=joints[i];
              break;
          }
      }
      String str=" searchBackward current: "+PathSegment.toShortString();
      if(next!=null) str+=", next: "+next.toShortString()+", "+jointSave.toShortString();
      else  str+=", next=null, joint=null";
      if(debug>0) System.out.println(str);
      return next;
    }
    
    public static void exec() {
        PathConnect con=new PathConnect();
        Point2D[][] endPs=con.createTest();
        PathSegment[][] paths=con.findPaths(endPs);
      //print path data
        String str="Path list";
        int numPaths=paths.length;
        for(int i=0;i<numPaths;i++){
            int len=paths[i].length;
            if(len==0) continue;
            str+="\npath no.="+i;
            for(int j=0;j<len;j++){
                PathSegment pathSeg=paths[i][j];
                str+="\n  -- PathSegment "+pathSeg.toString();
            }
        }
        System.out.println(str);
        System.exit(0);
    }

    private Point2D[][] createTest(){
        Point2D[][] endPs=new Point2D[10][2];
       //Path-0 
        endPs[0][0]=new Point2D.Double(20,10);
        endPs[0][1]=new Point2D.Double(40,10);
      //Path-1
        endPs[1][0]=new Point2D.Double(0,0);
        endPs[1][1]=new Point2D.Double(0,0);
      //Path2
        endPs[2][0]=new Point2D.Double(10,30);
        endPs[2][1]=new Point2D.Double(10,40);
      //Path-3  
        endPs[3][0]=new Point2D.Double(40,20);
        endPs[3][1]=new Point2D.Double(40,10);
      //Path-4
        endPs[4][0]=new Point2D.Double(10,30);
        endPs[4][1]=new Point2D.Double(0,20);
      //Path-5
        endPs[5][0]=new Point2D.Double(20,30);
        endPs[5][1]=new Point2D.Double(30,30);
      //Path-6
        endPs[6][0]=new Point2D.Double(20,30);
        endPs[6][1]=new Point2D.Double(20,10);
      //Path-7
        endPs[7][0]=new Point2D.Double(30,20);
        endPs[7][1]=new Point2D.Double(40,20);
      //Path-8
        endPs[8][0]=new Point2D.Double(20,40);
        endPs[8][1]=new Point2D.Double(10,40);
      //Path-9
        endPs[9][0]=new Point2D.Double(30,20);
        endPs[9][1]=new Point2D.Double(30,30);
        return endPs;
    }
}//End of PathSegmentConnect
/*
class PathSegment{
    int id=-1;
    Point2D startP=null;
    Point2D endP=null;
    boolean closed=false;
    boolean reversed=false;
    boolean passed=false;
    
    public PathSegment(int id, Point2D startP, Point2D endP){
        this.id=id;
        this.startP=startP;
        this.endP=endP;
    }
    
    public String toString(){
        Point2D startPoint=this.startP;
        Point2D endPoint=this.endP;
        if(this.reversed){
            startPoint=this.endP;
            endPoint=this.startP;
        }
        String str="id="+id+", closed="+closed+", reversed="+reversed+
                ", passed="+passed+", start="+Pr.Pt(startPoint)+", end="+Pr.Pt(endPoint);
        return str;
    }
} //End of PathSegment class
*/
class Joint{
    PathSegment PathSegment1=null;
    PathSegment PathSegment2=null;
    int seg1_pos=-1;
    int seg2_pos=-1;
    boolean passed=false;
    public final static int startP=0;
    public final static int endP=1;
    public final static String[] posStr={"startP", "endP"};
    

    public Joint(PathSegment PathSegment1, int seg1_pos, PathSegment PathSegment2,  int seg2_pos){
        this.PathSegment1=PathSegment1;
        this.seg1_pos=seg1_pos;
        this.PathSegment2=PathSegment2;
        this.seg2_pos=seg2_pos;
    }
    public String toString(){
        String str="joint PathSegment.ids=("+this.PathSegment1.id+", "+PathSegment2.id+")"
                +", seg1_pos="+posStr[this.seg1_pos]+", seg2_pos="+posStr[this.seg2_pos]
                +", passed="+passed;
        return str;
    }
    public String toShortString(){
        String str="joint PathSegment.ids=("+this.PathSegment1.id+", "+PathSegment2.id+")"
                +", pos=("+posStr[this.seg1_pos]+", "+posStr[this.seg2_pos]+")"
                +", passed="+passed;
        return str;
    }
} //End of Joint class

class JointList{
    ArrayList list=new ArrayList();
    Vector workVector=new Vector();
    public JointList(){}
    
    public void addJoint(Joint joint){
        this.list.add(joint);
    }
    
    public Joint[] getJoints(PathSegment PathSegment){
        this.workVector.clear();
        int size=this.list.size();
        for(int i=0;i<size;i++){
            Joint joint=(Joint)this.list.get(i);
            if(joint.passed) continue;
            int PathSegmentId1=joint.PathSegment1.id;
            int PathSegmentId2=joint.PathSegment2.id;
            if(PathSegment.id==PathSegmentId1||PathSegment.id==PathSegmentId2){
                this.workVector.add(joint);
            }
        }
        size=this.workVector.size();
        Joint[] joints=new Joint[size];
        String str="getConnections PathSegment"+PathSegment.toString();
        for(int i=0;i<size;i++) {
            joints[i]=(Joint)this.workVector.get(i);
            str+=" joint"+joints[i].toString();
        }
        return joints;
    }
    
    public String toString(){
        int size=this.list.size();
        String str="Joint list  size="+size;
        for(int i=0;i<size;i++){
            Joint joint=(Joint)this.list.get(i);
            str+="\n joint["+i+"] "+joint.toString();
        }
        return str;
    }
} //End of JointList class