4
\$\begingroup\$

This is a stack implementation that only retains the last x elements that are added. I have also added an IStack interface to allow alternate stack implementations in the future.

The main use case i had in mind for this data structure was for part of an error loggin system. Where the last x SQL statements want to be stored, in reverse order so the most recent one is at the top. This allows that use case without having to either reverse it later (as a standard queue would have to do), or have to keep shifting an array around as new items are added.

Interface:

public interface IStack<T> : IEnumerable<T>
{
    T this[int index] { get; }
    void Clear();
    bool Contains(T item);
    int Count();
    int Size { get; }
    T Peek();
    T Pop();
    void Push(T item);
}

The rolling fixed size stack implementation. I think that pushing, popping, retrieving the amount of added elements,emptying, and accessing by index are all \$O(1)\$ operations. Iteration and contains are \$O(n)\$ I believe. I am mainly looking for any potential performance improvements, or optimisations that I may have missed. Although any other improvements are welcome.

[Serializable]
public class FixedSizeStack<T> : IStack<T>
{
    private T[] _data;
    private int _pointer;
    private int _count;
    private long _version;

    public FixedSizeStack(int size)
    {
        _data = new T[size];
        _pointer = _data.GetLowerBound(0);
        _version = 0;
    }

    private void _IncrementPointer()
    {
        if (_pointer++ == _data.GetUpperBound(0))
        {
            _pointer = _data.GetLowerBound(0);
        }
    }

    private void _DecrementPointer()
    {
        if (_pointer-- == _data.GetLowerBound(0))
        {
            _pointer = _data.GetUpperBound(0);
        }
    }

    public bool Contains(T item) => _data.Contains(item);
    public int Count() => _count;
    public int Size => _data.Length;
    public void Clear() => _data = new T[Size];

    public T this[int index]
    {
        get
        {
            var i = _pointer - index;
            if (i < 0)
            {
                i += Size;
            }
            return _data[i];
        }
    }

    public T Pop()
    {
        var item = _data[_pointer];
        _data[_pointer] = default(T);
        _DecrementPointer();
        _version++;
        if (_count > _data.GetLowerBound(0))
        {
            _count--;
        }
        return item;
    }

    public void Push(T item)
    {
        _IncrementPointer();
        _data[_pointer] = item;
        _version++;
        if (_count <= _data.GetUpperBound(0))
        {
            _count++;
        }
    }

    public T Peek() => _data[_pointer];

    [Serializable]
    private struct Enumerator : IEnumerator<T>
    {
        private FixedSizeStack<T> _stack;
        private int _index;
        private long _version;
        private T _currentElement;

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

        public void Dispose() => _index = -1;

        public bool MoveNext()
        {
            if (_version != _stack._version)
                throw new InvalidOperationException("Version Conflict");
            if (_index == -2)
            {
                _index = 0;
                var flag = _index >= 0;
                if (flag)
                    _currentElement = _stack[_index];
                return flag;
            }
            if (_index == -1)
                return false;
            var num = _index + 1;
            _index = num;
            var flag1 = num < _stack.Count();
            _currentElement = !flag1 ? default(T) : _stack[_index];
            return flag1;
        }

        public T Current
        {
            get
            {
                if (_index == -2)
                    throw new InvalidOperationException("Enumeration Not Started");
                if (_index == -1)
                    throw new InvalidOperationException("Enumeration Ended");
                return _currentElement;
            }
        }

        object IEnumerator.Current => Current;

        void IEnumerator.Reset()
        {
            if (_version != _stack._version)
                throw new InvalidOperationException("Version Conflict");
            _index = -2;
            _currentElement = default(T);
        }
    }

    public IEnumerator<T> GetEnumerator() => new Enumerator(this);
    IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();
}

Some Clarifications

  1. The _version fields are to stop an enumeration if the underlying data structure changes. This is to prevent potential concurrency issues.
\$\endgroup\$
12
  • \$\begingroup\$ @t3chb0t It is now fixed i believe, wasn't bounds checking the count increment/decrement in the push/pop methods. \$\endgroup\$ – Justinw Dec 15 '17 at 22:26
  • \$\begingroup\$ Indeed, it looks better now and does not crash but... this is a queue ;-) \$\endgroup\$ – t3chb0t Dec 15 '17 at 22:27
  • 1
    \$\begingroup\$ thats why I refered to it as a "Rolling Stack", it might be a weird mixture between queue and stack. It might be better to call it a LIFO Queue? \$\endgroup\$ – Justinw Dec 15 '17 at 22:32
  • 1
    \$\begingroup\$ @t3chb0t since I can now see that the use of something like this might not be obvious, I'll add the use case I had that caused me to write this. \$\endgroup\$ – Justinw Dec 15 '17 at 22:37
  • 1
    \$\begingroup\$ @t3chb0t added some clarification about that \$\endgroup\$ – Justinw Dec 15 '17 at 22:51
5
\$\begingroup\$

You have 2 bugs in your code.

  1. You can create a stack with an invalid size
  2. Enumerating an empty stack produces incorrect behaviour

1 see this example:

var s = new FixedSizeStack<string>(0);
s.Push("a"); // throws 
s.Any(); // throws

You should add a check for your size parameter in the constructor. I don't know why anyone would ever try to create a size 0 stack but you should code defensively regardless.

public FixedSizeStack(int size)
{
    if (size < 1) 
    {
        throw new ArgumentOutOfRangeException(nameof(size));
    }
    _data = new T[size];
    _pointer = _data.GetLowerBound(0);
    _version = 0;
} 

Your second bug is more interesting. Take these examples:

 var s = new FixedSizeStack<string>(1);
 s.Any(); // returns true
 Enumerable.Count(s); // returns 1
 foreach(var a in s)
 {
     // a is null here
 }

As the stack has no elements, I'd expect the count to be 0, .Any to return false and the foreach to enumerate no elements. I appreciate they're all symptoms of the same bug but a useful illustration none the less.

You need to fix your enumerator so that it returns an empty enumerator when the stack is empty.

\$\endgroup\$
1
  • \$\begingroup\$ I have seen the first point with the size but forget to mention it. Missed the second totally. Good catch. \$\endgroup\$ – Heslacher Dec 18 '17 at 11:40
4
\$\begingroup\$

Overall the code in question looks good but there is still room for improvement.

  • Omitting braces {} although they might be optional can lead to hidden and therefor hard to find bugs. I would like to encourage you to always use them. Right now you are mixing your codeing styles. Sometimes you use braces and sometimes you don't. Choose one style and stick to it.

  • Magic numbers like -2 (Enumeration Not Started) or -1 (Enumeration Ended) should be extracted to constants. This would make the code much easier to read. Like so

    private const int EnumerationNotStarted = -2;
    private const int EnumerationEnded = -1;
    public bool MoveNext()
    {
        if (_version != _stack._version) { throw new InvalidOperationException("Version Conflict"); }
    
        if (_index == EnumerationNotStarted)
        {
            _index = 0;
            var flag = _index >= 0;
            if (flag)
                _currentElement = _stack[_index];
            return flag;
        }
    
        if (_index == EnumerationEnded) { return false; }
    
        var num = _index + 1;
        _index = num;
        var flag1 = num < _stack.Count();
        _currentElement = !flag1 ? default(T) : _stack[_index];
        return flag1;
    }
    

    but this method looks strange in itself.
    In the body of the if (_index == EnumerationNotStarted) you are setting _index = 0 and in the next line you are checking if _index >= 0. This should be written like so

    if (_index == EnumerationNotStarted)
    {
        _index = 0;
        _currentElement = _stack[_index];
        return true;
    }
    

    The usage of the ! operator is with bad eyes hard to see. You should maybe reverse the condition of the ternary expression. I don't really see any sense in having the var num. I would write this like so

    _index += 1;
    if (_index < _stack.Count())
    {
        _currentElement = _stack[_index];
        return true;
    }
    _currentElement =  default(T);
    return false;  
    

    Now the code has one more line but IMO it is easier to read. Or alternatively with the ternary like so

    _index += 1;
    var flag = _index < _stack.Count();
    _currentElement = flag ? _stack[_index] : default(T);
    return flag;
    
  • Shouldn't the Clear() method set the _version = 0 ? At least it would be more clear for a reader of the code that he/she doesn't need to care about the _version after calling Clear().

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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