?//******************************
// Written by Peter Golde
// Copyright (c) 2004-2005, Wintellect
//
// Use and restribution of this code is subject to the license agreement 
// contained in the file "License.txt" accompanying this file.
//******************************

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

#pragma warning disable 419  // Ambigious cref in XML comment

// Make internals of this library available to the unit test framework.
[assembly: System.Runtime.CompilerServices.InternalsVisibleTo("UnitTests")]

// Everything should be CLS compliant.
[assembly: CLSCompliant(true)]


namespace Wintellect.PowerCollections
{
    /// <summary>
    /// The BinaryPredicate delegate type  encapsulates a method that takes two
    /// items of the same type, and returns a boolean value representating 
    /// some relationship between them. For example, checking whether two
    /// items are equal or equivalent is one kind of binary predicate.
    /// </summary>
    /// <param name="item1">The first item.</param>
    /// <param name="item2">The second item.</param>
    /// <returns>Whether item1 and item2 satisfy the relationship that the BinaryPredicate defines.</returns>
    public delegate bool BinaryPredicate<T>(T item1, T item2);

    /// <summary>
    /// Algorithms contains a number of static methods that implement
    /// algorithms that work on collections. Most of the methods deal with
    /// the standard generic collection interfaces such as IEnumerable&lt;T&gt;,
    /// ICollection&lt;T&gt; and IList&lt;T&gt;.
    /// </summary>
    public static class Algorithms
    {
        #region Collection wrappers

        /// <summary>
        /// The class that is used to implement IList&lt;T&gt; to view a sub-range
        /// of a list. The object stores a wrapped list, and a start/count indicating
        /// a sub-range of the list. Insertion/deletions through the sub-range view
        /// cause the count to change also; insertions and deletions directly on
        /// the wrapped list do not.
        /// </summary>
        [Serializable]
        private class ListRange<T> : ListBase<T>, ICollection<T>
        {
            private IList<T> wrappedList;
            private int start;
            private int count;

            /// <summary>
            /// Create a sub-range view object on the indicate part 
            /// of the list.
            /// </summary>
            /// <param name="wrappedList">List to wrap.</param>
            /// <param name="start">The start index of the view in the wrapped list.</param>
            /// <param name="count">The number of items in the view.</param>
            public ListRange(IList<T> wrappedList, int start, int count)
            {
                this.wrappedList = wrappedList;
                this.start = start;
                this.count = count;
            }

            public override int Count
            {
                get { 
                    return Math.Min(count, wrappedList.Count - start); 
                }
            }

            public override void Clear()
            {
                if (wrappedList.Count - start < count)
                    count = wrappedList.Count - start;

                while (count > 0) {
                    wrappedList.RemoveAt(start + count - 1);
                    --count;
                }
            }

            public override void Insert(int index, T item)
            {
                if (index < 0 || index > count)
                    throw new ArgumentOutOfRangeException("index");

                wrappedList.Insert(start + index, item);
                ++count;
            }

            public override void RemoveAt(int index)
            {
                if (index < 0 || index >= count)
                    throw new ArgumentOutOfRangeException("index");

                wrappedList.RemoveAt(start + index);
                --count;
            }

            public override bool Remove(T item)
            {
                if (wrappedList.IsReadOnly)
                    throw new NotSupportedException(string.Format(Strings.CannotModifyCollection, "Range"));
                else
                    return base.Remove(item);
            }

            public override T this[int index]
            {
                get
                {
                    if (index < 0 || index >= count)
                        throw new ArgumentOutOfRangeException("index");

                    return wrappedList[start + index];
                }
                set
                {
                    if (index < 0 || index >= count)
                        throw new ArgumentOutOfRangeException("index");

                    wrappedList[start + index] = value;
                }
            }

            bool ICollection<T>.IsReadOnly
            {
                get
                {
                    return wrappedList.IsReadOnly;
                }
            }
        }

        /// <summary>
        /// Returns a view onto a sub-range of a list. Items from <paramref name="list"/> are not copied; the
        /// returned IList&lt;T&gt; is simply a different view onto the same underlying items. Changes to <paramref name="list"/>
        /// are reflected in the view, and vice versa. Insertions and deletions in the view change the size of the 
        /// view, but insertions and deletions in the underlying list do not.
        /// </summary>
        /// <remarks>This method can be used to apply an algorithm to a portion of a list. For example:
        /// <code>Algorithms.ReverseInPlace(Algorithms.Range(list, 3, 6))</code>
        /// will reverse the 6 items beginning at index 3.</remarks>
        /// <typeparam name="T">The type of the items in the list.</typeparam>
        /// <param name="list">The list to view.</param>
        /// <param name="start">The starting index of the view.</param>
        /// <param name="count">The number of items in the view.</param>
        /// <returns>A list that is a view onto the given sub-list. </returns>
        /// <exception cref="ArgumentNullException"><paramref name="list"/> is null.</exception>
        /// <exception cref="ArgumentOutOfRangeException"><paramref name="start"/> or <paramref name="count"/> is negative.</exception>
        /// <exception cref="ArgumentOutOfRangeException"><paramref name="start"/> + <paramref name="count"/> is greater than the
        /// size of <paramref name="list"/>.</exception>
        public static IList<T> Range<T>(IList<T> list, int start, int count)
        {
            if (list == null)
                throw new ArgumentOutOfRangeException("list");
            if (start < 0 || start > list.Count || (start == list.Count && count != 0))
                throw new ArgumentOutOfRangeException("start");
            if (count < 0 || count > list.Count || count + start > list.Count)
                throw new ArgumentOutOfRangeException("count");

            return new ListRange<T>(list, start, count);
        }

        /// <summary>
        /// The class that is used to implement IList&lt;T&gt; to view a sub-range
        /// of an array. The object stores a wrapped array, and a start/count indicating
        /// a sub-range of the array. Insertion/deletions through the sub-range view
        /// cause the count to change up to the size of the underlying array. Elements
        /// fall off the end of the underlying array.
        /// </summary>
        [Serializable]
        private class ArrayRange<T> : ListBase<T>
        {
            private T[] wrappedArray;
            private int start;
            private int count;

            /// <summary>
            /// Create a sub-range view object on the indicate part 
            /// of the array.
            /// </summary>
            /// <param name="wrappedArray">Array to wrap.</param>
            /// <param name="start">The start index of the view in the wrapped list.</param>
            /// <param name="count">The number of items in the view.</param>
            public ArrayRange(T[] wrappedArray, int start, int count)
            {
                this.wrappedArray = wrappedArray;
                this.start = start;
                this.count = count;
            }

            public override int Count
            {
                get
                {
                    return count;
                }
            }

            public override void Clear()
            {
                Array.Copy(wrappedArray, start + count, wrappedArray, start, wrappedArray.Length - (start + count));
                Algorithms.FillRange(wrappedArray, wrappedArray.Length - count, count, default(T));
                count = 0;
            }

            public override void Insert(int index, T item)
            {
                if (index < 0 || index > count)
                    throw new ArgumentOutOfRangeException("index");

                int i = start + index;

                if (i + 1 < wrappedArray.Length)
                    Array.Copy(wrappedArray, i, wrappedArray, i + 1, wrappedArray.Length - i - 1);
                if (i < wrappedArray.Length)
                    wrappedArray[i] = item;

                if (start + count < wrappedArray.Length)
                    ++count;
            }

            public override void RemoveAt(int index)
            {
                if (index < 0 || index >= count)
                    throw new ArgumentOutOfRangeException("index");

                int i = start + index;

                if (i < wrappedArray.Length - 1)
                    Array.Copy(wrappedArray, i + 1, wrappedArray, i, wrappedArray.Length - i - 1);
                wrappedArray[wrappedArray.Length - 1] = default(T);

                --count;
            }

            public override T this[int index]
            {
                get
                {
                    if (index < 0 || index >= count)
                        throw new ArgumentOutOfRangeException("index");

                    return wrappedArray[start + index];
                }
                set
                {
                    if (index < 0 || index >= count)
                        throw new ArgumentOutOfRangeException("index");

                    wrappedArray[start + index] = value;
                }
            }
        }

        /// <summary>
        /// Returns a view onto a sub-range of an array. Items from <paramref name="array"/> are not copied; the
        /// returned IList&lt;T&gt; is simply a different view onto the same underlying items. Changes to <paramref name="array"/>
        /// are reflected in the view, and vice versa. Insertions and deletions in the view change the size of the 
        /// view. After an insertion, the last item in <paramref name="array"/> "falls off the end". After a deletion, the
        /// last item in array becomes the default value (0 or null).
        /// </summary>
        /// <remarks>This method can be used to apply an algorithm to a portion of a array. For example:
        /// <code>Algorithms.ReverseInPlace(Algorithms.Range(array, 3, 6))</code>
        /// will reverse the 6 items beginning at index 3.</remarks>
        /// <param name="array">The array to view.</param>
        /// <param name="start">The starting index of the view.</param>
        /// <param name="count">The number of items in the view.</param>
        /// <returns>A list that is a view onto the given sub-array. </returns>
        /// <exception cref="ArgumentNullException"><paramref name="array"/> is null.</exception>
        /// <exception cref="ArgumentOutOfRangeException"><paramref name="start"/> or <paramref name="count"/> is negative.</exception>
        /// <exception cref="ArgumentOutOfRangeException"><paramref name="start"/> + <paramref name="count"/> is greater than the
        /// size of <paramref name="array"/>.</exception>
        public static IList<T> Range<T>(T[] array, int start, int count)
        {
            if (array == null)
                throw new ArgumentOutOfRangeException("array");
            if (start < 0 || start > array.Length || (start == array.Length && count != 0))
                throw new ArgumentOutOfRangeException("start");
            if (count < 0 || count > array.Length || count + start > array.Length)
                throw new ArgumentOutOfRangeException("count");

            return new ArrayRange<T>(array, start, count);
        }

        /// <summary>
        /// The read-only ICollection&lt;T&gt; implementation that is used by the ReadOnly method.
        /// Methods that modify the collection throw a NotSupportedException, methods that don't
        /// modify are fowarded through to the wrapped collection.