/*
* Copyright 2011 Google Inc.
*
* Use of this source code is governed by a BSD-style license that can be
* found in the LICENSE file.
*/
#ifndef GrRedBlackTree_DEFINED
#define GrRedBlackTree_DEFINED
#include "GrConfig.h"
#include "SkTypes.h"
template <typename T>
class GrLess {
public:
bool operator()(const T& a, const T& b) const { return a < b; }
};
template <typename T>
class GrLess<T*> {
public:
bool operator()(const T* a, const T* b) const { return *a < *b; }
};
class GrStrLess {
public:
bool operator()(const char* a, const char* b) const { return strcmp(a,b) < 0; }
};
/**
* In debug build this will cause full traversals of the tree when the validate
* is called on insert and remove. Useful for debugging but very slow.
*/
#define DEEP_VALIDATE 0
/**
* A sorted tree that uses the red-black tree algorithm. Allows duplicate
* entries. Data is of type T and is compared using functor C. A single C object
* will be created and used for all comparisons.
*/
template <typename T, typename C = GrLess<T> >
class GrRedBlackTree : SkNoncopyable {
public:
/**
* Creates an empty tree.
*/
GrRedBlackTree();
virtual ~GrRedBlackTree();
/**
* Class used to iterater through the tree. The valid range of the tree
* is given by [begin(), end()). It is legal to dereference begin() but not
* end(). The iterator has preincrement and predecrement operators, it is
* legal to decerement end() if the tree is not empty to get the last
* element. However, a last() helper is provided.
*/
class Iter;
/**
* Add an element to the tree. Duplicates are allowed.
* @param t the item to add.
* @return an iterator to the item.
*/
Iter insert(const T& t);
/**
* Removes all items in the tree.
*/
void reset();
/**
* @return true if there are no items in the tree, false otherwise.
*/
bool empty() const {return 0 == fCount;}
/**
* @return the number of items in the tree.
*/
int count() const {return fCount;}
/**
* @return an iterator to the first item in sorted order, or end() if empty
*/
Iter begin();
/**
* Gets the last valid iterator. This is always valid, even on an empty.
* However, it can never be dereferenced. Useful as a loop terminator.
* @return an iterator that is just beyond the last item in sorted order.
*/
Iter end();
/**
* @return an iterator that to the last item in sorted order, or end() if
* empty.
*/
Iter last();
/**
* Finds an occurrence of an item.
* @param t the item to find.
* @return an iterator to a tree element equal to t or end() if none exists.
*/
Iter find(const T& t);
/**
* Finds the first of an item in iterator order.
* @param t the item to find.
* @return an iterator to the first element equal to t or end() if
* none exists.
*/
Iter findFirst(const T& t);
/**
* Finds the last of an item in iterator order.
* @param t the item to find.
* @return an iterator to the last element equal to t or end() if
* none exists.
*/
Iter findLast(const T& t);
/**
* Gets the number of items in the tree equal to t.
* @param t the item to count.
* @return number of items equal to t in the tree
*/
int countOf(const T& t) const;
/**
* Removes the item indicated by an iterator. The iterator will not be valid
* afterwards.
*
* @param iter iterator of item to remove. Must be valid (not end()).
*/
void remove(const Iter& iter) { deleteAtNode(iter.fN); }
private:
enum Color {
kRed_Color,
kBlack_Color
};
enum Child {
kLeft_Child = 0,
kRight_Child = 1
};
struct Node {
T fItem;
Color fColor;
Node* fParent;
Node* fChildren[2];
};
void rotateRight(Node* n);
void rotateLeft(Node* n);
static Node* SuccessorNode(Node* x);
static Node* PredecessorNode(Node* x);
void deleteAtNode(Node* x);
static void RecursiveDelete(Node* x);
int onCountOf(const Node* n, const T& t) const;
#ifdef SK_DEBUG
void validate() const;
int checkNode(Node* n, int* blackHeight) const;
// checks relationship between a node and its children. allowRedRed means
// node may be in an intermediate state where a red parent has a red child.
bool validateChildRelations(const Node* n, bool allowRedRed) const;
// place to stick break point if validateChildRelations is failing.
bool validateChildRelationsFailed() const { return false; }
#else
void validate() const {}
#endif
int fCount;
Node* fRoot;
Node* fFirst;
Node* fLast;
const C fComp;
};
template <typename T, typename C>
class GrRedBlackTree<T,C>::Iter {
public:
Iter() {};
Iter(const Iter& i) {fN = i.fN; fTree = i.fTree;}
Iter& operator =(const Iter& i) {
fN = i.fN;
fTree = i.fTree;
return *this;
}
// altering the sort value of the item using this method will cause
// errors.
T& operator *() const { return fN->fItem; }
bool operator ==(const Iter& i) const {
return fN == i.fN && fTree == i.fTree;
}
bool operator !=(const Iter& i) const { return !(*this == i); }
Iter& operator ++() {
SkASSERT(*this != fTree->end());
fN = SuccessorNode(fN);
return *this;
}
Iter& operator --() {
SkASSERT(*this != fTree->begin());
if (NULL != fN) {
fN = PredecessorNode(fN);
} else {
*this = fTree->last();
}
return *this;
}
private:
friend class GrRedBlackTree;
explicit Iter(Node* n, GrRedBlackTree* tree) {
fN = n;
fTree = tree;
}
Node* fN;
GrRedBlackTree* fTree;
};
template <typename T, typename C>
GrRedBlackTree<T,C>::GrRedBlackTree() : fComp() {
fRoot = NULL;
fFirst = NULL;
fLast = NULL;
fCount = 0;
validate();
}
template <typename T, typename C>
GrRedBlackTree<T,C>::~GrRedBlackTree() {
RecursiveDelete(fRoot);
}
template <typename T, typename C>
typename GrRedBlackTree<T,C>::Iter GrRedBlackTree<T,C>::begin() {
return Iter(fFirst, this);
}
template <typename T, typename C>
typename GrRedBlackTree<T,C>::Iter GrRedBlackTree<T,C>::end() {
return Iter(NULL, this);
}
template <typename T, typename C>
typename GrRedBlackTree<T,C>::Iter GrRedBlackTree<T,C>::last() {
return Iter(fLast, this);
}
template <typename T, typename C>
typename GrRedBlackTree<T,C>::Iter GrRedBlackTree<T,C>::find(const T& t) {
Node* n = fRoot;
while (NULL != n) {
if (fComp(t, n->fItem)) {
n = n->fChildren[kLeft_Child];
} else {
if (!fComp(n->fItem, t)) {
return Iter(n, this);
}
n = n->fChildren[kRight_Child];
}
}
return end();
}
template <typename T, typename C>
typename GrRedBlackTree<T,C>::Iter GrRedBlackTree<T,C>::findFirst(const T& t) {
Node* n = fRoot;
Node* leftMost = NULL;
while (NULL != n) {
if (fComp(t, n->fItem)) {
n = n->fChildren[kLeft_Child];
} else {
if (!fComp(n->fItem, t)) {
// found one. check if another in left subtree.
leftMost = n;
n = n->fChildren[kLeft_Child];
} else {
n = n->fChildren[kRight_Child];
}
}
}
return Iter(leftMost, this);
}
template <typename T, typename C>
typename GrRedBlackTree<T,C>::Iter GrRedBlackTree<T,C>::findLast(const T& t) {
Node* n = fRoot;
Node* rightMost = NULL;
while (NULL != n) {
if (fComp(t, n->fItem)) {
n = n->fChildren[kLeft_Child];
} else {
if (!fComp(n->fItem, t)) {
