fibonacci_heap_test.cc File Reference

Tests for Fibonacci Heap. More...

#include <gtest/gtest.h>
#include <numeric>
#include <tpl_fibonacci_heap.H>
#include <vector>
#include <algorithm>
#include <random>
#include <string>
#include <set>
#include <chrono>
#include <functional>

Include dependency graph for fibonacci_heap_test.cc:

Go to the source code of this file.

Classes
class	FibonacciHeapTest
class	FibonacciHeapWithDataTest
struct	Point

Functions
	TEST (FibonacciHeapConstruction, DefaultConstructor)
	TEST (FibonacciHeapConstruction, ConstructorWithComparator)
	TEST (FibonacciHeapConstruction, MoveConstructor)
	TEST (FibonacciHeapConstruction, MoveAssignment)
	TEST (FibonacciHeapConstruction, MoveAssignmentRoundtrip)
	TEST_F (FibonacciHeapTest, InsertSingleElement)
	TEST_F (FibonacciHeapTest, InsertMultipleElements)
	TEST_F (FibonacciHeapTest, InsertDescendingOrder)
	TEST_F (FibonacciHeapTest, InsertAscendingOrder)
	TEST_F (FibonacciHeapTest, InsertDuplicates)
	TEST_F (FibonacciHeapTest, InsertWithMoveSemantics)
	TEST_F (FibonacciHeapTest, EmplaceConstruction)
	TEST_F (FibonacciHeapTest, GetMinOnEmptyHeapThrows)
	TEST_F (FibonacciHeapTest, GetMinNodeOnEmptyHeap)
	TEST_F (FibonacciHeapTest, GetMinAfterInserts)
	TEST_F (FibonacciHeapTest, ExtractMinOnEmptyHeapThrows)
	TEST_F (FibonacciHeapTest, ExtractMinSingleElement)
	TEST_F (FibonacciHeapTest, ExtractMinMultipleElements)
	TEST_F (FibonacciHeapTest, ExtractMinMaintainsSortedOrder)
	TEST_F (FibonacciHeapTest, ExtractMinWithDuplicates)
	TEST_F (FibonacciHeapWithDataTest, DecreaseKeyToNewMinimum)
	TEST_F (FibonacciHeapWithDataTest, DecreaseKeyNotAffectingMinimum)
	TEST_F (FibonacciHeapWithDataTest, DecreaseKeyToSameValue)
	TEST_F (FibonacciHeapTest, DecreaseKeyWithInvalidIncreaseThrows)
	TEST_F (FibonacciHeapTest, DecreaseKeyWithNullptrThrows)
	TEST_F (FibonacciHeapTest, DecreaseKeyTriggersCut)
	TEST_F (FibonacciHeapTest, DecreaseKeyTriggersCascadingCuts)
	TEST_F (FibonacciHeapTest, DecreaseKeyMoveSemantics)
	TEST_F (FibonacciHeapTest, UpdateKeyDecrease)
	TEST_F (FibonacciHeapTest, UpdateKeyIncrease)
	TEST_F (FibonacciHeapTest, UpdateKeySameValue)
	TEST_F (FibonacciHeapTest, UpdateKeyNullptrThrows)
	TEST_F (FibonacciHeapTest, DeleteNodeSingleElement)
	TEST_F (FibonacciHeapTest, DeleteNodeMinimum)
	TEST_F (FibonacciHeapTest, DeleteNodeNonMinimum)
	TEST_F (FibonacciHeapTest, DeleteNodeNullptrThrows)
	TEST_F (FibonacciHeapTest, DeleteNodeFromDeepTree)
	TEST_F (FibonacciHeapTest, DeleteSolitaryRootWithChildren)
	TEST_F (FibonacciHeapTest, DeleteSolitaryRootWithChildrenDirect)
	TEST_F (FibonacciHeapTest, DeleteAllNodesOneByOne)
	TEST_F (FibonacciHeapTest, MergeEmptyHeaps)
	TEST_F (FibonacciHeapTest, MergeIntoEmptyHeap)
	TEST_F (FibonacciHeapTest, MergeEmptyIntoNonEmpty)
	TEST_F (FibonacciHeapTest, MergeTwoNonEmptyHeaps)
	TEST_F (FibonacciHeapTest, MergeWithRvalue)
	TEST_F (FibonacciHeapTest, MergeLargeHeaps)
	TEST_F (FibonacciHeapTest, SwapHeaps)
	TEST_F (FibonacciHeapTest, SwapWithEmptyHeap)
	TEST_F (FibonacciHeapTest, SwapFreeFunction)
	TEST_F (FibonacciHeapTest, ClearEmptyHeap)
	TEST_F (FibonacciHeapTest, ClearNonEmptyHeap)
	TEST_F (FibonacciHeapTest, ClearAndReuse)
	TEST (FibonacciHeapTypeAliases, ValueType)
	TEST (FibonacciHeapTypeAliases, HandleType)
	TEST (FibonacciMaxHeap, BasicOperations)
	TEST (FibonacciMaxHeap, DecreaseKey)
	TEST (FibonacciHeapCustomType, PointHeap)
	TEST (FibonacciHeapCustomType, PairHeap)
	TEST (FibonacciHeapStress, LargeNumberOfInserts)
	TEST (FibonacciHeapStress, LargeNumberOfExtractMin)
	TEST (FibonacciHeapStress, InterleavedOperations)
	TEST (FibonacciHeapStress, ManyDecreaseKeys)
	TEST (FibonacciHeapStress, ManyDeleteNodes)
	TEST (FibonacciHeapStress, ManyMerges)
	TEST (FibonacciHeapEdgeCases, NegativeNumbers)
	TEST (FibonacciHeapEdgeCases, IntMinMax)
	TEST (FibonacciHeapEdgeCases, SingleElementOperations)
	TEST (FibonacciHeapEdgeCases, AlternatingMinMax)
template<typename T , typename Compare >
bool	verify_heap_property (Fibonacci_Heap< T, Compare > &heap)
	TEST (FibonacciHeapProperty, RandomInsertions)
	TEST (FibonacciHeapProperty, AfterDecreaseKeys)
	TEST (FibonacciHeapProperty, AfterMerge)
	TEST (FibonacciHeapMemory, DestructorFreesMemory)
	TEST (FibonacciHeapMemory, ClearFreesMemory)
	TEST (FibonacciHeapPerformance, DISABLED_TimingComparison)
	TEST (FibonacciHeapUsagePattern, DijkstraSimulation)
	TEST (FibonacciHeapComparator, KeyComp)
	TEST (FibonacciHeapComparator, CustomLambdaComparator)
	TEST (FibonacciHeapEdgeCases, DecreaseKeyOnRootNode)
	TEST (FibonacciHeapEdgeCases, DecreaseKeyChildBecomesSmallerThanParent)
	TEST (FibonacciHeapEdgeCases, DeleteNodeWithMultipleChildren)
	TEST (FibonacciHeapEdgeCases, MergeSelfNoOp)
	TEST (FibonacciHeapEdgeCases, UpdateKeyToSameValueOnChild)
	TEST (FibonacciHeapEdgeCases, ConsecutiveDecreaseKeys)
	TEST (FibonacciHeapEdgeCases, EmplaceWithSingleArg)
	TEST (FibonacciHeapEdgeCases, LargeDegreeTrees)
	TEST (FibonacciHeapEdgeCases, SwapEmptyHeaps)
	TEST (FibonacciHeapEdgeCases, MoveAssignToSelf)
	TEST (FibonacciHeapEdgeCases, DeleteLastTwoNodes)
	TEST (FibonacciHeapRegression, DeleteAloneRootWithChildren)
	TEST (FibonacciHeapRegression, CascadingCutsChain)
int	main (int argc, char **argv)

Detailed Description

Tests for Fibonacci Heap.

Definition in file fibonacci_heap_test.cc.

Function Documentation

main()

int main	(	int	argc,
		char **	argv
	)

Definition at line 1628 of file fibonacci_heap_test.cc.

References Aleph::blossom_maximum_cardinality_matching().

TEST() [1/43]

TEST	(	FibonacciHeapComparator	,
		CustomLambdaComparator
	)

Definition at line 1338 of file fibonacci_heap_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), cmp(), and Aleph::Fibonacci_Heap< T, Compare >::insert().

TEST() [2/43]

TEST	(	FibonacciHeapComparator	,
		KeyComp
	)

Definition at line 1328 of file fibonacci_heap_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), cmp(), and Aleph::Fibonacci_Heap< T, Compare >::key_comp().

TEST() [3/43]

TEST	(	FibonacciHeapConstruction	,
		ConstructorWithComparator
	)

Definition at line 92 of file fibonacci_heap_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), and Aleph::Fibonacci_Heap< T, Compare >::insert().

TEST() [4/43]

TEST	(	FibonacciHeapConstruction	,
		DefaultConstructor
	)

Definition at line 84 of file fibonacci_heap_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), and h.

TEST() [5/43]

TEST	(	FibonacciHeapConstruction	,
		MoveAssignment
	)

Definition at line 118 of file fibonacci_heap_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), and Aleph::Fibonacci_Heap< T, Compare >::insert().

TEST() [6/43]

TEST	(	FibonacciHeapConstruction	,
		MoveAssignmentRoundtrip
	)

Definition at line 134 of file fibonacci_heap_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), h, and Aleph::Fibonacci_Heap< T, Compare >::insert().

TEST() [7/43]

TEST	(	FibonacciHeapConstruction	,
		MoveConstructor
	)

Definition at line 101 of file fibonacci_heap_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), and Aleph::Fibonacci_Heap< T, Compare >::insert().

TEST() [8/43]

TEST	(	FibonacciHeapCustomType	,
		PairHeap
	)

Definition at line 893 of file fibonacci_heap_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), and Aleph::Fibonacci_Heap< T, Compare >::insert().

TEST() [9/43]

TEST	(	FibonacciHeapCustomType	,
		PointHeap
	)

Definition at line 879 of file fibonacci_heap_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), and Aleph::Fibonacci_Heap< T, Compare >::insert().

TEST() [10/43]

TEST	(	FibonacciHeapEdgeCases	,
		AlternatingMinMax
	)

Definition at line 1115 of file fibonacci_heap_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::Fibonacci_Heap< T, Compare >::extract_min(), Aleph::Fibonacci_Heap< T, Compare >::insert(), and Aleph::Fibonacci_Heap< T, Compare >::is_empty().

TEST() [11/43]

TEST	(	FibonacciHeapEdgeCases	,
		ConsecutiveDecreaseKeys
	)

Definition at line 1460 of file fibonacci_heap_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::Fibonacci_Heap< T, Compare >::decrease_key(), Aleph::Fibonacci_Heap< T, Compare >::extract_min(), Aleph::Fibonacci_Heap< T, Compare >::get_min(), and Aleph::Fibonacci_Heap< T, Compare >::insert().

TEST() [12/43]

TEST	(	FibonacciHeapEdgeCases	,
		DecreaseKeyChildBecomesSmallerThanParent
	)

Definition at line 1372 of file fibonacci_heap_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::Fibonacci_Heap< T, Compare >::decrease_key(), Aleph::Fibonacci_Heap< T, Compare >::extract_min(), Aleph::Fibonacci_Heap< T, Compare >::get_min(), Aleph::Fibonacci_Heap< T, Compare >::insert(), and Aleph::Fibonacci_Heap< T, Compare >::is_empty().

TEST() [13/43]

TEST	(	FibonacciHeapEdgeCases	,
		DecreaseKeyOnRootNode
	)

Definition at line 1356 of file fibonacci_heap_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::Fibonacci_Heap< T, Compare >::decrease_key(), Aleph::Fibonacci_Heap< T, Compare >::extract_min(), Aleph::Fibonacci_Heap< T, Compare >::get_min(), and Aleph::Fibonacci_Heap< T, Compare >::insert().

TEST() [14/43]

TEST	(	FibonacciHeapEdgeCases	,
		DeleteLastTwoNodes
	)

Definition at line 1548 of file fibonacci_heap_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::Fibonacci_Heap< T, Compare >::delete_node(), Aleph::Fibonacci_Heap< T, Compare >::get_min(), Aleph::Fibonacci_Heap< T, Compare >::insert(), Aleph::Fibonacci_Heap< T, Compare >::is_empty(), and Aleph::Fibonacci_Heap< T, Compare >::size().

TEST() [15/43]

TEST	(	FibonacciHeapEdgeCases	,
		DeleteNodeWithMultipleChildren
	)

Definition at line 1400 of file fibonacci_heap_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::Fibonacci_Heap< T, Compare >::delete_node(), Aleph::Fibonacci_Heap< T, Compare >::extract_min(), Aleph::Fibonacci_Heap< T, Compare >::insert(), Aleph::Fibonacci_Heap< T, Compare >::is_empty(), nodes, and Aleph::Fibonacci_Heap< T, Compare >::size().

TEST() [16/43]

TEST	(	FibonacciHeapEdgeCases	,
		EmplaceWithSingleArg
	)

Definition at line 1484 of file fibonacci_heap_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::Fibonacci_Heap< T, Compare >::emplace(), and Aleph::Fibonacci_Heap< T, Compare >::get_min().

TEST() [17/43]

TEST	(	FibonacciHeapEdgeCases	,
		IntMinMax
	)

Definition at line 1088 of file fibonacci_heap_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::Fibonacci_Heap< T, Compare >::extract_min(), and Aleph::Fibonacci_Heap< T, Compare >::insert().

TEST() [18/43]

TEST	(	FibonacciHeapEdgeCases	,
		LargeDegreeTrees
	)

Definition at line 1495 of file fibonacci_heap_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::Fibonacci_Heap< T, Compare >::extract_min(), Aleph::Fibonacci_Heap< T, Compare >::insert(), Aleph::Fibonacci_Heap< T, Compare >::is_empty(), and N.

TEST() [19/43]

TEST	(	FibonacciHeapEdgeCases	,
		MergeSelfNoOp
	)

Definition at line 1429 of file fibonacci_heap_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::Fibonacci_Heap< T, Compare >::get_min(), Aleph::Fibonacci_Heap< T, Compare >::insert(), Aleph::Fibonacci_Heap< T, Compare >::merge(), and Aleph::Fibonacci_Heap< T, Compare >::size().

TEST() [20/43]

TEST	(	FibonacciHeapEdgeCases	,
		MoveAssignToSelf
	)

Definition at line 1532 of file fibonacci_heap_test.cc.

References Aleph::Fibonacci_Heap< T, Compare >::insert().

TEST() [21/43]

TEST	(	FibonacciHeapEdgeCases	,
		NegativeNumbers
	)

Definition at line 1071 of file fibonacci_heap_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::Fibonacci_Heap< T, Compare >::extract_min(), and Aleph::Fibonacci_Heap< T, Compare >::insert().

TEST() [22/43]

TEST	(	FibonacciHeapEdgeCases	,
		SingleElementOperations
	)

Definition at line 1101 of file fibonacci_heap_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::Fibonacci_Heap< T, Compare >::decrease_key(), Aleph::Fibonacci_Heap< T, Compare >::delete_node(), Aleph::Fibonacci_Heap< T, Compare >::get_min(), Aleph::Fibonacci_Heap< T, Compare >::insert(), and Aleph::Fibonacci_Heap< T, Compare >::is_empty().

TEST() [23/43]

TEST	(	FibonacciHeapEdgeCases	,
		SwapEmptyHeaps
	)

Definition at line 1522 of file fibonacci_heap_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), and Aleph::Fibonacci_Heap< T, Compare >::swap().

TEST() [24/43]

TEST	(	FibonacciHeapEdgeCases	,
		UpdateKeyToSameValueOnChild
	)

Definition at line 1441 of file fibonacci_heap_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::Fibonacci_Heap< T, Compare >::extract_min(), Aleph::Fibonacci_Heap< T, Compare >::insert(), and Aleph::Fibonacci_Heap< T, Compare >::update_key().

TEST() [25/43]

TEST	(	FibonacciHeapMemory	,
		ClearFreesMemory
	)

Definition at line 1229 of file fibonacci_heap_test.cc.

References Aleph::Fibonacci_Heap< T, Compare >::clear(), and Aleph::Fibonacci_Heap< T, Compare >::insert().

TEST() [26/43]

TEST	(	FibonacciHeapMemory	,
		DestructorFreesMemory
	)

Definition at line 1217 of file fibonacci_heap_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), and Aleph::Fibonacci_Heap< T, Compare >::insert().

TEST() [27/43]

TEST	(	FibonacciHeapPerformance	,
		DISABLED_TimingComparison
	)

Definition at line 1243 of file fibonacci_heap_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::Fibonacci_Heap< T, Compare >::extract_min(), Aleph::Fibonacci_Heap< T, Compare >::insert(), Aleph::Fibonacci_Heap< T, Compare >::is_empty(), and N.

TEST() [28/43]

TEST	(	FibonacciHeapProperty	,
		AfterDecreaseKeys
	)

Definition at line 1176 of file fibonacci_heap_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::Fibonacci_Heap< T, Compare >::decrease_key(), Aleph::Fibonacci_Heap< T, Compare >::extract_min(), Aleph::Fibonacci_Heap< T, Compare >::insert(), nodes, and verify_heap_property().

TEST() [29/43]

TEST	(	FibonacciHeapProperty	,
		AfterMerge
	)

Definition at line 1195 of file fibonacci_heap_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), and verify_heap_property().

TEST() [30/43]

TEST	(	FibonacciHeapProperty	,
		RandomInsertions
	)

Definition at line 1163 of file fibonacci_heap_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::Fibonacci_Heap< T, Compare >::insert(), and verify_heap_property().

TEST() [31/43]

TEST	(	FibonacciHeapRegression	,
		CascadingCutsChain
	)

Definition at line 1593 of file fibonacci_heap_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::Fibonacci_Heap< T, Compare >::decrease_key(), Aleph::Fibonacci_Heap< T, Compare >::extract_min(), Aleph::Fibonacci_Heap< T, Compare >::insert(), Aleph::Fibonacci_Heap< T, Compare >::is_empty(), and nodes.

TEST() [32/43]

TEST	(	FibonacciHeapRegression	,
		DeleteAloneRootWithChildren
	)

Definition at line 1568 of file fibonacci_heap_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::Fibonacci_Heap< T, Compare >::delete_node(), Aleph::Fibonacci_Heap< T, Compare >::extract_min(), Aleph::Fibonacci_Heap< T, Compare >::get_min(), Aleph::Fibonacci_Heap< T, Compare >::get_min_node(), Aleph::Fibonacci_Heap< T, Compare >::insert(), root(), and Aleph::Fibonacci_Heap< T, Compare >::size().

TEST() [33/43]

TEST	(	FibonacciHeapStress	,
		InterleavedOperations
	)

Definition at line 937 of file fibonacci_heap_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::Fibonacci_Heap< T, Compare >::extract_min(), Aleph::Fibonacci_Heap< T, Compare >::get_min(), Aleph::Fibonacci_Heap< T, Compare >::insert(), Aleph::Fibonacci_Heap< T, Compare >::is_empty(), and N.

TEST() [34/43]

TEST	(	FibonacciHeapStress	,
		LargeNumberOfExtractMin
	)

Definition at line 923 of file fibonacci_heap_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::Fibonacci_Heap< T, Compare >::extract_min(), Aleph::Fibonacci_Heap< T, Compare >::insert(), Aleph::Fibonacci_Heap< T, Compare >::is_empty(), and N.

TEST() [35/43]

TEST	(	FibonacciHeapStress	,
		LargeNumberOfInserts
	)

Definition at line 911 of file fibonacci_heap_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::Fibonacci_Heap< T, Compare >::get_min(), Aleph::Fibonacci_Heap< T, Compare >::insert(), N, and Aleph::Fibonacci_Heap< T, Compare >::size().

TEST() [36/43]

TEST	(	FibonacciHeapStress	,
		ManyDecreaseKeys
	)

Definition at line 983 of file fibonacci_heap_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), counter, Aleph::Fibonacci_Heap< T, Compare >::decrease_key(), Aleph::Fibonacci_Heap< T, Compare >::extract_min(), Aleph::Fibonacci_Heap< T, Compare >::insert(), Aleph::Fibonacci_Heap< T, Compare >::is_empty(), N, and nodes.

TEST() [37/43]

TEST	(	FibonacciHeapStress	,
		ManyDeleteNodes
	)

Definition at line 1017 of file fibonacci_heap_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::Fibonacci_Heap< T, Compare >::delete_node(), Aleph::Fibonacci_Heap< T, Compare >::extract_min(), Aleph::Fibonacci_Heap< T, Compare >::insert(), Aleph::Fibonacci_Heap< T, Compare >::is_empty(), N, nodes, and Aleph::Fibonacci_Heap< T, Compare >::size().

TEST() [38/43]

TEST	(	FibonacciHeapStress	,
		ManyMerges
	)

Definition at line 1042 of file fibonacci_heap_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::merge(), and Aleph::size().

TEST() [39/43]

TEST	(	FibonacciHeapTypeAliases	,
		HandleType
	)

Definition at line 827 of file fibonacci_heap_test.cc.

TEST() [40/43]

TEST	(	FibonacciHeapTypeAliases	,
		ValueType
	)

Definition at line 821 of file fibonacci_heap_test.cc.

TEST() [41/43]

TEST	(	FibonacciHeapUsagePattern	,
		DijkstraSimulation
	)

Definition at line 1273 of file fibonacci_heap_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), and operator<().

TEST() [42/43]

TEST	(	FibonacciMaxHeap	,
		BasicOperations
	)

Definition at line 836 of file fibonacci_heap_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), and Aleph::Fibonacci_Heap< T, Compare >::insert().

TEST() [43/43]

TEST	(	FibonacciMaxHeap	,
		DecreaseKey
	)

Definition at line 850 of file fibonacci_heap_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), and Aleph::Fibonacci_Heap< T, Compare >::insert().

TEST_F() [1/47]

TEST_F	(	FibonacciHeapTest	,
		ClearAndReuse
	)

Definition at line 804 of file fibonacci_heap_test.cc.

References Aleph::blossom_maximum_cardinality_matching().

TEST_F() [2/47]

TEST_F	(	FibonacciHeapTest	,
		ClearEmptyHeap
	)

Definition at line 787 of file fibonacci_heap_test.cc.

References Aleph::blossom_maximum_cardinality_matching().

TEST_F() [3/47]

TEST_F	(	FibonacciHeapTest	,
		ClearNonEmptyHeap
	)

Definition at line 793 of file fibonacci_heap_test.cc.

References Aleph::blossom_maximum_cardinality_matching().

TEST_F() [4/47]

TEST_F	(	FibonacciHeapTest	,
		DecreaseKeyMoveSemantics
	)

Definition at line 406 of file fibonacci_heap_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), and Aleph::Fibonacci_Heap< T, Compare >::insert().

TEST_F() [5/47]

TEST_F	(	FibonacciHeapTest	,
		DecreaseKeyTriggersCascadingCuts
	)

Definition at line 378 of file fibonacci_heap_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), and nodes.

TEST_F() [6/47]

TEST_F	(	FibonacciHeapTest	,
		DecreaseKeyTriggersCut
	)

Definition at line 361 of file fibonacci_heap_test.cc.

References Aleph::blossom_maximum_cardinality_matching().

TEST_F() [7/47]

TEST_F	(	FibonacciHeapTest	,
		DecreaseKeyWithInvalidIncreaseThrows
	)

Definition at line 350 of file fibonacci_heap_test.cc.

References Aleph::blossom_maximum_cardinality_matching().

TEST_F() [8/47]

TEST_F	(	FibonacciHeapTest	,
		DecreaseKeyWithNullptrThrows
	)

Definition at line 356 of file fibonacci_heap_test.cc.

References Aleph::blossom_maximum_cardinality_matching().

TEST_F() [9/47]

TEST_F	(	FibonacciHeapTest	,
		DeleteAllNodesOneByOne
	)

Definition at line 613 of file fibonacci_heap_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), and nodes.

TEST_F() [10/47]

TEST_F	(	FibonacciHeapTest	,
		DeleteNodeFromDeepTree
	)

Definition at line 507 of file fibonacci_heap_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), and nodes.

TEST_F() [11/47]

TEST_F	(	FibonacciHeapTest	,
		DeleteNodeMinimum
	)

Definition at line 476 of file fibonacci_heap_test.cc.

References Aleph::blossom_maximum_cardinality_matching().

TEST_F() [12/47]

TEST_F	(	FibonacciHeapTest	,
		DeleteNodeNonMinimum
	)

Definition at line 488 of file fibonacci_heap_test.cc.

References Aleph::blossom_maximum_cardinality_matching().

TEST_F() [13/47]

TEST_F	(	FibonacciHeapTest	,
		DeleteNodeNullptrThrows
	)

Definition at line 502 of file fibonacci_heap_test.cc.

References Aleph::blossom_maximum_cardinality_matching().

TEST_F() [14/47]

TEST_F	(	FibonacciHeapTest	,
		DeleteNodeSingleElement
	)

Definition at line 468 of file fibonacci_heap_test.cc.

References Aleph::blossom_maximum_cardinality_matching().

TEST_F() [15/47]

TEST_F	(	FibonacciHeapTest	,
		DeleteSolitaryRootWithChildren
	)

Definition at line 538 of file fibonacci_heap_test.cc.

References Aleph::blossom_maximum_cardinality_matching().

TEST_F() [16/47]

TEST_F	(	FibonacciHeapTest	,
		DeleteSolitaryRootWithChildrenDirect
	)

Definition at line 583 of file fibonacci_heap_test.cc.

References Aleph::blossom_maximum_cardinality_matching().

TEST_F() [17/47]

TEST_F	(	FibonacciHeapTest	,
		EmplaceConstruction
	)

Definition at line 218 of file fibonacci_heap_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), and Aleph::Fibonacci_Heap< T, Compare >::emplace().

TEST_F() [18/47]

TEST_F	(	FibonacciHeapTest	,
		ExtractMinMaintainsSortedOrder
	)

Definition at line 290 of file fibonacci_heap_test.cc.

References Aleph::blossom_maximum_cardinality_matching().

TEST_F() [19/47]

TEST_F	(	FibonacciHeapTest	,
		ExtractMinMultipleElements
	)

Definition at line 278 of file fibonacci_heap_test.cc.

References Aleph::blossom_maximum_cardinality_matching().

TEST_F() [20/47]

TEST_F	(	FibonacciHeapTest	,
		ExtractMinOnEmptyHeapThrows
	)

Definition at line 264 of file fibonacci_heap_test.cc.

References Aleph::blossom_maximum_cardinality_matching().

TEST_F() [21/47]

TEST_F	(	FibonacciHeapTest	,
		ExtractMinSingleElement
	)

Definition at line 269 of file fibonacci_heap_test.cc.

References Aleph::blossom_maximum_cardinality_matching().

TEST_F() [22/47]

TEST_F	(	FibonacciHeapTest	,
		ExtractMinWithDuplicates
	)

Definition at line 306 of file fibonacci_heap_test.cc.

References Aleph::blossom_maximum_cardinality_matching().

TEST_F() [23/47]

TEST_F	(	FibonacciHeapTest	,
		GetMinAfterInserts
	)

Definition at line 242 of file fibonacci_heap_test.cc.

References Aleph::blossom_maximum_cardinality_matching().

TEST_F() [24/47]

TEST_F	(	FibonacciHeapTest	,
		GetMinNodeOnEmptyHeap
	)

Definition at line 237 of file fibonacci_heap_test.cc.

References Aleph::blossom_maximum_cardinality_matching().

TEST_F() [25/47]

TEST_F	(	FibonacciHeapTest	,
		GetMinOnEmptyHeapThrows
	)

Definition at line 232 of file fibonacci_heap_test.cc.

References Aleph::blossom_maximum_cardinality_matching().

TEST_F() [26/47]

TEST_F	(	FibonacciHeapTest	,
		InsertAscendingOrder
	)

Definition at line 183 of file fibonacci_heap_test.cc.

References Aleph::blossom_maximum_cardinality_matching().

TEST_F() [27/47]

TEST_F	(	FibonacciHeapTest	,
		InsertDescendingOrder
	)

Definition at line 174 of file fibonacci_heap_test.cc.

References Aleph::blossom_maximum_cardinality_matching().

TEST_F() [28/47]

TEST_F	(	FibonacciHeapTest	,
		InsertDuplicates
	)

Definition at line 192 of file fibonacci_heap_test.cc.

References Aleph::blossom_maximum_cardinality_matching().

TEST_F() [29/47]

TEST_F	(	FibonacciHeapTest	,
		InsertMultipleElements
	)

Definition at line 162 of file fibonacci_heap_test.cc.

References Aleph::blossom_maximum_cardinality_matching().

TEST_F() [30/47]

TEST_F	(	FibonacciHeapTest	,
		InsertSingleElement
	)

Definition at line 152 of file fibonacci_heap_test.cc.

References Aleph::blossom_maximum_cardinality_matching().

TEST_F() [31/47]

TEST_F	(	FibonacciHeapTest	,
		InsertWithMoveSemantics
	)

Definition at line 207 of file fibonacci_heap_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), and Aleph::Fibonacci_Heap< T, Compare >::insert().

TEST_F() [32/47]

TEST_F	(	FibonacciHeapTest	,
		MergeEmptyHeaps
	)

Definition at line 638 of file fibonacci_heap_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), and Aleph::Fibonacci_Heap< T, Compare >::merge().

TEST_F() [33/47]

TEST_F	(	FibonacciHeapTest	,
		MergeEmptyIntoNonEmpty
	)

Definition at line 660 of file fibonacci_heap_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), and Aleph::Fibonacci_Heap< T, Compare >::insert().

TEST_F() [34/47]

TEST_F	(	FibonacciHeapTest	,
		MergeIntoEmptyHeap
	)

Definition at line 647 of file fibonacci_heap_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), and Aleph::Fibonacci_Heap< T, Compare >::insert().

TEST_F() [35/47]

TEST_F	(	FibonacciHeapTest	,
		MergeLargeHeaps
	)

Definition at line 713 of file fibonacci_heap_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), and Aleph::Fibonacci_Heap< T, Compare >::insert().

TEST_F() [36/47]

TEST_F	(	FibonacciHeapTest	,
		MergeTwoNonEmptyHeaps
	)

Definition at line 672 of file fibonacci_heap_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), and Aleph::Fibonacci_Heap< T, Compare >::insert().

TEST_F() [37/47]

TEST_F	(	FibonacciHeapTest	,
		MergeWithRvalue
	)

Definition at line 699 of file fibonacci_heap_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), and Aleph::Fibonacci_Heap< T, Compare >::insert().

TEST_F() [38/47]

TEST_F	(	FibonacciHeapTest	,
		SwapFreeFunction
	)

Definition at line 771 of file fibonacci_heap_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::Fibonacci_Heap< T, Compare >::insert(), and Aleph::swap().

TEST_F() [39/47]

TEST_F	(	FibonacciHeapTest	,
		SwapHeaps
	)

Definition at line 739 of file fibonacci_heap_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), and Aleph::Fibonacci_Heap< T, Compare >::insert().

TEST_F() [40/47]

TEST_F	(	FibonacciHeapTest	,
		SwapWithEmptyHeap
	)

Definition at line 759 of file fibonacci_heap_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), and Aleph::Fibonacci_Heap< T, Compare >::insert().

TEST_F() [41/47]

TEST_F	(	FibonacciHeapTest	,
		UpdateKeyDecrease
	)

Definition at line 421 of file fibonacci_heap_test.cc.

References Aleph::blossom_maximum_cardinality_matching().

TEST_F() [42/47]

TEST_F	(	FibonacciHeapTest	,
		UpdateKeyIncrease
	)

Definition at line 430 of file fibonacci_heap_test.cc.

References Aleph::blossom_maximum_cardinality_matching().

TEST_F() [43/47]

TEST_F	(	FibonacciHeapTest	,
		UpdateKeyNullptrThrows
	)

Definition at line 459 of file fibonacci_heap_test.cc.

References Aleph::blossom_maximum_cardinality_matching().

TEST_F() [44/47]

TEST_F	(	FibonacciHeapTest	,
		UpdateKeySameValue
	)

Definition at line 450 of file fibonacci_heap_test.cc.

References Aleph::blossom_maximum_cardinality_matching().

TEST_F() [45/47]

TEST_F	(	FibonacciHeapWithDataTest	,
		DecreaseKeyNotAffectingMinimum
	)

Definition at line 334 of file fibonacci_heap_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), and nodes.

TEST_F() [46/47]

TEST_F	(	FibonacciHeapWithDataTest	,
		DecreaseKeyToNewMinimum
	)

Definition at line 324 of file fibonacci_heap_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), and nodes.

TEST_F() [47/47]

TEST_F	(	FibonacciHeapWithDataTest	,
		DecreaseKeyToSameValue
	)

Definition at line 343 of file fibonacci_heap_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), and nodes.

verify_heap_property()

template<typename T , typename Compare >

bool verify_heap_property

(

Fibonacci_Heap< T, Compare > &

heap

)

Definition at line 1144 of file fibonacci_heap_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::Fibonacci_Heap< T, Compare >::extract_min(), and Aleph::Fibonacci_Heap< T, Compare >::is_empty().

Referenced by TEST(), TEST(), and TEST().