Click here to Skip to main content
12,945,575 members (51,957 online)
Click here to Skip to main content


89 bookmarked
Posted 23 Feb 2005

Persistent Data Structures

, 23 Feb 2005 MIT
An article describing the basic principles of persistent data structures.
 * Created by: Leslie Sanford 
 * Last modified: 02/23/2005
 * Contact:

using System;
using System.Collections;
using System.Diagnostics;

namespace ImmutableCollections
    /// <summary>
    /// Provides functionality for enumerating a RandomAccessList.
    /// </summary>
    internal class RalEnumerator : IEnumerator
        #region Enumerator Members

        #region Instance Fields

        // The object at the current position.
        private object current = null;

        // The current index position.
        private int index;

        // For storing and traversing the nodes in the tree.
        private System.Collections.Stack treeStack = new System.Collections.Stack();

        // The first top node in the list.
        private RalTopNode head;

        // The current top node in the list.
        private RalTopNode currentTopNode;

        // The number of nodes in the list.
        private int count;


        #region Construction

        /// <summary>
        /// Initializes a new instance of the Enumerator with the specified 
        /// head of the list and the number of nodes in the list.
        /// </summary>
        /// <param name="head">
        /// The head of the list.
        /// </param>
        /// <param name="count">
        /// The number of nodes in the list.
        /// </param>
        public RalEnumerator(RalTopNode head, int count)
            this.head = head;
            this.count = count;

            if(count > 0)
                Debug.Assert(head != null);



        #region IEnumerator Members

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

            //  If the list is not empty.
            if(count > 0)
                // Push the first node in the list onto the stack.

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

                return current;

        /// <summary>
        /// Advances the enumerator to the next element in the random access 
        /// list.
        /// </summary>
        /// <returns>
        /// <b>true</b> if the enumerator was successfully advanced to the 
        /// next element; <b>false</b> if the enumerator has passed the end 
        /// of the collection.
        /// </returns>
        public bool MoveNext()
            // Move index to the next position.

            // If the index has moved beyond the end of the list, return false.
            if(index >= count)
                return false;

            RalTreeNode currentNode; 

            // Get the node at the top of the stack.
            currentNode = (RalTreeNode)treeStack.Peek();

            // Get the value at the top of the stack.
            current = currentNode.Value;

            // If there are still left children to traverse.
            if(currentNode.LeftChild != null)
                // If the left child is not null, the right child should not be
                // null either.
                Debug.Assert(currentNode.RightChild != null);

                // Push left child onto stack.
            // Else the bottom of the tree has been reached.
                // If the left child is null, the right child should be null, 
                // too.
                Debug.Assert(currentNode.RightChild == null);

                // Move back up in the tree to the parent node.
                RalTreeNode previousNode;

                // Whild the stack is not empty.
                while(treeStack.Count > 0)
                    // Get the previous node.
                    previousNode = (RalTreeNode)treeStack.Peek();

                    // If the bottom of the left tree has been reached.
                    if(currentNode == previousNode.LeftChild)
                        // Push the right child onto the stack so that the 
                        // right tree will now be traversed.

                        // Finished.
                    // Else the bottom of the right tree has been reached.
                        // Keep track of the current node.
                        currentNode = previousNode;

                        // Pop the stack to move back up the tree.

                // If the stack is empty.
                if(treeStack.Count == 0)
                    // Move to the next tree in the list.
                    currentTopNode = currentTopNode.NextNode;

                    // If the end of the list has not yet been reached.
                    if(currentTopNode != null)
                        // Begin with the next tree.

            return true;


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.


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


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.

You may also be interested in...

Permalink | Advertise | Privacy | Terms of Use | Mobile
Web02 | 2.8.170518.1 | Last Updated 24 Feb 2005
Article Copyright 2005 by Leslie Sanford
Everything else Copyright © CodeProject, 1999-2017
Layout: fixed | fluid