Click here to Skip to main content
12,246,406 members (39,126 online)
Click here to Skip to main content

Stats

117.4K views
5.6K downloads
56 bookmarked
Posted

Auto-filter for Microsoft WPF DataGrid

, 29 Jan 2009 Eclipse
Allows auto filtering functionality for DataGrid columns.
WPFGridFilter
PowerCollections
PowerCollections.csproj.user
Properties
Stepi.Collections
bin
Filters
Properties
Stepi.UIFilters
bin
Initializers
Properties
Themes
Test.GridSorting
bin
Debug
Test.GridFilter.vshost.exe
Properties
//******************************
// 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&lt;T&gt; 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&lt;T&gt; is optimized for efficient operations on large (&gt;100 items)
    /// lists, especially for insertions, deletions, copies, and concatinations.
    /// </summary>
    /// <remarks>
    /// <para>BigList&lt;T&gt; class is similar in functionality to the standard List&lt;T&gt; 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&lt;T&gt; differs significantly from List&lt;T&gt; in the performance of various operations, 
    /// especially when the lists become large (several hundred items or more). With List&lt;T&gt;, 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&lt;T&gt; class, however, allows for fast insertions
    /// and deletions anywhere in the list. Furthermore, BigList&lt;T&gt; 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 (&gt;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&lt;T&gt; 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&lt;T&gt; 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&lt;T&gt; that enumerates all the
        /// items in the list.</returns>
        public sealed override IEnumerator<T> GetEnumerator()
        {
            return GetEnumerator(0, int.MaxValue);
        }

        /// <summary>
        /// Given an IEnumerable&lt;T&gt;, 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&lt;T&gt;
        /// interface implementation on the type T.</para></remarks>
        /// <exception cref="InvalidOperationException">The type T does not implement either the IComparable or
        /// IComparable&lt;T&gt; interfaces.</exception>
        public void Sort()
        {
            Sort(Comparers.DefaultComparer<T>());
        }
        
        /// <summary>
        /// Sorts the list in place. A supplied IComparer&lt;T&gt; 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&lt;T&gt; 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&lt;T&gt; 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&lt;T&gt; interface; otherwise, 
        /// incorrect results will be returned.
        /// </summary>
        /// <param name="item">The item to search for.</param>
        /// <param name="comparer">The IComparer&lt;T&gt; 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&lt;T&gt; 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&lt;T&gt; 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);
            } 
        }

    }
}

By viewing downloads associated with this article you agree to the Terms of Service and the article's licence.

If a file you wish to view isn't highlighted, and is a text file (not binary), please let us know and we'll add colourisation support for it.

License

This article, along with any associated source code and files, is licensed under The Eclipse Public License 1.0

Share

About the Author

Stefan Bocutiu
Software Developer (Senior) Lab49
United Kingdom United Kingdom
No Biography provided

You may also be interested in...

| Advertise | Privacy | Terms of Use | Mobile
Web02 | 2.8.160426.1 | Last Updated 29 Jan 2009
Article Copyright 2009 by Stefan Bocutiu
Everything else Copyright © CodeProject, 1999-2016
Layout: fixed | fluid