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, InsertSinglePoint)
	TEST (QuadTreeBasic, InsertOutsideBounds)
	TEST (QuadTreeBasic, ContainsCheck)
	TEST (QuadTreeBasic, SearchExistingPoint)
	TEST (QuadTreeBasic, SearchNonExistingPoint)
	TEST (QuadTreeBasic, SearchContainerNode)
	TEST (QuadTreeBasic, RemoveSinglePoint)
	TEST (QuadTreeBasic, RemoveNonExistingPoint)
	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 (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, 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 622 of file quadtree_test.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST() [1/31]

TEST	(	QuadTreeBasic	,
		ClearEdgeCases
	)

Definition at line 178 of file quadtree_test.cc.

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

TEST() [2/31]

TEST	(	QuadTreeBasic	,
		ClearYieldsSameStateAsEmpty
	)

Definition at line 194 of file quadtree_test.cc.

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

TEST() [3/31]

TEST	(	QuadTreeBasic	,
		ConstructorAndEmpty
	)

Definition at line 50 of file quadtree_test.cc.

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

TEST() [4/31]

TEST	(	QuadTreeBasic	,
		ContainsCheck
	)

Definition at line 84 of file quadtree_test.cc.

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

TEST() [5/31]

TEST	(	QuadTreeBasic	,
		EmptyTree
	)

Definition at line 163 of file quadtree_test.cc.

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

TEST() [6/31]

TEST	(	QuadTreeBasic	,
		InsertOutsideBounds
	)

Definition at line 69 of file quadtree_test.cc.

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

TEST() [7/31]

TEST	(	QuadTreeBasic	,
		InsertSinglePoint
	)

Definition at line 58 of file quadtree_test.cc.

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

TEST() [8/31]

TEST	(	QuadTreeBasic	,
		RemoveNonExistingPoint
	)

Definition at line 151 of file quadtree_test.cc.

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

TEST() [9/31]

TEST	(	QuadTreeBasic	,
		RemoveSinglePoint
	)

Definition at line 140 of file quadtree_test.cc.

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

TEST() [10/31]

TEST	(	QuadTreeBasic	,
		SearchContainerNode
	)

Definition at line 127 of file quadtree_test.cc.

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

TEST() [11/31]

TEST	(	QuadTreeBasic	,
		SearchExistingPoint
	)

Definition at line 98 of file quadtree_test.cc.

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

TEST() [12/31]

TEST	(	QuadTreeBasic	,
		SearchNonExistingPoint
	)

Definition at line 116 of file quadtree_test.cc.

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

TEST() [13/31]

TEST	(	QuadTreeCopy	,
		AssignmentOperator
	)

Definition at line 348 of file quadtree_test.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST() [14/31]

TEST	(	QuadTreeCopy	,
		CopyConstructor
	)

Definition at line 328 of file quadtree_test.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST() [15/31]

TEST	(	QuadTreeCopy	,
		SelfAssignment
	)

Definition at line 368 of file quadtree_test.cc.

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

TEST() [16/31]

TEST	(	QuadTreeEdgeCases	,
		BoundaryPoints
	)

Definition at line 469 of file quadtree_test.cc.

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

TEST() [17/31]

TEST	(	QuadTreeEdgeCases	,
		MidpointCoordinates
	)

Definition at line 485 of file quadtree_test.cc.

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

TEST() [18/31]

TEST	(	QuadTreeEdgeCases	,
		SinglePointCapacity
	)

Definition at line 499 of file quadtree_test.cc.

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

TEST() [19/31]

TEST	(	QuadTreeEdgeCases	,
		VeryLargeRegion
	)

Definition at line 521 of file quadtree_test.cc.

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

TEST() [20/31]

TEST	(	QuadTreeEdgeCases	,
		VerySmallRegion
	)

Definition at line 510 of file quadtree_test.cc.

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

TEST() [21/31]

TEST	(	QuadTreeFuzz	,
		RandomOperations
	)

Definition at line 578 of file quadtree_test.cc.

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

TEST() [22/31]

TEST	(	QuadTreeMerging	,
		MultipleRemovalsGradualJoin
	)

Definition at line 297 of file quadtree_test.cc.

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

TEST() [23/31]

TEST	(	QuadTreeMerging	,
		RemovalTriggersJoin
	)

Definition at line 278 of file quadtree_test.cc.

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

TEST() [24/31]

TEST	(	QuadTreeStress	,
		DenseRegion
	)

Definition at line 442 of file quadtree_test.cc.

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

TEST() [25/31]

TEST	(	QuadTreeStress	,
		InsertManyPoints
	)

Definition at line 383 of file quadtree_test.cc.

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

TEST() [26/31]

TEST	(	QuadTreeStress	,
		InsertRemoveCycles
	)

Definition at line 408 of file quadtree_test.cc.

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

TEST() [27/31]

TEST	(	QuadTreeSubdivision	,
		AllQuadrantsPopulated
	)

Definition at line 253 of file quadtree_test.cc.

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

TEST() [28/31]

TEST	(	QuadTreeSubdivision	,
		MultiLevelSplit
	)

Definition at line 228 of file quadtree_test.cc.

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

TEST() [29/31]

TEST	(	QuadTreeSubdivision	,
		SingleLevelSplit
	)

Definition at line 210 of file quadtree_test.cc.

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

TEST() [30/31]

TEST	(	QuadTreeTraversal	,
		CountLeaves
	)

Definition at line 556 of file quadtree_test.cc.

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

TEST() [31/31]

TEST	(	QuadTreeTraversal	,
		ForEachNode
	)

Definition at line 538 of file quadtree_test.cc.

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