diff options
Diffstat (limited to 'main/src/core/Mono.Texteditor/Mono.TextEditor.Utils/Rope.cs')
| -rw-r--r-- | main/src/core/Mono.Texteditor/Mono.TextEditor.Utils/Rope.cs | 854 |
1 files changed, 854 insertions, 0 deletions
diff --git a/main/src/core/Mono.Texteditor/Mono.TextEditor.Utils/Rope.cs b/main/src/core/Mono.Texteditor/Mono.TextEditor.Utils/Rope.cs new file mode 100644 index 0000000000..0ce950d5bc --- /dev/null +++ b/main/src/core/Mono.Texteditor/Mono.TextEditor.Utils/Rope.cs @@ -0,0 +1,854 @@ +// Copyright (c) 2014 AlphaSierraPapa for the SharpDevelop Team +// +// Permission is hereby granted, free of charge, to any person obtaining a copy of this +// software and associated documentation files (the "Software"), to deal in the Software +// without restriction, including without limitation the rights to use, copy, modify, merge, +// publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons +// to whom the Software is furnished to do so, subject to the following conditions: +// +// The above copyright notice and this permission notice shall be included in all copies or +// substantial portions of the Software. +// +// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, +// INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR +// PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE +// FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR +// OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER +// DEALINGS IN THE SOFTWARE. + +using System; +using System.Linq; +using System.Collections.Generic; +using System.Diagnostics; +using System.Globalization; +using System.Runtime.Serialization; +using System.Text; + +namespace Mono.TextEditor.Utils +{ + /// <summary> + /// A kind of List<T>, but more efficient for random insertions/removal. + /// Also has cheap Clone() and SubRope() implementations. + /// </summary> + /// <remarks> + /// This class is not thread-safe: multiple concurrent write operations or writes concurrent to reads have undefined behaviour. + /// Concurrent reads, however, are safe. + /// However, clones of a rope are safe to use on other threads even though they share data with the original rope. + /// </remarks> + [Serializable] + [System.Diagnostics.CodeAnalysis.SuppressMessage("Microsoft.Naming", "CA1710:IdentifiersShouldHaveCorrectSuffix")] + public sealed class Rope<T> : IList<T>, ICloneable + { + internal RopeNode<T> root; + + internal Rope(RopeNode<T> root) + { + this.root = root; + root.CheckInvariants(); + } + + /// <summary> + /// Creates a new rope representing the empty string. + /// </summary> + public Rope() + { + // we'll construct the empty rope as a clone of an imaginary static empty rope + this.root = RopeNode<T>.emptyRopeNode; + root.CheckInvariants(); + } + + /// <summary> + /// Creates a rope from the specified input. + /// This operation runs in O(N). + /// </summary> + /// <exception cref="ArgumentNullException">input is null.</exception> + public Rope(IEnumerable<T> input) + { + if (input == null) + throw new ArgumentNullException("input"); + Rope<T> inputRope = input as Rope<T>; + if (inputRope != null) { + // clone ropes instead of copying them + inputRope.root.Publish(); + this.root = inputRope.root; + } else { + string text = input as string; + if (text != null) { + // if a string is IEnumerable<T>, then T must be char + ((Rope<char>)(object)this).root = CharRope.InitFromString(text); + } else { + T[] arr = ToArray(input); + this.root = RopeNode<T>.CreateFromArray(arr, 0, arr.Length); + } + } + this.root.CheckInvariants(); + } + + /// <summary> + /// Creates a rope from a part of the array. + /// This operation runs in O(N). + /// </summary> + /// <exception cref="ArgumentNullException">input is null.</exception> + public Rope(T[] array, int arrayIndex, int count) + { + VerifyArrayWithRange(array, arrayIndex, count); + this.root = RopeNode<T>.CreateFromArray(array, arrayIndex, count); + this.root.CheckInvariants(); + } + + /// <summary> + /// Creates a new rope that lazily initalizes its content. + /// </summary> + /// <param name="length">The length of the rope that will be lazily loaded.</param> + /// <param name="initializer"> + /// The callback that provides the content for this rope. + /// <paramref name="initializer"/> will be called exactly once when the content of this rope is first requested. + /// It must return a rope with the specified length. + /// Because the initializer function is not called when a rope is cloned, and such clones may be used on another threads, + /// it is possible for the initializer callback to occur on any thread. + /// </param> + /// <remarks> + /// Any modifications inside the rope will also cause the content to be initialized. + /// However, insertions at the beginning and the end, as well as inserting this rope into another or + /// using the <see cref="Concat(Rope{T},Rope{T})"/> method, allows constructions of larger ropes where parts are + /// lazily loaded. + /// However, even methods like Concat may sometimes cause the initializer function to be called, e.g. when + /// two short ropes are concatenated. + /// </remarks> + [System.Diagnostics.CodeAnalysis.SuppressMessage("Microsoft.Design", "CA1006:DoNotNestGenericTypesInMemberSignatures")] + public Rope(int length, Func<Rope<T>> initializer) + { + if (initializer == null) + throw new ArgumentNullException("initializer"); + if (length < 0) + throw new ArgumentOutOfRangeException("length", length, "Length must not be negative"); + if (length == 0) { + this.root = RopeNode<T>.emptyRopeNode; + } else { + this.root = new FunctionNode<T>(length, initializer); + } + this.root.CheckInvariants(); + } + + static T[] ToArray(IEnumerable<T> input) + { + T[] arr = input as T[]; + return arr ?? input.ToArray(); + } + + /// <summary> + /// Clones the rope. + /// This operation runs in linear time to the number of rope nodes touched since the last clone was created. + /// If you count the per-node cost to the operation modifying the rope (doing this doesn't increase the complexity of the modification operations); + /// the remainder of Clone() runs in O(1). + /// </summary> + /// <remarks> + /// This method counts as a read access and may be called concurrently to other read accesses. + /// </remarks> + public Rope<T> Clone() + { + // The Publish() call actually modifies this rope instance; but this modification is thread-safe + // as long as the tree structure doesn't change during the operation. + root.Publish(); + return new Rope<T>(root); + } + + object ICloneable.Clone() + { + return this.Clone(); + } + + /// <summary> + /// Resets the rope to an empty list. + /// Runs in O(1). + /// </summary> + public void Clear() + { + root = RopeNode<T>.emptyRopeNode; + OnChanged(); + } + + /// <summary> + /// Gets the length of the rope. + /// Runs in O(1). + /// </summary> + /// <remarks> + /// This method counts as a read access and may be called concurrently to other read accesses. + /// </remarks> + public int Length { + get { return root.length; } + } + + /// <summary> + /// Gets the length of the rope. + /// Runs in O(1). + /// </summary> + /// <remarks> + /// This method counts as a read access and may be called concurrently to other read accesses. + /// </remarks> + public int Count { + get { return root.length; } + } + + /// <summary> + /// Inserts another rope into this rope. + /// Runs in O(lg N + lg M), plus a per-node cost as if <c>newElements.Clone()</c> was called. + /// </summary> + /// <exception cref="ArgumentNullException">newElements is null.</exception> + /// <exception cref="ArgumentOutOfRangeException">index or length is outside the valid range.</exception> + public void InsertRange(int index, Rope<T> newElements) + { + if (index < 0 || index > this.Length) { + throw new ArgumentOutOfRangeException("index", index, "0 <= index <= " + this.Length.ToString(CultureInfo.InvariantCulture)); + } + if (newElements == null) + throw new ArgumentNullException("newElements"); + newElements.root.Publish(); + root = root.Insert(index, newElements.root); + OnChanged(); + } + + /// <summary> + /// Inserts new elemetns into this rope. + /// Runs in O(lg N + M), where N is the length of this rope and M is the number of new elements. + /// </summary> + /// <exception cref="ArgumentNullException">newElements is null.</exception> + /// <exception cref="ArgumentOutOfRangeException">index or length is outside the valid range.</exception> + public void InsertRange(int index, IEnumerable<T> newElements) + { + if (newElements == null) + throw new ArgumentNullException("newElements"); + Rope<T> newElementsRope = newElements as Rope<T>; + if (newElementsRope != null) { + InsertRange(index, newElementsRope); + } else { + T[] arr = ToArray(newElements); + InsertRange(index, arr, 0, arr.Length); + } + } + + /// <summary> + /// Inserts new elements into this rope. + /// Runs in O(lg N + M), where N is the length of this rope and M is the number of new elements. + /// </summary> + /// <exception cref="ArgumentNullException">newElements is null.</exception> + /// <exception cref="ArgumentOutOfRangeException">index or length is outside the valid range.</exception> + public void InsertRange(int index, T[] array, int arrayIndex, int count) + { + if (index < 0 || index > this.Length) { + throw new ArgumentOutOfRangeException("index", index, "0 <= index <= " + this.Length.ToString(CultureInfo.InvariantCulture)); + } + VerifyArrayWithRange(array, arrayIndex, count); + if (count > 0) { + root = root.Insert(index, array, arrayIndex, count); + OnChanged(); + } + } + + /// <summary> + /// Appends multiple elements to the end of this rope. + /// Runs in O(lg N + M), where N is the length of this rope and M is the number of new elements. + /// </summary> + /// <exception cref="ArgumentNullException">newElements is null.</exception> + public void AddRange(IEnumerable<T> newElements) + { + InsertRange(this.Length, newElements); + } + + /// <summary> + /// Appends another rope to the end of this rope. + /// Runs in O(lg N + lg M), plus a per-node cost as if <c>newElements.Clone()</c> was called. + /// </summary> + /// <exception cref="ArgumentNullException">newElements is null.</exception> + public void AddRange(Rope<T> newElements) + { + InsertRange(this.Length, newElements); + } + + /// <summary> + /// Appends new elements to the end of this rope. + /// Runs in O(lg N + M), where N is the length of this rope and M is the number of new elements. + /// </summary> + /// <exception cref="ArgumentNullException">array is null.</exception> + public void AddRange(T[] array, int arrayIndex, int count) + { + InsertRange(this.Length, array, arrayIndex, count); + } + + /// <summary> + /// Removes a range of elements from the rope. + /// Runs in O(lg N). + /// </summary> + /// <exception cref="ArgumentOutOfRangeException">offset or length is outside the valid range.</exception> + public void RemoveRange(int index, int count) + { + VerifyRange(index, count); + if (count > 0) { + root = root.RemoveRange(index, count); + OnChanged(); + } + } + + /// <summary> + /// Copies a range of the specified array into the rope, overwriting existing elements. + /// Runs in O(lg N + M). + /// </summary> + public void SetRange(int index, T[] array, int arrayIndex, int count) + { + VerifyRange(index, count); + VerifyArrayWithRange(array, arrayIndex, count); + if (count > 0) { + root = root.StoreElements(index, array, arrayIndex, count); + OnChanged(); + } + } + + /// <summary> + /// Creates a new rope and initializes it with a part of this rope. + /// Runs in O(lg N) plus a per-node cost as if <c>this.Clone()</c> was called. + /// </summary> + /// <exception cref="ArgumentOutOfRangeException">offset or length is outside the valid range.</exception> + /// <remarks> + /// This method counts as a read access and may be called concurrently to other read accesses. + /// </remarks> + public Rope<T> GetRange(int index, int count) + { + VerifyRange(index, count); + Rope<T> newRope = Clone(); + int endIndex = index + count; + newRope.RemoveRange(endIndex, newRope.Length - endIndex); + newRope.RemoveRange(0, index); + return newRope; + } + + /* + #region Equality + /// <summary> + /// Gets whether the two ropes have the same content. + /// Runs in O(N + M). + /// </summary> + /// <remarks> + /// This method counts as a read access and may be called concurrently to other read accesses. + /// </remarks> + public bool Equals(Rope other) + { + if (other == null) + return false; + // quick detection for ropes that are clones of each other: + if (other.root == this.root) + return true; + if (other.Length != this.Length) + return false; + using (RopeTextReader a = new RopeTextReader(this, false)) { + using (RopeTextReader b = new RopeTextReader(other, false)) { + int charA, charB; + do { + charA = a.Read(); + charB = b.Read(); + if (charA != charB) + return false; + } while (charA != -1); + return true; + } + } + } + + /// <summary> + /// Gets whether two ropes have the same content. + /// Runs in O(N + M). + /// </summary> + public override bool Equals(object obj) + { + return Equals(obj as Rope); + } + + /// <summary> + /// Calculates the hash code of the rope's content. + /// Runs in O(N). + /// </summary> + /// <remarks> + /// This method counts as a read access and may be called concurrently to other read accesses. + /// </remarks> + public override int GetHashCode() + { + int hashcode = 0; + using (RopeTextReader reader = new RopeTextReader(this, false)) { + unchecked { + int val; + while ((val = reader.Read()) != -1) { + hashcode = hashcode * 31 + val; + } + } + } + return hashcode; + } + #endregion + */ + + /// <summary> + /// Concatenates two ropes. The input ropes are not modified. + /// Runs in O(lg N + lg M). + /// </summary> + /// <remarks> + /// This method counts as a read access and may be called concurrently to other read accesses. + /// </remarks> + [System.Diagnostics.CodeAnalysis.SuppressMessage("Microsoft.Design", "CA1000:DoNotDeclareStaticMembersOnGenericTypes")] + public static Rope<T> Concat(Rope<T> left, Rope<T> right) + { + if (left == null) + throw new ArgumentNullException("left"); + if (right == null) + throw new ArgumentNullException("right"); + left.root.Publish(); + right.root.Publish(); + return new Rope<T>(RopeNode<T>.Concat(left.root, right.root)); + } + + /// <summary> + /// Concatenates multiple ropes. The input ropes are not modified. + /// </summary> + /// <remarks> + /// This method counts as a read access and may be called concurrently to other read accesses. + /// </remarks> + [System.Diagnostics.CodeAnalysis.SuppressMessage("Microsoft.Design", "CA1000:DoNotDeclareStaticMembersOnGenericTypes")] + public static Rope<T> Concat(params Rope<T>[] ropes) + { + if (ropes == null) + throw new ArgumentNullException("ropes"); + Rope<T> result = new Rope<T>(); + foreach (Rope<T> r in ropes) + result.AddRange(r); + return result; + } + + #region Caches / Changed event + internal struct RopeCacheEntry + { + internal readonly RopeNode<T> node; + internal readonly int nodeStartIndex; + + internal RopeCacheEntry(RopeNode<T> node, int nodeStartOffset) + { + this.node = node; + this.nodeStartIndex = nodeStartOffset; + } + + internal bool IsInside(int offset) + { + return node != null && offset >= nodeStartIndex && offset < nodeStartIndex + node.length; + } + } + + // cached pointer to 'last used node', used to speed up accesses by index that are close together + [NonSerialized] + volatile ImmutableStack<RopeCacheEntry> lastUsedNodeStack; + + internal void OnChanged() + { + lastUsedNodeStack = null; + + root.CheckInvariants(); + } + #endregion + + #region GetChar / SetChar + /// <summary> + /// Gets/Sets a single character. + /// Runs in O(lg N) for random access. Sequential read-only access benefits from a special optimization and runs in amortized O(1). + /// </summary> + /// <exception cref="ArgumentOutOfRangeException">Offset is outside the valid range (0 to Length-1).</exception> + /// <remarks> + /// The getter counts as a read access and may be called concurrently to other read accesses. + /// </remarks> + public T this[int index] { + get { + // use unsigned integers - this way negative values for index overflow and can be tested for with the same check + if (unchecked((uint)index >= (uint)this.Length)) { + throw new ArgumentOutOfRangeException("index", index, "0 <= index < " + this.Length.ToString(CultureInfo.InvariantCulture)); + } + RopeCacheEntry entry = FindNodeUsingCache(index).PeekOrDefault(); + return entry.node.contents[index - entry.nodeStartIndex]; + } + set { + if (index < 0 || index >= this.Length) { + throw new ArgumentOutOfRangeException("index", index, "0 <= index < " + this.Length.ToString(CultureInfo.InvariantCulture)); + } + root = root.SetElement(index, value); + OnChanged(); + /* Here's a try at implementing the setter using the cached node stack (UNTESTED code!). + * However I don't use the code because it's complicated and doesn't integrate correctly with change notifications. + * Instead, I'll use the much easier to understand recursive solution. + * Oh, and it also doesn't work correctly with function nodes. + ImmutableStack<RopeCacheEntry> nodeStack = FindNodeUsingCache(offset); + RopeCacheEntry entry = nodeStack.Peek(); + if (!entry.node.isShared) { + entry.node.contents[offset - entry.nodeStartOffset] = value; + // missing: clear the caches except for the node stack cache (e.g. ToString() cache?) + } else { + RopeNode oldNode = entry.node; + RopeNode newNode = oldNode.Clone(); + newNode.contents[offset - entry.nodeStartOffset] = value; + for (nodeStack = nodeStack.Pop(); !nodeStack.IsEmpty; nodeStack = nodeStack.Pop()) { + RopeNode parentNode = nodeStack.Peek().node; + RopeNode newParentNode = parentNode.CloneIfShared(); + if (newParentNode.left == oldNode) { + newParentNode.left = newNode; + } else { + Debug.Assert(newParentNode.right == oldNode); + newParentNode.right = newNode; + } + if (parentNode == newParentNode) { + // we were able to change the existing node (it was not shared); + // there's no reason to go further upwards + ClearCacheOnModification(); + return; + } else { + oldNode = parentNode; + newNode = newParentNode; + } + } + // we reached the root of the rope. + Debug.Assert(root == oldNode); + root = newNode; + ClearCacheOnModification(); + }*/ + } + } + + internal ImmutableStack<RopeCacheEntry> FindNodeUsingCache(int index) + { + Debug.Assert(index >= 0 && index < this.Length); + + // thread safety: fetch stack into local variable + ImmutableStack<RopeCacheEntry> stack = lastUsedNodeStack; + ImmutableStack<RopeCacheEntry> oldStack = stack; + + if (stack == null) { + stack = ImmutableStack<RopeCacheEntry>.Empty.Push(new RopeCacheEntry(root, 0)); + } + while (!stack.PeekOrDefault().IsInside(index)) + stack = stack.Pop(); + while (true) { + RopeCacheEntry entry = stack.PeekOrDefault(); + // check if we've reached a leaf or function node + if (entry.node.height == 0) { + if (entry.node.contents == null) { + // this is a function node - go down into its subtree + entry = new RopeCacheEntry(entry.node.GetContentNode(), entry.nodeStartIndex); + // entry is now guaranteed NOT to be another function node + } + if (entry.node.contents != null) { + // this is a node containing actual content, so we're done + break; + } + } + // go down towards leaves + if (index - entry.nodeStartIndex >= entry.node.left.length) + stack = stack.Push(new RopeCacheEntry(entry.node.right, entry.nodeStartIndex + entry.node.left.length)); + else + stack = stack.Push(new RopeCacheEntry(entry.node.left, entry.nodeStartIndex)); + } + + // write back stack to volatile cache variable + // (in multithreaded access, it doesn't matter which of the threads wins - it's just a cache) + if (oldStack != stack) { + // no need to write when we the cache variable didn't change + lastUsedNodeStack = stack; + } + + // this method guarantees that it finds a leaf node + Debug.Assert(stack.Peek().node.contents != null); + return stack; + } + #endregion + + #region ToString / WriteTo + internal void VerifyRange(int startIndex, int length) + { + if (startIndex < 0 || startIndex > this.Length) { + throw new ArgumentOutOfRangeException("startIndex", startIndex, "0 <= startIndex <= " + this.Length.ToString(CultureInfo.InvariantCulture)); + } + if (length < 0 || startIndex + length > this.Length) { + throw new ArgumentOutOfRangeException("length", length, "0 <= length, startIndex(" + startIndex + ")+length <= " + this.Length.ToString(CultureInfo.InvariantCulture)); + } + } + + internal static void VerifyArrayWithRange(T[] array, int arrayIndex, int count) + { + if (array == null) + throw new ArgumentNullException("array"); + if (arrayIndex < 0 || arrayIndex > array.Length) { + throw new ArgumentOutOfRangeException("startIndex", arrayIndex, "0 <= arrayIndex <= " + array.Length.ToString(CultureInfo.InvariantCulture)); + } + if (count < 0 || arrayIndex + count > array.Length) { + throw new ArgumentOutOfRangeException("count", count, "0 <= length, arrayIndex(" + arrayIndex + ")+count <= " + array.Length.ToString(CultureInfo.InvariantCulture)); + } + } + + /// <summary> + /// Creates a string from the rope. Runs in O(N). + /// </summary> + /// <returns>A string consisting of all elements in the rope as comma-separated list in {}. + /// As a special case, Rope<char> will return its contents as string without any additional separators or braces, + /// so it can be used like StringBuilder.ToString().</returns> + /// <remarks> + /// This method counts as a read access and may be called concurrently to other read accesses. + /// </remarks> + public override string ToString() + { + Rope<char> charRope = this as Rope<char>; + if (charRope != null) { + return charRope.ToString(0, this.Length); + } else { + StringBuilder b = new StringBuilder(); + foreach (T element in this) { + if (b.Length == 0) + b.Append('{'); + else + b.Append(", "); + b.Append(element.ToString()); + } + b.Append('}'); + return b.ToString(); + } + } + + internal string GetTreeAsString() + { + #if DEBUG + return root.GetTreeAsString(); + #else + return "Not available in release build."; + #endif + } + #endregion + + bool ICollection<T>.IsReadOnly { + get { return false; } + } + + /// <summary> + /// Finds the first occurance of item. + /// Runs in O(N). + /// </summary> + /// <returns>The index of the first occurance of item, or -1 if it cannot be found.</returns> + /// <remarks> + /// This method counts as a read access and may be called concurrently to other read accesses. + /// </remarks> + public int IndexOf(T item) + { + return IndexOf(item, 0, this.Length); + } + + /// <summary> + /// Gets the index of the first occurrence the specified item. + /// </summary> + /// <param name="item">Item to search for.</param> + /// <param name="startIndex">Start index of the search.</param> + /// <param name="count">Length of the area to search.</param> + /// <returns>The first index where the item was found; or -1 if no occurrence was found.</returns> + /// <remarks> + /// This method counts as a read access and may be called concurrently to other read accesses. + /// </remarks> + public int IndexOf(T item, int startIndex, int count) + { + VerifyRange(startIndex, count); + + while (count > 0) { + var entry = FindNodeUsingCache(startIndex).PeekOrDefault(); + T[] contents = entry.node.contents; + int startWithinNode = startIndex - entry.nodeStartIndex; + int nodeLength = System.Math.Min(entry.node.length, startWithinNode + count); + int r = Array.IndexOf(contents, item, startWithinNode, nodeLength - startWithinNode); + if (r >= 0) + return entry.nodeStartIndex + r; + count -= nodeLength - startWithinNode; + startIndex = entry.nodeStartIndex + nodeLength; + } + return -1; + } + + /// <summary> + /// Gets the index of the last occurrence of the specified item in this rope. + /// </summary> + public int LastIndexOf(T item) + { + return LastIndexOf(item, 0, this.Length); + } + + /// <summary> + /// Gets the index of the last occurrence of the specified item in this rope. + /// </summary> + /// <param name="item">The search item</param> + /// <param name="startIndex">Start index of the area to search.</param> + /// <param name="count">Length of the area to search.</param> + /// <returns>The last index where the item was found; or -1 if no occurrence was found.</returns> + /// <remarks>The search proceeds backwards from (startIndex+count) to startIndex. + /// This is different than the meaning of the parameters on Array.LastIndexOf!</remarks> + public int LastIndexOf(T item, int startIndex, int count) + { + VerifyRange(startIndex, count); + + var comparer = EqualityComparer<T>.Default; + for (int i = startIndex + count - 1; i >= startIndex; i--) { + if (comparer.Equals(this[i], item)) + return i; + } + return -1; + } + + /// <summary> + /// Inserts the item at the specified index in the rope. + /// Runs in O(lg N). + /// </summary> + public void Insert(int index, T item) + { + InsertRange(index, new[] { item }, 0, 1); + } + + /// <summary> + /// Removes a single item from the rope. + /// Runs in O(lg N). + /// </summary> + public void RemoveAt(int index) + { + RemoveRange(index, 1); + } + + /// <summary> + /// Appends the item at the end of the rope. + /// Runs in O(lg N). + /// </summary> + public void Add(T item) + { + InsertRange(this.Length, new[] { item }, 0, 1); + } + + /// <summary> + /// Searches the item in the rope. + /// Runs in O(N). + /// </summary> + /// <remarks> + /// This method counts as a read access and may be called concurrently to other read accesses. + /// </remarks> + public bool Contains(T item) + { + return IndexOf(item) >= 0; + } + + /// <summary> + /// Copies the whole content of the rope into the specified array. + /// Runs in O(N). + /// </summary> + /// <remarks> + /// This method counts as a read access and may be called concurrently to other read accesses. + /// </remarks> + public void CopyTo(T[] array, int arrayIndex) + { + CopyTo(0, array, arrayIndex, this.Length); + } + + /// <summary> + /// Copies the a part of the rope into the specified array. + /// Runs in O(lg N + M). + /// </summary> + /// <remarks> + /// This method counts as a read access and may be called concurrently to other read accesses. + /// </remarks> + public void CopyTo(int index, T[] array, int arrayIndex, int count) + { + VerifyRange(index, count); + VerifyArrayWithRange(array, arrayIndex, count); + this.root.CopyTo(index, array, arrayIndex, count); + } + + /// <summary> + /// Removes the first occurance of an item from the rope. + /// Runs in O(N). + /// </summary> + public bool Remove(T item) + { + int index = IndexOf(item); + if (index >= 0) { + RemoveAt(index); + return true; + } + return false; + } + + /// <summary> + /// Retrieves an enumerator to iterate through the rope. + /// The enumerator will reflect the state of the rope from the GetEnumerator() call, further modifications + /// to the rope will not be visible to the enumerator. + /// </summary> + /// <remarks> + /// This method counts as a read access and may be called concurrently to other read accesses. + /// </remarks> + public IEnumerator<T> GetEnumerator() + { + this.root.Publish(); + return Enumerate(root); + } + + /// <summary> + /// Creates an array and copies the contents of the rope into it. + /// Runs in O(N). + /// </summary> + /// <remarks> + /// This method counts as a read access and may be called concurrently to other read accesses. + /// </remarks> + public T[] ToArray() + { + T[] arr = new T[this.Length]; + this.root.CopyTo(0, arr, 0, arr.Length); + return arr; + } + + /// <summary> + /// Creates an array and copies the contents of the rope into it. + /// Runs in O(N). + /// </summary> + /// <remarks> + /// This method counts as a read access and may be called concurrently to other read accesses. + /// </remarks> + public T[] ToArray(int startIndex, int count) + { + VerifyRange(startIndex, count); + T[] arr = new T[count]; + CopyTo(startIndex, arr, 0, count); + return arr; + } + + static IEnumerator<T> Enumerate(RopeNode<T> node) + { + Stack<RopeNode<T>> stack = new Stack<RopeNode<T>>(); + while (node != null) { + // go to leftmost node, pushing the right parts that we'll have to visit later + while (node.contents == null) { + if (node.height == 0) { + // go down into function nodes + node = node.GetContentNode(); + continue; + } + Debug.Assert(node.right != null); + stack.Push(node.right); + node = node.left; + } + // yield contents of leaf node + for (int i = 0; i < node.length; i++) { + yield return node.contents[i]; + } + // go up to the next node not visited yet + if (stack.Count > 0) + node = stack.Pop(); + else + node = null; + } + } + + System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() + { + return this.GetEnumerator(); + } + } +} |