deque.cs

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

                    d += length;

                int c = move;
                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;
                }

                // At this point, s == end.
                for (c = 0; c < count; ++c) {
                    if (--s < 0)
                        s += length;
                    buffer[s] = default(T);
                }
                end = s;
            }
        }

        /// <summary>
        /// Increase the amount of buffer space. When calling this method, the Deque
        /// must not be empty. If start and end are equal, that indicates a completely
        /// full Deque.
        /// </summary>
        private void IncreaseBuffer()
        {
            int count = Count;
            int length = buffer.Length;

            T[] newBuffer = new T[length * 2];
            if (start >= end) {
                Array.Copy(buffer, start, newBuffer, 0, length - start);
                Array.Copy(buffer, 0, newBuffer, length - start, end);
                end = end + length - start;
                start = 0;
            }
            else {
                Array.Copy(buffer, start, newBuffer, 0, end - start);
                end = end - start;
                start = 0;
            }

            buffer = newBuffer;
        }

        /// <summary>
        /// Adds an item to the front of the Deque. The indices of all existing items
        /// in the Deque are increased by 1. This method is 
        /// equivalent to <c>Insert(0, item)</c> but is a little more
        /// efficient.
        /// </summary>
        /// <remarks>Adding an item to the front of the Deque takes
        /// a small constant amount of time, regardless of how many items are in the Deque.</remarks>
        /// <param name="item">The item to add.</param>
        public void AddToFront(T item)
        {
            StopEnumerations();

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

            if (--start < 0)
                start += buffer.Length;
            buffer[start] = item;
            if (start == end)
                IncreaseBuffer();
        }

        /// <summary>
        /// Adds a collection of items to the front of the Deque. The indices of all existing items
        /// in the Deque are increased by the number of items inserted. The first item in the added collection becomes the
        /// first item in the Deque. 
        /// </summary>
        /// <remarks>This method takes time O(M), where M is the number of items in the 
        /// <paramref name="collection"/>.</remarks>
        /// <param name="collection">The collection of items to add.</param>
        public void AddManyToFront(IEnumerable<T> collection)
        {
            if (collection == null)
                throw new ArgumentNullException("collection");

            InsertRange(0, collection);
        }

        /// <summary>
        /// Adds an item to the back of the Deque. The indices of all existing items
        /// in the Deque are unchanged. This method is 
        /// equivalent to <c>Insert(Count, item)</c> but is a little more
        /// efficient.
        /// </summary>
        /// <remarks>Adding an item to the back of the Deque takes
        /// a small constant amount of time, regardless of how many items are in the Deque.</remarks>
        /// <param name="item">The item to add.</param>
        public void AddToBack(T item)
        {
            StopEnumerations();

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

            buffer[end] = item;
            if (++end >= buffer.Length)
                end -= buffer.Length;
            if (start == end)
                IncreaseBuffer();
        }

        /// <summary>
        /// Adds an item to the back of the Deque. The indices of all existing items
        /// in the Deque are unchanged. This method is 
        /// equivalent to <c>AddToBack(item)</c>.
        /// </summary>
        /// <remarks>Adding an item to the back of the Deque takes
        /// a small constant amount of time, regardless of how many items are in the Deque.</remarks>
        /// <param name="item">The item to add.</param>
        public sealed override void Add(T item)
        {
            AddToBack(item);
        }


        /// <summary>
        /// Adds a collection of items to the back of the Deque. The indices of all existing items
        /// in the Deque are unchanged. The last item in the added collection becomes the
        /// last item in the Deque.
        /// </summary>
        /// <remarks>This method takes time O(M), where M is the number of items in the 
        /// <paramref name="collection"/>.</remarks>
        /// <param name="collection">The collection of item to add.</param>
        public void AddManyToBack(IEnumerable<T> collection)
        {
            if (collection == null)
                throw new ArgumentNullException("collection");

            foreach (T item in collection)
                AddToBack(item);
        }

        /// <summary>
        /// Removes an item from the front of the Deque. The indices of all existing items
        /// in the Deque are decreased by 1. This method is 
        /// equivalent to <c>RemoveAt(0)</c> but is a little more
        /// efficient.
        /// </summary>
        /// <remarks>Removing an item from the front of the Deque takes
        /// a small constant amount of time, regardless of how many items are in the Deque.</remarks>
        /// <returns>The item that was removed.</returns>
        /// <exception cref="InvalidOperationException">The Deque is empty.</exception>
        public T RemoveFromFront()
        {
            if (start == end)
                throw new InvalidOperationException(Strings.CollectionIsEmpty);

            StopEnumerations();

            T item = buffer[start];
            buffer[start] = default(T);
            if (++start >= buffer.Length)
                start -= buffer.Length;
            return item;
        }

        /// <summary>
        /// Removes an item from the back of the Deque. The indices of all existing items
        /// in the Deque are unchanged. This method is 
        /// equivalent to <c>RemoveAt(Count-1)</c> but is a little more
        /// efficient.
        /// </summary>
        /// <remarks>Removing an item from the back of the Deque takes
        /// a small constant amount of time, regardless of how many items are in the Deque.</remarks>
        /// <exception cref="InvalidOperationException">The Deque is empty.</exception>
        public T RemoveFromBack()
        {
            if (start == end)
                throw new InvalidOperationException(Strings.CollectionIsEmpty);

            StopEnumerations();

            if (--end < 0)
                end += buffer.Length;
            T item = buffer[end];
            buffer[end] = default(T);
            return item;
        }

        /// <summary>
        /// Retreives the item currently at the front of the Deque. The Deque is 
        /// unchanged. This method is 
        /// equivalent to <c>deque[0]</c> (except that a different exception is thrown).
        /// </summary>
        /// <remarks>Retreiving the item at the front of the Deque takes
        /// a small constant amount of time, regardless of how many items are in the Deque.</remarks>
        /// <returns>The item at the front of the Deque.</returns>
        /// <exception cref="InvalidOperationException">The Deque is empty.</exception>
        public T GetAtFront()
        {
            if (start == end)
                throw new InvalidOperationException(Strings.CollectionIsEmpty);

            return buffer[start];
        }

        /// <summary>
        /// Retreives the item currently at the back of the Deque. The Deque is 
        /// unchanged. This method is 
        /// equivalent to <c>deque[deque.Count - 1]</c> (except that a different exception is thrown).
        /// </summary>
        /// <remarks>Retreiving the item at the back of the Deque takes
        /// a small constant amount of time, regardless of how many items are in the Deque.</remarks>
        /// <returns>The item at the back of the Deque.</returns>
        /// <exception cref="InvalidOperationException">The Deque is empty.</exception>
        public T GetAtBack()
        {
            if (start == end)
                throw new InvalidOperationException(Strings.CollectionIsEmpty);

            if (end == 0)
                return buffer[buffer.Length - 1];
            else
                return buffer[end - 1];
        }

        /// <summary>
        /// Creates a new Deque that is a copy of this one.
        /// </summary>
        /// <remarks>Copying a Deque takes O(N) time, where N is the number of items in this Deque..</remarks>
        /// <returns>A copy of the current deque.</returns>
        public Deque<T> Clone()
        {
            return new Deque<T>(this);
        }

        /// <summary>
        /// Creates a new Deque that is a copy of this one.
        /// </summary>
        /// <remarks>Copying a Deque takes O(N) time, where N is the number of items in this Deque..</remarks>
        /// <returns>A copy of the current deque.</returns>
        object ICloneable.Clone()
        {
            return this.Clone();
        }

        /// <summary>
        /// Makes a deep clone of this Deque. A new Deque is created with a clone of
        /// each element of this set, by calling ICloneable.Clone on each element. If T is
        /// a value type, then each element is copied as if by simple assignment.
        /// </summary>
        /// <remarks><para>If T is a reference type, it must implement
        /// ICloneable. Otherwise, an InvalidOperationException is thrown.</para>
        /// <para>Cloning the Deque takes time O(N), where N is the number of items in the Deque.</para></remarks>
        /// <returns>The cloned Deque.</returns>
        /// <exception cref="InvalidOperationException">T is a reference type that does not implement ICloneable.</exception>
        public Deque<T> CloneContents()
        {
            bool itemIsValueType;
            if (!Util.IsCloneableType(typeof(T), out itemIsValueType))
                throw new InvalidOperationException(string.Format(Strings.TypeNotCloneable, typeof(T).FullName));

            Deque<T> clone = new Deque<T>();

            // Clone each item, and add it to the new ordered set.
            foreach (T item in this) {
                T itemClone;

                if (itemIsValueType)
                    itemClone = item;
                else {
                    if (item == null)
                        itemClone = default(T);    // Really null, because we know T is a reference type
                    else
                        itemClone = (T)(((ICloneable)item).Clone());
                }

                clone.AddToBack(itemClone);
            }

            return clone;
        }

#if DEBUG
        /// <summary>
        /// Print out the internal state of the Deque for debugging.
        /// </summary>
        internal void Print()
        {
            Console.WriteLine("length={0}  start={1}  end={2}", buffer.Length, start, end);
            for (int i = 0; i < buffer.Length; ++i) {
                if (i == start)
                    Console.Write("start-> ");
                else
                    Console.Write("        ");
                if (i == end)
                    Console.Write("end-> ");
                else
                    Console.Write("      ");
                Console.WriteLine("{0,4} {1}", i, buffer[i]);
            }
            Console.WriteLine();
        }
#endif // DEBUG
    }
}