12,693,601 members (28,413 online)

103.2K views
89 bookmarked
Posted

# Persistent Data Structures

, 24 Feb 2005 MIT
An article describing the basic principles of persistent data structures.
 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 { /// /// Represents an array data structure. /// 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 /// /// Initialize an instance of the Array class with the specified array /// length. /// /// /// The length of the array. /// 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; } } /// /// Initializes a new instance of the Array class with the specified /// head of the random access list and the length of the array. /// /// /// The head of the random access list. /// /// /// The length of the array. /// private Array(RalTopNode head, int length) { this.head = head; this.length = length; } #endregion #region Methods /// /// Gets the value of the specified element in the current Array. /// /// /// An integer that represents the position of the Array element to /// get. /// /// /// The value at the specified position in the Array. /// /// /// index is outside the range of valid indexes for the current Array. /// public object GetValue(int index) { // Preconditions. if(index < 0 || index >= Length) { throw new ArgumentOutOfRangeException( "Index out of range."); } return head.GetValue(index); } /// /// Sets the specified element in the current Array to the specified /// value. /// /// /// The new value for the specified element. /// /// /// An integer that represents the position of the Array element to set. /// /// /// A new array with the element at the specified position set to the /// specified value. /// /// /// index is outside the range of valid indexes for the current Array. /// 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 /// /// Gets an integer that represents the total number of elements in all /// the dimensions of the Array. /// public int Length { get { return length; } } #endregion #endregion #region IEnumerable Members /// /// Returns an IEnumerator for the Array. /// /// /// An IEnumerator for the Array. /// public IEnumerator GetEnumerator() { return new RalEnumerator(head, length); } #endregion } } ```

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.

## Share

 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.