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//===----------------------------------------------------------------------===// 937b74a387bb3993387029859c2d9d051c41c724eStephen Hines#ifndef MCLD_ADT_TREEBASE_H_ 1037b74a387bb3993387029859c2d9d051c41c724eStephen Hines#define MCLD_ADT_TREEBASE_H_ 1137b74a387bb3993387029859c2d9d051c41c724eStephen Hines 1237b74a387bb3993387029859c2d9d051c41c724eStephen Hines#include "mcld/ADT/TypeTraits.h" 135460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 146f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hines#include <cassert> 1537b74a387bb3993387029859c2d9d051c41c724eStephen Hines#include <cstddef> 166f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hines#include <iterator> 17f767be5432ccac097334be48698e48621d730190Shih-wei Liao 1822add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liaonamespace mcld { 195460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 2037b74a387bb3993387029859c2d9d051c41c724eStephen Hinesclass NodeBase { 2137b74a387bb3993387029859c2d9d051c41c724eStephen Hines public: 2237b74a387bb3993387029859c2d9d051c41c724eStephen Hines NodeBase* left; 2337b74a387bb3993387029859c2d9d051c41c724eStephen Hines NodeBase* right; 245460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 2537b74a387bb3993387029859c2d9d051c41c724eStephen Hines public: 2637b74a387bb3993387029859c2d9d051c41c724eStephen Hines NodeBase() : left(NULL), right(NULL) {} 275460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao}; 285460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 2937b74a387bb3993387029859c2d9d051c41c724eStephen Hinesclass TreeIteratorBase { 3037b74a387bb3993387029859c2d9d051c41c724eStephen Hines public: 3137b74a387bb3993387029859c2d9d051c41c724eStephen Hines enum Direct { Leftward, Rightward }; 325460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 3337b74a387bb3993387029859c2d9d051c41c724eStephen Hines typedef size_t size_type; 3437b74a387bb3993387029859c2d9d051c41c724eStephen Hines typedef ptrdiff_t difference_type; 355460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef std::bidirectional_iterator_tag iterator_category; 365460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 3737b74a387bb3993387029859c2d9d051c41c724eStephen Hines public: 385460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao NodeBase* m_pNode; 395460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 4037b74a387bb3993387029859c2d9d051c41c724eStephen Hines public: 4137b74a387bb3993387029859c2d9d051c41c724eStephen Hines TreeIteratorBase() : m_pNode(NULL) {} 425460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 4337b74a387bb3993387029859c2d9d051c41c724eStephen Hines explicit TreeIteratorBase(NodeBase* X) : m_pNode(X) {} 445460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 455460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao virtual ~TreeIteratorBase(){}; 465460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 4737b74a387bb3993387029859c2d9d051c41c724eStephen Hines template <size_t DIRECT> 4837b74a387bb3993387029859c2d9d051c41c724eStephen Hines void move() { 4937b74a387bb3993387029859c2d9d051c41c724eStephen Hines assert(0 && "not allowed"); 5037b74a387bb3993387029859c2d9d051c41c724eStephen Hines } 51f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines 5237b74a387bb3993387029859c2d9d051c41c724eStephen Hines template <size_t DIRECT> 5337b74a387bb3993387029859c2d9d051c41c724eStephen Hines void hook(NodeBase* pNode) { 5437b74a387bb3993387029859c2d9d051c41c724eStephen Hines assert(0 && "not allowed"); 5537b74a387bb3993387029859c2d9d051c41c724eStephen Hines } 565460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 5737b74a387bb3993387029859c2d9d051c41c724eStephen Hines bool isRoot() const { return (m_pNode->right == m_pNode); } 5867e37f1be98c926645219cfb47fab9e90d8c725cShih-wei Liao 5937b74a387bb3993387029859c2d9d051c41c724eStephen Hines bool hasRightChild() const { 6037b74a387bb3993387029859c2d9d051c41c724eStephen Hines return ((m_pNode->right) != (m_pNode->right->right)); 6137b74a387bb3993387029859c2d9d051c41c724eStephen Hines } 625460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 6337b74a387bb3993387029859c2d9d051c41c724eStephen Hines bool hasLeftChild() const { 6437b74a387bb3993387029859c2d9d051c41c724eStephen Hines return ((m_pNode->left) != (m_pNode->left->right)); 6537b74a387bb3993387029859c2d9d051c41c724eStephen Hines } 665460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 6737b74a387bb3993387029859c2d9d051c41c724eStephen Hines bool operator==(const TreeIteratorBase& y) const { 6837b74a387bb3993387029859c2d9d051c41c724eStephen Hines return this->m_pNode == y.m_pNode; 6937b74a387bb3993387029859c2d9d051c41c724eStephen Hines } 705460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 7137b74a387bb3993387029859c2d9d051c41c724eStephen Hines bool operator!=(const TreeIteratorBase& y) const { 7237b74a387bb3993387029859c2d9d051c41c724eStephen Hines return this->m_pNode != y.m_pNode; 7337b74a387bb3993387029859c2d9d051c41c724eStephen Hines } 745460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao}; 755460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 7637b74a387bb3993387029859c2d9d051c41c724eStephen Hinestemplate <> 7737b74a387bb3993387029859c2d9d051c41c724eStephen Hinesinline void TreeIteratorBase::move<TreeIteratorBase::Leftward>() { 78f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines this->m_pNode = this->m_pNode->left; 79f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines} 805460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 8137b74a387bb3993387029859c2d9d051c41c724eStephen Hinestemplate <> 8237b74a387bb3993387029859c2d9d051c41c724eStephen Hinesinline void TreeIteratorBase::move<TreeIteratorBase::Rightward>() { 83f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines this->m_pNode = this->m_pNode->right; 84f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines} 855460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 8637b74a387bb3993387029859c2d9d051c41c724eStephen Hinestemplate <> 8737b74a387bb3993387029859c2d9d051c41c724eStephen Hinesinline void TreeIteratorBase::hook<TreeIteratorBase::Leftward>( 8837b74a387bb3993387029859c2d9d051c41c724eStephen Hines NodeBase* pOther) { 89f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines this->m_pNode->left = pOther; 90f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines} 915460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 9237b74a387bb3993387029859c2d9d051c41c724eStephen Hinestemplate <> 9337b74a387bb3993387029859c2d9d051c41c724eStephen Hinesinline void TreeIteratorBase::hook<TreeIteratorBase::Rightward>( 9437b74a387bb3993387029859c2d9d051c41c724eStephen Hines NodeBase* pOther) { 95f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines this->m_pNode->right = pOther; 96f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines} 975460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 9837b74a387bb3993387029859c2d9d051c41c724eStephen Hinestemplate <typename DataType> 9937b74a387bb3993387029859c2d9d051c41c724eStephen Hinesclass Node : public NodeBase { 10037b74a387bb3993387029859c2d9d051c41c724eStephen Hines public: 10137b74a387bb3993387029859c2d9d051c41c724eStephen Hines typedef DataType value_type; 1025460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 10337b74a387bb3993387029859c2d9d051c41c724eStephen Hines public: 1045460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao value_type* data; 1055460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 10637b74a387bb3993387029859c2d9d051c41c724eStephen Hines public: 10737b74a387bb3993387029859c2d9d051c41c724eStephen Hines Node() : NodeBase(), data(NULL) {} 1085460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 10937b74a387bb3993387029859c2d9d051c41c724eStephen Hines explicit Node(const value_type& pValue) : NodeBase(), data(&pValue) {} 1105460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao}; 1115460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 11237b74a387bb3993387029859c2d9d051c41c724eStephen Hines} // namespace mcld 113affc150dc44fab1911775a49636d0ce85333b634Zonr Chang 11437b74a387bb3993387029859c2d9d051c41c724eStephen Hines#endif // MCLD_ADT_TREEBASE_H_ 115