File indexing completed on 2024-07-21 08:05:27

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