﻿using System;
using System.Collections.Generic;
using System.Linq;
using Gamelogic;
using UnityEngine;

public static class Backtrack
{
	public static IEnumerable<T> BackTrack<T>(
		T root,
		Func<T, IEnumerable<T>> getNeighbors,
		Func<IEnumerable<T>, bool> validation)
	{
		var path = new List<T>();

		BackTrack(root, getNeighbors, validation, path, new List<T>());

		return path;
	}

	private static IEnumerable<T> BackTrack<T>(
		T node,
		Func<T, IEnumerable<T>> getNeighbors,
		Func<IEnumerable<T>, bool> isValid,
		IList<T> path,
		ICollection<T> closedList)
	{
		path.Add(node);
		closedList.Add(node);

		bool valid = isValid(path);

		if (valid)
		{
			return path;
		}

		foreach (var neighbor in getNeighbors(node).Except(closedList))
		{
			var newPath = BackTrack(neighbor, getNeighbors, isValid, path, closedList);

			if (newPath != null)
			{
				return newPath;
			}
		}

		path.RemoveAt(path.Count - 1);

		return null;
	}

	public static IEnumerable<List<T>> FindLongestValid<T>(
		T start,
		Func<T, IEnumerable<T>> getNeighbors,
		Func<IEnumerable<T>, bool> isValid,
		Func<IEnumerable<T>, bool> shouldExpand)
	{
		var path = new List<T>();
		var solutions = new List<List<T>>();

		FindLongestValid(start, getNeighbors, isValid, shouldExpand, path, new List<T>(), solutions);
	
		return solutions;
	}

	private static void FindLongestValid<T>(
		T start,
		Func<T, IEnumerable<T>> getNeighbors,
		Func<IEnumerable<T>, bool> isValid,
		Func<IEnumerable<T>, bool> shouldExpand,
		IList<T> path,
		ICollection<T> closedList,
		ICollection<List<T>> solutions)
	{
		path.Add(start);
		closedList.Add(start);

		var valid = isValid(path);

		if (valid)
		{
			solutions.Add(path.ToList());
		}

		if(shouldExpand(path))
		{
			var neighbors = getNeighbors(start).Except(path);
			
			foreach (var neighbor in neighbors)
			{
				FindLongestValid(neighbor, getNeighbors, isValid, shouldExpand, path, closedList, solutions);
			}
		}

		path.RemoveAt(path.Count - 1);
	}
}
