import java.util.*;
import java.awt.*;

class Path
{
  int dimension;
  Vector step;
  Arrow endPt;

  static Path compost;
  static boolean composting = true;
  static CompostHeap compostHeap = new CompostHeap(new Path().getClass(),
						   true,2);

public void debug(int i, String s)
  {
    if (i>=4) System.out.println(s);
  }

public void dbgalloc(int i,String s)
  {
    if (i>=3) System.out.println("     "+s);
  }

public Path()
  {
    dbgalloc(2,"Made a null path");
  }

public Path(Arrow arrow)
  {
    dimension = arrow.dimension;
    step = new Vector();
    step.addElement(arrow);
    endPt = new Arrow(arrow);
    dbgalloc(2,"Made a path from an arrow");
  }

public Path(Path pathToCopy)
  {
    copy(pathToCopy);
    dbgalloc(2,"...of another path");
  }

static public Path newPath(Path pathToCopy)
  {
    Path ans;
    if (compostHeap.exists())
      {
	pathToCopy.dbgalloc(2,"Reused a path!");
	ans = (Path)compostHeap.likeNew();
	ans.copy(pathToCopy);
      }
    else
      {
	pathToCopy.dbgalloc(2,"Couldn't reuse");
	ans = new Path(pathToCopy);
      }

    return ans;
  }

public void free()
  {
    compostHeap.recycle(this);
  }

public void copy(Path pathToCopy)
  {
    int newSteps = pathToCopy.step.size();

    dimension = pathToCopy.dimension;
    if (step == null)
      step = new Vector();
    int oldSteps = step.size();

    for (int i=step.size(); i<newSteps; i++)
      step.addElement(Arrow.newArrow(dimension));

    for (int i=newSteps; i<oldSteps; i++)
      {
	((Arrow)step.elementAt(newSteps)).free();
	step.removeElementAt(newSteps);
      }
//     if (step.size() != newSteps)
//       debug(99,"Didn't get the length right:"+
// 	    " Made "+oldSteps+" into "+step.size()+", wanted "+newSteps);

    for (int i=0; i<pathToCopy.step.size(); i++) 
	((Arrow)step.elementAt(i)).copy((Arrow)pathToCopy.step.elementAt(i));
    
    endPt = new Arrow(pathToCopy.endPt);
    dbgalloc(2,"Made a copy");
  }

public Path thenDo(Path p)
  {
    Path ans = new Path();
    if (dimension != p.dimension)
      System.out.println("Concatenating paths in different spaces!");
    else
      {
	ans.dimension = dimension;
	ans.step = new Vector();
	int i;
	for (i=0; i<step.size(); i++)
	  ans.step.addElement(new Arrow((Arrow)step.elementAt(i)));
	for (i=0; i<p.step.size(); i++)
	  ans.step.addElement(new Arrow((Arrow)p.step.elementAt(i)));
	ans.coalesce(step.size()-1);
      }
    ans.endPt = endPt.plus(p.endPt);
    //    debug(1,"Concatenation produced "+ans);
    return ans;
  }

public String th(int i)
  {
    String ans = i+"th";
    if (i==1) ans = "1st";
    if (i==2) ans = "2nd";
    if (i==3) ans = "3rd";
    return ans;
  }

public boolean coalesce(int where)
  {
    boolean ans = false;
    if ((where >= 0) && (where < step.size()-1))
      {
	Arrow a = (Arrow)step.elementAt(where);
	Arrow b = (Arrow)step.elementAt(where+1);
	if (a.posPropTo(b))
	  {
//	    if (a.color == b.color)
	      {
//		debug(0,"Coalescing "+where+"="+a+" and "+(where+1)+"="+b);
		step.setElementAt(a.plus(b), where);
		b.free();
		step.removeElementAt(where+1);
		ans = true;
	      }
// 	    else
// 	      System.out.println(where + ": "+ a.color +" != "+b.color);
	  }
      }
    return ans;
  }

public boolean LittelArrow(Arrow root, int where)
  {
    Arrow straight = (Arrow)step.elementAt(where);
    Arrow reflected = straight.reflectedThrough(root);
    Arrow shift = straight.minus(reflected);
    Szam scale = root.dotProd(root).over(
		 root.dotProd(reflected).times(Szam.TWO));
      //shift.over(root);
//     debug(0,"Flipping the "+th(where)+" step would move by "
// 	  +Szam.ONE.over(scale)+" * "+root);

    if (scale.lessThanEq(Szam.ZERO))
      {
	debug(0,"Don't want to flip the "+th(where)+" step");
	return false;
      }
    else
      {
	if (!scale.lessThan(Szam.ONE))
	  {
//	    debug(0,"Want to completely flip the "+th(where)+" step");
	    ((Arrow)step.elementAt(where)).copy(reflected);
	    root.add(shift);
	    shift.free();
	    return false;
	  }
	else
	  {
  //	    scale = (root.dotProd(root)).over(scale.times(new Szam(2,1)));
// 	    debug(0,"Have to break the "+th(where)+" step at "+scale+" along");
	    step.setElementAt(reflected.scaleBy(scale),where);
	    reflected.free();
	    ((Arrow)step.elementAt(where)).color = Color.red;
// 	    System.out.println(	    ((Arrow)step.elementAt(where)).color);
	    step.insertElementAt(
			    straight.scaleBy(Szam.ONE.minus(scale)),
			    where+1);
	    ((Arrow)step.elementAt(where+1)).color = Color.black;
	    root.copy(new Arrow(dimension));
	    return (!coalesce(where-1));
	  }
      }
  }

static Szam extent2 = new Szam(0,1);
static Szam curExtent = new Szam(0,1);

public boolean LittelPiece(Arrow root, Step Where, Step WhereNext)
//
// This operates destructively on the current Path after the Whereth step,
// doing the Littelmann lowering operation in the direction root. 
// It is assumed when we enter that the point on Path after Where furthest
// in the root direction is its first point, with the runnerup in WhereNext
// (or WhereNext == -1, in which case LittelPiece determines it).
// Where and WhereNext are set appropriately on exit. This speed up
// repeated application of the same root.
//

  {
    int dbg = 2;
    int where = Where.intValue();
    int furthest = where, nextFurthest = WhereNext.intValue();
//     debug(dbg,"Into LittelPiece at "+where+","+nextFurthest+" with a "
// 	  +step.size()+"-step path, "+this+", to move "+root);
    boolean haveRunnerUp = false;
    Arrow soFar = new Arrow(dimension);
    boolean ans = true;

    if (nextFurthest > -1)
      {
	extent2 = root.dotProd((Arrow) step.elementAt(WhereNext.intValue()));
	haveRunnerUp = true;
      }
    else
      for (int i=where; i<step.size(); i++)
	{
	  soFar = soFar.plus((Arrow) step.elementAt(i));
	  soFar.getDotProd(root,curExtent);
	  if ((!haveRunnerUp) || (extent2.lessThanEq(curExtent)))
	    {
		nextFurthest = i+1;
		extent2.copy(curExtent);
		haveRunnerUp = true;
	    }
	}
//     debug(dbg,"Second furthest step after the "+th(where)
// 	  +" is the "+th(nextFurthest));
    

    if (nextFurthest == step.size()) haveRunnerUp = false;

    if (furthest < step.size())
      ((Arrow)step.elementAt(furthest)).color = Color.green;
    if (haveRunnerUp)
      ((Arrow)step.elementAt(nextFurthest)).color = Color.blue;

    Szam piece = new Szam(1,1);
    if (haveRunnerUp)
      {
	piece = (Szam.TWO.times(Szam.ZERO.minus(extent2))).
	  over(root.dotProd(root));
// 	debug(dbg,"Amount to flip: -2 * "+extent2+"/"
// 	      +root.dotProd(root)+" = "+piece);
      }
    if (piece.lessThan(Szam.ZERO))
      {
      System.out.println("   Entered LittelPiece with incorrect Where!!!"
			 +"Should be "+nextFurthest);
	try { Thread.sleep(1000000); } catch (InterruptedException e) {}
      }
    if (Szam.ONE.lessThanEq(piece)) 
      {
	piece = new Szam(1,1);
// 	debug(dbg,"Needn't worry about "+th(nextFurthest)+" step from "
// 	      +th(furthest)+", just flip consecutively");
       }
//     else
//       debug(dbg,"Can only flip "+piece+" between the "
// 	    +th(furthest)+" step and the "+nextFurthest);

    Arrow remaining = root.scaleBy(piece);
    
    int flipWhich = furthest;
//     debug(dbg,"Remaining = "+remaining+
//     	  ", flipWhich = "+flipWhich+" of "+step.size()+" steps");
    while ((!remaining.isZero()) && (flipWhich<step.size()))
      {
// 	debug(dbg,remaining+" remains: Flipping the "+th(flipWhich)
// 	      +" step of "+this);
	if (LittelArrow(remaining,flipWhich++))
	  nextFurthest++;
	if (coalesce(where-1)) {
	  nextFurthest--; 
// 	  debug(dbg,"A coalescing decreases nextFurthest"); 
	}
// 	debug(dbg,"...producing "+this+", nextFurthest = "+nextFurthest);
      }
    if ((flipWhich == step.size()) && (!remaining.isZero()))
      return false;

    //      debug(0,"Can only flip "+piece+" of the "+th(furthest)+" arrow");

    Where.i = flipWhich;
    WhereNext.i = nextFurthest;
//     debug(dbg, "Next time: Where, WhereNext = "
// 	  +Where.intValue()+","+WhereNext.intValue());

    if (piece.lessThan(Szam.ONE))
      {
	Where.i = nextFurthest;
	WhereNext.i = -1;
	ans = LittelPiece(root.scaleBy(Szam.ONE.minus(piece)), 
			  Where, WhereNext);
      }
    else return true;

//     if (!ans)
//       debug(dbg,"Inapplicable, leaving "+remaining+" over, producing "+this);
//     else
//       debug(dbg,"Leaving LittelPiece, having produced "+this);
    return ans;
  }

static    Szam extent1 = new Szam(0,1);

public int findFurthest(Arrow root)
  {
    //    Szam curExtent = new Szam(0,1);
    int furthest = 0;
    Arrow soFar = new Arrow(dimension);
    extent1.copy(Szam.ZERO);

    for (int i=0; i<step.size(); i++)
      {
	soFar.add((Arrow) step.elementAt(i));
	soFar.getDotProd(root,curExtent);
	if (extent1.lessThanEq(curExtent))
	  {
	    furthest = i+1;
	    extent1.copy(curExtent);
// 	    debug(1,"Furthest step "+soFar+" toward "+root+" is "
// 		  +th(furthest)+" so far, with extent "+extent1);
	  }
      }
    return furthest;
  }

public boolean Littelmann(Arrow root)
  {
    int furthest = findFurthest(root);
    endPt.copy(endPt.plus(root));

    if (furthest == step.size())
      {
// 	debug(0,"Can't move this at all");
	return false;
      }
    else
      {
// 	debug(2,"");
// 	debug(2,"Littelmanning "+this+" starting at "+furthest);
	return LittelPiece(root, new Step(furthest), new Step(-1));
      }
  }

Step WherE = new Step(0), WhereNexT = new Step(0);

public boolean Littelmen(Arrow root, boolean first)
  {
    if (first)
      {
	WherE = new Step(findFurthest(root));
      }
	WhereNexT = new Step(-1);

//     debug(2,"Making Littelmen with "+this+", first = "+first);
    boolean ans = LittelPiece(root, WherE, WhereNexT);
//     debug(2,"Leaving Littelmen with WherE, WhereNexT = "+WherE+", "+WhereNexT);
    return ans;
  }

public boolean equals(Path p)
       // WARNING - this will claim that the non-coalesced Path (1,0):(1,0) 
       // is different from the Path (2,0). But Paths produced by the
       // operations in this class are coalesced, so it shouldn't matter.
  {
    boolean ans = (step.size() == p.step.size());
    
    int i=0;
    while ((ans) && (i<step.size()))
      ans = ((Arrow)step.elementAt(i)).equals((Arrow)p.step.elementAt(i++));
    return ans;
  }

public Arrow endPoint()
  {
    Arrow ans = new Arrow(dimension);
    for (int i=0; i<step.size(); i++)
      ans = ans.plus((Arrow)step.elementAt(i));
    return ans;
  }

public void draw(Graphics g, double curx, double cury, double scale, Color col)
  {
    //    System.out.println(current.size() + " segments");
    
    double newx,newy;
    g.drawOval((int)curx-1,(int)cury-1,2,2);
    g.setColor(col);

    for (int i=0; i<step.size(); i++)
      {
	Arrow curArrow = (Arrow)step.elementAt(i);
	newx = curx + curArrow.cuurd[0][0] * scale / curArrow.cuurd[0][1];
	newy = cury - curArrow.cuurd[1][0] * scale / curArrow.cuurd[1][1];

	g.drawLine((int)curx,(int)cury, (int)newx,(int)newy);
	//	g.drawOval((int)newx-2,(int)newy-2,5,5);
	
	curx = newx; cury = newy;
      }
  }

public String toString()
  {
    String ans = "[";
    for (int i=0; i<step.size()-1; i++)
      ans = ans + ((Arrow)step.elementAt(i)).toString() + ":";
    ans = ans + ((Arrow)step.elementAt(step.size()-1)).toString() + "]";
    return ans;
  }
    
}