aboutsummaryrefslogtreecommitdiffstats
path: root/Software/Visual_Studio/Scripting/Tango.Scripting.Editors/Rendering/HeightTree.cs
blob: 6751af8faadbfdff809fa20aa6f20b6c0f9d47a7 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
pre { line-height: 125%; }
td.linenos .normal { color: inherit; background-color: transparent; padding-left: 5px; padding-right: 5px; }
span.linenos { color: inherit; background-color: transparent; padding-left: 5px; padding-right: 5px; }
td.linenos .special { color: #000000; background-color: #ffffc0; padding-left: 5px; padding-right: 5px; }
span.linenos.special { color: #000000; background-color: #ffffc0; padding-left: 5px; padding-right: 5px; }
.highlight .hll { background-color: #ffffcc }
.highlight .c { color: #888888 } /* Comment */
.highlight .err { color: #a61717; background-color: #e3d2d2 } /* Error */
.highlight .k { color: #008800; font-weight: bold } /* Keyword */
.highlight .ch { color: #888888 } /* Comment.Hashbang */
.highlight .cm { color: #888888 } /* Comment.Multiline */
.highlight .cp { color: #cc0000; font-weight: bold } /* Comment.Preproc */
.highlight .cpf { color: #888888 } /* Comment.PreprocFile */
.highlight .c1 { color: #888888 } /* Comment.Single */
.highlight .cs { color: #cc0000; font-weight: bold; background-color: #fff0f0 } /* Comment.Special */
.highlight .gd { color: #000000; background-color: #ffdddd } /* Generic.Deleted */
.highlight .ge { font-style: italic } /* Generic.Emph */
.highlight .ges { font-weight: bold; font-style: italic } /* Generic.EmphStrong */
.highlight .gr { color: #aa0000 } /* Generic.Error */
.highlight .gh { color: #333333 } /* Generic.Heading */
.highlight .gi { color: #000000; background-color: #ddffdd } /* Generic.Inserted */
.highlight .go { color: #888888 } /* Generic.Output */
.highlight .gp { color: #555555 } /* Generic.Prompt */
.highlight .gs { font-weight: bold } /* Generic.Strong */
.highlight .gu { color: #666666 } /* Generic.Subheading */
.highlight .gt { color: #aa0000 } /* Generic.Traceback */
.highlight .kc { color: #008800; font-weight: bold } /* Keyword.Constant */
.highlight .kd { color: #008800; font-weight: bold } /* Keyword.Declaration */
.highlight .kn { color: #008800; font-weight: bold } /* Keyword.Namespace */
.highlight .kp { color: #008800 } /* Keyword.Pseudo */
.highlight .kr { color: #008800; font-weight: bold } /* Keyword.Reserved */
.highlight .kt { color: #888888; font-weight: bold } /* Keyword.Type */
.highlight .m { color: #0000DD; font-weight: bold } /* Literal.Number */
.highlight .s { color: #dd2200; background-color: #fff0f0 } /* Literal.String */
.highlight .na { color: #336699 } /* Name.Attribute */
.highlight .nb { color: #003388 } /* Name.Builtin */
.highlight .nc { color: #bb0066; font-weight: bold } /* Name.Class */
.highlight .no { color: #003366; font-weight: bold } /* Name.Constant */
.highlight .nd { color: #555555 } /* Name.Decorator */
.highlight .ne { color: #bb0066; font-weight: bold } /* Name.Exception */
.highlight .nf { color: #0066bb; font-weight: bold } /* Name.Function */
.highlight .nl { color: #336699; font-style: italic } /* Name.Label */
.highlight .nn { color: #bb0066; font-weight: bold } /* Name.Namespace */
.highlight .py { color: #336699; font-weight: bold } /* Name.Property */
.highlight .nt { color: #bb0066; font-weight: bold } /* Name.Tag */
.highlight .nv { color: #336699 } /* Name.Variable */
.highlight .ow { color: #008800 } /* Operator.Word */
.highlight .w { color: #bbbbbb } /* Text.Whitespace */
.highlight .mb { color: #0000DD; font-weight: bold } /* Literal.Number.Bin */
.highlight .mf { color: #0000DD; font-weight: bold } /* Literal.Number.Float */
.highlight .mh { color: #0000DD; font-weight: bold } /* Literal.Number.Hex */
.highlight .mi { color: #0000DD; font-weight: bold } /* Literal.Number.Integer */
.highlight .mo { color: #0000DD; font-weight: bold } /* Literal.Number.Oct */
.highlight .sa { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Affix */
.highlight .sb { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Backtick */
.highlight .sc { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Char */
.highlight .dl { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Delimiter */
.highlight .sd { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Doc */
.highlight .s2 { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Double */
.highlight .se { color: #0044dd; background-color: #fff0f0 } /* Literal.String.Escape */
.highlight .sh { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Heredoc */
.highlight .si { color: #3333bb; background-color: #fff0f0 } /* Literal.String.Interpol */
.highlight .sx { color: #22bb22; background-color: #f0fff0 } /* Literal.String.Other */
.highlight .sr { color: #008800; background-color: #fff0ff } /* Literal.String.Regex */
.highlight .s1 { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Single */
.highlight .ss { color: #aa6600; background-color: #fff0f0 } /* Literal.String.Symbol */
.highlight .bp { color: #003388 } /* Name.Builtin.Pseudo */
.highlight .fm { color: #0066bb; font-weight: bold } /* Name.Function.Magic */
.highlight .vc { color: #336699 } /* Name.Variable.Class */
.highlight .vg { color: #dd7700 } /* Name.Variable.Global */
.highlight .vi { color: #3333bb } /* Name.Variable.Instance */
.highlight .vm { color: #336699 } /* Name.Variable.Magic */
.highlight .il { color: #0000DD; font-weight: bold } /* Literal.Number.Integer.Long */
using Microsoft.Win32;
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using Tango.BL.Entities;
using Tango.Core.Commands;
using Tango.MachineStudio.Common.Notifications;
using Tango.MachineStudio.Common.Tup;
using Tango.SharedUI;

namespace Tango.MachineStudio.MachineDesigner.ViewModels
{
    public class TupViewVM : ViewModel
    {
        private INotificationProvider _notification;

        private String _latestVersion;
        public String LatestVersion
        {
            get { return _latestVersion; }
            set { _latestVersion = value; RaisePropertyChangedAuto(); }
        }

        private Machine _machine;
        public Machine Machine
        {
            get { return _machine; }
            set { _machine = value; RaisePropertyChangedAuto(); }
        }

        private String _filePath;
        public String FilePath
        {
            get { return _filePath; }
            set { _filePath = value; RaisePropertyChangedAuto(); InvalidateRelayCommands(); }
        }

        private TupFileBuilderProgressEventArgs _progress;
        public TupFileBuilderProgressEventArgs Progress
        {
            get { return _progress; }
            set { _progress = value; RaisePropertyChangedAuto(); }
        }

        public RelayCommand CreateTupFileCommand { get; set; }

        public RelayCommand SelectFileCommand { get; set; }

        public TupViewVM()
        {

        }

        public TupViewVM(INotificationProvider notification) : this()
        {
            _notification = notification;
            CreateTupFileCommand = new RelayCommand(CreateTupFile, () => FilePath != null && IsFree);
            SelectFileCommand = new RelayCommand(SelectFile);
        }

        public void Init(Machine machine)
        {
            Machine = machine;
            DisplayLatestPPCVersion();
        }

        private async void DisplayLatestPPCVersion()
        {
            TupFileBuilder builder = new TupFileBuilder();

            try
            {
                LatestVersion = await builder.GetLatestPPCVersion(Machine.SerialNumber);
            }
            catch (Exception ex)
            {
                LogManager.Log(ex, "Error retrieving latest PPC version.");
                await Task.Delay(5000);
                DisplayLatestPPCVersion();
            }
        }

        private void SelectFile()
        {
            SaveFileDialog dlg = new SaveFileDialog();
            dlg.Title = "Select package location";
            dlg.Filter = "Tango Update Package Files|*.tup";
            dlg.DefaultExt = ".tup";
            dlg.FileName = LatestVersion == null ? $"{Machine.SerialNumber}_Update_{DateTime.Now.Date.ToFileName()}.tup" : $"{Machine.SerialNumber}_Update_{DateTime.Now.Date.ToFileName()}_v{LatestVersion}.tup";

            if (dlg.ShowDialog().Value)
            {
                FilePath = dlg.FileName;
            }
        }

        private async void CreateTupFile()
        {
            try
            {
                LogManager.Log($"Generating TUP file to '{FilePath}'...");

                IsFree = false;
                TupFileBuilder builder = new TupFileBuilder();
                builder.Progress += Builder_Progress;
                await builder.Build(Machine.SerialNumber, FilePath);

                LogManager.Log("TUP file generated successfully.");
                _notification.ShowInfo("Tango update package created successfuly.");
            }
            catch (Exception ex)
            {
                LogManager.Log(ex, "Error generating tup file.");
                _notification.ShowError($"An error occurred while generating the .tup file.\n{ex.FlattenMessage()}");
            }
            finally
            {
                IsFree = true;
            }
        }

        private void Builder_Progress(object sender, TupFileBuilderProgressEventArgs e)
        {
            Progress = e;
        }
    }
}
6'>906 907 908 909 910 911 912 913 914 915 916 917 918 919 920 921 922 923 924 925 926 927 928 929 930 931 932 933 934 935 936 937 938 939 940 941 942 943 944 945 946 947 948 949 950 951 952 953 954 955 956 957 958 959 960 961 962 963 964 965 966 967 968 969 970 971 972 973 974 975 976 977 978 979 980 981 982 983 984 985 986 987 988 989 990 991 992 993 994 995 996 997 998 999 1000 1001 1002 1003 1004 1005 1006 1007 1008 1009 1010 1011 1012 1013 1014 1015 1016 1017 1018 1019 1020 1021 1022 1023 1024 1025 1026 1027 1028 1029 1030 1031 1032 1033 1034 1035 1036 1037 1038 1039 1040 1041 1042 1043 1044 1045 1046 1047 1048 1049 1050 1051 1052 1053 1054 1055 1056 1057 1058 1059 1060 1061 1062 1063 1064 1065 1066 1067 1068 1069 1070 1071 1072 1073 1074 1075 1076 1077 1078 1079 1080 1081 1082 1083 1084 1085 1086 1087 1088 1089 1090 1091 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
{
	/// <summary>
	/// Red-black tree similar to DocumentLineTree, augmented with collapsing and height data.
	/// </summary>
	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<CollapsedSection> 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)
		{
		}
		
		/// <summary>
		/// Rebuild the tree, in O(n).
		/// </summary>
		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
		}
		
		/// <summary>
		/// build a tree from a list of nodes
		/// </summary>
		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<HeightTreeNode> nodesToCheckForMerging;
		
		void BeginRemoval()
		{
			Debug.Assert(!inRemoval);
			if (nodesToCheckForMerging == null) {
				nodesToCheckForMerging = new List<HeightTreeNode>();
			}
			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);
		}
		
		/// <summary>
		/// Collapses the specified text section.
		/// Runtime: O(log n)
		/// </summary>
		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<HeightTreeNode> AllNodes {
			get {
				if (root != null) {
					HeightTreeNode node = root.LeftMost;
					while (node != null) {
						yield return node;
						node = node.Successor;
					}
				}
			}
		}
		
		internal IEnumerable<CollapsedLineSection> GetAllCollapsedSections()
		{
			List<CollapsedLineSection> emptyCSList = new List<CollapsedLineSection>();
			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));
		}
		
		/// <summary>
		/// Checks that all elements in list1 are contained in list2.
		/// </summary>
		static void CheckAllContainedIn(IEnumerable<CollapsedLineSection> list1, ICollection<CollapsedLineSection> list2)
		{
			if (list1 == null) list1 = new List<CollapsedLineSection>();
			if (list2 == null) list2 = new List<CollapsedLineSection>();
			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
	}
}