// Graph.java
// applet/application for displaying pointer graphs
// see (near) end of file for original copyright notice


import java.util.*;
import java.awt.*;
import java.awt.event.*;     // WindowListener
import java.applet.Applet;
import java.io.*;            // Serializable


// ===================== tty/listbox abstraction =======================
// generic output device
interface OutputDest {
  public void newReport();
  public void println(String s);
}

// output to debugging console
class ConsoleDest implements OutputDest {
  public void newReport() {}
  public void println(String s) {
    System.out.println(s);
  }
}

// output to a gui list box
class ListboxDest implements OutputDest {
  List list;

  public ListboxDest(List L)
  {
    list = L;
  }

  public void newReport()
  {
    list.removeAll();
  }

  public void println(String s)
  {
    list.add(s);
  }
}


// ======================== graph representation ===========================
// characterizes node neighbors
class Degree implements Serializable {
  // same constants as appear in Node class
  // (defines kinds of nodes)
  static final int STACK = Node.STACK;
  static final int DATA = Node.DATA;
  static final int HEAP = Node.HEAP;
  static final int SELF = Node.SELF;
  static final int OTHER = Node.OTHER;
  static final int NUM_KINDS = Node.NUM_KINDS;

  // both arrays indexed by STACK/DATA/HEAP/SELF/OTHER
  int from[];      // # of ptrs from each kind of obj
  int to[];        // # of ptrs to each kind of obj

  Degree()
  {
    from = new int[NUM_KINDS];
    to = new int[NUM_KINDS];
    clear();
  }

  void clear()
  {
    for (int i=0; i<NUM_KINDS; i++) {
      from[i] = 0;
      to[i] = 0;
    }
  }

  // copy ctor
  Degree(Degree obj)
  {
    from = new int[NUM_KINDS];
    to = new int[NUM_KINDS];
    for (int i=0; i<NUM_KINDS; i++) {
      from[i] = obj.from[i];
      to[i] = obj.to[i];
    }
  }

  // since we don't have macros, we have to rely on the
  // stack trace line numbers
  private void assert(boolean cond)
  {
    if (!cond) {
      throw new RuntimeException("assertion failed");
    }
  }

  public void checkInvariants()
  {
    for (int i=0; i<NUM_KINDS; i++) {
      assert(from[i] >= 0 && to[i] >= 0);      // counts are never negative
    }
    assert(from[SELF] == to[SELF]);
  }

  // memberwise equality
  public boolean equals(Object obj)
  {
    Degree o = (Degree)obj;
    for (int i=0; i<NUM_KINDS; i++) {
      if (from[i] != o.from[i] || to[i] != o.to[i]) {
        return false;
      }
    }
    return true;
  }

  // string representation for a single one of the two arrays
  private static String oneWayString(int arr[])
  {
    String lbl;
    lbl = "" + arr[STACK] + "/" +
               arr[DATA] + "/" +
               arr[HEAP];
    if (arr[OTHER] != 0) {          // expect 0 value always
      lbl = lbl + "/" + arr[OTHER];
    }
    return lbl;
  }

  public String inDegString() { return oneWayString(from); }
  public String outDegString() { return oneWayString(to); }

  public String toString()
  {
    String lbl = "in=" + inDegString() +
                 " out=" + outDegString();

    if (from[SELF] != 0) {       // from[SELF] == to[SELF]
      lbl = lbl + " (" + from[SELF] + ")";
    }

    return lbl;
  }


  // # of (other) objects that have ptrs to this one
  public int inDegree()
  {
    int sum=0;
    for (int i=0; i<NUM_KINDS; i++) {
      sum += from[i];
    }
    return sum - from[SELF];
  }


  // # of (other) objects at which this object points
  public int outDegree()
  {
    int sum=0;
    for (int i=0; i<NUM_KINDS; i++) {
      sum += to[i];
    }
    return sum - to[SELF];
  }


  // true if we (think we) can handle this node
  public boolean isPrunable()
  {
    // leaf node pointed-to by one thing
    if (inDegree() == 1 && outDegree() == 0) {
      return true;
    }

    // garbage (leaked)
    if (inDegree() == 0) {
      return true;
    }

    return false;
  }
}


// represents a single pointer graph node
class Node implements Serializable {
// package-access data
// (access level is as I found it, and haven't bothered to improve it yet)
  double x;        // location on screen, in pixels (fractional values
  double y;        // rounded before display)

  double dx;       // node's next-displacement, for relaxation algorithm
  double dy;

  boolean fixed;   // when true, this node is not moved by relaxation
  boolean hidden;  // when true, this node (nor any incident edges) is not displayed

  String lbl;      // node label
  String desc;     // slash-delimited trace, or null if there is none available

  static final int STACK = 0;
  static final int DATA = 1;
  static final int HEAP = 2;
  static final int SELF = 3;
  static final int OTHER = 4;
  static final int NUM_KINDS = 5;
  int sourceType;           // which kind of memory node this is

  // # of ptrs to/from this object from/to each kind of pointer-containing object
  Degree degree;


// methods
  public Node(double nx, double ny, String nlbl)
  {
    x = nx;
    y = ny;
    lbl = nlbl;
    switch (lbl.charAt(0)) {
      case 'd': sourceType = DATA;  break;
      case 's': sourceType = STACK; break;
      case '0': sourceType = HEAP;  break;    // e.g. 0x123
      default:  sourceType = OTHER; break;
    }

    // dx, dy, fixed, hidden remain at default values

    degree = new Degree();
  }

  public String fromsLabel()
  {
    return degree.toString();
  }

  // debugging dump (unwanted members commented-out)
  public String toString()
  {
    return "(x~=" + (int)x +
           " y~=" + (int)y +
           //" dx=" + dx +
           //" dy=" + dy +
           //" fixed=" + fixed +
           //" hidden=" + hidden +
           " lbl=" + lbl +
           //" desc=" + desc +
           //" sourceType=" + sourceType +
           " degree=" + degree +
           ")";
  }


  // set the description from a string found in a .g or .html file;
  // this description may contain a location first
  public void setLoadedDesc(String desc)
  {
    // check for location (identified by leading '@')
    if (desc.startsWith("@")) {
      // parse location
      String coords[] = Graph.parseString(desc.substring(1), ",; ");
      x = (double)Integer.parseInt(coords[0]);
      y = (double)Integer.parseInt(coords[1]);
      fixed = (desc.indexOf(";") != -1);

      // skip past it for real description
      int firstSpace = desc.indexOf(" ");
      if (firstSpace == -1) {
        // no desc. other than location
        desc = "";
      }
      else {
        desc = desc.substring(firstSpace+1);
      }
    }

    // set this node's description field
    this.desc = desc;
  }

  // return description suitable for .g or .html, i.e. it includes
  // the x,y info embedded within it (if desired)
  public String getDesc(boolean includeXY)
  {
    // get this node's desc, but use its label if it doesn't have one
    String desc = (this.desc==null? lbl : this.desc);

    if (!includeXY) {
      return desc;
    }
    else {
      // format: @<x>(,|;)<y> <desc>
      //   where separator is comma (,) for not-fixed,
      //   and semi-colon (;) for fixed
      String separator = fixed? ";" : ",";
      return "@" + ((int)x) + separator +
                   ((int)y) + " " + desc;
    }
  }
}


// represents a pointer in the pointer graph
class Edge implements Serializable {
// data
  // from/to are indices into the 'nodes' array in the parent GraphData object
  public int from;       // source
  public int to;         // target

  public double len;     // edge's desired length (almost always 50)

  public int count;      // # of edges represented (usually 1)


// methods
  public Edge(int f, int t, int L)
  {
    from = f;
    to = t;
    len = L;
    count = 1;
  }

  // for inclusion in hash table
  public boolean equals(Object obj)
  {
    Edge e = (Edge)obj;
    return from == e.from && to == e.to;
  }

  // for inclusion in hash table
  public int hashCode()
  {
    return from + (to >> 16);
  }

  // debugging dump
  public String toString()
  {
    return "(from=" + from +
           " to=" + to +
           //" len=" + len +
           " count=" + count +
           ")";
  }
}


// the graph data itself
class GraphData implements Serializable {
// private data
  // note: we assume that the nodes all have unique labels
  private int nnodes;          // # of nodes
  private Node nodes[];        // ptrs to the nodes; indices [0,nnodes-1]

  private int nedges;          // # of edges
  private Edge edges[];        // ptrs to the edges; indices [0,nedges-1]

  // maps node labels (String) to array indices (Integer)
  private Hashtable labelMap;

  // maps edges (Edge) to themselves, compared by from/to
  private Hashtable edgeIdentity;

  // when true, additional checks are performed
  private static final boolean debug = true;

  // hack hack hack!
  private static final long serialVersionUID = -3841615961179505908L;


// private funcs
  private void growNodeArray()
  {
    Node arr[] = new Node[nodes.length * 2];    // alloc
    for (int i=0; i<nodes.length; i++) {
      arr[i] = nodes[i];                        // copy
    }
    nodes = arr;                                // replace
  }

  private void growEdgeArray()
  {
    Edge arr[] = new Edge[edges.length * 2];    // alloc
    for (int i=0; i<edges.length; i++) {
      arr[i] = edges[i];                        // copy
    }
    edges = arr;                                // replace
  }

// public funcs
  public GraphData()
  {
    nnodes = 0;
    nodes = new Node[50];     // arbitrary initial size; grows as necessary

    nedges = 0;
    edges = new Edge[100];

    labelMap = new Hashtable();
    edgeIdentity = new Hashtable();
  }

  // empty the graph
  public void reset()
  {
    // clear the arrays, so the objects can be deallocated
    for (int n=0; n<nnodes; n++) {
      nodes[n] = null;
    }
    for (int e=0; e<nedges; e++) {
      edges[e] = null;
    }

    nnodes = 0;
    nedges = 0;

    labelMap.clear();
    edgeIdentity.clear();
  }

  public int numNodes()         { return nnodes; }
  public Node getNode(int n)    { return nodes[n]; }
  public Node[] getNodeArray()  { return nodes; }

  public int numEdges()         { return nedges; }
  public Edge getEdge(int e)    { return edges[e]; }
  public Edge[] getEdgeArray()  { return edges; }

  // map node's label to its index; will add a new node if the
  // given label does not exist
  public int findNode(String lbl) {
    Integer i = (Integer)labelMap.get(lbl);
    if (i != null) {
      return i.intValue();
    }

    /* -- old, prior to hash table --
    for (int i = 0 ; i < nnodes ; i++) {
        if (nodes[i].lbl.equals(lbl)) {
            return i;
        }
    }
    */

    return addNode(lbl);
  }

  // map node reference to its index
  public int getNodeIndex(Node n)
  {
    int ret = findNode(n.lbl);
    assert(nodes[ret] == n);
    return ret;
  }

  // add a new node; 'lbl' must not already be used
  // (for public adding, use findNode)
  private int addNode(String lbl) {
    Node n = new Node(10 + 380*Math.random(),
                      10 + 380*Math.random(),
                      lbl);
    if (nnodes == nodes.length) {
      growNodeArray();
    }
    nodes[nnodes] = n;
    int retval = nnodes++;

    // add (name, index) to hashtable
    addToLabelMap(retval);

    return retval;
  }

  // add a single node, identified by its index, to the node hashtable
  private void addToLabelMap(int node)
  {
    labelMap.put(nodes[node].lbl, new Integer(node));
  }


  public void addEdge(String from, String to) {
    addEdge(from, to, 50 /*default len*/);
  }

  // add a new edge
  public void addEdge(String from, String to, int len) {
    int prevNnodes = nnodes;    // used below to detect node creation
    int f = findNode(from);
    int t = findNode(to);
    if (f != t) {
      // increment degrees
      nodes[t].degree.from[nodes[f].sourceType]++;
      nodes[f].degree.to[nodes[t].sourceType]++;

      // create the Edge object, in anticipation of adding it to the
      // array, but also so we can do a hashtable search with it
      Edge newEdge = new Edge(f, t, len);

      // see if the edge already exists
      Edge already = (Edge)edgeIdentity.get(newEdge);
      if (already != null) {
        // already exists; increment its count, and drop newEdge on the floor
        already.count++;
        return;
      }

      /* -- old, prior to hash table --
      for (int i=0; i<nedges; i++) {
        if (edges[i].from == f &&
            edges[i].to == t) {
          // simply increment its count
          edges[i].count++;
          return;
        }
      }
      */

      // edge doesn't already exist; add it to the array
      if (nedges == edges.length) {
        growEdgeArray();
      }
      edges[nedges++] = newEdge;

      // and add it to the hashtable
      edgeIdentity.put(newEdge, newEdge);
    }

    else {
      // from == to

      // we can't add a self-edge because the relaxation
      // code can't handle it

      // find the node with the self-edge
      int n = findNode(from);
      if (prevNnodes != nnodes) {
        // found it by adding it; it is possible this node isn't
        // connected to anything else, so let's prevent it from
        // floating away
        nodes[n].fixed = true;
        //System.out.println("making node " + from + " fixed");
      }

      // increment degree counts (from[SELF] == to[SELF])
      nodes[n].degree.from[Node.SELF]++;
      nodes[n].degree.to[Node.SELF]++;

      // debugging printf
      //System.out.println("self-edge: from=" + from + ", to=" + to);
    }
  }


  // like above
  private void assert(boolean cond)
  {
    if (!cond) {
      throw new RuntimeException("assertion failed");
    }
  }


  // remove an edge, named by its index
  // time: O(1)
  public void removeEdge(int edge)
  {
    assert(0 <= edge &&
                edge < nedges);

    // remove edge from hash table
    edgeIdentity.remove(edges[edge]);

    // decrement the degrees of the incident nodes
    Node to = nodes[edges[edge].to];
    Node from = nodes[edges[edge].from];
    to.degree.from[from.sourceType]--;
    from.degree.to[to.sourceType]--;
    if (debug) {
      to.degree.checkInvariants();
      from.degree.checkInvariants();
    }

    // since we don't retain permanent references to edges by their
    // indices, we can simply swap the last edge with the one being
    // removed, to keep the array contiguous

    int last = nedges-1;
    edges[edge] = edges[last];     // move last into position being vacated
                                   // (harmless if edge == last)
    nedges--;                      // now there is one less edge
  }

  // remove all edges adjacent to some node (named by its index)
  // time: O(E)
  public void removeAdjacentEdges(int node)
  {
    int e=0;
    while (e < nedges) {
      if (edges[e].from == node ||
          edges[e].to == node) {
        removeEdge(e);
          // this swaps a new edge into position 'e', so we don't e++
      }
      else {
        e++;
      }
    }
  }


  // remove a node, named by its index
  // time: O(E)
  public void removeNode(int node)
  {
    assert(0 <= node &&
                node < nnodes);

    // must remove all adjacent edges first, because it will be inconvenient
    // to do so when we sweep through the edges again below
    removeAdjacentEdges(node);

    // remove node from the hashtable
    labelMap.remove(nodes[node].lbl);

    // swap node with last (unless already *is* last)
    int lastNode = nnodes-1;
    if (lastNode != node) {
      nodes[node] = nodes[lastNode];

      // now we need to adjust all the edges that are incident upon the
      // node whose index we just moved
      for (int e=0; e<nedges; e++) {
        Edge E = edges[e];
        if (E.from == lastNode || E.to == lastNode) {
          // we need to modify this edge's from/to

          // this was a SUBTLE BUG because the edge's hash code depends on the
          // from/to values, so we must remove and reinsert!
          edgeIdentity.remove(E);       // still has old from/to

          if (E.from == lastNode) {
            E.from = node;
          }
          if (E.to == lastNode) {
            E.to = node;
          }

          edgeIdentity.put(E, E);       // reinsert with new from/to
        }
      }

      // the hashtable for the moved node needs to be updated to reflect
      // that its index has changed
      addToLabelMap(node);
    }

    // there is now one less node
    nnodes--;
  }


  // assert that all the invariants hold
  // (some invariants (specifically degree correctness) aren't checked)
  public void checkInvariants()
  {
    // basic size constraints
    assert(0 <= nnodes &&
                nnodes <= nodes.length);
    assert(0 <= nedges &&
                nedges <= edges.length);

    // check nodes
    for (int n=0; n<nnodes; n++) {
      // no null entries where there shouldn't be
      assert(nodes[n] != null);

      // must be in hashtable
      assert( ((Integer)(labelMap.get(nodes[n].lbl))).intValue() == n );

      // degrees must at least make sense
      nodes[n].degree.checkInvariants();
    }
    assert(labelMap.size() == nnodes);

    // check edges
    for (int e=0; e<nedges; e++) {
      // no nulls
      Edge E = edges[e];
      assert(E != null);

      // valid node references
      assert(0 <= E.from &&
                  E.from < nnodes);
      assert(0 <= E.to &&
                  E.to < nnodes);

      // must be in hashtable
      if (edgeIdentity.get(E) != E) {
        // I had trouble here, so I elaborated
        throw new RuntimeException(
          "edgeIdentity.get(E) != E: "+
          "edgeIdentity.get(E) = " + edgeIdentity.get(E) +
          " but E = " + E);
      }
    }
    assert(edgeIdentity.size() == nedges);
  }

  // check the invariants only when debug is true
  public void debugCheckInvariants()
  {
    if (debug) {
      checkInvariants();
    }
  }


  // debugging dump
  public String toString()
  {
    StringBuffer buf = new StringBuffer();     // initially empty

    buf.append("Nodes:\n");
    for (int n=0; n<nnodes; n++) {
      buf.append("  " + n + ": ")
         .append(nodes[n].toString())
         .append("\n");
    }

    buf.append("Edges:\n");
    for (int e=0; e<nedges; e++) {
      buf.append("  ")
         .append(edges[e].toString())
         .append("\n");
    }

    buf.append("labelMap: ").append(labelMap.toString()).append("\n");
    buf.append("edgeIdentity: ").append(edgeIdentity.toString()).append("\n");

    return buf.toString();
  }


  // return a node, chosen uniformly at random
  public Node randomNode() {
    return nodes[(int)(Math.random() * nnodes)];
  }


  // this method attempts to, a little at a time, spread the nodes out
  // in a way that reveals the structure of the graph as a whole; I didn't
  // write any of this, except the checks to skip hidden nodes; there are
  // three basic tendencies here:
  //   1) nodes repel each other
  //   2) edges have a certain natural length (usually 50 pixels)
  //   3) there is some random jitter
  public void relax(Dimension d) {
      for (int i = 0 ; i < nedges ; i++) {
          Edge e = edges[i];

          if (nodes[e.to].hidden || nodes[e.from].hidden) {
            continue;
          }

          double vx = nodes[e.to].x - nodes[e.from].x;
          double vy = nodes[e.to].y - nodes[e.from].y;
          double len = Math.sqrt(vx * vx + vy * vy);
          double f = (edges[i].len - len) / (len * 3) ;
          double dx = f * vx;
          double dy = f * vy;

          nodes[e.to].dx += dx;
          nodes[e.to].dy += dy;
          nodes[e.from].dx += -dx;
          nodes[e.from].dy += -dy;
      }

      for (int i = 0 ; i < nnodes ; i++) {
          Node n1 = nodes[i];
          if (n1.hidden) {
            continue;
          }

          double dx = 0;
          double dy = 0;

          for (int j = 0 ; j < nnodes ; j++) {
              if (i == j) {
                  continue;
              }
              Node n2 = nodes[j];
              if (n2.hidden) {
                continue;
              }
              double vx = n1.x - n2.x;
              double vy = n1.y - n2.y;
              double len = vx * vx + vy * vy;
              if (len == 0) {
                  dx += Math.random();
                  dy += Math.random();
              } else if (len < 100*100) {
                  dx += vx / len;
                  dy += vy / len;
              }
          }
          double dlen = dx * dx + dy * dy;
          if (dlen > 0) {
              dlen = Math.sqrt(dlen) / 2;
              n1.dx += dx / dlen;
              n1.dy += dy / dlen;
          }
      }

      for (int i = 0 ; i < nnodes ; i++) {
          Node n = nodes[i];
          if (n.hidden) {
            continue;
          }
          if (!n.fixed) {
              n.x += Math.max(-5, Math.min(5, n.dx));
              n.y += Math.max(-5, Math.min(5, n.dy));
              //System.out.println("v= " + n.dx + "," + n.dy);
              if (n.x < 0) {
                  n.x = 0;
              } else if (n.x > d.width) {
                  n.x = d.width;
              }
              if (n.y < 0) {
                  n.y = 0;
              } else if (n.y > d.height) {
                  n.y = d.height;
              }
          }
          n.dx /= 2;
          n.dy /= 2;
      }
  }

  // find the node closest to a given coordinate but not hidden
  // (may return null if all nodes are hidden)
  public Node closest(int x, int y)
  {
    Node pick = null;
    double bestdist = Double.MAX_VALUE;
    for (int i = 0 ; i < nnodes ; i++) {
        Node n = nodes[i];
        double dist = (n.x - x) * (n.x - x) + (n.y - y) * (n.y - y);
        if (dist < bestdist && !n.hidden) {
            pick = n;
            bestdist = dist;
        }
    }
    return pick;
  }

  // all (non-fixed) nodes are positioned randomly
  public void scramble(Dimension d)
  {
    for (int i = 0 ; i < nnodes ; i++) {
        Node n = nodes[i];
        if (!n.fixed) {
            n.x = 10 + (d.width-20)*Math.random();
            n.y = 10 + (d.height-20)*Math.random();
        }
    }
  }

  // all nodes get a random push
  public void shake()
  {
    for (int i = 0 ; i < nnodes ; i++) {
        Node n = nodes[i];
        if (!n.fixed) {
            n.x += 80*Math.random() - 40;
            n.y += 80*Math.random() - 40;
        }
    }
  }


  // toggle 'hidden' status of nodes with specified degree
  public void toggleHidden(Degree degree)
  {
    for (int n=0; n<nnodes; n++) {
      if (nodes[n].degree.equals(degree)) {
        nodes[n].hidden = !nodes[n].hidden;
      }
    }
  }

  public void unhideAll()
  {
    for (int n=0; n<nnodes; n++) {
      nodes[n].hidden = false;
    }
  }

  // unhide all nodes sharing an edge with this one
  public void showNeighbors(Node node)
  {
    for (int e=0; e<nedges; e++) {
      Node f = nodes[edges[e].from];
      Node t = nodes[edges[e].to];
      if (f == node || t == node) {     // 'node' is a neighbor of 't' or 'f'
        f.hidden = false;                 // unhide both
        t.hidden = false;
      }
    }
  }

  // hide neighbors that have the specified degree
  public void hideCertainNeighbors(Node node, Degree degree)
  {
    for (int e=0; e<nedges; e++) {
      Node f = nodes[edges[e].from];
      Node t = nodes[edges[e].to];
      if (f == node || t == node) {     // 'node' is a neighbor of 't' or 'f'
        if (f != node && f.degree.equals(degree)) {
          f.hidden = true;                // hide 'f'
        }
        if (t != node && t.degree.equals(degree)) {
          t.hidden = true;                // hide 't'
        }
      }
    }
  }


  // delete nodes with specified degree
  // time: O(V*E)
  public void deleteWithDegree(Degree degree)
  {
    int n=0;
    while (n < nnodes) {
      if (nodes[n].degree.equals(degree)) {
        removeNode(n);
        // don't n++ because removal swaps a new node into position 'n'
      }
      else {
        n++;
      }
    }

    debugCheckInvariants();
  }


  // throw away "uninteresting" nodes until no more can be pruned
  public void prune()
  {
    int prevNodes = -1;    // # of nodes during previous round
    for (int round=1; nnodes != prevNodes; round++) {
      prevNodes = nnodes;
      System.out.println("round " + round + ": " +
                         nnodes + " nodes and " +
                         nedges + " edges");
      pruneOnce();
    }
  }

  // one round of pruning
  public void pruneOnce()
  {
    // copy + paste from above.. does Java have a convenient closure mechanism?
    int n=0;
    while (n < nnodes) {
      if (nodes[n].degree.isPrunable()) {
        removeNode(n);
        // don't n++ because removal swaps a new node into position 'n'
      }
      else {
        n++;
      }
    }

    debugCheckInvariants();
  }


  // move nodes with the named degree to x,y
  public void moveSomeNodes(Degree degree, double x, double y)
  {
    for (int n=0; n<nnodes; n++) {
      Node N = nodes[n];
      if (degree.equals(N.degree)) {
        N.x = x;
        N.y = y;
      }
    }
  }


  // print a histogram of the already-computed node degrees;
  // it's not sorted at this time
  public void printHistogram(OutputDest dest)
  {
    // for each distinct degree (degree[i]) appearing in the graph,
    // hist[i] is the number of nodes with that degree; the array size
    // is usually much larger than necessary, but it is an accurate
    // worst-case size
    int hist[] = new int[nnodes];
    Degree degree[] = new Degree[nnodes];
    int histsize = 0;       // # of distinct degrees found so far

    // gather statistics
    for (int n=0; n<nnodes; n++) {
      Degree deg = nodes[n].degree;

      // don't print stats for the stack or data itself
      if (nodes[n].sourceType != Node.HEAP) {
        continue;
      }

      // see if an existing entry has the same degree
      int i;
      for (i=0; i<histsize; i++) {
        if (degree[i].equals(deg)) {
          // found it; increment its count
          hist[i]++;
          break;
        }
      }

      if (i == histsize) {
        // didn't find an entry; add a new one
        hist[i] = 1;
        degree[i] = deg;     // refers to object's copy; not a problem
        histsize++;
      }
    }

    // print it; this only makes nice columns in a fixed-width font, but
    // I don't know how to change the font of a listbox (on some systems,
    // it is fixed-width by default; but on NT it is not)
    dest.newReport();
    dest.println("          ******** from *********  ********** to *********");
    dest.println("count     stack  data  heap  self  stack  data  heap  self");
    dest.println("--------  -----  ----  ----  ----  -----  ----  ----  ----");
    for (int i=0; i<histsize; i++) {
      String s = "";
      s = s + printNum(hist[i], 8);     // count

      for (int j=0; j<2; j++) {
        int arr[] = j==0? degree[i].from : degree[i].to;
        s = s + printNum(arr[Node.STACK], 5);
        s = s + printNum(arr[Node.DATA], 4);
        s = s + printNum(arr[Node.HEAP], 4);
        s = s + printNum(arr[Node.SELF], 4);
      }

      /*      don't care about 'other' anymore
      if (degree[i].from[Node.OTHER] != 0) {
        s = s + printNum(degree[i].from[Node.OTHER], 8);
      }
      */

      dest.println(s);
    }
  }

  // return a string representing an integer, but padded to a fixed width
  // (and a column divider is appended, also)
  static private String printNum(int n, int width)
  {
    String s = "" + n;            // convert to string
    String pad = "";
    for (int i=s.length(); i<width; i++) {
      pad = pad + " ";            // padding
    }
    return pad + s + "  ";        // 2 spaces for column divider
  }


  // save graph to my .g format
  public void save(String fname, boolean saveXY) throws IOException
  {
    // open the file
    PrintWriter dest =
      new PrintWriter(
        new FileOutputStream(fname));

    // write edges; format:
    //   e <from-index> <to-index>
    for (int e=0; e<nedges; e++) {
      Node f = nodes[edges[e].from];
      Node t = nodes[edges[e].to];
      if (!f.hidden && !t.hidden) {
        for (int c=0; c < edges[e].count; c++) {
          dest.println("e " + f.lbl + " " + t.lbl);
        }
      }
    }

    // write nodes; format:
    //   n <label> <desc>
    for (int n=0; n<nnodes; n++) {
      Node N = nodes[n];
      if (!N.hidden) {
        dest.println("n " + N.lbl + " " + N.getDesc(saveXY));

        // add the self-edges
        for (int c=0; c < N.degree.from[Node.SELF]; c++) {
          dest.println("e " + N.lbl + " " + N.lbl);
        }
      }
    }

    // close file
    dest.close();
  }


  // convenient alias
  private static long time()
  {
    return System.currentTimeMillis();
  }

  // load my .g format into graph
  public void load(String fname) throws IOException
  {
    // profiling variables
    long start;
    long parseTime=0, edgeTime=0, nodeTime=0;
    long allStart = time();

    // open the file
    BufferedReader source =
      new BufferedReader(
        new FileReader(fname));

    // clear existing graph
    reset();

    // loop over input lines
    for(int line = 1; ; line++) {
      // read, parse line
      start = time();
      String inputLine = source.readLine();
      if (inputLine == null) {
        break;     // eof
      }
      String words[] = Graph.parseString(inputLine);
      parseTime += time() - start;

      // interpret it
      String bad = null;
      try {
        if (words[0].equals("e")) {          // edge
          start = time();
          addEdge(words[1] /*from*/, words[2] /*to*/);
          edgeTime += time() - start;
        }
        else if (words[0].equals("n")) {     // node
          start = time();
          int n = findNode(words[1]);

          // the description is *not* simply words[2], because it may have
          // embedded spaces.. so we search for the 2nd space that occurs
          // in the original string, and take the desc as all following chars
          int spacesToSkip = 2;
          int index = 0;
          while (spacesToSkip > 0 && index != -1) {
            index = inputLine.indexOf(" ", index+1);
            spacesToSkip--;
          }

          if (index == -1) {
            bad = "failed to find needed # of spaces";
          }
          else {
            // description begins after last space
            nodes[n].setLoadedDesc(inputLine.substring(index+1));
          }

          nodeTime += time() - start;
        }
        else {
          bad = "unknown data line code: " + words[0];
        }
      }
      catch (Exception e) {
        bad = e.toString();
      }

      if (bad != null) {
        System.out.println(fname + " " + line + ": " + bad);
      }
    }

    // print stats on loading
    System.out.println(fname + " has " + nnodes + " nodes and " + nedges + " edges");

    /*   -- it's fast enough for now, so I don't want to see profiling info --
    System.out.println("allTime=" + (time()-allStart) +
                       " parseTime=" + parseTime +
                       " edgeTime=" + edgeTime +
                       " nodeTime=" + nodeTime);
    */

    // close file
    source.close();

    // verify it all makes sense
    debugCheckInvariants();
  }
}


// ================ graphical user interface ==============================
// the panel is primary display sitting inside the applet window
class GraphPanel extends Panel
  implements Runnable,          // 'run' method for the relaxation thread
             ActionListener {   // 'actionPerformed' for right-click-menu response
// data
  Graph applet;       // applet containing this panel
  GraphData data;     // graph data itself

  Thread relaxer;             // reference to myself as a thread, to stop it
  boolean killRelaxer = false;  // way to stop the relaxer when it's safe

  boolean stress = true;      // this now controls display of edge-count
  boolean doRelax;            // when true, the relaxation algorithm runs
  boolean hide0x = false;     // that's zero-ex (0x), not oh-ex (Ox)
  boolean showFroms = false;  // show the fromKind data, instead of labels, for heap objs

  // interface to the histogram window
  public Degree highlightDegree = new Degree();     // degree stats to highlight
  public int highlightLine = 0;                     // highlighted histogram line

  Node rightSelected;         // node last right-clicked on

  Node pick;                  // node currently being dragged
  boolean pickfixed;          // holds 'pick's 'fixed' field (since it set to
                              // true during a drag operation)
  Image offscreen;            // hidden buffer to avoid display flicker
  Dimension offscreensize;    // size of the image to construct
  Graphics offgraphics;       // graphics context for the 'offscreen' image

// methods
  GraphPanel(Graph applet) {
      this.applet = applet;
      doRelax = applet.defaultDoRelax;     // little hacky, oh well
      data = new GraphData();
  }

  // relaxation thread entry point
  public void run() {
    try {
      // when doRelax is true, there is a race condition that causes all
      // the nodes to appear to be in the upper-left corner, but still not
      // retrievable by dragging; I can't find the bug, so this hack prevents
      // the relaxer from running immediately
      Thread.sleep(1000);

      while (!killRelaxer) {
        if (doRelax) {
          relax();
        }
        Thread.sleep(100);
      }
    } catch (InterruptedException e)
      {}
  }

  // the synchronization model appears to be based on protecting
  // the graph data from inconsistent modification
  synchronized void relax() {
      data.relax(size());
      repaint();
  }


  // browser-to-applet messages
  public void start() {
      relaxer = new Thread(this);
      relaxer.start();
  }
  public void stop() {
      relaxer.stop();
  }


  // I changed the colors to make them all close to yellow,
  // so they print nicely on black and white

  //final Color fixedColor = Color.red;
  final Color fixedColor = new Color(250, 220, 200);
  final Color highlightColor = Color.red;
  final Color selectColor = Color.pink;
  final Color edgeColor = Color.black;
  final Color nodeColor = new Color(250, 220, 100);
  final Color stressColor = Color.darkGray;
  final Color arcColor1 = Color.black;
  final Color arcColor2 = Color.pink;
  final Color arcColor3 = Color.red;

  // debug printf
  private void diagnostic(String s)
  {
    System.out.println(s);
  }

  // draw a node
  public void paintNode(Graphics g, Node n, FontMetrics fm) {
    //diagnostic("paintNode called");

    int x = (int)n.x;
    int y = (int)n.y;
    g.setColor(n == pick                          ? selectColor    :
               n.degree.equals(highlightDegree)   ? highlightColor :
               n.fixed                            ? fixedColor     :
                                                    nodeColor      );

    String lbl = n.lbl;
    if (hide0x && n.sourceType == Node.HEAP) {
      lbl = "";      // make node graphics smaller
    }

    if (showFroms && n.sourceType == Node.HEAP) {
      lbl = n.fromsLabel();
    }

    int w = fm.stringWidth(lbl) + 10;
    int h = fm.getHeight() + 4;
    g.fillRect(x - w/2, y - h / 2, w, h);
    g.setColor(Color.black);
    g.drawRect(x - w/2, y - h / 2, w-1, h-1);
    g.drawString(lbl, x - (w-10)/2, (y - (h-4)/2) + fm.getAscent());
  }


  // apparently, paint() is only called when the window is uncovered (etc.),
  // whereas update() is called in response to repaint()
  // synchronized so we don't update & paint at the same time
  public synchronized void paint(Graphics g)
  {
    // restore from offscreen image
    if (offscreen != null) {
      // copy the hidden buffer to the screen
      g.drawImage(offscreen, 0, 0, null /*observer*/);
    }
  }


  // synchronized because we don't want to draw with things changing
  public synchronized void update(Graphics g) {
    Dimension d = size();       // current panel size
    if ((offscreen == null) ||
        (d.width != offscreensize.width) ||
        (d.height != offscreensize.height)) {
      // offscreen image needs to be created
      offscreen = createImage(d.width, d.height);
      offscreensize = d;
      offgraphics = offscreen.getGraphics();
      offgraphics.setFont(getFont());
    }

    // copy data's variables for local access
    // (the arrays are not modified; wish Java had "const")
    int nnodes = data.numNodes();
    Node[] nodes = data.getNodeArray();
    int nedges = data.numEdges();
    Edge[] edges = data.getEdgeArray();

    // clear the image
    offgraphics.setColor(getBackground());
    offgraphics.fillRect(0, 0, d.width, d.height);

    // paint the edges first, so the nodes will be on top of them
    for (int i = 0 ; i < nedges ; i++) {
      Edge e = edges[i];

      // don't draw the edge if either node is hidden
      if (nodes[e.from].hidden || nodes[e.to].hidden) {
        continue;
      }

      // retrieve line endpoints
      int x1 = (int)nodes[e.from].x;
      int y1 = (int)nodes[e.from].y;
      int x2 = (int)nodes[e.to].x;
      int y2 = (int)nodes[e.to].y;

      // this calculation sets the edge color based on how far its length
      // deviates from its desired length; I don't care about this anymore,
      // but may as well leave it
      int len = (int)Math.abs(Math.sqrt((x1-x2)*(x1-x2) + (y1-y2)*(y1-y2)) - e.len);
      offgraphics.setColor((len < 10) ? arcColor1 : (len < 20 ? arcColor2 : arcColor3)) ;

      // draw the line
      offgraphics.drawLine(x1, y1, x2, y2);

      // draw a number near the edge
      if (stress && e.count != 1) {
        // old: stress value
        //String lbl = String.valueOf(len);

        // new: edge count
        String lbl = "" + e.count;

        offgraphics.setColor(stressColor);
        offgraphics.drawString(lbl, x1 + (x2-x1)/2, y1 + (y2-y1)/2);
        offgraphics.setColor(edgeColor);
      }

      // direction indicator: blue at target
      int mx = (x1+x2)/2;
      int my = (y1+y2)/2;
      offgraphics.setColor(Color.blue);

      // color alone isn't sufficient; I want it thick, too
      for(int dx=-1; dx<=1; dx++) {
        for(int dy=-1; dy<=1; dy++) {
          offgraphics.drawLine(mx+dx,my+dy, x2+dx,y2+dy);
        }
      }
    }

    // now, draw the nodes
    FontMetrics fm = offgraphics.getFontMetrics();
    for (int i = 0 ; i < nnodes ; i++) {
      if (!nodes[i].hidden) {
        paintNode(offgraphics, nodes[i], fm);
      }
    }

    // copy the hidden buffer to the screen
    g.drawImage(offscreen, 0, 0, null /*observer*/);
  }

  public synchronized boolean mouseDown(Event evt, int x, int y) {
    //System.out.println("mouseDown: " + evt.metaDown());

    if (pick != null) {
      // second mouse-press while first still held: toggle fixed
      pickfixed = !pickfixed;
      return true;
    }

    // hit-test
    pick = data.closest(x, y);
    if (pick == null) {
      return true;        // can happen if all nodes are hidden
    }

    if (evt.metaDown()) {        // right-click, as opposed to left-click
      // bring up a menu for this node
      rightSelected = pick;
      PopupMenu pmenu = new PopupMenu(pick.lbl);
      pmenu.add("Show Neighbors");   // note label dependency below
      pmenu.add("Hide Red Neighbors");
      pmenu.add("Hide Me");
      pmenu.add("Delete Me");
      pmenu.add("Move Red Here");
      pmenu.addActionListener(this);
      add(pmenu);                    // THIS IS ESSENTIAL!
      pmenu.show(this, x, y);        // show the menu here
      pick = null;                   // don't drag it when we select a menu option
      return true;
    }

    // used to load trace via getParameter here, but now I load
    // them all during HTML reading, to pick up x,y info

    // print trace
    OutputDest output = new ListboxDest(applet.traceList);
    output.newReport();
    if (pick.desc == null) {
      output.println(pick.lbl + " has no trace info");
    }
    else {
      output.println(pick.lbl + ":");
      for (StringTokenizer t = new StringTokenizer(pick.desc, "/") ; t.hasMoreTokens() ; ) {
        output.println(t.nextToken());
      }
    }

    pickfixed = pick.fixed;
    pick.fixed = true;
    pick.x = x;
    pick.y = y;
    repaint();
    return true;
  }


  // called when the right-click popup menu selection is made
  public synchronized void actionPerformed(ActionEvent evt)
  {
    // NOTE label text dependency with above
    String cmd = evt.getActionCommand();
    if (cmd.equals("Show Neighbors")) {
      data.showNeighbors(rightSelected);
    }
    else if (cmd.equals("Hide Red Neighbors")) {
      data.hideCertainNeighbors(rightSelected, highlightDegree);
    }
    else if (cmd.equals("Hide Me")) {
      rightSelected.hidden = true;
    }
    else if (cmd.equals("Delete Me")) {
      data.removeNode(data.getNodeIndex(rightSelected));
      applet.updateHistogram();
    }
    else if (cmd.equals("Move Red Here")) {
      data.moveSomeNodes(highlightDegree, rightSelected.x, rightSelected.y);
    }
    else {
      System.out.println("actionPerformed: " + evt);     // ?
      return;     // don't repaint
    }

    repaint();
  }


  public synchronized boolean mouseDrag(Event evt, int x, int y) {
    if (pick != null) {
      pick.x = x;
      pick.y = y;
    }
    repaint();
    return true;
  }

  public synchronized boolean mouseUp(Event evt, int x, int y) {
    if (pick != null) {
      pick.x = x;
      pick.y = y;
      pick.fixed = pickfixed;
      pick = null;
    }

    repaint();
    return true;
  }


  // toggle the 'hidden' status of all nodes in the highlighted row of histogram
  public synchronized void toggleHidden()
  {
    // toggle the hidden states
    data.toggleHidden(highlightDegree);

    // modify the histogram window to tag hidden lines
    String s = applet.histogram.getItem(highlightLine);
    char first = s.charAt(0);
    first = (first==' '? '*' : ' ');     // * means hidden
    s = "" + first + s.substring(1);     // change first character
    int temp = applet.histogram.getSelectedIndex();
    applet.histogram.replaceItem(s, highlightLine);
    applet.histogram.select(temp);        // keep the same item selected

    // redraw to show change to what is hidden
    repaint();
  }

  // delete the nodes with degree equal to the highlighted histogram row
  public synchronized void deleteHighlighted()
  {
    // delete the nodes from the graph itself
    data.deleteWithDegree(highlightDegree);

    // redraw
    repaint();
  }
}


// the "Graph" is the applet itself, at the top level; when this program
// is run as an applet (e.g. from a web browser, or appletviewer), the
// instance is created and init() called; when it is run as an application,
// an instance is *not* created, and instead main() is called
public class Graph extends Applet
  implements WindowListener,    // 'windowClosing', to detect click on upper-right "X"
             ItemListener,      // 'itemStateChanged', to see histogram item selection
             ActionListener {   // 'actionPerformed', to see histogram window actions
  GraphPanel panel;        // the contained panel
  List traceList;          // listbox for stack trace
  List histogram;          // histogram
  Frame traceFrame;        // frame containing trace
  Frame histFrame;         //   "       "      histogram
  boolean defaultDoRelax = true;  // default value for graph relaxer

  private void diagnostic(String s)
  {
    System.out.println(s);
  }

  public boolean action(Event evt, Object arg) {
    synchronized (panel) {
      if (arg instanceof Boolean) {
          String lbl = ((Checkbox)evt.target).getLabel();
          boolean b = ((Boolean)arg).booleanValue();
          //diagnostic("checkbox: " + lbl);
          if (lbl.equals("Stress")) {
              panel.stress = b;
          } else if (lbl.equals("Relax")) {
              panel.doRelax = b;
          } else if (lbl.equals("Hide 0x...")) {
              panel.hide0x = b;
          } else if (lbl.equals("Froms")) {
              panel.showFroms = b;
          } else {
              throw new RuntimeException(lbl);
          }
          return true;
      }

      if ("Hist".equals(arg)) {
          updateHistogram();
      }
      else if ("Delete Red".equals(arg)) {
          panel.deleteHighlighted();
          updateHistogram();
      }
      else if ("Hide Red".equals(arg)) {
          panel.toggleHidden();
      }

      // I'm leaving the code for these (unused) buttons here just
      // because I may want it at some point
      else if ("Scramble".equals(arg)) {
          play(getCodeBase(), "audio/computer.au");
          Dimension d = size();
          panel.data.scramble(d);
      }
      else if ("Shake".equals(arg)) {
          play(getCodeBase(), "audio/gong.au");
          panel.data.shake();
      }
      else {
          throw new RuntimeException(arg.toString());
      }

      return true;
    }
  }


  // called when the user selects an item in the histogram window
  public void itemStateChanged(ItemEvent evt)
  {
    try {
      // get string selected
      int elt = ((Integer)evt.getItem()).intValue();
      String str = histogram.getItem(elt).substring(1);     // ignore leading '*', if there
      //System.out.println("itemStateChanged: " + str);
      if (elt < 3) {    // clicked in legend area
        return;
      }

      // parse it into a Degree
      String nums[] = parseString(str);
      Degree deg = new Degree();
      for (int mode=0; mode<2; mode++) {
        int arr[] = mode==0? deg.from : deg.to;
        for (int kind=Degree.STACK; kind<=Degree.SELF; kind++) {
          arr[kind] = Integer.parseInt(nums[1 + mode*4 + kind]);
        }
      }
      //System.out.println("clicked degree: " + deg);

      // set it as the current highlight filter
      panel.highlightDegree = deg;
      panel.highlightLine = elt;
      panel.repaint();
    }
    catch (Exception e) {
      e.printStackTrace();
    }
  }

  // called when an action occurs in the histogram window
  public void actionPerformed(ActionEvent evt)
  {
    // at the moment, I'm not using this; I wanted to let the user
    // press, say, the Delete key to delete nodes, but apparently
    // this method doesn't see keystrokes.. ?
    System.out.println("actionPerformed: " + evt);
  }


  // initialize GUI (separated from init so can be called from main)
  public void initGUI(GraphData graphData)
  {
    // histogram
    histogram = new List(15);
    histogram.addItemListener(this);     // listen to histogram events
    histogram.addActionListener(this);   // ?  doesn't do what I want..
    histFrame = new Frame("Histogram");
    histFrame.add(histogram);
    histFrame.resize(280, 400);         // these size/locs are best for 800x600
    histFrame.setLocation(0, 20);
    // this is what I want, but it is huge, and smaller makes it unreadable.. arg...
    //histogram.setFont(new Font("Monospaced", Font.PLAIN, 12));
    histFrame.show();
    histFrame.toFront();

    // stack trace
    traceList = new List(15);
    traceFrame = new Frame("Stack Trace");
    traceFrame.add(traceList);
    traceFrame.resize(280, 180);
    traceFrame.setLocation(0, 420);
    traceFrame.show();
    traceFrame.toFront();

    // the above two sequences of creating frames and listboxes were
    // done by a single piece of code in a loop(2), but they are sufficiently
    // different at this point to justify the duplication currently present

    // use n/s/e/w/center layout
    setLayout(new BorderLayout());

    // create the panel that displays the graph itself
    panel = new GraphPanel(this);
    add("Center", panel);

    // create a panel of buttons and other controls
    Panel buttons = new Panel();
    add("South", buttons);

    // NOTE: label dependency with below
    //buttons.add(new Button("Scramble"));
    //buttons.add(new Button("Hist"));     // now, with 2 windows, don't need this
    buttons.add(new Button("Delete Red"));
    buttons.add(new Button("Hide Red"));
    buttons.add(new Checkbox("Stress", panel.stress));
    buttons.add(new Checkbox("Relax", panel.doRelax));
    buttons.add(new Checkbox("Hide 0x...", panel.hide0x));
    buttons.add(new Checkbox("Froms", panel.showFroms));

    if (graphData == null) {
      loadGraphFromHTML();         // applet
    }
    else {
      panel.data = graphData;      // application
    }

    // this is first rendering of histogram
    updateHistogram();

    // make center node fixed, if it exists
    // (this is a holdover from other stuff.. I don't use it, but
    // it doesn't hurt)
    Dimension d = size();
    String center = getParameter("center");
    if (center != null){
      Node n = panel.data.getNode(panel.data.findNode(center));
      n.x = d.width / 2;
      n.y = d.height / 2;
      n.fixed = true;
    }
  }


  public void updateHistogram()
  {
    synchronized (panel) {
      panel.data.printHistogram(new ListboxDest(histogram));
      //panel.data.printHistogram(new ConsoleDest());
    }
  }


  // ----------------- applet stuff -------------------------
  // entry point as an applet; get graph from applet HTML tags
  public void init() {
    initGUI(null /*graphData*/);
  }

  // load the graph (edge) contents from the HTML applet tags
  private void loadGraphFromHTML()
  {
    synchronized (panel) {
      String edges = getParameter("edges");
      for (StringTokenizer t = new StringTokenizer(edges, ",") ; t.hasMoreTokens() ; ) {
        String str = t.nextToken();
        int i = str.indexOf('-');
        if (i > 0) {
          int len = 50;
          int j = str.indexOf('/');
          if (j > 0) {
            len = Integer.valueOf(str.substring(j+1)).intValue();
            str = str.substring(0, j);
          }

          String from = str.substring(0,i);
          String to = str.substring(i+1);
          panel.data.addEdge(from, to, len);

          // get node descriptions (if they exist, and if not already loaded)
          getNodeDesc(from);
          getNodeDesc(to);
        }
      }
    }
  }

  // get a node description, if it's there and not already loaded
  private void getNodeDesc(String label)
  {
    Node node = panel.data.getNode(panel.data.findNode(label));
    if (node.desc == null) {
      String desc = getParameter("a" + label);
        // this prepended "a" is because the node labels I'm using
        // are often of the form "0x...", and I doubt
        // an applet parameter name can begin with a digit
      if (desc != null) {
        node.setLoadedDesc(desc);
      }
    }
  }


  // browser-to-applet messages
  public void start() {
      panel.start();
  }
  public void stop() {
      panel.stop();
  }


  // --------------- application stuff -------------------
  // wait for the user to type a command, and return it
  // as an array of Strings
  private static String[] readLine() throws IOException {
    // useful if there is a prompt (empties OS buffer)
    System.out.flush();

    // read the line
    String line = new String();
    BufferedReader in = new BufferedReader(
      new InputStreamReader(System.in));
    line = in.readLine();

    // parse it, and stuff it into an array
    return parseString(line);
  }

  // parse a string into an array
  public static String[] parseString(String line)
  {
    return parseString(line, " ");
  }

  // parse, with specified delimiters
  public static String[] parseString(String line, String delim)
  {
    StringTokenizer st = new StringTokenizer(line, delim);
    String arr[] = new String[st.countTokens()];
    for (int i=0; i<arr.length; i++) {
      arr[i] = st.nextToken();
    }

    return arr;
  }


  // entry point as an application
  //   arguments: [file.g [norelax]]
  public static void main(String args[])
  {
    /*
    String fonts[] = Toolkit.getDefaultToolkit().getFontList();
    for (int f=0; f<fonts.length; f++) {
      System.out.println("font: " + fonts[f]);
    }
    System.out.println("fixed: " + (new Font("Monospaced", Font.PLAIN, 12)));
    */

    // init
    GraphData graph = new GraphData();
    OutputDest output = new ConsoleDest();
    boolean defaultDoRelax = true;

    // process command line
    if (args.length >= 1) {
      try {
        graph.load(args[0]);
        showGraph(graph, args.length < 2);
      }
      catch (Exception e) {
        e.printStackTrace();
        return;
      }
    }

    // drop into command loop
    for(;;) {
      System.out.print("Graph> ");
      try {
        String words[] = readLine();

        if (words[0].equals("load")) {
          graph.load(words[1]);
        }
        else if (words[0].equals("save")) {
          graph.save(words[1], true /*saveXY*/);
        }
        else if (words[0].equals("savenoxy")) {
          graph.save(words[1], false /*saveXY*/);
        }
        else if (words[0].equals("hist")) {
          graph.printHistogram(output);
        }
        else if (words[0].equals("show")) {
          showGraph(graph, defaultDoRelax);
        }
        else if (words[0].equals("unhide")) {
          graph.unhideAll();
        }
        else if (words[0].equals("savesnap")) {
          FileOutputStream file = new FileOutputStream(words[1]);
          ObjectOutputStream objStream = new ObjectOutputStream(file);
          objStream.writeObject(graph);
          objStream.flush();
          file.close();
        }
        else if (words[0].equals("loadsnap")) {
          FileInputStream file = new FileInputStream(words[1]);
          ObjectInputStream objStream = new ObjectInputStream(file);
          graph = (GraphData)objStream.readObject();
          file.close();
        }
        else if (words[0].equals("check")) {
          graph.checkInvariants();
        }
        else if (words[0].equals("dump")) {
          System.out.println(graph.toString());
        }
        else if (words[0].equals("relax")) {
          defaultDoRelax = !defaultDoRelax;
          System.out.println("defaultDoRelax is now " + defaultDoRelax);
        }
        else if (words[0].equals("prune")) {
          graph.prune();
        }
        else if (words[0].equals("props")) {
          System.getProperties().list(System.out);
        }
        else if (words[0].equals("help")) {
          System.out.print(
            "Graph processor:\n"+
            "  load filename.g          - load a graph\n"+
            "  save filename.g          - save current graph (omits hidden)\n"+
            "  savenoxy filename.g      - save graph without x,y info\n"+
            "  hist                     - print in-degree histogram\n"+
            "  show                     - show current graph in a window\n"+
            "  unhide                   - unhide all nodes\n"+
            "  loadsnap filename.snap   - load a snapshot (inc. x/y/hidden)\n"+
            "  savesnap filename.snap   - save a snapshot\n"+
            "  check                    - check invariants\n"+
            "  dump                     - dump internal representation\n"+
            "  relax                    - toggle default relaxation\n"+
            "  prune                    - delete things we can handle\n"+
            "  props                    - print system properties\n"+
            "  help                     - print this message\n"+
            "  quit                     - quit program\n");
        }
        else if (words[0].equals("quit")) {
          // if we've done "show" at least once, then simply exiting
          // main() won't kill the process...
          java.lang.Runtime.getRuntime().exit(0);
        }
        else {
          System.out.println("unknown command: " + words[0]);
        }
      }
      catch (Exception e) {
        e.printStackTrace();
        //System.out.println(e);     // printStackTrace does this already
      }
    }
  }


  // show the graph in a window
  static private void showGraph(GraphData graph, boolean relax)
  {
    // create new application frame window
    Frame frame = new Frame("Graph");

    // add applet to frame window
    Graph applet = new Graph();
    applet.defaultDoRelax = relax;
    frame.add("Center", applet);
    frame.addWindowListener(applet);

    /*     -- don't need it, and I question the syntax.. --
    // add a quit menu item
    MenuBar menubar = new MenuBar();
    Menu file = new Menu("File", true);
    MenuItem item = new MenuItem("Quit");
    menubar.add(file);
    file.add(item);
    frame.setMenuBar(menubar);
    item.addActionListener(new ActionListener() {
            public void actionPerformed(ActionEvent e) {
                    // At this point, we simply leave.
                    java.lang.Runtime.getRuntime().exit(0);
            }
    });
    */

    // resize frame window to fit applet
    int width = 520;
    int height = 510;
    frame.pack();
    frame.setSize(width,height);
    frame.setLocation(280, 20);
    applet.setSize(width,height);

    // initialize the applet
    applet.setStub(new EmptyAppletStub());
    applet.initGUI(graph);
    applet.start();

    // show the window
    frame.show();
    frame.repaint();
    frame.toFront();
  }

  // WindowListener interface
  public void windowActivated(WindowEvent e) {}
  public void windowClosed(WindowEvent e) {}
  public void windowClosing(WindowEvent e) {
    panel.doRelax = false;          // otherwise bad things happen
    panel.killRelaxer = true;       // get it to exit eventually
    traceFrame.dispose();           // close stack trace window
    histFrame.dispose();            // close histogram window
    e.getWindow().dispose();        // close originating window
  }
  public void windowDeactivated(WindowEvent e) {}
  public void windowDeiconified(WindowEvent e) {}
  public void windowIconified(WindowEvent e) {}
  public void windowOpened(WindowEvent e) {}
}


// when this program is run as an application, I still call
// getParameter in a few places; this prevents that call from
// causing a NullPointerException
class EmptyAppletStub implements java.applet.AppletStub {
  public boolean isActive() { return true; }
  public java.net.URL getDocumentBase() { return null; }
  public java.net.URL getCodeBase() { return null; }
  public String getParameter(String str) { return null; }
  public java.applet.AppletContext getAppletContext() { return null; }
  public void appletResize(int x,int y) {}
}


// this is Sun's original copyright notice
/*
 * @(#)Graph.java	1.3 96/12/06
 *
 * Copyright (c) 1994-1996 Sun Microsystems, Inc. All Rights Reserved.
 *
 * Sun grants you ("Licensee") a non-exclusive, royalty free, license to use,
 * modify and redistribute this software in source and binary code form,
 * provided that i) this copyright notice and license appear on all copies of
 * the software; and ii) Licensee does not utilize the software in a manner
 * which is disparaging to Sun.
 *
 * This software is provided "AS IS," without a warranty of any kind. ALL
 * EXPRESS OR IMPLIED CONDITIONS, REPRESENTATIONS AND WARRANTIES, INCLUDING ANY
 * IMPLIED WARRANTY OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE OR
 * NON-INFRINGEMENT, ARE HEREBY EXCLUDED. SUN AND ITS LICENSORS SHALL NOT BE
 * LIABLE FOR ANY DAMAGES SUFFERED BY LICENSEE AS A RESULT OF USING, MODIFYING
 * OR DISTRIBUTING THE SOFTWARE OR ITS DERIVATIVES. IN NO EVENT WILL SUN OR ITS
 * LICENSORS BE LIABLE FOR ANY LOST REVENUE, PROFIT OR DATA, OR FOR DIRECT,
 * INDIRECT, SPECIAL, CONSEQUENTIAL, INCIDENTAL OR PUNITIVE DAMAGES, HOWEVER
 * CAUSED AND REGARDLESS OF THE THEORY OF LIABILITY, ARISING OUT OF THE USE OF
 * OR INABILITY TO USE SOFTWARE, EVEN IF SUN HAS BEEN ADVISED OF THE
 * POSSIBILITY OF SUCH DAMAGES.
 *
 * This software is not designed or intended for use in on-line control of
 * aircraft, air traffic, aircraft navigation or aircraft communications; or in
 * the design, construction, operation or maintenance of any nuclear
 * facility. Licensee represents and warrants that it will not use or
 * redistribute the Software for such purposes.
 */


/*  -- trash --
        // fonts..
        try {
          System.out.println("font is " + getFont());
          System.out.println("fixed is " + Font.getFont("fixed"));
          System.out.println("courier is " + Font.getFont("courier"));
        }
        catch (Exception e) {
          System.out.println(e);
        }
    String names[] = { "fixed", "courier", "arial", "tty", "console",
                       "times new roman", "Times New Roman",
                       "lucidia console", "dialog", "Dialog",
                       "awt.font.dialog", "java.awt.Font.Dialog",
                       "awt.font.Dialog", "java.awt.font.dialog" };
    for (int n=0; n<names.length; n++) {
      System.out.println("font " + names[n] + " is " + Font.getFont(names[n]));
    }


*/
    /* -- old; will use click in histogram window instead --
    // text fields for highlighting nodes with certain degree
    buttons.add(panel.tfFromStack = new TextField("0", 1));
    buttons.add(new Label("/"));
    buttons.add(panel.tfFromData = new TextField("0", 1));
    buttons.add(new Label("/"));
    buttons.add(panel.tfFromHeap = new TextField("0", 1));
    buttons.add(new Label("("));
    buttons.add(panel.tfFromSelf = new TextField("0", 1));
    buttons.add(new Label(")"));
    */

    //buttons.add(new Button("Save"));
    //buttons.add(new Button("Load"));