splay-tree.cc File Reference

Tests for Splay Tree. More...

#include <algorithm>
#include <vector>
#include <gtest/gtest.h>
#include <tpl_splay_tree.H>

Include dependency graph for splay-tree.cc:

Go to the source code of this file.

Functions
	TEST (SplayTree, EmptyTreeProperties)
	TEST (SplayTree, InsertSingleElementBecomesRoot)
	TEST (SplayTree, InsertRejectsDuplicates)
	TEST (SplayTree, InsertDupAllowsDuplicates)
	TEST (SplayTree, SearchFindsExistingKeyAndSplaysToRoot)
	TEST (SplayTree, SearchMissingSplaysToExtreme)
	TEST (SplayTree, SearchOrInsertDoesNotInsertDuplicate)
	TEST (SplayTree, RemoveExistingKeyDetachesNode)
	TEST (SplayTree, RemoveSplaysMaxOfLeftSubtree)
	TEST (SplayTree, StatefulComparatorAffectsEquality)

Detailed Description

Tests for Splay Tree.

Definition in file splay-tree.cc.

Function Documentation

TEST() [1/10]

TEST	(	SplayTree	,
		EmptyTreeProperties
	)

Definition at line 128 of file splay-tree.cc.

References Aleph::divide_and_conquer_partition_dp(), GenTdSplayTree< NodeType, Key, Compare >::getRoot(), GenTdSplayTree< NodeType, Key, Compare >::remove(), GenTdSplayTree< NodeType, Key, Compare >::search(), and GenTdSplayTree< NodeType, Key, Compare >::verify().

TEST() [2/10]

TEST	(	SplayTree	,
		InsertDupAllowsDuplicates
	)

Definition at line 170 of file splay-tree.cc.

References Aleph::divide_and_conquer_partition_dp(), inorder_keys(), and keys.

TEST() [3/10]

TEST	(	SplayTree	,
		InsertRejectsDuplicates
	)

Definition at line 152 of file splay-tree.cc.

References Aleph::divide_and_conquer_partition_dp(), and QuadTree::insert().

TEST() [4/10]

TEST	(	SplayTree	,
		InsertSingleElementBecomesRoot
	)

Definition at line 137 of file splay-tree.cc.

References Aleph::divide_and_conquer_partition_dp(), and QuadTree::insert().

TEST() [5/10]

TEST	(	SplayTree	,
		RemoveExistingKeyDetachesNode
	)

Definition at line 246 of file splay-tree.cc.

References Aleph::divide_and_conquer_partition_dp(), inorder_keys(), QuadTree::insert(), k, KEY, keys, LLINK, QuadTree::remove(), RLINK, and QuadTree::search().

TEST() [6/10]

TEST	(	SplayTree	,
		RemoveSplaysMaxOfLeftSubtree
	)

Definition at line 273 of file splay-tree.cc.

References Aleph::divide_and_conquer_partition_dp(), QuadTree::insert(), k, KEY, and QuadTree::remove().

TEST() [7/10]

TEST	(	SplayTree	,
		SearchFindsExistingKeyAndSplaysToRoot
	)

Definition at line 188 of file splay-tree.cc.

References Aleph::divide_and_conquer_partition_dp(), QuadTree::insert(), k, KEY, and QuadTree::search().

TEST() [8/10]

TEST	(	SplayTree	,
		SearchMissingSplaysToExtreme
	)

Definition at line 206 of file splay-tree.cc.

References Aleph::divide_and_conquer_partition_dp(), QuadTree::insert(), k, KEY, and QuadTree::search().

TEST() [9/10]

TEST	(	SplayTree	,
		SearchOrInsertDoesNotInsertDuplicate
	)

Definition at line 227 of file splay-tree.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST() [10/10]

TEST	(	SplayTree	,
		StatefulComparatorAffectsEquality
	)

Definition at line 294 of file splay-tree.cc.

References Aleph::divide_and_conquer_partition_dp(), QuadTree::insert(), and QuadTree::search().