Last-Modified: Sat, 01 Aug 2026 20:16:34 GMT Expires: Tue, 29 Jul 2036 20:16:34 GMT RealTimeGraphExReachCircle.cs « ReachGraphs « RealTimeGraphEx « SideChains « Visual_Studio « Software - Tango - Twine softwares
aboutsummaryrefslogtreecommitdiffstats
path: root/Software/Visual_Studio/SideChains/RealTimeGraphEx/ReachGraphs/RealTimeGraphExReachCircle.cs
blob: 0e1a95b5bac248c1ab467942c57c67fcea71f6bb (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
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295

using RealTimeGraphEx.Controllers;
using System;
using System.Collections.Generic;
using System.Collections.ObjectModel;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Windows;
using System.Windows.Media;
using System.Windows.Media.Animation;
using System.Windows.Shapes;
using System.Windows.Threading;

namespace RealTimeGraphEx.ReachGraphs
{
    public class RealTimeGraphExReachCircle : RealTimeGraphExBase
    {
        #region Protected Fields

        protected int updateCounter;
        protected Ellipse ellipse;
        protected double lastValue;

        #endregion

        #region Cross Thread Fields

        protected Brush _stroke;
        protected Brush _fill;
        protected GraphController _graphController;

        #endregion

        #region Properties

        /// <summary>
        /// Gets or sets the graph strokes color.
        /// </summary>
        public Brush Stroke
        {
            get { return (Brush)GetValue(StrokeProperty); }
            set { SetValue(StrokeProperty, value); }
        }
        public static readonly DependencyProperty StrokeProperty =
            DependencyProperty.Register("Stroke", typeof(Brush), typeof(RealTimeGraphExReachCircle), new PropertyMetadata(Brushes.Black, new PropertyChangedCallback(CrossModelChanged)));

        /// <summary>
        /// Gets or sets the graph fill color.
        /// </summary>
        public Brush Fill
        {
            get { return (Brush)GetValue(FillProperty); }
            set { SetValue(FillProperty, value); }
        }
        public static readonly DependencyProperty FillProperty =
            DependencyProperty.Register("Fill", typeof(Brush), typeof(RealTimeGraphExReachCircle), new PropertyMetadata(Brushes.Gray, new PropertyChangedCallback(CrossModelChanged)));

        /// <summary>
        /// Gets or sets the IDataSeries used to push data points to the graph.
        /// </summary>
        public GraphController Controller
        {
            get { return (GraphController)GetValue(ControllerProperty); }
            set { SetValue(ControllerProperty, value); }
        }
        public static readonly DependencyProperty ControllerProperty =
            DependencyProperty.Register("Controller", typeof(GraphController), typeof(RealTimeGraphExReachCircle), new PropertyMetadata(null, new PropertyChangedCallback(GraphControllerChanged)));
        private static void GraphControllerChanged(DependencyObject d, DependencyPropertyChangedEventArgs e)
        {
            var control = d as RealTimeGraphExReachCircle;

            if (control.Controller != null)
            {
                control.Controller.RegisterMethods(control.ClearGraph, control.StartPushThread, control.SetPaused, control.ChangeRenderMode, null);
                control._graphController = control.Controller;
            }
        }

        /// <summary>
        /// Gets or sets the collection of VU range data determines how to fill the VU graph.
        /// </summary>
        public ObservableCollection<Models.RangeData> Ranges
        {
            get { return (ObservableCollection<Models.RangeData>)GetValue(RangesProperty); }
            set { SetValue(RangesProperty, value); }
        }
        public static readonly DependencyProperty RangesProperty =
            DependencyProperty.Register("Ranges", typeof(ObservableCollection<Models.RangeData>), typeof(RealTimeGraphExReachCircle), new PropertyMetadata(null));

        /// <summary>
        /// Gets or sets whether to animate the circle when when it's value doens not change.
        /// </summary>
        public bool Animate
        {
            get { return (bool)GetValue(AnimateProperty); }
            set { SetValue(AnimateProperty, value); }
        }
        public static readonly DependencyProperty AnimateProperty =
            DependencyProperty.Register("Animate", typeof(bool), typeof(RealTimeGraphExReachCircle), new PropertyMetadata(false));

        /// <summary>
        /// Gets or sets the height value to animate when the Animate property is set to true.
        /// </summary>
        public double AnimationAmount
        {
            get { return (double)GetValue(AnimationAmountProperty); }
            set { SetValue(AnimationAmountProperty, value); }
        }
        public static readonly DependencyProperty AnimationAmountProperty =
            DependencyProperty.Register("AnimationAmount", typeof(double), typeof(RealTimeGraphExReachCircle), new PropertyMetadata(10.0));

        /// <summary>
        /// Gets or sets the duration of the animation when the Animate property is set to true.
        /// </summary>
        public Duration AnimationDuration
        {
            get { return (Duration)GetValue(AnimationDurationProperty); }
            set { SetValue(AnimationDurationProperty, value); }
        }
        public static readonly DependencyProperty AnimationDurationProperty =
            DependencyProperty.Register("AnimationDuration", typeof(Duration), typeof(RealTimeGraphExReachCircle), new PropertyMetadata(new Duration(TimeSpan.FromMilliseconds(500))));



        #endregion

        #region Constructors

        public RealTimeGraphExReachCircle()
            : base()
        {
            Ranges = new ObservableCollection<Models.RangeData>();
        }

        #endregion

        #region Override Methods

        protected override void Initialize()
        {
            base.Initialize();

            if (ellipse == null)
            {
                ellipse = new Ellipse() { Tag = "Default" };
                ellipse.Height = 0;
            }

            gridLinesAndImageWrapperGrid.Children.Remove(img);

            if (!gridLinesAndImageWrapperGrid.Children.Contains(ellipse))
            {
                gridLinesAndImageWrapperGrid.Children.Add(ellipse);
            }

            //TODO: Base on developer selection vertical/horizontal VU.
            ellipse.HorizontalAlignment = System.Windows.HorizontalAlignment.Center;
            ellipse.VerticalAlignment = System.Windows.VerticalAlignment.Center;
        }

        protected override void OnSetCrossThreadFields()
        {
            base.OnSetCrossThreadFields();

            this.Dispatcher.Invoke(() =>
            {
                _graphController = Controller;
                _stroke = Stroke;
                _fill = Fill;

                if (ellipse.Tag != null && ellipse.Tag.ToString() == "Default")
                {
                    ellipse.Fill = Fill;
                    ellipse.Stroke = Stroke;
                }

                if (_graphController != null && _graphController.dataSeries != null && _graphController.dataSeries.useFillandStroke)
                {
                    ellipse.Fill = _graphController.dataSeries.fill;
                    ellipse.Stroke = _graphController.dataSeries.stroke;
                }

            }, DispatcherPriority.Send);
        }

        protected override void OnClearGraph()
        {
            base.OnClearGraph();

            this.Dispatcher.Invoke(() =>
            {
                ellipse.BeginAnimation(WidthProperty, null);
                ellipse.BeginAnimation(HeightProperty, null);
                ellipse.Height = 0;
                ellipse.Width = 0;
            });
        }

        protected internal override void OnRenderGraph()
        {
            if (_graphController != null && _graphController.dataSeries.Points != null && _graphController.dataSeries.Points.Count > 0 && _width > 1 && _height > 1)
            {
                double value = _graphController.dataSeries.Points[_graphController.dataSeries.Points.Count - 1]; //Get last value.

                if (value == lastValue)
                {
                    _graphController.ClearPoints();
                    return;
                }

                lastValue = value;

                double valueHeightPrecentage = ConvertYToImageY(value);
                double valueWidthPrecentage = ConvertYToImageX(value);

                updateCounter++;

                if (updateCounter >= 1 && !_isPaused)
                {
                    updateCounter = 0;
                    OnDrawVisuals(valueHeightPrecentage, valueWidthPrecentage);
                }

                _graphController.ClearPoints();
            }
        }

        #endregion

        #region Virtual Methods

        protected virtual void OnDrawVisuals(double valueHeightPrecentage, double valueWidthPrecentage)
        {
            this.Dispatcher.Invoke(() =>
            {

                ellipse.BeginAnimation(WidthProperty, null);
                ellipse.BeginAnimation(HeightProperty, null);

                ellipse.Height = valueHeightPrecentage;
                ellipse.Width = valueWidthPrecentage;

                ellipse.Fill = GetEllipseBrush();

                if (Animate)
                {
                    DoubleAnimation ani = new DoubleAnimation();
                    ani.CurrentTimeInvalidated += (x, y) =>
                    {
                        ellipse.Fill = GetEllipseBrush();
                    };
                    ani.To = ellipse.Width - AnimationAmount;
                    ani.From = ellipse.Width;
                    ani.RepeatBehavior = RepeatBehavior.Forever;
                    ani.AutoReverse = true;
                    ani.Duration = AnimationDuration;

                    ellipse.BeginAnimation(WidthProperty, ani);
                    ellipse.BeginAnimation(HeightProperty, ani);
                }
            });
        }

        private Brush GetEllipseBrush()
        {
            if (Ranges != null && Ranges.Count > 0)
            {
                RadialGradientBrush rangesBrush = new RadialGradientBrush();
                rangesBrush.MappingMode = BrushMappingMode.Absolute;
                rangesBrush.Center = new Point(ellipse.Width / 2, ellipse.Height / 2);
                rangesBrush.GradientOrigin = new Point(ellipse.Width / 2, ellipse.Height / 2);
                rangesBrush.RadiusX = _width;
                rangesBrush.RadiusY = _height;

                for (int i = Ranges.Count - 1; i >= 0; i--)
                {
                    var range = Ranges[i];

                    double rangeValuePrecentage = ConvertYToImageY(range.Value);

                    GradientStop stop = new GradientStop();
                    stop.Color = range.Color;
                    stop.Offset = ((rangeValuePrecentage * 100) / _height) / 100;
                    rangesBrush.GradientStops.Add(stop);
                }

                return rangesBrush;
            }

            return Fill;
        }

        #endregion
    }
}
generated by cgit v1.3.1 (git 2.54.0) at 2026-08-01 20:16:34 +0000
n class="w"> throw new ArgumentNullException("item"); if (item.ownerTree != null) throw new ArgumentException("The segment is already added to a SegmentCollection."); AddSegment(item); } void ISegmentTree.Add(TextSegment s) { AddSegment(s); } void AddSegment(TextSegment node) { int insertionOffset = node.StartOffset; node.distanceToMaxEnd = node.segmentLength; if (root == null) { root = node; node.totalNodeLength = node.nodeLength; } else if (insertionOffset >= root.totalNodeLength) { // append segment at end of tree node.nodeLength = node.totalNodeLength = insertionOffset - root.totalNodeLength; InsertAsRight(root.RightMost, node); } else { // insert in middle of tree TextSegment n = FindNode(ref insertionOffset); Debug.Assert(insertionOffset < n.nodeLength); // split node segment 'n' at offset node.totalNodeLength = node.nodeLength = insertionOffset; n.nodeLength -= insertionOffset; InsertBefore(n, node); } node.ownerTree = this; count++; CheckProperties(); } void InsertBefore(TextSegment node, TextSegment newNode) { if (node.left == null) { InsertAsLeft(node, newNode); } else { InsertAsRight(node.left.RightMost, newNode); } } #endregion #region GetNextSegment / GetPreviousSegment /// <summary> /// Gets the next segment after the specified segment. /// Segments are sorted by their start offset. /// Returns null if segment is the last segment. /// </summary> public T GetNextSegment(T segment) { if (!Contains(segment)) throw new ArgumentException("segment is not inside the segment tree"); return (T)segment.Successor; } /// <summary> /// Gets the previous segment before the specified segment. /// Segments are sorted by their start offset. /// Returns null if segment is the first segment. /// </summary> public T GetPreviousSegment(T segment) { if (!Contains(segment)) throw new ArgumentException("segment is not inside the segment tree"); return (T)segment.Predecessor; } #endregion #region FirstSegment/LastSegment /// <summary> /// Returns the first segment in the collection or null, if the collection is empty. /// </summary> public T FirstSegment { get { return root == null ? null : (T)root.LeftMost; } } /// <summary> /// Returns the last segment in the collection or null, if the collection is empty. /// </summary> public T LastSegment { get { return root == null ? null : (T)root.RightMost; } } #endregion #region FindFirstSegmentWithStartAfter /// <summary> /// Gets the first segment with a start offset greater or equal to <paramref name="startOffset"/>. /// Returns null if no such segment is found. /// </summary> public T FindFirstSegmentWithStartAfter(int startOffset) { if (root == null) return null; if (startOffset <= 0) return (T)root.LeftMost; TextSegment s = FindNode(ref startOffset); // startOffset means that the previous segment is starting at the offset we were looking for while (startOffset == 0) { TextSegment p = (s == null) ? root.RightMost : s.Predecessor; // There must always be a predecessor: if we were looking for the first node, we would have already // returned it as root.LeftMost above. Debug.Assert(p != null); startOffset += p.nodeLength; s = p; } return (T)s; } /// <summary> /// Finds the node at the specified offset. /// After the method has run, offset is relative to the beginning of the returned node. /// </summary> TextSegment FindNode(ref int offset) { TextSegment n = root; while (true) { if (n.left != null) { if (offset < n.left.totalNodeLength) { n = n.left; // descend into left subtree continue; } else { offset -= n.left.totalNodeLength; // skip left subtree } } if (offset < n.nodeLength) { return n; // found correct node } else { offset -= n.nodeLength; // skip this node } if (n.right != null) { n = n.right; // descend into right subtree } else { // didn't find any node containing the offset return null; } } } #endregion #region FindOverlappingSegments /// <summary> /// Finds all segments that contain the given offset. /// (StartOffset &lt;= offset &lt;= EndOffset) /// Segments are returned in the order given by GetNextSegment/GetPreviousSegment. /// </summary> /// <returns>Returns a new collection containing the results of the query. /// This means it is safe to modify the TextSegmentCollection while iterating through the result collection.</returns> public ReadOnlyCollection<T> FindSegmentsContaining(int offset) { return FindOverlappingSegments(offset, 0); } /// <summary> /// Finds all segments that overlap with the given segment (including touching segments). /// </summary> /// <returns>Returns a new collection containing the results of the query. /// This means it is safe to modify the TextSegmentCollection while iterating through the result collection.</returns> public ReadOnlyCollection<T> FindOverlappingSegments(ISegment segment) { if (segment == null) throw new ArgumentNullException("segment"); return FindOverlappingSegments(segment.Offset, segment.Length); } /// <summary> /// Finds all segments that overlap with the given segment (including touching segments). /// Segments are returned in the order given by GetNextSegment/GetPreviousSegment. /// </summary> /// <returns>Returns a new collection containing the results of the query. /// This means it is safe to modify the TextSegmentCollection while iterating through the result collection.</returns> public ReadOnlyCollection<T> FindOverlappingSegments(int offset, int length) { ThrowUtil.CheckNotNegative(length, "length"); List<T> results = new List<T>(); if (root != null) { FindOverlappingSegments(results, root, offset, offset + length); } return results.AsReadOnly(); } void FindOverlappingSegments(List<T> results, TextSegment node, int low, int high) { // low and high are relative to node.LeftMost startpos (not node.LeftMost.Offset) if (high < 0) { // node is irrelevant for search because all intervals in node are after high return; } // find values relative to node.Offset int nodeLow = low - node.nodeLength; int nodeHigh = high - node.nodeLength; if (node.left != null) { nodeLow -= node.left.totalNodeLength; nodeHigh -= node.left.totalNodeLength; } if (node.distanceToMaxEnd < nodeLow) { // node is irrelevant for search because all intervals in node are before low return; } if (node.left != null) FindOverlappingSegments(results, node.left, low, high); if (nodeHigh < 0) { // node and everything in node.right is before low return; } if (nodeLow <= node.segmentLength) { results.Add((T)node); } if (node.right != null) FindOverlappingSegments(results, node.right, nodeLow, nodeHigh); } #endregion #region UpdateAugmentedData void UpdateAugmentedData(TextSegment node) { int totalLength = node.nodeLength; int distanceToMaxEnd = node.segmentLength; if (node.left != null) { totalLength += node.left.totalNodeLength; int leftDTME = node.left.distanceToMaxEnd; // dtme is relative, so convert it to the coordinates of node: if (node.left.right != null) leftDTME -= node.left.right.totalNodeLength; leftDTME -= node.nodeLength; if (leftDTME > distanceToMaxEnd) distanceToMaxEnd = leftDTME; } if (node.right != null) { totalLength += node.right.totalNodeLength; int rightDTME = node.right.distanceToMaxEnd; // dtme is relative, so convert it to the coordinates of node: rightDTME += node.right.nodeLength; if (node.right.left != null) rightDTME += node.right.left.totalNodeLength; if (rightDTME > distanceToMaxEnd) distanceToMaxEnd = rightDTME; } if (node.totalNodeLength != totalLength || node.distanceToMaxEnd != distanceToMaxEnd) { node.totalNodeLength = totalLength; node.distanceToMaxEnd = distanceToMaxEnd; if (node.parent != null) UpdateAugmentedData(node.parent); } } void ISegmentTree.UpdateAugmentedData(TextSegment node) { UpdateAugmentedData(node); } #endregion #region Remove /// <summary> /// Removes the specified segment from the tree. This will cause the segment to not update /// anymore when the document changes. /// </summary> public bool Remove(T item) { if (!Contains(item)) return false; RemoveSegment(item); return true; } void ISegmentTree.Remove(TextSegment s) { RemoveSegment(s); } void RemoveSegment(TextSegment s) { int oldOffset = s.StartOffset; TextSegment successor = s.Successor; if (successor != null) successor.nodeLength += s.nodeLength; RemoveNode(s); if (successor != null) UpdateAugmentedData(successor); Disconnect(s, oldOffset); CheckProperties(); } void Disconnect(TextSegment s, int offset) { s.left = s.right = s.parent = null; s.ownerTree = null; s.nodeLength = offset; count--; } /// <summary> /// Removes all segments from the tree. /// </summary> public void Clear() { T[] segments = this.ToArray(); root = null; int offset = 0; foreach (TextSegment s in segments) { offset += s.nodeLength; Disconnect(s, offset); } CheckProperties(); } #endregion #region CheckProperties [Conditional("DATACONSISTENCYTEST")] internal void CheckProperties() { #if DEBUG if (root != null) { CheckProperties(root); // check red-black property: int blackCount = -1; CheckNodeProperties(root, null, RED, 0, ref blackCount); } int expectedCount = 0; // we cannot trust LINQ not to call ICollection.Count, so we need this loop // to count the elements in the tree using (IEnumerator<T> en = GetEnumerator()) { while (en.MoveNext()) expectedCount++; } Debug.Assert(count == expectedCount); #endif } #if DEBUG void CheckProperties(TextSegment node) { int totalLength = node.nodeLength; int distanceToMaxEnd = node.segmentLength; if (node.left != null) { CheckProperties(node.left); totalLength += node.left.totalNodeLength; distanceToMaxEnd = Math.Max(distanceToMaxEnd, node.left.distanceToMaxEnd + node.left.StartOffset - node.StartOffset); } if (node.right != null) { CheckProperties(node.right); totalLength += node.right.totalNodeLength; distanceToMaxEnd = Math.Max(distanceToMaxEnd, node.right.distanceToMaxEnd + node.right.StartOffset - node.StartOffset); } Debug.Assert(node.totalNodeLength == totalLength); Debug.Assert(node.distanceToMaxEnd == distanceToMaxEnd); } /* 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(TextSegment node, TextSegment 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); } static void AppendTreeToString(TextSegment node, StringBuilder b, int indent) { if (node.color == RED) b.Append("RED "); else b.Append("BLACK "); b.AppendLine(node.ToString() + node.ToDebugString()); 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 internal string GetTreeAsString() { #if DEBUG StringBuilder b = new StringBuilder(); if (root != null) AppendTreeToString(root, b, 0); return b.ToString(); #else return "Not available in release build."; #endif } #endregion #region Red/Black Tree internal const bool RED = true; internal const bool BLACK = false; void InsertAsLeft(TextSegment parentNode, TextSegment newNode) { Debug.Assert(parentNode.left == null); parentNode.left = newNode; newNode.parent = parentNode; newNode.color = RED; UpdateAugmentedData(parentNode); FixTreeOnInsert(newNode); } void InsertAsRight(TextSegment parentNode, TextSegment newNode) { Debug.Assert(parentNode.right == null); parentNode.right = newNode; newNode.parent = parentNode; newNode.color = RED; UpdateAugmentedData(parentNode); FixTreeOnInsert(newNode); } void FixTreeOnInsert(TextSegment 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); TextSegment 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 TextSegment grandparentNode = parentNode.parent; TextSegment 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(TextSegment removedNode) { if (removedNode.left != null && removedNode.right != null) { // replace removedNode with it's in-order successor TextSegment leftMost = removedNode.right.LeftMost; RemoveNode(leftMost); // remove leftMost from its current location // and overwrite the removedNode with it ReplaceNode(removedNode, leftMost); leftMost.left = removedNode.left; if (leftMost.left != null) leftMost.left.parent = leftMost; leftMost.right = removedNode.right; if (leftMost.right != null) leftMost.right.parent = leftMost; leftMost.color = removedNode.color; UpdateAugmentedData(leftMost); if (leftMost.parent != null) UpdateAugmentedData(leftMost.parent); return; } // now either removedNode.left or removedNode.right is null // get the remaining child TextSegment parentNode = removedNode.parent; TextSegment childNode = removedNode.left ?? removedNode.right; ReplaceNode(removedNode, childNode); if (parentNode != null) UpdateAugmentedData(parentNode); if (removedNode.color == BLACK) { if (childNode != null && childNode.color == RED) { childNode.color = BLACK; } else { FixTreeOnDelete(childNode, parentNode); } } } void FixTreeOnDelete(TextSegment node, TextSegment parentNode) { Debug.Assert(node == null || node.parent == parentNode); if (parentNode == null) return; // warning: node may be null TextSegment 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(TextSegment replacedNode, TextSegment 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(TextSegment p) { // let q be p's right child TextSegment 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; UpdateAugmentedData(p); UpdateAugmentedData(q); } void RotateRight(TextSegment p) { // let q be p's left child TextSegment 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; UpdateAugmentedData(p); UpdateAugmentedData(q); } static TextSegment Sibling(TextSegment node) { if (node == node.parent.left) return node.parent.right; else return node.parent.left; } static TextSegment Sibling(TextSegment node, TextSegment parentNode) { Debug.Assert(node == null || node.parent == parentNode); if (node == parentNode.left) return parentNode.right; else return parentNode.left; } static bool GetColor(TextSegment node) { return node != null ? node.color : BLACK; } #endregion #region ICollection<T> implementation /// <summary> /// Gets the number of segments in the tree. /// </summary> public int Count { get { return count; } } bool ICollection<T>.IsReadOnly { get { return false; } } /// <summary> /// Gets whether this tree contains the specified item. /// </summary> public bool Contains(T item) { return item != null && item.ownerTree == this; } /// <summary> /// Copies all segments in this SegmentTree to the specified array. /// </summary> public void CopyTo(T[] array, int arrayIndex) { if (array == null) throw new ArgumentNullException("array"); if (array.Length < this.Count) throw new ArgumentException("The array is too small", "array"); if (arrayIndex < 0 || arrayIndex + count > array.Length) throw new ArgumentOutOfRangeException("arrayIndex", arrayIndex, "Value must be between 0 and " + (array.Length - count)); foreach (T s in this) { array[arrayIndex++] = s; } } /// <summary> /// Gets an enumerator to enumerate the segments. /// </summary> public IEnumerator<T> GetEnumerator() { if (root != null) { TextSegment current = root.LeftMost; while (current != null) { yield return (T)current; // TODO: check if collection was modified during enumeration current = current.Successor; } } } System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() { return this.GetEnumerator(); } #endregion } }
generated by cgit v1.3.1 (git 2.54.0) at 2026-08-01 20:16:34 +0000