btreebase.cpp

/***************************************************************************
 *   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.,                                       *
 *   59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.             *
 ***************************************************************************/

#include "btreebase.h"
#include "traverser.h"
#include "parser.h"
#include "pic14.h"

BTreeBase::BTreeBase()
{
        m_root = 0;
}

void BTreeBase::deleteTree()
{
        if(m_root) m_root->deleteChildren();
        delete m_root;
        m_root = 0;
}

BTreeBase::~BTreeBase()
{
        deleteTree();
}

void BTreeBase::addNode(BTreeNode *parent, BTreeNode *node, bool left)
{
        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() && 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)
        {
                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;
                        z = 0;
                }
        }
        // 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;
                        z = 0;
                }

                if(zero) {
                        BTreeNode *p = t.current();
                        p->deleteChildren();
                        p->setChildOp(Expression::noop);
                        p->setType(number);
                        p->setValue("0");
                }

// FIXME: A btree should not have only minimial knowledge of what it contains.
// I think there is a C++ STL class for trees, why aren't we using that? 

        } 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;
                                z = 0;
                        }
                        p->setValue(value);
                }
        }

        if(!t.current()->parent() || t.current() == root) done = true;

        }
}

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(0);
                return;
        }

        if(node->parent()->left() == node ) node->parent()->setLeft(replacement);
        if(node->parent()->right() == node) node->parent()->setRight(replacement);
}

---