using System;
using System.Collections.Generic;
using System.Linq;

namespace WasmBox.Pixie {
    /// <summary>
    /// A helper class that creates diffs.
    /// </summary>
    public static class Diff {
        /// <summary>
        /// Creates a diff from an old sequence and a new sequence.
        /// </summary>
        /// <param name="oldSequence">A 'before' sequence for the diff.</param>
        /// <param name="newSequence">An 'after' sequence of the diff.</param>
        /// <returns>
        /// A diff that, when applied, turns <paramref name="oldSequence"/> into
        /// <paramref name="newSequence"/>.
        /// </returns>
        public static Diff<T> Create<T>(
            IEnumerable<T> oldSequence,
            IEnumerable<T> newSequence) {
            return Create( oldSequence, newSequence, EqualityComparer<T>.Default);
        }

        /// <summary>
        /// Creates a diff from an old sequence, a new sequence
        /// and an equality comparer.
        /// </summary>
        /// <param name="oldSequence">A 'before' sequence for the diff.</param>
        /// <param name="newSequence">An 'after' sequence of the diff.</param>
        /// <param name="comparer">
        /// The equality comparer to use for comparing elements.
        /// </param>
        /// <returns>
        /// A diff that, when applied, turns <paramref name="oldSequence"/> into
        /// <paramref name="newSequence"/>.
        /// </returns>
        public static Diff<T> Create<T>(
            IEnumerable<T> oldSequence,
            IEnumerable<T> newSequence,
            IEqualityComparer<T> comparer) {
            // Algorithm based on the Python version of simplediff by
            // Paul Butler. Original source code at
            // https://github.com/paulgb/simplediff.
            // Comments are mostly preserved from original algorithm.

            // Create a map from old values to their indices.
            var oldIndexMap = new Dictionary<T, List<int>>(comparer);
            int oldSequenceLength = 0; {
                foreach (var val in oldSequence) {
                    List<int> indexList;
                    if (!oldIndexMap.TryGetValue(val, out indexList)) {
                        indexList = new List<int>();
                        oldIndexMap[val] = indexList;
                    }
                    indexList.Add(oldSequenceLength);
                    oldSequenceLength++;
                }
            }

            // Find the largest substring common to old and new.
            // We use a dynamic programming approach here.
            //
            // We iterate over each value in the `new` list, calling the
            // index `inew`. At each iteration, `overlap[i]` is the
            // length of the largest suffix of `old[:i]` equal to a suffix
            // of `new[:inew]` (or unset when `old[i]` != `new[inew]`).
            //
            // At each stage of iteration, the new `overlap` (called
            // `_overlap` until the original `overlap` is no longer needed)
            // is built from the old one.
            //
            // If the length of overlap exceeds the largest substring
            // seen so far (`sub_length`), we update the largest substring
            // to the overlapping strings.

            var overlap = new Dictionary<int, int>();

            // `sub_start_old` is the index of the beginning of the largest overlapping
            // substring in the old list. `sub_start_new` is the index of the beginning
            // of the same substring in the new list. `sub_length` is the length that
            // overlaps in both.
            // These track the largest overlapping substring seen so far, so naturally
            // we start with a 0-length substring.
            var sub_start_old = 0;
            var sub_start_new = 0;
            var sub_length = 0;

            int inew = 0;
            foreach (var val in newSequence) {
                var _overlap = new Dictionary<int, int>();
                List<int> oldIndexList;
                if (oldIndexMap.TryGetValue(val, out oldIndexList)) {
                    for (int i = 0; i < oldIndexList.Count; i++) {
                        int iold = oldIndexList[i];
                        // Now we are considering all values of iold such that
                        // `old[iold] == new[inew]`.
                        _overlap[iold] = (iold == 0 ? 0 : GetOrDefault( overlap, iold - 1, 0)) + 1;
                        if (_overlap[iold] > sub_length) {
                            // This is the largest substring seen so far, so store its
                            // indices.
                            sub_length = _overlap[iold];
                            sub_start_old = iold - sub_length + 1;
                            sub_start_new = inew - sub_length + 1;
                        }
                    }
                }
                overlap = _overlap;

                inew++;
            }
            int newSequenceLength = inew;

            var diffElems = new List<DiffElement<T>>();
            if (sub_length == 0) {
                // If no common substring is found, we return an insert and delete...
                if (oldSequenceLength > 0) {
                    diffElems.Add(
                        new DiffElement<T>(
                            DiffOperation.Deletion,
                            oldSequence));
                }
                if (newSequenceLength > 0) {
                    diffElems.Add(
                        new DiffElement<T>(
                            DiffOperation.Insertion,
                            newSequence));
                }
            }
            else {
                // ...otherwise, the common substring is unchanged and we recursively
                // diff the text before and after that substring.
                diffElems.AddRange(
                    Create<T>(
                        oldSequence.Take( sub_start_old),
                        newSequence.Take( sub_start_new),
                        comparer)
                    .Elements);

                diffElems.Add(
                    new DiffElement<T>(
                        DiffOperation.Unchanged,
                        newSequence
                            .Skip( sub_start_new)
                            .Take( sub_length)));

                diffElems.AddRange(
                    Create<T>(
                        oldSequence.Skip( sub_start_old + sub_length),
                        newSequence.Skip( sub_start_new + sub_length),
                        comparer)
                    .Elements);
            }
            return new Diff<T>(diffElems);
        }

        private static V GetOrDefault<K, V>(Dictionary<K, V> dictionary, K key, V defaultValue) {
            V result;
            if (dictionary.TryGetValue(key, out result)) {
                return result;
            }
            else {
                return defaultValue;
            }
        }
    }

    /// <summary>
    /// Represents the changes required to turn one sequence
    /// into another.
    /// </summary>
    public struct Diff<T> : IEquatable<Diff<T>> {
        /// <summary>
        /// Creates a diff from a sequence of diff elements.
        /// </summary>
        /// <param name="elements">The diff elements.</param>
        public Diff(IReadOnlyList<DiffElement<T>> elements) {
            this.Elements = elements;
        }

        /// <summary>
        /// Gets the elements in this diff.
        /// </summary>
        /// <returns>The diff elements.</returns>
        public IReadOnlyList<DiffElement<T>> Elements { get; private set; }

        /// <summary>
        /// Recreates the old sequence, that is, the sequence
        /// prior to applying this diff.
        /// </summary>
        /// <returns>The old sequence.</returns>
        public IReadOnlyList<T> OldSequence {
            get {
                var result = new List<T>();
                int elemCount = Elements.Count;
                for (int i = 0; i < elemCount; i++) {
                    var elem = Elements[i];
                    if (elem.Operation != DiffOperation.Insertion) {
                        result.AddRange(elem.Values);
                    }
                }
                return result;
            }
        }

        /// <summary>
        /// Recreates the new sequence, that is, the sequence
        /// produced by applying this diff.
        /// </summary>
        /// <returns>The new sequence.</returns>
        public IReadOnlyList<T> NewSequence {
            get {
                var result = new List<T>();
                int elemCount = Elements.Count;
                for (int i = 0; i < elemCount; i++) {
                    var elem = Elements[i];
                    if (elem.Operation != DiffOperation.Deletion) {
                        result.AddRange(elem.Values);
                    }
                }
                return result;
            }
        }

        /// <inheritdoc/>
        public override bool Equals(object obj) {
            return obj is Diff<T> && Equals((Diff<T>)obj);
        }

        /// <summary>
        /// Tests if this diff is the same as another diff.
        /// </summary>
        /// <param name="other">The other diff.</param>
        /// <returns>
        /// <c>true</c> if this diff equals the other diff; otherwise, <c>false</c>.
        /// </returns>
        public bool Equals(Diff<T> other) {
            return Enumerable.SequenceEqual( Elements, other.Elements);
        }

        /// <inheritdoc/>
        public override int GetHashCode() {
            int elemCount = Elements.Count;
            int hash = 0;
            for (int i = 0; i < elemCount; i++) {
                hash = (hash << 1) ^ Elements[i].GetHashCode();
            }
            return hash;
        }

        /// <inheritdoc/>
        public override string ToString() {
            return "[" + string.Join( ", ", Elements) + "]";
        }
    }

    /// <summary>
    /// An enumeration of possible operations a diff element
    /// can perform.
    /// </summary>
    public enum DiffOperation {
        /// <summary>
        /// The diff element leaves a number of values in place.
        /// </summary>
        Unchanged,

        /// <summary>
        /// The diff inserts a number of new values into the
        /// sequence.
        /// </summary>
        Insertion,

        /// <summary>
        /// The diff deletes a number of old values from the
        /// sequence.
        /// </summary>
        Deletion
    }

    /// <summary>
    /// An element of a diff.
    /// </summary>
    public struct DiffElement<T> : IEquatable<DiffElement<T>> {
        /// <summary>
        /// Creates a diff element.
        /// </summary>
        /// <param name="operation">
        /// The operation to perform.
        /// </param>
        /// <param name="values">
        /// The sequence of values to operate on.
        /// </param>
        public DiffElement(
            DiffOperation operation,
            IEnumerable<T> values)
            : this(operation, values.ToArray()) { }

        /// <summary>
        /// Creates a diff element.
        /// </summary>
        /// <param name="operation">
        /// The operation to perform.
        /// </param>
        /// <param name="values">
        /// The sequence of values to operate on.
        /// </param>
        public DiffElement(
            DiffOperation operation,
            IReadOnlyList<T> values) {
            this.Operation = operation;
            this.Values = values;
        }

        /// <summary>
        /// Gets the operation this diff element performs.
        /// </summary>
        /// <returns>The operation it performs.</returns>
        public DiffOperation Operation { get; private set; }

        /// <summary>
        /// Gets the sequence of values this diff element inserts,
        /// deletes or leaves unchanged.
        /// </summary>
        /// <returns>The sequence of values.</returns>
        public IReadOnlyList<T> Values { get; private set; }

        /// <summary>
        /// Tests if this diff elements equals another diff element.
        /// </summary>
        /// <param name="other">A diff element to test for equality.</param>
        /// <returns>
        /// <c>true</c> if this diff element equals the other diff element;
        /// otherwise, <c>false</c>.
        /// </returns>
        public bool Equals(DiffElement<T> other) {
            return Operation == other.Operation
                && Enumerable.SequenceEqual( Values, other.Values);
        }

        /// <inheritdoc/>
        public override bool Equals(object obj) {
            return obj is DiffElement<T> && Equals((DiffElement<T>)obj);
        }

        /// <inheritdoc/>
        public override int GetHashCode() {
            int valueCount = Values.Count;
            int hash = Operation.GetHashCode();
            for (int i = 0; i < valueCount; i++) {
                hash = (hash << 1) ^ Values[i].GetHashCode();
            }
            return hash;
        }

        /// <inheritdoc/>
        public override string ToString() {
            string prefix = Operation == DiffOperation.Insertion
                ? "+"
                : Operation == DiffOperation.Deletion
                    ? "-"
                    : "=";
            return prefix + " " + string.Concat( Values);
        }
    }
}