/*
 * +================================================================================+
 *      __  ___  ______________  __  __  ______________   ____
 *     / / / / |/ /  _/_  __/\ \/ / / / / /_  __/  _/ /  / __/
 *    / /_/ /    // /  / /    \  / / /_/ / / / _/ // /___\ \
 *    \____/_/|_/___/ /_/     /_/  \____/ /_/ /___/____/___/
 *
 * +================================================================================+
 *
 *    "THE BEER-WARE LICENSE"
 *    -----------------------
 *
 *    As long as you retain this notice you can do whatever you want with this
 *    stuff. However it is expressly forbidden to sell or commercially distribute
 *    Unity Utils or parts of it apart from your games.
 *    If you meet any of the authors some day, and you think this stuff is
 *    worth it, you can buy them a beer in return.
 *
 *    THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 *    IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 *    FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 *    AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 *    LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 *    OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
 *    THE SOFTWARE.
 *
 * +================================================================================+
 *
 *    Authors:
 *    David Krummenacher (dave@timbookedtwo.com)
 *
 */

using UnityEngine;

namespace Utils.Data {

	/// <summary>
	/// Generic representation of a 2 dimensional grid.
	/// </summary>
	public class Grid<T> {

		/// <summary>
		/// The cells of the grid.
		/// </summary>
		private T[,] cells;

		/// <summary>
		/// Initializes a new empty instance of the <see cref="Utils.Data.Grid`1"/> class.
		/// </summary>
		public Grid() : this(0, 0) { }

		/// <summary>
		/// Initializes a new instance of the <see cref="Utils.Data.Grid`1"/> class.
		/// </summary>
		/// <param name="columns">The amount of columns in the grid.</param>
		/// <param name="rows">The amount of rows in the grid.</param>
		public Grid(int columns, int rows) {
			cells = new T[columns, rows];
		}

		/// <summary>
		/// Copies an instance of the <see cref="Utils.Data.Grid`1"/> class.
		/// </summary>
		/// <param name="original">Original grid.</param>
		public Grid(Grid<T> original) {
			cells = original.cells;
		}

		/// <summary>
		/// Gets or sets the cell of the <see cref="Utils.Data.Grid`1"/> based on the specified column and row.
		/// </summary>
		/// <param name="column">Column.</param>
		/// <param name="row">Row.</param>
		public T this[int column, int row] {
			get { return cells[column, row]; }
			set { cells[column, row] = value; }
		}

		/// <summary>
		/// Gets or sets the cell of the <see cref="Utils.Data.Grid`1"/> based on the specified grid position.
		/// </summary>
		/// <param name="gridPosition">Grid position.</param>
		public T this[GridPosition gridPosition] {
			get { return cells[gridPosition.Column, gridPosition.Row]; }
			set { cells[gridPosition.Column, gridPosition.Row] = value; }
		}

		/// <summary>
		/// Gets the amount columns.
		/// </summary>
		/// <value>The columns.</value>
		public int Columns { get { return cells.GetLength(0); } }
		/// <summary>
		/// Gets the amount rows.
		/// </summary>
		/// <value>The rows.</value>
		public int Rows { get { return cells.GetLength(1); } }

		/// <summary>
		/// Adds rows to the grid.
		/// </summary>
		/// <param name="amount">The amount of rows to add.</param>
		/// <param name="inFront">If set to <c>true</c> places the row in front of the other rows.</param>
		public void AddRow(int amount = 1, bool inFront = false) {
			T[,] temp = new T[Columns, Rows + amount];
			for (int column = 0; column < Columns; column++) {
				for (int row = 0; row < Rows; row++) {
					temp[column, (inFront) ? row + amount : row] = cells[column, row];
				}
			}
			cells = temp;
		}

		/// <summary>
		/// Adds columns to the grid.
		/// </summary>
		/// <param name="amount">The amount of columns to add.</param>
		/// <param name="inFront">If set to <c>true</c> places the column in front of the other columns.</param>
		public void AddColumn(int amount = 1, bool inFront = false) {
			T[,] temp = new T[Columns + amount, Rows];
			for (int column = 0; column < Columns; column++) {
				for (int row = 0; row < Rows; row++) {
					temp[(inFront) ? column + amount : column, row] = cells[column, row];
				}
			}
			cells = temp;
		}

		/// <summary>
		/// Removes rows from the grid.
		/// </summary>
		/// <param name="amount">The amount of rows.</param>
		/// <param name="inFront">If set to <c>true</c> removes the rows in front of the other rows.</param>
		public void RemoveRow(int amount = 1, bool inFront = false) {
			T[,] temp = new T[Columns, Rows - amount];
			for (int column = 0; column < Columns; column++) {
				for (int row = 0; row < Rows - amount; row++) {
					temp[column, row] = cells[column, (inFront) ? row + amount : row];
				}
			}
			cells = temp;
		}

		/// <summary>
		/// Removes columns from the grid.
		/// </summary>
		/// <param name="amount">The amount of columns.</param>
		/// <param name="inFront">If set to <c>true</c> removes the columns in front of the other columns.</param>
		public void RemoveColumn(int amount = 1, bool inFront = false) {
			T[,] temp = new T[Columns - amount, Rows];
			for (int column = 0; column < Columns - amount; column++) {
				for (int row = 0; row < Rows; row++) {
					temp[column, row] = cells[(inFront) ? column + amount : column, row];
				}
			}
			cells = temp;
		}

		/// <summary>
		/// Removes the row at a given index.
		/// </summary>
		/// <param name="index">The index.</param>
		public void RemoveRowAtIndex(int index) {
			int rows = Rows - 1;

			T[,] temp = new T[Columns, rows];
			for (int column = 0; column < Columns; column++) {
				for (int row = 0; row < rows; row++) {
					if (row == index) continue;
					temp[column, row] = cells[column, (row >= index) ? row + 1 : row];
				}
			}
			cells = temp;
		}

		/// <summary>
		/// Removes the column at a given index.
		/// </summary>
		/// <param name="index">The index.</param>
		public void RemoveColumnAtIndex(int index) {
			int columns = Columns - 1;
			
			T[,] temp = new T[columns, Rows];
			for (int column = 0; column < columns; column++) {
				if (column == index) continue;
				for (int row = 0; row < Rows; row++) {
					temp[column, row] = cells[(column >= index) ? column + 1 : column, row];
				}
			}
			cells = temp;
		}

		/// <summary>
		/// Add the specified grid to the grid at the specified column and row.
		/// Can override the existing values.
		/// </summary>
		/// <param name="grid">The grid to add.</param>
		/// <param name="column">The column to place the added grid.</param>
		/// <param name="row">The row to place the added grid.</param>
		/// <param name="overrideExisting">If set to <c>true</c> overrides the existing values.</param>
		public void Add(Grid<T> grid, int column, int row, bool overrideExisting = true) {
			int columns, rows, originalColumn, originalRow;

			// Get column positions
			if (column >= 0) {
				originalColumn = 0;
				columns = (Columns > column + grid.Columns) ? Columns : column + grid.Columns;
			} else {
				originalColumn = Mathf.Abs(column);
				columns = Columns + originalColumn;
				column = 0;
			}

			// Get row positions
			if (row >= 0) {
				originalRow = 0;
				rows = (Rows > row + grid.Rows) ? Rows : row + grid.Rows;
			} else {
				originalRow = Mathf.Abs(row);
				rows = Rows + originalRow;
				row = 0;
			}

			T[,] temp = new T[columns, rows];

			if (overrideExisting) {
				for (int c = 0; c < columns; c++) {
					for (int r = 0; r < rows; r++) {
						// Copy new if available, else copy original if available
						if (c >= column && c < column + grid.Columns && r >= row && r < row + grid.Rows) {
							temp[c, r] = grid[c - column, r - row];
						} else if (c >= originalColumn && c < originalColumn + Columns && r >= originalRow && r < originalRow + Rows) {
							temp[c, r] = cells[c - originalColumn, r - originalRow];
						}
					}
				}
			} else {
				for (int c = 0; c < columns; c++) {
					for (int r = 0; r < rows; r++) {
						// Copy original if available, else copy new if available
						if (c >= originalColumn && c < originalColumn + Columns && r >= originalRow && r < originalRow + Rows) {
							temp[c, r] = cells[c - originalColumn, r - originalRow];
						} else if (c >= column && c < column + grid.Columns && r >= row && r < row + grid.Rows) {
							temp[c, r] = grid[c - column, r - row];
						}
					}
				}
			}

			cells = temp;
		}

		/// <summary>
		/// Checks if the grid contains the specified object.
		/// </summary>
		/// <returns><c>true</c> if the object was found in the grid; otherwise, <c>false</c></returns>
		/// <param name="obj">The object to look for.</param>
		public bool Contains(T obj) {
			for (int column = 0; column < Columns; column++) {
				for (int row = 0; row < Rows; row++) {
					if (cells[column, row].Equals(obj)) return true;
				}
			}
			return false;
		}

		/// <summary>
		/// Indicates whether the specified column and row are inside the bounds of the grid.
		/// </summary>
		/// <returns><c>true</c> if the specified column and row are inside the bounds of the grid; otherwise, <c>false</c>.</returns>
		/// <param name="column">The column.</param>
		/// <param name="row">The row.</param>
		public bool IsInsideBounds(int column, int row) {
			return column >= 0 && column < cells.GetLength(0) && row >= 0 && row < cells.GetLength(1);
		}

		/// <summary>
		/// Indicates whether the specified grid position is inside the bounds of the grid.
		/// </summary>
		/// <returns><c>true</c> if the specified grid position is inside the bounds of the grid; otherwise, <c>false</c>.</returns>
		/// <param name="gridPosition">The grid position.</param>
		public bool IsInsideBounds(GridPosition gridPosition) {
			return IsInsideBounds(gridPosition.Column, gridPosition.Row);
		}

		/// <summary>
		/// Trim the grid. All rows and columns that are empty will be removed.
		/// </summary>
		public void Trim() {
			// Find start row
			int startRow;
			for (startRow = 0; startRow < Rows; startRow++) {
				if (IsNotEmpty(true, startRow)) break;
			}
			
			// Find end row
			int endRow;
			for (endRow = Rows; endRow >= 0; endRow--) {
				if (IsNotEmpty(true, endRow)) break;
			}
			
			// Find start column
			int startColumn;
			for (startColumn = 0; startColumn < Columns; startColumn++) {
				if (IsNotEmpty(false, startColumn)) break;
			}
			
			// Find end column
			int endColumn;
			for (endColumn = 0; endColumn >= 0; endColumn--) {
				if (IsNotEmpty(false, endColumn)) break;
			}
			
			// Copy and apply
			T[,] temp = new T[endColumn - startColumn, endRow - startRow];
			for (int column = startColumn; column < endColumn; column++) {
				for (int row = startRow; row < endRow; row++) {
					temp[column - startColumn, row - startRow] = cells[column, row];
				}
			}
			cells = temp;
		}

		/// <summary>
		/// Helper method for <see cref="Utils.Data.Grid.Trim()"/>.
		/// </summary>
		/// <returns><c>true</c> if the row or column at the specified index is not empty; otherwise, <c>false</c>.</returns>
		/// <param name="row">If set to <c>true</c> type is a row; otherwise type is column</param>
		/// <param name="index">The index.</param>
		private bool IsNotEmpty(bool row, int index) {
			for (int i = 0; (row) ? i < Rows : i < Columns; i++) {
				if (cells[row ? index : i, row ? i : index] != null) return true;
			}
			return false;
		}

		/// <summary>
		/// Flips the grid horizontally and/or vertically.
		/// </summary>
		/// <param name="horizontal">If set to <c>true</c> flips the grid horizontally.</param>
		/// <param name="vertical">If set to <c>true</c> flips the grid vertically.</param>
		public void Flip(bool horizontal, bool vertical) {
			T[,] temp = new T[Columns, Rows];
			for (int column = 0; column < Columns; column++) {
				for (int row = 0; row < Rows; row++) {
					temp[column, row] = cells[(horizontal) ? Columns - column - 1 : column, (vertical) ? Rows - row - 1 : row];
				}
			}
			cells = temp;
		}

		/// <summary>
		/// Rotates the grid by the specified amount.
		/// Negative values mean CCW. Positive values mean CW.
		/// One unit of amount is 90 degrees.
		/// </summary>
		/// <param name="amount">The amount to rotate by.</param>
		public void Rotate(int amount) {
			while (amount < 0) amount += 4;
			while (amount > 3) amount -= 4;
			if (amount == 0) return;

			T[,] temp;
			if (amount % 2 == 0) temp = new T[Columns, Rows];
			else temp = new T[Rows, Columns];

			for (int column = 0; column < Columns; column++) {
				for (int row = 0; row < Rows; row++) {
					if (amount == 1) temp[Rows - row - 1, column] = cells[column, row];					// 90 degrees
					if (amount == 2) temp[Columns - column - 1, Rows - row - 1] = cells[column, row];	// 180 degrees
					if (amount == 3) temp[row, Columns - column - 1] = cells[column, row];				// 270 degrees
				}
			}

			cells = temp;
		}
	}

	/// <summary>
	/// Data representation of a grid position.
	/// Can be cast from and to Vector2 and Vector3.
	/// Vector3 looses its z position, you need to store it seperately.
	/// </summary>
	public struct GridPosition {

		/// <summary>
		/// The index of the column.
		/// </summary>
		public int Column;
		/// <summary>
		/// The index of the row.
		/// </summary>
		public int Row;

		/// <summary>
		/// Initializes a new instance of the <see cref="Utils.Data.GridPosition"/> struct.
		/// </summary>
		/// <param name="column">The index of the column.</param>
		/// <param name="row">The index of the row.</param>
		public GridPosition(int column, int row) {
			Column = column;
			Row = row;
		}

		/// <param name="x">The one grid position.</param>
		/// <param name="y">The other grid position.</param>
		public static bool operator ==(GridPosition x, GridPosition y) {
			return x.Column == y.Column && x.Row == y.Row;
		}

		/// <param name="x">The one grid position.</param>
		/// <param name="y">The other grid position.</param>
		public static bool operator !=(GridPosition x, GridPosition y) {
			return !(x == y);
		}

		/// <param name="x">The one grid position.</param>
		/// <param name="y">The other grid position.</param>
		public static GridPosition operator +(GridPosition x, GridPosition y) {
			return new GridPosition(x.Column + y.Column, x.Row + y.Row);
		}

		/// <param name="x">The one grid position.</param>
		/// <param name="y">The other grid position.</param>
		public static GridPosition operator -(GridPosition x, GridPosition y) {
			return new GridPosition(x.Column - y.Column, x.Row - y.Row);
		}

		/// <summary>
		/// Determines whether the specified <see cref="System.Object"/> is equal to the current <see cref="Utils.Data.GridPosition"/>.
		/// </summary>
		/// <param name="o">The <see cref="System.Object"/> to compare with the current <see cref="Utils.Data.GridPosition"/>.</param>
		/// <returns><c>true</c> if the specified <see cref="System.Object"/> is equal to the current
		/// <see cref="Utils.Data.GridPosition"/>; otherwise, <c>false</c>.</returns>
		public override bool Equals(object o) {
			try {
				return this == (GridPosition) o;
			} catch {
				return false;
			}
		}

		/// <summary>
		/// Serves as a hash function for a <see cref="Utils.Data.GridPosition"/> object.
		/// </summary>
		/// <returns>A hash code for this instance that is suitable for use in hashing algorithms and data structures such as a hash table.</returns>
		public override int GetHashCode() {
			return Column * Row + Column;
		}

		/// <param name="gridPosition">The grid position.</param>
		public static implicit operator Vector2(GridPosition gridPosition) {
			return new Vector2(gridPosition.Column, -gridPosition.Row);
		}

		/// <param name="vector">The vector.</param>
		public static implicit operator GridPosition(Vector2 vector) {
			return new GridPosition((int) vector.x, (int) -vector.y);
		}

		/// <param name="gridPosition">The grid position.</param>
		public static implicit operator Vector3(GridPosition gridPosition) {
			return new Vector3(gridPosition.Column, -gridPosition.Row);
		}

		/// <param name="vector">The vector.</param>
		public static implicit operator GridPosition(Vector3 vector) {
			return new GridPosition((int) vector.x, (int) -vector.y);
		}
	}
}