Skip to main content
added custom Enumerator
Source Link
Rick Davin
  • 6.8k
  • 1
  • 20
  • 32

With that saidEDIT

In light of @HenrikHansen 's answer about GetEnumerator, I offer the following modifications:have changed my answer to provide a custom enumerator. I see some discussion between Henrik and @sleptic, so let me add some context.

Microsoft has this to say about Stack.GetEnumerator :

public class StackV1 : IEnumerable
{
    private List<object> list = new List<object>();

    public IEnumerator GetEnumerator()
    {
        // No need for LINQ list.Any() here.
        if (list.Count > 0)
        {
            yield return Pop();
        }
    }

    public object Pop()
    {
        if (list.Count == 0)
        {
            throw new InvalidOperationException("Empty stack.  There is nothing to Pop().");
        }

        // Pop by removing from end of list.
        var index = list.Count - 1;
        var item = list[index];
        list.RemoveAt(index);

        return item;
    }

    public void Push(object item)
    {
        if (item == null)
        {
            throw new InvalidOperationException($"{nameof(item)} is null.  There is nothing to Push().");
        }

        // Push by adding to end of list.
        list.Add(item);
    }

    public void Clear()
    {
        // list will never be null, and it shouldEnumerators notcan be a crimeused to clear an empty list.
        list.Clear();
    }

    // The original exercise did not require a Print() or ToString() method.
    public override string ToString()
    {
        if (list.Count == 0)
        {
            return "{ empty stack }"; // or perhaps "{ }"
        }

        // Each Console.WriteLine has a tiny cost.  Let'sread trythe notdata evenin callthe itcollection, but rather comnpose a string.
     they cannot be //used Thisto honorsmodify the OP's order and display.
        var sb = new StringBuilder();
        for (var i = list.Count - 1; i >= 0; i--)
        {
            sb.AppendLine(list[i].ToString());
        }

        returnunderlying sbcollection.ToString();
    }
}

Also, out of furthering my own skills and providing a better answer, I borrowed some code from Microsoft's Stack implementation, which uses an array BTW.

With that said, I offer the following modifications with updated code which now includes a better GetEnumerator:

public class StackV1 : IEnumerable
{
    private List<object> list = new List<object>();
    private int _version = 0; // used to keep in-sync with enumerator

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

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

    public object Pop()
    {
        if (list.Count == 0)
        {
            throw new InvalidOperationException("Empty stack.  There is nothing to Pop().");
        }

        // Pop by removing from end of list.
        var index = list.Count - 1;
        var item = list[index];
        list.RemoveAt(index);

        _version++;

        return item;
    }

    public void Push(object item)
    {
        if (item == null)
        {
            throw new InvalidOperationException($"{nameof(item)} is null.  There is nothing to Push().");
        }

        _version++;

        // Push by adding to end of list.
        list.Add(item);
    }

    public void Clear()
    {
        // list will never be null, and it should not be a crime to clear an empty list.
        if (list.Count > 0)
        {
            list.Clear();
            _version++;
        }
    }

    public int Size => list.Count;

    // The original exercise did not require a Print() or ToString() method.
    public override string ToString()
    {
        if (list.Count == 0)
        {
            return "{ empty stack }"; // or perhaps "{ }"
        }

        // Each Console.WriteLine has a tiny cost.  Let's try not even call it, but rather comnpose a string.
        // This honors the OP's order and display.
        var sb = new StringBuilder();
        for (var i = list.Count - 1; i >= 0; i--)
        {
            sb.AppendLine(list[i].ToString());
        }
    
        return sb.ToString();
    }

    // See https://referencesource.microsoft.com/#System/compmod/system/collections/generic/stack.cs,8865095e0bceeafd
    public struct Enumerator : IEnumerator
    {
        private StackV1 _stack;
        private int _version;
        private int _index;
        private object currentElement;

        internal Enumerator(StackV1 stack)
        {
            _stack = stack;
            _version = stack._version;
            _index = -2;
            currentElement = default(object);
        }

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

        public bool MoveNext()
        {
            bool retval;
            if (_version != _stack._version)
            {
                throw new Exception("Out-of-sync Enumerator due to a modified Stack.");
            }
            if (_index == -2)
            {  // First call to enumerator.
                _index = _stack.Size - 1;
                retval = (_index >= 0);
                if (retval)
                {
                    currentElement = _stack.list[_index];
                }
                return retval;
            }
            if (_index == -1)
            {  // End of enumeration.
                return false;
            }

            retval = (--_index >= 0);
            currentElement = retval ? _stack.list[_index] : default(object);
            return retval;
        }

        public object Current
        {
            get
            {
                if (_index == -2)
                {
                    throw new Exception("Pointer is before top of the stack.");
                }
                if (_index == -1)
                {
                    throw new Exception("Pointer is past the bottom of the stack.");
                }
                return currentElement;
            }
        }

        public void Reset()
        {
            if (_version != _stack._version)
            {
                throw new Exception("Out-of-sync Enumerator due to the Stack being modified externally.");
            }
            _index = -2;
            currentElement = default(object);
        }
    }
}

When I first looked at this exercise, I wondered why it was for Intermediates. It seemed too easy. After updating with a customer Enumerator, I can know see why its Intermediate.

With that said, I offer the following modifications:

public class StackV1 : IEnumerable
{
    private List<object> list = new List<object>();

    public IEnumerator GetEnumerator()
    {
        // No need for LINQ list.Any() here.
        if (list.Count > 0)
        {
            yield return Pop();
        }
    }

    public object Pop()
    {
        if (list.Count == 0)
        {
            throw new InvalidOperationException("Empty stack.  There is nothing to Pop().");
        }

        // Pop by removing from end of list.
        var index = list.Count - 1;
        var item = list[index];
        list.RemoveAt(index);

        return item;
    }

    public void Push(object item)
    {
        if (item == null)
        {
            throw new InvalidOperationException($"{nameof(item)} is null.  There is nothing to Push().");
        }

        // Push by adding to end of list.
        list.Add(item);
    }

    public void Clear()
    {
        // list will never be null, and it should not be a crime to clear an empty list.
        list.Clear();
    }

    // The original exercise did not require a Print() or ToString() method.
    public override string ToString()
    {
        if (list.Count == 0)
        {
            return "{ empty stack }"; // or perhaps "{ }"
        }

        // Each Console.WriteLine has a tiny cost.  Let's try not even call it, but rather comnpose a string.
        // This honors the OP's order and display.
        var sb = new StringBuilder();
        for (var i = list.Count - 1; i >= 0; i--)
        {
            sb.AppendLine(list[i].ToString());
        }

        return sb.ToString();
    }
}

EDIT

In light of @HenrikHansen 's answer about GetEnumerator, I have changed my answer to provide a custom enumerator. I see some discussion between Henrik and @sleptic, so let me add some context.

Microsoft has this to say about Stack.GetEnumerator :

Enumerators can be used to read the data in the collection, but they cannot be used to modify the underlying collection.

Also, out of furthering my own skills and providing a better answer, I borrowed some code from Microsoft's Stack implementation, which uses an array BTW.

With that said, I offer the following modifications with updated code which now includes a better GetEnumerator:

public class StackV1 : IEnumerable
{
    private List<object> list = new List<object>();
    private int _version = 0; // used to keep in-sync with enumerator

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

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

    public object Pop()
    {
        if (list.Count == 0)
        {
            throw new InvalidOperationException("Empty stack.  There is nothing to Pop().");
        }

        // Pop by removing from end of list.
        var index = list.Count - 1;
        var item = list[index];
        list.RemoveAt(index);

        _version++;

        return item;
    }

    public void Push(object item)
    {
        if (item == null)
        {
            throw new InvalidOperationException($"{nameof(item)} is null.  There is nothing to Push().");
        }

        _version++;

        // Push by adding to end of list.
        list.Add(item);
    }

    public void Clear()
    {
        // list will never be null, and it should not be a crime to clear an empty list.
        if (list.Count > 0)
        {
            list.Clear();
            _version++;
        }
    }

    public int Size => list.Count;

    // The original exercise did not require a Print() or ToString() method.
    public override string ToString()
    {
        if (list.Count == 0)
        {
            return "{ empty stack }"; // or perhaps "{ }"
        }

        // Each Console.WriteLine has a tiny cost.  Let's try not even call it, but rather comnpose a string.
        // This honors the OP's order and display.
        var sb = new StringBuilder();
        for (var i = list.Count - 1; i >= 0; i--)
        {
            sb.AppendLine(list[i].ToString());
        }
    
        return sb.ToString();
    }

    // See https://referencesource.microsoft.com/#System/compmod/system/collections/generic/stack.cs,8865095e0bceeafd
    public struct Enumerator : IEnumerator
    {
        private StackV1 _stack;
        private int _version;
        private int _index;
        private object currentElement;

        internal Enumerator(StackV1 stack)
        {
            _stack = stack;
            _version = stack._version;
            _index = -2;
            currentElement = default(object);
        }

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

        public bool MoveNext()
        {
            bool retval;
            if (_version != _stack._version)
            {
                throw new Exception("Out-of-sync Enumerator due to a modified Stack.");
            }
            if (_index == -2)
            {  // First call to enumerator.
                _index = _stack.Size - 1;
                retval = (_index >= 0);
                if (retval)
                {
                    currentElement = _stack.list[_index];
                }
                return retval;
            }
            if (_index == -1)
            {  // End of enumeration.
                return false;
            }

            retval = (--_index >= 0);
            currentElement = retval ? _stack.list[_index] : default(object);
            return retval;
        }

        public object Current
        {
            get
            {
                if (_index == -2)
                {
                    throw new Exception("Pointer is before top of the stack.");
                }
                if (_index == -1)
                {
                    throw new Exception("Pointer is past the bottom of the stack.");
                }
                return currentElement;
            }
        }

        public void Reset()
        {
            if (_version != _stack._version)
            {
                throw new Exception("Out-of-sync Enumerator due to the Stack being modified externally.");
            }
            _index = -2;
            currentElement = default(object);
        }
    }
}

When I first looked at this exercise, I wondered why it was for Intermediates. It seemed too easy. After updating with a customer Enumerator, I can know see why its Intermediate.

Source Link
Rick Davin
  • 6.8k
  • 1
  • 20
  • 32

You have posted several such exercises before, and I have commented on them as well. First let's state the good: you are performing such exercises to improve your C# and .NET skills. But I have noticed a pattern that if someone questions you on why you do some things a certain, you quickly take refuge under the blanket of that's what the exercise states. But you also do things such as Print() all on your own. To me, this seems to be conflicting goals among (1) you want to learn and improve, (2) you want to follow the strict letter of the exercise when it suits you, and (3) when it suits you, you want to diverge from the exercise. This conflict may contribute to frustration others have when attempting to help you.

What caught my eye about your implementation was 2 notable things: (1) you rely heavily upon LINQ, and (2) you perform more expensive Insert(0, item) than to Add(item) to the end of list.

I take issue with Pop() because of FirstOrDefault. Not because it's LINQ, although you do not need to use any LINQ at all in your solution. Rather it's what it means. First off, you check for emptiness that is Count == 0. It would be better, i.e. more direct than for you to take list[0] because that's what the stack expects. FirstorDefault just happens to return the first item for you, but what it really means is iterate over this list and find the first item that matches the predicate (and a null predicate means any item). While it just happens to be that list[0] and FirstOrDefault works for you, they really mean 2 different things to someone reading your code.

Besides those observations, I would add the following remarks:

  • The internal methods really should be public.

  • _object does not need to be a class field or property. It should be local to a method.

  • I see no crime in clearing an empty list. It may be pointless but it's less expensive than throwing an exception for it. The edge case to consider would be if list was null, but it won't be.

  • I would prefer to override ToString() instead of Print().

  • Console writes take a small bit of overhead, so it would be best to avoid repeated calls for every item in the list. You can compose the string once with a fast StringBuilder and then write or return the string once. Whether you write that string to the console or a log file is up to a developer using your stack.

With that said, I offer the following modifications:

public class StackV1 : IEnumerable
{
    private List<object> list = new List<object>();

    public IEnumerator GetEnumerator()
    {
        // No need for LINQ list.Any() here.
        if (list.Count > 0)
        {
            yield return Pop();
        }
    }

    public object Pop()
    {
        if (list.Count == 0)
        {
            throw new InvalidOperationException("Empty stack.  There is nothing to Pop().");
        }

        // Pop by removing from end of list.
        var index = list.Count - 1;
        var item = list[index];
        list.RemoveAt(index);

        return item;
    }

    public void Push(object item)
    {
        if (item == null)
        {
            throw new InvalidOperationException($"{nameof(item)} is null.  There is nothing to Push().");
        }

        // Push by adding to end of list.
        list.Add(item);
    }

    public void Clear()
    {
        // list will never be null, and it should not be a crime to clear an empty list.
        list.Clear();
    }

    // The original exercise did not require a Print() or ToString() method.
    public override string ToString()
    {
        if (list.Count == 0)
        {
            return "{ empty stack }"; // or perhaps "{ }"
        }

        // Each Console.WriteLine has a tiny cost.  Let's try not even call it, but rather comnpose a string.
        // This honors the OP's order and display.
        var sb = new StringBuilder();
        for (var i = list.Count - 1; i >= 0; i--)
        {
            sb.AppendLine(list[i].ToString());
        }

        return sb.ToString();
    }
}

Your original Print and my ToString list each item on a new line. My personal preference would be to list as a collection like "{ 3, 2, 1 }"

// However my personal option would be to list as "{ 3, 2, 1 }"
sb.Append("{ ");
var first = true;
for (var i = list.Count - 1; i >= 0; i--)
{
    var delimiter = first ? "" : ", ";
    sb.Append($"{delimiter}{list[i]}");
    if (first)
    {
        first = false;
    }
}
sb.Append(" }");

The real fun would be to add generics for type-specific lists. However, I see the exercise says that will be covered in an advanced exercise. It's really not that much of a stretch and would be beneficial to the skills you wish to acquire.