Main page

---

Solver.cpp

Go to the documentation of this file.

// MathCore = a WYSIWYG equation editor + a powerful math engine     //
// Copyright (C) 2003 by Francesco Montorsi                          //
//                                                                   //
// This library is free software; you can redistribute it and/or     //
// modify it under the terms of the GNU Lesser General Public        //
// License as published by the Free Software Foundation; either      //
// version 2.1 of the License, or (at your option) any later         //
// version.                                                          //
//                                                                   //
// This library 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 Lesser General Public License for more details.               //
//                                                                   //
// You should have received a copy of the GNU Lesser 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.                                               //
//                                                                   //
// For any comment, suggestion or feature request, please contact    //
// the administrator of the project at frm@users.sourceforge.net     //
//                                                                   //



// optimization for GCC compiler
#ifdef __GNUG__
#pragma implementation "Solver.h"
#endif

// includes
#include "mc/mcprec.h"
#ifdef __BORLANDC__
    #pragma hdrstop
#endif

#ifndef mcPRECOMP
 #include "mc/Solver.h"
 #include "mc/MathSystem.h"
 #include "mc/MathAndSystem.h"
 #include "mc/MathOrSystem.h"
 #include "mc/Symbol.h"
#endif




// ---------------
// mcSOLVER
// ---------------

void mcSolver::math_ResetUnkArray()
{
 for (int i=0; i < mcSOLVER_MAXLINES; i++)
  m_pUnkArr[i] = NULL;
}

void mcSolver::math_SplitInTwoEquations(const mcPolynomial &lfirsteq, const mcPolynomial &rfirsteq, 
          const mcPolynomial &lseceq, const mcPolynomial &rseceq, 
          mcSystemStepArray &steps, mcLogicOperator conn)
{
 mcMathLine *equ1 = new mcMathLine(lfirsteq, rfirsteq);
 mcMathLine *equ2 = new mcMathLine(lseceq, rseceq);

 // just call the overloaded version
 math_SplitInTwoEquations(equ1, equ2, steps, conn);
}


void mcSolver::math_SplitInTwoEquations(const mcMathLine &equ1, const mcMathLine &equ2,
          mcSystemStepArray &steps, mcLogicOperator conn)
{
 // just call the overloaded version
 math_SplitInTwoEquations(new mcMathLine(equ1), new mcMathLine(equ2), steps, conn);
}

void mcSolver::math_SplitInTwoEquations(mcMathLine *equ1, mcMathLine *equ2,
          mcSystemStepArray &steps, mcLogicOperator conn)
{
 mcMathOrSystem *step = new mcMathOrSystem();
 
 if (conn == mcLO_OR) {
  
  // create two equations connected by a logical OR
  step->data_AddLineToNewAndSystem(equ1);
  step->data_AddLineToNewAndSystem(equ2);
  
 } else {
  
  // create two equations connected by a logical AND
  step->data_AddLineToLastAndSystem(equ1);
  step->data_AddLineToLastAndSystem(equ2);
 }

 // add this step to the steparray
 steps.data_Add(step);
}


/*mcMathMng *mcSolver::math_GetNewStep(const mcMathMng *last)
{
 mcMathMng *newstep = new mcMathMng(*last);

 // update current line pointer...
 //m_pCurrLine = newstep->GetLine(0);

 // and return it
 return newstep;
}

mcMathMng *mcSolver::math_GetNewSmartStep(const mcMathMng *last)
{
 mcRealValue ll = last->math_GetTotalLenght();

 // a negative value of m_fLastLenght means this is the first time
 // this function is used...
 if (m_fLastLenght > 0 &&
  ll-m_fLastLenght < mcMathCore::Get()->GetStepThreshold()) {

  // the required setp should not be created since the complexity
  // of the data is not diminuished enough...
  return (mcMathMng *)last;
 }

 // store this step's lenght
 m_fLastLenght = ll;
 return math_GetNewStep(last);
}
*/
#define mcDEFINE_EXPSIM_STEP(x, y)         \
 void mcSolver::x(long flags, long rflags, mcMathLine &tosimp, \
       mcSystemStepArray &steps,    \
                 mcExpSimRes *result) {     \
  /* simplify & (eventually) store simplification result */ \
  mcExpSimRes res = tosimp.y(flags, rflags);     \
  if (result) *result = res;         \
  steps.data_AddLine(tosimp);         \
 }

#define mcDEFINE_EXPSIM_COMPLETE(x, y)        \
 void mcSolver::x(long flags, long rflags,       \
     mcMathLine &last, mcSystemStepArray &steps) { \
  mcExpSimRes res;           \
  int cycles = 0;            \
                 \
  /* do first simplification step */       \
  y(flags, rflags, last, steps, &res);      \
  mcSOLVERLOG(wxT("mcSolver::") wxT(#x)      \
    wxT(" - completed 0-th step [%s]"), mcTXT(last)); \
  cycles++;             \
                 \
  /* add steps until the process is complete;         */  \
  /* the mcELEMENTMATH_MAX_PROCESS_CYCLES limit is    */  \
  /* used to avoid to get trapped in an infinite loop */  \
  while (res != mcESR_DONE &&         \
    cycles < mcELEMENTMATH_MAX_PROCESS_CYCLES) {   \
                  \
   /* do another step */         \
   y(flags, rflags, last, steps, &res);     \
   mcSOLVERLOG(wxT("mcSolver::") wxT(#x)     \
     wxT(" - completed %d-th step [%s]"),   \
        cycles, mcTXT(last));    \
   cycles++;            \
  }               \
 }

mcDEFINE_EXPSIM_STEP(math_DoSimplifyStep, math_Simplify)
mcDEFINE_EXPSIM_STEP(math_DoExpandStep, math_Expand)
mcDEFINE_EXPSIM_COMPLETE(math_DoCompleteSimplification, math_DoSimplifyStep)
mcDEFINE_EXPSIM_COMPLETE(math_DoCompleteExpansion, math_DoExpandStep)
/*
mcSymbolProperties *mcSolver::math_GetUnknown(const mcMathOrSystem *sys, int n) const
{
 mcSymbol sym;

 // cycle through registered unknowns and find the first
 // contained in this line...
 mcSymbolProperties *unk = NULL;
/* for (int i=0; i < mcSymbol::arrUnknowns.data_GetCount(); i++) {
  unk = mcSymbol::arrUnknowns.GetSymbol(i);
  sym.hlp()->data_LinkWith(unk);

  if (m_pCurrLine->math_Find(0, sym, FALSE) != mcEmptyElement) {

   if (n == 0)
    break;  // this is the unknown we're searching
   n--;  // try with next
  }

  unk = NULL;  // reset the pointer
 }
*
 return unk;
}*/

void mcSolver::data_Check() const
{
 // name is like a unique identification string
 mcASSERT(!m_strName.IsEmpty(), wxT("Invalid name"));
}

bool mcSolver::math_PreSolve(const mcMathOrSystem &p, mcSystemStepArray &steps)
{
 // make a first step identic to the given system
 steps.data_AddSys(new mcMathOrSystem(p));

 // decide the unknowns to use to solve each line
 for (int i=0; i < p.data_GetCount(); i++) {
  for (int k=0; k < p.data_GetSys(i).data_GetCount(); k++) {
   
   const mcMathLine &line = p.data_GetSys(i).data_GetLine(k);
   
   // scan the array of unknowns searching a valid one
   for (int j=0; j < mcSymbol::arrUnknowns.data_GetCount(); j++) {
    
    const mcSymbolProperties *sym = mcSymbol::arrUnknowns.data_GetSymbol(j);
    if (line.math_ContainsSymbol(sym)) {
     
     // we've found what we're searching for...
     m_pUnkArr[i] = sym;

     // and check again, it can be solved for *this* unknown
     if (math_WorksOn(p, sym))
      break;
    }
   }
   
   if (m_pUnkArr[i] == NULL) {
    
    // we did not find any unknown...
    m_strLastErr = wxString::Format(wxT("The %d-th line [%s] does not contain")
     wxT("any unknown... cannot proceed"), i, mcTXT(line));
    return FALSE;
   }
   
   mcMATHLOG(wxT("mcSolver::PreSolve - line %d will be solved for [%s]"), 
    i, mcTXTP(m_pUnkArr[i]));
  }
 }

 return TRUE;
}

bool mcSolver::math_PostSolve(const mcMathOrSystem &p, mcSystemStepArray &steps)
{
 mcMATHLOG(wxT("mcSolver::math_PostSolve - the step array is [%s]"), mcTXT(steps));

 // remove identic steps
 int removed = steps.math_RemoveIdenticSteps();
 //removed += steps.data_RemoveSimpleSteps();
#ifdef __MCDEBUG__
 mcMATHLOG(wxT("mcSolver::math_PostSolve - Removed %d useless steps."), removed);
#else
 mcUNUSED(removed);
#endif

 return TRUE;
}

bool mcSolver::math_Solve(const mcMathOrSystem &p, mcSystemStepArray &steps)
{
 // Solve() will return FALSE only on errors or problems with the
 // given system (which is user-dependent); programming errors
 // will be catched instead with ASSERTs: call the Solve() function
 // before setting all the options of this solver is a programming error
 mcASSERT(math_isReady(), wxT("Cannot work yet"));
 mcASSERT(math_WorksOn(p), wxT("Invalid data for this type of solver"));
 mcMATHLOG(wxT("mcSolver::math_Solve - this solver is ready to work"));

 // ...while trying to solve a constant data is not
 if (p.math_isConstant()) {
  m_strLastErr = wxT("The entire expression is constant; nothing to solve");
  return FALSE;
 }

 if (!p.math_isValidMath()) {
  m_strLastErr = wxT("The expression contains invalid data");
  return FALSE;
 }


 // do any preparatory step...
 if (!math_PreSolve(p, steps))
  return FALSE;

 // do solve each line 
 mcMATHLOG(wxT("mcSolver::math_Solve - the step array has %d steps"), steps.data_GetCount()); 
 for (int i=0; i < p.data_GetCount(); i++) {
  for (int j=0; j < p.data_GetSys(i).data_GetCount(); j++) {
   
   mcMathLine tosolve(p.data_GetSys(i).data_GetLine(j));
   if (!math_SolveLine(tosolve, m_pUnkArr[i], steps))
    return FALSE;
  
   // remove simple steps
   steps.math_RemoveSimpleSteps();
   steps.data_Check();

   mcMATHLOG(wxT("mcSolver::math_Solve - the step array for the resolution ")
     wxT("of the %d-th line contains [%d] steps:\n%s"), i*j, 
     steps.data_GetCount(), mcTXT(steps));
  }
 }

 // and make last operations...
 return math_PostSolve(p, steps);
}





// ---------------
// mcSOLVERARRAY
// ---------------

bool mcSolverArray::math_Add(mcSolver *solver)
{
 if (math_Contains(solver))
  return FALSE;  // don't make duplicates

 // ok; we can add it
 mcAbstractArray::data_Add(solver);
 return TRUE;
}

wxArrayString mcSolverArray::io_GetDescArray() const
{
 wxArrayString arr;
 for (int i=0; i < (int)data_GetCount(); i++)
  arr.Add(data_Get(i)->math_GetDesc());
 return arr;
}

void mcSolverArray::data_Check() const
{
 mcAbstractArray::data_Check();
 for (int i=0; i < data_GetCount(); i++)
  data_Get(i)->data_Check();
}

bool mcSolverArray::math_Contains(const mcSolver *p) const
{
 for (int i=0; i < data_GetCount(); i++)
  if (data_Get(i)->math_GetName() == p->math_GetName())
   return TRUE;
 return FALSE;
}





// --------------------
// mcSYSTEMSTEPARRAY
// --------------------
/*
void mcSystemStepArray::data_AddLine(const mcMathLine &p)
{
 // create a new mcMathOrSystem() and add to it the given line
 mcMathOrSystem *s=new mcMathOrSystem();
 s->data_AddLineToLastAndSystem(new mcMathLine(p));

 // then, add the system to this array
 data_Add(s);
}
*/
void mcSystemStepArray::data_AddLine(const mcMathLine &p)
{
 // see m_nFlags for more info
 if (m_nFlags & mcSYSTEMSTEPARR_DISCARD_SIMPLE) {
  data_AddLineOnlyIfComplexEnough(p);
  return;
 }

 mcMathOrSystem *s=new mcMathOrSystem();
 s->data_AddLineToLastAndSystem(new mcMathLine(p));

 // then, add the system to this array
 data_Add(s);
}

void mcSystemStepArray::data_AddKeyLine(const mcMathLine &p)
{
 mcMathOrSystem *s=new mcMathOrSystem();
 s->data_AddLineToLastAndSystem(new mcMathLine(p));

 // then, add the system to this array
 data_Add(s);
}

void mcSystemStepArray::data_AddSys(mcMathOrSystem *pointer)
{
 // see m_nFlags for more info
 if (m_nFlags & mcSYSTEMSTEPARR_DISCARD_SIMPLE) {
  data_AddSysOnlyIfComplexEnough(pointer);
  return;
 }

 mcAbstractArray::data_Add(pointer); 
}

void mcSystemStepArray::data_AddFinalSys(mcMathOrSystem *pointer)
{ mcAbstractArray::data_Add(pointer); }

void mcSystemStepArray::data_AddLineOnlyIfComplexEnough(const mcMathLine &p)
{
 mcMathOrSystem *s=new mcMathOrSystem();
 s->data_AddLineToLastAndSystem(new mcMathLine(p));

 // then, add the system to this array
 data_AddSysOnlyIfComplexEnough(s);
}

void mcSystemStepArray::data_AddSysOnlyIfComplexEnough(mcMathOrSystem *p)
{
 if (data_GetCount() < 1) {
  mcAbstractArray::data_Add(p); 
  return;
 }

 int i=data_GetCount()-1;
 mcRealValue last = data_Get(i)->math_GetTotalLenght();
 mcRealValue diff = p->math_GetTotalLenght()-last;

 // add this step only if the difference of lenght is less than
 // the step threshold...
 if (diff > mcMathCore::Get()->GetStepThreshold())
  mcAbstractArray::data_Add(p);
 else
  delete p;  // discard it
}

int mcSystemStepArray::math_RemoveIdenticSteps()
{
 int removed = 0;

 // discard checks on the first step
 for (int i=1; i < data_GetCount(); i++) {

  // use the math_Compare() function; hasSameContentOf should
  // always return TRUE...
  if (data_Get(i)->math_Compare(*data_Get(i-1), FALSE)) {

   // this step is exactly identic to the i-th step of the array
   // or it is the identic to the original system...
   // remove it and return a new pointer as new step
   data_RemoveAt(i);
   removed++;

   // check this entry again
   i--;
  }
 }

 return removed;
}

int mcSystemStepArray::math_RemoveSimpleSteps()
{
 int removed = 0;

 if (data_GetCount() == 0) return 0;
 mcRealValue last = data_Get(0)->math_GetTotalLenght();

 // discard checks on the first & last step
 // (last step, even if very very simple must always be kept)
 for (int i=1; i < data_GetCount()-1; i++) {
  
  // check if the difference of lenght is great enough
  mcRealValue currlenght = data_Get(i)->math_GetTotalLenght();  // compute only once (slow)
  mcRealValue diff = currlenght-last;

  if (diff < mcMathCore::Get()->GetStepThreshold()) {

   // it's not: remove this step
   data_RemoveAt(i);
   removed++;

   // check this entry again
   i--;

  } else {

   last = currlenght;
  }

  data_Check();
 }

 return removed;
}

void mcSystemStepArray::data_Check() const
{
 mcAbstractArray::data_Check();
 for (int i=0; i < data_GetCount(); i++)
  data_Get(i)->data_Check();
}

void mcSystemStepArray::data_Delete(int n)
{ 
 // this one cannot be placed in the header (since mcMathOrSystem must be defined)
 delete data_Get(n); 
}

wxString mcSystemStepArray::io_GetInlinedExpr() const
{
 wxString res;
 
 for (int i=0; i < data_GetCount(); i++) {

  // just leave some space between a step and the next one...
  if (i>0) res+=wxT("    ");
  res += data_Get(i)->io_GetInlinedExpr();
 }

 return res;
}

void mcSystemStepArray::math_AppendCombinationOf(const mcSystemStepArray &arr1,
            const mcSystemStepArray &arr2,
            mcLogicOperator lo)
{
 mcMATHLOG(wxT("mcSystemStepArray::math_AppendCombinationOf - merging\n\n%s\n\nwith\n\n%s"),
    mcTXT(arr1), mcTXT(arr2));
 int arr1idx=0, arr2idx=0;

 for (int i=0,max=mcMAX(arr1.data_GetCount(), arr2.data_GetCount()); i<max; i++) {

  // merge each step of the first array with the relative step of the
  // second array...
  mcMathOrSystem *toadd = new mcMathOrSystem();
  const mcMathOrSystem &first = *arr1.data_Get(arr1idx);
  const mcMathOrSystem &second = *arr2.data_Get(arr2idx);

  switch (lo) {
  case mcLO_AND:
   toadd->math_AndMerge(first, second);
   break;

  case mcLO_OR:
   toadd->math_OrMerge(first, second);
   break;

  default:
   mcASSERT(0, wxT("Unhandled logical operator"));
  }

  // then, add the result to this array
  data_Add(toadd);

  // now, advance array indexes
  arr1idx++;
  arr2idx++;

  // just check they do not exceed the array end... in this case, 
  // we must point the index of the array containing the lower
  // number of steps to its last step; in this way, the remaining
  // steps of the other array will be merged always with it:
  //
  // arr1:  A1, B1, C1, D1, E1, F1
  // arr2:  A1, B2, C2
  //
  // result of arr1+arr2:
  //            A1^A2, B1^B2, C1^C2, D1^C2, E1^C2, F1^C2
  //
  // where:
  // - the comma separes the various steps
  // - the wxT("^") symbol means "merged with"
  // 
  if (arr1idx >= arr1.data_GetCount()) arr1idx = arr1.data_GetCount()-1;
  if (arr2idx >= arr2.data_GetCount()) arr2idx = arr2.data_GetCount()-1;
 }
}





// --------------------
// mcLINESTEPARRAY
// --------------------
/*
void mcLineStepArray::data_Check() const
{
 for (int i=0; i < data_GetCount(); i++)
  data_Get(i)->data_Check();
}

int mcLineStepArray::data_RemoveSimpleSteps()
{
 int removed = 0;

 if (data_GetCount() == 0) return 0;
 mcRealValue last = data_Get(0)->math_GetTotalLenght();

 // discard checks on the first & last step
 // (last step, even if very very simple must always be kept)
 for (int i=1; i < data_GetCount()-1; i++) {
  
  // check if the difference of lenght is great enough
  mcRealValue currlenght = data_Get(i)->math_GetTotalLenght();  // compute only once (slow)
  mcRealValue diff = currlenght-last;

  if (diff < mcMathCore::Get()->GetStepThreshold()) {

   // it's not: remove this step
   data_RemoveAt(i);
   removed++;

   // check this entry again
   i--;

  } else {

   last = currlenght;
  }
 
  data_Check();
 }

 return removed;
}
*/

---

Documentation generated with Doxygen on Sun Feb 6 17:10:48 2005 Visit MathStudio home page for more info

[ Top ]