efbasis.cc

Gambit 是一个游戏库理论软件

//
// $Source: /home/gambit/CVS/gambit/sources/game/efbasis.cc,v $
// $Date: 2002/08/26 05:50:05 $
// $Revision: 1.6 $
//
// DESCRIPTION:
// Implementation of extensive form basis class
//
// 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 "efbasis.h"
#include "base/garray.imp"
#include "math/gvector.h"
#include "math/gpvector.h"
#include "math/gdpvect.imp"
#include "math/gmatrix.h"
#include "base/gnullstatus.h"
#include "game/efgutils.h"
#include "numerical/lpsolve.h"   

class EFNodeArrays   {
friend class EFNodeSet;
protected:
  gBlock<Node *> nodes;
  
public:
  EFNodeArrays ( const gArray <Node *> &a);
  EFNodeArrays ( const EFNodeArrays &a);
  virtual ~EFNodeArrays();
  EFNodeArrays &operator=( const EFNodeArrays &a);
  bool operator==( const EFNodeArrays &a) const;
};

//----------------------------------------------------
// EFNodeArray: Constructors, Destructor, operators
// ---------------------------------------------------

EFNodeArrays::EFNodeArrays(const gArray<Node *> &n)
  : nodes(n.Length())
{
  for (int i = 1; i <= nodes.Length(); i++)
    nodes[i] = n[i];
}

EFNodeArrays::EFNodeArrays(const EFNodeArrays &n)
  : nodes(n.nodes)
{ }

EFNodeArrays::~EFNodeArrays ()
{ }

EFNodeArrays &EFNodeArrays::operator=( const EFNodeArrays &n)
{
  nodes = n.nodes; 
  return *this;
}

#ifdef __BORLANDC__
bool operator==(const gArray<Node *> &a, const gArray<Node *> &b)
{
  if (a.First() != b.First() || a.Last() != b.Last())  {
    return false;
  }
  for (int i = a.First(); i <= a.Last(); i++) {
    if (a[i] != b[i])   return false;
  }
  return true;
}
#endif

bool EFNodeArrays::operator==(const EFNodeArrays &a) const
{
  return (nodes == a.nodes);
}

class EFNodeSet{

protected:
  EFPlayer *efp;
  gArray < EFNodeArrays *> infosets;
public:
  
  //----------------------------------------
  // Constructors, Destructor, operators
  //----------------------------------------

//  EFNodeSet();
  EFNodeSet(const EFNodeSet &);
  EFNodeSet(EFPlayer &);
  virtual ~EFNodeSet();

  EFNodeSet &operator=(const EFNodeSet &);
  bool operator==(const EFNodeSet &s) const;

  //--------------------
  // Member Functions
  //--------------------

  // Append a Node to an infoset;
  void AddNode(int iset, Node *);

  // Insert a Node in a particular place in an infoset;
  void AddNode(int iset, Node *, int index);


  // Remove a Node at int i, returns the removed Node pointer
  Node *RemoveNode(int iset, int i);

  // Remove a Node from an infoset . 
  // Returns true if the Node was successfully removed, false otherwise.
  bool RemoveNode(int iset, Node *);

  // Get a garray of the Nodes in an Infoset
  const gArray<Node *> &NodeList(int iset) const
     { return infosets[iset]->nodes; }
  
  // Get a Node
  Node *GetNode(int iset, int index);

  // returns the index of the Node if it is in the NodeSet
  int Find(Node *) const;

  // Number of Nodes in a particular infoset
  int NumNodes(int iset) const;

  // return the EFPlayer of the EFNodeSet
  EFPlayer &GetPlayer(void) const;

  // checks for a valid EFNodeSet
  bool IsValid(void) const;

};

//--------------------------------------------------
// EFNodeSet: Constructors, Destructor, operators
//--------------------------------------------------

EFNodeSet::EFNodeSet(EFPlayer &p)
  : infosets(p.NumInfosets())
{
  efp = &p;
  for (int i = 1; i <= p.NumInfosets(); i++){
    infosets[i] = new EFNodeArrays(p.Infosets()[i]->Members());
  }
}

EFNodeSet::EFNodeSet( const EFNodeSet &s )
: infosets(s.infosets.Length())
{
  efp = s.efp;
  for (int i = 1; i <= s.infosets.Length(); i++){
    infosets[i] = new EFNodeArrays(*(s.infosets[i]));
  }
}

EFNodeSet::~EFNodeSet()
{ 
  for (int i = 1; i <= infosets.Length(); i++)
    delete infosets[i];
}

EFNodeSet &EFNodeSet::operator=(const EFNodeSet &s)
{
  if (this != &s && efp == s.efp) {
    for (int i = 1; i<= infosets.Length(); i++)  {
      delete infosets[i];
      infosets[i] = new EFNodeArrays(*(s.infosets[i]));
    }
  }    
  return *this;
}

bool EFNodeSet::operator==(const EFNodeSet &s) const
{
  if (infosets.Length() != s.infosets.Length() ||
      efp != s.efp)
    return false;
  
  int i;
  for (i = 1; i <= infosets.Length() && 
       *(infosets[i]) == *(s.infosets[i]);  i++);
  return (i > infosets.Length());
}

//------------------------------------------
// EFNodeSet: Member functions 
//------------------------------------------

// Append a Node to a particular infoset;
void EFNodeSet::AddNode(int iset, Node *s) 
{ 
  infosets[iset]->nodes.Append(s); 
}

// Insert a Node  to a particular infoset at a particular place;
void EFNodeSet::AddNode(int iset, Node *s, int index) 
{ 
  infosets[iset]->nodes.Insert(s,index); 
}

// Remove a Node from infoset iset at int i, 
// returns the removed Infoset pointer
Node* EFNodeSet::RemoveNode(int iset, int i) 
{ 
  return (infosets[iset]->nodes.Remove(i)); 
}

// Removes a Node from infoset iset . Returns true if the 
//Node was successfully removed, false otherwise.
bool EFNodeSet::RemoveNode(int  iset, Node *s ) 
{ 
  int t = infosets[iset]->nodes.Find(s); 
  if (t>0) infosets[iset]->nodes.Remove(t); 
  return (t>0); 
} 

// Get a Node
Node *EFNodeSet::GetNode(int iset, int index)
{
  return (infosets[iset]->nodes)[index];
}

// Number of Nodes in a particular infoset
int EFNodeSet::NumNodes(int iset) const
{
  return (infosets[iset]->nodes.Length());
}

// Return the EFPlayer of this EFNodeSet
EFPlayer &EFNodeSet::GetPlayer(void) const
{
  return (*efp);
}

int EFNodeSet::Find(Node *n) const
{
  return (infosets[n->GetInfoset()->GetNumber()]->nodes.Find(n));
}

// checks for a valid EFNodeSet
bool EFNodeSet::IsValid(void) const
{
  if (infosets.Length() != efp->NumInfosets())   return false;

  for (int i = 1; i <= infosets.Length(); i++)
    if (infosets[i]->nodes.Length() == 0)   return false;

  return true;
}

//--------------------------------------------------
// EFBasis: Constructors, Destructors, Operators
//--------------------------------------------------

EFBasis::EFBasis(const efgGame &E) : EFSupport(E), nodes(E.NumPlayers())
{
  for (int i = 1; i <= nodes.Length(); i++)
    nodes[i] = new EFNodeSet(*(E.Players()[i]));
}

EFBasis::EFBasis(const EFBasis &b)
  : EFSupport(b), nodes(b.nodes.Length())
{
  for (int i = 1; i <= nodes.Length(); i++)
    nodes[i] = new EFNodeSet(*(b.nodes[i]));
}

EFBasis::~EFBasis()
{
  for (int i = 1; i <= nodes.Length(); i++)
    delete nodes[i];
}

EFBasis &EFBasis::operator=(const EFBasis &b)
{
  EFSupport::operator=(b);
  return *this;
}

bool EFBasis::operator==(const EFBasis &b) const
{
  if( (*this).EFSupport::operator!=(b)) return false;

  if (nodes.Length() != b.nodes.Length()) return false;

  int i;
  for (i = 1; i <= nodes.Length() && *(nodes[i]) == *(b.nodes[i]); i++);
  return (i > nodes.Length());
}

bool EFBasis::operator!=(const EFBasis &b) const
{
  return !(*this == b);
}

//-----------------------------
// EFBasis: Member Functions 
//-----------------------------

int EFBasis::NumNodes(int pl, int iset) const
{
  return nodes[pl]->NumNodes(iset);
}

const gArray<Node *> &EFBasis::Nodes(int pl, int iset) const
{