import javalib.impworld.World;
import javalib.worldimages.Posn;
import javalib.worldimages.RectangleImage;
import javalib.worldimages.WorldImage;
import tester.*;

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

//Represents a list of type T
interface IList<T> extends Iterable<T >{

    // Appends this list onto the given list
    IList<T> append(IList<T> that);

    // Apply f to each element of this list
    <R> IList<R> map(IFunc<T, R> f);

    // Remove all elements of this list that do not satisfy the pred
    IList<T> filter(IPred<T> pred);

    // To return the result of applying the given visitor to this list
    <R> R accept(IListVisitor<T, R> visitor);

}

// Represents an empty list of type T
class Empty<T> implements IList<T> {

    /*
     * Fields: Methods: this.append(IList<T>) - IList<T> this.map(IFunc<T, R>) -
     * IList<R> this.filter(IPred<T>) - IList<T> this.accept(IListVisitor<T, R>)
     * IList<R> Method from fields:
     */

    // Appends this empty list onto the given list
    public IList<T> append(IList<T> that) {
        return that;
    }

    // Apply f to each element of this empty list
    public <R> IList<R> map(IFunc<T, R> f) {
        return new Empty<R>();
    }

    // Remove all elements of this empty list that don't satisfy pred
    public IList<T> filter(IPred<T> pred) {
        return this;
    }

    // To return the result of applying the given visitor to this empty list
    public <R> R accept(IListVisitor<T, R> visitor) {
        return visitor.visit(this);
    }

    @Override
    public Iterator<T> iterator() {
        throw new RuntimeException("you can't iterate over an empty");
    }

}

// Represents a non-empty list of type T
class Cons<T> implements IList<T> {
    T first;
    IList<T> rest;

    Cons(T first, IList<T> rest) {
        this.first = first;
        this.rest = rest;
    }

    /*
     * Fields: this.first - T this.rest - IList<T> Methods:
     * this.append(IList<T>) - IList<T> this.map(IFunc<T, R>) - IList<R>
     * this.filter(IPred<T>) - IList<T> this.accept(IListVisitor<T, R>) IList<R>
     * Method from fields: this.rest.append(IList<T>) - IList<T>
     * this.rest.map(IFunc<T, R>) - IList<R> this.rest.filter(IPred<T>) -
     * IList<T> this.rest.accept(IListVisitor<T, R>) IList<R>
     */

    // Appends this non-empty list onto the given list
    public IList<T> append(IList<T> that) {
        return new Cons<T>(this.first, this.rest.append(that));
    }

    // Apply f to each element of this non-empty list
    public <R> IList<R> map(IFunc<T, R> f) {
        return new Cons<R>(f.apply(this.first), this.rest.map(f));
    }

    // Remove all elements from this non-empty list that don't satisfy the pred
    public IList<T> filter(IPred<T> pred) {
        if (pred.apply(this.first)) {
            return new Cons<T>(this.first, this.rest.filter(pred));
        } else {
            return this.rest.filter(pred);
        }
    }

    // To return the result of applying the given visitor to this non-empty list
    public <R> R accept(IListVisitor<T, R> visitor) {
        return visitor.visit(this);
    }

    @Override
    public Iterator<T> iterator() {
        return new IListIterator<T>(this);
    }

}

class IListIterator<T> implements Iterator<T> {

    Cons<T> cur;



    IListIterator(Cons<T> cur) {
        this.cur = cur;
    }

    @Override
    public boolean hasNext() {
       return cur.accept(new IsEmptyVisitor<T>());
    }

    @Override
    public T next() {
        Cons<T> prev = this.cur;
        if (this.hasNext()) {
            cur = (Cons<T>) cur.rest;
        }
        else {
            throw new RuntimeException("There is no next");
        }

        return prev.first;
    }

}

class IsEmptyVisitor<T> implements IListVisitor<T, Boolean> {

    @Override
    public Boolean visit(Empty<T> empty) {
        return true;
    }

    @Override
    public Boolean visit(Cons<T> cons) {
        return false;
    }

}

// Represents a function from type T to type R
interface IFunc<A, R> {

    // Applies this function to the argument and returns type R
    R apply(A arg);
}

// Represents a predicate for type T
interface IPred<T> {

    // Applies this predicate to the given t
    boolean apply(T t);
}

// To implement a function over lists of T, returning value of type R
interface IListVisitor<T, R> {

    // To visit the given Empty<T> and return list of type R
    R visit(Empty<T> empty);

    // To visit the given Cons<T> and return list of type R
    R visit(Cons<T> cons);

}

// Visits the given list, mapping the given function, returning list of type R
class MapVisitor<T, R> implements IListVisitor<T, IList<R>> {
    IFunc<T, R> op;

    MapVisitor(IFunc<T, R> op) {
        this.op = op;
    }

    /*
     * Fields: this.op - IFunc<T, R> Methods: this.visit(Empty<T>) - IList<R>
     * this.visit(Cons<T>) - IList<R> Methods on fields: this.op.apply(T) - R
     */

    // Visits the given Empty<T> and returns Empty<R>
    public IList<R> visit(Empty<T> empty) {
        return new Empty<R>();
    }

    // Visits the given Cons<T> and applies the op to each element
    public IList<R> visit(Cons<T> cons) {
        return new Cons<R>(this.op.apply(cons.first), cons.rest.accept(this));
    }

}

// Visits the given list, removing all elements that do not satisfy this
// visitor's pred
class FilterVisitor<T> implements IListVisitor<T, IList<T>> {
    IPred<T> pred;

    FilterVisitor(IPred<T> pred) {
        this.pred = pred;
    }

    /*
     * Fields: this.pred - IPred<T> Methods: this.visit(Empty<T>) - IList<T>
     * this.visit(Cons<T>) - IList<T> Methods on fields: this.pred.apply(T) -
     * boolean
     */

    // Visits the given Empty<T> and returns an Empty<T>
    public IList<T> visit(Empty<T> empty) {
        return empty;
    }

    // Visits the given Cons<T> and removes the elements that do not satisfy the
    // pred
    public IList<T> visit(Cons<T> cons) {
        if (this.pred.apply(cons.first)) {
            return new Cons<T>(cons.first, cons.rest.accept(this));
        } else {
            return cons.rest.accept(this);
        }
    }
}

class getFirstVisitor<T> implements IListVisitor<T, T> {

    @Override
    public T visit(Empty<T> empty) {
        throw new RuntimeException("can't get the first of an empty list");
    }

    @Override
    public T visit(Cons<T> cons) {
        return cons.first;
    }

}

// Represents a single square of the game area
class Cell implements Iterable<Cell> {
    Cell(double height, int x, int y, Cell left, Cell top, Cell right,
            Cell bottom, boolean isFlooded) {
        this.height = height;
        this.x = x;
        this.y = y;
        this.left = left;
        this.top = top;
        this.right = right;
        this.bottom = bottom;
        this.isFlooded = isFlooded;
    }

    // convenience constructor for initializing cells
    Cell(double height, int x, int y) {
        this.height = height;
        this.x = x;
        this.y = y;
        this.left = null;
        this.top = null;
        this.right = null;
        this.bottom = null;
        this.isFlooded = false;
    }

    // represents absolute height of this cell, in feet
    double height;

    // In logical coordinates, with the origin at the top-left corner of the
    // scren
    int x, y;

    // the four adjacent cells to this one
    Cell left, top, right, bottom;

    // reports whether this cell is flooded or not
    boolean isFlooded;

    // top left corner
    @Override
    public Iterator<Cell> iterator() {
        return new topLeftIterator(this);
    }

    public WorldImage draw() {
        int x = this.x * ForbiddenIslandWorld.SCALE_SIZE;
        int y = this.y * ForbiddenIslandWorld.SCALE_SIZE;

        Color c;

        if (this.height < 0) {
            c = new Color(0, 0, 255);
            //TODO make blue darker for sinking lands and deal with the actual water level
        }
        else {
            int rbVal = ((int) ((ForbiddenIslandWorld.MAX_HEIGHT - this.height) *
                    (155 / ForbiddenIslandWorld.MAX_HEIGHT))) + 100;

            c = new Color(rbVal, 255, rbVal);
        }

        return new RectangleImage(
                new Posn(x + ForbiddenIslandWorld.SCALE_SIZE /2,
                            y + ForbiddenIslandWorld.SCALE_SIZE /2),
                ForbiddenIslandWorld.SCALE_SIZE,
                ForbiddenIslandWorld.SCALE_SIZE, c);
    }
}

class topLeftIterator implements Iterator<Cell> {

    Cell cur;
    boolean goingRight;

    topLeftIterator(Cell cur) {
        this.cur = cur;
        goingRight = true;
    }

    @Override
    public boolean hasNext() {
        return !(cur == null);
    }

    @Override
    public Cell next() {
        Cell prev = cur;

        if (this.hasNext()) {
            if (goingRight) {
                if (cur.x == ForbiddenIslandWorld.ISLAND_SIZE
                        && cur.y == ForbiddenIslandWorld.ISLAND_SIZE) {
                    cur = null;
                } else if (cur.x == ForbiddenIslandWorld.ISLAND_SIZE) {
                    cur = cur.bottom;
                    goingRight = !goingRight;
                } else {
                    cur = cur.right;
                }
            } else if (cur.x == 0 && cur.y == ForbiddenIslandWorld.ISLAND_SIZE) {
                cur = null;
            } else if (cur.x == 0) {
                cur = cur.bottom;
            } else {
                cur = cur.left;
            }
        }

        return prev;
    }
}

class OceanCell extends Cell {
    OceanCell(int x, int y, Cell left, Cell top, Cell right, Cell bottom) {
        super(-1, x, y, left, top, right, bottom, true);
    }

    // convenience constructor for initializing
    OceanCell(int x, int y) {
        super(-1, x, y, null, null, null, null, true);
    }
}

class ForbiddenIslandWorld extends World {
    // size of the island
    static final int ISLAND_SIZE = 48;

    // max height of the island
    static final double MAX_HEIGHT = ForbiddenIslandWorld.ISLAND_SIZE
            - ForbiddenIslandWorld.ISLAND_SIZE / 4;

    // how large to scale up the board
    static final int SCALE_SIZE = 10;

    // All the cells of the game, including the ocean
    IList<Cell> board;

    // the current height of the ocean
    int waterHeight;

    ForbiddenIslandWorld(IList<Cell> board, int waterHeight) {
        this.board = board;
        this.waterHeight = waterHeight;
    }

    ForbiddenIslandWorld() {
        this.board = this.mountainWorld();
        this.waterHeight = 0;
    }

    // creates a uniform mountain world
    IList<Cell> mountainWorld() {
        ArrayList<ArrayList<Double>> sizes = new ArrayList<ArrayList<Double>>(
                ForbiddenIslandWorld.ISLAND_SIZE + 1);

        for (int i = 0; i <= ForbiddenIslandWorld.ISLAND_SIZE; i += 1) {
            sizes.add(i,
                    new ArrayList<Double>(ForbiddenIslandWorld.ISLAND_SIZE + 1));

            for (int j = 0; j <= ForbiddenIslandWorld.ISLAND_SIZE; j += 1) {

                if (this.manhattanDistanceToCenter(i, j) < ForbiddenIslandWorld.ISLAND_SIZE / 2) {
                    double num = ForbiddenIslandWorld.MAX_HEIGHT
                            - this.manhattanDistanceToCenter(i, j);
                    sizes.get(i).add(j, num);
                } else {
                    sizes.get(i).add(j, -1.0);
                }
            }
        }
        return this.generateBoardFromSizes(sizes);
    }

    // creates a random mountain
    IList<Cell> randomWorld() {
        ArrayList<ArrayList<Double>> sizes = new ArrayList<ArrayList<Double>>(
                ForbiddenIslandWorld.ISLAND_SIZE + 1);

        for (int i = 0; i <= ForbiddenIslandWorld.ISLAND_SIZE; i += 1) {
            sizes.add(i,
                    new ArrayList<Double>(ForbiddenIslandWorld.ISLAND_SIZE + 1));

            for (int j = 0; j <= ForbiddenIslandWorld.ISLAND_SIZE; j += 1) {
                if (this.manhattanDistanceToCenter(i, j) < ForbiddenIslandWorld.ISLAND_SIZE / 2) {
                    double num = (Math.random() * ForbiddenIslandWorld.MAX_HEIGHT);
                    sizes.get(i).add(j, num);
                } else {
                    sizes.get(i).add(j, -1.0);
                }
            }
        }
        return this.generateBoardFromSizes(sizes);
    }

    IList<Cell> generateBoardFromSizes(ArrayList<ArrayList<Double>> sizes) {
        ArrayList<ArrayList<Cell>> cells = new ArrayList<ArrayList<Cell>>(
                ForbiddenIslandWorld.ISLAND_SIZE + 1);

        for (int i = 0; i < sizes.size(); i += 1) {
            cells.add(i, new ArrayList<Cell>(ForbiddenIslandWorld.ISLAND_SIZE + 1));

            for (int j = 0; j < sizes.get(i).size(); j += 1) {
                double size = sizes.get(i).get(j);
                if (size < 0) {
                    cells.get(i).add(j, new OceanCell(j, i));
                } else {
                    cells.get(i).add(j, new Cell(size, j, i));
                }
            }
        }

        this.fixConnections(cells);
        return this.generateIList(cells);
    }

    //EFFECT: fixes connections between cells in the ArrayList
    void fixConnections(ArrayList<ArrayList<Cell>> cells) {
        for (int i = 0; i < cells.size(); i += 1) {

            for (int j = 0; j < cells.get(i).size(); j += 1) {
                Cell cur = cells.get(i).get(j);
                if (cur.x == 0 && cur.y == 0) {
                    cur.left = cur;
                    cur.top = cur;
                    cur.right = cells.get(i).get(j + 1);
                    cur.bottom = cells.get(i + 1).get(j);
                } else if (cur.x == ForbiddenIslandWorld.ISLAND_SIZE
                        && cur.y == 0) {
                    cur.left = cells.get(i).get(j - 1);
                    cur.top = cur;
                    cur.right = cur;
                    cur.bottom = cells.get(i + 1).get(j);
                } else if (cur.y == 0) {
                    cur.left = cells.get(i).get(j - 1);
                    cur.top = cur;
                    cur.right = cells.get(i).get(j + 1);
                    cur.bottom = cells.get(i + 1).get(j);
                } else if (cur.x == ForbiddenIslandWorld.ISLAND_SIZE
                        && cur.y == ForbiddenIslandWorld.ISLAND_SIZE) {
                    cur.left = cells.get(i).get(j - 1);
                    cur.top = cells.get(i - 1).get(j);
                    cur.right = cur;
                    cur.bottom = cur;
                } else if (cur.x == ForbiddenIslandWorld.ISLAND_SIZE) {
                    cur.left = cells.get(i).get(j - 1);
                    cur.top = cells.get(i - 1).get(j);
                    cur.right = cur;
                    cur.bottom = cells.get(i + 1).get(j);
                } else if (cur.x == 0
                        && cur.y == ForbiddenIslandWorld.ISLAND_SIZE) {
                    cur.left = cur;
                    cur.top = cells.get(i - 1).get(j);
                    cur.right = cells.get(i).get(j + 1);
                    cur.bottom = cur;
                } else if (cur.y == ForbiddenIslandWorld.ISLAND_SIZE) {
                    cur.left = cells.get(i).get(j - 1);
                    cur.top = cells.get(i - 1).get(j);
                    cur.right = cells.get(i).get(j + 1);
                    cur.bottom = cur;
                } else if (cur.x == 0) {
                    cur.left = cur;
                    cur.top = cells.get(i - 1).get(j);
                    cur.right = cells.get(i).get(j + 1);
                    cur.bottom = cells.get(i + 1).get(j);
                } else {
                    cur.left = cells.get(i).get(j - 1);
                    cur.top = cells.get(i - 1).get(j);
                    cur.right = cells.get(i).get(j + 1);
                    cur.bottom = cells.get(i + 1).get(j);
                }
            }
        }
    }

    IList<Cell> generateIList(ArrayList<ArrayList<Cell>> cells) {
        IList<Cell> listOfCells = new Empty<Cell>();

        for(ArrayList<Cell> a: cells) {
            for(Cell c: a) {
                listOfCells = new Cons<Cell>(c, listOfCells);
            }
        }
        return listOfCells;
    }

    int manhattanDistanceToCenter(int x, int y) {
        int centerX = ForbiddenIslandWorld.ISLAND_SIZE / 2;
        int centerY = ForbiddenIslandWorld.ISLAND_SIZE / 2;

        return Math.abs((centerX - Math.abs(x - centerX))
                + (centerY - Math.abs(y - centerY)));
    }

    @Override
    public WorldImage makeImage() {
        int size = (ForbiddenIslandWorld.ISLAND_SIZE + 1)
                * ForbiddenIslandWorld.SCALE_SIZE;
        WorldImage bg = new RectangleImage(new Posn(size / 2, size / 2), size, size,
                new Color(0, 0, 0));

        return this.renderScene(bg);

    }

    WorldImage renderScene(WorldImage bg) {
        Cell first = this.board.accept(new getFirstVisitor<Cell>());
        for(Cell c: first) {
            //bg = bg.overlayImages(bg, c.draw()); //TODO
        }
        return bg;
    }
}

class ExamplesForbiddenIsland {
    ForbiddenIslandWorld mountainWorld = new ForbiddenIslandWorld();

    /*void testBigBang(Tester t) {
        int size = (ForbiddenIslandWorld.ISLAND_SIZE + 1) * ForbiddenIslandWorld.SCALE_SIZE;

        mountainWorld.bigBang(size, size);
    }*/

    /*void testStuff(Tester t) {
        System.out.println(mountainWorld.board.accept(new getFirstVisitor<Cell>()).right.x);
    }*/
}