/*  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;
    };
};

    Source: geocities.com/drhenke