Click here to Skip to main content
Click here to Skip to main content
Add your own
alternative version
Go to top

Persistent Data Structures

, 23 Feb 2005
An article describing the basic principles of persistent data structures.
persistentdatastructures_src.zip
ImmutableCollections
ImmutableCollections
AVL Tree Classes
ImmutableCollections.csproj.user
RAL Helper Classes
/*
 * Created by: Leslie Sanford 
 * 
 * Last modified: 02/23/2005
 * 
 * Contact: jabberdabber@hotmail.com
 */

using System;
using System.Collections;

namespace ImmutableCollections
{
	/// <summary>
    /// Represents a simple last-in-first-out collection of objects.
	/// </summary>
	public class Stack : IEnumerable
	{
        #region Stack Members

        #region Class Fields

        /// <summary>
        /// An empty Stack.
        /// </summary>
        public static readonly Stack Empty = new Stack();

        #endregion

        #region Instance Fields

        // The number of elements in the stack.
        private readonly int count;

        // The top node in the stack.
        private Node top = null;

        #endregion

        #region Construction

        /// <summary>
        /// Initializes a new instance of the Stack class.
        /// </summary>
		public Stack()
		{
            count = 0;
		}

        /// <summary>
        /// Initializes a new instance of the Stack class with the 
        /// specified top node and the number of elements in the stack.
        /// </summary>
        /// <param name="top">
        /// The top node in the stack.
        /// </param>
        /// <param name="count">
        /// The number of elements in the stack.
        /// </param>        
        private Stack(Node top, int count)
        {
            this.top = top;
            this.count = count;            
        }

        #endregion

        #region Methods

        /// <summary>
        /// Inserts an object at the top of the Stack.
        /// </summary>
        /// <param name="obj">
        /// The Object to push onto the Stack.
        /// </param>
        /// <returns>
        /// A new stack with the specified object on the top of the stack.
        /// </returns>
        public Stack Push(object obj)
        {
            Node newTop = new Node(obj, top);

            return new Stack(newTop, Count + 1);
        }

        /// <summary>
        /// Removes the object at the top of the Stack.
        /// </summary>
        /// <returns>
        /// A new stack with top of the previous stack removed.
        /// </returns>
        /// <exception cref="InvalidOperationException">
        /// The Stack is empty.
        /// </exception>
        public Stack Pop()
        { 
            // Preconditions.
            if(Count == 0)
            {
                throw new InvalidOperationException(
                    "Cannot pop an empty stack.");
            }

            Stack result;

            if(Count - 1 == 0)
            {
                result = Empty;
            }
            else
            {
                result = new Stack(top.Next, Count - 1);
            }

            return result;
        }

        #endregion

        #region Properties

        /// <summary>
        /// Gets the number of elements in the Stack.
        /// </summary>
        public int Count
        {
            get
            {
                return count;
            }
        }

        /// <summary>
        /// Gets the top of the stack.
        /// </summary>
        /// <exception cref="InvalidOperationException">
        /// The Stack is empty.
        /// </exception>
        public object Top
        {
            get
            {
                if(Count == 0)
                {
                    throw new InvalidOperationException(
                        "Cannot access the top when the stack is empty.");
                }

                return top.Value;
            }
        }

        #endregion

        #region Node Class

        /// <summary>
        /// Represents a node in the stack.
        /// </summary>
        private class Node
        {
            private Node next = null;

            private object value;

            public Node(object value, Node next)
            {
                this.value = value;
                this.next = next;
            }

            public Node Next
            {
                get
                {
                    return next;
                }
            }

            public object Value
            {
                get
                {
                    return value;
                }
            }
        }

        #endregion 

        #region StackEnumerator Class

        /// <summary>
        /// Provides functionality for iterating over the Stack class.
        /// </summary>
        private class StackEnumerator : IEnumerator
        {
            #region StackEnumerator Members

            #region Instance Fields

            // The stack to iterate over.
            private Stack owner;

            // The current index into the stack.
            private int index;

            // The current node.
            private Node current;

            // The next node in the stack.
            private Node next;

            #endregion

            #region Construction

            /// <summary>
            /// Initializes a new instance of the StackEnumerator class with 
            /// the specified stack to iterate over.
            /// </summary>
            /// <param name="owner">
            /// The Stack to iterate over.
            /// </param>
            public StackEnumerator(Stack owner)
            {
                this.owner = owner;

                Reset();
            }

            #endregion

            #region IEnumerator Members

            /// <summary>
            /// Sets the enumerator to its initial position, which is before 
            /// the first element in the Stack.
            /// </summary>
            public void Reset()
            {
                index = -1;

                next = owner.top;
            }

            /// <summary>
            /// Gets the current element in the Stack.
            /// </summary>
            /// <exception cref="InvalidOperationException">
            /// The enumerator is positioned before the first element of the 
            /// Stack or after the last element.
            /// </exception>
            public object Current
            {
                get
                {
                    // Preconditions.
                    if(index < 0 || index >= owner.Count)
                    {
                        throw new InvalidOperationException(
                            "The enumerator is positioned before the first " +
                            "element of the collection or after the last element.");
                    }

                    return current.Value;
                }
            }

            /// <summary>
            /// Advances the enumerator to the next element of the Stack.
            /// </summary>
            /// <returns></returns>
            public bool MoveNext()
            {
                index++;

                if(index >= owner.Count)
                {
                    return false;
                }

                current = next;
                next = next.Next;

                return true;
            }

            #endregion
        }

        #endregion

        #endregion

        #endregion

        #region IEnumerable Members

        /// <summary>
        /// Returns an IEnumerator for the Stack.
        /// </summary>
        /// <returns>
        /// An IEnumerator for the Stack.
        /// </returns>
        public IEnumerator GetEnumerator()
        {
            return new StackEnumerator(this);
        }

        #endregion
    }
}

By viewing downloads associated with this article you agree to the Terms of Service and the article's licence.

If a file you wish to view isn't highlighted, and is a text file (not binary), please let us know and we'll add colourisation support for it.

License

This article, along with any associated source code and files, is licensed under The MIT License

Share

About the Author

Leslie Sanford

United States United States
Aside from dabbling in BASIC on his old Atari 1040ST years ago, Leslie's programming experience didn't really begin until he discovered the Internet in the late 90s. There he found a treasure trove of information about two of his favorite interests: MIDI and sound synthesis.
 
After spending a good deal of time calculating formulas he found on the Internet for creating new sounds by hand, he decided that an easier way would be to program the computer to do the work for him. This led him to learn C. He discovered that beyond using programming as a tool for synthesizing sound, he loved programming in and of itself.
 
Eventually he taught himself C++ and C#, and along the way he immersed himself in the ideas of object oriented programming. Like many of us, he gotten bitten by the design patterns bug and a copy of GOF is never far from his hands.
 
Now his primary interest is in creating a complete MIDI toolkit using the C# language. He hopes to create something that will become an indispensable tool for those wanting to write MIDI applications for the .NET framework.
 
Besides programming, his other interests are photography and playing his Les Paul guitars.

| Advertise | Privacy | Mobile
Web04 | 2.8.140916.1 | Last Updated 24 Feb 2005
Article Copyright 2005 by Leslie Sanford
Everything else Copyright © CodeProject, 1999-2014
Terms of Service
Layout: fixed | fluid