//
// $Source: /cvsroot/gambit/gambit/sources/libgambit/stratspt.cc,v $
// $Date: 2006/11/08 14:23:22 $
// $Revision: 1.17 $
//
// DESCRIPTION:
// Implementation of strategy classes for normal forms
//
// 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 "libgambit.h"

namespace Gambit {

//===========================================================================
//                          class StrategySupport
//===========================================================================

//---------------------------------------------------------------------------
//                               Lifecycle
//---------------------------------------------------------------------------

StrategySupport::StrategySupport(const Game &p_nfg) 
  : m_nfg(p_nfg), m_profileIndex(p_nfg->MixedProfileLength())
{ 
  for (int pl = 1, index = 1; pl <= p_nfg->NumPlayers(); pl++) {
    m_support.Append(Array<GameStrategy>());
    for (int st = 1; st <= p_nfg->GetPlayer(pl)->NumStrategies(); 
	 st++, index++) {
      m_support[pl].Append(p_nfg->GetPlayer(pl)->GetStrategy(st));
      m_profileIndex[index] = index;
    }
  }
}

//---------------------------------------------------------------------------
//                          General information
//---------------------------------------------------------------------------

Array<int> StrategySupport::NumStrategies(void) const
{
  Array<int> a(m_support.Length());

  for (int pl = 1; pl <= a.Length(); pl++) {
    a[pl] = m_support[pl].Length();
  }
  return a;
}

int StrategySupport::MixedProfileLength(void) const
{
  int total = 0;
  for (int pl = 1; pl <= m_nfg->NumPlayers();
       total += m_support[pl++].Length());
  return total;
}

bool StrategySupport::IsSubsetOf(const StrategySupport &p_support) const
{
  if (m_nfg != p_support.m_nfg)  return false;
  for (int pl = 1; pl <= m_support.Length(); pl++) {
    if (m_support[pl].Length() > p_support.m_support[pl].Length()) {
      return false;
    }
    else {
      for (int st = 1; st <= m_support[pl].Length(); st++) {
	if (!p_support.m_support[pl].Contains(m_support[pl][st])) {
	  return false;
	}
      }
    }
  }
  return true;
}

//---------------------------------------------------------------------------
//                        Modifying the support
//---------------------------------------------------------------------------

void StrategySupport::AddStrategy(const GameStrategy &p_strategy)
{ 
  // Get the null-pointer checking out of the way once and for all
  GameStrategyRep *strategy = p_strategy;
  Array<GameStrategy> &support = 
    m_support[strategy->GetPlayer()->GetNumber()];
  

  for (int i = 1; i <= support.Length(); i++) {
    GameStrategyRep *s = support[i];
    if (s->GetNumber() == strategy->GetNumber()) {
      // Strategy already in support; no change
      return;
    }
    if (s->GetNumber() > strategy->GetNumber()) {
      // Shift all higher-id strategies by one in the profile
      m_profileIndex[strategy->GetId()] = m_profileIndex[s->GetId()];
      for (int id = s->GetId(); id <= m_profileIndex.Length(); id++) {
	if (m_profileIndex[id] >= 0)  m_profileIndex[id]++;
      }
      // Insert here
      support.Insert(strategy, i);
      return;
    }
  }

  // If we get here, p_strategy has a higher number than anything in the
  // support for this player; append.
  GameStrategyRep *last = support[support.Last()];
  m_profileIndex[strategy->GetId()] = m_profileIndex[last->GetId()] + 1;
  for (int id = strategy->GetId()+1; id <= m_profileIndex.Length(); id++) {
    if (m_profileIndex[id] >= 0)  m_profileIndex[id]++;
  }
  support.Append(strategy);
}

bool StrategySupport::RemoveStrategy(const GameStrategy &p_strategy) 
{ 
  GameStrategyRep *strategy = p_strategy;
  Array<GameStrategy> &support = m_support[strategy->GetPlayer()->GetNumber()];

  if (support.Length() == 1) return false;

  for (int i = 1; i <= support.Length(); i++) {
    GameStrategyRep *s = support[i];
    if (s == strategy) {
      support.Remove(i);
      m_profileIndex[strategy->GetId()] = -1;
      // Shift strategies left in the profile
      for (int id = strategy->GetId()+1; id <= m_profileIndex.Length(); id++) {
	if (m_profileIndex[id] >= 0)  m_profileIndex[id]--;
      }
      return true;
    }
  }

  return false;
} 


//---------------------------------------------------------------------------
//                 Identification of dominated strategies
//---------------------------------------------------------------------------

bool StrategySupport::Dominates(const GameStrategy &s, 
				const GameStrategy &t, 
				bool p_strict) const
{
  bool equal = true;
  
  for (StrategyIterator iter(*this); !iter.AtEnd(); iter++) {
    Rational ap = iter->GetStrategyValue<Rational>(s);
    Rational bp = iter->GetStrategyValue<Rational>(t);
    if (p_strict && ap <= bp) {
      return false;
    }
    else if (!p_strict) {
      if (ap < bp) return false;
      else if (ap > bp) equal = false;
    }
  }

  return (p_strict || !equal);
}


bool StrategySupport::IsDominated(const GameStrategy &s, 
				  bool p_strict,
				  bool p_external) const
{
  if (p_external) {
    GamePlayer player = s->GetPlayer();
    for (int st = 1; st <= player->NumStrategies(); st++) {
      if (player->GetStrategy(st) != s &&
	  Dominates(player->GetStrategy(st), s, p_strict)) {
	return true;
      }
    }
    return false;
  }
  else {
    for (int i = 1; i <= NumStrategies(s->GetPlayer()->GetNumber()); i++) {
      if (GetStrategy(s->GetPlayer()->GetNumber(), i) != s &&
	  Dominates(GetStrategy(s->GetPlayer()->GetNumber(), i), s, 
		    p_strict)) {
	return true;
      }
    }
    return false;
  }
}

bool StrategySupport::Undominated(StrategySupport &newS, int p_player, 
				  bool p_strict, bool p_external) const
{
  Array<GameStrategy> set((p_external) ? 
			  m_nfg->GetPlayer(p_player)->NumStrategies() :
			  NumStrategies(p_player));

  if (p_external) {
    for (int st = 1; st <= set.Length(); st++) {
      set[st] = m_nfg->GetPlayer(p_player)->GetStrategy(st);
    }
  }
  else {
    for (int st = 1; st <= set.Length(); st++) {
      set[st] = GetStrategy(p_player, st);
    }
  }

  int min = 0, dis = set.Length() - 1;

  while (min <= dis) {
    int pp;
    for (pp = 0;
	 pp < min && !Dominates(set[pp+1], set[dis+1], p_strict);
	 pp++);
    if (pp < min)
      dis--;
    else  {
      GameStrategy foo = set[dis+1];
      set[dis+1] = set[min+1];
      set[min+1] = foo;

      for (int inc = min + 1; inc <= dis; )  {
	if (Dominates(set[min+1], set[dis+1], p_strict)) {
	  //p_tracefile << GetStrategy(p_player, set[dis+1])->GetNumber() << " dominated by " << GetStrategy(p_player, set[min+1])->GetNumber() << '\n';
	  dis--;
	}
	else if (Dominates(set[dis+1], set[min+1], p_strict)) {
	  //p_tracefile << GetStrategy(p_player, set[min+1])->GetNumber() << " dominated by " << GetStrategy(p_player, set[dis+1])->GetNumber() << '\n';
	  foo = set[dis+1];
	  set[dis+1] = set[min+1];
	  set[min+1] = foo;
	  dis--;
	}
	else  {
	  foo = set[dis+1];
	  set[dis+1] = set[inc+1];
	  set[inc+1] = foo;
	  inc++;
	}
      }
      min++;
    }
  }
    
  if (min + 1 <= set.Length()) {
    for (int i = min + 1; i <= set.Length(); i++) {
      newS.RemoveStrategy(set[i]);
    }
    
    return true;
  }
  else {
    return false;
  }
}

StrategySupport StrategySupport::Undominated(bool p_strict,
					     bool p_external) const
{
  StrategySupport newS(*this);

  for (int pl = 1; pl <= m_nfg->NumPlayers(); pl++)   {
    Undominated(newS, pl, p_strict, p_external);
  }

  return newS;
}

StrategySupport 
StrategySupport::Undominated(bool p_strict, const Array<int> &players) const
{
  StrategySupport newS(*this);
  
  for (int i = 1; i <= players.Length(); i++)   {
    //tracefile << "Dominated strategies for player " << pl << ":\n";
    Undominated(newS, players[i], p_strict);
  }

  return newS;
}

//---------------------------------------------------------------------------
//                Identification of overwhelmed strategies
//---------------------------------------------------------------------------

bool StrategySupport::Overwhelms(const GameStrategy &s, 
				 const GameStrategy &t, 
				 bool p_strict) const
{
  StrategyIterator iter(*this);
  Rational sMin = iter->GetStrategyValue<Rational>(s);
  Rational tMax = iter->GetStrategyValue<Rational>(t);

  for (; !iter.AtEnd(); iter++) {
    if (iter->GetStrategyValue<Rational>(s) < sMin) {
      sMin = iter->GetStrategyValue<Rational>(s);
    }
    
    if (iter->GetStrategyValue<Rational>(t) > tMax) { 
      tMax = iter->GetStrategyValue<Rational>(t);
    }

    if (sMin < tMax || (sMin == tMax && p_strict)) {
      return false;
    }
  }

  return true;
}



} // end namespace Gambit