KiCad PCB EDA Suite
Loading...
Searching...
No Matches
Functions
test_dynamic_rtree.cpp File Reference
#include <qa_utils/wx_utils/unit_test_utils.h>
#include <geometry/rtree/dynamic_rtree.h>
#include <geometry/rtree/dynamic_rtree_cow.h>
#include <algorithm>
#include <random>
#include <set>
#include <vector>

Go to the source code of this file.

Functions

 BOOST_AUTO_TEST_CASE (EmptyTree)
 
 BOOST_AUTO_TEST_CASE (SingleInsert)
 
 BOOST_AUTO_TEST_CASE (BulkInsert1K)
 
 BOOST_AUTO_TEST_CASE (RemoveExisting)
 
 BOOST_AUTO_TEST_CASE (RemoveNonExistent)
 
 BOOST_AUTO_TEST_CASE (SearchOverlapDisjointAll)
 
 BOOST_AUTO_TEST_CASE (BulkInsertAndBruteForce)
 
 BOOST_AUTO_TEST_CASE (RemoveAndVerify)
 
 BOOST_AUTO_TEST_CASE (MoveSemantics)
 
 BOOST_AUTO_TEST_CASE (RemoveAll)
 
 BOOST_AUTO_TEST_CASE (ThreeDimensional)
 
 BOOST_AUTO_TEST_CASE (NearestNeighbors)
 
 BOOST_AUTO_TEST_CASE (IteratorFullCoverage)
 
 BOOST_AUTO_TEST_CASE (EarlyTermination)
 
 BOOST_AUTO_TEST_CASE (RemoveMovedItem)
 
 BOOST_AUTO_TEST_CASE (StressInterleavedInsertRemoveQuery)
 
 BOOST_AUTO_TEST_CASE (BulkLoadEmpty)
 
 BOOST_AUTO_TEST_CASE (BulkLoadSingleItem)
 
 BOOST_AUTO_TEST_CASE (BulkLoadCorrectnessVsBruteForce)
 
 BOOST_AUTO_TEST_CASE (MortonIndexOrdersOnHighBits)
 
 BOOST_AUTO_TEST_CASE (BulkLoad3DCorrectnessVsBruteForce)
 
 BOOST_AUTO_TEST_CASE (BulkLoadThenInsertAndRemove)
 
 BOOST_AUTO_TEST_CASE (CloneSharesData)
 
 BOOST_AUTO_TEST_CASE (CloneMutateInsert)
 
 BOOST_AUTO_TEST_CASE (CloneMutateRemove)
 
 BOOST_AUTO_TEST_CASE (MultiLevelClone)
 
 BOOST_AUTO_TEST_CASE (CloneIterator)
 

Function Documentation

◆ BOOST_AUTO_TEST_CASE() [1/27]

BOOST_AUTO_TEST_CASE ( BulkInsert1K )

Definition at line 85 of file test_dynamic_rtree.cpp.

References BOOST_CHECK_EQUAL(), KIRTREE::DYNAMIC_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES >::Insert(), KIRTREE::DYNAMIC_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES >::Search(), and KIRTREE::DYNAMIC_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES >::size().

◆ BOOST_AUTO_TEST_CASE() [2/27]

BOOST_AUTO_TEST_CASE ( BulkInsertAndBruteForce )

Definition at line 218 of file test_dynamic_rtree.cpp.

References actual, BOOST_CHECK_EQUAL(), expected, KIRTREE::DYNAMIC_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES >::Insert(), ITEM, N, rng, KIRTREE::DYNAMIC_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES >::Search(), and KIRTREE::DYNAMIC_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES >::size().

◆ BOOST_AUTO_TEST_CASE() [3/27]

BOOST_AUTO_TEST_CASE ( BulkLoad3DCorrectnessVsBruteForce )

Definition at line 765 of file test_dynamic_rtree.cpp.

References actual, BOOST_CHECK_EQUAL(), KIRTREE::DYNAMIC_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES >::BulkLoad(), expected, ITEM, N, rng, KIRTREE::DYNAMIC_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES >::Search(), and KIRTREE::DYNAMIC_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES >::size().

◆ BOOST_AUTO_TEST_CASE() [4/27]

BOOST_AUTO_TEST_CASE ( BulkLoadCorrectnessVsBruteForce )

Definition at line 666 of file test_dynamic_rtree.cpp.

References actual, BOOST_CHECK_EQUAL(), KIRTREE::DYNAMIC_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES >::BulkLoad(), expected, ITEM, N, rng, KIRTREE::DYNAMIC_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES >::Search(), and KIRTREE::DYNAMIC_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES >::size().

◆ BOOST_AUTO_TEST_CASE() [5/27]

BOOST_AUTO_TEST_CASE ( BulkLoadEmpty )

Definition at line 635 of file test_dynamic_rtree.cpp.

References BOOST_CHECK_EQUAL(), KIRTREE::DYNAMIC_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES >::BulkLoad(), KIRTREE::DYNAMIC_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES >::empty(), and KIRTREE::DYNAMIC_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES >::size().

◆ BOOST_AUTO_TEST_CASE() [6/27]

BOOST_AUTO_TEST_CASE ( BulkLoadSingleItem )

Definition at line 646 of file test_dynamic_rtree.cpp.

References BOOST_CHECK_EQUAL(), KIRTREE::DYNAMIC_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES >::BulkLoad(), KIRTREE::DYNAMIC_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES >::Search(), and KIRTREE::DYNAMIC_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES >::size().

◆ BOOST_AUTO_TEST_CASE() [7/27]

BOOST_AUTO_TEST_CASE ( BulkLoadThenInsertAndRemove )

Definition at line 848 of file test_dynamic_rtree.cpp.

References actual, BOOST_CHECK_EQUAL(), KIRTREE::DYNAMIC_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES >::BulkLoad(), expected, KIRTREE::DYNAMIC_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES >::Insert(), ITEM, N, KIRTREE::DYNAMIC_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES >::Remove(), rng, KIRTREE::DYNAMIC_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES >::Search(), and KIRTREE::DYNAMIC_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES >::size().

◆ BOOST_AUTO_TEST_CASE() [8/27]

BOOST_AUTO_TEST_CASE ( CloneIterator )

Definition at line 1113 of file test_dynamic_rtree.cpp.

References BOOST_CHECK_EQUAL(), KIRTREE::COW_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES >::Clone(), and KIRTREE::COW_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES >::Insert().

◆ BOOST_AUTO_TEST_CASE() [9/27]

BOOST_AUTO_TEST_CASE ( CloneMutateInsert )

Definition at line 985 of file test_dynamic_rtree.cpp.

References BOOST_CHECK_EQUAL(), KIRTREE::COW_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES >::Clone(), KIRTREE::COW_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES >::Insert(), KIRTREE::COW_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES >::Search(), and KIRTREE::COW_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES >::size().

◆ BOOST_AUTO_TEST_CASE() [10/27]

BOOST_AUTO_TEST_CASE ( CloneMutateRemove )

Definition at line 1033 of file test_dynamic_rtree.cpp.

References BOOST_CHECK_EQUAL(), KIRTREE::COW_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES >::Clone(), KIRTREE::COW_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES >::Insert(), KIRTREE::COW_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES >::Search(), and KIRTREE::COW_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES >::size().

◆ BOOST_AUTO_TEST_CASE() [11/27]

BOOST_AUTO_TEST_CASE ( CloneSharesData )

Definition at line 942 of file test_dynamic_rtree.cpp.

References BOOST_AUTO_TEST_CASE(), BOOST_CHECK_EQUAL(), KIRTREE::COW_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES >::Clone(), KIRTREE::COW_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES >::Insert(), KIRTREE::COW_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES >::Search(), and KIRTREE::COW_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES >::size().

◆ BOOST_AUTO_TEST_CASE() [12/27]

BOOST_AUTO_TEST_CASE ( EarlyTermination )

Definition at line 485 of file test_dynamic_rtree.cpp.

References BOOST_CHECK_EQUAL(), KIRTREE::DYNAMIC_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES >::Insert(), and KIRTREE::DYNAMIC_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES >::Search().

◆ BOOST_AUTO_TEST_CASE() [13/27]

BOOST_AUTO_TEST_CASE ( EmptyTree )

Definition at line 35 of file test_dynamic_rtree.cpp.

References KIRTREE::DYNAMIC_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES >::begin(), BOOST_AUTO_TEST_CASE(), BOOST_CHECK_EQUAL(), KIRTREE::DYNAMIC_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES >::empty(), KIRTREE::DYNAMIC_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES >::end(), KIRTREE::DYNAMIC_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES >::Search(), and KIRTREE::DYNAMIC_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES >::size().

◆ BOOST_AUTO_TEST_CASE() [14/27]

BOOST_AUTO_TEST_CASE ( IteratorFullCoverage )

Definition at line 462 of file test_dynamic_rtree.cpp.

References BOOST_CHECK_EQUAL(), and KIRTREE::DYNAMIC_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES >::Insert().

◆ BOOST_AUTO_TEST_CASE() [15/27]

BOOST_AUTO_TEST_CASE ( MortonIndexOrdersOnHighBits )

Definition at line 743 of file test_dynamic_rtree.cpp.

References KIRTREE::HilbertND2D().

◆ BOOST_AUTO_TEST_CASE() [16/27]

BOOST_AUTO_TEST_CASE ( MoveSemantics )

Definition at line 341 of file test_dynamic_rtree.cpp.

References BOOST_CHECK_EQUAL(), KIRTREE::DYNAMIC_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES >::Insert(), KIRTREE::DYNAMIC_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES >::Search(), and KIRTREE::DYNAMIC_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES >::size().

◆ BOOST_AUTO_TEST_CASE() [17/27]

BOOST_AUTO_TEST_CASE ( MultiLevelClone )

Definition at line 1069 of file test_dynamic_rtree.cpp.

References BOOST_CHECK_EQUAL(), KIRTREE::COW_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES >::Clone(), KIRTREE::COW_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES >::Insert(), KIRTREE::COW_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES >::Search(), and KIRTREE::COW_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES >::size().

◆ BOOST_AUTO_TEST_CASE() [18/27]

BOOST_AUTO_TEST_CASE ( NearestNeighbors )

Definition at line 434 of file test_dynamic_rtree.cpp.

References BOOST_CHECK_EQUAL(), KIRTREE::DYNAMIC_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES >::Insert(), and KIRTREE::DYNAMIC_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES >::NearestNeighbors().

◆ BOOST_AUTO_TEST_CASE() [19/27]

BOOST_AUTO_TEST_CASE ( RemoveAll )

Definition at line 381 of file test_dynamic_rtree.cpp.

References BOOST_CHECK_EQUAL(), KIRTREE::DYNAMIC_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES >::empty(), KIRTREE::DYNAMIC_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES >::Insert(), KIRTREE::DYNAMIC_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES >::RemoveAll(), and KIRTREE::DYNAMIC_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES >::size().

◆ BOOST_AUTO_TEST_CASE() [20/27]

BOOST_AUTO_TEST_CASE ( RemoveAndVerify )

Definition at line 290 of file test_dynamic_rtree.cpp.

References BOOST_CHECK_EQUAL(), KIRTREE::DYNAMIC_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES >::Insert(), ITEM, N, KIRTREE::DYNAMIC_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES >::Remove(), KIRTREE::DYNAMIC_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES >::Search(), and KIRTREE::DYNAMIC_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES >::size().

◆ BOOST_AUTO_TEST_CASE() [21/27]

BOOST_AUTO_TEST_CASE ( RemoveExisting )

Definition at line 114 of file test_dynamic_rtree.cpp.

References BOOST_CHECK_EQUAL(), KIRTREE::DYNAMIC_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES >::Insert(), KIRTREE::DYNAMIC_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES >::Remove(), KIRTREE::DYNAMIC_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES >::Search(), and KIRTREE::DYNAMIC_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES >::size().

◆ BOOST_AUTO_TEST_CASE() [22/27]

BOOST_AUTO_TEST_CASE ( RemoveMovedItem )

Definition at line 512 of file test_dynamic_rtree.cpp.

References BOOST_CHECK_EQUAL(), KIRTREE::DYNAMIC_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES >::Insert(), KIRTREE::DYNAMIC_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES >::Remove(), KIRTREE::DYNAMIC_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES >::Search(), and KIRTREE::DYNAMIC_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES >::size().

◆ BOOST_AUTO_TEST_CASE() [23/27]

BOOST_AUTO_TEST_CASE ( RemoveNonExistent )

Definition at line 150 of file test_dynamic_rtree.cpp.

References BOOST_CHECK_EQUAL(), KIRTREE::DYNAMIC_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES >::Insert(), KIRTREE::DYNAMIC_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES >::Remove(), and KIRTREE::DYNAMIC_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES >::size().

◆ BOOST_AUTO_TEST_CASE() [24/27]

BOOST_AUTO_TEST_CASE ( SearchOverlapDisjointAll )

Definition at line 165 of file test_dynamic_rtree.cpp.

References BOOST_CHECK_EQUAL(), KIRTREE::DYNAMIC_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES >::Insert(), and KIRTREE::DYNAMIC_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES >::Search().

◆ BOOST_AUTO_TEST_CASE() [25/27]

BOOST_AUTO_TEST_CASE ( SingleInsert )

Definition at line 52 of file test_dynamic_rtree.cpp.

References BOOST_CHECK_EQUAL(), KIRTREE::DYNAMIC_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES >::empty(), KIRTREE::DYNAMIC_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES >::Insert(), KIRTREE::DYNAMIC_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES >::Search(), and KIRTREE::DYNAMIC_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES >::size().

◆ BOOST_AUTO_TEST_CASE() [26/27]

BOOST_AUTO_TEST_CASE ( StressInterleavedInsertRemoveQuery )

Definition at line 554 of file test_dynamic_rtree.cpp.

References actual, BOOST_CHECK_EQUAL(), expected, KIRTREE::DYNAMIC_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES >::Insert(), ITEM, N, KIRTREE::DYNAMIC_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES >::Remove(), rng, KIRTREE::DYNAMIC_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES >::Search(), and KIRTREE::DYNAMIC_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES >::size().

◆ BOOST_AUTO_TEST_CASE() [27/27]

BOOST_AUTO_TEST_CASE ( ThreeDimensional )

Definition at line 406 of file test_dynamic_rtree.cpp.

References BOOST_CHECK_EQUAL(), KIRTREE::DYNAMIC_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES >::Insert(), KIRTREE::DYNAMIC_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES >::Search(), and KIRTREE::DYNAMIC_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES >::size().