quadtree_test.cc File Reference

Comprehensive test suite for QuadTree spatial data structure. More...

#include <gtest/gtest.h>
#include <quadtree.H>
#include <random>
#include <algorithm>
#include <unordered_set>
#include <sstream>

Include dependency graph for quadtree_test.cc:

Go to the source code of this file.

Functions
	TEST (QuadTreeBasic, ConstructorAndEmpty)
	TEST (QuadTreeBasic, RejectsInvalidBoundsAndZeroCapacity)
	TEST (QuadTreeBasic, QuadNodeSetRegionRejectsInvalidBoundsWithoutMutation)
	TEST (QuadTreeBasic, InsertSinglePoint)
	TEST (QuadTreeBasic, InsertOutsideBounds)
	TEST (QuadTreeBasic, ContainsCheck)
	TEST (QuadTreeBasic, SearchExistingPoint)
	TEST (QuadTreeBasic, SearchNonExistingPoint)
	TEST (QuadTreeBasic, SearchContainerNode)
	TEST (QuadTreeBasic, RemoveSinglePoint)
	TEST (QuadTreeBasic, RemoveNonExistingPoint)
	TEST (QuadTreeBasic, RemoveOutsideBoundsIsANoOp)
	TEST (QuadTreeBasic, EmptyTree)
	TEST (QuadTreeBasic, ClearEdgeCases)
	TEST (QuadTreeBasic, ClearYieldsSameStateAsEmpty)
	TEST (QuadTreeSubdivision, SingleLevelSplit)
	TEST (QuadTreeSubdivision, MultiLevelSplit)
	TEST (QuadTreeSubdivision, AllQuadrantsPopulated)
	TEST (QuadTreeMerging, RemovalTriggersJoin)
	TEST (QuadTreeMerging, MultipleRemovalsGradualJoin)
	TEST (QuadTreeMerging, CollapsesEveryEligibleAncestor)
	TEST (QuadTreeCopy, CopyConstructor)
	TEST (QuadTreeCopy, AssignmentOperator)
	TEST (QuadTreeCopy, SelfAssignment)
	TEST (QuadTreeStress, InsertManyPoints)
	TEST (QuadTreeStress, InsertRemoveCycles)
	TEST (QuadTreeStress, DenseRegion)
	TEST (QuadTreeEdgeCases, BoundaryPoints)
	TEST (QuadTreeEdgeCases, MidpointCoordinates)
	TEST (QuadTreeEdgeCases, SinglePointCapacity)
	TEST (QuadTreeEdgeCases, DuplicatePointsTerminateAndRemainCounted)
	TEST (QuadTreeEdgeCases, VerySmallRegion)
	TEST (QuadTreeEdgeCases, VeryLargeRegion)
	TEST (QuadTreeTraversal, ForEachNode)
	TEST (QuadTreeTraversal, CountLeaves)
	TEST (QuadTreeFuzz, RandomOperations)
int	main (int argc, char **argv)

Detailed Description

Comprehensive test suite for QuadTree spatial data structure.

Author

Test Suite Generator

Definition in file quadtree_test.cc.

Function Documentation

main()

int main	(	int	argc,
		char **	argv
	)

Definition at line 700 of file quadtree_test.cc.

References Aleph::blossom_maximum_cardinality_matching().

TEST() [1/36]

TEST	(	QuadTreeBasic	,
		ClearEdgeCases
	)

Definition at line 213 of file quadtree_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), QuadTree::clear(), QuadTree::insert(), and QuadTree::search().

TEST() [2/36]

TEST	(	QuadTreeBasic	,
		ClearYieldsSameStateAsEmpty
	)

Definition at line 229 of file quadtree_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), QuadTree::clear(), QuadTree::insert(), and QuadTree::search().

TEST() [3/36]

TEST	(	QuadTreeBasic	,
		ConstructorAndEmpty
	)

Definition at line 50 of file quadtree_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), QuadTree::get_max_num_points_per_node(), and QuadTree::get_root().

TEST() [4/36]

TEST	(	QuadTreeBasic	,
		ContainsCheck
	)

Definition at line 107 of file quadtree_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), QuadTree::contains(), and QuadTree::insert().

TEST() [5/36]

TEST	(	QuadTreeBasic	,
		EmptyTree
	)

Definition at line 198 of file quadtree_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), QuadTree::empty(), QuadTree::insert(), and QuadTree::search().

TEST() [6/36]

TEST	(	QuadTreeBasic	,
		InsertOutsideBounds
	)

Definition at line 92 of file quadtree_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), and QuadTree::insert().

TEST() [7/36]

TEST	(	QuadTreeBasic	,
		InsertSinglePoint
	)

Definition at line 81 of file quadtree_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::Point::get_x(), Aleph::Point::get_y(), and QuadTree::insert().

TEST() [8/36]

TEST	(	QuadTreeBasic	,
		QuadNodeSetRegionRejectsInvalidBoundsWithoutMutation
	)

Definition at line 71 of file quadtree_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), QuadNode::get_max_x(), QuadNode::get_max_y(), QuadNode::get_min_x(), QuadNode::get_min_y(), and QuadNode::set_region().

TEST() [9/36]

TEST	(	QuadTreeBasic	,
		RejectsInvalidBoundsAndZeroCapacity
	)

Definition at line 58 of file quadtree_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), QuadTree::get_max_num_points_per_node(), and QuadTree::set_max_num_points_per_node().

TEST() [10/36]

TEST	(	QuadTreeBasic	,
		RemoveNonExistingPoint
	)

Definition at line 174 of file quadtree_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), QuadTree::insert(), QuadTree::remove(), and QuadTree::search().

TEST() [11/36]

TEST	(	QuadTreeBasic	,
		RemoveOutsideBoundsIsANoOp
	)

Definition at line 186 of file quadtree_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), QuadTree::insert(), QuadTree::remove(), and QuadTree::search().

TEST() [12/36]

TEST	(	QuadTreeBasic	,
		RemoveSinglePoint
	)

Definition at line 163 of file quadtree_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), QuadTree::insert(), QuadTree::remove(), and QuadTree::search().

TEST() [13/36]

TEST	(	QuadTreeBasic	,
		SearchContainerNode
	)

Definition at line 150 of file quadtree_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), QuadTree::insert(), QuadNode::is_leaf(), QuadTree::search_container_node(), and QuadNode::search_point().

TEST() [14/36]

TEST	(	QuadTreeBasic	,
		SearchExistingPoint
	)

Definition at line 121 of file quadtree_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), QuadTree::insert(), and QuadTree::search().

TEST() [15/36]

TEST	(	QuadTreeBasic	,
		SearchNonExistingPoint
	)

Definition at line 139 of file quadtree_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), QuadTree::insert(), and QuadTree::search().

TEST() [16/36]

TEST	(	QuadTreeCopy	,
		AssignmentOperator
	)

Definition at line 408 of file quadtree_test.cc.

References Aleph::blossom_maximum_cardinality_matching().

TEST() [17/36]

TEST	(	QuadTreeCopy	,
		CopyConstructor
	)

Definition at line 388 of file quadtree_test.cc.

References Aleph::blossom_maximum_cardinality_matching().

TEST() [18/36]

TEST	(	QuadTreeCopy	,
		SelfAssignment
	)

Definition at line 428 of file quadtree_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), QuadTree::insert(), and QuadTree::search().

TEST() [19/36]

TEST	(	QuadTreeEdgeCases	,
		BoundaryPoints
	)

Definition at line 529 of file quadtree_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), and QuadTree::insert().

TEST() [20/36]

TEST	(	QuadTreeEdgeCases	,
		DuplicatePointsTerminateAndRemainCounted
	)

Definition at line 570 of file quadtree_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), COLOR, QuadNode::get_num_points(), QuadTree::get_root(), QuadTree::insert(), QuadNode::is_leaf(), QuadTree::remove(), and QuadTree::search().

TEST() [21/36]

TEST	(	QuadTreeEdgeCases	,
		MidpointCoordinates
	)

Definition at line 545 of file quadtree_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), QuadTree::insert(), and QuadTree::search().

TEST() [22/36]

TEST	(	QuadTreeEdgeCases	,
		SinglePointCapacity
	)

Definition at line 559 of file quadtree_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), QuadTree::get_root(), QuadTree::insert(), and QuadNode::is_leaf().

TEST() [23/36]

TEST	(	QuadTreeEdgeCases	,
		VeryLargeRegion
	)

Definition at line 599 of file quadtree_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), QuadTree::insert(), and QuadTree::search().

TEST() [24/36]

TEST	(	QuadTreeEdgeCases	,
		VerySmallRegion
	)

Definition at line 588 of file quadtree_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), QuadTree::insert(), and QuadTree::search().

TEST() [25/36]

TEST	(	QuadTreeFuzz	,
		RandomOperations
	)

Definition at line 656 of file quadtree_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), QuadTree::insert(), QuadTree::remove(), and QuadTree::search().

TEST() [26/36]

TEST	(	QuadTreeMerging	,
		CollapsesEveryEligibleAncestor
	)

Definition at line 359 of file quadtree_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), QuadTree::get_root(), QuadTree::insert(), QuadNode::is_leaf(), QuadTree::remove(), and QuadTree::search().

TEST() [27/36]

TEST	(	QuadTreeMerging	,
		MultipleRemovalsGradualJoin
	)

Definition at line 332 of file quadtree_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), COLOR, QuadTree::get_root(), QuadTree::insert(), QuadNode::is_leaf(), and QuadTree::remove().

TEST() [28/36]

TEST	(	QuadTreeMerging	,
		RemovalTriggersJoin
	)

Definition at line 313 of file quadtree_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), QuadTree::get_root(), QuadTree::insert(), QuadNode::is_leaf(), and QuadTree::remove().

TEST() [29/36]

TEST	(	QuadTreeStress	,
		DenseRegion
	)

Definition at line 502 of file quadtree_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), QuadTree::insert(), QuadTree::search(), and y.

TEST() [30/36]

TEST	(	QuadTreeStress	,
		InsertManyPoints
	)

Definition at line 443 of file quadtree_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), QuadTree::insert(), and QuadTree::search().

TEST() [31/36]

TEST	(	QuadTreeStress	,
		InsertRemoveCycles
	)

Definition at line 468 of file quadtree_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), QuadTree::insert(), QuadTree::remove(), and test().

TEST() [32/36]

TEST	(	QuadTreeSubdivision	,
		AllQuadrantsPopulated
	)

Definition at line 288 of file quadtree_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), QuadTree::get_root(), QuadTree::insert(), Aleph::is_leaf(), NE_CHILD, NW_CHILD, root(), SE_CHILD, and SW_CHILD.

TEST() [33/36]

TEST	(	QuadTreeSubdivision	,
		MultiLevelSplit
	)

Definition at line 263 of file quadtree_test.cc.

References Aleph::and, Aleph::blossom_maximum_cardinality_matching(), QuadTree::get_root(), QuadTree::insert(), QuadNode::is_leaf(), NE_CHILD, and NW_CHILD.

TEST() [34/36]

TEST	(	QuadTreeSubdivision	,
		SingleLevelSplit
	)

Definition at line 245 of file quadtree_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), COLOR, QuadTree::get_root(), QuadTree::insert(), and QuadNode::is_leaf().

TEST() [35/36]

TEST	(	QuadTreeTraversal	,
		CountLeaves
	)

Definition at line 634 of file quadtree_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), QuadTree::for_each(), QuadTree::insert(), and QuadNode::is_leaf().

TEST() [36/36]

TEST	(	QuadTreeTraversal	,
		ForEachNode
	)

Definition at line 616 of file quadtree_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), QuadTree::for_each(), and QuadTree::insert().