/*
    This simple extension of the java.awt.Frame class
    contains all the elements necessary to act as the
    main window of an application.
 */

import twinfeats.pilot.pdb.*;
import twinfeats.util.*;

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

public class Boggle extends Frame {
	public static final int SIZE = 0x2000;

	long compares = 0;
	long processcount = 0;
	long nodecountstart = 0;
	long time = 0;
	int wordcount;
	int nodenum;
	CreatePDB pdb;
	long parentrelinkedcount=0;
	long siblingrelinkedcount=0;
	
	byte[] dawgrec = new byte[5*SIZE];
	byte[] nodebytes = new byte[5];
/*
	The word list compression mechanism is DAWG. The physical pdb layout is as follows:
	
	word 4:
	bit 7: end of word
	bit 6: high order bit of sibling node number
	bit 5: high order bit of child node number
	bits 4-0: character
	
	words 3-2:
	child node number
	
	words 1-0:
	sibling node number
	
	Nodes are numbered from each trie level down, left to right.
	*/
   
	int compressDAWG(DataInputStream dis) throws IOException {
		int n,i;
		String s;
		DAWGNode root = new DAWGNode();
		byte[] node;
		byte[] word;
		int idx,count=0;
		
		while(true) {
			s = dis.readLine();
			if (s == null) break;
			if (s.equals("")) continue;
			count++;
			if ((count%1000) == 0)
				Status.setText("Words processed: "+count);
			word = s.getBytes();
			for (idx=0;idx<word.length;idx++) {
				word[idx] = (byte)(word[idx]-0x61);
			}
			addWord(root,word,0);
		}
		nodecountstart = countNodes(root.child);
    	Status.setText("#DAWG nodes: "+nodecountstart);
    	System.out.println("#DAWG nodes: "+nodecountstart);
		uncountNodes(root.child);
		long t = System.currentTimeMillis();
		System.out.println("minimizing trie...");
		compressTrie(root.child,root.child);
		System.out.println("#parent relinked="+parentrelinkedcount);
		System.out.println("#sibling relinked="+siblingrelinkedcount);
		addSiblingRedirectors(root.child);
		System.out.println("done minimizing trie, output serialized dawg...");
		time = System.currentTimeMillis()-t;
		count = countNodes(root.child);
		try {
			System.out.println("saveDawg...");
			saveDAWG(root.child);
	    	FileOutputStream fos = new FileOutputStream("dawg.out");
	    	DataOutputStream dos = new DataOutputStream(fos);
	    	printWords(root.child,new StringBuffer(30),dos);
	    	dos.close();
	    	fos.close();
	    	System.out.println("#words: "+wordcount);
			fos = new FileOutputStream("dawg");
			ObjectOutputStream oos = new ObjectOutputStream(fos);
			oos.writeObject(root);
			oos.close();
			fos.close();
    	}
    	catch (Exception e) {
    		e.printStackTrace();
    	}
		System.out.println("done outputing serialized dawg...");
		return count;
	}
	
	void addWord(DAWGNode parent, byte[] w, int offset) {
		DAWGNode node,last=null;;
		for (node=parent.child;node!=null;node=node.sibling) {
			if (node.letter == w[offset]) {
				addWord(node,w,offset+1);
				return;
			}
			last = node;
		}
		//if we get here, node not found and last contains the last node
		//in this list.
		node = new DAWGNode(parent,w[offset]);
		if (last != null) {
			last.sibling = node;
			node.prev = last;
		}
		else
			parent.child = node;
		for (int i=offset+1;i<w.length;i++) {
			last = new DAWGNode(node,w[i]);
			node.child = last;
			node = last;
		}
		node.end = true;
	}
	
	void addSiblingRedirectors(DAWGNode node) {
		DAWGNode n,t;
		for (n=node;n!=null;n=n.sibling) {
			if (n.siblingrelinked) {	//we need to add a redirectory node
				t = new DAWGNode();
				t.sibling = n.sibling;
				t.letter = 0x1f;
				n.sibling = t;
			}
			if (n.child != null)
				addSiblingRedirectors(n.child);
		}
	}
	
	boolean compareSubgraphs(DAWGNode n1, DAWGNode n2) {
		boolean rc = true;
		if (n1 == n2) return false;
		compares++;
		if ((n1.letter == n2.letter))
		if (n1.end == n2.end)
		if ((n1.child==null)==(n2.child==null))
		if (((n1.sibling==null)==(n2.sibling==null))) {
		 	if (n1.sibling != null)
				rc = compareSubgraphs(n1.sibling,n2.sibling);
			if (rc && n1.child != null)
				rc = compareSubgraphs(n1.child,n2.child);
			return rc;
		}
		return false;
	}
	
	void compressTrie(DAWGNode root, DAWGNode node) {
		processcount++;
		if (processcount%1000 == 0)
			System.out.println("Compressing subtrie: "+processcount);
		DAWGNode n;
		for (n=node;n!=null;n=n.sibling) {
			compressSubgraphs(root,n);
			//if the above compressSubgraphs relinked the current node to an existing subtrie, then
			//we can skip processing it's chidren since they've already been processed
			if (n.parentrelinked)
				continue;
			if (n.child != null)
				compressTrie(root,n.child);
			//if the above compressTrie relinked the current node to an existing subtrie, then
			//we can skip processing it's siblings since they've already been processed
			if (n.prev != null && n.prev.siblingrelinked) {
				break;
			}
		}
	}
	
	//ok, now this is tricky. When we are compressing the entire trie we
	//are processing from the current node looking for subtrie at that
	//node. The net effect is that in compressSubgraphs root is *always*
	//either equal to node or is a previous/parent node. This is critical
	//to how the subtries are relinked and pruned to gain compression.
	boolean compressSubgraphs(DAWGNode root, DAWGNode node) {
		DAWGNode n,tn;
		boolean rc = true;
		for (n=root;n!=null && n != node;n=n.sibling) {
			if (compareSubgraphs(n,node)) {	//added the true parm, see comment below
				//replace the subtrie node with the subtrie n
				if (node.prev != null) {
					node.prev.sibling = n;
					node.prev.siblingrelinked = true;
					siblingrelinkedcount++;
				}
				else {
					node.parent.child = n;
					node.parent.parentrelinked = true;
					parentrelinkedcount++;
				}
				//looks too damn easy, huh?
				break;
			}
			else if (n.child != null) {
				if (n.parentrelinked)
					continue;
				rc = compressSubgraphs(n.child,node);
				if (!rc)
					break;
			}
			if (n.siblingrelinked)
				return true;
		}
		return n==null;
	}
	
	int countNodes(DAWGNode root) {
		DAWGNode n;
		int count = 0;
		for (n=root;n!=null;n=n.sibling) {
			if (n.visited) {
				continue;
			}
			n.visited = true;
//			System.out.print((char)(n.letter+0x61));
			count++;
			if (n.child != null)
				count += countNodes(n.child);
		}
		return count;
	}
	
	void uncountNodes(DAWGNode root) {
		DAWGNode n;
		for (n=root;n!=null;n=n.sibling) {
			n.visited = false;
//			System.out.print((char)(n.letter+0x61));
			if (n.child != null)
				uncountNodes(n.child);
		}
	}
	
	void Compress_Action(Event event) {
		// to do: place event handler code here.
	    FileDialog fd = new FileDialog(this,"Select dictionary file",FileDialog.LOAD);
	    fd.setFile("dict.txt");
	    fd.show();
	    File f = new File(fd.getDirectory());
	    File fn = new File(f,fd.getFile());
        Compressor c = new Compressor(this,fn);
	}

	void DeserializeDAWG_Action(Event event) {
		// to do: place event handler code here.
	    FileDialog fd = new FileDialog(this,"Select DAWG",FileDialog.LOAD);
	    fd.setFile("dawg");
	    fd.show();
	    File f = new File(fd.getDirectory());
	    File fn = new File(f,fd.getFile());
	    try {
	    	System.out.println("Deserializing DAWG...");
	    	FileInputStream fis = new FileInputStream(fn);
	    	ObjectInputStream ois = new ObjectInputStream(fis);
	    	DAWGNode root = (DAWGNode)ois.readObject();
	    	System.out.println("...done");
	    	ois.close();
	    	fis.close();
	    	wordcount = 0;
/*
	    	FileOutputStream fos = new FileOutputStream("dawg.out");
	    	DataOutputStream dos = new DataOutputStream(fos);
	    	printWords(root.child,new StringBuffer(30),dos);
	    	dos.close();
	    	fos.close();
	    	System.out.println("#words: "+wordcount);
*/
			saveDAWG(root.child);
	    }
	    catch (Exception e) {
	    	e.printStackTrace();
	    }
	}

	void saveDAWG(DAWGNode node) throws Exception {
		nodenum = 0;
      pdb = new CreatePDB("WordList",(short)0,(short)1,0,"Data","WBox",6,0);
		uncountNodes(node);
      numberNodes(node);
      uncountNodes(node);
		nodenum = 0;
      writeNodes(node);
		if (nodenum > 0) {
			PDBRecord pdbrec = new PDBRecord(dawgrec,nodenum,true);
			pdb.addRecord(pdbrec);
			System.out.println("adding pdb record size="+nodenum);
		}
		pdb.writePDB("dawg.pdb");
	}
	
	void numberNodes(DAWGNode node) {
		DAWGNode n;
		for (n=node;n != null;n=n.sibling) {
			if (n.visited)
				continue;
			n.number = nodenum;
			n.visited = true;
			nodenum++;
		}
		for (n=node;n != null;n=n.sibling) {
			if (n.child != null)
				numberNodes(n.child);
		}
	}
	
	void writeNodes(DAWGNode node) {
		DAWGNode n;
		byte[] rec;
		for (n=node;n != null;n=n.sibling) {
			if (n.visited)
				continue;
			n.visited = true;
			rec = makeNodeRec(n);
			System.arraycopy(rec,0,dawgrec,(n.number%SIZE)*5,5);
			nodenum += 5;
			if (nodenum == SIZE*5) {
				PDBRecord pdbrec = new PDBRecord(dawgrec,true);
				pdb.addRecord(pdbrec);
				System.out.println("adding pdb record , node number="+n.number);
				nodenum = 0;
			}
		}
		for (n=node;n != null;n=n.sibling) {
			if (n.child != null)
				writeNodes(n.child);
		}
	}
	
	byte[] makeNodeRec(DAWGNode n) {
		nodebytes[0] = 0;
		nodebytes[1] = 0;
		nodebytes[2] = 0;
		nodebytes[3] = 0;
		nodebytes[4] = 0;
		nodebytes[0] |= n.letter;
		if (n.end)
			nodebytes[0] |= 0x80;
		if (n.sibling == null) {
			nodebytes[0] |= 0x40;
			nodebytes[3] = (byte)0xff;
			nodebytes[4] = (byte)0xff;
		}
		else {
			if (n.sibling.number >= 0x10000) {
				nodebytes[0] |= 0x40;
				nodebytes[3] = (byte)((n.sibling.number&0x0000ffff) >> 8);
				nodebytes[4] = (byte)(n.sibling.number&0x000000ff);
			}
			else {
				nodebytes[3] = (byte)((n.sibling.number) >> 8);
				nodebytes[4] = (byte)(n.sibling.number&0x000000ff);
			}
		}
		if (n.child == null) {
			nodebytes[0] |= 0x20;
			nodebytes[1] = (byte)0xff;
			nodebytes[2] = (byte)0xff;
		}
		else {
			if (n.child.number >= 0x10000) {
				nodebytes[0] |= 0x20;
				nodebytes[1] = (byte)((n.child.number&0x0000ffff) >> 8);
				nodebytes[2] = (byte)(n.child.number&0x000000ff);
			}
			else {
				nodebytes[1] = (byte)((n.child.number) >> 8);
				nodebytes[2] = (byte)(n.child.number&0x000000ff);
			}
		}
		return nodebytes;
	}
	
	void printWords(DAWGNode node, StringBuffer word, DataOutputStream dos) throws IOException {
		if (node.letter != 0x1f)
			word.append((char)(node.letter+0x61));
		if (node.end) {
			dos.writeBytes(word.toString());
			dos.writeBytes("\n");
			wordcount++;
		}
		if (node.child != null)
			printWords(node.child,word,dos);
		if (node.letter != 0x1f)
			word.setLength(word.length()-1);
			
		if (node.sibling != null) {
			printWords(node.sibling,word,dos);
		}
	}
	
    static Enumeration Sort(Hashtable h) {
        int n=h.size();
        Vector v = new Vector(n);
        Enumeration e = h.elements();
        String t;
        while (e.hasMoreElements()) {
            v.addElement(e.nextElement());
        }
        int incr = n/2;
        while (incr >= 1) {
            for (int i=incr;i<n;i++) {
                t = (String)v.elementAt(i);
                int j = i;
                while (j >= incr && t.compareTo((String)v.elementAt(j-incr)) < 0) {
                    v.setElementAt(v.elementAt(j-incr),j);
                    j -= incr;
                }
                v.setElementAt(t,j);
            }
            incr /= 2;
        }
        return v.elements();
    }
    
	void About_Action(Event event) {
		//{{CONNECTION
		// Action from About Create and show as modal
//		(new AboutDialog(this, true)).show();
		//}}
	}

	void Exit_Action(Event event) {
		//{{CONNECTION
		// Action from Exit Create and show as modal
//		(new QuitDialog(this, true)).show();
		//}}
	}

	public Boggle() {

		//{{INIT_CONTROLS
		setLayout(null);
		addNotify();
		resize(insets().left + insets().right + 405,insets().top + insets().bottom + 479);
		openFileDialog1 = new java.awt.FileDialog(this, "Open",FileDialog.LOAD);
		//$$ openFileDialog1.move(37,277);
		Status = new java.awt.TextField();
		Status.setEditable(false);
		Status.reshape(insets().left + 71,insets().top + 13,314,22);
		add(Status);
		label1 = new java.awt.Label("Status:",Label.RIGHT);
		label1.reshape(insets().left + 9,insets().top + 13,55,21);
		add(label1);
		WordList = new java.awt.TextArea();
		WordList.reshape(insets().left + 210,insets().top + 44,189,428);
		add(WordList);
		Puzzle = new java.awt.TextArea();
		Puzzle.reshape(insets().left + 11,insets().top + 47,186,225);
		Puzzle.setFont(new Font("Courier", Font.BOLD, 24));
		add(Puzzle);
		Input = new java.awt.TextArea();
		Input.reshape(insets().left + 10,insets().top + 313,184,135);
		Input.setFont(new Font("Courier", Font.BOLD, 12));
		add(Input);
		setTitle("A Basic Application");
		//}}

		//{{INIT_MENUS
		mainMenuBar = new java.awt.MenuBar();

		menu1 = new java.awt.Menu("File");
		menu1.add("Compress");
		menu1.add("Deserialize DAWG");
		menu1.addSeparator();
		menu1.add("Exit");
		mainMenuBar.add(menu1);

		menu3 = new java.awt.Menu("Help");
		mainMenuBar.setHelpMenu(menu3);
		menu3.add("About");
		mainMenuBar.add(menu3);
		setMenuBar(mainMenuBar);
		//$$ mainMenuBar.move(4,277);
		//}}
	}

	public Boggle(String title) {
	    this();
	    setTitle(title);
	}

    public synchronized void show() {
    	move(50, 50);
    	super.show();
    }

	public boolean handleEvent(Event event) {
    	if (event.id == Event.WINDOW_DESTROY) {
            hide();         // hide the Frame
            dispose();      // free the system resources
            System.exit(0); // close the application
            return true;
    	}
		return super.handleEvent(event);
	}

	public boolean action(Event event, Object arg) {
		if (event.target instanceof MenuItem) {
			String label = (String) arg;
			if (label.equalsIgnoreCase("Compress")) {
				Compress_Action(event);
				return true;
			} else
			if (label.equalsIgnoreCase("About")) {
				About_Action(event);
				return true;
			} else
				if (label.equalsIgnoreCase("Exit")) {
					Exit_Action(event);
					return true;
			} else
			if (label.equalsIgnoreCase("Deserialize DAWG")) {
				DeserializeDAWG_Action(event);
				return true;
			}
		}
		return super.action(event, arg);
	}

	static public void main(String args[]) {
	    (new Boggle()).show();
	}

	//{{DECLARE_CONTROLS
	java.awt.FileDialog openFileDialog1;
	java.awt.TextField Status;
	java.awt.Label label1;
	java.awt.TextArea WordList;
	java.awt.TextArea Puzzle;
	java.awt.TextArea Input;
	//}}

	//{{DECLARE_MENUS
	java.awt.MenuBar mainMenuBar;
	java.awt.Menu menu1;
	java.awt.Menu menu2;
	java.awt.Menu menu3;
	//}}
    static final int used = 0x10;
    
    static Vector allwords;
    static byte[] word=new byte[25];
    static int WordCount;
    static int Lengths[];
    static int Words[];
    static boolean dictReady = false;
    static byte[] dict;
    static int index2[] = new int[26*26];
    static int index3[] = new int[26*26*26];
    static int Board[] = new int[25];					/* 5x5 grid */
    static String Letters;
    static String Cubes[] =	/* 25 6-sided cubes */
    {
    	"QBZJXK",	/*  0 */
    	"HHLRDO",	/*  1 */
    	"TELPCI",	/*  2 */
    	"TTOTEM",   /*  3 */
    	"AEAEEE",	/*  4 */
    	"TOUOTO",	/*  5 */
    	"NHDTHO",	/*  6 */
    	"SSNSEU",	/*  7 */
    	"SCTIEP",	/*  8 */
    	"YIFPSR",	/*  9 */
    	"OVWRGR",	/* 10 */
    	"LHNROD",	/* 11 */
    	"RIYPRH",	/* 12 */
    	"EANDNN",	/* 13 */
    	"EEEEMA",	/* 14 */
    	"AAAFSR",	/* 15 */
    	"AFAISR",	/* 16 */
    	"DORDLN",	/* 17 */
    	"MNNEAG",	/* 18 */
    	"ITITIE",	/* 19 */
    	"AUMEEG",	/* 20 */
    	"YIFASR",	/* 21 */
    	"CCWNST",	/* 22 */
    	"UOTOWN",	/* 23 */
    	"ETILIC"	/* 24 */
    };
}

class Compressor extends Thread {
	DataInputStream dis;
	FileInputStream fis;
    public Compressor(Boggle boggle, File f) {
        super();
        m_boggle = boggle;
        try {
        	fis = new FileInputStream(f);
        	dis = new DataInputStream(fis);
	        start();
	    }
	    catch (Exception e) {
	    	e.printStackTrace();
	    }
    }

    public void run() {
        try {
	        int count = m_boggle.compressDAWG(dis);
	        dis.close();
    	    fis.close();
    	    m_boggle.time = m_boggle.time/1000;
    	    if (m_boggle.time == 0)
    	    	m_boggle.time = 1;
    	    m_boggle.Status.setText("#DAWG nodes: "+count+"/"+m_boggle.nodecountstart+", compares="+m_boggle.compares+",n/s="+count/m_boggle.time);
    	    System.out.flush();
    	    System.out.println("#DAWG nodes: "+count+"/"+m_boggle.nodecountstart+", compares="+m_boggle.compares+",n/s="+count/(m_boggle.time/1000));
    	    System.out.flush();
    	}
    	catch (Exception e) {
    		e.printStackTrace();
    	}
    }
    
    Boggle m_boggle;
}

class DAWGNode implements Serializable {
	static final long serialVersionUID =  1L;

	static int count = 0;
	byte letter;
	DAWGNode sibling;
	DAWGNode prev;
	DAWGNode child;
	DAWGNode parent;
	boolean end;
	boolean parentrelinked,siblingrelinked;

	boolean visited;
	
	transient int number;
	
	DAWGNode() {
	}
	
	DAWGNode(byte b) {
		letter = b;
		count++;
	}
	
	DAWGNode(DAWGNode parent,byte b) {
		this(b);
		this.parent = parent;
	}
	
	DAWGNode(DAWGNode n) {
		n.letter = letter;
		n.sibling = sibling;
		n.child = child;
		n.end = end;
	}
}