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//===----------------------------------------------------------------------===// 95460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao#ifndef MCLD_TREE_BASE_H 105460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao#define MCLD_TREE_BASE_H 115460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao#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 315460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaonamespace proxy 325460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao{ 335460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao template<size_t DIRECT> 345460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao inline void move(NodeBase *&X) 355460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { assert(0 && "not allowed"); } 365460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 375460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao template<size_t DIRECT> 385460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao inline void hook(NodeBase *X, const NodeBase *Y) 395460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { assert(0 && "not allowed"); } 405460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 415460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao} // namespace of template proxy 425460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 4322add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liaoclass TreeIteratorBase 445460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao{ 455460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaopublic: 465460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao enum Direct { 475460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao Leftward, 485460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao Rightward 495460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao }; 505460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 515460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef size_t size_type; 525460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef ptrdiff_t difference_type; 535460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef std::bidirectional_iterator_tag iterator_category; 545460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 555460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaopublic: 565460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao NodeBase* m_pNode; 575460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 585460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaopublic: 595460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao TreeIteratorBase() 605460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao : m_pNode(0) 615460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { } 625460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 635460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao TreeIteratorBase(NodeBase *X) 645460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao : m_pNode(X) 655460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { } 665460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 675460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao virtual ~TreeIteratorBase(){}; 685460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 695460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao template<size_t DIRECT> 705460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao inline void move() { 715460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao proxy::move<DIRECT>(m_pNode); 725460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 735460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 7467e37f1be98c926645219cfb47fab9e90d8c725cShih-wei Liao bool isRoot() const 7567e37f1be98c926645219cfb47fab9e90d8c725cShih-wei Liao { return (m_pNode->right == m_pNode); } 7667e37f1be98c926645219cfb47fab9e90d8c725cShih-wei Liao 775460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao bool hasRightChild() const 785460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { return ((m_pNode->right) != (m_pNode->right->right)); } 795460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 805460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao bool hasLeftChild() const 815460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { return ((m_pNode->left) != (m_pNode->left->right)); } 825460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 835460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao bool operator==(const TreeIteratorBase& y) const 845460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { return this->m_pNode == y.m_pNode; } 855460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 865460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao bool operator!=(const TreeIteratorBase& y) const 875460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { return this->m_pNode != y.m_pNode; } 885460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao}; 895460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 905460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaonamespace proxy 915460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao{ 925460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao template<> 93f767be5432ccac097334be48698e48621d730190Shih-wei Liao inline void move<TreeIteratorBase::Leftward>(NodeBase *&X) 945460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { X = X->left; } 955460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 965460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao template<> 975460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao inline void move<TreeIteratorBase::Rightward>(NodeBase *&X) 985460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { X = X->right; } 995460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1005460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao template<> 1015460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao inline void hook<TreeIteratorBase::Leftward>(NodeBase *X, const NodeBase *Y) 1025460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { X->left = const_cast<NodeBase*>(Y); } 1035460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1045460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao template<> 1055460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao inline void hook<TreeIteratorBase::Rightward>(NodeBase* X, const NodeBase* Y) 1065460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { X->right = const_cast<NodeBase*>(Y); } 1075460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1085460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao} //namespace of template proxy 1095460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1105460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaotemplate<typename DataType> 1115460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaoclass Node : public NodeBase 1125460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao{ 1135460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaopublic: 1145460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef DataType value_type; 1155460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1165460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaopublic: 1175460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao value_type* data; 1185460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1195460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaopublic: 1205460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao Node() 1215460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao : NodeBase(), data(0) 1225460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { } 1235460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1245460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao Node(const value_type& pValue) 1255460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao : NodeBase(), data(&pValue) 1265460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { } 1275460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1285460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao}; 1295460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1305460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao} // namespace of mcld 1315460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1325460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao#endif 133affc150dc44fab1911775a49636d0ce85333b634Zonr Chang 134