OLD | NEW |
1 | 1 |
2 /* | 2 /* |
3 * Copyright 2011 Google Inc. | 3 * Copyright 2011 Google Inc. |
4 * | 4 * |
5 * Use of this source code is governed by a BSD-style license that can be | 5 * Use of this source code is governed by a BSD-style license that can be |
6 * found in the LICENSE file. | 6 * found in the LICENSE file. |
7 */ | 7 */ |
8 | 8 |
9 | 9 |
10 #ifndef GrRedBlackTree_DEFINED | 10 #ifndef GrRedBlackTree_DEFINED |
(...skipping 178 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
189 return *this; | 189 return *this; |
190 } | 190 } |
191 // altering the sort value of the item using this method will cause | 191 // altering the sort value of the item using this method will cause |
192 // errors. | 192 // errors. |
193 T& operator *() const { return fN->fItem; } | 193 T& operator *() const { return fN->fItem; } |
194 bool operator ==(const Iter& i) const { | 194 bool operator ==(const Iter& i) const { |
195 return fN == i.fN && fTree == i.fTree; | 195 return fN == i.fN && fTree == i.fTree; |
196 } | 196 } |
197 bool operator !=(const Iter& i) const { return !(*this == i); } | 197 bool operator !=(const Iter& i) const { return !(*this == i); } |
198 Iter& operator ++() { | 198 Iter& operator ++() { |
199 GrAssert(*this != fTree->end()); | 199 SkASSERT(*this != fTree->end()); |
200 fN = SuccessorNode(fN); | 200 fN = SuccessorNode(fN); |
201 return *this; | 201 return *this; |
202 } | 202 } |
203 Iter& operator --() { | 203 Iter& operator --() { |
204 GrAssert(*this != fTree->begin()); | 204 SkASSERT(*this != fTree->begin()); |
205 if (NULL != fN) { | 205 if (NULL != fN) { |
206 fN = PredecessorNode(fN); | 206 fN = PredecessorNode(fN); |
207 } else { | 207 } else { |
208 *this = fTree->last(); | 208 *this = fTree->last(); |
209 } | 209 } |
210 return *this; | 210 return *this; |
211 } | 211 } |
212 | 212 |
213 private: | 213 private: |
214 friend class GrRedBlackTree; | 214 friend class GrRedBlackTree; |
(...skipping 156 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
371 fLast = x; | 371 fLast = x; |
372 } | 372 } |
373 if (first) { | 373 if (first) { |
374 fFirst = x; | 374 fFirst = x; |
375 } | 375 } |
376 | 376 |
377 if (NULL == p) { | 377 if (NULL == p) { |
378 fRoot = x; | 378 fRoot = x; |
379 x->fColor = kBlack_Color; | 379 x->fColor = kBlack_Color; |
380 x->fParent = NULL; | 380 x->fParent = NULL; |
381 GrAssert(1 == fCount); | 381 SkASSERT(1 == fCount); |
382 return Iter(returnNode, this); | 382 return Iter(returnNode, this); |
383 } | 383 } |
384 p->fChildren[pc] = x; | 384 p->fChildren[pc] = x; |
385 x->fColor = kRed_Color; | 385 x->fColor = kRed_Color; |
386 x->fParent = p; | 386 x->fParent = p; |
387 | 387 |
388 do { | 388 do { |
389 // assumptions at loop start. | 389 // assumptions at loop start. |
390 GrAssert(NULL != x); | 390 SkASSERT(NULL != x); |
391 GrAssert(kRed_Color == x->fColor); | 391 SkASSERT(kRed_Color == x->fColor); |
392 // can't have a grandparent but no parent. | 392 // can't have a grandparent but no parent. |
393 GrAssert(!(NULL != gp && NULL == p)); | 393 SkASSERT(!(NULL != gp && NULL == p)); |
394 // make sure pc and gpc are correct | 394 // make sure pc and gpc are correct |
395 GrAssert(NULL == p || p->fChildren[pc] == x); | 395 SkASSERT(NULL == p || p->fChildren[pc] == x); |
396 GrAssert(NULL == gp || gp->fChildren[gpc] == p); | 396 SkASSERT(NULL == gp || gp->fChildren[gpc] == p); |
397 | 397 |
398 // if x's parent is black then we didn't violate any of the | 398 // if x's parent is black then we didn't violate any of the |
399 // red/black properties when we added x as red. | 399 // red/black properties when we added x as red. |
400 if (kBlack_Color == p->fColor) { | 400 if (kBlack_Color == p->fColor) { |
401 return Iter(returnNode, this); | 401 return Iter(returnNode, this); |
402 } | 402 } |
403 // gp must be valid because if p was the root then it is black | 403 // gp must be valid because if p was the root then it is black |
404 GrAssert(NULL != gp); | 404 SkASSERT(NULL != gp); |
405 // gp must be black since it's child, p, is red. | 405 // gp must be black since it's child, p, is red. |
406 GrAssert(kBlack_Color == gp->fColor); | 406 SkASSERT(kBlack_Color == gp->fColor); |
407 | 407 |
408 | 408 |
409 // x and its parent are red, violating red-black property. | 409 // x and its parent are red, violating red-black property. |
410 Node* u = gp->fChildren[1-gpc]; | 410 Node* u = gp->fChildren[1-gpc]; |
411 // if x's uncle (p's sibling) is also red then we can flip | 411 // if x's uncle (p's sibling) is also red then we can flip |
412 // p and u to black and make gp red. But then we have to recurse | 412 // p and u to black and make gp red. But then we have to recurse |
413 // up to gp since it's parent may also be red. | 413 // up to gp since it's parent may also be red. |
414 if (NULL != u && kRed_Color == u->fColor) { | 414 if (NULL != u && kRed_Color == u->fColor) { |
415 p->fColor = kBlack_Color; | 415 p->fColor = kBlack_Color; |
416 u->fColor = kBlack_Color; | 416 u->fColor = kBlack_Color; |
417 gp->fColor = kRed_Color; | 417 gp->fColor = kRed_Color; |
418 x = gp; | 418 x = gp; |
419 p = x->fParent; | 419 p = x->fParent; |
420 if (NULL == p) { | 420 if (NULL == p) { |
421 // x (prev gp) is the root, color it black and be done. | 421 // x (prev gp) is the root, color it black and be done. |
422 GrAssert(fRoot == x); | 422 SkASSERT(fRoot == x); |
423 x->fColor = kBlack_Color; | 423 x->fColor = kBlack_Color; |
424 validate(); | 424 validate(); |
425 return Iter(returnNode, this); | 425 return Iter(returnNode, this); |
426 } | 426 } |
427 gp = p->fParent; | 427 gp = p->fParent; |
428 pc = (p->fChildren[kLeft_Child] == x) ? kLeft_Child : | 428 pc = (p->fChildren[kLeft_Child] == x) ? kLeft_Child : |
429 kRight_Child; | 429 kRight_Child; |
430 if (NULL != gp) { | 430 if (NULL != gp) { |
431 gpc = (gp->fChildren[kLeft_Child] == p) ? kLeft_Child : | 431 gpc = (gp->fChildren[kLeft_Child] == p) ? kLeft_Child : |
432 kRight_Child; | 432 kRight_Child; |
433 } | 433 } |
434 continue; | 434 continue; |
435 } break; | 435 } break; |
436 } while (true); | 436 } while (true); |
437 // Here p is red but u is black and we still have to resolve the fact | 437 // Here p is red but u is black and we still have to resolve the fact |
438 // that x and p are both red. | 438 // that x and p are both red. |
439 GrAssert(NULL == gp->fChildren[1-gpc] || kBlack_Color == gp->fChildren[1-gpc
]->fColor); | 439 SkASSERT(NULL == gp->fChildren[1-gpc] || kBlack_Color == gp->fChildren[1-gpc
]->fColor); |
440 GrAssert(kRed_Color == x->fColor); | 440 SkASSERT(kRed_Color == x->fColor); |
441 GrAssert(kRed_Color == p->fColor); | 441 SkASSERT(kRed_Color == p->fColor); |
442 GrAssert(kBlack_Color == gp->fColor); | 442 SkASSERT(kBlack_Color == gp->fColor); |
443 | 443 |
444 // make x be on the same side of p as p is of gp. If it isn't already | 444 // make x be on the same side of p as p is of gp. If it isn't already |
445 // the case then rotate x up to p and swap their labels. | 445 // the case then rotate x up to p and swap their labels. |
446 if (pc != gpc) { | 446 if (pc != gpc) { |
447 if (kRight_Child == pc) { | 447 if (kRight_Child == pc) { |
448 rotateLeft(p); | 448 rotateLeft(p); |
449 Node* temp = p; | 449 Node* temp = p; |
450 p = x; | 450 p = x; |
451 x = temp; | 451 x = temp; |
452 pc = kLeft_Child; | 452 pc = kLeft_Child; |
453 } else { | 453 } else { |
454 rotateRight(p); | 454 rotateRight(p); |
455 Node* temp = p; | 455 Node* temp = p; |
456 p = x; | 456 p = x; |
457 x = temp; | 457 x = temp; |
458 pc = kRight_Child; | 458 pc = kRight_Child; |
459 } | 459 } |
460 } | 460 } |
461 // we now rotate gp down, pulling up p to be it's new parent. | 461 // we now rotate gp down, pulling up p to be it's new parent. |
462 // gp's child, u, that is not affected we know to be black. gp's new | 462 // gp's child, u, that is not affected we know to be black. gp's new |
463 // child is p's previous child (x's pre-rotation sibling) which must be | 463 // child is p's previous child (x's pre-rotation sibling) which must be |
464 // black since p is red. | 464 // black since p is red. |
465 GrAssert(NULL == p->fChildren[1-pc] || | 465 SkASSERT(NULL == p->fChildren[1-pc] || |
466 kBlack_Color == p->fChildren[1-pc]->fColor); | 466 kBlack_Color == p->fChildren[1-pc]->fColor); |
467 // Since gp's two children are black it can become red if p is made | 467 // Since gp's two children are black it can become red if p is made |
468 // black. This leaves the black-height of both of p's new subtrees | 468 // black. This leaves the black-height of both of p's new subtrees |
469 // preserved and removes the red/red parent child relationship. | 469 // preserved and removes the red/red parent child relationship. |
470 p->fColor = kBlack_Color; | 470 p->fColor = kBlack_Color; |
471 gp->fColor = kRed_Color; | 471 gp->fColor = kRed_Color; |
472 if (kLeft_Child == pc) { | 472 if (kLeft_Child == pc) { |
473 rotateRight(gp); | 473 rotateRight(gp); |
474 } else { | 474 } else { |
475 rotateLeft(gp); | 475 rotateLeft(gp); |
476 } | 476 } |
477 validate(); | 477 validate(); |
478 return Iter(returnNode, this); | 478 return Iter(returnNode, this); |
479 } | 479 } |
480 | 480 |
481 | 481 |
482 template <typename T, typename C> | 482 template <typename T, typename C> |
483 void GrRedBlackTree<T,C>::rotateRight(Node* n) { | 483 void GrRedBlackTree<T,C>::rotateRight(Node* n) { |
484 /* d? d? | 484 /* d? d? |
485 * / / | 485 * / / |
486 * n s | 486 * n s |
487 * / \ ---> / \ | 487 * / \ ---> / \ |
488 * s a? c? n | 488 * s a? c? n |
489 * / \ / \ | 489 * / \ / \ |
490 * c? b? b? a? | 490 * c? b? b? a? |
491 */ | 491 */ |
492 Node* d = n->fParent; | 492 Node* d = n->fParent; |
493 Node* s = n->fChildren[kLeft_Child]; | 493 Node* s = n->fChildren[kLeft_Child]; |
494 GrAssert(NULL != s); | 494 SkASSERT(NULL != s); |
495 Node* b = s->fChildren[kRight_Child]; | 495 Node* b = s->fChildren[kRight_Child]; |
496 | 496 |
497 if (NULL != d) { | 497 if (NULL != d) { |
498 Child c = d->fChildren[kLeft_Child] == n ? kLeft_Child : | 498 Child c = d->fChildren[kLeft_Child] == n ? kLeft_Child : |
499 kRight_Child; | 499 kRight_Child; |
500 d->fChildren[c] = s; | 500 d->fChildren[c] = s; |
501 } else { | 501 } else { |
502 GrAssert(fRoot == n); | 502 SkASSERT(fRoot == n); |
503 fRoot = s; | 503 fRoot = s; |
504 } | 504 } |
505 s->fParent = d; | 505 s->fParent = d; |
506 s->fChildren[kRight_Child] = n; | 506 s->fChildren[kRight_Child] = n; |
507 n->fParent = s; | 507 n->fParent = s; |
508 n->fChildren[kLeft_Child] = b; | 508 n->fChildren[kLeft_Child] = b; |
509 if (NULL != b) { | 509 if (NULL != b) { |
510 b->fParent = n; | 510 b->fParent = n; |
511 } | 511 } |
512 | 512 |
513 GR_DEBUGASSERT(validateChildRelations(d, true)); | 513 GR_DEBUGASSERT(validateChildRelations(d, true)); |
514 GR_DEBUGASSERT(validateChildRelations(s, true)); | 514 GR_DEBUGASSERT(validateChildRelations(s, true)); |
515 GR_DEBUGASSERT(validateChildRelations(n, false)); | 515 GR_DEBUGASSERT(validateChildRelations(n, false)); |
516 GR_DEBUGASSERT(validateChildRelations(n->fChildren[kRight_Child], true)); | 516 GR_DEBUGASSERT(validateChildRelations(n->fChildren[kRight_Child], true)); |
517 GR_DEBUGASSERT(validateChildRelations(b, true)); | 517 GR_DEBUGASSERT(validateChildRelations(b, true)); |
518 GR_DEBUGASSERT(validateChildRelations(s->fChildren[kLeft_Child], true)); | 518 GR_DEBUGASSERT(validateChildRelations(s->fChildren[kLeft_Child], true)); |
519 } | 519 } |
520 | 520 |
521 template <typename T, typename C> | 521 template <typename T, typename C> |
522 void GrRedBlackTree<T,C>::rotateLeft(Node* n) { | 522 void GrRedBlackTree<T,C>::rotateLeft(Node* n) { |
523 | 523 |
524 Node* d = n->fParent; | 524 Node* d = n->fParent; |
525 Node* s = n->fChildren[kRight_Child]; | 525 Node* s = n->fChildren[kRight_Child]; |
526 GrAssert(NULL != s); | 526 SkASSERT(NULL != s); |
527 Node* b = s->fChildren[kLeft_Child]; | 527 Node* b = s->fChildren[kLeft_Child]; |
528 | 528 |
529 if (NULL != d) { | 529 if (NULL != d) { |
530 Child c = d->fChildren[kRight_Child] == n ? kRight_Child : | 530 Child c = d->fChildren[kRight_Child] == n ? kRight_Child : |
531 kLeft_Child; | 531 kLeft_Child; |
532 d->fChildren[c] = s; | 532 d->fChildren[c] = s; |
533 } else { | 533 } else { |
534 GrAssert(fRoot == n); | 534 SkASSERT(fRoot == n); |
535 fRoot = s; | 535 fRoot = s; |
536 } | 536 } |
537 s->fParent = d; | 537 s->fParent = d; |
538 s->fChildren[kLeft_Child] = n; | 538 s->fChildren[kLeft_Child] = n; |
539 n->fParent = s; | 539 n->fParent = s; |
540 n->fChildren[kRight_Child] = b; | 540 n->fChildren[kRight_Child] = b; |
541 if (NULL != b) { | 541 if (NULL != b) { |
542 b->fParent = n; | 542 b->fParent = n; |
543 } | 543 } |
544 | 544 |
545 GR_DEBUGASSERT(validateChildRelations(d, true)); | 545 GR_DEBUGASSERT(validateChildRelations(d, true)); |
546 GR_DEBUGASSERT(validateChildRelations(s, true)); | 546 GR_DEBUGASSERT(validateChildRelations(s, true)); |
547 GR_DEBUGASSERT(validateChildRelations(n, true)); | 547 GR_DEBUGASSERT(validateChildRelations(n, true)); |
548 GR_DEBUGASSERT(validateChildRelations(n->fChildren[kLeft_Child], true)); | 548 GR_DEBUGASSERT(validateChildRelations(n->fChildren[kLeft_Child], true)); |
549 GR_DEBUGASSERT(validateChildRelations(b, true)); | 549 GR_DEBUGASSERT(validateChildRelations(b, true)); |
550 GR_DEBUGASSERT(validateChildRelations(s->fChildren[kRight_Child], true)); | 550 GR_DEBUGASSERT(validateChildRelations(s->fChildren[kRight_Child], true)); |
551 } | 551 } |
552 | 552 |
553 template <typename T, typename C> | 553 template <typename T, typename C> |
554 typename GrRedBlackTree<T,C>::Node* GrRedBlackTree<T,C>::SuccessorNode(Node* x)
{ | 554 typename GrRedBlackTree<T,C>::Node* GrRedBlackTree<T,C>::SuccessorNode(Node* x)
{ |
555 GrAssert(NULL != x); | 555 SkASSERT(NULL != x); |
556 if (NULL != x->fChildren[kRight_Child]) { | 556 if (NULL != x->fChildren[kRight_Child]) { |
557 x = x->fChildren[kRight_Child]; | 557 x = x->fChildren[kRight_Child]; |
558 while (NULL != x->fChildren[kLeft_Child]) { | 558 while (NULL != x->fChildren[kLeft_Child]) { |
559 x = x->fChildren[kLeft_Child]; | 559 x = x->fChildren[kLeft_Child]; |
560 } | 560 } |
561 return x; | 561 return x; |
562 } | 562 } |
563 while (NULL != x->fParent && x == x->fParent->fChildren[kRight_Child]) { | 563 while (NULL != x->fParent && x == x->fParent->fChildren[kRight_Child]) { |
564 x = x->fParent; | 564 x = x->fParent; |
565 } | 565 } |
566 return x->fParent; | 566 return x->fParent; |
567 } | 567 } |
568 | 568 |
569 template <typename T, typename C> | 569 template <typename T, typename C> |
570 typename GrRedBlackTree<T,C>::Node* GrRedBlackTree<T,C>::PredecessorNode(Node* x
) { | 570 typename GrRedBlackTree<T,C>::Node* GrRedBlackTree<T,C>::PredecessorNode(Node* x
) { |
571 GrAssert(NULL != x); | 571 SkASSERT(NULL != x); |
572 if (NULL != x->fChildren[kLeft_Child]) { | 572 if (NULL != x->fChildren[kLeft_Child]) { |
573 x = x->fChildren[kLeft_Child]; | 573 x = x->fChildren[kLeft_Child]; |
574 while (NULL != x->fChildren[kRight_Child]) { | 574 while (NULL != x->fChildren[kRight_Child]) { |
575 x = x->fChildren[kRight_Child]; | 575 x = x->fChildren[kRight_Child]; |
576 } | 576 } |
577 return x; | 577 return x; |
578 } | 578 } |
579 while (NULL != x->fParent && x == x->fParent->fChildren[kLeft_Child]) { | 579 while (NULL != x->fParent && x == x->fParent->fChildren[kLeft_Child]) { |
580 x = x->fParent; | 580 x = x->fParent; |
581 } | 581 } |
582 return x->fParent; | 582 return x->fParent; |
583 } | 583 } |
584 | 584 |
585 template <typename T, typename C> | 585 template <typename T, typename C> |
586 void GrRedBlackTree<T,C>::deleteAtNode(Node* x) { | 586 void GrRedBlackTree<T,C>::deleteAtNode(Node* x) { |
587 GrAssert(NULL != x); | 587 SkASSERT(NULL != x); |
588 validate(); | 588 validate(); |
589 --fCount; | 589 --fCount; |
590 | 590 |
591 bool hasLeft = NULL != x->fChildren[kLeft_Child]; | 591 bool hasLeft = NULL != x->fChildren[kLeft_Child]; |
592 bool hasRight = NULL != x->fChildren[kRight_Child]; | 592 bool hasRight = NULL != x->fChildren[kRight_Child]; |
593 Child c = hasLeft ? kLeft_Child : kRight_Child; | 593 Child c = hasLeft ? kLeft_Child : kRight_Child; |
594 | 594 |
595 if (hasLeft && hasRight) { | 595 if (hasLeft && hasRight) { |
596 // first and last can't have two children. | 596 // first and last can't have two children. |
597 GrAssert(fFirst != x); | 597 SkASSERT(fFirst != x); |
598 GrAssert(fLast != x); | 598 SkASSERT(fLast != x); |
599 // if x is an interior node then we find it's successor | 599 // if x is an interior node then we find it's successor |
600 // and swap them. | 600 // and swap them. |
601 Node* s = x->fChildren[kRight_Child]; | 601 Node* s = x->fChildren[kRight_Child]; |
602 while (NULL != s->fChildren[kLeft_Child]) { | 602 while (NULL != s->fChildren[kLeft_Child]) { |
603 s = s->fChildren[kLeft_Child]; | 603 s = s->fChildren[kLeft_Child]; |
604 } | 604 } |
605 GrAssert(NULL != s); | 605 SkASSERT(NULL != s); |
606 // this might be expensive relative to swapping node ptrs around. | 606 // this might be expensive relative to swapping node ptrs around. |
607 // depends on T. | 607 // depends on T. |
608 x->fItem = s->fItem; | 608 x->fItem = s->fItem; |
609 x = s; | 609 x = s; |
610 c = kRight_Child; | 610 c = kRight_Child; |
611 } else if (NULL == x->fParent) { | 611 } else if (NULL == x->fParent) { |
612 // if x was the root we just replace it with its child and make | 612 // if x was the root we just replace it with its child and make |
613 // the new root (if the tree is not empty) black. | 613 // the new root (if the tree is not empty) black. |
614 GrAssert(fRoot == x); | 614 SkASSERT(fRoot == x); |
615 fRoot = x->fChildren[c]; | 615 fRoot = x->fChildren[c]; |
616 if (NULL != fRoot) { | 616 if (NULL != fRoot) { |
617 fRoot->fParent = NULL; | 617 fRoot->fParent = NULL; |
618 fRoot->fColor = kBlack_Color; | 618 fRoot->fColor = kBlack_Color; |
619 if (x == fLast) { | 619 if (x == fLast) { |
620 GrAssert(c == kLeft_Child); | 620 SkASSERT(c == kLeft_Child); |
621 fLast = fRoot; | 621 fLast = fRoot; |
622 } else if (x == fFirst) { | 622 } else if (x == fFirst) { |
623 GrAssert(c == kRight_Child); | 623 SkASSERT(c == kRight_Child); |
624 fFirst = fRoot; | 624 fFirst = fRoot; |
625 } | 625 } |
626 } else { | 626 } else { |
627 GrAssert(fFirst == fLast && x == fFirst); | 627 SkASSERT(fFirst == fLast && x == fFirst); |
628 fFirst = NULL; | 628 fFirst = NULL; |
629 fLast = NULL; | 629 fLast = NULL; |
630 GrAssert(0 == fCount); | 630 SkASSERT(0 == fCount); |
631 } | 631 } |
632 delete x; | 632 delete x; |
633 validate(); | 633 validate(); |
634 return; | 634 return; |
635 } | 635 } |
636 | 636 |
637 Child pc; | 637 Child pc; |
638 Node* p = x->fParent; | 638 Node* p = x->fParent; |
639 pc = p->fChildren[kLeft_Child] == x ? kLeft_Child : kRight_Child; | 639 pc = p->fChildren[kLeft_Child] == x ? kLeft_Child : kRight_Child; |
640 | 640 |
641 if (NULL == x->fChildren[c]) { | 641 if (NULL == x->fChildren[c]) { |
642 if (fLast == x) { | 642 if (fLast == x) { |
643 fLast = p; | 643 fLast = p; |
644 GrAssert(p == PredecessorNode(x)); | 644 SkASSERT(p == PredecessorNode(x)); |
645 } else if (fFirst == x) { | 645 } else if (fFirst == x) { |
646 fFirst = p; | 646 fFirst = p; |
647 GrAssert(p == SuccessorNode(x)); | 647 SkASSERT(p == SuccessorNode(x)); |
648 } | 648 } |
649 // x has two implicit black children. | 649 // x has two implicit black children. |
650 Color xcolor = x->fColor; | 650 Color xcolor = x->fColor; |
651 p->fChildren[pc] = NULL; | 651 p->fChildren[pc] = NULL; |
652 delete x; | 652 delete x; |
653 x = NULL; | 653 x = NULL; |
654 // when x is red it can be with an implicit black leaf without | 654 // when x is red it can be with an implicit black leaf without |
655 // violating any of the red-black tree properties. | 655 // violating any of the red-black tree properties. |
656 if (kRed_Color == xcolor) { | 656 if (kRed_Color == xcolor) { |
657 validate(); | 657 validate(); |
658 return; | 658 return; |
659 } | 659 } |
660 // s is p's other child (x's sibling) | 660 // s is p's other child (x's sibling) |
661 Node* s = p->fChildren[1-pc]; | 661 Node* s = p->fChildren[1-pc]; |
662 | 662 |
663 //s cannot be an implicit black node because the original | 663 //s cannot be an implicit black node because the original |
664 // black-height at x was >= 2 and s's black-height must equal the | 664 // black-height at x was >= 2 and s's black-height must equal the |
665 // initial black height of x. | 665 // initial black height of x. |
666 GrAssert(NULL != s); | 666 SkASSERT(NULL != s); |
667 GrAssert(p == s->fParent); | 667 SkASSERT(p == s->fParent); |
668 | 668 |
669 // assigned in loop | 669 // assigned in loop |
670 Node* sl; | 670 Node* sl; |
671 Node* sr; | 671 Node* sr; |
672 bool slRed; | 672 bool slRed; |
673 bool srRed; | 673 bool srRed; |
674 | 674 |
675 do { | 675 do { |
676 // When we start this loop x may already be deleted it is/was | 676 // When we start this loop x may already be deleted it is/was |
677 // p's child on its pc side. x's children are/were black. The | 677 // p's child on its pc side. x's children are/were black. The |
678 // first time through the loop they are implict children. | 678 // first time through the loop they are implict children. |
679 // On later passes we will be walking up the tree and they will | 679 // On later passes we will be walking up the tree and they will |
680 // be real nodes. | 680 // be real nodes. |
681 // The x side of p has a black-height that is one less than the | 681 // The x side of p has a black-height that is one less than the |
682 // s side. It must be rebalanced. | 682 // s side. It must be rebalanced. |
683 GrAssert(NULL != s); | 683 SkASSERT(NULL != s); |
684 GrAssert(p == s->fParent); | 684 SkASSERT(p == s->fParent); |
685 GrAssert(NULL == x || x->fParent == p); | 685 SkASSERT(NULL == x || x->fParent == p); |
686 | 686 |
687 //sl and sr are s's children, which may be implicit. | 687 //sl and sr are s's children, which may be implicit. |
688 sl = s->fChildren[kLeft_Child]; | 688 sl = s->fChildren[kLeft_Child]; |
689 sr = s->fChildren[kRight_Child]; | 689 sr = s->fChildren[kRight_Child]; |
690 | 690 |
691 // if the s is red we will rotate s and p, swap their colors so | 691 // if the s is red we will rotate s and p, swap their colors so |
692 // that x's new sibling is black | 692 // that x's new sibling is black |
693 if (kRed_Color == s->fColor) { | 693 if (kRed_Color == s->fColor) { |
694 // if s is red then it's parent must be black. | 694 // if s is red then it's parent must be black. |
695 GrAssert(kBlack_Color == p->fColor); | 695 SkASSERT(kBlack_Color == p->fColor); |
696 // s's children must also be black since s is red. They can't | 696 // s's children must also be black since s is red. They can't |
697 // be implicit since s is red and it's black-height is >= 2. | 697 // be implicit since s is red and it's black-height is >= 2. |
698 GrAssert(NULL != sl && kBlack_Color == sl->fColor); | 698 SkASSERT(NULL != sl && kBlack_Color == sl->fColor); |
699 GrAssert(NULL != sr && kBlack_Color == sr->fColor); | 699 SkASSERT(NULL != sr && kBlack_Color == sr->fColor); |
700 p->fColor = kRed_Color; | 700 p->fColor = kRed_Color; |
701 s->fColor = kBlack_Color; | 701 s->fColor = kBlack_Color; |
702 if (kLeft_Child == pc) { | 702 if (kLeft_Child == pc) { |
703 rotateLeft(p); | 703 rotateLeft(p); |
704 s = sl; | 704 s = sl; |
705 } else { | 705 } else { |
706 rotateRight(p); | 706 rotateRight(p); |
707 s = sr; | 707 s = sr; |
708 } | 708 } |
709 sl = s->fChildren[kLeft_Child]; | 709 sl = s->fChildren[kLeft_Child]; |
710 sr = s->fChildren[kRight_Child]; | 710 sr = s->fChildren[kRight_Child]; |
711 } | 711 } |
712 // x and s are now both black. | 712 // x and s are now both black. |
713 GrAssert(kBlack_Color == s->fColor); | 713 SkASSERT(kBlack_Color == s->fColor); |
714 GrAssert(NULL == x || kBlack_Color == x->fColor); | 714 SkASSERT(NULL == x || kBlack_Color == x->fColor); |
715 GrAssert(p == s->fParent); | 715 SkASSERT(p == s->fParent); |
716 GrAssert(NULL == x || p == x->fParent); | 716 SkASSERT(NULL == x || p == x->fParent); |
717 | 717 |
718 // when x is deleted its subtree will have reduced black-height. | 718 // when x is deleted its subtree will have reduced black-height. |
719 slRed = (NULL != sl && kRed_Color == sl->fColor); | 719 slRed = (NULL != sl && kRed_Color == sl->fColor); |
720 srRed = (NULL != sr && kRed_Color == sr->fColor); | 720 srRed = (NULL != sr && kRed_Color == sr->fColor); |
721 if (!slRed && !srRed) { | 721 if (!slRed && !srRed) { |
722 // if s can be made red that will balance out x's removal | 722 // if s can be made red that will balance out x's removal |
723 // to make both subtrees of p have the same black-height. | 723 // to make both subtrees of p have the same black-height. |
724 if (kBlack_Color == p->fColor) { | 724 if (kBlack_Color == p->fColor) { |
725 s->fColor = kRed_Color; | 725 s->fColor = kRed_Color; |
726 // now subtree at p has black-height of one less than | 726 // now subtree at p has black-height of one less than |
727 // p's parent's other child's subtree. We move x up to | 727 // p's parent's other child's subtree. We move x up to |
728 // p and go through the loop again. At the top of loop | 728 // p and go through the loop again. At the top of loop |
729 // we assumed x and x's children are black, which holds | 729 // we assumed x and x's children are black, which holds |
730 // by above ifs. | 730 // by above ifs. |
731 // if p is the root there is no other subtree to balance | 731 // if p is the root there is no other subtree to balance |
732 // against. | 732 // against. |
733 x = p; | 733 x = p; |
734 p = x->fParent; | 734 p = x->fParent; |
735 if (NULL == p) { | 735 if (NULL == p) { |
736 GrAssert(fRoot == x); | 736 SkASSERT(fRoot == x); |
737 validate(); | 737 validate(); |
738 return; | 738 return; |
739 } else { | 739 } else { |
740 pc = p->fChildren[kLeft_Child] == x ? kLeft_Child : | 740 pc = p->fChildren[kLeft_Child] == x ? kLeft_Child : |
741 kRight_Child; | 741 kRight_Child; |
742 | 742 |
743 } | 743 } |
744 s = p->fChildren[1-pc]; | 744 s = p->fChildren[1-pc]; |
745 GrAssert(NULL != s); | 745 SkASSERT(NULL != s); |
746 GrAssert(p == s->fParent); | 746 SkASSERT(p == s->fParent); |
747 continue; | 747 continue; |
748 } else if (kRed_Color == p->fColor) { | 748 } else if (kRed_Color == p->fColor) { |
749 // we can make p black and s red. This balance out p's | 749 // we can make p black and s red. This balance out p's |
750 // two subtrees and keep the same black-height as it was | 750 // two subtrees and keep the same black-height as it was |
751 // before the delete. | 751 // before the delete. |
752 s->fColor = kRed_Color; | 752 s->fColor = kRed_Color; |
753 p->fColor = kBlack_Color; | 753 p->fColor = kBlack_Color; |
754 validate(); | 754 validate(); |
755 return; | 755 return; |
756 } | 756 } |
757 } | 757 } |
758 break; | 758 break; |
759 } while (true); | 759 } while (true); |
760 // if we made it here one or both of sl and sr is red. | 760 // if we made it here one or both of sl and sr is red. |
761 // s and x are black. We make sure that a red child is on | 761 // s and x are black. We make sure that a red child is on |
762 // the same side of s as s is of p. | 762 // the same side of s as s is of p. |
763 GrAssert(slRed || srRed); | 763 SkASSERT(slRed || srRed); |
764 if (kLeft_Child == pc && !srRed) { | 764 if (kLeft_Child == pc && !srRed) { |
765 s->fColor = kRed_Color; | 765 s->fColor = kRed_Color; |
766 sl->fColor = kBlack_Color; | 766 sl->fColor = kBlack_Color; |
767 rotateRight(s); | 767 rotateRight(s); |
768 sr = s; | 768 sr = s; |
769 s = sl; | 769 s = sl; |
770 //sl = s->fChildren[kLeft_Child]; don't need this | 770 //sl = s->fChildren[kLeft_Child]; don't need this |
771 } else if (kRight_Child == pc && !slRed) { | 771 } else if (kRight_Child == pc && !slRed) { |
772 s->fColor = kRed_Color; | 772 s->fColor = kRed_Color; |
773 sr->fColor = kBlack_Color; | 773 sr->fColor = kBlack_Color; |
774 rotateLeft(s); | 774 rotateLeft(s); |
775 sl = s; | 775 sl = s; |
776 s = sr; | 776 s = sr; |
777 //sr = s->fChildren[kRight_Child]; don't need this | 777 //sr = s->fChildren[kRight_Child]; don't need this |
778 } | 778 } |
779 // now p is either red or black, x and s are red and s's 1-pc | 779 // now p is either red or black, x and s are red and s's 1-pc |
780 // child is red. | 780 // child is red. |
781 // We rotate p towards x, pulling s up to replace p. We make | 781 // We rotate p towards x, pulling s up to replace p. We make |
782 // p be black and s takes p's old color. | 782 // p be black and s takes p's old color. |
783 // Whether p was red or black, we've increased its pc subtree | 783 // Whether p was red or black, we've increased its pc subtree |
784 // rooted at x by 1 (balancing the imbalance at the start) and | 784 // rooted at x by 1 (balancing the imbalance at the start) and |
785 // we've also its subtree rooted at s's black-height by 1. This | 785 // we've also its subtree rooted at s's black-height by 1. This |
786 // can be balanced by making s's red child be black. | 786 // can be balanced by making s's red child be black. |
787 s->fColor = p->fColor; | 787 s->fColor = p->fColor; |
788 p->fColor = kBlack_Color; | 788 p->fColor = kBlack_Color; |
789 if (kLeft_Child == pc) { | 789 if (kLeft_Child == pc) { |
790 GrAssert(NULL != sr && kRed_Color == sr->fColor); | 790 SkASSERT(NULL != sr && kRed_Color == sr->fColor); |
791 sr->fColor = kBlack_Color; | 791 sr->fColor = kBlack_Color; |
792 rotateLeft(p); | 792 rotateLeft(p); |
793 } else { | 793 } else { |
794 GrAssert(NULL != sl && kRed_Color == sl->fColor); | 794 SkASSERT(NULL != sl && kRed_Color == sl->fColor); |
795 sl->fColor = kBlack_Color; | 795 sl->fColor = kBlack_Color; |
796 rotateRight(p); | 796 rotateRight(p); |
797 } | 797 } |
798 } | 798 } |
799 else { | 799 else { |
800 // x has exactly one implicit black child. x cannot be red. | 800 // x has exactly one implicit black child. x cannot be red. |
801 // Proof by contradiction: Assume X is red. Let c0 be x's implicit | 801 // Proof by contradiction: Assume X is red. Let c0 be x's implicit |
802 // child and c1 be its non-implicit child. c1 must be black because | 802 // child and c1 be its non-implicit child. c1 must be black because |
803 // red nodes always have two black children. Then the two subtrees | 803 // red nodes always have two black children. Then the two subtrees |
804 // of x rooted at c0 and c1 will have different black-heights. | 804 // of x rooted at c0 and c1 will have different black-heights. |
805 GrAssert(kBlack_Color == x->fColor); | 805 SkASSERT(kBlack_Color == x->fColor); |
806 // So we know x is black and has one implicit black child, c0. c1 | 806 // So we know x is black and has one implicit black child, c0. c1 |
807 // must be red, otherwise the subtree at c1 will have a different | 807 // must be red, otherwise the subtree at c1 will have a different |
808 // black-height than the subtree rooted at c0. | 808 // black-height than the subtree rooted at c0. |
809 GrAssert(kRed_Color == x->fChildren[c]->fColor); | 809 SkASSERT(kRed_Color == x->fChildren[c]->fColor); |
810 // replace x with c1, making c1 black, preserves all red-black tree | 810 // replace x with c1, making c1 black, preserves all red-black tree |
811 // props. | 811 // props. |
812 Node* c1 = x->fChildren[c]; | 812 Node* c1 = x->fChildren[c]; |
813 if (x == fFirst) { | 813 if (x == fFirst) { |
814 GrAssert(c == kRight_Child); | 814 SkASSERT(c == kRight_Child); |
815 fFirst = c1; | 815 fFirst = c1; |
816 while (NULL != fFirst->fChildren[kLeft_Child]) { | 816 while (NULL != fFirst->fChildren[kLeft_Child]) { |
817 fFirst = fFirst->fChildren[kLeft_Child]; | 817 fFirst = fFirst->fChildren[kLeft_Child]; |
818 } | 818 } |
819 GrAssert(fFirst == SuccessorNode(x)); | 819 SkASSERT(fFirst == SuccessorNode(x)); |
820 } else if (x == fLast) { | 820 } else if (x == fLast) { |
821 GrAssert(c == kLeft_Child); | 821 SkASSERT(c == kLeft_Child); |
822 fLast = c1; | 822 fLast = c1; |
823 while (NULL != fLast->fChildren[kRight_Child]) { | 823 while (NULL != fLast->fChildren[kRight_Child]) { |
824 fLast = fLast->fChildren[kRight_Child]; | 824 fLast = fLast->fChildren[kRight_Child]; |
825 } | 825 } |
826 GrAssert(fLast == PredecessorNode(x)); | 826 SkASSERT(fLast == PredecessorNode(x)); |
827 } | 827 } |
828 c1->fParent = p; | 828 c1->fParent = p; |
829 p->fChildren[pc] = c1; | 829 p->fChildren[pc] = c1; |
830 c1->fColor = kBlack_Color; | 830 c1->fColor = kBlack_Color; |
831 delete x; | 831 delete x; |
832 validate(); | 832 validate(); |
833 } | 833 } |
834 validate(); | 834 validate(); |
835 } | 835 } |
836 | 836 |
837 template <typename T, typename C> | 837 template <typename T, typename C> |
838 void GrRedBlackTree<T,C>::RecursiveDelete(Node* x) { | 838 void GrRedBlackTree<T,C>::RecursiveDelete(Node* x) { |
839 if (NULL != x) { | 839 if (NULL != x) { |
840 RecursiveDelete(x->fChildren[kLeft_Child]); | 840 RecursiveDelete(x->fChildren[kLeft_Child]); |
841 RecursiveDelete(x->fChildren[kRight_Child]); | 841 RecursiveDelete(x->fChildren[kRight_Child]); |
842 delete x; | 842 delete x; |
843 } | 843 } |
844 } | 844 } |
845 | 845 |
846 #if GR_DEBUG | 846 #if GR_DEBUG |
847 template <typename T, typename C> | 847 template <typename T, typename C> |
848 void GrRedBlackTree<T,C>::validate() const { | 848 void GrRedBlackTree<T,C>::validate() const { |
849 if (fCount) { | 849 if (fCount) { |
850 GrAssert(NULL == fRoot->fParent); | 850 SkASSERT(NULL == fRoot->fParent); |
851 GrAssert(NULL != fFirst); | 851 SkASSERT(NULL != fFirst); |
852 GrAssert(NULL != fLast); | 852 SkASSERT(NULL != fLast); |
853 | 853 |
854 GrAssert(kBlack_Color == fRoot->fColor); | 854 SkASSERT(kBlack_Color == fRoot->fColor); |
855 if (1 == fCount) { | 855 if (1 == fCount) { |
856 GrAssert(fFirst == fRoot); | 856 SkASSERT(fFirst == fRoot); |
857 GrAssert(fLast == fRoot); | 857 SkASSERT(fLast == fRoot); |
858 GrAssert(0 == fRoot->fChildren[kLeft_Child]); | 858 SkASSERT(0 == fRoot->fChildren[kLeft_Child]); |
859 GrAssert(0 == fRoot->fChildren[kRight_Child]); | 859 SkASSERT(0 == fRoot->fChildren[kRight_Child]); |
860 } | 860 } |
861 } else { | 861 } else { |
862 GrAssert(NULL == fRoot); | 862 SkASSERT(NULL == fRoot); |
863 GrAssert(NULL == fFirst); | 863 SkASSERT(NULL == fFirst); |
864 GrAssert(NULL == fLast); | 864 SkASSERT(NULL == fLast); |
865 } | 865 } |
866 #if DEEP_VALIDATE | 866 #if DEEP_VALIDATE |
867 int bh; | 867 int bh; |
868 int count = checkNode(fRoot, &bh); | 868 int count = checkNode(fRoot, &bh); |
869 GrAssert(count == fCount); | 869 SkASSERT(count == fCount); |
870 #endif | 870 #endif |
871 } | 871 } |
872 | 872 |
873 template <typename T, typename C> | 873 template <typename T, typename C> |
874 int GrRedBlackTree<T,C>::checkNode(Node* n, int* bh) const { | 874 int GrRedBlackTree<T,C>::checkNode(Node* n, int* bh) const { |
875 if (NULL != n) { | 875 if (NULL != n) { |
876 GrAssert(validateChildRelations(n, false)); | 876 SkASSERT(validateChildRelations(n, false)); |
877 if (kBlack_Color == n->fColor) { | 877 if (kBlack_Color == n->fColor) { |
878 *bh += 1; | 878 *bh += 1; |
879 } | 879 } |
880 GrAssert(!fComp(n->fItem, fFirst->fItem)); | 880 SkASSERT(!fComp(n->fItem, fFirst->fItem)); |
881 GrAssert(!fComp(fLast->fItem, n->fItem)); | 881 SkASSERT(!fComp(fLast->fItem, n->fItem)); |
882 int leftBh = *bh; | 882 int leftBh = *bh; |
883 int rightBh = *bh; | 883 int rightBh = *bh; |
884 int cl = checkNode(n->fChildren[kLeft_Child], &leftBh); | 884 int cl = checkNode(n->fChildren[kLeft_Child], &leftBh); |
885 int cr = checkNode(n->fChildren[kRight_Child], &rightBh); | 885 int cr = checkNode(n->fChildren[kRight_Child], &rightBh); |
886 GrAssert(leftBh == rightBh); | 886 SkASSERT(leftBh == rightBh); |
887 *bh = leftBh; | 887 *bh = leftBh; |
888 return 1 + cl + cr; | 888 return 1 + cl + cr; |
889 } | 889 } |
890 return 0; | 890 return 0; |
891 } | 891 } |
892 | 892 |
893 template <typename T, typename C> | 893 template <typename T, typename C> |
894 bool GrRedBlackTree<T,C>::validateChildRelations(const Node* n, | 894 bool GrRedBlackTree<T,C>::validateChildRelations(const Node* n, |
895 bool allowRedRed) const { | 895 bool allowRedRed) const { |
896 if (NULL != n) { | 896 if (NULL != n) { |
(...skipping 53 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
950 GrRedBlackTree<int> tree; | 950 GrRedBlackTree<int> tree; |
951 typedef GrRedBlackTree<int>::Iter iter; | 951 typedef GrRedBlackTree<int>::Iter iter; |
952 | 952 |
953 SkMWCRandom r; | 953 SkMWCRandom r; |
954 | 954 |
955 int count[100] = {0}; | 955 int count[100] = {0}; |
956 // add 10K ints | 956 // add 10K ints |
957 for (int i = 0; i < 10000; ++i) { | 957 for (int i = 0; i < 10000; ++i) { |
958 int x = r.nextU()%100; | 958 int x = r.nextU()%100; |
959 SkDEBUGCODE(Iter xi = ) tree.insert(x); | 959 SkDEBUGCODE(Iter xi = ) tree.insert(x); |
960 GrAssert(*xi == x); | 960 SkASSERT(*xi == x); |
961 ++count[x]; | 961 ++count[x]; |
962 } | 962 } |
963 | 963 |
964 tree.insert(0); | 964 tree.insert(0); |
965 ++count[0]; | 965 ++count[0]; |
966 tree.insert(99); | 966 tree.insert(99); |
967 ++count[99]; | 967 ++count[99]; |
968 GrAssert(*tree.begin() == 0); | 968 SkASSERT(*tree.begin() == 0); |
969 GrAssert(*tree.last() == 99); | 969 SkASSERT(*tree.last() == 99); |
970 GrAssert(--(++tree.begin()) == tree.begin()); | 970 SkASSERT(--(++tree.begin()) == tree.begin()); |
971 GrAssert(--tree.end() == tree.last()); | 971 SkASSERT(--tree.end() == tree.last()); |
972 GrAssert(tree.count() == 10002); | 972 SkASSERT(tree.count() == 10002); |
973 | 973 |
974 int c = 0; | 974 int c = 0; |
975 // check that we iterate through the correct number of | 975 // check that we iterate through the correct number of |
976 // elements and they are properly sorted. | 976 // elements and they are properly sorted. |
977 for (Iter a = tree.begin(); tree.end() != a; ++a) { | 977 for (Iter a = tree.begin(); tree.end() != a; ++a) { |
978 Iter b = a; | 978 Iter b = a; |
979 ++b; | 979 ++b; |
980 ++c; | 980 ++c; |
981 GrAssert(b == tree.end() || *a <= *b); | 981 SkASSERT(b == tree.end() || *a <= *b); |
982 } | 982 } |
983 GrAssert(c == tree.count()); | 983 SkASSERT(c == tree.count()); |
984 | 984 |
985 // check that the tree reports the correct number of each int | 985 // check that the tree reports the correct number of each int |
986 // and that we can iterate through them correctly both forward | 986 // and that we can iterate through them correctly both forward |
987 // and backward. | 987 // and backward. |
988 for (int i = 0; i < 100; ++i) { | 988 for (int i = 0; i < 100; ++i) { |
989 int c; | 989 int c; |
990 c = tree.countOf(i); | 990 c = tree.countOf(i); |
991 GrAssert(c == count[i]); | 991 SkASSERT(c == count[i]); |
992 c = 0; | 992 c = 0; |
993 Iter iter = tree.findFirst(i); | 993 Iter iter = tree.findFirst(i); |
994 while (iter != tree.end() && *iter == i) { | 994 while (iter != tree.end() && *iter == i) { |
995 ++c; | 995 ++c; |
996 ++iter; | 996 ++iter; |
997 } | 997 } |
998 GrAssert(count[i] == c); | 998 SkASSERT(count[i] == c); |
999 c = 0; | 999 c = 0; |
1000 iter = tree.findLast(i); | 1000 iter = tree.findLast(i); |
1001 if (iter != tree.end()) { | 1001 if (iter != tree.end()) { |
1002 do { | 1002 do { |
1003 if (*iter == i) { | 1003 if (*iter == i) { |
1004 ++c; | 1004 ++c; |
1005 } else { | 1005 } else { |
1006 break; | 1006 break; |
1007 } | 1007 } |
1008 if (iter != tree.begin()) { | 1008 if (iter != tree.begin()) { |
1009 --iter; | 1009 --iter; |
1010 } else { | 1010 } else { |
1011 break; | 1011 break; |
1012 } | 1012 } |
1013 } while (true); | 1013 } while (true); |
1014 } | 1014 } |
1015 GrAssert(c == count[i]); | 1015 SkASSERT(c == count[i]); |
1016 } | 1016 } |
1017 // remove all the ints between 25 and 74. Randomly chose to remove | 1017 // remove all the ints between 25 and 74. Randomly chose to remove |
1018 // the first, last, or any entry for each. | 1018 // the first, last, or any entry for each. |
1019 for (int i = 25; i < 75; ++i) { | 1019 for (int i = 25; i < 75; ++i) { |
1020 while (0 != tree.countOf(i)) { | 1020 while (0 != tree.countOf(i)) { |
1021 --count[i]; | 1021 --count[i]; |
1022 int x = r.nextU() % 3; | 1022 int x = r.nextU() % 3; |
1023 Iter iter; | 1023 Iter iter; |
1024 switch (x) { | 1024 switch (x) { |
1025 case 0: | 1025 case 0: |
1026 iter = tree.findFirst(i); | 1026 iter = tree.findFirst(i); |
1027 break; | 1027 break; |
1028 case 1: | 1028 case 1: |
1029 iter = tree.findLast(i); | 1029 iter = tree.findLast(i); |
1030 break; | 1030 break; |
1031 case 2: | 1031 case 2: |
1032 default: | 1032 default: |
1033 iter = tree.find(i); | 1033 iter = tree.find(i); |
1034 break; | 1034 break; |
1035 } | 1035 } |
1036 tree.remove(iter); | 1036 tree.remove(iter); |
1037 } | 1037 } |
1038 GrAssert(0 == count[i]); | 1038 SkASSERT(0 == count[i]); |
1039 GrAssert(tree.findFirst(i) == tree.end()); | 1039 SkASSERT(tree.findFirst(i) == tree.end()); |
1040 GrAssert(tree.findLast(i) == tree.end()); | 1040 SkASSERT(tree.findLast(i) == tree.end()); |
1041 GrAssert(tree.find(i) == tree.end()); | 1041 SkASSERT(tree.find(i) == tree.end()); |
1042 } | 1042 } |
1043 // remove all of the 0 entries. (tests removing begin()) | 1043 // remove all of the 0 entries. (tests removing begin()) |
1044 GrAssert(*tree.begin() == 0); | 1044 SkASSERT(*tree.begin() == 0); |
1045 GrAssert(*(--tree.end()) == 99); | 1045 SkASSERT(*(--tree.end()) == 99); |
1046 while (0 != tree.countOf(0)) { | 1046 while (0 != tree.countOf(0)) { |
1047 --count[0]; | 1047 --count[0]; |
1048 tree.remove(tree.find(0)); | 1048 tree.remove(tree.find(0)); |
1049 } | 1049 } |
1050 GrAssert(0 == count[0]); | 1050 SkASSERT(0 == count[0]); |
1051 GrAssert(tree.findFirst(0) == tree.end()); | 1051 SkASSERT(tree.findFirst(0) == tree.end()); |
1052 GrAssert(tree.findLast(0) == tree.end()); | 1052 SkASSERT(tree.findLast(0) == tree.end()); |
1053 GrAssert(tree.find(0) == tree.end()); | 1053 SkASSERT(tree.find(0) == tree.end()); |
1054 GrAssert(0 < *tree.begin()); | 1054 SkASSERT(0 < *tree.begin()); |
1055 | 1055 |
1056 // remove all the 99 entries (tests removing last()). | 1056 // remove all the 99 entries (tests removing last()). |
1057 while (0 != tree.countOf(99)) { | 1057 while (0 != tree.countOf(99)) { |
1058 --count[99]; | 1058 --count[99]; |
1059 tree.remove(tree.find(99)); | 1059 tree.remove(tree.find(99)); |
1060 } | 1060 } |
1061 GrAssert(0 == count[99]); | 1061 SkASSERT(0 == count[99]); |
1062 GrAssert(tree.findFirst(99) == tree.end()); | 1062 SkASSERT(tree.findFirst(99) == tree.end()); |
1063 GrAssert(tree.findLast(99) == tree.end()); | 1063 SkASSERT(tree.findLast(99) == tree.end()); |
1064 GrAssert(tree.find(99) == tree.end()); | 1064 SkASSERT(tree.find(99) == tree.end()); |
1065 GrAssert(99 > *(--tree.end())); | 1065 SkASSERT(99 > *(--tree.end())); |
1066 GrAssert(tree.last() == --tree.end()); | 1066 SkASSERT(tree.last() == --tree.end()); |
1067 | 1067 |
1068 // Make sure iteration still goes through correct number of entries | 1068 // Make sure iteration still goes through correct number of entries |
1069 // and is still sorted correctly. | 1069 // and is still sorted correctly. |
1070 c = 0; | 1070 c = 0; |
1071 for (Iter a = tree.begin(); tree.end() != a; ++a) { | 1071 for (Iter a = tree.begin(); tree.end() != a; ++a) { |
1072 Iter b = a; | 1072 Iter b = a; |
1073 ++b; | 1073 ++b; |
1074 ++c; | 1074 ++c; |
1075 GrAssert(b == tree.end() || *a <= *b); | 1075 SkASSERT(b == tree.end() || *a <= *b); |
1076 } | 1076 } |
1077 GrAssert(c == tree.count()); | 1077 SkASSERT(c == tree.count()); |
1078 | 1078 |
1079 // repeat check that correct number of each entry is in the tree | 1079 // repeat check that correct number of each entry is in the tree |
1080 // and iterates correctly both forward and backward. | 1080 // and iterates correctly both forward and backward. |
1081 for (int i = 0; i < 100; ++i) { | 1081 for (int i = 0; i < 100; ++i) { |
1082 GrAssert(tree.countOf(i) == count[i]); | 1082 SkASSERT(tree.countOf(i) == count[i]); |
1083 int c = 0; | 1083 int c = 0; |
1084 Iter iter = tree.findFirst(i); | 1084 Iter iter = tree.findFirst(i); |
1085 while (iter != tree.end() && *iter == i) { | 1085 while (iter != tree.end() && *iter == i) { |
1086 ++c; | 1086 ++c; |
1087 ++iter; | 1087 ++iter; |
1088 } | 1088 } |
1089 GrAssert(count[i] == c); | 1089 SkASSERT(count[i] == c); |
1090 c = 0; | 1090 c = 0; |
1091 iter = tree.findLast(i); | 1091 iter = tree.findLast(i); |
1092 if (iter != tree.end()) { | 1092 if (iter != tree.end()) { |
1093 do { | 1093 do { |
1094 if (*iter == i) { | 1094 if (*iter == i) { |
1095 ++c; | 1095 ++c; |
1096 } else { | 1096 } else { |
1097 break; | 1097 break; |
1098 } | 1098 } |
1099 if (iter != tree.begin()) { | 1099 if (iter != tree.begin()) { |
1100 --iter; | 1100 --iter; |
1101 } else { | 1101 } else { |
1102 break; | 1102 break; |
1103 } | 1103 } |
1104 } while (true); | 1104 } while (true); |
1105 } | 1105 } |
1106 GrAssert(count[i] == c); | 1106 SkASSERT(count[i] == c); |
1107 } | 1107 } |
1108 | 1108 |
1109 // remove all entries | 1109 // remove all entries |
1110 while (!tree.empty()) { | 1110 while (!tree.empty()) { |
1111 tree.remove(tree.begin()); | 1111 tree.remove(tree.begin()); |
1112 } | 1112 } |
1113 | 1113 |
1114 // test reset on empty tree. | 1114 // test reset on empty tree. |
1115 tree.reset(); | 1115 tree.reset(); |
1116 } | 1116 } |
1117 | 1117 |
1118 #endif | 1118 #endif |
OLD | NEW |