← Back to branch summary

~ubuntu-branches/ubuntu/oneiric/monodevelop/oneiric

« back to all changes in this revision

Viewing changes to src/core/Mono.Texteditor/Mono.TextEditor/SegmentTree.cs

  • Committer: Bazaar Package Importer
  • Author(s): Jo Shields
  • Date: 2011-06-27 17:03:13 UTC
  • mto: (1.8.1 upstream)
  • mto: This revision was merged to the branch mainline in revision 54.
  • Revision ID: james.westby@ubuntu.com-20110627170313-6cvz3s19x6e9hqe9
Import upstream version 2.5.92+dfsg

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/core/Mono.Texteditor/Mono.TextEditor/SegmentTree.cs
 
1
// 
 
2
// SegmentTree.cs
 
3
//  
 
4
// Author:
 
5
//       mkrueger <mkrueger@novell.com>
 
6
// 
 
7
// Copyright (c) 2011 Novell, Inc (http://www.novell.com)
 
8
// 
 
9
// Permission is hereby granted, free of charge, to any person obtaining a copy
 
10
// of this software and associated documentation files (the "Software"), to deal
 
11
// in the Software without restriction, including without limitation the rights
 
12
// to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 
13
// copies of the Software, and to permit persons to whom the Software is
 
14
// furnished to do so, subject to the following conditions:
 
15
// 
 
16
// The above copyright notice and this permission notice shall be included in
 
17
// all copies or substantial portions of the Software.
 
18
// 
 
19
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 
20
// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 
21
// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 
22
// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 
23
// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 
24
// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
 
25
// THE SOFTWARE.
 
26
using System;
 
27
using System.Collections.Generic;
 
28
using System.Linq;
 
29
using Mono.TextEditor.Utils;
 
30
 
 
31
namespace Mono.TextEditor
 
32
{
 
33
        /// <summary>
 
34
        /// A segment tree contains overlapping segments and get all segments overlapping a segment. It's implemented as a augmented interval tree
 
35
        /// described in Cormen et al. (2001, Section 14.3: Interval trees, pp. 311–317).
 
36
        /// </summary>
 
37
        public class SegmentTree<T> : ISegmentTree where T : TreeSegment
 
38
        {
 
39
                internal readonly RedBlackTree<T> tree = new RedBlackTree<T> ();
 
40
                
 
41
                public int Count {
 
42
                        get {
 
43
                                return tree.Count;
 
44
                        }
 
45
                }
 
46
                
 
47
                public IEnumerable<T> Segments {
 
48
                        get {
 
49
                                var root = tree.Root;
 
50
                                if (root == null)
 
51
                                        yield break;
 
52
                                var node = root.GetOuterLeft ();
 
53
                                while (node != null) {
 
54
                                        yield return node;
 
55
                                        node = node.GetNextNode ();
 
56
                                }
 
57
                        }
 
58
                }
 
59
                
 
60
                public void InstallListener (Document doc)
 
61
                {
 
62
                        doc.TextReplaced += UpdateOnTextReplace;
 
63
                }
 
64
 
 
65
                public void RemoveListener (Document doc)
 
66
                {
 
67
                        doc.TextReplaced -= UpdateOnTextReplace;
 
68
                }
 
69
 
 
70
                void UpdateOnTextReplace (object sender, ReplaceEventArgs e)
 
71
                {
 
72
                        if (e.Count == 0) {
 
73
                                var length = (e.Value != null ? e.Value.Length : 0);
 
74
                                foreach (var segment in GetSegmentsAt (e.Offset).Where (s => s.Offset < e.Offset && e.Offset < s.EndOffset)) {
 
75
                                        segment.Length += length;
 
76
                                        segment.UpdateAugmentedData ();
 
77
                                }
 
78
                                var node = SearchFirstSegmentWithStartAfter (e.Offset);
 
79
                                if (node != null) {
 
80
                                        node.DistanceToPrevNode += length;
 
81
                                        node.UpdateAugmentedData ();
 
82
                                }
 
83
                                return;
 
84
                        }
 
85
                        int delta = (e.Value != null ? e.Value.Length : 0) - e.Count;
 
86
                        foreach (var segment in new List<T> (GetSegmentsOverlapping (e.Offset, e.Count))) {
 
87
                                if (segment.Offset <= e.Offset) {
 
88
                                        if (segment.EndOffset >= e.Offset + e.Count) {
 
89
                                                segment.Length += delta;
 
90
                                        } else {
 
91
                                                segment.Length = e.Offset - segment.Offset;
 
92
                                        }
 
93
                                        segment.UpdateAugmentedData ();
 
94
                                        continue;
 
95
                                }
 
96
                                int remainingLength = segment.EndOffset - (e.Offset + e.Count);
 
97
                                Remove (segment);
 
98
                                
 
99
                                if (remainingLength > 0) {
 
100
                                        segment.Offset = e.Offset + e.Count;
 
101
                                        segment.Length = remainingLength;
 
102
                                        Add (segment);
 
103
                                }
 
104
                        }
 
105
 
 
106
                        var next = SearchFirstSegmentWithStartAfter (e.Offset + 1);
 
107
 
 
108
                        if (next != null) {
 
109
                                next.DistanceToPrevNode += delta;
 
110
                                next.UpdateAugmentedData ();
 
111
                        }
 
112
                }
 
113
                
 
114
                public void Add (TreeSegment node)
 
115
                {
 
116
                        if (node == null)
 
117
                                throw new ArgumentNullException ("node");
 
118
                        if (node.segmentTree != null)
 
119
                                throw new InvalidOperationException ("Node already attached.");
 
120
                        
 
121
                        node.segmentTree = this;
 
122
                        
 
123
                
 
124
                        int insertionOffset = node.Offset;
 
125
                        node.DistanceToMaxEnd = node.Length;
 
126
                        
 
127
                        if (tree.Root == null) {
 
128
                                tree.Count = 1;
 
129
                                tree.Root = (T)node;
 
130
                                node.TotalLength = node.DistanceToPrevNode;
 
131
                                return;
 
132
                        }
 
133
                        
 
134
                        if (insertionOffset < tree.Root.TotalLength) {
 
135
                                var n = SearchNode (ref insertionOffset);
 
136
                                node.TotalLength = node.DistanceToPrevNode = insertionOffset;
 
137
                                n.DistanceToPrevNode -= insertionOffset;
 
138
                                tree.InsertBefore (n, node);
 
139
                                return;
 
140
                        }
 
141
                        
 
142
                        node.DistanceToPrevNode = node.TotalLength = insertionOffset - tree.Root.TotalLength;
 
143
                        tree.InsertRight (tree.Root.GetOuterRight (), node);
 
144
                }
 
145
                
 
146
                public void Remove (TreeSegment node)
 
147
                {
 
148
                        var calculatedOffset = node.Offset;
 
149
                        var next = node.GetNextNode ();
 
150
                        if (next != null)
 
151
                                next.DistanceToPrevNode += node.DistanceToPrevNode;
 
152
                        tree.Remove (node);
 
153
                        if (next != null)
 
154
                                next.UpdateAugmentedData ();
 
155
                        node.segmentTree = null;
 
156
                        node.parent = node.left = node.right = null;
 
157
                        node.DistanceToPrevNode = calculatedOffset;
 
158
                }
 
159
                
 
160
                TreeSegment SearchFirstSegmentWithStartAfter (int startOffset)
 
161
                {
 
162
                        if (tree.Root == null)
 
163
                                return null;
 
164
                        if (startOffset <= 0)
 
165
                                return tree.Root.GetOuterLeft ();
 
166
                        var result = SearchNode (ref startOffset);
 
167
                        while (startOffset == 0) {
 
168
                                var pre = result == null ? tree.Root.GetOuterRight () : result.GetPrevNode ();
 
169
                                startOffset += pre.DistanceToPrevNode;
 
170
                                result = pre;
 
171
                        }
 
172
                        return result;
 
173
                }
 
174
                
 
175
                TreeSegment SearchNode (ref int offset)
 
176
                {
 
177
                        TreeSegment n = tree.Root;
 
178
                        while (true) {
 
179
                                if (n.left != null) {
 
180
                                        if (offset < n.left.TotalLength) {
 
181
                                                n = n.left;
 
182
                                                continue;
 
183
                                        }
 
184
                                        offset -= n.left.TotalLength;
 
185
                                }
 
186
                                if (offset < n.DistanceToPrevNode) 
 
187
                                        return n; 
 
188
                                offset -= n.DistanceToPrevNode; 
 
189
                                if (n.right == null) 
 
190
                                        return null;
 
191
                                n = n.right;
 
192
                        }
 
193
                }
 
194
                
 
195
                public IEnumerable<T> GetSegmentsAt (int offset)
 
196
                {
 
197
                        return GetSegmentsOverlapping (offset, 0);
 
198
                }
 
199
                
 
200
                public IEnumerable<T> GetSegmentsOverlapping (ISegment segment)
 
201
                {
 
202
                        if (segment == null)
 
203
                                return Enumerable.Empty<T> ();
 
204
                        return GetSegmentsOverlapping (segment.Offset, segment.Length);
 
205
                }
 
206
                
 
207
                struct Interval 
 
208
                {
 
209
                        internal TreeSegment node;
 
210
                        internal int start, end;
 
211
                        
 
212
                        public Interval (TreeSegment node,int start,int end)
 
213
                        {
 
214
                                this.node = node;
 
215
                                this.start = start;
 
216
                                this.end = end;
 
217
                        }
 
218
                }
 
219
                
 
220
                public IEnumerable<T> GetSegmentsOverlapping (int offset, int length)
 
221
                {
 
222
                        if (tree.Root == null)
 
223
                                yield break;
 
224
                        Stack<Interval> intervalStack = new Stack<Interval> ();
 
225
                        intervalStack.Push (new Interval (tree.Root, offset, offset + length));
 
226
                        while (intervalStack.Count > 0) {
 
227
                                var interval = intervalStack.Pop ();
 
228
                                if (interval.end < 0) 
 
229
                                        continue;
 
230
                                
 
231
                                var node = interval.node;
 
232
                                int nodeStart = interval.start - node.DistanceToPrevNode;
 
233
                                int nodeEnd = interval.end - node.DistanceToPrevNode;
 
234
                                if (node.left != null) {
 
235
                                        nodeStart -= node.left.TotalLength;
 
236
                                        nodeEnd -= node.left.TotalLength;
 
237
                                }
 
238
                        
 
239
                                if (node.DistanceToMaxEnd < nodeStart) 
 
240
                                        continue;
 
241
                        
 
242
                                if (node.left != null)
 
243
                                        intervalStack.Push (new Interval (node.left, interval.start, interval.end));
 
244
                                
 
245
                                if (nodeEnd < 0) 
 
246
                                        continue;
 
247
                                
 
248
                                if (nodeStart <= node.Length) 
 
249
                                        yield return (T)node;
 
250
                        
 
251
                                if (node.right != null) 
 
252
                                        intervalStack.Push (new Interval (node.right, nodeStart, nodeEnd));
 
253
                        }
 
254
                }
 
255
        }
 
256
        
 
257
        interface ISegmentTree
 
258
        {
 
259
                void Add (TreeSegment segment);
 
260
                void Remove (TreeSegment segment);
 
261
        }
 
262
        
 
263
        public class TreeSegment : Segment, IRedBlackTreeNode
 
264
        {
 
265
                internal ISegmentTree segmentTree;
 
266
 
 
267
                public override int Offset {
 
268
                        get {
 
269
                                if (segmentTree == null)
 
270
                                        return DistanceToPrevNode;
 
271
                                
 
272
                                var curNode = this;
 
273
                                int offset = curNode.DistanceToPrevNode;
 
274
                                if (curNode.left != null)
 
275
                                        offset += curNode.left.TotalLength;
 
276
                                while (curNode.parent != null) {
 
277
                                        if (curNode == curNode.parent.right) {
 
278
                                                if (curNode.parent.left != null)
 
279
                                                        offset += curNode.parent.left.TotalLength;
 
280
                                                offset += curNode.parent.DistanceToPrevNode;
 
281
                                        }
 
282
                                        curNode = curNode.parent;
 
283
                                }
 
284
                                return offset;
 
285
                        }
 
286
                        set {
 
287
                                if (segmentTree != null)
 
288
                                        segmentTree.Remove (this);
 
289
                                DistanceToPrevNode = value;
 
290
                                if (segmentTree != null)
 
291
                                        segmentTree.Add (this);
 
292
                        }
 
293
                }
 
294
                
 
295
                // TotalLength = DistanceToPrevNode + Left.DistanceToPrevNode + Right.DistanceToPrevNode
 
296
                internal int TotalLength;
 
297
                
 
298
                internal int DistanceToPrevNode;
 
299
                
 
300
                // DistanceToMaxEnd = Max (Length, left.DistanceToMaxEnd + Max (left.Offset, right.Offset) - Offset)
 
301
                internal int DistanceToMaxEnd;
 
302
                
 
303
                protected TreeSegment ()
 
304
                {
 
305
                }
 
306
 
 
307
                public TreeSegment (int offset, int length) : base (offset, length)
 
308
                {
 
309
                }
 
310
 
 
311
                public TreeSegment (ISegment segment) : base (segment)
 
312
                {
 
313
                }
 
314
 
 
315
                #region IRedBlackTreeNode implementation
 
316
                public void UpdateAugmentedData ()
 
317
                {
 
318
                        int totalLength = DistanceToPrevNode;
 
319
                        int distanceToMaxEnd = Length;
 
320
                        
 
321
                        if (left != null) {
 
322
                                totalLength += left.TotalLength;
 
323
                                int leftdistance = left.DistanceToMaxEnd - DistanceToPrevNode;
 
324
                                if (left.right != null)
 
325
                                        leftdistance -= left.right.TotalLength;
 
326
                                if (leftdistance > distanceToMaxEnd)
 
327
                                        distanceToMaxEnd = leftdistance;
 
328
                        }
 
329
                        
 
330
                        if (right != null) {
 
331
                                totalLength += right.TotalLength;
 
332
                                int rightdistance = right.DistanceToMaxEnd + right.DistanceToPrevNode;
 
333
                                if (right.left != null)
 
334
                                        rightdistance += right.left.TotalLength;
 
335
                                if (rightdistance > distanceToMaxEnd)
 
336
                                        distanceToMaxEnd = rightdistance;
 
337
                        }
 
338
                        
 
339
                        if (TotalLength != totalLength || DistanceToMaxEnd != distanceToMaxEnd) {
 
340
                                TotalLength = totalLength;
 
341
                                DistanceToMaxEnd = distanceToMaxEnd;
 
342
                                if (parent != null)
 
343
                                        parent.UpdateAugmentedData ();
 
344
                        }
 
345
                }
 
346
 
 
347
                internal TreeSegment parent, left, right;
 
348
 
 
349
                Mono.TextEditor.Utils.IRedBlackTreeNode Mono.TextEditor.Utils.IRedBlackTreeNode.Parent {
 
350
                        get {
 
351
                                return parent;
 
352
                        }
 
353
                        set {
 
354
                                parent = (TreeSegment)value;
 
355
                        }
 
356
                }
 
357
 
 
358
                Mono.TextEditor.Utils.IRedBlackTreeNode Mono.TextEditor.Utils.IRedBlackTreeNode.Left {
 
359
                        get {
 
360
                                return left;
 
361
                        }
 
362
                        set {
 
363
                                left = (TreeSegment)value;
 
364
                        }
 
365
                }
 
366
 
 
367
                
 
368
                IRedBlackTreeNode Mono.TextEditor.Utils.IRedBlackTreeNode.Right {
 
369
                        get {
 
370
                                return right;
 
371
                        }
 
372
                        set {
 
373
                                right = (TreeSegment)value;
 
374
                        }
 
375
                }
 
376
 
 
377
                RedBlackColor Mono.TextEditor.Utils.IRedBlackTreeNode.Color {
 
378
                        get;
 
379
                        set;
 
380
                }
 
381
                #endregion
 
382
                
 
383
        }
 
384
}