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 1122add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao#include <mcld/ADT/TypeTraits.h> 1222add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao#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 195460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao// Constructor can do set-up work for all test here. 205460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei LiaoBinTreeTest::BinTreeTest() 215460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao{ 225460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao // create testee. modify it if need 235460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao m_pTestee = new BinaryTree<int>(); 245460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao} 255460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 265460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao// Destructor can do clean-up work that doesn't throw exceptions here. 275460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei LiaoBinTreeTest::~BinTreeTest() 285460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao{ 295460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao delete m_pTestee; 305460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao} 315460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 325460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao// SetUp() will be called immediately before each test. 335460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaovoid BinTreeTest::SetUp() 345460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao{ 355460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao} 365460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 375460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao// TearDown() will be called immediately after each test. 385460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaovoid BinTreeTest::TearDown() 395460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao{ 405460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao} 415460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 425460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao//==========================================================================// 435460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao// Testcases 445460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao// 455460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 465460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 4722add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao/// General 4822add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei LiaoTEST_F( BinTreeTest,Two_non_null_tree_merge) 495460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao{ 505460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao BinaryTree<int>::iterator pos = m_pTestee->root(); 515460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao m_pTestee->join<TreeIteratorBase::Rightward>(pos,0); 525460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao --pos; 535460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao m_pTestee->join<TreeIteratorBase::Rightward>(pos,1); 545460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao m_pTestee->join<TreeIteratorBase::Leftward>(pos,1); 555460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao --pos; 565460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao m_pTestee->join<TreeIteratorBase::Rightward>(pos,2); 575460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao m_pTestee->join<TreeIteratorBase::Leftward>(pos,2); 585460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 595460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao BinaryTree<int> *mergeTree = new BinaryTree<int>; 605460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao BinaryTree<int>::iterator pos2 = mergeTree->root(); 615460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao mergeTree->join<TreeIteratorBase::Rightward>(pos2,1); 625460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao --pos2; 635460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao mergeTree->join<TreeIteratorBase::Rightward>(pos2,1); 645460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao mergeTree->join<TreeIteratorBase::Leftward>(pos2,1); 655460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 6622add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao m_pTestee->merge<TreeIteratorBase::Rightward>(pos,*mergeTree); 675460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao delete mergeTree; 685460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao EXPECT_TRUE(m_pTestee->size()==8); 695460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao} 705460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 715460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao/// ---- TEST - 2 ---- 7222add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei LiaoTEST_F( BinTreeTest, A_null_tree_merge_a_non_null_tree) 7322add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao{ 745460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao BinaryTree<int>::iterator pos = m_pTestee->root(); 7522add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 765460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao BinaryTree<int> *mergeTree = new BinaryTree<int>; 775460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao mergeTree->join<TreeIteratorBase::Rightward>(pos,0); 785460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao --pos; 795460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao mergeTree->join<TreeIteratorBase::Rightward>(pos,1); 805460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao mergeTree->join<TreeIteratorBase::Leftward>(pos,1); 815460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao --pos; 825460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao mergeTree->join<TreeIteratorBase::Rightward>(pos,2); 835460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao mergeTree->join<TreeIteratorBase::Leftward>(pos,2); 845460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 8522add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao m_pTestee->merge<TreeIteratorBase::Rightward>(pos,*mergeTree); 865460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 875460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao delete mergeTree; 885460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao EXPECT_TRUE(m_pTestee->size()==5); 895460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao} 905460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 9122add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei LiaoTEST_F( BinTreeTest, A_non_null_tree_merge_a_null_tree) 9222add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao{ 935460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao BinaryTree<int>::iterator pos = m_pTestee->root(); 945460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao m_pTestee->join<TreeIteratorBase::Rightward>(pos,0); 955460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao --pos; 965460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao m_pTestee->join<TreeIteratorBase::Rightward>(pos,1); 975460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao m_pTestee->join<TreeIteratorBase::Leftward>(pos,1); 985460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao --pos; 995460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao m_pTestee->join<TreeIteratorBase::Rightward>(pos,2); 1005460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao m_pTestee->join<TreeIteratorBase::Leftward>(pos,2); 10122add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 1025460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao BinaryTree<int> *mergeTree = new BinaryTree<int>; 10322add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao BinaryTree<int>::iterator pos2 = mergeTree->root(); 10422add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao mergeTree->merge<TreeIteratorBase::Rightward>(pos2,*m_pTestee); 1055460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1065460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao //delete m_pTestee; 1075460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao EXPECT_TRUE(mergeTree->size()==5); 1085460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao delete mergeTree; 1095460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao} 1105460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 11122add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei LiaoTEST_F( BinTreeTest, Two_null_tree_merge) 11222add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao{ 1135460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao BinaryTree<int>::iterator pos = m_pTestee->root(); 11422add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 1155460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao BinaryTree<int> *mergeTree = new BinaryTree<int>; 11622add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao BinaryTree<int>::iterator pos2 = mergeTree->root(); 1175460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 11822add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao mergeTree->merge<TreeIteratorBase::Rightward>(pos2,*m_pTestee); 1195460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1205460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao //delete m_pTestee; 1215460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao EXPECT_TRUE(mergeTree->size()==0); 1225460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao delete mergeTree; 1235460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao} 1245460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1255460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei LiaoTEST_F( BinTreeTest, DFSIterator_BasicTraversal) 1265460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao{ 1275460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao int a = 111; 1285460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao BinaryTree<int>::iterator pos = m_pTestee->root(); 12922add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 1305460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao m_pTestee->join<InputTree::Inclusive>(pos,a); 1315460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao pos.move<InputTree::Inclusive>(); 1325460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao m_pTestee->join<InputTree::Positional>(pos,10); 1335460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao m_pTestee->join<InputTree::Inclusive>(pos,9); 1345460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao pos.move<InputTree::Inclusive>(); 1355460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao m_pTestee->join<InputTree::Positional>(pos,8); 1365460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao m_pTestee->join<InputTree::Inclusive>(pos,7); 13722add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 13822add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao BinaryTree<int>::dfs_iterator dfs_it = m_pTestee->dfs_begin(); 13922add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao BinaryTree<int>::dfs_iterator dfs_end = m_pTestee->dfs_end(); 1405460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1415460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao ASSERT_EQ(111, **dfs_it); 1425460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao ++dfs_it; 1435460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao ASSERT_EQ(9, **dfs_it); 1445460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao ++dfs_it; 1455460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao ASSERT_EQ(7, **dfs_it); 1465460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao ++dfs_it; 1475460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao ASSERT_EQ(8, **dfs_it); 1485460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao ++dfs_it; 1495460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao ASSERT_EQ(10, **dfs_it); 1505460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao ++dfs_it; 1515460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao ASSERT_TRUE( dfs_it == dfs_end); 15222add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao BinaryTree<int>::bfs_iterator bfs_it = m_pTestee->bfs_begin(); 15322add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao BinaryTree<int>::bfs_iterator bfs_end = m_pTestee->bfs_end(); 1545460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao} 1555460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1565460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei LiaoTEST_F( BinTreeTest, DFSIterator_RightMostTree) 1575460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao{ 1585460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao BinaryTree<int>::iterator pos = m_pTestee->root(); 1595460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao m_pTestee->join<InputTree::Inclusive>(pos,0); 1605460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao pos.move<InputTree::Inclusive>(); 1615460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao m_pTestee->join<InputTree::Positional>(pos,1); 1625460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao pos.move<InputTree::Positional>(); 1635460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao m_pTestee->join<InputTree::Positional>(pos,2); 1645460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao pos.move<InputTree::Positional>(); 1655460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao m_pTestee->join<InputTree::Positional>(pos,3); 1665460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao pos.move<InputTree::Positional>(); 1675460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao m_pTestee->join<InputTree::Positional>(pos,4); 16822add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 16922add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao BinaryTree<int>::dfs_iterator dfs_it = m_pTestee->dfs_begin(); 17022add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao BinaryTree<int>::dfs_iterator dfs_end = m_pTestee->dfs_end(); 1715460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1725460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao ASSERT_EQ(0, **dfs_it); 1735460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao ++dfs_it; 1745460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao ASSERT_EQ(1, **dfs_it); 1755460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao ++dfs_it; 1765460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao ASSERT_EQ(2, **dfs_it); 1775460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao ++dfs_it; 1785460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao ASSERT_EQ(3, **dfs_it); 1795460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao ++dfs_it; 1805460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao ASSERT_EQ(4, **dfs_it); 1815460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao ++dfs_it; 1825460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao ASSERT_TRUE( dfs_it == dfs_end); 1835460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao} 1845460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1855460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1865460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei LiaoTEST_F( BinTreeTest, DFSIterator_SingleNode) 1875460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao{ 1885460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao BinaryTree<int>::iterator pos = m_pTestee->root(); 1895460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao m_pTestee->join<InputTree::Inclusive>(pos,0); 19022add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao BinaryTree<int>::dfs_iterator dfs_it = m_pTestee->dfs_begin(); 19122add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao BinaryTree<int>::dfs_iterator dfs_end = m_pTestee->dfs_end(); 1925460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao int counter = 0; 1935460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao while( dfs_it != dfs_end ) { 1945460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao ++counter; 1955460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao ++dfs_it; 1965460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 1975460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao ASSERT_EQ(1, counter); 1985460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao} 1995460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 2005460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei LiaoTEST_F( BinTreeTest, BFSIterator_BasicTraversal) 2015460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao{ 2025460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao int a = 111; 2035460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao BinaryTree<int>::iterator pos = m_pTestee->root(); 20422add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 2055460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao m_pTestee->join<InputTree::Inclusive>(pos,a); 2065460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao pos.move<InputTree::Inclusive>(); 2075460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao m_pTestee->join<InputTree::Positional>(pos,10); 2085460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao m_pTestee->join<InputTree::Inclusive>(pos,9); 2095460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao pos.move<InputTree::Inclusive>(); 2105460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao m_pTestee->join<InputTree::Positional>(pos,8); 2115460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao m_pTestee->join<InputTree::Inclusive>(pos,7); 21222add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 21322add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao BinaryTree<int>::bfs_iterator bfs_it = m_pTestee->bfs_begin(); 21422add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao BinaryTree<int>::bfs_iterator bfs_end = m_pTestee->bfs_end(); 2155460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 2165460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao ASSERT_EQ(111, **bfs_it); 2175460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao ++bfs_it; 2185460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao ASSERT_EQ(10, **bfs_it); 2195460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao ++bfs_it; 2205460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao ASSERT_EQ(9, **bfs_it); 2215460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao ++bfs_it; 2225460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao ASSERT_EQ(8, **bfs_it); 2235460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao ++bfs_it; 2245460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao ASSERT_EQ(7, **bfs_it); 2255460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao ++bfs_it; 2265460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao ASSERT_TRUE(bfs_it == bfs_end); 22722add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao bfs_it = m_pTestee->bfs_begin(); 22822add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao bfs_end = m_pTestee->bfs_end(); 2295460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao} 2305460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 2315460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei LiaoTEST_F( BinTreeTest, BFSIterator_RightMostTree) 2325460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao{ 2335460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao BinaryTree<int>::iterator pos = m_pTestee->root(); 2345460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao m_pTestee->join<InputTree::Inclusive>(pos,0); 2355460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao pos.move<InputTree::Inclusive>(); 2365460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao m_pTestee->join<InputTree::Positional>(pos,1); 2375460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao pos.move<InputTree::Positional>(); 2385460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao m_pTestee->join<InputTree::Positional>(pos,2); 2395460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao pos.move<InputTree::Positional>(); 2405460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao m_pTestee->join<InputTree::Positional>(pos,3); 2415460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao pos.move<InputTree::Positional>(); 2425460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao m_pTestee->join<InputTree::Positional>(pos,4); 24322add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 24422add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao BinaryTree<int>::bfs_iterator bfs_it = m_pTestee->bfs_begin(); 24522add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao BinaryTree<int>::bfs_iterator bfs_end = m_pTestee->bfs_end(); 2465460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 2475460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao ASSERT_EQ(0, **bfs_it); 2485460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao ++bfs_it; 2495460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao ASSERT_EQ(1, **bfs_it); 2505460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao ++bfs_it; 2515460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao ASSERT_EQ(2, **bfs_it); 2525460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao ++bfs_it; 2535460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao ASSERT_EQ(3, **bfs_it); 2545460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao ++bfs_it; 2555460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao ASSERT_EQ(4, **bfs_it); 2565460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao ++bfs_it; 2575460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao ASSERT_TRUE( bfs_it == bfs_end); 2585460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao} 2595460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 2605460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 2615460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei LiaoTEST_F( BinTreeTest, BFSIterator_SingleNode) 2625460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao{ 2635460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao BinaryTree<int>::iterator pos = m_pTestee->root(); 2645460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao m_pTestee->join<InputTree::Inclusive>(pos,0); 26522add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao BinaryTree<int>::bfs_iterator bfs_it = m_pTestee->bfs_begin(); 26622add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao BinaryTree<int>::bfs_iterator bfs_end = m_pTestee->bfs_end(); 2675460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao int counter = 0; 2685460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao while( bfs_it != bfs_end ) { 2695460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao ++counter; 2705460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao ++bfs_it; 2715460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 2725460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao ASSERT_EQ(1, counter); 2735460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao} 2745460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 27522add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei LiaoTEST_F( BinTreeTest, TreeIterator) 27622add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao{ 27722add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao BinaryTree<int>::iterator pos = m_pTestee->root(); 27822add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao m_pTestee->join<InputTree::Inclusive>(pos,0); 27922add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao pos.move<InputTree::Inclusive>(); 28022add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao m_pTestee->join<InputTree::Positional>(pos,1); 28122add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao pos.move<InputTree::Positional>(); 28222add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao m_pTestee->join<InputTree::Inclusive>(pos,2); 28322add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao m_pTestee->join<InputTree::Positional>(pos,5); 28422add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao pos.move<InputTree::Inclusive>(); 28522add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao m_pTestee->join<InputTree::Positional>(pos,3); 28622add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao pos.move<InputTree::Positional>(); 28722add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao m_pTestee->join<InputTree::Positional>(pos,4); 28822add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 28922add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao BinaryTree<int>::iterator it = m_pTestee->begin(); 29022add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao BinaryTree<int>::iterator end = m_pTestee->end(); 29122add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 29222add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao ASSERT_EQ(0, **it); 29322add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao ++it; 29422add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao ASSERT_EQ(1, **it); 29522add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao --it; 29622add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao ASSERT_EQ(2, **it); 29722add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao ++it; 29822add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao ASSERT_EQ(3, **it); 29922add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao ++it; 30022add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao ASSERT_EQ(4, **it); 30122add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao ++it; 30222add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao ASSERT_TRUE(it == end); 30322add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 30422add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao it = m_pTestee->begin(); 30522add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao ++it; 30622add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao ++it; 30722add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao ASSERT_EQ(5, **it); 30822add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao ++it; 30922add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao ASSERT_TRUE(it == end); 31022add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao} 3115460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 312