713 lines
26 KiB
C#
713 lines
26 KiB
C#
|
// 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.Diagnostics;
|
|||
|
|
using System.Text;
|
|||
|
|
|
|||
|
|
namespace Unity.CodeEditor.Utils
|
|||
|
|
{
|
|||
|
|
/// <summary>
|
|||
|
|
/// Class used to represent a node in the tree.
|
|||
|
|
/// </summary>
|
|||
|
|
/// <remarks>
|
|||
|
|
/// There are three types of nodes:
|
|||
|
|
/// Concat nodes: height>0, left!=null, right!=null, contents==null
|
|||
|
|
/// Leaf nodes: height==0, left==null, right==null, contents!=null
|
|||
|
|
/// Function nodes: height==0, left==null, right==null, contents==null, are of type FunctionNode<T>
|
|||
|
|
/// </remarks>
|
|||
|
|
/// <typeparam name="T"></typeparam>
|
|||
|
|
internal class RopeNode<T>
|
|||
|
|
{
|
|||
|
|
internal const int NodeSize = 256;
|
|||
|
|
|
|||
|
|
internal static RopeNode<T> EmptyRopeNode { get; } = new RopeNode<T>(isShared: true) { Contents = new T[NodeSize] };
|
|||
|
|
|
|||
|
|
// Fields for pointers to sub-nodes. Only non-null for concat nodes (height>=1)
|
|||
|
|
|
|||
|
|
internal RopeNode<T> Left { get; set; }
|
|||
|
|
|
|||
|
|
internal RopeNode<T> Right { get; set; }
|
|||
|
|
|
|||
|
|
// specifies whether this node is shared between multiple ropes
|
|||
|
|
// the total length of all text in this subtree
|
|||
|
|
private volatile bool _isShared;
|
|||
|
|
|
|||
|
|
internal int Length;
|
|||
|
|
// the height of this subtree: 0 for leaf nodes; 1+max(left.height,right.height) for concat nodes
|
|||
|
|
internal byte Height;
|
|||
|
|
|
|||
|
|
// The character data. Only non-null for leaf nodes (height=0) that aren't function nodes.
|
|||
|
|
internal T[] Contents { get; set; }
|
|||
|
|
|
|||
|
|
internal RopeNode() { }
|
|||
|
|
|
|||
|
|
protected RopeNode(bool isShared)
|
|||
|
|
{
|
|||
|
|
_isShared = isShared;
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
internal int Balance => Right.Height - Left.Height;
|
|||
|
|
|
|||
|
|
[Conditional("DATACONSISTENCYTEST")]
|
|||
|
|
internal void CheckInvariants()
|
|||
|
|
{
|
|||
|
|
if (Height == 0)
|
|||
|
|
{
|
|||
|
|
Debug.Assert(Left == null && Right == null);
|
|||
|
|
if (Contents == null)
|
|||
|
|
{
|
|||
|
|
Debug.Assert(this is FunctionNode<T>);
|
|||
|
|
Debug.Assert(Length > 0);
|
|||
|
|
Debug.Assert(_isShared);
|
|||
|
|
}
|
|||
|
|
else
|
|||
|
|
{
|
|||
|
|
Debug.Assert(Contents != null && Contents.Length == NodeSize);
|
|||
|
|
Debug.Assert(Length >= 0 && Length <= NodeSize);
|
|||
|
|
}
|
|||
|
|
}
|
|||
|
|
else
|
|||
|
|
{
|
|||
|
|
Debug.Assert(Left != null && Right != null);
|
|||
|
|
Debug.Assert(Contents == null);
|
|||
|
|
Debug.Assert(Length == Left.Length + Right.Length);
|
|||
|
|
Debug.Assert(Height == 1 + Math.Max(Left.Height, Right.Height));
|
|||
|
|
Debug.Assert(Math.Abs(Balance) <= 1);
|
|||
|
|
|
|||
|
|
// this is an additional invariant that forces the tree to combine small leafs to prevent excessive memory usage:
|
|||
|
|
Debug.Assert(Length > NodeSize);
|
|||
|
|
// note that this invariant ensures that all nodes except for the empty rope's single node have at least length 1
|
|||
|
|
|
|||
|
|
if (_isShared)
|
|||
|
|
Debug.Assert(Left._isShared && Right._isShared);
|
|||
|
|
Left.CheckInvariants();
|
|||
|
|
Right.CheckInvariants();
|
|||
|
|
}
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
internal RopeNode<T> Clone()
|
|||
|
|
{
|
|||
|
|
if (Height == 0)
|
|||
|
|
{
|
|||
|
|
// If a function node needs cloning, we'll evaluate it.
|
|||
|
|
if (Contents == null)
|
|||
|
|
return GetContentNode().Clone();
|
|||
|
|
var newContents = new T[NodeSize];
|
|||
|
|
Contents.CopyTo(newContents, 0);
|
|||
|
|
return new RopeNode<T>
|
|||
|
|
{
|
|||
|
|
Length = Length,
|
|||
|
|
Contents = newContents
|
|||
|
|
};
|
|||
|
|
}
|
|||
|
|
return new RopeNode<T>
|
|||
|
|
{
|
|||
|
|
Left = Left,
|
|||
|
|
Right = Right,
|
|||
|
|
Length = Length,
|
|||
|
|
Height = Height
|
|||
|
|
};
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
internal RopeNode<T> CloneIfShared()
|
|||
|
|
{
|
|||
|
|
if (_isShared)
|
|||
|
|
return Clone();
|
|||
|
|
return this;
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
internal void Publish()
|
|||
|
|
{
|
|||
|
|
if (!_isShared)
|
|||
|
|
{
|
|||
|
|
Left?.Publish();
|
|||
|
|
Right?.Publish();
|
|||
|
|
// it's important that isShared=true is set at the end:
|
|||
|
|
// Publish() must not return until the whole subtree is marked as shared, even when
|
|||
|
|
// Publish() is called concurrently.
|
|||
|
|
_isShared = true;
|
|||
|
|
}
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
internal static RopeNode<T> CreateFromArray(T[] arr, int index, int length)
|
|||
|
|
{
|
|||
|
|
if (length == 0)
|
|||
|
|
{
|
|||
|
|
return EmptyRopeNode;
|
|||
|
|
}
|
|||
|
|
var node = CreateNodes(length);
|
|||
|
|
return node.StoreElements(0, arr, index, length);
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
internal static RopeNode<T> CreateNodes(int totalLength)
|
|||
|
|
{
|
|||
|
|
var leafCount = (totalLength + NodeSize - 1) / NodeSize;
|
|||
|
|
return CreateNodes(leafCount, totalLength);
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
private static RopeNode<T> CreateNodes(int leafCount, int totalLength)
|
|||
|
|
{
|
|||
|
|
Debug.Assert(leafCount > 0);
|
|||
|
|
Debug.Assert(totalLength > 0);
|
|||
|
|
var result = new RopeNode<T> { Length = totalLength };
|
|||
|
|
if (leafCount == 1)
|
|||
|
|
{
|
|||
|
|
result.Contents = new T[NodeSize];
|
|||
|
|
}
|
|||
|
|
else
|
|||
|
|
{
|
|||
|
|
var rightSide = leafCount / 2;
|
|||
|
|
var leftSide = leafCount - rightSide;
|
|||
|
|
var leftLength = leftSide * NodeSize;
|
|||
|
|
result.Left = CreateNodes(leftSide, leftLength);
|
|||
|
|
result.Right = CreateNodes(rightSide, totalLength - leftLength);
|
|||
|
|
result.Height = (byte)(1 + Math.Max(result.Left.Height, result.Right.Height));
|
|||
|
|
}
|
|||
|
|
return result;
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
/// <summary>
|
|||
|
|
/// Balances this node and recomputes the 'height' field.
|
|||
|
|
/// This method assumes that the children of this node are already balanced and have an up-to-date 'height' value.
|
|||
|
|
/// </summary>
|
|||
|
|
internal void Rebalance()
|
|||
|
|
{
|
|||
|
|
// Rebalance() shouldn't be called on shared nodes - it's only called after modifications!
|
|||
|
|
Debug.Assert(!_isShared);
|
|||
|
|
// leaf nodes are always balanced (we don't use 'height' to detect leaf nodes here
|
|||
|
|
// because Balance is supposed to recompute the height).
|
|||
|
|
if (Left == null)
|
|||
|
|
return;
|
|||
|
|
|
|||
|
|
// ensure we didn't miss a MergeIfPossible step
|
|||
|
|
Debug.Assert(Length > NodeSize);
|
|||
|
|
|
|||
|
|
// We need to loop until it's balanced. Rotations might cause two small leaves to combine to a larger one,
|
|||
|
|
// which changes the height and might mean we need additional balancing steps.
|
|||
|
|
while (Math.Abs(Balance) > 1)
|
|||
|
|
{
|
|||
|
|
// AVL balancing
|
|||
|
|
// note: because we don't care about the identity of concat nodes, this works a little different than usual
|
|||
|
|
// tree rotations: in our implementation, the "this" node will stay at the top, only its children are rearranged
|
|||
|
|
if (Balance > 1)
|
|||
|
|
{
|
|||
|
|
if (Right.Balance < 0)
|
|||
|
|
{
|
|||
|
|
Right = Right.CloneIfShared();
|
|||
|
|
Right.RotateRight();
|
|||
|
|
}
|
|||
|
|
RotateLeft();
|
|||
|
|
// If 'this' was unbalanced by more than 2, we've shifted some of the inbalance to the left node; so rebalance that.
|
|||
|
|
Left.Rebalance();
|
|||
|
|
}
|
|||
|
|
else if (Balance < -1)
|
|||
|
|
{
|
|||
|
|
if (Left.Balance > 0)
|
|||
|
|
{
|
|||
|
|
Left = Left.CloneIfShared();
|
|||
|
|
Left.RotateLeft();
|
|||
|
|
}
|
|||
|
|
RotateRight();
|
|||
|
|
// If 'this' was unbalanced by more than 2, we've shifted some of the inbalance to the right node; so rebalance that.
|
|||
|
|
Right.Rebalance();
|
|||
|
|
}
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
Debug.Assert(Math.Abs(Balance) <= 1);
|
|||
|
|
Height = (byte)(1 + Math.Max(Left.Height, Right.Height));
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
private void RotateLeft()
|
|||
|
|
{
|
|||
|
|
Debug.Assert(!_isShared);
|
|||
|
|
|
|||
|
|
/* Rotate tree to the left
|
|||
|
|
*
|
|||
|
|
* this this
|
|||
|
|
* / \ / \
|
|||
|
|
* A right ===> left C
|
|||
|
|
* / \ / \
|
|||
|
|
* B C A B
|
|||
|
|
*/
|
|||
|
|
var a = Left;
|
|||
|
|
var b = Right.Left;
|
|||
|
|
var c = Right.Right;
|
|||
|
|
// reuse right concat node, if possible
|
|||
|
|
Left = Right._isShared ? new RopeNode<T>() : Right;
|
|||
|
|
Left.Left = a;
|
|||
|
|
Left.Right = b;
|
|||
|
|
Left.Length = a.Length + b.Length;
|
|||
|
|
Left.Height = (byte)(1 + Math.Max(a.Height, b.Height));
|
|||
|
|
Right = c;
|
|||
|
|
|
|||
|
|
Left.MergeIfPossible();
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
private void RotateRight()
|
|||
|
|
{
|
|||
|
|
Debug.Assert(!_isShared);
|
|||
|
|
|
|||
|
|
/* Rotate tree to the right
|
|||
|
|
*
|
|||
|
|
* this this
|
|||
|
|
* / \ / \
|
|||
|
|
* left C ===> A right
|
|||
|
|
* / \ / \
|
|||
|
|
* A B B C
|
|||
|
|
*/
|
|||
|
|
var a = Left.Left;
|
|||
|
|
var b = Left.Right;
|
|||
|
|
var c = Right;
|
|||
|
|
// reuse left concat node, if possible
|
|||
|
|
Right = Left._isShared ? new RopeNode<T>() : Left;
|
|||
|
|
Right.Left = b;
|
|||
|
|
Right.Right = c;
|
|||
|
|
Right.Length = b.Length + c.Length;
|
|||
|
|
Right.Height = (byte)(1 + Math.Max(b.Height, c.Height));
|
|||
|
|
Left = a;
|
|||
|
|
|
|||
|
|
Right.MergeIfPossible();
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
private void MergeIfPossible()
|
|||
|
|
{
|
|||
|
|
Debug.Assert(!_isShared);
|
|||
|
|
|
|||
|
|
if (Length <= NodeSize)
|
|||
|
|
{
|
|||
|
|
// Convert this concat node to leaf node.
|
|||
|
|
// We know left and right cannot be concat nodes (they would have merged already),
|
|||
|
|
// but they could be function nodes.
|
|||
|
|
Height = 0;
|
|||
|
|
var lengthOnLeftSide = Left.Length;
|
|||
|
|
if (Left._isShared)
|
|||
|
|
{
|
|||
|
|
Contents = new T[NodeSize];
|
|||
|
|
Left.CopyTo(0, Contents, 0, lengthOnLeftSide);
|
|||
|
|
}
|
|||
|
|
else
|
|||
|
|
{
|
|||
|
|
// must be a leaf node: function nodes are always marked shared
|
|||
|
|
Debug.Assert(Left.Contents != null);
|
|||
|
|
// steal buffer from left side
|
|||
|
|
Contents = Left.Contents;
|
|||
|
|
#if DEBUG
|
|||
|
|
// In debug builds, explicitly mark left node as 'damaged' - but no one else should be using it
|
|||
|
|
// because it's not shared.
|
|||
|
|
Left.Contents = Array.Empty<T>();
|
|||
|
|
#endif
|
|||
|
|
}
|
|||
|
|
Left = null;
|
|||
|
|
Right.CopyTo(0, Contents, lengthOnLeftSide, Right.Length);
|
|||
|
|
Right = null;
|
|||
|
|
}
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
/// <summary>
|
|||
|
|
/// Copies from the array to this node.
|
|||
|
|
/// </summary>
|
|||
|
|
internal RopeNode<T> StoreElements(int index, T[] array, int arrayIndex, int count)
|
|||
|
|
{
|
|||
|
|
var result = CloneIfShared();
|
|||
|
|
// result cannot be function node after a call to Clone()
|
|||
|
|
if (result.Height == 0)
|
|||
|
|
{
|
|||
|
|
// leaf node:
|
|||
|
|
Array.Copy(array, arrayIndex, result.Contents, index, count);
|
|||
|
|
}
|
|||
|
|
else
|
|||
|
|
{
|
|||
|
|
// concat node:
|
|||
|
|
if (index + count <= result.Left.Length)
|
|||
|
|
{
|
|||
|
|
result.Left = result.Left.StoreElements(index, array, arrayIndex, count);
|
|||
|
|
}
|
|||
|
|
else if (index >= Left.Length)
|
|||
|
|
{
|
|||
|
|
result.Right = result.Right.StoreElements(index - result.Left.Length, array, arrayIndex, count);
|
|||
|
|
}
|
|||
|
|
else
|
|||
|
|
{
|
|||
|
|
var amountInLeft = result.Left.Length - index;
|
|||
|
|
result.Left = result.Left.StoreElements(index, array, arrayIndex, amountInLeft);
|
|||
|
|
result.Right = result.Right.StoreElements(0, array, arrayIndex + amountInLeft, count - amountInLeft);
|
|||
|
|
}
|
|||
|
|
result.Rebalance(); // tree layout might have changed if function nodes were replaced with their content
|
|||
|
|
}
|
|||
|
|
return result;
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
/// <summary>
|
|||
|
|
/// Copies from this node to the array.
|
|||
|
|
/// </summary>
|
|||
|
|
internal void CopyTo(int index, T[] array, int arrayIndex, int count)
|
|||
|
|
{
|
|||
|
|
if (Height == 0)
|
|||
|
|
{
|
|||
|
|
if (Contents == null)
|
|||
|
|
{
|
|||
|
|
// function node
|
|||
|
|
GetContentNode().CopyTo(index, array, arrayIndex, count);
|
|||
|
|
}
|
|||
|
|
else
|
|||
|
|
{
|
|||
|
|
// leaf node
|
|||
|
|
Array.Copy(Contents, index, array, arrayIndex, count);
|
|||
|
|
}
|
|||
|
|
}
|
|||
|
|
else
|
|||
|
|
{
|
|||
|
|
// concat node
|
|||
|
|
if (index + count <= Left.Length)
|
|||
|
|
{
|
|||
|
|
Left.CopyTo(index, array, arrayIndex, count);
|
|||
|
|
}
|
|||
|
|
else if (index >= Left.Length)
|
|||
|
|
{
|
|||
|
|
Right.CopyTo(index - Left.Length, array, arrayIndex, count);
|
|||
|
|
}
|
|||
|
|
else
|
|||
|
|
{
|
|||
|
|
var amountInLeft = Left.Length - index;
|
|||
|
|
Left.CopyTo(index, array, arrayIndex, amountInLeft);
|
|||
|
|
Right.CopyTo(0, array, arrayIndex + amountInLeft, count - amountInLeft);
|
|||
|
|
}
|
|||
|
|
}
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
internal RopeNode<T> SetElement(int offset, T value)
|
|||
|
|
{
|
|||
|
|
var result = CloneIfShared();
|
|||
|
|
// result of CloneIfShared() is leaf or concat node
|
|||
|
|
if (result.Height == 0)
|
|||
|
|
{
|
|||
|
|
result.Contents[offset] = value;
|
|||
|
|
}
|
|||
|
|
else
|
|||
|
|
{
|
|||
|
|
if (offset < result.Left.Length)
|
|||
|
|
{
|
|||
|
|
result.Left = result.Left.SetElement(offset, value);
|
|||
|
|
}
|
|||
|
|
else
|
|||
|
|
{
|
|||
|
|
result.Right = result.Right.SetElement(offset - result.Left.Length, value);
|
|||
|
|
}
|
|||
|
|
result.Rebalance(); // tree layout might have changed if function nodes were replaced with their content
|
|||
|
|
}
|
|||
|
|
return result;
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
internal static RopeNode<T> Concat(RopeNode<T> left, RopeNode<T> right)
|
|||
|
|
{
|
|||
|
|
if (left.Length == 0)
|
|||
|
|
return right;
|
|||
|
|
if (right.Length == 0)
|
|||
|
|
return left;
|
|||
|
|
|
|||
|
|
if (left.Length + right.Length <= NodeSize)
|
|||
|
|
{
|
|||
|
|
left = left.CloneIfShared();
|
|||
|
|
// left is guaranteed to be leaf node after cloning:
|
|||
|
|
// - it cannot be function node (due to clone)
|
|||
|
|
// - it cannot be concat node (too short)
|
|||
|
|
right.CopyTo(0, left.Contents, left.Length, right.Length);
|
|||
|
|
left.Length += right.Length;
|
|||
|
|
return left;
|
|||
|
|
}
|
|||
|
|
var concatNode = new RopeNode<T>
|
|||
|
|
{
|
|||
|
|
Left = left,
|
|||
|
|
Right = right,
|
|||
|
|
Length = left.Length + right.Length
|
|||
|
|
};
|
|||
|
|
concatNode.Rebalance();
|
|||
|
|
return concatNode;
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
/// <summary>
|
|||
|
|
/// Splits this leaf node at offset and returns a new node with the part of the text after offset.
|
|||
|
|
/// </summary>
|
|||
|
|
private RopeNode<T> SplitAfter(int offset)
|
|||
|
|
{
|
|||
|
|
Debug.Assert(!_isShared && Height == 0 && Contents != null);
|
|||
|
|
var newPart = new RopeNode<T>
|
|||
|
|
{
|
|||
|
|
Contents = new T[NodeSize],
|
|||
|
|
Length = Length - offset
|
|||
|
|
};
|
|||
|
|
Array.Copy(Contents, offset, newPart.Contents, 0, newPart.Length);
|
|||
|
|
Length = offset;
|
|||
|
|
return newPart;
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
internal RopeNode<T> Insert(int offset, RopeNode<T> newElements)
|
|||
|
|
{
|
|||
|
|
if (offset == 0)
|
|||
|
|
{
|
|||
|
|
return Concat(newElements, this);
|
|||
|
|
}
|
|||
|
|
if (offset == Length)
|
|||
|
|
{
|
|||
|
|
return Concat(this, newElements);
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
// first clone this node (converts function nodes to leaf or concat nodes)
|
|||
|
|
var result = CloneIfShared();
|
|||
|
|
if (result.Height == 0)
|
|||
|
|
{
|
|||
|
|
// leaf node: we'll need to split this node
|
|||
|
|
var left = result;
|
|||
|
|
var right = left.SplitAfter(offset);
|
|||
|
|
return Concat(Concat(left, newElements), right);
|
|||
|
|
}
|
|||
|
|
// concat node
|
|||
|
|
if (offset < result.Left.Length)
|
|||
|
|
{
|
|||
|
|
result.Left = result.Left.Insert(offset, newElements);
|
|||
|
|
}
|
|||
|
|
else
|
|||
|
|
{
|
|||
|
|
result.Right = result.Right.Insert(offset - result.Left.Length, newElements);
|
|||
|
|
}
|
|||
|
|
result.Length += newElements.Length;
|
|||
|
|
result.Rebalance();
|
|||
|
|
return result;
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
internal RopeNode<T> Insert(int offset, T[] array, int arrayIndex, int count)
|
|||
|
|
{
|
|||
|
|
Debug.Assert(count > 0);
|
|||
|
|
|
|||
|
|
if (Length + count < RopeNode<char>.NodeSize)
|
|||
|
|
{
|
|||
|
|
var result = CloneIfShared();
|
|||
|
|
// result must be leaf node (Clone never returns function nodes, too short for concat node)
|
|||
|
|
var lengthAfterOffset = result.Length - offset;
|
|||
|
|
var resultContents = result.Contents;
|
|||
|
|
for (var i = lengthAfterOffset; i >= 0; i--)
|
|||
|
|
{
|
|||
|
|
resultContents[i + offset + count] = resultContents[i + offset];
|
|||
|
|
}
|
|||
|
|
Array.Copy(array, arrayIndex, resultContents, offset, count);
|
|||
|
|
result.Length += count;
|
|||
|
|
return result;
|
|||
|
|
}
|
|||
|
|
if (Height == 0)
|
|||
|
|
{
|
|||
|
|
// TODO: implement this more efficiently?
|
|||
|
|
return Insert(offset, CreateFromArray(array, arrayIndex, count));
|
|||
|
|
}
|
|||
|
|
{
|
|||
|
|
// this is a concat node (both leafs and function nodes are handled by the case above)
|
|||
|
|
var result = CloneIfShared();
|
|||
|
|
if (offset < result.Left.Length)
|
|||
|
|
{
|
|||
|
|
result.Left = result.Left.Insert(offset, array, arrayIndex, count);
|
|||
|
|
}
|
|||
|
|
else
|
|||
|
|
{
|
|||
|
|
result.Right = result.Right.Insert(offset - result.Left.Length, array, arrayIndex, count);
|
|||
|
|
}
|
|||
|
|
result.Length += count;
|
|||
|
|
result.Rebalance();
|
|||
|
|
return result;
|
|||
|
|
}
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
internal RopeNode<T> RemoveRange(int index, int count)
|
|||
|
|
{
|
|||
|
|
Debug.Assert(count > 0);
|
|||
|
|
|
|||
|
|
// produce empty node when one node is deleted completely
|
|||
|
|
if (index == 0 && count == Length)
|
|||
|
|
return EmptyRopeNode;
|
|||
|
|
|
|||
|
|
var endIndex = index + count;
|
|||
|
|
var result = CloneIfShared(); // convert function node to concat/leaf
|
|||
|
|
if (result.Height == 0)
|
|||
|
|
{
|
|||
|
|
var remainingAfterEnd = result.Length - endIndex;
|
|||
|
|
for (var i = 0; i < remainingAfterEnd; i++)
|
|||
|
|
{
|
|||
|
|
result.Contents[index + i] = result.Contents[endIndex + i];
|
|||
|
|
}
|
|||
|
|
result.Length -= count;
|
|||
|
|
}
|
|||
|
|
else
|
|||
|
|
{
|
|||
|
|
if (endIndex <= result.Left.Length)
|
|||
|
|
{
|
|||
|
|
// deletion is only within the left part
|
|||
|
|
result.Left = result.Left.RemoveRange(index, count);
|
|||
|
|
}
|
|||
|
|
else if (index >= result.Left.Length)
|
|||
|
|
{
|
|||
|
|
// deletion is only within the right part
|
|||
|
|
result.Right = result.Right.RemoveRange(index - result.Left.Length, count);
|
|||
|
|
}
|
|||
|
|
else
|
|||
|
|
{
|
|||
|
|
// deletion overlaps both parts
|
|||
|
|
var deletionAmountOnLeftSide = result.Left.Length - index;
|
|||
|
|
result.Left = result.Left.RemoveRange(index, deletionAmountOnLeftSide);
|
|||
|
|
result.Right = result.Right.RemoveRange(0, count - deletionAmountOnLeftSide);
|
|||
|
|
}
|
|||
|
|
// The deletion might have introduced empty nodes. Those must be removed.
|
|||
|
|
if (result.Left.Length == 0)
|
|||
|
|
return result.Right;
|
|||
|
|
if (result.Right.Length == 0)
|
|||
|
|
return result.Left;
|
|||
|
|
|
|||
|
|
result.Length -= count;
|
|||
|
|
result.MergeIfPossible();
|
|||
|
|
result.Rebalance();
|
|||
|
|
}
|
|||
|
|
return result;
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
#region Debug Output
|
|||
|
|
#if DEBUG
|
|||
|
|
internal virtual void AppendTreeToString(StringBuilder b, int indent)
|
|||
|
|
{
|
|||
|
|
b.AppendLine(ToString());
|
|||
|
|
indent += 2;
|
|||
|
|
if (Left != null)
|
|||
|
|
{
|
|||
|
|
b.Append(' ', indent);
|
|||
|
|
b.Append("L: ");
|
|||
|
|
Left.AppendTreeToString(b, indent);
|
|||
|
|
}
|
|||
|
|
if (Right != null)
|
|||
|
|
{
|
|||
|
|
b.Append(' ', indent);
|
|||
|
|
b.Append("R: ");
|
|||
|
|
Right.AppendTreeToString(b, indent);
|
|||
|
|
}
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
public override string ToString()
|
|||
|
|
{
|
|||
|
|
if (Contents != null)
|
|||
|
|
{
|
|||
|
|
#pragma warning disable IDE0019 // Use pattern matching
|
|||
|
|
var charContents = Contents as char[];
|
|||
|
|
#pragma warning restore IDE0019 // Use pattern matching
|
|||
|
|
if (charContents != null)
|
|||
|
|
return "[Leaf length=" + Length + ", isShared=" + _isShared + ", text=\"" + new string(charContents, 0, Length) + "\"]";
|
|||
|
|
return "[Leaf length=" + Length + ", isShared=" + _isShared + "\"]";
|
|||
|
|
}
|
|||
|
|
return "[Concat length=" + Length + ", isShared=" + _isShared + ", height=" + Height + ", Balance=" + Balance + "]";
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
internal string GetTreeAsString()
|
|||
|
|
{
|
|||
|
|
var b = new StringBuilder();
|
|||
|
|
AppendTreeToString(b, 0);
|
|||
|
|
return b.ToString();
|
|||
|
|
}
|
|||
|
|
#endif
|
|||
|
|
#endregion
|
|||
|
|
|
|||
|
|
/// <summary>
|
|||
|
|
/// Gets the root node of the subtree from a lazily evaluated function node.
|
|||
|
|
/// Such nodes are always marked as shared.
|
|||
|
|
/// GetContentNode() will return either a Concat or Leaf node, never another FunctionNode.
|
|||
|
|
/// </summary>
|
|||
|
|
internal virtual RopeNode<T> GetContentNode()
|
|||
|
|
{
|
|||
|
|
throw new InvalidOperationException("Called GetContentNode() on non-FunctionNode.");
|
|||
|
|
}
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
internal sealed class FunctionNode<T> : RopeNode<T>
|
|||
|
|
{
|
|||
|
|
private Func<Rope<T>> _initializer;
|
|||
|
|
private RopeNode<T> _cachedResults;
|
|||
|
|
|
|||
|
|
internal FunctionNode(int length, Func<Rope<T>> initializer) : base(isShared: true)
|
|||
|
|
{
|
|||
|
|
Debug.Assert(length > 0);
|
|||
|
|
Debug.Assert(initializer != null);
|
|||
|
|
|
|||
|
|
Length = length;
|
|||
|
|
_initializer = initializer;
|
|||
|
|
// Function nodes are immediately shared, but cannot be cloned.
|
|||
|
|
// This ensures we evaluate every initializer only once.
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
internal override RopeNode<T> GetContentNode()
|
|||
|
|
{
|
|||
|
|
lock (this)
|
|||
|
|
{
|
|||
|
|
if (_cachedResults == null)
|
|||
|
|
{
|
|||
|
|
if (_initializer == null)
|
|||
|
|
throw new InvalidOperationException("Trying to load this node recursively; or: a previous call to a rope initializer failed.");
|
|||
|
|
var initializerCopy = _initializer;
|
|||
|
|
_initializer = null;
|
|||
|
|
var resultRope = initializerCopy();
|
|||
|
|
if (resultRope == null)
|
|||
|
|
throw new InvalidOperationException("Rope initializer returned null.");
|
|||
|
|
var resultNode = resultRope.Root;
|
|||
|
|
resultNode.Publish(); // result is shared between returned rope and the rope containing this function node
|
|||
|
|
if (resultNode.Length != Length)
|
|||
|
|
throw new InvalidOperationException("Rope initializer returned rope with incorrect length.");
|
|||
|
|
if (resultNode.Height == 0 && resultNode.Contents == null)
|
|||
|
|
{
|
|||
|
|
// ResultNode is another function node.
|
|||
|
|
// We want to guarantee that GetContentNode() never returns function nodes, so we have to
|
|||
|
|
// go down further in the tree.
|
|||
|
|
_cachedResults = resultNode.GetContentNode();
|
|||
|
|
}
|
|||
|
|
else
|
|||
|
|
{
|
|||
|
|
_cachedResults = resultNode;
|
|||
|
|
}
|
|||
|
|
}
|
|||
|
|
return _cachedResults;
|
|||
|
|
}
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
#if DEBUG
|
|||
|
|
internal override void AppendTreeToString(StringBuilder b, int indent)
|
|||
|
|
{
|
|||
|
|
RopeNode<T> resultNode;
|
|||
|
|
lock (this)
|
|||
|
|
{
|
|||
|
|
b.AppendLine(ToString());
|
|||
|
|
resultNode = _cachedResults;
|
|||
|
|
}
|
|||
|
|
indent += 2;
|
|||
|
|
if (resultNode != null)
|
|||
|
|
{
|
|||
|
|
b.Append(' ', indent);
|
|||
|
|
b.Append("C: ");
|
|||
|
|
resultNode.AppendTreeToString(b, indent);
|
|||
|
|
}
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
public override string ToString()
|
|||
|
|
{
|
|||
|
|
return "[FunctionNode length=" + Length + " initializerRan=" + (_initializer == null) + "]";
|
|||
|
|
}
|
|||
|
|
#endif
|
|||
|
|
}
|
|||
|
|
}
|