15460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao//===- TreeBase.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//===----------------------------------------------------------------------===// 9f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines#ifndef MCLD_ADT_TREEBASE_H 10f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines#define MCLD_ADT_TREEBASE_H 11f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines#include <mcld/ADT/TypeTraits.h> 125460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 13f767be5432ccac097334be48698e48621d730190Shih-wei Liao#include <cstddef> 146f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hines#include <cassert> 156f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hines#include <iterator> 16f767be5432ccac097334be48698e48621d730190Shih-wei Liao 1722add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liaonamespace mcld { 185460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 195460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaoclass NodeBase 205460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao{ 215460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaopublic: 225460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao NodeBase *left; 235460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao NodeBase *right; 245460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 255460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaopublic: 265460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao NodeBase() 275460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao : left(0), right(0) 285460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { } 295460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao}; 305460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 3122add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liaoclass TreeIteratorBase 325460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao{ 335460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaopublic: 345460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao enum Direct { 355460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao Leftward, 365460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao Rightward 375460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao }; 385460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 395460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef size_t size_type; 405460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef ptrdiff_t difference_type; 415460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef std::bidirectional_iterator_tag iterator_category; 425460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 435460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaopublic: 445460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao NodeBase* m_pNode; 455460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 465460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaopublic: 475460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao TreeIteratorBase() 485460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao : m_pNode(0) 495460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { } 505460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 515460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao TreeIteratorBase(NodeBase *X) 525460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao : m_pNode(X) 535460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { } 545460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 555460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao virtual ~TreeIteratorBase(){}; 565460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 575460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao template<size_t DIRECT> 58f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines void move() { assert(0 && "not allowed"); } 59f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines 60f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines template<size_t DIRECT> 61f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines void hook(NodeBase* pNode) { assert(0 && "not allowed"); } 625460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 6367e37f1be98c926645219cfb47fab9e90d8c725cShih-wei Liao bool isRoot() const 6467e37f1be98c926645219cfb47fab9e90d8c725cShih-wei Liao { return (m_pNode->right == m_pNode); } 6567e37f1be98c926645219cfb47fab9e90d8c725cShih-wei Liao 665460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao bool hasRightChild() const 675460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { return ((m_pNode->right) != (m_pNode->right->right)); } 685460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 695460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao bool hasLeftChild() const 705460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { return ((m_pNode->left) != (m_pNode->left->right)); } 715460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 725460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao bool operator==(const TreeIteratorBase& y) const 735460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { return this->m_pNode == y.m_pNode; } 745460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 755460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao bool operator!=(const TreeIteratorBase& y) const 765460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { return this->m_pNode != y.m_pNode; } 775460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao}; 785460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 79f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hinestemplate<> inline 80f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hinesvoid TreeIteratorBase::move<TreeIteratorBase::Leftward>() 815460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao{ 82f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines this->m_pNode = this->m_pNode->left; 83f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines} 845460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 85f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hinestemplate<> inline 86f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hinesvoid TreeIteratorBase::move<TreeIteratorBase::Rightward>() 87f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines{ 88f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines this->m_pNode = this->m_pNode->right; 89f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines} 905460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 91f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hinestemplate<> inline 92f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hinesvoid TreeIteratorBase::hook<TreeIteratorBase::Leftward>(NodeBase* pOther) 93f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines{ 94f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines this->m_pNode->left = pOther; 95f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines} 965460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 97f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hinestemplate<> inline 98f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hinesvoid TreeIteratorBase::hook<TreeIteratorBase::Rightward>(NodeBase* pOther) 99f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines{ 100f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines this->m_pNode->right = pOther; 101f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines} 1025460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1035460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaotemplate<typename DataType> 1045460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaoclass Node : public NodeBase 1055460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao{ 1065460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaopublic: 1075460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef DataType value_type; 1085460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1095460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaopublic: 1105460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao value_type* data; 1115460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1125460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaopublic: 1135460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao Node() 1145460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao : NodeBase(), data(0) 1155460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { } 1165460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1175460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao Node(const value_type& pValue) 1185460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao : NodeBase(), data(&pValue) 1195460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { } 1205460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1215460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao}; 1225460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1235460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao} // namespace of mcld 1245460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1255460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao#endif 126affc150dc44fab1911775a49636d0ce85333b634Zonr Chang 127