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 #ifndef TRAVERSER_H
0021 #define TRAVERSER_H
0022 
0023 #include "btreenode.h"
0024 
0025 /**
0026 Keeps persistant information needed and the algorithm for traversing the binary trees made of BTreeNodes, initialise either by passing a BTreeBase or BTreeNode to traverse a sub tree.
0027 
0028 Note that this is designed for traversing in the *reverse* way starting at the end of each branch
0029 in order to calculate the expression contained in the tree.
0030 
0031 @author Daniel Clarke
0032 */
0033 class Traverser
0034 {
0035 public:
0036     Traverser(BTreeNode *root);
0037     ~Traverser();
0038     
0039     /** Find where to start in the tree and return it also resets all the data related to the traversal. */
0040     BTreeNode *start();
0041     
0042     /** Finds the next node to move to and returns it. */
0043     BTreeNode *next();
0044     
0045     /** Returns true if we are on the left branch, false otherwise. */
0046     bool onLeftBranch();
0047     
0048     /** Returns the node on the opposite branch of the parent. */
0049     BTreeNode * oppositeNode();
0050     
0051     BTreeNode * current() const { return m_current; }
0052 
0053     void setCurrent(BTreeNode *current){m_current = current;}
0054     
0055     /** From the current position, go down the tree taking a left turn always, 
0056      and stopping when reaching the left terminal node.
0057      */
0058     void descendLeftwardToTerminal();
0059     
0060     /** It might occur in the future that next() does not just move to the parent,
0061      so use this for moving to parent
0062      */
0063     void moveToParent();
0064     
0065     BTreeNode *root() const {return m_root;}
0066     
0067 protected:
0068     BTreeNode *m_root;
0069     BTreeNode *m_current;
0070 };
0071 
0072 #endif