← Back to branch summary

~vaifrax/inkscape/bugfix170049

« back to all changes in this revision

Viewing changes to src/livarot/AVL.cpp

  • Committer: mental
  • Date: 2006-01-16 02:36:01 UTC
  • Revision ID: mental@users.sourceforge.net-20060116023601-wkr0h7edl5veyudq
moving trunk for module inkscape

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/livarot/AVL.cpp
 
1
/*
 
2
 *  AVL.cpp
 
3
 *  nlivarot
 
4
 *
 
5
 *  Created by fred on Mon Jun 16 2003.
 
6
 *
 
7
 */
 
8
 
 
9
#include "AVL.h"
 
10
 
 
11
/*
 
12
 * the algorithm explanation for this code comes from purists.org, which seems to have disappeared since
 
13
 * it's a classic AVL tree rebalancing, nothing fancy
 
14
 */
 
15
 
 
16
AVLTree::AVLTree()
 
17
{
 
18
    MakeNew();
 
19
}
 
20
 
 
21
AVLTree::~AVLTree()
 
22
{
 
23
    MakeDelete();
 
24
}
 
25
 
 
26
void AVLTree::MakeNew()
 
27
{
 
28
    for (int i = 0; i < 2; i++)
 
29
    {
 
30
        elem[i] = NULL;
 
31
        son[i] = NULL;
 
32
    }
 
33
 
 
34
    dad = NULL;
 
35
    balance = 0;
 
36
}
 
37
 
 
38
void AVLTree::MakeDelete()
 
39
{
 
40
    for (int i = 0; i < 2; i++) {
 
41
        if (elem[i]) {
 
42
            elem[i]->elem[1 - i] = elem[1 - i];
 
43
        }
 
44
        elem[i] = NULL;
 
45
    }
 
46
}
 
47
 
 
48
AVLTree *AVLTree::Leftmost()
 
49
{
 
50
    return leafFromDad(NULL, LEFT);
 
51
}
 
52
 
 
53
AVLTree *AVLTree::leaf(AVLTree *from, Side s)
 
54
{
 
55
    if (from == son[1 - s]) {
 
56
        if (son[s]) {
 
57
            return son[s]->leafFromDad(this, s);
 
58
        }
 
59
        else if (dad) {
 
60
            return dad->leaf(this, s);
 
61
        }
 
62
    }
 
63
    else if (from == son[s]) {
 
64
        if (dad) {
 
65
            return dad->leaf(this, s);
 
66
        }
 
67
    }
 
68
 
 
69
    return NULL;
 
70
}
 
71
 
 
72
AVLTree *AVLTree::leafFromDad(AVLTree *from, Side s)
 
73
{
 
74
    if (son[s]) {
 
75
        return son[s]->leafFromDad(this, s);
 
76
    }
 
77
 
 
78
    return this;
 
79
}
 
80
 
 
81
int
 
82
AVLTree::RestoreBalances (AVLTree * from, AVLTree * &racine)
 
83
{
 
84
  if (from == NULL)
 
85
    {
 
86
      if (dad)
 
87
        return dad->RestoreBalances (this, racine);
 
88
    }
 
89
  else
 
90
    {
 
91
      if (balance == 0)
 
92
        {
 
93
          if (from == son[LEFT])
 
94
            balance = 1;
 
95
          if (from == son[RIGHT])
 
96
            balance = -1;
 
97
          if (dad)
 
98
            return dad->RestoreBalances (this, racine);
 
99
          return avl_no_err;
 
100
        }
 
101
      else if (balance > 0)
 
102
        {
 
103
          if (from == son[RIGHT])
 
104
            {
 
105
              balance = 0;
 
106
              return avl_no_err;
 
107
            }
 
108
          if (son[LEFT] == NULL)
 
109
            {
 
110
//                              cout << "mierda\n";
 
111
              return avl_bal_err;
 
112
            }
 
113
          AVLTree *a = this;
 
114
          AVLTree *b = son[LEFT];
 
115
          AVLTree *e = son[RIGHT];
 
116
          AVLTree *c = son[LEFT]->son[LEFT];
 
117
          AVLTree *d = son[LEFT]->son[RIGHT];
 
118
          if (son[LEFT]->balance > 0)
 
119
            {
 
120
              AVLTree *r = dad;
 
121
 
 
122
              a->dad = b;
 
123
              b->son[RIGHT] = a;
 
124
              a->son[RIGHT] = e;
 
125
              if (e)
 
126
                e->dad = a;
 
127
              a->son[LEFT] = d;
 
128
              if (d)
 
129
                d->dad = a;
 
130
              b->son[LEFT] = c;
 
131
              if (c)
 
132
                c->dad = b;
 
133
              b->dad = r;
 
134
              if (r)
 
135
                {
 
136
                  if (r->son[LEFT] == a)
 
137
                    r->son[LEFT] = b;
 
138
                  if (r->son[RIGHT] == a)
 
139
                    r->son[RIGHT] = b;
 
140
                }
 
141
              if (racine == a)
 
142
                racine = b;
 
143
 
 
144
              a->balance = 0;
 
145
              b->balance = 0;
 
146
              return avl_no_err;
 
147
            }
 
148
          else
 
149
            {
 
150
              if (son[LEFT]->son[RIGHT] == NULL)
 
151
                {
 
152
                  //                              cout << "mierda\n";
 
153
                  return avl_bal_err;
 
154
                }
 
155
              AVLTree *f = son[LEFT]->son[RIGHT]->son[LEFT];
 
156
              AVLTree *g = son[LEFT]->son[RIGHT]->son[RIGHT];
 
157
              AVLTree *r = dad;
 
158
 
 
159
              a->dad = d;
 
160
              d->son[RIGHT] = a;
 
161
              b->dad = d;
 
162
              d->son[LEFT] = b;
 
163
              a->son[LEFT] = g;
 
164
              if (g)
 
165
                g->dad = a;
 
166
              a->son[RIGHT] = e;
 
167
              if (e)
 
168
                e->dad = a;
 
169
              b->son[LEFT] = c;
 
170
              if (c)
 
171
                c->dad = b;
 
172
              b->son[RIGHT] = f;
 
173
              if (f)
 
174
                f->dad = b;
 
175
 
 
176
              d->dad = r;
 
177
              if (r)
 
178
                {
 
179
                  if (r->son[LEFT] == a)
 
180
                    r->son[LEFT] = d;
 
181
                  if (r->son[RIGHT] == a)
 
182
                    r->son[RIGHT] = d;
 
183
                }
 
184
              if (racine == a)
 
185
                racine = d;
 
186
 
 
187
              int old_bal = d->balance;
 
188
              d->balance = 0;
 
189
              if (old_bal == 0)
 
190
                {
 
191
                  a->balance = 0;
 
192
                  b->balance = 0;
 
193
                }
 
194
              else if (old_bal > 0)
 
195
                {
 
196
                  a->balance = -1;
 
197
                  b->balance = 0;
 
198
                }
 
199
              else if (old_bal < 0)
 
200
                {
 
201
                  a->balance = 0;
 
202
                  b->balance = 1;
 
203
                }
 
204
              return avl_no_err;
 
205
            }
 
206
        }
 
207
      else if (balance < 0)
 
208
        {
 
209
          if (from == son[LEFT])
 
210
            {
 
211
              balance = 0;
 
212
              return avl_no_err;
 
213
            }
 
214
          if (son[RIGHT] == NULL)
 
215
            {
 
216
//                              cout << "mierda\n";
 
217
              return avl_bal_err;
 
218
            }
 
219
          AVLTree *a = this;
 
220
          AVLTree *b = son[RIGHT];
 
221
          AVLTree *e = son[LEFT];
 
222
          AVLTree *c = son[RIGHT]->son[RIGHT];
 
223
          AVLTree *d = son[RIGHT]->son[LEFT];
 
224
          AVLTree *r = dad;
 
225
          if (son[RIGHT]->balance < 0)
 
226
            {
 
227
 
 
228
              a->dad = b;
 
229
              b->son[LEFT] = a;
 
230
              a->son[LEFT] = e;
 
231
              if (e)
 
232
                e->dad = a;
 
233
              a->son[RIGHT] = d;
 
234
              if (d)
 
235
                d->dad = a;
 
236
              b->son[RIGHT] = c;
 
237
              if (c)
 
238
                c->dad = b;
 
239
              b->dad = r;
 
240
              if (r)
 
241
                {
 
242
                  if (r->son[LEFT] == a)
 
243
                    r->son[LEFT] = b;
 
244
                  if (r->son[RIGHT] == a)
 
245
                    r->son[RIGHT] = b;
 
246
                }
 
247
              if (racine == a)
 
248
                racine = b;
 
249
              a->balance = 0;
 
250
              b->balance = 0;
 
251
              return avl_no_err;
 
252
            }
 
253
          else
 
254
            {
 
255
              if (son[RIGHT]->son[LEFT] == NULL)
 
256
                {
 
257
//                                      cout << "mierda\n";
 
258
                  return avl_bal_err;
 
259
                }
 
260
              AVLTree *f = son[RIGHT]->son[LEFT]->son[RIGHT];
 
261
              AVLTree *g = son[RIGHT]->son[LEFT]->son[LEFT];
 
262
 
 
263
              a->dad = d;
 
264
              d->son[LEFT] = a;
 
265
              b->dad = d;
 
266
              d->son[RIGHT] = b;
 
267
              a->son[RIGHT] = g;
 
268
              if (g)
 
269
                g->dad = a;
 
270
              a->son[LEFT] = e;
 
271
              if (e)
 
272
                e->dad = a;
 
273
              b->son[RIGHT] = c;
 
274
              if (c)
 
275
                c->dad = b;
 
276
              b->son[LEFT] = f;
 
277
              if (f)
 
278
                f->dad = b;
 
279
 
 
280
              d->dad = r;
 
281
              if (r)
 
282
                {
 
283
                  if (r->son[LEFT] == a)
 
284
                    r->son[LEFT] = d;
 
285
                  if (r->son[RIGHT] == a)
 
286
                    r->son[RIGHT] = d;
 
287
                }
 
288
              if (racine == a)
 
289
                racine = d;
 
290
              int old_bal = d->balance;
 
291
              d->balance = 0;
 
292
              if (old_bal == 0)
 
293
                {
 
294
                  a->balance = 0;
 
295
                  b->balance = 0;
 
296
                }
 
297
              else if (old_bal > 0)
 
298
                {
 
299
                  a->balance = 0;
 
300
                  b->balance = -1;
 
301
                }
 
302
              else if (old_bal < 0)
 
303
                {
 
304
                  a->balance = 1;
 
305
                  b->balance = 0;
 
306
                }
 
307
              return avl_no_err;
 
308
            }
 
309
        }
 
310
    }
 
311
  return avl_no_err;
 
312
}
 
313
 
 
314
int
 
315
AVLTree::RestoreBalances (int diff, AVLTree * &racine)
 
316
{
 
317
  if (balance > 0)
 
318
    {
 
319
      if (diff < 0)
 
320
        {
 
321
          balance = 0;
 
322
          if (dad)
 
323
            {
 
324
              if (this == dad->son[RIGHT])
 
325
                return dad->RestoreBalances (1, racine);
 
326
              if (this == dad->son[LEFT])
 
327
                return dad->RestoreBalances (-1, racine);
 
328
            }
 
329
          return avl_no_err;
 
330
        }
 
331
      else if (diff == 0)
 
332
        {
 
333
        }
 
334
      else if (diff > 0)
 
335
        {
 
336
          if (son[LEFT] == NULL)
 
337
            {
 
338
//                              cout << "un probleme\n";
 
339
              return avl_bal_err;
 
340
            }
 
341
          AVLTree *r = dad;
 
342
          AVLTree *a = this;
 
343
          AVLTree *b = son[RIGHT];
 
344
          AVLTree *e = son[LEFT];
 
345
          AVLTree *f = e->son[RIGHT];
 
346
          AVLTree *g = e->son[LEFT];
 
347
          if (e->balance > 0)
 
348
            {
 
349
              e->son[RIGHT] = a;
 
350
              e->son[LEFT] = g;
 
351
              a->son[RIGHT] = b;
 
352
              a->son[LEFT] = f;
 
353
              if (a)
 
354
                a->dad = e;
 
355
              if (g)
 
356
                g->dad = e;
 
357
              if (b)
 
358
                b->dad = a;
 
359
              if (f)
 
360
                f->dad = a;
 
361
              e->dad = r;
 
362
              if (r)
 
363
                {
 
364
                  if (r->son[LEFT] == a)
 
365
                    r->son[LEFT] = e;
 
366
                  if (r->son[RIGHT] == a)
 
367
                    r->son[RIGHT] = e;
 
368
                }
 
369
              if (racine == this)
 
370
                racine = e;
 
371
              e->balance = 0;
 
372
              a->balance = 0;
 
373
              if (r)
 
374
                {
 
375
                  if (e == r->son[RIGHT])
 
376
                    return r->RestoreBalances (1, racine);
 
377
                  if (e == r->son[LEFT])
 
378
                    return r->RestoreBalances (-1, racine);
 
379
                }
 
380
              return avl_no_err;
 
381
            }
 
382
          else if (e->balance == 0)
 
383
            {
 
384
              e->son[RIGHT] = a;
 
385
              e->son[LEFT] = g;
 
386
              a->son[RIGHT] = b;
 
387
              a->son[LEFT] = f;
 
388
              if (a)
 
389
                a->dad = e;
 
390
              if (g)
 
391
                g->dad = e;
 
392
              if (b)
 
393
                b->dad = a;
 
394
              if (f)
 
395
                f->dad = a;
 
396
              e->dad = r;
 
397
              if (r)
 
398
                {
 
399
                  if (r->son[LEFT] == a)
 
400
                    r->son[LEFT] = e;
 
401
                  if (r->son[RIGHT] == a)
 
402
                    r->son[RIGHT] = e;
 
403
                }
 
404
              if (racine == this)
 
405
                racine = e;
 
406
              e->balance = -1;
 
407
              a->balance = 1;
 
408
              return avl_no_err;
 
409
            }
 
410
          else if (e->balance < 0)
 
411
            {
 
412
              if (son[LEFT]->son[RIGHT] == NULL)
 
413
                {
 
414
//                                      cout << "un probleme\n";
 
415
                  return avl_bal_err;
 
416
                }
 
417
              AVLTree *i = son[LEFT]->son[RIGHT]->son[RIGHT];
 
418
              AVLTree *j = son[LEFT]->son[RIGHT]->son[LEFT];
 
419
 
 
420
              f->son[RIGHT] = a;
 
421
              f->son[LEFT] = e;
 
422
              a->son[RIGHT] = b;
 
423
              a->son[LEFT] = i;
 
424
              e->son[RIGHT] = j;
 
425
              e->son[LEFT] = g;
 
426
              if (b)
 
427
                b->dad = a;
 
428
              if (i)
 
429
                i->dad = a;
 
430
              if (g)
 
431
                g->dad = e;
 
432
              if (j)
 
433
                j->dad = e;
 
434
              if (a)
 
435
                a->dad = f;
 
436
              if (e)
 
437
                e->dad = f;
 
438
              f->dad = r;
 
439
              if (r)
 
440
                {
 
441
                  if (r->son[LEFT] == a)
 
442
                    r->son[LEFT] = f;
 
443
                  if (r->son[RIGHT] == a)
 
444
                    r->son[RIGHT] = f;
 
445
                }
 
446
              if (racine == this)
 
447
                racine = f;
 
448
              int oBal = f->balance;
 
449
              f->balance = 0;
 
450
              if (oBal > 0)
 
451
                {
 
452
                  a->balance = -1;
 
453
                  e->balance = 0;
 
454
                }
 
455
              else if (oBal == 0)
 
456
                {
 
457
                  a->balance = 0;
 
458
                  e->balance = 0;
 
459
                }
 
460
              else if (oBal < 0)
 
461
                {
 
462
                  a->balance = 0;
 
463
                  e->balance = 1;
 
464
                }
 
465
              if (r)
 
466
                {
 
467
                  if (f == r->son[RIGHT])
 
468
                    return r->RestoreBalances (1, racine);
 
469
                  if (f == r->son[LEFT])
 
470
                    return r->RestoreBalances (-1, racine);
 
471
                }
 
472
              return avl_no_err;
 
473
            }
 
474
        }
 
475
    }
 
476
  else if (balance == 0)
 
477
    {
 
478
      if (diff < 0)
 
479
        {
 
480
          balance = -1;
 
481
        }
 
482
      else if (diff == 0)
 
483
        {
 
484
        }
 
485
      else if (diff > 0)
 
486
        {
 
487
          balance = 1;
 
488
        }
 
489
      return avl_no_err;
 
490
    }
 
491
  else if (balance < 0)
 
492
    {
 
493
      if (diff < 0)
 
494
        {
 
495
          if (son[RIGHT] == NULL)
 
496
            {
 
497
//                              cout << "un probleme\n";
 
498
              return avl_bal_err;
 
499
            }
 
500
          AVLTree *r = dad;
 
501
          AVLTree *a = this;
 
502
          AVLTree *b = son[LEFT];
 
503
          AVLTree *e = son[RIGHT];
 
504
          AVLTree *f = e->son[LEFT];
 
505
          AVLTree *g = e->son[RIGHT];
 
506
          if (e->balance < 0)
 
507
            {
 
508
              e->son[LEFT] = a;
 
509
              e->son[RIGHT] = g;
 
510
              a->son[LEFT] = b;
 
511
              a->son[RIGHT] = f;
 
512
              if (a)
 
513
                a->dad = e;
 
514
              if (g)
 
515
                g->dad = e;
 
516
              if (b)
 
517
                b->dad = a;
 
518
              if (f)
 
519
                f->dad = a;
 
520
              e->dad = r;
 
521
              if (r)
 
522
                {
 
523
                  if (r->son[LEFT] == a)
 
524
                    r->son[LEFT] = e;
 
525
                  if (r->son[RIGHT] == a)
 
526
                    r->son[RIGHT] = e;
 
527
                }
 
528
              if (racine == this)
 
529
                racine = e;
 
530
              e->balance = 0;
 
531
              a->balance = 0;
 
532
              if (r)
 
533
                {
 
534
                  if (e == r->son[RIGHT])
 
535
                    return r->RestoreBalances (1, racine);
 
536
                  if (e == r->son[LEFT])
 
537
                    return r->RestoreBalances (-1, racine);
 
538
                }
 
539
              return avl_no_err;
 
540
            }
 
541
          else if (e->balance == 0)
 
542
            {
 
543
              e->son[LEFT] = a;
 
544
              e->son[RIGHT] = g;
 
545
              a->son[LEFT] = b;
 
546
              a->son[RIGHT] = f;
 
547
              if (a)
 
548
                a->dad = e;
 
549
              if (g)
 
550
                g->dad = e;
 
551
              if (b)
 
552
                b->dad = a;
 
553
              if (f)
 
554
                f->dad = a;
 
555
              e->dad = r;
 
556
              if (r)
 
557
                {
 
558
                  if (r->son[LEFT] == a)
 
559
                    r->son[LEFT] = e;
 
560
                  if (r->son[RIGHT] == a)
 
561
                    r->son[RIGHT] = e;
 
562
                }
 
563
              if (racine == this)
 
564
                racine = e;
 
565
              e->balance = 1;
 
566
              a->balance = -1;
 
567
              return avl_no_err;
 
568
            }
 
569
          else if (e->balance > 0)
 
570
            {
 
571
              if (son[RIGHT]->son[LEFT] == NULL)
 
572
                {
 
573
//                                      cout << "un probleme\n";
 
574
                  return avl_bal_err;
 
575
                }
 
576
              AVLTree *i = son[RIGHT]->son[LEFT]->son[LEFT];
 
577
              AVLTree *j = son[RIGHT]->son[LEFT]->son[RIGHT];
 
578
 
 
579
              f->son[LEFT] = a;
 
580
              f->son[RIGHT] = e;
 
581
              a->son[LEFT] = b;
 
582
              a->son[RIGHT] = i;
 
583
              e->son[LEFT] = j;
 
584
              e->son[RIGHT] = g;
 
585
              if (b)
 
586
                b->dad = a;
 
587
              if (i)
 
588
                i->dad = a;
 
589
              if (g)
 
590
                g->dad = e;
 
591
              if (j)
 
592
                j->dad = e;
 
593
              if (a)
 
594
                a->dad = f;
 
595
              if (e)
 
596
                e->dad = f;
 
597
              f->dad = r;
 
598
              if (r)
 
599
                {
 
600
                  if (r->son[LEFT] == a)
 
601
                    r->son[LEFT] = f;
 
602
                  if (r->son[RIGHT] == a)
 
603
                    r->son[RIGHT] = f;
 
604
                }
 
605
              if (racine == this)
 
606
                racine = f;
 
607
              int oBal = f->balance;
 
608
              f->balance = 0;
 
609
              if (oBal > 0)
 
610
                {
 
611
                  a->balance = 0;
 
612
                  e->balance = -1;
 
613
                }
 
614
              else if (oBal == 0)
 
615
                {
 
616
                  a->balance = 0;
 
617
                  e->balance = 0;
 
618
                }
 
619
              else if (oBal < 0)
 
620
                {
 
621
                  a->balance = 1;
 
622
                  e->balance = 0;
 
623
                }
 
624
              if (r)
 
625
                {
 
626
                  if (f == r->son[RIGHT])
 
627
                    return r->RestoreBalances (1, racine);
 
628
                  if (f == r->son[LEFT])
 
629
                    return r->RestoreBalances (-1, racine);
 
630
                }
 
631
              return avl_no_err;
 
632
            }
 
633
        }
 
634
      else if (diff == 0)
 
635
        {
 
636
        }
 
637
      else if (diff > 0)
 
638
        {
 
639
          balance = 0;
 
640
          if (dad)
 
641
            {
 
642
              if (this == dad->son[RIGHT])
 
643
                return dad->RestoreBalances (1, racine);
 
644
              if (this == dad->son[LEFT])
 
645
                return dad->RestoreBalances (-1, racine);
 
646
            }
 
647
          return avl_no_err;
 
648
        }
 
649
    }
 
650
  return avl_no_err;
 
651
}
 
652
 
 
653
/*
 
654
 * removal
 
655
 */
 
656
int
 
657
AVLTree::Remove (AVLTree * &racine, bool rebalance)
 
658
{
 
659
  AVLTree *startNode = NULL;
 
660
  int remDiff = 0;
 
661
  int res = Remove (racine, startNode, remDiff);
 
662
  if (res == avl_no_err && rebalance && startNode)
 
663
    res = startNode->RestoreBalances (remDiff, racine);
 
664
  return res;
 
665
}
 
666
 
 
667
int
 
668
AVLTree::Remove (AVLTree * &racine, AVLTree * &startNode, int &diff)
 
669
{
 
670
  if (elem[LEFT])
 
671
    elem[LEFT]->elem[RIGHT] = elem[RIGHT];
 
672
  if (elem[RIGHT])
 
673
    elem[RIGHT]->elem[LEFT] = elem[LEFT];
 
674
  elem[LEFT] = elem[RIGHT] = NULL;
 
675
 
 
676
  if (son[LEFT] && son[RIGHT])
 
677
    {
 
678
      AVLTree *newMe = son[LEFT]->leafFromDad(this, RIGHT);
 
679
      if (newMe == NULL || newMe->son[RIGHT])
 
680
        {
 
681
//                      cout << "pas normal\n";
 
682
          return avl_rm_err;
 
683
        }
 
684
      if (newMe == son[LEFT])
 
685
        {
 
686
          startNode = newMe;
 
687
          diff = -1;
 
688
          newMe->son[RIGHT] = son[RIGHT];
 
689
          son[RIGHT]->dad = newMe;
 
690
          newMe->dad = dad;
 
691
          if (dad)
 
692
            {
 
693
              if (dad->son[LEFT] == this)
 
694
                dad->son[LEFT] = newMe;
 
695
              if (dad->son[RIGHT] == this)
 
696
                dad->son[RIGHT] = newMe;
 
697
            }
 
698
        }
 
699
      else
 
700
        {
 
701
          AVLTree *oDad = newMe->dad;
 
702
          startNode = oDad;
 
703
          diff = 1;
 
704
 
 
705
          oDad->son[RIGHT] = newMe->son[LEFT];
 
706
          if (newMe->son[LEFT])
 
707
            newMe->son[LEFT]->dad = oDad;
 
708
 
 
709
          newMe->dad = dad;
 
710
          newMe->son[LEFT] = son[LEFT];
 
711
          newMe->son[RIGHT] = son[RIGHT];
 
712
          if (dad)
 
713
            {
 
714
              if (dad->son[LEFT] == this)
 
715
                dad->son[LEFT] = newMe;
 
716
              if (dad->son[RIGHT] == this)
 
717
                dad->son[RIGHT] = newMe;
 
718
            }
 
719
          if (son[LEFT])
 
720
            son[LEFT]->dad = newMe;
 
721
          if (son[RIGHT])
 
722
            son[RIGHT]->dad = newMe;
 
723
        }
 
724
      newMe->balance = balance;
 
725
      if (racine == this)
 
726
        racine = newMe;
 
727
    }
 
728
  else if (son[LEFT])
 
729
    {
 
730
      startNode = dad;
 
731
      diff = 0;
 
732
      if (dad)
 
733
        {
 
734
          if (this == dad->son[LEFT])
 
735
            diff = -1;
 
736
          if (this == dad->son[RIGHT])
 
737
            diff = 1;
 
738
        }
 
739
      if (dad)
 
740
        {
 
741
          if (dad->son[LEFT] == this)
 
742
            dad->son[LEFT] = son[LEFT];
 
743
          if (dad->son[RIGHT] == this)
 
744
            dad->son[RIGHT] = son[LEFT];
 
745
        }
 
746
      if (son[LEFT]->dad == this)
 
747
        son[LEFT]->dad = dad;
 
748
      if (racine == this)
 
749
        racine = son[LEFT];
 
750
    }
 
751
  else if (son[RIGHT])
 
752
    {
 
753
      startNode = dad;
 
754
      diff = 0;
 
755
      if (dad)
 
756
        {
 
757
          if (this == dad->son[LEFT])
 
758
            diff = -1;
 
759
          if (this == dad->son[RIGHT])
 
760
            diff = 1;
 
761
        }
 
762
      if (dad)
 
763
        {
 
764
          if (dad->son[LEFT] == this)
 
765
            dad->son[LEFT] = son[RIGHT];
 
766
          if (dad->son[RIGHT] == this)
 
767
            dad->son[RIGHT] = son[RIGHT];
 
768
        }
 
769
      if (son[RIGHT]->dad == this)
 
770
        son[RIGHT]->dad = dad;
 
771
      if (racine == this)
 
772
        racine = son[RIGHT];
 
773
    }
 
774
  else
 
775
    {
 
776
      startNode = dad;
 
777
      diff = 0;
 
778
      if (dad)
 
779
        {
 
780
          if (this == dad->son[LEFT])
 
781
            diff = -1;
 
782
          if (this == dad->son[RIGHT])
 
783
            diff = 1;
 
784
        }
 
785
      if (dad)
 
786
        {
 
787
          if (dad->son[LEFT] == this)
 
788
            dad->son[LEFT] = NULL;
 
789
          if (dad->son[RIGHT] == this)
 
790
            dad->son[RIGHT] = NULL;
 
791
        }
 
792
      if (racine == this)
 
793
        racine = NULL;
 
794
    }
 
795
  dad = son[RIGHT] = son[LEFT] = NULL;
 
796
  balance = 0;
 
797
  return avl_no_err;
 
798
}
 
799
 
 
800
/*
 
801
 * insertion
 
802
 */
 
803
int
 
804
AVLTree::Insert (AVLTree * &racine, int insertType, AVLTree * insertL,
 
805
                 AVLTree * insertR, bool rebalance)
 
806
{
 
807
  int res = Insert (racine, insertType, insertL, insertR);
 
808
  if (res == avl_no_err && rebalance)
 
809
    res = RestoreBalances ((AVLTree *) NULL, racine);
 
810
  return res;
 
811
}
 
812
 
 
813
int
 
814
AVLTree::Insert (AVLTree * &racine, int insertType, AVLTree * insertL,
 
815
                 AVLTree * insertR)
 
816
{
 
817
  if (racine == NULL)
 
818
    {
 
819
      racine = this;
 
820
      return avl_no_err;
 
821
    }
 
822
  else
 
823
    {
 
824
      if (insertType == not_found)
 
825
        {
 
826
//                      cout << "pb avec l'arbre de raster\n";
 
827
          return avl_ins_err;
 
828
        }
 
829
      else if (insertType == found_on_left)
 
830
        {
 
831
          if (insertR == NULL || insertR->son[LEFT])
 
832
            {
 
833
//                              cout << "ngou?\n";
 
834
              return avl_ins_err;
 
835
            }
 
836
          insertR->son[LEFT] = this;
 
837
          dad = insertR;
 
838
          insertOn(LEFT, insertR);
 
839
        }
 
840
      else if (insertType == found_on_right)
 
841
        {
 
842
          if (insertL == NULL || insertL->son[RIGHT])
 
843
            {
 
844
//                              cout << "ngou?\n";
 
845
              return avl_ins_err;
 
846
            }
 
847
          insertL->son[RIGHT] = this;
 
848
          dad = insertL;
 
849
          insertOn(RIGHT, insertL);
 
850
        }
 
851
      else if (insertType == found_between)
 
852
        {
 
853
          if (insertR == NULL || insertL == NULL
 
854
              || (insertR->son[LEFT] != NULL && insertL->son[RIGHT] != NULL))
 
855
            {
 
856
//                              cout << "ngou?\n";
 
857
              return avl_ins_err;
 
858
            }
 
859
          if (insertR->son[LEFT] == NULL)
 
860
            {
 
861
              insertR->son[LEFT] = this;
 
862
              dad = insertR;
 
863
            }
 
864
          else if (insertL->son[RIGHT] == NULL)
 
865
            {
 
866
              insertL->son[RIGHT] = this;
 
867
              dad = insertL;
 
868
            }
 
869
          insertBetween (insertL, insertR);
 
870
        }
 
871
      else if (insertType == found_exact)
 
872
        {
 
873
          if (insertL == NULL)
 
874
            {
 
875
//                              cout << "ngou?\n";
 
876
              return avl_ins_err;
 
877
            }
 
878
          // et on insere
 
879
 
 
880
          if (insertL->son[RIGHT])
 
881
            {
 
882
                insertL = insertL->son[RIGHT]->leafFromDad(insertL, LEFT);
 
883
              if (insertL->son[LEFT])
 
884
                {
 
885
//                                      cout << "ngou?\n";
 
886
                  return avl_ins_err;
 
887
                }
 
888
              insertL->son[LEFT] = this;
 
889
              this->dad = insertL;
 
890
              insertBetween (insertL->elem[LEFT], insertL);
 
891
            }
 
892
          else
 
893
            {
 
894
              insertL->son[RIGHT] = this;
 
895
              dad = insertL;
 
896
              insertBetween (insertL, insertL->elem[RIGHT]);
 
897
            }
 
898
        }
 
899
      else
 
900
        {
 
901
          //                      cout << "code incorrect\n";
 
902
          return avl_ins_err;
 
903
        }
 
904
    }
 
905
  return avl_no_err;
 
906
}
 
907
 
 
908
void
 
909
AVLTree::Relocate (AVLTree * to)
 
910
{
 
911
  if (elem[LEFT])
 
912
    elem[LEFT]->elem[RIGHT] = to;
 
913
  if (elem[RIGHT])
 
914
    elem[RIGHT]->elem[LEFT] = to;
 
915
  to->elem[LEFT] = elem[LEFT];
 
916
  to->elem[RIGHT] = elem[RIGHT];
 
917
    
 
918
  if (dad)
 
919
    {
 
920
      if (dad->son[LEFT] == this)
 
921
        dad->son[LEFT] = to;
 
922
      if (dad->son[RIGHT] == this)
 
923
        dad->son[RIGHT] = to;
 
924
    }
 
925
  if (son[RIGHT])
 
926
    {
 
927
      son[RIGHT]->dad = to;
 
928
    }
 
929
  if (son[LEFT])
 
930
    {
 
931
      son[LEFT]->dad = to;
 
932
    }
 
933
  to->dad = dad;
 
934
  to->son[RIGHT] = son[RIGHT];
 
935
  to->son[LEFT] = son[LEFT];
 
936
}
 
937
 
 
938
 
 
939
void AVLTree::insertOn(Side s, AVLTree *of)
 
940
{
 
941
  elem[1 - s] = of;
 
942
  if (of)
 
943
    of->elem[s] = this;
 
944
}
 
945
 
 
946
void AVLTree::insertBetween(AVLTree *l, AVLTree *r)
 
947
{
 
948
  if (l)
 
949
    l->elem[RIGHT] = this;
 
950
  if (r)
 
951
    r->elem[LEFT] = this;
 
952
  elem[LEFT] = l;
 
953
  elem[RIGHT] = r;
 
954
}
 
955
 
 
956
/*
 
957
  Local Variables:
 
958
  mode:c++
 
959
  c-file-style:"stroustrup"
 
960
  c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +))
 
961
  indent-tabs-mode:nil
 
962
  fill-column:99
 
963
  End:
 
964
*/
 
965
// vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:encoding=utf-8:textwidth=99 :