← 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/RedBlackTree.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/RedBlackTree.cs
1
 
// RedBlackTree.cs
2
 
//
3
 
// Author:
4
 
//   Mike Krüger <mkrueger@novell.com>
5
 
//
6
 
// Copyright (c) 2007 Novell, Inc (http://www.novell.com)
7
 
//
8
 
// Permission is hereby granted, free of charge, to any person obtaining a copy
9
 
// of this software and associated documentation files (the "Software"), to deal
10
 
// in the Software without restriction, including without limitation the rights
11
 
// to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
12
 
// copies of the Software, and to permit persons to whom the Software is
13
 
// furnished to do so, subject to the following conditions:
14
 
//
15
 
// The above copyright notice and this permission notice shall be included in
16
 
// all copies or substantial portions of the Software.
17
 
//
18
 
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
19
 
// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
20
 
// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
21
 
// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
22
 
// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
23
 
// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
24
 
// THE SOFTWARE.
25
 
//
26
 
//
27
 
 
28
 
using System;
29
 
using System.Text;
30
 
using System.Diagnostics;
31
 
using System.Collections.Generic;
32
 
 
33
 
namespace Mono.TextEditor
34
 
{
35
 
        public class RedBlackTree<T> : ICollection<T>
36
 
        {
37
 
                public RedBlackTreeNode Root {
38
 
                        get;
39
 
                        set;
40
 
                }
41
 
                
42
 
                public void Add (RedBlackTreeNode node)
43
 
                {
44
 
                        Count++;
45
 
                        if (Root == null) {
46
 
                                Root = node;
47
 
                                FixTreeOnInsert (node);
48
 
                                return;
49
 
                        }
50
 
                        
51
 
                        RedBlackTreeNode parent = Root;
52
 
                        
53
 
                        while (true) {
54
 
                                if (((IComparable)parent.value).CompareTo (node.value) <= 0) {
55
 
                                        if (parent.left == null) {
56
 
                                                Insert (parent, node, true);
57
 
                                                break;
58
 
                                        }
59
 
                                        parent = parent.left;
60
 
                                } else {
61
 
                                        if (parent.right == null) {
62
 
                                                Insert (parent, node, false);
63
 
                                                break;
64
 
                                        }
65
 
                                        parent = parent.right;
66
 
                                }
67
 
                        }
68
 
                }
69
 
                
70
 
                public RedBlackTreeIterator Insert (RedBlackTreeNode parent, RedBlackTreeNode node, bool insertLeft)
71
 
                {
72
 
                        if (insertLeft) {
73
 
                                Debug.Assert (parent.left == null);
74
 
                                parent.left = node;
75
 
                        } else {
76
 
                                Debug.Assert (parent.right == null);
77
 
                                parent.right = node;
78
 
                        }
79
 
                        node.parent = parent;
80
 
                        node.color = red;
81
 
                        
82
 
                        this.OnChildrenChanged (new RedBlackTreeNodeEventArgs (parent));
83
 
                        FixTreeOnInsert (node);
84
 
                        Count++;
85
 
                        return new RedBlackTreeIterator (node); 
86
 
                }
87
 
                
88
 
                void FixTreeOnInsert (RedBlackTreeNode node)
89
 
                {
90
 
                        if (node.parent == null) {
91
 
                                node.color = black;
92
 
                                return;
93
 
                        }
94
 
                        
95
 
                        if (node.parent.color == black) 
96
 
                                return;
97
 
                        
98
 
                        if (node.Uncle != null && node.Uncle.color == red) {
99
 
                                node.parent.color = black;
100
 
                                node.Uncle.color = black;
101
 
                                node.Grandparent.color = red;
102
 
                                FixTreeOnInsert (node.Grandparent);
103
 
                                return;
104
 
                        }
105
 
                        
106
 
                        if (node == node.parent.right && node.parent == node.Grandparent.left) {
107
 
                                RotateLeft (node.parent);
108
 
                                node = node.left;
109
 
                        } else if (node == node.parent.left && node.parent == node.Grandparent.right) {
110
 
                                RotateRight (node.parent);
111
 
                                node = node.right;
112
 
                        }
113
 
                        
114
 
                        node.parent.color = black;
115
 
                        node.Grandparent.color = red;
116
 
                        if (node == node.parent.left && node.parent == node.Grandparent.left) {
117
 
                                RotateRight (node.Grandparent);
118
 
                        } else {
119
 
                                RotateLeft (node.Grandparent);
120
 
                        }
121
 
                }
122
 
                
123
 
                void RotateLeft (RedBlackTreeNode node) 
124
 
                {
125
 
                        RedBlackTreeNode right = node.right;
126
 
                        this.Replace (node, right);
127
 
                        node.right = right.left;
128
 
                        if (node.right != null) 
129
 
                                node.right.parent = node;
130
 
                        right.left = node;
131
 
                        node.parent = right;
132
 
                        this.OnNodeRotateLeft (new RedBlackTreeNodeEventArgs (node));
133
 
                }
134
 
 
135
 
                void RotateRight (RedBlackTreeNode node) 
136
 
                {
137
 
                        RedBlackTreeNode left = node.left;
138
 
                        Replace (node, left);
139
 
                        node.left = left.right;
140
 
                        if (node.left != null) 
141
 
                                node.left.parent = node;
142
 
                        left.right = node;
143
 
                        node.parent = left;                     
144
 
                        this.OnNodeRotateRight (new RedBlackTreeNodeEventArgs (node));
145
 
                }
146
 
                
147
 
                public void RemoveAt (RedBlackTreeIterator iter)
148
 
                {
149
 
                        try {
150
 
                                Remove (iter.node);
151
 
                        } catch (Exception e) {
152
 
                                string s1 = "remove:" + iter.node.value;
153
 
                                string s2 = this.ToString ();
154
 
                                Console.WriteLine (s1);
155
 
                                Console.WriteLine (s2);
156
 
                                Console.WriteLine ("----");
157
 
                                Console.WriteLine (e);
158
 
                        }
159
 
                                
160
 
                }
161
 
                
162
 
                void Replace (RedBlackTreeNode oldNode, RedBlackTreeNode newNode)
163
 
                {
164
 
                        if (newNode != null)
165
 
                                newNode.parent = oldNode.parent;
166
 
                        if (oldNode.parent == null) {
167
 
                                Root = newNode;
168
 
                        } else {
169
 
                                if (oldNode.parent.left == oldNode)
170
 
                                        oldNode.parent.left = newNode;
171
 
                                else
172
 
                                        oldNode.parent.right = newNode;
173
 
                                this.OnChildrenChanged (new RedBlackTreeNodeEventArgs (oldNode.parent));
174
 
                        }
175
 
                }
176
 
                
177
 
                public void Remove (RedBlackTreeNode node)
178
 
                {
179
 
                        if (node.left != null && node.right != null) {
180
 
                                RedBlackTreeNode outerLeft = node.right.OuterLeft;
181
 
                                Remove (outerLeft);
182
 
                                Replace (node, outerLeft);
183
 
                                
184
 
                                outerLeft.color = node.color;
185
 
                                outerLeft.left = node.left;
186
 
                                if (outerLeft.left != null) 
187
 
                                        outerLeft.left.parent = outerLeft;
188
 
                                
189
 
                                outerLeft.right = node.right;
190
 
                                if (outerLeft.right != null) 
191
 
                                        outerLeft.right.parent = outerLeft;
192
 
                                this.OnChildrenChanged (new RedBlackTreeNodeEventArgs (outerLeft));
193
 
                                return;
194
 
                        }
195
 
                        Count--;
196
 
                        // node has only one child
197
 
                        RedBlackTreeNode child = node.left ?? node.right;
198
 
                        
199
 
                        Replace (node, child);
200
 
                        
201
 
                        if (node.color == black && child != null) {
202
 
                                if (child.color == red) {
203
 
                                        child.color = black;
204
 
                                } else {
205
 
                                        DeleteOneChild (child);
206
 
                                }
207
 
                        }
208
 
                }
209
 
                
210
 
                static bool GetColorSafe (RedBlackTreeNode node)
211
 
                {
212
 
                        return node != null ? node.color : black;
213
 
                }
214
 
                                
215
 
                void DeleteOneChild (RedBlackTreeNode node) 
216
 
                {
217
 
                        // case 1
218
 
                        if (node == null || node.parent == null)
219
 
                                return;
220
 
                        
221
 
                        RedBlackTreeNode parent  = node.parent;
222
 
                        RedBlackTreeNode sibling = node.Sibling;
223
 
                        if (sibling == null)
224
 
                                return;
225
 
                        
226
 
                        // case 2
227
 
                        if (sibling.color == red) {
228
 
                                parent.color  = red;
229
 
                                sibling.color = black;
230
 
                                if (node == parent.left) {
231
 
                                        RotateLeft (parent);
232
 
                                } else {
233
 
                                        RotateRight (parent);
234
 
                                }
235
 
                                sibling = node.Sibling;
236
 
                                if (sibling == null)
237
 
                                        return;
238
 
                        }
239
 
                        
240
 
                        // case 3
241
 
                        if (parent.color == black &&
242
 
                            sibling.color == black &&
243
 
                            GetColorSafe (sibling.left) == black &&
244
 
                            GetColorSafe (sibling.right) == black) {
245
 
                                sibling.color = red;
246
 
                                DeleteOneChild (parent);
247
 
                                return;
248
 
                        }
249
 
                        
250
 
                        // case 4
251
 
                        if (parent.color == red &&
252
 
                            sibling.color == black &&
253
 
                            GetColorSafe (sibling.left) == black &&
254
 
                            GetColorSafe (sibling.right) == black) {
255
 
                                sibling.color = red;
256
 
                                parent.color = black;
257
 
                                return;
258
 
                        }
259
 
                        
260
 
                        // case 5
261
 
                        if (node == parent.left &&
262
 
                            sibling.color == black &&
263
 
                            GetColorSafe (sibling.left) == red &&
264
 
                            GetColorSafe (sibling.right) == black) {
265
 
                                sibling.color = red;
266
 
                                if (sibling.left != null)
267
 
                                        sibling.left.color = black;
268
 
                                RotateRight (sibling);
269
 
                        } else if (node == parent.right &&
270
 
                                   sibling.color == black &&
271
 
                                   GetColorSafe (sibling.right) == red &&
272
 
                                   GetColorSafe (sibling.left) == black) {
273
 
                                sibling.color = red;
274
 
                                if (sibling.right != null)
275
 
                                        sibling.right.color = black;
276
 
                                RotateLeft (sibling);
277
 
                        }
278
 
                        
279
 
                        // case 6
280
 
                        sibling = node.Sibling;
281
 
                        if (sibling == null)
282
 
                                return;
283
 
                        sibling.color = parent.color;
284
 
                        parent.color = black;
285
 
                        if (node == parent.left) {
286
 
                                if (sibling.right != null) 
287
 
                                        sibling.right.color = black;
288
 
                                RotateLeft (parent);
289
 
                        } else {
290
 
                                if (sibling.left != null) 
291
 
                                        sibling.left.color = black;
292
 
                                RotateRight (parent);
293
 
                        }
294
 
                }
295
 
                
296
 
#region ICollection<T> implementation
297
 
                public int Count {
298
 
                        get;
299
 
                        set;
300
 
                }
301
 
                
302
 
                public void Add(T item)
303
 
                {
304
 
                        Add (new RedBlackTreeNode (item));
305
 
                }
306
 
                
307
 
                public void Clear()
308
 
                {
309
 
                        Root = null;
310
 
                        Count = 0;
311
 
                }
312
 
                
313
 
                public bool Contains(T item)
314
 
                {
315
 
                        RedBlackTreeIterator iter = new RedBlackTreeIterator (Root.OuterLeft);
316
 
                        while (iter.IsValid) {
317
 
                                if (iter.Current.Equals (item)) 
318
 
                                        return true;
319
 
                                iter.MoveNext ();
320
 
                        }
321
 
                        return false;
322
 
                }
323
 
                
324
 
                public bool Remove(T item)
325
 
                {
326
 
                        RedBlackTreeIterator iter = new RedBlackTreeIterator (Root.OuterLeft);
327
 
                        while (iter.IsValid) {
328
 
                                if (iter.Current.Equals (item)) {
329
 
                                        this.RemoveAt (iter);
330
 
                                        return true;
331
 
                                }
332
 
                                iter.MoveNext ();
333
 
                        }
334
 
                        return false;
335
 
                }
336
 
                
337
 
                IEnumerator<T> IEnumerable<T>.GetEnumerator()
338
 
                {
339
 
                        return GetEnumerator();
340
 
                }
341
 
                
342
 
                System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
343
 
                {
344
 
                        return GetEnumerator();
345
 
                }
346
 
                
347
 
                public bool IsReadOnly {
348
 
                        get { return false; }
349
 
                }
350
 
 
351
 
                
352
 
                public void CopyTo (T[] array, int arrayIndex)
353
 
                {
354
 
                        Debug.Assert (array != null);
355
 
                        Debug.Assert (0 <= arrayIndex && arrayIndex < array.Length);
356
 
                        int i = arrayIndex;
357
 
                        foreach (T value in this) 
358
 
                                array [i++] = value;
359
 
                }
360
 
                
361
 
                public RedBlackTreeIterator GetEnumerator()
362
 
                {
363
 
                        if (Root == null) 
364
 
                                return null;
365
 
                        RedBlackTreeNode dummyNode = new RedBlackTreeNode (default(T));
366
 
                        dummyNode.right = Root;
367
 
                        return new RedBlackTreeIterator (dummyNode);
368
 
                }
369
 
#endregion
370
 
                
371
 
                public event EventHandler<RedBlackTreeNodeEventArgs> ChildrenChanged;
372
 
                protected virtual void OnChildrenChanged (RedBlackTreeNodeEventArgs args)
373
 
                {
374
 
                        if (ChildrenChanged != null)
375
 
                                ChildrenChanged (this, args);
376
 
                }
377
 
                
378
 
                public event EventHandler<RedBlackTreeNodeEventArgs> NodeRotateLeft;
379
 
                protected virtual void OnNodeRotateLeft (RedBlackTreeNodeEventArgs args)
380
 
                {
381
 
                        if (NodeRotateLeft != null)
382
 
                                NodeRotateLeft (this, args);
383
 
                }
384
 
                
385
 
                public event EventHandler<RedBlackTreeNodeEventArgs> NodeRotateRight;
386
 
                protected virtual void OnNodeRotateRight (RedBlackTreeNodeEventArgs args)
387
 
                {
388
 
                        if (NodeRotateRight != null)
389
 
                                NodeRotateRight (this, args);
390
 
                }
391
 
 
392
 
                public class RedBlackTreeNodeEventArgs : EventArgs
393
 
                {
394
 
                        public RedBlackTreeNode Node {
395
 
                                get;
396
 
                                private set;
397
 
                        }
398
 
                        
399
 
                        public RedBlackTreeNodeEventArgs (RedBlackTreeNode node)
400
 
                        {
401
 
                                this.Node = node;
402
 
                        }
403
 
                }
404
 
                
405
 
                string GetIndent (int level)
406
 
                {
407
 
                        return new String ('\t', level);
408
 
                }
409
 
                
410
 
                void AppendNode (StringBuilder builder, RedBlackTreeNode node, int indent)
411
 
                {
412
 
                        builder.Append (GetIndent (indent) + "Node (" + (node.color == red ? "r" : "b" ) + "):" + node.value.ToString () + Environment.NewLine);
413
 
                        builder.Append (GetIndent (indent) + "Left: ");
414
 
                        if (node.left != null) {
415
 
                                builder.Append (Environment.NewLine);
416
 
                                AppendNode (builder, node.left, indent + 1);
417
 
                        } else { 
418
 
                                builder.Append ("null");
419
 
                        }
420
 
                                
421
 
                        builder.Append (Environment.NewLine);
422
 
                        builder.Append (GetIndent (indent) +  "Right: ");
423
 
                        if (node.right != null) {
424
 
                                builder.Append (Environment.NewLine);
425
 
                                AppendNode (builder, node.right, indent + 1);
426
 
                        } else { 
427
 
                                builder.Append ("null");
428
 
                        }
429
 
                }
430
 
                
431
 
                public override string ToString ()
432
 
                {
433
 
                        StringBuilder result = new StringBuilder ();
434
 
                        AppendNode (result, Root, 0);
435
 
                        return result.ToString ();
436
 
                }
437
 
                
438
 
                static bool red   = true;
439
 
                static bool black = false;
440
 
                
441
 
                public class RedBlackTreeNode
442
 
                {
443
 
                        public RedBlackTreeNode parent;
444
 
                        public RedBlackTreeNode left, right;
445
 
                        public T value;
446
 
                        public bool color;
447
 
                        
448
 
                        public RedBlackTreeNode (T value)
449
 
                        {
450
 
                                this.value = value;
451
 
                        }
452
 
                        
453
 
                        public bool IsLeaf {
454
 
                                get {
455
 
                                        return left == null && right == null;
456
 
                                }
457
 
                        }
458
 
                        
459
 
                        public RedBlackTreeNode Sibling {
460
 
                                get {
461
 
                                        if (parent == null)
462
 
                                                return null;
463
 
                                        return this == parent.left ? parent.right : parent.left;
464
 
                                }
465
 
                        }
466
 
                        public RedBlackTreeNode OuterLeft {
467
 
                                get {
468
 
                                        return left != null ? left.OuterLeft : this;
469
 
                                }
470
 
                        }
471
 
                        
472
 
                        public RedBlackTreeNode OuterRight {
473
 
                                get {
474
 
                                        return right != null ? right.OuterRight : this;
475
 
                                }
476
 
                        }
477
 
                        
478
 
                        public RedBlackTreeNode Grandparent {
479
 
                                get {
480
 
                                        return parent != null ? parent.parent : null;
481
 
                                }
482
 
                        }
483
 
                        
484
 
                        public RedBlackTreeNode Uncle {
485
 
                                get {
486
 
                                        RedBlackTreeNode grandparent = Grandparent;
487
 
                                        if (grandparent == null)
488
 
                                                return null;
489
 
                                        return parent == grandparent.left ? grandparent.right : grandparent.left;
490
 
                                }
491
 
                        }
492
 
                }
493
 
                
494
 
                public class RedBlackTreeIterator : IEnumerator<T>
495
 
                {
496
 
                        public RedBlackTreeNode startNode;
497
 
                        public RedBlackTreeNode node;
498
 
                        
499
 
                        public RedBlackTreeIterator (RedBlackTreeNode node)
500
 
                        {
501
 
                                this.startNode = this.node = node;
502
 
                        }
503
 
                        
504
 
                        public RedBlackTreeIterator Clone ()
505
 
                        {
506
 
                                return new RedBlackTreeIterator (this.startNode);
507
 
                        }
508
 
                        
509
 
                        public bool IsValid {
510
 
                                get { return node != null; }
511
 
                        }
512
 
                        
513
 
                        public T Current {
514
 
                                get {
515
 
                                        return node != null ? node.value : default(T);
516
 
                                }
517
 
                        }
518
 
                        
519
 
                        public RedBlackTreeNode CurrentNode {
520
 
                                get {
521
 
                                        return node;
522
 
                                }
523
 
                        }
524
 
                        
525
 
                        object System.Collections.IEnumerator.Current {
526
 
                                get {
527
 
                                        return this.Current;
528
 
                                }
529
 
                        }
530
 
                        
531
 
                        public void Reset ()
532
 
                        {
533
 
                                this.node = this.startNode; 
534
 
                        }
535
 
                        
536
 
                        public void Dispose ()
537
 
                        {
538
 
                        }
539
 
                        
540
 
                        public bool MoveNext ()
541
 
                        {
542
 
                                if (!IsValid)
543
 
                                        return false;
544
 
                                if (node.right == null) {
545
 
                                        RedBlackTreeNode oldNode;
546
 
                                        do {
547
 
                                                oldNode = node;
548
 
                                                node = node.parent;
549
 
                                        } while (node != null && node.right == oldNode);
550
 
                                } else {
551
 
                                        node = node.right.OuterLeft;
552
 
                                }
553
 
                                return IsValid;                 
554
 
                        }
555
 
                        
556
 
                        public bool MoveBack ()
557
 
                        {
558
 
                                if (!IsValid)
559
 
                                        return false;
560
 
                                if (node.left == null) {
561
 
                                        RedBlackTreeNode oldNode;
562
 
                                        do {
563
 
                                                oldNode = node;
564
 
                                                node = node.parent;
565
 
                                        } while (node != null && node.left == oldNode);
566
 
                                } else {
567
 
                                        node = node.left.OuterRight;
568
 
                                }
569
 
                                return IsValid;
570
 
                        }
571
 
                }               
572
 
        }
573
 
}