From fc8a05358a92cc3c77c5f1e30d536807ef0614fd Mon Sep 17 00:00:00 2001 From: Victoria Plitt Date: Mon, 8 Apr 2019 13:49:55 +0300 Subject: were added scripting projects --- .../Rendering/HeightTree.cs | 1092 ++++++++++++++++++++ 1 file changed, 1092 insertions(+) create mode 100644 Software/Visual_Studio/Scripting/Tango.Scripting.Editors/Rendering/HeightTree.cs (limited to 'Software/Visual_Studio/Scripting/Tango.Scripting.Editors/Rendering/HeightTree.cs') diff --git a/Software/Visual_Studio/Scripting/Tango.Scripting.Editors/Rendering/HeightTree.cs b/Software/Visual_Studio/Scripting/Tango.Scripting.Editors/Rendering/HeightTree.cs new file mode 100644 index 000000000..6751af8fa --- /dev/null +++ b/Software/Visual_Studio/Scripting/Tango.Scripting.Editors/Rendering/HeightTree.cs @@ -0,0 +1,1092 @@ +// 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; + +using Tango.Scripting.Editors.Document; +using Tango.Scripting.Editors.Utils; + +namespace Tango.Scripting.Editors.Rendering +{ + /// + /// Red-black tree similar to DocumentLineTree, augmented with collapsing and height data. + /// + sealed class HeightTree : ILineTracker, IDisposable + { + // TODO: Optimize this. This tree takes alot of memory. + // (56 bytes for HeightTreeNode + // We should try to get rid of the dictionary and find height nodes per index. (DONE!) + // And we might do much better by compressing lines with the same height into a single node. + // That would also improve load times because we would always start with just a single node. + + /* Idea: + class NewHeightTreeNode { + int totalCount; // =count+left.count+right.count + int count; // one node can represent multiple lines + double height; // height of each line in this node + double totalHeight; // =(collapsedSections!=null?0:height*count) + left.totalHeight + right.totalHeight + List collapsedSections; // sections holding this line collapsed + // no "nodeCollapsedSections"/"totalCollapsedSections": + NewHeightTreeNode left, right, parent; + bool color; + } + totalCollapsedSections: are hard to update and not worth the effort. O(n log n) isn't too bad for + collapsing/uncollapsing, especially when compression reduces the n. + */ + + #region Constructor + readonly TextDocument document; + HeightTreeNode root; + WeakLineTracker weakLineTracker; + + public HeightTree(TextDocument document, double defaultLineHeight) + { + this.document = document; + weakLineTracker = WeakLineTracker.Register(document, this); + this.DefaultLineHeight = defaultLineHeight; + RebuildDocument(); + } + + public void Dispose() + { + if (weakLineTracker != null) + weakLineTracker.Deregister(); + this.root = null; + this.weakLineTracker = null; + } + + double defaultLineHeight; + + public double DefaultLineHeight { + get { return defaultLineHeight; } + set { + double oldValue = defaultLineHeight; + if (oldValue == value) + return; + defaultLineHeight = value; + // update the stored value in all nodes: + foreach (var node in AllNodes) { + if (node.lineNode.height == oldValue) { + node.lineNode.height = value; + UpdateAugmentedData(node, UpdateAfterChildrenChangeRecursionMode.IfRequired); + } + } + } + } + + HeightTreeNode GetNode(DocumentLine ls) + { + return GetNodeByIndex(ls.LineNumber - 1); + } + #endregion + + #region RebuildDocument + void ILineTracker.SetLineLength(DocumentLine ls, int newTotalLength) + { + } + + /// + /// Rebuild the tree, in O(n). + /// + public void RebuildDocument() + { + foreach (CollapsedLineSection s in GetAllCollapsedSections()) { + s.Start = null; + s.End = null; + } + + HeightTreeNode[] nodes = new HeightTreeNode[document.LineCount]; + int lineNumber = 0; + foreach (DocumentLine ls in document.Lines) { + nodes[lineNumber++] = new HeightTreeNode(ls, defaultLineHeight); + } + Debug.Assert(nodes.Length > 0); + // now build the corresponding balanced tree + int height = DocumentLineTree.GetTreeHeight(nodes.Length); + Debug.WriteLine("HeightTree will have height: " + height); + root = BuildTree(nodes, 0, nodes.Length, height); + root.color = BLACK; + #if DEBUG + CheckProperties(); + #endif + } + + /// + /// build a tree from a list of nodes + /// + HeightTreeNode BuildTree(HeightTreeNode[] nodes, int start, int end, int subtreeHeight) + { + Debug.Assert(start <= end); + if (start == end) { + return null; + } + int middle = (start + end) / 2; + HeightTreeNode 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; + UpdateAugmentedData(node, UpdateAfterChildrenChangeRecursionMode.None); + return node; + } + #endregion + + #region Insert/Remove lines + void ILineTracker.BeforeRemoveLine(DocumentLine line) + { + HeightTreeNode node = GetNode(line); + if (node.lineNode.collapsedSections != null) { + foreach (CollapsedLineSection cs in node.lineNode.collapsedSections.ToArray()) { + if (cs.Start == line && cs.End == line) { + cs.Start = null; + cs.End = null; + } else if (cs.Start == line) { + Uncollapse(cs); + cs.Start = line.NextLine; + AddCollapsedSection(cs, cs.End.LineNumber - cs.Start.LineNumber + 1); + } else if (cs.End == line) { + Uncollapse(cs); + cs.End = line.PreviousLine; + AddCollapsedSection(cs, cs.End.LineNumber - cs.Start.LineNumber + 1); + } + } + } + BeginRemoval(); + RemoveNode(node); + // clear collapsedSections from removed line: prevent damage if removed line is in "nodesToCheckForMerging" + node.lineNode.collapsedSections = null; + EndRemoval(); + } + +// void ILineTracker.AfterRemoveLine(DocumentLine line) +// { +// +// } + + void ILineTracker.LineInserted(DocumentLine insertionPos, DocumentLine newLine) + { + InsertAfter(GetNode(insertionPos), newLine); + #if DEBUG + CheckProperties(); + #endif + } + + HeightTreeNode InsertAfter(HeightTreeNode node, DocumentLine newLine) + { + HeightTreeNode newNode = new HeightTreeNode(newLine, defaultLineHeight); + if (node.right == null) { + if (node.lineNode.collapsedSections != null) { + // we are inserting directly after node - so copy all collapsedSections + // that do not end at node. + foreach (CollapsedLineSection cs in node.lineNode.collapsedSections) { + if (cs.End != node.documentLine) + newNode.AddDirectlyCollapsed(cs); + } + } + InsertAsRight(node, newNode); + } else { + node = node.right.LeftMost; + if (node.lineNode.collapsedSections != null) { + // we are inserting directly before node - so copy all collapsedSections + // that do not start at node. + foreach (CollapsedLineSection cs in node.lineNode.collapsedSections) { + if (cs.Start != node.documentLine) + newNode.AddDirectlyCollapsed(cs); + } + } + InsertAsLeft(node, newNode); + } + return newNode; + } + #endregion + + #region Rotation callbacks + enum UpdateAfterChildrenChangeRecursionMode + { + None, + IfRequired, + WholeBranch + } + + static void UpdateAfterChildrenChange(HeightTreeNode node) + { + UpdateAugmentedData(node, UpdateAfterChildrenChangeRecursionMode.IfRequired); + } + + static void UpdateAugmentedData(HeightTreeNode node, UpdateAfterChildrenChangeRecursionMode mode) + { + int totalCount = 1; + double totalHeight = node.lineNode.TotalHeight; + if (node.left != null) { + totalCount += node.left.totalCount; + totalHeight += node.left.totalHeight; + } + if (node.right != null) { + totalCount += node.right.totalCount; + totalHeight += node.right.totalHeight; + } + if (node.IsDirectlyCollapsed) + totalHeight = 0; + if (totalCount != node.totalCount + || !totalHeight.IsClose(node.totalHeight) + || mode == UpdateAfterChildrenChangeRecursionMode.WholeBranch) + { + node.totalCount = totalCount; + node.totalHeight = totalHeight; + if (node.parent != null && mode != UpdateAfterChildrenChangeRecursionMode.None) + UpdateAugmentedData(node.parent, mode); + } + } + + void UpdateAfterRotateLeft(HeightTreeNode node) + { + // node = old parent + // node.parent = pivot, new parent + var collapsedP = node.parent.collapsedSections; + var collapsedQ = node.collapsedSections; + // move collapsedSections from old parent to new parent + node.parent.collapsedSections = collapsedQ; + node.collapsedSections = null; + // split the collapsedSections from the new parent into its old children: + if (collapsedP != null) { + foreach (CollapsedLineSection cs in collapsedP) { + if (node.parent.right != null) + node.parent.right.AddDirectlyCollapsed(cs); + node.parent.lineNode.AddDirectlyCollapsed(cs); + if (node.right != null) + node.right.AddDirectlyCollapsed(cs); + } + } + MergeCollapsedSectionsIfPossible(node); + + UpdateAfterChildrenChange(node); + + // not required: rotations only happen on insertions/deletions + // -> totalCount changes -> the parent is always updated + //UpdateAfterChildrenChange(node.parent); + } + + void UpdateAfterRotateRight(HeightTreeNode node) + { + // node = old parent + // node.parent = pivot, new parent + var collapsedP = node.parent.collapsedSections; + var collapsedQ = node.collapsedSections; + // move collapsedSections from old parent to new parent + node.parent.collapsedSections = collapsedQ; + node.collapsedSections = null; + // split the collapsedSections from the new parent into its old children: + if (collapsedP != null) { + foreach (CollapsedLineSection cs in collapsedP) { + if (node.parent.left != null) + node.parent.left.AddDirectlyCollapsed(cs); + node.parent.lineNode.AddDirectlyCollapsed(cs); + if (node.left != null) + node.left.AddDirectlyCollapsed(cs); + } + } + MergeCollapsedSectionsIfPossible(node); + + UpdateAfterChildrenChange(node); + + // not required: rotations only happen on insertions/deletions + // -> totalCount changes -> the parent is always updated + //UpdateAfterChildrenChange(node.parent); + } + + // node removal: + // a node in the middle of the tree is removed as following: + // its successor is removed + // it is replaced with its successor + + void BeforeNodeRemove(HeightTreeNode removedNode) + { + Debug.Assert(removedNode.left == null || removedNode.right == null); + + var collapsed = removedNode.collapsedSections; + if (collapsed != null) { + HeightTreeNode childNode = removedNode.left ?? removedNode.right; + if (childNode != null) { + foreach (CollapsedLineSection cs in collapsed) + childNode.AddDirectlyCollapsed(cs); + } + } + if (removedNode.parent != null) + MergeCollapsedSectionsIfPossible(removedNode.parent); + } + + void BeforeNodeReplace(HeightTreeNode removedNode, HeightTreeNode newNode, HeightTreeNode newNodeOldParent) + { + Debug.Assert(removedNode != null); + Debug.Assert(newNode != null); + while (newNodeOldParent != removedNode) { + if (newNodeOldParent.collapsedSections != null) { + foreach (CollapsedLineSection cs in newNodeOldParent.collapsedSections) { + newNode.lineNode.AddDirectlyCollapsed(cs); + } + } + newNodeOldParent = newNodeOldParent.parent; + } + if (newNode.collapsedSections != null) { + foreach (CollapsedLineSection cs in newNode.collapsedSections) { + newNode.lineNode.AddDirectlyCollapsed(cs); + } + } + newNode.collapsedSections = removedNode.collapsedSections; + MergeCollapsedSectionsIfPossible(newNode); + } + + bool inRemoval; + List nodesToCheckForMerging; + + void BeginRemoval() + { + Debug.Assert(!inRemoval); + if (nodesToCheckForMerging == null) { + nodesToCheckForMerging = new List(); + } + inRemoval = true; + } + + void EndRemoval() + { + Debug.Assert(inRemoval); + inRemoval = false; + foreach (HeightTreeNode node in nodesToCheckForMerging) { + MergeCollapsedSectionsIfPossible(node); + } + nodesToCheckForMerging.Clear(); + } + + void MergeCollapsedSectionsIfPossible(HeightTreeNode node) + { + Debug.Assert(node != null); + if (inRemoval) { + nodesToCheckForMerging.Add(node); + return; + } + // now check if we need to merge collapsedSections together + bool merged = false; + var collapsedL = node.lineNode.collapsedSections; + if (collapsedL != null) { + for (int i = collapsedL.Count - 1; i >= 0; i--) { + CollapsedLineSection cs = collapsedL[i]; + if (cs.Start == node.documentLine || cs.End == node.documentLine) + continue; + if (node.left == null + || (node.left.collapsedSections != null && node.left.collapsedSections.Contains(cs))) + { + if (node.right == null + || (node.right.collapsedSections != null && node.right.collapsedSections.Contains(cs))) + { + // all children of node contain cs: -> merge! + if (node.left != null) node.left.RemoveDirectlyCollapsed(cs); + if (node.right != null) node.right.RemoveDirectlyCollapsed(cs); + collapsedL.RemoveAt(i); + node.AddDirectlyCollapsed(cs); + merged = true; + } + } + } + if (collapsedL.Count == 0) + node.lineNode.collapsedSections = null; + } + if (merged && node.parent != null) { + MergeCollapsedSectionsIfPossible(node.parent); + } + } + #endregion + + #region GetNodeBy... / Get...FromNode + HeightTreeNode GetNodeByIndex(int index) + { + Debug.Assert(index >= 0); + Debug.Assert(index < root.totalCount); + HeightTreeNode node = root; + while (true) { + if (node.left != null && index < node.left.totalCount) { + node = node.left; + } else { + if (node.left != null) { + index -= node.left.totalCount; + } + if (index == 0) + return node; + index--; + node = node.right; + } + } + } + + HeightTreeNode GetNodeByVisualPosition(double position) + { + HeightTreeNode node = root; + while (true) { + double positionAfterLeft = position; + if (node.left != null) { + positionAfterLeft -= node.left.totalHeight; + if (positionAfterLeft < 0) { + // Descend into left + node = node.left; + continue; + } + } + double positionBeforeRight = positionAfterLeft - node.lineNode.TotalHeight; + if (positionBeforeRight < 0) { + // Found the correct node + return node; + } + if (node.right == null || node.right.totalHeight == 0) { + // Can happen when position>node.totalHeight, + // i.e. at the end of the document, or due to rounding errors in previous loop iterations. + + // If node.lineNode isn't collapsed, return that. + // Also return node.lineNode if there is no previous node that we could return instead. + if (node.lineNode.TotalHeight > 0 || node.left == null) + return node; + // Otherwise, descend into left (find the last non-collapsed node) + node = node.left; + } else { + // Descend into right + position = positionBeforeRight; + node = node.right; + } + } + } + + static double GetVisualPositionFromNode(HeightTreeNode node) + { + double position = (node.left != null) ? node.left.totalHeight : 0; + while (node.parent != null) { + if (node.IsDirectlyCollapsed) + position = 0; + if (node == node.parent.right) { + if (node.parent.left != null) + position += node.parent.left.totalHeight; + position += node.parent.lineNode.TotalHeight; + } + node = node.parent; + } + return position; + } + #endregion + + #region Public methods + public DocumentLine GetLineByNumber(int number) + { + return GetNodeByIndex(number - 1).documentLine; + } + + public DocumentLine GetLineByVisualPosition(double position) + { + return GetNodeByVisualPosition(position).documentLine; + } + + public double GetVisualPosition(DocumentLine line) + { + return GetVisualPositionFromNode(GetNode(line)); + } + + public double GetHeight(DocumentLine line) + { + return GetNode(line).lineNode.height; + } + + public void SetHeight(DocumentLine line, double val) + { + var node = GetNode(line); + node.lineNode.height = val; + UpdateAfterChildrenChange(node); + } + + public bool GetIsCollapsed(int lineNumber) + { + var node = GetNodeByIndex(lineNumber - 1); + return node.lineNode.IsDirectlyCollapsed || GetIsCollapedFromNode(node); + } + + /// + /// Collapses the specified text section. + /// Runtime: O(log n) + /// + public CollapsedLineSection CollapseText(DocumentLine start, DocumentLine end) + { + if (!document.Lines.Contains(start)) + throw new ArgumentException("Line is not part of this document", "start"); + if (!document.Lines.Contains(end)) + throw new ArgumentException("Line is not part of this document", "end"); + int length = end.LineNumber - start.LineNumber + 1; + if (length < 0) + throw new ArgumentException("start must be a line before end"); + CollapsedLineSection section = new CollapsedLineSection(this, start, end); + AddCollapsedSection(section, length); + #if DEBUG + CheckProperties(); + #endif + return section; + } + #endregion + + #region LineCount & TotalHeight + public int LineCount { + get { + return root.totalCount; + } + } + + public double TotalHeight { + get { + return root.totalHeight; + } + } + #endregion + + #region GetAllCollapsedSections + IEnumerable AllNodes { + get { + if (root != null) { + HeightTreeNode node = root.LeftMost; + while (node != null) { + yield return node; + node = node.Successor; + } + } + } + } + + internal IEnumerable GetAllCollapsedSections() + { + List emptyCSList = new List(); + return System.Linq.Enumerable.Distinct( + System.Linq.Enumerable.SelectMany( + AllNodes, node => System.Linq.Enumerable.Concat(node.lineNode.collapsedSections ?? emptyCSList, + node.collapsedSections ?? emptyCSList) + )); + } + #endregion + + #region CheckProperties + #if DEBUG + [Conditional("DATACONSISTENCYTEST")] + internal void CheckProperties() + { + CheckProperties(root); + + foreach (CollapsedLineSection cs in GetAllCollapsedSections()) { + Debug.Assert(GetNode(cs.Start).lineNode.collapsedSections.Contains(cs)); + Debug.Assert(GetNode(cs.End).lineNode.collapsedSections.Contains(cs)); + int endLine = cs.End.LineNumber; + for (int i = cs.Start.LineNumber; i <= endLine; i++) { + CheckIsInSection(cs, GetLineByNumber(i)); + } + } + + // check red-black property: + int blackCount = -1; + CheckNodeProperties(root, null, RED, 0, ref blackCount); + } + + void CheckIsInSection(CollapsedLineSection cs, DocumentLine line) + { + HeightTreeNode node = GetNode(line); + if (node.lineNode.collapsedSections != null && node.lineNode.collapsedSections.Contains(cs)) + return; + while (node != null) { + if (node.collapsedSections != null && node.collapsedSections.Contains(cs)) + return; + node = node.parent; + } + throw new InvalidOperationException(cs + " not found for line " + line); + } + + void CheckProperties(HeightTreeNode node) + { + int totalCount = 1; + double totalHeight = node.lineNode.TotalHeight; + if (node.lineNode.IsDirectlyCollapsed) + Debug.Assert(node.lineNode.collapsedSections.Count > 0); + if (node.left != null) { + CheckProperties(node.left); + totalCount += node.left.totalCount; + totalHeight += node.left.totalHeight; + + CheckAllContainedIn(node.left.collapsedSections, node.lineNode.collapsedSections); + } + if (node.right != null) { + CheckProperties(node.right); + totalCount += node.right.totalCount; + totalHeight += node.right.totalHeight; + + CheckAllContainedIn(node.right.collapsedSections, node.lineNode.collapsedSections); + } + if (node.left != null && node.right != null) { + if (node.left.collapsedSections != null && node.right.collapsedSections != null) { + var intersection = System.Linq.Enumerable.Intersect(node.left.collapsedSections, node.right.collapsedSections); + Debug.Assert(System.Linq.Enumerable.Count(intersection) == 0); + } + } + if (node.IsDirectlyCollapsed) { + Debug.Assert(node.collapsedSections.Count > 0); + totalHeight = 0; + } + Debug.Assert(node.totalCount == totalCount); + Debug.Assert(node.totalHeight.IsClose(totalHeight)); + } + + /// + /// Checks that all elements in list1 are contained in list2. + /// + static void CheckAllContainedIn(IEnumerable list1, ICollection list2) + { + if (list1 == null) list1 = new List(); + if (list2 == null) list2 = new List(); + foreach (CollapsedLineSection cs in list1) { + Debug.Assert(list2.Contains(cs)); + } + } + + /* + 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(HeightTreeNode node, HeightTreeNode 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(HeightTreeNode 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 Red/Black Tree + const bool RED = true; + const bool BLACK = false; + + void InsertAsLeft(HeightTreeNode parentNode, HeightTreeNode newNode) + { + Debug.Assert(parentNode.left == null); + parentNode.left = newNode; + newNode.parent = parentNode; + newNode.color = RED; + UpdateAfterChildrenChange(parentNode); + FixTreeOnInsert(newNode); + } + + void InsertAsRight(HeightTreeNode parentNode, HeightTreeNode newNode) + { + Debug.Assert(parentNode.right == null); + parentNode.right = newNode; + newNode.parent = parentNode; + newNode.color = RED; + UpdateAfterChildrenChange(parentNode); + FixTreeOnInsert(newNode); + } + + void FixTreeOnInsert(HeightTreeNode 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); + + HeightTreeNode 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 + HeightTreeNode grandparentNode = parentNode.parent; + HeightTreeNode 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(HeightTreeNode removedNode) + { + if (removedNode.left != null && removedNode.right != null) { + // replace removedNode with it's in-order successor + + HeightTreeNode leftMost = removedNode.right.LeftMost; + HeightTreeNode parentOfLeftMost = leftMost.parent; + RemoveNode(leftMost); // remove leftMost from its current location + + BeforeNodeReplace(removedNode, leftMost, parentOfLeftMost); + // 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 + HeightTreeNode parentNode = removedNode.parent; + HeightTreeNode childNode = removedNode.left ?? removedNode.right; + BeforeNodeRemove(removedNode); + 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(HeightTreeNode node, HeightTreeNode parentNode) + { + Debug.Assert(node == null || node.parent == parentNode); + if (parentNode == null) + return; + + // warning: node may be null + HeightTreeNode 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(HeightTreeNode replacedNode, HeightTreeNode 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(HeightTreeNode p) + { + // let q be p's right child + HeightTreeNode 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(HeightTreeNode p) + { + // let q be p's left child + HeightTreeNode 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 HeightTreeNode Sibling(HeightTreeNode node) + { + if (node == node.parent.left) + return node.parent.right; + else + return node.parent.left; + } + + static HeightTreeNode Sibling(HeightTreeNode node, HeightTreeNode parentNode) + { + Debug.Assert(node == null || node.parent == parentNode); + if (node == parentNode.left) + return parentNode.right; + else + return parentNode.left; + } + + static bool GetColor(HeightTreeNode node) + { + return node != null ? node.color : BLACK; + } + #endregion + + #region Collapsing support + static bool GetIsCollapedFromNode(HeightTreeNode node) + { + while (node != null) { + if (node.IsDirectlyCollapsed) + return true; + node = node.parent; + } + return false; + } + + internal void AddCollapsedSection(CollapsedLineSection section, int sectionLength) + { + AddRemoveCollapsedSection(section, sectionLength, true); + } + + void AddRemoveCollapsedSection(CollapsedLineSection section, int sectionLength, bool add) + { + Debug.Assert(sectionLength > 0); + + HeightTreeNode node = GetNode(section.Start); + // Go up in the tree. + while (true) { + // Mark all middle nodes as collapsed + if (add) + node.lineNode.AddDirectlyCollapsed(section); + else + node.lineNode.RemoveDirectlyCollapsed(section); + sectionLength -= 1; + if (sectionLength == 0) { + // we are done! + Debug.Assert(node.documentLine == section.End); + break; + } + // Mark all right subtrees as collapsed. + if (node.right != null) { + if (node.right.totalCount < sectionLength) { + if (add) + node.right.AddDirectlyCollapsed(section); + else + node.right.RemoveDirectlyCollapsed(section); + sectionLength -= node.right.totalCount; + } else { + // mark partially into the right subtree: go down the right subtree. + AddRemoveCollapsedSectionDown(section, node.right, sectionLength, add); + break; + } + } + // go up to the next node + HeightTreeNode parentNode = node.parent; + Debug.Assert(parentNode != null); + while (parentNode.right == node) { + node = parentNode; + parentNode = node.parent; + Debug.Assert(parentNode != null); + } + node = parentNode; + } + UpdateAugmentedData(GetNode(section.Start), UpdateAfterChildrenChangeRecursionMode.WholeBranch); + UpdateAugmentedData(GetNode(section.End), UpdateAfterChildrenChangeRecursionMode.WholeBranch); + } + + static void AddRemoveCollapsedSectionDown(CollapsedLineSection section, HeightTreeNode node, int sectionLength, bool add) + { + while (true) { + if (node.left != null) { + if (node.left.totalCount < sectionLength) { + // mark left subtree + if (add) + node.left.AddDirectlyCollapsed(section); + else + node.left.RemoveDirectlyCollapsed(section); + sectionLength -= node.left.totalCount; + } else { + // mark only inside the left subtree + node = node.left; + Debug.Assert(node != null); + continue; + } + } + if (add) + node.lineNode.AddDirectlyCollapsed(section); + else + node.lineNode.RemoveDirectlyCollapsed(section); + sectionLength -= 1; + if (sectionLength == 0) { + // done! + Debug.Assert(node.documentLine == section.End); + break; + } + // mark inside right subtree: + node = node.right; + Debug.Assert(node != null); + } + } + + public void Uncollapse(CollapsedLineSection section) + { + int sectionLength = section.End.LineNumber - section.Start.LineNumber + 1; + AddRemoveCollapsedSection(section, sectionLength, false); + // do not call CheckProperties() in here - Uncollapse is also called during line removals + } + #endregion + } +} -- cgit v1.3.1