QBspTree Class Reference

#include <qbsptree_p.h>

Classes
struct	Data
struct	Node

Public Types
typedef void	callback(QVector< int > &leaf, const QRect &area, uint visited, QBspTreeData data)
typedef Node::Type	NodeType
typedef QBspTree::Data	QBspTreeData

Public Functions
void	climbTree (const QRect &rect, callback *function, QBspTreeData data)
void	create (int n, int d=-1)
void	destroy ()
void	init (const QRect &area, NodeType type)
void	insertLeaf (const QRect &r, int i)
QVector< int > &	leaf (int i)
int	leafCount () const
	QBspTree ()
void	removeLeaf (const QRect &r, int i)

Protected Functions
void	climbTree (const QRect &rect, callback *function, QBspTreeData data, int index)
int	firstChildIndex (int i) const
void	init (const QRect &area, int depth, NodeType type, int index)
int	parentIndex (int i) const

Static Protected Functions
static void	insert (QVector< int > &leaf, const QRect &area, uint visited, QBspTreeData data)
static void	remove (QVector< int > &leaf, const QRect &area, uint visited, QBspTreeData data)

Properties
uint	depth
QVector< QVector< int > >	leaves
QVector< Node >	nodes
uint	visited

Detailed Description

Definition at line 61 of file qbsptree_p.h.

Typedefs

callback

typedef void QBspTree::callback(QVector< int > &leaf, const QRect &area, uint visited, QBspTreeData data)

Definition at line 84 of file qbsptree_p.h.

NodeType

typedef Node::Type QBspTree::NodeType

Definition at line 72 of file qbsptree_p.h.

QBspTreeData

typedef QBspTree::Data QBspTree::QBspTreeData

Definition at line 83 of file qbsptree_p.h.

Constructors and Destructors

QBspTree()

QBspTree::QBspTree

(

)

Definition at line 46 of file qbsptree.cpp.

: depth(6), visited(0) {}

Functions

climbTree() [1/2]

void QBspTree::climbTree	(	const QRect &	rect,
		callback *	function,
		QBspTreeData	data
	)

Definition at line 71 of file qbsptree.cpp.

Referenced by climbTree(), init(), insertLeaf(), QIconModeViewBase::intersectingSet(), and removeLeaf().

{
    if (nodes.isEmpty())
        return;
    ++visited;
    climbTree(rect, function, data, 0);
}

climbTree() [2/2]

void QBspTree::climbTree ( const QRect &  rect, callback *  function, QBspTreeData  data, int  index  )

protected

Definition at line 79 of file qbsptree.cpp.

{
    if (index >= nodes.count()) { // the index points to a leaf
        Q_ASSERT(!nodes.isEmpty());
        function(leaf(index - nodes.count()), area, visited, data);
        return;
    }

    Node::Type t = (Node::Type) nodes.at(index).type;

    int pos = nodes.at(index).pos;
    int idx = firstChildIndex(index);
    if (t == Node::VerticalPlane) {
        if (area.left() < pos)
            climbTree(area, function, data, idx); // back
        if (area.right() >= pos)
            climbTree(area, function, data, idx + 1); // front
    } else {
        if (area.top() < pos)
            climbTree(area, function, data, idx); // back
        if (area.bottom() >= pos)
            climbTree(area, function, data, idx + 1); // front
    }
}

create()

void QBspTree::create	(	int	n,
		int	d = -1
	)

Definition at line 48 of file qbsptree.cpp.

{
    // simple heuristics to find the best tree depth
    if (d == -1) {
        int c;
        for (c = 0; n; ++c)
            n = n / 10;
        depth = c << 1;
    } else {
        depth = d;
    }
    depth = qMax(depth, uint(1));

    nodes.resize((1 << depth) - 1); // resize to number of nodes
    leaves.resize(1 << depth); // resize to number of leaves
}

destroy()

void QBspTree::destroy

(

)

Definition at line 65 of file qbsptree.cpp.

{
    leaves.clear();
    nodes.clear();
}

firstChildIndex()

int QBspTree::firstChildIndex ( int  i ) const

inlineprotected

Definition at line 105 of file qbsptree_p.h.

Referenced by climbTree(), and init().

{ return ((i * 2) + 1); }

init() [1/2]

void QBspTree::init ( const QRect &  area, NodeType  type  )

inline

Definition at line 91 of file qbsptree_p.h.

Referenced by init(), and removeLeaf().

{ init(area, depth, type, 0); }

init() [2/2]

void QBspTree::init ( const QRect &  area, int  depth, NodeType  type, int  index  )

protected

Definition at line 104 of file qbsptree.cpp.

{
    Node::Type t = Node::None; // t should never have this value
    if (type == Node::Both) // if both planes are specified, use 2d bsp
        t = (depth & 1) ? Node::HorizontalPlane : Node::VerticalPlane;
    else
        t = type;
    QPoint center = area.center();
    nodes[index].pos = (t == Node::VerticalPlane ? center.x() : center.y());
    nodes[index].type = t;

    QRect front = area;
    QRect back = area;

    if (t == Node::VerticalPlane) {
        front.setLeft(center.x());
        back.setRight(center.x() - 1); // front includes the center
    } else { // t == Node::HorizontalPlane
        front.setTop(center.y());
        back.setBottom(center.y() - 1);
    }

    int idx = firstChildIndex(index);
    if (--depth) {
        init(back, depth, type, idx);
        init(front, depth, type, idx + 1);
    }
}

insert()

void QBspTree::insert ( QVector< int > &  leaf, const QRect &  area, uint  visited, QBspTreeData  data  )

staticprotected

Definition at line 133 of file qbsptree.cpp.

Referenced by firstChildIndex(), and insertLeaf().

{
    leaf.append(data.i);
}

insertLeaf()

void QBspTree::insertLeaf ( const QRect &  r, int  i  )

inline

Definition at line 97 of file qbsptree_p.h.

{ climbTree(r, &insert, i, 0); }

leaf()

QVector<int>& QBspTree::leaf ( int  i )

inline

Definition at line 96 of file qbsptree_p.h.

Referenced by climbTree(), and firstChildIndex().

{ return leaves[i]; }

leafCount()

int QBspTree::leafCount ( ) const

inline

Definition at line 95 of file qbsptree_p.h.

{ return leaves.count(); }

parentIndex()

int QBspTree::parentIndex ( int  i ) const

inlineprotected

Definition at line 104 of file qbsptree_p.h.

{ return (i & 1) ? ((i - 1) / 2) : ((i - 2) / 2); }

remove()

void QBspTree::remove ( QVector< int > &  leaf, const QRect &  area, uint  visited, QBspTreeData  data  )

staticprotected

Definition at line 138 of file qbsptree.cpp.

{
    int i = leaf.indexOf(data.i);
    if (i != -1)
        leaf.remove(i);
}

removeLeaf()

void QBspTree::removeLeaf ( const QRect &  r, int  i  )

inline

Definition at line 98 of file qbsptree_p.h.

{ climbTree(r, &remove, i, 0); }

Properties

depth

uint QBspTree::depth

private

Definition at line 111 of file qbsptree_p.h.

Referenced by create(), init(), and removeLeaf().

leaves

QVector< QVector<int> > QBspTree::leaves

mutableprivate

Definition at line 114 of file qbsptree_p.h.

Referenced by create(), destroy(), leaf(), and leafCount().

nodes

QVector<Node> QBspTree::nodes

private

Definition at line 113 of file qbsptree_p.h.

Referenced by climbTree(), create(), destroy(), and init().

visited

uint QBspTree::visited

mutableprivate

Definition at line 112 of file qbsptree_p.h.

Referenced by climbTree(), and firstChildIndex().

---

The documentation for this class was generated from the following files:

• /src/gui/itemviews/qbsptree_p.h
• /src/gui/itemviews/qbsptree.cpp