diff options
Diffstat (limited to 'microbe/btreebase.cpp')
| -rw-r--r-- | microbe/btreebase.cpp | 248 |
1 files changed, 248 insertions, 0 deletions
diff --git a/microbe/btreebase.cpp b/microbe/btreebase.cpp new file mode 100644 index 0000000..bd9e38a --- /dev/null +++ b/microbe/btreebase.cpp @@ -0,0 +1,248 @@ +/*************************************************************************** + * Copyright (C) 2004-2005 by Daniel Clarke * + * daniel.jc@gmail.com * + * * + * This program is free software; you can redistribute it and/or modify * + * it under the terms of the GNU General Public License as published by * + * the Free Software Foundation; either version 2 of the License, or * + * (at your option) any later version. * + * * + * This program is distributed in the hope that it will be useful, * + * but WITHOUT ANY WARRANTY; without even the implied warranty of * + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * + * GNU General Public License for more details. * + * * + * You should have received a copy of the GNU General Public License * + * along with this program; if not, write to the * + * Free Software Foundation, Inc., * + * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. * + ***************************************************************************/ + +#include "btreebase.h" +#include "traverser.h" +#include "parser.h" +#include "pic14.h" + +BTreeBase::BTreeBase() +{ + m_root = 0L; +} + +void BTreeBase::deleteTree() +{ + if(m_root) m_root->deleteChildren(); + delete m_root; + m_root = 0L; +} + +BTreeBase::~BTreeBase() +{ + deleteTree(); +} + + +void BTreeBase::addNode(BTreeNode *parent, BTreeNode *node, bool left) +{ + // Debugging lines, remove when expression parsing has been completed. + //if(!parent) cerr<<"Null parent pointer!\n"; + //if(!node) cerr<<"Null node pointer!\n"); + + if(left) parent->setLeft(node); + else parent->setRight(node); +} + +void BTreeBase::pruneTree(BTreeNode *root, bool /*conditionalRoot*/) +{ + Traverser t(root); + + t.descendLeftwardToTerminal(); + bool done = false; + while(!done) + { + //t.descendLeftwardToTerminal(); + if( t.current()->parent() ) + { + if( t.oppositeNode()->hasChildren() ) pruneTree(t.oppositeNode()); + } + + t.moveToParent(); + if( !t.current()->hasChildren() ) + { + //if(t.current() == t.root()) done = true; + if(!t.current()->parent()) done = true; + continue; + } + + BTreeNode *l = t.current()->left(); + BTreeNode *r = t.current()->right(); + BTreeNode *n = 0; + BTreeNode *z = 0; + + + // Deal with situations where there are two constants so we want + // to evaluate at compile time + if( (l->type() == number && r->type() == number) ) // && !(t.current()==root&&conditionalRoot) ) + { + if(t.current()->childOp() == Expression::division && r->value() == "0" ) + { + t.current()->setChildOp(Expression::divbyzero); + return; + } + QString value = QString::number(Parser::doArithmetic(l->value().toInt(),r->value().toInt(),t.current()->childOp())); + t.current()->deleteChildren(); + t.current()->setChildOp(Expression::noop); + t.current()->setType(number); + t.current()->setValue(value); + } + + // Addition and subtraction + else if(t.current()->childOp() == Expression::addition || t.current()->childOp() == Expression::subtraction) + { + // See if one of the nodes is 0, and set n to the node that actually has data, + // z to the one containing zero. + bool zero = false; + if( l->value() == "0" ) + { + zero = true; + n = r; + z = l; + } + else if( r->value() == "0" ) + { + zero = true; + n = l; + z = r; + } + // Now get rid of the useless nodes + if(zero) + { + BTreeNode *p = t.current(); // save in order to delete after + + replaceNode(p,n); + t.setCurrent(n); + // Delete the old nodes + delete p; + delete z; + } + } + + // Multiplication and division + else if(t.current()->childOp() == Expression::multiplication || t.current()->childOp() == Expression::division) + { + // See if one of the nodes is 0, and set n to the node that actually has data, + // z to the one containing zero. + bool zero = false; + bool one = false; + if( l->value() == "1" ) + { + one = true; + n = r; + z = l; + } + else if( r->value() == "1" ) + { + one = true; + n = l; + z = r; + } + if( l->value() == "0" ) + { + zero = true; + n = r; + z = l; + } + else if( r->value() == "0" ) + { + + // since we can't call compileError from in this class, we have a special way of handling it: + // Leave the children as they are, and set childOp to divbyzero + if( t.current()->childOp() == Expression::division ) + { + t.current()->setChildOp(Expression::divbyzero); + return; // no point doing any more since we are going to raise a compileError later anyway. + } + zero = true; + n = l; + z = r; + } + // Now get rid of the useless nodes + if(one) + { + BTreeNode *p = t.current(); // save in order to delete after + replaceNode(p,n); + t.setCurrent(n); + // Delete the old nodes + delete p; + delete z; + } + if(zero) + { + BTreeNode *p = t.current(); + p->deleteChildren(); + p->setChildOp(Expression::noop); + p->setType(number); + p->setValue("0"); + + } + } + else if( t.current()->childOp() == Expression::bwand || t.current()->childOp() == Expression::bwor || t.current()->childOp() == Expression::bwxor ) + { + bool zero = false; + if( l->value() == "0" ) + { + zero = true; + n = r; + z = l; + } + else if( r->value() == "0" ) + { + zero = true; + n = l; + z = r; + } + // Now get rid of the useless nodes + if(zero) + { + BTreeNode *p = t.current(); + QString value; + if( p->childOp() == Expression::bwand ) + { + value = "0"; + p->deleteChildren(); + p->setChildOp(Expression::noop); + p->setType(number); + } + if( p->childOp() == Expression::bwor || p->childOp() == Expression::bwxor ) + { + value = n->value(); + BTreeNode *p = t.current(); // save in order to delete after + replaceNode(p,n); + t.setCurrent(n); + // Delete the old nodes + delete p; + delete z; + } + p->setValue(value); + } + } + + if(!t.current()->parent() || t.current() == root) done = true; + else + { + + } + } +} + +void BTreeBase::replaceNode(BTreeNode *node, BTreeNode *replacement) +{ + // (This works under the assumption that a node is not linked to two places at once). + if( !node->parent() ) + { + setRoot(replacement); + replacement->setParent(0L); + return; + } + if( node->parent()->left() == node ) node->parent()->setLeft(replacement); + if( node->parent()->right() == node ) node->parent()->setRight(replacement); +} |