using System;
using System.Collections.Generic;
using System.Linq;
using System.Threading.Tasks;
using Sandbox;

namespace RedSnail.WaterTool2;

public sealed partial class WaterNetwork
{
	/// <summary>
	/// Bumped whenever the way pieces are built changes, so pieces built the old way are rebuilt.
	/// </summary>
	private const int GeneratorVersion = 2;

	/// <summary>
	/// A river never gets shorter than this between whatever stops it at either end.
	/// </summary>
	private const float MinSurfaceLength = 8.0f;

	private sealed class LakeBuild
	{
		public long Signature;
		public float Depth;
		public Task<List<WaterMeshData>> Task;
	}

	/// <summary>
	/// A piece of the sea (a river mouth, a chunk of the coast zone) being built on a worker thread in the editor.
	/// </summary>
	private sealed class PieceBuild
	{
		public long Signature;
		public float Depth;
		public Task<WaterMeshData> Task;
	}

	private readonly Dictionary<WaterPieceKey, PieceBuild> m_PieceBuilds = new();
	private readonly Dictionary<WaterPieceKey, (long Signature, float Depth, Func<WaterMeshData> Build)> m_PieceQueue = new();

	/// <summary>
	/// The signatures of river mouths that couldn't be built: their blocks go back to the coast zone.
	/// </summary>
	private readonly HashSet<long> m_FailedMouths = new();

	/// <summary>
	/// Pieces whose inputs gave nothing to draw, by the signature they were built from.
	/// </summary>
	private readonly Dictionary<WaterPieceKey, long> m_EmptyPieces = new();

	private bool m_IsDirty = true;
	private Transform m_BuiltTransform;
	private long m_BuiltTransformHash;

	private readonly Dictionary<WaterPieceKey, WaterPiece> m_Pieces = new();

	/// <summary>
	/// The signature of the lake tiles in place, by lake, and the lake builds running on worker threads (with the next
	/// build of the same lake waiting for the running one to finish).
	/// </summary>
	private readonly Dictionary<int, long> m_LakeSignatures = new();
	private readonly Dictionary<int, LakeBuild> m_LakeBuilds = new();
	private readonly Dictionary<int, LakeBuildInput> m_LakeQueue = new();
	private readonly HashSet<long> m_ReportedFailures = new();

	// What the last reconcile worked out from the graph.
	private readonly Dictionary<int, RiverWidth> m_Widths = new();
	private readonly Dictionary<int, JunctionLayout> m_Junctions = new();
	private readonly Dictionary<int, (float Start, float End)> m_Trims = new();
	private readonly Dictionary<int, RiverFlow> m_Flows = new();
	private readonly Dictionary<(int RiverId, bool AtStart), RiverRow> m_EndRows = new();
	private readonly Dictionary<int, List<LakeOpening>> m_LakeOpenings = new();

	/// <summary>
	/// Every piece of water currently built.
	/// </summary>
	internal IReadOnlyCollection<WaterPiece> Pieces => m_Pieces.Values;

	/// <summary>
	/// True while lakes are still being built in the background.
	/// </summary>
	public bool IsRebuilding => m_LakeBuilds.Count > 0;

	/// <summary>
	/// Bumped every time a piece is added, replaced or removed.
	/// </summary>
	public int PieceRevision { get; private set; }



	/// <summary>
	/// Asks for a reconcile pass on the next update: the graph is compared against the pieces that exist and only what
	/// differs is rebuilt.
	/// </summary>
	public void MarkDirty()
	{
		m_IsDirty = true;

		// Undo, reloads and the inspector all land here with a graph nobody told us about piece by piece.
		InvalidateIndex();
	}



	/// <summary>
	/// Throws every piece away and builds the whole network again.
	/// </summary>
	[Button("Rebuild All", "refresh")]
	public void RebuildAll()
	{
		ReleasePieces();
		MarkDirty();
	}



	/// <summary>
	/// One reconcile pass when something changed, then whatever lake builds have finished. Driven from the component's
	/// own update.
	/// </summary>
	private void Tick()
	{
		// Moving the network's GameObject moves all of its water.
		if (!m_IsDirty && TransformHash(WorldTransform) != m_BuiltTransformHash)
			m_IsDirty = true;

		if (m_IsDirty)
		{
			m_IsDirty = false;
			Reconcile();
		}

		PollLakeBuilds();
		PollPieceBuilds();
	}



	/// <summary>
	/// Works out everything the pieces are built from, then rebuilds every piece whose inputs changed and drops the ones
	/// nothing asks for any more. Stateless on purpose: it copes with undo, reloads and hot reloads alike, because every
	/// piece carries the signature of what it was built from.
	/// </summary>
	private void Reconcile()
	{
		m_BuiltTransform = WorldTransform;
		m_BuiltTransformHash = TransformHash(m_BuiltTransform);

		PruneCurveTables();
		PruneShores();

		// The coast lies at sea level, wherever it has been moved to since; a lake's openings (the coast's too) belong to
		// its shore, wherever the lake has been moved to since.
		SyncCoasts();
		SnapAllOpenings();

		ComputeWidths();
		ComputeJunctions();
		ComputeTrims();
		ComputeFlows();
		ComputeEndRows();
		ComputeLakeOpenings();
		ComputeMouths();

		var wanted = new HashSet<WaterPieceKey>();

		ReconcileRivers(wanted, m_BuiltTransformHash);
		ReconcileJunctions(wanted, m_BuiltTransformHash);

		// The river mouths before the coast zone: a mouth that can't be built gives its block back to the zone.
		ReconcileMouths(wanted, m_BuiltTransformHash);
		UpdateCoastZone(m_BuiltTransformHash);
		ReconcileCoast(wanted);

		ReconcileLakes(m_BuiltTransformHash);

		foreach (var key in m_Pieces.Keys.ToList())
		{
			if (wanted.Contains(key))
				continue;

			// A lake looks after its own tiles: a finished build replaces them all at once, whenever it lands (straight
			// away in a game, later in the editor), and they only go here once the lake itself is gone.
			if (key.Kind == WaterPieceKind.Lake && FindLake(key.Owner) is not null)
				continue;

			m_Pieces[key].Release();
			m_Pieces.Remove(key);
			PieceRevision++;
		}

		foreach (var key in m_EmptyPieces.Keys.ToList())
		{
			if (!wanted.Contains(key))
				m_EmptyPieces.Remove(key);
		}

		foreach (int lakeId in m_LakeSignatures.Keys.ToList())
		{
			if (FindLake(lakeId) is null)
				m_LakeSignatures.Remove(lakeId);
		}
	}



	/// <summary>
	/// Whether a piece is built from these inputs already: there, or known to come out empty (a chunk of the coast zone
	/// that is all land), which is not built again and again.
	/// </summary>
	private bool IsBuilt(WaterPieceKey _Key, long _Signature)
	{
		if (m_Pieces.TryGetValue(_Key, out var piece) && piece.Signature == _Signature)
			return true;

		return m_EmptyPieces.TryGetValue(_Key, out long empty) && empty == _Signature;
	}



	private void PruneShores()
	{
		var live = new HashSet<int>(Lakes.Select(lake => lake.Id));

		foreach (int id in m_Shores.Keys.Where(id => !live.Contains(id)).ToList())
			m_Shores.Remove(id);
	}



	/// <summary>
	/// The width profile of every river. Where a river simply bends on into the next, both share one width at the node
	/// (the average of what each asks for), so the row they share fits both.
	/// </summary>
	private void ComputeWidths()
	{
		m_Widths.Clear();

		foreach (var river in Rivers)
		{
			var table = GetCurveTable(river);

			if (table is null)
				continue;

			m_Widths[river.Id] = new RiverWidth(SharedWidth(river, river.StartNodeId), SharedWidth(river, river.EndNodeId), table.Length);
		}
	}



	private float SharedWidth(WaterRiver _River, int _NodeId)
	{
		float own = _River.WidthAt(_NodeId);
		var rivers = GetRiversAt(_NodeId);

		if (rivers.Count != 2 || LakeAtOpening(_NodeId) is not null)
			return own;

		var other = rivers[0] == _River ? rivers[1] : rivers[0];

		return (own + other.WidthAt(_NodeId)) * 0.5f;
	}



	/// <summary>
	/// Lays out every confluence. A river too short for the fillets at both its ends gets those fillets shrunk until they
	/// fit on it; only corners that cannot fit even sharp are clamped.
	/// </summary>
	private void ComputeJunctions()
	{
		m_Junctions.Clear();

		var radii = new Dictionary<int, float>();

		foreach (var node in Nodes)
			radii[node.Id] = MathF.Max(0.0f, node.CornerRadius);

		var layouts = BuildJunctions(radii);
		var shrink = new Dictionary<int, float>();

		foreach (var river in Rivers)
		{
			var table = GetCurveTable(river);

			if (table is null)
				continue;

			var startArm = layouts.GetValueOrDefault(river.StartNodeId)?.FindArm(river.Id);
			var endArm = layouts.GetValueOrDefault(river.EndNodeId)?.FindArm(river.Id);
			float sharp = (startArm?.SharpTrim ?? 0.0f) + (endArm?.SharpTrim ?? 0.0f);
			float fillet = (startArm is null ? 0.0f : startArm.RawTrim - startArm.SharpTrim) + (endArm is null ? 0.0f : endArm.RawTrim - endArm.SharpTrim);
			float available = MathF.Max(0.0f, table.Length - MinSurfaceLength - EndTrimAt(river.StartNodeId) - EndTrimAt(river.EndNodeId));

			if (fillet <= 0.0f || sharp + fillet <= available)
				continue;

			// The fillet's share of a trim is proportional to the radius, so this factor makes it fit exactly.
			float factor = Math.Clamp((available - sharp) / fillet, 0.0f, 1.0f);

			foreach (int nodeId in new[] { river.StartNodeId, river.EndNodeId })
			{
				if (layouts.ContainsKey(nodeId))
					shrink[nodeId] = MathF.Min(shrink.GetValueOrDefault(nodeId, 1.0f), factor);
			}
		}

		if (shrink.Count > 0)
		{
			foreach (var (nodeId, factor) in shrink)
				radii[nodeId] *= factor;

			layouts = BuildJunctions(radii);
		}

		foreach (var (nodeId, layout) in layouts)
			m_Junctions[nodeId] = layout;
	}



	private Dictionary<int, JunctionLayout> BuildJunctions(Dictionary<int, float> _Radii)
	{
		var layouts = new Dictionary<int, JunctionLayout>();

		foreach (var node in Nodes)
		{
			if (GetDegree(node.Id) < 2 || LakeAtOpening(node.Id) is not null)
				continue;

			var layout = JunctionLayout.Create(this, node, _Radii.GetValueOrDefault(node.Id), m_Widths);

			if (layout is not null)
				layouts[node.Id] = layout;
		}

		return layouts;
	}



	/// <summary>
	/// How far a river is held back at a node it ends at where something else takes over: a lake's flares, or an
	/// estuary's where it opens into the sea.
	/// </summary>
	private float EndTrimAt(int _NodeId)
	{
		return LakeTrimAt(_NodeId);
	}



	/// <summary>
	/// How far each river is held back at each end: past its confluence's corners, or past the flares of the lake it
	/// opens into, or of its estuary. A river too short for both is shared out, and the confluence takes the same
	/// numbers so the outline still lands on the river's rows.
	/// </summary>
	private void ComputeTrims()
	{
		m_Trims.Clear();

		foreach (var river in Rivers)
		{
			var table = GetCurveTable(river);

			if (table is null || !m_Widths.ContainsKey(river.Id))
				continue;

			var startArm = m_Junctions.GetValueOrDefault(river.StartNodeId)?.FindArm(river.Id);
			var endArm = m_Junctions.GetValueOrDefault(river.EndNodeId)?.FindArm(river.Id);

			float start = MathF.Max(startArm?.Trim ?? 0.0f, EndTrimAt(river.StartNodeId));
			float end = MathF.Max(endArm?.Trim ?? 0.0f, EndTrimAt(river.EndNodeId));
			float available = MathF.Max(0.0f, table.Length - MinSurfaceLength);

			if (start + end > available && start + end > 0.0f)
			{
				float scale = available / (start + end);

				start *= scale;
				end *= scale;
			}

			if (startArm is not null)
				startArm.Trim = start;

			if (endArm is not null)
				endArm.Trim = end;

			m_Trims[river.Id] = (start, end);
		}
	}



	/// <summary>
	/// How fast the water runs everywhere, worked out downstream: a river nothing flows into starts at its own speed,
	/// a river below a confluence starts with the speeds flowing into it (weighted by how wide each is), and along
	/// every river the water speeds up on slopes and settles back to the river's own speed on the flat.
	/// </summary>
	private void ComputeFlows()
	{
		m_Flows.Clear();

		var incoming = new Dictionary<int, List<WaterRiver>>();
		var outgoing = new Dictionary<int, List<WaterRiver>>();

		foreach (var river in Rivers)
		{
			if (!m_Widths.ContainsKey(river.Id))
				continue;

			GetList(incoming, river.EndNodeId).Add(river);
			GetList(outgoing, river.StartNodeId).Add(river);
		}

		var pending = new Dictionary<int, int>();
		var queue = new Queue<WaterRiver>();
		var endSpeeds = new Dictionary<int, float>();

		foreach (var river in Rivers)
		{
			if (!m_Widths.ContainsKey(river.Id))
				continue;

			int feeding = incoming.TryGetValue(river.StartNodeId, out var list) ? list.Count : 0;
			pending[river.Id] = feeding;

			if (feeding == 0)
				queue.Enqueue(river);
		}

		while (queue.Count > 0)
		{
			var river = queue.Dequeue();
			var flow = SolveFlow(river, StartSpeed(river, incoming, endSpeeds));

			endSpeeds[river.Id] = flow.Speeds[^1];

			if (!outgoing.TryGetValue(river.EndNodeId, out var below))
				continue;

			foreach (var next in below)
			{
				if (pending.ContainsKey(next.Id) && --pending[next.Id] == 0)
					queue.Enqueue(next);
			}
		}

		// Rivers flowing round in a loop never come up: they start from their own speed.
		foreach (var river in Rivers)
		{
			if (m_Widths.ContainsKey(river.Id) && !m_Flows.ContainsKey(river.Id))
				SolveFlow(river, river.Speed);
		}
	}



	private static List<WaterRiver> GetList(Dictionary<int, List<WaterRiver>> _Map, int _Key)
	{
		if (!_Map.TryGetValue(_Key, out var list))
		{
			list = new List<WaterRiver>();
			_Map[_Key] = list;
		}

		return list;
	}



	private float StartSpeed(WaterRiver _River, Dictionary<int, List<WaterRiver>> _Incoming, Dictionary<int, float> _EndSpeeds)
	{
		if (!_Incoming.TryGetValue(_River.StartNodeId, out var feeding) || feeding.Count == 0)
			return _River.Speed;

		float sum = 0.0f;
		float weight = 0.0f;

		foreach (var upstream in feeding)
		{
			if (!_EndSpeeds.TryGetValue(upstream.Id, out float speed))
				continue;

			float width = m_Widths[upstream.Id].End;

			sum += speed * width;
			weight += width;
		}

		return weight > 0.0f ? sum / weight : _River.Speed;
	}



	private RiverFlow SolveFlow(WaterRiver _River, float _StartSpeed)
	{
		var table = GetCurveTable(_River);
		var width = m_Widths[_River.Id];
		var trims = m_Trims.GetValueOrDefault(_River.Id);

		float length = table.Length;
		int count = Math.Max(2, (int)MathF.Ceiling(length / MathF.Max(16.0f, CellSize)) + 1);
		float step = length / (count - 1);
		var speeds = new float[count];

		float speed = MathF.Min(_StartSpeed, MaxSpeed);
		float previousHeight = table.PositionAt(0.0f).z;
		float settle = MathF.Exp(-step / SpeedSmoothing);

		speeds[0] = RiverFlow.Quantize(speed);

		for (int i = 1; i < count; i++)
		{
			float height = table.PositionAt(i * step).z;
			float drop = (previousHeight - height) / MathF.Max(0.001f, step);
			float target = MathF.Min(_River.Speed * Math.Clamp(1.0f + SlopeSpeedup * drop, 0.25f, 8.0f), MaxSpeed);

			speed = target + (speed - target) * settle;
			speeds[i] = RiverFlow.Quantize(speed);
			previousHeight = height;
		}

		var flow = new RiverFlow
		{
			Length = length,
			Step = step,
			Speeds = speeds,
			TrimStart = trims.Start,
			TrimEnd = trims.End,
			Waves = _River.Waves,
			WavesStart = WaveTarget(_River, _River.StartNodeId),
			WavesEnd = WaveTarget(_River, _River.EndNodeId),
			BlendStart = WaveBlend * width.Start,
			BlendEnd = WaveBlend * width.End
		};

		m_Flows[_River.Id] = flow;

		return flow;
	}



	/// <summary>
	/// The wave strength a river has to arrive at on its row at a node: the lake's when it opens into one, halfway to
	/// the next river's when it bends on into it, its own otherwise (a confluence blends its arms itself, an estuary
	/// hands it over to the sea's).
	/// </summary>
	private float WaveTarget(WaterRiver _River, int _NodeId)
	{
		if (LakeAtOpening(_NodeId) is { IsCoast: false } lake)
			return lake.Waves;

		if (IsSmoothBend(_NodeId))
		{
			var rivers = GetRiversAt(_NodeId);
			var other = rivers[0] == _River ? rivers[1] : rivers[0];

			return (_River.Waves + other.Waves) * 0.5f;
		}

		return _River.Waves;
	}



	/// <summary>
	/// A node a river simply bends on through: two rivers, no confluence to fill between them, no lake.
	/// </summary>
	private bool IsSmoothBend(int _NodeId)
	{
		return GetDegree(_NodeId) == 2 && !m_Junctions.ContainsKey(_NodeId) && LakeAtOpening(_NodeId) is null;
	}



	/// <summary>
	/// The row each river starts and ends on, worked out once and handed to both pieces that share it. At a bend the
	/// two rivers share a single row, laid square to the way the water runs through the node.
	/// </summary>
	private void ComputeEndRows()
	{
		m_EndRows.Clear();

		var bendRows = new Dictionary<int, RiverRow>();

		foreach (var river in Rivers)
		{
			if (!m_Flows.ContainsKey(river.Id))
				continue;

			m_EndRows[(river.Id, true)] = EndRow(river, true, bendRows);
			m_EndRows[(river.Id, false)] = EndRow(river, false, bendRows);
		}
	}



	private RiverRow EndRow(WaterRiver _River, bool _AtStart, Dictionary<int, RiverRow> _BendRows)
	{
		var table = GetCurveTable(_River);
		var width = m_Widths[_River.Id];
		var flow = m_Flows[_River.Id];
		var trims = m_Trims.GetValueOrDefault(_River.Id);

		int nodeId = _AtStart ? _River.StartNodeId : _River.EndNodeId;
		float trim = _AtStart ? trims.Start : trims.End;
		float distance = _AtStart ? trim : table.Length - trim;

		if (trim <= 0.0f && IsSmoothBend(nodeId))
		{
			if (!_BendRows.TryGetValue(nodeId, out var shared))
			{
				shared = BuildBendRow(nodeId);
				_BendRows[nodeId] = shared;
			}

			if (shared is not null)
				return OrientRow(shared, table, distance);
		}

		return RiverBuilder.BuildRow(table, width, flow, distance, CellSize, BankDrag, FoamFor);
	}



	/// <summary>
	/// The row two rivers share at a bend: square to the average of the way the two run through the node, as wide as
	/// both are there, carrying the average of their water.
	/// </summary>
	private RiverRow BuildBendRow(int _NodeId)
	{
		var node = FindNode(_NodeId);
		var rivers = GetRiversAt(_NodeId);

		if (node is null || rivers.Count != 2)
			return null;

		var a = rivers[0];
		var b = rivers[1];
		var tableA = GetCurveTable(a);
		var tableB = GetCurveTable(b);

		if (tableA is null || tableB is null || !m_Flows.TryGetValue(a.Id, out var flowA) || !m_Flows.TryGetValue(b.Id, out var flowB))
			return null;

		bool startA = a.StartNodeId == _NodeId;
		bool startB = b.StartNodeId == _NodeId;
		float distanceA = startA ? 0.0f : tableA.Length;
		float distanceB = startB ? 0.0f : tableB.Length;

		// The way each river runs downstream at the node, and the way each leaves the node.
		Vector3 downstreamA = Flat(tableA.TangentAt(distanceA));
		Vector3 downstreamB = Flat(tableB.TangentAt(distanceB));
		Vector3 leavingA = startA ? downstreamA : -downstreamA;
		Vector3 leavingB = startB ? downstreamB : -downstreamB;

		Vector3 axis = leavingA - leavingB;
		axis = axis.IsNearZeroLength ? leavingA : axis.Normal;

		Vector3 right = WaterCurve.RightOf(axis);
		float half = m_Widths[a.Id].HalfAt(distanceA);
		int count = RiverRow.ColumnCount(half * 2.0f, CellSize);

		float speedA = flowA.SpeedAt(distanceA);
		float speedB = flowB.SpeedAt(distanceB);
		float waves = (flowA.WavesAt(distanceA) + flowB.WavesAt(distanceB)) * 0.5f;
		float foam = FoamFor((speedA + speedB) * 0.5f);

		var row = new RiverRow(count);

		for (int i = 0; i < count; i++)
		{
			float across = RiverRow.Across(i, count);
			float bank = RiverBuilder.BankFactor(across, BankDrag);
			Vector3 velocity = (downstreamA * speedA + downstreamB * speedB) * (0.5f * bank);

			row.Points[i] = node.Position + right * (-half + 2.0f * half * across);
			row.Velocities[i] = new Vector2(velocity.x, velocity.y);
			row.Waves[i] = waves;
			row.Foams[i] = foam;
		}

		return row;
	}



	/// <summary>
	/// A shared row as one of its rivers sees it: left bank first looking down that river.
	/// </summary>
	private static RiverRow OrientRow(RiverRow _Row, WaterCurveTable _Table, float _Distance)
	{
		Vector3 right = WaterCurve.RightOf(_Table.TangentAt(_Distance));
		Vector3 across = _Row.Points[^1] - _Row.Points[0];

		var row = Vector3.Dot(right, across) >= 0.0f ? _Row.Clone() : _Row.Reversed();
		row.Distance = _Distance;

		return row;
	}



	private static Vector3 Flat(Vector3 _Direction)
	{
		Vector3 flat = _Direction.WithZ(0.0f);

		return flat.IsNearZeroLength ? Vector3.Forward : flat.Normal;
	}



	/// <summary>
	/// Where every river meets every lake: the opening's place round the shore, and the river's row there in the order
	/// the shore runs. Openings that would overlap the one before them round the shore are left out.
	/// </summary>
	private void ComputeLakeOpenings()
	{
		m_LakeOpenings.Clear();

		foreach (var lake in Lakes)
		{
			var openings = new List<LakeOpening>();
			var shore = GetShore(lake);

			m_LakeOpenings[lake.Id] = openings;

			if (shore is null)
				continue;

			foreach (int nodeId in lake.Openings)
			{
				var node = FindNode(nodeId);
				var rivers = GetRiversAt(nodeId);

				if (node is null || rivers.Count != 1)
					continue;

				var river = rivers[0];
				bool inflow = river.EndNodeId == nodeId;

				if (!m_EndRows.TryGetValue((river.Id, !inflow), out var row) || row is null || row.Count < 2)
					continue;

				var table = GetCurveTable(river);
				var trims = m_Trims.GetValueOrDefault(river.Id);

				float at = shore.NearestDistance(node.Position);
				shore.At(at, out _, out Vector3 outward, out Vector3 direction);

				// The row in the order the shore runs.
				var ordered = Vector3.Dot(row.Points[^1] - row.Points[0], direction) >= 0.0f ? row : row.Reversed();

				// The way the river heads away from the lake at its row.
				Vector3 tangent = table.TangentAt(row.Distance);
				Vector3 away = (inflow ? -tangent : tangent).WithZ(0.0f);

				openings.Add(new LakeOpening
				{
					NodeId = nodeId,
					River = river,
					Inflow = inflow,
					At = at,
					HalfWidth = row.HalfWidth,
					Flare = inflow ? trims.End : trims.Start,
					Row = ordered,
					Away = away.IsNearZeroLength ? outward : away.Normal
				});
			}

			openings.Sort((x, y) => x.At.CompareTo(y.At));

			// Two openings fighting over the same stretch of shore: the later one round the shore is left out.
			for (int i = openings.Count - 1; i >= 1 && openings.Count > 1; i--)
			{
				var current = openings[i];
				var previous = openings[i - 1];

				if (current.At - current.Reach < previous.At + previous.Reach)
					openings.RemoveAt(i);
			}

			if (openings.Count > 1)
			{
				var last = openings[^1];
				var first = openings[0];

				if (last.At + last.Reach > shore.Length + first.At - first.Reach)
					openings.RemoveAt(openings.Count - 1);
			}
		}
	}



	private static long TransformHash(in Transform _Transform)
	{
		var hash = StableHash.Create();

		hash.Add(_Transform.Position);
		hash.Add(_Transform.Rotation.Forward);
		hash.Add(_Transform.Rotation.Up);
		hash.Add(_Transform.Scale);

		return hash.Value;
	}



	/// <summary>
	/// Rebuilds every stretch of river whose inputs changed. A river is cut into stretches of about the chunk length,
	/// each with rows every cell; a stretch's end rows are worked out the same way by both stretches that share them, and
	/// a river's very first and last rows are the shared rows of whatever it meets.
	/// </summary>
	private void ReconcileRivers(HashSet<WaterPieceKey> _Wanted, long _TransformHash)
	{
		foreach (var river in Rivers)
		{
			if (!m_Flows.TryGetValue(river.Id, out var flow) || !m_Widths.TryGetValue(river.Id, out var width))
				continue;

			var table = GetCurveTable(river);
			var trims = m_Trims.GetValueOrDefault(river.Id);

			float start = trims.Start;
			float end = table.Length - trims.End;

			if (end - start < 1.0f)
				continue;

			var startRow = m_EndRows[(river.Id, true)];
			var endRow = m_EndRows[(river.Id, false)];

			int chunks = Math.Max(1, (int)MathF.Ceiling((end - start) / MathF.Max(CellSize * 4.0f, ChunkLength)));

			for (int k = 0; k < chunks; k++)
			{
				float from = k == 0 ? start : start + (end - start) * k / chunks;
				float to = k == chunks - 1 ? end : start + (end - start) * (k + 1) / chunks;

				var key = new WaterPieceKey(WaterPieceKind.River, river.Id, k);
				_Wanted.Add(key);

				var hash = StableHash.Create();

				hash.Add(GeneratorVersion);
				hash.Add((int)WaterPieceKind.River);
				hash.Add(_TransformHash);
				hash.Add(CellSize);
				hash.Add(BankDrag);
				hash.Add(FoamAmount);
				hash.Add(FoamStartSpeed);
				hash.Add(FoamFullSpeed);
				hash.Add(table.Curve.P0);
				hash.Add(table.Curve.P1);
				hash.Add(table.Curve.P2);
				hash.Add(table.Curve.P3);
				width.AddToHash(ref hash);
				hash.Add(from);
				hash.Add(to);
				flow.AddToHash(ref hash, from, to);

				if (k == 0)
					startRow.AddToHash(ref hash);

				if (k == chunks - 1)
					endRow.AddToHash(ref hash);

				if (IsBuilt(key, hash.Value))
					continue;

				var rows = new List<RiverRow>();

				foreach (float distance in EvenRows(from, to, CellSize))
				{
					if (k == 0 && distance == from)
						rows.Add(startRow);
					else if (k == chunks - 1 && distance == to)
						rows.Add(endRow);
					else
						rows.Add(RiverBuilder.BuildRow(table, width, flow, distance, CellSize, BankDrag, FoamFor));
				}

				SetPiece(key, hash.Value, RiverBuilder.Build(rows, m_BuiltTransform), river.Depth);
			}
		}
	}



	/// <summary>
	/// Rows every spacing along a stretch, its exact ends included.
	/// </summary>
	private static List<float> EvenRows(float _Start, float _End, float _Spacing)
	{
		float length = MathF.Max(0.0f, _End - _Start);
		int steps = Math.Max(1, (int)MathF.Ceiling(length / MathF.Max(1.0f, _Spacing)));
		var rows = new List<float>(steps + 1);

		for (int i = 0; i <= steps; i++)
			rows.Add(i == steps ? _End : _Start + length * i / steps);

		return rows;
	}



	/// <summary>
	/// Rebuilds every confluence whose outline changed (an outline holds the rows of every river at it, so it changes
	/// whenever any of them does).
	/// </summary>
	private void ReconcileJunctions(HashSet<WaterPieceKey> _Wanted, long _TransformHash)
	{
		foreach (var (nodeId, layout) in m_Junctions)
		{
			var node = FindNode(nodeId);

			if (node is null)
				continue;

			var outline = layout.BuildOutline(arm => m_EndRows.GetValueOrDefault((arm.River.Id, arm.AtStart)), 0);

			if (outline is null || outline.Count < 3)
				continue;

			var key = new WaterPieceKey(WaterPieceKind.Junction, nodeId, 0);
			_Wanted.Add(key);

			var hash = StableHash.Create();

			hash.Add(GeneratorVersion);
			hash.Add((int)WaterPieceKind.Junction);
			hash.Add(_TransformHash);
			hash.Add(CellSize);
			AddOutlineToHash(ref hash, outline);

			if (IsBuilt(key, hash.Value))
				continue;

			float depth = layout.Arms.Max(arm => arm.River.Depth);

			SetPiece(key, hash.Value, JunctionBuilder.Build(outline, node.Position, CellSize, m_BuiltTransform), depth);
		}
	}



	private static void AddOutlineToHash(ref StableHash _Hash, List<OutlineVertex> _Outline)
	{
		_Hash.Add(_Outline.Count);

		foreach (var vertex in _Outline)
		{
			_Hash.Add(vertex.Position);
			_Hash.Add(vertex.Row);
			_Hash.Add(vertex.Velocity);
			_Hash.Add(vertex.Waves);
			_Hash.Add(vertex.Foam);
		}
	}



	/// <summary>
	/// Starts a build for every lake whose outline, openings or settings changed. In the editor lakes are built on a
	/// worker thread (a big lake takes a moment), keeping their old tiles until the new ones are ready; in a game they
	/// are built straight away, so they are there before anything floats on them.
	/// </summary>
	private void ReconcileLakes(long _TransformHash)
	{
		foreach (var lake in Lakes)
		{
			var shore = GetShore(lake);

			// A coast has no surface of its own: the sea is outside it, and its estuaries are built with the sea.
			if (shore is null || lake.IsCoast)
			{
				RemoveLakeTiles(lake.Id);
				m_LakeQueue.Remove(lake.Id);
				continue;
			}

			var openings = m_LakeOpenings.GetValueOrDefault(lake.Id) ?? new List<LakeOpening>();
			var outline = LakeOutline.Build(shore, openings, 0);
			var jets = new LakeJet[openings.Count];

			for (int i = 0; i < openings.Count; i++)
			{
				var opening = openings[i];
				var row = opening.Row;
				Vector3 inward = -opening.Away;

				jets[i] = new LakeJet(new Vector2(row.Centre.x, row.Centre.y), new Vector2(inward.x, inward.y).Normal, row.HalfWidth, row.MeanVelocity, row.MeanFoam, PlumeLength * row.HalfWidth * 2.0f);
			}

			var hash = StableHash.Create();

			hash.Add(GeneratorVersion);
			hash.Add((int)WaterPieceKind.Lake);
			hash.Add(_TransformHash);
			hash.Add(CellSize);
			hash.Add(LakeTileSize);
			hash.Add(PlumeLength);
			lake.AddToHash(ref hash);
			AddOutlineToHash(ref hash, outline);

			long signature = hash.Value;

			if (m_LakeSignatures.TryGetValue(lake.Id, out long current) && current == signature)
			{
				m_LakeQueue.Remove(lake.Id);
				continue;
			}

			var input = new LakeBuildInput
			{
				LakeId = lake.Id,
				Signature = signature,
				Outline = outline,
				Jets = jets,
				Height = lake.Height,
				Waves = lake.Waves,
				CellSize = CellSize,
				TileSize = LakeTileSize,
				Transform = m_BuiltTransform
			};

			if (!Scene.IsEditor)
			{
				ApplyLake(lake.Id, signature, LakeBuilder.Build(input), lake.Depth);
				continue;
			}

			if (m_LakeBuilds.TryGetValue(lake.Id, out var running))
			{
				// One build at a time per lake: the newest inputs wait for the running one to finish.
				if (running.Signature != signature)
					m_LakeQueue[lake.Id] = input;
				else
					m_LakeQueue.Remove(lake.Id);

				continue;
			}

			StartLakeBuild(input, lake.Depth);
		}
	}



	private void StartLakeBuild(LakeBuildInput _Input, float _Depth)
	{
		m_LakeBuilds[_Input.LakeId] = new LakeBuild
		{
			Signature = _Input.Signature,
			Depth = _Depth,
			Task = GameTask.RunInThreadAsync(() => LakeBuilder.Build(_Input))
		};
	}



	/// <summary>
	/// Puts the tiles of every finished lake build in place, and starts whatever build was waiting behind it.
	/// </summary>
	private void PollLakeBuilds()
	{
		if (m_LakeBuilds.Count == 0)
			return;

		foreach (var (lakeId, build) in m_LakeBuilds.ToList())
		{
			if (!build.Task.IsCompleted)
				continue;

			m_LakeBuilds.Remove(lakeId);

			var lake = FindLake(lakeId);

			if (build.Task.IsFaulted)
				Log.Warning($"[WaterTool2] Building lake #{lakeId} failed: {build.Task.Exception?.InnerException?.Message}");
			else if (lake is not null)
				ApplyLake(lakeId, build.Signature, build.Task.Result, lake.Depth);

			if (lake is not null && m_LakeQueue.Remove(lakeId, out var next))
				StartLakeBuild(next, lake.Depth);

			// The graph may have moved on while the lake was building (and back again): check it against the result.
			m_IsDirty = true;
		}
	}



	/// <summary>
	/// Replaces a lake's tiles with freshly built ones. A null build is a shore that crosses itself: the lake is left
	/// empty, with a warning, until it is fixed.
	/// </summary>
	private void ApplyLake(int _LakeId, long _Signature, List<WaterMeshData> _Tiles, float _Depth)
	{
		RemoveLakeTiles(_LakeId);

		m_LakeSignatures[_LakeId] = _Signature;

		if (_Tiles is null)
		{
			if (m_ReportedFailures.Add(_Signature))
				Log.Warning($"[WaterTool2] Lake #{_LakeId} can't be built: its shore crosses itself, or a river opening into it folds back over it.");

			return;
		}

		for (int i = 0; i < _Tiles.Count; i++)
			SetPiece(new WaterPieceKey(WaterPieceKind.Lake, _LakeId, i), _Signature, _Tiles[i], _Depth);
	}



	private void RemoveLakeTiles(int _LakeId)
	{
		foreach (var key in m_Pieces.Keys.Where(key => key.Kind == WaterPieceKind.Lake && key.Owner == _LakeId).ToList())
		{
			m_Pieces[key].Release();
			m_Pieces.Remove(key);
			PieceRevision++;
		}
	}



	private void SetPiece(WaterPieceKey _Key, long _Signature, WaterMeshData _Mesh, float _Depth)
	{
		if (m_Pieces.TryGetValue(_Key, out var old))
			old.Release();

		if (_Mesh is null || _Mesh.VertexCount == 0)
		{
			m_Pieces.Remove(_Key);
			m_EmptyPieces[_Key] = _Signature;
			PieceRevision++;
			return;
		}

		var piece = new WaterPiece(_Key, _Signature, _Mesh, _Depth);

		if (!Application.IsHeadless)
			piece.Upload();

		m_Pieces[_Key] = piece;
		m_EmptyPieces.Remove(_Key);
		PieceRevision++;
	}



	private void ReleasePieces()
	{
		foreach (var piece in m_Pieces.Values)
			piece.Release();

		m_Pieces.Clear();
		m_EmptyPieces.Clear();
		m_LakeSignatures.Clear();
		m_LakeBuilds.Clear();
		m_LakeQueue.Clear();
		m_PieceBuilds.Clear();
		m_PieceQueue.Clear();
		PieceRevision++;
	}



	/// <summary>
	/// Builds a piece of the sea: straight away in a game, so it is there before anything floats on it; in the editor on
	/// a worker thread, keeping the piece there was until the new one is ready, so dragging a river about never waits on
	/// it. One build at a time per piece: the newest inputs wait for the running one to finish. The build must only read
	/// what it was handed.
	/// </summary>
	private void BuildPiece(WaterPieceKey _Key, long _Signature, float _Depth, Func<WaterMeshData> _Build)
	{
		if (!Scene.IsEditor)
		{
			// A build that throws counts as one that gave nothing, as on a worker thread, rather than cutting the reconcile
			// short before the rest of the sea is in place.
			WaterMeshData mesh = null;

			try
			{
				mesh = _Build();
			}
			catch (Exception exception)
			{
				Log.Warning($"[WaterTool2] Building a piece of the sea failed: {exception.Message}");
			}

			ApplyPiece(_Key, _Signature, mesh, _Depth);
			return;
		}

		if (m_PieceBuilds.TryGetValue(_Key, out var running))
		{
			if (running.Signature == _Signature)
				m_PieceQueue.Remove(_Key);
			else
				m_PieceQueue[_Key] = (_Signature, _Depth, _Build);

			return;
		}

		m_PieceBuilds[_Key] = new PieceBuild { Signature = _Signature, Depth = _Depth, Task = GameTask.RunInThreadAsync(_Build) };
	}



	/// <summary>
	/// Puts every finished piece in place, and starts whatever build was waiting behind it.
	/// </summary>
	private void PollPieceBuilds()
	{
		if (m_PieceBuilds.Count == 0)
			return;

		foreach (var (key, build) in m_PieceBuilds.ToList())
		{
			if (!build.Task.IsCompleted)
				continue;

			m_PieceBuilds.Remove(key);

			// A build that threw gave nothing: recorded as such, so the same inputs aren't built again and again.
			if (build.Task.IsFaulted)
				Log.Warning($"[WaterTool2] Building a piece of the sea failed: {build.Task.Exception?.InnerException?.Message}");

			ApplyPiece(key, build.Signature, build.Task.IsFaulted ? null : build.Task.Result, build.Depth);

			if (m_PieceQueue.Remove(key, out var next))
				m_PieceBuilds[key] = new PieceBuild { Signature = next.Signature, Depth = next.Depth, Task = GameTask.RunInThreadAsync(next.Build) };

			// The graph may have moved on while it was building: check it against the result.
			m_IsDirty = true;
		}
	}



	/// <summary>
	/// A finished piece into place. A river mouth that couldn't be built is remembered, so the next reconcile hands its
	/// block back to the coast zone.
	/// </summary>
	private void ApplyPiece(WaterPieceKey _Key, long _Signature, WaterMeshData _Mesh, float _Depth)
	{
		if (_Mesh is null && _Key.Kind == WaterPieceKind.Estuary)
		{
			if (m_FailedMouths.Add(_Signature))
				Log.Warning($"[WaterTool2] The river mouth at node #{_Key.Owner} can't be built: the river or the coast folds back over it.");

			m_IsDirty = true;
		}

		SetPiece(_Key, _Signature, _Mesh, _Depth);
	}



	/// <summary>
	/// The confluence layout at a node, as the last reconcile worked it out. Editor tools draw it.
	/// </summary>
	internal JunctionLayout JunctionAt(int _NodeId)
	{
		return m_Junctions.GetValueOrDefault(_NodeId);
	}



	/// <summary>
	/// The flow worked out for a river, for overlays.
	/// </summary>
	internal RiverFlow FlowOf(int _RiverId)
	{
		return m_Flows.GetValueOrDefault(_RiverId);
	}



	/// <summary>
	/// The slowest and fastest the water runs along a river, as the last reconcile worked it out. False before the river
	/// has been worked out.
	/// </summary>
	public bool TryGetSpeedRange(int _RiverId, out float _Slowest, out float _Fastest)
	{
		_Slowest = 0.0f;
		_Fastest = 0.0f;

		if (!m_Flows.TryGetValue(_RiverId, out var flow) || flow.Speeds is null || flow.Speeds.Length == 0)
			return false;

		_Slowest = flow.Speeds.Min();
		_Fastest = flow.Speeds.Max();

		return true;
	}



	/// <summary>
	/// The openings of a lake as the last reconcile worked them out.
	/// </summary>
	internal IReadOnlyList<LakeOpening> OpeningsOf(int _LakeId)
	{
		return m_LakeOpenings.GetValueOrDefault(_LakeId);
	}
}