deque.cs

C#写的类似于STL的集合类,首先是C#编写,可以用于.net变程.

            StopEnumerations();

            int count = Count;
            if (index < 0 || index > Count)
                throw new ArgumentOutOfRangeException("index");

            if (buffer == null) {
                // The buffer hasn't been created yet.
                CreateInitialBuffer(item);
                return;
            }

            int length = buffer.Length;
            int i;  // The location the new item was placed at.

            if (index < count / 2) {
                // Inserting into the first half of the list. Move items with
                // lower index down in the buffer.
                start -= 1;
                if (start < 0)
                    start += length;
                i = index + start;
                if (i >= length) {
                    i -= length;
                    if (length - 1 > start)
                        Array.Copy(buffer, start + 1, buffer, start, length - 1 - start);
                    buffer[length - 1] = buffer[0];  // unneeded if end == 0, but doesn't hurt
                    if (i > 0)
                        Array.Copy(buffer, 1, buffer, 0, i);
                }
                else {
                    if (i > start)
                        Array.Copy(buffer, start + 1, buffer, start, i - start);
                }
            }
            else {
                // Inserting into the last half of the list. Move items with higher
                // index up in the buffer.
                i = index + start;
                if (i >= length)
                    i -= length;
                if (i <= end) {  
                    if (end > i)
                        Array.Copy(buffer, i, buffer, i + 1, end - i);
                    end += 1;
                    if (end >= length)
                        end -= length;
                }
                else {
                    if (end > 0)
                        Array.Copy(buffer, 0, buffer, 1, end);
                    buffer[0] = buffer[length - 1];
                    if (length - 1 > i)
                        Array.Copy(buffer, i, buffer, i + 1, length - 1 - i);
                    end += 1;
                }
            }

            buffer[i] = item;
            if (start == end)
                IncreaseBuffer();
        }

        /// <summary>
        /// Inserts a collection of items at the given index in the Deque. All items at indexes 
        /// equal to or greater than <paramref name="index"/> increase their indices in the Deque
        /// by the number of items inserted.
        /// </summary>
        /// <remarks>The amount of time to insert a collection in the Deque is proportional
        /// to the distance of index from the closest end of the Deque, plus the number of items
        /// inserted (M): 
        /// O(M + Min(<paramref name="index"/>, Count - <paramref name="index"/>)).
        /// </remarks>
        /// <param name="index">The index in the Deque to insert the collection at. After the
        /// insertion, the first item of the inserted collection is located at this index. The
        /// front item in the Deque has index 0.</param>
        /// <param name="collection">The collection of items to insert at the given index.</param>
        /// <exception cref="ArgumentOutOfRangeException"><paramref name="index"/> is
        /// less than zero or greater than Count.</exception>
        public void InsertRange(int index, IEnumerable<T> collection)
        {
            if (collection == null)
                throw new ArgumentNullException("collection");

            StopEnumerations();

            int count = Count;
            if (index < 0 || index > Count)
                throw new ArgumentOutOfRangeException("index");

            // We need an ICollection, because we need the count of the collection.
            // If needed, copy the items to a temporary list.
            ICollection<T> coll;
            if (collection is ICollection<T>)
                coll = (ICollection<T>) collection;
            else {
                coll = new List<T>(collection);
            }
            if (coll.Count == 0)
                return;          // nothing to do.

            // Create enough capacity in the list for the new items.
            if (Capacity < Count + coll.Count)
                Capacity = Count + coll.Count;

            int length = buffer.Length;
            int s, d;

            if (index < count / 2) {
                // Inserting into the first half of the list. Move items with
                // lower index down in the buffer.
                s = start;
                d = s - coll.Count;
                if (d < 0)
                    d += length;
                start = d;
                int c = index;

                while (c > 0) {
                    int chunk = c;
                    if (length - d < chunk)
                        chunk = length - d;
                    if (length - s < chunk)
                        chunk = length - s;
                    Array.Copy(buffer, s, buffer, d, chunk);
                    c -= chunk;
                    if ((d += chunk) >= length)
                        d -= length;
                    if ((s += chunk) >= length)
                        s -= length;
                }
            }
            else {
                // Inserting into the last half of the list. Move items with higher
                // index up in the buffer.
                s = end;
                d = s + coll.Count;
                if (d >= length)
                    d -= length;
                end = d;
                int move = count - index;  // number of items at end to move

                int c = move;
                while (c > 0) {
                    int chunk = c;
                    if (d > 0 && d < chunk)
                        chunk = d;
                    if (s > 0 && s < chunk)
                        chunk = s;
                    if ((d -= chunk) < 0)
                        d += length;
                    if ((s -= chunk) < 0)
                        s += length;
                    Array.Copy(buffer, s, buffer, d, chunk);
                    c -= chunk;
                }

                d -= coll.Count;
                if (d < 0)
                    d += length;
            }

            // Copy the items into the space vacated, which starts at d.
            foreach (T item in coll) {
                buffer[d] = item;
                if (++d >= length)
                    d -= length;
            }
        }

        /// <summary>
        /// Removes the item at the given index in the Deque. All items at indexes 
        /// greater than <paramref name="index"/> move down one index
        /// in the Deque.
        /// </summary>
        /// <remarks>The amount of time to delete 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 - 1 - <paramref name="index"/>)).
        /// Thus, deleting an item at the front or end of the Deque is always fast; the middle of
        /// of the Deque is the slowest place to delete.
        /// </remarks>
        /// <param name="index">The index in the list to remove the item at. The
        /// first item in the list has index 0.</param>
        /// <exception cref="ArgumentOutOfRangeException"><paramref name="index"/> is
        /// less than zero or greater than or equal to Count.</exception>
        public sealed override void RemoveAt(int index)
        {
            StopEnumerations();

            int count = Count;

            if (index < 0 || index >= count)
                throw new ArgumentOutOfRangeException("index");

            int length = buffer.Length;
            int i; // index of removed item
            if (index < count / 2) {
                // Removing in the first half of the list. Move items with
                // lower index up in the buffer.
                i = index + start;

                if (i >= length) {
                    i -= length;

                    if (i > 0)
                        Array.Copy(buffer, 0, buffer, 1, i);
                    buffer[0] = buffer[length - 1];   
                    if (length - 1 > start)
                        Array.Copy(buffer, start, buffer, start + 1, length - 1 - start);
                }
                else {
                    if (i > start)
                        Array.Copy(buffer, start, buffer, start + 1, i - start);
                }

                buffer[start] = default(T);
                start += 1;
                if (start >= length)
                    start -= length;
            }
            else {
                // Removing in the second half of the list. Move items with
                // higher indexes down in the buffer.
                i = index + start;
                if (i >= length)
                    i -= length;
                end -= 1;
                if (end < 0)
                    end = length - 1;

                if (i <= end) {
                    if (end > i)
                        Array.Copy(buffer, i + 1, buffer, i, end - i);
                }
                else {
                    if (length - 1 > i)
                        Array.Copy(buffer, i + 1, buffer, i, length - 1 - i);
                    buffer[length - 1] = buffer[0];  
                    if (end > 0)
                        Array.Copy(buffer, 1, buffer, 0, end);
                }

                buffer[end] = default(T);
            }
        }

        /// <summary>
        /// Removes a range of items at the given index in the Deque. All items at indexes 
        /// greater than <paramref name="index"/> move down <paramref name="count"/> indices
        /// in the Deque.
        /// </summary>
        /// <remarks>The amount of time to delete <paramref name="count"/> items in the Deque is proportional
        /// to the distance to the closest end of the Deque: 
        /// O(Min(<paramref name="index"/>, Count - <paramref name="index"/> - <paramref name="count"/>)).
        /// </remarks>
        /// <param name="index">The index in the list to remove the range at. The
        /// first item in the list has index 0.</param>
        /// <param name="count">The number of items to remove.</param>
        /// <exception cref="ArgumentOutOfRangeException"><paramref name="index"/> is
        /// less than zero or greater than or equal to Count, or <paramref name="count"/> is less than zero
        /// or too large.</exception>
        public void RemoveRange(int index, int count)
        {
            StopEnumerations();

            int dequeCount = Count;

            if (index < 0 || index >= dequeCount)
                throw new ArgumentOutOfRangeException("index");
            if (count < 0 || count > dequeCount - index)
                throw new ArgumentOutOfRangeException("count");
            if (count == 0)
                return;

            int length = buffer.Length;
            int s, d;
            if (index < dequeCount / 2) {
                // Removing in the first half of the list. Move items with
                // lower index up in the buffer.
                s = start + index;
                if (s >= length)
                    s -= length;
                d = s + count;
                if (d >= length)
                    d -= length;

                int c = index;
                while (c > 0) {
                    int chunk = c;
                    if (d > 0 && d < chunk)
                        chunk = d;
                    if (s > 0 && s < chunk)
                        chunk = s;
                    if ((d -= chunk) < 0)
                        d += length;
                    if ((s -= chunk) < 0)
                        s += length;
                    Array.Copy(buffer, s, buffer, d, chunk);
                    c -= chunk;
                }

                // At this point, s == start
                for (c = 0; c < count; ++c) {
                    buffer[s] = default(T);
                    if (++s >= length)
                        s -= length;
                }
                start = s;
            }
            else {
                // Removing in the second half of the list. Move items with
                // higher indexes down in the buffer.
                int move = dequeCount - index - count;
                s = end - move;
                if (s < 0)
                    s += length;
                d = s - count;
                if (d < 0)