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

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;
using System.Diagnostics;

namespace ImmutableCollections
{
	/// <summary>
	/// Represents a collection of elements accessible by index and supports
	/// insertion and deletion.
	/// </summary>
	public class ArrayList
	{
        #region ArrayList Members

        #region Constants

        // The height of the tree pool.
        private const int TreePoolHeight = 30;

        // The default height of the initial tree.
        private const int DefaultCapacityHeight = 5;

        #endregion

        #region Readonly

        /* 
         * The tree pool is a tree made up of null nodes. It is completely 
         * balanced and is used to form a template of nodes for use in the
         * ArrayList. Initially, a small subtree is taken from the tree pool
         * when an ArrayList is created. New nodes replace the null nodes as
         * new versions of the ArrayList are created. Once the tree has been 
         * filled, another subtree of equal height is taken from the tree pool
         * to enlarge the tree for the next version of the ArrayList.
         * 
         * The reasoning behind this approach is that the Add method of the 
         * ArrayList will probably be the most widely used operation. By having
         * a prefabricated balanced tree, no rebalancing has to take place as 
         * new nodes are added to the tree. Their position in the tree has 
         * already been determined by the existing null tree. This improves 
         * performance.
         */

        private static readonly IAvlNode TreePool;

        #endregion

        #region Fields

        // The number of items in the ArrayList.
        private int count = 0;

        // The root of the tree.
        private IAvlNode root;

        #endregion

        #region Contstruction

        /// <summary>
        /// Initializes the ArrayList class.
        /// </summary>
        static ArrayList()
        {
            IAvlNode parent = AvlNode.NullNode;
            IAvlNode child = AvlNode.NullNode;

            // Create the tree pool.
            for(int i = 0; i < TreePoolHeight; i++)
            {
                parent = new AvlNode(null, child, child);
                child = parent;
            }

            TreePool = parent;

            // Postconditions.
            Debug.Assert(TreePool.Height == TreePoolHeight);
        }

        /// <summary>
        /// Initializes a new instance of the ArrayList class.
        /// </summary>
		public ArrayList()
		{
            root = GetSubTree(DefaultCapacityHeight);
        }

        /// <summary>
        /// Initializes a new instance of the ArrayList class with the 
        /// specified root and count.
        /// </summary>
        /// <param name="root">
        /// The root of the tree.
        /// </param>
        /// <param name="count">
        /// The number of items in the ArrayList.
        /// </param>
        private ArrayList(IAvlNode root, int count)
        {
            this.root = root;
            this.count = count;
        }

        #endregion        

        #region Methods

        /// <summary>
        /// Adds an object to the end of the ArrayList.
        /// </summary>
        /// <param name="value">
        /// The Object to be added to the end of the ArrayList. 
        /// </param>
        /// <returns>
        /// A new ArrayList object with the specified value added at the end.
        /// </returns>
        public ArrayList Add(object value)
        {
            ArrayList result;

            // If the tree has been filled.
            if(count == root.Count)
            {
                // Create a new ArrayList while enlarging the tree. The 
                // current count serves as an index for setting the specified
                // value.
                result = new ArrayList(
                    SetValue(count, value, EnlargeTree()), 
                    count + 1);
            }
                // Else the tree has not been filled.
            else
            {
                // Create a new ArrayList. The current count serves as an index 
                // for setting the specified value.
                result = new ArrayList(
                    SetValue(count, value, root), 
                    count + 1);
            }

            // Postconditions.
            Debug.Assert(result.Count == Count + 1);
            Debug.Assert(result.GetValue(result.Count - 1) == value);

            return result;
        }

        /// <summary>
        /// Determines whether an element is in the ArrayList.
        /// </summary>
        /// <param name="value">
        /// The Object to locate in the ArrayList. 
        /// </param>
        /// <returns>
        /// <b>true</b> if item is found in the ArrayList; otherwise, 
        /// <b>false</b>.
        /// </returns>
        public bool Contains(object value)
        {
            return IndexOf(value) > -1;
        }

        /// <summary>
        /// Returns the zero-based index of the first occurrence of a value in 
        /// the ArrayList.
        /// </summary>
        /// <param name="value">
        /// The Object to locate in the ArrayList.
        /// </param>
        /// <returns>
        /// The zero-based index of the first occurrence of value within the 
        /// ArrayList, if found; otherwise, -1.
        /// </returns>
        public int IndexOf(object value)
        {
            int index = 0;

            // Iterate through the ArrayList and compare each value with the
            // specified value. If they match, return the index of the value.
            foreach(object v in this)
            {
                if(value.Equals(v))
                {
                    return index;
                }

                index++;
            }

            // The specified value is not in the ArrayList.
            return -1;
        }

        /// <summary>
        /// Inserts an element into the ArrayList at the specified index.
        /// </summary>
        /// <param name="index">
        /// The zero-based index at which value should be inserted. 
        /// </param>
        /// <param name="value">
        /// The Object to insert.
        /// </param>
        /// <returns>
        /// A new ArrayList with the specified object inserted at the specified 
        /// index.
        /// </returns>
        /// <exception cref="ArgumentOutOfRangeException">
        /// index is less than zero or index is greater than Count.
        /// </exception>
        public ArrayList Insert(int index, object value)
        {
            // Preconditions.
            if(index < 0 || index > Count)
            {
                throw new ArgumentOutOfRangeException(
                    "ArrayList index out of range.");
            }            

            // Create new ArrayList with the value inserted at the specified index.
            ArrayList result = new ArrayList(Insert(index, value, root), count + 1);

            // Post conditions.
            Debug.Assert(result.GetValue(index) == value);

            return result;
        }

        /// <summary>
        /// Removes the first occurrence of a specified object from the 
        /// ArrayList.
        /// </summary>
        /// <param name="obj">
        /// The Object to remove from the ArrayList. 
        /// </param>
        /// <returns>
        /// A new ArrayList with the first occurrent of the specified object 
        /// removed.
        /// </returns>
        public ArrayList Remove(object value)
        {
            ArrayList result;
            int index = IndexOf(value);

            // If the object is in the ArrayList.
            if(index > -1)
            {
                // Remove the object.
                result = RemoveAt(index);

                // Postcondition.
                Debug.Assert(result.Count == Count - 1);
            }
            // Else the object is not in the ArrayList.
            else
            {
                result = this;
            }

            return result;
        }

        /// <summary>
        /// Removes the element at the specified index of the ArrayList.
        /// </summary>
        /// <param name="index">
        /// The zero-based index of the element to remove. 
        /// </param>
        /// <returns>
        /// A new ArrayList with the element at the specified index removed.
        /// </returns>
        /// <exception cref="ArgumentOutOfRangeException">
        /// index is less than zero or index is equal to or greater than Count.
        /// </exception>
        public ArrayList RemoveAt(int index)
        {
            // Preconditions.
            if(index < 0 || index >= Count)
            {
                throw new ArgumentOutOfRangeException("index", index,
                    "ArrayList index out of range.");
            } 
           
            // Create a new ArrayList with the element at the specified index 
            // removed.
            ArrayList result = new ArrayList(RemoveAt(index, root), count - 1);

            // Postconditions.
            Debug.Assert(result.Count == Count - 1);

            return result;
        }

        /// <summary>
        /// Gets the value at the specified index.
        /// </summary>
        /// <param name="index">
        /// The zero-based index of the element to get.
        /// </param>
        /// <returns>
        /// The value at the specified index.
        /// </returns>
        /// <exception cref="ArgumentOutOfRangeException">
        /// index is less than zero or index is equal to or greater than Count.
        /// </exception>
        public object GetValue(int index)
        {
            // Preconditions.
            if(index < 0 || index >= Count)
            {
                throw new ArgumentOutOfRangeException("index", index,
                    "Index out of range.");
            }

            return GetValue(index, root);
        }

        /// <summary>
        /// Sets the value at the specified index.
        /// </summary>
        /// <param name="index">
        /// The zero-based index of the element to set.
        /// </param>
        /// <param name="value">
        /// The value to set at the specified index.
        /// </param>
        /// <returns>
        /// A new ArrayList with the specified value set at the specified index.
        /// </returns>
        /// <exception cref="ArgumentOutOfRangeException">
        /// index is less than zero or index is equal to or greater than Count.
        /// </exception>
        public ArrayList SetValue(int index, object value)
        {
            // Preconditions.
            if(index < 0 || index >= count)
            {
                throw new ArgumentOutOfRangeException(
                    "ArrayList index out of range.");
            }

            // Create a new ArrayList with the specified value set at the 
            // specified index.
            ArrayList result = new ArrayList(SetValue(index, value, root), count);

            // Postconditions.
            Debug.Assert(result.GetValue(index) == value);

            return result;
        }

        // Enlarges the tree used by the ArrayList.
        private IAvlNode EnlargeTree()
        {
            // Preconditions.
            Debug.Assert(root.Height <= TreePool.Height);

            // Create new root for the enlarged tree.
            IAvlNode result = new AvlNode(null, root, GetSubTree(root.Height));

            // Postconditions.
            Debug.Assert(result.BalanceFactor == 0);
            Debug.Assert(result.Height == root.Height + 1);

            return result;
        }

        // Recursive GetValue helper method.
        private object GetValue(int index, IAvlNode node)
        {
            // Preconditions.
            Debug.Assert(index >= 0 && index < Count);
            Debug.Assert(node != AvlNode.NullNode);

            object result;
            int leftCount =  node.LeftChild.Count;

            // If the node has been found.
            if(index == leftCount)
            {
                // Get value.
                result = node.Data;
            }
            // Else if the node is in the left tree.
            else if(index < leftCount)
            {
                // Move search to left child.
                result = GetValue(index, node.LeftChild);
            }
            // Else if the node is in the right tree.
            else
            {
                // Move search to the right child.
                result = GetValue(index - (leftCount + 1), node.RightChild);
            }

            return result;
        }
        
        // Recursive SetValue helper method.
        private IAvlNode SetValue(int index, object value, IAvlNode node)
        {
            // Preconditions.
            Debug.Assert(index >= 0 && index < node.Count);
            Debug.Assert(node != AvlNode.NullNode);

            IAvlNode result;
            int leftCount = node.LeftChild.Count;

            // If the node has been found.
            if(index == leftCount)
            {
                // Create new node with the new value.
                result = new AvlNode(value, node.LeftChild, node.RightChild);
            }
            // Else if the node is in the left tree.
            else if(index < leftCount)
            {
                // Create new node and move search to the left child. The new 
                // node will reuse the right child subtree.
                result = new AvlNode(
                    node.Data, 
                    SetValue(index, value, node.LeftChild),
                    node.RightChild);
            }
            // Else if the node is in the right tree.
            else
            {
                // Create new node and move search to the right child. The new 
                // node will reuse the left child subtree.
                result = new AvlNode(
                    node.Data,
                    node.LeftChild,
                    SetValue(index - (leftCount + 1), value, node.RightChild));
            }

            return result;
        }

        // Gets a subtree from the tree pool at the specified height.
        private static IAvlNode GetSubTree(int height)
        {
            // Preconditions.
            Debug.Assert(height >= 0 && height <= TreePool.Height);

            IAvlNode result = TreePool;

            // How far to descend into the tree pool to get the subtree.
            int d = TreePool.Height - height;

            // Descend down the tree pool until arriving at the root of the 
            // subtree.
            for(int i = 0; i < d; i++)
            {
                result = result.LeftChild;
            }

            // Postconditions.
            Debug.Assert(result.Height == height);
      
            return result;
        }        

        // Recursive Insert helper method.
        private IAvlNode Insert(int index, object value, IAvlNode node)
        {
            // Preconditions.
            Debug.Assert(index >= 0 && index <= Count);
            Debug.Assert(node != null);            

            /*
             * The insertion algorithm searches for the correct place to add a
             * new node at the bottom of the tree using the specified index.
             */

            IAvlNode result;

            // If the bottom of the tree has not yet been reached.
            if(node != AvlNode.NullNode)
            {
                int leftCount = node.LeftChild.Count;

                // If we need to descend to the left.
                if(index <= leftCount)
                {
                    // Create new node and move search to the left child. The 
                    // new node will reuse the right child subtree.
                    result = new AvlNode(
                        node.Data,
                        Insert(index, value, node.LeftChild),
                        node.RightChild);
                }
                // Else we need to descend to the right.
                else
                {
                    // Create new node and move search to the right child. The 
                    // new node will reuse the left child subtree.
                    result = new AvlNode(
                        node.Data,
                        node.LeftChild,
                        Insert(index - (leftCount + 1), 
                            value, 
                            node.RightChild));
                }
            }
            // Else the bottom of the tree has been reached.
            else
            {
                // Create new node at the specified index.
                result = new AvlNode(value, AvlNode.NullNode, AvlNode.NullNode);
            }

            /*
             * This check isn't necessary if a node has already been rebalanced 
             * after an insertion. AVL tree insertions never require more than
             * one rebalancing. However, it's easier to go ahead and check at 
             * this point since we're using recursion. This may need optimizing
             * in the future.
             */

            // If the node is not balanced.
            if(!result.IsBalanced())
            {                
                // Rebalance node.
                result = result.Balance();
            }

            // Postconditions.
            Debug.Assert(result.IsBalanced());

            return result;
        }

        // Recursive RemoveAt helper method.
        private IAvlNode RemoveAt(int index, IAvlNode node)
        {
            // Preconditions.
            Debug.Assert(index >= 0 && index < Count);
            Debug.Assert(node != AvlNode.NullNode);

            IAvlNode newNode = AvlNode.NullNode;

            int leftCount = node.LeftChild.Count;

            // If the node has been found.
            if(index == leftCount)
            {
                newNode = node.Remove();
            }
            // Else if the node is in the left tree.
            else if(index < leftCount)
            {
                // Create new node and move search to the left child. The new 
                // node will reuse the right child subtree.
                newNode = new AvlNode(
                    node.Data,
                    RemoveAt(index, node.LeftChild),
                    node.RightChild);
            }
            // Else if the node is in the right tree.
            else
            {
                // Create new node and move search to the right child. The new 
                // node will reuse the left child subtree.
                newNode = new AvlNode(
                    node.Data,
                    node.LeftChild,
                    RemoveAt(index - (leftCount + 1), node.RightChild));
            }

            // If the node is out of balance.
            if(!newNode.IsBalanced())
            {
                // Rebalance node.
                newNode = newNode.Balance();
            }

            // Postconditions.
            Debug.Assert(newNode.IsBalanced());

            return newNode;
        }        

        #endregion

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

        #endregion

        #region IEnumerable Members

        /// <summary>
        /// Returns an enumerator that can iterate through the ArrayList.
        /// </summary>
        /// <returns>
        /// An IEnumerator that can be used to iterate through the ArrayList.
        /// </returns>
        public IEnumerator GetEnumerator()
        {
            return new AvlEnumerator(root, Count);
        }

        #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

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
Web02 | 2.8.140718.1 | Last Updated 24 Feb 2005
Article Copyright 2005 by Leslie Sanford
Everything else Copyright © CodeProject, 1999-2014
Terms of Service
Layout: fixed | fluid