RangeExtensions.cs

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

namespace AshTools.Extensions
{
    public static class RangeExtensions
    {
        /// <summary>
        /// Evaluates whether or not two ranges overlap with eachother.
        /// </summary>
        /// <returns><c>true</c>, if there is an overlap, <c>false</c> otherwise.</returns>
        /// <param name="range">Range to compare on</param>
        /// <param name="with">Range to compare to</param>
        /// <typeparam name="T">The type used in the Range</typeparam>
        public static bool OverlapsWith<T>(this Range<T> range, Range<T> with) where T : IComparable<T>
            => range.Start.CompareTo(with.End) < 0 && with.Start.CompareTo(range.End) < 0;

        /// <summary>
        /// Evaluates whether or not two ranges of `T` overlap with eachother.
        /// </summary>
        /// <returns><c>true</c>, if there is an overlap, <c>false</c> otherwise.</returns>
        /// <param name="range">Range to compare on</param>
        /// <param name="start">Start of the range to compare to</param>
        /// <param name="end">End of the range to compare to</param>
        /// <typeparam name="T">The type used in the Range</typeparam>
        public static bool OverlapsWith<T>(this Range<T> range, T start, T end) where T : IComparable<T>
            => range.Start.CompareTo(end) < 0 && start.CompareTo(range.End) < 0;

        /// <summary>
        /// Evaluates whether or not a range contains another range.
        /// </summary>
        /// <returns><c>true</c>, if the other range is contained within this range, <c>false</c> otherwise.</returns>
        /// <param name="range">Range to compare on</param>
        /// <param name="other">Range to evaluate whether or not it is contained within the aforementioned range.</param>
        /// <typeparam name="T">The type used in the Range</typeparam>
        public static bool Contains<T>(this Range<T> range, Range<T> other) where T : IComparable<T>
            => range.Contains(other.Start) && range.Contains(other.End);

        /// <summary>
        /// Merges two ranges such that the resulting enumerable contains no overlapping ranges.
        /// </summary>
        /// <returns>An enumerable of the merged ranges.</returns>
        /// <param name="range">Range to merge on</param>
        /// <param name="compliment">Complimenting range to merge with</param>
        /// <typeparam name="T">The type used in the Range</typeparam>
        public static IEnumerable<Range<T>> MergeOn<T>(this Range<T> range, Range<T> compliment) where T : IComparable<T>
        {
            var rangeList = new List<Range<T>>();

            if (range.OverlapsWith(compliment))
            {
                if (range.Contains(compliment.Start))
                {
                    if (range.Contains(compliment.End))
                    {
                        rangeList.Add(range);
                    }
                    else
                    {
                        rangeList.Add(new Range<T>(range.Start, compliment.End));
                    }
                }
                else
                {
                    if (range.Contains(compliment.End))
                    {
                        rangeList.Add(new Range<T>(compliment.Start, range.End));
                    }
                    else
                    {
                        rangeList.Add(compliment);
                    }
                }
            }
            else
            {
                rangeList.Add(range);
                rangeList.Add(compliment);
            }

            return rangeList;
        }

        /// <summary>
        /// Subtracts a reducer from a range, ensuring that the resultant range is either empty or does not contain
        /// any values that are inside of the reducer.
        /// 
        /// <para>
        /// Example (formatting involved):
        ///  Range
        ///   a       b
        ///   |-------|
        ///  Reducer
        ///     c  d
        ///     |--|
        ///  Result
        ///   a c  d  b
        ///   |-|  |--|
        /// </para>
        /// 
        /// </summary>
        /// <returns>The reduced range.</returns>
        /// <param name="range">A range to reduce.</param>
        /// <param name="reducer">A range to reduce by.</param>
        /// <typeparam name="T">A comparable type that the ranges contain.</typeparam>
        public static IEnumerable<Range<T>> ReduceBy<T>(this Range<T> range, Range<T> reducer) where T : IComparable<T>
        {
            var rangeList = new List<Range<T>>();

            if (range.OverlapsWith(reducer))
            {
                if (reducer.Contains(range.Start) && !reducer.Contains(range.End))
                {
                    rangeList.Add(new Range<T>(reducer.End, range.End));
                }
                else if (!reducer.Contains(range.Start) && reducer.Contains(range.End))
                {
                    rangeList.Add(new Range<T>(range.Start, reducer.Start));
                }
                else if (!reducer.Contains(range.Start) && !reducer.Contains(range.End))
                {
                    rangeList.Add(new Range<T>(range.Start, reducer.Start));
                    rangeList.Add(new Range<T>(reducer.End, range.End));
                }
            }
            else
            {
                rangeList.Add(range);
            }

            return rangeList;
        }

        /// <summary>
        /// Subtracts multiple reducers from a range, ensuring that the resultant range is either empty or does not contain
        /// any values that are inside of the reducers.
        /// </summary>
        /// <returns>The reduced range.</returns>
        /// <param name="range">The range to reduce.</param>
        /// <param name="reducers">Ranges to reduce by.</param>
        /// <typeparam name="T">A comparable type that the ranges contain.</typeparam>
        public static IEnumerable<Range<T>> ReduceBy<T>(this Range<T> range, IEnumerable<Range<T>> reducers) where T : IComparable<T>
        {
            return ReduceBy(new[] { range }, reducers);
        }

        /// <summary>
        /// Subtracts multiple reducers from each range, ensuring that the resultant ranges are either empty or do not contain
        /// any values that are inside of the reducers.
        /// </summary>
        /// <returns>The reduced ranges..</returns>
        /// <param name="ranges">The ranges to reduce.</param>
        /// <param param name="reducers">The ranges to reduce by.</param>
        /// <typeparam name="T">A comparable type that the ranges contain.</typeparam>
        public static IEnumerable<Range<T>> ReduceBy<T>(this IEnumerable<Range<T>> ranges, IEnumerable<Range<T>> reducers) where T : IComparable<T>
        {
            var reducedRanges = ranges.ToList();

            foreach (var reducer in reducers)
            {
                var newRanges = new List<Range<T>>(reducedRanges);
                foreach (var range in reducedRanges)
                {
                    newRanges.Remove(range);
                    newRanges.AddRange(range.ReduceBy(reducer));
                }
                reducedRanges = newRanges;
            }

            return reducedRanges;
        }

        /// <summary>
        /// Ensures there are no overlapping ranges by merging all overlapping ranges together. O(nlogn) time complexity. O(n) space complexity.
        /// </summary>
        /// <returns>The flattened ranges.</returns>
        /// <param name="ranges">Ranges to flatten.</param>
        /// <typeparam name="T">A comparable type that the ranges contain.</typeparam>
        public static IEnumerable<Range<T>> Flatten<T>(this IEnumerable<Range<T>> ranges) where T : IComparable<T>
        {
            var sorted = ranges.OrderBy(r => r.Start).ToList();
            if (sorted.Count == 0)
            {
                return sorted;
            }

            var stack = new Stack<Range<T>>();
            stack.Push(sorted.First());

            for (var i = 1; i < sorted.Count; i++)
            {
                var top = stack.Peek();

                if (top.End.CompareTo(sorted[i].Start) < 0)
                {
                    stack.Push(sorted[i]);
                }
                else if (top.End.CompareTo(sorted[i].End) < 0)
                {
                    top = new Range<T>(top.Start, sorted[i].End);
                    stack.Pop();
                    stack.Push(top);
                }
            }

            return stack;
        }
    }
}