InputTree.cpp revision 22add6ff3426df1a85089fe6a6e1597ee3b6f300
1affc150dc44fab1911775a49636d0ce85333b634Zonr Chang//===- InputTree.cpp ------------------------------------------------------===// 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#include <mcld/InputTree.h> 105460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 115460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaousing namespace mcld; 125460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 135460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei LiaoInputTree::Succeeder InputTree::Afterward; 145460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei LiaoInputTree::Includer InputTree::Downward; 155460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 165460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao//===----------------------------------------------------------------------===// 175460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao// InputTree 1822add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao//===----------------------------------------------------------------------===// 1922add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei LiaoInputTree& InputTree::merge(TreeIteratorBase pRoot, 20affc150dc44fab1911775a49636d0ce85333b634Zonr Chang const InputTree::Mover& pMover, 215460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao InputTree& pTree) 225460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao{ 235460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao if (this == &pTree) 245460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao return *this; 255460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 265460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao if (!pTree.empty()) { 27affc150dc44fab1911775a49636d0ce85333b634Zonr Chang pMover.connect(pRoot, iterator(pTree.m_Root.node.right)); 285460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao BinaryTreeBase<Input>::m_Root.summon( 295460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao pTree.BinaryTreeBase<Input>::m_Root); 305460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao BinaryTreeBase<Input>::m_Root.delegate(pTree.m_Root); 315460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao pTree.m_Root.node.left = pTree.m_Root.node.right = &pTree.m_Root.node; 325460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 335460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao return *this; 345460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao} 355460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 3667e37f1be98c926645219cfb47fab9e90d8c725cShih-wei LiaoInputTree& InputTree::enterGroup(TreeIteratorBase pRoot, 37affc150dc44fab1911775a49636d0ce85333b634Zonr Chang const InputTree::Mover& pMover) 385460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao{ 395460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao NodeBase* node = createNode(); 40affc150dc44fab1911775a49636d0ce85333b634Zonr Chang pMover.connect(pRoot, iterator(node)); 415460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao return *this; 425460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao} 435460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 4467e37f1be98c926645219cfb47fab9e90d8c725cShih-wei LiaoInputTree& InputTree::insert(TreeIteratorBase pRoot, 45affc150dc44fab1911775a49636d0ce85333b634Zonr Chang const InputTree::Mover& pMover, 4622add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao mcld::Input& pInput) 475460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao{ 485460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao BinaryTree<Input>::node_type* node = createNode(); 4922add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao node->data = &pInput; 50affc150dc44fab1911775a49636d0ce85333b634Zonr Chang pMover.connect(pRoot, iterator(node)); 515460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao return *this; 525460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao} 535460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 545460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao//===----------------------------------------------------------------------===// 555460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao// non-member functions 5622add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao//===----------------------------------------------------------------------===// 575460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaobool mcld::isGroup(const InputTree::iterator& pos) 585460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao{ 5922add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao return !pos.hasData() && !pos.isRoot(); 605460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao} 615460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 625460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaobool mcld::isGroup(const InputTree::const_iterator& pos) 635460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao{ 6422add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao return !pos.hasData() && !pos.isRoot(); 655460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao} 665460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 675460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaobool mcld::isGroup(const InputTree::dfs_iterator& pos) 685460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao{ 6922add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao return !pos.hasData() && !pos.isRoot(); 705460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao} 715460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 725460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaobool mcld::isGroup(const InputTree::const_dfs_iterator& pos) 735460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao{ 7422add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao return !pos.hasData() && !pos.isRoot(); 755460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao} 765460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 775460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaobool mcld::isGroup(const InputTree::bfs_iterator& pos) 785460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao{ 7922add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao return !pos.hasData() && !pos.isRoot(); 805460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao} 815460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 825460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaobool mcld::isGroup(const InputTree::const_bfs_iterator& pos) 835460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao{ 8422add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao return !pos.hasData() && !pos.isRoot(); 855460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao} 865460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 87