FLQTree Class Reference

The FLQTree class provides a quadtree that uses an efficient linear scheme to store data and avoid many pointers indirection, overhead, and memory cost. More...

Public Member Functions
	FLQTree ()
	FLQTree (const tSelf &)=delete
	~FLQTree ()
void	Clear ()
void	Erase (uint16 iX, uint16 iY)
bool	IsEmpty () const
FRectI	LeafGeometry () const
tSelf &	operator= (const tSelf &)=delete
const uint8 *	QueryConst (FTilePool &iPool, uint8 iX, uint8 iY) const
FTile **	QueryMutable (FTilePool &iPool, uint8 iX, uint8 iY)
void	SanitizeNow (FTilePool &iPool)

Public Attributes
uint8	mNumEntries

Static Public Attributes
static constexpr uint16	sm_leaf_size_as_pixels = FMath::ContexprPow( 2, sm_leaf_threshold )
static constexpr uint8	sm_leaf_threshold = 6
static constexpr uint32	sm_num_leafs = sm_root_size_as_leafs * sm_root_size_as_leafs
static constexpr uint16	sm_root_size_as_leafs = FMath::ContexprPow( 2, sm_root_threshold )
static constexpr uint32	sm_root_size_as_pixels = sm_leaf_size_as_pixels * sm_root_size_as_leafs
static constexpr uint8	sm_root_threshold = 4

Detailed Description

A linear quadtree is a typical way to optimize a quadtree and guarantee constant time access to leafs and neighbours. It also allows to remove the actual memory cost of a pointer based structure, and access to leafs elements is computed from a simple formula. See: morton codes, space filling curve Z-order curve.

Deep copy and Shallow copy are explicitely forbidden.

Leaf entries are simply called attributes associated with a leaf type code, the corresponding attribute value is searched in an attribute array associated with the leaf type. Attribute arrays are TArrays with a reserved size that is a multiple of the maximum depth at wich one or more leaf exist, and cannot exceed the maximum number of max depth leafs.

Constructor & Destructor Documentation

~FLQTree()

FLQTree::~FLQTree

(

)

Destructor, cleanup bulk and attributes.

FLQTree() [1/2]

FLQTree::FLQTree

(

)

Constructor, initialize empty quadtree structure.

FLQTree() [2/2]

FLQTree::FLQTree ( const tSelf &  )

delete

Explicitely deleted copy constructor

Member Function Documentation

Clear()

void FLQTree::Clear

(

)

Clear all of this QTree

Erase()

void FLQTree::Erase	(	uint16	iX,
		uint16	iY
	)

Erase tile at pixel coordinates

IsEmpty()

bool FLQTree::IsEmpty

(

)

const

Check if the LQT is empty, might be deleted if so.

LeafGeometry()

FRectI FLQTree::LeafGeometry

(

)

const

Rough leaf geometry in local QTree referential as pixel sizes

operator=()

tSelf& FLQTree::operator= ( const tSelf &  )

delete

Explicitely deleted copy assignment operator

QueryConst()

const uint8* FLQTree::QueryConst	(	FTilePool &	iPool,
		uint8	iX,
		uint8	iY
	)		const

Query const client data at pixel coordinates ( Read-only )

QueryMutable()

FTile** FLQTree::QueryMutable	(	FTilePool &	iPool,
		uint8	iX,
		uint8	iY
	)

Query one mutable tile element for imminent dirty operation at pixel coordinates

SanitizeNow()

void FLQTree::SanitizeNow

(

FTilePool &

iPool

)

Sanitize.

Member Data Documentation

mNumEntries

uint8 FLQTree::mNumEntries

sm_leaf_size_as_pixels

constexpr uint16 FLQTree::sm_leaf_size_as_pixels = FMath::ContexprPow( 2, sm_leaf_threshold )

staticconstexpr

sm_leaf_threshold

constexpr uint8 FLQTree::sm_leaf_threshold = 6

staticconstexpr

sm_num_leafs

constexpr uint32 FLQTree::sm_num_leafs = sm_root_size_as_leafs * sm_root_size_as_leafs

staticconstexpr

sm_root_size_as_leafs

constexpr uint16 FLQTree::sm_root_size_as_leafs = FMath::ContexprPow( 2, sm_root_threshold )

staticconstexpr

sm_root_size_as_pixels

constexpr uint32 FLQTree::sm_root_size_as_pixels = sm_leaf_size_as_pixels * sm_root_size_as_leafs

staticconstexpr

sm_root_threshold

constexpr uint8 FLQTree::sm_root_threshold = 4

staticconstexpr