package busrider;

/**
 This class is used by the conductor, when a Strategy fails to select
 a valid Segment for a player to traverse.
**/

class Router {

    /* We relate the cost of boarding a bus to the opportunity cost
       of travelling some distance. We assume the payoffs are roughly
       equal to the distance, and the average roll is eight. Therefore
       the cost of travelling is $1/8 per unit distance. Costs will be
       scaled by eight. */
    /* packaged */ final static int
	BOARDING_SCALE = 8,
	DISTANCE_COST  = 1;


    /* ----- internal classes ----- */

    /* For each segment-end to which we find a path, we keep the cost of
       getting there, and how we got there. */
    private static class SegInfo {
	public Segment seg;   // the segment
	public Junction junc; // which end of the segment
	public boolean done;  /* whether the current path is cheapest
				 and we have explored the fan-out */
	public int cost;      // cost of getting here
	public SegInfo prev;  // previous segment-end

	public SegInfo(Segment sg, Junction jend,
		       int playerIndex, Junction here, Route current)
	{
	    seg = sg;
	    junc = jend;
	    done = false;
	    cost = Integer.MAX_VALUE;
	    prev = null;

	    if (junc == here) {
		// calculate boarding cost
		Route segroute = seg.getRoute();
		int owner = Game.getInstance().getOwner(segroute);
		if ((segroute == current) || (owner == playerIndex)) {
		    cost = 0;
		} else if (owner < 0) {
		    cost = BOARDING_SCALE * Game.SMALL_FARE;
		} else {
		    cost = BOARDING_SCALE * Game.LARGE_FARE;
		}
	    }
	}

    }


    /* ----- methods ----- */

    /**
     picks the next segment to traverse.
    **/
    public static Segment pickSegment(int playerIndex,
	Junction here, Junction there, Route current)
    {
	if ((here == null) || (there == null)) return null;
	if (here.equals(there)) return null;

	Game ga = Game.getInstance();
	Board bo = ga.getBoard();

	/* -- initialize segInfos -- */
	int segquan = bo.getSegmentQuan();
	int sgiquan = segquan * 2; // one for each segment-end
	SegInfo[] infos = new SegInfo[sgiquan];
	int ix = 0;
	for (int sx = 0; sx < segquan; sx += 1) {
	    Segment seg = bo.getSegment(sx);
	    infos[ix] = new SegInfo(seg, seg.getAjunc(),
				    playerIndex, here, current);
	    ix += 1;
	    infos[ix] = new SegInfo(seg, seg.getBjunc(),
				    playerIndex, here, current);
	    ix += 1;
	}

	/* -- find the best route, Here to There -- */
	SegInfo bestsgi;
	for ( ; ; ) {
	    /* find the cheapest non-done segInfo.
	       There can be no cheaper way to get there, since we have
	       checked all segments from done-segInfos, and all other
	       paths go through equally- or more- expensive segInfos. */
	    bestsgi = null;
	    int mincost = Integer.MAX_VALUE;
	    for (int sx = 0; sx < sgiquan; sx += 1) {
		SegInfo sgi = infos[sx];
		if ((! sgi.done) && (sgi.cost < mincost)) {
		    mincost = sgi.cost;
		    bestsgi = sgi;
		}
	    }
	    if (bestsgi == null) {
		throw new FailureException("Router pgmerror #1");
	    }
	    bestsgi.done = true;

	    /* If Best's junction is There, we have finished the path. */
/* exit */  if (bestsgi.junc == there) break;

	    /* Try all segments from Bestsgi's junction. */
	    int jsq = bestsgi.junc.getSegmentQuan();
	    for (int jsx = 0; jsx < jsq; jsx += 1) {
		Segment jseg = bestsgi.junc.getSegment(jsx);
		int toidx = jseg.getIndex() * 2;
		    // index of next segInfo, if we end up at A-junc

		int cost = bestsgi.cost;
		if (bestsgi.seg == jseg) {
		    // same segment: traverse
		    cost += jseg.getLength() * DISTANCE_COST;

		    if (jseg.getAjunc() == bestsgi.junc) toidx += 1;
			// use segInfo at other end
		} else {
		    // different segment: check boarding cost
		    if ((bestsgi.prev == null) ||
			(bestsgi.prev.seg.getRoute() != jseg.getRoute()))
		    {
			// need to board
			int owner = ga.getOwner(jseg.getRoute());
			if (owner < 0) {
			    cost += BOARDING_SCALE * Game.SMALL_FARE;
			} else if (owner != playerIndex) {
			    cost += BOARDING_SCALE * Game.LARGE_FARE;
			}
		    }

		    if (jseg.getBjunc() == bestsgi.junc) toidx += 1;
			// use segInfo at this end
		}
		SegInfo tosgi = infos[toidx];

		if (cost < tosgi.cost) {
		    // we have a cheaper way to get there
		    tosgi.cost = cost;
		    tosgi.prev = bestsgi;
		}
	    }
	}

	/* We have the cheapest way from Here to There.
	   Backtrack from There(bestsgi) to Here. */
	while (bestsgi.prev.junc != here) {
	    sgiquan -= 1;
	    if (sgiquan < 0) {
		throw new FailureException("Router pgmerror #2");
	    }
	    bestsgi = bestsgi.prev;
	}
	return bestsgi.seg;
    }

}