efglayout.cc

Gambit 是一个游戏库理论软件

							    p_entry->GetChildNumber());
  case BRANCH_BELOW_VALUE:
    return (const char *) m_parent->Parent()->GetActionValue(parent,
							     p_entry->GetChildNumber());
  default:
    return "";
  }
}

NodeEntry *efgTreeLayout::GetValidParent(Node *e)
{
  NodeEntry *n = GetNodeEntry(e->GetParent());
  if (n) {
    return n;
  }
  else { 
    return GetValidParent(e->GetParent());
  }
}

NodeEntry *efgTreeLayout::GetValidChild(Node *e)
{
  for (int i = 1; i <= e->Game()->NumChildren(e); i++)  {
    NodeEntry *n = GetNodeEntry(e->GetChild(i));
    if (n) {
      return n;
    }
    else  {
      n = GetValidChild(e->GetChild(i));
      if (n) return n;
    }
  }
  return 0;
}

NodeEntry *efgTreeLayout::GetEntry(Node *p_node) const
{
  for (int i = 1; i <= m_nodeList.Length(); i++) {
    if (m_nodeList[i]->GetNode() == p_node) {
      return m_nodeList[i];
    }
  }
  return 0;
}

Node *efgTreeLayout::PriorSameLevel(Node *p_node) const
{
  NodeEntry *entry = GetEntry(p_node);
  if (entry) {
    for (int i = m_nodeList.Find(entry) - 1; i >= 1; i--) {
      if (m_nodeList[i]->GetLevel() == entry->GetLevel())
	return m_nodeList[i]->GetNode();
    }
  }
  return 0;
}

Node *efgTreeLayout::NextSameLevel(Node *p_node) const
{
  NodeEntry *entry = GetEntry(p_node);
  if (entry) {
    for (int i = m_nodeList.Find(entry) + 1; i <= m_nodeList.Length(); i++) {
      if (m_nodeList[i]->GetLevel() == entry->GetLevel()) { 
	return m_nodeList[i]->GetNode();
      }
    }
  }
  return 0;
}

int efgTreeLayout::LayoutSubtree(Node *p_node, const EFSupport &p_support,
				 int &p_maxy, int &p_miny, int &p_ycoord)
{
  int y1 = -1, yn = 0;
  const TreeDrawSettings &settings = m_parent->DrawSettings();
    
  NodeEntry *entry = m_nodeList[p_node->GetNumber()];
  entry->SetNextMember(0);
  if (p_node->NumChildren() > 0) {
    for (int i = 1; i <= p_node->NumChildren(); i++) {
      yn = LayoutSubtree(p_node->GetChild(i), p_support,
			 p_maxy, p_miny, p_ycoord);
      if (y1 == -1) {
	y1 = yn;
      }

      if (!p_node->GetPlayer()->IsChance() &&
	  !p_support.Find(p_node->GetInfoset()->Actions()[i])) {
	m_nodeList[p_node->GetChild(i)->GetNumber()]->SetInSupport(false);
      }
    }
    entry->SetY((y1 + yn) / 2);
  }
  else {
    entry->SetY(p_ycoord);
    p_ycoord += settings.TerminalSpacing();
  }
    
  if (settings.BranchStyle() == BRANCH_STYLE_LINE) {
    entry->SetX(c_leftMargin + entry->GetLevel() * (settings.NodeSize() +
						    settings.BranchLength()));
  }
  else {
    entry->SetX(c_leftMargin + entry->GetLevel() * (settings.NodeSize() +
						    settings.BranchLength() +
						    settings.TineLength()));
  }

  if (p_node->GetPlayer() && p_node->GetPlayer()->IsChance()) {
    entry->SetColor(settings.ChanceColor());
    entry->SetToken(settings.ChanceToken());
  }
  else if (p_node->GetPlayer()) {
    entry->SetColor(settings.PlayerColor(p_node->GetPlayer()->GetNumber()));
    entry->SetToken(settings.PlayerToken());
  }
  else {
    entry->SetColor(settings.TerminalColor());
    entry->SetToken(settings.TerminalToken());
  }  
  
  entry->SetSize(settings.NodeSize());
  entry->SetBranchStyle(settings.BranchStyle());
  if (settings.BranchStyle() == BRANCH_STYLE_LINE) {
    entry->SetBranchLabelStyle(settings.BranchLabels());
  }
  entry->SetBranchLength(settings.BranchLength());

  if (settings.SubgameStyle() == SUBGAME_ARC &&
      p_node->Game()->IsLegalSubgame(p_node)) {
    entry->SetSubgameRoot(true);
    entry->SetSubgameMarked(p_node->GetSubgameRoot() == p_node);
  }
  p_maxy = gmax(entry->Y(), p_maxy);
  p_miny = gmin(entry->Y(), p_miny);
    
  return entry->Y();
}

//
// Checks if there are any nodes in the same infoset as e that are either
// on the same level (if SHOWISET_SAME) or on any level (if SHOWISET_ALL)
//
NodeEntry *efgTreeLayout::NextInfoset(NodeEntry *e)
{
  const TreeDrawSettings &draw_settings = m_parent->DrawSettings();
  
  for (int pos = m_nodeList.Find(e) + 1; pos <= m_nodeList.Length(); pos++) {
    NodeEntry *e1 = m_nodeList[pos];
    // infosets are the same and the nodes are on the same level
    if (e->GetNode()->GetInfoset() == e1->GetNode()->GetInfoset()) {
      if (draw_settings.InfosetConnect() == INFOSET_CONNECT_ALL) {
	return e1;
      }
      else if (e->GetLevel() == e1->GetLevel()) {
	return e1;
      }
    }
  }
  return 0;
}

//
// CheckInfosetEntry.  Checks how many infoset lines are to be drawn at each
// level, spaces them by setting each infoset's node's num to the previous
// infoset node+1.  Also lengthens the nodes by the amount of space taken up
// by the infoset lines.
//
void efgTreeLayout::CheckInfosetEntry(NodeEntry *e)
{
  int pos;
  NodeEntry *infoset_entry, *e1;
  // Check if the infoset this entry belongs to (on this level) has already
  // been processed.  If so, make this entry->num the same as the one already
  // processed and return
  infoset_entry = NextInfoset(e);
  for (pos = 1; pos <= m_nodeList.Length(); pos++) {
    e1 = m_nodeList[pos];
    // if the infosets are the same and they are on the same level and e1 has been processed
    if (e->GetNode()->GetInfoset() == e1->GetNode()->GetInfoset() && 
	e->GetLevel() == e1->GetLevel() && e1->GetSublevel() > 0) {
      e->SetSublevel(e1->GetSublevel());
      if (infoset_entry) {
	e->SetNextMember(infoset_entry);
      }
      return;
    }
  }
    
  // If we got here, this entry does not belong to any processed infoset yet.
  // Check if it belongs to ANY infoset, if not just return
  if (!infoset_entry) return;
    
  // If we got here, then this entry is new and is connected to other entries
  // find the entry on the same level with the maximum num.
  // This entry will have num = num+1.
  int num = 0;
  for (pos = 1; pos <= m_nodeList.Length(); pos++) {
    e1 = m_nodeList[pos];
    // Find the max num for this level
    if (e->GetLevel() == e1->GetLevel())  {
      num = gmax(e1->GetSublevel(), num);
    }
  }
  num++;
  e->SetSublevel(num);
  e->SetNextMember(infoset_entry);
}

void efgTreeLayout::FillInfosetTable(Node *n, const EFSupport &cur_sup)
{
  const TreeDrawSettings &draw_settings = m_parent->DrawSettings();
  NodeEntry *entry = GetNodeEntry(n);
  if (n->Game()->NumChildren(n)>0) {
    for (int i = 1; i <= n->Game()->NumChildren(n); i++) {
      bool in_sup = true;
      if (n->GetPlayer()->GetNumber()) {
	in_sup = cur_sup.Find(n->GetInfoset()->Actions()[i]);
      }
            
      if (in_sup || !draw_settings.RootReachable()) {
	FillInfosetTable(n->GetChild(i), cur_sup);
      }
    }
  }

  if (entry) {
    CheckInfosetEntry(entry);
  }
}

void efgTreeLayout::UpdateTableInfosets(void)
{
  // Note that levels are numbered from 0, not 1.
  // create an array to hold max num for each level
  gArray<int> nums(0, m_maxLevel + 1); 
    
  for (int i = 0; i <= m_maxLevel + 1; nums[i++] = 0);
  // find the max e->num for each level
  for (int pos = 1; pos <= m_nodeList.Length(); pos++) {
    NodeEntry *entry = m_nodeList[pos];
    nums[entry->GetLevel()] = gmax(entry->GetSublevel() + 1,
				   nums[entry->GetLevel()]);
  }
    
  for (int i = 0; i <= m_maxLevel; i++) {
    nums[i+1] += nums[i];
  }
    
  // now add the needed length to each level, and set maxX accordingly
  m_maxX = 0;
  for (int pos = 1; pos <= m_nodeList.Length(); pos++) {
    NodeEntry *entry = m_nodeList[pos];
    if (entry->GetLevel() != 0) {
      entry->SetX(entry->X() + 
		  (nums[entry->GetLevel()-1] +
		   entry->GetSublevel()) * m_infosetSpacing);
    }
    m_maxX = gmax(m_maxX, entry->X());
  }
}

void efgTreeLayout::UpdateTableParents(void)
{
  for (int pos = 1; pos <= m_nodeList.Length(); pos++) {
    NodeEntry *e = m_nodeList[pos];
    e->SetParent((e->GetNode() == m_efg.RootNode()) ? 
		 e : GetValidParent(e->GetNode()));
  }
}

void efgTreeLayout::Layout(const EFSupport &p_support)
{
  // Kinda kludgey; probably should query draw settings whenever needed.
  m_infosetSpacing = 
    (m_parent->DrawSettings().InfosetJoin() == INFOSET_JOIN_LINES) ? 10 : 40;

  if (m_nodeList.Length() != NumNodes(m_efg)) {
    // A rebuild is in order; force it
    BuildNodeList(p_support);
  }

  int miny = 0, maxy = 0, ycoord = c_topMargin;
  LayoutSubtree(m_efg.RootNode(), p_support, maxy, miny, ycoord);

  const TreeDrawSettings &draw_settings = m_parent->DrawSettings();
  if (draw_settings.InfosetConnect() != INFOSET_CONNECT_NONE) {
    // FIXME! This causes lines to disappear... sometimes.
    FillInfosetTable(m_efg.RootNode(), p_support);
    UpdateTableInfosets();
  }

  UpdateTableParents();
  GenerateLabels();

  const int OUTCOME_LENGTH = 60;

  m_maxX += draw_settings.NodeSize() + OUTCOME_LENGTH;
  m_maxY = maxy + 25;
}

void efgTreeLayout::BuildNodeList(Node *p_node, const EFSupport &p_support,
				  int p_level)
{
  NodeEntry *entry = new NodeEntry(p_node);
  m_nodeList += entry;
  entry->SetLevel(p_level);
  if (p_node->NumChildren() > 0) {
    for (int i = 1; i <= p_node->NumChildren(); i++) {
      BuildNodeList(p_node->GetChild(i), p_support, p_level + 1);
    }
  }
  m_maxLevel = gmax(p_level, m_maxLevel);
}

void efgTreeLayout::BuildNodeList(const EFSupport &p_support)
{
  while (m_nodeList.Length() > 0) {
    delete m_nodeList.Remove(1);
  }

  m_maxLevel = 0;
  BuildNodeList(m_efg.RootNode(), p_support, 0);
}


void efgTreeLayout::GenerateLabels(void)
{
  const TreeDrawSettings &settings = m_parent->DrawSettings();
  for (int i = 1; i <= m_nodeList.Length(); i++) {
    NodeEntry *entry = m_nodeList[i];
    entry->SetNodeAboveLabel(CreateNodeAboveLabel(entry));
    entry->SetNodeAboveFont(settings.NodeAboveFont());
    entry->SetNodeBelowLabel(CreateNodeBelowLabel(entry));
    entry->SetNodeBelowFont(settings.NodeBelowFont());
    entry->SetNodeRightLabel(CreateNodeRightLabel(entry));
    entry->SetNodeRightFont(settings.NodeRightFont());
    if (entry->GetChildNumber() > 0) {
      entry->SetBranchAboveLabel(CreateBranchAboveLabel(entry));
      entry->SetBranchAboveFont(settings.BranchAboveFont());
      entry->SetBranchBelowLabel(CreateBranchBelowLabel(entry));
      entry->SetBranchBelowFont(settings.BranchBelowFont());
      entry->SetActionProb(m_parent->Parent()->ActionProb(entry->GetNode()->GetParent(),
							  entry->GetChildNumber()));
    }
  }
}

//
// RenderSubtree: Render branches and labels
//
// The following speed optimizations have been added:
// The algorithm now traverses the tree as a linear linked list, eliminating
// expensive searches.
//
// There was some clipping code in here, but it didn't correctly
// deal with drawing information sets while scrolling.  So, the code
// has temporarily been removed.  It remains to be seen whether
// performance will require a more sophisticated solution to the
// problem.  (TLT 5/2001)
//
void efgTreeLayout::RenderSubtree(wxDC &p_dc) const
{
  const TreeDrawSettings &settings = m_parent->DrawSettings();

  for (int pos = 1; pos <= m_nodeList.Length(); pos++) {
    NodeEntry *entry = m_nodeList[pos];  
    NodeEntry *parentEntry = entry->GetParent();
        
    if (entry->GetChildNumber() == 1) {
      parentEntry->Draw(p_dc);

      if (m_parent->DrawSettings().InfosetConnect() != INFOSET_CONNECT_NONE &&
	  parentEntry->GetNextMember()) {
	int nextX = parentEntry->GetNextMember()->X();
	int nextY = parentEntry->GetNextMember()->Y();

	if ((m_parent->DrawSettings().InfosetConnect() !=
	     INFOSET_CONNECT_SAMELEVEL) ||
	    parentEntry->X() == nextX) {
#ifdef __WXGTK__
	  // A problem with using styled pens and user scaling on wxGTK
	  p_dc.SetPen(wxPen(parentEntry->GetColor(), 1, wxSOLID));
#else
	  p_dc.SetPen(wxPen(parentEntry->GetColor(), 1, wxDOT));
#endif   // __WXGTK__
	  p_dc.DrawLine(parentEntry->X(), parentEntry->Y(), 
			parentEntry->X(), nextY);
	  if (settings.InfosetJoin() == INFOSET_JOIN_CIRCLES) {
	    p_dc.DrawLine(parentEntry->X() + parentEntry->GetSize(), 
			  parentEntry->Y(),
			  parentEntry->X() + parentEntry->GetSize(), 
			  nextY);
	  }

	  if (parentEntry->GetNextMember()->X() != parentEntry->X()) {
	    // Draw a little arrow in the direction of the iset.
	    int startX, endX; 
	    if (settings.InfosetJoin() == INFOSET_JOIN_LINES) {
	      startX = parentEntry->X();
	      endX = (startX + m_infosetSpacing * 
		      ((parentEntry->GetNextMember()->X() > 
			parentEntry->X()) ? 1 : -1));
	    }
	    else {
	      if (parentEntry->GetNextMember()->X() < parentEntry->X()) {
		// information set is continued to the left
		startX = parentEntry->X() + parentEntry->GetSize();
		endX = parentEntry->X() - m_infosetSpacing;
	      }
	      else {
		// information set is continued to the right
		startX = parentEntry->X();
		endX = (parentEntry->X() + parentEntry->GetSize() + 
			m_infosetSpacing);
	      }
	    }
	    p_dc.DrawLine(startX, nextY, endX, nextY);
	    if (startX > endX) {
	      p_dc.DrawLine(endX, nextY, endX + m_infosetSpacing / 2,
			    nextY + m_infosetSpacing / 2);
	      p_dc.DrawLine(endX, nextY, endX + m_infosetSpacing / 2,
			    nextY - m_infosetSpacing / 2);
	    }
	    else {
	      p_dc.DrawLine(endX, nextY, endX - m_infosetSpacing / 2,
			    nextY + m_infosetSpacing / 2);
	      p_dc.DrawLine(endX, nextY, endX - m_infosetSpacing / 2,
			    nextY - m_infosetSpacing / 2);
	    }
	  }
	}
      }
    }

    if (entry->GetNode()->NumChildren() == 0) {
      entry->Draw(p_dc);
    }

  }
}

void efgTreeLayout::Render(wxDC &p_dc) const
{ 
  RenderSubtree(p_dc);
}

void efgTreeLayout::SetCutNode(Node *p_node, bool p_cut)
{
  for (int i = 1; i <= m_nodeList.Length(); i++) {
    if (m_efg.IsPredecessor(p_node, m_nodeList[i]->GetNode())) {
      m_nodeList[i]->SetCut(p_cut);
    }
  }
}