//******************************
// Written by Peter Golde
// Copyright (c) 2004-2005, Wintellect
//
// Use and restribution of this code is subject to the license agreement
// contained in the file "License.txt" accompanying this file.
//******************************
using System;
using System.Collections.Generic;
using System.Collections;
using System.Diagnostics;
// CONSIDER: provide more efficient implementation of CopyTo.
namespace Wintellect.PowerCollections
{
/// <summary>
/// BigList<T> provides a list of items, in order, with indices of the items ranging from 0 to one less
/// than the count of items in the collection. BigList<T> is optimized for efficient operations on large (>100 items)
/// lists, especially for insertions, deletions, copies, and concatinations.
/// </summary>
/// <remarks>
/// <para>BigList<T> class is similar in functionality to the standard List<T> class. Both classes
/// provide a collection that stores an set of items in order, with indices of the items ranging from 0 to one less
/// than the count of items in the collection. Both classes provide the ability to add and remove items from any index,
/// and the get or set the item at any index.</para>
/// <para>BigList<T> differs significantly from List<T> in the performance of various operations,
/// especially when the lists become large (several hundred items or more). With List<T>, inserting or removing
/// elements from anywhere in a large list except the end is very inefficient -- every item after the point of inserting
/// or deletion has to be moved in the list. The BigList<T> class, however, allows for fast insertions
/// and deletions anywhere in the list. Furthermore, BigList<T> allows copies of a list, sub-parts
/// of a list, and concatinations of two lists to be very fast. When a copy is made of part or all of a BigList,
/// two lists shared storage for the parts of the lists that are the same. Only when one of the lists is changed is additional
/// memory allocated to store the distinct parts of the lists.</para>
/// <para>Of course, there is a small price to pay for this extra flexibility. Although still quite efficient, using an
/// index to get or change one element of a BigList, while still reasonably efficient, is significantly slower than using
/// a plain List. Because of this, if you want to process every element of a BigList, using a foreach loop is a lot
/// more efficient than using a for loop and indexing the list.</para>
/// <para>In general, use a List when the only operations you are using are Add (to the end), foreach,
/// or indexing, or you are very sure the list will always remain small (less than 100 items). For large (>100 items) lists
/// that do insertions, removals, copies, concatinations, or sub-ranges, BigList will be more efficient than List.
/// In almost all cases, BigList is more efficient and easier to use than LinkedList.</para>
/// </remarks>
/// <typeparam name="T">The type of items to store in the BigList.</typeparam>
[Serializable]
public class BigList<T>: ListBase<T>, ICloneable
{
const uint MAXITEMS = int.MaxValue - 1; // maximum number of items in a BigList.
#if DEBUG
const int MAXLEAF = 8; // Maximum number of elements in a leaf node -- small for debugging purposes.
#else
const int MAXLEAF = 120; // Maximum number of elements in a leaf node.
#endif
const int BALANCEFACTOR = 6; // how far the root must be in depth from fully balanced to invoke the rebalance operation (min 3).
// The fibonacci numbers. Used in the rebalancing algorithm. Final MaxValue makes sure we don't go off the end.
static readonly int[] FIBONACCI = {1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584,
4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040,
1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817, 39088169, 63245986,
102334155, 165580141, 267914296, 433494437, 701408733, 1134903170, 1836311903, int.MaxValue};
const int MAXFIB = 44; // maximum index in the above, not counting the final MaxValue.
// If null, the BigList is empty. If non-null, the list has at least one item.
private Node root;
// Holds the change stamp for the collection.
private int changeStamp;
/// <summary>
/// Must be called whenever there is a structural change in the tree. Causes
/// changeStamp to be changed, which causes any in-progress enumerations
/// to throw exceptions.
/// </summary>
private void StopEnumerations()
{
++changeStamp;
}
/// <summary>
/// Checks the given stamp against the current change stamp. If different, the
/// collection has changed during enumeration and an InvalidOperationException
/// must be thrown
/// </summary>
/// <param name="startStamp">changeStamp at the start of the enumeration.</param>
private void CheckEnumerationStamp(int startStamp)
{
if (startStamp != changeStamp) {
throw new InvalidOperationException(Strings.ChangeDuringEnumeration);
}
}
/// <summary>
/// Creates a new BigList. The BigList is initially empty.
/// </summary>
/// <remarks>Creating a empty BigList takes constant time and consumes a very small amount of memory.</remarks>
public BigList()
{
root = null;
}
/// <summary>
/// Creates a new BigList initialized with the items from <paramref name="collection"/>, in order.
/// </summary>
/// <remarks>Initializing the tree list with the elements of collection takes time O(N), where N is the number of
/// items in <paramref name="collection"/>.</remarks>
/// <param name="collection">The collection used to initialize the BigList. </param>
/// <exception cref="ArgumentNullException"><paramref name="collection"/> is null.</exception>
public BigList(IEnumerable<T> collection)
{
if (collection == null)
throw new ArgumentNullException("collection");
root = NodeFromEnumerable(collection);
CheckBalance();
}
/// <summary>
/// Creates a new BigList initialized with a given number of copies of the items from <paramref name="collection"/>, in order.
/// </summary>
/// <remarks>Initializing the tree list with the elements of collection takes time O(N + log K), where N is the number of
/// items in <paramref name="collection"/>, and K is the number of copies.</remarks>
/// <param name="copies">Number of copies of the collection to use.</param>
/// <param name="collection">The collection used to initialize the BigList. </param>
/// <exception cref="ArgumentOutOfRangeException"><paramref name="copies"/> is negative.</exception>
/// <exception cref="ArgumentNullException"><paramref name="collection"/> is null.</exception>
public BigList(IEnumerable<T> collection, int copies)
{
if (collection == null)
throw new ArgumentNullException("collection");
root = NCopiesOfNode(copies, NodeFromEnumerable(collection));
CheckBalance();
}
/// <summary>
/// Creates a new BigList that is a copy of <paramref name="list"/>.
/// </summary>
/// <remarks>Copying a BigList takes constant time, and little
/// additional memory, since the storage for the items of the two lists is shared. However, changing
/// either list will take additional time and memory. Portions of the list are copied when they are changed.</remarks>
/// <param name="list">The BigList to copy. </param>
/// <exception cref="ArgumentNullException"><paramref name="list"/> is null.</exception>
public BigList(BigList<T> list)
{
if (list == null)
throw new ArgumentNullException("list");
if (list.root == null)
root = null;
else {
list.root.MarkShared();
root = list.root;
}
}
/// <summary>
/// Creates a new BigList that is several copies of <paramref name="list"/>.
/// </summary>
/// <remarks>Creating K copies of a BigList takes time O(log K), and O(log K)
/// additional memory, since the storage for the items of the two lists is shared. However, changing
/// either list will take additional time and memory. Portions of the list are copied when they are changed.</remarks>
/// <param name="copies">Number of copies of the collection to use.</param>
/// <param name="list">The BigList to copy. </param>
/// <exception cref="ArgumentNullException"><paramref name="list"/> is null.</exception>
public BigList(BigList<T> list, int copies)
{
if (list == null)
throw new ArgumentNullException("list");
if (list.root == null)
root = null;
else {
list.root.MarkShared();
root = NCopiesOfNode(copies, list.root);
}
}
/// <summary>
/// Creates a new BigList from the indicated Node.
/// </summary>
/// <param name="node">Node that becomes the new root. If null, the new BigList is empty.</param>
private BigList(Node node)
{
this.root = node;
CheckBalance();
}
/// <summary>
/// Gets the number of items stored in the BigList. The indices of the items
/// range from 0 to Count-1.
/// </summary>
/// <remarks>Getting the number of items in the BigList takes constant time.</remarks>
/// <value>The number of items in the BigList.</value>
public sealed override int Count
{
get
{
if (root == null)
return 0;
else
return root.Count;
}
}
/// <summary>
/// Gets or sets an item in the list, by index.
/// </summary>
/// <remarks><para> Gettingor setting an item takes time O(log N), where N is the number of items
/// in the list.</para>
/// <para>To process each of the items in the list, using GetEnumerator() or a foreach loop is more efficient
/// that accessing each of the elements by index.</para></remarks>
/// <param name="index">The index of the item to get or set. The first item in the list
/// has index 0, the last item has index Count-1.</param>
/// <returns>The value of the item at the given index.</returns>
/// <exception cref="ArgumentOutOfRangeException"><paramref name="index"/> is less than zero or
/// greater than or equal to Count.</exception>
public sealed override T this[int index]
{
get
{
// This could just be a simple call to GetAt on the root.
// It is recoded as an interative algorithm for performance.
if (root == null || index < 0 || index >= root.Count)
throw new ArgumentOutOfRangeException("index");
Node current = root;
ConcatNode curConcat = current as ConcatNode;
while (curConcat != null) {
int leftCount = curConcat.left.Count;
if (index < leftCount)
current = curConcat.left;
else {
current = curConcat.right;
index -= leftCount;
}
curConcat = current as ConcatNode;
}
LeafNode curLeaf = (LeafNode)current;
return curLeaf.items[index];
}
set
{
// This could just be a simple call to SetAtInPlace on the root.
// It is recoded as an interative algorithm for performance.
if (root == null || index < 0 || index >= root.Count)
throw new ArgumentOutOfRangeException("index");
// Like List<T>, we stop enumerations after a set operation. This could be made
// to not happen, but it would be complex, because set operations on a shared node
// could change the node.
StopEnumerations();
if (root.Shared)
root = root.SetAt(index, value);
Node current = root;
ConcatNode curConcat = current as ConcatNode;
while (curConcat != null) {
int leftCount = curConcat.left.Count;
if (index < leftCount) {
current = curConcat.left;
if (current.Shared) {
curConcat.left = current.SetAt(index, value);
return;
}
}
else {
current = curConcat.right;
index -= leftCount;
if (current.Shared) {
curConcat.right = current.SetAt(index, value);
return;
}
}
curConcat = current as ConcatNode;
}
LeafNode curLeaf = (LeafNode)current;
curLeaf.items[index] = value;
}
}
/// <summary>
/// Removes all of the items from the BigList.
/// </summary>
/// <remarks>Clearing a BigList takes constant time.</remarks>
public sealed override void Clear()
{
StopEnumerations();
root = null;
}
/// <summary>
/// Inserts a new item at the given index in the BigList. All items at indexes
/// equal to or greater than <paramref name="index"/> move up one index.
/// </summary>
/// <remarks>The amount of time to insert an item is O(log N), no matter where
/// in the list the insertion occurs. Inserting an item at the beginning or end of the
/// list is O(N).
/// </remarks>
/// <param name="index">The index to insert the item at. After the
/// insertion, the inserted item is located at this index. The
/// first item has index 0.</param>
/// <param name="item">The item to insert at the given index.</param>
/// <exception cref="ArgumentOutOfRangeException"><paramref name="index"/> is
/// less than zero or greater than Count.</exception>
public sealed override void Insert(int index, T item)
{
StopEnumerations();
if ((uint)Count + 1 > MAXITEMS)
throw new InvalidOperationException(Strings.CollectionTooLarge);
if (index <= 0 || index >= Count) {
if (index == 0)
AddToFront(item);
else if (index == Count)
Add(item);
else
throw new ArgumentOutOfRangeException("index");
}
else {
if (root == null)
root = new LeafNode(item);
else {
Node newRoot = root.InsertInPlace(index, item);
if (newRoot != root) {
root = newRoot;
CheckBalance();
}
}
}
}
/// <summary>
/// Inserts a collection of items at the given index in the BigList. All items at indexes
/// equal to or greater than <paramref name="index"/> increase their indices
/// by the number of items inserted.
/// </summary>
/// <remarks>The amount of time to insert an arbitrary collection in the BigList is O(M + log N),
/// where M is the number of items inserted, and N is the number of items in the list.
/// </remarks>
/// <param name="index">The index to insert the collection at. After the
/// insertion, the first item of the inserted collection is located at this index. The
/// first item has index 0.</param>
/// <param name="collection">The collection of items to insert at the given index.</param>
/// <exception cref="ArgumentOutOfRangeException"><paramref name="index"/> is
/// less than zero or greater than Count.</exception>
/// <exception cref="ArgumentNullException"><paramref name="collection"/> is null.</exception>
public void InsertRange(int index, IEnumerable<T> collection)
{
StopEnumerations();
if (collection == null)
throw new ArgumentNullException("collection");
if (index <= 0 || index >= Count) {
if (index == 0)
AddRangeToFront(collection);
else if (index == Count)
AddRange(collection);
else
throw new ArgumentOutOfRangeException("index");
}
else {
Node node = NodeFromEnumerable(collection);
if (node == null)
return;
else if (root == null)
root = node;
else {
if ((uint)Count + (uint)node.Count > MAXITEMS)
throw new InvalidOperationException(Strings.CollectionTooLarge);
Node newRoot = root.InsertInPlace(index, node, true);
if (newRoot != root) {
root = newRoot;
CheckBalance();
}
}
}
}
/// <summary>
/// Inserts a BigList of items at the given index in the BigList. All items at indexes
/// equal to or greater than <paramref name="index"/> increase their indices
/// by the number of items inserted.
/// </summary>
/// <remarks>The amount of time to insert another BigList is O(log N),
/// where N is the number of items in the list, regardless of the number of items in the
/// inserted list. Storage is shared between the two lists until one of them is changed.
/// </remarks>
/// <param name="index">The index to insert the collection at. After the
/// insertion, the first item of the inserted collection is located at this index. The
/// first item has index 0.</param>
/// <param name="list">The BigList of items to insert at the given index.</param>
/// <exception cref="ArgumentOutOfRangeException"><paramref name="index"/> is
/// less than zero or greater than Count.</exception>
/// <exception cref="ArgumentNullException"><paramref name="list"/> is null.</exception>
public void InsertRange(int index, BigList<T> list)
{
StopEnumerations();
if (list == null)
throw new ArgumentNullException("list");
if ((uint)Count + (uint)list.Count > MAXITEMS)
throw new InvalidOperationException(Strings.CollectionTooLarge);
if (index <= 0 || index >= Count) {
if (index == 0)
AddRangeToFront(list);
else if (index == Count)
AddRange(list);
else
throw new ArgumentOutOfRangeException("index");
}
else {
if (list.Count == 0)
return;
if (root == null) {
list.root.MarkShared();
root = list.root;
}
else {
if (list.root == root)
root.MarkShared(); // make sure inserting into itself works.
Node newRoot = root.InsertInPlace(index, list.root, false);
if (newRoot != root) {
root = newRoot;
CheckBalance();
}
}
}
}
/// <summary>
/// Removes the item at the given index in the BigList. All items at indexes
/// greater than <paramref name="index"/> move down one index.
/// </summary>
/// <remarks>The amount of time to delete an item in the BigList is O(log N),
/// where N is the number of items in the list.
/// </remarks>
/// <param name="index">The index in the list to remove the item at. The
/// first item in the list has index 0.</param>
/// <exception cref="ArgumentOutOfRangeException"><paramref name="index"/> is
/// less than zero or greater than or equal to Count.</exception>
public sealed override void RemoveAt(int index)
{
RemoveRange(index, 1);
}
/// <summary>
/// Removes a range of items at the given index in the Deque. All items at indexes
/// greater than <paramref name="index"/> move down <paramref name="count"/> indices
/// in the Deque.
/// </summary>
/// <remarks>The amount of time to delete <paramref name="count"/> items in the Deque is proportional
/// to the distance of index from the closest end of the Deque, plus <paramref name="count"/>:
/// O(count + Min(<paramref name="index"/>, Count - 1 - <paramref name="index"/>)).
/// </remarks>
/// <param name="index">The index in the list to remove the range at. The
/// first item in the list has index 0.</param>
/// <param name="count">The number of items to remove.</param>
/// <exception cref="ArgumentOutOfRangeException"><paramref name="index"/> is
/// less than zero or greater than or equal to Count, or <paramref name="count"/> is less than zero
/// or too large.</exception>
public void RemoveRange(int index, int count)
{
if (count == 0)
return; // nothing to do.
if (index < 0 || index >= Count)
throw new ArgumentOutOfRangeException("index");
if (count < 0 || count > Count - index)
throw new ArgumentOutOfRangeException("count");
StopEnumerations();
Node newRoot = root.RemoveRangeInPlace(index, index + count - 1);
if (newRoot != root) {
root = newRoot;
CheckBalance();
}
}
/// <summary>
/// Adds an item to the end of the BigList. The indices of all existing items
/// in the Deque are unchanged.
/// </summary>
/// <remarks>Adding an item takes, on average, constant time.</remarks>
/// <param name="item">The item to add.</param>
public sealed override void Add(T item)
{
if ((uint)Count + 1 > MAXITEMS)
throw new InvalidOperationException(Strings.CollectionTooLarge);
StopEnumerations();
if (root == null)
root = new LeafNode(item);
else {
Node newRoot = root.AppendInPlace(item);
if (newRoot != root) {
root = newRoot;
CheckBalance();
}
}
}
/// <summary>
/// Adds an item to the beginning of the BigList. The indices of all existing items
/// in the Deque are increased by one, and the new item has index zero.
/// </summary>
/// <remarks>Adding an item takes, on average, constant time.</remarks>
/// <param name="item">The item to add.</param>
public void AddToFront(T item)
{
if ((uint)Count + 1 > MAXITEMS)
throw new InvalidOperationException(Strings.CollectionTooLarge);
StopEnumerations();
if (root == null)
root = new LeafNode(item);
else {
Node newRoot = root.PrependInPlace(item);
if (newRoot != root) {
root = newRoot;
CheckBalance();
}
}
}
/// <summary>
/// Adds a collection of items to the end of BigList. The indices of all existing items
/// are unchanged. The last item in the added collection becomes the
/// last item in the BigList.
/// </summary>
/// <remarks>This method takes time O(M + log N), where M is the number of items in the
/// <paramref name="collection"/>, and N is the size of the BigList.</remarks>
/// <param name="collection">The collection of items to add.</param>
/// <exception cref="ArgumentNullException"><paramref name="collection"/> is null.</exception>
public void AddRange(IEnumerable<T> collection)
{
if (collection == null)
throw new ArgumentNullException("collection");
StopEnumerations();
Node node = NodeFromEnumerable(collection);
if (node == null)
return;
else if (root == null) {
root = node;
CheckBalance();
}
else {
if ((uint)Count + (uint)node.count > MAXITEMS)
throw new InvalidOperationException(Strings.CollectionTooLarge);
Node newRoot = root.AppendInPlace(node, true);
if (newRoot != root) {
root = newRoot;
CheckBalance();
}
}
}
/// <summary>
/// Adds a collection of items to the front of BigList. The indices of all existing items
/// in the are increased by the number of items in <paramref name="collection"/>.
/// The first item in the added collection becomes the first item in the BigList.
/// </summary>
/// <remarks>This method takes time O(M + log N), where M is the number of items in the
/// <paramref name="collection"/>, and N is the size of the BigList.</remarks>
/// <param name="collection">The collection of items to add.</param>
/// <exception cref="ArgumentNullException"><paramref name="collection"/> is null.</exception>
public void AddRangeToFront(IEnumerable<T> collection)
{
if (collection == null)
throw new ArgumentNullException("collection");
StopEnumerations();
Node node = NodeFromEnumerable(collection);
if (node == null)
return;
else if (root == null) {
root = node;
CheckBalance();
}
else {
if ((uint)Count + (uint)node.Count > MAXITEMS)
throw new InvalidOperationException(Strings.CollectionTooLarge);
Node newRoot = root.PrependInPlace(node, true);
if (newRoot != root) {
root = newRoot;
CheckBalance();
}
}
}
/// <summary>
/// Creates a new BigList that is a copy of this list.
/// </summary>
/// <remarks>Copying a BigList takes constant time, and little
/// additional memory, since the storage for the items of the two lists is shared. However, changing
/// either list will take additional time and memory. Portions of the list are copied when they are changed.</remarks>
/// <returns>A copy of the current list</returns>
public BigList<T> Clone()
{
if (root == null)
return new BigList<T>();
else {
root.MarkShared();
return new BigList<T>(root);
}
}
/// <summary>
/// Creates a new BigList that is a copy of this list.
/// </summary>
/// <remarks>Copying a BigList takes constant time, and little
/// additional memory, since the storage for the items of the two lists is shared. However, changing
/// either list will take additional time and memory. Portions of the list are copied when they are changed.</remarks>
/// <returns>A copy of the current list</returns>
object ICloneable.Clone()
{
return Clone();
}
/// <summary>
/// Makes a deep clone of this BigList. A new BigList is created with a clone of
/// each element of this set, by calling ICloneable.Clone on each element. If T is
/// a value type, then this method is the same as Clone.
/// </summary>
/// <remarks><para>If T is a reference type, it must implement
/// ICloneable. Otherwise, an InvalidOperationException is thrown.</para>
/// <para>If T is a reference type, cloning the list takes time approximate O(N), where N is the number of items in the list.</para></remarks>
/// <returns>The cloned set.</returns>
/// <exception cref="InvalidOperationException">T is a reference type that does not implement ICloneable.</exception>
public BigList<T> CloneContents()
{
if (root == null)
return new BigList<T>();
else {
bool itemIsValueType;
if (!Util.IsCloneableType(typeof(T), out itemIsValueType))
throw new InvalidOperationException(string.Format(Strings.TypeNotCloneable, typeof(T).FullName));
if (itemIsValueType)
return Clone();
// Create a new list by converting each item in this list via cloning.
return new BigList<T>(Algorithms.Convert<T,T>(this, delegate(T item) {
if (item == null)
return default(T); // Really null, because we know T is a reference type
else
return (T)(((ICloneable)item).Clone());
}));
}
}
/// <summary>
/// Adds a BigList of items to the end of BigList. The indices of all existing items
/// are unchanged. The last item in <paramref name="list"/> becomes the
/// last item in this list. The added list <paramref name="list"/> is unchanged.
/// </summary>
/// <remarks>This method takes, on average, constant time, regardless of the size
/// of either list. Although conceptually all of the items in <paramref name="list"/> are
/// copied, storage is shared between the two lists until changes are made to the
/// shared sections.</remarks>
/// <param name="list">The list of items to add.</param>
/// <exception cref="ArgumentNullException"><paramref name="list"/> is null.</exception>
public void AddRange(BigList<T> list)
{
if (list == null)
throw new ArgumentNullException("list");
if ((uint)Count + (uint)list.Count > MAXITEMS)
throw new InvalidOperationException(Strings.CollectionTooLarge);
if (list.Count == 0)
return;
StopEnumerations();
if (root == null) {
list.root.MarkShared();
root = list.root;
}
else {
Node newRoot = root.AppendInPlace(list.root, false);
if (newRoot != root) {
root = newRoot;
CheckBalance();
}
}
}
/// <summary>
/// Adds a BigList of items to the front of BigList. The indices of all existing items
/// are increased by the number of items in <paramref name="list"/>. The first item in <paramref name="list"/>
/// becomes the first item in this list. The added list <paramref name="list"/> is unchanged.
/// </summary>
/// <remarks>This method takes, on average, constant time, regardless of the size
/// of either list. Although conceptually all of the items in <paramref name="list"/> are
/// copied, storage is shared between the two lists until changes are made to the
/// shared sections.</remarks>
/// <param name="list">The list of items to add.</param>
/// <exception cref="ArgumentNullException"><paramref name="list"/> is null.</exception>
public void AddRangeToFront(BigList<T> list)
{
if (list == null)
throw new ArgumentNullException("list");
if ((uint)Count + (uint)list.Count > MAXITEMS)
throw new InvalidOperationException(Strings.CollectionTooLarge);
if (list.Count == 0)
return;
StopEnumerations();
if (root == null) {
list.root.MarkShared();
root = list.root;
}
else {
Node newRoot = root.PrependInPlace(list.root, false);
if (newRoot != root) {
root = newRoot;
CheckBalance();
}
}
}
/// <summary>
/// Concatenates two lists together to create a new list. Both lists being concatenated
/// are unchanged. The resulting list contains all the items in <paramref name="first"/>, followed
/// by all the items in <paramref name="second"/>.
/// </summary>
/// <remarks>This method takes, on average, constant time, regardless of the size
/// of either list. Although conceptually all of the items in both lists are
/// copied, storage is shared until changes are made to the
/// shared sections.</remarks>
/// <param name="first">The first list to concatenate.</param>
/// <param name="second">The second list to concatenate.</param>
/// <exception cref="ArgumentNullException"><paramref name="first"/> or <paramref name="second"/> is null.</exception>
public static BigList<T> operator +(BigList<T> first, BigList<T> second)
{
if (first == null)
throw new ArgumentNullException("first");
if (second == null)
throw new ArgumentNullException("second");
if ((uint)first.Count + (uint)second.Count > MAXITEMS)
throw new InvalidOperationException(Strings.CollectionTooLarge);
if (first.Count == 0)
return second.Clone();
else if (second.Count == 0)
return first.Clone();
else {
BigList<T> result = new BigList<T>(first.root.Append(second.root, false));
result.CheckBalance();
return result;
}
}
/// <summary>
/// Creates a new list that contains a subrange of elements from this list. The
/// current list is unchanged.
/// </summary>
/// <remarks>This method takes take O(log N), where N is the size of the current list. Although
/// the sub-range is conceptually copied, storage is shared between the two lists until a change
/// is made to the shared items.</remarks>
/// <remarks>If a view of a sub-range is desired, instead of a copy, use the
/// more efficient <see cref="Range"/> method, which provides a view onto a sub-range of items.</remarks>
/// <param name="index">The starting index of the sub-range.</param>
/// <param name="count">The number of items in the sub-range. If this is zero,
/// the returned list is empty.</param>
/// <returns>A new list with the <paramref name="count"/> items that start at <paramref name="index"/>.</returns>
public BigList<T> GetRange(int index, int count)
{
if (count == 0)
return new BigList<T>();
if (index < 0 || index >= Count)
throw new ArgumentOutOfRangeException("index");
if (count < 0 || count > Count - index)
throw new ArgumentOutOfRangeException("count");
return new BigList<T>(root.Subrange(index, index + count - 1));
}
/// <summary>
/// Returns a view onto a sub-range of this list. Items are not copied; the
/// returned IList<T> is simply a different view onto the same underlying items. Changes to this list
/// are reflected in the view, and vice versa. Insertions and deletions in the view change the size of the
/// view, but insertions and deletions in the underlying list do not.
/// </summary>
/// <remarks>
/// <para>If a copy of the sub-range is desired, use the <see cref="GetRange"/> method instead.</para>
/// <para>This method can be used to apply an algorithm to a portion of a list. For example:</para>
/// <code>Algorithms.ReverseInPlace(list.Range(3, 6))</code>
/// will reverse the 6 items beginning at index 3.</remarks>
/// <param name="index">The starting index of the view.</param>
/// <param name="count">The number of items in the view.</param>
/// <returns>A list that is a view onto the given sub-list. </returns>
/// <exception cref="ArgumentOutOfRangeException"><paramref name="index"/> or <paramref name="count"/> is negative.</exception>
/// <exception cref="ArgumentOutOfRangeException"><paramref name="index"/> + <paramref name="count"/> is greater than the
/// size of this list.</exception>
public sealed override IList<T> Range(int index, int count)
{
if (index < 0 || index > this.Count || (index == this.Count && count != 0))
throw new ArgumentOutOfRangeException("index");
if (count < 0 || count > this.Count || count + index > this.Count)
throw new ArgumentOutOfRangeException("count");
return new BigListRange(this, index, count);
}
/// <summary>
/// Enumerates a range of the items in the list, in order. The item at <paramref name="start"/>
/// is enumerated first, then the next item at index 1, and so on. At most <paramref name="maxItems"/>
/// items are enumerated.
/// </summary>
/// <remarks>Enumerating all of the items in the list take time O(N), where
/// N is the number of items being enumerated. Using GetEnumerator() or foreach
/// is much more efficient than accessing all items by index.</remarks>
/// <param name="start">Index to start enumerating at.</param>
/// <param name="maxItems">Max number of items to enumerate.</param>
/// <returns>An IEnumerator<T> that enumerates all the
/// items in the given range.</returns>
private IEnumerator<T> GetEnumerator(int start, int maxItems)
{
// We could use a recursive enumerator here, but an explicit stack
// is a lot more efficient, and efficiency matters here.
int startStamp = changeStamp; // to detect changes during enumeration.
if (root != null && maxItems > 0) {
ConcatNode[] stack = new ConcatNode[root.Depth];
bool[] leftStack = new bool[root.Depth];
int stackPtr = 0, startIndex = 0;
Node current = root;
LeafNode currentLeaf;
ConcatNode currentConcat;
if (start != 0) {
// Set current to the node containing start, and set startIndex to
// the index within that node.
if (start < 0 || start >= root.Count)
throw new ArgumentOutOfRangeException("start");
currentConcat = current as ConcatNode;
startIndex = start;
while (currentConcat != null) {
stack[stackPtr] = currentConcat;
int leftCount = currentConcat.left.Count;
if (startIndex < leftCount) {
leftStack[stackPtr] = true;
current = currentConcat.left;
}
else {
leftStack[stackPtr] = false;
current = currentConcat.right;
startIndex -= leftCount;
}
++stackPtr;
currentConcat = current as ConcatNode;
}
}
for (; ; ) {
// If not already at a leaf, walk to the left to find a leaf node.
while ((currentConcat = current as ConcatNode) != null) {
stack[stackPtr] = currentConcat;
leftStack[stackPtr] = true;
++stackPtr;
current = currentConcat.left;
}
// Iterate the leaf.
currentLeaf = (LeafNode)current;
int limit = currentLeaf.Count;
if (limit > startIndex + maxItems)
limit = startIndex + maxItems;
for (int i = startIndex; i < limit; ++i) {
yield return currentLeaf.items[i];
CheckEnumerationStamp(startStamp);
}
// Update the number of items to interate.
maxItems -= limit - startIndex;
if (maxItems <= 0)
yield break; // Done!
// From now on, start enumerating at 0.
startIndex = 0;
// Go back up the stack until we find a place to the right
// we didn't just come from.
for (; ; ) {
ConcatNode parent;
if (stackPtr == 0)
yield break; // iteration is complete.
parent = stack[--stackPtr];
if (leftStack[stackPtr]) {
leftStack[stackPtr] = false;
++stackPtr;
current = parent.right;
break;
}
current = parent;
// And keep going up...
}
// current is now a new node we need to visit. Loop around to get it.
}
}
}
/// <summary>
/// Enumerates all of the items in the list, in order. The item at index 0
/// is enumerated first, then the item at index 1, and so on. Usually, the
/// foreach statement is used to call this method implicitly.
/// </summary>
/// <remarks>Enumerating all of the items in the list take time O(N), where
/// N is the number of items in the list. Using GetEnumerator() or foreach
/// is much more efficient than accessing all items by index.</remarks>
/// <returns>An IEnumerator<T> that enumerates all the
/// items in the list.</returns>
public sealed override IEnumerator<T> GetEnumerator()
{
return GetEnumerator(0, int.MaxValue);
}
/// <summary>
/// Given an IEnumerable<T>, create a new Node with all of the
/// items in the enumerable. Returns null if the enumerable has no items.
/// </summary>
/// <param name="collection">The collection to copy.</param>
/// <returns>Returns a Node, not shared or with any shared children,
/// with the items from the collection. If the collection was empty,
/// null is returned.</returns>
private Node NodeFromEnumerable(IEnumerable<T> collection)
{
Node node = null;
LeafNode leaf;
IEnumerator<T> enumerator = collection.GetEnumerator();
while ((leaf = LeafFromEnumerator(enumerator)) != null) {
if (node == null)
node = leaf;
else {
if ((uint)(node.count) + (uint)(leaf.count) > MAXITEMS)
throw new InvalidOperationException(Strings.CollectionTooLarge);
node = node.AppendInPlace(leaf, true);
}
}
return node;
}
/// <summary>
/// Consumes up to MAXLEAF items from an Enumerator and places them in a leaf
/// node. If the enumerator is at the end, null is returned.
/// </summary>
/// <param name="enumerator">The enumerator to take items from.</param>
/// <returns>A LeafNode with items taken from the enumerator. </returns>
private LeafNode LeafFromEnumerator(IEnumerator<T> enumerator)
{
int i = 0;
T[] items = null;
while (i < MAXLEAF && enumerator.MoveNext()) {
if (i == 0)
items = new T[MAXLEAF];
items[i++] = enumerator.Current;
}
if (items != null)
return new LeafNode(i, items);
else
return null;
}
/// <summary>
/// Create a node that has N copies of the given node.
/// </summary>
/// <param name="copies">Number of copies. Must be non-negative.</param>
/// <param name="node">Node to make copies of.</param>
/// <returns>null if node is null or copies is 0. Otherwise, a node consisting of <paramref name="copies"/> copies
/// of node.</returns>
/// <exception cref="ArgumentOutOfRangeException">copies is negative.</exception>
private Node NCopiesOfNode(int copies, Node node)
{
if (copies < 0)
throw new ArgumentOutOfRangeException("copies", Strings.ArgMustNotBeNegative);
// Do the simple cases.
if (copies == 0 || node == null)
return null;
if (copies == 1)
return node;
if ((long)copies * (long)(node.count) > MAXITEMS)
throw new InvalidOperationException(Strings.CollectionTooLarge);
// Build up the copies by powers of two.
int n = 1;
Node power = node, builder = null;
while (copies > 0) {
power.MarkShared();
if ((copies & n) != 0) {
// This power of two is used in the final result.
copies -= n;
if (builder == null)
builder = power;
else
builder = builder.Append(power, false);
}
n *= 2;
power = power.Append(power, false);
}
return builder;
}
/// <summary>
/// Check the balance of the current tree and rebalance it if it is more than BALANCEFACTOR
/// levels away from fully balanced. Note that rebalancing a tree may leave it two levels away from
/// fully balanced.
/// </summary>
private void CheckBalance()
{
if (root != null &&
(root.Depth > BALANCEFACTOR && !(root.Depth - BALANCEFACTOR <= MAXFIB && Count >= FIBONACCI[root.Depth - BALANCEFACTOR])))
{
Rebalance();
}
}
/// <summary>
/// Rebalance the current tree. Once rebalanced, the depth of the current tree is no more than
/// two levels from fully balanced, where fully balanced is defined as having Fibonacci(N+2) or more items
/// in a tree of depth N.
/// </summary>
/// <remarks>The rebalancing algorithm is from "Ropes: an Alternative to Strings", by
/// Boehm, Atkinson, and Plass, in SOFTWARE--PRACTICE AND EXPERIENCE, VOL. 25(12), 1315–1330 (DECEMBER 1995).
/// </remarks>
internal void Rebalance()
{
Node[] rebalanceArray;
int slots;
// The basic rebalancing algorithm is add nodes to a rabalance array, where a node at index K in the
// rebalance array has Fibonacci(K+1) to Fibonacci(K+2) items, and the entire list has the nodes
// from largest to smallest concatenated.
if (root == null)
return;
if (root.Depth <= 1 || (root.Depth-2 <= MAXFIB && Count >= FIBONACCI[root.Depth-2]))
return; // already sufficiently balanced.
// How many slots does the rebalance array need?
for (slots = 0; slots <= MAXFIB; ++slots)
if (root.Count < FIBONACCI[slots])
break;
rebalanceArray = new Node[slots];
// Add all the nodes to the rebalance array.
AddNodeToRebalanceArray(rebalanceArray, root, false);
// Concatinate all the node in the rebalance array.
Node result = null;
for (int slot = 0; slot < slots; ++slot) {
Node n = rebalanceArray[slot];
if (n != null) {
if (result == null)
result = n;
else
result = result.PrependInPlace(n, !n.Shared);
}
}
// And we're done. Check that it worked!
root = result;
Debug.Assert(root.Depth <= 1 || (root.Depth - 2 <= MAXFIB && Count >= FIBONACCI[root.Depth - 2]));
}
/// <summary>
/// Part of the rebalancing algorithm. Adds a node to the rebalance array. If it is already balanced, add it directly, otherwise
/// add its children.
/// </summary>
/// <param name="rebalanceArray">Rebalance array to insert into.</param>
/// <param name="node">Node to add.</param>
/// <param name="shared">If true, mark the node as shared before adding, because one
/// of its parents was shared.</param>
private void AddNodeToRebalanceArray(Node[] rebalanceArray, Node node, bool shared)
{
if (node.Shared)
shared = true;
if (node.IsBalanced()) {
if (shared)
node.MarkShared();
AddBalancedNodeToRebalanceArray(rebalanceArray, node);
}
else {
ConcatNode n = (ConcatNode)node; // leaf nodes are always balanced.
AddNodeToRebalanceArray(rebalanceArray, n.left, shared);
AddNodeToRebalanceArray(rebalanceArray, n.right, shared);
}
}
/// <summary>
/// Part of the rebalancing algorithm. Adds a balanced node to the rebalance array.
/// </summary>
/// <param name="rebalanceArray">Rebalance array to insert into.</param>
/// <param name="balancedNode">Node to add.</param>
private void AddBalancedNodeToRebalanceArray(Node[] rebalanceArray, Node balancedNode)
{
int slot;
int count;
Node accum = null;
Debug.Assert(balancedNode.IsBalanced());
count = balancedNode.Count;
slot = 0;
while (count >= FIBONACCI[slot + 1]) {
Node n = rebalanceArray[slot];
if (n != null) {
rebalanceArray[slot] = null;
if (accum == null)
accum = n;
else
accum = accum.PrependInPlace(n, !n.Shared);
}
++slot;
}
// slot is the location where balancedNode originally ended up, but possibly
// not the final resting place.
if (accum != null)
balancedNode = balancedNode.PrependInPlace(accum, !accum.Shared);
for (;;) {
Node n = rebalanceArray[slot];
if (n != null) {
rebalanceArray[slot] = null;
balancedNode = balancedNode.PrependInPlace(n, !n.Shared);
}
if (balancedNode.Count < FIBONACCI[slot + 1]) {
rebalanceArray[slot] = balancedNode;
break;
}
++slot;
}
#if DEBUG
// The above operations should ensure that everything in the rebalance array is now almost balanced.
for (int i = 0; i < rebalanceArray.Length; ++i) {
if (rebalanceArray[i] != null)
Debug.Assert(rebalanceArray[i].IsAlmostBalanced());
}
#endif //DEBUG
}
/// <summary>
/// Convert the list to a new list by applying a delegate to each item in the collection. The resulting list
/// contains the result of applying <paramref name="converter"/> to each item in the list, in
/// order. The current list is unchanged.
/// </summary>
/// <typeparam name="TDest">The type each item is being converted to.</typeparam>
/// <param name="converter">A delegate to the method to call, passing each item in <paramref name="sourceCollection"/>.</param>
/// <returns>The resulting BigList from applying <paramref name="converter"/> to each item in this list.</returns>
/// <exception cref="ArgumentNullException"><paramref name="converter"/> is null.</exception>
public new BigList<TDest> ConvertAll<TDest>(Converter<T, TDest> converter)
{
return new BigList<TDest>(Algorithms.Convert<T, TDest>(this, converter));
}
/// <summary>
/// Reverses the current list in place.
/// </summary>
public void Reverse()
{
Algorithms.ReverseInPlace<T>(this);
}
/// <summary>
/// Reverses the items in the range of <paramref name="count"/> items starting from <paramref name="startIndex"/>, in place.
/// </summary>
/// <param name="start">The starting index of the range to reverse.</param>
/// <param name="count">The number of items in range to reverse.</param>
public void Reverse(int start, int count)
{
Algorithms.ReverseInPlace<T>(Range(start, count));
}
/// <summary>
/// Sorts the list in place.
/// </summary>
/// <remarks><para>The Quicksort algorithm is used to sort the items. In virtually all cases,
/// this takes time O(N log N), where N is the number of items in the list.</para>
/// <para>Values are compared by using the IComparable or IComparable<T>
/// interface implementation on the type T.</para></remarks>
/// <exception cref="InvalidOperationException">The type T does not implement either the IComparable or
/// IComparable<T> interfaces.</exception>
public void Sort()
{
Sort(Comparers.DefaultComparer<T>());
}
/// <summary>
/// Sorts the list in place. A supplied IComparer<T> is used
/// to compare the items in the list.
/// </summary>
/// <remarks>The Quicksort algorithms is used to sort the items. In virtually all cases,
/// this takes time O(N log N), where N is the number of items in the list.</remarks>
/// <param name="comparer">The comparer instance used to compare items in the collection. Only
/// the Compare method is used.</param>
public void Sort(IComparer<T> comparer)
{
Algorithms.SortInPlace(this, comparer);
}
/// <summary>
/// Sorts the list in place. A supplied Comparison<T> delegate is used
/// to compare the items in the list.
/// </summary>
/// <remarks>The Quicksort algorithms is used to sort the items. In virtually all cases,
/// this takes time O(N log N), where N is the number of items in the list.</remarks>
/// <param name="comparison">The comparison delegate used to compare items in the collection.</param>
public void Sort(Comparison<T> comparison)
{
Sort(Comparers.ComparerFromComparison<T>(comparison));
}
/// <summary>
/// Searches a sorted list for an item via binary search. The list must be sorted
/// in the order defined by the default ordering of the item type; otherwise,
/// incorrect results will be returned.
/// </summary>
/// <param name="item">The item to search for.</param>
/// <returns>Returns the index of the first occurence of <paramref name="item"/> in the list. If the item does not occur
/// in the list, the bitwise complement of the first item larger than <paramref name="item"/> in the list is returned. If no item is
/// larger than <paramref name="item"/>, the bitwise complement of Count is returned.</returns>
/// <exception cref="InvalidOperationException">The type T does not implement either the IComparable or
/// IComparable<T> interfaces.</exception>
public int BinarySearch(T item)
{
return BinarySearch(item, Comparers.DefaultComparer<T>());
}
/// <summary>
/// Searches a sorted list for an item via binary search. The list must be sorted
/// by the ordering defined by the passed IComparer<T> interface; otherwise,
/// incorrect results will be returned.
/// </summary>
/// <param name="item">The item to search for.</param>
/// <param name="comparer">The IComparer<T> interface used to sort the list.</param>
/// <returns>Returns the index of the first occurence of <paramref name="item"/> in the list. If the item does not occur
/// in the list, the bitwise complement of the first item larger than <paramref name="item"/> in the list is returned. If no item is
/// larger than <paramref name="item"/>, the bitwise complement of Count is returned.</returns>
public int BinarySearch(T item, IComparer<T> comparer)
{
int count, index;
count = Algorithms.BinarySearch<T>(this, item, comparer, out index);
if (count == 0)
return (~index);
else
return index;
}
/// <summary>
/// Searches a sorted list for an item via binary search. The list must be sorted
/// by the ordering defined by the passed Comparison<T> delegate; otherwise,
/// incorrect results will be returned.
/// </summary>
/// <param name="item">The item to search for.</param>
/// <param name="comparison">The comparison delegate used to sort the list.</param>
/// <returns>Returns the index of the first occurence of <paramref name="item"/> in the list. If the item does not occur
/// in the list, the bitwise complement of the first item larger than <paramref name="item"/> in the list is returned. If no item is
/// larger than <paramref name="item"/>, the bitwise complement of Count is returned.</returns>
public int BinarySearch(T item, Comparison<T> comparison)
{
return BinarySearch(item, Comparers.ComparerFromComparison<T>(comparison));
}
#if DEBUG
/// <summary>
/// Attempts to validate the internal consistency of the tree.
/// </summary>
public void Validate()
{
if (root != null) {
root.Validate();
Debug.Assert(Count != 0);
}
else
Debug.Assert(Count == 0);
}
/// <summary>
/// Prints out the internal structure of the tree, for debugging purposes.
/// </summary>
public void Print()
{
Console.WriteLine("SERIES: Count={0}", Count);
if (Count > 0) {
Console.Write("ITEMS: ");
foreach (T item in this) {
Console.Write("{0} ", item);
}
Console.WriteLine();
Console.WriteLine("TREE:");
root.Print(" ", " ");
}
Console.WriteLine();
}
#endif //DEBUG
/// <summary>
/// The base class for the two kinds of nodes in the tree: Concat nodes
/// and Leaf nodes.
/// </summary>
[Serializable]
private abstract class Node
{
// Number of items in this node.
public int count;
// If true, indicates that this node is referenced by multiple
// concat nodes or multiple BigList. Neither this node nor
// nodes below it may be modifed ever again. Never becomes
// false after being set to true. It's volatile so that accesses
// from another thread work appropriately -- if shared is set
// to true, no other thread will attempt to change the node.
protected volatile bool shared;
/// <summary>
/// The number of items stored in the node (or below it).
/// </summary>
/// <value>The number of items in the node or below.</value>
public int Count
{
get { return count; }
}
/// <summary>
/// Is this node shared by more that one list (or within a single)
/// lists. If true, indicates that this node, and any nodes below it,
/// may never be modified. Never becomes false after being set to
/// true.
/// </summary>
/// <value></value>
public bool Shared
{
get { return shared; }
}
/// <summary>
/// Marks this node as shared by setting the shared variable.
/// </summary>
public void MarkShared()
{
shared = true;
}
/// <summary>
/// Gets the depth of this node. A leaf node has depth 0,
/// a concat node with two leaf children has depth 1, etc.
/// </summary>
/// <value>The depth of this node.</value>
public abstract int Depth { get;}
/// <summary>
/// Returns the items at the given index in this node.
/// </summary>
/// <param name="index">0-based index, relative to this node.</param>
/// <returns>Item at that index.</returns>
public abstract T GetAt(int index);
/// <summary>
/// Returns a node that has a sub-range of items from this node. The
/// sub-range may not be empty, but may extend outside the node.
/// In other words, first might be less than zero or last might be greater
/// than count. But, last can't be less than zero and first can't be
/// greater than count. Also, last must be greater than or equal to last.
/// </summary>
/// <param name="first">Inclusive first element, relative to this node.</param>
/// <param name="last">Inclusize last element, relative to this node.</param>
/// <returns>Node with the given sub-range.</returns>
public abstract Node Subrange(int first, int last);
// Any operation that could potentially modify a node exists
// in two forms -- the "in place" form that possibly modifies the
// node, and the non-"in place" that returns a new node with
// the modification. However, even "in-place" operations may return
// a new node, because a shared node can never be modified, even
// by an in-place operation.
/// <summary>
/// Changes the item at the given index. Never changes this node,
/// but always returns a new node with the given item changed.
/// </summary>
/// <param name="index">Index, relative to this node, to change.</param>
/// <param name="item">New item to place at the given index.</param>
/// <returns>A new node with the given item changed.</returns>
public abstract Node SetAt(int index, T item);
/// <summary>
/// Changes the item at the given index. May change this node,
/// or return a new node with the given item changed.
/// </summary>
/// <param name="index">Index, relative to this node, to change.</param>
/// <param name="item">New item to place at the given index.</param>
/// <returns>A node with the give item changed. If it can be done in place
/// then "this" is returned.</returns>
public abstract Node SetAtInPlace(int index, T item);
/// <summary>
/// Append a node after this node. Never changes this node, but returns
/// a new node with the given appending done.
/// </summary>
/// <param name="node">Node to append.</param>
/// <param name="nodeIsUnused">If true, the given node is not used
/// in any current list, so it may be change, overwritten, or destroyed
/// if convenient. If false, the given node is in use. It should be marked
/// as shared if is is used within the return value.</param>
/// <returns>A new node with the give node appended to this node.</returns>
public abstract Node Append(Node node, bool nodeIsUnused);
/// <summary>
/// Append a node after this node. May change this node, or return
/// a new node.
/// </summary>
/// <param name="node">Node to append.</param>
/// <param name="nodeIsUnused">If true, the given node is not used
/// in any current list, so it may be change, overwritten, or destroyed
/// if convenient. If false, the given node is in use. It should be marked
/// as shared if is is used within the return value.</param>
/// <returns>A node with the give node appended to this node. May be a new
/// node or the current node.</returns>
public abstract Node AppendInPlace(Node node, bool nodeIsUnused);
/// <summary>
/// Append a item after this node. May change this node, or return
/// a new node. Equivalent to AppendInPlace(new LeafNode(item), true), but
/// may be more efficient because a new LeafNode might not be allocated.
/// </summary>
/// <param name="item">Item to append.</param>
/// <returns>A node with the given item appended to this node. May be a new
/// node or the current node.</returns>
public abstract Node AppendInPlace(T item);
/// <summary>
/// Remove a range of items from this node. Never changes this node, but returns
/// a new node with the removing done. The
/// sub-range may not be empty, but may extend outside the node.
/// In other words, first might be less than zero or last might be greater
/// than count. But, last can't be less than zero and first can't be
/// greater than count. Also, last must be greater than or equal to last.
/// </summary>
/// <param name="first">Inclusive index of first item in sub-range, relative
/// to this node.</param>
/// <param name="last">Inclusize index of last item in sub-range, relative
/// to this node.</param>
/// <returns>A new node with the sub-range removed.</returns>
public abstract Node RemoveRange(int first, int last);
/// <summary>
/// Remove a range of items from this node. May change this node, or returns
/// a new node with the given appending done. The
/// sub-range may not be empty, but may extend outside the node.
/// In other words, first might be less than zero or last might be greater
/// than count. But, last can't be less than zero and first can't be
/// greater than count. Also, last must be greater than or equal to last.
/// </summary>
/// <param name="first">Inclusive index of first item in sub-range, relative
/// to this node.</param>
/// <param name="last">Inclusize index of last item in sub-range, relative
/// to this node.</param>
/// <returns>A node with the sub-range removed. If done in-place, returns
/// "this".</returns>
public abstract Node RemoveRangeInPlace(int first, int last);
/// <summary>
/// Inserts a node inside this node. Never changes this node, but returns
/// a new node with the given appending done.
/// </summary>
/// <param name="index">Index, relative to this node, to insert at. Must
/// be in bounds.</param>
/// <param name="node">Node to insert.</param>
/// <param name="nodeIsUnused">If true, the given node is not used
/// in any current list, so it may be change, overwritten, or destroyed
/// if convenient. If false, the given node is in use. It should be marked
/// as shared if is is used within the return value.</param>
/// <returns>A new node with the give node inserted.</returns>
public abstract Node Insert(int index, Node node, bool nodeIsUnused);
/// <summary>
/// Inserts an item inside this node. May change this node, or return
/// a new node with the given appending done. Equivalent to
/// InsertInPlace(new LeafNode(item), true), but may be more efficient.
/// </summary>
/// <param name="index">Index, relative to this node, to insert at. Must
/// be in bounds.</param>
/// <param name="item">Item to insert.</param>
/// <returns>A node with the give item inserted. If done in-place, returns
/// "this".</returns>
public abstract Node InsertInPlace(int index, T item);
/// <summary>
/// Inserts a node inside this node. May change this node, or return
/// a new node with the given appending done.
/// </summary>
/// <param name="index">Index, relative to this node, to insert at. Must
/// be in bounds.</param>
/// <param name="node">Node to insert.</param>
/// <param name="nodeIsUnused">If true, the given node is not used
/// in any current list, so it may be change, overwritten, or destroyed
/// if convenient. If false, the given node is in use. It should be marked
/// as shared if is is used within the return value.</param>
/// <returns>A node with the given item inserted. If done in-place, returns
/// "this".</returns>
public abstract Node InsertInPlace(int index, Node node, bool nodeIsUnused);
#if DEBUG
/// <summary>
/// Validates the node for consistency, as much as possible. Also validates
/// child nodes, if any.
/// </summary>
public abstract void Validate();
/// <summary>
/// Print out the contents of this node.
/// </summary>
/// <param name="prefixNode">Prefix to use in front of this node.</param>
/// <param name="prefixChildren">Prefixed to use in front of children of this node.</param>
public abstract void Print(string prefixNode, string prefixChildren);
#endif //DEBUG
/// <summary>
/// Prefpend a node before this node. Never changes this node, but returns
/// a new node with the given prepending done.
/// </summary>
/// <param name="node">Node to prepend.</param>
/// <param name="nodeIsUnused">If true, the given node is not used
/// in any current list, so it may be change, overwritten, or destroyed
/// if convenient. If false, the given node is in use. It should be marked
/// as shared if is is used within the return value.</param>
/// <returns>A new node with the give node prepended to this node.</returns>
public Node Prepend(Node node, bool nodeIsUnused)
{
if (nodeIsUnused)
return node.AppendInPlace(this, false);
else
return node.Append(this, false);
}
/// <summary>
/// Prepend a node before this node. May change this node, or return
/// a new node.
/// </summary>
/// <param name="node">Node to prepend.</param>
/// <param name="nodeIsUnused">If true, the given node is not used
/// in any current list, so it may be change, overwritten, or destroyed
/// if convenient. If false, the given node is in use. It should be marked
/// as shared if is is used within the return value.</param>
/// <returns>A node with the give node prepended to this node. May be a new
/// node or the current node.</returns>
public Node PrependInPlace(Node node, bool nodeIsUnused)
{
if (nodeIsUnused)
return node.AppendInPlace(this, !this.shared);
else
return node.Append(this, !this.shared);
}
/// <summary>
/// Prepend a item before this node. May change this node, or return
/// a new node. Equivalent to PrependInPlace(new LeafNode(item), true), but
/// may be more efficient because a new LeafNode might not be allocated.
/// </summary>
/// <param name="item">Item to prepend.</param>
/// <returns>A node with the given item prepended to this node. May be a new
/// node or the current node.</returns>
public abstract Node PrependInPlace(T item);
/// <summary>
/// Determine if this node is balanced. A node is balanced if the number
/// of items is greater than
/// Fibonacci(Depth+2). Balanced nodes are never rebalanced unless
/// they go out of balance again.
/// </summary>
/// <returns>True if the node is balanced by this definition.</returns>
public bool IsBalanced()
{
return (Depth <= MAXFIB && Count >= FIBONACCI[Depth]);
}
/// <summary>
/// Determine if this node is almost balanced. A node is almost balanced if t
/// its depth is at most one greater than a fully balanced node with the same count.
/// </summary>
/// <returns>True if the node is almost balanced by this definition.</returns>
public bool IsAlmostBalanced()
{
return (Depth == 0 || (Depth - 1 <= MAXFIB && Count >= FIBONACCI[Depth - 1]));
}
}
/// <summary>
/// The LeafNode class is the type of node that lives at the leaf of a tree and holds
/// the actual items stored in the list. Each leaf holds at least 1, and at most MAXLEAF
/// items in the items array. The number of items stored is found in "count", which may
/// be less than "items.Length".
/// </summary>
[Serializable]
private sealed class LeafNode : Node
{
/// <summary>
/// Array that stores the items in the nodes. Always has a least "count" elements,
/// but may have more as padding.
/// </summary>
public T[] items;
/// <summary>
/// Creates a LeafNode that holds a single item.
/// </summary>
/// <param name="item">Item to place into the leaf node.</param>
public LeafNode(T item)
{
// CONSIDER: is MAXLEAF always the right thing to do? It seems to work well in most cases.
count = 1;
items = new T[MAXLEAF];
items[0] = item;
}
/// <summary>
/// Creates a new leaf node with the indicates count of item and the
/// </summary>
/// <param name="count">Number of items. Can't be zero.</param>
/// <param name="newItems">The array of items. The LeafNode takes
/// possession of this array.</param>
public LeafNode(int count, T[] newItems)
{
Debug.Assert(count <= newItems.Length && count > 0);
Debug.Assert(newItems.Length <= MAXLEAF);
this.count = count;
items = newItems;
}
public override int Depth
{
get { return 0; }
}
/// <summary>
/// Returns the items at the given index in this node.
/// </summary>
/// <param name="index">0-based index, relative to this node.</param>
/// <returns>Item at that index.</returns>
public override T GetAt(int index)
{
return items[index];
}
/// <summary>
/// Changes the item at the given index. May change this node,
/// or return a new node with the given item changed.
/// </summary>
/// <param name="index">Index, relative to this node, to change.</param>
/// <param name="item">New item to place at the given index.</param>
/// <returns>A node with the give item changed. If it can be done in place
/// then "this" is returned.</returns>
public override Node SetAtInPlace(int index, T item)
{
if (shared)
return SetAt(index, item); // Can't update a shared node in place.
items[index] = item;
return this;
}
/// <summary>
/// Changes the item at the given index. Never changes this node,
/// but always returns a new node with the given item changed.
/// </summary>
/// <param name="index">Index, relative to this node, to change.</param>
/// <param name="item">New item to place at the given index.</param>
/// <returns>A new node with the given item changed.</returns>
public override Node SetAt(int index, T item)
{
T[] newItems = (T[])items.Clone();
newItems[index] = item;
return new LeafNode(count, newItems);
}
/// <summary>
/// If other is a leaf node, and the resulting size would be less than MAXLEAF, merge
/// the other leaf node into this one (after this one) and return true.
/// </summary>
/// <param name="other">Other node to possible merge.</param>
/// <returns>If <paramref name="other"/> could be merged into this node, returns
/// true. Otherwise returns false and the current node is unchanged.</returns>
private bool MergeLeafInPlace(Node other)
{
Debug.Assert(!shared);
LeafNode otherLeaf = (other as LeafNode);
int newCount;
if (otherLeaf != null && (newCount = otherLeaf.Count + this.count) <= MAXLEAF) {
// Combine the two leaf nodes into one.
if (newCount > items.Length) {
T[] newItems = new T[MAXLEAF];
Array.Copy(items, 0, newItems, 0, count);
items = newItems;
}
Array.Copy(otherLeaf.items, 0, items, count, otherLeaf.count);
count = newCount;
return true;
}
return false;
}
/// <summary>
/// If other is a leaf node, and the resulting size would be less than MAXLEAF, merge
/// the other leaf node with this one (after this one) and return a new node with
/// the merged items. Does not modify this.
/// If no merging, return null.
/// </summary>
/// <param name="other">Other node to possible merge.</param>
/// <returns>If the nodes could be merged, returns the new node. Otherwise
/// returns null.</returns>
private Node MergeLeaf(Node other)
{
LeafNode otherLeaf = (other as LeafNode);
int newCount;
if (otherLeaf != null && (newCount = otherLeaf.Count + this.count) <= MAXLEAF) {
// Combine the two leaf nodes into one.
T[] newItems = new T[MAXLEAF];
Array.Copy(items, 0, newItems, 0, count);
Array.Copy(otherLeaf.items, 0, newItems, count, otherLeaf.count);
return new LeafNode(newCount, newItems);
}
return null;
}
/// <summary>
/// Prepend a item before this node. May change this node, or return
/// a new node. Equivalent to PrependInPlace(new LeafNode(item), true), but
/// may be more efficient because a new LeafNode might not be allocated.
/// </summary>
/// <param name="item">Item to prepend.</param>
/// <returns>A node with the given item prepended to this node. May be a new
/// node or the current node.</returns>
public override Node PrependInPlace(T item)
{
if (shared)
return Prepend(new LeafNode(item), true); // Can't update a shared node in place.
// Add into the current leaf, if possible.
if (count < MAXLEAF) {
if (count == items.Length) {
T[] newItems = new T[MAXLEAF];
Array.Copy(items, 0, newItems, 1, count);
items = newItems;
}
else {
Array.Copy(items, 0, items, 1, count);
}
items[0] = item;
count += 1;
return this;
}
else {
return new ConcatNode(new LeafNode(item), this);
}
}
/// <summary>
/// Append a item after this node. May change this node, or return
/// a new node. Equivalent to AppendInPlace(new LeafNode(item), true), but
/// may be more efficient because a new LeafNode might not be allocated.
/// </summary>
/// <param name="item">Item to append.</param>
/// <returns>A node with the given item appended to this node. May be a new
/// node or the current node.</returns>
public override Node AppendInPlace(T item)
{
if (shared)
return Append(new LeafNode(item), true); // Can't update a shared node in place.
// Add into the current leaf, if possible.
if (count < MAXLEAF) {
if (count == items.Length) {
T[] newItems = new T[MAXLEAF];
Array.Copy(items, 0, newItems, 0, count);
items = newItems;
}
items[count] = item;
count += 1;
return this;
}
else {
return new ConcatNode(this, new LeafNode(item));
}
}
/// <summary>
/// Append a node after this node. May change this node, or return
/// a new node.
/// </summary>
/// <param name="node">Node to append.</param>
/// <param name="nodeIsUnused">If true, the given node is not used
/// in any current list, so it may be change, overwritten, or destroyed
/// if convenient. If false, the given node is in use. It should be marked
/// as shared if is is used within the return value.</param>
/// <returns>A node with the give node appended to this node. May be a new
/// node or the current node.</returns>
public override Node AppendInPlace(Node node, bool nodeIsUnused)
{
if (shared)
return Append(node, nodeIsUnused); // Can't update a shared node in place.
// If we're appending a leaf, try to merge them if possible.
if (MergeLeafInPlace(node)) {
return this;
}
// If we're appending a tree with a left leaf node, try to merge them if possible.
ConcatNode otherConcat = (node as ConcatNode);
if (otherConcat != null && MergeLeafInPlace(otherConcat.left)) {
if (! nodeIsUnused)
otherConcat.right.MarkShared();
return new ConcatNode(this, otherConcat.right);
}
// Otherwise, create a Concat node.
if (! nodeIsUnused)
node.MarkShared();
return new ConcatNode(this, node);
}
public override Node Append(Node node, bool nodeIsUnused)
{
Node result;
// If we're appending a leaf, try to merge them if possible.
if ((result = MergeLeaf(node)) != null)
return result;
// If we're appending a concat with a left leaf, try to merge them if possible.
ConcatNode otherConcat = (node as ConcatNode);
if (otherConcat != null && (result = MergeLeaf(otherConcat.left)) != null) {
if (! nodeIsUnused)
otherConcat.right.MarkShared();
return new ConcatNode(result, otherConcat.right);
}
// Otherwise, create a Concat node.
if (!nodeIsUnused)
node.MarkShared();
MarkShared();
return new ConcatNode(this, node);
}
/// <summary>
/// Inserts an item inside this node. May change this node, or return
/// a new node with the given appending done. Equivalent to
/// InsertInPlace(new LeafNode(item), true), but may be more efficient.
/// </summary>
/// <param name="index">Index, relative to this node, to insert at. Must
/// be in bounds.</param>
/// <param name="item">Item to insert.</param>
/// <returns>A node with the give item inserted. If done in-place, returns
/// "this".</returns>
public override Node InsertInPlace(int index, T item)
{
if (shared)
return Insert(index, new LeafNode(item), true); // Can't update a shared node in place.
// Insert into the current leaf, if possible.
if (count < MAXLEAF) {
if (count == items.Length) {
T[] newItems = new T[MAXLEAF];
if (index > 0)
Array.Copy(items, 0, newItems, 0, index);
if (count > index)
Array.Copy(items, index, newItems, index + 1, count - index);
items = newItems;
}
else {
if (count > index)
Array.Copy(items, index, items, index + 1, count - index);
}
items[index] = item;
count += 1;
return this;
}
else {
if (index == count) {
// Inserting at count is just an appending operation.
return new ConcatNode(this, new LeafNode(item));
}
else if (index == 0) {
// Inserting at 0 is just a prepending operation.
return new ConcatNode(new LeafNode(item), this);
}
else {
// Split into two nodes, and put the new item at the end of the first.
T[] leftItems = new T[MAXLEAF];
Array.Copy(items, 0, leftItems, 0, index);
leftItems[index] = item;
Node leftNode = new LeafNode(index + 1, leftItems);
T[] rightItems = new T[count - index];
Array.Copy(items, index, rightItems, 0, count - index);
Node rightNode = new LeafNode(count - index, rightItems);
return new ConcatNode(leftNode, rightNode);
}
}
}
/// <summary>
/// Inserts a node inside this node. May change this node, or return
/// a new node with the given appending done.
/// </summary>
/// <param name="index">Index, relative to this node, to insert at. Must
/// be in bounds.</param>
/// <param name="node">Node to insert.</param>
/// <param name="nodeIsUnused">If true, the given node is not used
/// in any current list, so it may be change, overwritten, or destroyed
/// if convenient. If false, the given node is in use. It should be marked
/// as shared if is is used within the return value.</param>
/// <returns>A node with the given item inserted. If done in-place, returns
/// "this".</returns>
public override Node InsertInPlace(int index, Node node, bool nodeIsUnused)
{
if (shared)
return Insert(index, node, nodeIsUnused); // Can't update a shared node in place.
LeafNode otherLeaf = (node as LeafNode);
int newCount;
if (otherLeaf != null && (newCount = otherLeaf.Count + this.count) <= MAXLEAF) {
// Combine the two leaf nodes into one.
if (newCount > items.Length) {
T[] newItems = new T[MAXLEAF];
Array.Copy(items, 0, newItems, 0, index);
Array.Copy(otherLeaf.items, 0, newItems, index, otherLeaf.Count);
Array.Copy(items, index, newItems, index + otherLeaf.Count, count - index);
items = newItems;
}
else {
Array.Copy(items, index, items, index + otherLeaf.Count, count - index);
Array.Copy(otherLeaf.items, 0, items, index, otherLeaf.count);
}
count = newCount;
return this;
}
else if (index == 0) {
// Inserting at 0 is a prepend.
return PrependInPlace(node, nodeIsUnused);
}
else if (index == count) {
// Inserting at count is an append.
return AppendInPlace(node, nodeIsUnused);
}
else {
// Split existing node into two nodes at the insertion point, then concat all three nodes together.
T[] leftItems = new T[index];
Array.Copy(items, 0, leftItems, 0, index);
Node leftNode = new LeafNode(index, leftItems);
T[] rightItems = new T[count - index];
Array.Copy(items, index, rightItems, 0, count - index);
Node rightNode = new LeafNode(count - index, rightItems);
leftNode = leftNode.AppendInPlace(node, nodeIsUnused);
leftNode = leftNode.AppendInPlace(rightNode, true);
return leftNode;
}
}
/// <summary>
/// Inserts a node inside this node. Never changes this node, but returns
/// a new node with the given appending done.
/// </summary>
/// <param name="index">Index, relative to this node, to insert at. Must
/// be in bounds.</param>
/// <param name="node">Node to insert.</param>
/// <param name="nodeIsUnused">If true, the given node is not used
/// in any current list, so it may be change, overwritten, or destroyed
/// if convenient. If false, the given node is in use. It should be marked
/// as shared if is is used within the return value.</param>
/// <returns>A new node with the give node inserted.</returns>
public override Node Insert(int index, Node node, bool nodeIsUnused)
{
LeafNode otherLeaf = (node as LeafNode);
int newCount;
if (otherLeaf != null && (newCount = otherLeaf.Count + this.count) <= MAXLEAF) {
// Combine the two leaf nodes into one.
T[] newItems = new T[MAXLEAF];
Array.Copy(items, 0, newItems, 0, index);
Array.Copy(otherLeaf.items, 0, newItems, index, otherLeaf.Count);
Array.Copy(items, index, newItems, index + otherLeaf.Count, count - index);
return new LeafNode(newCount, newItems);
}
else if (index == 0) {
// Inserting at 0 is a prepend.
return Prepend(node, nodeIsUnused);
}
else if (index == count) {
// Inserting at count is an append.
return Append(node, nodeIsUnused);
}
else {
// Split existing node into two nodes at the insertion point, then concat all three nodes together.
T[] leftItems = new T[index];
Array.Copy(items, 0, leftItems, 0, index);
Node leftNode = new LeafNode(index, leftItems);
T[] rightItems = new T[count - index];
Array.Copy(items, index, rightItems, 0, count - index);
Node rightNode = new LeafNode(count - index, rightItems);
leftNode = leftNode.AppendInPlace(node, nodeIsUnused);
leftNode = leftNode.AppendInPlace(rightNode, true);
return leftNode;
}
}
/// <summary>
/// Remove a range of items from this node. May change this node, or returns
/// a new node with the given appending done. The
/// sub-range may not be empty, but may extend outside the node.
/// In other words, first might be less than zero or last might be greater
/// than count. But, last can't be less than zero and first can't be
/// greater than count. Also, last must be greater than or equal to last.
/// </summary>
/// <param name="first">Inclusive index of first item in sub-range, relative
/// to this node.</param>
/// <param name="last">Inclusize index of last item in sub-range, relative
/// to this node.</param>
/// <returns>A node with the sub-range removed. If done in-place, returns
/// "this".</returns>
public override Node RemoveRangeInPlace(int first, int last)
{
if (shared)
return RemoveRange(first, last);
Debug.Assert(first <= last);
Debug.Assert(last >= 0);
if (first <= 0 && last >= count - 1) {
return null; // removing entire node.
}
if (first < 0)
first = 0;
if (last >= count)
last = count - 1;
int newCount = first + (count - last - 1); // number of items remaining.
if (count > last + 1)
Array.Copy(items, last + 1, items, first, count - last - 1);
for (int i = newCount; i < count; ++i)
items[i] = default(T);
count = newCount;
return this;
}
/// <summary>
/// Remove a range of items from this node. Never changes this node, but returns
/// a new node with the removing done. The
/// sub-range may not be empty, but may extend outside the node.
/// In other words, first might be less than zero or last might be greater
/// than count. But, last can't be less than zero and first can't be
/// greater than count. Also, last must be greater than or equal to last.
/// </summary>
/// <param name="first">Inclusive index of first item in sub-range, relative
/// to this node.</param>
/// <param name="last">Inclusize index of last item in sub-range, relative
/// to this node.</param>
/// <returns>A new node with the sub-range removed.</returns>
public override Node RemoveRange(int first, int last)
{
Debug.Assert(first <= last);
Debug.Assert(last >= 0);
if (first <= 0 && last >= count - 1) {
return null; // removing entire node.
}
if (first < 0)
first = 0;
if (last >= count)
last = count - 1;
int newCount = first + (count - last - 1); // number of items remaining.
T[] newItems = new T[newCount];
if (first > 0)
Array.Copy(items, 0, newItems, 0, first);
if (count > last + 1)
Array.Copy(items, last + 1, newItems, first, count - last - 1);
return new LeafNode(newCount, newItems);
}
/// <summary>
/// Returns a node that has a sub-range of items from this node. The
/// sub-range may not be empty, but may extend outside the node.
/// In other words, first might be less than zero or last might be greater
/// than count. But, last can't be less than zero and first can't be
/// greater than count. Also, last must be greater than or equal to last.
/// </summary>
/// <param name="first">Inclusive first element, relative to this node.</param>
/// <param name="last">Inclusize last element, relative to this node.</param>
/// <returns>Node with the given sub-range.</returns>
public override Node Subrange(int first, int last)
{
Debug.Assert(first <= last);
Debug.Assert(last >= 0);
if (first <= 0 && last >= count - 1) {
MarkShared();
return this;
}
else {
if (first < 0)
first = 0;
if (last >= count)
last = count - 1;
int n = last - first + 1;
T[] newItems = new T[n];
Array.Copy(items, first, newItems, 0, n);
return new LeafNode(n, newItems);
}
}
#if DEBUG
/// <summary>
/// Validates the node for consistency, as much as possible. Also validates
/// child nodes, if any.
/// </summary>
public override void Validate()
{
// Check count and length of buffer.
Debug.Assert(count > 0);
Debug.Assert(items != null);
Debug.Assert(items.Length > 0);
Debug.Assert(count <= MAXLEAF);
Debug.Assert(items.Length <= MAXLEAF);
Debug.Assert(count <= items.Length);
}
/// <summary>
/// Print out the contents of this node.
/// </summary>
/// <param name="prefixNode">Prefix to use in front of this node.</param>
/// <param name="prefixChildren">Prefixed to use in front of children of this node.</param>
public override void Print(string prefixNode, string prefixChildren)
{
Console.Write("{0}LEAF {1} count={2}/{3} ", prefixNode, shared ? "S" : " ", count, items.Length);
for (int i = 0; i < count; ++i)
Console.Write("{0} ", items[i]);
Console.WriteLine();
}
#endif //DEBUG
}
/// <summary>
/// A ConcatNode is an interior (non-leaf) node that represents the concatination of
/// the left and right child nodes. Both children must always be non-null.
/// </summary>
[Serializable]
private sealed class ConcatNode : Node
{
/// <summary>
/// The left and right child nodes. They are never null.
/// </summary>
public Node left, right;
/// <summary>
/// The depth of this node -- the maximum length path to
/// a leaf. If this node has two children that are leaves, the
/// depth in 1.
/// </summary>
private short depth;
/// <summary>
/// The depth of this node -- the maximum length path to
/// a leaf. If this node has two children that are leaves, the
/// depth in 1.
/// </summary>
/// <value>The depth of this node.</value>
public override int Depth
{
get { return depth; }
}
/// <summary>
/// Create a new ConcatNode with the given children.
/// </summary>
/// <param name="left">The left child. May not be null.</param>
/// <param name="right">The right child. May not be null.</param>
public ConcatNode(Node left, Node right)
{
Debug.Assert(left != null && right != null);
this.left = left;
this.right = right;
this.count = left.Count + right.Count;
if (left.Depth > right.Depth)
this.depth = (short)(left.Depth + 1);
else
this.depth = (short)(right.Depth + 1);
}
/// <summary>
/// Create a new node with the given children. Mark unchanged
/// children as shared. There are four
/// possible cases:
/// 1. If one of the new children is null, the other new child is returned.
/// 2. If neither child has changed, then this is marked as shared as returned.
/// 3. If one child has changed, the other child is marked shared an a new node is returned.
/// 4. If both children have changed, a new node is returned.
/// </summary>
/// <param name="newLeft">New left child.</param>
/// <param name="newRight">New right child.</param>
/// <returns>New node with the given children. Returns null if and only if both
/// new children are null.</returns>
private Node NewNode(Node newLeft, Node newRight)
{
if (left == newLeft) {
if (right == newRight) {
MarkShared();
return this; // Nothing changed. In this case we can return the same node.
}
else
left.MarkShared();
}
else {
if (right == newRight)
right.MarkShared();
}
if (newLeft == null)
return newRight;
else if (newRight == null)
return newLeft;
else
return new ConcatNode(newLeft, newRight);
}
/// <summary>
/// Updates a node with the given new children. If one of the new children is
/// null, the other is returned. If both are null, null is returned.
/// </summary>
/// <param name="newLeft">New left child.</param>
/// <param name="newRight">New right child.</param>
/// <returns>Node with the given children. Usually, but not always, this. Returns
/// null if and only if both new children are null.</returns>
private Node NewNodeInPlace(Node newLeft, Node newRight)
{
Debug.Assert(!shared);
if (newLeft == null)
return newRight;
else if (newRight == null)
return newLeft;
left = newLeft;
right = newRight;
count = left.Count + right.Count;
if (left.Depth > right.Depth)
depth = (short)(left.Depth + 1);
else
depth = (short)(right.Depth + 1);
return this;
}
/// <summary>
/// Returns the items at the given index in this node.
/// </summary>
/// <param name="index">0-based index, relative to this node.</param>
/// <returns>Item at that index.</returns>
public override T GetAt(int index)
{
int leftCount = left.Count;
if (index < leftCount)
return left.GetAt(index);
else
return right.GetAt(index - leftCount);
}
/// <summary>
/// Changes the item at the given index. May change this node,
/// or return a new node with the given item changed.
/// </summary>
/// <param name="index">Index, relative to this node, to change.</param>
/// <param name="item">New item to place at the given index.</param>
/// <returns>A node with the give item changed. If it can be done in place
/// then "this" is returned.</returns>
public override Node SetAtInPlace(int index, T item)
{
if (shared)
return SetAt(index, item); // Can't update a shared node in place.
int leftCount = left.Count;
if (index < leftCount) {
Node newLeft = left.SetAtInPlace(index, item);
if (newLeft != left)
return NewNodeInPlace(newLeft, right);
else
return this;
}
else {
Node newRight = right.SetAtInPlace(index - leftCount, item);
if (newRight != right)
return NewNodeInPlace(left, newRight);
else
return this;
}
}
/// <summary>
/// Changes the item at the given index. Never changes this node,
/// but always returns a new node with the given item changed.
/// </summary>
/// <param name="index">Index, relative to this node, to change.</param>
/// <param name="item">New item to place at the given index.</param>
/// <returns>A new node with the given item changed.</returns>
public override Node SetAt(int index, T item)
{
int leftCount = left.Count;
if (index < leftCount) {
return NewNode(left.SetAt(index, item), right);
}
else {
return NewNode(left, right.SetAt(index - leftCount, item));
}
}
/// <summary>
/// Prepend a item before this node. May change this node, or return
/// a new node. Equivalent to PrependInPlace(new LeafNode(item), true), but
/// may be more efficient because a new LeafNode might not be allocated.
/// </summary>
/// <param name="item">Item to prepend.</param>
/// <returns>A node with the given item prepended to this node. May be a new
/// node or the current node.</returns>
public override Node PrependInPlace(T item)
{
if (shared)
return Prepend(new LeafNode(item), true); // Can't update a shared node in place.
LeafNode leftLeaf;
if (left.Count < MAXLEAF && !left.Shared && (leftLeaf = left as LeafNode) != null) {
// Prepend the item to the left leaf. This keeps repeated prepends from creating
// single item nodes.
int c = leftLeaf.Count;
if (c == leftLeaf.items.Length) {
T[] newItems = new T[MAXLEAF];
Array.Copy(leftLeaf.items, 0, newItems, 1, c);
leftLeaf.items = newItems;
}
else {
Array.Copy(leftLeaf.items, 0, leftLeaf.items, 1, c);
}
leftLeaf.items[0] = item;
leftLeaf.count += 1;
this.count += 1;
return this;
}
else
return new ConcatNode(new LeafNode(item), this);
}
/// <summary>
/// Append a item after this node. May change this node, or return
/// a new node. Equivalent to AppendInPlace(new LeafNode(item), true), but
/// may be more efficient because a new LeafNode might not be allocated.
/// </summary>
/// <param name="item">Item to append.</param>
/// <returns>A node with the given item appended to this node. May be a new
/// node or the current node.</returns>
public override Node AppendInPlace(T item)
{
if (shared)
return Append(new LeafNode(item), true); // Can't update a shared node in place.
LeafNode rightLeaf;
if (right.Count < MAXLEAF && !right.Shared && (rightLeaf = right as LeafNode) != null) {
int c = rightLeaf.Count;
if (c == rightLeaf.items.Length) {
T[] newItems = new T[MAXLEAF]; // use MAXLEAF when appending, because we'll probably append again.
Array.Copy(rightLeaf.items, 0, newItems, 0, c);
rightLeaf.items = newItems;
}
rightLeaf.items[c] = item;
rightLeaf.count += 1;
this.count += 1;
return this;
}
else
return new ConcatNode(this, new LeafNode(item));
}
/// <summary>
/// Append a node after this node. May change this node, or return
/// a new node.
/// </summary>
/// <param name="node">Node to append.</param>
/// <param name="nodeIsUnused">If true, the given node is not used
/// in any current list, so it may be change, overwritten, or destroyed
/// if convenient. If false, the given node is in use. It should be marked
/// as shared if is is used within the return value.</param>
/// <returns>A node with the give node appended to this node. May be a new
/// node or the current node.</returns>
public override Node AppendInPlace(Node node, bool nodeIsUnused)
{
if (shared)
return Append(node, nodeIsUnused); // Can't update a shared node in place.
if (right.Count + node.Count <= MAXLEAF && right is LeafNode && node is LeafNode)
return NewNodeInPlace(left, right.AppendInPlace(node, nodeIsUnused));
if (!nodeIsUnused)
node.MarkShared();
return new ConcatNode(this, node);
}
public override Node Append(Node node, bool nodeIsUnused)
{
// If possible combine with a child leaf node on the right.
if (right.Count + node.Count <= MAXLEAF && right is LeafNode && node is LeafNode)
return NewNode(left, right.Append(node, nodeIsUnused));
// Concatinate with this node.
this.MarkShared();
if (!nodeIsUnused)
node.MarkShared();
return new ConcatNode(this, node);
}
/// <summary>
/// Inserts an item inside this node. May change this node, or return
/// a new node with the given appending done. Equivalent to
/// InsertInPlace(new LeafNode(item), true), but may be more efficient.
/// </summary>
/// <param name="index">Index, relative to this node, to insert at. Must
/// be in bounds.</param>
/// <param name="item">Item to insert.</param>
/// <returns>A node with the give item inserted. If done in-place, returns
/// "this".</returns>
public override Node InsertInPlace(int index, T item)
{
if (shared)
return Insert(index, new LeafNode(item), true);
int leftCount = left.Count;
if (index <= leftCount)
return NewNodeInPlace(left.InsertInPlace(index, item), right);
else
return NewNodeInPlace(left, right.InsertInPlace(index - leftCount, item));
}
/// <summary>
/// Inserts a node inside this node. May change this node, or return
/// a new node with the given appending done.
/// </summary>
/// <param name="index">Index, relative to this node, to insert at. Must
/// be in bounds.</param>
/// <param name="node">Node to insert.</param>
/// <param name="nodeIsUnused">If true, the given node is not used
/// in any current list, so it may be change, overwritten, or destroyed
/// if convenient. If false, the given node is in use. It should be marked
/// as shared if is is used within the return value.</param>
/// <returns>A node with the given item inserted. If done in-place, returns
/// "this".</returns>
public override Node InsertInPlace(int index, Node node, bool nodeIsUnused)
{
if (shared)
return Insert(index, node, nodeIsUnused);
int leftCount = left.Count;
if (index < leftCount)
return NewNodeInPlace(left.InsertInPlace(index, node, nodeIsUnused), right);
else
return NewNodeInPlace(left, right.InsertInPlace(index - leftCount, node, nodeIsUnused));
}
/// <summary>
/// Inserts a node inside this node. Never changes this node, but returns
/// a new node with the given appending done.
/// </summary>
/// <param name="index">Index, relative to this node, to insert at. Must
/// be in bounds.</param>
/// <param name="node">Node to insert.</param>
/// <param name="nodeIsUnused">If true, the given node is not used
/// in any current list, so it may be change, overwritten, or destroyed
/// if convenient. If false, the given node is in use. It should be marked
/// as shared if is is used within the return value.</param>
/// <returns>A new node with the give node inserted.</returns>
public override Node Insert(int index, Node node, bool nodeIsUnused)
{
int leftCount = left.Count;
if (index < leftCount)
return NewNode(left.Insert(index, node, nodeIsUnused), right);
else
return NewNode(left, right.Insert(index - leftCount, node, nodeIsUnused));
}
/// <summary>
/// Remove a range of items from this node. May change this node, or returns
/// a new node with the given appending done. The
/// sub-range may not be empty, but may extend outside the node.
/// In other words, first might be less than zero or last might be greater
/// than count. But, last can't be less than zero and first can't be
/// greater than count. Also, last must be greater than or equal to last.
/// </summary>
/// <param name="first">Inclusive index of first item in sub-range, relative
/// to this node.</param>
/// <param name="last">Inclusize index of last item in sub-range, relative
/// to this node.</param>
/// <returns>A node with the sub-range removed. If done in-place, returns
/// "this".</returns>
public override Node RemoveRangeInPlace(int first, int last)
{
if (shared)
return RemoveRange(first, last);
Debug.Assert(first < count);
Debug.Assert(last >= 0);
if (first <= 0 && last >= count - 1) {
return null;
}
int leftCount = left.Count;
Node newLeft = left, newRight = right;
// Is part of the left being removed?
if (first < leftCount)
newLeft = left.RemoveRangeInPlace(first, last);
// Is part of the right being remove?
if (last >= leftCount)
newRight = right.RemoveRangeInPlace(first - leftCount, last - leftCount);
return NewNodeInPlace(newLeft, newRight);
}
/// <summary>
/// Remove a range of items from this node. Never changes this node, but returns
/// a new node with the removing done. The
/// sub-range may not be empty, but may extend outside the node.
/// In other words, first might be less than zero or last might be greater
/// than count. But, last can't be less than zero and first can't be
/// greater than count. Also, last must be greater than or equal to last.
/// </summary>
/// <param name="first">Inclusive index of first item in sub-range, relative
/// to this node.</param>
/// <param name="last">Inclusize index of last item in sub-range, relative
/// to this node.</param>
/// <returns>A new node with the sub-range removed.</returns>
public override Node RemoveRange(int first, int last)
{
Debug.Assert(first < count);
Debug.Assert(last >= 0);
if (first <= 0 && last >= count - 1) {
return null;
}
int leftCount = left.Count;
Node newLeft = left, newRight = right;
// Is part of the left being removed?
if (first < leftCount)
newLeft = left.RemoveRange(first, last);
// Is part of the right being remove?
if (last >= leftCount)
newRight = right.RemoveRange(first - leftCount, last - leftCount);
return NewNode(newLeft, newRight);
}
/// <summary>
/// Returns a node that has a sub-range of items from this node. The
/// sub-range may not be empty, but may extend outside the node.
/// In other words, first might be less than zero or last might be greater
/// than count. But, last can't be less than zero and first can't be
/// greater than count. Also, last must be greater than or equal to last.
/// </summary>
/// <param name="first">Inclusive first element, relative to this node.</param>
/// <param name="last">Inclusize last element, relative to this node.</param>
/// <returns>Node with the given sub-range.</returns>
public override Node Subrange(int first, int last)
{
Debug.Assert(first < count);
Debug.Assert(last >= 0);
if (first <= 0 && last >= count - 1) {
// range encapsulate the whole node, so just return it.
MarkShared();
return this;
}
int leftCount = left.Count;
Node leftPart = null, rightPart = null;
// Is part of the left included?
if (first < leftCount)
leftPart = left.Subrange(first, last);
// Is part of the right included?
if (last >= leftCount)
rightPart = right.Subrange(first - leftCount, last - leftCount);
Debug.Assert(leftPart != null || rightPart != null);
// Combine the left parts and the right parts.
if (leftPart == null)
return rightPart;
else if (rightPart == null)
return leftPart;
else
return new ConcatNode(leftPart, rightPart);
}
#if DEBUG
/// <summary>
/// Validates the node for consistency, as much as possible. Also validates
/// child nodes, if any.
/// </summary>
public override void Validate()
{
Debug.Assert(left != null);
Debug.Assert(right != null);
Debug.Assert(Depth > 0);
Debug.Assert(Count > 0);
Debug.Assert(Math.Max(left.Depth, right.Depth) + 1 == Depth);
Debug.Assert(left.Count + right.Count == Count);
left.Validate();
right.Validate();
}
/// <summary>
/// Print out the contents of this node.
/// </summary>
/// <param name="prefixNode">Prefix to use in front of this node.</param>
/// <param name="prefixChildren">Prefixed to use in front of children of this node.</param>
public override void Print(string prefixNode, string prefixChildren)
{
Console.WriteLine("{0}CONCAT {1} {2} count={3} depth={4}", prefixNode, shared ? "S" : " ", IsBalanced() ? "B" : (IsAlmostBalanced() ? "A" : " "), count, depth);
left.Print(prefixChildren + "|-L-", prefixChildren + "| ");
right.Print(prefixChildren + "|-R-", prefixChildren + " ");
}
#endif //DEBUG
}
/// <summary>
/// The class that is used to implement IList<T> to view a sub-range
/// of a BigList. The object stores a wrapped list, and a start/count indicating
/// a sub-range of the list. Insertion/deletions through the sub-range view
/// cause the count to change also; insertions and deletions directly on
/// the wrapped list do not.
/// </summary>
/// <remarks>This is different from Algorithms.Range in a very few respects:
/// it is specialized to only wrap BigList, and it is a lot more efficient in enumeration.</remarks>
[Serializable]
private class BigListRange : ListBase<T>
{
private BigList<T> wrappedList;
private int start;
private int count;
/// <summary>
/// Create a sub-range view object on the indicate part
/// of the list.
/// </summary>
/// <param name="wrappedList">List to wrap.</param>
/// <param name="start">The start index of the view in the wrapped list.</param>
/// <param name="count">The number of items in the view.</param>
public BigListRange(BigList<T> wrappedList, int start, int count)
{
this.wrappedList = wrappedList;
this.start = start;
this.count = count;
}
public override int Count
{
get
{
return Math.Min(count, wrappedList.Count - start);
}
}
public override void Clear()
{
if (wrappedList.Count - start < count)
count = wrappedList.Count - start;
while (count > 0) {
wrappedList.RemoveAt(start + count - 1);
--count;
}
}
public override void Insert(int index, T item)
{
if (index < 0 || index > count)
throw new ArgumentOutOfRangeException("index");
wrappedList.Insert(start + index, item);
++count;
}
public override void RemoveAt(int index)
{
if (index < 0 || index >= count)
throw new ArgumentOutOfRangeException("index");
wrappedList.RemoveAt(start + index);
--count;
}
public override T this[int index]
{
get
{
if (index < 0 || index >= count)
throw new ArgumentOutOfRangeException("index");
return wrappedList[start + index];
}
set
{
if (index < 0 || index >= count)
throw new ArgumentOutOfRangeException("index");
wrappedList[start + index] = value;
}
}
public override IEnumerator<T> GetEnumerator()
{
return wrappedList.GetEnumerator(start, count);
}
}
}
}
Submit an article or tip