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

public class WordTree
{
    private BinaryNode root;
    public static final int NUM_LETTERS = 7;

    public WordTree()
    {
		root = null;
    }

    public WordTree(BufferedReader file) throws IOException
    {
		String word;
		int wordCount = 0;
		int insertCount = 0;
		
		while ((word = file.readLine()) != null)
		{
			wordCount++;
			if (word.length() <= NUM_LETTERS)
			{
				insert(new ScrabbleWord(word));
				insertCount++;
			}
		}
		file.close();
		System.out.println("Number of words read: " + wordCount);
		System.out.println("Number of words inserted (length <= " + NUM_LETTERS + "): " + insertCount);
    }

    public void insert(ScrabbleWord w)
    {
	root = insertHelper(root,w,0);
    }

    private BinaryNode insertHelper(BinaryNode root, ScrabbleWord w, int level)
    {
	if (root == null)
	    return new BinaryNode(w,level);

	if (((Comparable)root.getData()).compareTo(w) == 0)
	{
	    if (root.getList() == null)
		root.setList(new LList());
	    root.getList().addAtFront(w);
	    return root;
	}
	// if w is < root's data, recursively insert on left subtree,
	// set current node's left to whatever's returned and then return
	// (modified) current node
	if (((Comparable)root.getData()).compareTo(w) > 0)
	    root.setLeft(insertHelper(root.getLeft(),w,level+1));
	else
	    root.setRight(insertHelper(root.getRight(),w,level+1));
	//then return root back to caller
	return root;
    }

    public BinaryNode find(ScrabbleWord w)
    {
	return findHelper(root,w);
    }

    private BinaryNode findHelper(BinaryNode root, ScrabbleWord w)
    {
	if (root == null)
	    return null;

	// if equal, return
	if (((Comparable)root.getData()).compareTo(w) == 0)
	    return root;

	// if w < root's data, recursively find on left subtree
	if (((Comparable)root.getData()).compareTo(w) > 0)
	    return findHelper(root.getLeft(),w);

	return findHelper(root.getRight(),w);
    }

    public void findAndPrint(ScrabbleWord w, LList words)
    {
	BinaryNode b = find(w);
	if (b != null && !b.getVisited())
	{
	    b.setVisited(true);
	    // System.out.print(b);
	    words.addAtFront(b.getData());
	    if (b.getList() != null)
	    {
		// System.out.println(" -> " + b.getList());
		words.addList(b.getList());
	    }
	    // else
	        // System.out.println();
	}
    }

    public void findAndReset(ScrabbleWord w)
    {
	BinaryNode b = find(w);
	if (b != null)
	    b.setVisited(false);
    }

    public void inOrder()
    // prints an inorder traversal of the WordTree
    {
	printInOrder(root);
    }

    private void printInOrder(BinaryNode root)
    {
	if (root != null)
	{
	    printInOrder(root.getLeft());
	    System.out.print(root);
	    System.out.println(" (" + root.getList() + ")");
	    printInOrder(root.getRight());
	}
    }

    public void preOrder()
    // prints a preorder traversal of the WordTree
    {
	printPreOrder(root);
    }

    private void printPreOrder(BinaryNode root)
    {
	if (root != null)
	{
	    System.out.println(root);
	    printPreOrder(root.getLeft());
	    printPreOrder(root.getRight());
	}
    }

    public int countNodes()
    {
	return countHelper(root);
    }

    private int countHelper(BinaryNode rt)
    {
	if (rt != null)
	    return 1 + countHelper(rt.getLeft()) + countHelper(rt.getRight());

	return 0;
    }

    public void breadthFirst()
    {
	ArrayList queue = new ArrayList();
	int max = -1;

	if (root != null)
	    queue.add(root);

	while (queue.size() != 0)
	{
	    BinaryNode b = (BinaryNode)queue.remove(0);
	    if (b.getLevel() > max)
		{
		    max = b.getLevel();
		    System.out.print("\nLevel " + max + "\n");
		}
	    System.out.print("  " + ((ScrabbleWord)b.getData()).getWord() + "\n");
	    if (b.getLeft() != null)
		queue.add(b.getLeft());
	    if (b.getRight() != null)
		queue.add(b.getRight());
	}
    }

    // a reasonable attempt at a nice level-ordered print
    public String toString()
    {
	String result = "";
	int level = 0;
	String s;

	while ((s = levelString(root,level)) != null)
	{
	    result += s + "\n";
	    level++;
	}

	return result;
    }

    private String levelString(BinaryNode root, int level)
    {
	if (root == null)
	    return null;

	if (level == 0)
	    return root.getData() + " ";

	String left = levelString(root.getLeft(),level-1);
	String right = levelString(root.getRight(),level-1);

	if (left == null && right == null)
	    return null;

	String result = "";
	if (left != null)
	    result += left;
	if (right != null)
	    result += " " + right;
	return result;
    }

    public static void main(String[] args) throws IOException
    {
	System.out.println("Lab 9 by mjs\n");

	/*
	int length = 3;
	BitSet mask = new BitSet(length);

	for (int i = 0; i < (int)Math.pow(2, length) - 1; i++)
	{
	    addOne(mask, length);
	    System.out.println(i+1 + " " + mask);
	}
	*/

	BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
	String s;
	WordTree tree = null;

	System.out.print("Enter name of dictionary file: ");
	s = input.readLine();

	boolean flag = true;

	do
	{
	    try
	    {
		tree = new WordTree(new BufferedReader(new FileReader(s)));
		flag = false;
	    }
	    catch (FileNotFoundException e)
	    {
		System.out.print("Enter a valid filename: ");
		s = input.readLine();
	    }
	} while (flag);

	//System.out.println(tree);
	System.out.println("Number of canonical forms (nodes in tree) = " + tree.countNodes());
	System.out.print("\nDo you wish to see a breadth-first traversal [y/n]? ");
	s = input.readLine();
	if (s.equals("y"))
	    tree.breadthFirst();

	String str;
	do
	{
	    System.out.print("\nEnter sequence of letters to search for (# to stop): ");
	    str = input.readLine();
	    if (!str.equals("#"))
	    {
		if (str.length() > WordTree.NUM_LETTERS)
		    System.out.println("\tWord exceeds " + WordTree.NUM_LETTERS + " letters and will not be processed!");
		else
		{
		    traversePowerSet(tree, str, true);
		    traversePowerSet(tree, str, false);
		}
	    }
	}
	while (!str.equals("#"));
    }

    public static void traversePowerSet(WordTree tree, String str, boolean printing)
    {
	ScrabbleWord w = new ScrabbleWord(str);
	int length = str.length();
	BitSet mask = new BitSet(length);
	LList[] queue = new LList[length+1];
	for (int i = 1; i < length+1; i++)
	    queue[i] = new LList();

	for (int i = 0; i < (int)Math.pow(2, length) - 1; i++) {
	    addOne(mask, length);
	    String key = "";
	    for (int bit = 0; bit < length; bit++)
		if (mask.get(bit))
		    key += w.getWord().charAt(bit);
	    if (printing)
		tree.findAndPrint(new ScrabbleWord(key), queue[key.length()]);
	    else
		tree.findAndReset(new ScrabbleWord(key));
	}

	if (printing)
	    for (int i = 1; i < length+1; i++)
		if (!queue[i].isEmpty())
		    System.out.println(i + ": " + queue[i]);
    }

    public static void addOne(BitSet b, int length)
    {
	for (int bit = 0; bit < length; bit++)
	    if (!b.get(bit))
	    {
		b.set(bit);
		return;
	    }
	    else if (b.get(bit))
		b.clear(bit);
    }
}
