tpl_segment_tree_test.cc File Reference

Tests for Gen_Segment_Tree, Lazy variants, and Segment_Tree_Beats. More...

#include <gtest/gtest.h>
#include <tpl_segment_tree.H>
#include <algorithm>
#include <cstddef>
#include <numeric>
#include <random>
#include <utility>
#include <vector>

Include dependency graph for tpl_segment_tree_test.cc:

Go to the source code of this file.

Functions
	TEST (GenSegmentTree, EmptyConstruction)
	TEST (GenSegmentTree, UniformConstruction)
	TEST (GenSegmentTree, SumAgainstBruteForce)
	TEST (GenSegmentTree, MinAgainstBruteForce)
	TEST (GenSegmentTree, MaxAgainstBruteForce)
	TEST (GenSegmentTree, PointUpdate)
	TEST (GenSegmentTree, SetValue)
	TEST (GenSegmentTree, ConstructorsAllContainers)
	TEST (GenSegmentTree, CustomXorMonoid)
	TEST (GenSegmentTree, CustomGcdMonoid)
	TEST (GenSegmentTree, CopyMoveSwap)
	TEST (GenSegmentTree, BoundsChecking)
	TEST (GenSegmentTree, OneElement)
	TEST (GenSegmentTree, TwoElements)
	TEST (GenSegmentTree, Values)
	TEST (GenSegmentTree, StressRandomSumUpdates)
	TEST (GenSegmentTree, StressRandomMinUpdates)
	TEST (SegmentTreeTypedefs, SumSegmentTree)
	TEST (SegmentTreeTypedefs, MinSegmentTree)
	TEST (SegmentTreeTypedefs, MaxSegmentTree)
	TEST (SegmentTreeTypedefs, DoubleSum)
	TEST (LazySegmentTree, EmptyConstruction)
	TEST (LazySegmentTree, RangeUpdateSum)
	TEST (LazySegmentTree, OverlappingRangeUpdates)
	TEST (LazySegmentTree, PointUpdate)
	TEST (LazySegmentTree, SetValue)
	TEST (LazySegmentTree, ConstructorsAllContainers)
	TEST (LazySegmentTree, CopyMoveSwap)
	TEST (LazySegmentTree, BoundsChecking)
	TEST (LazySegmentTree, OneElement)
	TEST (LazySegmentTree, StressRandom)
	TEST (LazyPolicies, AddMin)
	TEST (LazyPolicies, AddMax)
	TEST (LazyPolicies, AssignSum)
	TEST (LazyPolicies, AddMinStress)
	TEST (SegmentTreeBeats, EmptyConstruction)
	TEST (SegmentTreeBeats, BasicChmin)
	TEST (SegmentTreeBeats, BasicChmax)
	TEST (SegmentTreeBeats, InterleavedChminChmax)
	TEST (SegmentTreeBeats, SumAfterOps)
	TEST (SegmentTreeBeats, OneElement)
	TEST (SegmentTreeBeats, CopyMoveSwap)
	TEST (SegmentTreeBeats, BoundsChecking)
	TEST (SegmentTreeBeats, StressBruteForce)
	TEST (SegmentTreeBeats, Values)

Detailed Description

Tests for Gen_Segment_Tree, Lazy variants, and Segment_Tree_Beats.

Definition in file tpl_segment_tree_test.cc.

Function Documentation

TEST() [1/45]

TEST	(	GenSegmentTree	,
		BoundsChecking
	)

Definition at line 254 of file tpl_segment_tree_test.cc.

References Aleph::divide_and_conquer_partition_dp(), Aleph::Gen_Segment_Tree< T, Op >::get(), Aleph::Gen_Segment_Tree< T, Op >::query(), Aleph::Gen_Segment_Tree< T, Op >::set(), and Aleph::Gen_Segment_Tree< T, Op >::update().

TEST() [2/45]

TEST	(	GenSegmentTree	,
		ConstructorsAllContainers
	)

Definition at line 175 of file tpl_segment_tree_test.cc.

References Aleph::Array< T >::append(), Aleph::DynList< T >::append(), brute_sum(), Aleph::divide_and_conquer_partition_dp(), l, r, and Aleph::HTList::size().

TEST() [3/45]

TEST	(	GenSegmentTree	,
		CopyMoveSwap
	)

Definition at line 232 of file tpl_segment_tree_test.cc.

References Aleph::copy(), Aleph::divide_and_conquer_partition_dp(), and Aleph::Gen_Segment_Tree< T, Op >::swap().

TEST() [4/45]

TEST	(	GenSegmentTree	,
		CustomGcdMonoid
	)

Definition at line 222 of file tpl_segment_tree_test.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST() [5/45]

TEST	(	GenSegmentTree	,
		CustomXorMonoid
	)

Definition at line 204 of file tpl_segment_tree_test.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST() [6/45]

TEST	(	GenSegmentTree	,
		EmptyConstruction
	)

Definition at line 98 of file tpl_segment_tree_test.cc.

References Aleph::divide_and_conquer_partition_dp(), Aleph::Gen_Segment_Tree< T, Op >::get(), Aleph::Gen_Segment_Tree< T, Op >::is_empty(), Aleph::Gen_Segment_Tree< T, Op >::query(), and Aleph::Gen_Segment_Tree< T, Op >::size().

TEST() [7/45]

TEST	(	GenSegmentTree	,
		MaxAgainstBruteForce
	)

Definition at line 142 of file tpl_segment_tree_test.cc.

References brute_max(), Aleph::divide_and_conquer_partition_dp(), l, Aleph::Gen_Segment_Tree< T, Op >::query(), r, and Aleph::HTList::size().

TEST() [8/45]

TEST	(	GenSegmentTree	,
		MinAgainstBruteForce
	)

Definition at line 132 of file tpl_segment_tree_test.cc.

References brute_min(), Aleph::divide_and_conquer_partition_dp(), l, Aleph::Gen_Segment_Tree< T, Op >::query(), r, and Aleph::HTList::size().

TEST() [9/45]

TEST	(	GenSegmentTree	,
		OneElement
	)

Definition at line 265 of file tpl_segment_tree_test.cc.

References Aleph::divide_and_conquer_partition_dp(), Aleph::Gen_Segment_Tree< T, Op >::get(), Aleph::Gen_Segment_Tree< T, Op >::query(), Aleph::Gen_Segment_Tree< T, Op >::set(), Aleph::Gen_Segment_Tree< T, Op >::size(), and Aleph::Gen_Segment_Tree< T, Op >::update().

TEST() [10/45]

TEST	(	GenSegmentTree	,
		PointUpdate
	)

Definition at line 152 of file tpl_segment_tree_test.cc.

References Aleph::divide_and_conquer_partition_dp(), Aleph::Gen_Segment_Tree< T, Op >::get(), Aleph::Gen_Segment_Tree< T, Op >::query(), and Aleph::Gen_Segment_Tree< T, Op >::update().

TEST() [11/45]

TEST	(	GenSegmentTree	,
		SetValue
	)

Definition at line 162 of file tpl_segment_tree_test.cc.

References Aleph::divide_and_conquer_partition_dp(), Aleph::Gen_Segment_Tree< T, Op >::get(), Aleph::Gen_Segment_Tree< T, Op >::query(), and Aleph::Gen_Segment_Tree< T, Op >::set().

TEST() [12/45]

TEST	(	GenSegmentTree	,
		StressRandomMinUpdates
	)

Definition at line 341 of file tpl_segment_tree_test.cc.

References brute_min(), Aleph::divide_and_conquer_partition_dp(), N, Aleph::Gen_Segment_Tree< T, Op >::query(), rng, and Aleph::Gen_Segment_Tree< T, Op >::set().

TEST() [13/45]

TEST	(	GenSegmentTree	,
		StressRandomSumUpdates
	)

Definition at line 305 of file tpl_segment_tree_test.cc.

References brute_sum(), Aleph::divide_and_conquer_partition_dp(), N, Aleph::Gen_Segment_Tree< T, Op >::query(), rng, and Aleph::Gen_Segment_Tree< T, Op >::update().

TEST() [14/45]

TEST	(	GenSegmentTree	,
		SumAgainstBruteForce
	)

Definition at line 122 of file tpl_segment_tree_test.cc.

References brute_sum(), Aleph::divide_and_conquer_partition_dp(), l, Aleph::Gen_Segment_Tree< T, Op >::query(), r, and Aleph::HTList::size().

TEST() [15/45]

TEST	(	GenSegmentTree	,
		TwoElements
	)

Definition at line 280 of file tpl_segment_tree_test.cc.

References Aleph::divide_and_conquer_partition_dp(), Aleph::Gen_Segment_Tree< T, Op >::query(), and Aleph::Gen_Segment_Tree< T, Op >::set().

TEST() [16/45]

TEST	(	GenSegmentTree	,
		UniformConstruction
	)

Definition at line 108 of file tpl_segment_tree_test.cc.

References Aleph::divide_and_conquer_partition_dp(), Aleph::Gen_Segment_Tree< T, Op >::get(), Aleph::Gen_Segment_Tree< T, Op >::is_empty(), Aleph::Gen_Segment_Tree< T, Op >::query(), and Aleph::Gen_Segment_Tree< T, Op >::size().

TEST() [17/45]

TEST	(	GenSegmentTree	,
		Values
	)

Definition at line 292 of file tpl_segment_tree_test.cc.

References Aleph::divide_and_conquer_partition_dp(), and Aleph::Gen_Segment_Tree< T, Op >::values().

TEST() [18/45]

TEST	(	LazyPolicies	,
		AddMax
	)

Definition at line 591 of file tpl_segment_tree_test.cc.

References Aleph::divide_and_conquer_partition_dp(), Aleph::Gen_Lazy_Segment_Tree< Policy >::query(), and Aleph::Gen_Lazy_Segment_Tree< Policy >::update().

TEST() [19/45]

TEST	(	LazyPolicies	,
		AddMin
	)

Definition at line 581 of file tpl_segment_tree_test.cc.

References Aleph::divide_and_conquer_partition_dp(), Aleph::Gen_Lazy_Segment_Tree< Policy >::query(), and Aleph::Gen_Lazy_Segment_Tree< Policy >::update().

TEST() [20/45]

TEST	(	LazyPolicies	,
		AddMinStress
	)

Definition at line 619 of file tpl_segment_tree_test.cc.

References brute_min(), Aleph::divide_and_conquer_partition_dp(), N, Aleph::Gen_Lazy_Segment_Tree< Policy >::query(), rng, and Aleph::Gen_Lazy_Segment_Tree< Policy >::update().

TEST() [21/45]

TEST	(	LazyPolicies	,
		AssignSum
	)

Definition at line 601 of file tpl_segment_tree_test.cc.

References Aleph::divide_and_conquer_partition_dp(), Aleph::Gen_Lazy_Segment_Tree< Policy >::get(), Aleph::Gen_Lazy_Segment_Tree< Policy >::query(), and Aleph::Gen_Lazy_Segment_Tree< Policy >::update().

TEST() [22/45]

TEST	(	LazySegmentTree	,
		BoundsChecking
	)

Definition at line 524 of file tpl_segment_tree_test.cc.

References Aleph::divide_and_conquer_partition_dp(), Aleph::Gen_Lazy_Segment_Tree< Policy >::query(), Aleph::Gen_Lazy_Segment_Tree< Policy >::set(), and Aleph::Gen_Lazy_Segment_Tree< Policy >::update().

TEST() [23/45]

TEST	(	LazySegmentTree	,
		ConstructorsAllContainers
	)

Definition at line 476 of file tpl_segment_tree_test.cc.

References Aleph::Array< T >::append(), Aleph::DynList< T >::append(), brute_sum(), Aleph::divide_and_conquer_partition_dp(), l, r, and Aleph::HTList::size().

TEST() [24/45]

TEST	(	LazySegmentTree	,
		CopyMoveSwap
	)

Definition at line 505 of file tpl_segment_tree_test.cc.

References Aleph::copy(), Aleph::divide_and_conquer_partition_dp(), and Aleph::Gen_Lazy_Segment_Tree< Policy >::swap().

TEST() [25/45]

TEST	(	LazySegmentTree	,
		EmptyConstruction
	)

Definition at line 419 of file tpl_segment_tree_test.cc.

References Aleph::divide_and_conquer_partition_dp(), Aleph::Gen_Lazy_Segment_Tree< Policy >::is_empty(), Aleph::Gen_Lazy_Segment_Tree< Policy >::query(), and Aleph::Gen_Lazy_Segment_Tree< Policy >::size().

TEST() [26/45]

TEST	(	LazySegmentTree	,
		OneElement
	)

Definition at line 534 of file tpl_segment_tree_test.cc.

References Aleph::divide_and_conquer_partition_dp(), Aleph::Gen_Lazy_Segment_Tree< Policy >::get(), Aleph::Gen_Lazy_Segment_Tree< Policy >::set(), and Aleph::Gen_Lazy_Segment_Tree< Policy >::update().

TEST() [27/45]

TEST	(	LazySegmentTree	,
		OverlappingRangeUpdates
	)

Definition at line 441 of file tpl_segment_tree_test.cc.

References Aleph::divide_and_conquer_partition_dp(), Aleph::Gen_Lazy_Segment_Tree< Policy >::get(), Aleph::Gen_Lazy_Segment_Tree< Policy >::query(), and Aleph::Gen_Lazy_Segment_Tree< Policy >::update().

TEST() [28/45]

TEST	(	LazySegmentTree	,
		PointUpdate
	)

Definition at line 458 of file tpl_segment_tree_test.cc.

References Aleph::divide_and_conquer_partition_dp(), Aleph::Gen_Lazy_Segment_Tree< Policy >::get(), Aleph::Gen_Lazy_Segment_Tree< Policy >::point_update(), and Aleph::Gen_Lazy_Segment_Tree< Policy >::query().

TEST() [29/45]

TEST	(	LazySegmentTree	,
		RangeUpdateSum
	)

Definition at line 428 of file tpl_segment_tree_test.cc.

References Aleph::divide_and_conquer_partition_dp(), Aleph::Gen_Lazy_Segment_Tree< Policy >::get(), Aleph::Gen_Lazy_Segment_Tree< Policy >::query(), and Aleph::Gen_Lazy_Segment_Tree< Policy >::update().

TEST() [30/45]

TEST	(	LazySegmentTree	,
		SetValue
	)

Definition at line 467 of file tpl_segment_tree_test.cc.

References Aleph::divide_and_conquer_partition_dp(), Aleph::Gen_Lazy_Segment_Tree< Policy >::get(), Aleph::Gen_Lazy_Segment_Tree< Policy >::query(), and Aleph::Gen_Lazy_Segment_Tree< Policy >::set().

TEST() [31/45]

TEST	(	LazySegmentTree	,
		StressRandom
	)

Definition at line 545 of file tpl_segment_tree_test.cc.

References brute_sum(), Aleph::divide_and_conquer_partition_dp(), N, Aleph::Gen_Lazy_Segment_Tree< Policy >::query(), rng, and Aleph::Gen_Lazy_Segment_Tree< Policy >::update().

TEST() [32/45]

TEST	(	SegmentTreeBeats	,
		BasicChmax
	)

Definition at line 675 of file tpl_segment_tree_test.cc.

References Aleph::Segment_Tree_Beats< T >::chmax(), Aleph::divide_and_conquer_partition_dp(), Aleph::Segment_Tree_Beats< T >::query_max(), Aleph::Segment_Tree_Beats< T >::query_min(), and Aleph::Segment_Tree_Beats< T >::query_sum().

TEST() [33/45]

TEST	(	SegmentTreeBeats	,
		BasicChmin
	)

Definition at line 664 of file tpl_segment_tree_test.cc.

References Aleph::Segment_Tree_Beats< T >::chmin(), Aleph::divide_and_conquer_partition_dp(), Aleph::Segment_Tree_Beats< T >::query_max(), Aleph::Segment_Tree_Beats< T >::query_min(), and Aleph::Segment_Tree_Beats< T >::query_sum().

TEST() [34/45]

TEST	(	SegmentTreeBeats	,
		BoundsChecking
	)

Definition at line 743 of file tpl_segment_tree_test.cc.

References Aleph::Segment_Tree_Beats< T >::chmax(), Aleph::Segment_Tree_Beats< T >::chmin(), Aleph::divide_and_conquer_partition_dp(), and Aleph::Segment_Tree_Beats< T >::query_sum().

TEST() [35/45]

TEST	(	SegmentTreeBeats	,
		CopyMoveSwap
	)

Definition at line 724 of file tpl_segment_tree_test.cc.

References Aleph::copy(), Aleph::divide_and_conquer_partition_dp(), and Aleph::Segment_Tree_Beats< T >::swap().

TEST() [36/45]

TEST	(	SegmentTreeBeats	,
		EmptyConstruction
	)

Definition at line 655 of file tpl_segment_tree_test.cc.

References Aleph::divide_and_conquer_partition_dp(), Aleph::Segment_Tree_Beats< T >::is_empty(), Aleph::Segment_Tree_Beats< T >::query_sum(), and Aleph::Segment_Tree_Beats< T >::size().

TEST() [37/45]

TEST	(	SegmentTreeBeats	,
		InterleavedChminChmax
	)

Definition at line 686 of file tpl_segment_tree_test.cc.

References Aleph::Segment_Tree_Beats< T >::chmax(), Aleph::Segment_Tree_Beats< T >::chmin(), Aleph::divide_and_conquer_partition_dp(), Aleph::Segment_Tree_Beats< T >::query_max(), Aleph::Segment_Tree_Beats< T >::query_min(), and Aleph::Segment_Tree_Beats< T >::query_sum().

TEST() [38/45]

TEST	(	SegmentTreeBeats	,
		OneElement
	)

Definition at line 709 of file tpl_segment_tree_test.cc.

References Aleph::Segment_Tree_Beats< T >::chmax(), Aleph::Segment_Tree_Beats< T >::chmin(), Aleph::divide_and_conquer_partition_dp(), Aleph::Segment_Tree_Beats< T >::get(), Aleph::Segment_Tree_Beats< T >::query_max(), Aleph::Segment_Tree_Beats< T >::query_min(), and Aleph::Segment_Tree_Beats< T >::query_sum().

TEST() [39/45]

TEST	(	SegmentTreeBeats	,
		StressBruteForce
	)

Definition at line 752 of file tpl_segment_tree_test.cc.

References brute_max(), brute_min(), brute_sum(), Aleph::Segment_Tree_Beats< T >::chmax(), Aleph::Segment_Tree_Beats< T >::chmin(), Aleph::divide_and_conquer_partition_dp(), Aleph::Segment_Tree_Beats< T >::get(), N, Aleph::Segment_Tree_Beats< T >::query_max(), Aleph::Segment_Tree_Beats< T >::query_min(), Aleph::Segment_Tree_Beats< T >::query_sum(), and rng.

TEST() [40/45]

TEST	(	SegmentTreeBeats	,
		SumAfterOps
	)

Definition at line 698 of file tpl_segment_tree_test.cc.

References Aleph::Segment_Tree_Beats< T >::chmax(), Aleph::Segment_Tree_Beats< T >::chmin(), Aleph::divide_and_conquer_partition_dp(), and Aleph::Segment_Tree_Beats< T >::query_sum().

TEST() [41/45]

TEST	(	SegmentTreeBeats	,
		Values
	)

Definition at line 811 of file tpl_segment_tree_test.cc.

References Aleph::Segment_Tree_Beats< T >::chmin(), Aleph::divide_and_conquer_partition_dp(), and Aleph::Segment_Tree_Beats< T >::values().

TEST() [42/45]

TEST	(	SegmentTreeTypedefs	,
		DoubleSum
	)

Definition at line 407 of file tpl_segment_tree_test.cc.

References Aleph::divide_and_conquer_partition_dp(), Aleph::Gen_Segment_Tree< T, Op >::query(), and Aleph::Gen_Segment_Tree< T, Op >::update().

TEST() [43/45]

TEST	(	SegmentTreeTypedefs	,
		MaxSegmentTree
	)

Definition at line 398 of file tpl_segment_tree_test.cc.

References Aleph::divide_and_conquer_partition_dp(), Aleph::Gen_Segment_Tree< T, Op >::query(), and Aleph::Gen_Segment_Tree< T, Op >::set().

TEST() [44/45]

TEST	(	SegmentTreeTypedefs	,
		MinSegmentTree
	)

Definition at line 389 of file tpl_segment_tree_test.cc.

References Aleph::divide_and_conquer_partition_dp(), Aleph::Gen_Segment_Tree< T, Op >::query(), and Aleph::Gen_Segment_Tree< T, Op >::set().

TEST() [45/45]

TEST	(	SegmentTreeTypedefs	,
		SumSegmentTree
	)

Definition at line 381 of file tpl_segment_tree_test.cc.

References Aleph::divide_and_conquer_partition_dp(), Aleph::Gen_Segment_Tree< T, Op >::query(), and Aleph::Gen_Segment_Tree< T, Op >::update().