package jp.ac.nii.icpc2010.players;

import java.awt.Point;
import java.util.Vector;

import jp.ac.nii.icpc2010.playfield.IPlayField;

// Player that moves to the point from which the longest hilbert curve can be drawn.
public class HilbertCurveSelecter extends ZigzagSelecter {

    private Point routes[][];

    public HilbertCurveSelecter(int id, IPlayField playField) {
        super(id, playField);

        int width = Math.max(playField.getWidth(), playField.getHeight());
        int bit;
        for(bit = 0; (1 << bit) < width; bit++){}
        Point[] curve = getHilbertCurve(bit);

        this.routes = new Point[8][curve.length];
        for(int i = 0; i < curve.length; i++){
            int x = curve[i].x;
            int y = curve[i].y;

            this.routes[0][i] = new Point( x,  y);
            this.routes[1][i] = new Point( x, -y);
            this.routes[2][i] = new Point(-x,  y);
            this.routes[3][i] = new Point(-x, -y);
            this.routes[4][i] = new Point( y,  x);
            this.routes[5][i] = new Point(-y,  x);
            this.routes[6][i] = new Point( y, -x);
            this.routes[7][i] = new Point(-y, -x);
        }
    }

    private enum Dir{
        UP, DOWN, RIGHT, LEFT;

        public Dir plus(){
            switch(this){
            case UP:
                return LEFT;
            case LEFT:
                return DOWN;
            case DOWN:
                return RIGHT;
            case RIGHT:
                return UP;
            default:
                return null;
            }
        }

        public Dir minus(){
            switch(this){
            case UP:
                return RIGHT;
            case RIGHT:
                return DOWN;
            case DOWN:
                return LEFT;
            case LEFT:
                return UP;
            default:
                return null;
            }
        }

        public Point step(Point p){
            switch(this){
            case UP:
                return new Point(p.x, p.y + 1);
            case RIGHT:
                return new Point(p.x + 1, p.y);
            case DOWN:
                return new Point(p.x, p.y - 1);
            case LEFT:
                return new Point(p.x - 1, p.y);
            default:
                return null;
            }
        }
    };

    private static Point[] getHilbertCurve(int bit){
        Vector<Point> curve = new Vector<Point>();
        Point[] point = new Point[]{new Point(0, 0)};
        Dir[] dir = new Dir[]{Dir.RIGHT};
        curve.addAll(hilbertCurveL(point, dir, bit - 1));
        return curve.toArray(new Point[curve.size()]);
    }

    // refer Wikipedia
    private static Vector<Point> hilbertCurveL(Point[] point, Dir[] dir, int depth){
        Vector<Point> curve = new Vector<Point>();

        // L --> +RF−LFL−FR+
        // +
        dir[0] = dir[0].plus();
        // R
        if(depth > 0){
            curve.addAll(hilbertCurveR(point, dir, depth - 1));
        }
        // F
        point[0] = dir[0].step(point[0]);
        curve.add(new Point(point[0]));
        // -
        dir[0] = dir[0].minus();
        // L
        if(depth > 0){
            curve.addAll(hilbertCurveL(point, dir, depth - 1));
        }
        // F
        point[0] = dir[0].step(point[0]);
        curve.add(new Point(point[0]));
        // L
        if(depth > 0){
            curve.addAll(hilbertCurveL(point, dir, depth - 1));
        }
        // -
        dir[0] = dir[0].minus();
        // F
        point[0] = dir[0].step(point[0]);
        curve.add(new Point(point[0]));
        // R
        if(depth > 0){
            curve.addAll(hilbertCurveR(point, dir, depth - 1));
        }
        // +
        dir[0] = dir[0].plus();

        return curve;
    }
    private static Vector<Point> hilbertCurveR(Point[] point, Dir[] dir, int depth){
        Vector<Point> curve = new Vector<Point>();

        // R --> -LF+RFR+FL-
        // -
        dir[0] = dir[0].minus();
        // L
        if(depth > 0){
            curve.addAll(hilbertCurveL(point, dir, depth - 1));
        }
        // F
        point[0] = dir[0].step(point[0]);
        curve.add(new Point(point[0]));
        // +
        dir[0] = dir[0].plus();
        // R
        if(depth > 0){
            curve.addAll(hilbertCurveR(point, dir, depth - 1));
        }
        // F
        point[0] = dir[0].step(point[0]);
        curve.add(new Point(point[0]));
        // R
        if(depth > 0){
            curve.addAll(hilbertCurveR(point, dir, depth - 1));
        }
        // +
        dir[0] = dir[0].plus();
        // F
        point[0] = dir[0].step(point[0]);
        curve.add(new Point(point[0]));
        // L
        if(depth > 0){
            curve.addAll(hilbertCurveL(point, dir, depth - 1));
        }
        // -
        dir[0] = dir[0].minus();

        return curve;
    }

    @Override
    protected int getNumOfRoutes() {
        return this.routes.length + super.getNumOfRoutes();
    }

    @Override
    protected Point[] getRoute(int routeId) {
        if(routeId >= this.routes.length){
            return super.getRoute(routeId - this.routes.length);
        }else{
            return this.routes[routeId];
        }
    }
}
