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//===----------------------------------------------------------------------===// 937b74a387bb3993387029859c2d9d051c41c724eStephen Hines#ifndef MCLD_INPUTTREE_H_ 1037b74a387bb3993387029859c2d9d051c41c724eStephen Hines#define MCLD_INPUTTREE_H_ 115460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1237b74a387bb3993387029859c2d9d051c41c724eStephen Hines#include "mcld/ADT/BinTree.h" 1337b74a387bb3993387029859c2d9d051c41c724eStephen Hines#include "mcld/ADT/TypeTraits.h" 1437b74a387bb3993387029859c2d9d051c41c724eStephen Hines#include "mcld/MC/Input.h" 1537b74a387bb3993387029859c2d9d051c41c724eStephen Hines#include "mcld/Support/Path.h" 165460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 175460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao#include <string> 185460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1922add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liaonamespace mcld { 205460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 2137b74a387bb3993387029859c2d9d051c41c724eStephen Hines/** \class template<typename Traits, typename Iterator> 2237b74a387bb3993387029859c2d9d051c41c724eStephen Hines * PolicyIterator<mcld::Input> 235460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * \brief PolicyIterator<mcld::Input> is a partially specific PolicyIterator 245460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao */ 2537b74a387bb3993387029859c2d9d051c41c724eStephen Hinestemplate <typename Traits, typename IteratorType> 2637b74a387bb3993387029859c2d9d051c41c724eStephen Hinesclass PolicyIterator<mcld::Input, Traits, IteratorType> 2737b74a387bb3993387029859c2d9d051c41c724eStephen Hines : public PolicyIteratorBase<Input, Traits, IteratorType> { 2837b74a387bb3993387029859c2d9d051c41c724eStephen Hines public: 295460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef PolicyIterator<Input, Traits, IteratorType> Self; 305460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef PolicyIteratorBase<Input, Traits, IteratorType> Base; 3137b74a387bb3993387029859c2d9d051c41c724eStephen Hines typedef PolicyIterator<Input, typename Traits::nonconst_traits, IteratorType> 3237b74a387bb3993387029859c2d9d051c41c724eStephen Hines iterator; 3337b74a387bb3993387029859c2d9d051c41c724eStephen Hines typedef PolicyIterator<Input, typename Traits::const_traits, IteratorType> 3437b74a387bb3993387029859c2d9d051c41c724eStephen Hines const_iterator; 355460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 3637b74a387bb3993387029859c2d9d051c41c724eStephen Hines public: 3737b74a387bb3993387029859c2d9d051c41c724eStephen Hines PolicyIterator() : Base() {} 385460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 3937b74a387bb3993387029859c2d9d051c41c724eStephen Hines PolicyIterator(const iterator& X) : Base(X.m_pNode) {} 405460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 4137b74a387bb3993387029859c2d9d051c41c724eStephen Hines explicit PolicyIterator(NodeBase* X) : Base(X) {} 425460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 435460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao virtual ~PolicyIterator() {} 445460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 4537b74a387bb3993387029859c2d9d051c41c724eStephen Hines bool isGroup() const { return !Base::hasData() && !Base::isRoot(); } 465460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 475460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao Self& operator++() { 485460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao IteratorType::advance(); 4922add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao // skip the Group node 5022add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao while (isGroup()) 515460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao IteratorType::advance(); 525460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao return *this; 535460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 545460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 555460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao Self operator++(int) { 565460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao Self tmp(*this); 575460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao IteratorType::advance(); 5822add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao // skip the Group node 5922add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao while (isGroup()) 605460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao IteratorType::advance(); 615460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao return tmp; 625460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 635460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao}; 645460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 6537b74a387bb3993387029859c2d9d051c41c724eStephen Hinestemplate <> 6637b74a387bb3993387029859c2d9d051c41c724eStephen Hinesclass BinaryTree<Input> : public BinaryTreeBase<Input> { 6737b74a387bb3993387029859c2d9d051c41c724eStephen Hines public: 6837b74a387bb3993387029859c2d9d051c41c724eStephen Hines typedef size_t size_type; 6937b74a387bb3993387029859c2d9d051c41c724eStephen Hines typedef ptrdiff_t difference_type; 7037b74a387bb3993387029859c2d9d051c41c724eStephen Hines typedef Input value_type; 7137b74a387bb3993387029859c2d9d051c41c724eStephen Hines typedef value_type* pointer; 7237b74a387bb3993387029859c2d9d051c41c724eStephen Hines typedef value_type& reference; 7337b74a387bb3993387029859c2d9d051c41c724eStephen Hines typedef const value_type* const_pointer; 7437b74a387bb3993387029859c2d9d051c41c724eStephen Hines typedef const value_type& const_reference; 7537b74a387bb3993387029859c2d9d051c41c724eStephen Hines 7637b74a387bb3993387029859c2d9d051c41c724eStephen Hines typedef BinaryTree<Input> Self; 77f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines typedef TreeIterator<value_type, NonConstTraits<value_type> > iterator; 7837b74a387bb3993387029859c2d9d051c41c724eStephen Hines typedef TreeIterator<value_type, ConstTraits<value_type> > const_iterator; 7937b74a387bb3993387029859c2d9d051c41c724eStephen Hines 8037b74a387bb3993387029859c2d9d051c41c724eStephen Hines typedef PolicyIterator<value_type, NonConstTraits<value_type>, DFSIterator> 8137b74a387bb3993387029859c2d9d051c41c724eStephen Hines dfs_iterator; 8237b74a387bb3993387029859c2d9d051c41c724eStephen Hines typedef PolicyIterator<value_type, ConstTraits<value_type>, DFSIterator> 8337b74a387bb3993387029859c2d9d051c41c724eStephen Hines const_dfs_iterator; 8437b74a387bb3993387029859c2d9d051c41c724eStephen Hines typedef PolicyIterator<value_type, NonConstTraits<value_type>, BFSIterator> 8537b74a387bb3993387029859c2d9d051c41c724eStephen Hines bfs_iterator; 8637b74a387bb3993387029859c2d9d051c41c724eStephen Hines typedef PolicyIterator<value_type, ConstTraits<value_type>, BFSIterator> 8737b74a387bb3993387029859c2d9d051c41c724eStephen Hines const_bfs_iterator; 8837b74a387bb3993387029859c2d9d051c41c724eStephen Hines 8937b74a387bb3993387029859c2d9d051c41c724eStephen Hines protected: 90f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines typedef Node<value_type> node_type; 91f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines 9237b74a387bb3993387029859c2d9d051c41c724eStephen Hines public: 93f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines // ----- constructors and destructor ----- // 9437b74a387bb3993387029859c2d9d051c41c724eStephen Hines BinaryTree() : BinaryTreeBase<Input>() {} 95f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines 9637b74a387bb3993387029859c2d9d051c41c724eStephen Hines ~BinaryTree() {} 97f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines 98f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines // ----- iterators ----- // 9937b74a387bb3993387029859c2d9d051c41c724eStephen Hines bfs_iterator bfs_begin() { 10037b74a387bb3993387029859c2d9d051c41c724eStephen Hines bfs_iterator it = bfs_iterator(BinaryTreeBase<Input>::m_Root.node.left); 10137b74a387bb3993387029859c2d9d051c41c724eStephen Hines if (it.isGroup()) 10237b74a387bb3993387029859c2d9d051c41c724eStephen Hines ++it; 10337b74a387bb3993387029859c2d9d051c41c724eStephen Hines return it; 104f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines } 105f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines 10637b74a387bb3993387029859c2d9d051c41c724eStephen Hines bfs_iterator bfs_end() { 10737b74a387bb3993387029859c2d9d051c41c724eStephen Hines return bfs_iterator(BinaryTreeBase<Input>::m_Root.node.right); 10837b74a387bb3993387029859c2d9d051c41c724eStephen Hines } 109f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines 11037b74a387bb3993387029859c2d9d051c41c724eStephen Hines const_bfs_iterator bfs_begin() const { 11137b74a387bb3993387029859c2d9d051c41c724eStephen Hines const_bfs_iterator it = 11237b74a387bb3993387029859c2d9d051c41c724eStephen Hines const_bfs_iterator(BinaryTreeBase<Input>::m_Root.node.left); 11337b74a387bb3993387029859c2d9d051c41c724eStephen Hines if (it.isGroup()) 11437b74a387bb3993387029859c2d9d051c41c724eStephen Hines ++it; 11537b74a387bb3993387029859c2d9d051c41c724eStephen Hines return it; 116f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines } 117f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines 11837b74a387bb3993387029859c2d9d051c41c724eStephen Hines const_bfs_iterator bfs_end() const { 11937b74a387bb3993387029859c2d9d051c41c724eStephen Hines return const_bfs_iterator(BinaryTreeBase<Input>::m_Root.node.right); 12037b74a387bb3993387029859c2d9d051c41c724eStephen Hines } 121f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines 12237b74a387bb3993387029859c2d9d051c41c724eStephen Hines dfs_iterator dfs_begin() { 123f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines dfs_iterator it = dfs_iterator(BinaryTreeBase<Input>::m_Root.node.left); 124f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines if (it.isGroup()) 125f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines ++it; 126f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines return it; 127f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines } 128f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines 12937b74a387bb3993387029859c2d9d051c41c724eStephen Hines dfs_iterator dfs_end() { 13037b74a387bb3993387029859c2d9d051c41c724eStephen Hines return dfs_iterator(BinaryTreeBase<Input>::m_Root.node.right); 13137b74a387bb3993387029859c2d9d051c41c724eStephen Hines } 132f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines 13337b74a387bb3993387029859c2d9d051c41c724eStephen Hines const_dfs_iterator dfs_begin() const { 134f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines const_dfs_iterator it = 13537b74a387bb3993387029859c2d9d051c41c724eStephen Hines const_dfs_iterator(BinaryTreeBase<Input>::m_Root.node.left); 136f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines if (it.isGroup()) 137f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines ++it; 138f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines return it; 139f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines } 140f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines 14137b74a387bb3993387029859c2d9d051c41c724eStephen Hines const_dfs_iterator dfs_end() const { 14237b74a387bb3993387029859c2d9d051c41c724eStephen Hines return const_dfs_iterator(BinaryTreeBase<Input>::m_Root.node.right); 14337b74a387bb3993387029859c2d9d051c41c724eStephen Hines } 144f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines 14537b74a387bb3993387029859c2d9d051c41c724eStephen Hines iterator root() { return iterator(&(BinaryTreeBase<Input>::m_Root.node)); } 146f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines 14737b74a387bb3993387029859c2d9d051c41c724eStephen Hines const_iterator root() const { 148f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines // FIXME: provide the iterater constructors for constant NodeBase instead of 149f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines // using const_cast 150f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines return const_iterator( 15137b74a387bb3993387029859c2d9d051c41c724eStephen Hines const_cast<NodeBase*>(&BinaryTreeBase<Input>::m_Root.node)); 152f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines } 153f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines 15437b74a387bb3993387029859c2d9d051c41c724eStephen Hines iterator begin() { 155f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines iterator it = iterator(BinaryTreeBase<Input>::m_Root.node.left); 156f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines return it; 157f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines } 158f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines 15937b74a387bb3993387029859c2d9d051c41c724eStephen Hines iterator end() { return iterator(BinaryTreeBase<Input>::m_Root.node.right); } 160f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines 16137b74a387bb3993387029859c2d9d051c41c724eStephen Hines const_iterator begin() const { 16237b74a387bb3993387029859c2d9d051c41c724eStephen Hines return const_iterator(BinaryTreeBase<Input>::m_Root.node.left); 163f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines } 164f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines 16537b74a387bb3993387029859c2d9d051c41c724eStephen Hines const_iterator end() const { 16637b74a387bb3993387029859c2d9d051c41c724eStephen Hines return const_iterator(BinaryTreeBase<Input>::m_Root.node.right); 16737b74a387bb3993387029859c2d9d051c41c724eStephen Hines } 168f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines 169f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines // ----- modifiers ----- // 170f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines /// join - create a leaf node and merge it in the tree. 171f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines // This version of join determines the direction on compilation time. 172f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines // @param DIRECT the direction of the connecting edge of the parent node. 173f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines // @param position the parent node 174f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines // @param value the value being pushed. 17537b74a387bb3993387029859c2d9d051c41c724eStephen Hines template <size_t DIRECT> 17687f34658dec9097d987d254a990ea7f311bfc95fStephen Hines BinaryTree& join(TreeIteratorBase& pPosition, const Input& value) { 17737b74a387bb3993387029859c2d9d051c41c724eStephen Hines node_type* node = BinaryTreeBase<Input>::createNode(); 178f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines node->data = const_cast<Input*>(&value); 17987f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 18087f34658dec9097d987d254a990ea7f311bfc95fStephen Hines if (pPosition.isRoot()) 18187f34658dec9097d987d254a990ea7f311bfc95fStephen Hines pPosition.hook<TreeIteratorBase::Leftward>(node); 182f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines else 18387f34658dec9097d987d254a990ea7f311bfc95fStephen Hines pPosition.hook<DIRECT>(node); 18487f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 185f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines return *this; 186f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines } 187f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines 188f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines /// merge - merge the tree 189f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines // @param DIRECT the direction of the connecting edge of the parent node. 190f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines // @param position the parent node 191f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines // @param the tree being joined. 192f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines // @return the joined tree 19337b74a387bb3993387029859c2d9d051c41c724eStephen Hines template <size_t DIRECT> 19487f34658dec9097d987d254a990ea7f311bfc95fStephen Hines BinaryTree& merge(TreeIteratorBase& pPosition, BinaryTree& pTree) { 195f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines if (this == &pTree) 196f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines return *this; 197f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines 198f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines if (!pTree.empty()) { 19987f34658dec9097d987d254a990ea7f311bfc95fStephen Hines pPosition.hook<DIRECT>(pTree.m_Root.node.left); 20037b74a387bb3993387029859c2d9d051c41c724eStephen Hines BinaryTreeBase<Input>::m_Root.summon(pTree.BinaryTreeBase<Input>::m_Root); 201f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines BinaryTreeBase<Input>::m_Root.delegate(pTree.m_Root); 202f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines pTree.m_Root.node.left = pTree.m_Root.node.right = &pTree.m_Root.node; 203f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines } 204f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines return *this; 205f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines } 206f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines}; 207f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines 2085460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao/** \class InputTree 2095460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * \brief InputTree is the input tree to contains all inputs from the 2105460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * command line. 2115460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * 2125460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * InputTree, of course, is uncopyable. 2135460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * 2145460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * @see Input 2155460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao */ 21637b74a387bb3993387029859c2d9d051c41c724eStephen Hinesclass InputTree : public BinaryTree<Input> { 21737b74a387bb3993387029859c2d9d051c41c724eStephen Hines private: 2185460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef BinaryTree<Input> BinTreeTy; 2195460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 22037b74a387bb3993387029859c2d9d051c41c724eStephen Hines public: 2215460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao enum Direction { 22237b74a387bb3993387029859c2d9d051c41c724eStephen Hines Inclusive = TreeIteratorBase::Leftward, 2235460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao Positional = TreeIteratorBase::Rightward 2245460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao }; 2255460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 22637b74a387bb3993387029859c2d9d051c41c724eStephen Hines typedef BinaryTree<Input>::iterator iterator; 2275460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef BinaryTree<Input>::const_iterator const_iterator; 2285460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 22937b74a387bb3993387029859c2d9d051c41c724eStephen Hines public: 230affc150dc44fab1911775a49636d0ce85333b634Zonr Chang /** \class Mover 231affc150dc44fab1911775a49636d0ce85333b634Zonr Chang * \brief Mover provides the interface for moving iterator forward. 232affc150dc44fab1911775a49636d0ce85333b634Zonr Chang * 233affc150dc44fab1911775a49636d0ce85333b634Zonr Chang * Mover is a function object (functor). @ref Mover::move moves 234affc150dc44fab1911775a49636d0ce85333b634Zonr Chang * iterator forward in certain direction. @ref Mover::connect 235affc150dc44fab1911775a49636d0ce85333b634Zonr Chang * connects two nodes of the given iterators togather. 236affc150dc44fab1911775a49636d0ce85333b634Zonr Chang */ 237affc150dc44fab1911775a49636d0ce85333b634Zonr Chang struct Mover { 23887f34658dec9097d987d254a990ea7f311bfc95fStephen Hines virtual void connect(TreeIteratorBase& pFrom, NodeBase* pTo) const = 0; 23967e37f1be98c926645219cfb47fab9e90d8c725cShih-wei Liao virtual void move(TreeIteratorBase& pNode) const = 0; 24037b74a387bb3993387029859c2d9d051c41c724eStephen Hines virtual ~Mover() {} 2415460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao }; 2425460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 243affc150dc44fab1911775a49636d0ce85333b634Zonr Chang /** \class Succeeder 244affc150dc44fab1911775a49636d0ce85333b634Zonr Chang * \brief class Succeeder moves the iterator afterward. 245affc150dc44fab1911775a49636d0ce85333b634Zonr Chang */ 246affc150dc44fab1911775a49636d0ce85333b634Zonr Chang struct Succeeder : public Mover { 24787f34658dec9097d987d254a990ea7f311bfc95fStephen Hines void connect(TreeIteratorBase& pFrom, NodeBase* pTo) const { 24887f34658dec9097d987d254a990ea7f311bfc95fStephen Hines pFrom.hook<Positional>(pTo); 2495460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 2505460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 25137b74a387bb3993387029859c2d9d051c41c724eStephen Hines void move(TreeIteratorBase& pNode) const { pNode.move<Positional>(); } 2525460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao }; 2535460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 254affc150dc44fab1911775a49636d0ce85333b634Zonr Chang /** \class Includer 255affc150dc44fab1911775a49636d0ce85333b634Zonr Chang * \brief class Includer moves the iterator downward. 256affc150dc44fab1911775a49636d0ce85333b634Zonr Chang */ 257affc150dc44fab1911775a49636d0ce85333b634Zonr Chang struct Includer : public Mover { 25887f34658dec9097d987d254a990ea7f311bfc95fStephen Hines void connect(TreeIteratorBase& pFrom, NodeBase* pTo) const { 25987f34658dec9097d987d254a990ea7f311bfc95fStephen Hines pFrom.hook<Inclusive>(pTo); 2605460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 2615460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 26237b74a387bb3993387029859c2d9d051c41c724eStephen Hines void move(TreeIteratorBase& pNode) const { pNode.move<Inclusive>(); } 2635460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao }; 2645460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 26537b74a387bb3993387029859c2d9d051c41c724eStephen Hines public: 2665460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao static Succeeder Afterward; 26737b74a387bb3993387029859c2d9d051c41c724eStephen Hines static Includer Downward; 2685460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 26937b74a387bb3993387029859c2d9d051c41c724eStephen Hines public: 2705460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao using BinTreeTy::merge; 2715460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 2725460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao // ----- modify ----- // 27337b74a387bb3993387029859c2d9d051c41c724eStephen Hines template <size_t DIRECT> 27467e37f1be98c926645219cfb47fab9e90d8c725cShih-wei Liao InputTree& enterGroup(TreeIteratorBase pRoot); 2755460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 27637b74a387bb3993387029859c2d9d051c41c724eStephen Hines template <size_t DIRECT> 27737b74a387bb3993387029859c2d9d051c41c724eStephen Hines InputTree& insert(TreeIteratorBase pRoot, Input& pInput); 2785460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 27922add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao InputTree& merge(TreeIteratorBase pRoot, 280affc150dc44fab1911775a49636d0ce85333b634Zonr Chang const Mover& pMover, 2815460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao InputTree& pTree); 2825460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 28337b74a387bb3993387029859c2d9d051c41c724eStephen Hines InputTree& insert(TreeIteratorBase pRoot, const Mover& pMover, Input& pInput); 2845460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 28537b74a387bb3993387029859c2d9d051c41c724eStephen Hines InputTree& enterGroup(TreeIteratorBase pRoot, const Mover& pMover); 2865460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao}; 2875460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 2885460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaobool isGroup(const InputTree::iterator& pos); 2895460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaobool isGroup(const InputTree::const_iterator& pos); 2905460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaobool isGroup(const InputTree::dfs_iterator& pos); 2915460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaobool isGroup(const InputTree::const_dfs_iterator& pos); 2925460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaobool isGroup(const InputTree::bfs_iterator& pos); 2935460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaobool isGroup(const InputTree::const_bfs_iterator& pos); 2945460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 29537b74a387bb3993387029859c2d9d051c41c724eStephen Hines} // namespace mcld 2965460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 2975460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao//===----------------------------------------------------------------------===// 2985460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao// template member functions 29922add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao//===----------------------------------------------------------------------===// 30037b74a387bb3993387029859c2d9d051c41c724eStephen Hinestemplate <size_t DIRECT> 30137b74a387bb3993387029859c2d9d051c41c724eStephen Hinesmcld::InputTree& mcld::InputTree::enterGroup(mcld::TreeIteratorBase pRoot) { 30222add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao BinTreeTy::node_type* node = createNode(); 30387f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 304affc150dc44fab1911775a49636d0ce85333b634Zonr Chang if (pRoot.isRoot()) 30587f34658dec9097d987d254a990ea7f311bfc95fStephen Hines pRoot.hook<TreeIteratorBase::Leftward>(node); 3065460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao else 30787f34658dec9097d987d254a990ea7f311bfc95fStephen Hines pRoot.hook<DIRECT>(node); 30887f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 3095460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao return *this; 3105460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao} 3115460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 31237b74a387bb3993387029859c2d9d051c41c724eStephen Hinestemplate <size_t DIRECT> 31367e37f1be98c926645219cfb47fab9e90d8c725cShih-wei Liaomcld::InputTree& mcld::InputTree::insert(mcld::TreeIteratorBase pRoot, 31437b74a387bb3993387029859c2d9d051c41c724eStephen Hines mcld::Input& pInput) { 3155460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao BinTreeTy::node_type* node = createNode(); 31622add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao node->data = &pInput; 31787f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 318affc150dc44fab1911775a49636d0ce85333b634Zonr Chang if (pRoot.isRoot()) 31987f34658dec9097d987d254a990ea7f311bfc95fStephen Hines pRoot.hook<TreeIteratorBase::Leftward>(node); 3205460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao else 32187f34658dec9097d987d254a990ea7f311bfc95fStephen Hines pRoot.hook<DIRECT>(node); 32287f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 3235460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao return *this; 3245460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao} 3255460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 32637b74a387bb3993387029859c2d9d051c41c724eStephen Hines#endif // MCLD_INPUTTREE_H_ 327