GrRedBlackTree.h revision a0b40280a49a8a43af7929ead3b3489951c58501
1ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com/* 2ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com * Copyright 2011 Google Inc. 3ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com * 4ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com * Use of this source code is governed by a BSD-style license that can be 5ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com * found in the LICENSE file. 66034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com */ 76034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com 86034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com#ifndef GrRedBlackTree_DEFINED 96034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com#define GrRedBlackTree_DEFINED 106034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com 11a0b40280a49a8a43af7929ead3b3489951c58501commit-bot@chromium.org#include "SkTypes.h" 126034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com 136034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.comtemplate <typename T> 146034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.comclass GrLess { 156034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.compublic: 166034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com bool operator()(const T& a, const T& b) const { return a < b; } 176034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com}; 186034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com 196034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.comtemplate <typename T> 206034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.comclass GrLess<T*> { 216034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.compublic: 226034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com bool operator()(const T* a, const T* b) const { return *a < *b; } 236034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com}; 246034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com 256034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com/** 266034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com * In debug build this will cause full traversals of the tree when the validate 276034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com * is called on insert and remove. Useful for debugging but very slow. 286034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com */ 296034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com#define DEEP_VALIDATE 0 306034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com 316034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com/** 326034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com * A sorted tree that uses the red-black tree algorithm. Allows duplicate 336034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com * entries. Data is of type T and is compared using functor C. A single C object 346034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com * will be created and used for all comparisons. 356034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com */ 366034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.comtemplate <typename T, typename C = GrLess<T> > 37a0b40280a49a8a43af7929ead3b3489951c58501commit-bot@chromium.orgclass GrRedBlackTree : public SkNoncopyable { 386034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.compublic: 396034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com /** 406034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com * Creates an empty tree. 416034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com */ 426034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com GrRedBlackTree(); 436034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com virtual ~GrRedBlackTree(); 446034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com 456034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com /** 466034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com * Class used to iterater through the tree. The valid range of the tree 476034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com * is given by [begin(), end()). It is legal to dereference begin() but not 486034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com * end(). The iterator has preincrement and predecrement operators, it is 496034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com * legal to decerement end() if the tree is not empty to get the last 506034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com * element. However, a last() helper is provided. 516034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com */ 526034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com class Iter; 536034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com 546034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com /** 556034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com * Add an element to the tree. Duplicates are allowed. 566034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com * @param t the item to add. 576034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com * @return an iterator to the item. 586034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com */ 596034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com Iter insert(const T& t); 606034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com 616034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com /** 626034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com * Removes all items in the tree. 636034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com */ 646034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com void reset(); 656034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com 666034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com /** 676034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com * @return true if there are no items in the tree, false otherwise. 686034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com */ 696034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com bool empty() const {return 0 == fCount;} 706034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com 716034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com /** 726034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com * @return the number of items in the tree. 736034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com */ 746034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com int count() const {return fCount;} 756034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com 766034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com /** 776034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com * @return an iterator to the first item in sorted order, or end() if empty 786034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com */ 796034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com Iter begin(); 806034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com /** 816034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com * Gets the last valid iterator. This is always valid, even on an empty. 826034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com * However, it can never be dereferenced. Useful as a loop terminator. 836034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com * @return an iterator that is just beyond the last item in sorted order. 846034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com */ 856034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com Iter end(); 866034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com /** 876034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com * @return an iterator that to the last item in sorted order, or end() if 886034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com * empty. 896034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com */ 906034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com Iter last(); 916034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com 926034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com /** 936034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com * Finds an occurrence of an item. 946034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com * @param t the item to find. 956034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com * @return an iterator to a tree element equal to t or end() if none exists. 966034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com */ 976034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com Iter find(const T& t); 986034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com /** 996034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com * Finds the first of an item in iterator order. 1006034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com * @param t the item to find. 1016034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com * @return an iterator to the first element equal to t or end() if 1026034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com * none exists. 1036034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com */ 1046034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com Iter findFirst(const T& t); 1056034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com /** 1066034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com * Finds the last of an item in iterator order. 1076034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com * @param t the item to find. 1086034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com * @return an iterator to the last element equal to t or end() if 1096034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com * none exists. 1106034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com */ 1116034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com Iter findLast(const T& t); 1126034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com /** 1136034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com * Gets the number of items in the tree equal to t. 1146034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com * @param t the item to count. 1156034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com * @return number of items equal to t in the tree 1166034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com */ 1176034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com int countOf(const T& t) const; 1186034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com 1196034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com /** 1206034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com * Removes the item indicated by an iterator. The iterator will not be valid 1216034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com * afterwards. 1226034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com * 1236034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com * @param iter iterator of item to remove. Must be valid (not end()). 1246034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com */ 1256034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com void remove(const Iter& iter) { deleteAtNode(iter.fN); } 1266034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com 1276034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com static void UnitTest(); 1286034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com 1296034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.comprivate: 1306034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com enum Color { 1316034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com kRed_Color, 1326034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com kBlack_Color 1336034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com }; 1346034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com 1356034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com enum Child { 1366034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com kLeft_Child = 0, 1376034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com kRight_Child = 1 1386034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com }; 1396034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com 1406034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com struct Node { 1416034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com T fItem; 1426034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com Color fColor; 1436034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com 1446034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com Node* fParent; 1456034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com Node* fChildren[2]; 1466034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com }; 1476034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com 1486034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com void rotateRight(Node* n); 1496034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com void rotateLeft(Node* n); 1506034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com 1516034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com static Node* SuccessorNode(Node* x); 1526034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com static Node* PredecessorNode(Node* x); 1536034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com 1546034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com void deleteAtNode(Node* x); 1556034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com static void RecursiveDelete(Node* x); 1566034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com 157bcdbbe61e1a3f89545b2c1461164f0f8bf5f0797bsalomon@google.com int onCountOf(const Node* n, const T& t) const; 1586034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com 159515dcd36032997ce335daa0163c6d67e851bcad1commit-bot@chromium.org#ifdef SK_DEBUG 1606034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com void validate() const; 1616034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com int checkNode(Node* n, int* blackHeight) const; 1626034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // checks relationship between a node and its children. allowRedRed means 1636034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // node may be in an intermediate state where a red parent has a red child. 1646034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com bool validateChildRelations(const Node* n, bool allowRedRed) const; 1656034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // place to stick break point if validateChildRelations is failing. 1666034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com bool validateChildRelationsFailed() const { return false; } 1676034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com#else 1686034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com void validate() const {} 1696034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com#endif 1706034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com 1716034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com int fCount; 1726034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com Node* fRoot; 1736034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com Node* fFirst; 1746034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com Node* fLast; 1756034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com 1766034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com const C fComp; 1776034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com}; 1786034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com 1796034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.comtemplate <typename T, typename C> 1806034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.comclass GrRedBlackTree<T,C>::Iter { 1816034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.compublic: 1826034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com Iter() {}; 1836034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com Iter(const Iter& i) {fN = i.fN; fTree = i.fTree;} 1846034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com Iter& operator =(const Iter& i) { 1856034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com fN = i.fN; 1866034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com fTree = i.fTree; 1876034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com return *this; 1886034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } 1896034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // altering the sort value of the item using this method will cause 1906034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // errors. 1916034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com T& operator *() const { return fN->fItem; } 1926034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com bool operator ==(const Iter& i) const { 1936034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com return fN == i.fN && fTree == i.fTree; 1946034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } 1956034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com bool operator !=(const Iter& i) const { return !(*this == i); } 1966034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com Iter& operator ++() { 197f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(*this != fTree->end()); 1986034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com fN = SuccessorNode(fN); 1996034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com return *this; 2006034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } 2016034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com Iter& operator --() { 202f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(*this != fTree->begin()); 2036034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com if (NULL != fN) { 2046034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com fN = PredecessorNode(fN); 2056034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } else { 2066034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com *this = fTree->last(); 2076034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } 2086034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com return *this; 2096034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } 2106034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com 2116034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.comprivate: 2126034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com friend class GrRedBlackTree; 2136034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com explicit Iter(Node* n, GrRedBlackTree* tree) { 2146034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com fN = n; 2156034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com fTree = tree; 2166034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } 2176034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com Node* fN; 2186034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com GrRedBlackTree* fTree; 2196034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com}; 2206034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com 2216034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.comtemplate <typename T, typename C> 2226034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.comGrRedBlackTree<T,C>::GrRedBlackTree() : fComp() { 2236034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com fRoot = NULL; 2246034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com fFirst = NULL; 2256034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com fLast = NULL; 2266034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com fCount = 0; 2276034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com validate(); 2286034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com} 2296034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com 2306034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.comtemplate <typename T, typename C> 2316034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.comGrRedBlackTree<T,C>::~GrRedBlackTree() { 2326034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com RecursiveDelete(fRoot); 2336034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com} 2346034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com 2356034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.comtemplate <typename T, typename C> 2366034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.comtypename GrRedBlackTree<T,C>::Iter GrRedBlackTree<T,C>::begin() { 2376034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com return Iter(fFirst, this); 2386034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com} 2396034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com 2406034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.comtemplate <typename T, typename C> 2416034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.comtypename GrRedBlackTree<T,C>::Iter GrRedBlackTree<T,C>::end() { 2426034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com return Iter(NULL, this); 2436034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com} 2446034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com 2456034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.comtemplate <typename T, typename C> 2466034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.comtypename GrRedBlackTree<T,C>::Iter GrRedBlackTree<T,C>::last() { 2476034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com return Iter(fLast, this); 2486034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com} 2496034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com 2506034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.comtemplate <typename T, typename C> 2516034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.comtypename GrRedBlackTree<T,C>::Iter GrRedBlackTree<T,C>::find(const T& t) { 2526034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com Node* n = fRoot; 2536034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com while (NULL != n) { 2546034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com if (fComp(t, n->fItem)) { 2556034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com n = n->fChildren[kLeft_Child]; 2566034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } else { 2576034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com if (!fComp(n->fItem, t)) { 2586034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com return Iter(n, this); 2596034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } 2606034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com n = n->fChildren[kRight_Child]; 2616034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } 2626034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } 2636034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com return end(); 2646034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com} 2656034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com 2666034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.comtemplate <typename T, typename C> 2676034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.comtypename GrRedBlackTree<T,C>::Iter GrRedBlackTree<T,C>::findFirst(const T& t) { 2686034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com Node* n = fRoot; 2696034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com Node* leftMost = NULL; 2706034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com while (NULL != n) { 2716034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com if (fComp(t, n->fItem)) { 2726034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com n = n->fChildren[kLeft_Child]; 2736034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } else { 2746034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com if (!fComp(n->fItem, t)) { 2756034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // found one. check if another in left subtree. 2766034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com leftMost = n; 2776034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com n = n->fChildren[kLeft_Child]; 2786034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } else { 2796034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com n = n->fChildren[kRight_Child]; 2806034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } 2816034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } 2826034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } 2836034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com return Iter(leftMost, this); 2846034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com} 2856034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com 2866034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.comtemplate <typename T, typename C> 2876034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.comtypename GrRedBlackTree<T,C>::Iter GrRedBlackTree<T,C>::findLast(const T& t) { 2886034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com Node* n = fRoot; 2896034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com Node* rightMost = NULL; 2906034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com while (NULL != n) { 2916034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com if (fComp(t, n->fItem)) { 2926034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com n = n->fChildren[kLeft_Child]; 2936034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } else { 2946034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com if (!fComp(n->fItem, t)) { 2956034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // found one. check if another in right subtree. 2966034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com rightMost = n; 2976034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } 2986034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com n = n->fChildren[kRight_Child]; 2996034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } 3006034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } 3016034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com return Iter(rightMost, this); 3026034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com} 3036034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com 3046034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.comtemplate <typename T, typename C> 3056034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.comint GrRedBlackTree<T,C>::countOf(const T& t) const { 306bcdbbe61e1a3f89545b2c1461164f0f8bf5f0797bsalomon@google.com return onCountOf(fRoot, t); 3076034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com} 3086034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com 3096034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.comtemplate <typename T, typename C> 310bcdbbe61e1a3f89545b2c1461164f0f8bf5f0797bsalomon@google.comint GrRedBlackTree<T,C>::onCountOf(const Node* n, const T& t) const { 3116034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // this is count*log(n) :( 3126034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com while (NULL != n) { 3136034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com if (fComp(t, n->fItem)) { 3146034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com n = n->fChildren[kLeft_Child]; 3156034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } else { 3166034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com if (!fComp(n->fItem, t)) { 3176034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com int count = 1; 318bcdbbe61e1a3f89545b2c1461164f0f8bf5f0797bsalomon@google.com count += onCountOf(n->fChildren[kLeft_Child], t); 319bcdbbe61e1a3f89545b2c1461164f0f8bf5f0797bsalomon@google.com count += onCountOf(n->fChildren[kRight_Child], t); 3206034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com return count; 3216034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } 3226034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com n = n->fChildren[kRight_Child]; 3236034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } 3246034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } 3256034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com return 0; 3266034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com 3276034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com} 3286034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com 3296034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.comtemplate <typename T, typename C> 3306034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.comvoid GrRedBlackTree<T,C>::reset() { 3316034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com RecursiveDelete(fRoot); 3326034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com fRoot = NULL; 3336034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com fFirst = NULL; 3346034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com fLast = NULL; 3356034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com fCount = 0; 3366034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com} 3376034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com 3386034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.comtemplate <typename T, typename C> 3396034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.comtypename GrRedBlackTree<T,C>::Iter GrRedBlackTree<T,C>::insert(const T& t) { 3406034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com validate(); 3416034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com 3426034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com ++fCount; 3436034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com 344c377baf406996aed18d82d328029c82dbc3b8ddatomhudson@google.com Node* x = SkNEW(Node); 3456034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com x->fChildren[kLeft_Child] = NULL; 3466034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com x->fChildren[kRight_Child] = NULL; 3476034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com x->fItem = t; 3486034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com 3495aaa69e4339e229adfb05e96084a8ec0a590238bbsalomon@google.com Node* returnNode = x; 3505aaa69e4339e229adfb05e96084a8ec0a590238bbsalomon@google.com 3516034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com Node* gp = NULL; 3526034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com Node* p = NULL; 3536034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com Node* n = fRoot; 354ba9d628b1b7aa13ddd59499624f672c6443b5f74bsalomon@google.com Child pc = kLeft_Child; // suppress uninit warning 3552c2508d2ede7e6a8eb43dba0ef2419905ccbb3d8tomhudson@google.com Child gpc = kLeft_Child; 3566034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com 3576034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com bool first = true; 3586034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com bool last = true; 3596034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com while (NULL != n) { 3606034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com gpc = pc; 3616034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com pc = fComp(x->fItem, n->fItem) ? kLeft_Child : kRight_Child; 3626034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com first = first && kLeft_Child == pc; 3636034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com last = last && kRight_Child == pc; 3646034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com gp = p; 3656034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com p = n; 3666034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com n = p->fChildren[pc]; 3676034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } 3686034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com if (last) { 3696034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com fLast = x; 3706034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } 3716034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com if (first) { 3726034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com fFirst = x; 3736034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } 3746034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com 3756034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com if (NULL == p) { 3766034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com fRoot = x; 3776034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com x->fColor = kBlack_Color; 3786034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com x->fParent = NULL; 379f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(1 == fCount); 3805aaa69e4339e229adfb05e96084a8ec0a590238bbsalomon@google.com return Iter(returnNode, this); 3816034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } 3826034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com p->fChildren[pc] = x; 3836034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com x->fColor = kRed_Color; 3846034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com x->fParent = p; 3856034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com 3866034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com do { 3876034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // assumptions at loop start. 388f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(NULL != x); 389f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(kRed_Color == x->fColor); 3906034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // can't have a grandparent but no parent. 391f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(!(NULL != gp && NULL == p)); 3926034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // make sure pc and gpc are correct 393f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(NULL == p || p->fChildren[pc] == x); 394f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(NULL == gp || gp->fChildren[gpc] == p); 3956034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com 3966034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // if x's parent is black then we didn't violate any of the 3976034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // red/black properties when we added x as red. 3986034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com if (kBlack_Color == p->fColor) { 3995aaa69e4339e229adfb05e96084a8ec0a590238bbsalomon@google.com return Iter(returnNode, this); 4006034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } 4016034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // gp must be valid because if p was the root then it is black 402f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(NULL != gp); 4036034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // gp must be black since it's child, p, is red. 404f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(kBlack_Color == gp->fColor); 4056034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com 4066034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com 4076034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // x and its parent are red, violating red-black property. 4086034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com Node* u = gp->fChildren[1-gpc]; 4096034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // if x's uncle (p's sibling) is also red then we can flip 4106034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // p and u to black and make gp red. But then we have to recurse 4116034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // up to gp since it's parent may also be red. 4126034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com if (NULL != u && kRed_Color == u->fColor) { 4136034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com p->fColor = kBlack_Color; 4146034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com u->fColor = kBlack_Color; 4156034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com gp->fColor = kRed_Color; 4166034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com x = gp; 4176034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com p = x->fParent; 4186034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com if (NULL == p) { 4196034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // x (prev gp) is the root, color it black and be done. 420f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(fRoot == x); 4216034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com x->fColor = kBlack_Color; 4226034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com validate(); 4235aaa69e4339e229adfb05e96084a8ec0a590238bbsalomon@google.com return Iter(returnNode, this); 4246034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } 4256034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com gp = p->fParent; 4266034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com pc = (p->fChildren[kLeft_Child] == x) ? kLeft_Child : 4276034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com kRight_Child; 4286034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com if (NULL != gp) { 4296034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com gpc = (gp->fChildren[kLeft_Child] == p) ? kLeft_Child : 4306034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com kRight_Child; 4316034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } 4326034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com continue; 4336034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } break; 4346034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } while (true); 4356034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // Here p is red but u is black and we still have to resolve the fact 4366034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // that x and p are both red. 437f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(NULL == gp->fChildren[1-gpc] || kBlack_Color == gp->fChildren[1-gpc]->fColor); 438f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(kRed_Color == x->fColor); 439f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(kRed_Color == p->fColor); 440f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(kBlack_Color == gp->fColor); 4416034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com 4426034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // make x be on the same side of p as p is of gp. If it isn't already 4436034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // the case then rotate x up to p and swap their labels. 4446034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com if (pc != gpc) { 4456034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com if (kRight_Child == pc) { 4466034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com rotateLeft(p); 4476034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com Node* temp = p; 4486034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com p = x; 4496034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com x = temp; 4506034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com pc = kLeft_Child; 4516034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } else { 4526034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com rotateRight(p); 4536034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com Node* temp = p; 4546034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com p = x; 4556034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com x = temp; 4566034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com pc = kRight_Child; 4576034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } 4586034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } 4596034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // we now rotate gp down, pulling up p to be it's new parent. 4606034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // gp's child, u, that is not affected we know to be black. gp's new 4616034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // child is p's previous child (x's pre-rotation sibling) which must be 4626034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // black since p is red. 463f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(NULL == p->fChildren[1-pc] || 4646034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com kBlack_Color == p->fChildren[1-pc]->fColor); 4656034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // Since gp's two children are black it can become red if p is made 4666034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // black. This leaves the black-height of both of p's new subtrees 4676034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // preserved and removes the red/red parent child relationship. 4686034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com p->fColor = kBlack_Color; 4696034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com gp->fColor = kRed_Color; 4706034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com if (kLeft_Child == pc) { 4716034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com rotateRight(gp); 4726034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } else { 4736034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com rotateLeft(gp); 4746034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } 4756034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com validate(); 4765aaa69e4339e229adfb05e96084a8ec0a590238bbsalomon@google.com return Iter(returnNode, this); 4776034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com} 4786034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com 4796034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com 4806034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.comtemplate <typename T, typename C> 4816034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.comvoid GrRedBlackTree<T,C>::rotateRight(Node* n) { 4826034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com /* d? d? 4836034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com * / / 4846034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com * n s 4856034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com * / \ ---> / \ 4866034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com * s a? c? n 4876034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com * / \ / \ 4886034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com * c? b? b? a? 4896034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com */ 4906034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com Node* d = n->fParent; 4916034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com Node* s = n->fChildren[kLeft_Child]; 492f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(NULL != s); 4936034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com Node* b = s->fChildren[kRight_Child]; 4946034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com 4956034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com if (NULL != d) { 4966034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com Child c = d->fChildren[kLeft_Child] == n ? kLeft_Child : 4976034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com kRight_Child; 4986034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com d->fChildren[c] = s; 4996034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } else { 500f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(fRoot == n); 5016034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com fRoot = s; 5026034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } 5036034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com s->fParent = d; 5046034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com s->fChildren[kRight_Child] = n; 5056034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com n->fParent = s; 5066034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com n->fChildren[kLeft_Child] = b; 5076034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com if (NULL != b) { 5086034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com b->fParent = n; 5096034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } 5106034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com 5116034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com GR_DEBUGASSERT(validateChildRelations(d, true)); 5126034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com GR_DEBUGASSERT(validateChildRelations(s, true)); 5136034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com GR_DEBUGASSERT(validateChildRelations(n, false)); 5146034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com GR_DEBUGASSERT(validateChildRelations(n->fChildren[kRight_Child], true)); 5156034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com GR_DEBUGASSERT(validateChildRelations(b, true)); 5166034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com GR_DEBUGASSERT(validateChildRelations(s->fChildren[kLeft_Child], true)); 5176034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com} 5186034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com 5196034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.comtemplate <typename T, typename C> 5206034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.comvoid GrRedBlackTree<T,C>::rotateLeft(Node* n) { 5216034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com 5226034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com Node* d = n->fParent; 5236034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com Node* s = n->fChildren[kRight_Child]; 524f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(NULL != s); 5256034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com Node* b = s->fChildren[kLeft_Child]; 5266034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com 5276034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com if (NULL != d) { 5286034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com Child c = d->fChildren[kRight_Child] == n ? kRight_Child : 5296034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com kLeft_Child; 5306034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com d->fChildren[c] = s; 5316034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } else { 532f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(fRoot == n); 5336034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com fRoot = s; 5346034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } 5356034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com s->fParent = d; 5366034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com s->fChildren[kLeft_Child] = n; 5376034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com n->fParent = s; 5386034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com n->fChildren[kRight_Child] = b; 5396034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com if (NULL != b) { 5406034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com b->fParent = n; 5416034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } 5426034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com 5436034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com GR_DEBUGASSERT(validateChildRelations(d, true)); 5446034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com GR_DEBUGASSERT(validateChildRelations(s, true)); 5456034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com GR_DEBUGASSERT(validateChildRelations(n, true)); 5466034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com GR_DEBUGASSERT(validateChildRelations(n->fChildren[kLeft_Child], true)); 5476034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com GR_DEBUGASSERT(validateChildRelations(b, true)); 5486034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com GR_DEBUGASSERT(validateChildRelations(s->fChildren[kRight_Child], true)); 5496034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com} 5506034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com 5516034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.comtemplate <typename T, typename C> 5526034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.comtypename GrRedBlackTree<T,C>::Node* GrRedBlackTree<T,C>::SuccessorNode(Node* x) { 553f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(NULL != x); 5546034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com if (NULL != x->fChildren[kRight_Child]) { 5556034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com x = x->fChildren[kRight_Child]; 5566034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com while (NULL != x->fChildren[kLeft_Child]) { 5576034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com x = x->fChildren[kLeft_Child]; 5586034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } 5596034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com return x; 5606034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } 5616034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com while (NULL != x->fParent && x == x->fParent->fChildren[kRight_Child]) { 5626034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com x = x->fParent; 5636034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } 5646034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com return x->fParent; 5656034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com} 5666034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com 5676034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.comtemplate <typename T, typename C> 5686034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.comtypename GrRedBlackTree<T,C>::Node* GrRedBlackTree<T,C>::PredecessorNode(Node* x) { 569f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(NULL != x); 5706034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com if (NULL != x->fChildren[kLeft_Child]) { 5716034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com x = x->fChildren[kLeft_Child]; 5726034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com while (NULL != x->fChildren[kRight_Child]) { 5736034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com x = x->fChildren[kRight_Child]; 5746034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } 5756034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com return x; 5766034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } 5776034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com while (NULL != x->fParent && x == x->fParent->fChildren[kLeft_Child]) { 5786034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com x = x->fParent; 5796034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } 5806034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com return x->fParent; 5816034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com} 5826034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com 5836034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.comtemplate <typename T, typename C> 5846034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.comvoid GrRedBlackTree<T,C>::deleteAtNode(Node* x) { 585f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(NULL != x); 5866034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com validate(); 5876034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com --fCount; 5886034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com 5896034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com bool hasLeft = NULL != x->fChildren[kLeft_Child]; 5906034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com bool hasRight = NULL != x->fChildren[kRight_Child]; 5916034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com Child c = hasLeft ? kLeft_Child : kRight_Child; 5926034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com 5936034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com if (hasLeft && hasRight) { 5946034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // first and last can't have two children. 595f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(fFirst != x); 596f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(fLast != x); 5976034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // if x is an interior node then we find it's successor 5986034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // and swap them. 5996034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com Node* s = x->fChildren[kRight_Child]; 6006034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com while (NULL != s->fChildren[kLeft_Child]) { 6016034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com s = s->fChildren[kLeft_Child]; 6026034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } 603f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(NULL != s); 6046034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // this might be expensive relative to swapping node ptrs around. 6056034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // depends on T. 6066034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com x->fItem = s->fItem; 6076034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com x = s; 6086034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com c = kRight_Child; 6096034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } else if (NULL == x->fParent) { 6106034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // if x was the root we just replace it with its child and make 6116034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // the new root (if the tree is not empty) black. 612f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(fRoot == x); 6136034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com fRoot = x->fChildren[c]; 6146034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com if (NULL != fRoot) { 6156034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com fRoot->fParent = NULL; 6166034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com fRoot->fColor = kBlack_Color; 6176034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com if (x == fLast) { 618f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(c == kLeft_Child); 6196034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com fLast = fRoot; 6206034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } else if (x == fFirst) { 621f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(c == kRight_Child); 6226034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com fFirst = fRoot; 6236034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } 6246034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } else { 625f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(fFirst == fLast && x == fFirst); 6266034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com fFirst = NULL; 6276034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com fLast = NULL; 628f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(0 == fCount); 6296034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } 6306034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com delete x; 6316034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com validate(); 6326034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com return; 6336034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } 6346034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com 6356034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com Child pc; 6366034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com Node* p = x->fParent; 6376034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com pc = p->fChildren[kLeft_Child] == x ? kLeft_Child : kRight_Child; 6386034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com 6396034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com if (NULL == x->fChildren[c]) { 6406034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com if (fLast == x) { 6416034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com fLast = p; 642f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(p == PredecessorNode(x)); 6436034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } else if (fFirst == x) { 6446034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com fFirst = p; 645f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(p == SuccessorNode(x)); 6466034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } 6476034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // x has two implicit black children. 6486034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com Color xcolor = x->fColor; 6496034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com p->fChildren[pc] = NULL; 6506034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com delete x; 6515aaa69e4339e229adfb05e96084a8ec0a590238bbsalomon@google.com x = NULL; 6526034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // when x is red it can be with an implicit black leaf without 6536034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // violating any of the red-black tree properties. 6546034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com if (kRed_Color == xcolor) { 6556034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com validate(); 6566034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com return; 6576034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } 6586034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // s is p's other child (x's sibling) 6596034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com Node* s = p->fChildren[1-pc]; 6606034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com 6616034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com //s cannot be an implicit black node because the original 6626034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // black-height at x was >= 2 and s's black-height must equal the 6636034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // initial black height of x. 664f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(NULL != s); 665f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(p == s->fParent); 6666034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com 6676034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // assigned in loop 6686034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com Node* sl; 6696034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com Node* sr; 6706034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com bool slRed; 6716034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com bool srRed; 6726034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com 6736034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com do { 6746034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // When we start this loop x may already be deleted it is/was 6756034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // p's child on its pc side. x's children are/were black. The 6766034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // first time through the loop they are implict children. 6776034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // On later passes we will be walking up the tree and they will 6786034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // be real nodes. 6796034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // The x side of p has a black-height that is one less than the 6806034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // s side. It must be rebalanced. 681f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(NULL != s); 682f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(p == s->fParent); 683f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(NULL == x || x->fParent == p); 6846034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com 6856034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com //sl and sr are s's children, which may be implicit. 6866034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com sl = s->fChildren[kLeft_Child]; 6876034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com sr = s->fChildren[kRight_Child]; 6886034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com 6896034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // if the s is red we will rotate s and p, swap their colors so 6906034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // that x's new sibling is black 6916034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com if (kRed_Color == s->fColor) { 6926034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // if s is red then it's parent must be black. 693f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(kBlack_Color == p->fColor); 6946034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // s's children must also be black since s is red. They can't 6956034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // be implicit since s is red and it's black-height is >= 2. 696f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(NULL != sl && kBlack_Color == sl->fColor); 697f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(NULL != sr && kBlack_Color == sr->fColor); 6986034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com p->fColor = kRed_Color; 6996034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com s->fColor = kBlack_Color; 7006034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com if (kLeft_Child == pc) { 7016034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com rotateLeft(p); 7026034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com s = sl; 7036034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } else { 7046034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com rotateRight(p); 7056034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com s = sr; 7066034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } 7076034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com sl = s->fChildren[kLeft_Child]; 7086034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com sr = s->fChildren[kRight_Child]; 7096034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } 7106034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // x and s are now both black. 711f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(kBlack_Color == s->fColor); 712f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(NULL == x || kBlack_Color == x->fColor); 713f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(p == s->fParent); 714f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(NULL == x || p == x->fParent); 7156034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com 7166034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // when x is deleted its subtree will have reduced black-height. 7176034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com slRed = (NULL != sl && kRed_Color == sl->fColor); 7186034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com srRed = (NULL != sr && kRed_Color == sr->fColor); 7196034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com if (!slRed && !srRed) { 7206034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // if s can be made red that will balance out x's removal 7216034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // to make both subtrees of p have the same black-height. 7226034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com if (kBlack_Color == p->fColor) { 7236034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com s->fColor = kRed_Color; 7246034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // now subtree at p has black-height of one less than 7256034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // p's parent's other child's subtree. We move x up to 7266034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // p and go through the loop again. At the top of loop 7276034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // we assumed x and x's children are black, which holds 7286034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // by above ifs. 7296034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // if p is the root there is no other subtree to balance 7306034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // against. 7316034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com x = p; 7326034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com p = x->fParent; 7336034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com if (NULL == p) { 734f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(fRoot == x); 7356034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com validate(); 7366034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com return; 7376034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } else { 7386034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com pc = p->fChildren[kLeft_Child] == x ? kLeft_Child : 7396034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com kRight_Child; 7406034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com 7416034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } 7426034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com s = p->fChildren[1-pc]; 743f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(NULL != s); 744f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(p == s->fParent); 7456034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com continue; 7466034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } else if (kRed_Color == p->fColor) { 7476034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // we can make p black and s red. This balance out p's 7486034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // two subtrees and keep the same black-height as it was 7496034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // before the delete. 7506034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com s->fColor = kRed_Color; 7516034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com p->fColor = kBlack_Color; 7526034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com validate(); 7536034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com return; 7546034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } 7556034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } 7566034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com break; 7576034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } while (true); 7586034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // if we made it here one or both of sl and sr is red. 7596034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // s and x are black. We make sure that a red child is on 7606034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // the same side of s as s is of p. 761f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(slRed || srRed); 7626034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com if (kLeft_Child == pc && !srRed) { 7636034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com s->fColor = kRed_Color; 7646034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com sl->fColor = kBlack_Color; 7656034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com rotateRight(s); 7666034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com sr = s; 7676034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com s = sl; 7686034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com //sl = s->fChildren[kLeft_Child]; don't need this 7696034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } else if (kRight_Child == pc && !slRed) { 7706034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com s->fColor = kRed_Color; 7716034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com sr->fColor = kBlack_Color; 7726034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com rotateLeft(s); 7736034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com sl = s; 7746034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com s = sr; 7756034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com //sr = s->fChildren[kRight_Child]; don't need this 7766034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } 7776034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // now p is either red or black, x and s are red and s's 1-pc 7786034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // child is red. 7796034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // We rotate p towards x, pulling s up to replace p. We make 7806034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // p be black and s takes p's old color. 7816034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // Whether p was red or black, we've increased its pc subtree 7826034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // rooted at x by 1 (balancing the imbalance at the start) and 7836034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // we've also its subtree rooted at s's black-height by 1. This 7846034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // can be balanced by making s's red child be black. 7856034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com s->fColor = p->fColor; 7866034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com p->fColor = kBlack_Color; 7876034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com if (kLeft_Child == pc) { 788f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(NULL != sr && kRed_Color == sr->fColor); 7896034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com sr->fColor = kBlack_Color; 7906034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com rotateLeft(p); 7916034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } else { 792f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(NULL != sl && kRed_Color == sl->fColor); 7936034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com sl->fColor = kBlack_Color; 7946034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com rotateRight(p); 7956034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } 7966034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } 7976034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com else { 7986034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // x has exactly one implicit black child. x cannot be red. 7996034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // Proof by contradiction: Assume X is red. Let c0 be x's implicit 8006034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // child and c1 be its non-implicit child. c1 must be black because 8016034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // red nodes always have two black children. Then the two subtrees 8026034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // of x rooted at c0 and c1 will have different black-heights. 803f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(kBlack_Color == x->fColor); 8046034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // So we know x is black and has one implicit black child, c0. c1 8056034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // must be red, otherwise the subtree at c1 will have a different 8066034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // black-height than the subtree rooted at c0. 807f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(kRed_Color == x->fChildren[c]->fColor); 8086034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // replace x with c1, making c1 black, preserves all red-black tree 8096034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // props. 8106034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com Node* c1 = x->fChildren[c]; 8116034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com if (x == fFirst) { 812f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(c == kRight_Child); 8136034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com fFirst = c1; 8146034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com while (NULL != fFirst->fChildren[kLeft_Child]) { 8156034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com fFirst = fFirst->fChildren[kLeft_Child]; 8166034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } 817f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(fFirst == SuccessorNode(x)); 8186034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } else if (x == fLast) { 819f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(c == kLeft_Child); 8206034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com fLast = c1; 8216034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com while (NULL != fLast->fChildren[kRight_Child]) { 8226034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com fLast = fLast->fChildren[kRight_Child]; 8236034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } 824f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(fLast == PredecessorNode(x)); 8256034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } 8266034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com c1->fParent = p; 8276034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com p->fChildren[pc] = c1; 8286034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com c1->fColor = kBlack_Color; 8296034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com delete x; 8306034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com validate(); 8316034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } 8326034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com validate(); 8336034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com} 8346034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com 8356034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.comtemplate <typename T, typename C> 8366034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.comvoid GrRedBlackTree<T,C>::RecursiveDelete(Node* x) { 8376034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com if (NULL != x) { 8386034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com RecursiveDelete(x->fChildren[kLeft_Child]); 8396034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com RecursiveDelete(x->fChildren[kRight_Child]); 8406034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com delete x; 8416034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } 8426034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com} 8436034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com 844515dcd36032997ce335daa0163c6d67e851bcad1commit-bot@chromium.org#ifdef SK_DEBUG 8456034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.comtemplate <typename T, typename C> 8466034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.comvoid GrRedBlackTree<T,C>::validate() const { 8476034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com if (fCount) { 848f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(NULL == fRoot->fParent); 849f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(NULL != fFirst); 850f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(NULL != fLast); 8516034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com 852f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(kBlack_Color == fRoot->fColor); 8536034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com if (1 == fCount) { 854f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(fFirst == fRoot); 855f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(fLast == fRoot); 856f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(0 == fRoot->fChildren[kLeft_Child]); 857f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(0 == fRoot->fChildren[kRight_Child]); 8586034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } 8596034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } else { 860f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(NULL == fRoot); 861f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(NULL == fFirst); 862f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(NULL == fLast); 8636034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } 8646034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com#if DEEP_VALIDATE 8656034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com int bh; 8666034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com int count = checkNode(fRoot, &bh); 867f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(count == fCount); 8686034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com#endif 8696034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com} 8706034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com 8716034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.comtemplate <typename T, typename C> 8726034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.comint GrRedBlackTree<T,C>::checkNode(Node* n, int* bh) const { 8736034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com if (NULL != n) { 874f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(validateChildRelations(n, false)); 8756034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com if (kBlack_Color == n->fColor) { 8766034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com *bh += 1; 8776034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } 878f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(!fComp(n->fItem, fFirst->fItem)); 879f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(!fComp(fLast->fItem, n->fItem)); 8806034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com int leftBh = *bh; 8816034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com int rightBh = *bh; 8826034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com int cl = checkNode(n->fChildren[kLeft_Child], &leftBh); 8836034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com int cr = checkNode(n->fChildren[kRight_Child], &rightBh); 884f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(leftBh == rightBh); 8856034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com *bh = leftBh; 8866034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com return 1 + cl + cr; 8876034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } 8886034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com return 0; 8896034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com} 8906034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com 8916034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.comtemplate <typename T, typename C> 8926034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.combool GrRedBlackTree<T,C>::validateChildRelations(const Node* n, 8936034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com bool allowRedRed) const { 8946034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com if (NULL != n) { 8956034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com if (NULL != n->fChildren[kLeft_Child] || 8966034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com NULL != n->fChildren[kRight_Child]) { 8976034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com if (n->fChildren[kLeft_Child] == n->fChildren[kRight_Child]) { 8986034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com return validateChildRelationsFailed(); 8996034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } 9006034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com if (n->fChildren[kLeft_Child] == n->fParent && 9016034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com NULL != n->fParent) { 9026034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com return validateChildRelationsFailed(); 9036034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } 9046034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com if (n->fChildren[kRight_Child] == n->fParent && 9056034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com NULL != n->fParent) { 9066034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com return validateChildRelationsFailed(); 9076034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } 9086034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com if (NULL != n->fChildren[kLeft_Child]) { 9096034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com if (!allowRedRed && 9106034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com kRed_Color == n->fChildren[kLeft_Child]->fColor && 9116034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com kRed_Color == n->fColor) { 9126034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com return validateChildRelationsFailed(); 9136034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } 9146034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com if (n->fChildren[kLeft_Child]->fParent != n) { 9156034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com return validateChildRelationsFailed(); 9166034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } 9176034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com if (!(fComp(n->fChildren[kLeft_Child]->fItem, n->fItem) || 9186034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com (!fComp(n->fChildren[kLeft_Child]->fItem, n->fItem) && 9196034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com !fComp(n->fItem, n->fChildren[kLeft_Child]->fItem)))) { 9206034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com return validateChildRelationsFailed(); 9216034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } 9226034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } 9236034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com if (NULL != n->fChildren[kRight_Child]) { 9246034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com if (!allowRedRed && 9256034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com kRed_Color == n->fChildren[kRight_Child]->fColor && 9266034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com kRed_Color == n->fColor) { 9276034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com return validateChildRelationsFailed(); 9286034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } 9296034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com if (n->fChildren[kRight_Child]->fParent != n) { 9306034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com return validateChildRelationsFailed(); 9316034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } 9326034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com if (!(fComp(n->fItem, n->fChildren[kRight_Child]->fItem) || 9336034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com (!fComp(n->fChildren[kRight_Child]->fItem, n->fItem) && 9346034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com !fComp(n->fItem, n->fChildren[kRight_Child]->fItem)))) { 9356034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com return validateChildRelationsFailed(); 9366034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } 9376034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } 9386034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } 9396034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } 9406034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com return true; 9416034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com} 9426034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com#endif 9436034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com 944223137f49d1a4e805f5c1b1c20b7fd68719ac54btfarina@chromium.org#include "SkRandom.h" 9456034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com 9466034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.comtemplate <typename T, typename C> 9476034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.comvoid GrRedBlackTree<T,C>::UnitTest() { 9486034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com GrRedBlackTree<int> tree; 9496034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com 950e0e7cfe44bb9d66d76120a79e5275c294bacaa22commit-bot@chromium.org SkRandom r; 9516034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com 9526034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com int count[100] = {0}; 9536034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // add 10K ints 9546034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com for (int i = 0; i < 10000; ++i) { 9556034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com int x = r.nextU()%100; 9560e51577a14f903ffeafa117a75954baeb173ffb9humper@google.com SkDEBUGCODE(Iter xi = ) tree.insert(x); 957f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(*xi == x); 9586034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com ++count[x]; 9596034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } 9606034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com 9616034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com tree.insert(0); 9626034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com ++count[0]; 9636034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com tree.insert(99); 9646034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com ++count[99]; 965f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(*tree.begin() == 0); 966f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(*tree.last() == 99); 967f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(--(++tree.begin()) == tree.begin()); 968f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(--tree.end() == tree.last()); 969f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(tree.count() == 10002); 9706034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com 9716034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com int c = 0; 9726034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // check that we iterate through the correct number of 9736034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // elements and they are properly sorted. 9746034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com for (Iter a = tree.begin(); tree.end() != a; ++a) { 9756034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com Iter b = a; 9766034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com ++b; 9776034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com ++c; 978f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(b == tree.end() || *a <= *b); 9796034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } 980f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(c == tree.count()); 9816034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com 9826034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // check that the tree reports the correct number of each int 9836034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // and that we can iterate through them correctly both forward 9846034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // and backward. 9856034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com for (int i = 0; i < 100; ++i) { 9866034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com int c; 9876034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com c = tree.countOf(i); 988f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(c == count[i]); 9896034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com c = 0; 9906034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com Iter iter = tree.findFirst(i); 9916034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com while (iter != tree.end() && *iter == i) { 9926034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com ++c; 9936034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com ++iter; 9946034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } 995f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(count[i] == c); 9966034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com c = 0; 9976034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com iter = tree.findLast(i); 9986034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com if (iter != tree.end()) { 9996034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com do { 10006034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com if (*iter == i) { 10016034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com ++c; 10026034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } else { 10036034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com break; 10046034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } 10056034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com if (iter != tree.begin()) { 10066034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com --iter; 10076034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } else { 10086034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com break; 10096034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } 10106034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } while (true); 10116034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } 1012f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(c == count[i]); 10136034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } 10146034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // remove all the ints between 25 and 74. Randomly chose to remove 10156034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // the first, last, or any entry for each. 10166034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com for (int i = 25; i < 75; ++i) { 10176034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com while (0 != tree.countOf(i)) { 10186034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com --count[i]; 10196034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com int x = r.nextU() % 3; 10206034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com Iter iter; 10216034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com switch (x) { 10226034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com case 0: 10236034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com iter = tree.findFirst(i); 10246034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com break; 10256034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com case 1: 10266034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com iter = tree.findLast(i); 10276034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com break; 10286034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com case 2: 10296034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com default: 10306034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com iter = tree.find(i); 10316034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com break; 10326034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } 10336034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com tree.remove(iter); 10346034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } 1035f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(0 == count[i]); 1036f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(tree.findFirst(i) == tree.end()); 1037f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(tree.findLast(i) == tree.end()); 1038f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(tree.find(i) == tree.end()); 10396034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } 10406034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // remove all of the 0 entries. (tests removing begin()) 1041f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(*tree.begin() == 0); 1042f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(*(--tree.end()) == 99); 10436034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com while (0 != tree.countOf(0)) { 10446034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com --count[0]; 10456034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com tree.remove(tree.find(0)); 10466034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } 1047f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(0 == count[0]); 1048f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(tree.findFirst(0) == tree.end()); 1049f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(tree.findLast(0) == tree.end()); 1050f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(tree.find(0) == tree.end()); 1051f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(0 < *tree.begin()); 10526034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com 10536034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // remove all the 99 entries (tests removing last()). 10546034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com while (0 != tree.countOf(99)) { 10556034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com --count[99]; 10566034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com tree.remove(tree.find(99)); 10576034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } 1058f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(0 == count[99]); 1059f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(tree.findFirst(99) == tree.end()); 1060f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(tree.findLast(99) == tree.end()); 1061f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(tree.find(99) == tree.end()); 1062f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(99 > *(--tree.end())); 1063f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(tree.last() == --tree.end()); 10646034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com 10656034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // Make sure iteration still goes through correct number of entries 10666034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // and is still sorted correctly. 10676034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com c = 0; 10686034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com for (Iter a = tree.begin(); tree.end() != a; ++a) { 10696034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com Iter b = a; 10706034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com ++b; 10716034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com ++c; 1072f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(b == tree.end() || *a <= *b); 10736034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } 1074f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(c == tree.count()); 10756034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com 10766034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // repeat check that correct number of each entry is in the tree 10776034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // and iterates correctly both forward and backward. 10786034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com for (int i = 0; i < 100; ++i) { 1079f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(tree.countOf(i) == count[i]); 10806034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com int c = 0; 10816034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com Iter iter = tree.findFirst(i); 10826034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com while (iter != tree.end() && *iter == i) { 10836034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com ++c; 10846034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com ++iter; 10856034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } 1086f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(count[i] == c); 10876034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com c = 0; 10886034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com iter = tree.findLast(i); 10896034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com if (iter != tree.end()) { 10906034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com do { 10916034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com if (*iter == i) { 10926034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com ++c; 10936034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } else { 10946034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com break; 10956034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } 10966034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com if (iter != tree.begin()) { 10976034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com --iter; 10986034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } else { 10996034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com break; 11006034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } 11016034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } while (true); 11026034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } 1103f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(count[i] == c); 11046034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } 11056034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com 11066034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // remove all entries 11076034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com while (!tree.empty()) { 11086034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com tree.remove(tree.begin()); 11096034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } 11106034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com 11116034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // test reset on empty tree. 11126034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com tree.reset(); 11136034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com} 11146034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com 11156034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com#endif 1116