File indexing completed on 2024-04-21 05:43:20
0001 /*************************************************************************** 0002 * Copyright (C) 2004-2005 by Daniel Clarke * 0003 * daniel.jc@gmail.com * 0004 * * 0005 * This program is free software; you can redistribute it and/or modify * 0006 * it under the terms of the GNU General Public License as published by * 0007 * the Free Software Foundation; either version 2 of the License, or * 0008 * (at your option) any later version. * 0009 * * 0010 * This program is distributed in the hope that it will be useful, * 0011 * but WITHOUT ANY WARRANTY; without even the implied warranty of * 0012 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * 0013 * GNU General Public License for more details. * 0014 * * 0015 * You should have received a copy of the GNU General Public License * 0016 * along with this program; if not, write to the * 0017 * Free Software Foundation, Inc., * 0018 * 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. * 0019 ***************************************************************************/ 0020 0021 #include "traverser.h" 0022 #include "pic14.h" 0023 0024 Traverser::Traverser(BTreeNode *root) 0025 { 0026 m_root = root; 0027 m_current = root; 0028 } 0029 0030 Traverser::~Traverser() 0031 { 0032 } 0033 0034 BTreeNode * Traverser::start() 0035 { 0036 /* To find the start we will iterate, or possibly recurse 0037 down the tree, each time turning down the node that has children, 0038 if they both have no children we have reached the end and it shouldn't 0039 really matter which we pick (check this algorithm) */ 0040 0041 BTreeNode *n = m_root; 0042 bool found = false; 0043 0044 while(!found) 0045 { 0046 if( !n->hasChildren() ) found = true; 0047 else 0048 { 0049 if( !n->left()->hasChildren() ) 0050 { 0051 if( !n->right()->hasChildren() ) found = true; 0052 n = n->right(); 0053 } 0054 else n = n->left(); 0055 } 0056 } 0057 //if(n->parent()) m_current = n->parent(); 0058 //else m_current = n; 0059 m_current = n; 0060 return m_current; 0061 } 0062 0063 BTreeNode * Traverser::next() 0064 { 0065 // a.t.m we will just take the next thing to be the parent. 0066 if( m_current != m_root ) m_current = m_current->parent(); 0067 return m_current; 0068 } 0069 0070 bool Traverser::onLeftBranch() 0071 { 0072 return current()->parent()->left() == current(); 0073 } 0074 0075 BTreeNode * Traverser::oppositeNode() 0076 { 0077 if ( onLeftBranch() ) 0078 return current()->parent()->right(); 0079 else 0080 return current()->parent()->left(); 0081 } 0082 0083 void Traverser::descendLeftwardToTerminal() 0084 { 0085 bool done = false; 0086 while(!done) 0087 { 0088 if( !current()->hasChildren() ) return; 0089 else 0090 { 0091 m_current = current()->left(); 0092 } 0093 } 0094 } 0095 0096 void Traverser::moveToParent() 0097 { 0098 if(current()->parent()) m_current = current()->parent(); 0099 } 0100