/* Jumble for Java -- DRH */ import java.awt.Graphics; import java.util.Vector; import java.io.FileInputStream; import java.io.DataInputStream; class Canonical { static private boolean bubble_char(char canon[], int bound) { char temp; boolean exchange = false; int i,j; for (i = 0; i < bound; i++) { j = i + 1; if (canon[i] > canon[j]) { /* exchange */ exchange = true; temp = canon[i]; canon[i] = canon[j]; canon[j] = temp; } } return(exchange); }; static public String canonicalize(String candidate) { boolean exchange = true; int length = candidate.length(); char canon[] = new char[length]; int bound = length - 1; candidate.getChars(0, length, canon, 0); while (exchange) { exchange = bubble_char(canon, bound); } return(new String(canon)); }; }; class Dict_entry { String string; String canonical; public Dict_entry(String line) { string = new String(line); canonical = Canonical.canonicalize(line); }; }; class Dict { public Dict_entry dict[]; public int num_words; private String filename = new String("/usr/dict/words"); /* private String filename = new String("/usr/people/henke/java.sun/jumble.ORIG/mywords"); */ private FileInputStream file_input_dict; private DataInputStream input_dict; public Dict() { boolean done; String line; System.out.println ("Reading dictionary started"); try { file_input_dict = new FileInputStream(filename); input_dict = new DataInputStream(file_input_dict); } catch (java.io.FileNotFoundException e) { System.out.println ("Exception: file not found"); System.exit(-1); } num_words = 0; dict = new Dict_entry[64000]; done = false; while (!done) { try { line = input_dict.readLine(); if (line == null) { done = true; } else { dict[num_words] = new Dict_entry(line); num_words++; } } catch (java.io.IOException e) { System.out.println ("Exception: I/O Error on read"); System.exit(-1); } } System.out.println ("Reading dictionary ended, num_words:" + num_words); }; public void dump() { System.out.println ("Dump of dictionary, num_words:" + num_words); for (int i = 0; i < num_words; i++) { System.out.println ("i: " + i + " string: " + dict[i].string + " canonical: " + dict[i].canonical); } } private void quickSort(int lo, int hi) { if (lo >= hi) return; int mid = (lo + hi) / 2; if (dict[lo].canonical.compareTo(dict[mid].canonical) > 0) { /* swap */ Dict_entry tmp = dict[lo]; dict[lo] = dict[mid]; dict[mid] = tmp; } if (dict[mid].canonical.compareTo(dict[hi].canonical) > 0) { /* swap */ Dict_entry tmp = dict[mid]; dict[mid] = dict[hi]; dict[hi] = tmp; if (dict[lo].canonical.compareTo(dict[mid].canonical) > 0) { /* swap */ Dict_entry tmp2 = dict[lo]; dict[lo] = dict[mid]; dict[mid] = tmp2; } } int left = lo+1; // start one past lo since already handled lo int right = hi-1; // similarly if (left >= right) return; // if three or fewer we are done Dict_entry partition = dict[mid]; for (;;) { while (dict[right].canonical.compareTo(partition.canonical) > 0) { --right; } while (left < right && dict[left].canonical.compareTo(partition.canonical) <= 0) { ++left; } if (left < right) { /* swap */ Dict_entry tmp = dict[left]; dict[left] = dict[right]; dict[right] = tmp; --right; } else { break; } } quickSort(lo, left); quickSort(left+1, hi); }; public void sort() { System.out.println("Sorting started"); quickSort(0, num_words - 1); System.out.println("Sorting ended"); } private int bsearch(String canonical) { int length = num_words; int first = 0; int middle; int half; while (length > 0) { half = length / 2; middle = first + half; if (dict[middle].canonical.compareTo(canonical) < 0) { first = middle + 1; length = length - half - 1; } else { /* value is in lower half */ length = half; } } if ((first != num_words) && (dict[first].canonical.compareTo(canonical) == 0)) { return(first); } else { return(-1); } } public void find(String canonical) { int index = bsearch(canonical); if (index == -1) { /* no matches found */ System.out.println ("No jumbles found"); } else { /* walk thru list posting ALL found matches */ System.out.println("Following jumbles found:"); boolean match = true; while (match) { System.out.println(dict[index].string); index++; if ((index >= num_words) || (canonical.compareTo(dict[index].canonical) != 0)) { match = false; } } } } }; public class Jumble { private String candidate; String canonical; Dict dictionary; public Jumble(String jumbled) { candidate = new String(jumbled); canonical = Canonical.canonicalize(candidate); dictionary = new Dict(); dictionary.sort(); /* dictionary.dump(); */ dictionary.find(canonical); }; public static void main (String args[]) { if (args.length != 1) { System.out.println ("Usage: Jumble"); return; } Jumble jumble = new Jumble(args[0]); return; }; };