xref: /frameworks/compile/mclinker/unittests/BinTreeTest.cpp

//===- BinTreeTest.cpp ----------------------------------------------------===//
//
//                     The MCLinker Project
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
#include "BinTreeTest.h"

#include <mcld/ADT/TypeTraits.h>
#include <mcld/InputTree.h>
#include <string>

using namespace mcld;
using namespace mcldtest;


// Constructor can do set-up work for all test here.
BinTreeTest::BinTreeTest()
{
	// create testee. modify it if need
	m_pTestee = new BinaryTree<int>();
}

// Destructor can do clean-up work that doesn't throw exceptions here.
BinTreeTest::~BinTreeTest()
{
	delete m_pTestee;
}

// SetUp() will be called immediately before each test.
void BinTreeTest::SetUp()
{
}

// TearDown() will be called immediately after each test.
void BinTreeTest::TearDown()
{
}

//==========================================================================//
// Testcases
//


/// General
TEST_F( BinTreeTest,Two_non_null_tree_merge)
{
  BinaryTree<int>::iterator pos = m_pTestee->root();
  m_pTestee->join<TreeIteratorBase::Rightward>(pos,0);
  --pos;
  m_pTestee->join<TreeIteratorBase::Rightward>(pos,1);
  m_pTestee->join<TreeIteratorBase::Leftward>(pos,1);
  --pos;
  m_pTestee->join<TreeIteratorBase::Rightward>(pos,2);
  m_pTestee->join<TreeIteratorBase::Leftward>(pos,2);

  BinaryTree<int> *mergeTree = new BinaryTree<int>;
  BinaryTree<int>::iterator pos2 = mergeTree->root();
  mergeTree->join<TreeIteratorBase::Rightward>(pos2,1);
  --pos2;
  mergeTree->join<TreeIteratorBase::Rightward>(pos2,1);
  mergeTree->join<TreeIteratorBase::Leftward>(pos2,1);

  m_pTestee->merge<TreeIteratorBase::Rightward>(pos,*mergeTree);
  delete mergeTree;
  EXPECT_TRUE(m_pTestee->size()==8);
}

/// ---- TEST - 2 ----
TEST_F( BinTreeTest, A_null_tree_merge_a_non_null_tree)
{
  BinaryTree<int>::iterator pos = m_pTestee->root();

  BinaryTree<int> *mergeTree = new BinaryTree<int>;
  mergeTree->join<TreeIteratorBase::Rightward>(pos,0);
  --pos;
  mergeTree->join<TreeIteratorBase::Rightward>(pos,1);
  mergeTree->join<TreeIteratorBase::Leftward>(pos,1);
  --pos;
  mergeTree->join<TreeIteratorBase::Rightward>(pos,2);
  mergeTree->join<TreeIteratorBase::Leftward>(pos,2);

  m_pTestee->merge<TreeIteratorBase::Rightward>(pos,*mergeTree);

  delete mergeTree;
  EXPECT_TRUE(m_pTestee->size()==5);
}

TEST_F( BinTreeTest, A_non_null_tree_merge_a_null_tree)
{
  BinaryTree<int>::iterator pos = m_pTestee->root();
  m_pTestee->join<TreeIteratorBase::Rightward>(pos,0);
  --pos;
  m_pTestee->join<TreeIteratorBase::Rightward>(pos,1);
  m_pTestee->join<TreeIteratorBase::Leftward>(pos,1);
  --pos;
  m_pTestee->join<TreeIteratorBase::Rightward>(pos,2);
  m_pTestee->join<TreeIteratorBase::Leftward>(pos,2);

  BinaryTree<int> *mergeTree = new BinaryTree<int>;
  BinaryTree<int>::iterator pos2 = mergeTree->root();
  mergeTree->merge<TreeIteratorBase::Rightward>(pos2,*m_pTestee);

  //delete m_pTestee;
  EXPECT_TRUE(mergeTree->size()==5);
  delete mergeTree;
}

TEST_F( BinTreeTest, Two_null_tree_merge)
{
  BinaryTree<int>::iterator pos = m_pTestee->root();

  BinaryTree<int> *mergeTree = new BinaryTree<int>;
  BinaryTree<int>::iterator pos2 = mergeTree->root();

  mergeTree->merge<TreeIteratorBase::Rightward>(pos2,*m_pTestee);

  //delete m_pTestee;
  EXPECT_TRUE(mergeTree->size()==0);
  delete mergeTree;
}

TEST_F( BinTreeTest, DFSIterator_BasicTraversal)
{
  int a = 111, b = 10, c = 9, d = 8, e = 7;
  BinaryTree<int>::iterator pos = m_pTestee->root();

  m_pTestee->join<InputTree::Inclusive>(pos,a);
  pos.move<InputTree::Inclusive>();
  m_pTestee->join<InputTree::Positional>(pos,b);
  m_pTestee->join<InputTree::Inclusive>(pos,c);
  pos.move<InputTree::Inclusive>();
  m_pTestee->join<InputTree::Positional>(pos,d);
  m_pTestee->join<InputTree::Inclusive>(pos,e);

  BinaryTree<int>::dfs_iterator dfs_it = m_pTestee->dfs_begin();
  BinaryTree<int>::dfs_iterator dfs_end = m_pTestee->dfs_end();

  ASSERT_EQ(111, **dfs_it);
  ++dfs_it;
  EXPECT_EQ(9, **dfs_it);
  ++dfs_it;
  EXPECT_EQ(7, **dfs_it);
  ++dfs_it;
  EXPECT_EQ(8, **dfs_it);
  ++dfs_it;
  EXPECT_EQ(10, **dfs_it);
  ++dfs_it;
  EXPECT_TRUE( dfs_it ==  dfs_end);
}

TEST_F( BinTreeTest, DFSIterator_RightMostTree)
{
  int a = 0, b = 1, c = 2, d = 3, e = 4;
  BinaryTree<int>::iterator pos = m_pTestee->root();
  m_pTestee->join<InputTree::Inclusive>(pos,a);
  pos.move<InputTree::Inclusive>();
  m_pTestee->join<InputTree::Positional>(pos,b);
  pos.move<InputTree::Positional>();
  m_pTestee->join<InputTree::Positional>(pos,c);
  pos.move<InputTree::Positional>();
  m_pTestee->join<InputTree::Positional>(pos,d);
  pos.move<InputTree::Positional>();
  m_pTestee->join<InputTree::Positional>(pos,e);

  BinaryTree<int>::dfs_iterator dfs_it = m_pTestee->dfs_begin();
  BinaryTree<int>::dfs_iterator dfs_end = m_pTestee->dfs_end();

  ASSERT_EQ(0, **dfs_it);
  ++dfs_it;
  ASSERT_EQ(1, **dfs_it);
  ++dfs_it;
  ASSERT_EQ(2, **dfs_it);
  ++dfs_it;
  ASSERT_EQ(3, **dfs_it);
  ++dfs_it;
  ASSERT_EQ(4, **dfs_it);
  ++dfs_it;
  ASSERT_TRUE( dfs_it ==  dfs_end);
}


TEST_F( BinTreeTest, DFSIterator_SingleNode)
{
  BinaryTree<int>::iterator pos = m_pTestee->root();
  m_pTestee->join<InputTree::Inclusive>(pos,0);
  BinaryTree<int>::dfs_iterator dfs_it = m_pTestee->dfs_begin();
  BinaryTree<int>::dfs_iterator dfs_end = m_pTestee->dfs_end();
  int counter = 0;
  while( dfs_it != dfs_end ) {
    ++counter;
    ++dfs_it;
  }
  ASSERT_EQ(1, counter);
}

TEST_F( BinTreeTest, BFSIterator_BasicTraversal)
{
  int a = 111, b = 10, c = 9, d = 8, e = 7;
  BinaryTree<int>::iterator pos = m_pTestee->root();

  m_pTestee->join<InputTree::Inclusive>(pos,a);
  pos.move<InputTree::Inclusive>();
  m_pTestee->join<InputTree::Positional>(pos,b);
  m_pTestee->join<InputTree::Inclusive>(pos,c);
  pos.move<InputTree::Inclusive>();
  m_pTestee->join<InputTree::Positional>(pos,d);
  m_pTestee->join<InputTree::Inclusive>(pos,e);

  BinaryTree<int>::bfs_iterator bfs_it = m_pTestee->bfs_begin();
  BinaryTree<int>::bfs_iterator bfs_end = m_pTestee->bfs_end();

  ASSERT_EQ(111, **bfs_it);
  ++bfs_it;
  ASSERT_EQ(10, **bfs_it);
  ++bfs_it;
  ASSERT_EQ(9, **bfs_it);
  ++bfs_it;
  ASSERT_EQ(8, **bfs_it);
  ++bfs_it;
  ASSERT_EQ(7, **bfs_it);
  ++bfs_it;
  ASSERT_TRUE(bfs_it ==  bfs_end);
  bfs_it = m_pTestee->bfs_begin();
  bfs_end = m_pTestee->bfs_end();
}

TEST_F( BinTreeTest, BFSIterator_RightMostTree)
{
  int a = 0, b = 1, c = 2, d = 3, e = 4;
  BinaryTree<int>::iterator pos = m_pTestee->root();
  m_pTestee->join<InputTree::Inclusive>(pos,a);
  pos.move<InputTree::Inclusive>();
  m_pTestee->join<InputTree::Positional>(pos,b);
  pos.move<InputTree::Positional>();
  m_pTestee->join<InputTree::Positional>(pos,c);
  pos.move<InputTree::Positional>();
  m_pTestee->join<InputTree::Positional>(pos,d);
  pos.move<InputTree::Positional>();
  m_pTestee->join<InputTree::Positional>(pos,e);

  BinaryTree<int>::bfs_iterator bfs_it = m_pTestee->bfs_begin();
  BinaryTree<int>::bfs_iterator bfs_end = m_pTestee->bfs_end();

  ASSERT_EQ(0, **bfs_it);
  ++bfs_it;
  ASSERT_EQ(1, **bfs_it);
  ++bfs_it;
  ASSERT_EQ(2, **bfs_it);
  ++bfs_it;
  ASSERT_EQ(3, **bfs_it);
  ++bfs_it;
  ASSERT_EQ(4, **bfs_it);
  ++bfs_it;
  ASSERT_TRUE( bfs_it ==  bfs_end);
}


TEST_F( BinTreeTest, BFSIterator_SingleNode)
{
  BinaryTree<int>::iterator pos = m_pTestee->root();
  m_pTestee->join<InputTree::Inclusive>(pos,0);
  BinaryTree<int>::bfs_iterator bfs_it = m_pTestee->bfs_begin();
  BinaryTree<int>::bfs_iterator bfs_end = m_pTestee->bfs_end();
  int counter = 0;
  while( bfs_it != bfs_end ) {
    ++counter;
    ++bfs_it;
  }
  ASSERT_EQ(1, counter);
}

TEST_F( BinTreeTest, TreeIterator)
{
  int a = 0, b = 1, c = 2, d = 3, e = 4, f = 5;
  BinaryTree<int>::iterator pos = m_pTestee->root();
  m_pTestee->join<InputTree::Inclusive>(pos,a);
  pos.move<InputTree::Inclusive>();
  m_pTestee->join<InputTree::Positional>(pos,b);
  pos.move<InputTree::Positional>();
  m_pTestee->join<InputTree::Inclusive>(pos,c);
  m_pTestee->join<InputTree::Positional>(pos,f);
  pos.move<InputTree::Inclusive>();
  m_pTestee->join<InputTree::Positional>(pos,d);
  pos.move<InputTree::Positional>();
  m_pTestee->join<InputTree::Positional>(pos,e);

  BinaryTree<int>::iterator it = m_pTestee->begin();
  BinaryTree<int>::iterator end = m_pTestee->end();

  ASSERT_EQ(0, **it);
  ++it;
  ASSERT_EQ(1, **it);
  --it;
  ASSERT_EQ(2, **it);
  ++it;
  ASSERT_EQ(3, **it);
  ++it;
  ASSERT_EQ(4, **it);
  ++it;
  ASSERT_TRUE(it == end);

  it = m_pTestee->begin();
  ++it;
  ++it;
  ASSERT_EQ(5, **it);
  ++it;
  ASSERT_TRUE(it == end);
}