fibonacci_heap_test.cc File Reference

Tests for Fibonacci Heap. More...

#include <gtest/gtest.h>
#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
	Rectangular point in the plane. More...

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 1627 of file fibonacci_heap_test.cc.

References Aleph::maps().

TEST() [1/43]

TEST	(	FibonacciHeapComparator	,
		CustomLambdaComparator
	)

Definition at line 1337 of file fibonacci_heap_test.cc.

References cmp(), Aleph::DynList< T >::insert(), and Aleph::maps().

TEST() [2/43]

TEST	(	FibonacciHeapComparator	,
		KeyComp
	)

Definition at line 1327 of file fibonacci_heap_test.cc.

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

TEST() [3/43]

TEST	(	FibonacciHeapConstruction	,
		ConstructorWithComparator
	)

Definition at line 91 of file fibonacci_heap_test.cc.

References Aleph::DynList< T >::insert(), and Aleph::maps().

TEST() [4/43]

TEST	(	FibonacciHeapConstruction	,
		DefaultConstructor
	)

Definition at line 83 of file fibonacci_heap_test.cc.

References h, and Aleph::maps().

TEST() [5/43]

TEST	(	FibonacciHeapConstruction	,
		MoveAssignment
	)

Definition at line 117 of file fibonacci_heap_test.cc.

References Aleph::DynList< T >::insert(), Aleph::HTList::is_empty(), Aleph::maps(), and Aleph::HTList::size().

TEST() [6/43]

TEST	(	FibonacciHeapConstruction	,
		MoveAssignmentRoundtrip
	)

Definition at line 133 of file fibonacci_heap_test.cc.

References h, Aleph::Fibonacci_Heap< T, Compare >::insert(), Aleph::maps(), and Aleph::HTList::size().

TEST() [7/43]

TEST	(	FibonacciHeapConstruction	,
		MoveConstructor
	)

Definition at line 100 of file fibonacci_heap_test.cc.

References Aleph::DynList< T >::insert(), Aleph::HTList::is_empty(), Aleph::maps(), and Aleph::HTList::size().

TEST() [8/43]

TEST	(	FibonacciHeapCustomType	,
		PairHeap
	)

Definition at line 892 of file fibonacci_heap_test.cc.

References Aleph::DynList< T >::insert(), and Aleph::maps().

TEST() [9/43]

TEST	(	FibonacciHeapCustomType	,
		PointHeap
	)

Definition at line 878 of file fibonacci_heap_test.cc.

References Aleph::DynList< T >::insert(), and Aleph::maps().

TEST() [10/43]

TEST	(	FibonacciHeapEdgeCases	,
		AlternatingMinMax
	)

Definition at line 1114 of file fibonacci_heap_test.cc.

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

TEST() [11/43]

TEST	(	FibonacciHeapEdgeCases	,
		ConsecutiveDecreaseKeys
	)

Definition at line 1459 of file fibonacci_heap_test.cc.

References 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::maps().

TEST() [12/43]

TEST	(	FibonacciHeapEdgeCases	,
		DecreaseKeyChildBecomesSmallerThanParent
	)

Definition at line 1371 of file fibonacci_heap_test.cc.

References 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(), Aleph::Fibonacci_Heap< T, Compare >::is_empty(), and Aleph::maps().

TEST() [13/43]

TEST	(	FibonacciHeapEdgeCases	,
		DecreaseKeyOnRootNode
	)

Definition at line 1355 of file fibonacci_heap_test.cc.

References 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::maps().

TEST() [14/43]

TEST	(	FibonacciHeapEdgeCases	,
		DeleteLastTwoNodes
	)

Definition at line 1547 of file fibonacci_heap_test.cc.

References 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(), Aleph::maps(), and Aleph::Fibonacci_Heap< T, Compare >::size().

TEST() [15/43]

TEST	(	FibonacciHeapEdgeCases	,
		DeleteNodeWithMultipleChildren
	)

Definition at line 1399 of file fibonacci_heap_test.cc.

References 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(), Aleph::maps(), nodes, and Aleph::Fibonacci_Heap< T, Compare >::size().

TEST() [16/43]

TEST	(	FibonacciHeapEdgeCases	,
		EmplaceWithSingleArg
	)

Definition at line 1483 of file fibonacci_heap_test.cc.

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

TEST() [17/43]

TEST	(	FibonacciHeapEdgeCases	,
		IntMinMax
	)

Definition at line 1087 of file fibonacci_heap_test.cc.

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

TEST() [18/43]

TEST	(	FibonacciHeapEdgeCases	,
		LargeDegreeTrees
	)

Definition at line 1494 of file fibonacci_heap_test.cc.

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

TEST() [19/43]

TEST	(	FibonacciHeapEdgeCases	,
		MergeSelfNoOp
	)

Definition at line 1428 of file fibonacci_heap_test.cc.

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

TEST() [20/43]

TEST	(	FibonacciHeapEdgeCases	,
		MoveAssignToSelf
	)

Definition at line 1531 of file fibonacci_heap_test.cc.

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

TEST() [21/43]

TEST	(	FibonacciHeapEdgeCases	,
		NegativeNumbers
	)

Definition at line 1070 of file fibonacci_heap_test.cc.

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

TEST() [22/43]

TEST	(	FibonacciHeapEdgeCases	,
		SingleElementOperations
	)

Definition at line 1100 of file fibonacci_heap_test.cc.

References 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(), Aleph::Fibonacci_Heap< T, Compare >::is_empty(), and Aleph::maps().

TEST() [23/43]

TEST	(	FibonacciHeapEdgeCases	,
		SwapEmptyHeaps
	)

Definition at line 1521 of file fibonacci_heap_test.cc.

References Aleph::HTList::is_empty(), Aleph::maps(), and Aleph::DynList< T >::swap().

TEST() [24/43]

TEST	(	FibonacciHeapEdgeCases	,
		UpdateKeyToSameValueOnChild
	)

Definition at line 1440 of file fibonacci_heap_test.cc.

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

TEST() [25/43]

TEST	(	FibonacciHeapMemory	,
		ClearFreesMemory
	)

Definition at line 1228 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 1216 of file fibonacci_heap_test.cc.

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

TEST() [27/43]

TEST	(	FibonacciHeapPerformance	,
		DISABLED_TimingComparison
	)

Definition at line 1242 of file fibonacci_heap_test.cc.

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

TEST() [28/43]

TEST	(	FibonacciHeapProperty	,
		AfterDecreaseKeys
	)

Definition at line 1175 of file fibonacci_heap_test.cc.

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

TEST() [29/43]

TEST	(	FibonacciHeapProperty	,
		AfterMerge
	)

Definition at line 1194 of file fibonacci_heap_test.cc.

References Aleph::DynList< T >::insert(), Aleph::maps(), and verify_heap_property().

TEST() [30/43]

TEST	(	FibonacciHeapProperty	,
		RandomInsertions
	)

Definition at line 1162 of file fibonacci_heap_test.cc.

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

TEST() [31/43]

TEST	(	FibonacciHeapRegression	,
		CascadingCutsChain
	)

Definition at line 1592 of file fibonacci_heap_test.cc.

References 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(), Aleph::maps(), and nodes.

TEST() [32/43]

TEST	(	FibonacciHeapRegression	,
		DeleteAloneRootWithChildren
	)

Definition at line 1567 of file fibonacci_heap_test.cc.

References 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(), Aleph::maps(), root(), and Aleph::Fibonacci_Heap< T, Compare >::size().

TEST() [33/43]

TEST	(	FibonacciHeapStress	,
		InterleavedOperations
	)

Definition at line 936 of file fibonacci_heap_test.cc.

References StlAlephIterator< SetName >::begin(), 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(), Aleph::maps(), and N.

TEST() [34/43]

TEST	(	FibonacciHeapStress	,
		LargeNumberOfExtractMin
	)

Definition at line 922 of file fibonacci_heap_test.cc.

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

TEST() [35/43]

TEST	(	FibonacciHeapStress	,
		LargeNumberOfInserts
	)

Definition at line 910 of file fibonacci_heap_test.cc.

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

TEST() [36/43]

TEST	(	FibonacciHeapStress	,
		ManyDecreaseKeys
	)

Definition at line 982 of file fibonacci_heap_test.cc.

References 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(), Aleph::maps(), N, and nodes.

TEST() [37/43]

TEST	(	FibonacciHeapStress	,
		ManyDeleteNodes
	)

Definition at line 1016 of file fibonacci_heap_test.cc.

References 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(), Aleph::maps(), N, nodes, Aleph::HTList::size(), and Aleph::Fibonacci_Heap< T, Compare >::size().

TEST() [38/43]

TEST	(	FibonacciHeapStress	,
		ManyMerges
	)

Definition at line 1041 of file fibonacci_heap_test.cc.

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

TEST() [39/43]

TEST	(	FibonacciHeapTypeAliases	,
		HandleType
	)

Definition at line 826 of file fibonacci_heap_test.cc.

TEST() [40/43]

TEST	(	FibonacciHeapTypeAliases	,
		ValueType
	)

Definition at line 820 of file fibonacci_heap_test.cc.

TEST() [41/43]

TEST	(	FibonacciHeapUsagePattern	,
		DijkstraSimulation
	)

Definition at line 1272 of file fibonacci_heap_test.cc.

References Aleph::DynList< T >::insert(), Aleph::HTList::is_empty(), Aleph::maps(), and operator<().

TEST() [42/43]

TEST	(	FibonacciMaxHeap	,
		BasicOperations
	)

Definition at line 835 of file fibonacci_heap_test.cc.

References Aleph::DynList< T >::insert(), and Aleph::maps().

TEST() [43/43]

TEST	(	FibonacciMaxHeap	,
		DecreaseKey
	)

Definition at line 849 of file fibonacci_heap_test.cc.

References Aleph::DynList< T >::insert(), and Aleph::maps().

TEST_F() [1/47]

TEST_F	(	FibonacciHeapTest	,
		ClearAndReuse
	)

Definition at line 803 of file fibonacci_heap_test.cc.

References Aleph::maps().

TEST_F() [2/47]

TEST_F	(	FibonacciHeapTest	,
		ClearEmptyHeap
	)

Definition at line 786 of file fibonacci_heap_test.cc.

References Aleph::maps().

TEST_F() [3/47]

TEST_F	(	FibonacciHeapTest	,
		ClearNonEmptyHeap
	)

Definition at line 792 of file fibonacci_heap_test.cc.

References Aleph::maps().

TEST_F() [4/47]

TEST_F	(	FibonacciHeapTest	,
		DecreaseKeyMoveSemantics
	)

Definition at line 405 of file fibonacci_heap_test.cc.

References Aleph::DynList< T >::insert(), and Aleph::maps().

TEST_F() [5/47]

TEST_F	(	FibonacciHeapTest	,
		DecreaseKeyTriggersCascadingCuts
	)

Definition at line 377 of file fibonacci_heap_test.cc.

References Aleph::maps(), nodes, and Aleph::HTList::size().

TEST_F() [6/47]

TEST_F	(	FibonacciHeapTest	,
		DecreaseKeyTriggersCut
	)

Definition at line 360 of file fibonacci_heap_test.cc.

References Aleph::maps().

TEST_F() [7/47]

TEST_F	(	FibonacciHeapTest	,
		DecreaseKeyWithInvalidIncreaseThrows
	)

Definition at line 349 of file fibonacci_heap_test.cc.

References Aleph::maps().

TEST_F() [8/47]

TEST_F	(	FibonacciHeapTest	,
		DecreaseKeyWithNullptrThrows
	)

Definition at line 355 of file fibonacci_heap_test.cc.

References Aleph::maps().

TEST_F() [9/47]

TEST_F	(	FibonacciHeapTest	,
		DeleteAllNodesOneByOne
	)

Definition at line 612 of file fibonacci_heap_test.cc.

References StlAlephIterator< SetName >::begin(), StlAlephIterator< SetName >::end(), Aleph::maps(), and nodes.

TEST_F() [10/47]

TEST_F	(	FibonacciHeapTest	,
		DeleteNodeFromDeepTree
	)

Definition at line 506 of file fibonacci_heap_test.cc.

References Aleph::maps(), nodes, and Aleph::HTList::size().

TEST_F() [11/47]

TEST_F	(	FibonacciHeapTest	,
		DeleteNodeMinimum
	)

Definition at line 475 of file fibonacci_heap_test.cc.

References Aleph::maps().

TEST_F() [12/47]

TEST_F	(	FibonacciHeapTest	,
		DeleteNodeNonMinimum
	)

Definition at line 487 of file fibonacci_heap_test.cc.

References Aleph::DynList< T >::insert(), and Aleph::maps().

TEST_F() [13/47]

TEST_F	(	FibonacciHeapTest	,
		DeleteNodeNullptrThrows
	)

Definition at line 501 of file fibonacci_heap_test.cc.

References Aleph::maps().

TEST_F() [14/47]

TEST_F	(	FibonacciHeapTest	,
		DeleteNodeSingleElement
	)

Definition at line 467 of file fibonacci_heap_test.cc.

References Aleph::maps().

TEST_F() [15/47]

TEST_F	(	FibonacciHeapTest	,
		DeleteSolitaryRootWithChildren
	)

Definition at line 537 of file fibonacci_heap_test.cc.

References Aleph::DynList< T >::insert(), and Aleph::maps().

TEST_F() [16/47]

TEST_F	(	FibonacciHeapTest	,
		DeleteSolitaryRootWithChildrenDirect
	)

Definition at line 582 of file fibonacci_heap_test.cc.

References Aleph::maps().

TEST_F() [17/47]

TEST_F	(	FibonacciHeapTest	,
		EmplaceConstruction
	)

Definition at line 217 of file fibonacci_heap_test.cc.

References FunctionalMethods< Container, T >::emplace(), and Aleph::maps().

TEST_F() [18/47]

TEST_F	(	FibonacciHeapTest	,
		ExtractMinMaintainsSortedOrder
	)

Definition at line 289 of file fibonacci_heap_test.cc.

References StlAlephIterator< SetName >::begin(), StlAlephIterator< SetName >::end(), Aleph::DynList< T >::insert(), and Aleph::maps().

TEST_F() [19/47]

TEST_F	(	FibonacciHeapTest	,
		ExtractMinMultipleElements
	)

Definition at line 277 of file fibonacci_heap_test.cc.

References Aleph::maps().

TEST_F() [20/47]

TEST_F	(	FibonacciHeapTest	,
		ExtractMinOnEmptyHeapThrows
	)

Definition at line 263 of file fibonacci_heap_test.cc.

References Aleph::maps().

TEST_F() [21/47]

TEST_F	(	FibonacciHeapTest	,
		ExtractMinSingleElement
	)

Definition at line 268 of file fibonacci_heap_test.cc.

References Aleph::maps().

TEST_F() [22/47]

TEST_F	(	FibonacciHeapTest	,
		ExtractMinWithDuplicates
	)

Definition at line 305 of file fibonacci_heap_test.cc.

References StlAlephIterator< SetName >::begin(), StlAlephIterator< SetName >::end(), Aleph::DynList< T >::insert(), and Aleph::maps().

TEST_F() [23/47]

TEST_F	(	FibonacciHeapTest	,
		GetMinAfterInserts
	)

Definition at line 241 of file fibonacci_heap_test.cc.

References Aleph::maps().

TEST_F() [24/47]

TEST_F	(	FibonacciHeapTest	,
		GetMinNodeOnEmptyHeap
	)

Definition at line 236 of file fibonacci_heap_test.cc.

References Aleph::maps().

TEST_F() [25/47]

TEST_F	(	FibonacciHeapTest	,
		GetMinOnEmptyHeapThrows
	)

Definition at line 231 of file fibonacci_heap_test.cc.

References Aleph::maps().

TEST_F() [26/47]

TEST_F	(	FibonacciHeapTest	,
		InsertAscendingOrder
	)

Definition at line 182 of file fibonacci_heap_test.cc.

References Aleph::maps().

TEST_F() [27/47]

TEST_F	(	FibonacciHeapTest	,
		InsertDescendingOrder
	)

Definition at line 173 of file fibonacci_heap_test.cc.

References Aleph::maps().

TEST_F() [28/47]

TEST_F	(	FibonacciHeapTest	,
		InsertDuplicates
	)

Definition at line 191 of file fibonacci_heap_test.cc.

References Aleph::maps().

TEST_F() [29/47]

TEST_F	(	FibonacciHeapTest	,
		InsertMultipleElements
	)

Definition at line 161 of file fibonacci_heap_test.cc.

References Aleph::maps().

TEST_F() [30/47]

TEST_F	(	FibonacciHeapTest	,
		InsertSingleElement
	)

Definition at line 151 of file fibonacci_heap_test.cc.

References Aleph::maps().

TEST_F() [31/47]

TEST_F	(	FibonacciHeapTest	,
		InsertWithMoveSemantics
	)

Definition at line 206 of file fibonacci_heap_test.cc.

References Aleph::DynList< T >::insert(), and Aleph::maps().

TEST_F() [32/47]

TEST_F	(	FibonacciHeapTest	,
		MergeEmptyHeaps
	)

Definition at line 637 of file fibonacci_heap_test.cc.

References Aleph::HTList::is_empty(), and Aleph::maps().

TEST_F() [33/47]

TEST_F	(	FibonacciHeapTest	,
		MergeEmptyIntoNonEmpty
	)

Definition at line 659 of file fibonacci_heap_test.cc.

References Aleph::DynList< T >::insert(), Aleph::maps(), and Aleph::HTList::size().

TEST_F() [34/47]

TEST_F	(	FibonacciHeapTest	,
		MergeIntoEmptyHeap
	)

Definition at line 646 of file fibonacci_heap_test.cc.

References Aleph::DynList< T >::insert(), Aleph::HTList::is_empty(), Aleph::maps(), and Aleph::HTList::size().

TEST_F() [35/47]

TEST_F	(	FibonacciHeapTest	,
		MergeLargeHeaps
	)

Definition at line 712 of file fibonacci_heap_test.cc.

References Aleph::DynList< T >::insert(), Aleph::HTList::is_empty(), Aleph::maps(), and Aleph::HTList::size().

TEST_F() [36/47]

TEST_F	(	FibonacciHeapTest	,
		MergeTwoNonEmptyHeaps
	)

Definition at line 671 of file fibonacci_heap_test.cc.

References Aleph::DynList< T >::insert(), Aleph::HTList::is_empty(), Aleph::maps(), and Aleph::HTList::size().

TEST_F() [37/47]

TEST_F	(	FibonacciHeapTest	,
		MergeWithRvalue
	)

Definition at line 698 of file fibonacci_heap_test.cc.

References Aleph::DynList< T >::insert(), Aleph::maps(), and Aleph::HTList::size().

TEST_F() [38/47]

TEST_F	(	FibonacciHeapTest	,
		SwapFreeFunction
	)

Definition at line 770 of file fibonacci_heap_test.cc.

References Aleph::DynList< T >::insert(), Aleph::maps(), and Aleph::swap().

TEST_F() [39/47]

TEST_F	(	FibonacciHeapTest	,
		SwapHeaps
	)

Definition at line 738 of file fibonacci_heap_test.cc.

References Aleph::DynList< T >::insert(), Aleph::maps(), Aleph::HTList::size(), and Aleph::DynList< T >::swap().

TEST_F() [40/47]

TEST_F	(	FibonacciHeapTest	,
		SwapWithEmptyHeap
	)

Definition at line 758 of file fibonacci_heap_test.cc.

References Aleph::DynList< T >::insert(), Aleph::HTList::is_empty(), Aleph::maps(), Aleph::HTList::size(), and Aleph::DynList< T >::swap().

TEST_F() [41/47]

TEST_F	(	FibonacciHeapTest	,
		UpdateKeyDecrease
	)

Definition at line 420 of file fibonacci_heap_test.cc.

References Aleph::maps().

TEST_F() [42/47]

TEST_F	(	FibonacciHeapTest	,
		UpdateKeyIncrease
	)

Definition at line 429 of file fibonacci_heap_test.cc.

References Aleph::maps().

TEST_F() [43/47]

TEST_F	(	FibonacciHeapTest	,
		UpdateKeyNullptrThrows
	)

Definition at line 458 of file fibonacci_heap_test.cc.

References Aleph::maps().

TEST_F() [44/47]

TEST_F	(	FibonacciHeapTest	,
		UpdateKeySameValue
	)

Definition at line 449 of file fibonacci_heap_test.cc.

References Aleph::maps().

TEST_F() [45/47]

TEST_F	(	FibonacciHeapWithDataTest	,
		DecreaseKeyNotAffectingMinimum
	)

Definition at line 333 of file fibonacci_heap_test.cc.

References Aleph::maps(), and nodes.

TEST_F() [46/47]

TEST_F	(	FibonacciHeapWithDataTest	,
		DecreaseKeyToNewMinimum
	)

Definition at line 323 of file fibonacci_heap_test.cc.

References Aleph::maps(), and nodes.

TEST_F() [47/47]

TEST_F	(	FibonacciHeapWithDataTest	,
		DecreaseKeyToSameValue
	)

Definition at line 342 of file fibonacci_heap_test.cc.

References Aleph::maps(), and nodes.

verify_heap_property()

template<typename T , typename Compare >

bool verify_heap_property

(

Fibonacci_Heap< T, Compare > &

heap

)

Definition at line 1143 of file fibonacci_heap_test.cc.

References Aleph::Fibonacci_Heap< T, Compare >::extract_min(), Aleph::Fibonacci_Heap< T, Compare >::is_empty(), Aleph::maps(), and Aleph::HTList::size().

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