/*  Jumble for Java Applet -- DRH */
import java.net.*;
import java.io.*;
import java.applet.*;
import java.util.*;
import java.awt.*;
import java.io.FileInputStream;
import java.io.DataInputStream;

/************************************************************/
public class Jumble extends Applet
{
 String canonical;
 Dict _dict;
 TextField _input;
 TextField _output;

 public Jumble ()
    {
     _dict = null;
     /* layout manager for entire applet */
     setLayout(new BorderLayout());

     /* construct the user input area */
     Panel inputPanel = new Panel();
     inputPanel.setLayout(new FlowLayout(FlowLayout.LEFT));
     Label inputLabel = new Label("Enter jumble:");
     _input = new TextField(20);
     inputPanel.add("West", inputLabel);
     inputPanel.add("East", _input);
     _input.setBackground(Color.pink);
     _input.setForeground(Color.black);


     /* construct output text area */
     Panel outputPanel = new Panel();
     outputPanel.setLayout(new FlowLayout(FlowLayout.LEFT));
     Label outputLabel = new Label("Results:");
     _output = new TextField(25);
     outputPanel.add("West", outputLabel);
     outputPanel.add("East", _output);
     _output.setBackground(Color.cyan);
     _output.setForeground(Color.magenta);

     /* add/position all areas to top level (applet) panel */
     add("North", inputPanel);
     add("South", outputPanel);
    };

 public void init()
    {
     _dict = new Dict();
     _dict.init();
    };

 public void stop()
    {
     return;
    }

 void handleNewWord(String s)
    {
     Vector results = _dict.find(s);
     String output = "";
     if(results.isEmpty())
        {
         output = output + "No match found for " + s;
        }
     else
        {
         for (int i = 0; i < results.size(); i++)
            {
             output = output + "  " + (String)results.elementAt(i);
            }
        }
     _output.setText(output);
    };

 public boolean action(Event e, Object arg)
    {
     if(e.id == Event.ACTION_EVENT)
        {
         if (e.target == _input)
            {
             String word = _input.getText();
             handleNewWord(word);
             return true;
            }
        }
     return true;
    };

 public static void main (String args[])
    {
     /* for debugging only */
     Frame frame = new Frame();
     Jumble jumble = new Jumble();
     jumble.init();
     jumble.start();
     frame.add("Center", jumble);
     frame.resize(300, 300);
     frame.show();
    };
};
/*************************************************************/

/************************************************************/
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;
 public BufferedReader input_dict;

 public void init()
    {
     boolean done;
     String line;
     URL url_name;
     InputStream url_stream;
     InputStreamReader url_stream_reader;

     try 
        {
         url_name = new URL("http://www.geocities.com/drhenke/words.txt");
         url_stream = url_name.openStream();
         url_stream_reader = new InputStreamReader(url_stream);
         input_dict = new BufferedReader(url_stream_reader);
        }
     catch (Exception e)
        {
         return;
        }

     num_words = 0;
     dict = new Dict_entry[94000];
     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)
            {
             return; 
            }
        }
     sort();
    };

 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);
    };

 void sort()
    {
     quickSort(0, num_words - 1);
    }

 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 Vector find(String word)
    {
     String canonical = Canonical.canonicalize(word);
     Vector results = new Vector();
     int index = bsearch(canonical);
     if (index != -1)
        {
         /* walk thru list posting ALL found matches */
         boolean match = true;
         while (match)
            {
             results.addElement(dict[index].string);
             index++;
             if ((index >= num_words) || (canonical.compareTo(dict[index].canonical) != 0))
                {
                 match = false;
                }
            }
        }
      return results;
    }
};
/************************************************************/