r_tree_test.cc File Reference

Tests for Aleph::RTree. More...

#include <gtest/gtest.h>
#include <algorithm>
#include <concepts>
#include <limits>
#include <memory>
#include <random>
#include <type_traits>
#include <utility>
#include <ahSort.H>
#include <tpl_r_tree.H>
#include "r_tree_debug_snapshot_test_helpers.H"

Include dependency graph for r_tree_test.cc:

Go to the source code of this file.

Functions
	TEST (RTree, EmptyTree)
	TEST (RTree, SingletonInsertAndQuery)
	TEST (RTree, EraseSingletonEmptiesTree)
	TEST (RTree, EraseNonexistentReturnsFalse)
	TEST (RTree, GrowsInHeightWithManyInserts)
	TEST (RTree, DebugSnapshotEmptyTree)
	TEST (RTree, DebugSnapshotStructuralInvariants)
	TEST (RTree, DebugSnapshotSingleLeafRoot)
	TEST (RTree, CoincidentRectangles)
	TEST (RTree, DegenerateRectangles)
	TEST (RTree, CopyIsIndependentDeepClone)
	TEST (RTree, MoveConstructionTransfersOwnership)
	TEST (RTree, SupportsMoveOnlyPayload)
	TEST (RTree, CopyConstructiblePayloadNeedNotBeCopyAssignable)
	TEST (RTree, AssignmentClearAndDrainRemainValid)
	TEST (RTree, RandomizedParityAgainstBruteForce)

Detailed Description

Tests for Aleph::RTree.

Definition in file r_tree_test.cc.

Function Documentation

TEST() [1/16]

TEST	(	RTree	,
		AssignmentClearAndDrainRemainValid
	)

Definition at line 343 of file r_tree_test.cc.

References Aleph::Array< T >::append(), Aleph::blossom_maximum_cardinality_matching(), Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::erase(), Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::height(), Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::insert(), Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::is_empty(), Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::size(), and Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::verify().

TEST() [2/16]

TEST	(	RTree	,
		CoincidentRectangles
	)

Definition at line 229 of file r_tree_test.cc.

References StlAlephIterator< SetName >::begin(), Aleph::blossom_maximum_cardinality_matching(), box(), StlAlephIterator< SetName >::end(), Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::erase(), Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::insert(), Aleph::Array< T >::size(), Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::size(), Aleph::size(), and Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::verify().

TEST() [3/16]

TEST	(	RTree	,
		CopyConstructiblePayloadNeedNotBeCopyAssignable
	)

Definition at line 322 of file r_tree_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::copy(), Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::insert(), and value.

TEST() [4/16]

TEST	(	RTree	,
		CopyIsIndependentDeepClone
	)

Definition at line 266 of file r_tree_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::copy(), and Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::insert().

TEST() [5/16]

TEST	(	RTree	,
		DebugSnapshotEmptyTree
	)

Definition at line 196 of file r_tree_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), and Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::debug_snapshot().

TEST() [6/16]

TEST	(	RTree	,
		DebugSnapshotSingleLeafRoot
	)

Definition at line 216 of file r_tree_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::debug_snapshot(), and Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::insert().

TEST() [7/16]

TEST	(	RTree	,
		DebugSnapshotStructuralInvariants
	)

Definition at line 204 of file r_tree_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::test_helpers::check_snapshot_node(), Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::debug_snapshot(), Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::insert(), and Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::size().

TEST() [8/16]

TEST	(	RTree	,
		DegenerateRectangles
	)

Definition at line 248 of file r_tree_test.cc.

References StlAlephIterator< SetName >::begin(), Aleph::blossom_maximum_cardinality_matching(), StlAlephIterator< SetName >::end(), Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::insert(), Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::size(), and Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::verify().

TEST() [9/16]

TEST	(	RTree	,
		EmptyTree
	)

Definition at line 128 of file r_tree_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::erase(), Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::height(), Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::is_empty(), Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::search_contains(), Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::search_intersects(), Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::size(), Aleph::size(), and Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::verify().

TEST() [10/16]

TEST	(	RTree	,
		EraseNonexistentReturnsFalse
	)

Definition at line 167 of file r_tree_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::erase(), Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::insert(), Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::size(), and Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::verify().

TEST() [11/16]

TEST	(	RTree	,
		EraseSingletonEmptiesTree
	)

Definition at line 156 of file r_tree_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::erase(), Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::height(), Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::insert(), Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::is_empty(), Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::size(), and Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::verify().

TEST() [12/16]

TEST	(	RTree	,
		GrowsInHeightWithManyInserts
	)

Definition at line 177 of file r_tree_test.cc.

References StlAlephIterator< SetName >::begin(), Aleph::blossom_maximum_cardinality_matching(), StlAlephIterator< SetName >::end(), Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::height(), Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::insert(), Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::size(), and Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::verify().

TEST() [13/16]

TEST	(	RTree	,
		MoveConstructionTransfersOwnership
	)

Definition at line 288 of file r_tree_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::insert(), Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::is_empty(), Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::size(), and Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::verify().

TEST() [14/16]

TEST	(	RTree	,
		RandomizedParityAgainstBruteForce
	)

Definition at line 388 of file r_tree_test.cc.

References Aleph::Array< T >::append(), Aleph::blossom_maximum_cardinality_matching(), Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::erase(), Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::insert(), Aleph::Array< T >::is_empty(), k, Aleph::Array< T >::remove_last(), rng, Aleph::Array< T >::size(), Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::size(), Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::verify(), y, and y1().

TEST() [15/16]

TEST	(	RTree	,
		SingletonInsertAndQuery
	)

Definition at line 140 of file r_tree_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::height(), Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::insert(), Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::is_empty(), Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::size(), and Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::verify().

TEST() [16/16]

TEST	(	RTree	,
		SupportsMoveOnlyPayload
	)

Definition at line 301 of file r_tree_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::for_each_intersecting(), Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::insert(), Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::size(), Aleph::sum(), and Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::verify().