sum.cc

Go to the documentation of this file.

//
//  Copyright (c) 2006 by Rafael Ostertag
//
//  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.
//
//
// $Id: sum.cc,v 1.18 2006/12/31 00:49:39 rafi Exp $
//

#include <iostream>
#include <iterator>
#include <vector>

#ifdef DEBUG
#include <cassert>
#endif

#include "casfuncobj.h"
#include "casexception.h"
#include "castemplates.h"
#include "sum.h"
#include "product.h"
#include "fraction.h"
#include "longint.h"

// Private methods
// ----------------------------------------------------------------------------
CASObject*
Sum::CollectEqualOperands() const {
    Sum *working_obj = dynamic_cast<Sum*> ( Clone() );

    bool exprmodified;
    do {
        exprmodified = false;
        resolve_parentheses<Sum> ( working_obj );
        working_obj->Sort();
#ifdef DEBUG
        assert ( working_obj != 0 );
#endif
        std::vector<CASObject*>::const_iterator op_it = working_obj->operands.begin();
        std::vector<CASObject*>::const_iterator op_begin = op_it;
        std::vector<CASObject*>::const_iterator op_it_next = op_it;
        // Get the iterator for the next object
        op_it_next++;
        std::vector<CASObject*>::const_iterator op_end = working_obj->operands.end();

        // Holds the equal objects
        std::vector<CASObject*> equal_objs;

        // Temporary vector, which is later appended to the existing one
        std::vector<CASObject*> new_operands;
        while ( op_it != op_end && op_it_next != op_end ) {
            while ( op_it != op_end &&
                    op_it_next != op_end &&
                    ( *op_it )->IsEqual ( *op_it_next ) ) {
                equal_objs.push_back ( *op_it );
                equal_objs.push_back ( *op_it_next );

                op_it++;
                op_it_next++;
            }

            // Now replace the found objects, if any
            if ( equal_objs.size() > 0 ) {
                exprmodified = true;

                // The above method for searching same operands yields duplicate results
                // thus we have to unique'ing the equal_obj vector.
                // CASGarbageSort_Cmp() is used because it sorts by memory address
                std::sort ( equal_objs.begin(), equal_objs.end(), CASGarbageSort_Cmp() );

                std::vector<CASObject*>::iterator ip =
                    std::unique ( equal_objs.begin(), equal_objs.end() );

                equal_objs.erase ( ip, equal_objs.end() );

                LongInt coefficient ( equal_objs.size() );
                coefficient.meta.SetCoefficient();
                CASObject *product = coefficient.Multiply ( ( equal_objs.front() ) );

                new_operands.push_back ( product );

                // Now, destroy the equal operands, and zero 'em out
                std::vector<CASObject*>::const_iterator eqo_it = equal_objs.begin();
                while ( eqo_it != equal_objs.end() ) {
                    // find the operand in the operand vector, so we can set it to
                    // zero
                    CASObjectFindByAddr needle ( *eqo_it );
                    std::vector<CASObject*>::iterator pos =
                        std::find_if ( working_obj->operands.begin(),
                                       working_obj->operands.end(),
                                       needle );
#ifdef DEBUG
                    assert ( pos != op_end );
                    assert ( *pos != 0 );
#endif
                    *pos = 0;
                    CASObject::Garbage->Put ( *eqo_it );
                    eqo_it++;
                }
                // Finally, clear the list for the next iteration
                equal_objs.clear();
            } else {
                exprmodified = false;
            }

            op_it++;
            op_it_next++;
        }

        if ( new_operands.size() > 0 ) {
            // Remove the elements zero'ed out above and shrink
            // the vector.
            std::vector<CASObject*>::iterator last =
                std::remove ( working_obj->operands.begin(),
                                  working_obj->operands.end(),
                                  ( ( CASObject* ) 0 ) );
            working_obj->operands.erase ( last, working_obj->operands.end() );

            std::copy ( new_operands.begin(),
                        new_operands.end(),
                        std::back_inserter ( working_obj->operands ) );
            working_obj->meta.UnsetSorted();
            working_obj->Sort();
        }
    } while ( exprmodified );

    return working_obj;
}

CASObject* Sum::CollectSingleValues() const {
    std::vector<const CASObject*> this_singleval;
    std::vector<const CASObject*> this_nonsingleval;
    GetSingleValues ( this_singleval );
    GetNonSingleValues ( this_nonsingleval );

    std::vector<CASObject*> working_singleval;
    std::vector<CASObject*> working_nonsingleval;

    // Necessary because Get(Non)SingleValues() return vectors holding the
    // pointers to the operands of this object.
    std::transform ( this_singleval.begin(),
                     this_singleval.end(),
                     std::back_inserter ( working_singleval ),
                     CASCloneObject() );

    std::transform ( this_nonsingleval.begin(),
                     this_nonsingleval.end(),
                     std::back_inserter ( working_nonsingleval ),
                     CASCloneObject() );

    // Try to assign the single values to other objects, e.g. collect them.
    std::vector<CASObject *>::iterator singleval_it = working_singleval.begin();
    while ( singleval_it != working_singleval.end() ) {
        std::vector<CASObject*>::iterator nonsingleval_it =
            working_nonsingleval.begin();
        while ( nonsingleval_it != working_nonsingleval.end() ) {
            CASTerm *term = dynamic_cast<CASTerm*> ( ( *nonsingleval_it ) );
            if ( term != 0 ) {
                if ( term->IsSimilar ( ( *singleval_it ) ) ) {
                    CASObject *result = term->Add ( ( *singleval_it ) );
                    CASObject::Garbage->Put ( term );
                    ( *nonsingleval_it ) = result;
                    CASObject::Garbage->Put ( ( *singleval_it ) );
                    // Clear this out
                    ( *singleval_it ) = 0;
                    break;
                }
            }
            nonsingleval_it++;
        }
        singleval_it++;
    }

    // From here on compose the Sum
    Sum *Collected_Sum = new Sum;
#ifdef DEBUG
    assert ( Collected_Sum->exponent != 0 );
#endif
    CASObject::Garbage->Put ( Collected_Sum->exponent );
    Collected_Sum->exponent = exponent->Clone();

    std::vector<CASObject*>::iterator last =
        std::remove ( working_singleval.begin(),
                          working_singleval.end(),
                          ( CASObject* ) 0 );

    working_singleval.erase ( last, working_singleval.end() );

    std::copy ( working_singleval.begin(),
                working_singleval.end(),
                std::back_inserter ( Collected_Sum->operands ) );

    std::copy ( working_nonsingleval.begin(),
                working_nonsingleval.end(),
                std::back_inserter ( Collected_Sum->operands ) );

    Collected_Sum->meta.UnsetSorted();
    Collected_Sum->Sort();

    return Collected_Sum;
}

CASObject* Sum::CollectNonSingleValues() const {
    std::vector<const CASObject*> this_singleval;
    std::vector<const CASObject*> this_nonsingleval;

    // We get both, becaus we need to concatenate them later on, but we barely
    // touch the single values
    GetSingleValues ( this_singleval );
    GetNonSingleValues ( this_nonsingleval );

    std::vector<CASObject*> working_singleval;
    std::vector<CASObject*> working_nonsingleval;

    // Necessary because Get(Non)SingleValues() return vectors holding the
    // pointers to the operands of this object.
    std::transform ( this_singleval.begin(),
                     this_singleval.end(),
                     std::back_inserter ( working_singleval ),
                     CASCloneObject() );

    std::transform ( this_nonsingleval.begin(),
                     this_nonsingleval.end(),
                     std::back_inserter ( working_nonsingleval ),
                     CASCloneObject() );

    std::vector<CASObject*>::iterator it = working_nonsingleval.begin();
    std::vector<CASObject*>::iterator secondary_it;
    while ( it != working_nonsingleval.end() ) {
        secondary_it = it;
        secondary_it++;

        CASTerm *term_a = dynamic_cast<CASTerm*> ( *it );
        while ( secondary_it != working_nonsingleval.end() &&  term_a != 0 ) {
            CASTerm *term_b = dynamic_cast<CASTerm*> ( *secondary_it );
            if ( term_b == 0 ) {
                break;
            }

            if ( term_a->IsSimilar ( term_b ) ) {
                CASObject *result = term_a->Add ( term_b );
                CASObject::Garbage->Put ( *it );
                *it = 0;
                CASObject::Garbage->Put ( *secondary_it );
                *secondary_it = result;
                break;
            }
            secondary_it++;
        }

        it++;
    }

    // From here on compose the Sum
    Sum *Collected_Sum = new Sum;
#ifdef DEBUG
    assert ( Collected_Sum->exponent != 0 );
#endif
    CASObject::Garbage->Put ( Collected_Sum->exponent );
    Collected_Sum->exponent = exponent->Clone();

    std::vector<CASObject*>::iterator last =
        std::remove ( working_nonsingleval.begin(),
                          working_nonsingleval.end(),
                          ( CASObject* ) 0 );

    working_nonsingleval.erase ( last, working_nonsingleval.end() );

    std::copy ( working_singleval.begin(),
                working_singleval.end(),
                std::back_inserter ( Collected_Sum->operands ) );

    std::copy ( working_nonsingleval.begin(),
                working_nonsingleval.end(),
                std::back_inserter ( Collected_Sum->operands ) );
    Collected_Sum->meta.UnsetSorted();
    Collected_Sum->Sort();

    return Collected_Sum;
}

Sum*
Sum::WithExponentOne() const {
    Sum *res = dynamic_cast<Sum*> ( Clone() );
#ifdef DEBUG
    assert ( res != 0 );
    assert ( res->exponent != 0 );
#endif
    CASObject::Garbage->Put ( res->exponent );
    LongInt one ( 1 );
    res->exponent = one.Clone();
    return res;
}

// ----------------------------------------------------------------------------


// Protected methods
// ----------------------------------------------------------------------------
// ----------------------------------------------------------------------------


// Constructors & Destructor
// ----------------------------------------------------------------------------
Sum::Sum() : CASTerm() {
#ifdef SHOWCONSTRUCTOR
    std::cout << "# Sum::Sum()" << std::endl;
#endif
    LongInt one ( 1L );
    exponent = one.Clone();
}

Sum::Sum ( const Sum &s ) {
#ifdef SHOWCONSTRUCTOR
    std::cout << "# Sum::Sum(const Sum &f)" << std::endl;
#endif
    std::transform ( s.operands.begin(),
                     s.operands.end(),
                     std::back_inserter ( operands ),
                     CASCloneObject() );

    meta = s.meta;
    exponent = s.exponent->Clone();
}

Sum::~Sum() {
#ifdef SHOWCONSTRUCTOR
    std::cout << "# Sum::~Sum()" << std::endl;
#endif
#ifdef DEBUG
    assert ( exponent != 0 );
#endif
    delete exponent;
}

// ----------------------------------------------------------------------------


// Public Methods
// ----------------------------------------------------------------------------
CASObject*
Sum::Clone() const {
    Sum *tmp = new Sum;
    *tmp = *this;
    return tmp;
}

void
Sum::Get ( std::string &s ) const {
    s.erase();
    std::string tmp;

#ifdef DEBUG
    s = "{";
#endif

    if ( !exponent->IsOne() ) {
#ifdef DEBUG
        s += "(";
#else
        s = "(";
#endif
    }

    for ( unsigned long i = 0; i < operands.size(); i++ ) {
#ifdef DEBUG
        assert ( operands[i] != 0 );
#endif
        if ( i > 0 ) {
            s += "+";
        }
        operands[i]->Get ( tmp );
        s += tmp;
    }

    if ( !exponent->IsOne() ) {
        exponent->Get ( tmp );
        if ( !exponent->meta.IsSingleValue() ) {
            s += ")^(" + tmp + ")";
        } else {
            s += ")^" + tmp;
        }
    }

#ifdef DEBUG
    s += "}";
#endif
}

void
Sum::Get ( char *s, unsigned long size ) const {
    checkptr ( s );

    if ( size < ( Length() + 1 ) ) {
        throw EBufTooSmall();
    }

    memset ( s, '\0', size );

    std::string tmp;
    Get ( tmp );

    strncpy ( s, tmp.c_str(), size );
}

void
Sum::Print() const {
    std::string tmp;
    Get ( tmp );
    std::cout << tmp;
}

unsigned long
Sum::Length() const {
    unsigned long len = 0;

    for ( unsigned long i = 0; i < operands.size(); i++ ) {
#ifdef DEBUG
        assert ( operands[i] != 0 );
#endif
        len += operands[i]->Length();
    }

    // Add the size of the operators '+'
    len += operands.size() - 1;

    return len;
}

bool
Sum::IsZero() const {
    if ( operands.size() == 0 )
        return true;

    for ( unsigned long i = 0; i < operands.size(); i++ ) {
#ifdef DEBUG
        assert ( operands[i] != 0 );
#endif
        if ( !operands[i]->IsZero() ) {
            return false;
        }
    }

    return true;
}

bool
Sum::IsOne() const {
#ifdef WARNINGS
#warning "Not fully Implemented: bool Sum::IsOne() const"
#endif
    return false;
}

bool
Sum::IsSimilar ( const CASObject *o ) const {
    checkptr ( o );

    if ( IsEqual ( o ) ) {
        return true;
    }

    return HaveSameOperands ( o );
}

CASObject*
Sum::Absolute() const {
    Sum *tmp = new Sum;
    *tmp = *this;

    std::for_each ( tmp->operands.begin(),
                    tmp->operands.end(),
                    CASAbsoluteObjectIP() );

    return tmp;
}

void
Sum::AbsoluteIP() {
    std::for_each ( operands.begin(), operands.end(), CASAbsoluteObjectIP() );
    meta.UnsetAll();
}

CASObject*
Sum::Invert() const {
    Sum *tmp = new Sum;
    *tmp = *this;

    std::for_each ( tmp->operands.begin(),
                    tmp->operands.end(),
                    CASInvertObjectIP() );

    return tmp;
}

void
Sum::InvertIP() {
    std::for_each ( operands.begin(), operands.end(), CASInvertObjectIP() );
    meta.UnsetAll();
}

CASObject*
Sum::Add ( const CASObject* addend ) const {
    checkptr ( addend );

    if ( addend->GetType() == GetType() ) {
        // We have to add two sums, so, if they are equal, we form a
        // product with the coefficient '2', else we simply put them
        // together in a new sum.
        const Sum *addend_sum = dynamic_cast<const Sum*> ( addend );
#ifdef DEBUG
        assert ( addend_sum != 0 );
#endif
        if ( IsEqual ( addend_sum ) ) {
            Product *result = new Product;
            LongInt two ( 2L );
            result->Append ( &two );
            result->Append ( this );
            result->Sort();
            return result;
        }

        // Default return result
        Sum *result = new Sum;
        result->Append ( addend_sum );
        result->Append ( this );
        result->Sort();
        return result;

    } else {
        // Since we are here, we do not deal with a sum as
        // addend. Therefore, we first have to make sure the exponent
        // is one ('1'). If the exponent is not one, we simply put
        // them together in a new sum.  If the exponent is one, we
        // seek for an operand of the same type as the addend, and, if
        // one exists, we add them and replace the original item in
        // this->operands with the result.
        Sum *new_sum = new Sum;
        *new_sum = *this;
        if ( exponent->IsOne() ) {
            // Is there already an item of that type?
            std::vector<CASObject*>::iterator si = find_if ( new_sum->operands.begin(),
                                                   new_sum->operands.end(),
                                                   CASTypeFinder_EQ ( addend ) );

            if ( si != new_sum->operands.end() ) {
                // Compute the sum
                CASObject *result = ( *si )->Add ( addend );
                // Free the memory occupied by the existing item
                CASObject::Garbage->Put ( *si );
                // Remove the item from the vector
                new_sum->operands.erase ( si );
                // Add the result
                new_sum->operands.push_back ( result );
                new_sum->Sort();
                return new_sum;
            }
        }
        new_sum->Append ( addend );
        new_sum->Sort();
        return new_sum;
    }

    return 0L;
}

CASObject*
Sum::Subtract ( const CASObject* subtrahend ) const {
    checkptr ( subtrahend );

    Sum *NewSum = new Sum;
    *NewSum = *this;

    if ( subtrahend->GetType() == GetType() ) {
        const Sum *subtrahend_sum = dynamic_cast<const Sum*> ( subtrahend );
#ifdef DEBUG
        assert ( subtrahend_sum != 0 );
#endif
        std::transform ( subtrahend_sum->operands.begin(),
                         subtrahend_sum->operands.end(),
                         std::back_inserter ( NewSum->operands ),
                         CASInvertObject() );
    } else {
        // Is there already an item of that type?
        std::vector<CASObject*>::iterator si =
            find_if ( NewSum->operands.begin(),
                      NewSum->operands.end(),
                      CASTypeFinder_EQ ( subtrahend ) );

        if ( si != NewSum->operands.end() ) {
            // Compute the difference
            CASObject *result = ( *si )->Subtract ( subtrahend );
            // Free the memory occupied by the existing item
            CASObject::Garbage->Put ( *si );
            // Remove the item from the vector
            NewSum->operands.erase ( si );
            // Add the result
            NewSum->operands.push_back ( result );
        } else {
            NewSum->operands.push_back ( subtrahend->Invert() );
        }
    }

    NewSum->Sort();
    return NewSum;
}

CASObject*
Sum::Multiply ( const CASObject* factor ) const {
    checkptr ( factor );

    if ( GetType() == factor->GetType() ) {
        const Sum *sum = dynamic_cast<const Sum*> ( factor );
#ifdef DEBUG
        assert ( sum != 0 );
#endif
        if ( HaveSameOperands ( sum ) ) {
            Sum *result = new Sum;
            *result = *this;
            CASObject::Garbage->Put ( result->exponent );
            result->exponent = exponent->Add ( sum->exponent );
            result->Sort();
            return result;
        }
    }

    Product *result = new Product;
    result->Append ( this );
    result->Append ( factor );
    result->Sort();
    return result;
}

CASObject*
Sum::Divide ( const CASObject* divisor ) const {
    checkptr ( divisor );

    return  new Fraction ( this, divisor );
}

CASObject*
Sum::Modulo ( const CASObject* divisor ) const {
#ifdef WARNINGS
#warning "Not fully implemented: Sum::Modulo(const CASObject* divisor) const"
#endif
    checkptr ( divisor );

    return new LongInt ( 0L );
}

CASObject*
Sum::GCD ( const CASObject* o ) const{
#ifdef WARNINGS
#warning "Not fully implemented: Sum::GCD(const CASObject* o) const"
#endif
    checkptr ( o );

    return new LongInt ( 1L );
}

CASObject*
Sum::Evaluate() const {
    if ( meta.IsEvaluated() ) {
        return Clone();
    }
#ifdef DEBUG2
    std::cout << ">>> Begin evaluation of ";
    Print();
    std::cout << std::endl;
#endif
    Sum* tmp = dynamic_cast<Sum*> ( Clone() );
#ifdef DEBUG
    assert ( tmp != 0 );
#endif
    tmp->UnsetAllEvaluated();
    resolve_parentheses<Sum> ( tmp );
    evaluate_operands<Sum> ( tmp );

    CASObject* result = tmp->Collect();
    CASObject::Garbage->Put ( tmp );

    result->meta.SetEvaluated();
    CASTerm *term = dynamic_cast<CASTerm*> ( result );
    if ( term != 0 ) {
        term->RemoveNoOpElements();
        if ( term->IsZero() ) {
            CASObject::Garbage->Put ( result );
            LongInt r ( 0L );
            return r.Clone();
        }
        term->SetAllEvaluated();
    }

    if ( result->IsOne() ) {
        CASObject::Garbage->Put ( result );
        LongInt r ( 1L );
        return r.Clone();
    }

    if ( result->IsZero() ) {
        CASObject::Garbage->Put ( result );
        LongInt r ( 0L );
        return r.Clone();
    }

#ifdef DEBUG2
    std::cout << ">>> End evaluation of ";
    Print();
    std::cout << std::endl;
#endif

    return result;
}

CASObject *
Sum::Collect() const {
    Sum *sum = dynamic_cast<Sum*> ( Clone() );
    CASObject* tmp = sum->CollectEqualOperands();
#ifdef DEBUG
    checkptr ( tmp );
#endif
    CASObject::Garbage->Put ( sum );

    sum = dynamic_cast<Sum*> ( tmp );
    // By collecting, it has become another type
    if ( sum == 0 ) {
        return tmp;
    }

#ifdef DEBUG2
    std::cout << "Going to collect Single Values in " << std::endl;
    sum->Print();
    std::cout << std::endl;
#endif
    tmp = sum->CollectSingleValues();
    CASObject::Garbage->Put ( sum );

    sum = dynamic_cast<Sum*> ( tmp );
    // By collecting, it has become another type
    if ( sum == 0 ) {
        return tmp;
    }

    CASObject *result = sum->CollectNonSingleValues();
    CASObject::Garbage->Put ( tmp );

    return result;
}

CASObject*
Sum::Expand() const {
    if ( !meta.IsEvaluated() ) {
        throw EEvaluateFirst();
    }

    CASObject *clone = Clone();

    Sum* wrking = dynamic_cast<Sum*> ( clone );
#ifdef DEBUG
    assert ( wrking != 0 );
#endif

    if ( wrking->exponent->GetType() == CT_LONGINT &&
            !wrking->exponent->IsOne() ) {
        LongInt const *li_exp = dynamic_cast<LongInt*> ( wrking->exponent );
        Sum *wo_exponent = wrking->WithExponentOne();
        // We assume that it is evaluated, because *this object is.
        wo_exponent->meta.SetEvaluated();

        resolve_parentheses<Sum> ( wo_exponent );
        Product* prod = new Product;
#ifdef DEBUG
        assert ( prod->NumOperands() == 0 );
#endif
        for ( LongInt i ( 0L );i < ( *li_exp );i++ ) {
            prod->Append ( wo_exponent );
        }

        CASObject::Garbage->Put ( wo_exponent );
        CASObject::Garbage->Put ( wrking );

        resolve_parentheses<Product> ( prod );

        // Same as obove, assuming it is evaluated...
        // btw. leave it here, because Product::Append()
        // and resolve_parentheses() change that flag.
        prod->meta.SetEvaluated();

        CASObject* res = prod->Expand();

        CASObject::Garbage->Put ( prod );
        return res;
    } else {
        return clone;
    }
}

void
Sum::RemoveNoOpElements() {
    std::vector<CASObject*>::iterator it = operands.begin();
    while ( it != operands.end() ) {
        if ( ( *it )->IsZero() ) {
            CASObject::Garbage->Put ( *it );
            it = operands.erase ( it );
        } else {
            CASTerm *term = dynamic_cast<CASTerm*> ( *it );
            if ( term != 0 ) {
                term->RemoveNoOpElements();
            }
            it++;
        }
        // Iterator already incremented... no need for it++
    }
}

// ----------------------------------------------------------------------------

// Operators
// ----------------------------------------------------------------------------
const Sum&
Sum::operator= ( const Sum &s ) {
#ifdef SHOWCONSTRUCTOR
    std::cout << "# Sum::operator=(const Sum &s)" << std::endl;
#endif
    if ( &s == this ) {
        return *this;
    }

    CASObject::Garbage->Put ( operands );

    operands.clear();

    std::transform ( s.operands.begin(),
                     s.operands.end(),
                     std::back_inserter ( operands ),
                     CASCloneObject() );

    meta = s.meta;
    CASObject::Garbage->Put ( exponent );
    exponent = s.exponent->Clone();

    return *this;
}

// ----------------------------------------------------------------------------

---