//****************************** // 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 { ///

/// BigList<T> provides a list of items, in order, with indices of the items ranging from 0 to one less /// than the count of items in the collection. BigList<T> is optimized for efficient operations on large (>100 items) /// lists, especially for insertions, deletions, copies, and concatinations. ///

/// /// BigList<T> class is similar in functionality to the standard List<T> class. Both classes /// provide a collection that stores an set of items in order, with indices of the items ranging from 0 to one less /// than the count of items in the collection. Both classes provide the ability to add and remove items from any index, /// and the get or set the item at any index. /// BigList<T> differs significantly from List<T> in the performance of various operations, /// especially when the lists become large (several hundred items or more). With List<T>, inserting or removing /// elements from anywhere in a large list except the end is very inefficient -- every item after the point of inserting /// or deletion has to be moved in the list. The BigList<T> class, however, allows for fast insertions /// and deletions anywhere in the list. Furthermore, BigList<T> allows copies of a list, sub-parts /// of a list, and concatinations of two lists to be very fast. When a copy is made of part or all of a BigList, /// two lists shared storage for the parts of the lists that are the same. Only when one of the lists is changed is additional /// memory allocated to store the distinct parts of the lists. /// 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. /// In general, use a List when the only operations you are using are Add (to the end), foreach, /// or indexing, or you are very sure the list will always remain small (less than 100 items). For large (>100 items) lists /// that do insertions, removals, copies, concatinations, or sub-ranges, BigList will be more efficient than List. /// In almost all cases, BigList is more efficient and easier to use than LinkedList. /// /// The type of items to store in the BigList. [Serializable] public class BigList: ListBase, 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; ///

/// 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. ///

private void StopEnumerations() { ++changeStamp; } ///

/// Checks the given stamp against the current change stamp. If different, the /// collection has changed during enumeration and an InvalidOperationException /// must be thrown ///

/// changeStamp at the start of the enumeration. private void CheckEnumerationStamp(int startStamp) { if (startStamp != changeStamp) { throw new InvalidOperationException(Strings.ChangeDuringEnumeration); } } ///

/// Creates a new BigList. The BigList is initially empty. ///

/// Creating a empty BigList takes constant time and consumes a very small amount of memory. public BigList() { root = null; } ///

/// Creates a new BigList initialized with the items from , in order. ///

/// Initializing the tree list with the elements of collection takes time O(N), where N is the number of /// items in . /// The collection used to initialize the BigList. /// is null. public BigList(IEnumerable collection) { if (collection == null) throw new ArgumentNullException("collection"); root = NodeFromEnumerable(collection); CheckBalance(); } ///

/// Creates a new BigList initialized with a given number of copies of the items from , in order. ///

/// Initializing the tree list with the elements of collection takes time O(N + log K), where N is the number of /// items in , and K is the number of copies. /// Number of copies of the collection to use. /// The collection used to initialize the BigList. /// is negative. /// is null. public BigList(IEnumerable collection, int copies) { if (collection == null) throw new ArgumentNullException("collection"); root = NCopiesOfNode(copies, NodeFromEnumerable(collection)); CheckBalance(); } ///

/// Creates a new BigList that is a copy of . ///

/// 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. /// The BigList to copy. /// is null. public BigList(BigList list) { if (list == null) throw new ArgumentNullException("list"); if (list.root == null) root = null; else { list.root.MarkShared(); root = list.root; } } ///

/// Creates a new BigList that is several copies of . ///

/// 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. /// Number of copies of the collection to use. /// The BigList to copy. /// is null. public BigList(BigList 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); } } ///

/// Creates a new BigList from the indicated Node. ///

/// Node that becomes the new root. If null, the new BigList is empty. private BigList(Node node) { this.root = node; CheckBalance(); } ///

/// Gets the number of items stored in the BigList. The indices of the items /// range from 0 to Count-1. ///

/// Getting the number of items in the BigList takes constant time. /// The number of items in the BigList. public sealed override int Count { get { if (root == null) return 0; else return root.Count; } } ///

/// Gets or sets an item in the list, by index. ///

/// Gettingor setting an item takes time O(log N), where N is the number of items /// in the list. /// 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. /// 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. /// The value of the item at the given index. /// is less than zero or /// greater than or equal to Count. 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, 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; } } ///

/// Removes all of the items from the BigList. ///

/// Clearing a BigList takes constant time. public sealed override void Clear() { StopEnumerations(); root = null; } ///

/// Inserts a new item at the given index in the BigList. All items at indexes /// equal to or greater than move up one index. ///

/// 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). /// /// The index to insert the item at. After the /// insertion, the inserted item is located at this index. The /// first item has index 0. /// The item to insert at the given index. /// is /// less than zero or greater than Count. 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(); } } } } ///

/// Inserts a collection of items at the given index in the BigList. All items at indexes /// equal to or greater than increase their indices /// by the number of items inserted. ///

/// 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. /// /// 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. /// The collection of items to insert at the given index. /// is /// less than zero or greater than Count. /// is null. public void InsertRange(int index, IEnumerable 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(); } } } } ///

/// Inserts a BigList of items at the given index in the BigList. All items at indexes /// equal to or greater than increase their indices /// by the number of items inserted. ///

/// 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. /// /// 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. /// The BigList of items to insert at the given index. /// is /// less than zero or greater than Count. /// is null. public void InsertRange(int index, BigList 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(); } } } } ///

/// Removes the item at the given index in the BigList. All items at indexes /// greater than move down one index. ///

/// 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. /// /// The index in the list to remove the item at. The /// first item in the list has index 0. /// is /// less than zero or greater than or equal to Count. public sealed override void RemoveAt(int index) { RemoveRange(index, 1); } ///

/// Removes a range of items at the given index in the Deque. All items at indexes /// greater than move down indices /// in the Deque. ///

/// The amount of time to delete items in the Deque is proportional /// to the distance of index from the closest end of the Deque, plus : /// O(count + Min(, Count - 1 - )). /// /// The index in the list to remove the range at. The /// first item in the list has index 0. /// The number of items to remove. /// is /// less than zero or greater than or equal to Count, or is less than zero /// or too large. 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(); } } ///

/// Adds an item to the end of the BigList. The indices of all existing items /// in the Deque are unchanged. ///

/// Adding an item takes, on average, constant time. /// The item to add. 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(); } } } ///

/// 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. ///

/// Adding an item takes, on average, constant time. /// The item to add. 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(); } } } ///

/// 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. ///

/// This method takes time O(M + log N), where M is the number of items in the /// , and N is the size of the BigList. /// The collection of items to add. /// is null. public void AddRange(IEnumerable 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(); } } } ///

/// 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 . /// The first item in the added collection becomes the first item in the BigList. ///

/// This method takes time O(M + log N), where M is the number of items in the /// , and N is the size of the BigList. /// The collection of items to add. /// is null. public void AddRangeToFront(IEnumerable 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(); } } } ///

/// Creates a new BigList that is a copy of this list. ///

/// 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. /// A copy of the current list public BigList Clone() { if (root == null) return new BigList(); else { root.MarkShared(); return new BigList(root); } } ///

/// Creates a new BigList that is a copy of this list. ///

/// 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. /// A copy of the current list object ICloneable.Clone() { return Clone(); } ///

/// 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. ///

/// If T is a reference type, it must implement /// ICloneable. Otherwise, an InvalidOperationException is thrown. /// If T is a reference type, cloning the list takes time approximate O(N), where N is the number of items in the list. /// The cloned set. /// T is a reference type that does not implement ICloneable. public BigList CloneContents() { if (root == null) return new BigList(); 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(Algorithms.Convert(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()); })); } } ///

/// Adds a BigList of items to the end of BigList. The indices of all existing items /// are unchanged. The last item in becomes the /// last item in this list. The added list is unchanged. ///

/// This method takes, on average, constant time, regardless of the size /// of either list. Although conceptually all of the items in are /// copied, storage is shared between the two lists until changes are made to the /// shared sections. /// The list of items to add. /// is null. public void AddRange(BigList 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(); } } } ///

/// Adds a BigList of items to the front of BigList. The indices of all existing items /// are increased by the number of items in . The first item in /// becomes the first item in this list. The added list is unchanged. ///

/// This method takes, on average, constant time, regardless of the size /// of either list. Although conceptually all of the items in are /// copied, storage is shared between the two lists until changes are made to the /// shared sections. /// The list of items to add. /// is null. public void AddRangeToFront(BigList 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(); } } } ///

/// Concatenates two lists together to create a new list. Both lists being concatenated /// are unchanged. The resulting list contains all the items in , followed /// by all the items in . ///

/// 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. /// The first list to concatenate. /// The second list to concatenate. /// or is null. public static BigList operator +(BigList first, BigList 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 result = new BigList(first.root.Append(second.root, false)); result.CheckBalance(); return result; } } ///

/// Creates a new list that contains a subrange of elements from this list. The /// current list is unchanged. ///

/// 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. /// If a view of a sub-range is desired, instead of a copy, use the /// more efficient method, which provides a view onto a sub-range of items. /// The starting index of the sub-range. /// The number of items in the sub-range. If this is zero, /// the returned list is empty. /// A new list with the items that start at . public BigList GetRange(int index, int count) { if (count == 0) return new BigList(); if (index < 0 || index >= Count) throw new ArgumentOutOfRangeException("index"); if (count < 0 || count > Count - index) throw new ArgumentOutOfRangeException("count"); return new BigList(root.Subrange(index, index + count - 1)); } ///

/// Returns a view onto a sub-range of this list. Items are not copied; the /// returned IList<T> is simply a different view onto the same underlying items. Changes to this list /// are reflected in the view, and vice versa. Insertions and deletions in the view change the size of the /// view, but insertions and deletions in the underlying list do not. ///

/// /// If a copy of the sub-range is desired, use the method instead. /// This method can be used to apply an algorithm to a portion of a list. For example: /// Algorithms.ReverseInPlace(list.Range(3, 6)) /// will reverse the 6 items beginning at index 3. /// The starting index of the view. /// The number of items in the view. /// A list that is a view onto the given sub-list. /// or is negative. /// + is greater than the /// size of this list. public sealed override IList 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); } ///

/// Enumerates a range of the items in the list, in order. The item at /// is enumerated first, then the next item at index 1, and so on. At most /// items are enumerated. ///

/// 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. /// Index to start enumerating at. /// Max number of items to enumerate. /// An IEnumerator<T> that enumerates all the /// items in the given range. private IEnumerator 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. } } } ///

/// 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. ///

/// 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. /// An IEnumerator<T> that enumerates all the /// items in the list. public sealed override IEnumerator GetEnumerator() { return GetEnumerator(0, int.MaxValue); } ///

/// Given an IEnumerable<T>, create a new Node with all of the /// items in the enumerable. Returns null if the enumerable has no items. ///

/// The collection to copy. /// Returns a Node, not shared or with any shared children, /// with the items from the collection. If the collection was empty, /// null is returned. private Node NodeFromEnumerable(IEnumerable collection) { Node node = null; LeafNode leaf; IEnumerator 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; } ///

/// 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. ///

/// The enumerator to take items from. /// A LeafNode with items taken from the enumerator. private LeafNode LeafFromEnumerator(IEnumerator 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; } ///

/// Create a node that has N copies of the given node. ///

/// Number of copies. Must be non-negative. /// Node to make copies of. /// null if node is null or copies is 0. Otherwise, a node consisting of copies /// of node. /// copies is negative. 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; } ///

/// 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. ///

private void CheckBalance() { if (root != null && (root.Depth > BALANCEFACTOR && !(root.Depth - BALANCEFACTOR <= MAXFIB && Count >= FIBONACCI[root.Depth - BALANCEFACTOR]))) { Rebalance(); } } ///

/// 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. ///

/// 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). /// 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])); } ///

/// Part of the rebalancing algorithm. Adds a node to the rebalance array. If it is already balanced, add it directly, otherwise /// add its children. ///

/// Rebalance array to insert into. /// Node to add. /// If true, mark the node as shared before adding, because one /// of its parents was shared. 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); } } ///

/// Part of the rebalancing algorithm. Adds a balanced node to the rebalance array. ///

/// Rebalance array to insert into. /// Node to add. 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 } ///

/// 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 to each item in the list, in /// order. The current list is unchanged. ///

/// The type each item is being converted to. /// A delegate to the method to call, passing each item in . /// The resulting BigList from applying to each item in this list. /// is null. public new BigList ConvertAll(Converter converter) { return new BigList(Algorithms.Convert(this, converter)); } ///

/// Reverses the current list in place. ///

public void Reverse() { Algorithms.ReverseInPlace(this); } ///

/// Reverses the items in the range of items starting from , in place. ///

/// The starting index of the range to reverse. /// The number of items in range to reverse. public void Reverse(int start, int count) { Algorithms.ReverseInPlace(Range(start, count)); } ///

/// Sorts the list in place. ///

/// 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. /// Values are compared by using the IComparable or IComparable<T> /// interface implementation on the type T. /// The type T does not implement either the IComparable or /// IComparable<T> interfaces. public void Sort() { Sort(Comparers.DefaultComparer()); } ///

/// Sorts the list in place. A supplied IComparer<T> is used /// to compare the items in the list. ///

/// 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. /// The comparer instance used to compare items in the collection. Only /// the Compare method is used. public void Sort(IComparer comparer) { Algorithms.SortInPlace(this, comparer); } ///

/// Sorts the list in place. A supplied Comparison<T> delegate is used /// to compare the items in the list. ///

/// 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. /// The comparison delegate used to compare items in the collection. public void Sort(Comparison comparison) { Sort(Comparers.ComparerFromComparison(comparison)); } ///

/// 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. ///

/// The item to search for. /// Returns the index of the first occurence of in the list. If the item does not occur /// in the list, the bitwise complement of the first item larger than in the list is returned. If no item is /// larger than , the bitwise complement of Count is returned. /// The type T does not implement either the IComparable or /// IComparable<T> interfaces. public int BinarySearch(T item) { return BinarySearch(item, Comparers.DefaultComparer()); } ///

/// Searches a sorted list for an item via binary search. The list must be sorted /// by the ordering defined by the passed IComparer<T> interface; otherwise, /// incorrect results will be returned. ///

/// The item to search for. /// The IComparer<T> interface used to sort the list. /// Returns the index of the first occurence of in the list. If the item does not occur /// in the list, the bitwise complement of the first item larger than in the list is returned. If no item is /// larger than , the bitwise complement of Count is returned. public int BinarySearch(T item, IComparer comparer) { int count, index; count = Algorithms.BinarySearch(this, item, comparer, out index); if (count == 0) return (~index); else return index; } ///

/// Searches a sorted list for an item via binary search. The list must be sorted /// by the ordering defined by the passed Comparison<T> delegate; otherwise, /// incorrect results will be returned. ///

/// The item to search for. /// The comparison delegate used to sort the list. /// Returns the index of the first occurence of in the list. If the item does not occur /// in the list, the bitwise complement of the first item larger than in the list is returned. If no item is /// larger than , the bitwise complement of Count is returned. public int BinarySearch(T item, Comparison comparison) { return BinarySearch(item, Comparers.ComparerFromComparison(comparison)); } #if DEBUG ///

/// Attempts to validate the internal consistency of the tree. ///

public void Validate() { if (root != null) { root.Validate(); Debug.Assert(Count != 0); } else Debug.Assert(Count == 0); } ///

/// Prints out the internal structure of the tree, for debugging purposes. ///

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 ///

/// The base class for the two kinds of nodes in the tree: Concat nodes /// and Leaf nodes. ///

[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; ///

/// The number of items stored in the node (or below it). ///

/// The number of items in the node or below. public int Count { get { return count; } } ///

/// 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. ///

/// public bool Shared { get { return shared; } } ///

/// Marks this node as shared by setting the shared variable. ///

public void MarkShared() { shared = true; } ///

/// Gets the depth of this node. A leaf node has depth 0, /// a concat node with two leaf children has depth 1, etc. ///

/// The depth of this node. public abstract int Depth { get;} ///

/// Returns the items at the given index in this node. ///

/// 0-based index, relative to this node. /// Item at that index. public abstract T GetAt(int index); ///

/// 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. ///

/// Inclusive first element, relative to this node. /// Inclusize last element, relative to this node. /// Node with the given sub-range. 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. ///

/// Changes the item at the given index. Never changes this node, /// but always returns a new node with the given item changed. ///

/// Index, relative to this node, to change. /// New item to place at the given index. /// A new node with the given item changed. public abstract Node SetAt(int index, T item); ///

/// Changes the item at the given index. May change this node, /// or return a new node with the given item changed. ///

/// Append a node after this node. Never changes this node, but returns /// a new node with the given appending done. ///

/// Append a node after this node. May change this node, or return /// a new node. ///

/// 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. ///

/// Item to append. /// A node with the given item appended to this node. May be a new /// node or the current node. public abstract Node AppendInPlace(T item); ///

/// 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. ///

/// 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. ///

/// Inserts a node inside this node. Never changes this node, but returns /// a new node with the given appending done. ///

/// 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. ///

/// Index, relative to this node, to insert at. Must /// be in bounds. /// Item to insert. /// A node with the give item inserted. If done in-place, returns /// "this". public abstract Node InsertInPlace(int index, T item); ///

/// Inserts a node inside this node. May change this node, or return /// a new node with the given appending done. ///

/// Validates the node for consistency, as much as possible. Also validates /// child nodes, if any. ///

public abstract void Validate(); ///

/// Print out the contents of this node. ///

/// Prefix to use in front of this node. /// Prefixed to use in front of children of this node. public abstract void Print(string prefixNode, string prefixChildren); #endif //DEBUG ///

/// Prefpend a node before this node. Never changes this node, but returns /// a new node with the given prepending done. ///

/// Node to prepend. /// 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. /// A new node with the give node prepended to this node. public Node Prepend(Node node, bool nodeIsUnused) { if (nodeIsUnused) return node.AppendInPlace(this, false); else return node.Append(this, false); } ///

/// Prepend a node before this node. May change this node, or return /// a new node. ///

/// Node to prepend. /// 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. /// A node with the give node prepended to this node. May be a new /// node or the current node. public Node PrependInPlace(Node node, bool nodeIsUnused) { if (nodeIsUnused) return node.AppendInPlace(this, !this.shared); else return node.Append(this, !this.shared); } ///

/// 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. ///

/// Item to prepend. /// A node with the given item prepended to this node. May be a new /// node or the current node. public abstract Node PrependInPlace(T item); ///

/// 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. ///

/// True if the node is balanced by this definition. public bool IsBalanced() { return (Depth <= MAXFIB && Count >= FIBONACCI[Depth]); } ///

/// 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. ///

/// True if the node is almost balanced by this definition. public bool IsAlmostBalanced() { return (Depth == 0 || (Depth - 1 <= MAXFIB && Count >= FIBONACCI[Depth - 1])); } } ///

/// 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". ///

[Serializable] private sealed class LeafNode : Node { ///

/// Array that stores the items in the nodes. Always has a least "count" elements, /// but may have more as padding. ///

public T[] items; ///

/// Creates a LeafNode that holds a single item. ///

/// Item to place into the leaf node. 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; } ///

/// Creates a new leaf node with the indicates count of item and the ///

/// Number of items. Can't be zero. /// The array of items. The LeafNode takes /// possession of this array. 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; } } ///

/// Returns the items at the given index in this node. ///

/// 0-based index, relative to this node. /// Item at that index. public override T GetAt(int index) { return items[index]; } ///

/// Changes the item at the given index. May change this node, /// or return a new node with the given item changed. ///

/// Changes the item at the given index. Never changes this node, /// but always returns a new node with the given item changed. ///

/// Index, relative to this node, to change. /// New item to place at the given index. /// A new node with the given item changed. public override Node SetAt(int index, T item) { T[] newItems = (T[])items.Clone(); newItems[index] = item; return new LeafNode(count, newItems); } ///

/// 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. ///

/// Other node to possible merge. /// If could be merged into this node, returns /// true. Otherwise returns false and the current node is unchanged. 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; } ///

/// 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. ///

/// Other node to possible merge. /// If the nodes could be merged, returns the new node. Otherwise /// returns null. 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; } ///

/// Item to prepend. /// A node with the given item prepended to this node. May be a new /// node or the current node. 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); } } ///

/// Item to append. /// A node with the given item appended to this node. May be a new /// node or the current node. 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)); } } ///

/// Append a node after this node. May change this node, or return /// a new node. ///

/// Node to append. /// 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. /// A node with the give node appended to this node. May be a new /// node or the current node. 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); } ///

/// Index, relative to this node, to insert at. Must /// be in bounds. /// Item to insert. /// A node with the give item inserted. If done in-place, returns /// "this". 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); } } } ///

/// Inserts a node inside this node. May change this node, or return /// a new node with the given appending done. ///

/// Index, relative to this node, to insert at. Must /// be in bounds. /// Node to insert. /// 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. /// A node with the given item inserted. If done in-place, returns /// "this". 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; } } ///

/// Inserts a node inside this node. Never changes this node, but returns /// a new node with the given appending done. ///

/// Index, relative to this node, to insert at. Must /// be in bounds. /// Node to insert. /// 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. /// A new node with the give node inserted. 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; } } ///

/// Inclusive index of first item in sub-range, relative /// to this node. /// Inclusize index of last item in sub-range, relative /// to this node. /// A node with the sub-range removed. If done in-place, returns /// "this". 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; } ///

/// Inclusive index of first item in sub-range, relative /// to this node. /// Inclusize index of last item in sub-range, relative /// to this node. /// A new node with the sub-range removed. 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); } ///

/// Validates the node for consistency, as much as possible. Also validates /// child nodes, if any. ///

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); } ///

/// Print out the contents of this node. ///

/// Prefix to use in front of this node. /// Prefixed to use in front of children of this node. 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 } ///

/// 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. ///

[Serializable] private sealed class ConcatNode : Node { ///

/// The left and right child nodes. They are never null. ///

public Node left, right; ///

/// 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. ///

private short depth; ///

/// 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. ///

/// The depth of this node. public override int Depth { get { return depth; } } ///

/// Create a new ConcatNode with the given children. ///

/// The left child. May not be null. /// The right child. May not be null. 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); } ///

/// 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. ///

/// New left child. /// New right child. /// New node with the given children. Returns null if and only if both /// new children are null. 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); } ///

/// 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. ///

/// New left child. /// New right child. /// Node with the given children. Usually, but not always, this. Returns /// null if and only if both new children are null. 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; } ///

/// Returns the items at the given index in this node. ///

/// 0-based index, relative to this node. /// Item at that index. public override T GetAt(int index) { int leftCount = left.Count; if (index < leftCount) return left.GetAt(index); else return right.GetAt(index - leftCount); } ///

/// Changes the item at the given index. May change this node, /// or return a new node with the given item changed. ///

/// Index, relative to this node, to change. /// New item to place at the given index. /// A node with the give item changed. If it can be done in place /// then "this" is returned. 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; } } ///

/// Changes the item at the given index. Never changes this node, /// but always returns a new node with the given item changed. ///

/// Index, relative to this node, to change. /// New item to place at the given index. /// A new node with the given item changed. 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)); } } ///

/// Item to prepend. /// A node with the given item prepended to this node. May be a new /// node or the current node. 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); } ///

/// Item to append. /// A node with the given item appended to this node. May be a new /// node or the current node. 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)); } ///

/// Append a node after this node. May change this node, or return /// a new node. ///

/// Inserts a node inside this node. May change this node, or return /// a new node with the given appending done. ///

/// Inserts a node inside this node. Never changes this node, but returns /// a new node with the given appending done. ///

/// Inclusive index of first item in sub-range, relative /// to this node. /// Inclusize index of last item in sub-range, relative /// to this node. /// A node with the sub-range removed. If done in-place, returns /// "this". 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); } ///

/// Inclusive index of first item in sub-range, relative /// to this node. /// Inclusize index of last item in sub-range, relative /// to this node. /// A new node with the sub-range removed. 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); } ///

/// Inclusive first element, relative to this node. /// Inclusize last element, relative to this node. /// Node with the given sub-range. 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 ///

/// Validates the node for consistency, as much as possible. Also validates /// child nodes, if any. ///

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(); } ///

/// Print out the contents of this node. ///

/// Prefix to use in front of this node. /// Prefixed to use in front of children of this node. 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 } ///

/// The class that is used to implement IList<T> to view a sub-range /// of a BigList. The object stores a wrapped list, and a start/count indicating /// a sub-range of the list. Insertion/deletions through the sub-range view /// cause the count to change also; insertions and deletions directly on /// the wrapped list do not. ///

/// 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. [Serializable] private class BigListRange : ListBase { private BigList wrappedList; private int start; private int count; ///

/// Create a sub-range view object on the indicate part /// of the list. ///

/// List to wrap. /// The start index of the view in the wrapped list. /// The number of items in the view. public BigListRange(BigList 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 GetEnumerator() { return wrappedList.GetEnumerator(start, count); } } } }