15460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao//===- BinTreeTest.cpp ----------------------------------------------------===// 25460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao// 35460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao// The MCLinker Project 45460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao// 55460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao// This file is distributed under the University of Illinois Open Source 65460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao// License. See LICENSE.TXT for details. 75460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao// 85460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao//===----------------------------------------------------------------------===// 95460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao#include "BinTreeTest.h" 105460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1137b74a387bb3993387029859c2d9d051c41c724eStephen Hines#include "mcld/ADT/TypeTraits.h" 1237b74a387bb3993387029859c2d9d051c41c724eStephen Hines#include "mcld/InputTree.h" 135460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao#include <string> 145460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 155460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaousing namespace mcld; 165460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaousing namespace mcldtest; 175460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 185460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao// Constructor can do set-up work for all test here. 1937b74a387bb3993387029859c2d9d051c41c724eStephen HinesBinTreeTest::BinTreeTest() { 2037b74a387bb3993387029859c2d9d051c41c724eStephen Hines // create testee. modify it if need 2137b74a387bb3993387029859c2d9d051c41c724eStephen Hines m_pTestee = new BinaryTree<int>(); 225460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao} 235460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 245460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao// Destructor can do clean-up work that doesn't throw exceptions here. 2537b74a387bb3993387029859c2d9d051c41c724eStephen HinesBinTreeTest::~BinTreeTest() { 2637b74a387bb3993387029859c2d9d051c41c724eStephen Hines delete m_pTestee; 275460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao} 285460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 295460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao// SetUp() will be called immediately before each test. 3037b74a387bb3993387029859c2d9d051c41c724eStephen Hinesvoid BinTreeTest::SetUp() { 315460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao} 325460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 335460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao// TearDown() will be called immediately after each test. 3437b74a387bb3993387029859c2d9d051c41c724eStephen Hinesvoid BinTreeTest::TearDown() { 355460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao} 365460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 375460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao//==========================================================================// 385460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao// Testcases 395460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao// 405460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 4122add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao/// General 4237b74a387bb3993387029859c2d9d051c41c724eStephen HinesTEST_F(BinTreeTest, Two_non_null_tree_merge) { 435460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao BinaryTree<int>::iterator pos = m_pTestee->root(); 4437b74a387bb3993387029859c2d9d051c41c724eStephen Hines m_pTestee->join<TreeIteratorBase::Rightward>(pos, 0); 455460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao --pos; 4637b74a387bb3993387029859c2d9d051c41c724eStephen Hines m_pTestee->join<TreeIteratorBase::Rightward>(pos, 1); 4737b74a387bb3993387029859c2d9d051c41c724eStephen Hines m_pTestee->join<TreeIteratorBase::Leftward>(pos, 1); 485460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao --pos; 4937b74a387bb3993387029859c2d9d051c41c724eStephen Hines m_pTestee->join<TreeIteratorBase::Rightward>(pos, 2); 5037b74a387bb3993387029859c2d9d051c41c724eStephen Hines m_pTestee->join<TreeIteratorBase::Leftward>(pos, 2); 515460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 5237b74a387bb3993387029859c2d9d051c41c724eStephen Hines BinaryTree<int>* mergeTree = new BinaryTree<int>; 535460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao BinaryTree<int>::iterator pos2 = mergeTree->root(); 5437b74a387bb3993387029859c2d9d051c41c724eStephen Hines mergeTree->join<TreeIteratorBase::Rightward>(pos2, 1); 555460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao --pos2; 5637b74a387bb3993387029859c2d9d051c41c724eStephen Hines mergeTree->join<TreeIteratorBase::Rightward>(pos2, 1); 5737b74a387bb3993387029859c2d9d051c41c724eStephen Hines mergeTree->join<TreeIteratorBase::Leftward>(pos2, 1); 585460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 5937b74a387bb3993387029859c2d9d051c41c724eStephen Hines m_pTestee->merge<TreeIteratorBase::Rightward>(pos, *mergeTree); 605460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao delete mergeTree; 6137b74a387bb3993387029859c2d9d051c41c724eStephen Hines EXPECT_TRUE(m_pTestee->size() == 8); 625460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao} 635460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 645460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao/// ---- TEST - 2 ---- 6537b74a387bb3993387029859c2d9d051c41c724eStephen HinesTEST_F(BinTreeTest, A_null_tree_merge_a_non_null_tree) { 665460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao BinaryTree<int>::iterator pos = m_pTestee->root(); 6722add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 6837b74a387bb3993387029859c2d9d051c41c724eStephen Hines BinaryTree<int>* mergeTree = new BinaryTree<int>; 6937b74a387bb3993387029859c2d9d051c41c724eStephen Hines mergeTree->join<TreeIteratorBase::Rightward>(pos, 0); 705460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao --pos; 7137b74a387bb3993387029859c2d9d051c41c724eStephen Hines mergeTree->join<TreeIteratorBase::Rightward>(pos, 1); 7237b74a387bb3993387029859c2d9d051c41c724eStephen Hines mergeTree->join<TreeIteratorBase::Leftward>(pos, 1); 735460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao --pos; 7437b74a387bb3993387029859c2d9d051c41c724eStephen Hines mergeTree->join<TreeIteratorBase::Rightward>(pos, 2); 7537b74a387bb3993387029859c2d9d051c41c724eStephen Hines mergeTree->join<TreeIteratorBase::Leftward>(pos, 2); 765460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 7737b74a387bb3993387029859c2d9d051c41c724eStephen Hines m_pTestee->merge<TreeIteratorBase::Rightward>(pos, *mergeTree); 785460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 795460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao delete mergeTree; 8037b74a387bb3993387029859c2d9d051c41c724eStephen Hines EXPECT_TRUE(m_pTestee->size() == 5); 815460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao} 825460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 8337b74a387bb3993387029859c2d9d051c41c724eStephen HinesTEST_F(BinTreeTest, A_non_null_tree_merge_a_null_tree) { 845460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao BinaryTree<int>::iterator pos = m_pTestee->root(); 8537b74a387bb3993387029859c2d9d051c41c724eStephen Hines m_pTestee->join<TreeIteratorBase::Rightward>(pos, 0); 865460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao --pos; 8737b74a387bb3993387029859c2d9d051c41c724eStephen Hines m_pTestee->join<TreeIteratorBase::Rightward>(pos, 1); 8837b74a387bb3993387029859c2d9d051c41c724eStephen Hines m_pTestee->join<TreeIteratorBase::Leftward>(pos, 1); 895460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao --pos; 9037b74a387bb3993387029859c2d9d051c41c724eStephen Hines m_pTestee->join<TreeIteratorBase::Rightward>(pos, 2); 9137b74a387bb3993387029859c2d9d051c41c724eStephen Hines m_pTestee->join<TreeIteratorBase::Leftward>(pos, 2); 9222add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 9337b74a387bb3993387029859c2d9d051c41c724eStephen Hines BinaryTree<int>* mergeTree = new BinaryTree<int>; 9422add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao BinaryTree<int>::iterator pos2 = mergeTree->root(); 9537b74a387bb3993387029859c2d9d051c41c724eStephen Hines mergeTree->merge<TreeIteratorBase::Rightward>(pos2, *m_pTestee); 965460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 9737b74a387bb3993387029859c2d9d051c41c724eStephen Hines // delete m_pTestee; 9837b74a387bb3993387029859c2d9d051c41c724eStephen Hines EXPECT_TRUE(mergeTree->size() == 5); 995460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao delete mergeTree; 1005460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao} 1015460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 10237b74a387bb3993387029859c2d9d051c41c724eStephen HinesTEST_F(BinTreeTest, Two_null_tree_merge) { 1035460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao BinaryTree<int>::iterator pos = m_pTestee->root(); 10422add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 10537b74a387bb3993387029859c2d9d051c41c724eStephen Hines BinaryTree<int>* mergeTree = new BinaryTree<int>; 10622add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao BinaryTree<int>::iterator pos2 = mergeTree->root(); 1075460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 10837b74a387bb3993387029859c2d9d051c41c724eStephen Hines mergeTree->merge<TreeIteratorBase::Rightward>(pos2, *m_pTestee); 1095460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 11037b74a387bb3993387029859c2d9d051c41c724eStephen Hines // delete m_pTestee; 11137b74a387bb3993387029859c2d9d051c41c724eStephen Hines EXPECT_TRUE(mergeTree->size() == 0); 1125460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao delete mergeTree; 1135460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao} 1145460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 11537b74a387bb3993387029859c2d9d051c41c724eStephen HinesTEST_F(BinTreeTest, DFSIterator_BasicTraversal) { 116f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines int a = 111, b = 10, c = 9, d = 8, e = 7; 1175460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao BinaryTree<int>::iterator pos = m_pTestee->root(); 11822add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 11937b74a387bb3993387029859c2d9d051c41c724eStephen Hines m_pTestee->join<InputTree::Inclusive>(pos, a); 1205460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao pos.move<InputTree::Inclusive>(); 12137b74a387bb3993387029859c2d9d051c41c724eStephen Hines m_pTestee->join<InputTree::Positional>(pos, b); 12237b74a387bb3993387029859c2d9d051c41c724eStephen Hines m_pTestee->join<InputTree::Inclusive>(pos, c); 1235460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao pos.move<InputTree::Inclusive>(); 12437b74a387bb3993387029859c2d9d051c41c724eStephen Hines m_pTestee->join<InputTree::Positional>(pos, d); 12537b74a387bb3993387029859c2d9d051c41c724eStephen Hines m_pTestee->join<InputTree::Inclusive>(pos, e); 12622add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 12722add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao BinaryTree<int>::dfs_iterator dfs_it = m_pTestee->dfs_begin(); 12822add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao BinaryTree<int>::dfs_iterator dfs_end = m_pTestee->dfs_end(); 1295460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1305460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao ASSERT_EQ(111, **dfs_it); 1315460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao ++dfs_it; 132f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines EXPECT_EQ(9, **dfs_it); 1335460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao ++dfs_it; 134f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines EXPECT_EQ(7, **dfs_it); 1355460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao ++dfs_it; 136f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines EXPECT_EQ(8, **dfs_it); 1375460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao ++dfs_it; 138f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines EXPECT_EQ(10, **dfs_it); 1395460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao ++dfs_it; 14037b74a387bb3993387029859c2d9d051c41c724eStephen Hines EXPECT_TRUE(dfs_it == dfs_end); 1415460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao} 1425460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 14337b74a387bb3993387029859c2d9d051c41c724eStephen HinesTEST_F(BinTreeTest, DFSIterator_RightMostTree) { 144f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines int a = 0, b = 1, c = 2, d = 3, e = 4; 1455460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao BinaryTree<int>::iterator pos = m_pTestee->root(); 14637b74a387bb3993387029859c2d9d051c41c724eStephen Hines m_pTestee->join<InputTree::Inclusive>(pos, a); 1475460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao pos.move<InputTree::Inclusive>(); 14837b74a387bb3993387029859c2d9d051c41c724eStephen Hines m_pTestee->join<InputTree::Positional>(pos, b); 1495460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao pos.move<InputTree::Positional>(); 15037b74a387bb3993387029859c2d9d051c41c724eStephen Hines m_pTestee->join<InputTree::Positional>(pos, c); 1515460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao pos.move<InputTree::Positional>(); 15237b74a387bb3993387029859c2d9d051c41c724eStephen Hines m_pTestee->join<InputTree::Positional>(pos, d); 1535460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao pos.move<InputTree::Positional>(); 15437b74a387bb3993387029859c2d9d051c41c724eStephen Hines m_pTestee->join<InputTree::Positional>(pos, e); 15522add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 15622add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao BinaryTree<int>::dfs_iterator dfs_it = m_pTestee->dfs_begin(); 15722add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao BinaryTree<int>::dfs_iterator dfs_end = m_pTestee->dfs_end(); 1585460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1595460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao ASSERT_EQ(0, **dfs_it); 1605460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao ++dfs_it; 1615460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao ASSERT_EQ(1, **dfs_it); 1625460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao ++dfs_it; 1635460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao ASSERT_EQ(2, **dfs_it); 1645460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao ++dfs_it; 1655460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao ASSERT_EQ(3, **dfs_it); 1665460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao ++dfs_it; 1675460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao ASSERT_EQ(4, **dfs_it); 1685460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao ++dfs_it; 16937b74a387bb3993387029859c2d9d051c41c724eStephen Hines ASSERT_TRUE(dfs_it == dfs_end); 1705460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao} 1715460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 17237b74a387bb3993387029859c2d9d051c41c724eStephen HinesTEST_F(BinTreeTest, DFSIterator_SingleNode) { 1735460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao BinaryTree<int>::iterator pos = m_pTestee->root(); 17437b74a387bb3993387029859c2d9d051c41c724eStephen Hines m_pTestee->join<InputTree::Inclusive>(pos, 0); 17522add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao BinaryTree<int>::dfs_iterator dfs_it = m_pTestee->dfs_begin(); 17622add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao BinaryTree<int>::dfs_iterator dfs_end = m_pTestee->dfs_end(); 1775460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao int counter = 0; 17837b74a387bb3993387029859c2d9d051c41c724eStephen Hines while (dfs_it != dfs_end) { 1795460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao ++counter; 1805460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao ++dfs_it; 1815460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 1825460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao ASSERT_EQ(1, counter); 1835460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao} 1845460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 18537b74a387bb3993387029859c2d9d051c41c724eStephen HinesTEST_F(BinTreeTest, BFSIterator_BasicTraversal) { 186f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines int a = 111, b = 10, c = 9, d = 8, e = 7; 1875460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao BinaryTree<int>::iterator pos = m_pTestee->root(); 18822add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 18937b74a387bb3993387029859c2d9d051c41c724eStephen Hines m_pTestee->join<InputTree::Inclusive>(pos, a); 1905460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao pos.move<InputTree::Inclusive>(); 19137b74a387bb3993387029859c2d9d051c41c724eStephen Hines m_pTestee->join<InputTree::Positional>(pos, b); 19237b74a387bb3993387029859c2d9d051c41c724eStephen Hines m_pTestee->join<InputTree::Inclusive>(pos, c); 1935460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao pos.move<InputTree::Inclusive>(); 19437b74a387bb3993387029859c2d9d051c41c724eStephen Hines m_pTestee->join<InputTree::Positional>(pos, d); 19537b74a387bb3993387029859c2d9d051c41c724eStephen Hines m_pTestee->join<InputTree::Inclusive>(pos, e); 19622add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 19722add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao BinaryTree<int>::bfs_iterator bfs_it = m_pTestee->bfs_begin(); 19822add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao BinaryTree<int>::bfs_iterator bfs_end = m_pTestee->bfs_end(); 1995460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 2005460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao ASSERT_EQ(111, **bfs_it); 2015460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao ++bfs_it; 2025460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao ASSERT_EQ(10, **bfs_it); 2035460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao ++bfs_it; 2045460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao ASSERT_EQ(9, **bfs_it); 2055460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao ++bfs_it; 2065460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao ASSERT_EQ(8, **bfs_it); 2075460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao ++bfs_it; 2085460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao ASSERT_EQ(7, **bfs_it); 2095460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao ++bfs_it; 21037b74a387bb3993387029859c2d9d051c41c724eStephen Hines ASSERT_TRUE(bfs_it == bfs_end); 21122add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao bfs_it = m_pTestee->bfs_begin(); 21222add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao bfs_end = m_pTestee->bfs_end(); 2135460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao} 2145460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 21537b74a387bb3993387029859c2d9d051c41c724eStephen HinesTEST_F(BinTreeTest, BFSIterator_RightMostTree) { 216f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines int a = 0, b = 1, c = 2, d = 3, e = 4; 2175460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao BinaryTree<int>::iterator pos = m_pTestee->root(); 21837b74a387bb3993387029859c2d9d051c41c724eStephen Hines m_pTestee->join<InputTree::Inclusive>(pos, a); 2195460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao pos.move<InputTree::Inclusive>(); 22037b74a387bb3993387029859c2d9d051c41c724eStephen Hines m_pTestee->join<InputTree::Positional>(pos, b); 2215460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao pos.move<InputTree::Positional>(); 22237b74a387bb3993387029859c2d9d051c41c724eStephen Hines m_pTestee->join<InputTree::Positional>(pos, c); 2235460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao pos.move<InputTree::Positional>(); 22437b74a387bb3993387029859c2d9d051c41c724eStephen Hines m_pTestee->join<InputTree::Positional>(pos, d); 2255460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao pos.move<InputTree::Positional>(); 22637b74a387bb3993387029859c2d9d051c41c724eStephen Hines m_pTestee->join<InputTree::Positional>(pos, e); 22722add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 22822add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao BinaryTree<int>::bfs_iterator bfs_it = m_pTestee->bfs_begin(); 22922add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao BinaryTree<int>::bfs_iterator bfs_end = m_pTestee->bfs_end(); 2305460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 2315460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao ASSERT_EQ(0, **bfs_it); 2325460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao ++bfs_it; 2335460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao ASSERT_EQ(1, **bfs_it); 2345460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao ++bfs_it; 2355460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao ASSERT_EQ(2, **bfs_it); 2365460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao ++bfs_it; 2375460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao ASSERT_EQ(3, **bfs_it); 2385460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao ++bfs_it; 2395460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao ASSERT_EQ(4, **bfs_it); 2405460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao ++bfs_it; 24137b74a387bb3993387029859c2d9d051c41c724eStephen Hines ASSERT_TRUE(bfs_it == bfs_end); 2425460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao} 2435460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 24437b74a387bb3993387029859c2d9d051c41c724eStephen HinesTEST_F(BinTreeTest, BFSIterator_SingleNode) { 2455460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao BinaryTree<int>::iterator pos = m_pTestee->root(); 24637b74a387bb3993387029859c2d9d051c41c724eStephen Hines m_pTestee->join<InputTree::Inclusive>(pos, 0); 24722add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao BinaryTree<int>::bfs_iterator bfs_it = m_pTestee->bfs_begin(); 24822add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao BinaryTree<int>::bfs_iterator bfs_end = m_pTestee->bfs_end(); 2495460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao int counter = 0; 25037b74a387bb3993387029859c2d9d051c41c724eStephen Hines while (bfs_it != bfs_end) { 2515460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao ++counter; 2525460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao ++bfs_it; 2535460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 2545460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao ASSERT_EQ(1, counter); 2555460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao} 2565460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 25737b74a387bb3993387029859c2d9d051c41c724eStephen HinesTEST_F(BinTreeTest, TreeIterator) { 258f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines int a = 0, b = 1, c = 2, d = 3, e = 4, f = 5; 25922add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao BinaryTree<int>::iterator pos = m_pTestee->root(); 26037b74a387bb3993387029859c2d9d051c41c724eStephen Hines m_pTestee->join<InputTree::Inclusive>(pos, a); 26122add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao pos.move<InputTree::Inclusive>(); 26237b74a387bb3993387029859c2d9d051c41c724eStephen Hines m_pTestee->join<InputTree::Positional>(pos, b); 26322add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao pos.move<InputTree::Positional>(); 26437b74a387bb3993387029859c2d9d051c41c724eStephen Hines m_pTestee->join<InputTree::Inclusive>(pos, c); 26537b74a387bb3993387029859c2d9d051c41c724eStephen Hines m_pTestee->join<InputTree::Positional>(pos, f); 26622add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao pos.move<InputTree::Inclusive>(); 26737b74a387bb3993387029859c2d9d051c41c724eStephen Hines m_pTestee->join<InputTree::Positional>(pos, d); 26822add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao pos.move<InputTree::Positional>(); 26937b74a387bb3993387029859c2d9d051c41c724eStephen Hines m_pTestee->join<InputTree::Positional>(pos, e); 27022add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 27122add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao BinaryTree<int>::iterator it = m_pTestee->begin(); 27222add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao BinaryTree<int>::iterator end = m_pTestee->end(); 27322add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 27422add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao ASSERT_EQ(0, **it); 27522add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao ++it; 27622add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao ASSERT_EQ(1, **it); 27722add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao --it; 27822add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao ASSERT_EQ(2, **it); 27922add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao ++it; 28022add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao ASSERT_EQ(3, **it); 28122add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao ++it; 28222add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao ASSERT_EQ(4, **it); 28322add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao ++it; 28422add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao ASSERT_TRUE(it == end); 28522add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 28622add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao it = m_pTestee->begin(); 28722add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao ++it; 28822add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao ++it; 28922add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao ASSERT_EQ(5, **it); 29022add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao ++it; 29122add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao ASSERT_TRUE(it == end); 29222add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao} 293