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

Persistent Data Structures

, 24 Feb 2005 MIT
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 an array data structure.
	/// </summary>
	public class Array : IEnumerable
	{
        #region Array Members

        #region Instance Fields

        // The length of the array.
        private int length;

        // The head node of the random access list.
        private RalTopNode head;

        #endregion

        #region Construction

        /// <summary>
        /// Initialize an instance of the Array class with the specified array 
        /// length.
        /// </summary>
        /// <param name="length">
        /// The length of the array.
        /// </param>
        public Array(int length)
        {
            // Precondition.
            if(length < 0)
            {
                throw new ArgumentOutOfRangeException("length", length,
                    "Array length out of range.");
            }

            this.length = length;

            int n = length;
            int exponent;
            int count;

            head = null;

            /*
             * The following algorithm creates the trees for the array. The
             * trees have the form of a random access list.
             */

            // While there are still nodes to create.
            while(n > 0)
            {
                // Get the log based 2 of the number of nodes.
                exponent = (int)Math.Log(n, 2);

                // Get the number of nodes for each subtree.
                count = ((int)Math.Pow(2, exponent) - 1) / 2;

                // Create the top node representing the subtree.
                head = new RalTopNode(
                    new RalTreeNode(
                        null, 
                        CreateSubTree(count), 
                        CreateSubTree(count)),
                    head);

                // Get the remaining number of nodes to create.
                n -= head.Root.Count;
            }            
        }

        /// <summary>
        /// Initializes a new instance of the Array class with the specified 
        /// head of the random access list and the length of the array.
        /// </summary>
        /// <param name="head">
        /// The head of the random access list.
        /// </param>
        /// <param name="length">
        /// The length of the array.
        /// </param>
        private Array(RalTopNode head, int length)
        {
            this.head = head;
            this.length = length;            
        }

        #endregion

        #region Methods

        /// <summary>
        /// Gets the value of the specified element in the current Array. 
        /// </summary>
        /// <param name="index">
        /// An integer that represents the position of the Array element to 
        /// get. 
        /// </param>
        /// <returns>
        /// The value at the specified position in the Array.
        /// </returns>
        /// <exception cref="ArgumentOutOfRange">
        /// index is outside the range of valid indexes for the current Array.
        /// </exception>
        public object GetValue(int index)
        {
            // Preconditions.
            if(index < 0 || index >= Length)
            {
                throw new ArgumentOutOfRangeException(
                    "Index out of range.");
            }

            return head.GetValue(index);            
        }

        /// <summary>
        /// Sets the specified element in the current Array to the specified 
        /// value.
        /// </summary>
        /// <param name="value">
        /// The new value for the specified element. 
        /// </param>
        /// <param name="index">
        /// An integer that represents the position of the Array element to set. 
        /// </param>
        /// <returns>
        /// A new array with the element at the specified position set to the 
        /// specified value.
        /// </returns>
        /// <exception cref="ArgumentOutOfRange">
        /// index is outside the range of valid indexes for the current Array.
        /// </exception>
        public Array SetValue(object value, int index)
        {
            // Preconditions.
            if(index < 0 || index >= Length)
            {
                throw new ArgumentOutOfRangeException(
                    "Index out of range.");
            }

            return new Array(head.SetValue(value, index), Length);
        }

        // Creates subtrees within the random access list.
        private RalTreeNode CreateSubTree(int count)
        {
            RalTreeNode result = null;

            if(count > 0)
            {
                int c = count / 2;

                result = new RalTreeNode(
                    null,
                    CreateSubTree(c),
                    CreateSubTree(c));
            }

            return result;
        }

        #endregion

        #region Properties

        /// <summary>
        /// Gets an integer that represents the total number of elements in all 
        /// the dimensions of the Array.
        /// </summary>
        public int Length
        {
            get
            {
                return length;
            }
        }

        #endregion

        #endregion

        #region IEnumerable Members

        /// <summary>
        /// Returns an IEnumerator for the Array.
        /// </summary>
        /// <returns>
        /// An IEnumerator for the Array.
        /// </returns>
        public IEnumerator GetEnumerator()
        {
            return new RalEnumerator(head, length);
        }

        #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 | Terms of Use | Mobile
Web02 | 2.8.150129.1 | Last Updated 24 Feb 2005
Article Copyright 2005 by Leslie Sanford
Everything else Copyright © CodeProject, 1999-2015
Layout: fixed | fluid