tpl_cartesian_tree_test.cc File Reference

Unit tests for Gen_Cartesian_Tree, Gen_Euler_Tour_LCA, and Gen_Cartesian_Tree_RMQ. More...

#include <gtest/gtest.h>
#include <tpl_cartesian_tree.H>
#include <tpl_sparse_table.H>
#include <algorithm>
#include <cstddef>
#include <numeric>
#include <random>
#include <vector>

Include dependency graph for tpl_cartesian_tree_test.cc:

Go to the source code of this file.

Functions
	TEST (GenCartesianTree, Empty)
	TEST (GenCartesianTree, SingleElement)
	TEST (GenCartesianTree, TwoElements)
	TEST (GenCartesianTree, HeapProperty)
	TEST (GenCartesianTree, InorderProperty)
	TEST (GenCartesianTree, ManualSmall)
	TEST (GenCartesianTree, DuplicateValues)
	TEST (GenCartesianTree, Sorted)
	TEST (GenCartesianTree, ReverseSorted)
	TEST (GenCartesianTree, AllEqual)
	TEST (GenCartesianTree, CustomComparatorMax)
	TEST (GenCartesianTree, FromArray)
	TEST (GenCartesianTree, FromVector)
	TEST (GenCartesianTree, FromInitList)
	TEST (GenCartesianTree, FromDynList)
	TEST (GenCartesianTree, Height)
	TEST (GenCartesianTree, CopyMoveSwap)
	TEST (GenCartesianTree, BoundsChecking)
	TEST (GenCartesianTree, StressRandom)
	TEST (EulerTourLCA, Empty)
	TEST (EulerTourLCA, SingleElement)
	TEST (EulerTourLCA, EulerTourSize)
	TEST (EulerTourLCA, LcaSelf)
	TEST (EulerTourLCA, LcaRootChildren)
	TEST (EulerTourLCA, ManualSmall)
	TEST (EulerTourLCA, DepthOf)
	TEST (EulerTourLCA, Distance)
	TEST (EulerTourLCA, LcaSymmetry)
	TEST (EulerTourLCA, LcaBoundsCheck)
	TEST (EulerTourLCA, StressVsBruteForce)
	TEST (CartesianTreeRMQ, Empty)
	TEST (CartesianTreeRMQ, SingleElement)
	TEST (CartesianTreeRMQ, QueryEntireRange)
	TEST (CartesianTreeRMQ, QuerySingleElement)
	TEST (CartesianTreeRMQ, QueryVsSparseTable)
	TEST (CartesianTreeRMQ, QueryIdx)
	TEST (CartesianTreeRMQ, MaxVariant)
	TEST (CartesianTreeRMQ, StressRandomVsBruteForce)
	TEST (CartesianTreeRMQ, BoundsCheck)

Detailed Description

Unit tests for Gen_Cartesian_Tree, Gen_Euler_Tour_LCA, and Gen_Cartesian_Tree_RMQ.

Definition in file tpl_cartesian_tree_test.cc.

Function Documentation

TEST() [1/39]

TEST	(	CartesianTreeRMQ	,
		BoundsCheck
	)

Definition at line 592 of file tpl_cartesian_tree_test.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST() [2/39]

TEST	(	CartesianTreeRMQ	,
		Empty
	)

Definition at line 492 of file tpl_cartesian_tree_test.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST() [3/39]

TEST	(	CartesianTreeRMQ	,
		MaxVariant
	)

Definition at line 557 of file tpl_cartesian_tree_test.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST() [4/39]

TEST	(	CartesianTreeRMQ	,
		QueryEntireRange
	)

Definition at line 509 of file tpl_cartesian_tree_test.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST() [5/39]

TEST	(	CartesianTreeRMQ	,
		QueryIdx
	)

Definition at line 543 of file tpl_cartesian_tree_test.cc.

References Aleph::divide_and_conquer_partition_dp(), and Aleph::Gen_Cartesian_Tree_RMQ< T, Comp >::query_idx().

TEST() [6/39]

TEST	(	CartesianTreeRMQ	,
		QuerySingleElement
	)

Definition at line 516 of file tpl_cartesian_tree_test.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST() [7/39]

TEST	(	CartesianTreeRMQ	,
		QueryVsSparseTable
	)

Definition at line 523 of file tpl_cartesian_tree_test.cc.

References Aleph::divide_and_conquer_partition_dp(), l, N, Aleph::Gen_Sparse_Table< T, Op >::query(), r, and rng.

TEST() [8/39]

TEST	(	CartesianTreeRMQ	,
		SingleElement
	)

Definition at line 500 of file tpl_cartesian_tree_test.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST() [9/39]

TEST	(	CartesianTreeRMQ	,
		StressRandomVsBruteForce
	)

Definition at line 565 of file tpl_cartesian_tree_test.cc.

References brute_min(), Aleph::divide_and_conquer_partition_dp(), l, N, r, and rng.

TEST() [10/39]

TEST	(	EulerTourLCA	,
		DepthOf
	)

Definition at line 416 of file tpl_cartesian_tree_test.cc.

References Aleph::Gen_Euler_Tour_LCA< T, Comp >::depth_of(), and Aleph::divide_and_conquer_partition_dp().

TEST() [11/39]

TEST	(	EulerTourLCA	,
		Distance
	)

Definition at line 429 of file tpl_cartesian_tree_test.cc.

References Aleph::Gen_Euler_Tour_LCA< T, Comp >::distance(), Aleph::divide_and_conquer_partition_dp(), and Aleph::Gen_Euler_Tour_LCA< T, Comp >::size().

TEST() [12/39]

TEST	(	EulerTourLCA	,
		Empty
	)

Definition at line 351 of file tpl_cartesian_tree_test.cc.

References Aleph::divide_and_conquer_partition_dp(), Aleph::Gen_Euler_Tour_LCA< T, Comp >::is_empty(), and Aleph::Gen_Euler_Tour_LCA< T, Comp >::size().

TEST() [13/39]

TEST	(	EulerTourLCA	,
		EulerTourSize
	)

Definition at line 368 of file tpl_cartesian_tree_test.cc.

References Aleph::divide_and_conquer_partition_dp(), and Aleph::Gen_Euler_Tour_LCA< T, Comp >::euler_tour_size().

TEST() [14/39]

TEST	(	EulerTourLCA	,
		LcaBoundsCheck
	)

Definition at line 454 of file tpl_cartesian_tree_test.cc.

References Aleph::Gen_Euler_Tour_LCA< T, Comp >::depth_of(), Aleph::divide_and_conquer_partition_dp(), and Aleph::Gen_Euler_Tour_LCA< T, Comp >::lca().

TEST() [15/39]

TEST	(	EulerTourLCA	,
		LcaRootChildren
	)

Definition at line 382 of file tpl_cartesian_tree_test.cc.

References Aleph::divide_and_conquer_partition_dp(), Aleph::Gen_Euler_Tour_LCA< T, Comp >::lca(), r, Aleph::Gen_Cartesian_Tree< T, Comp >::root(), and Aleph::Gen_Euler_Tour_LCA< T, Comp >::tree().

TEST() [16/39]

TEST	(	EulerTourLCA	,
		LcaSelf
	)

Definition at line 375 of file tpl_cartesian_tree_test.cc.

References Aleph::divide_and_conquer_partition_dp(), Aleph::Gen_Euler_Tour_LCA< T, Comp >::lca(), and Aleph::Gen_Euler_Tour_LCA< T, Comp >::size().

TEST() [17/39]

TEST	(	EulerTourLCA	,
		LcaSymmetry
	)

Definition at line 445 of file tpl_cartesian_tree_test.cc.

References Aleph::divide_and_conquer_partition_dp(), Aleph::Gen_Euler_Tour_LCA< T, Comp >::lca(), and Aleph::Gen_Euler_Tour_LCA< T, Comp >::size().

TEST() [18/39]

TEST	(	EulerTourLCA	,
		ManualSmall
	)

Definition at line 395 of file tpl_cartesian_tree_test.cc.

References Aleph::divide_and_conquer_partition_dp(), and Aleph::Gen_Euler_Tour_LCA< T, Comp >::lca().

TEST() [19/39]

TEST	(	EulerTourLCA	,
		SingleElement
	)

Definition at line 359 of file tpl_cartesian_tree_test.cc.

References Aleph::Gen_Euler_Tour_LCA< T, Comp >::depth_of(), Aleph::Gen_Euler_Tour_LCA< T, Comp >::distance(), Aleph::divide_and_conquer_partition_dp(), Aleph::Gen_Euler_Tour_LCA< T, Comp >::lca(), and Aleph::Gen_Euler_Tour_LCA< T, Comp >::size().

TEST() [20/39]

TEST	(	EulerTourLCA	,
		StressVsBruteForce
	)

Definition at line 462 of file tpl_cartesian_tree_test.cc.

References Aleph::divide_and_conquer_partition_dp(), Aleph::Gen_Euler_Tour_LCA< T, Comp >::lca(), N, rng, Aleph::Gen_Euler_Tour_LCA< T, Comp >::tree(), and w.

TEST() [21/39]

TEST	(	GenCartesianTree	,
		AllEqual
	)

Definition at line 239 of file tpl_cartesian_tree_test.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST() [22/39]

TEST	(	GenCartesianTree	,
		BoundsChecking
	)

Definition at line 319 of file tpl_cartesian_tree_test.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST() [23/39]

TEST	(	GenCartesianTree	,
		CopyMoveSwap
	)

Definition at line 302 of file tpl_cartesian_tree_test.cc.

References Aleph::divide_and_conquer_partition_dp(), and Aleph::Gen_Cartesian_Tree< T, Comp >::swap().

TEST() [24/39]

TEST	(	GenCartesianTree	,
		CustomComparatorMax
	)

Definition at line 246 of file tpl_cartesian_tree_test.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST() [25/39]

TEST	(	GenCartesianTree	,
		DuplicateValues
	)

Definition at line 210 of file tpl_cartesian_tree_test.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST() [26/39]

TEST	(	GenCartesianTree	,
		Empty
	)

Definition at line 136 of file tpl_cartesian_tree_test.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST() [27/39]

TEST	(	GenCartesianTree	,
		FromArray
	)

Definition at line 255 of file tpl_cartesian_tree_test.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST() [28/39]

TEST	(	GenCartesianTree	,
		FromDynList
	)

Definition at line 281 of file tpl_cartesian_tree_test.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST() [29/39]

TEST	(	GenCartesianTree	,
		FromInitList
	)

Definition at line 273 of file tpl_cartesian_tree_test.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST() [30/39]

TEST	(	GenCartesianTree	,
		FromVector
	)

Definition at line 264 of file tpl_cartesian_tree_test.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST() [31/39]

TEST	(	GenCartesianTree	,
		HeapProperty
	)

Definition at line 175 of file tpl_cartesian_tree_test.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST() [32/39]

TEST	(	GenCartesianTree	,
		Height
	)

Definition at line 290 of file tpl_cartesian_tree_test.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST() [33/39]

TEST	(	GenCartesianTree	,
		InorderProperty
	)

Definition at line 181 of file tpl_cartesian_tree_test.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST() [34/39]

TEST	(	GenCartesianTree	,
		ManualSmall
	)

Definition at line 187 of file tpl_cartesian_tree_test.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST() [35/39]

TEST	(	GenCartesianTree	,
		ReverseSorted
	)

Definition at line 229 of file tpl_cartesian_tree_test.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST() [36/39]

TEST	(	GenCartesianTree	,
		SingleElement
	)

Definition at line 148 of file tpl_cartesian_tree_test.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST() [37/39]

TEST	(	GenCartesianTree	,
		Sorted
	)

Definition at line 219 of file tpl_cartesian_tree_test.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST() [38/39]

TEST	(	GenCartesianTree	,
		StressRandom
	)

Definition at line 330 of file tpl_cartesian_tree_test.cc.

References Aleph::divide_and_conquer_partition_dp(), N, and rng.

TEST() [39/39]

TEST	(	GenCartesianTree	,
		TwoElements
	)

Definition at line 164 of file tpl_cartesian_tree_test.cc.

References Aleph::divide_and_conquer_partition_dp().