using System;
using System.Collections.Generic;
using Sandbox;

namespace RedSnail.WaterTool2;

/// <summary>
/// A lake's shore as a closed polyline, walked with the water on its left seen from above (counter-clockwise round a
/// lake, clockwise round a coast's land): its control points joined by a smooth curve (or by straight edges), sampled
/// finely, at the lake's height. Everything about a lake's outline (where a river opens into it, which stretch of shore
/// the opening replaces) is measured as a distance round this, the same way for a lake and for the sea.
/// </summary>
public sealed class LakeShore
{
	public readonly List<Vector3> Points = new();

	/// <summary>
	/// The way away from the water at every point: out of a lake, or into a coast's land.
	/// </summary>
	public readonly List<Vector3> Outwards = new();

	public readonly List<float> Distances = new();

	/// <summary>
	/// The whole way round.
	/// </summary>
	public float Length { get; private set; }

	public int Count => Points.Count;



	/// <summary>
	/// The shore of a lake, sampled every <paramref name="_Spacing"/> at most. Null for a lake with too few points.
	/// </summary>
	public static LakeShore Build(WaterLake _Lake, float _Spacing)
	{
		if (_Lake is null || !_Lake.IsValid)
			return null;

		var shore = new LakeShore();
		float spacing = MathF.Max(4.0f, _Spacing);

		// Counter-clockwise whatever way the points were laid, so the outside is always on the right.
		var control = new List<Vector3>(_Lake.Points.Count);
		bool clockwise = _Lake.SignedArea() < 0.0f;

		for (int i = 0; i < _Lake.Points.Count; i++)
			control.Add(_Lake.PointAt(clockwise ? _Lake.Points.Count - 1 - i : i));

		int count = control.Count;

		for (int i = 0; i < count; i++)
		{
			Vector3 p0 = control[(i + count - 1) % count];
			Vector3 p1 = control[i];
			Vector3 p2 = control[(i + 1) % count];
			Vector3 p3 = control[(i + 2) % count];

			float chord = p1.Distance(p2);

			if (chord < 0.01f)
				continue;

			// A curve runs a little longer than its chord.
			int steps = Math.Max(1, (int)MathF.Ceiling(chord * (_Lake.Smooth ? 1.2f : 1.0f) / spacing));

			for (int k = 0; k < steps; k++)
			{
				float t = (float)k / steps;
				Vector3 point = _Lake.Smooth ? CatmullRom(p0, p1, p2, p3, t) : Vector3.Lerp(p1, p2, t);

				shore.Add(point.WithZ(_Lake.Height));
			}
		}

		if (shore.Count < 3)
			return null;

		// A smooth shore can loop round a point laid too close to another; whatever it does, the outside stays on the
		// right of the way round.
		if (shore.SignedArea() < 0.0f)
			shore.Points.Reverse();

		// A coast's water is outside it. Walked the other way round, the water is on the left for a coast as for a lake,
		// and everything measured along the shore (openings, flares, which way a river leaves) works the same.
		if (_Lake.IsCoast)
			shore.Points.Reverse();

		shore.Finish();

		return shore;
	}



	private void Add(Vector3 _Point)
	{
		if (Points.Count > 0 && Points[^1].Distance(_Point) < 0.01f)
			return;

		Points.Add(_Point);
	}



	private float SignedArea()
	{
		float area = 0.0f;

		for (int i = 0; i < Points.Count; i++)
		{
			Vector3 a = Points[i];
			Vector3 b = Points[(i + 1) % Points.Count];

			area += a.x * b.y - b.x * a.y;
		}

		return area * 0.5f;
	}



	/// <summary>
	/// Distances round the shore, and the way away from the water at every point.
	/// </summary>
	private void Finish()
	{
		Distances.Clear();
		Outwards.Clear();

		float distance = 0.0f;

		for (int i = 0; i < Count; i++)
		{
			if (i > 0)
				distance += Points[i - 1].Distance(Points[i]);

			Distances.Add(distance);

			Vector3 tangent = (Points[(i + 1) % Count] - Points[(i + Count - 1) % Count]).WithZ(0.0f);

			Outwards.Add(WaterCurve.RightOf(tangent.IsNearZeroLength ? Vector3.Forward : tangent.Normal));
		}

		Length = distance + Points[^1].Distance(Points[0]);
	}



	/// <summary>
	/// Centripetal Catmull-Rom between p1 and p2: a smooth curve through every point that never loops or overshoots,
	/// however unevenly the points are spaced.
	/// </summary>
	private static Vector3 CatmullRom(Vector3 _P0, Vector3 _P1, Vector3 _P2, Vector3 _P3, float _T)
	{
		float t0 = 0.0f;
		float t1 = t0 + Knot(_P0, _P1);
		float t2 = t1 + Knot(_P1, _P2);
		float t3 = t2 + Knot(_P2, _P3);
		float t = MathX.Lerp(t1, t2, _T);

		Vector3 a1 = Blend(_P0, _P1, t0, t1, t);
		Vector3 a2 = Blend(_P1, _P2, t1, t2, t);
		Vector3 a3 = Blend(_P2, _P3, t2, t3, t);
		Vector3 b1 = Blend(a1, a2, t0, t2, t);
		Vector3 b2 = Blend(a2, a3, t1, t3, t);

		return Blend(b1, b2, t1, t2, t);
	}



	private static float Knot(Vector3 _A, Vector3 _B)
	{
		return MathF.Max(0.001f, MathF.Sqrt(_A.Distance(_B)));
	}



	private static Vector3 Blend(Vector3 _A, Vector3 _B, float _TA, float _TB, float _T)
	{
		float span = _TB - _TA;

		if (span < 0.000001f)
			return _A;

		return _A * ((_TB - _T) / span) + _B * ((_T - _TA) / span);
	}



	public float Wrap(float _Distance)
	{
		if (Length <= 0.0f)
			return 0.0f;

		float distance = _Distance % Length;

		return distance < 0.0f ? distance + Length : distance;
	}



	/// <summary>
	/// Where the shore is at a distance round it, which way is away from the water there, and which way the shore runs.
	/// </summary>
	public void At(float _Distance, out Vector3 _Point, out Vector3 _Outward, out Vector3 _Direction)
	{
		float distance = Wrap(_Distance);
		int index = IndexAt(distance);
		int next = (index + 1) % Count;

		float from = Distances[index];
		float to = index + 1 < Count ? Distances[next] : Length;
		float t = to > from ? Math.Clamp((distance - from) / (to - from), 0.0f, 1.0f) : 0.0f;

		_Point = Vector3.Lerp(Points[index], Points[next], t);
		_Outward = Vector3.Lerp(Outwards[index], Outwards[next], t).Normal;

		Vector3 direction = (Points[next] - Points[index]).WithZ(0.0f);
		_Direction = direction.IsNearZeroLength ? Vector3.Cross(Vector3.Up, _Outward) : direction.Normal;
	}



	/// <summary>
	/// The index of the shore point at or before a (wrapped) distance.
	/// </summary>
	private int IndexAt(float _Distance)
	{
		int low = 0;
		int high = Count - 1;

		if (_Distance >= Distances[high])
			return high;

		while (high - low > 1)
		{
			int mid = (low + high) / 2;

			if (Distances[mid] <= _Distance)
				low = mid;
			else
				high = mid;
		}

		return low;
	}



	/// <summary>
	/// The points of the shore from one distance round to another, both ends included (interpolated). A stretch that
	/// runs past the end of the loop carries on from its start.
	/// </summary>
	public List<Vector3> Between(float _From, float _To)
	{
		var run = new List<Vector3>();

		At(_From, out Vector3 start, out _, out _);
		run.Add(start);

		float from = Wrap(_From);
		float span = Wrap(_To - _From);

		if (span <= 0.01f)
			span = Length;

		int first = IndexAt(from);

		for (int step = 1; step <= Count; step++)
		{
			int index = (first + step) % Count;
			float along = Wrap(Distances[index] - from);

			if (along <= 0.01f)
				continue;

			if (along >= span - 0.01f)
				break;

			run.Add(Points[index]);
		}

		At(_To, out Vector3 end, out _, out _);
		run.Add(end);

		return run;
	}



	/// <summary>
	/// How far round the shore the point nearest another one sits, and how far from the shore that point is.
	/// </summary>
	public float NearestDistance(Vector3 _Point, out float _Offset)
	{
		float best = float.MaxValue;
		float distance = 0.0f;
		var target = new Vector2(_Point.x, _Point.y);

		for (int i = 0; i < Count; i++)
		{
			int next = (i + 1) % Count;
			var from = new Vector2(Points[i].x, Points[i].y);
			var span = new Vector2(Points[next].x, Points[next].y) - from;
			float lengthSquared = span.LengthSquared;
			float t = lengthSquared > 0.0f ? Math.Clamp(Vector2.Dot(target - from, span) / lengthSquared, 0.0f, 1.0f) : 0.0f;
			float offset = (from + span * t).Distance(target);

			if (offset >= best)
				continue;

			best = offset;
			distance = Distances[i] + MathF.Sqrt(lengthSquared) * t;
		}

		_Offset = best;

		return Wrap(distance);
	}



	public float NearestDistance(Vector3 _Point)
	{
		return NearestDistance(_Point, out _);
	}



	/// <summary>
	/// Walking round the shore from a distance (forwards, or backwards) that lies inside a region, how far round it first
	/// leaves the region: that distance, unwrapped (it can run past either end of the loop). False when the walk starts
	/// outside, or comes all the way round without leaving.
	/// </summary>
	public bool TryLeave(float _From, bool _Forward, Func<Vector3, bool> _Inside, out float _Distance)
	{
		_Distance = _From;

		if (Count < 3 || Length <= 0.0f)
			return false;

		float from = Wrap(_From);
		int index = IndexAt(from);

		At(from, out Vector3 previous, out _, out _);

		if (!_Inside(previous))
			return false;

		float previousAlong = 0.0f;

		// The first shore point the walk reaches, and how far along the shore it is.
		int current = _Forward ? (index + 1) % Count : index;
		float along = _Forward ? (index + 1 < Count ? Distances[index + 1] : Length) - from : from - Distances[index];

		for (int step = 0; step <= Count && along <= Length; step++)
		{
			Vector3 point = Points[current];

			if (!_Inside(point))
			{
				// Where between the last point inside and this one the edge is crossed.
				float inside = 0.0f;
				float outside = 1.0f;

				for (int k = 0; k < 24; k++)
				{
					float middle = (inside + outside) * 0.5f;

					if (_Inside(Vector3.Lerp(previous, point, middle)))
						inside = middle;
					else
						outside = middle;
				}

				float walked = previousAlong + (along - previousAlong) * outside;

				_Distance = _Forward ? _From + walked : _From - walked;
				return true;
			}

			previous = point;
			previousAlong = along;

			if (_Forward)
			{
				along += SegmentLength(current);
				current = (current + 1) % Count;
			}
			else
			{
				current = (current + Count - 1) % Count;
				along += SegmentLength(current);
			}
		}

		return false;
	}



	/// <summary>
	/// The length of the shore from a point to the next one round.
	/// </summary>
	private float SegmentLength(int _Index)
	{
		return _Index + 1 < Count ? Distances[_Index + 1] - Distances[_Index] : Length - Distances[_Index];
	}



	/// <summary>
	/// Whether a point (in plan) is inside the shore: in a lake's water, or on a coast's land.
	/// </summary>
	public bool Contains(Vector3 _Point)
	{
		bool inside = false;

		for (int i = 0, j = Count - 1; i < Count; j = i++)
		{
			Vector3 a = Points[i];
			Vector3 b = Points[j];

			if ((a.y > _Point.y) != (b.y > _Point.y) && _Point.x < (b.x - a.x) * (_Point.y - a.y) / (b.y - a.y) + a.x)
				inside = !inside;
		}

		return inside;
	}
}