TreeBase.h revision f767be5432ccac097334be48698e48621d730190
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> 14f767be5432ccac097334be48698e48621d730190Shih-wei Liao 155460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaonamespace mcld 165460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao{ 175460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 185460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaoclass NodeBase 195460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao{ 205460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaopublic: 215460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao NodeBase *left; 225460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao NodeBase *right; 235460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 245460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaopublic: 255460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao NodeBase() 265460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao : left(0), right(0) 275460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { } 285460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao}; 295460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 305460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaonamespace proxy 315460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao{ 325460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao template<size_t DIRECT> 335460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao inline void move(NodeBase *&X) 345460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { assert(0 && "not allowed"); } 355460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 365460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao template<size_t DIRECT> 375460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao inline void hook(NodeBase *X, const NodeBase *Y) 385460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { assert(0 && "not allowed"); } 395460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 405460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao} // namespace of template proxy 415460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 425460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaostruct TreeIteratorBase 435460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao{ 445460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaopublic: 455460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao enum Direct { 465460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao Leftward, 475460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao Rightward 485460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao }; 495460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 505460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef size_t size_type; 515460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef ptrdiff_t difference_type; 525460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef std::bidirectional_iterator_tag iterator_category; 535460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 545460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaopublic: 555460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao NodeBase* m_pNode; 565460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 575460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaopublic: 585460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao TreeIteratorBase() 595460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao : m_pNode(0) 605460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { } 615460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 625460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao TreeIteratorBase(NodeBase *X) 635460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao : m_pNode(X) 645460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { } 655460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 665460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao virtual ~TreeIteratorBase(){}; 675460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 685460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao template<size_t DIRECT> 695460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao inline void move() { 705460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao proxy::move<DIRECT>(m_pNode); 715460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 725460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 735460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao bool hasRightChild() const 745460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { return ((m_pNode->right) != (m_pNode->right->right)); } 755460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 765460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao bool hasLeftChild() const 775460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { return ((m_pNode->left) != (m_pNode->left->right)); } 785460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 795460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao bool operator==(const TreeIteratorBase& y) const 805460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { return this->m_pNode == y.m_pNode; } 815460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 825460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao bool operator!=(const TreeIteratorBase& y) const 835460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { return this->m_pNode != y.m_pNode; } 845460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao}; 855460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 865460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaonamespace proxy 875460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao{ 885460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao template<> 89f767be5432ccac097334be48698e48621d730190Shih-wei Liao inline void move<TreeIteratorBase::Leftward>(NodeBase *&X) 905460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { X = X->left; } 915460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 925460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao template<> 935460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao inline void move<TreeIteratorBase::Rightward>(NodeBase *&X) 945460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { X = X->right; } 955460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 965460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao template<> 975460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao inline void hook<TreeIteratorBase::Leftward>(NodeBase *X, const NodeBase *Y) 985460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { X->left = const_cast<NodeBase*>(Y); } 995460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1005460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao template<> 1015460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao inline void hook<TreeIteratorBase::Rightward>(NodeBase* X, const NodeBase* Y) 1025460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { X->right = const_cast<NodeBase*>(Y); } 1035460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1045460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao} //namespace of template proxy 1055460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1065460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaotemplate<typename DataType> 1075460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaoclass Node : public NodeBase 1085460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao{ 1095460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaopublic: 1105460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef DataType value_type; 1115460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1125460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaopublic: 1135460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao value_type* data; 1145460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1155460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaopublic: 1165460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao Node() 1175460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao : NodeBase(), data(0) 1185460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { } 1195460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1205460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao Node(const value_type& pValue) 1215460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao : NodeBase(), data(&pValue) 1225460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { } 1235460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1245460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao}; 1255460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1265460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao} // namespace of mcld 1275460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1285460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao#endif 129