|
|
/*
* Created by: Leslie Sanford
*
* Last modified: 02/23/2005
*
* Contact: jabberdabber@hotmail.com
*/
using System;
using System.Collections;
using System.Diagnostics;
namespace ImmutableCollections
{
/// <summary>
/// Implements Chris Okasaki's random access list.
/// </summary>
public class RandomAccessList : IEnumerable
{
#region RandomAccessList Members
#region Class Fields
// Represents an empty random access list.
public static readonly RandomAccessList Empty = new RandomAccessList();
#endregion
#region Instance Fields
// The number of elements in the random access list.
private readonly int count;
// The first top node in the list.
private readonly RalTopNode first;
// A random access list representing the head of the current list.
private RandomAccessList head = null;
// A random access list representing the tail of the current list.
private RandomAccessList tail = null;
#endregion
#region Construction
/// <summary>
/// Initializes a new instance of the RandomAccessList class.
/// </summary>
public RandomAccessList()
{
count = 0;
first = null;
}
/// <summary>
/// Initializes a new instance of the RandomAccessList class with the
/// specified first top node and the number of elements in the list.
/// </summary>
/// <param name="first">
/// The first top node in the list.
/// </param>
/// <param name="count">
/// The number of nodes in the list.
/// </param>
private RandomAccessList(RalTopNode first, int count)
{
this.first = first;
this.count = count;
}
#endregion
#region Methods
/// <summary>
/// Prepends a value to the random access list.
/// </summary>
/// <param name="value">
/// The value to prepend to the list.
/// </param>
/// <returns>
/// A new random access list with the specified value prepended to the
/// list.
/// </returns>
public RandomAccessList Cons(object value)
{
RandomAccessList result;
// If the list is empty, or there is only one tree in the list, or
// the first tree is smaller than the second tree.
if(Count == 0 ||
first.NextNode == null ||
first.Root.Count < first.NextNode.Root.Count)
{
// Create a new first node with the specified value.
RalTreeNode newRoot = new RalTreeNode(value, null, null);
// Create a new random access list.
result = new RandomAccessList(
new RalTopNode(newRoot, first),
Count + 1);
}
// Else the first and second trees in the list are the same size.
else
{
Debug.Assert(first.Root.Count == first.NextNode.Root.Count);
// Create a new first node with the old first and second node
// as the left and right children respectively.
RalTreeNode newRoot = new RalTreeNode(
value,
first.Root,
first.NextNode.Root);
// Create a new random access list.
result = new RandomAccessList(
new RalTopNode(newRoot, first.NextNode.NextNode),
Count + 1);
}
return result;
}
/// <summary>
/// Gets the value at the specified position in the current
/// RandomAccessList.
/// </summary>
/// <param name="index">
/// An integer that represents the position of the RandomAccessList
/// element to get.
/// </param>
/// <returns>
/// The value at the specified position in the RandomAccessList.
/// </returns>
/// <exception cref="ArgumentOutOfRange">
/// index is outside the range of valid indexes for the current
/// RandomAccessList.
/// </exception>
public object GetValue(int index)
{
// Precondition.
if(index < 0 || index >= Count)
{
throw new ArgumentOutOfRangeException("index", index,
"Index out of range.");
}
return first.GetValue(index);
}
/// <summary>
/// Sets the specified element in the current RandomAccessList 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 RandomAccessList
/// element to set.
/// </param>
/// <returns>
/// A new RandomAccessList 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
/// RandomAccessList.
/// </exception>
public RandomAccessList SetValue(object value, int index)
{
// Precondition.
if(index < 0 || index >= Count)
{
throw new ArgumentOutOfRangeException("index", index,
"Index out of range.");
}
return new RandomAccessList(first.SetValue(value, index), Count);
}
#endregion
#region Properties
/// <summary>
/// Gets the number of elements in the RandomAccessList.
/// </summary>
public int Count
{
get
{
return count;
}
}
/// <summary>
/// Gets a RandomAccessList with first element of the current
/// RandomAccessList.
/// </summary>
/// <exception cref="InvalidOperationException">
/// If the RandomAccessList is empty.
/// </exception>
public RandomAccessList Head
{
get
{
// Preconditions.
if(Count == 0)
{
throw new InvalidOperationException(
"Cannot get the head of an empty random access list.");
}
if(head == null)
{
RalTreeNode newRoot = new RalTreeNode(
first.Root.Value, null, null);
RalTopNode newFirst = new RalTopNode(newRoot, null);
head = new RandomAccessList(newFirst, 1);
}
return head;
}
}
/// <summary>
/// Gets a RandomAccessList with all but the first element of the
/// current RandomAccessList.
/// </summary>
/// <exception cref="InvalidOperationException">
/// If the RandomAccessList is empty.
/// </exception>
public RandomAccessList Tail
{
get
{
// Precondition.
if(Count == 0)
{
throw new InvalidOperationException(
"Cannot get the tail of an empty random access list.");
}
if(tail == null)
{
if(Count == 1)
{
tail = Empty;
}
else
{
if(first.Root.Count > 1)
{
RalTreeNode left = first.Root.LeftChild;
RalTreeNode right = first.Root.RightChild;
RalTopNode newSecond = new RalTopNode(
right, first.NextNode);
RalTopNode newFirst = new RalTopNode(
left, newSecond);
tail = new RandomAccessList(newFirst, Count - 1);
}
else
{
tail = new RandomAccessList(first.NextNode, Count - 1);
}
}
}
return tail;
}
}
#endregion
#endregion
#region IEnumerable Members
/// <summary>
/// Returns an IEnumerator for the RandomAccessList.
/// </summary>
/// <returns>
/// An IEnumerator for the RandomAccessList.
/// </returns>
public IEnumerator GetEnumerator()
{
return new RalEnumerator(first, 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.
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.
Submit an article or tip