1affc150dc44fab1911775a49636d0ce85333b634Zonr Chang//===- InputTree.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//===----------------------------------------------------------------------===// 922add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao#ifndef MCLD_MC_INPUT_TREE_H 1022add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao#define MCLD_MC_INPUT_TREE_H 115460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao#ifdef ENABLE_UNITTEST 125460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao#include <gtest.h> 135460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao#endif 145460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1522add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao#include <mcld/ADT/BinTree.h> 1622add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao#include <mcld/ADT/TypeTraits.h> 1722add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao#include <mcld/MC/MCLDInput.h> 1822add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao#include <mcld/Support/Path.h> 195460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 205460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao#include <string> 215460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 225460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 2322add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liaonamespace mcld { 245460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 255460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao/** \class template<typename Traits, typename Iterator> PolicyIterator<mcld::Input> 265460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * \brief PolicyIterator<mcld::Input> is a partially specific PolicyIterator 275460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao */ 285460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaotemplate<typename Traits, typename IteratorType> 295460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaoclass PolicyIterator<mcld::Input, Traits, IteratorType> : public PolicyIteratorBase<Input, Traits, IteratorType> 305460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao{ 315460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaopublic: 325460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef PolicyIterator<Input, Traits, IteratorType> Self; 335460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef PolicyIteratorBase<Input, Traits, IteratorType> Base; 345460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef PolicyIterator<Input, typename Traits::nonconst_traits, IteratorType> iterator; 355460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef PolicyIterator<Input, typename Traits::const_traits, IteratorType> const_iterator; 365460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 375460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaopublic: 385460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao PolicyIterator() 395460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao : Base() {} 405460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 415460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao PolicyIterator(const iterator &X) 425460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao : Base(X.m_pNode) {} 435460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 445460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao explicit PolicyIterator(NodeBase* X) 455460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao : Base(X) {} 465460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 475460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao virtual ~PolicyIterator() {} 485460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 495460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao bool isGroup() const 5022add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao { return !Base::hasData() && !Base::isRoot(); } 515460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 525460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao Self& operator++() { 535460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao IteratorType::advance(); 5422add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao // skip the Group node 5522add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao while (isGroup()) 565460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao IteratorType::advance(); 575460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao return *this; 585460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 595460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 605460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao Self operator++(int) { 615460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao Self tmp(*this); 625460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao IteratorType::advance(); 6322add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao // skip the Group node 6422add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao while (isGroup()) 655460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao IteratorType::advance(); 665460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao return tmp; 675460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 685460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao}; 695460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 70f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hinestemplate<> 71f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hinesclass BinaryTree<Input> : public BinaryTreeBase<Input> 72f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines{ 73f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hinespublic: 74f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines typedef size_t size_type; 75f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines typedef ptrdiff_t difference_type; 76f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines typedef Input value_type; 77f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines typedef value_type* pointer; 78f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines typedef value_type& reference; 79f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines typedef const value_type* const_pointer; 80f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines typedef const value_type& const_reference; 81f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines 82f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines typedef BinaryTree<Input> Self; 83f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines typedef TreeIterator<value_type, NonConstTraits<value_type> > iterator; 84f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines typedef TreeIterator<value_type, ConstTraits<value_type> > const_iterator; 85f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines 86f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines typedef PolicyIterator<value_type, NonConstTraits<value_type>, DFSIterator> dfs_iterator; 87f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines typedef PolicyIterator<value_type, ConstTraits<value_type>, DFSIterator> const_dfs_iterator; 88f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines typedef PolicyIterator<value_type, NonConstTraits<value_type>, BFSIterator> bfs_iterator; 89f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines typedef PolicyIterator<value_type, ConstTraits<value_type>, BFSIterator> const_bfs_iterator; 90f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines 91f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hinesprotected: 92f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines typedef Node<value_type> node_type; 93f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines 94f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hinespublic: 95f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines // ----- constructors and destructor ----- // 96f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines BinaryTree() 97f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines : BinaryTreeBase<Input>() 98f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines { } 99f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines 100f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines ~BinaryTree() { 101f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines } 102f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines 103f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines // ----- iterators ----- // 104f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines bfs_iterator bfs_begin() 105f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines { 106f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines bfs_iterator it = bfs_iterator(BinaryTreeBase<Input>::m_Root.node.left); 107f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines if (it.isGroup()) 108f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines ++it; 109f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines return it; 110f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines } 111f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines 112f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines bfs_iterator bfs_end() 113f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines { return bfs_iterator(BinaryTreeBase<Input>::m_Root.node.right); } 114f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines 115f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines const_bfs_iterator bfs_begin() const 116f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines { 117f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines const_bfs_iterator it = 118f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines const_bfs_iterator(BinaryTreeBase<Input>::m_Root.node.left); 119f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines if (it.isGroup()) 120f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines ++it; 121f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines return it; 122f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines } 123f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines 124f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines const_bfs_iterator bfs_end() const 125f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines { return const_bfs_iterator(BinaryTreeBase<Input>::m_Root.node.right); } 126f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines 127f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines dfs_iterator dfs_begin() 128f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines { 129f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines dfs_iterator it = dfs_iterator(BinaryTreeBase<Input>::m_Root.node.left); 130f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines if (it.isGroup()) 131f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines ++it; 132f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines return it; 133f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines } 134f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines 135f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines dfs_iterator dfs_end() 136f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines { return dfs_iterator(BinaryTreeBase<Input>::m_Root.node.right); } 137f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines 138f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines const_dfs_iterator dfs_begin() const 139f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines { 140f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines const_dfs_iterator it = 141f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines const_dfs_iterator(BinaryTreeBase<Input>::m_Root.node.left); 142f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines if (it.isGroup()) 143f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines ++it; 144f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines return it; 145f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines } 146f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines 147f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines const_dfs_iterator dfs_end() const 148f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines { return const_dfs_iterator(BinaryTreeBase<Input>::m_Root.node.right); } 149f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines 150f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines iterator root() 151f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines { return iterator(&(BinaryTreeBase<Input>::m_Root.node)); } 152f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines 153f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines const_iterator root() const 154f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines { 155f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines // FIXME: provide the iterater constructors for constant NodeBase instead of 156f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines // using const_cast 157f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines return const_iterator( 158f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines const_cast<NodeBase*>(&BinaryTreeBase<Input>::m_Root.node)); 159f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines } 160f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines 161f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines iterator begin() 162f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines { 163f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines iterator it = iterator(BinaryTreeBase<Input>::m_Root.node.left); 164f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines return it; 165f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines } 166f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines 167f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines iterator end() 168f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines { return iterator(BinaryTreeBase<Input>::m_Root.node.right); } 169f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines 170f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines const_iterator begin() const 171f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines { 172f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines const_iterator it = const_iterator(BinaryTreeBase<Input>::m_Root.node.left); 173f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines return it; 174f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines } 175f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines 176f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines const_iterator end() const 177f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines { return const_iterator(BinaryTreeBase<Input>::m_Root.node.right); } 178f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines 179f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines // ----- modifiers ----- // 180f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines /// join - create a leaf node and merge it in the tree. 181f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines // This version of join determines the direction on compilation time. 182f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines // @param DIRECT the direction of the connecting edge of the parent node. 183f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines // @param position the parent node 184f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines // @param value the value being pushed. 185f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines template<size_t DIRECT, class Pos> 186f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines BinaryTree& join(Pos position, const Input& value) { 187f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines node_type *node = BinaryTreeBase<Input>::createNode(); 188f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines node->data = const_cast<Input*>(&value); 189f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines if (position.isRoot()) 190f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines proxy::hook<TreeIteratorBase::Leftward>(position.m_pNode, 191f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines const_cast<const node_type*>(node)); 192f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines else 193f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines proxy::hook<DIRECT>(position.m_pNode, 194f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines const_cast<const node_type*>(node)); 195f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines return *this; 196f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines } 197f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines 198f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines /// merge - merge the tree 199f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines // @param DIRECT the direction of the connecting edge of the parent node. 200f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines // @param position the parent node 201f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines // @param the tree being joined. 202f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines // @return the joined tree 203f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines template<size_t DIRECT, class Pos> 204f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines BinaryTree& merge(Pos position, BinaryTree& pTree) { 205f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines if (this == &pTree) 206f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines return *this; 207f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines 208f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines if (!pTree.empty()) { 209f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines proxy::hook<DIRECT>(position.m_pNode, 210f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines const_cast<const NodeBase*>(pTree.m_Root.node.left)); 211f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines BinaryTreeBase<Input>::m_Root.summon( 212f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines pTree.BinaryTreeBase<Input>::m_Root); 213f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines BinaryTreeBase<Input>::m_Root.delegate(pTree.m_Root); 214f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines pTree.m_Root.node.left = pTree.m_Root.node.right = &pTree.m_Root.node; 215f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines } 216f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines return *this; 217f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines } 218f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines}; 219f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines 2205460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao/** \class InputTree 2215460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * \brief InputTree is the input tree to contains all inputs from the 2225460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * command line. 2235460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * 2245460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * InputTree, of course, is uncopyable. 2255460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * 2265460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * @see Input 2275460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao */ 2285460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaoclass InputTree : public BinaryTree<Input> 2295460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao{ 2305460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaoprivate: 2315460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef BinaryTree<Input> BinTreeTy; 2325460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 2335460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaopublic: 2345460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao enum Direction { 2355460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao Inclusive = TreeIteratorBase::Leftward, 2365460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao Positional = TreeIteratorBase::Rightward 2375460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao }; 2385460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 2395460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef BinaryTree<Input>::iterator iterator; 2405460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef BinaryTree<Input>::const_iterator const_iterator; 2415460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 2425460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaopublic: 243affc150dc44fab1911775a49636d0ce85333b634Zonr Chang /** \class Mover 244affc150dc44fab1911775a49636d0ce85333b634Zonr Chang * \brief Mover provides the interface for moving iterator forward. 245affc150dc44fab1911775a49636d0ce85333b634Zonr Chang * 246affc150dc44fab1911775a49636d0ce85333b634Zonr Chang * Mover is a function object (functor). @ref Mover::move moves 247affc150dc44fab1911775a49636d0ce85333b634Zonr Chang * iterator forward in certain direction. @ref Mover::connect 248affc150dc44fab1911775a49636d0ce85333b634Zonr Chang * connects two nodes of the given iterators togather. 249affc150dc44fab1911775a49636d0ce85333b634Zonr Chang */ 250affc150dc44fab1911775a49636d0ce85333b634Zonr Chang struct Mover { 251affc150dc44fab1911775a49636d0ce85333b634Zonr Chang virtual ~Mover() {} 25267e37f1be98c926645219cfb47fab9e90d8c725cShih-wei Liao virtual void connect(TreeIteratorBase& pFrom, const TreeIteratorBase& pTo) const = 0; 25367e37f1be98c926645219cfb47fab9e90d8c725cShih-wei Liao virtual void move(TreeIteratorBase& pNode) const = 0; 2545460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao }; 2555460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 256affc150dc44fab1911775a49636d0ce85333b634Zonr Chang /** \class Succeeder 257affc150dc44fab1911775a49636d0ce85333b634Zonr Chang * \brief class Succeeder moves the iterator afterward. 258affc150dc44fab1911775a49636d0ce85333b634Zonr Chang */ 259affc150dc44fab1911775a49636d0ce85333b634Zonr Chang struct Succeeder : public Mover { 26067e37f1be98c926645219cfb47fab9e90d8c725cShih-wei Liao virtual void connect(TreeIteratorBase& pFrom, const TreeIteratorBase& pTo) const { 2615460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao proxy::hook<Positional>(pFrom.m_pNode, pTo.m_pNode); 2625460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 2635460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 26467e37f1be98c926645219cfb47fab9e90d8c725cShih-wei Liao virtual void move(TreeIteratorBase& pNode) const { 2655460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao pNode.move<Positional>(); 2665460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 2675460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao }; 2685460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 269affc150dc44fab1911775a49636d0ce85333b634Zonr Chang /** \class Includer 270affc150dc44fab1911775a49636d0ce85333b634Zonr Chang * \brief class Includer moves the iterator downward. 271affc150dc44fab1911775a49636d0ce85333b634Zonr Chang */ 272affc150dc44fab1911775a49636d0ce85333b634Zonr Chang struct Includer : public Mover { 27367e37f1be98c926645219cfb47fab9e90d8c725cShih-wei Liao virtual void connect(TreeIteratorBase& pFrom, const TreeIteratorBase& pTo) const { 2745460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao proxy::hook<Inclusive>(pFrom.m_pNode, pTo.m_pNode); 2755460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 2765460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 27767e37f1be98c926645219cfb47fab9e90d8c725cShih-wei Liao virtual void move(TreeIteratorBase& pNode) const { 2785460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao pNode.move<Inclusive>(); 2795460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 2805460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao }; 2815460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 2825460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaopublic: 2835460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao static Succeeder Afterward; 2845460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao static Includer Downward; 2855460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 2865460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaopublic: 2875460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 2885460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao using BinTreeTy::merge; 2895460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 2905460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao // ----- modify ----- // 2915460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao template<size_t DIRECT> 29267e37f1be98c926645219cfb47fab9e90d8c725cShih-wei Liao InputTree& enterGroup(TreeIteratorBase pRoot); 2935460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 2945460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao template<size_t DIRECT> 29567e37f1be98c926645219cfb47fab9e90d8c725cShih-wei Liao InputTree& insert(TreeIteratorBase pRoot, 29622add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao Input& pInput); 2975460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 29822add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao InputTree& merge(TreeIteratorBase pRoot, 299affc150dc44fab1911775a49636d0ce85333b634Zonr Chang const Mover& pMover, 3005460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao InputTree& pTree); 3015460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 30267e37f1be98c926645219cfb47fab9e90d8c725cShih-wei Liao InputTree& insert(TreeIteratorBase pRoot, 303affc150dc44fab1911775a49636d0ce85333b634Zonr Chang const Mover& pMover, 30422add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao Input& pInput); 3055460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 30667e37f1be98c926645219cfb47fab9e90d8c725cShih-wei Liao InputTree& enterGroup(TreeIteratorBase pRoot, 307affc150dc44fab1911775a49636d0ce85333b634Zonr Chang const Mover& pMover); 3085460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 3095460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao}; 3105460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 3115460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaobool isGroup(const InputTree::iterator& pos); 3125460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaobool isGroup(const InputTree::const_iterator& pos); 3135460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaobool isGroup(const InputTree::dfs_iterator& pos); 3145460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaobool isGroup(const InputTree::const_dfs_iterator& pos); 3155460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaobool isGroup(const InputTree::bfs_iterator& pos); 3165460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaobool isGroup(const InputTree::const_bfs_iterator& pos); 3175460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 3185460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao} // namespace of mcld 3195460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 3205460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao//===----------------------------------------------------------------------===// 3215460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao// template member functions 32222add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao//===----------------------------------------------------------------------===// 3235460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaotemplate<size_t DIRECT> 3245460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaomcld::InputTree& 32567e37f1be98c926645219cfb47fab9e90d8c725cShih-wei Liaomcld::InputTree::enterGroup(mcld::TreeIteratorBase pRoot) 3265460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao{ 32722add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao BinTreeTy::node_type* node = createNode(); 328affc150dc44fab1911775a49636d0ce85333b634Zonr Chang if (pRoot.isRoot()) 329affc150dc44fab1911775a49636d0ce85333b634Zonr Chang proxy::hook<TreeIteratorBase::Leftward>(pRoot.m_pNode, 3305460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao const_cast<const node_type*>(node)); 3315460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao else 332affc150dc44fab1911775a49636d0ce85333b634Zonr Chang proxy::hook<DIRECT>(pRoot.m_pNode, 3335460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao const_cast<const node_type*>(node)); 3345460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao return *this; 3355460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao} 3365460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 3375460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaotemplate<size_t DIRECT> 33867e37f1be98c926645219cfb47fab9e90d8c725cShih-wei Liaomcld::InputTree& mcld::InputTree::insert(mcld::TreeIteratorBase pRoot, 33922add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao mcld::Input& pInput) 3405460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao{ 3415460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao BinTreeTy::node_type* node = createNode(); 34222add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao node->data = &pInput; 343affc150dc44fab1911775a49636d0ce85333b634Zonr Chang if (pRoot.isRoot()) 344affc150dc44fab1911775a49636d0ce85333b634Zonr Chang proxy::hook<TreeIteratorBase::Leftward>(pRoot.m_pNode, 3455460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao const_cast<const node_type*>(node)); 3465460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao else 347affc150dc44fab1911775a49636d0ce85333b634Zonr Chang proxy::hook<DIRECT>(pRoot.m_pNode, 3485460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao const_cast<const node_type*>(node)); 3495460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao return *this; 3505460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao} 3515460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 3525460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao#endif 3535460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 354