// 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 ICSharpCode.AvalonEdit.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 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 = 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(); } } }