namespace System.Collections.Generic
{
    using System.Linq;

    public sealed class CircularBuffer<TItem> : IList<TItem>, ICollection<TItem>, IEnumerable<TItem>
    {
        private int count = 0;
        private int offset = 0;

        private readonly TItem[] buffer;
        public CircularBuffer(int size)
        {
            buffer = new TItem[size];
        }

        public TItem Add(TItem item)
        {
            var index = (count + offset) % buffer.Length;
            var old = buffer[index];
            buffer[index] = item;
            if (count < buffer.Length) { ++count; old = default(TItem); }
            else offset = (offset + 1) % buffer.Length;
            return old;
        }

        public TItem Pop()
        {
            var item = Top();
            Drop();
            return item;
        }

        public TItem Top()
        {
            if (count == 0) throw new InvalidOperationException("The collection is empty");
            var index = (count + offset - 1) % buffer.Length;
            return buffer[index];
        }

        public void Drop()
        {
            if (count > 0) { --count; return; }
            throw new InvalidOperationException("The collection is empty");
        }

        public int Count { get { return count; } }

        public bool IsReadOnly { get { return false; } }

        public TItem this[int index]
        {
            get
            {
                if (index < 0 || index >= buffer.Length)
                    throw new IndexOutOfRangeException("Index is out of range");
                if (index >= count) return default(TItem);
                var pos = (offset + index) % buffer.Length;
                return buffer[pos];
            }

            set
            {
                if (index < 0 || index >= buffer.Length)
                    throw new IndexOutOfRangeException("Index is out of range");
                var pos = (offset + index) % buffer.Length;
                count = Math.Max(count, index + 1);
                buffer[pos] = value;
            }
        }

        public IEnumerator<TItem> GetEnumerator()
        {
            for (int i = 0; i < count; ++i)
            {
                var index = (offset + i) % buffer.Length;
                if (index >= 0) yield return buffer[index];
            }
        }

        IEnumerator IEnumerable.GetEnumerator()
        {
            return this.GetEnumerator();
        }

        void ICollection<TItem>.Add(TItem item)
        {
            this.Add(item);
        }

        public void Clear()
        {
            count = 0;
            offset = 0;
        }

        public bool Contains(TItem item)
        {
            return IndexOf(item) >= 0;
        }

        public void CopyTo(TItem[] array, int offset)
        {
            var index = 0;
            foreach (var item in this)
            {
                array[offset + index] = item;
                ++index;
            }
        }

        public bool Remove(TItem item)
        {
            var index = IndexOf(item);
            if (index >= 0) RemoveAt(index);
            return index >= 0;
        }

        public int IndexOf(TItem item)
        {
            var comparer = EqualityComparer<TItem>.Default;
            return this.Select((e, i) => comparer.Equals(e, item) ? i : -1)
                .Where(i => i > 0).Take(1).DefaultIfEmpty(-1).SingleOrDefault();
        }

        public void Insert(int index, TItem item)
        {
            if (index < 0 || index >= buffer.Length)
                throw new IndexOutOfRangeException("Index is out of range");

            var prev = item;
            for (int i = index + 1; i <= count; ++i)
            {
                var pos = (offset + i) % buffer.Length;
                if (pos >= buffer.Length) break;
                var tmp = buffer[pos];
                buffer[pos] = prev;
                prev = tmp;
            }

            if (count < buffer.Length) ++count;
            else offset = (offset + 1) % buffer.Length;
        }

        public void RemoveAt(int index)
        {
            if (index < 0 || index >= count)
                throw new IndexOutOfRangeException("Index is out of range");

            --count;
            for (int i = index; i <= count; ++i)
            {
                var pos = (offset + i) % buffer.Length;
                buffer[pos] = buffer[pos + 1];
            }
        }
    }
}