listfunc.cc

来自「Gambit 是一个游戏库理论软件」· CC 代码 · 共 952 行 · 第 1/2 页

//
// $Source: /home/gambit/CVS/gambit/sources/gcl/listfunc.cc,v $
// $Date: 2002/08/27 18:57:19 $
// $Revision: 1.4 $
//
// DESCRIPTION:
// List- and text-oriented GCL functions
//
// 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 "base/base.h"

#include "gsm.h"
#include "portion.h"
#include "gsmfunc.h"

#include "math/rational.h"
#include "math/gsmatrix.h"

#include "game/nfg.h"
#include "game/efg.h"



//---------
// Concat
//---------

static Portion* GSM_Concat_List(GSM &, Portion** param)
{
  const gList<Portion*>& p_value = ((ListPortion*) param[1])->Value();
  Portion *result = new ListPortion(((ListPortion*) param[0])->Value());
  for (int i = 1; i <= p_value.Length(); i++)  {
    int append_result = ((ListPortion*) result)->Append(p_value[i]->ValCopy());
    if(append_result == 0)  {
      delete result;
      throw gclRuntimeError("Attempted concatenating lists of different types");
    }
  }
  return result;
}


//------------
// Index
//------------

static Portion* GSM_Index(GSM &, Portion** param)
{
  ListPortion* result = new ListPortion();
  ListPortion& list = *(ListPortion*) param[0];
  bool type_found = false;
  for (int i = 1; i <= list.Length(); i++)  {
    if (PortionEqual(list[i], param[1], type_found)) 
      result->Append(new NumberPortion(i));
  }
  return result;
}




//-------------------
// Flatten
//-------------------

static void GSM_Flatten_Top(ListPortion* list, int levels, int depth, 
			    ListPortion* result)
{
  int Length = list->Length();
  int i;
  if (levels < 0) {
    throw gclRuntimeError("Internal error in Flatten[]");
  }

  if(levels == 0) {
    for (i=1; i<=Length; i++)
      if((*list)[i]->Spec().ListDepth == 0)
	result->Append((*list)[i]->ValCopy());
      else
	GSM_Flatten_Top((ListPortion*)(*list)[i], levels, depth+1, result);
  }
  else if(levels > 0) {
    if(depth >= levels)
      for(i=1; i<=Length; i++)
	result->Append((*list)[i]->ValCopy());
    else
      for(i=1; i<=Length; i++)
	if((*list)[i]->Spec().ListDepth == 0)
	  result->Append((*list)[i]->ValCopy());
	else
	  GSM_Flatten_Top((ListPortion*)(*list)[i], levels, depth+1, result);
  }
}

static void GSM_Flatten_Bottom(ListPortion* list, int levels, int depth, 
			       ListPortion* result)
{
  int Length = result->Length();
  int i;
  if (levels <= 0 || list != 0) {
    throw gclRuntimeError("Internal error in Flatten[]");
  }
  if(depth >= levels-1) {
    for(i=1; i<=Length; i++)
      if((*result)[i]->Spec().ListDepth == 0)
	;
      else
      {
	ListPortion* oldsublist = (ListPortion*) result->Remove(i);
	ListPortion* newsublist = new ListPortion();
	GSM_Flatten_Top(oldsublist, 0, depth+1, newsublist);
	result->Insert(newsublist, i);
	delete oldsublist;
      }
  }
  else
  {
    for(i=1; i<=Length; i++)
      if((*result)[i]->Spec().ListDepth == 0)
	;
      else
	GSM_Flatten_Bottom(0, levels, depth+1, (ListPortion*)(*result)[i]);
  }
}

static Portion* GSM_Flatten(GSM &, Portion** param)
{
  // if levels > 0, flatten from bottom
  ListPortion* list;
  int levels = ((NumberPortion*) param[1])->Value();
  if(levels >= 0)
  {
    list = new ListPortion();
    GSM_Flatten_Top((ListPortion*) param[0], levels, 0, list);
  }
  else
  {
    list = (ListPortion*) ((ListPortion*) param[0])->ValCopy();
    GSM_Flatten_Bottom(0, -levels, 0, list);
  }
    
  return list;
}


static bool ListDimCheck(ListPortion* p0, ListPortion* p1)
{
  int i;
  int Length;
  if (p0->Spec().ListDepth <= 0 || p1->Spec().ListDepth <= 0) {
    throw gclRuntimeError("Internal error in ListDimCheck()");
  }
  Length = p0->Length();
  if(Length != p1->Length())
    return false;
  for(i = 1; i <= Length; i++)
  {
    if((*p0)[i]->Spec().ListDepth != (*p1)[i]->Spec().ListDepth)
      return false;
    if((*p0)[i]->Spec().ListDepth > 0)
      if(!ListDimCheck((ListPortion*)(*p0)[i], (ListPortion*)(*p1)[i]))
	return false;
  }
  return true;
}

static ListPortion* GSM_Filter_Aid(ListPortion* p0, ListPortion* p1)
{
  int i;
  int Length = p0->Length();
  ListPortion* list = new ListPortion();
  for(i=1; i<=Length; i++)
    if((*p0)[i]->Spec().ListDepth == 0) {
      if ((*p1)[i]->Spec().Type != porBOOLEAN) {
	throw gclRuntimeError("Internal error in Filter[]");
      }
      if(((BoolPortion*) (*p1)[i])->Value())
	list->Append((*p0)[i]->ValCopy());
    }
    else
      list->Append(GSM_Filter_Aid((ListPortion*)(*p0)[i], 
				  (ListPortion*)(*p1)[i]));
  return list;
}

static Portion* GSM_Filter(GSM &, Portion** param)
{
  if(!ListDimCheck((ListPortion*) param[0], (ListPortion*) param[1]))
    throw gclRuntimeError("Mismatching list dimensions");
  ListPortion* list = GSM_Filter_Aid((ListPortion*) param[0], 
				     (ListPortion*) param[1]);
  list->SetDataType( param[0]->Spec().Type );
  return list;
}


static Portion* GSM_Sort(Portion** param, 
			 bool (*compfunc)(Portion*, Portion*), 
			 bool altsort = false)
{
  // If altsort, param[1] is rearranged using the sorted result of param[0]

  unsigned long n = ((ListPortion*) param[0])->Length();
  
  if (!param[0]) {
    throw gclRuntimeError("Internal error in Sort[]");
  }
  if (altsort && !param[1]) {
    throw gclRuntimeError("Internal error in Sort[]");
  }

  if(altsort)
    if(n != (unsigned) ((ListPortion*) param[1])->Length())
      throw gclRuntimeError("Mismatching list dimensions");
  
  Portion* *a=new Portion* [n+1];
  Portion* *b=new Portion* [n+1];
  unsigned long* c=new unsigned long[n+1];
  unsigned long i, j, inc;
  Portion* va; 
  unsigned long vc;
  bool no_sub_lists = true;

  for(i=1; i<=n; i++)
  {
    c[i] = i;
    a[i] = ((ListPortion*) param[0])->Remove(1);
    if(a[i]->Spec().ListDepth > 0)
      no_sub_lists = false;
    if(altsort)
    {
      b[i] = ((ListPortion*) param[1])->Remove(1);
      if(b[i]->Spec().ListDepth > 0)
	no_sub_lists = false;
    }
  }

  if(no_sub_lists)
  {
    // sort via Shell's method, adapted from 
    // _Numerical_Recipes_in_C_, 2nd Edition, p. 332
    inc = 1;
    do {
      inc *= 3;
      inc++;
    } while(inc <= n);
    do {
      inc /= 3;
      for(i=inc+1; i<=n; i++) {
	va = a[i];
	vc = c[i];
	j=i;
	// RDM 9/24/00: changed test to maintain original ordering  
	// under equality
	while(compfunc(a[j-inc], va) 
	      || (!compfunc(va,a[j-inc]) && (c[j-inc] > vc))) {
	  a[j] = a[j-inc];
	  c[j] = c[j-inc];
	  j -= inc;
	  if(j <= inc) break;
	}
	a[j] = va;
	c[j] = vc;
      }
    } while(inc > 1);
  }

  for(i=1; i<=n; i++)
  {
    ((ListPortion*) param[0])->Append(a[i]);
    if(altsort)
      ((ListPortion*) param[1])->Append(b[c[i]]);      
  }

  delete[] a;
  delete[] b;
  delete[] c;

  if(no_sub_lists)
  {
    if(!altsort)
      return param[0]->ValCopy();
    else
      return param[1]->ValCopy();
  }
  else
    throw gclRuntimeError("Cannot sort a nested list");
}


#ifdef UNUSED
static bool GSM_Compare_Integer(Portion* p1, Portion* p2)
{ return ((NumberPortion*) p1)->Value() > ((NumberPortion*) p2)->Value(); }

static Portion* GSM_Sort_Integer(GSM &, Portion** param)
{ return GSM_Sort(param, GSM_Compare_Integer); }

static Portion* GSM_Sort_By_Integer(GSM &, Portion** param)
{
  Portion* p[2]; 
  p[0] = param[1]; 
  p[1] = param[0];
  return GSM_Sort(p, GSM_Compare_Integer, true);
}
#endif  // UNUSED

bool GSM_Compare_Number(Portion* p1, Portion* p2)
{ return ((NumberPortion*) p1)->Value() > ((NumberPortion*) p2)->Value(); }
Portion* GSM_Sort_Number(GSM &, Portion** param)
{ return GSM_Sort(param, GSM_Compare_Number); }
static Portion* GSM_Sort_By_Number(GSM &, Portion** param)
{
  Portion* p[2]; 
  p[0] = param[1]; 
  p[1] = param[0];
  return GSM_Sort(p, GSM_Compare_Number, true);
}

static bool GSM_Compare_Text(Portion* p1, Portion* p2)
{ return ((TextPortion*) p1)->Value() > ((TextPortion*) p2)->Value(); }
static Portion* GSM_Sort_Text(GSM &, Portion** param)
{ return GSM_Sort(param, GSM_Compare_Text); }
static Portion* GSM_Sort_By_Text(GSM &, Portion** param)
{
  Portion* p[2]; 
  p[0] = param[1]; 
  p[1] = param[0];
  return GSM_Sort(p, GSM_Compare_Text, true);
}




static Portion *GSM_NthElement(GSM &, Portion **param)
{
  int n = ((NumberPortion *) param[1])->Value();
  if(n <= 0 || n > ((ListPortion *) param[0])->Length())
    throw gclRuntimeError("Subscript out of range");
  else
    return ((ListPortion *) param[0])->SubscriptCopy(n);
}

static Portion *GSM_Remove(GSM &, Portion **param)
{
  ListPortion *ret = (ListPortion *) param[0]->ValCopy();
  delete ret->Remove(((NumberPortion *) param[1])->Value());
  return ret;
}

static Portion *GSM_Contains(GSM &, Portion **param)
{
  return new BoolPortion(((ListPortion *) param[0])->Contains(param[1]));
}

static Portion *GSM_NumElements(GSM &, Portion **param)
{
  return new NumberPortion(((ListPortion *) param[0])->Length());
}

static Portion *GSM_LengthList(GSM &, Portion **param)
{
  return new NumberPortion(((ListPortion *) param[0])->Length());
}

static Portion *GSM_LengthText(GSM &, Portion **param)
{
  return new NumberPortion((int) ((TextPortion *) param[0])->Value().Length());
}

static Portion *GSM_NthElementText(GSM &, Portion **param)
{
  gText text(((TextPortion *) param[0])->Value());
  unsigned int n = ((NumberPortion *) param[1])->Value();
  if (n <= 0 || n > text.Length())
    return 0;
  return new TextPortion(text[(unsigned int) (n-1)]);
}


//--------------------------- Text ---------------------------

static Portion *GSM_Text_Number(GSM &, Portion **param)
{
  return new TextPortion(ToText(((NumberPortion *) param[0])->Value()));
}

static Portion *GSM_TextText(GSM &, Portion **param)
{
  return param[0]->ValCopy();
}


//------------------------ Integer --------------------------

static Portion *GSM_IntegerNumber(GSM &, Portion **param)
{
  return new NumberPortion((long) ((NumberPortion *) param[0])->Value());
}


gWatch _gcl_watch(0);

static Portion *GSM_StartWatch(GSM &, Portion **)
{
  _gcl_watch.Start();
  return new NumberPortion(0.0);
}

static Portion *GSM_StopWatch(GSM &, Portion **)
{
  _gcl_watch.Stop();
  return new NumberPortion(_gcl_watch.Elapsed());
}

static Portion *GSM_ElapsedTime(GSM &, Portion **)
{
  return new NumberPortion(_gcl_watch.Elapsed());
}

static Portion *GSM_IsWatchRunning(GSM &, Portion **)
{
  return new BoolPortion(_gcl_watch.IsRunning());
}

//--------------------------- List ------------------------------

static Portion* GSM_List(GSM &, Portion** param)
{
  ListPortion* p;
  int i;

  if( ((NumberPortion*) param[1])->Value() < gNumber(0))
    throw gclRuntimeError( "Invalid list Length" );

  p = new ListPortion();
  p->SetDataType( param[0]->Spec().Type );
  for( i = 1; i <= (double) ((NumberPortion*) param[1])->Value(); i++ )
    p->Append( param[0]->ValCopy() );
  return p;
}

static Portion* GSM_List_List(GSM &, Portion **param)
{
  ListPortion* p;
  int i;

  if( ((NumberPortion*) param[1])->Value() < gNumber(0) )
    throw gclRuntimeError( "Invalid list Length" );

  p = new ListPortion();
  p->SetDataType( param[0]->Spec().Type );
  for( i = 1; i <= (double) ((NumberPortion*) param[1])->Value(); i++ )
    p->Append( param[0]->ValCopy() );
  return p;
}

static Portion* GSM_List_Number(GSM &, Portion **param)
{
  ListPortion* p;