k2tree_test.cc File Reference

Comprehensive test suite for K2Tree (2D k-d tree) spatial data structure. More...

#include <gtest/gtest.h>
#include <tpl_2dtree.H>
#include <tpl_array.H>
#include <random>
#include <algorithm>
#include <vector>
#include <set>
#include <cmath>

Include dependency graph for k2tree_test.cc:

Go to the source code of this file.

Typedefs
using	K2TreeInt = K2Tree< Empty_Class >

Functions
	TEST (K2TreeBasic, ConstructorAndEmpty)
	TEST (K2TreeBasic, InsertSinglePoint)
	TEST (K2TreeBasic, InsertMultiplePoints)
	TEST (K2TreeBasic, InsertDuplicatePoint)
	TEST (K2TreeBasic, ContainsExisting)
	TEST (K2TreeBasic, ContainsNonExisting)
	TEST (K2TreeBasic, EmptyTreeContains)
	TEST (K2TreeInsertion, AscendingOrder)
	TEST (K2TreeInsertion, DescendingOrder)
	TEST (K2TreeInsertion, RandomOrder)
	TEST (K2TreeInsertion, ClusteredPoints)
	TEST (K2TreeNearest, BasicQueries)
	TEST (K2TreeNearest, MultiplePoints)
	TEST (K2TreeNearest, EmptyTree)
	TEST (K2TreeNearest, ExactMatch)
	TEST (K2TreeNearest, GridOfPoints)
	TEST (K2TreeRange, EmptyTree)
	TEST (K2TreeRange, AllPointsInRange)
	TEST (K2TreeRange, NoPointsInRange)
	TEST (K2TreeRange, SomePointsInRange)
	TEST (K2TreeRange, BoundaryPoints)
	TEST (K2TreeStress, LargeNumberOfPoints)
	TEST (K2TreeStress, ManyNearestQueries)
	TEST (K2TreeStress, ManyRangeQueries)
	TEST (K2TreeStress, DenseAndSparseRegions)
	TEST (K2TreeEdgeCases, ColinearPoints)
	TEST (K2TreeEdgeCases, VerticalLine)
	TEST (K2TreeEdgeCases, HorizontalLine)
	TEST (K2TreeEdgeCases, VeryClosePoints)
	TEST (K2TreeEdgeCases, NegativeCoordinates)
	TEST (K2TreeCorrectness, NearestIsActuallyNearest)
	TEST (K2TreeCorrectness, RangeIncludesAllInside)
	TEST (K2TreeFuzz, RandomInsertionsAndQueries)
	TEST (K2TreeInsertCorrectness, ReturnsTrueOnSuccess)
	TEST (K2TreeInsertCorrectness, ReturnsFalseOnDuplicate)
	TEST (K2TreeInsertCorrectness, AllInsertedPointsAreContained)
	TEST (K2TreeMove, MoveConstructor)
	TEST (K2TreeMove, MoveAssignment)
	TEST (K2TreeMove, MoveToSelf)
	TEST (K2TreeBuild, EmptyArray)
	TEST (K2TreeBuild, SinglePoint)
	TEST (K2TreeBuild, MultiplePoints)
	TEST (K2TreeBuild, DuplicatesRemoved)
	TEST (K2TreeBuild, NearestWorksOnBalancedTree)
	TEST (K2TreeBuild, StressBuildVsInsert)
	TEST (K2TreeForEach, EmptyTree)
	TEST (K2TreeForEach, VisitsAllPoints)
	TEST (K2TreeForEach, BalancedTreeVisitsAll)
int	main (int argc, char **argv)

Detailed Description

Comprehensive test suite for K2Tree (2D k-d tree) spatial data structure.

Author

Test Suite Generator

Definition in file k2tree_test.cc.

Typedef Documentation

K2TreeInt

using K2TreeInt = K2Tree<Empty_Class>

Definition at line 48 of file k2tree_test.cc.

Function Documentation

main()

int main	(	int	argc,
		char **	argv
	)

Definition at line 972 of file k2tree_test.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST() [1/48]

TEST	(	K2TreeBasic	,
		ConstructorAndEmpty
	)

Definition at line 54 of file k2tree_test.cc.

References Aleph::divide_and_conquer_partition_dp(), K2Tree< T >::is_empty(), and K2Tree< T >::size().

TEST() [2/48]

TEST	(	K2TreeBasic	,
		ContainsExisting
	)

Definition at line 96 of file k2tree_test.cc.

References K2Tree< T >::contains(), Aleph::divide_and_conquer_partition_dp(), and K2Tree< T >::insert().

TEST() [3/48]

TEST	(	K2TreeBasic	,
		ContainsNonExisting
	)

Definition at line 107 of file k2tree_test.cc.

References K2Tree< T >::contains(), Aleph::divide_and_conquer_partition_dp(), and K2Tree< T >::insert().

TEST() [4/48]

TEST	(	K2TreeBasic	,
		EmptyTreeContains
	)

Definition at line 117 of file k2tree_test.cc.

References K2Tree< T >::contains(), and Aleph::divide_and_conquer_partition_dp().

TEST() [5/48]

TEST	(	K2TreeBasic	,
		InsertDuplicatePoint
	)

Definition at line 84 of file k2tree_test.cc.

References Aleph::divide_and_conquer_partition_dp(), K2Tree< T >::insert(), and K2Tree< T >::size().

TEST() [6/48]

TEST	(	K2TreeBasic	,
		InsertMultiplePoints
	)

Definition at line 73 of file k2tree_test.cc.

References Aleph::divide_and_conquer_partition_dp(), K2Tree< T >::insert(), and K2Tree< T >::size().

TEST() [7/48]

TEST	(	K2TreeBasic	,
		InsertSinglePoint
	)

Definition at line 62 of file k2tree_test.cc.

References Aleph::divide_and_conquer_partition_dp(), K2Tree< T >::insert(), K2Tree< T >::is_empty(), and K2Tree< T >::size().

TEST() [8/48]

TEST	(	K2TreeBuild	,
		DuplicatesRemoved
	)

Definition at line 849 of file k2tree_test.cc.

References Aleph::Array< T >::append(), K2Tree< T >::build(), and Aleph::divide_and_conquer_partition_dp().

TEST() [9/48]

TEST	(	K2TreeBuild	,
		EmptyArray
	)

Definition at line 813 of file k2tree_test.cc.

References K2Tree< T >::build(), and Aleph::divide_and_conquer_partition_dp().

TEST() [10/48]

TEST	(	K2TreeBuild	,
		MultiplePoints
	)

Definition at line 833 of file k2tree_test.cc.

References Aleph::Array< T >::append(), K2Tree< T >::build(), and Aleph::divide_and_conquer_partition_dp().

TEST() [11/48]

TEST	(	K2TreeBuild	,
		NearestWorksOnBalancedTree
	)

Definition at line 866 of file k2tree_test.cc.

References Aleph::Array< T >::append(), K2Tree< T >::build(), and Aleph::divide_and_conquer_partition_dp().

TEST() [12/48]

TEST	(	K2TreeBuild	,
		SinglePoint
	)

Definition at line 822 of file k2tree_test.cc.

References Aleph::Array< T >::append(), K2Tree< T >::build(), and Aleph::divide_and_conquer_partition_dp().

TEST() [13/48]

TEST	(	K2TreeBuild	,
		StressBuildVsInsert
	)

Definition at line 885 of file k2tree_test.cc.

References Aleph::Array< T >::append(), K2Tree< T >::build(), and Aleph::divide_and_conquer_partition_dp().

TEST() [14/48]

TEST	(	K2TreeCorrectness	,
		NearestIsActuallyNearest
	)

Definition at line 578 of file k2tree_test.cc.

References Aleph::divide_and_conquer_partition_dp(), K2Tree< T >::insert(), and K2Tree< T >::nearest().

TEST() [15/48]

TEST	(	K2TreeCorrectness	,
		RangeIncludesAllInside
	)

Definition at line 606 of file k2tree_test.cc.

References Aleph::divide_and_conquer_partition_dp(), K2Tree< T >::insert(), r, and K2Tree< T >::range().

TEST() [16/48]

TEST	(	K2TreeEdgeCases	,
		ColinearPoints
	)

Definition at line 506 of file k2tree_test.cc.

References K2Tree< T >::contains(), Aleph::divide_and_conquer_partition_dp(), K2Tree< T >::insert(), and K2Tree< T >::size().

TEST() [17/48]

TEST	(	K2TreeEdgeCases	,
		HorizontalLine
	)

Definition at line 537 of file k2tree_test.cc.

References Aleph::divide_and_conquer_partition_dp(), K2Tree< T >::insert(), and K2Tree< T >::size().

TEST() [18/48]

TEST	(	K2TreeEdgeCases	,
		NegativeCoordinates
	)

Definition at line 560 of file k2tree_test.cc.

References K2Tree< T >::contains(), Aleph::divide_and_conquer_partition_dp(), K2Tree< T >::insert(), and K2Tree< T >::size().

TEST() [19/48]

TEST	(	K2TreeEdgeCases	,
		VerticalLine
	)

Definition at line 525 of file k2tree_test.cc.

References Aleph::divide_and_conquer_partition_dp(), K2Tree< T >::insert(), and K2Tree< T >::size().

TEST() [20/48]

TEST	(	K2TreeEdgeCases	,
		VeryClosePoints
	)

Definition at line 549 of file k2tree_test.cc.

References Aleph::divide_and_conquer_partition_dp(), K2Tree< T >::insert(), and K2Tree< T >::size().

TEST() [21/48]

TEST	(	K2TreeForEach	,
		BalancedTreeVisitsAll
	)

Definition at line 953 of file k2tree_test.cc.

References Aleph::Array< T >::append(), K2Tree< T >::build(), Aleph::count(), and Aleph::divide_and_conquer_partition_dp().

TEST() [22/48]

TEST	(	K2TreeForEach	,
		EmptyTree
	)

Definition at line 921 of file k2tree_test.cc.

References Aleph::count(), Aleph::divide_and_conquer_partition_dp(), and K2Tree< T >::for_each().

TEST() [23/48]

TEST	(	K2TreeForEach	,
		VisitsAllPoints
	)

Definition at line 931 of file k2tree_test.cc.

References Aleph::divide_and_conquer_partition_dp(), K2Tree< T >::for_each(), __gmp_expr< mpq_t, mpq_t >::get_d(), Aleph::Point::get_x(), Aleph::Point::get_y(), and K2Tree< T >::insert().

TEST() [24/48]

TEST	(	K2TreeFuzz	,
		RandomInsertionsAndQueries
	)

Definition at line 654 of file k2tree_test.cc.

References K2Tree< T >::contains(), Aleph::divide_and_conquer_partition_dp(), __gmp_expr< mpq_t, mpq_t >::get_d(), Aleph::Point::get_x(), Aleph::Point::get_y(), K2Tree< T >::insert(), K2Tree< T >::is_empty(), K2Tree< T >::nearest(), K2Tree< T >::range(), y, and y1().

TEST() [25/48]

TEST	(	K2TreeInsertCorrectness	,
		AllInsertedPointsAreContained
	)

Definition at line 729 of file k2tree_test.cc.

References K2Tree< T >::contains(), Aleph::divide_and_conquer_partition_dp(), K2Tree< T >::insert(), and K2Tree< T >::size().

TEST() [26/48]

TEST	(	K2TreeInsertCorrectness	,
		ReturnsFalseOnDuplicate
	)

Definition at line 720 of file k2tree_test.cc.

References Aleph::divide_and_conquer_partition_dp(), K2Tree< T >::insert(), and K2Tree< T >::size().

TEST() [27/48]

TEST	(	K2TreeInsertCorrectness	,
		ReturnsTrueOnSuccess
	)

Definition at line 710 of file k2tree_test.cc.

References Aleph::divide_and_conquer_partition_dp(), K2Tree< T >::insert(), and K2Tree< T >::size().

TEST() [28/48]

TEST	(	K2TreeInsertion	,
		AscendingOrder
	)

Definition at line 128 of file k2tree_test.cc.

References K2Tree< T >::contains(), Aleph::divide_and_conquer_partition_dp(), K2Tree< T >::insert(), and K2Tree< T >::size().

TEST() [29/48]

TEST	(	K2TreeInsertion	,
		ClusteredPoints
	)

Definition at line 190 of file k2tree_test.cc.

References Aleph::divide_and_conquer_partition_dp(), K2Tree< T >::insert(), and K2Tree< T >::size().

TEST() [30/48]

TEST	(	K2TreeInsertion	,
		DescendingOrder
	)

Definition at line 152 of file k2tree_test.cc.

References Aleph::divide_and_conquer_partition_dp(), K2Tree< T >::insert(), and K2Tree< T >::size().

TEST() [31/48]

TEST	(	K2TreeInsertion	,
		RandomOrder
	)

Definition at line 167 of file k2tree_test.cc.

References K2Tree< T >::contains(), Aleph::divide_and_conquer_partition_dp(), K2Tree< T >::insert(), and K2Tree< T >::size().

TEST() [32/48]

TEST	(	K2TreeMove	,
		MoveAssignment
	)

Definition at line 775 of file k2tree_test.cc.

References Aleph::divide_and_conquer_partition_dp(), K2Tree< T >::insert(), K2Tree< T >::is_empty(), and K2Tree< T >::size().

TEST() [33/48]

TEST	(	K2TreeMove	,
		MoveConstructor
	)

Definition at line 754 of file k2tree_test.cc.

References Aleph::divide_and_conquer_partition_dp(), K2Tree< T >::insert(), K2Tree< T >::is_empty(), and K2Tree< T >::size().

TEST() [34/48]

TEST	(	K2TreeMove	,
		MoveToSelf
	)

Definition at line 796 of file k2tree_test.cc.

References K2Tree< T >::contains(), Aleph::divide_and_conquer_partition_dp(), K2Tree< T >::insert(), and K2Tree< T >::size().

TEST() [35/48]

TEST	(	K2TreeNearest	,
		BasicQueries
	)

Definition at line 213 of file k2tree_test.cc.

References Aleph::divide_and_conquer_partition_dp(), K2Tree< T >::insert(), and K2Tree< T >::nearest().

TEST() [36/48]

TEST	(	K2TreeNearest	,
		EmptyTree
	)

Definition at line 252 of file k2tree_test.cc.

References Aleph::divide_and_conquer_partition_dp(), and K2Tree< T >::nearest().

TEST() [37/48]

TEST	(	K2TreeNearest	,
		ExactMatch
	)

Definition at line 260 of file k2tree_test.cc.

References Aleph::divide_and_conquer_partition_dp(), K2Tree< T >::insert(), and K2Tree< T >::nearest().

TEST() [38/48]

TEST	(	K2TreeNearest	,
		GridOfPoints
	)

Definition at line 273 of file k2tree_test.cc.

References Aleph::divide_and_conquer_partition_dp(), K2Tree< T >::insert(), and K2Tree< T >::nearest().

TEST() [39/48]

TEST	(	K2TreeNearest	,
		MultiplePoints
	)

Definition at line 225 of file k2tree_test.cc.

References Aleph::divide_and_conquer_partition_dp(), K2Tree< T >::insert(), and K2Tree< T >::nearest().

TEST() [40/48]

TEST	(	K2TreeRange	,
		AllPointsInRange
	)

Definition at line 310 of file k2tree_test.cc.

References Aleph::divide_and_conquer_partition_dp(), K2Tree< T >::insert(), K2Tree< T >::range(), and Aleph::HTList::size().

TEST() [41/48]

TEST	(	K2TreeRange	,
		BoundaryPoints
	)

Definition at line 369 of file k2tree_test.cc.

References Aleph::divide_and_conquer_partition_dp(), K2Tree< T >::insert(), K2Tree< T >::range(), and Aleph::HTList::size().

TEST() [42/48]

TEST	(	K2TreeRange	,
		EmptyTree
	)

Definition at line 299 of file k2tree_test.cc.

References Aleph::divide_and_conquer_partition_dp(), Aleph::HTList::is_empty(), and K2Tree< T >::range().

TEST() [43/48]

TEST	(	K2TreeRange	,
		NoPointsInRange
	)

Definition at line 325 of file k2tree_test.cc.

References Aleph::divide_and_conquer_partition_dp(), K2Tree< T >::insert(), Aleph::HTList::is_empty(), and K2Tree< T >::range().

TEST() [44/48]

TEST	(	K2TreeRange	,
		SomePointsInRange
	)

Definition at line 339 of file k2tree_test.cc.

References Aleph::divide_and_conquer_partition_dp(), K2Tree< T >::insert(), K2Tree< T >::range(), and Aleph::HTList::size().

TEST() [45/48]

TEST	(	K2TreeStress	,
		DenseAndSparseRegions
	)

Definition at line 466 of file k2tree_test.cc.

References Aleph::divide_and_conquer_partition_dp(), K2Tree< T >::insert(), and K2Tree< T >::range().

TEST() [46/48]

TEST	(	K2TreeStress	,
		LargeNumberOfPoints
	)

Definition at line 390 of file k2tree_test.cc.

References Aleph::divide_and_conquer_partition_dp(), K2Tree< T >::insert(), and K2Tree< T >::size().

TEST() [47/48]

TEST	(	K2TreeStress	,
		ManyNearestQueries
	)

Definition at line 413 of file k2tree_test.cc.

References Aleph::divide_and_conquer_partition_dp(), K2Tree< T >::insert(), and K2Tree< T >::nearest().

TEST() [48/48]

TEST	(	K2TreeStress	,
		ManyRangeQueries
	)

Definition at line 435 of file k2tree_test.cc.

References Aleph::divide_and_conquer_partition_dp(), K2Tree< T >::insert(), K2Tree< T >::range(), Aleph::HTList::size(), and y1().