Free cookie consent management tool by TermsFeed Policy Generator

source: branches/ALPS/HeuristicLab.ExtLibs/HeuristicLab.AvalonEdit/5.0.1/AvalonEdit-5.0.1/Rendering/HeightTree.cs @ 12048

Last change on this file since 12048 was 11700, checked in by jkarder, 10 years ago

#2077: created branch and added first version

File size: 33.7 KB
Line 
1// Copyright (c) 2014 AlphaSierraPapa for the SharpDevelop Team
2//
3// Permission is hereby granted, free of charge, to any person obtaining a copy of this
4// software and associated documentation files (the "Software"), to deal in the Software
5// without restriction, including without limitation the rights to use, copy, modify, merge,
6// publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons
7// to whom the Software is furnished to do so, subject to the following conditions:
8//
9// The above copyright notice and this permission notice shall be included in all copies or
10// substantial portions of the Software.
11//
12// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED,
13// INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR
14// PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE
15// FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR
16// OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
17// DEALINGS IN THE SOFTWARE.
18
19using System;
20using System.Collections.Generic;
21using System.Diagnostics;
22using System.Text;
23
24using ICSharpCode.AvalonEdit.Document;
25using ICSharpCode.AvalonEdit.Utils;
26
27namespace ICSharpCode.AvalonEdit.Rendering
28{
29  /// <summary>
30  /// Red-black tree similar to DocumentLineTree, augmented with collapsing and height data.
31  /// </summary>
32  sealed class HeightTree : ILineTracker, IDisposable
33  {
34    // TODO: Optimize this. This tree takes alot of memory.
35    // (56 bytes for HeightTreeNode
36    // We should try to get rid of the dictionary and find height nodes per index. (DONE!)
37    // And we might do much better by compressing lines with the same height into a single node.
38    // That would also improve load times because we would always start with just a single node.
39   
40    /* Idea:
41     class NewHeightTreeNode {
42      int totalCount; // =count+left.count+right.count
43      int count; // one node can represent multiple lines
44      double height; // height of each line in this node
45      double totalHeight; // =(collapsedSections!=null?0:height*count) + left.totalHeight + right.totalHeight
46      List<CollapsedSection> collapsedSections; // sections holding this line collapsed
47      // no "nodeCollapsedSections"/"totalCollapsedSections":
48      NewHeightTreeNode left, right, parent;
49      bool color;
50    }
51    totalCollapsedSections: are hard to update and not worth the effort. O(n log n) isn't too bad for
52     collapsing/uncollapsing, especially when compression reduces the n.
53     */
54   
55    #region Constructor
56    readonly TextDocument document;
57    HeightTreeNode root;
58    WeakLineTracker weakLineTracker;
59   
60    public HeightTree(TextDocument document, double defaultLineHeight)
61    {
62      this.document = document;
63      weakLineTracker = WeakLineTracker.Register(document, this);
64      this.DefaultLineHeight = defaultLineHeight;
65      RebuildDocument();
66    }
67   
68    public void Dispose()
69    {
70      if (weakLineTracker != null)
71        weakLineTracker.Deregister();
72      this.root = null;
73      this.weakLineTracker = null;
74    }
75   
76    double defaultLineHeight;
77   
78    public double DefaultLineHeight {
79      get { return defaultLineHeight; }
80      set {
81        double oldValue = defaultLineHeight;
82        if (oldValue == value)
83          return;
84        defaultLineHeight = value;
85        // update the stored value in all nodes:
86        foreach (var node in AllNodes) {
87          if (node.lineNode.height == oldValue) {
88            node.lineNode.height = value;
89            UpdateAugmentedData(node, UpdateAfterChildrenChangeRecursionMode.IfRequired);
90          }
91        }
92      }
93    }
94   
95    HeightTreeNode GetNode(DocumentLine ls)
96    {
97      return GetNodeByIndex(ls.LineNumber - 1);
98    }
99    #endregion
100   
101    #region RebuildDocument
102    void ILineTracker.ChangeComplete(DocumentChangeEventArgs e)
103    {
104    }
105   
106    void ILineTracker.SetLineLength(DocumentLine ls, int newTotalLength)
107    {
108    }
109   
110    /// <summary>
111    /// Rebuild the tree, in O(n).
112    /// </summary>
113    public void RebuildDocument()
114    {
115      foreach (CollapsedLineSection s in GetAllCollapsedSections()) {
116        s.Start = null;
117        s.End = null;
118      }
119     
120      HeightTreeNode[] nodes = new HeightTreeNode[document.LineCount];
121      int lineNumber = 0;
122      foreach (DocumentLine ls in document.Lines) {
123        nodes[lineNumber++] = new HeightTreeNode(ls, defaultLineHeight);
124      }
125      Debug.Assert(nodes.Length > 0);
126      // now build the corresponding balanced tree
127      int height = DocumentLineTree.GetTreeHeight(nodes.Length);
128      Debug.WriteLine("HeightTree will have height: " + height);
129      root = BuildTree(nodes, 0, nodes.Length, height);
130      root.color = BLACK;
131      #if DEBUG
132      CheckProperties();
133      #endif
134    }
135   
136    /// <summary>
137    /// build a tree from a list of nodes
138    /// </summary>
139    HeightTreeNode BuildTree(HeightTreeNode[] nodes, int start, int end, int subtreeHeight)
140    {
141      Debug.Assert(start <= end);
142      if (start == end) {
143        return null;
144      }
145      int middle = (start + end) / 2;
146      HeightTreeNode node = nodes[middle];
147      node.left = BuildTree(nodes, start, middle, subtreeHeight - 1);
148      node.right = BuildTree(nodes, middle + 1, end, subtreeHeight - 1);
149      if (node.left != null) node.left.parent = node;
150      if (node.right != null) node.right.parent = node;
151      if (subtreeHeight == 1)
152        node.color = RED;
153      UpdateAugmentedData(node, UpdateAfterChildrenChangeRecursionMode.None);
154      return node;
155    }
156    #endregion
157   
158    #region Insert/Remove lines
159    void ILineTracker.BeforeRemoveLine(DocumentLine line)
160    {
161      HeightTreeNode node = GetNode(line);
162      if (node.lineNode.collapsedSections != null) {
163        foreach (CollapsedLineSection cs in node.lineNode.collapsedSections.ToArray()) {
164          if (cs.Start == line && cs.End == line) {
165            cs.Start = null;
166            cs.End = null;
167          } else if (cs.Start == line) {
168            Uncollapse(cs);
169            cs.Start = line.NextLine;
170            AddCollapsedSection(cs, cs.End.LineNumber - cs.Start.LineNumber + 1);
171          } else if (cs.End == line) {
172            Uncollapse(cs);
173            cs.End = line.PreviousLine;
174            AddCollapsedSection(cs, cs.End.LineNumber - cs.Start.LineNumber + 1);
175          }
176        }
177      }
178      BeginRemoval();
179      RemoveNode(node);
180      // clear collapsedSections from removed line: prevent damage if removed line is in "nodesToCheckForMerging"
181      node.lineNode.collapsedSections = null;
182      EndRemoval();
183    }
184   
185//    void ILineTracker.AfterRemoveLine(DocumentLine line)
186//    {
187//
188//    }
189   
190    void ILineTracker.LineInserted(DocumentLine insertionPos, DocumentLine newLine)
191    {
192      InsertAfter(GetNode(insertionPos), newLine);
193      #if DEBUG
194      CheckProperties();
195      #endif
196    }
197   
198    HeightTreeNode InsertAfter(HeightTreeNode node, DocumentLine newLine)
199    {
200      HeightTreeNode newNode = new HeightTreeNode(newLine, defaultLineHeight);
201      if (node.right == null) {
202        if (node.lineNode.collapsedSections != null) {
203          // we are inserting directly after node - so copy all collapsedSections
204          // that do not end at node.
205          foreach (CollapsedLineSection cs in node.lineNode.collapsedSections) {
206            if (cs.End != node.documentLine)
207              newNode.AddDirectlyCollapsed(cs);
208          }
209        }
210        InsertAsRight(node, newNode);
211      } else {
212        node = node.right.LeftMost;
213        if (node.lineNode.collapsedSections != null) {
214          // we are inserting directly before node - so copy all collapsedSections
215          // that do not start at node.
216          foreach (CollapsedLineSection cs in node.lineNode.collapsedSections) {
217            if (cs.Start != node.documentLine)
218              newNode.AddDirectlyCollapsed(cs);
219          }
220        }
221        InsertAsLeft(node, newNode);
222      }
223      return newNode;
224    }
225    #endregion
226   
227    #region Rotation callbacks
228    enum UpdateAfterChildrenChangeRecursionMode
229    {
230      None,
231      IfRequired,
232      WholeBranch
233    }
234   
235    static void UpdateAfterChildrenChange(HeightTreeNode node)
236    {
237      UpdateAugmentedData(node, UpdateAfterChildrenChangeRecursionMode.IfRequired);
238    }
239   
240    static void UpdateAugmentedData(HeightTreeNode node, UpdateAfterChildrenChangeRecursionMode mode)
241    {
242      int totalCount = 1;
243      double totalHeight = node.lineNode.TotalHeight;
244      if (node.left != null) {
245        totalCount += node.left.totalCount;
246        totalHeight += node.left.totalHeight;
247      }
248      if (node.right != null) {
249        totalCount += node.right.totalCount;
250        totalHeight += node.right.totalHeight;
251      }
252      if (node.IsDirectlyCollapsed)
253        totalHeight = 0;
254      if (totalCount != node.totalCount
255          || !totalHeight.IsClose(node.totalHeight)
256          || mode == UpdateAfterChildrenChangeRecursionMode.WholeBranch)
257      {
258        node.totalCount = totalCount;
259        node.totalHeight = totalHeight;
260        if (node.parent != null && mode != UpdateAfterChildrenChangeRecursionMode.None)
261          UpdateAugmentedData(node.parent, mode);
262      }
263    }
264   
265    void UpdateAfterRotateLeft(HeightTreeNode node)
266    {
267      // node = old parent
268      // node.parent = pivot, new parent
269      var collapsedP = node.parent.collapsedSections;
270      var collapsedQ = node.collapsedSections;
271      // move collapsedSections from old parent to new parent
272      node.parent.collapsedSections = collapsedQ;
273      node.collapsedSections = null;
274      // split the collapsedSections from the new parent into its old children:
275      if (collapsedP != null) {
276        foreach (CollapsedLineSection cs in collapsedP) {
277          if (node.parent.right != null)
278            node.parent.right.AddDirectlyCollapsed(cs);
279          node.parent.lineNode.AddDirectlyCollapsed(cs);
280          if (node.right != null)
281            node.right.AddDirectlyCollapsed(cs);
282        }
283      }
284      MergeCollapsedSectionsIfPossible(node);
285     
286      UpdateAfterChildrenChange(node);
287     
288      // not required: rotations only happen on insertions/deletions
289      // -> totalCount changes -> the parent is always updated
290      //UpdateAfterChildrenChange(node.parent);
291    }
292   
293    void UpdateAfterRotateRight(HeightTreeNode node)
294    {
295      // node = old parent
296      // node.parent = pivot, new parent
297      var collapsedP = node.parent.collapsedSections;
298      var collapsedQ = node.collapsedSections;
299      // move collapsedSections from old parent to new parent
300      node.parent.collapsedSections = collapsedQ;
301      node.collapsedSections = null;
302      // split the collapsedSections from the new parent into its old children:
303      if (collapsedP != null) {
304        foreach (CollapsedLineSection cs in collapsedP) {
305          if (node.parent.left != null)
306            node.parent.left.AddDirectlyCollapsed(cs);
307          node.parent.lineNode.AddDirectlyCollapsed(cs);
308          if (node.left != null)
309            node.left.AddDirectlyCollapsed(cs);
310        }
311      }
312      MergeCollapsedSectionsIfPossible(node);
313     
314      UpdateAfterChildrenChange(node);
315     
316      // not required: rotations only happen on insertions/deletions
317      // -> totalCount changes -> the parent is always updated
318      //UpdateAfterChildrenChange(node.parent);
319    }
320   
321    // node removal:
322    // a node in the middle of the tree is removed as following:
323    //  its successor is removed
324    //  it is replaced with its successor
325   
326    void BeforeNodeRemove(HeightTreeNode removedNode)
327    {
328      Debug.Assert(removedNode.left == null || removedNode.right == null);
329     
330      var collapsed = removedNode.collapsedSections;
331      if (collapsed != null) {
332        HeightTreeNode childNode = removedNode.left ?? removedNode.right;
333        if (childNode != null) {
334          foreach (CollapsedLineSection cs in collapsed)
335            childNode.AddDirectlyCollapsed(cs);
336        }
337      }
338      if (removedNode.parent != null)
339        MergeCollapsedSectionsIfPossible(removedNode.parent);
340    }
341   
342    void BeforeNodeReplace(HeightTreeNode removedNode, HeightTreeNode newNode, HeightTreeNode newNodeOldParent)
343    {
344      Debug.Assert(removedNode != null);
345      Debug.Assert(newNode != null);
346      while (newNodeOldParent != removedNode) {
347        if (newNodeOldParent.collapsedSections != null) {
348          foreach (CollapsedLineSection cs in newNodeOldParent.collapsedSections) {
349            newNode.lineNode.AddDirectlyCollapsed(cs);
350          }
351        }
352        newNodeOldParent = newNodeOldParent.parent;
353      }
354      if (newNode.collapsedSections != null) {
355        foreach (CollapsedLineSection cs in newNode.collapsedSections) {
356          newNode.lineNode.AddDirectlyCollapsed(cs);
357        }
358      }
359      newNode.collapsedSections = removedNode.collapsedSections;
360      MergeCollapsedSectionsIfPossible(newNode);
361    }
362   
363    bool inRemoval;
364    List<HeightTreeNode> nodesToCheckForMerging;
365   
366    void BeginRemoval()
367    {
368      Debug.Assert(!inRemoval);
369      if (nodesToCheckForMerging == null) {
370        nodesToCheckForMerging = new List<HeightTreeNode>();
371      }
372      inRemoval = true;
373    }
374   
375    void EndRemoval()
376    {
377      Debug.Assert(inRemoval);
378      inRemoval = false;
379      foreach (HeightTreeNode node in nodesToCheckForMerging) {
380        MergeCollapsedSectionsIfPossible(node);
381      }
382      nodesToCheckForMerging.Clear();
383    }
384   
385    void MergeCollapsedSectionsIfPossible(HeightTreeNode node)
386    {
387      Debug.Assert(node != null);
388      if (inRemoval) {
389        nodesToCheckForMerging.Add(node);
390        return;
391      }
392      // now check if we need to merge collapsedSections together
393      bool merged = false;
394      var collapsedL = node.lineNode.collapsedSections;
395      if (collapsedL != null) {
396        for (int i = collapsedL.Count - 1; i >= 0; i--) {
397          CollapsedLineSection cs = collapsedL[i];
398          if (cs.Start == node.documentLine || cs.End == node.documentLine)
399            continue;
400          if (node.left == null
401              || (node.left.collapsedSections != null && node.left.collapsedSections.Contains(cs)))
402          {
403            if (node.right == null
404                || (node.right.collapsedSections != null && node.right.collapsedSections.Contains(cs)))
405            {
406              // all children of node contain cs: -> merge!
407              if (node.left != null) node.left.RemoveDirectlyCollapsed(cs);
408              if (node.right != null) node.right.RemoveDirectlyCollapsed(cs);
409              collapsedL.RemoveAt(i);
410              node.AddDirectlyCollapsed(cs);
411              merged = true;
412            }
413          }
414        }
415        if (collapsedL.Count == 0)
416          node.lineNode.collapsedSections = null;
417      }
418      if (merged && node.parent != null) {
419        MergeCollapsedSectionsIfPossible(node.parent);
420      }
421    }
422    #endregion
423   
424    #region GetNodeBy... / Get...FromNode
425    HeightTreeNode GetNodeByIndex(int index)
426    {
427      Debug.Assert(index >= 0);
428      Debug.Assert(index < root.totalCount);
429      HeightTreeNode node = root;
430      while (true) {
431        if (node.left != null && index < node.left.totalCount) {
432          node = node.left;
433        } else {
434          if (node.left != null) {
435            index -= node.left.totalCount;
436          }
437          if (index == 0)
438            return node;
439          index--;
440          node = node.right;
441        }
442      }
443    }
444   
445    HeightTreeNode GetNodeByVisualPosition(double position)
446    {
447      HeightTreeNode node = root;
448      while (true) {
449        double positionAfterLeft = position;
450        if (node.left != null) {
451          positionAfterLeft -= node.left.totalHeight;
452          if (positionAfterLeft < 0) {
453            // Descend into left
454            node = node.left;
455            continue;
456          }
457        }
458        double positionBeforeRight = positionAfterLeft - node.lineNode.TotalHeight;
459        if (positionBeforeRight < 0) {
460          // Found the correct node
461          return node;
462        }
463        if (node.right == null || node.right.totalHeight == 0) {
464          // Can happen when position>node.totalHeight,
465          // i.e. at the end of the document, or due to rounding errors in previous loop iterations.
466         
467          // If node.lineNode isn't collapsed, return that.
468          // Also return node.lineNode if there is no previous node that we could return instead.
469          if (node.lineNode.TotalHeight > 0 || node.left == null)
470            return node;
471          // Otherwise, descend into left (find the last non-collapsed node)
472          node = node.left;
473        } else {
474          // Descend into right
475          position = positionBeforeRight;
476          node = node.right;
477        }
478      }
479    }
480   
481    static double GetVisualPositionFromNode(HeightTreeNode node)
482    {
483      double position = (node.left != null) ? node.left.totalHeight : 0;
484      while (node.parent != null) {
485        if (node.IsDirectlyCollapsed)
486          position = 0;
487        if (node == node.parent.right) {
488          if (node.parent.left != null)
489            position += node.parent.left.totalHeight;
490          position += node.parent.lineNode.TotalHeight;
491        }
492        node = node.parent;
493      }
494      return position;
495    }
496    #endregion
497   
498    #region Public methods
499    public DocumentLine GetLineByNumber(int number)
500    {
501      return GetNodeByIndex(number - 1).documentLine;
502    }
503   
504    public DocumentLine GetLineByVisualPosition(double position)
505    {
506      return GetNodeByVisualPosition(position).documentLine;
507    }
508   
509    public double GetVisualPosition(DocumentLine line)
510    {
511      return GetVisualPositionFromNode(GetNode(line));
512    }
513   
514    public double GetHeight(DocumentLine line)
515    {
516      return GetNode(line).lineNode.height;
517    }
518   
519    public void SetHeight(DocumentLine line, double val)
520    {
521      var node = GetNode(line);
522      node.lineNode.height = val;
523      UpdateAfterChildrenChange(node);
524    }
525   
526    public bool GetIsCollapsed(int lineNumber)
527    {
528      var node = GetNodeByIndex(lineNumber - 1);
529      return node.lineNode.IsDirectlyCollapsed || GetIsCollapedFromNode(node);
530    }
531   
532    /// <summary>
533    /// Collapses the specified text section.
534    /// Runtime: O(log n)
535    /// </summary>
536    public CollapsedLineSection CollapseText(DocumentLine start, DocumentLine end)
537    {
538      if (!document.Lines.Contains(start))
539        throw new ArgumentException("Line is not part of this document", "start");
540      if (!document.Lines.Contains(end))
541        throw new ArgumentException("Line is not part of this document", "end");
542      int length = end.LineNumber - start.LineNumber + 1;
543      if (length < 0)
544        throw new ArgumentException("start must be a line before end");
545      CollapsedLineSection section = new CollapsedLineSection(this, start, end);
546      AddCollapsedSection(section, length);
547      #if DEBUG
548      CheckProperties();
549      #endif
550      return section;
551    }
552    #endregion
553   
554    #region LineCount & TotalHeight
555    public int LineCount {
556      get {
557        return root.totalCount;
558      }
559    }
560   
561    public double TotalHeight {
562      get {
563        return root.totalHeight;
564      }
565    }
566    #endregion
567   
568    #region GetAllCollapsedSections
569    IEnumerable<HeightTreeNode> AllNodes {
570      get {
571        if (root != null) {
572          HeightTreeNode node = root.LeftMost;
573          while (node != null) {
574            yield return node;
575            node = node.Successor;
576          }
577        }
578      }
579    }
580   
581    internal IEnumerable<CollapsedLineSection> GetAllCollapsedSections()
582    {
583      List<CollapsedLineSection> emptyCSList = new List<CollapsedLineSection>();
584      return System.Linq.Enumerable.Distinct(
585        System.Linq.Enumerable.SelectMany(
586          AllNodes, node => System.Linq.Enumerable.Concat(node.lineNode.collapsedSections ?? emptyCSList,
587                                                          node.collapsedSections ?? emptyCSList)
588        ));
589    }
590    #endregion
591   
592    #region CheckProperties
593    #if DEBUG
594    [Conditional("DATACONSISTENCYTEST")]
595    internal void CheckProperties()
596    {
597      CheckProperties(root);
598     
599      foreach (CollapsedLineSection cs in GetAllCollapsedSections()) {
600        Debug.Assert(GetNode(cs.Start).lineNode.collapsedSections.Contains(cs));
601        Debug.Assert(GetNode(cs.End).lineNode.collapsedSections.Contains(cs));
602        int endLine = cs.End.LineNumber;
603        for (int i = cs.Start.LineNumber; i <= endLine; i++) {
604          CheckIsInSection(cs, GetLineByNumber(i));
605        }
606      }
607     
608      // check red-black property:
609      int blackCount = -1;
610      CheckNodeProperties(root, null, RED, 0, ref blackCount);
611    }
612   
613    void CheckIsInSection(CollapsedLineSection cs, DocumentLine line)
614    {
615      HeightTreeNode node = GetNode(line);
616      if (node.lineNode.collapsedSections != null && node.lineNode.collapsedSections.Contains(cs))
617        return;
618      while (node != null) {
619        if (node.collapsedSections != null && node.collapsedSections.Contains(cs))
620          return;
621        node = node.parent;
622      }
623      throw new InvalidOperationException(cs + " not found for line " + line);
624    }
625   
626    void CheckProperties(HeightTreeNode node)
627    {
628      int totalCount = 1;
629      double totalHeight = node.lineNode.TotalHeight;
630      if (node.lineNode.IsDirectlyCollapsed)
631        Debug.Assert(node.lineNode.collapsedSections.Count > 0);
632      if (node.left != null) {
633        CheckProperties(node.left);
634        totalCount += node.left.totalCount;
635        totalHeight += node.left.totalHeight;
636       
637        CheckAllContainedIn(node.left.collapsedSections, node.lineNode.collapsedSections);
638      }
639      if (node.right != null) {
640        CheckProperties(node.right);
641        totalCount += node.right.totalCount;
642        totalHeight += node.right.totalHeight;
643       
644        CheckAllContainedIn(node.right.collapsedSections, node.lineNode.collapsedSections);
645      }
646      if (node.left != null && node.right != null) {
647        if (node.left.collapsedSections != null && node.right.collapsedSections != null) {
648          var intersection = System.Linq.Enumerable.Intersect(node.left.collapsedSections, node.right.collapsedSections);
649          Debug.Assert(System.Linq.Enumerable.Count(intersection) == 0);
650        }
651      }
652      if (node.IsDirectlyCollapsed) {
653        Debug.Assert(node.collapsedSections.Count > 0);
654        totalHeight = 0;
655      }
656      Debug.Assert(node.totalCount == totalCount);
657      Debug.Assert(node.totalHeight.IsClose(totalHeight));
658    }
659   
660    /// <summary>
661    /// Checks that all elements in list1 are contained in list2.
662    /// </summary>
663    static void CheckAllContainedIn(IEnumerable<CollapsedLineSection> list1, ICollection<CollapsedLineSection> list2)
664    {
665      if (list1 == null) list1 = new List<CollapsedLineSection>();
666      if (list2 == null) list2 = new List<CollapsedLineSection>();
667      foreach (CollapsedLineSection cs in list1) {
668        Debug.Assert(list2.Contains(cs));
669      }
670    }
671   
672    /*
673    1. A node is either red or black.
674    2. The root is black.
675    3. All leaves are black. (The leaves are the NIL children.)
676    4. Both children of every red node are black. (So every red node must have a black parent.)
677    5. Every simple path from a node to a descendant leaf contains the same number of black nodes. (Not counting the leaf node.)
678     */
679    void CheckNodeProperties(HeightTreeNode node, HeightTreeNode parentNode, bool parentColor, int blackCount, ref int expectedBlackCount)
680    {
681      if (node == null) return;
682     
683      Debug.Assert(node.parent == parentNode);
684     
685      if (parentColor == RED) {
686        Debug.Assert(node.color == BLACK);
687      }
688      if (node.color == BLACK) {
689        blackCount++;
690      }
691      if (node.left == null && node.right == null) {
692        // node is a leaf node:
693        if (expectedBlackCount == -1)
694          expectedBlackCount = blackCount;
695        else
696          Debug.Assert(expectedBlackCount == blackCount);
697      }
698      CheckNodeProperties(node.left, node, node.color, blackCount, ref expectedBlackCount);
699      CheckNodeProperties(node.right, node, node.color, blackCount, ref expectedBlackCount);
700    }
701   
702    [System.Diagnostics.CodeAnalysis.SuppressMessage("Microsoft.Performance", "CA1811:AvoidUncalledPrivateCode")]
703    public string GetTreeAsString()
704    {
705      StringBuilder b = new StringBuilder();
706      AppendTreeToString(root, b, 0);
707      return b.ToString();
708    }
709   
710    static void AppendTreeToString(HeightTreeNode node, StringBuilder b, int indent)
711    {
712      if (node.color == RED)
713        b.Append("RED   ");
714      else
715        b.Append("BLACK ");
716      b.AppendLine(node.ToString());
717      indent += 2;
718      if (node.left != null) {
719        b.Append(' ', indent);
720        b.Append("L: ");
721        AppendTreeToString(node.left, b, indent);
722      }
723      if (node.right != null) {
724        b.Append(' ', indent);
725        b.Append("R: ");
726        AppendTreeToString(node.right, b, indent);
727      }
728    }
729    #endif
730    #endregion
731   
732    #region Red/Black Tree
733    const bool RED = true;
734    const bool BLACK = false;
735   
736    void InsertAsLeft(HeightTreeNode parentNode, HeightTreeNode newNode)
737    {
738      Debug.Assert(parentNode.left == null);
739      parentNode.left = newNode;
740      newNode.parent = parentNode;
741      newNode.color = RED;
742      UpdateAfterChildrenChange(parentNode);
743      FixTreeOnInsert(newNode);
744    }
745   
746    void InsertAsRight(HeightTreeNode parentNode, HeightTreeNode newNode)
747    {
748      Debug.Assert(parentNode.right == null);
749      parentNode.right = newNode;
750      newNode.parent = parentNode;
751      newNode.color = RED;
752      UpdateAfterChildrenChange(parentNode);
753      FixTreeOnInsert(newNode);
754    }
755   
756    void FixTreeOnInsert(HeightTreeNode node)
757    {
758      Debug.Assert(node != null);
759      Debug.Assert(node.color == RED);
760      Debug.Assert(node.left == null || node.left.color == BLACK);
761      Debug.Assert(node.right == null || node.right.color == BLACK);
762     
763      HeightTreeNode parentNode = node.parent;
764      if (parentNode == null) {
765        // we inserted in the root -> the node must be black
766        // since this is a root node, making the node black increments the number of black nodes
767        // on all paths by one, so it is still the same for all paths.
768        node.color = BLACK;
769        return;
770      }
771      if (parentNode.color == BLACK) {
772        // if the parent node where we inserted was black, our red node is placed correctly.
773        // since we inserted a red node, the number of black nodes on each path is unchanged
774        // -> the tree is still balanced
775        return;
776      }
777      // parentNode is red, so there is a conflict here!
778     
779      // because the root is black, parentNode is not the root -> there is a grandparent node
780      HeightTreeNode grandparentNode = parentNode.parent;
781      HeightTreeNode uncleNode = Sibling(parentNode);
782      if (uncleNode != null && uncleNode.color == RED) {
783        parentNode.color = BLACK;
784        uncleNode.color = BLACK;
785        grandparentNode.color = RED;
786        FixTreeOnInsert(grandparentNode);
787        return;
788      }
789      // now we know: parent is red but uncle is black
790      // First rotation:
791      if (node == parentNode.right && parentNode == grandparentNode.left) {
792        RotateLeft(parentNode);
793        node = node.left;
794      } else if (node == parentNode.left && parentNode == grandparentNode.right) {
795        RotateRight(parentNode);
796        node = node.right;
797      }
798      // because node might have changed, reassign variables:
799      parentNode = node.parent;
800      grandparentNode = parentNode.parent;
801     
802      // Now recolor a bit:
803      parentNode.color = BLACK;
804      grandparentNode.color = RED;
805      // Second rotation:
806      if (node == parentNode.left && parentNode == grandparentNode.left) {
807        RotateRight(grandparentNode);
808      } else {
809        // because of the first rotation, this is guaranteed:
810        Debug.Assert(node == parentNode.right && parentNode == grandparentNode.right);
811        RotateLeft(grandparentNode);
812      }
813    }
814   
815    void RemoveNode(HeightTreeNode removedNode)
816    {
817      if (removedNode.left != null && removedNode.right != null) {
818        // replace removedNode with it's in-order successor
819       
820        HeightTreeNode leftMost = removedNode.right.LeftMost;
821        HeightTreeNode parentOfLeftMost = leftMost.parent;
822        RemoveNode(leftMost); // remove leftMost from its current location
823       
824        BeforeNodeReplace(removedNode, leftMost, parentOfLeftMost);
825        // and overwrite the removedNode with it
826        ReplaceNode(removedNode, leftMost);
827        leftMost.left = removedNode.left;
828        if (leftMost.left != null) leftMost.left.parent = leftMost;
829        leftMost.right = removedNode.right;
830        if (leftMost.right != null) leftMost.right.parent = leftMost;
831        leftMost.color = removedNode.color;
832       
833        UpdateAfterChildrenChange(leftMost);
834        if (leftMost.parent != null) UpdateAfterChildrenChange(leftMost.parent);
835        return;
836      }
837     
838      // now either removedNode.left or removedNode.right is null
839      // get the remaining child
840      HeightTreeNode parentNode = removedNode.parent;
841      HeightTreeNode childNode = removedNode.left ?? removedNode.right;
842      BeforeNodeRemove(removedNode);
843      ReplaceNode(removedNode, childNode);
844      if (parentNode != null) UpdateAfterChildrenChange(parentNode);
845      if (removedNode.color == BLACK) {
846        if (childNode != null && childNode.color == RED) {
847          childNode.color = BLACK;
848        } else {
849          FixTreeOnDelete(childNode, parentNode);
850        }
851      }
852    }
853   
854    void FixTreeOnDelete(HeightTreeNode node, HeightTreeNode parentNode)
855    {
856      Debug.Assert(node == null || node.parent == parentNode);
857      if (parentNode == null)
858        return;
859     
860      // warning: node may be null
861      HeightTreeNode sibling = Sibling(node, parentNode);
862      if (sibling.color == RED) {
863        parentNode.color = RED;
864        sibling.color = BLACK;
865        if (node == parentNode.left) {
866          RotateLeft(parentNode);
867        } else {
868          RotateRight(parentNode);
869        }
870       
871        sibling = Sibling(node, parentNode); // update value of sibling after rotation
872      }
873     
874      if (parentNode.color == BLACK
875          && sibling.color == BLACK
876          && GetColor(sibling.left) == BLACK
877          && GetColor(sibling.right) == BLACK)
878      {
879        sibling.color = RED;
880        FixTreeOnDelete(parentNode, parentNode.parent);
881        return;
882      }
883     
884      if (parentNode.color == RED
885          && sibling.color == BLACK
886          && GetColor(sibling.left) == BLACK
887          && GetColor(sibling.right) == BLACK)
888      {
889        sibling.color = RED;
890        parentNode.color = BLACK;
891        return;
892      }
893     
894      if (node == parentNode.left &&
895          sibling.color == BLACK &&
896          GetColor(sibling.left) == RED &&
897          GetColor(sibling.right) == BLACK)
898      {
899        sibling.color = RED;
900        sibling.left.color = BLACK;
901        RotateRight(sibling);
902      }
903      else if (node == parentNode.right &&
904               sibling.color == BLACK &&
905               GetColor(sibling.right) == RED &&
906               GetColor(sibling.left) == BLACK)
907      {
908        sibling.color = RED;
909        sibling.right.color = BLACK;
910        RotateLeft(sibling);
911      }
912      sibling = Sibling(node, parentNode); // update value of sibling after rotation
913     
914      sibling.color = parentNode.color;
915      parentNode.color = BLACK;
916      if (node == parentNode.left) {
917        if (sibling.right != null) {
918          Debug.Assert(sibling.right.color == RED);
919          sibling.right.color = BLACK;
920        }
921        RotateLeft(parentNode);
922      } else {
923        if (sibling.left != null) {
924          Debug.Assert(sibling.left.color == RED);
925          sibling.left.color = BLACK;
926        }
927        RotateRight(parentNode);
928      }
929    }
930   
931    void ReplaceNode(HeightTreeNode replacedNode, HeightTreeNode newNode)
932    {
933      if (replacedNode.parent == null) {
934        Debug.Assert(replacedNode == root);
935        root = newNode;
936      } else {
937        if (replacedNode.parent.left == replacedNode)
938          replacedNode.parent.left = newNode;
939        else
940          replacedNode.parent.right = newNode;
941      }
942      if (newNode != null) {
943        newNode.parent = replacedNode.parent;
944      }
945      replacedNode.parent = null;
946    }
947   
948    void RotateLeft(HeightTreeNode p)
949    {
950      // let q be p's right child
951      HeightTreeNode q = p.right;
952      Debug.Assert(q != null);
953      Debug.Assert(q.parent == p);
954      // set q to be the new root
955      ReplaceNode(p, q);
956     
957      // set p's right child to be q's left child
958      p.right = q.left;
959      if (p.right != null) p.right.parent = p;
960      // set q's left child to be p
961      q.left = p;
962      p.parent = q;
963      UpdateAfterRotateLeft(p);
964    }
965   
966    void RotateRight(HeightTreeNode p)
967    {
968      // let q be p's left child
969      HeightTreeNode q = p.left;
970      Debug.Assert(q != null);
971      Debug.Assert(q.parent == p);
972      // set q to be the new root
973      ReplaceNode(p, q);
974     
975      // set p's left child to be q's right child
976      p.left = q.right;
977      if (p.left != null) p.left.parent = p;
978      // set q's right child to be p
979      q.right = p;
980      p.parent = q;
981      UpdateAfterRotateRight(p);
982    }
983   
984    static HeightTreeNode Sibling(HeightTreeNode node)
985    {
986      if (node == node.parent.left)
987        return node.parent.right;
988      else
989        return node.parent.left;
990    }
991   
992    static HeightTreeNode Sibling(HeightTreeNode node, HeightTreeNode parentNode)
993    {
994      Debug.Assert(node == null || node.parent == parentNode);
995      if (node == parentNode.left)
996        return parentNode.right;
997      else
998        return parentNode.left;
999    }
1000   
1001    static bool GetColor(HeightTreeNode node)
1002    {
1003      return node != null ? node.color : BLACK;
1004    }
1005    #endregion
1006   
1007    #region Collapsing support
1008    static bool GetIsCollapedFromNode(HeightTreeNode node)
1009    {
1010      while (node != null) {
1011        if (node.IsDirectlyCollapsed)
1012          return true;
1013        node = node.parent;
1014      }
1015      return false;
1016    }
1017   
1018    internal void AddCollapsedSection(CollapsedLineSection section, int sectionLength)
1019    {
1020      AddRemoveCollapsedSection(section, sectionLength, true);
1021    }
1022   
1023    void AddRemoveCollapsedSection(CollapsedLineSection section, int sectionLength, bool add)
1024    {
1025      Debug.Assert(sectionLength > 0);
1026     
1027      HeightTreeNode node = GetNode(section.Start);
1028      // Go up in the tree.
1029      while (true) {
1030        // Mark all middle nodes as collapsed
1031        if (add)
1032          node.lineNode.AddDirectlyCollapsed(section);
1033        else
1034          node.lineNode.RemoveDirectlyCollapsed(section);
1035        sectionLength -= 1;
1036        if (sectionLength == 0) {
1037          // we are done!
1038          Debug.Assert(node.documentLine == section.End);
1039          break;
1040        }
1041        // Mark all right subtrees as collapsed.
1042        if (node.right != null) {
1043          if (node.right.totalCount < sectionLength) {
1044            if (add)
1045              node.right.AddDirectlyCollapsed(section);
1046            else
1047              node.right.RemoveDirectlyCollapsed(section);
1048            sectionLength -= node.right.totalCount;
1049          } else {
1050            // mark partially into the right subtree: go down the right subtree.
1051            AddRemoveCollapsedSectionDown(section, node.right, sectionLength, add);
1052            break;
1053          }
1054        }
1055        // go up to the next node
1056        HeightTreeNode parentNode = node.parent;
1057        Debug.Assert(parentNode != null);
1058        while (parentNode.right == node) {
1059          node = parentNode;
1060          parentNode = node.parent;
1061          Debug.Assert(parentNode != null);
1062        }
1063        node = parentNode;
1064      }
1065      UpdateAugmentedData(GetNode(section.Start), UpdateAfterChildrenChangeRecursionMode.WholeBranch);
1066      UpdateAugmentedData(GetNode(section.End), UpdateAfterChildrenChangeRecursionMode.WholeBranch);
1067    }
1068   
1069    static void AddRemoveCollapsedSectionDown(CollapsedLineSection section, HeightTreeNode node, int sectionLength, bool add)
1070    {
1071      while (true) {
1072        if (node.left != null) {
1073          if (node.left.totalCount < sectionLength) {
1074            // mark left subtree
1075            if (add)
1076              node.left.AddDirectlyCollapsed(section);
1077            else
1078              node.left.RemoveDirectlyCollapsed(section);
1079            sectionLength -= node.left.totalCount;
1080          } else {
1081            // mark only inside the left subtree
1082            node = node.left;
1083            Debug.Assert(node != null);
1084            continue;
1085          }
1086        }
1087        if (add)
1088          node.lineNode.AddDirectlyCollapsed(section);
1089        else
1090          node.lineNode.RemoveDirectlyCollapsed(section);
1091        sectionLength -= 1;
1092        if (sectionLength == 0) {
1093          // done!
1094          Debug.Assert(node.documentLine == section.End);
1095          break;
1096        }
1097        // mark inside right subtree:
1098        node = node.right;
1099        Debug.Assert(node != null);
1100      }
1101    }
1102   
1103    public void Uncollapse(CollapsedLineSection section)
1104    {
1105      int sectionLength = section.End.LineNumber - section.Start.LineNumber + 1;
1106      AddRemoveCollapsedSection(section, sectionLength, false);
1107      // do not call CheckProperties() in here - Uncollapse is also called during line removals
1108    }
1109    #endregion
1110  }
1111}
Note: See TracBrowser for help on using the repository browser.