dp_optimizations_test.cc File Reference

Tests for DP_Optimizations.H. More...

#include <gtest/gtest.h>
#include <limits>
#include <random>
#include <chrono>
#include <numeric>
#include <ctime>
#include <cstdlib>
#include <DP_Optimizations.H>

Include dependency graph for dp_optimizations_test.cc:

Go to the source code of this file.

Functions
	TEST (DPOptimizations, DivideConquerPartitionMatchesBruteForce)
	TEST (DPOptimizations, DivideConquerPartitionEdgeCases)
	TEST (DPOptimizations, KnuthOptimalMergeMatchesBruteForce)
	TEST (DPOptimizations, KnuthOptimalMergeEdgeCases)
	TEST (DPOptimizations, ConvexHullTrickMatchesBruteForce)
	TEST (DPOptimizations, ConvexHullTrickSlopeChecksAndDuplicates)
	TEST (DPOptimizations, LiChaoMatchesBruteForce)
	TEST (DPOptimizations, LiChaoDomainAndEmptyChecks)
	TEST (DPOptimizations, MonotoneQueueDPMatchesBruteForce)
	TEST (DPOptimizations, MonotoneQueueDPEdgeCases)
	TEST (DPOptimizations, WeightedSquaredDistanceMatchesBruteForce)
	TEST (DPOptimizations, WeightedSquaredDistanceRandomVsBrute)
	TEST (DPOptimizations, WeightedSquaredDistanceValidatesSizes)
	TEST (DPOptimizations, DivideConquerPartitionPerf)

Detailed Description

Tests for DP_Optimizations.H.

Definition in file dp_optimizations_test.cc.

Function Documentation

TEST() [1/14]

TEST	(	DPOptimizations	,
		ConvexHullTrickMatchesBruteForce
	)

Definition at line 257 of file dp_optimizations_test.cc.

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

TEST() [2/14]

TEST	(	DPOptimizations	,
		ConvexHullTrickSlopeChecksAndDuplicates
	)

Definition at line 297 of file dp_optimizations_test.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST() [3/14]

TEST	(	DPOptimizations	,
		DivideConquerPartitionEdgeCases
	)

Definition at line 201 of file dp_optimizations_test.cc.

References Aleph::divide_and_conquer_partition_dp(), and k.

TEST() [4/14]

TEST	(	DPOptimizations	,
		DivideConquerPartitionMatchesBruteForce
	)

Definition at line 163 of file dp_optimizations_test.cc.

References Aleph::Array< T >::append(), Aleph::Array< T >::create(), Aleph::divide_and_conquer_partition_dp(), k, Aleph::Array< T >::reserve(), and rng.

TEST() [5/14]

TEST	(	DPOptimizations	,
		DivideConquerPartitionPerf
	)

Definition at line 438 of file dp_optimizations_test.cc.

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

TEST() [6/14]

TEST	(	DPOptimizations	,
		KnuthOptimalMergeEdgeCases
	)

Definition at line 246 of file dp_optimizations_test.cc.

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

TEST() [7/14]

TEST	(	DPOptimizations	,
		KnuthOptimalMergeMatchesBruteForce
	)

Definition at line 219 of file dp_optimizations_test.cc.

References Aleph::divide_and_conquer_partition_dp(), Aleph::optimal_merge_knuth(), Aleph::Array< T >::reserve(), rng, and w.

TEST() [8/14]

TEST	(	DPOptimizations	,
		LiChaoDomainAndEmptyChecks
	)

Definition at line 341 of file dp_optimizations_test.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST() [9/14]

TEST	(	DPOptimizations	,
		LiChaoMatchesBruteForce
	)

Definition at line 314 of file dp_optimizations_test.cc.

References OhashCommon< HashTbl, Key >::append(), Aleph::divide_and_conquer_partition_dp(), m, and rng.

TEST() [10/14]

TEST	(	DPOptimizations	,
		MonotoneQueueDPEdgeCases
	)

Definition at line 379 of file dp_optimizations_test.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST() [11/14]

TEST	(	DPOptimizations	,
		MonotoneQueueDPMatchesBruteForce
	)

Definition at line 352 of file dp_optimizations_test.cc.

References Aleph::Array< T >::append(), Aleph::divide_and_conquer_partition_dp(), Aleph::Array< T >::reserve(), rng, Aleph::Array< T >::size(), and w.

TEST() [12/14]

TEST	(	DPOptimizations	,
		WeightedSquaredDistanceMatchesBruteForce
	)

Definition at line 394 of file dp_optimizations_test.cc.

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

TEST() [13/14]

TEST	(	DPOptimizations	,
		WeightedSquaredDistanceRandomVsBrute
	)

Definition at line 406 of file dp_optimizations_test.cc.

References Aleph::divide_and_conquer_partition_dp(), Aleph::min_weighted_squared_distance_1d(), Aleph::Array< T >::reserve(), and rng.

TEST() [14/14]

TEST	(	DPOptimizations	,
		WeightedSquaredDistanceValidatesSizes
	)

Definition at line 431 of file dp_optimizations_test.cc.

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