// This file is not part of your solution; it is part of the problem.  Any
// changes you make to this file will be lost when you turn in your solution.


import java.util.Random;


class Graph {


  private final int adjacentNodes[][];


  void
  checkPairs(NodeRunnable nodes[]) {

    // Check the given set of nodes to make sure they're paired properly.  Do
    // nothing if they are; print an error message to std-err and die if they
    // aren't.

    assert nodes.length == adjacentNodes.length;

    for (int i = 0; i < nodes.length; i++)
      if (nodes[i].returnPartnerIndex() == i)
	noSingletonNeighbors(i, nodes);
      else 
	findPartner(i, nodes);	
    }


  private void
  findPartner(int nodeIndex, NodeRunnable nodes[]) {

    // 

    final int partnerIndex = nodes[nodeIndex].returnPartnerIndex();
    terror((partnerIndex < 0) || (nodes.length <= partnerIndex),
	   "Node " + nodeIndex + " claims node " + partnerIndex +
	   " as a partner, but " + partnerIndex + 
	   " is an invalid node index not in the range [0, " +
	   (nodes.length - 1) + "]");

    terror(nodes[partnerIndex].returnPartnerIndex() != nodeIndex,
	   "Node " + nodeIndex + " claims node " + partnerIndex +
	   " as a partner, but node " + partnerIndex + " claims node " +
	   nodes[partnerIndex].returnPartnerIndex() + " as a partner");

    int cnt = 0;
    for (int i = 0; i < adjacentNodes[i].length; i++)
      if (nodes[adjacentNodes[nodeIndex][i]].returnPartnerIndex() == nodeIndex) 
	cnt++;
    
    terror(cnt == 0,
	   "Node " + nodeIndex + " claims node " + partnerIndex +
	   " as a partner, but node " + partnerIndex + 
	   " is not a neighbor of node " + nodeIndex);

    terror(cnt > 1, "Node " + nodeIndex + " has " + cnt + 
	   " neighbors claiming it as a partner");
    }


  Graph(final int cnt, Random rint) {

    // Using the given random-number generator, create a random graph with the
    // given number of nodes.

    adjacentNodes = new int [cnt][];
    for (int i = 0; i < cnt; i++ ) {
      adjacentNodes[i] = new int [cnt];
      for (int j = 0; j < cnt; j++ )
	adjacentNodes[i][j] = -1;
      }      

    int i;

    for (i = rint.nextInt(cnt); i >= 0; i--)
      setPath(adjacentNodes, rint);

    for (i = 0; i < cnt; i++)
      partition(adjacentNodes[i]);

    if (false)
      for (i = 0; i < cnt; i++) {
	for (int j = 0; (j < cnt) && (adjacentNodes[i][j] > -1); j++ )
	  System.err.print(adjacentNodes[i][j] + " ");
	System.err.println("");
	}
    }


  private void 
  noSingletonNeighbors(int nodeIndex, NodeRunnable nodes[]) {

    // Check that the neighbors of the given, unpaired node are all paired,
    // printing a deadly error message of they're not.

    final int nbrs[] = adjacentNodes[nodeIndex];

    for (int i = 0; (i < nbrs.length) && (nbrs[i] > -1); i++)
      terror(nodes[nbrs[i]].returnPartnerIndex() == nbrs[i],
	     "Node " + nodeIndex + " claims no partners, but neighbor node " +
	     nbrs[i] + " is unpaired");
    }


  private void
  partition(int ints[]) {

    // Re-arrange the elements of the given vector so that all the non-negative
    // elements appear to the left of all the negative elements.

    int left = 0;
    int right = ints.length;

    // Invariant:  ints[0..left) > -1 and -1 >= ints[right..n).

    while (left < right) {
      final int r = right - 1;
      if (-1 >= ints[r]) 
	--right;
      else {
	int t = ints[r];
	ints[r] = ints[left];
	ints[left++] = t;
	}
      }
    }


  private int []
  permute(int cnt, Random rint) {

    // Return a random permutation of the numbers 0 to cnt - 1 using given
    // random-number generator.

    assert cnt > 0;

    final int perm [] = new int [cnt];
    int i;

    for (i = 0; i < cnt; i++ )
      perm[i] = i;
    
    for (i = (rint.nextInt(cnt) + 1)*cnt; i > 0; i--) {
      final int j = rint.nextInt(cnt);

      int k;
      do k = rint.nextInt(cnt);
      while (j == k);

      final int tmp = perm[k];
      perm[k] = perm[j];
      perm[j] = tmp;
      }

    return perm;
    }


  private void
  setPath(int adjacentNodes[][], Random rint) {

    // Using the given random-number generator, create a random path through
    // all the nodes in the given graph, then add the path edges to the graph.

    final int 
      nodeCount = adjacentNodes.length,
      path[] = permute(nodeCount, rint);

    for (int i = 1; i < nodeCount; i++ ) {
      final int 
	ni1 = path[i - 1],
	ni2 = path[i];
      adjacentNodes[ni1][ni2] = ni2;
      adjacentNodes[ni2][ni1] = ni1;
      }
    }


  private void 
  terror(boolean failed, String emsg) {
    
    // If the given test value failed, print the given error message and die;
    // otherwise, do nothing.

    if (failed) {
      System.err.println(emsg + ".");
      System.exit(1);
      }
    }


  void
  setNeighbors(int nodeIndex, NodeRunnable neighbors[], NodeRunnable nodes[]) {

    // Store into the given neighbors array the given node references that are
    // neighbors of the node with the given index.  Unused elements are set to
    // null.

    assert (0 <= nodeIndex) && (nodeIndex < adjacentNodes.length);

    final int nbrs[] = adjacentNodes[nodeIndex];
    int i;

    for (i = 0; (i < nbrs.length) && (nbrs[i] > -1); i++)
      neighbors[i] = nodes[nbrs[i]];

    for (i = nbrs.length; i < neighbors.length; i++)
      neighbors[i] = null;
    }
  }


// $Log: Graph.java,v $
// Revision 1.2  2003/08/08 23:57:18  rclayton
// Really generate random graphs; check for unpaired singleton nodes.
//