package stdlib;

import java.io.File;
import java.io.FileWriter;
import java.io.IOException;
import java.io.PrintWriter;
import java.lang.reflect.AccessibleObject;
import java.lang.reflect.Field;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Locale;
import java.util.Map;
import java.util.Objects;
import java.util.Set;

// A fancy way to draw trees: http://stackoverflow.com/questions/10902745/enforcing-horizontal-node-ordering-in-a-dot-tree
// GraphvizBuilder.nodesToFile (stack.first, "rankdir=\"LR\"");

// TODO: Documentation
public final class GraphvizBuilder {
  private static enum Type { DIGRAPH, GRAPH }

  private static ArrayList<String> DOT_EXTENSIONS;
  static {
    DOT_EXTENSIONS = new ArrayList<> ();
    DOT_EXTENSIONS.add ("gv");
    DOT_EXTENSIONS.add ("dot");
  }
  private static HashSet<String> DOT_OUTPUT_FORMATS;
  static {
    DOT_OUTPUT_FORMATS = new HashSet<> ();
    DOT_OUTPUT_FORMATS.add ("bmp");
    DOT_OUTPUT_FORMATS.add ("cgimage");
    DOT_OUTPUT_FORMATS.add ("cmap");
    DOT_OUTPUT_FORMATS.add ("cmapx");
    DOT_OUTPUT_FORMATS.add ("eps");
    DOT_OUTPUT_FORMATS.add ("exr");
    DOT_OUTPUT_FORMATS.add ("fig");
    DOT_OUTPUT_FORMATS.add ("gif");
    DOT_OUTPUT_FORMATS.add ("icns");
    DOT_OUTPUT_FORMATS.add ("ico");
    DOT_OUTPUT_FORMATS.add ("imap");
    DOT_OUTPUT_FORMATS.add ("ismap");
    DOT_OUTPUT_FORMATS.add ("jp2");
    DOT_OUTPUT_FORMATS.add ("jpe");
    DOT_OUTPUT_FORMATS.add ("jpeg");
    DOT_OUTPUT_FORMATS.add ("jpg");
    DOT_OUTPUT_FORMATS.add ("pct");
    DOT_OUTPUT_FORMATS.add ("pdf");
    DOT_OUTPUT_FORMATS.add ("pic");
    DOT_OUTPUT_FORMATS.add ("pict");
    DOT_OUTPUT_FORMATS.add ("png");
    DOT_OUTPUT_FORMATS.add ("pov");
    DOT_OUTPUT_FORMATS.add ("ps");
    DOT_OUTPUT_FORMATS.add ("ps2");
    DOT_OUTPUT_FORMATS.add ("psd");
    DOT_OUTPUT_FORMATS.add ("sgi");
    DOT_OUTPUT_FORMATS.add ("svg");
    DOT_OUTPUT_FORMATS.add ("svgz");
    DOT_OUTPUT_FORMATS.add ("tga");
    DOT_OUTPUT_FORMATS.add ("tif");
    DOT_OUTPUT_FORMATS.add ("tiff");
    DOT_OUTPUT_FORMATS.add ("tk");
    DOT_OUTPUT_FORMATS.add ("vml");
    DOT_OUTPUT_FORMATS.add ("vmlz");
  }
  private static ArrayList<String> GRAPHVIZ_POSSIBLE_DOT_LOCATIONS;
  static {
    GRAPHVIZ_POSSIBLE_DOT_LOCATIONS = new ArrayList<> ();
    String os = System.getProperty ("os.name").toLowerCase ();
    if (os.startsWith ("win")) {
      GRAPHVIZ_POSSIBLE_DOT_LOCATIONS.add ("c:/Program Files (x86)/Graphviz2.38/bin/dot.exe");         // installer 32 bit
      GRAPHVIZ_POSSIBLE_DOT_LOCATIONS.add ("c:/Program Files/Graphviz/bin/dot.exe");                   // installer 64 bit
      GRAPHVIZ_POSSIBLE_DOT_LOCATIONS.add ("c:/ProgramData/chocolatey/bin/dot.exe");                   // choco
      GRAPHVIZ_POSSIBLE_DOT_LOCATIONS.add (System.getProperty ("user.home") + "/scoop/shims/dot.exe"); // scoop
      GRAPHVIZ_POSSIBLE_DOT_LOCATIONS.add (System.getProperty ("user.dir") + "/lib/graphviz-windows/bin/dot.exe");
    } else if (os.startsWith ("mac")) {
      GRAPHVIZ_POSSIBLE_DOT_LOCATIONS.add ("/opt/homebrew/bin/dot"); // homebrew
      GRAPHVIZ_POSSIBLE_DOT_LOCATIONS.add ("/opt/local/bin/dot");    // macports 
      GRAPHVIZ_POSSIBLE_DOT_LOCATIONS.add ("/usr/local/bin/dot");    // homebrew
      GRAPHVIZ_POSSIBLE_DOT_LOCATIONS.add ("/usr/bin/dot");          // native
      GRAPHVIZ_POSSIBLE_DOT_LOCATIONS.add (System.getProperty ("user.dir") + "/lib/graphviz-mac/bin/dot");
    } else {
      GRAPHVIZ_POSSIBLE_DOT_LOCATIONS.add ("/usr/local/bin/dot");
      GRAPHVIZ_POSSIBLE_DOT_LOCATIONS.add ("/usr/bin/dot");
    }
    // Annoyingly, the PATH is usually not what you want when running inside an IDE like eclipse, thus the nonsense above.
    String[] paths = System.getenv ("PATH").split(File.pathSeparator);
    for (String p : paths) 
      GRAPHVIZ_POSSIBLE_DOT_LOCATIONS.add (p + File.separator + "dot");
  }
  public static void graphvizAddPossibleDotLocation (String value) {
    GRAPHVIZ_POSSIBLE_DOT_LOCATIONS.add (value);
  }

  private static interface Element {
    public String toString (Type type);
  }
  private static String getProperties (String label, String properties) {
    if (properties == null || "".equals (properties)) {
      if (label == null || "".equals (label)) {
        return ";";
      } else {
        return "[label=\"" + label + "\"];";
      }
    } else {
      if (label == null || "".equals (label)) {
        return "[" + properties + "];";
      } else {
        return "[label=\"" + label + "\"," + properties + "];";
      }
    }
  }
  private static final class Node implements Element {
    private final String id;
    private final String properties;
    public Node (String id, String label, String properties) {
      if (id == null || "".equals (id)) throw new IllegalArgumentException ();
      this.id = id;
      this.properties = getProperties (label, properties);
    }
    public String toString (Type type) {
      return "  " + id + properties;
    }
  }
  private static final class Edge implements Element {
    private final String src;
    private final String dst;
    private final String properties;
    public Edge (String src, String dst, String label, String properties) {
      if (src == null || "".equals (src)) throw new IllegalArgumentException ();
      if (dst == null || "".equals (dst)) throw new IllegalArgumentException ();
      this.src = src;
      this.dst = dst;
      this.properties = getProperties (label, properties);
    }
    public String toString (Type type) {
      String arrow = (type == Type.DIGRAPH ? " -> " : " -- ");
      return "  " + src + arrow + dst + properties;
    }
  }

  private static String defaultGraphProperties = "";
  private static String defaultNodeProperties = "";
  private static String defaultEdgeProperties = "fontsize=12";
  private static String nullNodeProperties = "shape=\"point\"";
  private static String nullEdgeProperties = "shape=\"point\"";

  private static int fileCount = 0;
  public static void binaryHeapToFile (double[] heap, int N) {
    binaryHeapToFile (heap, N, "heap" + fileCount + ".png");
    fileCount++;
  }
  public static void binaryHeapToFile (Object[] heap, int N) {
    binaryHeapToFile (heap, N, "heap" + fileCount + ".png");
    fileCount++;
  }
  public static void ufToFile (int[] uf) {
    ufToFile (uf, "uf" + fileCount + ".png");
    fileCount++;
  }
  /**
   * Shows simple recursive data structures.
   * The class of the root parameter is taken to be the must be an element of the recursive node class.
   *
   * @param root
   */
  public static void nodesToFile (Object root)                  { nodesToFile (root, defaultNodeProperties, true); }
  public static void nodesToFile (Object root, String filename) { nodesToFile (root, filename, defaultNodeProperties, true); }
  private static void nodesToFile (Object root, String properties, boolean withLabeledEdges) {
    nodesToFile (root, "nodes" + fileCount + ".png", properties, withLabeledEdges);
    fileCount++;
  }


  public static void binaryHeapToFile (double[] heap, int N, String filename) {
    GraphvizBuilder gb = new GraphvizBuilder ();
    gb.addBinaryHeap (heap, N);
    gb.toFile (filename, "rankdir=\"BT\"");
  }
  public static void binaryHeapToFile (Object[] heap, int N, String filename) {
    GraphvizBuilder gb = new GraphvizBuilder ();
    gb.addBinaryHeap (heap, N);
    gb.toFile (filename, "rankdir=\"BT\"");
  }
  public static void ufToFile (int[] uf, String filename) {
    GraphvizBuilder gb = new GraphvizBuilder ();
    gb.addUF (uf);
    gb.toFile (filename, "rankdir=\"BT\"");
  }
  public static void nodesToFile (Object root, String filename, String properties, boolean withLabeledEdges) {
    GraphvizBuilder gb = new GraphvizBuilder ();
    gb.addNodes (root, withLabeledEdges);
    gb.toFile (filename, properties);
  }


  private void addBinaryHeap (Object[] heap, int N) {
    if (heap == null) throw new IllegalArgumentException ("null heap");
    if (N<0 || N>heap.length) throw new IllegalArgumentException ("N=" + N + " is not in range [0.." + heap.length + "]");
    String prefix = "heap__" + heap.hashCode ();
    for (int i = 1; i <= N; i++) {
      addLabeledNodeString (prefix + i, heap[i].toString ());
    }
    for (int i = 2; i <= N; i++) {
      addEdgeString (prefix + i, prefix + (i/2));
    }
    int logN = 31 - Integer.numberOfLeadingZeros(N);
    for (int i = N+1; i<2<<logN; i++) {
      addFromNullEdgeString (prefix + (i/2));
    }
    //    if (N%2==0) {
    //      addFromNullEdgeString (prefix + (N/2));
    //    }
  }
  private void addBinaryHeap (double[] heap, int N) {
    if (heap == null) throw new IllegalArgumentException ("null heap");
    if (N<0 || N>heap.length) throw new IllegalArgumentException ("N=" + N + " is not in range [0.." + heap.length + "]");
    String prefix = "heap__" + heap.hashCode ();
    for (int i = 1; i <= N; i++) {
      addLabeledNodeString (prefix + i, Double.toString(heap[i]));
    }
    for (int i = 2; i <= N; i++) {
      addEdgeString (prefix + i, prefix + (i/2));
    }
    int logN = 31 - Integer.numberOfLeadingZeros(N);
    for (int i = N+1; i<2<<logN; i++) {
      addFromNullEdgeString (prefix + (i/2));
    }
    //    if (N%2==0) {
    //      addFromNullEdgeString (prefix + (N/2));
    //    }
  } 
  private void addUF (int[] uf) {
    if (uf == null) throw new IllegalArgumentException ("null uf");
    String prefix = "uf__" + uf.hashCode ();
    for (int i = 0; i < uf.length; i++) {
      addLabeledNodeString (prefix + i, Integer.toString (i));
    }
    for (int i = 0; i < uf.length; i++) {
      if (i != uf[i])
        addEdgeString (prefix + i, prefix + uf[i]);
    }
  }
  private void addNodes (Object root, boolean withLabeledEdges) {
    if (root == null) {
      addNullEdge (null);
    } else {
      addNodes (root, new HashSet<Object> (), root.getClass (), withLabeledEdges);
    }
  }
  private void addNodes (Object obj, Set<Object> visited, Class<?> nodeClass, boolean withLabeledEdges) {
    visited.add (obj);
    Class<?> clazz = obj.getClass ();
    if (clazz.isArray ()) {
      throw new Error ("Can't deal with arrays");
    } else {
      StringBuilder labelBuilder = new StringBuilder ();
      Map<Object,Field> children = new HashMap<> ();

      Field[] fields = clazz.getDeclaredFields ();
      AccessibleObject.setAccessible (fields, true);
      boolean first = true;
      for (int i = 0; i < fields.length; i++) {
        Field field = fields[i];
        Object value;
        try { value = field.get (obj); } catch (IllegalAccessException e) { throw new Error (e); }
        if (field.getType () == nodeClass) {
          if (value == null) {
            if (withLabeledEdges)
              addLabeledNullEdge (obj, field.getName ());
            else
              addNullEdge (obj);
          } else {
            children.put (value, field);
          }
        } else {
          if (first) { first = false; } else { labelBuilder.append (", "); }
          labelBuilder.append (value == null ? "null" : value.toString ());
        }
      }
      addLabeledNode (obj, labelBuilder.toString ());
      for (Object child : children.keySet ()) {
        if (!visited.contains (child))
          addNodes (child, visited, nodeClass, withLabeledEdges);
      }
      for (Object child : children.keySet ()) {
        if (withLabeledEdges)
          addLabeledEdge (obj, child, children.get (child).getName ());
        else
          addEdge (obj, child);
      }
    }

  }

  private static String getId (Object o) {
    return "hash__" + Objects.hashCode (o);
  }
  private static String getId (int i) {
    return Integer.toString (i);
  }

  private static String getLabel (Object o) {
    return quote (Objects.toString (o));
  }
  private static String getLabel (String s) {
    return quote (s);
  }
  private static String getLabel (int i) {
    return Integer.toString (i);
  }
  private static String getLabel (double d) {
    return Double.toString (d);
  }
  private static String getLabel (float f) {
    return Float.toString (f);
  }
  //private static final String canAppearUnquotedInLabelChars = " /$&*@#!-+()^%;_[],;.=";
  private static boolean canAppearUnquotedInLabel (char c) {
    return true;
    //return canAppearUnquotedInLabelChars.indexOf (c) != -1 || Character.isLetter (c) || Character.isDigit (c);
  }
  private static final String quotable = "\\\"<>{}|";
  protected static String quote (String s) {
    s = unescapeJavaString (s);
    StringBuffer sb = new StringBuffer ();
    for (int i = 0, n = s.length (); i < n; i++) {
      char c = s.charAt (i);
      if (quotable.indexOf (c) != -1) sb.append ('\\').append (c);
      else if (canAppearUnquotedInLabel (c)) sb.append (c);
      else sb.append ("\\\\u").append (Integer.toHexString (c));
    }
    return sb.toString ();
  }
  /**
   * Unescapes a string that contains standard Java escape sequences.
   * <ul>
   * <li><strong>\\b \\f \\n \\r \\t \\" \\'</strong> :
   * BS, FF, NL, CR, TAB, double and single quote.</li>
   * <li><strong>\\N \\NN \\NNN</strong> : Octal character
   * specification (0 - 377, 0x00 - 0xFF).</li>
   * <li><strong>\\uNNNN</strong> : Hexadecimal based Unicode character.</li>
   * </ul>
   *
   * @param st
   *            A string optionally containing standard java escape sequences.
   * @return The translated string.
   */
  // from http://udojava.com/2013/09/28/unescape-a-string-that-contains-standard-java-escape-sequences/
  private static String unescapeJavaString(String st) {
    StringBuilder sb = new StringBuilder(st.length());
    for (int i = 0; i < st.length(); i++) {
      char ch = st.charAt(i);
      if (ch == '\\') {
        char nextChar = (i == st.length() - 1) ? '\\' : st.charAt(i + 1);
        // Octal escape?
        if (nextChar >= '0' && nextChar <= '7') {
          String code = "" + nextChar;
          i++;
          if ((i < st.length() - 1) && st.charAt(i + 1) >= '0' && st.charAt(i + 1) <= '7') {
            code += st.charAt(i + 1);
            i++;
            if ((i < st.length() - 1) && st.charAt(i + 1) >= '0' && st.charAt(i + 1) <= '7') {
              code += st.charAt(i + 1);
              i++;
            }
          }
          sb.append((char) Integer.parseInt(code, 8));
          continue;
        }
        switch (nextChar) {
        case '\\': ch = '\\'; break;
        case 'b': ch = '\b'; break;
        case 'f': ch = '\f'; break;
        case 'n': ch = '\n'; break;
        case 'r': ch = '\r'; break;
        case 't': ch = '\t'; break;
        case '\"': ch = '\"'; break;
        case '\'': ch = '\''; break;
        // Hex Unicode: u????
        case 'u':
          if (i >= st.length() - 5) { ch = 'u'; break; }
          int code = Integer.parseInt(st.substring (i+2,i+6), 16);
          sb.append(Character.toChars(code));
          i += 5;
          continue;
        }
        i++;
      }
      sb.append(ch);
    }
    return sb.toString();
  }


  private final ArrayList<Element> elements = new ArrayList<> ();

  public void addNode (Object o)                                         { addLabeledNodeString (getId (o), getLabel (o), defaultNodeProperties); }
  public void addNode (Object o, String properties)                      { addLabeledNodeString (getId (o), getLabel (o), properties); }
  public void addLabeledNode (Object o, String label)                    { addLabeledNodeString (getId (o), getLabel (label), defaultNodeProperties); }
  public void addLabeledNode (Object o, String label, String properties) { addLabeledNodeString (getId (o), getLabel (label), properties); }

  public void addNode (int id)                                         { addLabeledNodeString (getId (id), getLabel (id), defaultNodeProperties); }
  public void addNode (int id, String properties)                      { addLabeledNodeString (getId (id), getLabel (id), properties); }
  public void addLabeledNode (int id, String label)                    { addLabeledNodeString (getId (id), getLabel (label), defaultNodeProperties); }
  public void addLabeledNode (int id, String label, String properties) { addLabeledNodeString (getId (id), getLabel (label), properties); }

  private void addNodeString (String id)                                         { addLabeledNodeString (id, id, defaultNodeProperties); }
  private void addNodeString (String id, String properties)                      { addLabeledNodeString (id, id, properties); }
  private void addLabeledNodeString (String id, String label)                    { addLabeledNodeString (id, getLabel (label), defaultNodeProperties); }
  private void addLabeledNodeString (String id, String label, String properties) { elements.add (new Node (id, getLabel (label), properties)); }

  public void addEdge (Object src, Object dst)                                         { addEdgeString (getId (src), getId (dst), defaultEdgeProperties); }
  public void addEdge (Object src, Object dst, String properties)                      { addEdgeString (getId (src), getId (dst), properties); }
  public void addLabeledEdge (Object src, Object dst, float label)                     { addLabeledEdgeString (getId (src), getId (dst), getLabel (label) + "\", length=\"" + getLabel (label), defaultEdgeProperties); }
  public void addLabeledEdge (Object src, Object dst, float label, String properties)  { addLabeledEdgeString (getId (src), getId (dst), getLabel (label) + "\", length=\"" + getLabel (label), properties); }
  public void addLabeledEdge (Object src, Object dst, double label)                    { addLabeledEdgeString (getId (src), getId (dst), getLabel (label) + "\", length=\"" + getLabel (label), defaultEdgeProperties); }
  public void addLabeledEdge (Object src, Object dst, double label, String properties) { addLabeledEdgeString (getId (src), getId (dst), getLabel (label) + "\", length=\"" + getLabel (label), properties); }
  public void addLabeledEdge (Object src, Object dst, int label)                       { addLabeledEdgeString (getId (src), getId (dst), getLabel (label) + "\", length=\"" + getId (label), defaultEdgeProperties); }
  public void addLabeledEdge (Object src, Object dst, int label, String properties)    { addLabeledEdgeString (getId (src), getId (dst), getLabel (label) + "\", length=\"" + getId (label), properties); }
  public void addLabeledEdge (Object src, Object dst, String label)                    { addLabeledEdgeString (getId (src), getId (dst), getLabel (label), defaultEdgeProperties); }
  public void addLabeledEdge (Object src, Object dst, String label, String properties) { addLabeledEdgeString (getId (src), getId (dst), getLabel (label), properties); }

  public void addEdge (int src, int dst)                                         { addEdgeString (getId (src), getId (dst), defaultEdgeProperties); }
  public void addEdge (int src, int dst, String properties)                      { addEdgeString (getId (src), getId (dst), properties); }
  public void addLabeledEdge (int src, int dst, float label)                     { addLabeledEdgeString (getId (src), getId (dst), getLabel (label) + "\", length=\"" + getLabel (label), defaultEdgeProperties); }
  public void addLabeledEdge (int src, int dst, float label, String properties)  { addLabeledEdgeString (getId (src), getId (dst), getLabel (label) + "\", length=\"" + getLabel (label), properties); }
  public void addLabeledEdge (int src, int dst, double label)                    { addLabeledEdgeString (getId (src), getId (dst), getLabel (label) + "\", length=\"" + getLabel (label), defaultEdgeProperties); }
  public void addLabeledEdge (int src, int dst, double label, String properties) { addLabeledEdgeString (getId (src), getId (dst), getLabel (label) + "\", length=\"" + getLabel (label), properties); }
  public void addLabeledEdge (int src, int dst, int label)                       { addLabeledEdgeString (getId (src), getId (dst), getLabel (label) + "\", length=\"" + getLabel (label), defaultEdgeProperties); }
  public void addLabeledEdge (int src, int dst, int label, String properties)    { addLabeledEdgeString (getId (src), getId (dst), getLabel (label) + "\", length=\"" + getLabel (label), properties); }
  public void addLabeledEdge (int src, int dst, String label)                    { addLabeledEdgeString (getId (src), getId (dst), getLabel (label), defaultEdgeProperties); }
  public void addLabeledEdge (int src, int dst, String label, String properties) { addLabeledEdgeString (getId (src), getId (dst), getLabel (label), properties); }

  private void addEdgeString (String src, String dst)                                         { addEdgeString (src, dst, defaultEdgeProperties); }
  private void addEdgeString (String src, String dst, String properties)                      { elements.add (new Edge (src, dst, null, properties)); }
  private void addLabeledEdgeString (String src, String dst, float label)                     { addLabeledEdgeString (src, dst, getLabel (label) + ", length=" + getLabel (label), defaultEdgeProperties); }
  private void addLabeledEdgeString (String src, String dst, float label, String properties)  { addLabeledEdgeString (src, dst, getLabel (label) + ", length=" + getLabel (label), properties); }
  private void addLabeledEdgeString (String src, String dst, double label)                    { addLabeledEdgeString (src, dst, getLabel (label) + ", length=" + getLabel (label), defaultEdgeProperties); }
  private void addLabeledEdgeString (String src, String dst, double label, String properties) { addLabeledEdgeString (src, dst, getLabel (label) + ", length=" + getLabel (label), properties); }
  private void addLabeledEdgeString (String src, String dst, int label)                       { addLabeledEdgeString (src, dst, getLabel (label) + ", length=" + getLabel (label), defaultEdgeProperties); }
  private void addLabeledEdgeString (String src, String dst, int label, String properties)    { addLabeledEdgeString (src, dst, getLabel (label) + ", length=" + getLabel (label), properties); }
  private void addLabeledEdgeString (String src, String dst, String label)                    { addLabeledEdgeString (src, dst, getLabel (label), defaultEdgeProperties); }
  private void addLabeledEdgeString (String src, String dst, String label, String properties) { elements.add (new Edge (src, dst, getLabel (label), properties)); }

  private int nullId = 0;
  public void addNullEdge (Object src) { addNullEdgeString(getId (src)); }
  public void addNullEdgeString (String src) {
    String id = "null__" + nullId;
    nullId++;
    addLabeledNodeString (id, "", nullNodeProperties);
    if (src != null) addEdgeString (src, id, nullEdgeProperties);
  }
  public void addFromNullEdgeString (String src) {
    String id = "null__" + nullId;
    nullId++;
    addLabeledNodeString (id, "", nullNodeProperties);
    if (src != null) addEdgeString (id, src, nullEdgeProperties);
  }
  public void addLabeledNullEdge (Object src, String label) { addLabeledNullEdgeString(getId (src), label); }
  public void addLabeledNullEdgeString (String src, String label) {
    String id = "null__" + nullId;
    nullId++;
    addLabeledNodeString (id, "", nullNodeProperties);
    if (src != null) addLabeledEdgeString (src, id, getLabel (label), nullEdgeProperties);
  }

  private static PrintWriter getPrintWriter (File file) {
    PrintWriter out;
    try {
      out = new PrintWriter (new FileWriter (file));
    } catch (IOException e) {
      throw new Error ("\n!!!! Cannot open " + file + " for writing");
    }
    return out;
  }
  private static String getGvExecutable () {
    String executable = null;
    for (String s : GRAPHVIZ_POSSIBLE_DOT_LOCATIONS) {
      if (new File (s).canExecute ()) executable = s;
    }
    if (executable == null)
      throw new Error  ("\n!!!! Cannot find dot executable in " + GRAPHVIZ_POSSIBLE_DOT_LOCATIONS
          + "\n!!!! Check the value of POSSIBLE_DOT_LOCATIONS in " + GraphvizBuilder.class.getCanonicalName ());
    return executable;
  }

  //public void toFileUndirected (boolean keepGvFile, String filename)                      { toFile (Type.GRAPH, keepGvFile, filename, defaultGraphProperties); }
  //public void toFileUndirected (boolean keepGvFile, String filename, String properties)   { toFile (Type.GRAPH, keepGvFile, filename, properties); }
  public void toFileUndirected (String filename)                                          { toFile (Type.GRAPH, false, filename, defaultGraphProperties); }
  public void toFileUndirected (String filename, String properties)                       { toFile (Type.GRAPH, false, filename, properties); }
  //public void toFile (boolean keepGvFile, String filename)                                { toFile (Type.DIGRAPH, keepGvFile, filename, defaultGraphProperties); }
  //public void toFile (boolean keepGvFile, String filename, String properties)             { toFile (Type.DIGRAPH, keepGvFile, filename, properties); }
  public void toFile (String filename)                                                    { toFile (Type.DIGRAPH, false, filename, defaultGraphProperties); }
  public void toFile (String filename, String properties)                                 { toFile (Type.DIGRAPH, false, filename, properties); }
  //public void toFile (Type type, boolean keepGvFile, String filename)                    { toFile (type, keepGvFile, filename, defaultGraphProperties); }
  private void toFile (Type type, boolean keepGvFile, String filename, String properties) {
    // keepGvFile = true;
    // Get basename and ext
    String basename;
    String ext;
    if (filename.indexOf ('.') < 0) {
      ext = "png";
      basename = filename;
    } else {
      int period = filename.lastIndexOf ('.');
      ext = filename.substring (period + 1);
      basename = filename.substring (0, period);
    }
    if (!new File (basename).isAbsolute ()) {
      if (dirName == null) setDirName ();
      basename = dirName + basename;
    }

    boolean extIsDot = DOT_EXTENSIONS.contains (ext);
    boolean extIsOut = DOT_OUTPUT_FORMATS.contains (ext);

    if ((!extIsDot) && (!extIsOut))
      throw new Error ("\n!!!! unrecognized extension \"" + ext + "\""
          + "\n!!!! filename must end in \".ext\", where ext is \"gv\" or one of the following:\n!!!! " + DOT_OUTPUT_FORMATS);


    String newBasename = basename;
    File newFile = new File (newBasename + "." + ext);
    int suffix = 0;
    while (newFile.exists()) {      
      suffix++; 
      newBasename = basename + " " + suffix;
      newFile = new File(newBasename + "." + ext);
    }
    basename = newBasename;

    // Create dot input file
    File gvFile;
    if (extIsDot) {
      gvFile = new File (basename + "." + ext);
    } else {
      gvFile = new File (basename + ".gv");
    }
    PrintWriter out = getPrintWriter (gvFile);
    switch (type) {
    case DIGRAPH: out.print ("digraph"); break;
    case GRAPH:   out.print ("graph"); break;
    }
    out.println (" G {");
    if (properties != null && !"".equals (properties))
      out.println ("  graph [" + properties + "];");
    for (Element e : elements)
      out.println (e.toString (type));
    out.println ("}");
    out.close ();


    // Run dot
    if (extIsOut) {
      File outFile = new File (basename + "." + ext);

      String executable = getGvExecutable ();
      ProcessBuilder pb = new ProcessBuilder (executable, "-T", ext);
      pb.redirectInput (gvFile);
      pb.redirectOutput (outFile);
      int result = -1;
      try {
        result = pb.start ().waitFor ();
      } catch (IOException e) {
        throw new Error ("\n!!!! Cannot execute \"" + executable + "\"\n!!!! Make sure you have installed http://www.graphviz.org/"
            + "\n!!!! Check the value of POSSIBLE_DOT_LOCATIONS in " + GraphvizBuilder.class.getCanonicalName ());
      } catch (InterruptedException e) {
        throw new Error ("\n!!!! Execution of \"" + executable + "\" interrupted");
      }
      if (result == 0) {
        if (!keepGvFile) gvFile.delete ();
      } else {
        outFile.delete ();
      }
    }
  }
  /**
   * Graphics files are saved in directory baseDirName/Graphviz.
   * If baseDirName is a relative pathname, then it is placed in the users Desktop folder.
   * baseDirName directory is created if it does not already exist.
   * If baseDirName/Graphviz exists, then numbers are appended to the directory name:
   * "baseDirName/Graphviz 1", "baseDirName/Graphviz 2", etc.
   */
  public static void setBaseDirName (String baseDirName) {
    if (baseDirName == null) throw new Error ("\n!!!! no nulls please");    
    GraphvizBuilder.baseDirName = baseDirName;
  }
  private static String baseDirName = "GraphvizOutput";

  private static boolean isWindows () {
    String osName = System.getProperty("os.name");
    if (osName == null) {
      throw new Error("\n!!! os.name not found");
    }
    osName = osName.toLowerCase(Locale.ENGLISH);
    return osName.contains("windows");
  }
  private static String getDesktop () {
    if (isWindows()) {
      // Supposedly this selects the windows desktop folder:
      return javax.swing.filechooser.FileSystemView.getFileSystemView().getHomeDirectory().toString();
    } else {
      return System.getProperty ("user.home") + File.separator + "Desktop";
    }
  }
  private static String dirName = null;
  private static void setDirName () {
    // create dir
    File dir = new File (baseDirName);
    if (!dir.isAbsolute ()) {
      baseDirName = getDesktop() + File.separator + baseDirName;
      dir = new File (baseDirName);
    }
    if (dir.exists ()) {
      if (!dir.isDirectory ()) 
        throw new Error ("\n!!!! \"" + dir + "\" is not a directory");
      if (!dir.canWrite ()) 
        throw new Error ("\n!!!! Unable to write directory: \"" + dir + "\"");
    } else {
      dir.mkdirs ();
    }

    // create newDir
    String mainClassName = "Graphviz";
    String prefix = baseDirName + File.separator;
    File newDir = new File (prefix + mainClassName);
    int suffix = 0;
    while (newDir.exists()) { 
      suffix++; 
      newDir = new File(prefix + mainClassName + " " + suffix);
    }
    newDir.mkdir ();

    if (!newDir.isDirectory () || !newDir.canWrite ())
      throw new Error ("Failed setOutputDirectory \"" + newDir + "\"");
    dirName = newDir + File.separator;
  }
}