RoundStack Implementation

Question

I just recently made an attempt at implementing what I have been led to understand is called a RoundStack, simply meaning contrary to .NET Stack's default behavior of doubling internal array size when it hits capacity, simply starts dropping off items at the bottom of the stack. I am developing this class for the purpose of facilitating an undo/redo system. I wanted to make this compliant with the functionality the default .NET stack has, and thus borrowed several pieces of code from the .NET reference source, only modifying where absolutely necessary to facilitate the round-robin pushing.

I have written several test in NUnit and the collection is working as intended. Now looking for any comments as to whether I implemented this properly and in the most efficient way.

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Schloss.Collections.Generic
{
[Serializable]
public class RoundStack<T> : IEnumerable<T>, ICollection, IEnumerable
{
    private T[] _items; // items.Length is Capacity + 1
    private int _size;
    private int _version;

    // if top is equal to bottom, stack is full
    private int _top = 1;
    private int _bottom = 0;

    private Object _syncRoot;

    private const int _defaultCapacity = 4;
    static T[] _emptyArray = new T[0];

    public RoundStack()
    {
        _items =_emptyArray;
        _size = 0;
        _version = 0;
    }

    public RoundStack(int capacity)
    {
        if (capacity < 1)
            throw new ArgumentOutOfRangeException("Capacity must be at least one.");
        _items = new T[capacity + 1];
        _size = 0;
        _version = 0;
    }

    public RoundStack(IEnumerable<T> collection)
    {
        if (collection == null)
            throw new ArgumentNullException("Cannot create from a null collection.");

        // borrowed from .NET Reference code for System.Collections.Generic.Stack<T>
        ICollection<T> c = collection as ICollection<T>;
        if (c != null)
        {
            int count = c.Count;
            _items = new T[count];
            c.CopyTo(_items, 0);
            _size = count;
        }
        else
        {
            _size = 0;
            _top = 1;
            _bottom = 0;
            _items = new T[_defaultCapacity];

            using (IEnumerator<T> en = collection.GetEnumerator())
            {
                while (en.MoveNext())
                {
                    Push(en.Current);
                }
            }
        }
    }

    public bool IsFull
    {
        get
        {
            return _top == _bottom;
        }
    }

    public int Count
    {
        get
        {
            _size = _top - _bottom - 1;
            if (_size < 0)
                _size += _items.Length;
            return _size;
        }
    }

    bool ICollection.IsSynchronized { get { return false; } }
    Object ICollection.SyncRoot
    {
        get
        {
            if (_syncRoot == null)
            {
                System.Threading.Interlocked.CompareExchange<Object>(ref _syncRoot, new Object(), null);
            }
            return _syncRoot;
        }
    }

    public int Capacity
    {
        get
        {
            return _items.Length - 1;
        }
    }

    public void Clear()
    {
        Array.Clear(_items, 0, Count);
        _size = 0;
        _top = 1;
        _bottom = 0;
        _version++;
    }

    public bool Contains(T item)
    {
        // borrowed from .NET reference
        int count = _size;

        EqualityComparer<T> c = EqualityComparer<T>.Default;
        while (count-- > 0)
        {
            if (((Object)item) == null)
            {
                if (((Object)_items[count]) == null)
                    return true;
            }
            else if (_items[count] != null && c.Equals(_items[count], item))
            {
                return true;
            }
        }
        return false;
    }

    public void CopyTo(T[] array, int arrayIndex)
    {

    }

    void ICollection.CopyTo(Array array, int arrayIndex)
    {

    }

    public Enumerator GetEnumerator()
    {
        return new Enumerator(this);
    }

    IEnumerator<T> IEnumerable<T>.GetEnumerator()
    {
        return new Enumerator(this);
    }

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

    public T Peek()
    {
        if (Count == 0)
            throw new InvalidOperationException("Cannot peek at an empty stack.");

        return _items[_top];
    }

    public T Pop()
    {
        if (Count == 0)
            throw new InvalidOperationException("Cannot pop from an empty stack.");

        _version++;
        T removed = _items[_top];
        _items[_top--] = default(T);
        if (_top < 0)
            _top += _items.Length;
        return removed;
    }

    public void Push (T item)
    {
        if (IsFull)
        {
            _bottom++;
            if (_bottom >= _items.Length)
                _bottom -= _items.Length;
        }
        if (++_top >= _items.Length)
            _top -= _items.Length;
        _items[_top] = item;
        _version++;
    }

    public T[] ToArray()
    {
        T[] objArray = new T[Count];
        int i = 0;
        while (i < Count)
        {
            objArray[i] = _items[Count - i - 1];
            i++;
        }
        return objArray;
    }

    public void TrimExcess()
    {
        int threshold = (int)(((double)_items.Length) * 0.9);
        if (Count < threshold)
        {
            T[] newarray = new T[Count];
            Array.Copy(_items, 0, newarray, 0, Count);
            _items = newarray;
            _version++;
        }
    }

    [Serializable]
    public struct Enumerator : IEnumerator<T>, IDisposable, IEnumerator
    {
        private RoundStack<T> _stack;
        private int _index;
        private int _version;
        private T currentElement;

        internal Enumerator(RoundStack<T> stack)
        {
            _stack = stack;
            _version = _stack._version;
            _index = -2;
            currentElement = default(T);
        }

        public void Dispose()
        {
            _index = -1;
        }

        public bool MoveNext()
        {
            // borrowed from .NET reference
            bool retval;
            if (_version != _stack._version)
                throw new InvalidOperationException("Enumerator failed version check against round stack version.");
            if (_index == -2)
            {  // First call to enumerator.
                _index = _stack._size - 1;
                retval = (_index >= 0);
                if (retval)
                    currentElement = _stack._items[_index];
                return retval;
            }
            if (_index == -1)
            {  // End of enumeration.
                return false;
            }

            retval = (--_index >= 0);
            if (retval)
                currentElement = _stack._items[_index];
            else
                currentElement = default(T);
            return retval;
        }

        public T Current
        {
            get
            {
                if (_index == -2)
                    throw new InvalidOperationException("Enumerator not started.");
                if (_index == -1)
                    throw new InvalidOperationException("Enumerator ended.");
                return currentElement;
            }
        }

        Object IEnumerator.Current
        {
            get
            {
                if (_index == -2)
                    throw new InvalidOperationException("Enumerator not started.");
                if (_index == -1)
                    throw new InvalidOperationException("Enumerator ended.");
                return currentElement;
            }
        }

        void IEnumerator.Reset()
        {
            if (_version != _stack._version)
                throw new InvalidOperationException("Enumerator failed version check against round stack version.");
            _index = -2;
            currentElement = default(T);
        }
    }
}
}

Mat's Mug · Accepted Answer · 2015-01-20 14:41:26Z

I like the exceptions you're throwing in your guard clauses, you're throwing exception types the client code would rightfully expect in these circumstances.

Vertical whitespace isn't consistent though. I like this:

    if (collection == null)
        throw new ArgumentNullException("Cannot create from a null collection.");

    // borrowed from .NET Reference code for System.Collections.Generic.Stack<T>
    ICollection<T> c = collection as ICollection<T>;

But for consistency this one should also have an empty line after the guard clause:

    if (capacity < 1)
        throw new ArgumentOutOfRangeException("Capacity must be at least one.");
    _items = new T[capacity + 1];

You're not very consistent either with one-liner scope braces - you omit them in guard clauses (which is fine IMO), but then there's this:

        if (_size < 0)
            _size += _items.Length;

And then that:

        if (_syncRoot == null)
        {
            System.Threading.Interlocked.CompareExchange<Object>(ref _syncRoot, new Object(), null);
        }

As a maintainer I would much rather like to see all scopes properly enclosed in curly braces.

    // borrowed from .NET reference
    int count = _size;

That's not really a useful comment. This would be more useful:

    // thread-local copy:
    int count = _size;

In the event that item is a value type, this would be boxing it:

    if (((Object)item) == null)

One of the advantages of generics, is that boxing becomes avoidable, since you have a way of knowing whether T is a value or a reference type. Why not leverage this knowledge?

In fact, the whole Contains implementation smells:

        if (((Object)item) == null)
        {
            if (((Object)_items[count]) == null)
                return true;
        }
        else if (_items[count] != null && c.Equals(_items[count], item))
        {
            return true;
        }

Can be simplified to:

        if ((object)item == null && (object)_items[count] == null)
        {
            return true;
        }
        else if (_items[count] != null && c.Equals(_items[count], item))
        {
            return true;
        }

And that still smells... but contracting the conditions any further would definitely hinder readability.

Notice I replaced Object with object - object is a language alias for System.Object (which you are using). For consistency's sake, if you're going to be using C# aliases for CLR types (object, int, string, ...), then use aliases throughout the code. Or don't, and use the CLR types everywhere (Object, Int32, String, ...).

This is MASSIVE overkill:

        using (IEnumerator<T> en = collection.GetEnumerator())
        {
            while (en.MoveNext())
            {
                Push(en.Current);
            }
        }

You know that collection is an IEnumerable<T> - why not just iterate it with a more casual-looking foreach loop?

        foreach(var item in collection)
        {
            Push(item);
        }

I would have never guessed the overkill, that code is taken straight for the .NET implementation of Stack<T>. Implementing these changes, great advice I very much appreciate it. — Tyler James Harden, Jan 20 '15 at 13:40
@Tyler you were probably looking at decompiled code... that said we usually review original code that OP has written - posting other people's code for review isn't the purpose of this site ;) — Mat's Mug♦, Jan 20 '15 at 14:35
The RoundStack implementation is my own. And my implementations are not entirely 1:1 copies of the .NET reference, but I did follow them heavily as a guideline. I can confidently say the code is my own. I wrote the RoundStack to solve a problem I had with an undo/redo stack that I wanted to limit the capacity of and simply drop off the oldest (bottom-most) entries once that limit is hit. As it has some things in common with the default Stack<T>, no reason to reinvent the wheel on some of the functions. — Tyler James Harden, Jan 20 '15 at 14:38
You might consider rolling back your revision 2 after I have applied a rollback to the question. — Vogel612, Jan 24 '15 at 19:40

asked	1 year ago
viewed	222 times
active	1 year ago

current community

your communities

more stack exchange communities

RoundStack Implementation

1 Answer 1

Your Answer

Not the answer you're looking for? Browse other questions tagged c# .net stack or ask your own question.

Hot Network Questions

current community

your communities

more stack exchange communities

RoundStack Implementation

1 Answer 1

Your Answer

Sign up or log in

Post as a guest

Not the answer you're looking for? Browse other questions tagged c# .net stack or ask your own question.

Related

Hot Network Questions