// Licensed to the .NET Foundation under one or more agreements.
// The .NET Foundation licenses this file to you under the MIT license.

namespace Microsoft.NET.Sdk.WorkloadManifestReader
{
    internal class WorkloadSuggestionFinder
    {
        public WorkloadSuggestionFinder(HashSet<WorkloadPackId> installedPacks, HashSet<WorkloadPackId> requestedPacks, IEnumerable<(WorkloadId id, HashSet<WorkloadPackId> expandedPacks)> expandedWorkloads)
        {
            FindPartialSuggestionsAndSimpleCompleteSuggestions(
                requestedPacks, expandedWorkloads,
                out List<WorkloadSuggestionCandidate> partialSuggestions,
                out HashSet<WorkloadSuggestionCandidate> completeSuggestions);

            foreach (var suggestion in GatherUniqueCompletePermutedSuggestions(partialSuggestions))
            {
                completeSuggestions.Add(suggestion);
            }

            UnsortedSuggestions = completeSuggestions.Select(
                c =>
                {
                    var installedCount = c.Packs.Count(p => installedPacks.Contains(p));
                    var extraPacks = c.Packs.Count - installedCount - requestedPacks.Count;
                    return new WorkloadSuggestion(c.Workloads, extraPacks);
                })
                .ToList();

            if (UnsortedSuggestions.Count == 0)
            {
                throw new ArgumentException("requestedPacks may only contain packs that exist in expandedWorkloads", "requestedPacks");
            }
        }

        /// <summary>
        /// Search the list of expanded workloads for workloads that are "simple" complete suggestions themselves and workloads that could be part of a more complex complete suggestion.
        /// </summary>
        /// <param name="requestedPacks">The packs that a complete suggestion must include</param>
        /// <param name="expandedWorkloads">The full set of workloads, flattened to include the packs in the workloads they extend</param>
        /// <param name="partialSuggestions">Workloads that contain one or more of the required packs and could be combined with another workload to make a complete suggestion</param>
        /// <param name="completeSuggestions">Workloads that contain all the requested packs and therefore are inherently complete suggestions</param>
        internal static void FindPartialSuggestionsAndSimpleCompleteSuggestions(
            HashSet<WorkloadPackId> requestedPacks,
            IEnumerable<(WorkloadId id, HashSet<WorkloadPackId> expandedPacks)> expandedWorkloads,
            out List<WorkloadSuggestionCandidate> partialSuggestions,
            out HashSet<WorkloadSuggestionCandidate> completeSuggestions)
        {
            partialSuggestions = new List<WorkloadSuggestionCandidate>();
            completeSuggestions = new HashSet<WorkloadSuggestionCandidate>();
            foreach (var workload in expandedWorkloads)
            {
                if (workload.expandedPacks.Any(e => requestedPacks.Contains(e)))
                {
                    var unsatisfied = new HashSet<WorkloadPackId>(requestedPacks.Where(p => !workload.expandedPacks.Contains(p)));
                    var suggestion = new WorkloadSuggestionCandidate(new HashSet<WorkloadId>() { workload.id }, workload.expandedPacks, unsatisfied);
                    if (suggestion.IsComplete)
                    {
                        completeSuggestions.Add(suggestion);
                    }
                    else
                    {
                        partialSuggestions.Add(suggestion);
                    }
                }
            }
        }

        /// <summary>
        /// Finds complete suggestions by permutationally combining partial suggestions.
        /// </summary>
        /// <param name="partialSuggestions">List of partial suggestions to permutationally combine</param>
        internal static HashSet<WorkloadSuggestionCandidate> GatherUniqueCompletePermutedSuggestions(List<WorkloadSuggestionCandidate> partialSuggestions)
        {
            var completeSuggestions = new HashSet<WorkloadSuggestionCandidate>();

            foreach (var root in partialSuggestions)
            {
                GatherCompletePermutedSuggestions(root, partialSuggestions, completeSuggestions);
            }

            return FilterRedundantSuggestions(completeSuggestions);
        }

        /// <summary>
        /// Recursively explores a branching tree from the root, adding branches that would reduce the number of unsatisfied packs, and recording any fully satisfied solutions found.
        /// This is intended to only be called by <see cref="GatherUniqueCompletePermutedSuggestions"/>.
        /// </summary>
        /// <remarks>
        /// Some of these solutions may contain redundancies, i.e. workloads that are not necessary for it to be a complete solution. These should be filtered out using
        /// <see cref="FilterRedundantSuggestions"/> before using them.
        /// </remarks>
        /// <param name="root">A partial suggestion candidate that is the base for this permutation</param>
        /// <param name="branches">Partial suggestion candidates that can be added to the root to make it more complete</param>
        /// <param name="completeSuggestions">A collection to which to add any discovered complete solutions</param>
        static void GatherCompletePermutedSuggestions(WorkloadSuggestionCandidate root, List<WorkloadSuggestionCandidate> branches, HashSet<WorkloadSuggestionCandidate> completeSuggestions)
        {
            foreach (var branch in branches)
            {
                //skip branches identical to ones that have already already been taken
                //there's probably a more efficient way to do this but this is easy to reason about
                if (root.Workloads.IsSupersetOf(branch.Workloads))
                {
                    continue;
                }

                //skip branches that don't reduce the number of missing packs
                //the branch may be a more optimal solution, but this will be handled elsewhere in the permutation space where it is treated as a root
                if (!root.UnsatisfiedPacks.Overlaps(branch.Packs))
                {
                    continue;
                }

                //construct the new condidate by combining the root and the branch
                var combinedIds = new HashSet<WorkloadId>(root.Workloads);
                combinedIds.UnionWith(branch.Workloads);
                var combinedPacks = new HashSet<WorkloadPackId>(root.Packs);
                combinedPacks.UnionWith(branch.Packs);
                var stillMissing = new HashSet<WorkloadPackId>(root.UnsatisfiedPacks);
                stillMissing.ExceptWith(branch.Packs);
                var candidate = new WorkloadSuggestionCandidate(combinedIds, combinedPacks, stillMissing);

                //if the candidate contains all the requested packs, it's complete. else, recurse to try adding more branches to it.
                if (candidate.IsComplete)
                {
                    completeSuggestions.Add(candidate);
                }
                else
                {
                    GatherCompletePermutedSuggestions(candidate, branches, completeSuggestions);
                }
            }
        }

        /// <summary>
        /// Returns a new set with redundant suggestions removed from it, i.e. suggestions that are a superset of another of the suggestions.
        /// </summary>
        internal static HashSet<WorkloadSuggestionCandidate> FilterRedundantSuggestions(HashSet<WorkloadSuggestionCandidate> completeSuggestions)
        {
            var filtered = new HashSet<WorkloadSuggestionCandidate>();

            foreach (var suggestion in completeSuggestions)
            {
                bool isSupersetOfAny = false;
                foreach (var other in completeSuggestions)
                {
                    if (suggestion.Workloads.IsProperSupersetOf(other.Workloads))
                    {
                        isSupersetOfAny = true;
                    }
                }
                if (!isSupersetOfAny)
                {
                    filtered.Add(suggestion);
                }
            }

            return filtered;
        }

        public ICollection<WorkloadSuggestion> UnsortedSuggestions { get; }

        /// <summary>
        /// Finds the best value from a list of values according to one or more custom comparators. The comparators are an ordered fallback list - the second comparator is only checked when values are equal according to the first comparator, and so on.
        /// </summary>
        private static T FindBest<T>(IEnumerable<T> values, params Comparison<T>[] comparators)
        {
            T best = values.First();

            foreach (T val in values.Skip(1))
            {
                foreach (Comparison<T> c in comparators)
                {
                    var cmp = c(val, best);
                    if (cmp > 0)
                    {
                        best = val;
                        break;
                    }
                    else if (cmp < 0)
                    {
                        break;
                    }
                }
            }
            return best;
        }

        internal static WorkloadSuggestion GetBestSuggestion(ICollection<WorkloadSuggestion> suggestions) => FindBest(
                suggestions,
                (x, y) => ContainsExperimental(y.Workloads) - ContainsExperimental(x.Workloads),
                (x, y) => y.ExtraPacks - x.ExtraPacks,
                (x, y) => y.Workloads.Count - x.Workloads.Count);

        /// <summary>
        /// Gets the suggestion with the lowest number of extra packs and lowest number of workload IDs.
        /// </summary>
        public WorkloadSuggestion GetBestSuggestion() => GetBestSuggestion(UnsortedSuggestions);

        private static int ContainsExperimental(HashSet<WorkloadId> set) => set.Any(w => w.ToString().Contains("experimental")) ? 1 : 0;

        /// <summary>
        /// A partial or complete suggestion for workloads to install, annotated with which requested packs it does not satisfy
        /// </summary>
        internal class WorkloadSuggestionCandidate : IEquatable<WorkloadSuggestionCandidate>
        {
            public WorkloadSuggestionCandidate(HashSet<WorkloadId> id, HashSet<WorkloadPackId> packs, HashSet<WorkloadPackId> unsatisfiedPacks)
            {
                Packs = packs;
                UnsatisfiedPacks = unsatisfiedPacks;
                Workloads = id;
            }

            public HashSet<WorkloadId> Workloads { get; }
            public HashSet<WorkloadPackId> Packs { get; }
            public HashSet<WorkloadPackId> UnsatisfiedPacks { get; }
            public bool IsComplete => UnsatisfiedPacks.Count == 0;

            public bool Equals(WorkloadSuggestionCandidate? other) => other != null && Workloads.SetEquals(other.Workloads);

            public override int GetHashCode()
            {
                int hashcode = 0;
                foreach (var id in Workloads)
                {
                    hashcode ^= id.GetHashCode();
                }
                return hashcode;
            }
        }

        /// <summary>
        /// A suggestion of one or more workloads to be installed to satisfy missing packs.
        /// </summary>
        public class WorkloadSuggestion
        {
            public WorkloadSuggestion(HashSet<WorkloadId> workloads, int extraPacks)
            {
                Workloads = workloads;
                ExtraPacks = extraPacks;
            }

            /// <summary>
            /// The workload IDs that comprise this suggestion
            /// </summary>
            public HashSet<WorkloadId> Workloads { get; internal set; }

            /// <summary>
            /// How many additional (and potentionally unnecessary) packs this suggestion will result in installing
            /// </summary>
            public int ExtraPacks { get; internal set; }
        }
    }
}