michael@0: /*
michael@0:  * Copyright 2011 Google Inc.
michael@0:  *
michael@0:  * Use of this source code is governed by a BSD-style license that can be
michael@0:  * found in the LICENSE file.
michael@0:  */
michael@0: 
michael@0: #ifndef GrRedBlackTree_DEFINED
michael@0: #define GrRedBlackTree_DEFINED
michael@0: 
michael@0: #include "GrConfig.h"
michael@0: #include "SkTypes.h"
michael@0: 
michael@0: template <typename T>
michael@0: class GrLess {
michael@0: public:
michael@0:     bool operator()(const T& a, const T& b) const { return a < b; }
michael@0: };
michael@0: 
michael@0: template <typename T>
michael@0: class GrLess<T*> {
michael@0: public:
michael@0:     bool operator()(const T* a, const T* b) const { return *a < *b; }
michael@0: };
michael@0: 
michael@0: class GrStrLess {
michael@0: public:
michael@0:     bool operator()(const char* a, const char* b) const { return strcmp(a,b) < 0; }
michael@0: };
michael@0: 
michael@0: /**
michael@0:  * In debug build this will cause full traversals of the tree when the validate
michael@0:  * is called on insert and remove. Useful for debugging but very slow.
michael@0:  */
michael@0: #define DEEP_VALIDATE 0
michael@0: 
michael@0: /**
michael@0:  * A sorted tree that uses the red-black tree algorithm. Allows duplicate
michael@0:  * entries. Data is of type T and is compared using functor C. A single C object
michael@0:  * will be created and used for all comparisons.
michael@0:  */
michael@0: template <typename T, typename C = GrLess<T> >
michael@0: class GrRedBlackTree : public SkNoncopyable {
michael@0: public:
michael@0:     /**
michael@0:      * Creates an empty tree.
michael@0:      */
michael@0:     GrRedBlackTree();
michael@0:     virtual ~GrRedBlackTree();
michael@0: 
michael@0:     /**
michael@0:      * Class used to iterater through the tree. The valid range of the tree
michael@0:      * is given by [begin(), end()). It is legal to dereference begin() but not
michael@0:      * end(). The iterator has preincrement and predecrement operators, it is
michael@0:      * legal to decerement end() if the tree is not empty to get the last
michael@0:      * element. However, a last() helper is provided.
michael@0:      */
michael@0:     class Iter;
michael@0: 
michael@0:     /**
michael@0:      * Add an element to the tree. Duplicates are allowed.
michael@0:      * @param t     the item to add.
michael@0:      * @return  an iterator to the item.
michael@0:      */
michael@0:     Iter insert(const T& t);
michael@0: 
michael@0:     /**
michael@0:      * Removes all items in the tree.
michael@0:      */
michael@0:     void reset();
michael@0: 
michael@0:     /**
michael@0:      * @return true if there are no items in the tree, false otherwise.
michael@0:      */
michael@0:     bool empty() const {return 0 == fCount;}
michael@0: 
michael@0:     /**
michael@0:      * @return the number of items in the tree.
michael@0:      */
michael@0:     int  count() const {return fCount;}
michael@0: 
michael@0:     /**
michael@0:      * @return  an iterator to the first item in sorted order, or end() if empty
michael@0:      */
michael@0:     Iter begin();
michael@0:     /**
michael@0:      * Gets the last valid iterator. This is always valid, even on an empty.
michael@0:      * However, it can never be dereferenced. Useful as a loop terminator.
michael@0:      * @return  an iterator that is just beyond the last item in sorted order.
michael@0:      */
michael@0:     Iter end();
michael@0:     /**
michael@0:      * @return  an iterator that to the last item in sorted order, or end() if
michael@0:      * empty.
michael@0:      */
michael@0:     Iter last();
michael@0: 
michael@0:     /**
michael@0:      * Finds an occurrence of an item.
michael@0:      * @param t     the item to find.
michael@0:      * @return an iterator to a tree element equal to t or end() if none exists.
michael@0:      */
michael@0:     Iter find(const T& t);
michael@0:     /**
michael@0:      * Finds the first of an item in iterator order.
michael@0:      * @param t     the item to find.
michael@0:      * @return  an iterator to the first element equal to t or end() if
michael@0:      *          none exists.
michael@0:      */
michael@0:     Iter findFirst(const T& t);
michael@0:     /**
michael@0:      * Finds the last of an item in iterator order.
michael@0:      * @param t     the item to find.
michael@0:      * @return  an iterator to the last element equal to t or end() if
michael@0:      *          none exists.
michael@0:      */
michael@0:     Iter findLast(const T& t);
michael@0:     /**
michael@0:      * Gets the number of items in the tree equal to t.
michael@0:      * @param t     the item to count.
michael@0:      * @return  number of items equal to t in the tree
michael@0:      */
michael@0:     int countOf(const T& t) const;
michael@0: 
michael@0:     /**
michael@0:      * Removes the item indicated by an iterator. The iterator will not be valid
michael@0:      * afterwards.
michael@0:      *
michael@0:      * @param iter      iterator of item to remove. Must be valid (not end()).
michael@0:      */
michael@0:     void remove(const Iter& iter) { deleteAtNode(iter.fN); }
michael@0: 
michael@0: private:
michael@0:     enum Color {
michael@0:         kRed_Color,
michael@0:         kBlack_Color
michael@0:     };
michael@0: 
michael@0:     enum Child {
michael@0:         kLeft_Child  = 0,
michael@0:         kRight_Child = 1
michael@0:     };
michael@0: 
michael@0:     struct Node {
michael@0:         T       fItem;
michael@0:         Color   fColor;
michael@0: 
michael@0:         Node*   fParent;
michael@0:         Node*   fChildren[2];
michael@0:     };
michael@0: 
michael@0:     void rotateRight(Node* n);
michael@0:     void rotateLeft(Node* n);
michael@0: 
michael@0:     static Node* SuccessorNode(Node* x);
michael@0:     static Node* PredecessorNode(Node* x);
michael@0: 
michael@0:     void deleteAtNode(Node* x);
michael@0:     static void RecursiveDelete(Node* x);
michael@0: 
michael@0:     int onCountOf(const Node* n, const T& t) const;
michael@0: 
michael@0: #ifdef SK_DEBUG
michael@0:     void validate() const;
michael@0:     int checkNode(Node* n, int* blackHeight) const;
michael@0:     // checks relationship between a node and its children. allowRedRed means
michael@0:     // node may be in an intermediate state where a red parent has a red child.
michael@0:     bool validateChildRelations(const Node* n, bool allowRedRed) const;
michael@0:     // place to stick break point if validateChildRelations is failing.
michael@0:     bool validateChildRelationsFailed() const { return false; }
michael@0: #else
michael@0:     void validate() const {}
michael@0: #endif
michael@0: 
michael@0:     int     fCount;
michael@0:     Node*   fRoot;
michael@0:     Node*   fFirst;
michael@0:     Node*   fLast;
michael@0: 
michael@0:     const C fComp;
michael@0: };
michael@0: 
michael@0: template <typename T, typename C>
michael@0: class GrRedBlackTree<T,C>::Iter {
michael@0: public:
michael@0:     Iter() {};
michael@0:     Iter(const Iter& i) {fN = i.fN; fTree = i.fTree;}
michael@0:     Iter& operator =(const Iter& i) {
michael@0:         fN = i.fN;
michael@0:         fTree = i.fTree;
michael@0:         return *this;
michael@0:     }
michael@0:     // altering the sort value of the item using this method will cause
michael@0:     // errors.
michael@0:     T& operator *() const { return fN->fItem; }
michael@0:     bool operator ==(const Iter& i) const {
michael@0:         return fN == i.fN && fTree == i.fTree;
michael@0:     }
michael@0:     bool operator !=(const Iter& i) const { return !(*this == i); }
michael@0:     Iter& operator ++() {
michael@0:         SkASSERT(*this != fTree->end());
michael@0:         fN = SuccessorNode(fN);
michael@0:         return *this;
michael@0:     }
michael@0:     Iter& operator --() {
michael@0:         SkASSERT(*this != fTree->begin());
michael@0:         if (NULL != fN) {
michael@0:             fN = PredecessorNode(fN);
michael@0:         } else {
michael@0:             *this = fTree->last();
michael@0:         }
michael@0:         return *this;
michael@0:     }
michael@0: 
michael@0: private:
michael@0:     friend class GrRedBlackTree;
michael@0:     explicit Iter(Node* n, GrRedBlackTree* tree) {
michael@0:         fN = n;
michael@0:         fTree = tree;
michael@0:     }
michael@0:     Node* fN;
michael@0:     GrRedBlackTree* fTree;
michael@0: };
michael@0: 
michael@0: template <typename T, typename C>
michael@0: GrRedBlackTree<T,C>::GrRedBlackTree() : fComp() {
michael@0:     fRoot = NULL;
michael@0:     fFirst = NULL;
michael@0:     fLast = NULL;
michael@0:     fCount = 0;
michael@0:     validate();
michael@0: }
michael@0: 
michael@0: template <typename T, typename C>
michael@0: GrRedBlackTree<T,C>::~GrRedBlackTree() {
michael@0:     RecursiveDelete(fRoot);
michael@0: }
michael@0: 
michael@0: template <typename T, typename C>
michael@0: typename GrRedBlackTree<T,C>::Iter GrRedBlackTree<T,C>::begin() {
michael@0:     return Iter(fFirst, this);
michael@0: }
michael@0: 
michael@0: template <typename T, typename C>
michael@0: typename GrRedBlackTree<T,C>::Iter GrRedBlackTree<T,C>::end() {
michael@0:     return Iter(NULL, this);
michael@0: }
michael@0: 
michael@0: template <typename T, typename C>
michael@0: typename GrRedBlackTree<T,C>::Iter GrRedBlackTree<T,C>::last() {
michael@0:     return Iter(fLast, this);
michael@0: }
michael@0: 
michael@0: template <typename T, typename C>
michael@0: typename GrRedBlackTree<T,C>::Iter GrRedBlackTree<T,C>::find(const T& t) {
michael@0:     Node* n = fRoot;
michael@0:     while (NULL != n) {
michael@0:         if (fComp(t, n->fItem)) {
michael@0:             n = n->fChildren[kLeft_Child];
michael@0:         } else {
michael@0:             if (!fComp(n->fItem, t)) {
michael@0:                 return Iter(n, this);
michael@0:             }
michael@0:             n = n->fChildren[kRight_Child];
michael@0:         }
michael@0:     }
michael@0:     return end();
michael@0: }
michael@0: 
michael@0: template <typename T, typename C>
michael@0: typename GrRedBlackTree<T,C>::Iter GrRedBlackTree<T,C>::findFirst(const T& t) {
michael@0:     Node* n = fRoot;
michael@0:     Node* leftMost = NULL;
michael@0:     while (NULL != n) {
michael@0:         if (fComp(t, n->fItem)) {
michael@0:             n = n->fChildren[kLeft_Child];
michael@0:         } else {
michael@0:             if (!fComp(n->fItem, t)) {
michael@0:                 // found one. check if another in left subtree.
michael@0:                 leftMost = n;
michael@0:                 n = n->fChildren[kLeft_Child];
michael@0:             } else {
michael@0:                 n = n->fChildren[kRight_Child];
michael@0:             }
michael@0:         }
michael@0:     }
michael@0:     return Iter(leftMost, this);
michael@0: }
michael@0: 
michael@0: template <typename T, typename C>
michael@0: typename GrRedBlackTree<T,C>::Iter GrRedBlackTree<T,C>::findLast(const T& t) {
michael@0:     Node* n = fRoot;
michael@0:     Node* rightMost = NULL;
michael@0:     while (NULL != n) {
michael@0:         if (fComp(t, n->fItem)) {
michael@0:             n = n->fChildren[kLeft_Child];
michael@0:         } else {
michael@0:             if (!fComp(n->fItem, t)) {
michael@0:                 // found one. check if another in right subtree.
michael@0:                 rightMost = n;
michael@0:             }
michael@0:             n = n->fChildren[kRight_Child];
michael@0:         }
michael@0:     }
michael@0:     return Iter(rightMost, this);
michael@0: }
michael@0: 
michael@0: template <typename T, typename C>
michael@0: int GrRedBlackTree<T,C>::countOf(const T& t) const {
michael@0:     return onCountOf(fRoot, t);
michael@0: }
michael@0: 
michael@0: template <typename T, typename C>
michael@0: int GrRedBlackTree<T,C>::onCountOf(const Node* n, const T& t) const {
michael@0:     // this is count*log(n) :(
michael@0:     while (NULL != n) {
michael@0:         if (fComp(t, n->fItem)) {
michael@0:             n = n->fChildren[kLeft_Child];
michael@0:         } else {
michael@0:             if (!fComp(n->fItem, t)) {
michael@0:                 int count = 1;
michael@0:                 count += onCountOf(n->fChildren[kLeft_Child], t);
michael@0:                 count += onCountOf(n->fChildren[kRight_Child], t);
michael@0:                 return count;
michael@0:             }
michael@0:             n = n->fChildren[kRight_Child];
michael@0:         }
michael@0:     }
michael@0:     return 0;
michael@0: 
michael@0: }
michael@0: 
michael@0: template <typename T, typename C>
michael@0: void GrRedBlackTree<T,C>::reset() {
michael@0:     RecursiveDelete(fRoot);
michael@0:     fRoot = NULL;
michael@0:     fFirst = NULL;
michael@0:     fLast = NULL;
michael@0:     fCount = 0;
michael@0: }
michael@0: 
michael@0: template <typename T, typename C>
michael@0: typename GrRedBlackTree<T,C>::Iter GrRedBlackTree<T,C>::insert(const T& t) {
michael@0:     validate();
michael@0: 
michael@0:     ++fCount;
michael@0: 
michael@0:     Node* x = SkNEW(Node);
michael@0:     x->fChildren[kLeft_Child] = NULL;
michael@0:     x->fChildren[kRight_Child] = NULL;
michael@0:     x->fItem = t;
michael@0: 
michael@0:     Node* returnNode = x;
michael@0: 
michael@0:     Node* gp = NULL;
michael@0:     Node* p = NULL;
michael@0:     Node* n = fRoot;
michael@0:     Child pc = kLeft_Child; // suppress uninit warning
michael@0:     Child gpc = kLeft_Child;
michael@0: 
michael@0:     bool first = true;
michael@0:     bool last = true;
michael@0:     while (NULL != n) {
michael@0:         gpc = pc;
michael@0:         pc = fComp(x->fItem, n->fItem) ? kLeft_Child : kRight_Child;
michael@0:         first = first && kLeft_Child == pc;
michael@0:         last = last && kRight_Child == pc;
michael@0:         gp = p;
michael@0:         p = n;
michael@0:         n = p->fChildren[pc];
michael@0:     }
michael@0:     if (last) {
michael@0:         fLast = x;
michael@0:     }
michael@0:     if (first) {
michael@0:         fFirst = x;
michael@0:     }
michael@0: 
michael@0:     if (NULL == p) {
michael@0:         fRoot = x;
michael@0:         x->fColor = kBlack_Color;
michael@0:         x->fParent = NULL;
michael@0:         SkASSERT(1 == fCount);
michael@0:         return Iter(returnNode, this);
michael@0:     }
michael@0:     p->fChildren[pc] = x;
michael@0:     x->fColor = kRed_Color;
michael@0:     x->fParent = p;
michael@0: 
michael@0:     do {
michael@0:         // assumptions at loop start.
michael@0:         SkASSERT(NULL != x);
michael@0:         SkASSERT(kRed_Color == x->fColor);
michael@0:         // can't have a grandparent but no parent.
michael@0:         SkASSERT(!(NULL != gp && NULL == p));
michael@0:         // make sure pc and gpc are correct
michael@0:         SkASSERT(NULL == p  || p->fChildren[pc] == x);
michael@0:         SkASSERT(NULL == gp || gp->fChildren[gpc] == p);
michael@0: 
michael@0:         // if x's parent is black then we didn't violate any of the
michael@0:         // red/black properties when we added x as red.
michael@0:         if (kBlack_Color == p->fColor) {
michael@0:             return Iter(returnNode, this);
michael@0:         }
michael@0:         // gp must be valid because if p was the root then it is black
michael@0:         SkASSERT(NULL != gp);
michael@0:         // gp must be black since it's child, p, is red.
michael@0:         SkASSERT(kBlack_Color == gp->fColor);
michael@0: 
michael@0: 
michael@0:         // x and its parent are red, violating red-black property.
michael@0:         Node* u = gp->fChildren[1-gpc];
michael@0:         // if x's uncle (p's sibling) is also red then we can flip
michael@0:         // p and u to black and make gp red. But then we have to recurse
michael@0:         // up to gp since it's parent may also be red.
michael@0:         if (NULL != u && kRed_Color == u->fColor) {
michael@0:             p->fColor = kBlack_Color;
michael@0:             u->fColor = kBlack_Color;
michael@0:             gp->fColor = kRed_Color;
michael@0:             x = gp;
michael@0:             p = x->fParent;
michael@0:             if (NULL == p) {
michael@0:                 // x (prev gp) is the root, color it black and be done.
michael@0:                 SkASSERT(fRoot == x);
michael@0:                 x->fColor = kBlack_Color;
michael@0:                 validate();
michael@0:                 return Iter(returnNode, this);
michael@0:             }
michael@0:             gp = p->fParent;
michael@0:             pc = (p->fChildren[kLeft_Child] == x) ? kLeft_Child :
michael@0:                                                     kRight_Child;
michael@0:             if (NULL != gp) {
michael@0:                 gpc = (gp->fChildren[kLeft_Child] == p) ? kLeft_Child :
michael@0:                                                           kRight_Child;
michael@0:             }
michael@0:             continue;
michael@0:         } break;
michael@0:     } while (true);
michael@0:     // Here p is red but u is black and we still have to resolve the fact
michael@0:     // that x and p are both red.
michael@0:     SkASSERT(NULL == gp->fChildren[1-gpc] || kBlack_Color == gp->fChildren[1-gpc]->fColor);
michael@0:     SkASSERT(kRed_Color == x->fColor);
michael@0:     SkASSERT(kRed_Color == p->fColor);
michael@0:     SkASSERT(kBlack_Color == gp->fColor);
michael@0: 
michael@0:     // make x be on the same side of p as p is of gp. If it isn't already
michael@0:     // the case then rotate x up to p and swap their labels.
michael@0:     if (pc != gpc) {
michael@0:         if (kRight_Child == pc) {
michael@0:             rotateLeft(p);
michael@0:             Node* temp = p;
michael@0:             p = x;
michael@0:             x = temp;
michael@0:             pc = kLeft_Child;
michael@0:         } else {
michael@0:             rotateRight(p);
michael@0:             Node* temp = p;
michael@0:             p = x;
michael@0:             x = temp;
michael@0:             pc = kRight_Child;
michael@0:         }
michael@0:     }
michael@0:     // we now rotate gp down, pulling up p to be it's new parent.
michael@0:     // gp's child, u, that is not affected we know to be black. gp's new
michael@0:     // child is p's previous child (x's pre-rotation sibling) which must be
michael@0:     // black since p is red.
michael@0:     SkASSERT(NULL == p->fChildren[1-pc] ||
michael@0:              kBlack_Color == p->fChildren[1-pc]->fColor);
michael@0:     // Since gp's two children are black it can become red if p is made
michael@0:     // black. This leaves the black-height of both of p's new subtrees
michael@0:     // preserved and removes the red/red parent child relationship.
michael@0:     p->fColor = kBlack_Color;
michael@0:     gp->fColor = kRed_Color;
michael@0:     if (kLeft_Child == pc) {
michael@0:         rotateRight(gp);
michael@0:     } else {
michael@0:         rotateLeft(gp);
michael@0:     }
michael@0:     validate();
michael@0:     return Iter(returnNode, this);
michael@0: }
michael@0: 
michael@0: 
michael@0: template <typename T, typename C>
michael@0: void GrRedBlackTree<T,C>::rotateRight(Node* n) {
michael@0:     /*            d?              d?
michael@0:      *           /               /
michael@0:      *          n               s
michael@0:      *         / \     --->    / \
michael@0:      *        s   a?          c?  n
michael@0:      *       / \                 / \
michael@0:      *      c?  b?              b?  a?
michael@0:      */
michael@0:     Node* d = n->fParent;
michael@0:     Node* s = n->fChildren[kLeft_Child];
michael@0:     SkASSERT(NULL != s);
michael@0:     Node* b = s->fChildren[kRight_Child];
michael@0: 
michael@0:     if (NULL != d) {
michael@0:         Child c = d->fChildren[kLeft_Child] == n ? kLeft_Child :
michael@0:                                              kRight_Child;
michael@0:         d->fChildren[c] = s;
michael@0:     } else {
michael@0:         SkASSERT(fRoot == n);
michael@0:         fRoot = s;
michael@0:     }
michael@0:     s->fParent = d;
michael@0:     s->fChildren[kRight_Child] = n;
michael@0:     n->fParent = s;
michael@0:     n->fChildren[kLeft_Child] = b;
michael@0:     if (NULL != b) {
michael@0:         b->fParent = n;
michael@0:     }
michael@0: 
michael@0:     GR_DEBUGASSERT(validateChildRelations(d, true));
michael@0:     GR_DEBUGASSERT(validateChildRelations(s, true));
michael@0:     GR_DEBUGASSERT(validateChildRelations(n, false));
michael@0:     GR_DEBUGASSERT(validateChildRelations(n->fChildren[kRight_Child], true));
michael@0:     GR_DEBUGASSERT(validateChildRelations(b, true));
michael@0:     GR_DEBUGASSERT(validateChildRelations(s->fChildren[kLeft_Child], true));
michael@0: }
michael@0: 
michael@0: template <typename T, typename C>
michael@0: void GrRedBlackTree<T,C>::rotateLeft(Node* n) {
michael@0: 
michael@0:     Node* d = n->fParent;
michael@0:     Node* s = n->fChildren[kRight_Child];
michael@0:     SkASSERT(NULL != s);
michael@0:     Node* b = s->fChildren[kLeft_Child];
michael@0: 
michael@0:     if (NULL != d) {
michael@0:         Child c = d->fChildren[kRight_Child] == n ? kRight_Child :
michael@0:                                                    kLeft_Child;
michael@0:         d->fChildren[c] = s;
michael@0:     } else {
michael@0:         SkASSERT(fRoot == n);
michael@0:         fRoot = s;
michael@0:     }
michael@0:     s->fParent = d;
michael@0:     s->fChildren[kLeft_Child] = n;
michael@0:     n->fParent = s;
michael@0:     n->fChildren[kRight_Child] = b;
michael@0:     if (NULL != b) {
michael@0:         b->fParent = n;
michael@0:     }
michael@0: 
michael@0:     GR_DEBUGASSERT(validateChildRelations(d, true));
michael@0:     GR_DEBUGASSERT(validateChildRelations(s, true));
michael@0:     GR_DEBUGASSERT(validateChildRelations(n, true));
michael@0:     GR_DEBUGASSERT(validateChildRelations(n->fChildren[kLeft_Child], true));
michael@0:     GR_DEBUGASSERT(validateChildRelations(b, true));
michael@0:     GR_DEBUGASSERT(validateChildRelations(s->fChildren[kRight_Child], true));
michael@0: }
michael@0: 
michael@0: template <typename T, typename C>
michael@0: typename GrRedBlackTree<T,C>::Node* GrRedBlackTree<T,C>::SuccessorNode(Node* x) {
michael@0:     SkASSERT(NULL != x);
michael@0:     if (NULL != x->fChildren[kRight_Child]) {
michael@0:         x = x->fChildren[kRight_Child];
michael@0:         while (NULL != x->fChildren[kLeft_Child]) {
michael@0:             x = x->fChildren[kLeft_Child];
michael@0:         }
michael@0:         return x;
michael@0:     }
michael@0:     while (NULL != x->fParent && x == x->fParent->fChildren[kRight_Child]) {
michael@0:         x = x->fParent;
michael@0:     }
michael@0:     return x->fParent;
michael@0: }
michael@0: 
michael@0: template <typename T, typename C>
michael@0: typename GrRedBlackTree<T,C>::Node* GrRedBlackTree<T,C>::PredecessorNode(Node* x) {
michael@0:     SkASSERT(NULL != x);
michael@0:     if (NULL != x->fChildren[kLeft_Child]) {
michael@0:         x = x->fChildren[kLeft_Child];
michael@0:         while (NULL != x->fChildren[kRight_Child]) {
michael@0:             x = x->fChildren[kRight_Child];
michael@0:         }
michael@0:         return x;
michael@0:     }
michael@0:     while (NULL != x->fParent && x == x->fParent->fChildren[kLeft_Child]) {
michael@0:         x = x->fParent;
michael@0:     }
michael@0:     return x->fParent;
michael@0: }
michael@0: 
michael@0: template <typename T, typename C>
michael@0: void GrRedBlackTree<T,C>::deleteAtNode(Node* x) {
michael@0:     SkASSERT(NULL != x);
michael@0:     validate();
michael@0:     --fCount;
michael@0: 
michael@0:     bool hasLeft =  NULL != x->fChildren[kLeft_Child];
michael@0:     bool hasRight = NULL != x->fChildren[kRight_Child];
michael@0:     Child c = hasLeft ? kLeft_Child : kRight_Child;
michael@0: 
michael@0:     if (hasLeft && hasRight) {
michael@0:         // first and last can't have two children.
michael@0:         SkASSERT(fFirst != x);
michael@0:         SkASSERT(fLast != x);
michael@0:         // if x is an interior node then we find it's successor
michael@0:         // and swap them.
michael@0:         Node* s = x->fChildren[kRight_Child];
michael@0:         while (NULL != s->fChildren[kLeft_Child]) {
michael@0:             s = s->fChildren[kLeft_Child];
michael@0:         }
michael@0:         SkASSERT(NULL != s);
michael@0:         // this might be expensive relative to swapping node ptrs around.
michael@0:         // depends on T.
michael@0:         x->fItem = s->fItem;
michael@0:         x = s;
michael@0:         c = kRight_Child;
michael@0:     } else if (NULL == x->fParent) {
michael@0:         // if x was the root we just replace it with its child and make
michael@0:         // the new root (if the tree is not empty) black.
michael@0:         SkASSERT(fRoot == x);
michael@0:         fRoot = x->fChildren[c];
michael@0:         if (NULL != fRoot) {
michael@0:             fRoot->fParent = NULL;
michael@0:             fRoot->fColor = kBlack_Color;
michael@0:             if (x == fLast) {
michael@0:                 SkASSERT(c == kLeft_Child);
michael@0:                 fLast = fRoot;
michael@0:             } else if (x == fFirst) {
michael@0:                 SkASSERT(c == kRight_Child);
michael@0:                 fFirst = fRoot;
michael@0:             }
michael@0:         } else {
michael@0:             SkASSERT(fFirst == fLast && x == fFirst);
michael@0:             fFirst = NULL;
michael@0:             fLast = NULL;
michael@0:             SkASSERT(0 == fCount);
michael@0:         }
michael@0:         delete x;
michael@0:         validate();
michael@0:         return;
michael@0:     }
michael@0: 
michael@0:     Child pc;
michael@0:     Node* p = x->fParent;
michael@0:     pc = p->fChildren[kLeft_Child] == x ? kLeft_Child : kRight_Child;
michael@0: 
michael@0:     if (NULL == x->fChildren[c]) {
michael@0:         if (fLast == x) {
michael@0:             fLast = p;
michael@0:             SkASSERT(p == PredecessorNode(x));
michael@0:         } else if (fFirst == x) {
michael@0:             fFirst = p;
michael@0:             SkASSERT(p == SuccessorNode(x));
michael@0:         }
michael@0:         // x has two implicit black children.
michael@0:         Color xcolor = x->fColor;
michael@0:         p->fChildren[pc] = NULL;
michael@0:         delete x;
michael@0:         x = NULL;
michael@0:         // when x is red it can be with an implicit black leaf without
michael@0:         // violating any of the red-black tree properties.
michael@0:         if (kRed_Color == xcolor) {
michael@0:             validate();
michael@0:             return;
michael@0:         }
michael@0:         // s is p's other child (x's sibling)
michael@0:         Node* s = p->fChildren[1-pc];
michael@0: 
michael@0:         //s cannot be an implicit black node because the original
michael@0:         // black-height at x was >= 2 and s's black-height must equal the
michael@0:         // initial black height of x.
michael@0:         SkASSERT(NULL != s);
michael@0:         SkASSERT(p == s->fParent);
michael@0: 
michael@0:         // assigned in loop
michael@0:         Node* sl;
michael@0:         Node* sr;
michael@0:         bool slRed;
michael@0:         bool srRed;
michael@0: 
michael@0:         do {
michael@0:             // When we start this loop x may already be deleted it is/was
michael@0:             // p's child on its pc side. x's children are/were black. The
michael@0:             // first time through the loop they are implict children.
michael@0:             // On later passes we will be walking up the tree and they will
michael@0:             // be real nodes.
michael@0:             // The x side of p has a black-height that is one less than the
michael@0:             // s side. It must be rebalanced.
michael@0:             SkASSERT(NULL != s);
michael@0:             SkASSERT(p == s->fParent);
michael@0:             SkASSERT(NULL == x || x->fParent == p);
michael@0: 
michael@0:             //sl and sr are s's children, which may be implicit.
michael@0:             sl = s->fChildren[kLeft_Child];
michael@0:             sr = s->fChildren[kRight_Child];
michael@0: 
michael@0:             // if the s is red we will rotate s and p, swap their colors so
michael@0:             // that x's new sibling is black
michael@0:             if (kRed_Color == s->fColor) {
michael@0:                 // if s is red then it's parent must be black.
michael@0:                 SkASSERT(kBlack_Color == p->fColor);
michael@0:                 // s's children must also be black since s is red. They can't
michael@0:                 // be implicit since s is red and it's black-height is >= 2.
michael@0:                 SkASSERT(NULL != sl && kBlack_Color == sl->fColor);
michael@0:                 SkASSERT(NULL != sr && kBlack_Color == sr->fColor);
michael@0:                 p->fColor = kRed_Color;
michael@0:                 s->fColor = kBlack_Color;
michael@0:                 if (kLeft_Child == pc) {
michael@0:                     rotateLeft(p);
michael@0:                     s = sl;
michael@0:                 } else {
michael@0:                     rotateRight(p);
michael@0:                     s = sr;
michael@0:                 }
michael@0:                 sl = s->fChildren[kLeft_Child];
michael@0:                 sr = s->fChildren[kRight_Child];
michael@0:             }
michael@0:             // x and s are now both black.
michael@0:             SkASSERT(kBlack_Color == s->fColor);
michael@0:             SkASSERT(NULL == x || kBlack_Color == x->fColor);
michael@0:             SkASSERT(p == s->fParent);
michael@0:             SkASSERT(NULL == x || p == x->fParent);
michael@0: 
michael@0:             // when x is deleted its subtree will have reduced black-height.
michael@0:             slRed = (NULL != sl && kRed_Color == sl->fColor);
michael@0:             srRed = (NULL != sr && kRed_Color == sr->fColor);
michael@0:             if (!slRed && !srRed) {
michael@0:                 // if s can be made red that will balance out x's removal
michael@0:                 // to make both subtrees of p have the same black-height.
michael@0:                 if (kBlack_Color == p->fColor) {
michael@0:                     s->fColor = kRed_Color;
michael@0:                     // now subtree at p has black-height of one less than
michael@0:                     // p's parent's other child's subtree. We move x up to
michael@0:                     // p and go through the loop again. At the top of loop
michael@0:                     // we assumed x and x's children are black, which holds
michael@0:                     // by above ifs.
michael@0:                     // if p is the root there is no other subtree to balance
michael@0:                     // against.
michael@0:                     x = p;
michael@0:                     p = x->fParent;
michael@0:                     if (NULL == p) {
michael@0:                         SkASSERT(fRoot == x);
michael@0:                         validate();
michael@0:                         return;
michael@0:                     } else {
michael@0:                         pc = p->fChildren[kLeft_Child] == x ? kLeft_Child :
michael@0:                                                               kRight_Child;
michael@0: 
michael@0:                     }
michael@0:                     s = p->fChildren[1-pc];
michael@0:                     SkASSERT(NULL != s);
michael@0:                     SkASSERT(p == s->fParent);
michael@0:                     continue;
michael@0:                 } else if (kRed_Color == p->fColor) {
michael@0:                     // we can make p black and s red. This balance out p's
michael@0:                     // two subtrees and keep the same black-height as it was
michael@0:                     // before the delete.
michael@0:                     s->fColor = kRed_Color;
michael@0:                     p->fColor = kBlack_Color;
michael@0:                     validate();
michael@0:                     return;
michael@0:                 }
michael@0:             }
michael@0:             break;
michael@0:         } while (true);
michael@0:         // if we made it here one or both of sl and sr is red.
michael@0:         // s and x are black. We make sure that a red child is on
michael@0:         // the same side of s as s is of p.
michael@0:         SkASSERT(slRed || srRed);
michael@0:         if (kLeft_Child == pc && !srRed) {
michael@0:             s->fColor = kRed_Color;
michael@0:             sl->fColor = kBlack_Color;
michael@0:             rotateRight(s);
michael@0:             sr = s;
michael@0:             s = sl;
michael@0:             //sl = s->fChildren[kLeft_Child]; don't need this
michael@0:         } else if (kRight_Child == pc && !slRed) {
michael@0:             s->fColor = kRed_Color;
michael@0:             sr->fColor = kBlack_Color;
michael@0:             rotateLeft(s);
michael@0:             sl = s;
michael@0:             s = sr;
michael@0:             //sr = s->fChildren[kRight_Child]; don't need this
michael@0:         }
michael@0:         // now p is either red or black, x and s are red and s's 1-pc
michael@0:         // child is red.
michael@0:         // We rotate p towards x, pulling s up to replace p. We make
michael@0:         // p be black and s takes p's old color.
michael@0:         // Whether p was red or black, we've increased its pc subtree
michael@0:         // rooted at x by 1 (balancing the imbalance at the start) and
michael@0:         // we've also its subtree rooted at s's black-height by 1. This
michael@0:         // can be balanced by making s's red child be black.
michael@0:         s->fColor = p->fColor;
michael@0:         p->fColor = kBlack_Color;
michael@0:         if (kLeft_Child == pc) {
michael@0:             SkASSERT(NULL != sr && kRed_Color == sr->fColor);
michael@0:             sr->fColor = kBlack_Color;
michael@0:             rotateLeft(p);
michael@0:         } else {
michael@0:             SkASSERT(NULL != sl && kRed_Color == sl->fColor);
michael@0:             sl->fColor = kBlack_Color;
michael@0:             rotateRight(p);
michael@0:         }
michael@0:     }
michael@0:     else {
michael@0:         // x has exactly one implicit black child. x cannot be red.
michael@0:         // Proof by contradiction: Assume X is red. Let c0 be x's implicit
michael@0:         // child and c1 be its non-implicit child. c1 must be black because
michael@0:         // red nodes always have two black children. Then the two subtrees
michael@0:         // of x rooted at c0 and c1 will have different black-heights.
michael@0:         SkASSERT(kBlack_Color == x->fColor);
michael@0:         // So we know x is black and has one implicit black child, c0. c1
michael@0:         // must be red, otherwise the subtree at c1 will have a different
michael@0:         // black-height than the subtree rooted at c0.
michael@0:         SkASSERT(kRed_Color == x->fChildren[c]->fColor);
michael@0:         // replace x with c1, making c1 black, preserves all red-black tree
michael@0:         // props.
michael@0:         Node* c1 = x->fChildren[c];
michael@0:         if (x == fFirst) {
michael@0:             SkASSERT(c == kRight_Child);
michael@0:             fFirst = c1;
michael@0:             while (NULL != fFirst->fChildren[kLeft_Child]) {
michael@0:                 fFirst = fFirst->fChildren[kLeft_Child];
michael@0:             }
michael@0:             SkASSERT(fFirst == SuccessorNode(x));
michael@0:         } else if (x == fLast) {
michael@0:             SkASSERT(c == kLeft_Child);
michael@0:             fLast = c1;
michael@0:             while (NULL != fLast->fChildren[kRight_Child]) {
michael@0:                 fLast = fLast->fChildren[kRight_Child];
michael@0:             }
michael@0:             SkASSERT(fLast == PredecessorNode(x));
michael@0:         }
michael@0:         c1->fParent = p;
michael@0:         p->fChildren[pc] = c1;
michael@0:         c1->fColor = kBlack_Color;
michael@0:         delete x;
michael@0:         validate();
michael@0:     }
michael@0:     validate();
michael@0: }
michael@0: 
michael@0: template <typename T, typename C>
michael@0: void GrRedBlackTree<T,C>::RecursiveDelete(Node* x) {
michael@0:     if (NULL != x) {
michael@0:         RecursiveDelete(x->fChildren[kLeft_Child]);
michael@0:         RecursiveDelete(x->fChildren[kRight_Child]);
michael@0:         delete x;
michael@0:     }
michael@0: }
michael@0: 
michael@0: #ifdef SK_DEBUG
michael@0: template <typename T, typename C>
michael@0: void GrRedBlackTree<T,C>::validate() const {
michael@0:     if (fCount) {
michael@0:         SkASSERT(NULL == fRoot->fParent);
michael@0:         SkASSERT(NULL != fFirst);
michael@0:         SkASSERT(NULL != fLast);
michael@0: 
michael@0:         SkASSERT(kBlack_Color == fRoot->fColor);
michael@0:         if (1 == fCount) {
michael@0:             SkASSERT(fFirst == fRoot);
michael@0:             SkASSERT(fLast == fRoot);
michael@0:             SkASSERT(0 == fRoot->fChildren[kLeft_Child]);
michael@0:             SkASSERT(0 == fRoot->fChildren[kRight_Child]);
michael@0:         }
michael@0:     } else {
michael@0:         SkASSERT(NULL == fRoot);
michael@0:         SkASSERT(NULL == fFirst);
michael@0:         SkASSERT(NULL == fLast);
michael@0:     }
michael@0: #if DEEP_VALIDATE
michael@0:     int bh;
michael@0:     int count = checkNode(fRoot, &bh);
michael@0:     SkASSERT(count == fCount);
michael@0: #endif
michael@0: }
michael@0: 
michael@0: template <typename T, typename C>
michael@0: int GrRedBlackTree<T,C>::checkNode(Node* n, int* bh) const {
michael@0:     if (NULL != n) {
michael@0:         SkASSERT(validateChildRelations(n, false));
michael@0:         if (kBlack_Color == n->fColor) {
michael@0:             *bh += 1;
michael@0:         }
michael@0:         SkASSERT(!fComp(n->fItem, fFirst->fItem));
michael@0:         SkASSERT(!fComp(fLast->fItem, n->fItem));
michael@0:         int leftBh = *bh;
michael@0:         int rightBh = *bh;
michael@0:         int cl = checkNode(n->fChildren[kLeft_Child], &leftBh);
michael@0:         int cr = checkNode(n->fChildren[kRight_Child], &rightBh);
michael@0:         SkASSERT(leftBh == rightBh);
michael@0:         *bh = leftBh;
michael@0:         return 1 + cl + cr;
michael@0:     }
michael@0:     return 0;
michael@0: }
michael@0: 
michael@0: template <typename T, typename C>
michael@0: bool GrRedBlackTree<T,C>::validateChildRelations(const Node* n,
michael@0:                                                  bool allowRedRed) const {
michael@0:     if (NULL != n) {
michael@0:         if (NULL != n->fChildren[kLeft_Child] ||
michael@0:             NULL != n->fChildren[kRight_Child]) {
michael@0:             if (n->fChildren[kLeft_Child] == n->fChildren[kRight_Child]) {
michael@0:                 return validateChildRelationsFailed();
michael@0:             }
michael@0:             if (n->fChildren[kLeft_Child] == n->fParent &&
michael@0:                 NULL != n->fParent) {
michael@0:                 return validateChildRelationsFailed();
michael@0:             }
michael@0:             if (n->fChildren[kRight_Child] == n->fParent &&
michael@0:                 NULL != n->fParent) {
michael@0:                 return validateChildRelationsFailed();
michael@0:             }
michael@0:             if (NULL != n->fChildren[kLeft_Child]) {
michael@0:                 if (!allowRedRed &&
michael@0:                     kRed_Color == n->fChildren[kLeft_Child]->fColor &&
michael@0:                     kRed_Color == n->fColor) {
michael@0:                     return validateChildRelationsFailed();
michael@0:                 }
michael@0:                 if (n->fChildren[kLeft_Child]->fParent != n) {
michael@0:                     return validateChildRelationsFailed();
michael@0:                 }
michael@0:                 if (!(fComp(n->fChildren[kLeft_Child]->fItem, n->fItem) ||
michael@0:                       (!fComp(n->fChildren[kLeft_Child]->fItem, n->fItem) &&
michael@0:                        !fComp(n->fItem, n->fChildren[kLeft_Child]->fItem)))) {
michael@0:                     return validateChildRelationsFailed();
michael@0:                 }
michael@0:             }
michael@0:             if (NULL != n->fChildren[kRight_Child]) {
michael@0:                 if (!allowRedRed &&
michael@0:                     kRed_Color == n->fChildren[kRight_Child]->fColor &&
michael@0:                     kRed_Color == n->fColor) {
michael@0:                     return validateChildRelationsFailed();
michael@0:                 }
michael@0:                 if (n->fChildren[kRight_Child]->fParent != n) {
michael@0:                     return validateChildRelationsFailed();
michael@0:                 }
michael@0:                 if (!(fComp(n->fItem, n->fChildren[kRight_Child]->fItem) ||
michael@0:                       (!fComp(n->fChildren[kRight_Child]->fItem, n->fItem) &&
michael@0:                        !fComp(n->fItem, n->fChildren[kRight_Child]->fItem)))) {
michael@0:                     return validateChildRelationsFailed();
michael@0:                 }
michael@0:             }
michael@0:         }
michael@0:     }
michael@0:     return true;
michael@0: }
michael@0: #endif
michael@0: 
michael@0: #endif