gpolylst.imp

Gambit 是一个游戏库理论软件

//
// $Source: /home/gambit/CVS/gambit/sources/poly/gpolylst.imp,v $
// $Date: 2002/08/27 17:29:46 $
// $Revision: 1.2 $
//
// DESCRIPTION:
// Implementation of polynomial list type
//
// This file is part of Gambit
// Copyright (c) 2002, The Gambit Project
//
// 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 "gpolylst.h"

//---------------------------------------------------------------
//                      gPolyList
//---------------------------------------------------------------

//---------------------------
// Constructors / Destructors
//---------------------------

template <class T> gPolyList<T>::gPolyList(const gSpace* sp, 
					   const term_order* to) 
: Space(sp), Order(to), List()
{
}

template<class T> gPolyList<T>::gPolyList(const gSpace * sp,
					  const term_order* to,
					  const gList< gPoly<T> *> & plist)
: Space(sp), Order(to), List()
{
  int ii;
  for ( ii = 1; ii <= plist.Length(); ii++) 
    { gPoly<T>* temp = new gPoly<T>(*plist[ii]); List+=temp; }
}

template<class T> gPolyList<T>::gPolyList(const gSpace * sp,
					  const term_order* to,
					  const gList< gPoly<T> > & list)
: Space(sp), Order(to), List()
{
  int ii;
  for ( ii = 1; ii <= list.Length(); ii++) 
    { gPoly<T>* temp = new gPoly<T>(list[ii]); List+=temp; }
}

template<class T> gPolyList<T>::gPolyList(const gPolyList<T> & lst)
: Space(lst.Space), Order(lst.Order), List()
{
  int ii;
  for ( ii = 1; ii <= lst.List.Length(); ii++) 
    { gPoly<T>* temp = new gPoly<T>(*(lst.List[ii])); List+=temp; }
}

template<class T> gPolyList<T>::~gPolyList()
{
  int ii;
  for (ii = 1; ii <= List.Length(); ii++) delete List[ii];
}

//----------------------------------
//        Operators
//----------------------------------

template<class T> 
gPolyList<T>& gPolyList<T>::operator=(const gPolyList<T> & rhs)
{
  assert (Space == rhs.Space && Order == rhs.Order);

  if (*this != rhs) {
    int ii;
    for (ii = List.Length(); ii >= 1; ii--) 
      { delete List[ii]; List.Remove(ii); }

    for (ii = 1; ii <= rhs.List.Length(); ii++) 
      { gPoly<T>* temp = new gPoly<T>(*(rhs.List[ii])); List+=temp; }

  }
  return *this;
}

template<class T>  
bool gPolyList<T>::operator==(const gPolyList<T> & rhs) const
{
  if (Space != rhs.Space || Order != rhs.Order) return false;
  if (List.Length() != rhs.List.Length()) return false;
  for (int j = 1; j <= List.Length(); j++)
    if (*List[j] != *(rhs.List[j]))
      return false;
  return true;
}

template<class T>  
bool gPolyList<T>::operator!=(const gPolyList<T> & rhs) const
{
  return !(*this == rhs);
}

template<class T>  void gPolyList<T>::operator+=(const gPoly<T> & new_poly)
{
  gPoly<T>* temp = new gPoly<T>(new_poly);
  List+=temp;
}

template<class T>  void gPolyList<T>::operator+=(const gPolyList<T> & new_list)
{
  gList<gPoly<T>*> temp;
  for (int i = 1; i <= new_list.Length(); i++)
    temp += new gPoly<T>(new_list[i]);
  List+=temp;
}

// NB - does not copy pointee - see gpolylst.h
template<class T>  void gPolyList<T>::operator+=(gPoly<T> * new_poly_ptr)
{
  List+=new_poly_ptr;
}

template<class T>  gPoly<T> gPolyList<T>::operator[](const int index) const
{
  return *(List[index]);
}

//-------------------------------------------------
//        Term Order and Grobner Basis Operations
//-------------------------------------------------

template<class T> bool gPolyList<T>::SelfReduction(const int& target,
					          const term_order& order)
{  
  assert (!List[target]->IsZero());

  gPoly<T> tear_up(*List[target]);
  gPoly<T> reduction(Space,(T)0,&order);
  bool     target_was_reduced = false;

  while (!tear_up.IsZero())
    {
      int index = 1;
      while (index <= List.Length() && !tear_up.IsZero()) {
        if (index == target || List[index]->IsZero()) index++;
	else if ( List[index]->LeadingPowerProduct(order) 
	            <= tear_up.LeadingPowerProduct(order) ) {
	  tear_up.ReduceByDivisionAtExpV(order,
					 *List[index],
					 tear_up.LeadingPowerProduct(order));
	  target_was_reduced = true;
	  index = 1;
	}
	if (!tear_up.IsZero()) {
	  reduction+=tear_up.LeadingTerm(order);
	  tear_up-=tear_up.LeadingTerm(order);
	}
      }
    }
  *List[target] = reduction;
  return target_was_reduced;
}

template<class T> gPoly<T> gPolyList<T>::ReductionOf(const gPoly<T>& f,
					           const term_order& order) 
                                                                        const
{
  assert (Space == f.GetSpace());

  if (f.IsZero()) {
    gPoly<T> zero(Space,(T)0,f.GetOrder());
    return zero;
  }

  gPoly<T> tear_up(f);
  gPoly<T> reduction(Space,(T)0,f.GetOrder());

  while (!tear_up.IsZero())
    {
      int index = 1;
      while (index <= List.Length() && !tear_up.IsZero()) {
	if (List[index]->IsZero()) index++;
	else if ( List[index]->LeadingPowerProduct(order) 
	            <= tear_up.LeadingPowerProduct(order) ) {

	  tear_up.ReduceByDivisionAtExpV(order,
					 *List[index],
					 tear_up.LeadingPowerProduct(order));
	  index = 1;
	}
	else index++;
      }
      if (!tear_up.IsZero()) {
	reduction+=tear_up.LeadingTerm(order);
	tear_up-=tear_up.LeadingTerm(order);
      }

    }
  return reduction;
}

template<class T> void gPolyList<T>::Sort(const term_order& order) 
                                       // bubble sort, justified since
                                       // I expect List.Length() < 10
{
  if (List.Length() <= 1) return;
  int ii;
  for (ii = 1; ii < List.Length(); ii++)
    if (!List[ii]->IsZero()) {
      for (int j = ii + 1; j <= List.Length(); j++) {
	bool swap = false;
	if (List[j]->IsZero())
	  swap = true;
	else if ( order.Less(List[j]->LeadingPowerProduct(order),
			    List[ii]->LeadingPowerProduct(order)) ) 
	  swap = true;
	if (swap) {
	  gPoly<T>* temp = List[ii];
	  List[ii] = List[j];
	  List[j] = temp;
	}
      }
    }
}

template <class T> 
void gPolyList<T>::CriterionTwo(      gList<index_pair>& uncomputed, 
				const gList<index_pair>& computed, 
				const int&               no_polys,
				const term_order & order)           const
{
  for (int ell = 1; ell < no_polys; ell++) {
    int spot = uncomputed.Find(index_pair(ell,no_polys));
    if (spot != 0) {
      int ii;
      for (ii = 1; ii < no_polys; ii++) 
	if (ii != ell && spot != 0) 
	  if ( uncomputed.Contains(index_pair(ii,ell)) ||
	       computed.Contains(index_pair(ii,ell)) )
	    if (uncomputed.Contains(index_pair(ii,no_polys)))  {
	      exp_vect lpp_i        = List[ii]->  LeadingPowerProduct(order);
	      exp_vect lpp_ell      = List[ell]->LeadingPowerProduct(order);
	      exp_vect lpp_no_polys = List[no_polys]->
		LeadingPowerProduct(order);
	      if ( lpp_ell.Divides(lpp_i.LCM(lpp_no_polys)) ) {
		uncomputed.Remove(spot); 
		spot = 0;
	      }
	    }
    }
  }
  int ii;
  for (ii = 1; ii < no_polys; ii++) {
    if ( uncomputed.Contains(index_pair(ii,no_polys)) )
      for (int j = ii + 1; j < no_polys; j++) {
	int spot = uncomputed.Find(index_pair(ii,j));
	if ( uncomputed.Contains(index_pair(j,no_polys)) && (spot != 0) ) {
	      exp_vect lpp_i        = List[ii]->LeadingPowerProduct(order);
	      exp_vect lpp_j        = List[j]->LeadingPowerProduct(order);
	      exp_vect lpp_no_polys = List[no_polys]->
		                               LeadingPowerProduct(order);
	      if ( lpp_no_polys.Divides(lpp_i.LCM(lpp_j)) )
		uncomputed.Remove(spot);
	    }
      }
  }
}

template<class T> void gPolyList<T>::Grobnerize(const term_order & order)
{
  int index = 1;                 // Remove all 0's from List
  while (index <= List.Length())
    if (List[index]->IsZero())
      { delete List[index]; List.Remove(index); }