// Lettergram.java
// Andrew Davison, ad@coe.psu.ac.th, Dec. 2022

/* A Lettergram is an undirected graph with a letter in
   each node. The aim is to create all the words by following
   the graph's edges, but without using a letter more than
   once in a word.

   This code employs a DFS traversal of the graph, generating
   a string at every step in the path until all the nodes
   have been visited. 

   The graph data structure is a simple form of adjacency list,
   with the data read from a text file. The data for a given node
   is stored in an AdjNode object.

   The list of words generated are checked by Hunspell, and the
   valid words are printed.

  Usage:
    > compile Lettergram.java
    > run Lettergram <data-file>
  e.g.
    > run Lettergram adjsLetters.txt
        // adjsletters.txt is based on the lettergram in lettergram.png
     
*/

import java.io.*;
import java.util.*;



public class Lettergram
{

  public static void main(String[] args)
  {
    if (args.length != 1) {
      System.out.println("Usage: run Lettergram <data-file>");
      return;
    }

    ArrayList<AdjNode> graph = buildGraph(args[0]);
    System.out.println("Graph:");
    for (AdjNode n : graph)
      System.out.println("  " + n);
    System.out.println();

    ArrayList<String> words = search(graph);
    System.out.println("No. of words collected: " + words.size());

    // collect the dictionary words
    ArrayList<String> dictWords = new ArrayList<>();
    HunspellChecker hsc = new HunspellChecker();
    for (String word : words) {
      if (hsc.isCorrect(word) && (word.length() >= 4))
        dictWords.add(word);
    }
    hsc.close();

    // sort and print
    System.out.println("Words in dictionary: ");
    Collections.sort(dictWords);
    WordUtils.printWords(dictWords, 3);
  }  // end of main()


  private static ArrayList<String> search(
                             ArrayList<AdjNode> graph)
  /* The DFS traversal is repeated starting from each of the
     nodes in the graph.
  */
  {
    ArrayList<String> words = new ArrayList<>();
    ArrayList<String> path = new ArrayList<>();

    // collect all the IDs of the nodes in the graph
    ArrayList<String> ids = new ArrayList<>();
    for (AdjNode n : graph)
       ids.add( n.getID());

    System.out.println("Traversing the graph...");
    for (String id : ids) {
      AdjNode node = findNode(id, graph);
      searchDFS(node, graph, path, words);
      node.setVisited(false);
      path.remove(path.size()-1);
    }

    return words;
  }  // end of search()


  private static AdjNode findNode(String id, ArrayList<AdjNode> graph)
  // return the AdjNode for the id node
  {
    for (AdjNode node : graph) {
      if (node.getID().equals(id))
        return node;
    }
    System.out.println(id + " not found in graph");
    return null;
  }  // end of findNode()



  private static void searchDFS(AdjNode node, ArrayList<AdjNode> graph,
                         ArrayList<String> path, ArrayList<String> words)
  {
    node.setVisited(true);
    path.add(node.getID());
    words.add( makeWord(path) );

    if (allVisited(graph))   // the search is completed
      return;

    // search all neighboring nodes
    ArrayList<String> neighbors = node.getNeighbors();
    for(String id: neighbors) {
      AdjNode toNode = findNode(id, graph);
      if (!toNode.isVisited()) {
        searchDFS(toNode, graph, path, words);
        // undo changes
        toNode.setVisited(false);
        path.remove(path.size()-1);
      }
    }
  }  // end of searchDFS()


  private static String makeWord(ArrayList<String> path)
  /* The path is a list of node IDs, which are letters
     with an optional number (e.g. "v", "a1", "a2", ...)
     The IDs in the path are concatenated, but ignoring
     any numerical suffix.
  */
  { StringBuilder sb = new StringBuilder();
    for (String id: path)
      sb.append(id.charAt(0));  // get the ID's letter only
    return sb.toString();
  }  // end of makeWord()


  private static boolean allVisited(ArrayList<AdjNode> graph)
  {
    for (AdjNode node : graph)
      if (!node.isVisited())
        return false;
    return true;
  }  // end of allVisited()



  private static ArrayList<AdjNode> buildGraph(String fnm)
  /* Build an adjacency list for a undirected graph.
     Input data format:
      - multiple lines, one for each vertex
           - each line: ID, list of ids

     An ID is a lowercase letter with an optional number.

     Format example:
       i    a1 r  v  t1 a2
       a1   i  v  t1 t2
       t1   a1 i  t2 g  r
       t2   t1 a1 g  e

      and blank lines and comment lines.
  */
  {
    ArrayList<AdjNode> graph = new ArrayList<>();

    try (BufferedReader br = new BufferedReader(new FileReader(fnm))) {
      String line;
      while ((line = br.readLine()) != null) {
        line = line.trim();
        if (line.length() == 0)  // blank line
          continue;
        if (line.startsWith("//"))   // comment
          continue;
        if (Character.isLowerCase(line.charAt(0))) // node info
          graph.add( buildAdjNode(line));
      }
      System.out.println("Loaded adj. info from " + fnm);
    }
    catch (Exception e)
    {   System.out.println("Could not load adj. info from " + fnm);  }

    return graph;
  }  // end of buildGraph()


  private static AdjNode buildAdjNode(String line)
  /* Extract node info from a line with the format
        <ID>    <neighbor1>  <neighbor2> ...
     e.g.
       i    a1 r  v  t1 a2
  */
  {
    String[] ids = line.split("\\s+");
    AdjNode node = new AdjNode(ids[0]);
    for (int i=1; i < ids.length; i++)
       node.addNeighbor(ids[i]);
    return node;
  }  // end of buildAdjNode()


}  // end of Lettergram class