?//******************************
// 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.Generic;
using System.Collections;

// CONSIDER: always create a small initial buffer, so that the checks in Add for a null buffer aren't needed. This 
// would improve performance slightly, but make empty Deque's take more memory. 

namespace Wintellect.PowerCollections
{
    /// <summary>
    /// <para>The Deque class implements a type of list known as a Double Ended Queue. A Deque
    /// is quite similar to a List, in that items have indices (starting at 0), and the item at any
    /// index can be efficiently retrieved. The difference between a List and a Deque lies in the
    /// efficiency of inserting elements at the beginning. In a List, items can be efficiently added
    /// to the end, but inserting an item at the beginning of the List is slow, taking time 
    /// proportional to the size of the List. In a Deque, items can be added to the beginning 
    /// or end equally efficiently, regardless of the number of items in the Deque. As a trade-off
    /// for this increased flexibility, Deque is somewhat slower than List (but still constant time) when
    /// being indexed to get or retrieve elements. </para>
    /// </summary>
    /// <remarks>
    /// <para>The Deque class can also be used as a more flexible alternative to the Queue 
    /// and Stack classes. Deque is as efficient as Queue and Stack for adding or removing items, 
    /// but is more flexible: it allows access
    /// to all items in the queue, and allows adding or removing from either end.</para>
    /// <para>Deque is implemented as a ring buffer, which is grown as necessary. The size
    /// of the buffer is doubled whenever the existing capacity is too small to hold all the
    /// elements.</para>
    /// </remarks>
    /// <typeparam name="T">The type of items stored in the Deque.</typeparam>
    [Serializable]
    public class Deque<T> : ListBase<T>, ICloneable
    {
        // The initial size of the buffer.
        private const int INITIAL_SIZE = 8;

        // A ring buffer containing all the items in the deque. Shrinks or grows as needed.
        // Except temporarily during an add, there is always at least one empty item.
        private T[] buffer;

        // Index of the first item (index 0) in the deque.
        // Always in the range 0 through buffer.Length - 1.
        private int start;

        // Index just beyond the last item in the deque. If equal to start, the deque is empty.
        // Always in the range 0 through buffer.Length - 1.
        private int end;

        // Holds the change stamp for the collection.
        private int changeStamp;

        /// <summary>
        /// Must be called whenever there is a structural change in the tree. Causes
        /// changeStamp to be changed, which causes any in-progress enumerations
        /// to throw exceptions.
        /// </summary>
        private void StopEnumerations()
        {
            ++changeStamp;
        }

        /// <summary>
        /// Checks the given stamp against the current change stamp. If different, the
        /// collection has changed during enumeration and an InvalidOperationException
        /// must be thrown
        /// </summary>
        /// <param name="startStamp">changeStamp at the start of the enumeration.</param>
        private void CheckEnumerationStamp(int startStamp)
        {
            if (startStamp != changeStamp) {
                throw new InvalidOperationException(Strings.ChangeDuringEnumeration);
            }
        }

        /// <summary>
        /// Create a new Deque that is initially empty.
        /// </summary>
        public Deque()
        {
        }

        /// <summary>
        /// Create a new Deque initialized with the items from the passed collection,
        /// in order.
        /// </summary>
        /// <param name="collection">A collection of items to initialize the Deque with.</param>
        public Deque(IEnumerable<T> collection)
        {
            AddManyToBack(collection);
        }

        /// <summary>
        /// Gets the number of items currently stored in the Deque. The last item
        /// in the Deque has index Count-1.
        /// </summary>
        /// <remarks>Getting the count of items in the Deque takes a small constant
        /// amount of time.</remarks>
        /// <value>The number of items stored in this Deque.</value>
        public sealed override int Count
        {
            get {
                if (end >= start)
                    return end - start;
                else
                    return end + buffer.Length - start;
            }
        }

        /// <summary>
        /// Copies all the items in the Deque into an array.
        /// </summary>
        /// <param name="array">Array to copy to.</param>
        /// <param name="arrayIndex">Starting index in <paramref name="array"/> to copy to.</param>
        public sealed override void CopyTo(T[] array, int arrayIndex)
        {
            if (array == null)
                throw new ArgumentNullException("array");

            // This override is provided to give a more efficient implementation to CopyTo than
            // the default one provided by CollectionBase.

            int length = (buffer == null) ? 0 : buffer.Length;

            if (start > end) {
                Array.Copy(buffer, start, array, arrayIndex, length - start);
                Array.Copy(buffer, 0, array, arrayIndex + length - start, end);
            }
            else {
                if (end > start)
                    Array.Copy(buffer, start, array, arrayIndex, end - start);
            }
        }

        /// <summary>
        /// Gets or sets the capacity of the Deque. The Capacity is the number of
        /// items that this Deque can hold without expanding its internal buffer. Since
        /// Deque will automatically expand its buffer when necessary, in almost all cases
        /// it is unnecessary to worry about the capacity. However, if it is known that a
        /// Deque will contain exactly 1000 items eventually, it can slightly improve 
        /// efficiency to set the capacity to 1000 up front, so that the Deque does not
        /// have to expand automatically.
        /// </summary>
        /// <value>The number of items that this Deque can hold without expanding its
        /// internal buffer.</value>
        /// <exception cref="ArgumentOutOfRangeException">The capacity is being set
        /// to less than Count, or to too large a value.</exception>
        public int Capacity
        {
            get
            {
                if (buffer == null)
                    return 0;
                else
                    return buffer.Length - 1;
            }
            set
            {
                if (value < Count)
                    throw new ArgumentOutOfRangeException("value", Strings.CapacityLessThanCount);
                if (value > int.MaxValue - 1)
                    throw new ArgumentOutOfRangeException("value");
                if (value == Capacity)
                    return;

                T[] newBuffer = new T[value + 1];
                CopyTo(newBuffer, 0);
                end = Count;
                start = 0;
                buffer = newBuffer;
            }
        }

        /// <summary>
        /// Trims the amount of memory used by the Deque by changing
        /// the Capacity to be equal to Count. If no more items will be added
        /// to the Deque, calling TrimToSize will reduce the amount of memory
        /// used by the Deque.
        /// </summary>
        public void TrimToSize()
        {
            Capacity = Count;
        }

        /// <summary>
        /// Removes all items from the Deque.
        /// </summary>
        /// <remarks>Clearing the Deque takes a small constant amount of time, regardless of
        /// how many items are currently in the Deque.</remarks>
        public sealed override void Clear()
        {
            StopEnumerations();
            buffer = null;
            start = end = 0;
        }

        /// <summary>
        /// Gets or sets an item at a particular index in the Deque. 
        /// </summary>
        /// <remarks>Getting or setting the item at a particular index takes a small constant amount
        /// of time, no matter what index is used.</remarks>
        /// <param name="index">The index of the item to retrieve or change. The front item has index 0, and
        /// the back item has index Count-1.</param>
        /// <returns>The value at the indicated index.</returns>
        /// <exception cref="ArgumentOutOfRangeException">The index is less than zero or greater than or equal
        /// to Count.</exception>
        public sealed override T this[int index]
        {
            get
            {
                int i = index + start;
                if (i < start)  // handles both the case where index < 0, or the above addition overflow to a negative number.
                    throw new ArgumentOutOfRangeException("index");

                if (end >= start) {
                    if (i >= end)
                        throw new ArgumentOutOfRangeException("index");
                    return buffer[i];
                }
                else {
                    int length = buffer.Length;
                    if (i >= length) {
                        i -= length;
                        if (i >= end)
                            throw new ArgumentOutOfRangeException("index");
                    }
                    return buffer[i];
                }
            }

            set
            {
                // Like List<T>, we stop enumerations after a set operation. There is no
                // technical reason to do this, however.
                StopEnumerations();

                int i = index + start;
                if (i < start)  // handles both the case where index < 0, or the above addition overflow to a negative number.
                    throw new ArgumentOutOfRangeException("index");

                if (end >= start) {
                    if (i >= end)
                        throw new ArgumentOutOfRangeException("index");
                    buffer[i] = value;
                }
                else {
                    int length = buffer.Length;
                    if (i >= length) {
                        i -= length;
                        if (i >= end)
                            throw new ArgumentOutOfRangeException("index");
                    }
                    buffer[i] = value;
                }
            }
        }

        /// <summary>
        /// Enumerates all of the items in the list, in order. The item at index 0
        /// is enumerated first, then the item at index 1, and so on. If the items
        /// are added to or removed from the Deque during enumeration, the 
        /// enumeration ends with an InvalidOperationException.
        /// </summary>
        /// <returns>An IEnumerator&lt;T&gt; that enumerates all the
        /// items in the list.</returns>
        /// <exception cref="InvalidOperationException">The Deque has an item added or deleted during the enumeration.</exception>
        public sealed override IEnumerator<T> GetEnumerator()
        {
            int startStamp = changeStamp;
            int count = Count;

            for (int i = 0; i < count; ++i) {
                yield return this[i];
                CheckEnumerationStamp(startStamp);
            }
        }

        /// <summary>
        /// Creates the initial buffer and initialized the Deque to contain one initial
        /// item.
        /// </summary>
        /// <param name="firstItem">First and only item for the Deque.</param>
        private void CreateInitialBuffer(T firstItem)
        {
            // The buffer hasn't been created yet.
            buffer = new T[INITIAL_SIZE];
            start = 0;
            end = 1;
            buffer[0] = firstItem;
            return;
        }

        /// <summary>
        /// Inserts a new item at the given index in the Deque. All items at indexes 
        /// equal to or greater than <paramref name="index"/> move up one index
        /// in the Deque.
        /// </summary>
        /// <remarks>The amount of time to insert an item in the Deque is proportional
        /// to the distance of index from the closest end of the Deque: 
        /// O(Min(<paramref name="index"/>, Count - <paramref name="index"/>)).
        /// Thus, inserting an item at the front or end of the Deque is always fast; the middle of
        /// of the Deque is the slowest place to insert.
        /// </remarks>
        /// <param name="index">The index in the Deque to insert the item at. After the
        /// insertion, the inserted item is located at this index. The
        /// front item in the Deque has index 0.</param>
        /// <param name="item">The item to insert at the given index.</param>
        /// <exception cref="ArgumentOutOfRangeException"><paramref name="index"/> is
        /// less than zero or greater than Count.</exception>
        public sealed override void Insert(int index, T item)
        {