/**
 * @author Bassem Halim
 * @source https://eskerda.com/bsp-dungeon-generation
 */

package byow.Core;

import byow.TileEngine.TERenderer;
import byow.TileEngine.TETile;
import byow.TileEngine.Tileset;
import java.util.*;
import java.awt.*;
import java.text.CompactNumberFormat;
import java.util.Random;

public class Engine {
    TERenderer ter = new TERenderer();
    /* Feel free to change the width and height. */
    public static final int WIDTH = 80;
    public static final int HEIGHT = 40;
    private static final int MinRoom = 2; // minimum room size 2 x 2
    private static final int MaxRoom = 7;
    private static final int MaxNumSplit = 15; //the maximum number canvas split
    private static final int MinNumSplit = 8;
    private  Deque<Room> rooms;
    TETile[][] world;

    private static final long SEED = 335098; //TODO delete after implementing input
    private static final Random RANDOM = new Random(SEED);

    private static class Position { //change to nonstatic
        int x;
        int y;
        Position(int x, int y){
            this.x = x;
            this.y = y;
        }
        //shifts x by dx (x=>x+dx...)
        public Position shift(int dx, int dy){
            return new Position(this.x + dx, this.y + dy);
        }
        @Override
        //for debugging
        public String toString(){
            String pos = "(" + String.valueOf(this.x) +"," + String.valueOf(this.y) + ")";
            return pos;
        }
        public int distanceTO(Position p){
           return (this.x - p.x)^2 + (this.y - p.y)^2;
        }
    }

    private static class Room {
        protected final Position pos; // bottom left of a room (not including walls
        protected final int l;
        protected final int h;
        public Room(Position pos, int l, int h) {
            this.pos = pos;
            this.l = l;
            this.h = h;
        }
        @Override
        //for debugging
        public String toString(){
            return this.pos.toString();
        }

        public Position center() {
            return pos.shift(l/2, h/2);
        }
    }

    private static class container {
        Position pos; //bottom left
        int h;
        int w;
        Room room;

        public container(Position p, int h, int w) {
            if (h < 0 || w < 0) {
                return;
            }
            this.pos = p;
            this.h = h;
            this.w = w;
        }

        public void addRoom(Room room) {
            this.room = room;
        }

        //returns a random position within the given area
        public Position getRandomPos() {
            int x = RandomUtils.uniform(RANDOM, pos.x, pos.x + w);
            int y = RandomUtils.uniform(RANDOM, pos.y, pos.y + h);
            return new Position(x, y);
        }

        @Override
        public String toString() {
            String dim = "HXW" + this.h + "x" + this.w;
            return  this.pos.toString() + dim;
        }
    }
    //binary tree of containers
    private class BT{
        container root;
        BT left;
        BT right;
        public BT(container root){
            this.root = root;
        }
    }


    // creates a canvas of WIDTH x HEIGHT and fills it with Tileset.NOTHING
    public Engine(){
        ter.initialize(WIDTH, HEIGHT);
        world = new TETile[WIDTH][HEIGHT];
        for (int x = 0; x < WIDTH; x += 1) {
            for (int y = 0; y < HEIGHT; y += 1) {
                world[x][y] = Tileset.NOTHING;
            }
        }
    }

    /**
     * Method used for exploring a fresh world. This method should handle all inputs,
     * including inputs from the main menu.
     */
    public void interactWithKeyboard() {
    }

    /**
     * Method used for autograding and testing your code. The input string will be a series
     * of characters (for example, "n123sswwdasdassadwas", "n123sss:q", "lwww". The engine should
     * behave exactly as if the user typed these characters into the engine using
     * interactWithKeyboard.
     *
     * Recall that strings ending in ":q" should cause the game to quite save. For example,
     * if we do interactWithInputString("n123sss:q"), we expect the game to run the first
     * 7 commands (n123sss) and then quit and save. If we then do
     * interactWithInputString("l"), we should be back in the exact same state.
     *
     * In other words, both of these calls:
     *   - interactWithInputString("n123sss:q")
     *   - interactWithInputString("lww")
     *
     * should yield the exact same world state as:
     *   - interactWithInputString("n123sssww")
     *
     * @param input the input string to feed to your program
     * @return the 2D TETile[][] representing the state of the world
     */
    public TETile[][] interactWithInputString(String input) {
        // TODO: Fill out this method so that it run the engine using the input
        // passed in as an argument, and return a 2D tile representation of the
        // world that would have been drawn if the same inputs had been given
        // to interactWithKeyboard().
        //
        // See proj3.byow.InputDemo for a demo of how you can make a nice clean interface
        // that works for many different input types.

        TETile[][] finalWorldFrame = null;
        return finalWorldFrame;
    }


    // generates a random number of rooms of random sizes and add them to canvas
    public void genRooms() {
        int splits = RandomUtils.uniform(RANDOM,MinNumSplit, MaxNumSplit);
        container fullMap = new container(new Position(0,0),HEIGHT, WIDTH );
        BT tree = genSplits(splits, fullMap);
        //TODO: connect each sister leaves level by level
        Deque<BT> leaves = getLeaves(tree);
        rooms = new LinkedList<>();
        for (BT t : leaves) {
            container c = t.root;
            boolean madeRoom;
            int i = 0;
            do {
                Position roomPos = c.getRandomPos();
                int l = RandomUtils.uniform(RANDOM, MinRoom, MaxRoom);
                int w = RandomUtils.uniform(RANDOM, MinRoom, MaxRoom);
                madeRoom = createRoom(l, w, roomPos,c);
                if (madeRoom) {
                    Room room = new Room(roomPos, l, w);
                    rooms.addFirst(room);
                }
                i++;
                if (i > 20) {
                    Position newPos = c.pos.shift(0,0);
                    madeRoom = createRoom(MinRoom,MinRoom,newPos, c);
                    if (madeRoom) {
                        Room room = new Room(roomPos, l, w);
                        rooms.addFirst(room);
                    }
                    break;
                }
            } while (!madeRoom);
        }
    }

    // returns all leaves of tree
    private static Deque<BT> getLeaves(BT tree){
        Deque<BT> leaves = new LinkedList<>();
        if (tree.right == null && tree.left == null){
            leaves.addLast(tree);
            return leaves;
        }
        if (tree.left != null) {
            Deque<BT> left = getLeaves(tree.left);
            for (BT t : left) {
                leaves.addFirst(t); //TODO addfirst?
            }
        }
        if (tree.right != null) {
            Deque<BT> right = getLeaves(tree.right);
            for (BT t : right) {
                leaves.addFirst(t);
            }
        }
        return leaves;
    }

    // splits the canvas numSplits times (2^numSplits rooms)
    private BT genSplits(int numSplits, container c){
        BT tree = new BT(c);
        if (numSplits != 0 && (c.h > 8 && c.w > 8)) {
            container[] newCont = splitContainer(tree.root);
            if (newCont != null) {
                tree.left = genSplits(numSplits - 1, newCont[0]);
                tree.right = genSplits(numSplits - 1, newCont[1]);
            }
        }
        return tree;
    }

    // splits the given container randomly either horizontally or vertically
    private container[] splitContainer(container c){
        int rand = RandomUtils.uniform(RANDOM, 0,2);
        container c1 = null, c2 = null;
        Position second;
        container[] out;
        if (c.h < 9 && c.w < 9){
            return null;
        } else if (c.h < 9){
            rand = 1; // can only cut vertically
        } else if (c.w < 9) {
            rand = 0; // can only cut horizontally
        }
        switch (rand){
            case 0:  // horizontally
                int dy =(c.h + 1) / 2;
                if (c.h > 9) {
                   dy =  RandomUtils.uniform(RANDOM,MinRoom + 3, c.h - 3);
                }
                c1 = new container(c.pos, dy ,c.w); // TODO: dy -1
                second =  c.pos.shift(0, dy);
                c2 = new container(second,c.h - dy,c.w);
                break;
            case 1: // vertically
                int dx =(c.w + 1) / 2;
                if (c.w > 9) {
                    dx =  RandomUtils.uniform(RANDOM,MinRoom + 3, c.w - 3);
                }
                c1 = new container(c.pos, c.h, dx); //TODO dx - 1
                second =  c.pos.shift(dx , 0);
                c2 = new container(second,c.h, c.w - dx);
                break;
        }
        out = new container[]{c1,c2};
        return out;
    }


    public void connectRooms() {
        Room curr = rooms.removeLast();
        while (!rooms.isEmpty()) {
            Room other = rooms.removeLast();
            if (curr.pos.distanceTO(other.pos) > 40){
                rooms.addFirst(other);
                continue;
            }
            connect(curr, other);
            curr = other;
        }
    }
    /**
     * generates a room of size l x w (not including walls) at the given position
     * the given position is the bottom left corner of the room
     * //       @@@@@
     * //       @...@   1 x 3
     * //  pos=>@@@@@
     */
    private boolean createRoom(int h, int w, Position pos, container c){
        if (c == null){
            c = new container(new Position(0,0),HEIGHT,WIDTH);
        }
        if (nearEdge(pos, h, w, c)) return false;
       // if (willOverlap(pos,l + 2,w + 2)) System.out.println("overlap");
        for (int dx = pos.x; dx < pos.x + w; dx++){
            for (int dy = pos.y; dy <pos.y + h; dy++){
                world[dx][dy] = Tileset.FLOOR;
            }
        }
        Position wallPos = pos.shift(-1,-1);
        if (c == null) {// don't wall ends
            addWall(h + 2, w + 2, wallPos, false);
        } else {
            addWall(h + 2, w + 2, wallPos, true);
        }
        return true;
    }

    // creates a Hallway of length l from start to end
    private void connect(Room first, Room second) {
        Position center1 = first.center();
        Position center2 = second.center();

        Room left = first, right = second, top = first, bottom = second;
        if (center2.x <= center1.x){
            left = second;
            right = first;
        }
        if (center1.y <= center2.y) {
            bottom = first;
            top = second;
        }

        //if both rooms are below each other and have some overlap in the x direction
        if (center1.x == center2.x || (left.pos.x <= right.pos.x && right.pos.x <= left.pos.x + left.l) ) {
            Position edgeOfBottom = bottom.pos.shift(right.pos.x - left.pos.x, bottom.h );
            int dist = top.pos.y - edgeOfBottom.y;
            makeCol(edgeOfBottom,dist + 1, Tileset.FLOOR);
            makeCol(edgeOfBottom.shift(-1,0),dist ,Tileset.WALL );
            makeCol(edgeOfBottom.shift(1,0),dist, Tileset.WALL);

        } else if (center1.y == center2.y || (bottom.pos.y <= top.pos.y && top.pos.y <= bottom.pos.y + bottom.h)){
            Position edgeOfLeft = left.center().shift(left.l , top.pos.y - bottom.pos.y);
            int dist = right.pos.x - edgeOfLeft.x ;
            makeRow(edgeOfLeft,dist + 1, Tileset.FLOOR);
            makeRow(edgeOfLeft.shift(0,1),dist, Tileset.WALL);
            makeRow(edgeOfLeft.shift(0,-1),dist, Tileset.WALL);
        } else {
//|| (left.pos.x <= right.pos.x && right.pos.x <= left.pos.x + left.l)
//  || (bottom.pos.y <= top.pos.y && top.pos.y <= bottom.pos.y + bottom.h)
        }
    }

    // this method determines if we will overlap with another room if we place an (l x w) room at
    // the given position
    private boolean willOverlap(Position pos,int l, int w){
        for (int x = pos.x; x < pos.x + w; x++) {
            for (int y = pos.y; y < pos.y + l; y++) {
                TETile tile = world[x][y];
                if (tile.equals(Tileset.WALL) || tile.equals(Tileset.FLOOR)) {
                    return true;
                }
            }
        }
        return false;
    }

    // this method puts a wall around a room
    private void addWall(int h, int w, Position pos, boolean fillEdge){
        //bottom wall
        makeRow(pos,w, Tileset.WALL);
        //top wall
        Position top = new Position(pos.x, pos.y + h - 1);
        makeRow(top,w, Tileset.WALL);
        //left wall
        makeCol(pos,h, Tileset.WALL); //overwrites 2 tiles
        //right wall
        Position right = new Position(pos.x + w - 1, pos.y);
        makeCol(right,h,Tileset.WALL);

    }
    // makes a row of length l at the given position (the given pos. is the left side of the row)
    private void makeRow(Position pos, int l, TETile tile) {
        for (int x = pos.x; x < pos.x + l; x++) {
            world[x][pos.y] = tile;
        }
    }

    // makes a column at the given position and build up
    private void makeCol(Position pos, int h, TETile tile) {
        for (int y = pos.y ; y < pos.y + h ; y++ ){
            world[pos.x][y] = tile;
        }
    }

    // determines if we are near an edge (or outside a container) to avoid out of bound errors
    private boolean nearEdge(Position pos, int l, int w, container c) {
        if (pos.x <= 0 || pos.x >= WIDTH   || pos.x + w >= c.pos.x + c.w || pos.x + w >= WIDTH - 1 ){ //TODO add >=?
            return true;
        }
        return pos.y <= 0 || pos.y >= HEIGHT || pos.y + l >= c.pos.y + c.h || pos.y + l >= HEIGHT - 1;
    }

    // for testing only
    public static void main(String[] args) {
        Engine engine = new Engine();
        engine.genRooms();
        engine.connectRooms();
        engine.ter.renderFrame(engine.world);
        System.out.println("done");


    }



}