From 080f1697e97e13461ec6df4d31c8924d01257a1b Mon Sep 17 00:00:00 2001 From: Roy Ben Shabat Date: Tue, 9 Apr 2019 01:47:48 +0300 Subject: MERGE --- .../Document/DocumentLineTree.cs | 712 +++++++++++++++++++++ 1 file changed, 712 insertions(+) create mode 100644 Software/Visual_Studio/Scripting/Tango.Scripting.Editors/Document/DocumentLineTree.cs (limited to 'Software/Visual_Studio/Scripting/Tango.Scripting.Editors/Document/DocumentLineTree.cs') diff --git a/Software/Visual_Studio/Scripting/Tango.Scripting.Editors/Document/DocumentLineTree.cs b/Software/Visual_Studio/Scripting/Tango.Scripting.Editors/Document/DocumentLineTree.cs new file mode 100644 index 000000000..927dc3e01 --- /dev/null +++ b/Software/Visual_Studio/Scripting/Tango.Scripting.Editors/Document/DocumentLineTree.cs @@ -0,0 +1,712 @@ +// Copyright (c) AlphaSierraPapa for the SharpDevelop Team (for details please see \doc\copyright.txt) +// This code is distributed under the GNU LGPL (for details please see \doc\license.txt) + +using System; +using System.Collections.Generic; +using System.Diagnostics; +using System.Text; + +namespace Tango.Scripting.Editors.Document +{ + using LineNode = DocumentLine; + + /// + /// Data structure for efficient management of the document lines (most operations are O(lg n)). + /// This implements an augmented red-black tree. + /// See for the augmented data. + /// + /// NOTE: The tree is never empty, initially it contains an empty line. + /// + sealed class DocumentLineTree : IList + { + #region Constructor + readonly TextDocument document; + LineNode root; + + public DocumentLineTree(TextDocument document) + { + this.document = document; + + DocumentLine emptyLine = new DocumentLine(document); + root = emptyLine.InitLineNode(); + } + #endregion + + #region Rotation callbacks + internal static void UpdateAfterChildrenChange(LineNode node) + { + int totalCount = 1; + int totalLength = node.TotalLength; + if (node.left != null) { + totalCount += node.left.nodeTotalCount; + totalLength += node.left.nodeTotalLength; + } + if (node.right != null) { + totalCount += node.right.nodeTotalCount; + totalLength += node.right.nodeTotalLength; + } + if (totalCount != node.nodeTotalCount + || totalLength != node.nodeTotalLength) + { + node.nodeTotalCount = totalCount; + node.nodeTotalLength = totalLength; + if (node.parent != null) UpdateAfterChildrenChange(node.parent); + } + } + + static void UpdateAfterRotateLeft(LineNode node) + { + UpdateAfterChildrenChange(node); + + // not required: rotations only happen on insertions/deletions + // -> totalCount changes -> the parent is always updated + //UpdateAfterChildrenChange(node.parent); + } + + static void UpdateAfterRotateRight(LineNode node) + { + UpdateAfterChildrenChange(node); + + // not required: rotations only happen on insertions/deletions + // -> totalCount changes -> the parent is always updated + //UpdateAfterChildrenChange(node.parent); + } + #endregion + + #region RebuildDocument + /// + /// Rebuild the tree, in O(n). + /// + public void RebuildTree(List documentLines) + { + LineNode[] nodes = new LineNode[documentLines.Count]; + for (int i = 0; i < documentLines.Count; i++) { + DocumentLine ls = documentLines[i]; + LineNode node = ls.InitLineNode(); + nodes[i] = node; + } + Debug.Assert(nodes.Length > 0); + // now build the corresponding balanced tree + int height = GetTreeHeight(nodes.Length); + Debug.WriteLine("DocumentLineTree will have height: " + height); + root = BuildTree(nodes, 0, nodes.Length, height); + root.color = BLACK; + #if DEBUG + CheckProperties(); + #endif + } + + internal static int GetTreeHeight(int size) + { + if (size == 0) + return 0; + else + return GetTreeHeight(size / 2) + 1; + } + + /// + /// build a tree from a list of nodes + /// + LineNode BuildTree(LineNode[] nodes, int start, int end, int subtreeHeight) + { + Debug.Assert(start <= end); + if (start == end) { + return null; + } + int middle = (start + end) / 2; + LineNode node = nodes[middle]; + node.left = BuildTree(nodes, start, middle, subtreeHeight - 1); + node.right = BuildTree(nodes, middle + 1, end, subtreeHeight - 1); + if (node.left != null) node.left.parent = node; + if (node.right != null) node.right.parent = node; + if (subtreeHeight == 1) + node.color = RED; + UpdateAfterChildrenChange(node); + return node; + } + #endregion + + #region GetNodeBy... / Get...FromNode + LineNode GetNodeByIndex(int index) + { + Debug.Assert(index >= 0); + Debug.Assert(index < root.nodeTotalCount); + LineNode node = root; + while (true) { + if (node.left != null && index < node.left.nodeTotalCount) { + node = node.left; + } else { + if (node.left != null) { + index -= node.left.nodeTotalCount; + } + if (index == 0) + return node; + index--; + node = node.right; + } + } + } + + internal static int GetIndexFromNode(LineNode node) + { + int index = (node.left != null) ? node.left.nodeTotalCount : 0; + while (node.parent != null) { + if (node == node.parent.right) { + if (node.parent.left != null) + index += node.parent.left.nodeTotalCount; + index++; + } + node = node.parent; + } + return index; + } + + LineNode GetNodeByOffset(int offset) + { + Debug.Assert(offset >= 0); + Debug.Assert(offset <= root.nodeTotalLength); + if (offset == root.nodeTotalLength) { + return root.RightMost; + } + LineNode node = root; + while (true) { + if (node.left != null && offset < node.left.nodeTotalLength) { + node = node.left; + } else { + if (node.left != null) { + offset -= node.left.nodeTotalLength; + } + offset -= node.TotalLength; + if (offset < 0) + return node; + node = node.right; + } + } + } + + internal static int GetOffsetFromNode(LineNode node) + { + int offset = (node.left != null) ? node.left.nodeTotalLength : 0; + while (node.parent != null) { + if (node == node.parent.right) { + if (node.parent.left != null) + offset += node.parent.left.nodeTotalLength; + offset += node.parent.TotalLength; + } + node = node.parent; + } + return offset; + } + #endregion + + #region GetLineBy + public DocumentLine GetByNumber(int number) + { + return GetNodeByIndex(number - 1); + } + + public DocumentLine GetByOffset(int offset) + { + return GetNodeByOffset(offset); + } + #endregion + + #region LineCount + public int LineCount { + get { + return root.nodeTotalCount; + } + } + #endregion + + #region CheckProperties + #if DEBUG + [Conditional("DATACONSISTENCYTEST")] + internal void CheckProperties() + { + Debug.Assert(root.nodeTotalLength == document.TextLength); + CheckProperties(root); + + // check red-black property: + int blackCount = -1; + CheckNodeProperties(root, null, RED, 0, ref blackCount); + } + + void CheckProperties(LineNode node) + { + int totalCount = 1; + int totalLength = node.TotalLength; + if (node.left != null) { + CheckProperties(node.left); + totalCount += node.left.nodeTotalCount; + totalLength += node.left.nodeTotalLength; + } + if (node.right != null) { + CheckProperties(node.right); + totalCount += node.right.nodeTotalCount; + totalLength += node.right.nodeTotalLength; + } + Debug.Assert(node.nodeTotalCount == totalCount); + Debug.Assert(node.nodeTotalLength == totalLength); + } + + /* + 1. A node is either red or black. + 2. The root is black. + 3. All leaves are black. (The leaves are the NIL children.) + 4. Both children of every red node are black. (So every red node must have a black parent.) + 5. Every simple path from a node to a descendant leaf contains the same number of black nodes. (Not counting the leaf node.) + */ + void CheckNodeProperties(LineNode node, LineNode parentNode, bool parentColor, int blackCount, ref int expectedBlackCount) + { + if (node == null) return; + + Debug.Assert(node.parent == parentNode); + + if (parentColor == RED) { + Debug.Assert(node.color == BLACK); + } + if (node.color == BLACK) { + blackCount++; + } + if (node.left == null && node.right == null) { + // node is a leaf node: + if (expectedBlackCount == -1) + expectedBlackCount = blackCount; + else + Debug.Assert(expectedBlackCount == blackCount); + } + CheckNodeProperties(node.left, node, node.color, blackCount, ref expectedBlackCount); + CheckNodeProperties(node.right, node, node.color, blackCount, ref expectedBlackCount); + } + + [System.Diagnostics.CodeAnalysis.SuppressMessage("Microsoft.Performance", "CA1811:AvoidUncalledPrivateCode")] + public string GetTreeAsString() + { + StringBuilder b = new StringBuilder(); + AppendTreeToString(root, b, 0); + return b.ToString(); + } + + static void AppendTreeToString(LineNode node, StringBuilder b, int indent) + { + if (node.color == RED) + b.Append("RED "); + else + b.Append("BLACK "); + b.AppendLine(node.ToString()); + indent += 2; + if (node.left != null) { + b.Append(' ', indent); + b.Append("L: "); + AppendTreeToString(node.left, b, indent); + } + if (node.right != null) { + b.Append(' ', indent); + b.Append("R: "); + AppendTreeToString(node.right, b, indent); + } + } + #endif + #endregion + + #region Insert/Remove lines + public void RemoveLine(DocumentLine line) + { + RemoveNode(line); + line.isDeleted = true; + } + + public DocumentLine InsertLineAfter(DocumentLine line, int totalLength) + { + DocumentLine newLine = new DocumentLine(document); + newLine.TotalLength = totalLength; + + InsertAfter(line, newLine); + return newLine; + } + + void InsertAfter(LineNode node, DocumentLine newLine) + { + LineNode newNode = newLine.InitLineNode(); + if (node.right == null) { + InsertAsRight(node, newNode); + } else { + InsertAsLeft(node.right.LeftMost, newNode); + } + } + #endregion + + #region Red/Black Tree + internal const bool RED = true; + internal const bool BLACK = false; + + void InsertAsLeft(LineNode parentNode, LineNode newNode) + { + Debug.Assert(parentNode.left == null); + parentNode.left = newNode; + newNode.parent = parentNode; + newNode.color = RED; + UpdateAfterChildrenChange(parentNode); + FixTreeOnInsert(newNode); + } + + void InsertAsRight(LineNode parentNode, LineNode newNode) + { + Debug.Assert(parentNode.right == null); + parentNode.right = newNode; + newNode.parent = parentNode; + newNode.color = RED; + UpdateAfterChildrenChange(parentNode); + FixTreeOnInsert(newNode); + } + + void FixTreeOnInsert(LineNode node) + { + Debug.Assert(node != null); + Debug.Assert(node.color == RED); + Debug.Assert(node.left == null || node.left.color == BLACK); + Debug.Assert(node.right == null || node.right.color == BLACK); + + LineNode parentNode = node.parent; + if (parentNode == null) { + // we inserted in the root -> the node must be black + // since this is a root node, making the node black increments the number of black nodes + // on all paths by one, so it is still the same for all paths. + node.color = BLACK; + return; + } + if (parentNode.color == BLACK) { + // if the parent node where we inserted was black, our red node is placed correctly. + // since we inserted a red node, the number of black nodes on each path is unchanged + // -> the tree is still balanced + return; + } + // parentNode is red, so there is a conflict here! + + // because the root is black, parentNode is not the root -> there is a grandparent node + LineNode grandparentNode = parentNode.parent; + LineNode uncleNode = Sibling(parentNode); + if (uncleNode != null && uncleNode.color == RED) { + parentNode.color = BLACK; + uncleNode.color = BLACK; + grandparentNode.color = RED; + FixTreeOnInsert(grandparentNode); + return; + } + // now we know: parent is red but uncle is black + // First rotation: + if (node == parentNode.right && parentNode == grandparentNode.left) { + RotateLeft(parentNode); + node = node.left; + } else if (node == parentNode.left && parentNode == grandparentNode.right) { + RotateRight(parentNode); + node = node.right; + } + // because node might have changed, reassign variables: + parentNode = node.parent; + grandparentNode = parentNode.parent; + + // Now recolor a bit: + parentNode.color = BLACK; + grandparentNode.color = RED; + // Second rotation: + if (node == parentNode.left && parentNode == grandparentNode.left) { + RotateRight(grandparentNode); + } else { + // because of the first rotation, this is guaranteed: + Debug.Assert(node == parentNode.right && parentNode == grandparentNode.right); + RotateLeft(grandparentNode); + } + } + + void RemoveNode(LineNode removedNode) + { + if (removedNode.left != null && removedNode.right != null) { + // replace removedNode with it's in-order successor + + LineNode leftMost = removedNode.right.LeftMost; + RemoveNode(leftMost); // remove leftMost from its current location + + // and overwrite the removedNode with it + ReplaceNode(removedNode, leftMost); + leftMost.left = removedNode.left; + if (leftMost.left != null) leftMost.left.parent = leftMost; + leftMost.right = removedNode.right; + if (leftMost.right != null) leftMost.right.parent = leftMost; + leftMost.color = removedNode.color; + + UpdateAfterChildrenChange(leftMost); + if (leftMost.parent != null) UpdateAfterChildrenChange(leftMost.parent); + return; + } + + // now either removedNode.left or removedNode.right is null + // get the remaining child + LineNode parentNode = removedNode.parent; + LineNode childNode = removedNode.left ?? removedNode.right; + ReplaceNode(removedNode, childNode); + if (parentNode != null) UpdateAfterChildrenChange(parentNode); + if (removedNode.color == BLACK) { + if (childNode != null && childNode.color == RED) { + childNode.color = BLACK; + } else { + FixTreeOnDelete(childNode, parentNode); + } + } + } + + void FixTreeOnDelete(LineNode node, LineNode parentNode) + { + Debug.Assert(node == null || node.parent == parentNode); + if (parentNode == null) + return; + + // warning: node may be null + LineNode sibling = Sibling(node, parentNode); + if (sibling.color == RED) { + parentNode.color = RED; + sibling.color = BLACK; + if (node == parentNode.left) { + RotateLeft(parentNode); + } else { + RotateRight(parentNode); + } + + sibling = Sibling(node, parentNode); // update value of sibling after rotation + } + + if (parentNode.color == BLACK + && sibling.color == BLACK + && GetColor(sibling.left) == BLACK + && GetColor(sibling.right) == BLACK) + { + sibling.color = RED; + FixTreeOnDelete(parentNode, parentNode.parent); + return; + } + + if (parentNode.color == RED + && sibling.color == BLACK + && GetColor(sibling.left) == BLACK + && GetColor(sibling.right) == BLACK) + { + sibling.color = RED; + parentNode.color = BLACK; + return; + } + + if (node == parentNode.left && + sibling.color == BLACK && + GetColor(sibling.left) == RED && + GetColor(sibling.right) == BLACK) + { + sibling.color = RED; + sibling.left.color = BLACK; + RotateRight(sibling); + } + else if (node == parentNode.right && + sibling.color == BLACK && + GetColor(sibling.right) == RED && + GetColor(sibling.left) == BLACK) + { + sibling.color = RED; + sibling.right.color = BLACK; + RotateLeft(sibling); + } + sibling = Sibling(node, parentNode); // update value of sibling after rotation + + sibling.color = parentNode.color; + parentNode.color = BLACK; + if (node == parentNode.left) { + if (sibling.right != null) { + Debug.Assert(sibling.right.color == RED); + sibling.right.color = BLACK; + } + RotateLeft(parentNode); + } else { + if (sibling.left != null) { + Debug.Assert(sibling.left.color == RED); + sibling.left.color = BLACK; + } + RotateRight(parentNode); + } + } + + void ReplaceNode(LineNode replacedNode, LineNode newNode) + { + if (replacedNode.parent == null) { + Debug.Assert(replacedNode == root); + root = newNode; + } else { + if (replacedNode.parent.left == replacedNode) + replacedNode.parent.left = newNode; + else + replacedNode.parent.right = newNode; + } + if (newNode != null) { + newNode.parent = replacedNode.parent; + } + replacedNode.parent = null; + } + + void RotateLeft(LineNode p) + { + // let q be p's right child + LineNode q = p.right; + Debug.Assert(q != null); + Debug.Assert(q.parent == p); + // set q to be the new root + ReplaceNode(p, q); + + // set p's right child to be q's left child + p.right = q.left; + if (p.right != null) p.right.parent = p; + // set q's left child to be p + q.left = p; + p.parent = q; + UpdateAfterRotateLeft(p); + } + + void RotateRight(LineNode p) + { + // let q be p's left child + LineNode q = p.left; + Debug.Assert(q != null); + Debug.Assert(q.parent == p); + // set q to be the new root + ReplaceNode(p, q); + + // set p's left child to be q's right child + p.left = q.right; + if (p.left != null) p.left.parent = p; + // set q's right child to be p + q.right = p; + p.parent = q; + UpdateAfterRotateRight(p); + } + + static LineNode Sibling(LineNode node) + { + if (node == node.parent.left) + return node.parent.right; + else + return node.parent.left; + } + + static LineNode Sibling(LineNode node, LineNode parentNode) + { + Debug.Assert(node == null || node.parent == parentNode); + if (node == parentNode.left) + return parentNode.right; + else + return parentNode.left; + } + + static bool GetColor(LineNode node) + { + return node != null ? node.color : BLACK; + } + #endregion + + #region IList implementation + DocumentLine IList.this[int index] { + get { + document.VerifyAccess(); + return GetByNumber(1 + index); + } + set { + throw new NotSupportedException(); + } + } + + int ICollection.Count { + get { + document.VerifyAccess(); + return LineCount; + } + } + + bool ICollection.IsReadOnly { + get { return true; } + } + + int IList.IndexOf(DocumentLine item) + { + document.VerifyAccess(); + if (item == null || item.IsDeleted) + return -1; + int index = item.LineNumber - 1; + if (index < LineCount && GetNodeByIndex(index) == item) + return index; + else + return -1; + } + + void IList.Insert(int index, DocumentLine item) + { + throw new NotSupportedException(); + } + + void IList.RemoveAt(int index) + { + throw new NotSupportedException(); + } + + void ICollection.Add(DocumentLine item) + { + throw new NotSupportedException(); + } + + void ICollection.Clear() + { + throw new NotSupportedException(); + } + + bool ICollection.Contains(DocumentLine item) + { + IList self = this; + return self.IndexOf(item) >= 0; + } + + void ICollection.CopyTo(DocumentLine[] array, int arrayIndex) + { + if (array == null) + throw new ArgumentNullException("array"); + if (array.Length < LineCount) + throw new ArgumentException("The array is too small", "array"); + if (arrayIndex < 0 || arrayIndex + LineCount > array.Length) + throw new ArgumentOutOfRangeException("arrayIndex", arrayIndex, "Value must be between 0 and " + (array.Length - LineCount)); + foreach (DocumentLine ls in this) { + array[arrayIndex++] = ls; + } + } + + bool ICollection.Remove(DocumentLine item) + { + throw new NotSupportedException(); + } + + public IEnumerator GetEnumerator() + { + document.VerifyAccess(); + return Enumerate(); + } + + IEnumerator Enumerate() + { + document.VerifyAccess(); + DocumentLine line = root.LeftMost; + while (line != null) { + yield return line; + line = line.NextLine; + } + } + + System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() + { + return this.GetEnumerator(); + } + #endregion + } +} -- cgit v1.3.1