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 <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, SinglePoint)
	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)
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 47 of file k2tree_test.cc.

Function Documentation

main()

int main	(	int	argc,
		char **	argv
	)

Definition at line 707 of file k2tree_test.cc.

References Aleph::maps().

TEST() [1/33]

TEST	(	K2TreeBasic	,
		ConstructorAndEmpty
	)

Definition at line 53 of file k2tree_test.cc.

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

TEST() [2/33]

TEST	(	K2TreeBasic	,
		ContainsExisting
	)

Definition at line 95 of file k2tree_test.cc.

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

TEST() [3/33]

TEST	(	K2TreeBasic	,
		ContainsNonExisting
	)

Definition at line 106 of file k2tree_test.cc.

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

TEST() [4/33]

TEST	(	K2TreeBasic	,
		EmptyTreeContains
	)

Definition at line 116 of file k2tree_test.cc.

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

TEST() [5/33]

TEST	(	K2TreeBasic	,
		InsertDuplicatePoint
	)

Definition at line 83 of file k2tree_test.cc.

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

TEST() [6/33]

TEST	(	K2TreeBasic	,
		InsertMultiplePoints
	)

Definition at line 72 of file k2tree_test.cc.

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

TEST() [7/33]

TEST	(	K2TreeBasic	,
		InsertSinglePoint
	)

Definition at line 61 of file k2tree_test.cc.

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

TEST() [8/33]

TEST	(	K2TreeCorrectness	,
		NearestIsActuallyNearest
	)

Definition at line 576 of file k2tree_test.cc.

References Point::distance_with(), K2Tree< T >::insert(), Aleph::maps(), and K2Tree< T >::nearest().

TEST() [9/33]

TEST	(	K2TreeCorrectness	,
		RangeIncludesAllInside
	)

Definition at line 603 of file k2tree_test.cc.

References Rectangle::contains(), K2Tree< T >::insert(), Aleph::maps(), and K2Tree< T >::range().

TEST() [10/33]

TEST	(	K2TreeEdgeCases	,
		ColinearPoints
	)

Definition at line 504 of file k2tree_test.cc.

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

TEST() [11/33]

TEST	(	K2TreeEdgeCases	,
		HorizontalLine
	)

Definition at line 535 of file k2tree_test.cc.

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

TEST() [12/33]

TEST	(	K2TreeEdgeCases	,
		NegativeCoordinates
	)

Definition at line 558 of file k2tree_test.cc.

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

TEST() [13/33]

TEST	(	K2TreeEdgeCases	,
		VerticalLine
	)

Definition at line 523 of file k2tree_test.cc.

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

TEST() [14/33]

TEST	(	K2TreeEdgeCases	,
		VeryClosePoints
	)

Definition at line 547 of file k2tree_test.cc.

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

TEST() [15/33]

TEST	(	K2TreeFuzz	,
		RandomInsertionsAndQueries
	)

Definition at line 651 of file k2tree_test.cc.

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

TEST() [16/33]

TEST	(	K2TreeInsertion	,
		AscendingOrder
	)

Definition at line 127 of file k2tree_test.cc.

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

TEST() [17/33]

TEST	(	K2TreeInsertion	,
		ClusteredPoints
	)

Definition at line 189 of file k2tree_test.cc.

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

TEST() [18/33]

TEST	(	K2TreeInsertion	,
		DescendingOrder
	)

Definition at line 151 of file k2tree_test.cc.

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

TEST() [19/33]

TEST	(	K2TreeInsertion	,
		RandomOrder
	)

Definition at line 166 of file k2tree_test.cc.

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

TEST() [20/33]

TEST	(	K2TreeNearest	,
		EmptyTree
	)

Definition at line 248 of file k2tree_test.cc.

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

TEST() [21/33]

TEST	(	K2TreeNearest	,
		ExactMatch
	)

Definition at line 258 of file k2tree_test.cc.

References Point::get_x(), Point::get_y(), K2Tree< T >::insert(), Aleph::maps(), and K2Tree< T >::nearest().

TEST() [22/33]

TEST	(	K2TreeNearest	,
		GridOfPoints
	)

Definition at line 271 of file k2tree_test.cc.

References Point::distance_with(), K2Tree< T >::insert(), Aleph::maps(), and K2Tree< T >::nearest().

TEST() [23/33]

TEST	(	K2TreeNearest	,
		MultiplePoints
	)

Definition at line 224 of file k2tree_test.cc.

References Point::get_x(), Point::get_y(), K2Tree< T >::insert(), Aleph::maps(), and K2Tree< T >::nearest().

TEST() [24/33]

TEST	(	K2TreeNearest	,
		SinglePoint
	)

Definition at line 212 of file k2tree_test.cc.

References Point::get_x(), Point::get_y(), K2Tree< T >::insert(), Aleph::maps(), and K2Tree< T >::nearest().

TEST() [25/33]

TEST	(	K2TreeRange	,
		AllPointsInRange
	)

Definition at line 307 of file k2tree_test.cc.

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

TEST() [26/33]

TEST	(	K2TreeRange	,
		BoundaryPoints
	)

Definition at line 366 of file k2tree_test.cc.

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

TEST() [27/33]

TEST	(	K2TreeRange	,
		EmptyTree
	)

Definition at line 296 of file k2tree_test.cc.

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

TEST() [28/33]

TEST	(	K2TreeRange	,
		NoPointsInRange
	)

Definition at line 322 of file k2tree_test.cc.

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

TEST() [29/33]

TEST	(	K2TreeRange	,
		SomePointsInRange
	)

Definition at line 336 of file k2tree_test.cc.

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

TEST() [30/33]

TEST	(	K2TreeStress	,
		DenseAndSparseRegions
	)

Definition at line 464 of file k2tree_test.cc.

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

TEST() [31/33]

TEST	(	K2TreeStress	,
		LargeNumberOfPoints
	)

Definition at line 387 of file k2tree_test.cc.

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

TEST() [32/33]

TEST	(	K2TreeStress	,
		ManyNearestQueries
	)

Definition at line 410 of file k2tree_test.cc.

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

TEST() [33/33]

TEST	(	K2TreeStress	,
		ManyRangeQueries
	)

Definition at line 433 of file k2tree_test.cc.

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