QRBTree< T > Struct Template Reference

Classes
struct	Node

Public Functions
void	attachAfter (Node *parent, Node *child)
void	attachBefore (Node *parent, Node *child)
Node *	back (Node *node) const
void	clear ()
void	deleteNode (Node *&node)
Node *	front (Node *node) const
Node *	newNode ()
Node *	next (Node *node) const
int	order (Node *left, Node *right)
Node *	previous (Node *node) const
	QRBTree ()
bool	validate () const
	~QRBTree ()

Public Variables
Node *	root

Private Functions
void	attachLeft (Node *parent, Node *child)
void	attachRight (Node *parent, Node *child)
int	blackDepth (Node *top) const
bool	checkRedBlackProperty (Node *top) const
void	detach (Node *node)
void	rebalance (Node *node)
void	rotateLeft (Node *node)
void	rotateRight (Node *node)
void	swapNodes (Node *n1, Node *n2)
void	update (Node *node)

Properties
Node *	freeList

Detailed Description

template<class T>
struct QRBTree< T >

Definition at line 595 of file qtriangulator.cpp.

Constructors and Destructors

QRBTree()

template<class T>

QRBTree< T >::QRBTree ( )

inline

Definition at line 608 of file qtriangulator.cpp.

: root(0), freeList(0) { }

~QRBTree()

template<class T >

QRBTree< T >::~QRBTree ( )

inline

Definition at line 653 of file qtriangulator.cpp.

{
    clear();
    while (freeList) {
        // Avoid recursively calling the destructor, as this list may become large.
        Node *next = freeList->right;
        freeList->right = 0;
        delete freeList;
        freeList = next;
    }
}

Functions

attachAfter()

template<class T >

void QRBTree< T >::attachAfter	(	Node *	parent,
		Node *	child
	)

Definition at line 820 of file qtriangulator.cpp.

{
    if (!root)
        update(root = child);
    else if (!parent)
        attachLeft(front(root), child);
    else if (parent->right)
        attachLeft(front(parent->right), child);
    else
        attachRight(parent, child);
}

attachBefore()

template<class T >

void QRBTree< T >::attachBefore	(	Node *	parent,
		Node *	child
	)

Definition at line 807 of file qtriangulator.cpp.

{
    if (!root)
        update(root = child);
    else if (!parent)
        attachRight(back(root), child);
    else if (parent->left)
        attachRight(back(parent->left), child);
    else
        attachLeft(parent, child);
}

attachLeft()

template<class T >

void QRBTree< T >::attachLeft ( Node *  parent, Node *  child  )

inlineprivate

Definition at line 789 of file qtriangulator.cpp.

{
    Q_ASSERT(!parent->left);
    parent->left = child;
    child->parent = parent;
    update(child);
}

attachRight()

template<class T >

void QRBTree< T >::attachRight ( Node *  parent, Node *  child  )

inlineprivate

Definition at line 798 of file qtriangulator.cpp.

{
    Q_ASSERT(!parent->right);
    parent->right = child;
    child->parent = parent;
    update(child);
}

back()

template<class T >

QRBTree< T >::Node * QRBTree< T >::back ( Node *  node ) const

inline

Definition at line 986 of file qtriangulator.cpp.

{
    while (node->right)
        node = node->right;
    return node;
}

blackDepth()

template<class T >

int QRBTree< T >::blackDepth ( Node *  top ) const

private

Definition at line 1014 of file qtriangulator.cpp.

{
    if (!top)
        return 0;
    int leftDepth = blackDepth(top->left);
    int rightDepth = blackDepth(top->right);
    if (leftDepth != rightDepth)
        return -1;
    if (!top->red)
        ++leftDepth;
    return leftDepth;
}

checkRedBlackProperty()

template<class T >

bool QRBTree< T >::checkRedBlackProperty ( Node *  top ) const

private

Definition at line 1028 of file qtriangulator.cpp.

{
    if (!top)
        return true;
    if (top->left && !checkRedBlackProperty(top->left))
        return false;
    if (top->right && !checkRedBlackProperty(top->right))
        return false;
    return !(top->red && ((top->left && top->left->red) || (top->right && top->right->red)));
}

clear()

template<class T >

void QRBTree< T >::clear ( )

inline

Definition at line 666 of file qtriangulator.cpp.

{
    if (root)
        delete root;
    root = 0;
}

deleteNode()

template<class T >

void QRBTree< T >::deleteNode ( Node *&  node )

inline

Definition at line 1046 of file qtriangulator.cpp.

{
    Q_ASSERT(node);
    detach(node);
    node->right = freeList;
    freeList = node;
    node = 0;
}

detach()

template<class T >

void QRBTree< T >::detach ( Node *  node )

private

Definition at line 880 of file qtriangulator.cpp.

{
    if (node->right)
        swapNodes(node, front(node->right));

    Node *child = (node->left ? node->left : node->right);

    if (!node->red) {
        if (child && child->red)
            child->red = false;
        else
            rebalance(node);
    }

    Node *&ref = (node->parent ? (node == node->parent->left ? node->parent->left : node->parent->right) : root);
    ref = child;
    if (child)
        child->parent = node->parent;
    node->left = node->right = node->parent = 0;
}

front()

template<class T >

QRBTree< T >::Node * QRBTree< T >::front ( Node *  node ) const

inline

Definition at line 978 of file qtriangulator.cpp.

Referenced by QTriangulator< T >::ComplexToSimple::Event::operator<().

{
    while (node->left)
        node = node->left;
    return node;
}

newNode()

template<class T >

QRBTree< T >::Node * QRBTree< T >::newNode ( )

inline

Definition at line 1056 of file qtriangulator.cpp.

Referenced by QTriangulator< T >::ComplexToSimple::calculateIntersections(), QTriangulator< T >::SimpleToMonotone::monotoneDecomposition(), and QTriangulator< T >::ComplexToSimple::removeUnwantedEdgesAndConnect().

{
    if (freeList) {
        Node *node = freeList;
        freeList = freeList->right;
        node->parent = node->left = node->right = 0;
        node->red = true;
        return node;
    }
    return new Node;
}

next()

template<class T >

QRBTree< T >::Node * QRBTree< T >::next

(

Node *

node

)

const

Definition at line 994 of file qtriangulator.cpp.

Referenced by QTriangulator< T >::ComplexToSimple::Event::operator<(), QTriangulator< T >::ComplexToSimple::removeUnwantedEdgesAndConnect(), QTriangulator< T >::ComplexToSimple::reorderEdgeListRange(), QTriangulator< T >::ComplexToSimple::searchEdgeLeftOf(), QTriangulator< T >::ComplexToSimple::sortEdgeList(), and QTriangulator< T >::ComplexToSimple::splitEdgeListRange().

{
    if (node->right)
        return front(node->right);
    while (node->parent && node == node->parent->right)
        node = node->parent;
    return node->parent;
}

order()

template<class T >

int QRBTree< T >::order	(	Node *	left,
		Node *	right
	)

Definition at line 1071 of file qtriangulator.cpp.

{
    Q_ASSERT(left && right);
    if (left == right)
        return 0;

    QVector<Node *> leftAncestors;
    QVector<Node *> rightAncestors;
    while (left) {
        leftAncestors.push_back(left);
        left = left->parent;
    }
    while (right) {
        rightAncestors.push_back(right);
        right = right->parent;
    }
    Q_ASSERT(leftAncestors.back() == root && rightAncestors.back() == root);

    while (!leftAncestors.empty() && !rightAncestors.empty() && leftAncestors.back() == rightAncestors.back()) {
        leftAncestors.pop_back();
        rightAncestors.pop_back();
    }

    if (!leftAncestors.empty())
        return (leftAncestors.back() == leftAncestors.back()->parent->left ? -1 : 1);

    if (!rightAncestors.empty())
        return (rightAncestors.back() == rightAncestors.back()->parent->right ? -1 : 1);

    // The code should never reach this point.
    Q_ASSERT(!leftAncestors.empty() || !rightAncestors.empty());
    return 0;
}

previous()

template<class T >

QRBTree< T >::Node * QRBTree< T >::previous

(

Node *

node

)

const

Definition at line 1004 of file qtriangulator.cpp.

Referenced by QTriangulator< T >::ComplexToSimple::removeUnwantedEdgesAndConnect(), QTriangulator< T >::ComplexToSimple::reorderEdgeListRange(), and QTriangulator< T >::ComplexToSimple::sortEdgeList().

{
    if (node->left)
        return back(node->left);
    while (node->parent && node == node->parent->left)
        node = node->parent;
    return node->parent;
}

rebalance()

template<class T >

void QRBTree< T >::rebalance ( Node *  node )

private

Definition at line 903 of file qtriangulator.cpp.

{
    Q_ASSERT(!node->red);
    for (;;) {
        if (!node->parent)
            return;

        // at this point, node is not a parent, it is black, thus it must have a sibling.
        Node *sibling = (node == node->parent->left ? node->parent->right : node->parent->left);
        Q_ASSERT(sibling);

        if (sibling->red) {
            sibling->red = false;
            node->parent->red = true;
            if (node == node->parent->left)
                rotateLeft(node->parent);
            else
                rotateRight(node->parent);
            sibling = (node == node->parent->left ? node->parent->right : node->parent->left);
            Q_ASSERT(sibling);
        }

        // at this point, the sibling is black.
        Q_ASSERT(!sibling->red);

        if ((!sibling->left || !sibling->left->red) && (!sibling->right || !sibling->right->red)) {
            bool parentWasRed = node->parent->red;
            sibling->red = true;
            node->parent->red = false;
            if (parentWasRed)
                return;
            node = node->parent;
            continue;
        }

        // at this point, at least one of the sibling's children is red.

        if (node == node->parent->left) {
            if (!sibling->right || !sibling->right->red) {
                Q_ASSERT(sibling->left);
                sibling->red = true;
                sibling->left->red = false;
                rotateRight(sibling);

                sibling = sibling->parent;
                Q_ASSERT(sibling);
            }
            sibling->red = node->parent->red;
            node->parent->red = false;

            Q_ASSERT(sibling->right->red);
            sibling->right->red = false;
            rotateLeft(node->parent);
        } else {
            if (!sibling->left || !sibling->left->red) {
                Q_ASSERT(sibling->right);
                sibling->red = true;
                sibling->right->red = false;
                rotateLeft(sibling);

                sibling = sibling->parent;
                Q_ASSERT(sibling);
            }
            sibling->red = node->parent->red;
            node->parent->red = false;

            Q_ASSERT(sibling->left->red);
            sibling->left->red = false;
            rotateRight(node->parent);
        }
        return;
    }
}

rotateLeft()

template<class T >

void QRBTree< T >::rotateLeft ( Node *  node )

private

Definition at line 674 of file qtriangulator.cpp.

{
    //   |            |      //
    //   N            B      //
    //  / \          / \     //
    // A   B  --->  N   D    //
    //    / \      / \       //
    //   C   D    A   C      //

    Node *&ref = (node->parent ? (node == node->parent->left ? node->parent->left : node->parent->right) : root);
    ref = node->right;
    node->right->parent = node->parent;

    //   :        //
    //   N        //
    //  / :|      //
    // A   B      //
    //    / \     //
    //   C   D    //

    node->right = ref->left;
    if (ref->left)
        ref->left->parent = node;

    //   :   |     //
    //   N   B     //
    //  / \ : \    //
    // A   C   D   //

    ref->left = node;
    node->parent = ref;

    //     |       //
    //     B       //
    //    / \      //
    //   N   D     //
    //  / \        //
    // A   C       //
}

rotateRight()

template<class T >

void QRBTree< T >::rotateRight ( Node *  node )

private

Definition at line 715 of file qtriangulator.cpp.

{
    //     |            |        //
    //     N            A        //
    //    / \          / \       //
    //   A   B  --->  C   N      //
    //  / \              / \     //
    // C   D            D   B    //

    Node *&ref = (node->parent ? (node == node->parent->left ? node->parent->left : node->parent->right) : root);
    ref = node->left;
    node->left->parent = node->parent;

    node->left = ref->right;
    if (ref->right)
        ref->right->parent = node;

    ref->right = node;
    node->parent = ref;
}

swapNodes()

template<class T >

void QRBTree< T >::swapNodes ( Node *  n1, Node *  n2  )

private

Definition at line 833 of file qtriangulator.cpp.

{
    // Since iterators must not be invalidated, it is not sufficient to only swap the data.
    if (n1->parent == n2) {
        n1->parent = n2->parent;
        n2->parent = n1;
    } else if (n2->parent == n1) {
        n2->parent = n1->parent;
        n1->parent = n2;
    } else {
        qSwap(n1->parent, n2->parent);
    }

    qSwap(n1->left, n2->left);
    qSwap(n1->right, n2->right);
    qSwap(n1->red, n2->red);

    if (n1->parent) {
        if (n1->parent->left == n2)
            n1->parent->left = n1;
        else
            n1->parent->right = n1;
    } else {
        root = n1;
    }

    if (n2->parent) {
        if (n2->parent->left == n1)
            n2->parent->left = n2;
        else
            n2->parent->right = n2;
    } else {
        root = n2;
    }

    if (n1->left)
        n1->left->parent = n1;
    if (n1->right)
        n1->right->parent = n1;

    if (n2->left)
        n2->left->parent = n2;
    if (n2->right)
        n2->right->parent = n2;
}

update()

template<class T >

void QRBTree< T >::update ( Node *  node )

private

Definition at line 737 of file qtriangulator.cpp.

{
    for (;;) {
        Node *parent = node->parent;

        // if the node is the root, color it black
        if (!parent) {
            node->red = false;
            return;
        }

        // if the parent is black, the node can be left red
        if (!parent->red)
            return;

        // at this point, the parent is red and cannot be the root
        Node *grandpa = parent->parent;
        Q_ASSERT(grandpa);

        Node *uncle = (parent == grandpa->left ? grandpa->right : grandpa->left);
        if (uncle && uncle->red) {
            // grandpa's black, parent and uncle are red.
            // let parent and uncle be black, grandpa red and recursively update grandpa.
            Q_ASSERT(!grandpa->red);
            parent->red = false;
            uncle->red = false;
            grandpa->red = true;
            node = grandpa;
            continue;
        }

        // at this point, uncle is black
        if (node == parent->right && parent == grandpa->left)
            rotateLeft(node = parent);
        else if (node == parent->left && parent == grandpa->right)
            rotateRight(node = parent);
        parent = node->parent;

        if (parent == grandpa->left) {
            rotateRight(grandpa);
            parent->red = false;
            grandpa->red = true;
        } else {
            rotateLeft(grandpa);
            parent->red = false;
            grandpa->red = true;
        }
        return;
    }
}

validate()

template<class T >

bool QRBTree< T >::validate ( ) const

inline

Definition at line 1040 of file qtriangulator.cpp.

{
    return checkRedBlackProperty(root) && blackDepth(root) != -1;
}

Properties

freeList

template<class T>

Node* QRBTree< T >::freeList

private

Definition at line 649 of file qtriangulator.cpp.

root

template<class T>

Node* QRBTree< T >::root

Definition at line 647 of file qtriangulator.cpp.

Referenced by QTriangulator< T >::ComplexToSimple::bounds(), QTriangulator< T >::ComplexToSimple::outerBounds(), QTriangulator< T >::ComplexToSimple::searchEdgeLeftOf(), QTriangulator< T >::SimpleToMonotone::searchEdgeLeftOfEdge(), and QTriangulator< T >::SimpleToMonotone::searchEdgeLeftOfPoint().

---

The documentation for this struct was generated from the following file:

• /src/opengl/gl2paintengineex/qtriangulator.cpp