Static (immutable) packed R-tree built via Hilbert-curve bulk loading. More...

#include <packed_rtree.h>

Classes
class	Builder
	Builder for constructing a PACKED_RTREE from a set of items. More...

class	Iterator
	Iterator for sequential access to all stored data items. More...

Public Member Functions
	PACKED_RTREE ()=default

	PACKED_RTREE (PACKED_RTREE &&aOther) noexcept

PACKED_RTREE &	operator= (PACKED_RTREE &&aOther) noexcept

	PACKED_RTREE (const PACKED_RTREE &)=delete

PACKED_RTREE &	operator= (const PACKED_RTREE &)=delete

template<class VISITOR>
int	Search (const ELEMTYPE aMin[NUMDIMS], const ELEMTYPE aMax[NUMDIMS], VISITOR &aVisitor) const
	Search for all items whose bounding boxes overlap the query rectangle.

Iterator	begin () const

Iterator	end () const

size_t	size () const

bool	empty () const

size_t	MemoryUsage () const
	Return approximate memory usage in bytes.

Private Member Functions
template<class VISITOR>
bool	searchNode (int aLevel, size_t aNodeIdx, const ELEMTYPE aMin[NUMDIMS], const ELEMTYPE aMax[NUMDIMS], VISITOR &aVisitor, int &aFound) const

bool	childOverlaps (size_t aNodeIdx, int aSlot, const ELEMTYPE aMin[NUMDIMS], const ELEMTYPE aMax[NUMDIMS]) const

Private Attributes
std::vector< ELEMTYPE >	m_bounds [NUMDIMS *2]

std::vector< int >	m_counts

std::vector< DATATYPE >	m_data

std::vector< size_t >	m_levelOffsets

size_t	m_size = 0

Detailed Description

template<class DATATYPE, class ELEMTYPE = int, int NUMDIMS = 2, int FANOUT = 16>
class KIRTREE::PACKED_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, FANOUT >

Static (immutable) packed R-tree built via Hilbert-curve bulk loading.

Provides optimal query performance for build-once-query-many workloads such as DRC spatial indexing. The tree is constructed in O(N log N) time via Hilbert curve sorting and stored in a single contiguous buffer with bottom-up level ordering.

Node bounding boxes use Structure-of-Arrays layout with fanout=FANOUT for cache-efficient scanning during queries.

Thread-safe for concurrent reads after construction.

Template Parameters

DATATYPE	Type of data stored (e.g. pointer to item)
ELEMTYPE	Coordinate element type (typically int)
NUMDIMS	Number of dimensions (2 or 3)
FANOUT	Maximum children per node (default 16 for SIMD alignment)

Definition at line 61 of file packed_rtree.h.

Constructor & Destructor Documentation

◆ PACKED_RTREE() [1/3]

template<class DATATYPE, class ELEMTYPE = int, int NUMDIMS = 2, int FANOUT = 16>

KIRTREE::PACKED_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, FANOUT >::PACKED_RTREE ( )

default

Referenced by KIRTREE::PACKED_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, FANOUT >::Builder::Build().

◆ PACKED_RTREE() [2/3]

template<class DATATYPE, class ELEMTYPE = int, int NUMDIMS = 2, int FANOUT = 16>

KIRTREE::PACKED_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, FANOUT >::PACKED_RTREE ( PACKED_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, FANOUT > && aOther )

inlinenoexcept

Definition at line 67 of file packed_rtree.h.

◆ PACKED_RTREE() [3/3]

template<class DATATYPE, class ELEMTYPE = int, int NUMDIMS = 2, int FANOUT = 16>

KIRTREE::PACKED_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, FANOUT >::PACKED_RTREE ( const PACKED_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, FANOUT > & )

delete

Member Function Documentation

◆ begin()

template<class DATATYPE, class ELEMTYPE = int, int NUMDIMS = 2, int FANOUT = 16>

Iterator KIRTREE::PACKED_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, FANOUT >::begin ( ) const

inline

Definition at line 149 of file packed_rtree.h.

Referenced by BOOST_AUTO_TEST_CASE().

◆ childOverlaps()

template<class DATATYPE, class ELEMTYPE = int, int NUMDIMS = 2, int FANOUT = 16>

bool KIRTREE::PACKED_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, FANOUT >::childOverlaps	(	size_t	aNodeIdx,
		int	aSlot,
		const ELEMTYPE	aMin[NUMDIMS],
		const ELEMTYPE	aMax[NUMDIMS] ) const

inlineprivate

Definition at line 513 of file packed_rtree.h.

Referenced by KIRTREE::PACKED_RTREE< CREEPAGE_TRACK_ENTRY *, int, 2 >::searchNode().

◆ empty()

template<class DATATYPE, class ELEMTYPE = int, int NUMDIMS = 2, int FANOUT = 16>

bool KIRTREE::PACKED_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, FANOUT >::empty ( ) const

inline

Definition at line 153 of file packed_rtree.h.

Referenced by BOOST_AUTO_TEST_CASE().

◆ end()

template<class DATATYPE, class ELEMTYPE = int, int NUMDIMS = 2, int FANOUT = 16>

Iterator KIRTREE::PACKED_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, FANOUT >::end ( ) const

inline

Definition at line 150 of file packed_rtree.h.

Referenced by BOOST_AUTO_TEST_CASE().

◆ MemoryUsage()

template<class DATATYPE, class ELEMTYPE = int, int NUMDIMS = 2, int FANOUT = 16>

size_t KIRTREE::PACKED_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, FANOUT >::MemoryUsage ( ) const

inline

Return approximate memory usage in bytes.

Definition at line 158 of file packed_rtree.h.

Referenced by BOOST_AUTO_TEST_CASE().

◆ operator=() [1/2]

template<class DATATYPE, class ELEMTYPE = int, int NUMDIMS = 2, int FANOUT = 16>

PACKED_RTREE & KIRTREE::PACKED_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, FANOUT >::operator= ( const PACKED_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, FANOUT > & )

delete

◆ operator=() [2/2]

template<class DATATYPE, class ELEMTYPE = int, int NUMDIMS = 2, int FANOUT = 16>

PACKED_RTREE & KIRTREE::PACKED_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, FANOUT >::operator= ( PACKED_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, FANOUT > && aOther )

inlinenoexcept

Definition at line 77 of file packed_rtree.h.

◆ Search()

template<class DATATYPE, class ELEMTYPE = int, int NUMDIMS = 2, int FANOUT = 16>

template<class VISITOR>

int KIRTREE::PACKED_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, FANOUT >::Search	(	const ELEMTYPE	aMin[NUMDIMS],
		const ELEMTYPE	aMax[NUMDIMS],
		VISITOR &	aVisitor ) const

inline

Search for all items whose bounding boxes overlap the query rectangle.

Parameters

aMin	Minimum corner of query rectangle
aMax	Maximum corner of query rectangle
aVisitor	Callback invoked for each matching item. Return false to stop early.

Returns: Number of items reported to visitor

Definition at line 106 of file packed_rtree.h.

Referenced by BOOST_AUTO_TEST_CASE(), BOOST_AUTO_TEST_CASE(), BOOST_AUTO_TEST_CASE(), BOOST_AUTO_TEST_CASE(), and DRC_RTREE::DRC_LAYER::DRC_LAYER().

◆ searchNode()

template<class DATATYPE, class ELEMTYPE = int, int NUMDIMS = 2, int FANOUT = 16>

template<class VISITOR>

bool KIRTREE::PACKED_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, FANOUT >::searchNode	(	int	aLevel,
		size_t	aNodeIdx,
		const ELEMTYPE	aMin[NUMDIMS],
		const ELEMTYPE	aMax[NUMDIMS],
		VISITOR &	aVisitor,
		int &	aFound ) const

inlineprivate

Definition at line 410 of file packed_rtree.h.

Referenced by KIRTREE::PACKED_RTREE< CREEPAGE_TRACK_ENTRY *, int, 2 >::Search(), and KIRTREE::PACKED_RTREE< CREEPAGE_TRACK_ENTRY *, int, 2 >::searchNode().

◆ size()

template<class DATATYPE, class ELEMTYPE = int, int NUMDIMS = 2, int FANOUT = 16>

size_t KIRTREE::PACKED_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, FANOUT >::size ( ) const

inline

Definition at line 152 of file packed_rtree.h.

Referenced by BOOST_AUTO_TEST_CASE(), and BOOST_AUTO_TEST_CASE().

Member Data Documentation

◆ m_bounds

template<class DATATYPE, class ELEMTYPE = int, int NUMDIMS = 2, int FANOUT = 16>

std::vector<ELEMTYPE> KIRTREE::PACKED_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, FANOUT >::m_bounds[NUMDIMS *2]

private

Definition at line 528 of file packed_rtree.h.

Referenced by KIRTREE::PACKED_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, FANOUT >::Builder::Build().

◆ m_counts

template<class DATATYPE, class ELEMTYPE = int, int NUMDIMS = 2, int FANOUT = 16>

std::vector<int> KIRTREE::PACKED_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, FANOUT >::m_counts

private

Definition at line 531 of file packed_rtree.h.

Referenced by KIRTREE::PACKED_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, FANOUT >::Builder::Build().

◆ m_data

template<class DATATYPE, class ELEMTYPE = int, int NUMDIMS = 2, int FANOUT = 16>

std::vector<DATATYPE> KIRTREE::PACKED_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, FANOUT >::m_data

private

Definition at line 534 of file packed_rtree.h.

Referenced by KIRTREE::PACKED_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, FANOUT >::Builder::Build().

◆ m_levelOffsets

template<class DATATYPE, class ELEMTYPE = int, int NUMDIMS = 2, int FANOUT = 16>

std::vector<size_t> KIRTREE::PACKED_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, FANOUT >::m_levelOffsets

private

Definition at line 537 of file packed_rtree.h.

Referenced by KIRTREE::PACKED_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, FANOUT >::Builder::Build().

◆ m_size

template<class DATATYPE, class ELEMTYPE = int, int NUMDIMS = 2, int FANOUT = 16>

size_t KIRTREE::PACKED_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, FANOUT >::m_size = 0

private

Definition at line 540 of file packed_rtree.h.

Referenced by KIRTREE::PACKED_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, FANOUT >::Builder::Build().

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

packed_rtree.h

Classes

Public Member Functions

Private Member Functions

Private Attributes

Detailed Description

Constructor & Destructor Documentation

◆ PACKED_RTREE() [1/3]

◆ PACKED_RTREE() [2/3]

◆ PACKED_RTREE() [3/3]

Member Function Documentation

◆ begin()

◆ childOverlaps()

◆ empty()

◆ end()

◆ MemoryUsage()

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ Search()

◆ searchNode()

◆ size()

Member Data Documentation

◆ m_bounds

◆ m_counts

◆ m_data

◆ m_levelOffsets

◆ m_size