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

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 "btreebase.h"
0022 #include "traverser.h"
0023 #include "parser.h"
0024 #include "pic14.h"
0025 
0026 BTreeBase::BTreeBase()
0027 {
0028     m_root = nullptr;
0029 }
0030 
0031 void BTreeBase::deleteTree()
0032 {
0033     if(m_root) m_root->deleteChildren();
0034     delete m_root;
0035     m_root = nullptr;
0036 }
0037 
0038 BTreeBase::~BTreeBase()
0039 {
0040     deleteTree();
0041 }
0042  
0043 
0044 void BTreeBase::addNode(BTreeNode *parent, BTreeNode *node, bool left)
0045 {
0046     // Debugging lines, remove when expression parsing has been completed.
0047     //if(!parent) cerr<<"Null parent pointer!\n";
0048     //if(!node) cerr<<"Null node pointer!\n");
0049     
0050     if(left) parent->setLeft(node);
0051     else parent->setRight(node);
0052 }
0053 
0054 void BTreeBase::pruneTree(BTreeNode *root, bool /*conditionalRoot*/)
0055 {
0056     Traverser t(root);
0057     
0058     t.descendLeftwardToTerminal();
0059     bool done = false;
0060     while(!done)
0061     {
0062     //t.descendLeftwardToTerminal();
0063     if( t.current()->parent() )
0064     {
0065         if( t.oppositeNode()->hasChildren() ) pruneTree(t.oppositeNode());
0066     }
0067     
0068     t.moveToParent();
0069     if( !t.current()->hasChildren() )
0070     {
0071         //if(t.current() == t.root()) done = true;
0072         if(!t.current()->parent()) done = true;
0073         continue;
0074     }
0075 
0076     BTreeNode *l = t.current()->left();
0077     BTreeNode *r = t.current()->right();
0078     BTreeNode *n = nullptr;
0079     BTreeNode *z = nullptr;
0080     
0081 
0082     // Deal with situations where there are two constants so we want
0083     // to evaluate at compile time
0084     if( (l->type() == number && r->type() == number) ) // && !(t.current()==root&&conditionalRoot) )
0085     {
0086         if(t.current()->childOp() == Expression::division && r->value() == "0" ) 
0087         {
0088             t.current()->setChildOp(Expression::divbyzero);
0089             return;
0090         }
0091         QString value = QString::number(Parser::doArithmetic(l->value().toInt(),r->value().toInt(),t.current()->childOp()));
0092         t.current()->deleteChildren();
0093         t.current()->setChildOp(Expression::noop);
0094         t.current()->setType(number);
0095         t.current()->setValue(value);
0096     }
0097     
0098     // Addition and subtraction
0099     else if(t.current()->childOp() == Expression::addition || t.current()->childOp() == Expression::subtraction)
0100     {
0101     // See if one of the nodes is 0, and set n to the node that actually has data,
0102     // z to the one containing zero.
0103     bool zero = false;
0104     if( l->value() == "0" )
0105     {
0106         zero = true;
0107         n = r;
0108         z = l;
0109     }
0110     else if( r->value() == "0" )
0111     {
0112         zero = true;
0113         n = l;
0114         z = r;
0115     }
0116     // Now get rid of the useless nodes
0117     if(zero)
0118     {
0119         BTreeNode *p = t.current(); // save in order to delete after
0120 
0121         replaceNode(p,n);
0122         t.setCurrent(n);
0123         // Delete the old nodes
0124         delete p;
0125         delete z;
0126     }
0127     }
0128     
0129     // Multiplication and division
0130     else if(t.current()->childOp() == Expression::multiplication || t.current()->childOp() == Expression::division)
0131     {
0132     // See if one of the nodes is 0, and set n to the node that actually has data,
0133     // z to the one containing zero.
0134     bool zero = false;
0135     bool one = false;
0136     if( l->value() == "1" )
0137     {
0138         one = true;
0139         n = r;
0140         z = l;
0141     }
0142     else if( r->value() == "1" )
0143     {
0144         one = true;
0145         n = l;
0146         z = r;
0147     }
0148     if( l->value() == "0" )
0149     {
0150         zero = true;
0151         n = r;
0152         z = l;
0153     }
0154     else if( r->value() == "0" )
0155     {
0156         
0157         // since we can't call compileError from in this class, we have a special way of handling it:
0158         // Leave the children as they are, and set childOp to divbyzero
0159         if( t.current()->childOp() == Expression::division )
0160         {
0161             t.current()->setChildOp(Expression::divbyzero);
0162             return; // no point doing any more since we are going to raise a compileError later anyway.
0163         }
0164         zero = true;
0165         n = l;
0166         z = r;
0167     }
0168     // Now get rid of the useless nodes
0169     if(one)
0170     {
0171         BTreeNode *p = t.current(); // save in order to delete after
0172         replaceNode(p,n);
0173         t.setCurrent(n);
0174         // Delete the old nodes
0175         delete p;
0176         delete z;
0177     }
0178     if(zero)
0179     {
0180         BTreeNode *p = t.current();
0181         p->deleteChildren();
0182         p->setChildOp(Expression::noop);
0183         p->setType(number);
0184         p->setValue("0");
0185         
0186     }
0187     }
0188     else if( t.current()->childOp() == Expression::bwand || t.current()->childOp() == Expression::bwor || t.current()->childOp() == Expression::bwxor )
0189     {
0190     bool zero = false;
0191     if( l->value() == "0" )
0192     {
0193         zero = true;
0194         n = r;
0195         z = l;
0196     }
0197     else if( r->value() == "0" )
0198     {
0199         zero = true;
0200         n = l;
0201         z = r;
0202     }
0203     // Now get rid of the useless nodes
0204     if(zero)
0205     {
0206         BTreeNode *p = t.current();
0207         QString value;
0208         if( p->childOp() == Expression::bwand )
0209         {
0210             value = "0";
0211             p->deleteChildren();
0212             p->setChildOp(Expression::noop);
0213             p->setType(number);
0214         }
0215         if( p->childOp() == Expression::bwor || p->childOp() == Expression::bwxor )
0216         {
0217             value = n->value();
0218             BTreeNode *p = t.current(); // save in order to delete after
0219             replaceNode(p,n);
0220             t.setCurrent(n);
0221             // Delete the old nodes
0222             delete p;
0223             delete z;
0224         }
0225         p->setValue(value);
0226     }
0227     }
0228     
0229     if(!t.current()->parent() || t.current() == root) done = true;
0230     else
0231     {
0232 
0233     }
0234     }
0235 }
0236 
0237 void BTreeBase::replaceNode(BTreeNode *node, BTreeNode *replacement)
0238 {
0239     // (This works under the assumption that a node is not linked to two places at once).
0240     if( !node->parent() )
0241     {
0242         setRoot(replacement);
0243         replacement->setParent(nullptr);
0244         return;
0245     }
0246     if( node->parent()->left() == node ) node->parent()->setLeft(replacement);
0247     if( node->parent()->right() == node ) node->parent()->setRight(replacement);
0248 }