/**
 * code to implement a binary tree to store a lexicon
 */

import java.lancs.* ;

class LexiconNode
    {
    String word ;
    int occurrenceCount ;
    LexiconNode left, right ;

    public LexiconNode(String s)
	{
	word = s ;
	occurrenceCount = 1 ;
	left =  null ;
	right = null ;
	} // end of constructor method
    } // end of class LexiconNode

class Lexicon
    {
    LexiconNode first ;
    int elementCount ;

    public Lexicon()
	{
	first = null ;
	elementCount = 0 ;
	} // end of constructor method

    public int getElementCount()
	{
	return elementCount ;
	} // end of method getElementCount

    // iterative version of the "add" method
    public void add(String s)
	{
	if (first == null)
	    {
	    first = new LexiconNode(s) ;
	    elementCount++ ;
	    return ;
	    }

        LexiconNode pointer = first ;
	while (true)
	    {
	    int result = s.compareTo(pointer.word) ;
	    if (result == 0)
	        {
	        pointer.occurrenceCount++ ;
	        return ;
	        }
	    else if (result < 0)
	        {
	        if (pointer.left == null)
	 	    {
		    pointer.left = new LexiconNode(s) ;
		    elementCount++ ;
		    return ;
		    }
	        else
		    pointer = pointer.left ;
	        }
	    else // result > 0
	        {
	        if (pointer.right == null)
		    {
		    pointer.right = new LexiconNode(s) ;
		    elementCount++ ;
		    return ;
		    }
	        else
		    pointer = pointer.right ;
	        }

	    }
        } // end of method add

    // recursive version of the "add" method
    /* public void add(String s)
	{
	first = addToTree(first, s) ;
	} // end of method add

    public LexiconNode addToTree(LexiconNode pointer, String s)
	{
	if (pointer == null)
	    {
	    elementCount++ ;
	    return new LexiconNode(s) ;
	    }
        else
	    {
	    int result = s.compareTo(pointer.word) ;
	    if (result == 0)
	        pointer.occurrenceCount++ ;
            else if (result < 0)
		pointer.left = addToTree(pointer.left, s) ;
	    else // result > 0
		pointer.right = addToTree(pointer.right, s) ;
	    return pointer ;
	    }
	} // end of method addToTree */

    private void displayLexiconElement(LexiconNode current)
	{
	if (current != null)
	    {
	    displayLexiconElement(current.left) ;
	    System.out.println(current.word + "   " + current.occurrenceCount) ;
	    displayLexiconElement(current.right) ;
	    }
	} // end of method displayLexiconElement

    public void display()
	{
	displayLexiconElement(first) ;
	} // end of method display
    } // end of class Lexicon

public class Chapter18n5
    {
    public static void main(String[] args) throws Exception
	{
	int noWords ;

	// open the file and initialise the lexicon
	BasicIo.prompt("file to read? ") ;
	String fileName = BasicIo.readString() ;
	WordFile file = new WordFile(WordFile.INPUT, fileName) ;
	Lexicon lex = new Lexicon() ;
	noWords = 0 ;

	while (true)
	    {
	    String word = file.readWord() ;
	    if (word == null)
		break ;

	    lex.add(word) ;
	    noWords++ ;
	    }

	file.closeFile() ;
	System.out.println("The Lexicon is") ;
	System.out.println("==============") ;
	lex.display() ;
	System.out.println("\nNo of words read " + noWords) ;
	System.out.println("No of distinct words read " +
					lex.getElementCount()) ;
	} // end of main method
    } // end of class Chapter18n5