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

namespace ImmutableCollections
{
    /// <summary>
    /// Represents subtree nodes within random access lists.
    /// </summary>
    internal class RalTreeNode
    {
        #region RalTreeNode Members

        #region Instance Fields

        // The value represented by this node.
        private readonly object value;

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

        // Left and right children.
        private readonly RalTreeNode leftChild = null;
        private readonly RalTreeNode rightChild = null;
        
        #endregion

        #region Construction

        /// <summary>
        /// Initializes an instance of the RandomAccessListNode with the
        /// specified value, left child, and right child.
        /// </summary>
        /// <param name="value">
        /// The value to store in the node.
        /// </param>
        /// <param name="leftChild">
        /// The left child.
        /// </param>
        /// <param name="rightChild">
        /// The right child.
        /// </param>
        public RalTreeNode(
            object value, 
            RalTreeNode leftChild, 
            RalTreeNode rightChild)
        {
            this.value = value;
            this.leftChild = leftChild;
            this.rightChild = rightChild;

            count = 1;

            if(leftChild != null)
            {
                count += leftChild.Count * 2;

                Debug.Assert(rightChild != null);
                Debug.Assert(count == 1 + leftChild.Count + rightChild.Count);
            }
        }

        #endregion

        #region Methods

        /// <summary>
        /// Gets the value at the specified element in the random access list
        /// subtree.
        /// </summary>
        /// <param name="index">
        /// An integer that represents the position of the random access list 
        /// subtree element to get. 
        /// </param>
        /// <returns>
        /// The value at the specified position in the random access list
        /// subtree.
        /// </returns>
        public object GetValue(int index)
        {
            Debug.Assert(index < Count);

            return GetValue(index, this);            
        }

        // Recursive method for getting the value at the specified position.
        private object GetValue(int index, RalTreeNode node)
        {
            object result;

            // If the position of the value to get has been reached.
            if(index == 0)
            {
                // Get the value.
                result = node.Value;
            }
            // Else the position of the value to get has not been reached.
            else
            { 
                int n = node.Count / 2;

                // If the value is in the left subtree.
                if(index <= n)
                {
                    Debug.Assert(node.LeftChild != null);

                    // Descend into the left subtree.
                    result = GetValue(index - 1, node.LeftChild);
                }
                // Else the value is in the right subtree.
                else
                {
                    Debug.Assert(node.RightChild != null);

                    // Descend into the right subtree.
                    result = GetValue(index - 1 - n, node.RightChild);
                }
            }

            return result;
        }

        /// <summary>
        /// Sets the specified element in the current random access list 
        /// subtree 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 random access list  
        /// subtree element to set. 
        /// </param>
        /// <returns>
        /// A new random access list tree node with the element at the specified 
        /// position set to the specified value.
        /// </returns>
        public RalTreeNode SetValue(object value, int index)
        {
            return SetValue(value, index, this);
        }

        // Recursive method for setting the value at the specified position.
        private RalTreeNode SetValue(object value, int index, RalTreeNode node)
        {
            RalTreeNode result;

            // If the position of the value to set has been reached.
            if(index == 0)
            {
                // Set the value.
                result = new RalTreeNode(
                    value,
                    node.LeftChild,
                    node.RightChild);
            }
            // Else if the position of the value to set has not been reached.
            else
            {
                Debug.Assert(node.LeftChild != null);

                int n = Count / 2;

                // If the value is in the left subtree.
                if(index <= n)
                {
                    // Descend into the left subtree.
                    result = new RalTreeNode(
                        node.Value,
                        node.LeftChild.SetValue(value, index - 1),
                        node.RightChild);
                }
                // Else if the value is in the right subtree.
                else
                {
                    Debug.Assert(node.RightChild != null);

                    // Descend into the right subtree.
                    result = new RalTreeNode(
                        node.Value,
                        node.LeftChild,
                        node.RightChild.SetValue(value, index - 1 - n));
                }
            }

            return result;
        }

        #endregion

        #region Properties

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

        /// <summary>
        /// Gets the left child.
        /// </summary>
        public RalTreeNode LeftChild
        {
            get
            {
                return leftChild;
            }
        }

        /// <summary>
        /// Gets the right child.
        /// </summary>
        public RalTreeNode RightChild
        {
            get
            {
                return rightChild;
            }
        }

        /// <summary>
        /// Gets the value represented by this node.
        /// </summary>
        public object Value
        {
            get
            {
                return value;
            }
        }

        #endregion

        #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
Web01 | 2.8.141223.1 | Last Updated 24 Feb 2005
Article Copyright 2005 by Leslie Sanford
Everything else Copyright © CodeProject, 1999-2014
Layout: fixed | fluid