#include <algorithm>
#include <cstdint>
#include <cstdlib>
#include <cstring>
#include <ncurses.h>

#include "character.h"
#include "dungeon.h"
#include "descriptions.h"
#include "draw_dungeon.h"
#include "util.h"

const char *header_top_bottom = "********************";
const char *header_middle =     "*   monster list   *";

const char *eastwest[] = {
  "east",
  "west"
};

const char *northsouth[] = {
  "south",
  "north"
};

/*
 * class room
 */
room::room() {
  x = 0;
  y = 0;
  w = 0;
  h = 0;
}

/*
 * class dungeon
 */
dungeon::dungeon() {
  fog_of_war = true;
  target_mode = false;
  
  int i, j;
  for (i = 0; i < MAP_HEIGHT; i++) {
    for (j = 0; j < MAP_WIDTH; j++) {
      characters[i][j] = NULL;
      fow_map[i][j] = false;
    }
  }
  
  parse_descriptions(*this);
}

dungeon::~dungeon() {
  free_data();
  
  destroy_descriptions(*this);
}

void dungeon::free_data() {
  int i, j, k;
  
  delete [] room_list;
  free(upstair_list);
  free(downstair_list);
  
  for (i = 0; i < MAP_HEIGHT; i++) {
    for (j = 0; j < MAP_WIDTH; j++) {
      fow_map[i][j] = false;
      if (characters[i][j]) {
        delete characters[i][j];
        characters[i][j] = NULL;
      }
      for (k = 0; k < (int)items[i][j].size(); k++) delete items[i][j][k];
      items[i][j].clear();
    }
  }
}

void dungeon::toggle_fog_of_war() {
  fog_of_war = !fog_of_war;
}

void dungeon::update_fog_of_war() {
  int i, j;
  for (i = 0; i < MAP_HEIGHT; i++) {
    for (j = 0; j < MAP_WIDTH; j++) {
      if (pc_sight[i][j]) {
        fow_map[i][j] = true;
      }
    }
  }
}

void dungeon::gen_random_dungeon() {
  init_dungeon_hardness();
  generate_rooms();
  generate_corridors();
  
  // Generate player position
  // Pick a random room
  int r = randrange(0, room_count-1);
  player_pos.x = randrange(room_list[r].x, room_list[r].x + room_list[r].w - 1);
  player_pos.y = randrange(room_list[r].y, room_list[r].y + room_list[r].h - 1);
  
  // Generate stairs
  generate_stairs();
  
  // Create the pc in the character array
  characters[player_pos.y][player_pos.x] = new player_character(player_pos.x, player_pos.y);
}

void dungeon::gen_monsters(int nummon) {
  int open_cells = 0;
  int i, j, k;
  
  // Count the open cells
  for (i = 0; i < MAP_HEIGHT; i++) {
    for (j = 0; j < MAP_WIDTH; j++) {
      if (hardness[i][j] == 0 && characters[i][j] == NULL) {
        open_cells++;
      }
    }
  }
  
  // Record the positions of the open cells
  position *monster_positions = (position *) malloc(open_cells * sizeof(position));
  k = 0;
  for (i = 0; i < MAP_HEIGHT; i++) {
    for (j = 0; j < MAP_WIDTH; j++) {
      if (hardness[i][j] == 0 && characters[i][j] == NULL) {
        monster_positions[k].x = j;
        monster_positions[k].y = i;
        k++;
      }
    }
  }
  
  // Shuffle the list of open cells
  for (i = 0; i < open_cells; i++) {
    int swap_index = rand() % open_cells;
    position tmp = monster_positions[i];
    monster_positions[i] = monster_positions[swap_index];
    monster_positions[swap_index] = tmp;
  }
  
  // Create the monsters
  for (i = 0; i < nummon && i < open_cells; i++) {
    int x = monster_positions[i].x;
    int y = monster_positions[i].y;
    
    monster *m;
    while ((m = monster_descriptions[randrange(0, monster_descriptions.size()-1)].make_monster(x, y)) == 0);
    characters[y][x] = m;
  }
  
  free(monster_positions);
}

void dungeon::gen_items(int numitems) {
  int i;
  
  for (i = 0; i < numitems; i++) {
    int x = 0;
    int y = 0;
    
    while (hardness[y][x] != 0) {
      x = randrange(1, MAP_WIDTH-2);
      y = randrange(1, MAP_HEIGHT-2);
    }
    
    item *it;
    while ((it = object_descriptions[randrange(0, object_descriptions.size()-1)].make_item()) == 0);
    items[y][x].push_back(it);
  }
}

void dungeon::init_turn_heap(heap_t *h) {
  int i, j;
  
  init_character_turn_heap(h);
  
  for (i = 0; i < MAP_HEIGHT; i++) {
    for (j = 0; j < MAP_WIDTH; j++) {
      if (characters[i][j]) {
        heap_insert(h, characters[i][j]);
      }
    }
  }
}

void dungeon::init_dungeon_hardness() {
  int i, j;
  for (i = 0; i < MAP_HEIGHT; i++) {
    for (j = 0; j < MAP_WIDTH; j++) {
      if (i == 0 || i == (MAP_HEIGHT - 1) || j == 0 || j == (MAP_WIDTH - 1)) {
        hardness[i][j] = 255;
      } else {
        hardness[i][j] = randrange(1, 254);
      }
    }
  }
}

void dungeon::generate_stairs() {
  int found_pos, i, j;
  
  // Up stairs
  int num_up_stairs = randrange(1, 2);
  upstair_count = num_up_stairs;
  upstair_list = (position *) malloc(num_up_stairs * sizeof(position));
  
  for (i = 0; i < num_up_stairs; i++) {
    found_pos = 0;
    while (!found_pos) {
      int x = randrange(1, MAP_WIDTH-2);
      int y = randrange(1, MAP_HEIGHT-2);

      if (hardness[y][x] == 0) {
        // This is an open space, let's see if it is already a stair
        int valid = 1;
        for (j = 0; j < i; j++) {
          if (upstair_list[j].x == x && upstair_list[j].y == y) {
            valid = 0;
          }
        }
        
        if (x == player_pos.x && y == player_pos.y) {
          valid = 0;
        }
        
        // If not valid, keep trying
        if (!valid) continue;
        
        upstair_list[i].x = x;
        upstair_list[i].y = y;
        found_pos = 1;
      }
    }
  }
    
  // Down stairs
  int num_down_stairs = randrange(1, 2);
  downstair_count = num_down_stairs;
  downstair_list = (position *) malloc(num_down_stairs * sizeof(position));
  
  for (i = 0; i < num_down_stairs; i++) {
    found_pos = 0;
    while (!found_pos) {
      int x = randrange(1, MAP_WIDTH-2);
      int y = randrange(1, MAP_HEIGHT-2);

      if (hardness[y][x] == 0) {
        // This is an open space, let's see if it is already a stair
        // Have to check both up stairs and down stairs now
        int valid = 1;
        for (j = 0; j < upstair_count; j++) {
          if (upstair_list[j].x == x && upstair_list[j].y == y) {
            valid = 0;
          }
        }
        
        for (j = 0; j < i; j++) {
          if (downstair_list[j].x == x && downstair_list[j].y == y) {
            valid = 0;
          }
        }
        
        if (x == player_pos.x && y == player_pos.y) {
          valid = 0;
        }
        
        // If not valid, keep trying
        if (!valid) continue;
        
        downstair_list[i].x = x;
        downstair_list[i].y = y;
        found_pos = 1;
      }
    }
  }
}

void dungeon::generate_corridors() {
  int i, j;
  
  int* connected = (int *) malloc(room_count * sizeof(int));
  for (i = 0; i < room_count; i++) {
    connected[i] = 0;
  }
  
  connected[0] = 1;
  
  while(1) {
    // Check if all the rooms are connected
    int flag = 1;
    for (i = 0; i < room_count; i++) {
      if (!connected[i]) flag = 0;
    }
    if (flag) break;
    
    // Find the closest connected/disconnected pair of rooms
    int minDistFact = 10000;
    int room1 = 0;
    int room2 = 0;
    for (i = 0; i < room_count; i++) {
      if (connected[i]) continue;
      for (j = 0; j < room_count; j++) {
        if (!connected[j]) continue;
        
        // Compare distance, no need to square root since we
        // don't care about the actual distance
        int xFact = room_list[j].x - room_list[i].x;
        int yFact = room_list[j].y - room_list[i].y;
        int distFact = xFact * xFact + yFact * yFact;
        if (distFact < minDistFact) {
          minDistFact = distFact;
          room1 = i; //disconnected room
          room2 = j; //connected room
        }
      }
    }
    
    // Connect the rooms with corridors
    connect_rooms(room1, room2);
    connected[room1] = 1;
  }
  
  free(connected);
}

void dungeon::connect_rooms(int room1, int room2) {
  int i;
  
  // Start position
  int currX = randrange(room_list[room1].x, room_list[room1].x + room_list[room1].w - 1);
  int currY = randrange(room_list[room1].y, room_list[room1].y + room_list[room1].h - 1);

  // End position
  int targetX  = randrange(room_list[room2].x, room_list[room2].x + room_list[room2].w - 1);
  int targetY = randrange(room_list[room2].y, room_list[room2].y + room_list[room2].h - 1);

  while(1) {
    // Where we need to travel to get there
    int dx = targetX - currX;
    int dy = targetY - currY;

    // Select which direction and how far to go
    if (randchance(0.5)) {
      dx = 0;
      dy = sign(dy) * randrange(0, abs(dy)/2+1);
    } else {
      dy = 0;
      dx = sign(dx) * randrange(0, abs(dx)/2+1);
    }

    // Number of iterations in this leg of the corridor
    int dist = abs(dx + dy);

    // Draw each cell along the way, avoiding rooms
    // If we cross an existing corridor, exit - it is connected
    for (i = 0; i < dist; i++) {
      currX += sign(dx);
      currY += sign(dy);
      
      hardness[currY][currX] = 0;
    }

    // Once we have reached our target, exit
    if (currX == targetX && currY == targetY) {
      return;
    }
  }
}

void dungeon::generate_rooms() {
  int i, j, k;
  
  int room_eligible[MAP_HEIGHT][MAP_WIDTH];
  for (i = 0; i < MAP_HEIGHT; i++) {
    for (j = 0; j < MAP_WIDTH; j++) {
      room_eligible[i][j] = !(i == 0 || i == (MAP_HEIGHT-1) || j == 0 || j == (MAP_WIDTH-1));
    }
  }
  
  // Choose how many rooms to make
  int rooms_to_make = randrange(MIN_ROOMS, MAX_ROOMS);
  
  // Initialize the dungeon with that information
  room_count = rooms_to_make;
  room_list = new room[room_count];
  
  for (k = 0; k < rooms_to_make; k++) {
    int foundRoom = 0;
    int x, y, w, h;
    
    // Until we have found a valid position for the room
    while(!foundRoom) {
      // Generate random parameters for the room
      w = randrange(4, 10);
      h = randrange(3, 8);
      x = randrange(1, MAP_WIDTH - w);
      y = randrange(1, MAP_HEIGHT - h);
      
      // Assume that this is good
      foundRoom = 1;
      
      // Check every cell in the new room to see if it is eligible
      // If not, set the flag to false so we will try again
      for (i = y; i < y+h; i++) {
        for (j = x; j < x+w; j++) {
          if (!room_eligible[i][j]) foundRoom = 0;
        }
      }
    }
    
    // Save the parameters of the room in the array
    room_list[k].x = x;
    room_list[k].y = y;
    room_list[k].w = w;
    room_list[k].h = h;
    
    // Mark this room and the border around it as ineligible for room placement
    for (i = y-1; i < y+h+1; i++) {
      for (j = x-1; j < x+w+1; j++) {
        room_eligible[i][j] = 0;
      }
    }
    
    // Mark the cells in the map as room cells
    for (i = y; i < y+h; i++) {
      for (j = x; j < x+w; j++) {
        hardness[i][j] = 0;
      }
    }
  }
}

int dungeon::targeting_mode() {
  targeting_pointer.x = player_pos.x;
  targeting_pointer.y = player_pos.y;
  
  target_mode = true;
  
  draw();
  refresh_screen();
  
  while (true) {
    char key = getch();
    
    if (key == '7' || key == 'y') {
      targeting_pointer.x--;
      targeting_pointer.y--;
    }

    if (key == '8' || key == 'k') {
      targeting_pointer.y--;
    }

    if (key == '9' || key == 'u') {
      targeting_pointer.y--;
      targeting_pointer.x++;
    }

    if (key == '6' || key == 'l') {
      targeting_pointer.x++;
    }

    if (key == '3' || key == 'n') {
      targeting_pointer.x++;
      targeting_pointer.y++;
    }

    if (key == '2' || key == 'j') {
      targeting_pointer.y++;
    }

    if (key == '1' || key == 'b') {
      targeting_pointer.x--;
      targeting_pointer.y++;
    }

    if (key == '4' || key == 'h') {
      targeting_pointer.x--;
    }
    
    if (key == 'r') {
      targeting_pointer.x = randrange(1, MAP_WIDTH-2);
      targeting_pointer.y = randrange(1, MAP_HEIGHT-2);
      key = 't';
    }
    
    if (key == 't') {
      if (targeting_pointer.x == player_pos.x && targeting_pointer.y == player_pos.y) {
        target_mode = false;
        return 0;
      }
      
      hardness[targeting_pointer.y][targeting_pointer.x] = 0;
      if (characters[targeting_pointer.y][targeting_pointer.x]) {
        characters[targeting_pointer.y][targeting_pointer.x]->alive = 0;
      }
      
      character *c = characters[player_pos.y][player_pos.x];
      characters[player_pos.y][player_pos.x] = NULL;
      characters[targeting_pointer.y][targeting_pointer.x] = c;
      player_pos = targeting_pointer;
      c->pos = targeting_pointer;
      
      target_mode = false;
      return 0;
    }
    
    if (key == 'q') {
      target_mode = false;
      return 1;
    }
    
    targeting_pointer.x = std::max((int)targeting_pointer.x, 1);
    targeting_pointer.x = std::min((int)targeting_pointer.x, MAP_WIDTH-2);
    targeting_pointer.y = std::max((int)targeting_pointer.y, 1);
    targeting_pointer.y = std::min((int)targeting_pointer.y, MAP_HEIGHT-2);
    
    draw();
    refresh_screen();
  }
}

int dungeon::display_monster_list() {
  attron(COLOR_PAIR(COLOR_WHITE));
  
  int i, j, k;
  int count = 0;
  for (i = 0; i < MAP_HEIGHT; i++) {
    for (j = 0; j < MAP_WIDTH; j++) {
      if (characters[i][j] && !characters[i][j]->is_player()) {
        count++;
      }
    }
  }
  
  k = 0;
  
  char **monster_strings = (char **) malloc(count * sizeof(char*));
  
  for (i = 0; i < MAP_HEIGHT; i++) {
    for (j = 0; j < MAP_WIDTH; j++) {
      if (characters[i][j] && !characters[i][j]->is_player()) {
        *(monster_strings+k) = (char *) malloc(40 * sizeof(char*));
        int dx = player_pos.x - characters[i][j]->pos.x;
        int dy = player_pos.y - characters[i][j]->pos.y;
        
        int horiz = abs(dx);
        int vert = abs(dy);
        
        const char *str1 = eastwest[std::min(1, sign(dx)+1)];
        const char *str2 = northsouth[std::min(1, sign(dy)+1)];
        snprintf(*(monster_strings+k), 39, "%c, %d %s and %d %s", characters[i][j]->symbol, horiz, str1, vert, str2);
        k++;
      }
    }
  }
  
  k = 0;
  int shouldExit = 0;
  while(1) {
    for (i = 2; i < 21; i++) {
      for (j = 1; j < 79; j++) {
        mvaddch(i, j, ' ');
      }
    }
    
    mvaddstr(3, (80 - strlen(header_top_bottom)) / 2, header_top_bottom);
    mvaddstr(4, (80 - strlen(header_middle)) / 2, header_middle);
    mvaddstr(5, (80 - strlen(header_top_bottom)) / 2, header_top_bottom);
    
    if (k > 0) {
      mvprintw(7, 38, "(+%d)", k);
    }
    
    for (i = k; i < std::min(k+5, count); i++) {
      mvaddstr(((i-k) * 2) + 9, (80 - strlen(monster_strings[i])) / 2, monster_strings[i]);
    }
    
    if (k+5 < count) {
      mvprintw(19, 38, "(+%d)", count-(k+5));
    }
    
    refresh_screen();
    
    int key = getch();
    
    if (key == KEY_DOWN) {
      k = std::max(0, std::min(count-5, k+1));
    }
    
    if (key == KEY_UP) {
      k = std::max(0, k-1);
    }
    
    if (key == 27) {
      // Escape key
      break;
    }
    
    if (key == 'q' || key == 'Q') {
      shouldExit = 1;
      break;
    }
  }
  
  attroff(COLOR_PAIR(COLOR_WHITE));
  
  for (i = 0; i < count; i++) {
    free(monster_strings[i]);
  }
  free(monster_strings);
  
  return shouldExit;
}

void dungeon::draw_map_char(int y, int x) {
  int i;
  
  // Check each position from top down, i.e. check the layers which would
  // render over other layers first.
  
  if (y == 0 || y == (MAP_HEIGHT-1) || x == 0 || x == (MAP_WIDTH-1)) {
    if (y == 0 || y == (MAP_HEIGHT - 1)) {
      print_char('-', COLOR_WHITE);
      return;
    } else {
      print_char('|', COLOR_WHITE);
      return;
    }
  }
  
  bool disp_fog_of_war = !target_mode && fog_of_war;
  
  if (disp_fog_of_war && !fow_map[y][x]) {
    print_char(' ', COLOR_WHITE);
    return;
  }
  
  if (pc_sight[y][x]) {
    remembered_terrain[y][x] = ' ';
    
    if (hardness[y][x] == 0) {
      remembered_terrain[y][x] = '#';
    }
    
    for (i = 0; i < room_count; i++) {
      room *r = room_list + i;
      if (x >= r->x && x < r->x + r->w && y >= r->y && y < r->y + r->h) {
        remembered_terrain[y][x] = '.';
      }
    }
    
    for (i = 0; i < upstair_count; i++) {
      if (x == upstair_list[i].x && y == upstair_list[i].y) {
        remembered_terrain[y][x] = '<';
      }
    }

    for (i = 0; i < downstair_count; i++) {
      if (x == downstair_list[i].x && y == downstair_list[i].y) {
        remembered_terrain[y][x] = '>';
      }
    }
  }
  
  if (pc_sight[y][x] || !disp_fog_of_war) {
    if (target_mode && y == targeting_pointer.y && x == targeting_pointer.x) {
      print_char('*', COLOR_WHITE);
      return;
    }
    
    if (characters[y][x]) {
      int color = characters[y][x]->next_color();
      print_char(characters[y][x]->symbol, color);
      return;
    }
  }
  
  if ((!disp_fog_of_war || fow_map[y][x]) && items[y][x].size() > 0) {
    char symbol;
    int color;
    if (items[y][x].size() > 1) {
      symbol = '&';
      color = items[y][x][0]->get_color();
    } else {
      symbol = items[y][x][0]->get_symbol();
      color = items[y][x][0]->get_color();
    }
    print_char(symbol, color);
    return;
  }
  
  if (disp_fog_of_war) {
    print_char(remembered_terrain[y][x], COLOR_WHITE);
    return;
  } else {    
    for (i = 0; i < upstair_count; i++) {
      if (x == upstair_list[i].x && y == upstair_list[i].y) {
        print_char('<', COLOR_WHITE);
        return;
      }
    }

    for (i = 0; i < downstair_count; i++) {
      if (x == downstair_list[i].x && y == downstair_list[i].y) {
        print_char('>', COLOR_WHITE);
        return;
      }
    }
    
    for (i = 0; i < room_count; i++) {
      room *r = room_list + i;
      if (x >= r->x && x < r->x + r->w && y >= r->y && y < r->y + r->h) {
        print_char('.', COLOR_WHITE);
        return;
      }
    }
    
    if (hardness[y][x] == 0) {
      print_char('#', COLOR_WHITE);
      return;
    }
    
    print_char(' ', COLOR_WHITE);
    return;
  }
}

void dungeon::draw() {
  int i, j;
  
  move(1, 0);
  
  for (i = 0; i < MAP_HEIGHT; i++) {
    for (j = 0; j < MAP_WIDTH; j++) {
      draw_map_char(i, j);
    }
  }
}