doc/oscl_html/oscl__tree_8h_source.html


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
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887

<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<meta http-equiv="Content-Type" content="text/xhtml;charset=UTF-8"/>
<title>oscl: oscl_tree.h Source File</title>
<link href="tabs.css" rel="stylesheet" type="text/css"/>
<link href="doxygen.css" rel="stylesheet" type="text/css"/>
</head>
<body>
<!-- Generated by Doxygen 1.6.3 -->
<div class="navigation" id="top">
  <div class="tabs">
    <ul>
      <li><a href="index.html"><span>Main&nbsp;Page</span></a></li>
      <li><a href="pages.html"><span>Related&nbsp;Pages</span></a></li>
      <li><a href="modules.html"><span>Modules</span></a></li>
      <li><a href="annotated.html"><span>Data&nbsp;Structures</span></a></li>
      <li class="current"><a href="files.html"><span>Files</span></a></li>
    </ul>
  </div>
  <div class="tabs">
    <ul>
      <li><a href="files.html"><span>File&nbsp;List</span></a></li>
      <li><a href="globals.html"><span>Globals</span></a></li>
    </ul>
  </div>
<h1>oscl_tree.h</h1><a href="oscl__tree_8h.html">Go to the documentation of this file.</a><div class="fragment"><pre class="fragment"><a name="l00001"></a>00001 <span class="comment">// -*- c++ -*-</span>
<a name="l00002"></a>00002 <span class="comment">// = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =</span>
<a name="l00003"></a>00003 
<a name="l00004"></a>00004 <span class="comment">//                     O S C L _ T R E E</span>
<a name="l00005"></a>00005 
<a name="l00006"></a>00006 <span class="comment">// = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =</span>
<a name="l00007"></a>00007 
<a name="l00018"></a>00018 <span class="preprocessor">#ifndef OSCL_TREE_H_INCLUDED</span>
<a name="l00019"></a>00019 <span class="preprocessor"></span><span class="preprocessor">#define OSCL_TREE_H_INCLUDED</span>
<a name="l00020"></a>00020 <span class="preprocessor"></span>
<a name="l00021"></a>00021 <span class="preprocessor">#ifndef OSCL_DEFALLOC_H_INCLUDED</span>
<a name="l00022"></a>00022 <span class="preprocessor"></span><span class="preprocessor">#include &quot;<a class="code" href="oscl__defalloc_8h.html" title="The file defines simple default memory allocator classes. These allocators are used...">oscl_defalloc.h</a>&quot;</span>
<a name="l00023"></a>00023 <span class="preprocessor">#endif</span>
<a name="l00024"></a>00024 <span class="preprocessor"></span>
<a name="l00025"></a>00025 <span class="preprocessor">#ifndef OSCL_BASE_H_INCLUDED</span>
<a name="l00026"></a>00026 <span class="preprocessor"></span><span class="preprocessor">#include &quot;<a class="code" href="oscl__base_8h.html" title="The file oscl_base.h is the public header that should be included to pick up the...">oscl_base.h</a>&quot;</span>
<a name="l00027"></a>00027 <span class="preprocessor">#endif</span>
<a name="l00028"></a>00028 <span class="preprocessor"></span>
<a name="l00029"></a><a class="code" href="group__osclbase.html#ga9fcc278d0a7a8d1c95f95c3bd7067994">00029</a> <span class="preprocessor">#define OSCL_DISABLE_WARNING_TRUNCATE_DEBUG_MESSAGE</span>
<a name="l00030"></a>00030 <span class="preprocessor"></span><span class="preprocessor">#include &quot;<a class="code" href="osclconfig__compiler__warnings_8h.html" title="This file contains the ability to turn off/on compiler warnings.">osclconfig_compiler_warnings.h</a>&quot;</span>
<a name="l00031"></a>00031 
<a name="l00032"></a>00032 <span class="keyword">template</span> &lt;<span class="keyword">class</span> T1, <span class="keyword">class</span> T2&gt;
<a name="l00033"></a><a class="code" href="structOscl__Pair.html">00033</a> <span class="keyword">struct </span><a class="code" href="structOscl__Pair.html">Oscl_Pair</a>
<a name="l00034"></a>00034 {
<a name="l00035"></a><a class="code" href="structOscl__Pair.html#a387c30c4c90b310715510ea0a74a94e4">00035</a>     T1 <a class="code" href="structOscl__Pair.html#a387c30c4c90b310715510ea0a74a94e4">first</a>;
<a name="l00036"></a><a class="code" href="structOscl__Pair.html#a014de341ef51349d9f8d288e87953efe">00036</a>     T2 <a class="code" href="structOscl__Pair.html#a014de341ef51349d9f8d288e87953efe">second</a>;
<a name="l00037"></a><a class="code" href="structOscl__Pair.html#a6c70edd64980ea960ea3a4e1f3d2fd56">00037</a>     <a class="code" href="structOscl__Pair.html#a6c70edd64980ea960ea3a4e1f3d2fd56">Oscl_Pair</a>() : <a class="code" href="structOscl__Pair.html#a387c30c4c90b310715510ea0a74a94e4">first</a>(T1()), <a class="code" href="structOscl__Pair.html#a014de341ef51349d9f8d288e87953efe">second</a>(T2()) {}
<a name="l00038"></a><a class="code" href="structOscl__Pair.html#a250647f79c6821f1f27034ef16839e48">00038</a>     <a class="code" href="structOscl__Pair.html#a250647f79c6821f1f27034ef16839e48">Oscl_Pair</a>(<span class="keyword">const</span> T1&amp; a, <span class="keyword">const</span> T2&amp; b) : <a class="code" href="structOscl__Pair.html#a387c30c4c90b310715510ea0a74a94e4">first</a>(a), <a class="code" href="structOscl__Pair.html#a014de341ef51349d9f8d288e87953efe">second</a>(b) {}
<a name="l00039"></a>00039 };
<a name="l00040"></a>00040 
<a name="l00041"></a>00041 
<a name="l00042"></a><a class="code" href="structOscl__Rb__Tree__Node__Base.html">00042</a> <span class="keyword">struct </span><a class="code" href="structOscl__Rb__Tree__Node__Base.html">Oscl_Rb_Tree_Node_Base</a>
<a name="l00043"></a>00043 {
<a name="l00044"></a><a class="code" href="structOscl__Rb__Tree__Node__Base.html#a031f9a90dc0f01b8f7959a15fc0892a7">00044</a>     <span class="keyword">typedef</span> <a class="code" href="structOscl__Rb__Tree__Node__Base.html">Oscl_Rb_Tree_Node_Base</a>* <a class="code" href="structOscl__Rb__Tree__Node__Base.html">base_link_type</a>;
<a name="l00045"></a><a class="code" href="structOscl__Rb__Tree__Node__Base.html#a896253504947002e44f59bd938dcdc4f">00045</a>     <span class="keyword">typedef</span> <span class="keyword">enum</span> <a class="code" href="structOscl__Rb__Tree__Node__Base.html#a896253504947002e44f59bd938dcdc4f">RedBl</a> {<a class="code" href="structOscl__Rb__Tree__Node__Base.html#a896253504947002e44f59bd938dcdc4fa5a6624ba603dd444a45d5162c7d25bc4">red</a>, <a class="code" href="structOscl__Rb__Tree__Node__Base.html#a896253504947002e44f59bd938dcdc4faba6d79b79574abfdab47adecce0a0525">black</a>} <a class="code" href="structOscl__Rb__Tree__Node__Base.html#ac14a3298f9282246b206c069cd1dea80">color_type</a>;
<a name="l00046"></a>00046 
<a name="l00047"></a><a class="code" href="structOscl__Rb__Tree__Node__Base.html#a3f5cf275956f5b7cec2acdc14426cc3c">00047</a>     <a class="code" href="structOscl__Rb__Tree__Node__Base.html#ac14a3298f9282246b206c069cd1dea80">color_type</a> <a class="code" href="structOscl__Rb__Tree__Node__Base.html#a3f5cf275956f5b7cec2acdc14426cc3c">color</a>;
<a name="l00048"></a><a class="code" href="structOscl__Rb__Tree__Node__Base.html#acf4bef8235be869292b7ba834fe6219a">00048</a>     <a class="code" href="structOscl__Rb__Tree__Node__Base.html">base_link_type</a> <a class="code" href="structOscl__Rb__Tree__Node__Base.html#acf4bef8235be869292b7ba834fe6219a">parent</a>;
<a name="l00049"></a><a class="code" href="structOscl__Rb__Tree__Node__Base.html#a0f72aa78dfbd88605c5d9df69fc46e30">00049</a>     <a class="code" href="structOscl__Rb__Tree__Node__Base.html">base_link_type</a> <a class="code" href="structOscl__Rb__Tree__Node__Base.html#a0f72aa78dfbd88605c5d9df69fc46e30">left</a>;
<a name="l00050"></a><a class="code" href="structOscl__Rb__Tree__Node__Base.html#ae9a58b98a2d87cee50ba51510c4177eb">00050</a>     <a class="code" href="structOscl__Rb__Tree__Node__Base.html">base_link_type</a> <a class="code" href="structOscl__Rb__Tree__Node__Base.html#ae9a58b98a2d87cee50ba51510c4177eb">right</a>;
<a name="l00051"></a>00051 
<a name="l00052"></a><a class="code" href="structOscl__Rb__Tree__Node__Base.html#ae044986b0b6f406e096bdda087991fc8">00052</a>     <span class="keyword">static</span> <a class="code" href="structOscl__Rb__Tree__Node__Base.html">base_link_type</a> <a class="code" href="structOscl__Rb__Tree__Node__Base.html#ae044986b0b6f406e096bdda087991fc8">minimum</a>(<a class="code" href="structOscl__Rb__Tree__Node__Base.html">base_link_type</a> x)
<a name="l00053"></a>00053     {
<a name="l00054"></a>00054         <span class="keywordflow">if</span> (x)
<a name="l00055"></a>00055         {
<a name="l00056"></a>00056             <span class="keywordflow">while</span> (x-&gt;<a class="code" href="structOscl__Rb__Tree__Node__Base.html#a0f72aa78dfbd88605c5d9df69fc46e30">left</a> != 0) x = x-&gt;<a class="code" href="structOscl__Rb__Tree__Node__Base.html#a0f72aa78dfbd88605c5d9df69fc46e30">left</a>;
<a name="l00057"></a>00057         }
<a name="l00058"></a>00058         <span class="keywordflow">return</span> x;
<a name="l00059"></a>00059     }
<a name="l00060"></a><a class="code" href="structOscl__Rb__Tree__Node__Base.html#a0bb7d82118180b05fb068046b08b3160">00060</a>     <span class="keyword">static</span> <a class="code" href="structOscl__Rb__Tree__Node__Base.html">base_link_type</a> <a class="code" href="structOscl__Rb__Tree__Node__Base.html#a0bb7d82118180b05fb068046b08b3160">maximum</a>(<a class="code" href="structOscl__Rb__Tree__Node__Base.html">base_link_type</a> x)
<a name="l00061"></a>00061     {
<a name="l00062"></a>00062         <span class="keywordflow">if</span> (x)
<a name="l00063"></a>00063         {
<a name="l00064"></a>00064             <span class="keywordflow">while</span> (x-&gt;<a class="code" href="structOscl__Rb__Tree__Node__Base.html#ae9a58b98a2d87cee50ba51510c4177eb">right</a> != 0) x = x-&gt;<a class="code" href="structOscl__Rb__Tree__Node__Base.html#ae9a58b98a2d87cee50ba51510c4177eb">right</a>;
<a name="l00065"></a>00065         }
<a name="l00066"></a>00066         <span class="keywordflow">return</span> x;
<a name="l00067"></a>00067     }
<a name="l00068"></a>00068 };
<a name="l00069"></a>00069 
<a name="l00070"></a>00070 <span class="keyword">template</span> &lt;<span class="keyword">class</span> Value&gt;
<a name="l00071"></a><a class="code" href="structOscl__Rb__Tree__Node.html">00071</a> <span class="keyword">struct </span><a class="code" href="structOscl__Rb__Tree__Node.html">Oscl_Rb_Tree_Node</a> : <span class="keyword">public</span> <a class="code" href="structOscl__Rb__Tree__Node__Base.html">Oscl_Rb_Tree_Node_Base</a>
<a name="l00072"></a>00072 {
<a name="l00073"></a><a class="code" href="structOscl__Rb__Tree__Node.html#a4734506f362a94c07a1b2b64983c67a3">00073</a>     <span class="keyword">typedef</span> Value <a class="code" href="structOscl__Rb__Tree__Node.html#a4734506f362a94c07a1b2b64983c67a3">value_type</a>;
<a name="l00074"></a><a class="code" href="structOscl__Rb__Tree__Node.html#abd7bce4bbbe59b698fcf474f809ee13d">00074</a>     <span class="keyword">typedef</span> <a class="code" href="structOscl__Rb__Tree__Node.html">Oscl_Rb_Tree_Node&lt;Value&gt;</a>* <a class="code" href="structOscl__Rb__Tree__Node.html">link_type</a>;
<a name="l00075"></a><a class="code" href="structOscl__Rb__Tree__Node.html#a4926978607f03035b64a620d50e70ee6">00075</a>     <a class="code" href="structOscl__Rb__Tree__Node.html#a4734506f362a94c07a1b2b64983c67a3">value_type</a> <a class="code" href="structOscl__Rb__Tree__Node.html#a4926978607f03035b64a620d50e70ee6">value</a>;
<a name="l00076"></a>00076 };
<a name="l00077"></a>00077 
<a name="l00078"></a>00078 
<a name="l00079"></a>00079 <span class="keyword">template</span> &lt;<span class="keyword">class</span> Value&gt;
<a name="l00080"></a><a class="code" href="structOscl__Rb__Tree__Iterator.html">00080</a> <span class="keyword">struct </span><a class="code" href="structOscl__Rb__Tree__Iterator.html">Oscl_Rb_Tree_Iterator</a>
<a name="l00081"></a>00081 {
<a name="l00082"></a><a class="code" href="structOscl__Rb__Tree__Iterator.html#a3d496607bfe1eae24d079de0735229c3">00082</a>     <span class="keyword">typedef</span> Value <a class="code" href="structOscl__Rb__Tree__Iterator.html#a3d496607bfe1eae24d079de0735229c3">value_type</a>;
<a name="l00083"></a><a class="code" href="structOscl__Rb__Tree__Iterator.html#a8c4275dedcec4f3ebc0468c02b54cdce">00083</a>     <span class="keyword">typedef</span> <a class="code" href="structOscl__Rb__Tree__Iterator.html#a3d496607bfe1eae24d079de0735229c3">value_type</a>&amp; <a class="code" href="structOscl__Rb__Tree__Iterator.html#a8c4275dedcec4f3ebc0468c02b54cdce">reference</a>;
<a name="l00084"></a><a class="code" href="structOscl__Rb__Tree__Iterator.html#a66d5075a5a47ac3e7cf22818ff151fe3">00084</a>     <span class="keyword">typedef</span> <a class="code" href="structOscl__Rb__Tree__Iterator.html#a3d496607bfe1eae24d079de0735229c3">value_type</a>* <a class="code" href="structOscl__Rb__Tree__Iterator.html#a66d5075a5a47ac3e7cf22818ff151fe3">pointer</a>;
<a name="l00085"></a><a class="code" href="structOscl__Rb__Tree__Iterator.html#a342ae0d7908efe2de74b87282097729b">00085</a>     <span class="keyword">typedef</span> <a class="code" href="structOscl__Rb__Tree__Iterator.html">Oscl_Rb_Tree_Iterator&lt;Value&gt;</a> <a class="code" href="structOscl__Rb__Tree__Iterator.html">iterator</a>;
<a name="l00086"></a><a class="code" href="structOscl__Rb__Tree__Iterator.html#a5a4d49065875a5106a684c044e35a0e7">00086</a>     <span class="keyword">typedef</span> <a class="code" href="structOscl__Rb__Tree__Iterator.html">Oscl_Rb_Tree_Iterator&lt;Value&gt;</a> <span class="keyword">self</span>;
<a name="l00087"></a><a class="code" href="structOscl__Rb__Tree__Iterator.html#a09ca120858e351c38acb5a0c5b58953c">00087</a>     <span class="keyword">typedef</span> <a class="code" href="structOscl__Rb__Tree__Node__Base.html">Oscl_Rb_Tree_Node_Base</a>* <a class="code" href="structOscl__Rb__Tree__Node__Base.html">base_link_type</a>;
<a name="l00088"></a><a class="code" href="structOscl__Rb__Tree__Iterator.html#a72b398920283a8e48a9fb26cadc06479">00088</a>     <span class="keyword">typedef</span> <a class="code" href="structOscl__Rb__Tree__Node.html">Oscl_Rb_Tree_Node&lt;Value&gt;</a>* <a class="code" href="structOscl__Rb__Tree__Node.html">link_type</a>;
<a name="l00089"></a>00089 
<a name="l00090"></a><a class="code" href="structOscl__Rb__Tree__Iterator.html#a5447f57a93a5f3f652c6ae3afd68f307">00090</a>     <a class="code" href="structOscl__Rb__Tree__Node__Base.html">base_link_type</a> <a class="code" href="structOscl__Rb__Tree__Iterator.html#a5447f57a93a5f3f652c6ae3afd68f307">node</a>;
<a name="l00091"></a>00091 
<a name="l00092"></a><a class="code" href="structOscl__Rb__Tree__Iterator.html#a53416d9553643bd1abcf68d2701e9d34">00092</a>     <a class="code" href="structOscl__Rb__Tree__Iterator.html#a53416d9553643bd1abcf68d2701e9d34">Oscl_Rb_Tree_Iterator</a>() {}
<a name="l00093"></a><a class="code" href="structOscl__Rb__Tree__Iterator.html#a91ceb9813641e2895eb72e59fa4ceffe">00093</a>     <a class="code" href="structOscl__Rb__Tree__Iterator.html#a53416d9553643bd1abcf68d2701e9d34">Oscl_Rb_Tree_Iterator</a>(<a class="code" href="structOscl__Rb__Tree__Node.html">link_type</a> x)
<a name="l00094"></a>00094     {
<a name="l00095"></a>00095         <a class="code" href="structOscl__Rb__Tree__Iterator.html#a5447f57a93a5f3f652c6ae3afd68f307">node</a> = x;
<a name="l00096"></a>00096     }
<a name="l00097"></a><a class="code" href="structOscl__Rb__Tree__Iterator.html#a94e2a498bd231f47d2e57f8152e6c853">00097</a>     <a class="code" href="structOscl__Rb__Tree__Iterator.html#a53416d9553643bd1abcf68d2701e9d34">Oscl_Rb_Tree_Iterator</a>(<span class="keyword">const</span> <a class="code" href="structOscl__Rb__Tree__Iterator.html">iterator</a>&amp; it)
<a name="l00098"></a>00098     {
<a name="l00099"></a>00099         <a class="code" href="structOscl__Rb__Tree__Iterator.html#a5447f57a93a5f3f652c6ae3afd68f307">node</a> = it.<a class="code" href="structOscl__Rb__Tree__Iterator.html#a5447f57a93a5f3f652c6ae3afd68f307">node</a>;
<a name="l00100"></a>00100     }
<a name="l00101"></a>00101 
<a name="l00102"></a><a class="code" href="structOscl__Rb__Tree__Iterator.html#a502a0e1164a43e7dd46fce304d4f4322">00102</a>     <a class="code" href="structOscl__Rb__Tree__Iterator.html#a8c4275dedcec4f3ebc0468c02b54cdce">reference</a> <a class="code" href="structOscl__Rb__Tree__Iterator.html#a502a0e1164a43e7dd46fce304d4f4322">operator*</a>()<span class="keyword"> const</span>
<a name="l00103"></a>00103 <span class="keyword">    </span>{
<a name="l00104"></a>00104         <span class="keywordflow">return</span> <a class="code" href="structOscl__Rb__Tree__Iterator.html#a72b398920283a8e48a9fb26cadc06479">link_type</a>(<a class="code" href="structOscl__Rb__Tree__Iterator.html#a5447f57a93a5f3f652c6ae3afd68f307">node</a>)-&gt;value;
<a name="l00105"></a>00105     }
<a name="l00106"></a><a class="code" href="structOscl__Rb__Tree__Iterator.html#a06504d932e5642dfa2742a1ee556b083">00106</a>     <a class="code" href="structOscl__Rb__Tree__Iterator.html#a66d5075a5a47ac3e7cf22818ff151fe3">pointer</a> <a class="code" href="structOscl__Rb__Tree__Iterator.html#a06504d932e5642dfa2742a1ee556b083">operator-&gt;</a>()<span class="keyword"> const</span>
<a name="l00107"></a>00107 <span class="keyword">    </span>{
<a name="l00108"></a>00108         <span class="keywordflow">return</span> &amp;(<a class="code" href="structOscl__Rb__Tree__Iterator.html#a502a0e1164a43e7dd46fce304d4f4322">operator*</a>());
<a name="l00109"></a>00109     }
<a name="l00110"></a>00110 
<a name="l00111"></a><a class="code" href="structOscl__Rb__Tree__Iterator.html#ac86283c696aae71aa66b4f44bcb98e88">00111</a>     <span class="keywordtype">bool</span> <a class="code" href="structOscl__Rb__Tree__Iterator.html#ac86283c696aae71aa66b4f44bcb98e88">operator==</a>(<span class="keyword">const</span> <span class="keyword">self</span>&amp; x)
<a name="l00112"></a>00112     {
<a name="l00113"></a>00113         <span class="keywordflow">return</span> <a class="code" href="structOscl__Rb__Tree__Iterator.html#a5447f57a93a5f3f652c6ae3afd68f307">node</a> == x.node;
<a name="l00114"></a>00114     }
<a name="l00115"></a>00115 
<a name="l00116"></a><a class="code" href="structOscl__Rb__Tree__Iterator.html#ac46dd0dd47ce5d7f3ff2bac64669b4a1">00116</a>     <span class="keywordtype">bool</span> <a class="code" href="structOscl__Rb__Tree__Iterator.html#ac46dd0dd47ce5d7f3ff2bac64669b4a1">operator!=</a>(<span class="keyword">const</span> <span class="keyword">self</span>&amp; x)
<a name="l00117"></a>00117     {
<a name="l00118"></a>00118         <span class="keywordflow">return</span> <a class="code" href="structOscl__Rb__Tree__Iterator.html#a5447f57a93a5f3f652c6ae3afd68f307">node</a> != x.node;
<a name="l00119"></a>00119     }
<a name="l00120"></a>00120 
<a name="l00121"></a><a class="code" href="structOscl__Rb__Tree__Iterator.html#a6676d3c5fe305124f2c40bde19a1dd3f">00121</a>     <span class="keyword">self</span>&amp; <a class="code" href="structOscl__Rb__Tree__Iterator.html#a6676d3c5fe305124f2c40bde19a1dd3f">operator++</a>()
<a name="l00122"></a>00122     {
<a name="l00123"></a>00123         <span class="keywordflow">if</span> (<a class="code" href="structOscl__Rb__Tree__Iterator.html#a5447f57a93a5f3f652c6ae3afd68f307">node</a>-&gt;<a class="code" href="structOscl__Rb__Tree__Node__Base.html#ae9a58b98a2d87cee50ba51510c4177eb">right</a> != 0)
<a name="l00124"></a>00124         {
<a name="l00125"></a>00125             <a class="code" href="structOscl__Rb__Tree__Iterator.html#a5447f57a93a5f3f652c6ae3afd68f307">node</a> = <a class="code" href="structOscl__Rb__Tree__Iterator.html#a5447f57a93a5f3f652c6ae3afd68f307">node</a>-&gt;<a class="code" href="structOscl__Rb__Tree__Node__Base.html#ae9a58b98a2d87cee50ba51510c4177eb">right</a>;
<a name="l00126"></a>00126             <span class="keywordflow">while</span> (<a class="code" href="structOscl__Rb__Tree__Iterator.html#a5447f57a93a5f3f652c6ae3afd68f307">node</a>-&gt;<a class="code" href="structOscl__Rb__Tree__Node__Base.html#a0f72aa78dfbd88605c5d9df69fc46e30">left</a> != 0)
<a name="l00127"></a>00127             {
<a name="l00128"></a>00128                 <a class="code" href="structOscl__Rb__Tree__Iterator.html#a5447f57a93a5f3f652c6ae3afd68f307">node</a> = <a class="code" href="structOscl__Rb__Tree__Iterator.html#a5447f57a93a5f3f652c6ae3afd68f307">node</a>-&gt;<a class="code" href="structOscl__Rb__Tree__Node__Base.html#a0f72aa78dfbd88605c5d9df69fc46e30">left</a>;
<a name="l00129"></a>00129             }
<a name="l00130"></a>00130         }
<a name="l00131"></a>00131         <span class="keywordflow">else</span>
<a name="l00132"></a>00132         {
<a name="l00133"></a>00133             <a class="code" href="structOscl__Rb__Tree__Node__Base.html">base_link_type</a> y = <a class="code" href="structOscl__Rb__Tree__Iterator.html#a5447f57a93a5f3f652c6ae3afd68f307">node</a>-&gt;<a class="code" href="structOscl__Rb__Tree__Node__Base.html#acf4bef8235be869292b7ba834fe6219a">parent</a>;
<a name="l00134"></a>00134             <span class="keywordflow">while</span> (<a class="code" href="structOscl__Rb__Tree__Iterator.html#a5447f57a93a5f3f652c6ae3afd68f307">node</a> == y-&gt;<a class="code" href="structOscl__Rb__Tree__Node__Base.html#ae9a58b98a2d87cee50ba51510c4177eb">right</a>)
<a name="l00135"></a>00135             {
<a name="l00136"></a>00136                 <a class="code" href="structOscl__Rb__Tree__Iterator.html#a5447f57a93a5f3f652c6ae3afd68f307">node</a> = y;
<a name="l00137"></a>00137                 y = y-&gt;<a class="code" href="structOscl__Rb__Tree__Node__Base.html#acf4bef8235be869292b7ba834fe6219a">parent</a>;
<a name="l00138"></a>00138             }
<a name="l00139"></a>00139             <span class="keywordflow">if</span> (<a class="code" href="structOscl__Rb__Tree__Iterator.html#a5447f57a93a5f3f652c6ae3afd68f307">node</a>-&gt;<a class="code" href="structOscl__Rb__Tree__Node__Base.html#ae9a58b98a2d87cee50ba51510c4177eb">right</a> != y) <a class="code" href="structOscl__Rb__Tree__Iterator.html#a5447f57a93a5f3f652c6ae3afd68f307">node</a> = y;
<a name="l00140"></a>00140         }
<a name="l00141"></a>00141         <span class="keywordflow">return</span> *<span class="keyword">this</span>;
<a name="l00142"></a>00142     }
<a name="l00143"></a>00143 
<a name="l00144"></a><a class="code" href="structOscl__Rb__Tree__Iterator.html#ad02aea7e45ce0133204189b3271a7de4">00144</a>     <span class="keyword">self</span> <a class="code" href="structOscl__Rb__Tree__Iterator.html#a6676d3c5fe305124f2c40bde19a1dd3f">operator++</a>(<span class="keywordtype">int</span>)
<a name="l00145"></a>00145     {
<a name="l00146"></a>00146         <span class="keyword">self</span> tmp = *<span class="keyword">this</span>;
<a name="l00147"></a>00147         ++*<span class="keyword">this</span>;
<a name="l00148"></a>00148         <span class="keywordflow">return</span> tmp;
<a name="l00149"></a>00149     }
<a name="l00150"></a>00150 
<a name="l00151"></a><a class="code" href="structOscl__Rb__Tree__Iterator.html#a9147a4e07e502a8613d9b3dc92de0843">00151</a>     <span class="keyword">self</span>&amp; <a class="code" href="structOscl__Rb__Tree__Iterator.html#a9147a4e07e502a8613d9b3dc92de0843">operator--</a>()
<a name="l00152"></a>00152     {
<a name="l00153"></a>00153         <span class="keywordflow">if</span> (<a class="code" href="structOscl__Rb__Tree__Iterator.html#a5447f57a93a5f3f652c6ae3afd68f307">node</a>-&gt;<a class="code" href="structOscl__Rb__Tree__Node__Base.html#a3f5cf275956f5b7cec2acdc14426cc3c">color</a> == <a class="code" href="structOscl__Rb__Tree__Node__Base.html#a896253504947002e44f59bd938dcdc4fa5a6624ba603dd444a45d5162c7d25bc4">Oscl_Rb_Tree_Node_Base::red</a> &amp;&amp; (<a class="code" href="structOscl__Rb__Tree__Iterator.html#a5447f57a93a5f3f652c6ae3afd68f307">node</a>-&gt;<a class="code" href="structOscl__Rb__Tree__Node__Base.html#acf4bef8235be869292b7ba834fe6219a">parent</a>)-&gt;parent == <a class="code" href="structOscl__Rb__Tree__Iterator.html#a5447f57a93a5f3f652c6ae3afd68f307">node</a>)
<a name="l00154"></a>00154         {
<a name="l00155"></a>00155             <a class="code" href="structOscl__Rb__Tree__Iterator.html#a5447f57a93a5f3f652c6ae3afd68f307">node</a> = <a class="code" href="structOscl__Rb__Tree__Iterator.html#a5447f57a93a5f3f652c6ae3afd68f307">node</a>-&gt;<a class="code" href="structOscl__Rb__Tree__Node__Base.html#ae9a58b98a2d87cee50ba51510c4177eb">right</a>;   <span class="comment">// return rightmost</span>
<a name="l00156"></a>00156         }
<a name="l00157"></a>00157         <span class="keywordflow">else</span> <span class="keywordflow">if</span> (<a class="code" href="structOscl__Rb__Tree__Iterator.html#a5447f57a93a5f3f652c6ae3afd68f307">node</a>-&gt;<a class="code" href="structOscl__Rb__Tree__Node__Base.html#a0f72aa78dfbd88605c5d9df69fc46e30">left</a> != 0)
<a name="l00158"></a>00158         {
<a name="l00159"></a>00159             <a class="code" href="structOscl__Rb__Tree__Node__Base.html">base_link_type</a> y = <a class="code" href="structOscl__Rb__Tree__Iterator.html#a5447f57a93a5f3f652c6ae3afd68f307">node</a>-&gt;<a class="code" href="structOscl__Rb__Tree__Node__Base.html#a0f72aa78dfbd88605c5d9df69fc46e30">left</a>;
<a name="l00160"></a>00160             <span class="keywordflow">while</span> (y-&gt;<a class="code" href="structOscl__Rb__Tree__Node__Base.html#ae9a58b98a2d87cee50ba51510c4177eb">right</a> != 0)
<a name="l00161"></a>00161                 y = y-&gt;<a class="code" href="structOscl__Rb__Tree__Node__Base.html#ae9a58b98a2d87cee50ba51510c4177eb">right</a>;
<a name="l00162"></a>00162             <a class="code" href="structOscl__Rb__Tree__Iterator.html#a5447f57a93a5f3f652c6ae3afd68f307">node</a> = y;
<a name="l00163"></a>00163         }
<a name="l00164"></a>00164         <span class="keywordflow">else</span>
<a name="l00165"></a>00165         {
<a name="l00166"></a>00166             <a class="code" href="structOscl__Rb__Tree__Node__Base.html">base_link_type</a> y = <a class="code" href="structOscl__Rb__Tree__Iterator.html#a5447f57a93a5f3f652c6ae3afd68f307">node</a>-&gt;<a class="code" href="structOscl__Rb__Tree__Node__Base.html#acf4bef8235be869292b7ba834fe6219a">parent</a>;
<a name="l00167"></a>00167             <span class="keywordflow">while</span> (<a class="code" href="structOscl__Rb__Tree__Iterator.html#a5447f57a93a5f3f652c6ae3afd68f307">node</a> == y-&gt;<a class="code" href="structOscl__Rb__Tree__Node__Base.html#a0f72aa78dfbd88605c5d9df69fc46e30">left</a>)
<a name="l00168"></a>00168             {
<a name="l00169"></a>00169                 <a class="code" href="structOscl__Rb__Tree__Iterator.html#a5447f57a93a5f3f652c6ae3afd68f307">node</a> = y;
<a name="l00170"></a>00170                 y = y-&gt;<a class="code" href="structOscl__Rb__Tree__Node__Base.html#acf4bef8235be869292b7ba834fe6219a">parent</a>;
<a name="l00171"></a>00171             }
<a name="l00172"></a>00172             <a class="code" href="structOscl__Rb__Tree__Iterator.html#a5447f57a93a5f3f652c6ae3afd68f307">node</a> = y;
<a name="l00173"></a>00173         }
<a name="l00174"></a>00174         <span class="keywordflow">return</span> *<span class="keyword">this</span>;
<a name="l00175"></a>00175     }
<a name="l00176"></a>00176 
<a name="l00177"></a><a class="code" href="structOscl__Rb__Tree__Iterator.html#ac9d67dbc837708e2b6cfb4f94a68b5c2">00177</a>     <span class="keyword">self</span> <a class="code" href="structOscl__Rb__Tree__Iterator.html#a9147a4e07e502a8613d9b3dc92de0843">operator--</a>(<span class="keywordtype">int</span>)
<a name="l00178"></a>00178     {
<a name="l00179"></a>00179         <span class="keyword">self</span> tmp = *<span class="keyword">this</span>;
<a name="l00180"></a>00180         --*<span class="keyword">this</span>;
<a name="l00181"></a>00181         <span class="keywordflow">return</span> tmp;
<a name="l00182"></a>00182     }
<a name="l00183"></a>00183 };
<a name="l00184"></a>00184 
<a name="l00185"></a>00185 
<a name="l00186"></a>00186 <span class="keyword">template</span> &lt;<span class="keyword">class</span> Value&gt;
<a name="l00187"></a><a class="code" href="structOscl__Rb__Tree__Const__Iterator.html">00187</a> <span class="keyword">struct </span><a class="code" href="structOscl__Rb__Tree__Const__Iterator.html">Oscl_Rb_Tree_Const_Iterator</a>
<a name="l00188"></a>00188 {
<a name="l00189"></a><a class="code" href="structOscl__Rb__Tree__Const__Iterator.html#a4209384867025c47c3a0e572c6f3866a">00189</a>     <span class="keyword">typedef</span> Value <a class="code" href="structOscl__Rb__Tree__Const__Iterator.html#a4209384867025c47c3a0e572c6f3866a">value_type</a>;
<a name="l00190"></a><a class="code" href="structOscl__Rb__Tree__Const__Iterator.html#ae3f85b0c1e3f7451270071c37dca1b2a">00190</a>     <span class="keyword">typedef</span> <span class="keyword">const</span> <a class="code" href="structOscl__Rb__Tree__Const__Iterator.html#a4209384867025c47c3a0e572c6f3866a">value_type</a>&amp; <a class="code" href="structOscl__Rb__Tree__Const__Iterator.html#ae3f85b0c1e3f7451270071c37dca1b2a">reference</a>;
<a name="l00191"></a><a class="code" href="structOscl__Rb__Tree__Const__Iterator.html#a1087f9b7b8cf31b49d72b1431d09b761">00191</a>     <span class="keyword">typedef</span> <span class="keyword">const</span> <a class="code" href="structOscl__Rb__Tree__Const__Iterator.html#a4209384867025c47c3a0e572c6f3866a">value_type</a>* <a class="code" href="structOscl__Rb__Tree__Const__Iterator.html#a1087f9b7b8cf31b49d72b1431d09b761">pointer</a>;
<a name="l00192"></a><a class="code" href="structOscl__Rb__Tree__Const__Iterator.html#a932194c6ece0e27c9d6e25ebae9bc451">00192</a>     <span class="keyword">typedef</span> <a class="code" href="structOscl__Rb__Tree__Const__Iterator.html">Oscl_Rb_Tree_Const_Iterator&lt;Value&gt;</a> <a class="code" href="structOscl__Rb__Tree__Const__Iterator.html">const_iterator</a>;
<a name="l00193"></a><a class="code" href="structOscl__Rb__Tree__Const__Iterator.html#a7422950b65cabb2033795d20978d70e0">00193</a>     <span class="keyword">typedef</span> <a class="code" href="structOscl__Rb__Tree__Const__Iterator.html">Oscl_Rb_Tree_Const_Iterator&lt;Value&gt;</a> <span class="keyword">self</span>;
<a name="l00194"></a><a class="code" href="structOscl__Rb__Tree__Const__Iterator.html#afe24806b1c2ade3fa16101967ff67c6e">00194</a>     <span class="keyword">typedef</span> <a class="code" href="structOscl__Rb__Tree__Node__Base.html">Oscl_Rb_Tree_Node_Base</a>* <a class="code" href="structOscl__Rb__Tree__Node__Base.html">base_link_type</a>;
<a name="l00195"></a><a class="code" href="structOscl__Rb__Tree__Const__Iterator.html#a880885a7aff3cdcf1313a0a528860471">00195</a>     <span class="keyword">typedef</span> <a class="code" href="structOscl__Rb__Tree__Node.html">Oscl_Rb_Tree_Node&lt;Value&gt;</a>* <a class="code" href="structOscl__Rb__Tree__Node.html">link_type</a>;
<a name="l00196"></a>00196 
<a name="l00197"></a><a class="code" href="structOscl__Rb__Tree__Const__Iterator.html#aa51a19b1c11ca57f60e75ab5af1e0cd8">00197</a>     <a class="code" href="structOscl__Rb__Tree__Node__Base.html">base_link_type</a> <a class="code" href="structOscl__Rb__Tree__Const__Iterator.html#aa51a19b1c11ca57f60e75ab5af1e0cd8">node</a>;
<a name="l00198"></a>00198 
<a name="l00199"></a><a class="code" href="structOscl__Rb__Tree__Const__Iterator.html#aa90ea8c3302a262018effc3a1c557c64">00199</a>     <a class="code" href="structOscl__Rb__Tree__Const__Iterator.html#aa90ea8c3302a262018effc3a1c557c64">Oscl_Rb_Tree_Const_Iterator</a>() {}
<a name="l00200"></a><a class="code" href="structOscl__Rb__Tree__Const__Iterator.html#ab5c0ea60bbeed9df35a3c09553ec8e75">00200</a>     <a class="code" href="structOscl__Rb__Tree__Const__Iterator.html#aa90ea8c3302a262018effc3a1c557c64">Oscl_Rb_Tree_Const_Iterator</a>(<a class="code" href="structOscl__Rb__Tree__Node.html">link_type</a> x)
<a name="l00201"></a>00201     {
<a name="l00202"></a>00202         <a class="code" href="structOscl__Rb__Tree__Const__Iterator.html#aa51a19b1c11ca57f60e75ab5af1e0cd8">node</a> = x;
<a name="l00203"></a>00203     }
<a name="l00204"></a><a class="code" href="structOscl__Rb__Tree__Const__Iterator.html#abdb37fe6c82de8720e5e4ee8f4379234">00204</a>     <a class="code" href="structOscl__Rb__Tree__Const__Iterator.html#aa90ea8c3302a262018effc3a1c557c64">Oscl_Rb_Tree_Const_Iterator</a>(<span class="keyword">const</span> <a class="code" href="structOscl__Rb__Tree__Const__Iterator.html">const_iterator</a>&amp; it)
<a name="l00205"></a>00205     {
<a name="l00206"></a>00206         <a class="code" href="structOscl__Rb__Tree__Const__Iterator.html#aa51a19b1c11ca57f60e75ab5af1e0cd8">node</a> = it.<a class="code" href="structOscl__Rb__Tree__Const__Iterator.html#aa51a19b1c11ca57f60e75ab5af1e0cd8">node</a>;
<a name="l00207"></a>00207     }
<a name="l00208"></a>00208 
<a name="l00209"></a><a class="code" href="structOscl__Rb__Tree__Const__Iterator.html#a6bd3f5a6d7bef5eacdd4d18e1817836f">00209</a>     <a class="code" href="structOscl__Rb__Tree__Const__Iterator.html#ae3f85b0c1e3f7451270071c37dca1b2a">reference</a> <a class="code" href="structOscl__Rb__Tree__Const__Iterator.html#a6bd3f5a6d7bef5eacdd4d18e1817836f">operator*</a>()<span class="keyword"> const</span>
<a name="l00210"></a>00210 <span class="keyword">    </span>{
<a name="l00211"></a>00211         <span class="keywordflow">return</span> <a class="code" href="structOscl__Rb__Tree__Const__Iterator.html#a880885a7aff3cdcf1313a0a528860471">link_type</a>(<a class="code" href="structOscl__Rb__Tree__Const__Iterator.html#aa51a19b1c11ca57f60e75ab5af1e0cd8">node</a>)-&gt;value;
<a name="l00212"></a>00212     }
<a name="l00213"></a><a class="code" href="structOscl__Rb__Tree__Const__Iterator.html#adb96207f8e19997cca80cc0a0c076368">00213</a>     <a class="code" href="structOscl__Rb__Tree__Const__Iterator.html#a1087f9b7b8cf31b49d72b1431d09b761">pointer</a> <a class="code" href="structOscl__Rb__Tree__Const__Iterator.html#adb96207f8e19997cca80cc0a0c076368">operator-&gt;</a>()<span class="keyword"> const</span>
<a name="l00214"></a>00214 <span class="keyword">    </span>{
<a name="l00215"></a>00215         <span class="keywordflow">return</span> &amp;(<a class="code" href="structOscl__Rb__Tree__Const__Iterator.html#a6bd3f5a6d7bef5eacdd4d18e1817836f">operator*</a>());
<a name="l00216"></a>00216     }
<a name="l00217"></a>00217 
<a name="l00218"></a><a class="code" href="structOscl__Rb__Tree__Const__Iterator.html#ad8003a88076a26b5f9656c19a2170c2d">00218</a>     <span class="keywordtype">bool</span> <a class="code" href="structOscl__Rb__Tree__Const__Iterator.html#ad8003a88076a26b5f9656c19a2170c2d">operator==</a>(<span class="keyword">const</span> <span class="keyword">self</span>&amp; x)
<a name="l00219"></a>00219     {
<a name="l00220"></a>00220         <span class="keywordflow">return</span> <a class="code" href="structOscl__Rb__Tree__Const__Iterator.html#aa51a19b1c11ca57f60e75ab5af1e0cd8">node</a> == x.node;
<a name="l00221"></a>00221     }
<a name="l00222"></a>00222 
<a name="l00223"></a><a class="code" href="structOscl__Rb__Tree__Const__Iterator.html#a5b573417dc2012831585dc30af263052">00223</a>     <span class="keywordtype">bool</span> <a class="code" href="structOscl__Rb__Tree__Const__Iterator.html#a5b573417dc2012831585dc30af263052">operator!=</a>(<span class="keyword">const</span> <span class="keyword">self</span>&amp; x)
<a name="l00224"></a>00224     {
<a name="l00225"></a>00225         <span class="keywordflow">return</span> <a class="code" href="structOscl__Rb__Tree__Const__Iterator.html#aa51a19b1c11ca57f60e75ab5af1e0cd8">node</a> != x.node;
<a name="l00226"></a>00226     }
<a name="l00227"></a>00227 
<a name="l00228"></a><a class="code" href="structOscl__Rb__Tree__Const__Iterator.html#a0c87cd790929863d3b504bc8faad5d0a">00228</a>     <span class="keyword">self</span>&amp; <a class="code" href="structOscl__Rb__Tree__Const__Iterator.html#a0c87cd790929863d3b504bc8faad5d0a">operator++</a>()
<a name="l00229"></a>00229     {
<a name="l00230"></a>00230         <span class="keywordflow">if</span> (<a class="code" href="structOscl__Rb__Tree__Const__Iterator.html#aa51a19b1c11ca57f60e75ab5af1e0cd8">node</a>-&gt;<a class="code" href="structOscl__Rb__Tree__Node__Base.html#ae9a58b98a2d87cee50ba51510c4177eb">right</a> != 0)
<a name="l00231"></a>00231         {
<a name="l00232"></a>00232             <a class="code" href="structOscl__Rb__Tree__Const__Iterator.html#aa51a19b1c11ca57f60e75ab5af1e0cd8">node</a> = <a class="code" href="structOscl__Rb__Tree__Const__Iterator.html#aa51a19b1c11ca57f60e75ab5af1e0cd8">node</a>-&gt;<a class="code" href="structOscl__Rb__Tree__Node__Base.html#ae9a58b98a2d87cee50ba51510c4177eb">right</a>;
<a name="l00233"></a>00233             <span class="keywordflow">while</span> (<a class="code" href="structOscl__Rb__Tree__Const__Iterator.html#aa51a19b1c11ca57f60e75ab5af1e0cd8">node</a>-&gt;<a class="code" href="structOscl__Rb__Tree__Node__Base.html#a0f72aa78dfbd88605c5d9df69fc46e30">left</a> != 0)
<a name="l00234"></a>00234             {
<a name="l00235"></a>00235                 <a class="code" href="structOscl__Rb__Tree__Const__Iterator.html#aa51a19b1c11ca57f60e75ab5af1e0cd8">node</a> = <a class="code" href="structOscl__Rb__Tree__Const__Iterator.html#aa51a19b1c11ca57f60e75ab5af1e0cd8">node</a>-&gt;<a class="code" href="structOscl__Rb__Tree__Node__Base.html#a0f72aa78dfbd88605c5d9df69fc46e30">left</a>;
<a name="l00236"></a>00236             }
<a name="l00237"></a>00237         }
<a name="l00238"></a>00238         <span class="keywordflow">else</span>
<a name="l00239"></a>00239         {
<a name="l00240"></a>00240             <a class="code" href="structOscl__Rb__Tree__Node__Base.html">base_link_type</a> y = <a class="code" href="structOscl__Rb__Tree__Const__Iterator.html#aa51a19b1c11ca57f60e75ab5af1e0cd8">node</a>-&gt;<a class="code" href="structOscl__Rb__Tree__Node__Base.html#acf4bef8235be869292b7ba834fe6219a">parent</a>;
<a name="l00241"></a>00241             <span class="keywordflow">while</span> (<a class="code" href="structOscl__Rb__Tree__Const__Iterator.html#aa51a19b1c11ca57f60e75ab5af1e0cd8">node</a> == y-&gt;<a class="code" href="structOscl__Rb__Tree__Node__Base.html#ae9a58b98a2d87cee50ba51510c4177eb">right</a>)
<a name="l00242"></a>00242             {
<a name="l00243"></a>00243                 <a class="code" href="structOscl__Rb__Tree__Const__Iterator.html#aa51a19b1c11ca57f60e75ab5af1e0cd8">node</a> = y;
<a name="l00244"></a>00244                 y = y-&gt;<a class="code" href="structOscl__Rb__Tree__Node__Base.html#acf4bef8235be869292b7ba834fe6219a">parent</a>;
<a name="l00245"></a>00245             }
<a name="l00246"></a>00246             <span class="keywordflow">if</span> (<a class="code" href="structOscl__Rb__Tree__Const__Iterator.html#aa51a19b1c11ca57f60e75ab5af1e0cd8">node</a>-&gt;<a class="code" href="structOscl__Rb__Tree__Node__Base.html#ae9a58b98a2d87cee50ba51510c4177eb">right</a> != y) <a class="code" href="structOscl__Rb__Tree__Const__Iterator.html#aa51a19b1c11ca57f60e75ab5af1e0cd8">node</a> = y;
<a name="l00247"></a>00247         }
<a name="l00248"></a>00248         <span class="keywordflow">return</span> *<span class="keyword">this</span>;
<a name="l00249"></a>00249     }
<a name="l00250"></a>00250 
<a name="l00251"></a><a class="code" href="structOscl__Rb__Tree__Const__Iterator.html#a6fbe3103a8ba0a8c285bfff87e33fb6b">00251</a>     <span class="keyword">self</span> <a class="code" href="structOscl__Rb__Tree__Const__Iterator.html#a0c87cd790929863d3b504bc8faad5d0a">operator++</a>(<span class="keywordtype">int</span>)
<a name="l00252"></a>00252     {
<a name="l00253"></a>00253         <span class="keyword">self</span> tmp = *<span class="keyword">this</span>;
<a name="l00254"></a>00254         ++*<span class="keyword">this</span>;
<a name="l00255"></a>00255         <span class="keywordflow">return</span> tmp;
<a name="l00256"></a>00256     }
<a name="l00257"></a>00257 
<a name="l00258"></a><a class="code" href="structOscl__Rb__Tree__Const__Iterator.html#a0e4aaa17635621a8acbe92f22b8d7d2f">00258</a>     <span class="keyword">self</span>&amp; <a class="code" href="structOscl__Rb__Tree__Const__Iterator.html#a0e4aaa17635621a8acbe92f22b8d7d2f">operator--</a>()
<a name="l00259"></a>00259     {
<a name="l00260"></a>00260         <span class="keywordflow">if</span> (<a class="code" href="structOscl__Rb__Tree__Const__Iterator.html#aa51a19b1c11ca57f60e75ab5af1e0cd8">node</a>-&gt;<a class="code" href="structOscl__Rb__Tree__Node__Base.html#a3f5cf275956f5b7cec2acdc14426cc3c">color</a> == <a class="code" href="structOscl__Rb__Tree__Node__Base.html#a896253504947002e44f59bd938dcdc4fa5a6624ba603dd444a45d5162c7d25bc4">Oscl_Rb_Tree_Node_Base::red</a> &amp;&amp; (<a class="code" href="structOscl__Rb__Tree__Const__Iterator.html#aa51a19b1c11ca57f60e75ab5af1e0cd8">node</a>-&gt;<a class="code" href="structOscl__Rb__Tree__Node__Base.html#acf4bef8235be869292b7ba834fe6219a">parent</a>)-&gt;parent == <a class="code" href="structOscl__Rb__Tree__Const__Iterator.html#aa51a19b1c11ca57f60e75ab5af1e0cd8">node</a>)
<a name="l00261"></a>00261         {
<a name="l00262"></a>00262             <a class="code" href="structOscl__Rb__Tree__Const__Iterator.html#aa51a19b1c11ca57f60e75ab5af1e0cd8">node</a> = <a class="code" href="structOscl__Rb__Tree__Const__Iterator.html#aa51a19b1c11ca57f60e75ab5af1e0cd8">node</a>-&gt;<a class="code" href="structOscl__Rb__Tree__Node__Base.html#ae9a58b98a2d87cee50ba51510c4177eb">right</a>;   <span class="comment">// return rightmost</span>
<a name="l00263"></a>00263         }
<a name="l00264"></a>00264         <span class="keywordflow">else</span> <span class="keywordflow">if</span> (<a class="code" href="structOscl__Rb__Tree__Const__Iterator.html#aa51a19b1c11ca57f60e75ab5af1e0cd8">node</a>-&gt;<a class="code" href="structOscl__Rb__Tree__Node__Base.html#a0f72aa78dfbd88605c5d9df69fc46e30">left</a> != 0)
<a name="l00265"></a>00265         {
<a name="l00266"></a>00266             <a class="code" href="structOscl__Rb__Tree__Node__Base.html">base_link_type</a> y = <a class="code" href="structOscl__Rb__Tree__Const__Iterator.html#aa51a19b1c11ca57f60e75ab5af1e0cd8">node</a>-&gt;<a class="code" href="structOscl__Rb__Tree__Node__Base.html#a0f72aa78dfbd88605c5d9df69fc46e30">left</a>;
<a name="l00267"></a>00267             <span class="keywordflow">while</span> (y-&gt;<a class="code" href="structOscl__Rb__Tree__Node__Base.html#ae9a58b98a2d87cee50ba51510c4177eb">right</a> != 0)
<a name="l00268"></a>00268                 y = y-&gt;<a class="code" href="structOscl__Rb__Tree__Node__Base.html#ae9a58b98a2d87cee50ba51510c4177eb">right</a>;
<a name="l00269"></a>00269             <a class="code" href="structOscl__Rb__Tree__Const__Iterator.html#aa51a19b1c11ca57f60e75ab5af1e0cd8">node</a> = y;
<a name="l00270"></a>00270         }
<a name="l00271"></a>00271         <span class="keywordflow">else</span>
<a name="l00272"></a>00272         {
<a name="l00273"></a>00273             <a class="code" href="structOscl__Rb__Tree__Node__Base.html">base_link_type</a> y = <a class="code" href="structOscl__Rb__Tree__Const__Iterator.html#aa51a19b1c11ca57f60e75ab5af1e0cd8">node</a>-&gt;<a class="code" href="structOscl__Rb__Tree__Node__Base.html#acf4bef8235be869292b7ba834fe6219a">parent</a>;
<a name="l00274"></a>00274             <span class="keywordflow">while</span> (<a class="code" href="structOscl__Rb__Tree__Const__Iterator.html#aa51a19b1c11ca57f60e75ab5af1e0cd8">node</a> == y-&gt;<a class="code" href="structOscl__Rb__Tree__Node__Base.html#a0f72aa78dfbd88605c5d9df69fc46e30">left</a>)
<a name="l00275"></a>00275             {
<a name="l00276"></a>00276                 <a class="code" href="structOscl__Rb__Tree__Const__Iterator.html#aa51a19b1c11ca57f60e75ab5af1e0cd8">node</a> = y;
<a name="l00277"></a>00277                 y = y-&gt;<a class="code" href="structOscl__Rb__Tree__Node__Base.html#acf4bef8235be869292b7ba834fe6219a">parent</a>;
<a name="l00278"></a>00278             }
<a name="l00279"></a>00279             <a class="code" href="structOscl__Rb__Tree__Const__Iterator.html#aa51a19b1c11ca57f60e75ab5af1e0cd8">node</a> = y;
<a name="l00280"></a>00280         }
<a name="l00281"></a>00281         <span class="keywordflow">return</span> *<span class="keyword">this</span>;
<a name="l00282"></a>00282     }
<a name="l00283"></a>00283 
<a name="l00284"></a><a class="code" href="structOscl__Rb__Tree__Const__Iterator.html#a1dd8329c80feb8cd46ef53a3480fc316">00284</a>     <span class="keyword">self</span> <a class="code" href="structOscl__Rb__Tree__Const__Iterator.html#a0e4aaa17635621a8acbe92f22b8d7d2f">operator--</a>(<span class="keywordtype">int</span>)
<a name="l00285"></a>00285     {
<a name="l00286"></a>00286         <span class="keyword">self</span> tmp = *<span class="keyword">this</span>;
<a name="l00287"></a>00287         --*<span class="keyword">this</span>;
<a name="l00288"></a>00288         <span class="keywordflow">return</span> tmp;
<a name="l00289"></a>00289     }
<a name="l00290"></a>00290 };
<a name="l00291"></a>00291 
<a name="l00292"></a>00292 
<a name="l00293"></a><a class="code" href="classOscl__Rb__Tree__Base.html">00293</a> <span class="keyword">class </span><a class="code" href="classOscl__Rb__Tree__Base.html">Oscl_Rb_Tree_Base</a>
<a name="l00294"></a>00294 {
<a name="l00295"></a>00295 
<a name="l00296"></a>00296     <span class="keyword">public</span>:
<a name="l00297"></a><a class="code" href="classOscl__Rb__Tree__Base.html#ac5bc127330a7d1ac2b93bec67baaac10">00297</a>         <span class="keyword">typedef</span> <a class="code" href="structOscl__Rb__Tree__Node__Base.html">Oscl_Rb_Tree_Node_Base::base_link_type</a> <a class="code" href="structOscl__Rb__Tree__Node__Base.html">base_link_type</a>;
<a name="l00298"></a>00298 
<a name="l00299"></a>00299         <a class="code" href="osclconfig_8h.html#a6de0f53c5c11f8f53ce72c70d74d9abc">OSCL_IMPORT_REF</a> <span class="keywordtype">void</span> <a class="code" href="classOscl__Rb__Tree__Base.html#a4890dfda4456d3c38098d2c6ff67898d">rotate_left</a>(<a class="code" href="structOscl__Rb__Tree__Node__Base.html">base_link_type</a> x, <a class="code" href="structOscl__Rb__Tree__Node__Base.html">base_link_type</a>&amp; root);
<a name="l00300"></a>00300         <a class="code" href="osclconfig_8h.html#a6de0f53c5c11f8f53ce72c70d74d9abc">OSCL_IMPORT_REF</a> <span class="keywordtype">void</span> <a class="code" href="classOscl__Rb__Tree__Base.html#ab1a83af227ef16d55665af196b58a614">rotate_right</a>(<a class="code" href="structOscl__Rb__Tree__Node__Base.html">base_link_type</a> x, <a class="code" href="structOscl__Rb__Tree__Node__Base.html">base_link_type</a>&amp; root);
<a name="l00301"></a>00301         <a class="code" href="osclconfig_8h.html#a6de0f53c5c11f8f53ce72c70d74d9abc">OSCL_IMPORT_REF</a> <span class="keywordtype">void</span> <a class="code" href="classOscl__Rb__Tree__Base.html#a09a56c132d2633ae9d75216e58c607be">rebalance</a>(<a class="code" href="structOscl__Rb__Tree__Node__Base.html">base_link_type</a> x, <a class="code" href="structOscl__Rb__Tree__Node__Base.html">base_link_type</a>&amp; root);
<a name="l00302"></a>00302         <a class="code" href="osclconfig_8h.html#a6de0f53c5c11f8f53ce72c70d74d9abc">OSCL_IMPORT_REF</a> <a class="code" href="structOscl__Rb__Tree__Node__Base.html">base_link_type</a> <a class="code" href="classOscl__Rb__Tree__Base.html#a0a1850223f27073fa4ba032f43ffd24e">rebalance_for_erase</a>(<a class="code" href="structOscl__Rb__Tree__Node__Base.html">base_link_type</a> z,
<a name="l00303"></a>00303                 <a class="code" href="structOscl__Rb__Tree__Node__Base.html">base_link_type</a>&amp; root,
<a name="l00304"></a>00304                 <a class="code" href="structOscl__Rb__Tree__Node__Base.html">base_link_type</a>&amp; leftmost,
<a name="l00305"></a>00305                 <a class="code" href="structOscl__Rb__Tree__Node__Base.html">base_link_type</a>&amp; rightmost);
<a name="l00306"></a>00306 };
<a name="l00307"></a>00307 
<a name="l00308"></a>00308 
<a name="l00309"></a>00309 <span class="keyword">template</span> &lt;<span class="keyword">class</span> Key, <span class="keyword">class</span> Value, <span class="keyword">class</span> KeyOfValue, <span class="keyword">class</span> Compare, <span class="keyword">class</span> Alloc&gt;
<a name="l00310"></a><a class="code" href="classOscl__Rb__Tree.html">00310</a> <span class="keyword">class </span><a class="code" href="classOscl__Rb__Tree.html">Oscl_Rb_Tree</a> : <span class="keyword">public</span> <a class="code" href="classOscl__Rb__Tree__Base.html">Oscl_Rb_Tree_Base</a>
<a name="l00311"></a>00311 {
<a name="l00312"></a>00312 
<a name="l00313"></a>00313     <span class="keyword">public</span>:
<a name="l00314"></a><a class="code" href="classOscl__Rb__Tree.html#aed455ac7b82e3529bc6ef2d9296ee376">00314</a>         <span class="keyword">typedef</span> Key <a class="code" href="classOscl__Rb__Tree.html#aed455ac7b82e3529bc6ef2d9296ee376">key_type</a>;
<a name="l00315"></a><a class="code" href="classOscl__Rb__Tree.html#ab97ac5512a2371111e1ba880c1a4a41f">00315</a>         <span class="keyword">typedef</span> Value <a class="code" href="classOscl__Rb__Tree.html#ab97ac5512a2371111e1ba880c1a4a41f">value_type</a>;
<a name="l00316"></a><a class="code" href="classOscl__Rb__Tree.html#a42d15633e230fb238206c98499ca283e">00316</a>         <span class="keyword">typedef</span> <a class="code" href="classOscl__Rb__Tree.html#ab97ac5512a2371111e1ba880c1a4a41f">value_type</a>* <a class="code" href="classOscl__Rb__Tree.html#a42d15633e230fb238206c98499ca283e">pointer</a>;
<a name="l00317"></a><a class="code" href="classOscl__Rb__Tree.html#a933d2e8e4c8571a96f780fc2994a7959">00317</a>         <span class="keyword">typedef</span> <span class="keyword">const</span> <a class="code" href="classOscl__Rb__Tree.html#ab97ac5512a2371111e1ba880c1a4a41f">value_type</a>* <a class="code" href="classOscl__Rb__Tree.html#a933d2e8e4c8571a96f780fc2994a7959">const_pointer</a>;
<a name="l00318"></a><a class="code" href="classOscl__Rb__Tree.html#a407ce7ae6a82b4e6d7a336098d8f800c">00318</a>         <span class="keyword">typedef</span> <a class="code" href="classOscl__Rb__Tree.html#ab97ac5512a2371111e1ba880c1a4a41f">value_type</a>&amp; <a class="code" href="classOscl__Rb__Tree.html#a407ce7ae6a82b4e6d7a336098d8f800c">reference</a>;
<a name="l00319"></a><a class="code" href="classOscl__Rb__Tree.html#acf1c56e9fd99bb7cf3e182c0cf514aac">00319</a>         <span class="keyword">typedef</span> <span class="keyword">const</span> <a class="code" href="classOscl__Rb__Tree.html#ab97ac5512a2371111e1ba880c1a4a41f">value_type</a>&amp; <a class="code" href="classOscl__Rb__Tree.html#acf1c56e9fd99bb7cf3e182c0cf514aac">const_reference</a>;
<a name="l00320"></a><a class="code" href="classOscl__Rb__Tree.html#ac071f362746175733b302918c28991b4">00320</a>         <span class="keyword">typedef</span> <span class="keyword">typename</span> <a class="code" href="structOscl__Rb__Tree__Node.html">Oscl_Rb_Tree_Node&lt;Value&gt;::link_type</a> <a class="code" href="classOscl__Rb__Tree.html#ac071f362746175733b302918c28991b4">link_type</a>;
<a name="l00321"></a><a class="code" href="classOscl__Rb__Tree.html#a5157f5b936d49b6d28ac52e5a826d37f">00321</a>         <span class="keyword">typedef</span> <a class="code" href="structOscl__Rb__Tree__Iterator.html">Oscl_Rb_Tree_Iterator&lt;value_type&gt;</a> <a class="code" href="structOscl__Rb__Tree__Iterator.html">iterator</a>;
<a name="l00322"></a><a class="code" href="classOscl__Rb__Tree.html#a195be28f483579b902dd5fbcba9460fb">00322</a>         <span class="keyword">typedef</span> <a class="code" href="structOscl__Rb__Tree__Const__Iterator.html">Oscl_Rb_Tree_Const_Iterator&lt;value_type&gt;</a> <a class="code" href="structOscl__Rb__Tree__Const__Iterator.html">const_iterator</a>;
<a name="l00323"></a><a class="code" href="classOscl__Rb__Tree.html#a97bd6d64c71ea73b325eb5d349a93a68">00323</a>         <span class="keyword">typedef</span> uint32 <a class="code" href="classOscl__Rb__Tree.html#a97bd6d64c71ea73b325eb5d349a93a68">size_type</a>;
<a name="l00324"></a><a class="code" href="classOscl__Rb__Tree.html#a0b22ae0d926fc3994fab65ff38e5a5a0">00324</a>         <span class="keyword">typedef</span> int32 <a class="code" href="classOscl__Rb__Tree.html#a0b22ae0d926fc3994fab65ff38e5a5a0">difference_type</a>;
<a name="l00325"></a>00325     <span class="keyword">private</span>:
<a name="l00326"></a>00326         <span class="keyword">typedef</span> <span class="keyword">typename</span> <a class="code" href="structOscl__Rb__Tree__Node.html">Oscl_Rb_Tree_Node&lt;Value&gt;::color_type</a> color_type;
<a name="l00327"></a>00327         <span class="keyword">typedef</span> <a class="code" href="structOscl__Rb__Tree__Node.html">Oscl_Rb_Tree_Node&lt;Value&gt;</a> <a class="code" href="structOscl__Rb__Tree__Node.html">node_type</a>;
<a name="l00328"></a>00328 
<a name="l00329"></a>00329     <span class="keyword">private</span>:
<a name="l00330"></a>00330         <a class="code" href="classOscl__Rb__Tree.html#ac071f362746175733b302918c28991b4">link_type</a> header;
<a name="l00331"></a>00331         <a class="code" href="classOscl__Rb__Tree.html#a97bd6d64c71ea73b325eb5d349a93a68">size_type</a> node_count;
<a name="l00332"></a>00332         Compare key_compare;
<a name="l00333"></a>00333         <a class="code" href="classOscl__TAlloc.html">Oscl_TAlloc&lt;node_type, Alloc&gt;</a> node_allocator;
<a name="l00334"></a>00334 
<a name="l00335"></a>00335     <span class="keyword">public</span>:
<a name="l00336"></a><a class="code" href="classOscl__Rb__Tree.html#ae28088d153dbb27e90920a49ecfa6d4a">00336</a>         <a class="code" href="classOscl__Rb__Tree.html#ae28088d153dbb27e90920a49ecfa6d4a">Oscl_Rb_Tree</a>(<span class="keyword">const</span> Compare&amp; comp = Compare())
<a name="l00337"></a>00337                 : node_count(0), key_compare(comp)
<a name="l00338"></a>00338         {
<a name="l00339"></a>00339             header = get_node();
<a name="l00340"></a>00340             header-&gt;<a class="code" href="structOscl__Rb__Tree__Node__Base.html#a3f5cf275956f5b7cec2acdc14426cc3c">color</a> = <a class="code" href="structOscl__Rb__Tree__Node__Base.html#a896253504947002e44f59bd938dcdc4fa5a6624ba603dd444a45d5162c7d25bc4">Oscl_Rb_Tree_Node_Base::red</a>;
<a name="l00341"></a>00341             leftmost() = header;
<a name="l00342"></a>00342             rightmost() = header;
<a name="l00343"></a>00343             root() = 0;
<a name="l00344"></a>00344         }
<a name="l00345"></a>00345 
<a name="l00346"></a><a class="code" href="classOscl__Rb__Tree.html#a640bc0442ad870bd4d399828da7a884c">00346</a>         <a class="code" href="classOscl__Rb__Tree.html#ae28088d153dbb27e90920a49ecfa6d4a">Oscl_Rb_Tree</a>(<span class="keyword">const</span> <a class="code" href="classOscl__Rb__Tree.html">Oscl_Rb_Tree&lt;Key, Value, KeyOfValue, Compare, Alloc&gt;</a>&amp; x)
<a name="l00347"></a>00347                 : node_count(0), key_compare(x.key_compare)
<a name="l00348"></a>00348         {
<a name="l00349"></a>00349             header = get_node();
<a name="l00350"></a>00350             header-&gt;<a class="code" href="structOscl__Rb__Tree__Node__Base.html#a3f5cf275956f5b7cec2acdc14426cc3c">color</a> = <a class="code" href="structOscl__Rb__Tree__Node__Base.html#a896253504947002e44f59bd938dcdc4fa5a6624ba603dd444a45d5162c7d25bc4">Oscl_Rb_Tree_Node_Base::red</a>;
<a name="l00351"></a>00351             <span class="keywordflow">if</span> (x.root() == 0)
<a name="l00352"></a>00352             {
<a name="l00353"></a>00353                 leftmost() = header;
<a name="l00354"></a>00354                 rightmost() = header;
<a name="l00355"></a>00355                 root() = 0;
<a name="l00356"></a>00356             }
<a name="l00357"></a>00357             <span class="keywordflow">else</span>
<a name="l00358"></a>00358             {
<a name="l00359"></a>00359                 root() = copy(x.root(), header);
<a name="l00360"></a>00360                 leftmost() = minimum(root());
<a name="l00361"></a>00361                 rightmost() = maximum(root());
<a name="l00362"></a>00362             }
<a name="l00363"></a>00363             node_count = x.node_count;
<a name="l00364"></a>00364         }
<a name="l00365"></a>00365 
<a name="l00366"></a><a class="code" href="classOscl__Rb__Tree.html#a80f330ae3444eef321ae387e04ac4c76">00366</a>         <a class="code" href="classOscl__Rb__Tree.html#a80f330ae3444eef321ae387e04ac4c76">~Oscl_Rb_Tree</a>()
<a name="l00367"></a>00367         {
<a name="l00368"></a>00368             <a class="code" href="classOscl__Rb__Tree.html#a59f1dfdb0d1299bc7768ec35e8e5a437">clear</a>();
<a name="l00369"></a>00369             release_node(header);
<a name="l00370"></a>00370         }
<a name="l00371"></a>00371 
<a name="l00372"></a>00372         <a class="code" href="classOscl__Rb__Tree.html">Oscl_Rb_Tree&lt;Key, Value, KeyOfValue, Compare, Alloc&gt;</a>&amp;
<a name="l00373"></a><a class="code" href="classOscl__Rb__Tree.html#a768a4cbb914d5a4090cab05a8f0af6ee">00373</a>         <a class="code" href="classOscl__Rb__Tree.html#a768a4cbb914d5a4090cab05a8f0af6ee">operator=</a>(<span class="keyword">const</span> <a class="code" href="classOscl__Rb__Tree.html">Oscl_Rb_Tree&lt;Key, Value, KeyOfValue, Compare, Alloc&gt;</a>&amp; x)
<a name="l00374"></a>00374         {
<a name="l00375"></a>00375             <span class="keywordflow">if</span> (<span class="keyword">this</span> != &amp;x)
<a name="l00376"></a>00376             {
<a name="l00377"></a>00377                 <a class="code" href="classOscl__Rb__Tree.html#a59f1dfdb0d1299bc7768ec35e8e5a437">clear</a>();
<a name="l00378"></a>00378                 node_count = 0;
<a name="l00379"></a>00379                 key_compare = x.key_compare;
<a name="l00380"></a>00380 
<a name="l00381"></a>00381                 <span class="keywordflow">if</span> (x.root() == 0)
<a name="l00382"></a>00382                 {
<a name="l00383"></a>00383                     root() = 0;
<a name="l00384"></a>00384                     leftmost() = header;
<a name="l00385"></a>00385                     rightmost() = header;
<a name="l00386"></a>00386                 }
<a name="l00387"></a>00387                 <span class="keywordflow">else</span>
<a name="l00388"></a>00388                 {
<a name="l00389"></a>00389                     root() = copy(x.root(), header);
<a name="l00390"></a>00390                     leftmost() = minimum(root());
<a name="l00391"></a>00391                     rightmost() = maximum(root());
<a name="l00392"></a>00392                     node_count = x.node_count;
<a name="l00393"></a>00393                 }
<a name="l00394"></a>00394             }
<a name="l00395"></a>00395             <span class="keywordflow">return</span> *<span class="keyword">this</span>;
<a name="l00396"></a>00396         }
<a name="l00397"></a>00397 
<a name="l00398"></a>00398     <span class="keyword">public</span>:
<a name="l00399"></a><a class="code" href="classOscl__Rb__Tree.html#ada9de4870590904bbff92f186c8bd9aa">00399</a>         <a class="code" href="structOscl__Rb__Tree__Iterator.html">iterator</a> <a class="code" href="classOscl__Rb__Tree.html#ada9de4870590904bbff92f186c8bd9aa">begin</a>()
<a name="l00400"></a>00400         {
<a name="l00401"></a>00401             <span class="keywordflow">return</span> leftmost();
<a name="l00402"></a>00402         }
<a name="l00403"></a><a class="code" href="classOscl__Rb__Tree.html#a3b2f86e45365531725e6a961c1b45e02">00403</a>         <a class="code" href="structOscl__Rb__Tree__Const__Iterator.html">const_iterator</a> <a class="code" href="classOscl__Rb__Tree.html#ada9de4870590904bbff92f186c8bd9aa">begin</a>()<span class="keyword"> const</span>
<a name="l00404"></a>00404 <span class="keyword">        </span>{
<a name="l00405"></a>00405             <span class="keywordflow">return</span> leftmost();
<a name="l00406"></a>00406         }
<a name="l00407"></a><a class="code" href="classOscl__Rb__Tree.html#accd49378d36ca2b2c2a83dcbec76baf8">00407</a>         <a class="code" href="structOscl__Rb__Tree__Iterator.html">iterator</a> <a class="code" href="classOscl__Rb__Tree.html#accd49378d36ca2b2c2a83dcbec76baf8">end</a>()
<a name="l00408"></a>00408         {
<a name="l00409"></a>00409             <span class="keywordflow">return</span> header;
<a name="l00410"></a>00410         }
<a name="l00411"></a><a class="code" href="classOscl__Rb__Tree.html#a8ffafe13a1974b59a94ca0863f5c0e2c">00411</a>         <a class="code" href="structOscl__Rb__Tree__Const__Iterator.html">const_iterator</a> <a class="code" href="classOscl__Rb__Tree.html#accd49378d36ca2b2c2a83dcbec76baf8">end</a>()<span class="keyword"> const</span>
<a name="l00412"></a>00412 <span class="keyword">        </span>{
<a name="l00413"></a>00413             <span class="keywordflow">return</span> header;
<a name="l00414"></a>00414         }
<a name="l00415"></a><a class="code" href="classOscl__Rb__Tree.html#a44e806d69de20d4b524ba0a3fdf7a4f2">00415</a>         <span class="keywordtype">bool</span> <a class="code" href="classOscl__Rb__Tree.html#a44e806d69de20d4b524ba0a3fdf7a4f2">empty</a>()<span class="keyword"> const</span>
<a name="l00416"></a>00416 <span class="keyword">        </span>{
<a name="l00417"></a>00417             <span class="keywordflow">return</span> node_count == 0;
<a name="l00418"></a>00418         }
<a name="l00419"></a><a class="code" href="classOscl__Rb__Tree.html#ad52a69a8c308804c64c7b1883adf4bdb">00419</a>         <a class="code" href="classOscl__Rb__Tree.html#a97bd6d64c71ea73b325eb5d349a93a68">size_type</a> <a class="code" href="classOscl__Rb__Tree.html#ad52a69a8c308804c64c7b1883adf4bdb">size</a>()<span class="keyword"> const</span>
<a name="l00420"></a>00420 <span class="keyword">        </span>{
<a name="l00421"></a>00421             <span class="keywordflow">return</span> node_count;
<a name="l00422"></a>00422         }
<a name="l00423"></a><a class="code" href="classOscl__Rb__Tree.html#aa082848ce3f503a242fa3d9ce22f0140">00423</a>         <a class="code" href="classOscl__Rb__Tree.html#a97bd6d64c71ea73b325eb5d349a93a68">size_type</a> <a class="code" href="classOscl__Rb__Tree.html#aa082848ce3f503a242fa3d9ce22f0140">max_size</a>()<span class="keyword"> const</span>
<a name="l00424"></a>00424 <span class="keyword">        </span>{
<a name="l00425"></a>00425             <span class="keywordflow">return</span> <a class="code" href="classOscl__Rb__Tree.html#a97bd6d64c71ea73b325eb5d349a93a68">size_type</a>(-1);
<a name="l00426"></a>00426         }
<a name="l00427"></a>00427 
<a name="l00428"></a><a class="code" href="classOscl__Rb__Tree.html#adf068ddc76bc9b85d81aedfd2e9c2d01">00428</a>         <a class="code" href="structOscl__Pair.html">Oscl_Pair&lt;iterator, bool&gt;</a> <a class="code" href="classOscl__Rb__Tree.html#adf068ddc76bc9b85d81aedfd2e9c2d01">insert_unique</a>(<span class="keyword">const</span> <a class="code" href="classOscl__Rb__Tree.html#ab97ac5512a2371111e1ba880c1a4a41f">value_type</a>&amp; v)
<a name="l00429"></a>00429         {
<a name="l00430"></a>00430             <a class="code" href="classOscl__Rb__Tree.html#ac071f362746175733b302918c28991b4">link_type</a> y = header;
<a name="l00431"></a>00431             <a class="code" href="classOscl__Rb__Tree.html#ac071f362746175733b302918c28991b4">link_type</a> x = root();
<a name="l00432"></a>00432             <span class="keywordtype">bool</span> comp = <span class="keyword">true</span>;
<a name="l00433"></a>00433             <span class="keywordflow">while</span> (x != 0)
<a name="l00434"></a>00434             {
<a name="l00435"></a>00435                 y = x;
<a name="l00436"></a>00436                 comp = key_compare(KeyOfValue()(v), key(x));
<a name="l00437"></a>00437                 x = comp ? left(x) : right(x);
<a name="l00438"></a>00438             }
<a name="l00439"></a>00439             <a class="code" href="structOscl__Rb__Tree__Iterator.html">iterator</a> j = <a class="code" href="classOscl__Rb__Tree.html#a5157f5b936d49b6d28ac52e5a826d37f">iterator</a>(y);
<a name="l00440"></a>00440             <span class="keywordflow">if</span> (comp)
<a name="l00441"></a>00441             {
<a name="l00442"></a>00442                 <span class="keywordflow">if</span> (j == <a class="code" href="classOscl__Rb__Tree.html#ada9de4870590904bbff92f186c8bd9aa">begin</a>())
<a name="l00443"></a>00443                     <span class="keywordflow">return</span> <a class="code" href="structOscl__Pair.html">Oscl_Pair&lt;iterator, bool&gt;</a>(insert(x, y, v), <span class="keyword">true</span>);
<a name="l00444"></a>00444                 <span class="keywordflow">else</span>
<a name="l00445"></a>00445                     --j;
<a name="l00446"></a>00446             }
<a name="l00447"></a>00447             <span class="keywordflow">if</span> (key_compare(key(j.<a class="code" href="structOscl__Rb__Tree__Iterator.html#a5447f57a93a5f3f652c6ae3afd68f307">node</a>), KeyOfValue()(v)))
<a name="l00448"></a>00448                 <span class="keywordflow">return</span> <a class="code" href="structOscl__Pair.html">Oscl_Pair&lt;iterator, bool&gt;</a>(insert(x, y, v), <span class="keyword">true</span>);
<a name="l00449"></a>00449 
<a name="l00450"></a>00450             <span class="keywordflow">return</span> <a class="code" href="structOscl__Pair.html">Oscl_Pair&lt;iterator, bool&gt;</a>(j, <span class="keyword">false</span>);
<a name="l00451"></a>00451         }
<a name="l00452"></a>00452 
<a name="l00453"></a><a class="code" href="classOscl__Rb__Tree.html#a52de623e34d607e6246a8a1d9452d41a">00453</a>         <a class="code" href="structOscl__Rb__Tree__Iterator.html">iterator</a> <a class="code" href="classOscl__Rb__Tree.html#adf068ddc76bc9b85d81aedfd2e9c2d01">insert_unique</a>(<a class="code" href="structOscl__Rb__Tree__Iterator.html">iterator</a> position, <span class="keyword">const</span> <a class="code" href="classOscl__Rb__Tree.html#ab97ac5512a2371111e1ba880c1a4a41f">value_type</a>&amp; v)
<a name="l00454"></a>00454         {
<a name="l00455"></a>00455             <span class="keywordflow">if</span> (position.<a class="code" href="structOscl__Rb__Tree__Iterator.html#a5447f57a93a5f3f652c6ae3afd68f307">node</a> == header-&gt;<a class="code" href="structOscl__Rb__Tree__Node__Base.html#a0f72aa78dfbd88605c5d9df69fc46e30">left</a>)   <span class="comment">// begin()</span>
<a name="l00456"></a>00456             {
<a name="l00457"></a>00457                 <span class="keywordflow">if</span> (<a class="code" href="classOscl__Rb__Tree.html#ad52a69a8c308804c64c7b1883adf4bdb">size</a>() &gt; 0 &amp;&amp; key_compare(KeyOfValue()(v), key(position.<a class="code" href="structOscl__Rb__Tree__Iterator.html#a5447f57a93a5f3f652c6ae3afd68f307">node</a>)))
<a name="l00458"></a>00458                     <span class="keywordflow">return</span> insert((<a class="code" href="classOscl__Rb__Tree.html#ac071f362746175733b302918c28991b4">link_type</a>)position.<a class="code" href="structOscl__Rb__Tree__Iterator.html#a5447f57a93a5f3f652c6ae3afd68f307">node</a>, (<a class="code" href="classOscl__Rb__Tree.html#ac071f362746175733b302918c28991b4">link_type</a>)position.<a class="code" href="structOscl__Rb__Tree__Iterator.html#a5447f57a93a5f3f652c6ae3afd68f307">node</a>, v);
<a name="l00459"></a>00459                 <span class="comment">// first argument just needs to be non-null</span>
<a name="l00460"></a>00460                 <span class="keywordflow">else</span>
<a name="l00461"></a>00461                     <span class="keywordflow">return</span> <a class="code" href="classOscl__Rb__Tree.html#adf068ddc76bc9b85d81aedfd2e9c2d01">insert_unique</a>(v).first;
<a name="l00462"></a>00462             }
<a name="l00463"></a>00463             <span class="keywordflow">else</span> <span class="keywordflow">if</span> (position.<a class="code" href="structOscl__Rb__Tree__Iterator.html#a5447f57a93a5f3f652c6ae3afd68f307">node</a> == header)   <span class="comment">// end()</span>
<a name="l00464"></a>00464             {
<a name="l00465"></a>00465                 <span class="keywordflow">if</span> (key_compare(key(rightmost()), KeyOfValue()(v)))
<a name="l00466"></a>00466                     <span class="keywordflow">return</span> insert(0, rightmost(), v);
<a name="l00467"></a>00467                 <span class="keywordflow">else</span>
<a name="l00468"></a>00468                     <span class="keywordflow">return</span> <a class="code" href="classOscl__Rb__Tree.html#adf068ddc76bc9b85d81aedfd2e9c2d01">insert_unique</a>(v).first;
<a name="l00469"></a>00469             }
<a name="l00470"></a>00470             <span class="keywordflow">else</span>
<a name="l00471"></a>00471             {
<a name="l00472"></a>00472                 <a class="code" href="structOscl__Rb__Tree__Iterator.html">iterator</a> before = position;
<a name="l00473"></a>00473                 --before;
<a name="l00474"></a>00474                 <span class="keywordflow">if</span> (key_compare(key(before.<a class="code" href="structOscl__Rb__Tree__Iterator.html#a5447f57a93a5f3f652c6ae3afd68f307">node</a>), KeyOfValue()(v))
<a name="l00475"></a>00475                         &amp;&amp; key_compare(KeyOfValue()(v), key(position.<a class="code" href="structOscl__Rb__Tree__Iterator.html#a5447f57a93a5f3f652c6ae3afd68f307">node</a>)))
<a name="l00476"></a>00476                 {
<a name="l00477"></a>00477                     <span class="keywordflow">if</span> (right(before.<a class="code" href="structOscl__Rb__Tree__Iterator.html#a5447f57a93a5f3f652c6ae3afd68f307">node</a>) == 0)
<a name="l00478"></a>00478                         <span class="keywordflow">return</span> insert(0, (<a class="code" href="classOscl__Rb__Tree.html#ac071f362746175733b302918c28991b4">link_type</a>)before.<a class="code" href="structOscl__Rb__Tree__Iterator.html#a5447f57a93a5f3f652c6ae3afd68f307">node</a>, v);
<a name="l00479"></a>00479                     <span class="keywordflow">else</span>
<a name="l00480"></a>00480                         <span class="keywordflow">return</span> insert((<a class="code" href="classOscl__Rb__Tree.html#ac071f362746175733b302918c28991b4">link_type</a>)position.<a class="code" href="structOscl__Rb__Tree__Iterator.html#a5447f57a93a5f3f652c6ae3afd68f307">node</a>, (<a class="code" href="classOscl__Rb__Tree.html#ac071f362746175733b302918c28991b4">link_type</a>)position.<a class="code" href="structOscl__Rb__Tree__Iterator.html#a5447f57a93a5f3f652c6ae3afd68f307">node</a>, v);
<a name="l00481"></a>00481                     <span class="comment">// first argument just needs to be non-null</span>
<a name="l00482"></a>00482                 }
<a name="l00483"></a>00483                 <span class="keywordflow">else</span>
<a name="l00484"></a>00484                     <span class="keywordflow">return</span> <a class="code" href="classOscl__Rb__Tree.html#adf068ddc76bc9b85d81aedfd2e9c2d01">insert_unique</a>(v).first;
<a name="l00485"></a>00485             }
<a name="l00486"></a>00486         }
<a name="l00487"></a>00487 
<a name="l00488"></a><a class="code" href="classOscl__Rb__Tree.html#acf8c81d5eee9703c1b945b5c35445c47">00488</a>         <span class="keywordtype">void</span> <a class="code" href="classOscl__Rb__Tree.html#adf068ddc76bc9b85d81aedfd2e9c2d01">insert_unique</a>(<a class="code" href="structOscl__Rb__Tree__Const__Iterator.html">const_iterator</a> first, <a class="code" href="structOscl__Rb__Tree__Const__Iterator.html">const_iterator</a> last)
<a name="l00489"></a>00489         {
<a name="l00490"></a>00490             <span class="keywordflow">for</span> (; first != last; ++first)
<a name="l00491"></a>00491                 <a class="code" href="classOscl__Rb__Tree.html#adf068ddc76bc9b85d81aedfd2e9c2d01">insert_unique</a>(*first);
<a name="l00492"></a>00492         }
<a name="l00493"></a>00493 
<a name="l00494"></a><a class="code" href="classOscl__Rb__Tree.html#a5aeeca7bb8676e44916141cf40628298">00494</a>         <span class="keywordtype">void</span> <a class="code" href="classOscl__Rb__Tree.html#adf068ddc76bc9b85d81aedfd2e9c2d01">insert_unique</a>(<span class="keyword">const</span> <a class="code" href="classOscl__Rb__Tree.html#ab97ac5512a2371111e1ba880c1a4a41f">value_type</a>* first, <span class="keyword">const</span> <a class="code" href="classOscl__Rb__Tree.html#ab97ac5512a2371111e1ba880c1a4a41f">value_type</a>* last)
<a name="l00495"></a>00495         {
<a name="l00496"></a>00496             <span class="keywordflow">for</span> (; first != last; ++first)
<a name="l00497"></a>00497                 <a class="code" href="classOscl__Rb__Tree.html#adf068ddc76bc9b85d81aedfd2e9c2d01">insert_unique</a>(*first);
<a name="l00498"></a>00498         }
<a name="l00499"></a>00499 
<a name="l00500"></a><a class="code" href="classOscl__Rb__Tree.html#a8b1e357fdcbb6eb60d3c8125eb32cc9d">00500</a>         <span class="keywordtype">void</span> <a class="code" href="classOscl__Rb__Tree.html#a8b1e357fdcbb6eb60d3c8125eb32cc9d">erase</a>(<a class="code" href="structOscl__Rb__Tree__Iterator.html">iterator</a> position)
<a name="l00501"></a>00501         {
<a name="l00502"></a>00502             <a class="code" href="classOscl__Rb__Tree.html#ac071f362746175733b302918c28991b4">link_type</a> y = (<a class="code" href="classOscl__Rb__Tree.html#ac071f362746175733b302918c28991b4">link_type</a>) <a class="code" href="classOscl__Rb__Tree__Base.html#a0a1850223f27073fa4ba032f43ffd24e">rebalance_for_erase</a>(position.<a class="code" href="structOscl__Rb__Tree__Iterator.html#a5447f57a93a5f3f652c6ae3afd68f307">node</a>,
<a name="l00503"></a>00503                           header-&gt;<a class="code" href="structOscl__Rb__Tree__Node__Base.html#acf4bef8235be869292b7ba834fe6219a">parent</a>,
<a name="l00504"></a>00504                           header-&gt;<a class="code" href="structOscl__Rb__Tree__Node__Base.html#a0f72aa78dfbd88605c5d9df69fc46e30">left</a>,
<a name="l00505"></a>00505                           header-&gt;<a class="code" href="structOscl__Rb__Tree__Node__Base.html#ae9a58b98a2d87cee50ba51510c4177eb">right</a>);
<a name="l00506"></a>00506 
<a name="l00507"></a>00507             destroy_node(y);
<a name="l00508"></a>00508             --node_count;
<a name="l00509"></a>00509         }
<a name="l00510"></a>00510 
<a name="l00511"></a><a class="code" href="classOscl__Rb__Tree.html#a2f40694ed9f9d530cdf95aed7e443240">00511</a>         <a class="code" href="classOscl__Rb__Tree.html#a97bd6d64c71ea73b325eb5d349a93a68">size_type</a> <a class="code" href="classOscl__Rb__Tree.html#a8b1e357fdcbb6eb60d3c8125eb32cc9d">erase</a>(<span class="keyword">const</span> <a class="code" href="classOscl__Rb__Tree.html#aed455ac7b82e3529bc6ef2d9296ee376">key_type</a>&amp; x)
<a name="l00512"></a>00512         {
<a name="l00513"></a>00513             <a class="code" href="structOscl__Pair.html">Oscl_Pair&lt;iterator, iterator&gt;</a> p = <a class="code" href="classOscl__Rb__Tree.html#a6600c02d24a2a83a8216e731598312a7">equal_range</a>(x);
<a name="l00514"></a>00514             <a class="code" href="classOscl__Rb__Tree.html#a97bd6d64c71ea73b325eb5d349a93a68">size_type</a> n = 0;
<a name="l00515"></a>00515             distance(p.<a class="code" href="structOscl__Pair.html#a387c30c4c90b310715510ea0a74a94e4">first</a>, p.<a class="code" href="structOscl__Pair.html#a014de341ef51349d9f8d288e87953efe">second</a>, n);
<a name="l00516"></a>00516             <a class="code" href="classOscl__Rb__Tree.html#a8b1e357fdcbb6eb60d3c8125eb32cc9d">erase</a>(p.<a class="code" href="structOscl__Pair.html#a387c30c4c90b310715510ea0a74a94e4">first</a>, p.<a class="code" href="structOscl__Pair.html#a014de341ef51349d9f8d288e87953efe">second</a>);
<a name="l00517"></a>00517             <span class="keywordflow">return</span> n;
<a name="l00518"></a>00518         }
<a name="l00519"></a>00519 
<a name="l00520"></a><a class="code" href="classOscl__Rb__Tree.html#a823a08e692c7711b17590bf1690f2456">00520</a>         <span class="keywordtype">void</span> <a class="code" href="classOscl__Rb__Tree.html#a8b1e357fdcbb6eb60d3c8125eb32cc9d">erase</a>(<a class="code" href="structOscl__Rb__Tree__Iterator.html">iterator</a> first, <a class="code" href="structOscl__Rb__Tree__Iterator.html">iterator</a> last)
<a name="l00521"></a>00521         {
<a name="l00522"></a>00522             <span class="keywordflow">if</span> (first == <a class="code" href="classOscl__Rb__Tree.html#ada9de4870590904bbff92f186c8bd9aa">begin</a>() &amp;&amp; last == <a class="code" href="classOscl__Rb__Tree.html#accd49378d36ca2b2c2a83dcbec76baf8">end</a>())
<a name="l00523"></a>00523                 <a class="code" href="classOscl__Rb__Tree.html#a59f1dfdb0d1299bc7768ec35e8e5a437">clear</a>();
<a name="l00524"></a>00524             <span class="keywordflow">else</span>
<a name="l00525"></a>00525                 <span class="keywordflow">while</span> (first != last) <a class="code" href="classOscl__Rb__Tree.html#a8b1e357fdcbb6eb60d3c8125eb32cc9d">erase</a>(first++);
<a name="l00526"></a>00526         }
<a name="l00527"></a>00527 
<a name="l00528"></a><a class="code" href="classOscl__Rb__Tree.html#abf33730b24cb0047d197762519327a39">00528</a>         <span class="keywordtype">void</span> <a class="code" href="classOscl__Rb__Tree.html#a8b1e357fdcbb6eb60d3c8125eb32cc9d">erase</a>(<span class="keyword">const</span> <a class="code" href="classOscl__Rb__Tree.html#aed455ac7b82e3529bc6ef2d9296ee376">key_type</a>* first, <span class="keyword">const</span> <a class="code" href="classOscl__Rb__Tree.html#aed455ac7b82e3529bc6ef2d9296ee376">key_type</a>* last)
<a name="l00529"></a>00529         {
<a name="l00530"></a>00530             <span class="keywordflow">while</span> (first != last) <a class="code" href="classOscl__Rb__Tree.html#a8b1e357fdcbb6eb60d3c8125eb32cc9d">erase</a>(*first++);
<a name="l00531"></a>00531         }
<a name="l00532"></a>00532 
<a name="l00533"></a><a class="code" href="classOscl__Rb__Tree.html#a59f1dfdb0d1299bc7768ec35e8e5a437">00533</a>         <span class="keywordtype">void</span> <a class="code" href="classOscl__Rb__Tree.html#a59f1dfdb0d1299bc7768ec35e8e5a437">clear</a>()
<a name="l00534"></a>00534         {
<a name="l00535"></a>00535             <span class="keywordflow">if</span> (node_count != 0)
<a name="l00536"></a>00536             {
<a name="l00537"></a>00537                 erase_without_rebalance(root());
<a name="l00538"></a>00538                 leftmost() = header;
<a name="l00539"></a>00539                 root() = 0;
<a name="l00540"></a>00540                 rightmost() = header;
<a name="l00541"></a>00541                 node_count = 0;
<a name="l00542"></a>00542             }
<a name="l00543"></a>00543         }
<a name="l00544"></a>00544 
<a name="l00545"></a><a class="code" href="classOscl__Rb__Tree.html#a15cf6e805436634c7821a30868161bb0">00545</a>         <a class="code" href="structOscl__Rb__Tree__Iterator.html">iterator</a> <a class="code" href="classOscl__Rb__Tree.html#a15cf6e805436634c7821a30868161bb0">find</a>(<span class="keyword">const</span> Key&amp; k)
<a name="l00546"></a>00546         {
<a name="l00547"></a>00547             <a class="code" href="classOscl__Rb__Tree.html#ac071f362746175733b302918c28991b4">link_type</a> y = header;        <span class="comment">// Last node which is not less than k.</span>
<a name="l00548"></a>00548             <a class="code" href="classOscl__Rb__Tree.html#ac071f362746175733b302918c28991b4">link_type</a> x = root();        <span class="comment">// Current node.</span>
<a name="l00549"></a>00549 
<a name="l00550"></a>00550             <span class="keywordflow">while</span> (x != 0)
<a name="l00551"></a>00551             {
<a name="l00552"></a>00552                 <span class="keywordflow">if</span> (!key_compare(key(x), k))
<a name="l00553"></a>00553                     y = x, x = left(x);
<a name="l00554"></a>00554                 <span class="keywordflow">else</span>
<a name="l00555"></a>00555                     x = right(x);
<a name="l00556"></a>00556             }
<a name="l00557"></a>00557             <a class="code" href="structOscl__Rb__Tree__Iterator.html">iterator</a> j = <a class="code" href="classOscl__Rb__Tree.html#a5157f5b936d49b6d28ac52e5a826d37f">iterator</a>(y);
<a name="l00558"></a>00558             <span class="keywordflow">return</span> (j == <a class="code" href="classOscl__Rb__Tree.html#accd49378d36ca2b2c2a83dcbec76baf8">end</a>() || key_compare(k, key(j.<a class="code" href="structOscl__Rb__Tree__Iterator.html#a5447f57a93a5f3f652c6ae3afd68f307">node</a>))) ? <a class="code" href="classOscl__Rb__Tree.html#accd49378d36ca2b2c2a83dcbec76baf8">end</a>() : j;
<a name="l00559"></a>00559         }
<a name="l00560"></a>00560 
<a name="l00561"></a><a class="code" href="classOscl__Rb__Tree.html#a759652049c5abab3a84f5475b46cc247">00561</a>         <a class="code" href="structOscl__Rb__Tree__Const__Iterator.html">const_iterator</a> <a class="code" href="classOscl__Rb__Tree.html#a15cf6e805436634c7821a30868161bb0">find</a>(<span class="keyword">const</span> Key&amp; k)<span class="keyword"> const</span>
<a name="l00562"></a>00562 <span class="keyword">        </span>{
<a name="l00563"></a>00563             <a class="code" href="classOscl__Rb__Tree.html#ac071f362746175733b302918c28991b4">link_type</a> y = header; <span class="comment">/* Last node which is not less than k. */</span>
<a name="l00564"></a>00564             <a class="code" href="classOscl__Rb__Tree.html#ac071f362746175733b302918c28991b4">link_type</a> x = root(); <span class="comment">/* Current node. */</span>
<a name="l00565"></a>00565 
<a name="l00566"></a>00566             <span class="keywordflow">while</span> (x != 0)
<a name="l00567"></a>00567             {
<a name="l00568"></a>00568                 <span class="keywordflow">if</span> (!key_compare(key(x), k))
<a name="l00569"></a>00569                     y = x, x = left(x);
<a name="l00570"></a>00570                 <span class="keywordflow">else</span>
<a name="l00571"></a>00571                     x = right(x);
<a name="l00572"></a>00572             }
<a name="l00573"></a>00573             <a class="code" href="structOscl__Rb__Tree__Const__Iterator.html">const_iterator</a> j = <a class="code" href="classOscl__Rb__Tree.html#a195be28f483579b902dd5fbcba9460fb">const_iterator</a>(y);
<a name="l00574"></a>00574             <span class="keywordflow">return</span> (j == <a class="code" href="classOscl__Rb__Tree.html#accd49378d36ca2b2c2a83dcbec76baf8">end</a>() || key_compare(k, key(j.<a class="code" href="structOscl__Rb__Tree__Const__Iterator.html#aa51a19b1c11ca57f60e75ab5af1e0cd8">node</a>))) ? <a class="code" href="classOscl__Rb__Tree.html#accd49378d36ca2b2c2a83dcbec76baf8">end</a>() : j;
<a name="l00575"></a>00575         }
<a name="l00576"></a>00576 
<a name="l00577"></a><a class="code" href="classOscl__Rb__Tree.html#aac75faceee92a1ab7d8f03dad3ee917c">00577</a>         <a class="code" href="classOscl__Rb__Tree.html#a97bd6d64c71ea73b325eb5d349a93a68">size_type</a> <a class="code" href="classOscl__Rb__Tree.html#aac75faceee92a1ab7d8f03dad3ee917c">count</a>(<span class="keyword">const</span> Key&amp; k)<span class="keyword"> const</span>
<a name="l00578"></a>00578 <span class="keyword">        </span>{
<a name="l00579"></a>00579             <a class="code" href="structOscl__Pair.html">Oscl_Pair&lt;const_iterator, const_iterator&gt;</a> p = <a class="code" href="classOscl__Rb__Tree.html#a6600c02d24a2a83a8216e731598312a7">equal_range</a>(k);
<a name="l00580"></a>00580             <a class="code" href="classOscl__Rb__Tree.html#a97bd6d64c71ea73b325eb5d349a93a68">size_type</a> n = 0;
<a name="l00581"></a>00581             distance(p.<a class="code" href="structOscl__Pair.html#a387c30c4c90b310715510ea0a74a94e4">first</a>, p.<a class="code" href="structOscl__Pair.html#a014de341ef51349d9f8d288e87953efe">second</a>, n);
<a name="l00582"></a>00582             <span class="keywordflow">return</span> n;
<a name="l00583"></a>00583         }
<a name="l00584"></a>00584 
<a name="l00585"></a><a class="code" href="classOscl__Rb__Tree.html#abafbe90bd41cfa11f62a6e1d83936ebb">00585</a>         <a class="code" href="structOscl__Rb__Tree__Iterator.html">iterator</a> <a class="code" href="classOscl__Rb__Tree.html#abafbe90bd41cfa11f62a6e1d83936ebb">lower_bound</a>(<span class="keyword">const</span> Key&amp; k)
<a name="l00586"></a>00586         {
<a name="l00587"></a>00587             <a class="code" href="classOscl__Rb__Tree.html#ac071f362746175733b302918c28991b4">link_type</a> y = header; <span class="comment">/* Last node which is not less than k. */</span>
<a name="l00588"></a>00588             <a class="code" href="classOscl__Rb__Tree.html#ac071f362746175733b302918c28991b4">link_type</a> x = root(); <span class="comment">/* Current node. */</span>
<a name="l00589"></a>00589 
<a name="l00590"></a>00590             <span class="keywordflow">while</span> (x != 0)
<a name="l00591"></a>00591             {
<a name="l00592"></a>00592                 <span class="keywordflow">if</span> (!key_compare(key(x), k))
<a name="l00593"></a>00593                 {
<a name="l00594"></a>00594                     y = x;
<a name="l00595"></a>00595                     x = left(x);
<a name="l00596"></a>00596                 }
<a name="l00597"></a>00597                 <span class="keywordflow">else</span>
<a name="l00598"></a>00598                     x = right(x);
<a name="l00599"></a>00599             }
<a name="l00600"></a>00600             <span class="keywordflow">return</span> <a class="code" href="classOscl__Rb__Tree.html#a5157f5b936d49b6d28ac52e5a826d37f">iterator</a>(y);
<a name="l00601"></a>00601         }
<a name="l00602"></a>00602 
<a name="l00603"></a><a class="code" href="classOscl__Rb__Tree.html#a5616fa9970d5054fbfbdd75c29234b3e">00603</a>         <a class="code" href="structOscl__Rb__Tree__Const__Iterator.html">const_iterator</a> <a class="code" href="classOscl__Rb__Tree.html#abafbe90bd41cfa11f62a6e1d83936ebb">lower_bound</a>(<span class="keyword">const</span> Key&amp; k)<span class="keyword"> const</span>
<a name="l00604"></a>00604 <span class="keyword">        </span>{
<a name="l00605"></a>00605             <a class="code" href="classOscl__Rb__Tree.html#ac071f362746175733b302918c28991b4">link_type</a> y = header; <span class="comment">/* Last node which is not less than k. */</span>
<a name="l00606"></a>00606             <a class="code" href="classOscl__Rb__Tree.html#ac071f362746175733b302918c28991b4">link_type</a> x = root(); <span class="comment">/* Current node. */</span>
<a name="l00607"></a>00607 
<a name="l00608"></a>00608             <span class="keywordflow">while</span> (x != 0)
<a name="l00609"></a>00609             {
<a name="l00610"></a>00610                 <span class="keywordflow">if</span> (!key_compare(key(x), k))
<a name="l00611"></a>00611                 {
<a name="l00612"></a>00612                     y = x;
<a name="l00613"></a>00613                     x = left(x);
<a name="l00614"></a>00614                 }
<a name="l00615"></a>00615                 <span class="keywordflow">else</span>
<a name="l00616"></a>00616                     x = right(x);
<a name="l00617"></a>00617             }
<a name="l00618"></a>00618             <span class="keywordflow">return</span> <a class="code" href="classOscl__Rb__Tree.html#a195be28f483579b902dd5fbcba9460fb">const_iterator</a>(y);
<a name="l00619"></a>00619         }
<a name="l00620"></a>00620 
<a name="l00621"></a><a class="code" href="classOscl__Rb__Tree.html#a7419c9dd3a81e5339b8f804087fd41f7">00621</a>         <a class="code" href="structOscl__Rb__Tree__Iterator.html">iterator</a> <a class="code" href="classOscl__Rb__Tree.html#a7419c9dd3a81e5339b8f804087fd41f7">upper_bound</a>(<span class="keyword">const</span> Key&amp; k)
<a name="l00622"></a>00622         {
<a name="l00623"></a>00623             <a class="code" href="classOscl__Rb__Tree.html#ac071f362746175733b302918c28991b4">link_type</a> y = header; <span class="comment">/* Last node which is greater than k. */</span>
<a name="l00624"></a>00624             <a class="code" href="classOscl__Rb__Tree.html#ac071f362746175733b302918c28991b4">link_type</a> x = root(); <span class="comment">/* Current node. */</span>
<a name="l00625"></a>00625 
<a name="l00626"></a>00626             <span class="keywordflow">while</span> (x != 0)
<a name="l00627"></a>00627             {
<a name="l00628"></a>00628                 <span class="keywordflow">if</span> (key_compare(k, key(x)))
<a name="l00629"></a>00629                 {
<a name="l00630"></a>00630                     y = x;
<a name="l00631"></a>00631                     x = left(x);
<a name="l00632"></a>00632                 }
<a name="l00633"></a>00633                 <span class="keywordflow">else</span>
<a name="l00634"></a>00634                     x = right(x);
<a name="l00635"></a>00635             }
<a name="l00636"></a>00636             <span class="keywordflow">return</span> <a class="code" href="classOscl__Rb__Tree.html#a5157f5b936d49b6d28ac52e5a826d37f">iterator</a>(y);
<a name="l00637"></a>00637         }
<a name="l00638"></a>00638 
<a name="l00639"></a><a class="code" href="classOscl__Rb__Tree.html#a0abbcc43983cc7158fc318f4c809a9c4">00639</a>         <a class="code" href="structOscl__Rb__Tree__Const__Iterator.html">const_iterator</a> <a class="code" href="classOscl__Rb__Tree.html#a7419c9dd3a81e5339b8f804087fd41f7">upper_bound</a>(<span class="keyword">const</span> Key&amp; k)<span class="keyword"> const</span>
<a name="l00640"></a>00640 <span class="keyword">        </span>{
<a name="l00641"></a>00641             <a class="code" href="classOscl__Rb__Tree.html#ac071f362746175733b302918c28991b4">link_type</a> y = header; <span class="comment">/* Last node which is greater than k. */</span>
<a name="l00642"></a>00642             <a class="code" href="classOscl__Rb__Tree.html#ac071f362746175733b302918c28991b4">link_type</a> x = root(); <span class="comment">/* Current node. */</span>
<a name="l00643"></a>00643 
<a name="l00644"></a>00644             <span class="keywordflow">while</span> (x != 0)
<a name="l00645"></a>00645             {
<a name="l00646"></a>00646                 <span class="keywordflow">if</span> (key_compare(k, key(x)))
<a name="l00647"></a>00647                 {
<a name="l00648"></a>00648                     y = x;
<a name="l00649"></a>00649                     x = left(x);
<a name="l00650"></a>00650                 }
<a name="l00651"></a>00651                 <span class="keywordflow">else</span>
<a name="l00652"></a>00652                     x = right(x);
<a name="l00653"></a>00653             }
<a name="l00654"></a>00654             <span class="keywordflow">return</span> <a class="code" href="classOscl__Rb__Tree.html#a195be28f483579b902dd5fbcba9460fb">const_iterator</a>(y);
<a name="l00655"></a>00655         }
<a name="l00656"></a>00656 
<a name="l00657"></a><a class="code" href="classOscl__Rb__Tree.html#a6600c02d24a2a83a8216e731598312a7">00657</a>         <a class="code" href="structOscl__Pair.html">Oscl_Pair&lt;iterator, iterator&gt;</a> <a class="code" href="classOscl__Rb__Tree.html#a6600c02d24a2a83a8216e731598312a7">equal_range</a>(<span class="keyword">const</span> Key&amp; k)
<a name="l00658"></a>00658         {
<a name="l00659"></a>00659             <span class="keywordflow">return</span> <a class="code" href="structOscl__Pair.html">Oscl_Pair&lt;iterator, iterator&gt;</a>(<a class="code" href="classOscl__Rb__Tree.html#abafbe90bd41cfa11f62a6e1d83936ebb">lower_bound</a>(k), <a class="code" href="classOscl__Rb__Tree.html#a7419c9dd3a81e5339b8f804087fd41f7">upper_bound</a>(k));
<a name="l00660"></a>00660         }
<a name="l00661"></a>00661 
<a name="l00662"></a><a class="code" href="classOscl__Rb__Tree.html#afdeb6a63e94fda677ad335a719e2f9c6">00662</a>         <a class="code" href="structOscl__Pair.html">Oscl_Pair&lt;const_iterator, const_iterator&gt;</a> <a class="code" href="classOscl__Rb__Tree.html#a6600c02d24a2a83a8216e731598312a7">equal_range</a>(<span class="keyword">const</span> Key&amp; k)<span class="keyword"> const</span>
<a name="l00663"></a>00663 <span class="keyword">        </span>{
<a name="l00664"></a>00664             <span class="keywordflow">return</span> <a class="code" href="structOscl__Pair.html">Oscl_Pair&lt;const_iterator, const_iterator&gt;</a>(<a class="code" href="classOscl__Rb__Tree.html#abafbe90bd41cfa11f62a6e1d83936ebb">lower_bound</a>(k), <a class="code" href="classOscl__Rb__Tree.html#a7419c9dd3a81e5339b8f804087fd41f7">upper_bound</a>(k));
<a name="l00665"></a>00665         }
<a name="l00666"></a>00666 
<a name="l00667"></a>00667     <span class="keyword">private</span>:
<a name="l00668"></a>00668         <span class="comment">// this helper function performs a downcast from base_link_type&amp; to link_type&amp;</span>
<a name="l00669"></a>00669         <span class="comment">// under C99 (gcc 3.x) this breaks aliasing rules so we have to go via a void** instead</span>
<a name="l00670"></a>00670         <span class="keyword">inline</span> <span class="keyword">static</span> <a class="code" href="classOscl__Rb__Tree.html#ac071f362746175733b302918c28991b4">link_type</a>&amp; cast_to_link_type(<a class="code" href="classOscl__Rb__Tree__Base.html#ac5bc127330a7d1ac2b93bec67baaac10">base_link_type</a> &amp;node)
<a name="l00671"></a>00671         {
<a name="l00672"></a>00672             <span class="keywordtype">void</span>** ptr = (<span class="keywordtype">void</span>**) &amp; node;
<a name="l00673"></a>00673             <a class="code" href="classOscl__Rb__Tree.html#ac071f362746175733b302918c28991b4">link_type</a>* base = (<a class="code" href="classOscl__Rb__Tree.html#ac071f362746175733b302918c28991b4">link_type</a>*) ptr;
<a name="l00674"></a>00674             <span class="keywordflow">return</span> *base;
<a name="l00675"></a>00675         }
<a name="l00676"></a>00676 
<a name="l00677"></a>00677         <a class="code" href="classOscl__Rb__Tree.html#ac071f362746175733b302918c28991b4">link_type</a>&amp; root()<span class="keyword"> const</span>
<a name="l00678"></a>00678 <span class="keyword">        </span>{
<a name="l00679"></a>00679             <span class="keywordflow">return</span> cast_to_link_type(header-&gt;<a class="code" href="structOscl__Rb__Tree__Node__Base.html#acf4bef8235be869292b7ba834fe6219a">parent</a>);
<a name="l00680"></a>00680         }
<a name="l00681"></a>00681         <a class="code" href="classOscl__Rb__Tree.html#ac071f362746175733b302918c28991b4">link_type</a>&amp; leftmost()<span class="keyword"> const</span>
<a name="l00682"></a>00682 <span class="keyword">        </span>{
<a name="l00683"></a>00683             <span class="keywordflow">return</span> cast_to_link_type(header-&gt;<a class="code" href="structOscl__Rb__Tree__Node__Base.html#a0f72aa78dfbd88605c5d9df69fc46e30">left</a>);
<a name="l00684"></a>00684         }
<a name="l00685"></a>00685         <a class="code" href="classOscl__Rb__Tree.html#ac071f362746175733b302918c28991b4">link_type</a>&amp; rightmost()<span class="keyword"> const</span>
<a name="l00686"></a>00686 <span class="keyword">        </span>{
<a name="l00687"></a>00687             <span class="keywordflow">return</span> cast_to_link_type(header-&gt;<a class="code" href="structOscl__Rb__Tree__Node__Base.html#ae9a58b98a2d87cee50ba51510c4177eb">right</a>);
<a name="l00688"></a>00688         }
<a name="l00689"></a>00689 
<a name="l00690"></a>00690         <span class="keyword">const</span> Key&amp; key(<a class="code" href="classOscl__Rb__Tree.html#ac071f362746175733b302918c28991b4">link_type</a> x)<span class="keyword"> const</span>
<a name="l00691"></a>00691 <span class="keyword">        </span>{
<a name="l00692"></a>00692             <span class="keywordflow">return</span> KeyOfValue()(value(x));
<a name="l00693"></a>00693         }
<a name="l00694"></a>00694         <span class="keyword">static</span> <a class="code" href="classOscl__Rb__Tree.html#a407ce7ae6a82b4e6d7a336098d8f800c">reference</a> value(<a class="code" href="classOscl__Rb__Tree.html#ac071f362746175733b302918c28991b4">link_type</a> x)
<a name="l00695"></a>00695         {
<a name="l00696"></a>00696             <span class="keywordflow">return</span> x-&gt;value;
<a name="l00697"></a>00697         }
<a name="l00698"></a>00698         <span class="keyword">static</span> <a class="code" href="classOscl__Rb__Tree.html#ac071f362746175733b302918c28991b4">link_type</a>&amp; left(<a class="code" href="classOscl__Rb__Tree.html#ac071f362746175733b302918c28991b4">link_type</a> x)
<a name="l00699"></a>00699         {
<a name="l00700"></a>00700             <span class="keywordflow">return</span> cast_to_link_type(x-&gt;left);
<a name="l00701"></a>00701         }
<a name="l00702"></a>00702         <span class="keyword">static</span> <a class="code" href="classOscl__Rb__Tree.html#ac071f362746175733b302918c28991b4">link_type</a>&amp; right(<a class="code" href="classOscl__Rb__Tree.html#ac071f362746175733b302918c28991b4">link_type</a> x)
<a name="l00703"></a>00703         {
<a name="l00704"></a>00704             <span class="keywordflow">return</span> cast_to_link_type(x-&gt;right);
<a name="l00705"></a>00705         }
<a name="l00706"></a>00706         <span class="keyword">static</span> <a class="code" href="classOscl__Rb__Tree.html#ac071f362746175733b302918c28991b4">link_type</a>&amp; parent(<a class="code" href="classOscl__Rb__Tree.html#ac071f362746175733b302918c28991b4">link_type</a> x)
<a name="l00707"></a>00707         {
<a name="l00708"></a>00708             <span class="keywordflow">return</span> cast_to_link_type(x-&gt;parent);
<a name="l00709"></a>00709         }
<a name="l00710"></a>00710 
<a name="l00711"></a>00711         <span class="keyword">const</span> Key&amp; key(<a class="code" href="classOscl__Rb__Tree__Base.html#ac5bc127330a7d1ac2b93bec67baaac10">base_link_type</a> x)<span class="keyword"> const</span>
<a name="l00712"></a>00712 <span class="keyword">        </span>{
<a name="l00713"></a>00713             <span class="keywordflow">return</span> KeyOfValue()(value(x));
<a name="l00714"></a>00714         }
<a name="l00715"></a>00715         <span class="keyword">static</span> <a class="code" href="classOscl__Rb__Tree.html#a407ce7ae6a82b4e6d7a336098d8f800c">reference</a> value(<a class="code" href="classOscl__Rb__Tree__Base.html#ac5bc127330a7d1ac2b93bec67baaac10">base_link_type</a> x)
<a name="l00716"></a>00716         {
<a name="l00717"></a>00717             <span class="keywordflow">return</span> ((<a class="code" href="classOscl__Rb__Tree.html#ac071f362746175733b302918c28991b4">link_type</a>)x)-&gt;value;
<a name="l00718"></a>00718         }
<a name="l00719"></a>00719         <span class="keyword">static</span> <a class="code" href="classOscl__Rb__Tree.html#ac071f362746175733b302918c28991b4">link_type</a>&amp; left(<a class="code" href="classOscl__Rb__Tree__Base.html#ac5bc127330a7d1ac2b93bec67baaac10">base_link_type</a> x)
<a name="l00720"></a>00720         {
<a name="l00721"></a>00721             <span class="keywordflow">return</span> cast_to_link_type(x-&gt;left);
<a name="l00722"></a>00722         }
<a name="l00723"></a>00723         <span class="keyword">static</span> <a class="code" href="classOscl__Rb__Tree.html#ac071f362746175733b302918c28991b4">link_type</a>&amp; right(<a class="code" href="classOscl__Rb__Tree__Base.html#ac5bc127330a7d1ac2b93bec67baaac10">base_link_type</a> x)
<a name="l00724"></a>00724         {
<a name="l00725"></a>00725             <span class="keywordflow">return</span> cast_to_link_type(x-&gt;right);
<a name="l00726"></a>00726         }
<a name="l00727"></a>00727         <span class="keyword">static</span> <a class="code" href="classOscl__Rb__Tree.html#ac071f362746175733b302918c28991b4">link_type</a>&amp; parent(<a class="code" href="classOscl__Rb__Tree__Base.html#ac5bc127330a7d1ac2b93bec67baaac10">base_link_type</a> x)
<a name="l00728"></a>00728         {
<a name="l00729"></a>00729             <span class="keywordflow">return</span> cast_to_link_type(x-&gt;parent);
<a name="l00730"></a>00730         }
<a name="l00731"></a>00731 
<a name="l00732"></a>00732         <span class="keyword">static</span> <a class="code" href="classOscl__Rb__Tree.html#ac071f362746175733b302918c28991b4">link_type</a> minimum(<a class="code" href="classOscl__Rb__Tree.html#ac071f362746175733b302918c28991b4">link_type</a> x)
<a name="l00733"></a>00733         {
<a name="l00734"></a>00734             <span class="keywordflow">return</span> (<a class="code" href="classOscl__Rb__Tree.html#ac071f362746175733b302918c28991b4">link_type</a>) <a class="code" href="structOscl__Rb__Tree__Node__Base.html#ae044986b0b6f406e096bdda087991fc8">Oscl_Rb_Tree_Node_Base::minimum</a>(x);
<a name="l00735"></a>00735         }
<a name="l00736"></a>00736         <span class="keyword">static</span> <a class="code" href="classOscl__Rb__Tree.html#ac071f362746175733b302918c28991b4">link_type</a> maximum(<a class="code" href="classOscl__Rb__Tree.html#ac071f362746175733b302918c28991b4">link_type</a> x)
<a name="l00737"></a>00737         {
<a name="l00738"></a>00738             <span class="keywordflow">return</span> (<a class="code" href="classOscl__Rb__Tree.html#ac071f362746175733b302918c28991b4">link_type</a>) <a class="code" href="structOscl__Rb__Tree__Node__Base.html#a0bb7d82118180b05fb068046b08b3160">Oscl_Rb_Tree_Node_Base::maximum</a>(x);
<a name="l00739"></a>00739         }
<a name="l00740"></a>00740 
<a name="l00741"></a>00741         <a class="code" href="classOscl__Rb__Tree.html#a5157f5b936d49b6d28ac52e5a826d37f">iterator</a> insert(<a class="code" href="classOscl__Rb__Tree.html#ac071f362746175733b302918c28991b4">link_type</a> x, <a class="code" href="classOscl__Rb__Tree.html#ac071f362746175733b302918c28991b4">link_type</a> y, <span class="keyword">const</span> <a class="code" href="classOscl__Rb__Tree.html#ab97ac5512a2371111e1ba880c1a4a41f">value_type</a>&amp; v)
<a name="l00742"></a>00742         {
<a name="l00743"></a>00743             <a class="code" href="classOscl__Rb__Tree.html#ac071f362746175733b302918c28991b4">link_type</a> z;
<a name="l00744"></a>00744 
<a name="l00745"></a>00745             <span class="keywordflow">if</span> (y == header || x != 0 || key_compare(KeyOfValue()(v), key(y)))
<a name="l00746"></a>00746             {
<a name="l00747"></a>00747                 z = create_node(v);
<a name="l00748"></a>00748                 left(y) = z;                <span class="comment">// also makes leftmost() = z when y == header</span>
<a name="l00749"></a>00749                 <span class="keywordflow">if</span> (y == header)
<a name="l00750"></a>00750                 {
<a name="l00751"></a>00751                     root() = z;
<a name="l00752"></a>00752                     rightmost() = z;
<a name="l00753"></a>00753                 }
<a name="l00754"></a>00754                 <span class="keywordflow">else</span> <span class="keywordflow">if</span> (y == leftmost())
<a name="l00755"></a>00755                     leftmost() = z;           <span class="comment">// maintain leftmost() pointing to min node</span>
<a name="l00756"></a>00756             }
<a name="l00757"></a>00757             <span class="keywordflow">else</span>
<a name="l00758"></a>00758             {
<a name="l00759"></a>00759                 z = create_node(v);
<a name="l00760"></a>00760                 right(y) = z;
<a name="l00761"></a>00761                 <span class="keywordflow">if</span> (y == rightmost())
<a name="l00762"></a>00762                     rightmost() = z;          <span class="comment">// maintain rightmost() pointing to max node</span>
<a name="l00763"></a>00763             }
<a name="l00764"></a>00764             parent(z) = y;
<a name="l00765"></a>00765             left(z) = 0;
<a name="l00766"></a>00766             right(z) = 0;
<a name="l00767"></a>00767             <a class="code" href="classOscl__Rb__Tree__Base.html#a09a56c132d2633ae9d75216e58c607be">rebalance</a>(z, header-&gt;<a class="code" href="structOscl__Rb__Tree__Node__Base.html#acf4bef8235be869292b7ba834fe6219a">parent</a>);
<a name="l00768"></a>00768             ++node_count;
<a name="l00769"></a>00769             <span class="keywordflow">return</span> <a class="code" href="classOscl__Rb__Tree.html#a5157f5b936d49b6d28ac52e5a826d37f">iterator</a>(z);
<a name="l00770"></a>00770 
<a name="l00771"></a>00771         }
<a name="l00772"></a>00772 
<a name="l00773"></a>00773         <span class="keywordtype">void</span> erase_without_rebalance(<a class="code" href="classOscl__Rb__Tree.html#ac071f362746175733b302918c28991b4">link_type</a> x)
<a name="l00774"></a>00774         {
<a name="l00775"></a>00775             <span class="keywordflow">while</span> (x != 0)
<a name="l00776"></a>00776             {
<a name="l00777"></a>00777                 erase_without_rebalance((<a class="code" href="classOscl__Rb__Tree.html#ac071f362746175733b302918c28991b4">link_type</a>)x-&gt;right);
<a name="l00778"></a>00778                 <a class="code" href="classOscl__Rb__Tree.html#ac071f362746175733b302918c28991b4">link_type</a> y = (<a class="code" href="classOscl__Rb__Tree.html#ac071f362746175733b302918c28991b4">link_type</a>)x-&gt;<a class="code" href="structOscl__Rb__Tree__Node__Base.html#a0f72aa78dfbd88605c5d9df69fc46e30">left</a>;
<a name="l00779"></a>00779                 destroy_node(x);
<a name="l00780"></a>00780                 x = y;
<a name="l00781"></a>00781             }
<a name="l00782"></a>00782         }
<a name="l00783"></a>00783 
<a name="l00784"></a>00784         <a class="code" href="classOscl__Rb__Tree.html#ac071f362746175733b302918c28991b4">link_type</a> copy(<a class="code" href="classOscl__Rb__Tree.html#ac071f362746175733b302918c28991b4">link_type</a> x, <a class="code" href="classOscl__Rb__Tree.html#ac071f362746175733b302918c28991b4">link_type</a> p)
<a name="l00785"></a>00785         {
<a name="l00786"></a>00786             <span class="comment">// structural copy.  x and p must be non-null.</span>
<a name="l00787"></a>00787             <a class="code" href="classOscl__Rb__Tree.html#ac071f362746175733b302918c28991b4">link_type</a> top = clone_node(x);
<a name="l00788"></a>00788             top-&gt;parent = p;
<a name="l00789"></a>00789 
<a name="l00790"></a>00790             <span class="keywordflow">if</span> (x-&gt;right)
<a name="l00791"></a>00791             {
<a name="l00792"></a>00792                 top-&gt;right = copy(right(x), top);
<a name="l00793"></a>00793             }
<a name="l00794"></a>00794             p = top;
<a name="l00795"></a>00795             x = left(x);
<a name="l00796"></a>00796 
<a name="l00797"></a>00797             <span class="keywordflow">while</span> (x != 0)
<a name="l00798"></a>00798             {
<a name="l00799"></a>00799                 <a class="code" href="classOscl__Rb__Tree.html#ac071f362746175733b302918c28991b4">link_type</a> y = clone_node(x);
<a name="l00800"></a>00800                 p-&gt;left = y;
<a name="l00801"></a>00801                 y-&gt;parent = p;
<a name="l00802"></a>00802                 <span class="keywordflow">if</span> (x-&gt;right)
<a name="l00803"></a>00803                 {
<a name="l00804"></a>00804                     y-&gt;right = copy(right(x), y);
<a name="l00805"></a>00805                 }
<a name="l00806"></a>00806                 p = y;
<a name="l00807"></a>00807                 x = left(x);
<a name="l00808"></a>00808             }
<a name="l00809"></a>00809 
<a name="l00810"></a>00810             <span class="keywordflow">return</span> top;
<a name="l00811"></a>00811         }
<a name="l00812"></a>00812 
<a name="l00813"></a>00813         <a class="code" href="classOscl__Rb__Tree.html#ac071f362746175733b302918c28991b4">link_type</a> get_node()
<a name="l00814"></a>00814         {
<a name="l00815"></a>00815             <span class="keywordflow">return</span> node_allocator.ALLOCATE(1);
<a name="l00816"></a>00816         }
<a name="l00817"></a>00817         <span class="keywordtype">void</span> release_node(<a class="code" href="classOscl__Rb__Tree.html#ac071f362746175733b302918c28991b4">link_type</a> node)
<a name="l00818"></a>00818         {
<a name="l00819"></a>00819             node_allocator.<a class="code" href="classOscl__TAlloc.html#aad556619cdcb4169d32df057fa4bce93">deallocate</a>(node);
<a name="l00820"></a>00820         }
<a name="l00821"></a>00821 
<a name="l00822"></a>00822         <a class="code" href="classOscl__Rb__Tree.html#ac071f362746175733b302918c28991b4">link_type</a> create_node(<span class="keyword">const</span> <a class="code" href="classOscl__Rb__Tree.html#ab97ac5512a2371111e1ba880c1a4a41f">value_type</a>&amp; v)
<a name="l00823"></a>00823         {
<a name="l00824"></a>00824             <a class="code" href="classOscl__Rb__Tree.html#ac071f362746175733b302918c28991b4">link_type</a> x = get_node();
<a name="l00825"></a>00825             <span class="keyword">new</span>(&amp;x-&gt;value) <a class="code" href="classOscl__Rb__Tree.html#ab97ac5512a2371111e1ba880c1a4a41f">value_type</a>(v);
<a name="l00826"></a>00826             <span class="keywordflow">return</span> x;
<a name="l00827"></a>00827         }
<a name="l00828"></a>00828 
<a name="l00829"></a>00829         <span class="keywordtype">void</span> destroy_node(<a class="code" href="classOscl__Rb__Tree.html#ac071f362746175733b302918c28991b4">link_type</a> x)
<a name="l00830"></a>00830         {
<a name="l00831"></a>00831             x-&gt;value.~Value();
<a name="l00832"></a>00832             release_node(x);
<a name="l00833"></a>00833         }
<a name="l00834"></a>00834 
<a name="l00835"></a>00835         <a class="code" href="classOscl__Rb__Tree.html#ac071f362746175733b302918c28991b4">link_type</a> clone_node(<a class="code" href="classOscl__Rb__Tree.html#ac071f362746175733b302918c28991b4">link_type</a> x)
<a name="l00836"></a>00836         {
<a name="l00837"></a>00837             <a class="code" href="classOscl__Rb__Tree.html#ac071f362746175733b302918c28991b4">link_type</a> tmp = create_node(x-&gt;value);
<a name="l00838"></a>00838             tmp-&gt;color = x-&gt;color;
<a name="l00839"></a>00839             tmp-&gt;left = 0;
<a name="l00840"></a>00840             tmp-&gt;right = 0;
<a name="l00841"></a>00841             <span class="keywordflow">return</span> tmp;
<a name="l00842"></a>00842         }
<a name="l00843"></a>00843 
<a name="l00844"></a>00844         <span class="keywordtype">void</span> distance(<a class="code" href="classOscl__Rb__Tree.html#a195be28f483579b902dd5fbcba9460fb">const_iterator</a> first, <a class="code" href="classOscl__Rb__Tree.html#a195be28f483579b902dd5fbcba9460fb">const_iterator</a> last, <a class="code" href="classOscl__Rb__Tree.html#a97bd6d64c71ea73b325eb5d349a93a68">size_type</a>&amp; n)<span class="keyword"> const</span>
<a name="l00845"></a>00845 <span class="keyword">        </span>{
<a name="l00846"></a>00846             <span class="keywordflow">while</span> (first != last)
<a name="l00847"></a>00847             {
<a name="l00848"></a>00848                 n++;
<a name="l00849"></a>00849                 first++;
<a name="l00850"></a>00850             }
<a name="l00851"></a>00851         }
<a name="l00852"></a>00852 
<a name="l00853"></a>00853         <span class="keywordtype">void</span> distance(<a class="code" href="classOscl__Rb__Tree.html#a5157f5b936d49b6d28ac52e5a826d37f">iterator</a> first, <a class="code" href="classOscl__Rb__Tree.html#a5157f5b936d49b6d28ac52e5a826d37f">iterator</a> last, <a class="code" href="classOscl__Rb__Tree.html#a97bd6d64c71ea73b325eb5d349a93a68">size_type</a>&amp; n)<span class="keyword"> const</span>
<a name="l00854"></a>00854 <span class="keyword">        </span>{
<a name="l00855"></a>00855             <span class="keywordflow">while</span> (first != last)
<a name="l00856"></a>00856             {
<a name="l00857"></a>00857                 n++;
<a name="l00858"></a>00858                 first++;
<a name="l00859"></a>00859             }
<a name="l00860"></a>00860         }
<a name="l00861"></a>00861 };
<a name="l00862"></a>00862 
<a name="l00863"></a>00863 
<a name="l00867"></a>00867 <span class="preprocessor">#endif</span>
<a name="l00868"></a>00868 <span class="preprocessor"></span>
</pre></div></div>
<hr size="1"><img src="pvlogo_small.jpg"><address style="align: right;"><small>OSCL API</small>
<address style="align: left;"><small>Posting Version: CORE_9.004.1.1 </small>
</small></address>
</body>
</html>