Specialized Queues - A Cyclic Queue

using System;
using System.Collections;

namespace DataStructures
{
    /// <summary>
    /// A CyclicQueue is a queue with a fixed size. It is called 'cyclic' because when
    /// and item is added to a full queue, the 'oldest' item in the queue is removed to
    /// free space for the new item (so the internal buffer can be regarded as a cyclic
    /// buffer).
    /// 
    /// The CyclicQueue provides all the functionalities of the System.Collections.Queue,
    /// except for the limit on the buffer size and the behavior it imposes.
    /// 
    /// Note: This implementation does not support wrap-around of the internal indexes.
    /// In other words, if you plan to call Enqueue more than int.MaxValue times, the
    /// behavior is undefined and the code will most probably break.
    /// </summary>
    [Serializable]
    public class CyclicQueue : Queue
    {
        #region Member Variables

        private int version = 0; // used to avoid enumeration of altered queues
        private int tailIndex = -1; // index of the last inserted item
        private int headIndex = -1; // index of the last extracted item
        private object[] buffer; // the actual buffer that holds the items

        #endregion Member Variables

        #region Constructors

        /// <summary>Creates a new CyclicQueue object with the given size.</summary>
        public CyclicQueue(int bufferSize)
        {
            if (bufferSize <= 0)
            {
                throw new ArgumentOutOfRangeException("bufferSize", bufferSize, "The buffer size must be a positive value.");
            }
            buffer = new object[bufferSize];
        }

        #endregion

        #region Queue Overridden Methods and Properties

        /// <summary>Removes all objects from the CyclicQueue.</summary>
        public override void Clear()
        {
            version++;
            buffer = new object[buffer.Length];
            headIndex = -1;
            tailIndex = -1;
        }

        /// <summary>Determines whether an element is in the CyclicQueue.</summary>
        public override bool Contains(object obj)
        {
            foreach (object o in buffer)
            {
                if (obj == null)
                {
                    if (o == null)
                    {
                        return true;
                    }
                }
                else if (obj.Equals(o))
                {
                    return true;
                }
            }
            return false;
        }

        /// <summary>Removes and returns the object at the beginning of the CyclicQueue.</summary>
        public override object Dequeue()
        {
            if (this.Count == 0)
            {
                throw new InvalidOperationException("Cannot dequeue an empty queue");
            }

            version++;
            headIndex++;
            object obj = buffer[headIndex%buffer.Length];
            return obj;
        }

        /// <summary>
        /// Adds the given object to the end of the CyclicQueue. If the CyclicQueue is full
        /// the object at the beginning of the CyclicQueue is removed prior to adding the
        /// given object to the CyclicQueue.
        /// </summary>
        public override void Enqueue(object obj)
        {
            if (tailIndex - headIndex == buffer.Length)
            {
                // The buffer is full - we have to drop the oldest object (in head)
                Dequeue();
            }
            version++; // TODO: Check that this is necessary and that it doesn't cause problem with the synchronized Q
            tailIndex++;
            buffer[tailIndex%buffer.Length] = obj;
        }

        /// <summary>Returns the object at the beginning of the CyclicQueue without removing it.</summary>
        public override object Peek()
        {
            if (this.Count == 0)
            {
                throw new InvalidOperationException("Cannot peek an empty queue");
            }

            return buffer[(headIndex + 1)%buffer.Length];
        }

        /// <summary>Copies the CyclicQueue elements to a new array.</summary>
        public override object[] ToArray()
        {
            object[] objs = new object[this.Count];
            if (this.Count > 0)
            {
                this.CopyTo(objs, 0);
            }
            return objs;
        }

        /// <summary>
        /// Sets the capacity to the actual number of elements in the CyclicQueue. After this method is
        /// called the buffer's size may have been decreased, and adding additional items to the CyclicQueue
        /// will cause the removal of the items at the beginning of the CyclicQueue.
        /// </summary>
        public override void TrimToSize()
        {
            version++;
            object[] newBuffer = this.ToArray();
            buffer = newBuffer;
        }

        #region ICollection Members

        /// <summary>Gets a value indicating whether access to the CyclicQueue is synchronized (thread-safe).</summary>
        public override bool IsSynchronized
        {
            get { return false; }
        }

        /// <summary>Gets the number of elements contained in the CyclicQueue.</summary>
        public override int Count
        {
            get { return tailIndex - headIndex; }
        }

        /// <summary>
        /// Copies the CyclicQueue elements to an existing one-dimensional Array, starting at the specified array index.
        /// </summary>
        public override void CopyTo(Array array, int index)
        {
            if (array == null)
            {
                throw new ArgumentNullException("array");
            }
            if (array.Rank != 1)
            {
                throw new ArgumentException("Array rank must be 1", "array");
            }
            if (index < 0)
            {
                throw new ArgumentOutOfRangeException("index", "Array index out of range");
            }
            if ((array.Length - index) < this.Count)
            {
                throw new ArgumentException("Array is too small", "array");
            }

            int arrayIndex = index;
            for (int i = headIndex + 1; i <= tailIndex; i++, arrayIndex++)
            {
                array.SetValue(buffer[i%buffer.Length], arrayIndex); // TODO: Check it works ok
            }
        }

        /// <summary>Gets an object that can be used to synchronize access to the CyclicQueue.</summary>
        public override object SyncRoot
        {
            get { return this; }
        }

        #endregion ICollection Members

        #region IEnumerable Members

        /// <summary>Returns an enumerator that can iterate through the CyclicQueue.</summary>
        public override IEnumerator GetEnumerator()
        {
            return new CyclicQueueEnumerator(this, headIndex + 1, tailIndex);
        }

        #endregion IEnumerable Members

        #region ICloneable Members

        /// <summary>Creates a shallow copy of the CyclicQueue.</summary>
        public override object Clone()
        {
            CyclicQueue cyclicQueue = new CyclicQueue(buffer.Length);
            Array.Copy(buffer, 0, cyclicQueue.buffer, 0, buffer.Length);
            cyclicQueue.version = this.version;
            cyclicQueue.headIndex = this.headIndex;
            cyclicQueue.tailIndex = this.tailIndex;
            return cyclicQueue;
        }

        #endregion ICloneable Members

        #endregion Queue Overridden Methods and Properties

        #region Static Methods

        /// <summary>Returns a CyclicQueue wrapper that is synchronized (thread-safe).</summary>
        public static CyclicQueue Synchronized(CyclicQueue cyclicQueue)
        {
            if (cyclicQueue == null)
            {
                throw new ArgumentNullException("cyclicQueue");
            }
            return new SynchronizedCyclicQueue(cyclicQueue);
        }

        #endregion Static Methods

        #region Enumerator Implementation

        /// <summary>
        /// A helper class that provides enumeration capabilities on a CyclicQueue.
        /// Any enumeration operation (Current, MoveNext) will fail (i.e. cause an exception)
        /// if the CyclicQueue has been altered.
        /// </summary>
        [Serializable]
        private class CyclicQueueEnumerator : IEnumerator, ICloneable
        {
            #region Member Variables

            private CyclicQueue cyclicQueue;
            private int index;
            // Keeps track of the original version to know whether the CyclicQueue was altered
            private readonly int version;
            // The startIndex and endIndex members make it possible to iterate over a portion (range)
            // of the CyclicQueue.
            private readonly int startIndex;
            private readonly int endIndex;

            #endregion Member Variables

            #region Constructors

            internal CyclicQueueEnumerator(CyclicQueue cyclicQueue, int startIndex, int endIndex)
            {
                this.cyclicQueue = cyclicQueue;
                this.index = startIndex - 1;
                this.version = cyclicQueue.version;
                this.startIndex = startIndex;
                this.endIndex = Math.Min(endIndex, cyclicQueue.tailIndex);
            }

            #endregion Constructors

            #region IEnumerator Members

            public void Reset()
            {
                index = startIndex - 1;
            }

            public object Current
            {
                get
                {
                    if (version != cyclicQueue.version)
                    {
                        throw new InvalidOperationException("Enumerator was changed!");
                    }

                    if ((index < startIndex) || (index > endIndex))
                    {
                        throw new InvalidOperationException("Enumerator out of bounds");
                    }

                    return cyclicQueue.buffer[index%cyclicQueue.buffer.Length];
                }
            }

            public bool MoveNext()
            {
                if (version != cyclicQueue.version)
                {
                    throw new InvalidOperationException("Enumerator was changed!");
                }

                index++;
                return (index <= endIndex);
            }

            #endregion

            #region ICloneable Members

            public object Clone()
            {
                return base.MemberwiseClone();
            }

            #endregion
        }

        #endregion Enumerator Implementation

        #region Synchronization Implementation

        /// <summary>
        /// A helper class that provides synchronization capabilities on a CyclicQueue.
        /// Any operation on the SynchronizedCyclicQueue is thread-safe.
        /// </summary>
        [Serializable]
        private class SynchronizedCyclicQueue : CyclicQueue
        {
            #region Member Variables

            private CyclicQueue cyclicQueue;
            private object syncRoot;

            #endregion Member Variables

            #region Constructors

            internal SynchronizedCyclicQueue(CyclicQueue cyclicQueue) : base(1)
            {
                syncRoot = new object();
                this.cyclicQueue = cyclicQueue;
            }

            #endregion Constructors

            #region Overridden Methods and Properties

            public override object SyncRoot
            {
                get { return syncRoot; }
            }

            public override int Count
            {
                get
                {
                    lock (syncRoot)
                    {
                        return cyclicQueue.Count;
                    }
                }
            }

            public override bool IsSynchronized
            {
                get { return true; }
            }

            public override object Clone()
            {
                object obj = null;
                lock (syncRoot)
                {
                    obj = new SynchronizedCyclicQueue((CyclicQueue) this.cyclicQueue.Clone());
                }
                return obj;
            }

            public override void Clear()
            {
                lock (syncRoot)
                {
                    cyclicQueue.Clear();
                }
            }

            public override bool Contains(object obj)
            {
                bool contains;
                lock (syncRoot)
                {
                    contains = cyclicQueue.Contains(obj);
                }
                return contains;
            }

            public override object Dequeue()
            {
                object obj;
                lock (syncRoot)
                {
                    obj = cyclicQueue.Dequeue();
                }
                return obj;
            }

            public override void Enqueue(object obj)
            {
                lock (syncRoot)
                {
                    cyclicQueue.Enqueue(obj);
                }
            }

            public override object Peek()
            {
                object obj;
                lock (syncRoot)
                {
                    obj = cyclicQueue.Peek();
                }
                return obj;
            }

            public override object[] ToArray()
            {
                object[] array;
                lock (syncRoot)
                {
                    array = cyclicQueue.ToArray();
                }
                return array;
            }

            public override void TrimToSize()
            {
                lock (syncRoot)
                {
                    cyclicQueue.TrimToSize();
                }
            }

            public override void CopyTo(Array array, int index)
            {
                lock (syncRoot)
                {
                    cyclicQueue.CopyTo(array, index);
                }
            }

            public override IEnumerator GetEnumerator()
            {
                IEnumerator enumerator;
                lock (syncRoot)
                {
                    enumerator = cyclicQueue.GetEnumerator();
                }
                return enumerator;
            }

            #endregion Overridden Methods and Properties
        }

        #endregion Synchronization Implementation
    }
}