interval_tree_test.cc File Reference

Comprehensive tests for Interval<T>, Interval_Tree, and DynIntervalTree. More...

#include <gtest/gtest.h>
#include <tpl_interval_tree.H>
#include <random>
#include <algorithm>
#include <string>
#include <vector>
#include <type_traits>

Include dependency graph for interval_tree_test.cc:

Go to the source code of this file.

Classes
struct	CountingLess
class	IntervalTypeTest
class	IntervalTreeRawTest
class	DynIntervalTreeTest

Functions
	TEST_F (IntervalTypeTest, Construction)
	TEST_F (IntervalTypeTest, Validity)
	TEST_F (IntervalTypeTest, OverlapDetection)
	TEST_F (IntervalTypeTest, Containment)
	TEST_F (IntervalTypeTest, PointIntervals)
	TEST_F (IntervalTypeTest, Ordering)
	TEST_F (IntervalTreeRawTest, EmptyTree)
	TEST_F (IntervalTreeRawTest, SingleInsert)
	TEST_F (IntervalTreeRawTest, MultipleInserts)
	TEST_F (IntervalTreeRawTest, DuplicateInsert)
	TEST_F (IntervalTreeRawTest, InsertDup)
	TEST_F (IntervalTreeRawTest, Remove)
	TEST_F (IntervalTreeRawTest, RemoveNonexistent)
	TEST_F (IntervalTreeRawTest, OverlapSearchFound)
	TEST_F (IntervalTreeRawTest, OverlapSearchNotFound)
	TEST_F (IntervalTreeRawTest, AllOverlaps)
	TEST_F (IntervalTreeRawTest, StabQuery)
	TEST_F (IntervalTreeRawTest, PointIntervalQueries)
	TEST_F (IntervalTreeRawTest, MaxEndpointInvariant)
	TEST_F (IntervalTreeRawTest, IteratorOrdering)
	TEST_F (IntervalTreeRawTest, CLRSTextbookExample)
	TEST_F (IntervalTreeRawTest, LargeRandomizedVerification)
	TEST_F (DynIntervalTreeTest, Construction)
	TEST_F (DynIntervalTreeTest, InsertAndSearch)
	TEST_F (DynIntervalTreeTest, InsertByEndpoints)
	TEST_F (DynIntervalTreeTest, Remove)
	TEST_F (DynIntervalTreeTest, RemoveByEndpoints)
	TEST_F (DynIntervalTreeTest, RemoveNonexistent)
	TEST_F (DynIntervalTreeTest, InvalidIntervalThrows)
	TEST_F (DynIntervalTreeTest, OverlapSearch)
	TEST_F (DynIntervalTreeTest, OverlapSearchByEndpoints)
	TEST_F (DynIntervalTreeTest, AllOverlaps)
	TEST_F (DynIntervalTreeTest, FindAllOverlapsByEndpoints)
	TEST_F (DynIntervalTreeTest, Stab)
	TEST_F (DynIntervalTreeTest, FindStab)
	TEST_F (DynIntervalTreeTest, CopyConstruction)
	TEST_F (DynIntervalTreeTest, MoveConstruction)
	TEST_F (DynIntervalTreeTest, CopyAssignment)
	TEST_F (DynIntervalTreeTest, MoveAssignment)
	TEST (IntervalTreeComparatorStateTest, CopyAssignmentPropagatesComparatorState)
	TEST_F (DynIntervalTreeTest, FunctionalForEach)
	TEST_F (DynIntervalTreeTest, FunctionalExists)
	TEST_F (DynIntervalTreeTest, FunctionalFilter)
	TEST_F (DynIntervalTreeTest, InitializerList)
	TEST_F (DynIntervalTreeTest, Verify)
	TEST_F (DynIntervalTreeTest, StlRangeFor)
	TEST (IntervalTreeTypeTest, IntIntervals)
	TEST (IntervalTreeTypeTest, DoubleIntervals)
	TEST (IntervalTreeTypeTest, StringIntervals)
	TEST (IntervalTreeStressTest, InsertRemoveVerify)
	TEST (IntervalTreeStressTest, AllOverlapsBruteForce)

Detailed Description

Comprehensive tests for Interval<T>, Interval_Tree, and DynIntervalTree.

Definition in file interval_tree_test.cc.

Function Documentation

TEST() [1/6]

TEST	(	IntervalTreeComparatorStateTest	,
		CopyAssignmentPropagatesComparatorState
	)

Definition at line 632 of file interval_tree_test.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST() [2/6]

TEST	(	IntervalTreeStressTest	,
		AllOverlapsBruteForce
	)

Definition at line 814 of file interval_tree_test.cc.

References Aleph::divide_and_conquer_partition_dp(), Aleph::DynIntervalTree< T, Compare >::find_all_overlaps(), Aleph::DynIntervalTree< T, Compare >::insert_dup(), and Aleph::DynIntervalTree< T, Compare >::verify().

TEST() [3/6]

TEST	(	IntervalTreeStressTest	,
		InsertRemoveVerify
	)

Definition at line 770 of file interval_tree_test.cc.

References Aleph::DynList< T >::append(), Aleph::divide_and_conquer_partition_dp(), FunctionalMethods< Container, T >::for_each(), Aleph::DynIntervalTree< T, Compare >::insert_dup(), Aleph::Interval< T >::low, Aleph::DynIntervalTree< T, Compare >::remove(), Aleph::DynIntervalTree< T, Compare >::search(), Aleph::DynIntervalTree< T, Compare >::size(), and Aleph::DynIntervalTree< T, Compare >::verify().

TEST() [4/6]

TEST	(	IntervalTreeTypeTest	,
		DoubleIntervals
	)

Definition at line 734 of file interval_tree_test.cc.

References Aleph::divide_and_conquer_partition_dp(), Aleph::DynIntervalTree< T, Compare >::insert(), Aleph::DynIntervalTree< T, Compare >::overlap_search(), Aleph::DynIntervalTree< T, Compare >::size(), and Aleph::DynIntervalTree< T, Compare >::verify().

TEST() [5/6]

TEST	(	IntervalTreeTypeTest	,
		IntIntervals
	)

Definition at line 723 of file interval_tree_test.cc.

References Aleph::divide_and_conquer_partition_dp(), Aleph::DynIntervalTree< T, Compare >::insert(), Aleph::DynIntervalTree< T, Compare >::overlap_search(), and Aleph::DynIntervalTree< T, Compare >::verify().

TEST() [6/6]

TEST	(	IntervalTreeTypeTest	,
		StringIntervals
	)

Definition at line 751 of file interval_tree_test.cc.

References Aleph::divide_and_conquer_partition_dp(), Aleph::DynIntervalTree< T, Compare >::insert(), Aleph::DynIntervalTree< T, Compare >::overlap_search(), Aleph::DynIntervalTree< T, Compare >::size(), and Aleph::DynIntervalTree< T, Compare >::verify().

TEST_F() [1/45]

TEST_F	(	DynIntervalTreeTest	,
		AllOverlaps
	)

Definition at line 532 of file interval_tree_test.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST_F() [2/45]

TEST_F	(	DynIntervalTreeTest	,
		Construction
	)

Definition at line 449 of file interval_tree_test.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST_F() [3/45]

TEST_F	(	DynIntervalTreeTest	,
		CopyAssignment
	)

Definition at line 607 of file interval_tree_test.cc.

References Aleph::divide_and_conquer_partition_dp(), and Aleph::DynIntervalTree< T, Compare >::insert().

TEST_F() [4/45]

TEST_F	(	DynIntervalTreeTest	,
		CopyConstruction
	)

Definition at line 582 of file interval_tree_test.cc.

References Aleph::copy(), and Aleph::divide_and_conquer_partition_dp().

TEST_F() [5/45]

TEST_F	(	DynIntervalTreeTest	,
		FindAllOverlapsByEndpoints
	)

Definition at line 547 of file interval_tree_test.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST_F() [6/45]

TEST_F	(	DynIntervalTreeTest	,
		FindStab
	)

Definition at line 566 of file interval_tree_test.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST_F() [7/45]

TEST_F	(	DynIntervalTreeTest	,
		FunctionalExists
	)

Definition at line 665 of file interval_tree_test.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST_F() [8/45]

TEST_F	(	DynIntervalTreeTest	,
		FunctionalFilter
	)

Definition at line 674 of file interval_tree_test.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST_F() [9/45]

TEST_F	(	DynIntervalTreeTest	,
		FunctionalForEach
	)

Definition at line 654 of file interval_tree_test.cc.

References Aleph::count(), and Aleph::divide_and_conquer_partition_dp().

TEST_F() [10/45]

TEST_F	(	DynIntervalTreeTest	,
		InitializerList
	)

Definition at line 686 of file interval_tree_test.cc.

References Aleph::divide_and_conquer_partition_dp(), Aleph::DynIntervalTree< T, Compare >::size(), and Aleph::DynIntervalTree< T, Compare >::verify().

TEST_F() [11/45]

TEST_F	(	DynIntervalTreeTest	,
		InsertAndSearch
	)

Definition at line 457 of file interval_tree_test.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST_F() [12/45]

TEST_F	(	DynIntervalTreeTest	,
		InsertByEndpoints
	)

Definition at line 472 of file interval_tree_test.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST_F() [13/45]

TEST_F	(	DynIntervalTreeTest	,
		InvalidIntervalThrows
	)

Definition at line 506 of file interval_tree_test.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST_F() [14/45]

TEST_F	(	DynIntervalTreeTest	,
		MoveAssignment
	)

Definition at line 620 of file interval_tree_test.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST_F() [15/45]

TEST_F	(	DynIntervalTreeTest	,
		MoveConstruction
	)

Definition at line 596 of file interval_tree_test.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST_F() [16/45]

TEST_F	(	DynIntervalTreeTest	,
		OverlapSearch
	)

Definition at line 512 of file interval_tree_test.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST_F() [17/45]

TEST_F	(	DynIntervalTreeTest	,
		OverlapSearchByEndpoints
	)

Definition at line 525 of file interval_tree_test.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST_F() [18/45]

TEST_F	(	DynIntervalTreeTest	,
		Remove
	)

Definition at line 480 of file interval_tree_test.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST_F() [19/45]

TEST_F	(	DynIntervalTreeTest	,
		RemoveByEndpoints
	)

Definition at line 492 of file interval_tree_test.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST_F() [20/45]

TEST_F	(	DynIntervalTreeTest	,
		RemoveNonexistent
	)

Definition at line 499 of file interval_tree_test.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST_F() [21/45]

TEST_F	(	DynIntervalTreeTest	,
		Stab
	)

Definition at line 555 of file interval_tree_test.cc.

References Aleph::count(), and Aleph::divide_and_conquer_partition_dp().

TEST_F() [22/45]

TEST_F	(	DynIntervalTreeTest	,
		StlRangeFor
	)

Definition at line 704 of file interval_tree_test.cc.

References Aleph::count(), and Aleph::divide_and_conquer_partition_dp().

TEST_F() [23/45]

TEST_F	(	DynIntervalTreeTest	,
		Verify
	)

Definition at line 693 of file interval_tree_test.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST_F() [24/45]

TEST_F	(	IntervalTreeRawTest	,
		AllOverlaps
	)

Definition at line 280 of file interval_tree_test.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST_F() [25/45]

TEST_F	(	IntervalTreeRawTest	,
		CLRSTextbookExample
	)

Definition at line 364 of file interval_tree_test.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST_F() [26/45]

TEST_F	(	IntervalTreeRawTest	,
		DuplicateInsert
	)

Definition at line 210 of file interval_tree_test.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST_F() [27/45]

TEST_F	(	IntervalTreeRawTest	,
		EmptyTree
	)

Definition at line 179 of file interval_tree_test.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST_F() [28/45]

TEST_F	(	IntervalTreeRawTest	,
		InsertDup
	)

Definition at line 221 of file interval_tree_test.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST_F() [29/45]

TEST_F	(	IntervalTreeRawTest	,
		IteratorOrdering
	)

Definition at line 344 of file interval_tree_test.cc.

References Aleph::and, cmp(), Aleph::divide_and_conquer_partition_dp(), k, and KEY.

TEST_F() [30/45]

TEST_F	(	IntervalTreeRawTest	,
		LargeRandomizedVerification
	)

Definition at line 393 of file interval_tree_test.cc.

References Aleph::divide_and_conquer_partition_dp(), and N.

TEST_F() [31/45]

TEST_F	(	IntervalTreeRawTest	,
		MaxEndpointInvariant
	)

Definition at line 324 of file interval_tree_test.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST_F() [32/45]

TEST_F	(	IntervalTreeRawTest	,
		MultipleInserts
	)

Definition at line 197 of file interval_tree_test.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST_F() [33/45]

TEST_F	(	IntervalTreeRawTest	,
		OverlapSearchFound
	)

Definition at line 256 of file interval_tree_test.cc.

References Aleph::divide_and_conquer_partition_dp(), and KEY.

TEST_F() [34/45]

TEST_F	(	IntervalTreeRawTest	,
		OverlapSearchNotFound
	)

Definition at line 270 of file interval_tree_test.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST_F() [35/45]

TEST_F	(	IntervalTreeRawTest	,
		PointIntervalQueries
	)

Definition at line 314 of file interval_tree_test.cc.

References Aleph::divide_and_conquer_partition_dp(), and KEY.

TEST_F() [36/45]

TEST_F	(	IntervalTreeRawTest	,
		Remove
	)

Definition at line 231 of file interval_tree_test.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST_F() [37/45]

TEST_F	(	IntervalTreeRawTest	,
		RemoveNonexistent
	)

Definition at line 247 of file interval_tree_test.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST_F() [38/45]

TEST_F	(	IntervalTreeRawTest	,
		SingleInsert
	)

Definition at line 188 of file interval_tree_test.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST_F() [39/45]

TEST_F	(	IntervalTreeRawTest	,
		StabQuery
	)

Definition at line 299 of file interval_tree_test.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST_F() [40/45]

TEST_F	(	IntervalTypeTest	,
		Construction
	)

Definition at line 73 of file interval_tree_test.cc.

References Aleph::divide_and_conquer_partition_dp(), Aleph::Interval< T >::high, Aleph::Interval< T >::low, and Aleph::Interval< T >::point().

TEST_F() [41/45]

TEST_F	(	IntervalTypeTest	,
		Containment
	)

Definition at line 114 of file interval_tree_test.cc.

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

TEST_F() [42/45]

TEST_F	(	IntervalTypeTest	,
		Ordering
	)

Definition at line 139 of file interval_tree_test.cc.

References cmp(), and Aleph::divide_and_conquer_partition_dp().

TEST_F() [43/45]

TEST_F	(	IntervalTypeTest	,
		OverlapDetection
	)

Definition at line 96 of file interval_tree_test.cc.

References Aleph::divide_and_conquer_partition_dp(), and Aleph::Interval< T >::overlaps().

TEST_F() [44/45]

TEST_F	(	IntervalTypeTest	,
		PointIntervals
	)

Definition at line 124 of file interval_tree_test.cc.

References Aleph::divide_and_conquer_partition_dp(), and Aleph::Interval< T >::point().

TEST_F() [45/45]

TEST_F	(	IntervalTypeTest	,
		Validity
	)

Definition at line 84 of file interval_tree_test.cc.

References Aleph::divide_and_conquer_partition_dp(), and Aleph::Interval< T >::is_valid().