// Copyright (c) 2013-2015 Robert Rouhani <robert.rouhani@gmail.com> and other contributors (see CONTRIBUTORS file).
// Licensed under the MIT License - https://raw.github.com/Robmaister/SharpNav/master/LICENSE

using System;
using System.Collections.Generic;

namespace SharpNav
{
	/// <summary>
	/// Flags that can be applied to a region.
	/// </summary>
	[Flags]
	public enum RegionFlags
	{
		/// <summary>
		/// The border flag
		/// </summary>
		Border = 0x20000000,

		/// <summary>
		/// The vertex border flag
		/// </summary>
		VertexBorder = 0x40000000,

		/// <summary>
		/// The area border flag
		/// </summary>
		AreaBorder = unchecked((int)0x80000000)
	}

	/// <summary>
	/// A <see cref="RegionId"/> is an identifier with flags marking borders.
	/// </summary>
	[Serializable]
	public struct RegionId : IEquatable<RegionId>, IEquatable<int>
	{
		/// <summary>
		/// A null region is one with an ID of 0.
		/// </summary>
		public static readonly RegionId Null = new RegionId(0, 0);

		/// <summary>
		/// A bitmask 
		/// </summary>
		public const int MaskId = 0x1fffffff;

		/// <summary>
		/// The internal storage of a <see cref="RegionId"/>. The <see cref="RegionFlags"/> portion are the most
		/// significant bits, the integer identifier are the least significant bits, marked by <see cref="MaskId"/>.
		/// </summary>
		private int bits;

		/// <summary>
		/// Initializes a new instance of the <see cref="RegionId"/> struct without any flags.
		/// </summary>
		/// <param name="id">The identifier.</param>
		public RegionId(int id)
			: this(id, 0)
		{
		}

		/// <summary>
		/// Initializes a new instance of the <see cref="RegionId"/> struct.
		/// </summary>
		/// <param name="id"></param>
		/// <param name="flags"></param>
		public RegionId(int id, RegionFlags flags)
		{
			int masked = id & MaskId;

			if (masked != id)
				throw new ArgumentOutOfRangeException("id", "The provided id is outside of the valid range. The 3 most significant bits must be 0. Maybe you wanted RegionId.FromRawBits()?");

			if ((RegionFlags)((int)flags & ~MaskId) != flags)
				throw new ArgumentException("flags", "The provide region flags are invalid.");

			bits = masked | (int)flags;
		}

		/// <summary>
		/// Gets the ID of the region without any flags.
		/// </summary>
		public int Id
		{
			get
			{
				return bits & MaskId;
			}
		}

		/// <summary>
		/// Gets the flags set for this region.
		/// </summary>
		public RegionFlags Flags
		{
			get
			{
				return (RegionFlags)(bits & ~MaskId);
			}
		}

		/// <summary>
		/// Gets a value indicating whether the region is the null region (ID == 0).
		/// </summary>
		public bool IsNull
		{
			get
			{
				return (bits & MaskId) == 0;
			}
		}

		/// <summary>
		/// Creates a new <see cref="RegionId"/> from a value that contains both the region ID and the flags.
		/// </summary>
		/// <param name="bits">The int containing <see cref="RegionId"/> data.</param>
		/// <returns>A new instance of the <see cref="RegionId"/> struct with the specified data.</returns>
		public static RegionId FromRawBits(int bits)
		{
			RegionId id;
			id.bits = bits;
			return id;
		}

		/// <summary>
		/// Creates a new <see cref="RegionId"/> with extra flags.
		/// </summary>
		/// <param name="region">The region to add flags to.</param>
		/// <param name="flags">The flags to add.</param>
		/// <returns>A new instance of the <see cref="RegionId"/> struct with extra flags.</returns>
		public static RegionId WithFlags(RegionId region, RegionFlags flags)
		{
			if ((RegionFlags)((int)flags & ~MaskId) != flags)
				throw new ArgumentException("flags", "The provide region flags are invalid.");

			RegionFlags newFlags = region.Flags | flags;
			return RegionId.FromRawBits((region.bits & MaskId) | (int)newFlags);
		}

		/// <summary>
		/// Creates a new instance of the <see cref="RegionId"/> class without any flags set.
		/// </summary>
		/// <param name="region">The region to use.</param>
		/// <returns>A new instance of the <see cref="RegionId"/> struct without any flags set.</returns>
		public static RegionId WithoutFlags(RegionId region)
		{
			return new RegionId(region.Id);
		}

		/// <summary>
		/// Creates a new instance of the <see cref="RegionId"/> class without certain flags set.
		/// </summary>
		/// <param name="region">The region to use.</param>
		/// <param name="flags">The flags to unset.</param>
		/// <returns>A new instnace of the <see cref="RegionId"/> struct without certain flags set.</returns>
		public static RegionId WithoutFlags(RegionId region, RegionFlags flags)
		{
			if ((RegionFlags)((int)flags & ~MaskId) != flags)
				throw new ArgumentException("flags", "The provide region flags are invalid.");

			RegionFlags newFlags = region.Flags & ~flags;
			return RegionId.FromRawBits((region.bits & MaskId) | (int)newFlags);
		}

		/// <summary>
		/// Checks if a region has certain flags.
		/// </summary>
		/// <param name="region">The region to check.</param>
		/// <param name="flags">The flags to check.</param>
		/// <returns>A value indicating whether the region has all of the specified flags.</returns>
		public static bool HasFlags(RegionId region, RegionFlags flags)
		{
			return (region.Flags & flags) != 0;
		}

		/// <summary>
		/// Compares an instance of <see cref="RegionId"/> with an integer for equality.
		/// </summary>
		/// <remarks>
		/// This checks for both the ID and flags set on the region. If you want to only compare the IDs, use the
		/// following code:
		/// <code>
		/// RegionId left = ...;
		/// int right = ...;
		/// if (left.Id == right)
		/// {
		///    // ...
		/// }
		/// </code>
		/// </remarks>
		/// <param name="left">An instance of <see cref="RegionId"/>.</param>
		/// <param name="right">An integer.</param>
		/// <returns>A value indicating whether the two values are equal.</returns>
		public static bool operator ==(RegionId left, int right)
		{
			return left.Equals(right);
		}

		/// <summary>
		/// Compares an instance of <see cref="RegionId"/> with an integer for inequality.
		/// </summary>
		/// <remarks>
		/// This checks for both the ID and flags set on the region. If you want to only compare the IDs, use the
		/// following code:
		/// <code>
		/// RegionId left = ...;
		/// int right = ...;
		/// if (left.Id != right)
		/// {
		///    // ...
		/// }
		/// </code>
		/// </remarks>
		/// <param name="left">An instance of <see cref="RegionId"/>.</param>
		/// <param name="right">An integer.</param>
		/// <returns>A value indicating whether the two values are unequal.</returns>
		public static bool operator !=(RegionId left, int right)
		{
			return !(left == right);
		}

		/// <summary>
		/// Compares two instances of <see cref="RegionId"/> for equality.
		/// </summary>
		/// <remarks>
		/// This checks for both the ID and flags set on the regions. If you want to only compare the IDs, use the
		/// following code:
		/// <code>
		/// RegionId left = ...;
		/// RegionId right = ...;
		/// if (left.Id == right.Id)
		/// {
		///    // ...
		/// }
		/// </code>
		/// </remarks>
		/// <param name="left">An instance of <see cref="RegionId"/>.</param>
		/// <param name="right">Another instance of <see cref="RegionId"/>.</param>
		/// <returns>A value indicating whether the two instances are equal.</returns>
		public static bool operator ==(RegionId left, RegionId right)
		{
			return left.Equals(right);
		}

		/// <summary>
		/// Compares two instances of <see cref="RegionId"/> for inequality.
		/// </summary>
		/// <remarks>
		/// This checks for both the ID and flags set on the regions. If you want to only compare the IDs, use the
		/// following code:
		/// <code>
		/// RegionId left = ...;
		/// RegionId right = ...;
		/// if (left.Id != right.Id)
		/// {
		///    // ...
		/// }
		/// </code>
		/// </remarks>
		/// <param name="left">An instance of <see cref="RegionId"/>.</param>
		/// <param name="right">Another instance of <see cref="RegionId"/>.</param>
		/// <returns>A value indicating whether the two instances are unequal.</returns>
		public static bool operator !=(RegionId left, RegionId right)
		{
			return !(left == right);
		}

		/// <summary>
		/// Converts an instance of <see cref="RegionId"/> to an integer containing both the ID and the flags.
		/// </summary>
		/// <param name="id">An instance of <see cref="RegionId"/>.</param>
		/// <returns>An integer.</returns>
		public static explicit operator int(RegionId id)
		{
			return id.bits;
		}

		/// <summary>
		/// Compares this instance with another instance of <see cref="RegionId"/> for equality, including flags.
		/// </summary>
		/// <param name="other">An instance of <see cref="RegionId"/>.</param>
		/// <returns>A value indicating whether the two instances are equal.</returns>
		public bool Equals(RegionId other)
		{
			bool thisNull = this.IsNull;
			bool otherNull = other.IsNull;

			if (thisNull && otherNull)
				return true;
			else if (thisNull ^ otherNull)
				return false;
			else
				return this.bits == other.bits;
		}

		/// <summary>
		/// Compares this instance with another an intenger for equality, including flags.
		/// </summary>
		/// <param name="other">An integer.</param>
		/// <returns>A value indicating whether the two instances are equal.</returns>
		public bool Equals(int other)
		{
			RegionId otherId;
			otherId.bits = other;

			return this.Equals(otherId);
		}

		/// <summary>
		/// Compares this instance with an object for equality.
		/// </summary>
		/// <param name="obj">An object</param>
		/// <returns>A value indicating whether the two instances are equal.</returns>
		public override bool Equals(object obj)
		{
			var regObj = obj as RegionId?;
			var intObj = obj as int?;

			if (regObj.HasValue)
				return this.Equals(regObj.Value);
			else if (intObj.HasValue)
				return this.Equals(intObj.Value);
			else
				return false;
		}

		/// <summary>
		/// Gets a unique hash code for this instance.
		/// </summary>
		/// <returns>A hash code.</returns>
		public override int GetHashCode()
		{
			if (IsNull)
				return 0;

			return bits.GetHashCode();
		}

		/// <summary>
		/// Gets a human-readable version of this instance.
		/// </summary>
		/// <returns>A string representing this instance.</returns>
		public override string ToString()
		{
			return "{ Id: " + Id + ", Flags: " + Flags + "}";
		}
	}

	/// <summary>
	/// A Region contains a group of adjacent spans.
	/// </summary>
	public class Region
	{
		private int spanCount;
		private RegionId id;
		private Area areaType;
		private bool remap;
		private bool visited;
		private List<RegionId> connections;
		private List<RegionId> floors;

		/// <summary>
		/// Initializes a new instance of the <see cref="Region" /> class.
		/// </summary>
		/// <param name="idNum">The id</param>
		public Region(int idNum)
		{
			spanCount = 0;
			id = new RegionId(idNum);
			areaType = 0;
			remap = false;
			visited = false;

			connections = new List<RegionId>();
			floors = new List<RegionId>();
		}

		/// <summary>
		/// Gets or sets the number of spans
		/// </summary>
		public int SpanCount
		{
			get
			{
				return spanCount;
			}

			set
			{
				this.spanCount = value;
			}
		}

		/// <summary>
		/// Gets or sets the region id 
		/// </summary>
		public RegionId Id 
		{
			get
			{
				return id;
			}

			set
			{
				this.id = value;
			}
		}

		/// <summary>
		/// Gets or sets the AreaType of this region
		/// </summary>
		public Area AreaType
		{
			get
			{
				return areaType;
			}

			set
			{
				this.areaType = value;
			}
		}

		/// <summary>
		/// Gets or sets a value indicating whether this region has been remapped or not
		/// </summary>
		public bool Remap 
		{
			get
			{
				return remap;
			}

			set
			{
				this.remap = value;
			}
		}

		/// <summary>
		/// Gets or sets a value indicating whether this region has been visited or not
		/// </summary>
		public bool Visited
		{
			get
			{
				return visited;
			}

			set
			{
				this.visited = value;
			}
		}

		/// <summary>
		/// Gets the list of floor regions
		/// </summary>
		public List<RegionId> FloorRegions
		{
			get
			{
				return floors;
			}
		}

		/// <summary>
		/// Gets the list of connected regions
		/// </summary>
		public List<RegionId> Connections
		{
			get
			{
				return connections;
			}
		}

		/// <summary>
		/// Gets a value indicating whether the region is a border region.
		/// </summary>
		public bool IsBorder
		{
			get
			{
				return RegionId.HasFlags(id, RegionFlags.Border);
			}
		}

		/// <summary>
		/// Gets a value indicating whether the region is either a border region or the null region.
		/// </summary>
		public bool IsBorderOrNull
		{
			get
			{
				return id.IsNull || IsBorder;
			}
		}

		/// <summary>
		/// Remove adjacent connections if there is a duplicate
		/// </summary>
		public void RemoveAdjacentNeighbours()
		{
			if (connections.Count <= 1)
				return;

			// Remove adjacent duplicates.
			for (int i = 0; i < connections.Count; i++)
			{
				//get the next i
				int ni = (i + 1) % connections.Count;

				//remove duplicate if found
				if (connections[i] == connections[ni])
				{
					connections.RemoveAt(i);
					i--;
				}
			}
		}

		/// <summary>
		/// Replace all connection and floor values 
		/// </summary>
		/// <param name="oldId">The value you want to replace</param>
		/// <param name="newId">The new value that will be used</param>
		public void ReplaceNeighbour(RegionId oldId, RegionId newId)
		{
			//replace the connections
			bool neiChanged = false;
			for (int i = 0; i < connections.Count; ++i)
			{
				if (connections[i] == oldId)
				{
					connections[i] = newId;
					neiChanged = true;
				}
			}

			//replace the floors
			for (int i = 0; i < floors.Count; ++i)
			{
				if (floors[i] == oldId)
					floors[i] = newId;
			}

			//make sure to remove adjacent neighbors
			if (neiChanged)
				RemoveAdjacentNeighbours();
		}

		/// <summary>
		/// Determine whether this region can merge with another region.
		/// </summary>
		/// <param name="otherRegion">The other region to merge with</param>
		/// <returns>True if the two regions can be merged, false if otherwise</returns>
		public bool CanMergeWith(Region otherRegion)
		{
			//make sure areas are the same
			if (areaType != otherRegion.areaType)
				return false;
			
			//count the number of connections to the other region
			int n = 0;
			for (int i = 0; i < connections.Count; i++)
			{
				if (connections[i] == otherRegion.id)
						n++;
			}
		
			//make sure there's only one connection
			if (n > 1)
				return false;
		
			//make sure floors are separate
			if (floors.Contains(otherRegion.id))
				return false;

			return true;
		}

		/// <summary>
		/// Only add a floor if it hasn't been added already
		/// </summary>
		/// <param name="n">The value of the floor</param>
		public void AddUniqueFloorRegion(RegionId n)
		{
			if (!floors.Contains(n))
				floors.Add(n);
		}

		/// <summary>
		/// Merge two regions into one. Needs good testing
		/// </summary>
		/// <param name="otherRegion">The region to merge with</param>
		/// <returns>True if merged successfully, false if otherwise</returns>
		public bool MergeWithRegion(Region otherRegion)
		{
			RegionId thisId = id;
			RegionId otherId = otherRegion.id;

			// Duplicate current neighbourhood.
			List<RegionId> thisConnected = new List<RegionId>();
			for (int i = 0; i < connections.Count; ++i)
				thisConnected.Add(connections[i]);
			List<RegionId> otherConnected = otherRegion.connections;

			// Find insertion point on this region
			int insertInThis = -1;
			for (int i = 0; i < thisConnected.Count; ++i)
			{
				if (thisConnected[i] == otherId)
				{
					insertInThis = i;
					break;
				}
			}

			if (insertInThis == -1)
				return false;

			// Find insertion point on the other region
			int insertInOther = -1;
			for (int i = 0; i < otherConnected.Count; ++i)
			{
				if (otherConnected[i] == thisId)
				{
					insertInOther = i;
					break;
				}
			}

			if (insertInOther == -1)
				return false;

			// Merge neighbours.
			connections = new List<RegionId>();
			for (int i = 0, ni = thisConnected.Count; i < ni - 1; ++i)
				connections.Add(thisConnected[(insertInThis + 1 + i) % ni]);

			for (int i = 0, ni = otherConnected.Count; i < ni - 1; ++i)
				connections.Add(otherConnected[(insertInOther + 1 + i) % ni]);

			RemoveAdjacentNeighbours();

			for (int j = 0; j < otherRegion.floors.Count; ++j)
				AddUniqueFloorRegion(otherRegion.floors[j]);
			spanCount += otherRegion.spanCount;
			otherRegion.spanCount = 0;
			otherRegion.connections.Clear();

			return true;
		}

		/// <summary>
		/// Test if region is connected to a border
		/// </summary>
		/// <returns>True if connected, false if not</returns>
		public bool IsConnectedToBorder()
		{
			// Region is connected to border if
			// one of the neighbours is null id.
			for (int i = 0; i < connections.Count; ++i)
			{
				if (connections[i] == 0)
					return true;
			}

			return false;
		}
	}
}