BinTree.h revision 5460a1f25d9ddecb5c70667267d66d51af177a99
15460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao//===- BinTree.h ----------------------------------------------------------===// 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#ifndef MCLD_BINARY_TREE_H 105460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao#define MCLD_BINARY_TREE_H 115460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao#ifdef ENABLE_UNITTEST 125460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao#include <gtest.h> 135460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao#endif 145460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 155460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao#include "mcld/ADT/Uncopyable.h" 165460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao#include "mcld/ADT/TreeAllocator.h" 175460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 185460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao#include <iterator> 195460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao#include <memory> 205460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao#include <queue> 215460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao#include <stack> 225460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 235460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaonamespace mcld 245460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao{ 255460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 265460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaotemplate<class DataType> 275460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaoclass BinaryTree; 285460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 295460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaoclass DFSIterator : public TreeIteratorBase 305460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao{ 315460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaopublic: 325460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao DFSIterator() 335460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao : TreeIteratorBase() 345460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { } 355460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 365460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao DFSIterator(NodeBase *X) 375460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao : TreeIteratorBase(X) { 385460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao if (hasRightChild()) 395460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao m_Stack.push(m_pNode->right); 405460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao if (hasLeftChild()) 415460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao m_Stack.push(m_pNode->left); 425460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 435460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 445460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao virtual ~DFSIterator() 455460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { } 465460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 475460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao void advance() { 485460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao if (m_Stack.empty()) { // reach the end 495460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao m_pNode = m_pNode->right; // should be root 505460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao return; 515460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 525460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao m_pNode = m_Stack.top(); 535460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao m_Stack.pop(); 545460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao if (hasRightChild()) 555460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao m_Stack.push(m_pNode->right); 565460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao if (hasLeftChild()) 575460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao m_Stack.push(m_pNode->left); 585460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 595460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 605460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaoprivate: 615460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao std::stack<NodeBase *> m_Stack; 625460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao}; 635460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 645460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaoclass BFSIterator : public TreeIteratorBase 655460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao{ 665460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaopublic: 675460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao BFSIterator() 685460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao : TreeIteratorBase() 695460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { } 705460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 715460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao BFSIterator(NodeBase *X) 725460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao : TreeIteratorBase(X) { 735460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao if (hasRightChild()) 745460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao m_Queue.push(m_pNode->right); 755460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao if (hasLeftChild()) 765460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao m_Queue.push(m_pNode->left); 775460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 785460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 795460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao virtual ~BFSIterator() 805460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { } 815460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 825460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao void advance() { 835460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao if (m_Queue.empty()) { // reach the end 845460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao m_pNode = m_pNode->right; // should be root 855460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao return; 865460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 875460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao m_pNode = m_Queue.front(); 885460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao m_Queue.pop(); 895460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao if (hasRightChild()) 905460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao m_Queue.push(m_pNode->right); 915460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao if (hasLeftChild()) 925460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao m_Queue.push(m_pNode->left); 935460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 945460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 955460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaoprivate: 965460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao std::queue<NodeBase *> m_Queue; 975460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao}; 985460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 995460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaotemplate<class DataType, class Traits, class IteratorType> 1005460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaoclass PolicyIteratorBase : public IteratorType 1015460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao{ 1025460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaopublic: 1035460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef DataType value_type; 1045460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef Traits traits; 1055460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef typename traits::pointer pointer; 1065460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef typename traits::reference reference; 1075460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1085460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef PolicyIteratorBase<value_type, Traits, IteratorType> Self; 1095460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef Node<value_type> node_type; 1105460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef typename traits::nonconst_traits nonconst_traits; 1115460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef PolicyIteratorBase<value_type, nonconst_traits, IteratorType> iterator; 1125460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef typename traits::const_traits const_traits; 1135460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef PolicyIteratorBase<value_type, const_traits, IteratorType> const_iterator; 1145460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef std::forward_iterator_tag iterator_category; 1155460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef size_t size_type; 1165460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef ptrdiff_t difference_type; 1175460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1185460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaopublic: 1195460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao PolicyIteratorBase() 1205460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao : IteratorType() {} 1215460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1225460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao PolicyIteratorBase(const iterator &X) 1235460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao : IteratorType(X.m_pNode) {} 1245460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1255460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao explicit PolicyIteratorBase(NodeBase* X) 1265460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao : IteratorType(X) {} 1275460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1285460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao virtual ~PolicyIteratorBase() {} 1295460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1305460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao // ----- operators ----- // 1315460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao pointer operator*() const 1325460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { return static_cast<node_type*>(IteratorType::m_pNode)->data; } 1335460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1345460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao reference operator->() const 1355460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { return *static_cast<node_type*>(IteratorType::m_pNode)->data; } 1365460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1375460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao bool isRoot() const 1385460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { return (IteratorType::m_pNode->right == IteratorType::m_pNode); } 1395460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1405460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao bool hasData() const 1415460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { return (!isRoot() && (0 != static_cast<node_type*>(IteratorType::m_pNode)->data)); } 1425460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1435460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao}; 1445460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1455460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaotemplate<class DataType, class Traits, class IteratorType> 1465460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaoclass PolicyIterator : public PolicyIteratorBase<DataType, Traits, IteratorType> 1475460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao{ 1485460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaopublic: 1495460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef PolicyIterator<DataType, Traits, IteratorType> Self; 1505460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef PolicyIteratorBase<DataType, Traits, IteratorType> Base; 1515460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef PolicyIterator<DataType, typename Traits::nonconst_traits, IteratorType> iterator; 1525460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef PolicyIterator<DataType, typename Traits::const_traits, IteratorType> const_iterator; 1535460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1545460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaopublic: 1555460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao PolicyIterator() 1565460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao : Base() {} 1575460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1585460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao PolicyIterator(const iterator &X) 1595460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao : Base(X.m_pNode) {} 1605460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1615460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao explicit PolicyIterator(NodeBase* X) 1625460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao : Base(X) {} 1635460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1645460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao virtual ~PolicyIterator() {} 1655460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1665460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao Self& operator++() { 1675460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao IteratorType::advance(); 1685460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao return *this; 1695460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 1705460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1715460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao Self operator++(int) { 1725460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao Self tmp = *this; 1735460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao IteratorType::advance(); 1745460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao return tmp; 1755460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 1765460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao}; 1775460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1785460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaotemplate<class DataType> 1795460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaoclass BinaryTree; 1805460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1815460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao/** \class TreeIterator 1825460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * \brief TreeIterator provides full functions of binary tree's iterator. 1835460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * 1845460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * TreeIterator is designed to compatible with STL iterators. 1855460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * TreeIterator is bi-directional. Incremental direction means to move 1865460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * rightward, and decremental direction is leftward. 1875460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * 1885460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * @see TreeIteratorBase 1895460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao */ 1905460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaotemplate<class DataType, class Traits> 1915460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaostruct TreeIterator : public TreeIteratorBase 1925460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao{ 1935460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaopublic: 1945460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef DataType value_type; 1955460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef Traits traits; 1965460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef typename traits::pointer pointer; 1975460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef typename traits::reference reference; 1985460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1995460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef TreeIterator<value_type, Traits> Self; 2005460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef Node<value_type> node_type; 2015460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 2025460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef typename traits::nonconst_traits nonconst_traits; 2035460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef TreeIterator<value_type, nonconst_traits> iterator; 2045460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef typename traits::const_traits const_traits; 2055460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef TreeIterator<value_type, const_traits> const_iterator; 2065460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef std::bidirectional_iterator_tag iterator_category; 2075460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef size_t size_type; 2085460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef ptrdiff_t difference_type; 2095460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 2105460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaopublic: 2115460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao TreeIterator() 2125460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao : TreeIteratorBase() {} 2135460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 2145460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao TreeIterator(const iterator &X) 2155460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao : TreeIteratorBase(X.m_pNode) {} 2165460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 2175460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao ~TreeIterator() {} 2185460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 2195460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao // ----- operators ----- // 2205460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao pointer operator*() const 2215460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { return static_cast<node_type*>(m_pNode)->data; } 2225460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 2235460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao reference operator->() const 2245460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { return *static_cast<node_type*>(m_pNode)->data; } 2255460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 2265460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao bool isRoot() const 2275460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { return (m_pNode->right == m_pNode); } 2285460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 2295460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao bool hasData() const 2305460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { return (!isRoot() && (0 != static_cast<node_type*>(m_pNode)->data)); } 2315460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 2325460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao Self& operator++() { 2335460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao this->move<TreeIteratorBase::Rightward>(); 2345460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao return *this; 2355460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 2365460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 2375460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao Self operator++(int) { 2385460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao Self tmp = *this; 2395460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao this->move<TreeIteratorBase::Rightward>(); 2405460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao return tmp; 2415460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 2425460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 2435460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao Self& operator--() { 2445460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao this->move<TreeIteratorBase::Leftward>(); 2455460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao return *this; 2465460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 2475460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 2485460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao Self operator--(int) { 2495460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao Self tmp = *this; 2505460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao this->move<TreeIteratorBase::Leftward>(); 2515460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao return tmp; 2525460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 2535460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 2545460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao explicit TreeIterator(NodeBase* X) 2555460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao : TreeIteratorBase(X) {} 2565460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao}; 2575460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 2585460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao/** \class BinaryTreeBase 2595460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * \brief BinaryTreeBase gives root node and memory management. 2605460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * 2615460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * The memory management of nodes in is hidden by BinaryTreeBase. 2625460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * BinaryTreeBase also provides the basic functions for merging a tree and 2635460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * inserton of a node. 2645460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * 2655460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * @see BinaryTree 2665460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao */ 2675460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaotemplate<class DataType> 2685460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaoclass BinaryTreeBase : private Uncopyable 2695460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao{ 2705460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaopublic: 2715460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef Node<DataType> NodeType; 2725460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaoprotected: 2735460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao /// TreeImpl - TreeImpl records the root node and the number of nodes 2745460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao // 2755460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao // +---> Root(end) <---+ 2765460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao // | |left | 2775460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao // | begin | 2785460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao // | / \ | 2795460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao // | Left Right | 2805460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao // +---/ \-----+ 2815460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao // 2825460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao class TreeImpl : public NodeFactory<DataType> 2835460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { 2845460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef typename NodeFactory<DataType>::iterator iterator; 2855460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef typename NodeFactory<DataType>::const_iterator const_iterator; 2865460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 2875460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao public: 2885460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao NodeBase node; 2895460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 2905460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao public: 2915460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao TreeImpl() 2925460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao : NodeFactory<DataType>() { 2935460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao node.left = node.right = &node; 2945460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 2955460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 2965460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao ~TreeImpl() 2975460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { } 2985460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 2995460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao /// summon - change the final edges of pClient to our root 3005460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao void summon(TreeImpl& pClient) { 3015460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao if (this == &pClient) 3025460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao return; 3035460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 3045460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao iterator data; 3055460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao iterator dEnd = pClient.end(); 3065460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao for (data = pClient.begin(); data!=dEnd; ++data ) { 3075460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao if ((*data).left == &pClient.node) 3085460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao (*data).left = &node; 3095460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao if ((*data).right == &pClient.node) 3105460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao (*data).right = &node; 3115460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 3125460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 3135460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao }; // TreeImpl 3145460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 3155460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaoprotected: 3165460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao /// m_Root is a special object who responses: 3175460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao // - the pointer of root 3185460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao // - the simple factory of nodes. 3195460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao TreeImpl m_Root; 3205460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 3215460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaoprotected: 3225460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao NodeType *createNode() { 3235460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao NodeType *result = m_Root.produce(); 3245460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao result->left = result->right = &m_Root.node; 3255460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao return result; 3265460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 3275460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 3285460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao void destroyNode(NodeType *pNode) { 3295460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao pNode->left = pNode->right = 0; 3305460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao pNode->data = 0; 3315460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao m_Root.deallocate(pNode); 3325460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 3335460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 3345460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaopublic: 3355460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao BinaryTreeBase() 3365460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao : m_Root() 3375460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { } 3385460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 3395460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao virtual ~BinaryTreeBase() 3405460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { } 3415460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 3425460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao size_t size() const { 3435460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao return m_Root.size(); 3445460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 3455460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 3465460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao bool empty() const { 3475460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao return m_Root.empty(); 3485460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 3495460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 3505460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaoprotected: 3515460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao void clear() { 3525460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao m_Root.clear(); 3535460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 3545460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao}; 3555460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 3565460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao/** \class BinaryTree 3575460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * \brief An abstract data type of binary tree. 3585460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * 3595460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * @see mcld::InputTree 3605460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao */ 3615460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaotemplate<class DataType> 3625460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaoclass BinaryTree : public BinaryTreeBase<DataType> 3635460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao{ 3645460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaopublic: 3655460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef size_t size_type; 3665460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef ptrdiff_t difference_type; 3675460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef DataType value_type; 3685460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef value_type* pointer; 3695460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef value_type& reference; 3705460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef const value_type* const_pointer; 3715460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef const value_type& const_reference; 3725460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 3735460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef BinaryTree<DataType> Self; 3745460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef TreeIterator<value_type, NonConstTraits<value_type> > iterator; 3755460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef TreeIterator<value_type, ConstTraits<value_type> > const_iterator; 3765460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 3775460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef PolicyIterator<value_type, NonConstTraits<value_type>, DFSIterator> dfs_iterator; 3785460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef PolicyIterator<value_type, ConstTraits<value_type>, DFSIterator> const_dfs_iterator; 3795460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef PolicyIterator<value_type, NonConstTraits<value_type>, BFSIterator> bfs_iterator; 3805460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef PolicyIterator<value_type, ConstTraits<value_type>, BFSIterator> const_bfs_iterator; 3815460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 3825460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaoprotected: 3835460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef Node<value_type> node_type; 3845460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 3855460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaopublic: 3865460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao // ----- constructors and destructor ----- // 3875460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao BinaryTree() 3885460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao : BinaryTreeBase<DataType>() 3895460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { } 3905460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 3915460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao ~BinaryTree() { 3925460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 3935460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 3945460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao // ----- iterators ----- // 3955460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao bfs_iterator bfs_begin() 3965460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { return bfs_iterator(BinaryTreeBase<DataType>::m_Root.node.left); } 3975460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 3985460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao bfs_iterator bfs_end() 3995460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { return bfs_iterator(BinaryTreeBase<DataType>::m_Root.node.right); } 4005460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 4015460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao const_bfs_iterator bfs_begin() const 4025460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { return const_bfs_iterator(BinaryTreeBase<DataType>::m_Root.node.left); } 4035460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 4045460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao const_bfs_iterator bfs_end() const 4055460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { return const_bfs_iterator(BinaryTreeBase<DataType>::m_Root.node.right); } 4065460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 4075460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao dfs_iterator dfs_begin() 4085460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { return dfs_iterator(BinaryTreeBase<DataType>::m_Root.node.left); } 4095460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 4105460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao dfs_iterator dfs_end() 4115460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { return dfs_iterator(BinaryTreeBase<DataType>::m_Root.node.right); } 4125460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 4135460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao const_dfs_iterator dfs_begin() const 4145460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { return const_dfs_iterator(BinaryTreeBase<DataType>::m_Root.node.left); } 4155460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 4165460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao const_dfs_iterator dfs_end() const 4175460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { return const_dfs_iterator(BinaryTreeBase<DataType>::m_Root.node.right); } 4185460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 4195460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao iterator root() 4205460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { return iterator(&(BinaryTreeBase<DataType>::m_Root.node)); } 4215460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 4225460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao const_iterator root() const 4235460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { return const_iterator(&(BinaryTreeBase<DataType>::m_Root.node)); } 4245460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 4255460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao iterator begin() 4265460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { return iterator(BinaryTreeBase<DataType>::m_Root.node.left); } 4275460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 4285460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao iterator end() 4295460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { return iterator(BinaryTreeBase<DataType>::m_Root.node.right); } 4305460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 4315460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao const_iterator begin() const 4325460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { return const_iterator(BinaryTreeBase<DataType>::m_Root.node.left); } 4335460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 4345460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao const_iterator end() const 4355460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { return const_iterator(BinaryTreeBase<DataType>::m_Root.node.right); } 4365460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 4375460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao // ----- modifiers ----- // 4385460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao /// join - create a leaf node and merge it in the tree. 4395460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao // This version of join determines the direction on compilation time. 4405460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao // @param DIRECT the direction of the connecting edge of the parent node. 4415460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao // @param position the parent node 4425460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao // @param value the value being pushed. 4435460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao template<size_t DIRECT, class Pos> 4445460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao BinaryTree& join(Pos position, const DataType& value) { 4455460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao node_type *node = BinaryTreeBase<DataType>::createNode(); 4465460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao node->data = const_cast<DataType*>(&value); 4475460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao if (position.isRoot()) 4485460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao proxy::hook<TreeIteratorBase::Leftward>(position.m_pNode, 4495460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao const_cast<const node_type*>(node)); 4505460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao else 4515460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao proxy::hook<DIRECT>(position.m_pNode, 4525460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao const_cast<const node_type*>(node)); 4535460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao return *this; 4545460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 4555460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 4565460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao /// merge - merge the tree 4575460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao // @param DIRECT the direction of the connecting edge of the parent node. 4585460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao // @param position the parent node 4595460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao // @param the tree being joined. 4605460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao // @return the joined tree 4615460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao template<size_t DIRECT, class Pos> 4625460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao BinaryTree& merge(Pos position, BinaryTree& pTree) { 4635460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao if (this == &pTree) 4645460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao return *this; 4655460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 4665460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao if (!pTree.empty()) { 4675460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao proxy::hook<DIRECT>(position.m_pNode, 4685460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao const_cast<const NodeBase*>(pTree.m_Root.node.left)); 4695460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao BinaryTreeBase<DataType>::m_Root.summon( 4705460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao pTree.BinaryTreeBase<DataType>::m_Root); 4715460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao BinaryTreeBase<DataType>::m_Root.delegate(pTree.m_Root); 4725460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao pTree.m_Root.node.left = pTree.m_Root.node.right = &pTree.m_Root.node; 4735460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 4745460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao return *this; 4755460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 4765460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao}; 4775460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 4785460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao} // namespace of mcld 4795460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 4805460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao#endif 4815460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 482