/* -------------------------------------------------------------------------- */
/*                                                                            */
/*                              WORD BINARY TREE                              */
/*                                                                            */
/*                                Frans Coenen                                */
/*                                                                            */
/*                          Tuesday 20 December 2005                          */
/*              (Modified Monday 3 July 2006, Tuesday 11 July 2006)           */
/*                                                                            */
/*                       Department of Computer Science                       */
/*                        The University of Liverpool                         */
/*                                                                            */
/* -------------------------------------------------------------------------- */

//package lucsKDD_ARM;

/** Contains methods to generate a binary tree to store all the words
representesd by a set of documents. Each node in the tree is an instance of the
class <TT>WordBinTreeNode</TT>. The methods in this class also process the word
bin tree to identify significant words.
@author Frans Coenen
@version 20 December 2005   */

public class WordBinTree {

    /* ------------------------------- */
    /*                                 */
    /*              FIELDS             */
    /*                                 */
    /* ------------------------------- */

    /** Maximum number of significant word allowed. */
    private int maxNumSigWords = 2500;
    /** The number of classes. */
    private int numClasses = 0;
    /** The given significance index. */
    private double sigIndex = 0.0;

    /* REFERENCES */
    /** Reference to start of bin tree. */
    private WordBinTreeNode wordBinTreeStart = null;

    /* DATA STRUCTURE */
    /** 2D array in which to store training set of binary valued ARM data,
    each attribute representing a keyword. */
    private short[][] trainingDataArray = null;
    /** Array of PotentialSigWord nodes in which to store the list of words
    from which the final set of significant words will be selected. */
    private PotentialSigWord[] potSigWordList = null;
    /** Documents per class in training set. */
    private int[] docsPerClass = null;

    /* DIAGNOSTIC FIELDS */
    /** Total number of words in document base. */
    private int totalNwordsInDB = 0; 
    /** Number of pruned words above Upper Noise Threshold (UNT) . */
    private int wordsAboveUNT = 0;
    /** Number of pruned words below Lower Noise Threshold (LNT) . */
    private int wordsBelowLNT = 0;
    /** Number of non-distinguishing words. */
    private int ordinaryWords = 0;
    /** Number of potential signifuicant words (i.e. number of enties in
    potential significant word list). */
    private int numPotSigWords = 0;
    /** Number of significant words. */
    private int sigWords = 0;
    /** Total number of words in documenmt base per class. */
    private int[] totalNwordsInDBperClass = null;

    /* FLAGS */
    /** Significant word contribution calculation strategy. */
    private String sigWordContCalcStrat = null;
    /** Potential significant word list generation strategy. */
    private String potSWlistGenStrat    = null;
    /** Significant word selection strategy. */
    private String sigWordSelectStrat   = null;

    /* ------------------------------------ */
    /*                                      */
    /*              CONSTRUCTORS            */
    /*                                      */
    /* ------------------------------------ */

    /** three argument constructor.
    @param nClasses the number of classes represented in the documnet base.
    @param the newMaxValue the desired maximum number of permitted significant
    words value.
    @param sigI the given sitgnificance index.
    @param newSWcontCalcStrat desired significant word contribution calculation
    strategy.
    @param newPotSWgenStrat desired potential significant word list generation
    strategy.
    @param newSWselectStrat desired significant word selection strategy.*/

    public WordBinTree(int nClasses, int newMaxValue, double sigI,
    			String newSWcontCalcStrat, String newPotSWgenStrat,
			                         String newSWselectStrat) {
        numClasses           = nClasses;
	maxNumSigWords       = newMaxValue;
	sigIndex             = sigI;
	sigWordContCalcStrat = newSWcontCalcStrat;
	potSWlistGenStrat    = newPotSWgenStrat;
	sigWordSelectStrat   = newSWselectStrat;
	
	// Define total number of words in document base per class array.
	totalNwordsInDBperClass = new int[nClasses];
	for (int index=0;index<totalNwordsInDBperClass.length;index++) 
		totalNwordsInDBperClass[index]=0;
	}

    /* ------------------------------------ */
    /*                                      */
    /*                 METHOS               */
    /*                                      */
    /* ------------------------------------ */

    /* --------------------------------------------------------- */
    /*              METHODS TO GENERATE WORD BIN TREE            */
    /* --------------------------------------------------------- */

    /** Starts recursive process of adding word to bin tree.
    @param word to be added.
    @param docNum the document number.
    @param classNum the identification number for the current document class.	 */

    public WordBinTreeNode addToWordBinTree(String word, int docNum,
                                                             int classNum) {
        // Upadate totals
	totalNwordsInDB++;
	totalNwordsInDBperClass[classNum]++;
	
	// Check for empty tree.
	if (wordBinTreeStart==null) {
	    wordBinTreeStart = new WordBinTreeNode(word,docNum,numClasses,
                                                                   classNum);
	    return(wordBinTreeStart);
	    }
	else return(addToWordBinTree(wordBinTreeStart,docNum,word,classNum));
	}

    /** Continues process of adding word to bin tree.
    @param node the current location in the bin tree.
    @param docNum the document number.
    @param word to be added.
    @param classNum the identification number for the current document class.
    @retun the relevant bin tree node. */

    private WordBinTreeNode addToWordBinTree(WordBinTreeNode currentNode,
    				     int docNum, String word, int classNum) {
        int selector = word.compareTo(currentNode.word);

	// Comparison
	if (selector == 0) {	// Same
	    updateWordBinTreeNode(currentNode,docNum,classNum);
	    return(currentNode);
	    }
	else if (selector < 0) {	// Before
	    if (currentNode.beforeBranch==null) {
	        WordBinTreeNode newWordBinTreeNode = new WordBinTreeNode(word,
					         docNum,numClasses,classNum);
	    	currentNode.beforeBranch = newWordBinTreeNode;
		return(newWordBinTreeNode);
		}
	    else return(addToWordBinTree(currentNode.beforeBranch,docNum,word,
	    						         classNum));
	    }
	else {	// After
	    if (currentNode.afterBranch==null) {
	        WordBinTreeNode newWordBinTreeNode = new WordBinTreeNode(word,
		 			         docNum,numClasses,classNum);
	        currentNode.afterBranch = newWordBinTreeNode;
		return(newWordBinTreeNode);
		}
	    else return(addToWordBinTree(currentNode.afterBranch,docNum,word,
	    						         classNum));
	    }
	}

    /** Updates existing node in word bin tree, increments the word frequency 
    and (if not previously recorded) the support for word at current node with 
    respect to the current document and adds document number to list of 
    documents.
    @param node the current node in the bin tree.
    @param docNum the document number.
    @param classNum the ID number of the class that the current document
    belongs to. */

    private void updateWordBinTreeNode(WordBinTreeNode node, int docNum, 
                                                                int classNum) {
        // Increment word frequency
	node.wordFrequency++;
	// Increment word frequency in class
	node.classFrequency[classNum]++;
	
	// Check that word has not been accounted for previously and if not add
	// to bin tree.
	if (node.notPrerviouslyInDoc) {
	    // Increment support
	    node.support++;
	    // Set flag
            node.notPrerviouslyInDoc = false;
	    // Add class support
	    node.classSupport[classNum] = node.classSupport[classNum]+1;
	    // Add document number
	    addToDocNumbers(node,docNum);
	    }
	}

    /** public void setAdds a document number to the document list for the
    current word.
    @param node the current node in the phrase bin tree.
    @param docNum the ID number of the current document.  */

    private void addToDocNumbers(WordBinTreeNode node, int newDocNum) {
        // Declare new document numbers array
        int length = node.docNumbers.length+1;
	int[] newDocNums = new int[length];

	// Copy existing document numbers
	int index=0;
	for (;index<node.docNumbers.length;index++) {
	    newDocNums[index] = node.docNumbers[index];
	    }

	// Add new document number and end
	newDocNums[index] = newDocNum;
	node.docNumbers = newDocNums;
	}

    /* ------------------------------------------- */
    /*                                             */
    /*              PRUNE WORD BIN TREE            */
    /*                                             */
    /* ------------------------------------------- */

    /** Commences process of pruning word bin tree. <P>Words below or above the
    noise thresholds are marked as such in the bin tree. Remaining words are
    considered (for the time being to be ordionary) but the "contribution" to
    each class is calculated. Bin tree Pruning is only appropriate for certain
    significant/keyword identification processes.
    @param lowerNT the lower noise threshold in terms of number of documents.
    @param upperNT the upper noise threshold in terms of number of documents.
    @param numRows the number of records in training set.	*/

    public void pruneWordBinTree(int lowerNT, int upperNT, int numRows) {
        // Outout significance contribution calculation stratgey
	System.out.println("Significance contribution calculation stratgey = " +
                                                         sigWordContCalcStrat);
							 
	// Procced						 
	pruneWordBinTree(wordBinTreeStart,lowerNT,upperNT,numRows);
	}

    /** Continues process of identifying ("pruning") words below or above
    support thresholds to leave only potential significant words. <P>If a word
    is potentially significant it is first described as an ordinary word, later
    when the potential significant word list is created and processed these
    ordinary (potentially significant) words may be redesignated as significant
    words.
    @param node the current location in the bin tree.
    @param lowerNT the lower support threshold.
    @param upperNT the upper support threshold.
    @param numRows the number of records in training set.              */

    private void pruneWordBinTree(WordBinTreeNode node, int lowerNT,
                                                  int upperNT, int numRows) {
        if (node != null) {
            if (node.support<=lowerNT) {
	        wordsBelowLNT++;
		node.isLowerNoiseWord  = true;
                }
	    else if (node.support>=upperNT) {
                wordsAboveUNT++;
		node.isUpperNoiseWord  = true;
                }
	    else {
	        calculateContribution(node,numRows);
		ordinaryWords++;
		node.isOrdWord = true;
		}
            // Class support array (containing support counts per class)
	    // no longer required so set to null;
	    node.classSupport = null;
	    // Continue
	    pruneWordBinTree(node.beforeBranch,lowerNT,upperNT,numRows);
	    pruneWordBinTree(node.afterBranch,lowerNT,upperNT,numRows);
	    }
        }

    /* ----------------------------------------------------------- */
    /*                                                             */
    /*              CALCULATE SIGNIFICANCE CONTRIBUTION            */
    /*                                                             */
    /* ----------------------------------------------------------- */

    /** Commences provess of calculating signifiance contribution by selecting
    desired calculation strategy. <P>The support count is the number of
    documents the word appears in (count of 1 per document), the frequency 
    count is the number of times the word appears in the entire document set
    (count of n per document).
    @param node the current location in the bin tree.
    @param numRows the number of records in training set.    */

    private void calculateContribution(WordBinTreeNode node, int numRows) {
	// Select stratgey: (i) word support, (ii) word frequency or (iii)
	//error.
	if (sigWordContCalcStrat.equals("Word Support")) 
	                                      calcContribWordSup(node,numRows);
	else if (sigWordContCalcStrat.equals("Word Frequency"))
	                                     calcContribWordFreq(node,numRows);
	else System.out.println("ERROR: Unrecognised significant word " +
		                            "contribution selection strategy");
	}

    /* CALCULATE CONTRIBUTION (WORD SUPPORT) */

    /** Calculates the signifcance contribution of the word which is later
    used to determine whether given word is a distinguishing (significant)
    word or not, i.e. can be used to distinguish between classes or otherwise
    using the word support calculation strategy. <P>Proceed as follows:
    <OL>
    <LI>Calculate local support for word in each class in terms of the number
    occurances of the word in the class with respect to the number of documents
    in the class.
    <LI>Calculate the global support.
    <LI>Find the contibution (fraction) of each local support value to the
    global support value.
    </OL>
    If contribution does not exceed the desired index (G) this indicates that
    the word does not serve to differentiate between classes (note that given
    an appropriate value of G it is possible for a word to be significant with
    respect to more than one class). If all contributions are 1 then the word
    is distributed equally over the classess. If contribution with respect to
    a particular class is greater than 1 then the word has some significance
    with respect to the class.
    @param node the current location in the bin tree.
    @param numRows the number of records in training set.         */

    private void calcContribWordSup(WordBinTreeNode node, int numRows) {
	// Calculate (percenatge) local support for word for each class
	double[] localSups = new double[numClasses];
	double total = 0.0;
        for (int index=0;index<node.classSupport.length;index++) {
	    // Avoid devide by zero error
            if (docsPerClass[index] != 0) localSups[index] = 100.0 *
	    			          ((double) node.classSupport[index]/
                                               (double) docsPerClass[index]);
	    else localSups[index] = 0;
            // Total number of occurances so far
	    total = total + node.classSupport[index];
	    }

	// Find global support
	double globalSupport = 100.0*((double) total/(double) numRows);

	// Calculate contributions and store
	for (int index=0;index<localSups.length;index++) {
	    localSups[index] = localSups[index]/globalSupport;
	    node.contribution[index] = (short) ((localSups[index]*100)+0.5);
	    }
	}

    /* CALCULATE CONTRIBUTION (WORD FREQUENCY) */

    /** Calculates the signifcance contribution of the word which is later
    used to determine whether given word is a distinguishing (significant)
    word or not, i.e. can be used to distinguish between classes or otherwise
    using the word frequency calculation strategy. 
    @param node the current location in the bin tree.
    @param numRows the number of records in training set.         */

    private void calcContribWordFreq(WordBinTreeNode node, int numRows) {
        double divisor = 
	                  (double) node.wordFrequency/(double) totalNwordsInDB;
	  
	// Determine contributions
	for (int index=0;index<totalNwordsInDBperClass.length;index++) {
	    double denominator = (double) node.classFrequency[index]/
	                               (double) totalNwordsInDBperClass[index];
	    double quotiant = denominator/divisor;
	    node.contribution[index] = (short) ((quotiant*100)+0.5); 
	    }
	}
    	 
    /* ----------------------------------------------------------------- */
    /*                                                                   */
    /*              GENERATE POTENTIAL SIGNIFICANT WORD LIST             */
    /*                                                                   */
    /* ----------------------------------------------------------------- */

    /** Commences process of generating list of potential significant wiords.
    <P>These are ordinary words that serve to distinguish between classes. A
    word is not significant if it serves to distinguish between groups of 2 or
    more classes. Note that contribution value is rased by 10^2 so sigIndix
    value must also be raised by the same amount.	 */

    public void generatePotentialSigWordList() {
        System.out.println("Potential Sig. Word. list generation stratgey = " +
                                                            potSWlistGenStrat);
							    
        // Include all words with contribution above G in potential significant
        // word list (likely to include words that are significant for more than
        // one class).
        if (potSWlistGenStrat.equals("All Significant Words")) 
	                                               genPotSWlistWithAllSW();

        // Include all unique words with contribution above G in potential
        // significant word list (i.e. words that are potentially significant
        // for one class only).
        else if (potSWlistGenStrat.equals("Unique Sig. Words")) 
	                                            genPotSWlistWithUniqueSW();

        // Error
        else System.out.println("ERROR: Unrecognised potential significant " +
             "word list generation strategy.");
        }

    /* GENERATE POTENTIAL SIGNIFICANT WORD LIST WITH ALL SIGNIFICANT WORDS */

    /** Commences process of generating list of potential significant words
    where list contains all available potential significant words, i.e. those
    with a significance contribution above the given significance threshold (G).
    <P>Note that contribution value is rased by 10^2 so sigIndix value must
    also be raised by the same amount.	 */

    private void genPotSWlistWithAllSW() {
        // Raise significance index (so that contributions can be output to two
	// decimal places).
	int sigI = (int) (sigIndex*100.0);

	// Get number of potentially significant words and check
	numPotSigWords = getNumPotSigWords(sigI);
	if (numPotSigWords==0) return;

	// Dimension potential significant words list
	potSigWordList = new PotentialSigWord[numPotSigWords];

	// Populate list by processing word bin tree
        int pswlIndex=0;
	populatePotSWlist(wordBinTreeStart,pswlIndex,sigI);

	// Order list
	sortPotSigWordList();
	}

    /** Recursively populates list of potential significant words by processing
    word bin tree. <P>Word is only entered once into the potential significant
    word list even if it is potentially significant with respect to a number of
    classes.
    @param node the current word bin tree node in the recirsion
    @param pswlIndex the current index in to the potential significant words
    list.
    @param sigI the significance index reaised by 100.
    @return the new index in to the potential significant words list.*/

    private int populatePotSWlist(WordBinTreeNode node, int pswlIndex,
                                                                   int sigI) {
	if (node != null) {
	    // Process before branch
	    pswlIndex = populatePotSWlist(node.beforeBranch,pswlIndex,sigI);
	    // Process node by first finding class with best contribution. If
	    // this is better than significance threshold add to potential
	    // significant word list.
	    double bestContrib = node.contribution[0];
	    short bestIndex    = 0; 
	    for (short index=1;index<node.contribution.length;index++) {
	        if (node.contribution[index]>bestContrib) {
		    bestContrib = node.contribution[index];
	            bestIndex   = index; 
	            }
		}
	    // Add to list?
	    if (bestContrib>sigI) {
		potSigWordList[pswlIndex] =
		                        new PotentialSigWord(node,bestIndex);
	        pswlIndex = pswlIndex+1;
		}
	    // Process after branch
	    pswlIndex = populatePotSWlist(node.afterBranch,pswlIndex,sigI);
	    }

	// Return
	return(pswlIndex);
	}

    /* GET NUMBER OF POTENTIAL SIGNIFICANT WORDS. */

    /** Gets the number of (potential) significant words. <P>A word is counted
    more once only regardless of whether it is potentially significant for more
    than one class. Note also that the contribution value hasd been raised by
    10^2 so sigIndix value must also be raised by the same amount.
    @param sifIndex the significance index raised by 100.
    @return the count so far.     */

    private int getNumPotSigWords(int sigI) {
	int count=0;

	// Generate count
        if (wordBinTreeStart!=null) count =
	                        getNumPotSigWords(wordBinTreeStart,sigI,count);

	// Return
	return(count);
	}

    /** Continues process of counting number of potential significant words.
    <P>Contribution value is rased by 10^2 so sigIndix value has also
    (temporarily) been raised by the same amount.
    @param node the current location in the bin tree.
    @param sifIndex the significance index raised by 100.
    @param countSoFar the current count.
    @return the count so far. */

    private int getNumPotSigWords(WordBinTreeNode node, int sigI,
    							     int countSoFar) {
	// Process node
	if (node != null) {
	    // Process before branch
	    countSoFar = getNumPotSigWords(node.beforeBranch,sigI,countSoFar);
	    // Process node.
	    for (int index=0;index<node.contribution.length;index++) {
                if (node.contribution[index]>sigI) {
	            countSoFar=countSoFar+1;
	            break;
                    }
                }
	    // Process after branch
	    countSoFar = getNumPotSigWords(node.afterBranch,sigI,countSoFar);
	    }

	// Return
	return(countSoFar);
	}

    /* GENERATE POTENTIAL SIGNIFICANT WORD LIST WITH UNIQUE SIGNIFICANT WORDS */

    /** Commences process of generating list of unique potential significant
    words. <P>Thus a candidate word is not considered potentially significant if
    it serves to distinguish between groups of 2 or more classes. Note also that
    contribution value is rased by 10^2 so sigIndix value must also be raised by
    the same amount.	 */

    private void genPotSWlistWithUniqueSW() {
        // Raise significance index (so that contributions can be output to two
	// decimal places).
	int sigI = (int) (sigIndex*100.0);

	// Get number of potentially significant words and check
	numPotSigWords = getNumPotUniqueSigWords(sigI);
	if (numPotSigWords==0) return;

	// Dimension potential significant words list
	potSigWordList = new PotentialSigWord[numPotSigWords];

	// Populate list by processing word bin tree
        int pswlIndex=0;
	populateUniquePotSWlist(wordBinTreeStart,pswlIndex,sigI);

	// Order list
	sortPotSigWordList();
	}

    /** Recursively populates list of unique potential significant words by
    processing word bin tree.
    @param node the current word bin tree node in the recirsion
    @param pswlIndex the current index in to the potential significant words
    list.
    @param sigI the significance index reaised by 100.
    @return the new index in to the potential significant words list.*/

    private int populateUniquePotSWlist(WordBinTreeNode node, int pswlIndex,
                                                                   int sigI) {
	if (node != null) {
	    // Process before branch
	    pswlIndex = populateUniquePotSWlist(node.beforeBranch,pswlIndex,
                                                                           sigI);
	    // Process node, count number of classes for which word is
	    // potentially significant and if this is 1 add to the potential
	    // significant word list
	    int tempCounter = 0;
	    short classIndex  = 0;
	    for (short index=0;index<node.contribution.length;index++) {
	        if (node.contribution[index]>sigI) {
		    tempCounter++;
		    classIndex=index;
		    }
		}
	    if (tempCounter==1)  {
		potSigWordList[pswlIndex] =
		                        new PotentialSigWord(node,classIndex);
	        pswlIndex = pswlIndex+1;
		}
	    // Process after branch
	    pswlIndex = populateUniquePotSWlist(node.afterBranch,pswlIndex,sigI);
	    }

	// Return
	return(pswlIndex);
	}

    /* GET NUMBER OF POTENTIAL UNIQUE SIGNIFICANT WORDS. */

    /** Gets the number of inique potential significant words in the word bin
    tree. <P>Note that contribution value is rased by 10^2 so sigIndix value
    must also be raised by the same amount.
    @param sifIndex the significance index raised by 100.
    @return the count so far.     */

    private int getNumPotUniqueSigWords(int sigI) {
	int count=0;

	// Generate count
        if (wordBinTreeStart!=null) count =
	                   getNumPotUniqueSigWords(wordBinTreeStart,sigI,count);

	// Return
	return(count);
	}

    /** Continues process of counting number of potential significant words.
    <P>(Contribution value has been rased by 10^2 so sigIndix value has also
    (temporarily) been raised by the same amount.
    @param node the current location in the bin tree.
    @param sifIndex the significance index raised by 100.
    @param countSoFar the current count.
    @return the count so far. */

    private int getNumPotUniqueSigWords(WordBinTreeNode node, int sigI,
    							    int countSoFar) {
	// Process node
	if (node != null) {
	    // Process before branch
	    countSoFar = getNumPotUniqueSigWords(node.beforeBranch,sigI,countSoFar);
	    // Process node, count number of classes for which word is
	    // potentially significant and if this is 1 increment count by 1.
	    int tempCounter = 0;
//System.out.print("Word = " + node.word);
	    for (int index=0;index<node.contribution.length;index++) {
//System.out.print(" " + node.contribution[index]);
	                    if (node.contribution[index]>sigI) tempCounter++;
		}
//System.out.println();
	    if (tempCounter==1) countSoFar=countSoFar+1;
	    // Process after branch
	    countSoFar = getNumPotUniqueSigWords(node.afterBranch,sigI,countSoFar);
	    }

	// Return
	return(countSoFar);
	}

    /* -------------------------------------------- */
    /*                                              */
    /*              ID SIGNIFICANT WORDS            */
    /*                                              */
    /* -------------------------------------------- */

    /** Commences process of identifying significant word by selecting desired
    strategy.
    @return the number of significant words (used in keyword only mode). */

    public int idSignificantWords() {
        // Check if any potential significant words exist
	if (potSigWordList==null) {
	    System.out.println("WARNING: No potential significant words " +
	    				"identified\n");
	    return(sigWords);
            }
	    
	// Output
	System.out.println("Sig. Word. identification stratgey = " +
	           sigWordSelectStrat + ", N is " + maxNumSigWords + " words.");
            
        // Select strategy: (i) First N words, (ii) First N words with even 
	// distribution (ED) across classes or (iii) error.
        if (sigWordSelectStrat.equals("First N")) idSignificantWordsAll();
        else if (sigWordSelectStrat.equals("First N (distributed)")) 
	                                             idSignificantWordsWithED();
	else System.out.println("ERROR: Unrecognised significant word " +
		                                          "selection strategy");

	// Return
	return(sigWords);
        }

    /* IDENTIFY FIRST N SIGNIFICANY WORDS WITH EVEN DISTRIBUTION */

    /** Identify first N significant words in the potential significant words
    list. <P>All potential significant words are iniatially identified as
    ordinary words, thus for each allocated significant word the ordinary word
    count must be decremented by one and the significant word count incremented
    by one.    */

    private void idSignificantWordsAll() {
        // Determine end
        int end = 0;
        if (potSigWordList.length<maxNumSigWords) end=potSigWordList.length;
        else end = maxNumSigWords;

        // Process potential significant words list
	for (int index=0;index<end;index++) {
	    potSigWordList[index].wordBinTreeNode.isSigWord = true;
	    potSigWordList[index].wordBinTreeNode.isOrdWord = false;
	    sigWords++;
	    ordinaryWords--;
	    }
	}

    /* IDENTIFY SIGNIFICANY WORDS WITH EVEN DISTRIBUTION */

    /** Identify significant words, these are the first N words in the
    potential significant words list for each class, where N is claculated
    by dividing the maximum permitted number of significant words by the number
    of classes. <P>If there are not sufficient words in a class then any
    unassigned potential significant words, starting from the top of the list,
    are identified as significant words. If the number of potential significant
    words is less than the maximum peritted number all the potential words
    become significant. All potential significant words are iniatially
    identified as ordinary words, thus for each allocated significant word the
    ordinary word count must be decremented by one and the significant word
    count incremented by one). */

    private void idSignificantWordsWithED() {
	// If less potentail significant words than desired maximum then all
	// potential significant words are considered to be significant.
	if (potSigWordList.length<=maxNumSigWords) idSWwithEDall();
	else idSignificantWordsSome();
	}

    /** Identifies a subset of the potential significant words list as
    significant by selecting words so that an even distribution across classes
    is obtained (if possible).<P>Proceed as folows:
    1. Define an array to hold significant word counts per class (same length as
    number of classes.
    2. Determine max number of sig. words per class.
    3. Process potential significant word list an attempt to fill up quota for
    each class with significant words (note that a significant word allocated to
    a class may also be significant for another class. */

    private void idSignificantWordsSome() {
        // Define an array to hold significant word counts per class.
	int[] counterArray = new int[numClasses];

	// Determine max number of sig. words per class
	int classMax = maxNumSigWords/numClasses;

	// Process potential significant word list
	for (int index=0;index<potSigWordList.length;index++) {
	    // Get counter array index
	    int caIndex = potSigWordList[index].classIndex;
	    // Check counter array, if OK set isSigWord field to true and
	    // isOrdWord field to false (by default non-noise words are all
	    // ordinary), then increemt/decrement counters/
	    if (counterArray[caIndex]<classMax) {
	        potSigWordList[index].wordBinTreeNode.isSigWord = true;
		potSigWordList[index].wordBinTreeNode.isOrdWord = false;
		sigWords++;
	        ordinaryWords--;
	        counterArray[caIndex]++;
	        }
	    // Check if max sig words reached, i.e. all classes full.
	    if (sigWords>=maxNumSigWords) break;
	    }

	// Add top N unsassigned words to make up maximum.
	int sigWordsStillToGo = maxNumSigWords-sigWords;

	// Identify remaining significant words.
	for (int index=0;index<potSigWordList.length;index++) {
	    if (sigWordsStillToGo==0) break;
	    // Otherwise process word
	    if (!potSigWordList[index].wordBinTreeNode.isSigWord) {
	        potSigWordList[index].wordBinTreeNode.isSigWord = true;
		potSigWordList[index].wordBinTreeNode.isOrdWord = false;
	        sigWords++;
	        ordinaryWords--;
	        sigWordsStillToGo--;
		}
	    }
	}

    /** Identifies all potential significant words as significant words.  */

    private void idSWwithEDall() {
	// Process potential significant words list
	for (int index=0;index<potSigWordList.length;index++) {
	    potSigWordList[index].wordBinTreeNode.isSigWord = true;	    
	    potSigWordList[index].wordBinTreeNode.isOrdWord = false;
	    sigWords++;
	    ordinaryWords--;
	    }
	}

    /* -------------------------------------------------------- */
    /*              GENERATE TRAINING DATA ARRAY (KEY WORDS)    */
    /* -------------------------------------------------------- */
    
    /** Commences process of recasting training set as array of attributes with 
    each key word representing a single attribute number --- used in keyword
    mode only (not in phrase mode). 
    @param numDocs the number of documents in the training set. 
    @param docBase the training set document base comprising a set of reference
    to nodes in the word bin tree.
    @param return the training data array. */
    
    public short[][] genTrainingDataArray(int numDocs, 
                                             TrainingSetDocumentBase docBase) {
        // Attributes are numbered from 1
	final short START_ATT_NUM = 1;
	
	// Initialise document array in which to store training set.
        trainingDataArray = new short[numDocs][];
	for (int index=0;index<trainingDataArray.length;index++) 
				       trainingDataArray[index] = new short[0];
					
	// Populate data array by processing word bin tree
	short lastAttNum = generateDataArray(wordBinTreeStart,START_ATT_NUM);
	addClassNumbers(lastAttNum,docBase);
	
	// return
	return(trainingDataArray);
	}
    
    /** Continues process of recasting training set as array of attributes
    (each attribute representing a key word). <P> Proceeds by processing word
    bin tree node by node, each word bin tree node includes a list of the
    documents in which the word represented by the node are contained. Note 
    that documents are numbered from 1 onwards while the data array is indexed 
    starting from zero therefore it is necessary to subtract 1 from the 
    document number to obtian the array index. If word is a key (significant)
    word add it to trainuing data array by including its attribute number.
    @param node the current location in the phrase bin tree.
    @param attNum the current attrivute number. */

    private short generateDataArray(WordBinTreeNode node, short attNum) {
        if (node != null) {
	    // Left Branch
	    attNum = generateDataArray(node.beforeBranch,attNum);
            // Process node
	    if (node.isSigWord) {
	        addToDataArray(node.docNumbers,attNum);
		attNum++;
		}
	    // Right Branch		
	    attNum = generateDataArray(node.afterBranch,attNum);
	    }
	    
	// End
	return(attNum);
	}

    /** Adds keyword attibute to appropriate locations in data array. Note 
    that documents are numbered from 1 onwards while the data array is indexed 
    starting from zero therefore it is necessary to subtract 1 from the 
    document number to obtian the array index. 
    @param docNumbers the list of documents in which the attribute appears. 
    @param attNum the current attrivute number.	*/
    
    private void addToDataArray(int[] docNumbers, short attNum) {
        // Process document numbers array
        for(int docNumIndex=0;docNumIndex<docNumbers.length;docNumIndex++) {
	    // Get document number (index into the data array)
	    int docNumber         = docNumbers[docNumIndex];
	    // Get length of training data array record so far
	    int length            = trainingDataArray[docNumber].length;
	    // Create a temprary record
	    short[] tempDataArray = new short[length+1];
	    // Add attribute number to records in data array, first copy
	    // record, then add attribute number, and then reassign.
	    int index             = 0;
	    for (;index<trainingDataArray[docNumber].length;index++) 
	    	  tempDataArray[index] = trainingDataArray[docNumber][index]; 
	    // Add new attribute number
	    tempDataArray[index]    = attNum;
	    // Reassign to data array
	    trainingDataArray[docNumber] = tempDataArray;
	    }
	}

    /** Adds class numbers to training data array
    @param lastAttNum the attribute number for the first class label.
    @param docBase reference to the TrainingSetDocumentBase object. */
    
    private void addClassNumbers(short lastAttNum, 
                                        TrainingSetDocumentBase docBase) {

        for (short docIndex=0;docIndex<trainingDataArray.length;docIndex++) {
	    short classNum = (short)
	    	                   (docBase.getClassLabel(docIndex)+lastAttNum);
	    int length            = trainingDataArray[docIndex].length;
	    short[] tempDataArray = new short[length+1];
	    int index             = 0;
	    // Add class number to record, first copy record, then add 
	    // class number, and then reassign.
	    for (;index<trainingDataArray[docIndex].length;index++) 
	    	 tempDataArray[index] = trainingDataArray[docIndex][index]; 
	    // Add new attribute number
	    tempDataArray[index]    = classNum;
	    // Reassign to data array
	    trainingDataArray[docIndex] = tempDataArray;
	    }
        }

    /* ---------------------------------------------------- */
    /*              GENERATE TEST DATA ARRAY (KEY WORDS)    */
    /* ---------------------------------------------------- */

    /** Commences process of recasting a single test set document into an array 
    of attributes with each significant word contained in the test set document
    represented by a single attribute number 
    @param testDocBase the given instance of the class TestSetDocBase contining
    a list (String array) of all the words represented in the test set document
    @param dovNum the current document number. 
    @param classNum the class ID number for the current document. */

    public void convertTestDocToAtts(TestSetDocumentBase testDocBase,
                                                int docNum, short classNum) {
        final short START_ATT_NUM = 1;

        // Generate attributes
	short lastAttNum = generateTestDataArray(testDocBase,
                                wordBinTreeStart,docNum,START_ATT_NUM);

	// Add class number
	testDocBase.addToDataArray(docNum,(short) (classNum+lastAttNum));
	}


    /** Continues process of recasting test set as array of attributes, each
    attribute representing a key word. <P>Proceeds in a recursive manner by 
    processing the word bin tree.
    @param testDocBase the given instance of the class TestSetDocBase.
    @param node the current location in the word bin tree.
    @param docNum the current document number.
    @param attNum the current attribute number. */

    private short generateTestDataArray(TestSetDocumentBase testDocBase,
                WordBinTreeNode node, int docNum, short attNum) {
        if (node != null) {
	    // Left Branch
	    attNum = generateTestDataArray(testDocBase,node.beforeBranch,
                                                                docNum,attNum);
            // Process word at node (method in TestSetDocumentBase class).
            if (node.isSigWord) {
	        testDocBase.findInTestSetDoc(node.word,docNum,attNum);
		attNum++;
		}
	    // Right Branch
	    attNum = generateTestDataArray(testDocBase,node.afterBranch,
                                                                docNum,attNum);
	    // Return
	    return(attNum);
	    }
	else return(attNum);
	}
	
    /* ------------------------------------ */
    /*              SET METHODS             */
    /* ------------------------------------ */

    /** Commences processes of walking through word bin tree and, for each 
    node, setting the <TT>notPrerviouslyInDoc</TT> flag to true ready for 
    processing the next training set document. */
    
    public void setDocNumbersToZero() {
        setDocNumbersToZero(wordBinTreeStart);
	}

    /** Continues process of of walking through word bin tree and, for each 
    node, setting the <TT>notPrerviouslyInDoc</TT> flag to true ready for 
    processing the next training set document.
    @param node the current location in the bin tree.	 */
    
    private void setDocNumbersToZero(WordBinTreeNode node) {
	if (node != null) {
	    // Process before branch
	    setDocNumbersToZero(node.beforeBranch);
	    // Process node if unpruned word
            node.notPrerviouslyInDoc=true;
	    // Process after branch
	    setDocNumbersToZero(node.afterBranch);
	    }
	}

    /** Sets documents per class array to the given values.
    @param newDocsPerClass the given numbers of documents per class. */
    
    public void setDocsPerClass(int[] newDocsPerClass) {
        docsPerClass = new int[newDocsPerClass.length];
	
	// process given array
	for (int index=0;index<docsPerClass.length;index++) 
				docsPerClass[index] = newDocsPerClass[index]; 
	}

    /* ------------------------------------ */
    /*              GET METHODS             */
    /* ------------------------------------ */
    
    /* GET NUMBER OF NODES WORD IN BIN TREE */
    
    /** Commences process of counting number of nodes in word bin tree. 
    <P> NOTE: when defining documents as phrases the word bin tree gets deleted 
    (so as to gain menmory) once the phrase bin tree has been created. This 
    output method must therefore be included either: (i) in the 
    <TT>loadTrainingSetDocumentBase</TT> method in the <TT>TextMining</TT>
    class after the word bin tree has been created, or (ii) in the 
    <TT>processTrainingSetDocumentBase</TT> method in the <TT>PhraseMining</TT>
    class before the word bin tree is deleted.
    @return the number of unpruned nodes.	*/
    
    public int getNumNodesInWordBinTree() {
        final int COUNTER=0;
	
    	return(getNumNodesInWordBinTree(wordBinTreeStart,COUNTER));
	}
    
    /** Continues process of counting number of nodes in word bin tree. 
    @param node the current location in the bin tree. 
    @param countSoFar the number of unpruned nodes counted so far.
    @return the number of unpruned nodes.	*/
    
    public int getNumNodesInWordBinTree(WordBinTreeNode node, int countSofar) {

	if (node != null) {
	    countSofar = countSofar+1;
	    // Process before branch
	    countSofar = getNumNodesInWordBinTree(node.beforeBranch,
	    							countSofar);
	    // Process after branch
	    countSofar = getNumNodesInWordBinTree(node.afterBranch,
	    							countSofar);
	    }
	
	// Return
	return(countSofar);
	}
        
    /* --------------------------------------------------------------------- */
    /*                                                                       */
    /*               POTENTIAL SIGNIFICANBT WORDS BUBBLE SORT                */
    /*                                                                       */
    /* --------------------------------------------------------------------- */

    /** Commences a bubble sort" on the list of potential significant words.
    <P>Has adavantage that it maintains alpha ordering. */	
    
    private void sortPotSigWordList() {
        boolean isOrdered;
        int index;

        do {
	    isOrdered = true;
            index     = 0;
            while (index < (potSigWordList.length-1)) {
                double value1 = getPotSigWordContribValue(index);
		double value2 = getPotSigWordContribValue(index+1);
		if (value1<value2) {
	            isOrdered=false;
                    // Swap
		    PotentialSigWord temp   = potSigWordList[index];
                    potSigWordList[index]   = potSigWordList[index+1];
                    potSigWordList[index+1] = temp;
	            }
	  	index++;
		}
	    } while (isOrdered==false);
    	}   

    /** Determine contribution value for a given index in to the potential
    significant word list. <P>First finds the "cIndex" into the contribution
    array, then gets the contribution array ref, and then the value. <P>Used by
    sort routines.
    @param index the given index into potentia significant word list. 
    @return the contribution.	*/
		
    private int getPotSigWordContribValue(int index) {
        // Get "cIndex" into the contribution array
	int cIndex = (int) potSigWordList[index].classIndex;
	
	// Gets the contribution array ref
	short[] contrib = potSigWordList[index].wordBinTreeNode.contribution;	
	
	// ReturnValue
	return(contrib[cIndex]);
	}
	
    /* -------------------------------------------------------------------- */
    /*                                                                      */
    /*               POTENTIAL SIGNIFICANBT WORDS QUICK SORT                */
    /*                                                                      */
    /* -------------------------------------------------------------------- */

    /** Commences a "quick sort" on the list of potential significant words.
    <P>Algorithm taken from Cay Horstmann's Big Java (2nd Edsition), Wiley. */	
    
    private void sortPotSigWordListQ() {
       int startIndex = 0;
       int endIndex   = potSigWordList.length-1;
       sortPotSigWordListQ(startIndex,endIndex);
       }
       
    /** Performs a "quick sort" on the list of potential significant words.
    @param fromIndex the start index of the current sub-array in the list.
    @param toIndex the end index of the current sub-array in the list.  */
    	
    private void sortPotSigWordListQ(int fromIndex, int toIndex) {
        if (fromIndex<toIndex) {
            // Partion list into two sub lists
	    int pivotIndex = partitionSigWordList(fromIndex,toIndex);
            // Sort partitions	
	    sortPotSigWordListQ(fromIndex,pivotIndex);
	    sortPotSigWordListQ(pivotIndex+1,toIndex);
	    }
	}
    
    /** Partitions a sub-array of the potential significant words list into two 
    further sub arrays either side of the "pivot".
    @param fromIndex the start index of the current sub-array in the list.
    @param toIndex the end index of the current sub-array in the list.  
    @return the final index of the "pivot" value. */
    
    private int partitionSigWordList(int fromIndex, int toIndex) {
        // Determine pivot value. 
	int  pivot   = getPotSigWordContribValue(fromIndex);

        // Define local from and to indexes and values
	int localFrom = fromIndex-1;
	int localTo   = toIndex+1;
	int fromValue = 0;
	int toValue   = 0;
	
	// Partition
	while (localFrom<localTo) {
	    localFrom++;
	    
	    
	    while (fromValue>pivot) {
	        localFrom++;
		fromValue  = getPotSigWordContribValue(localFrom);
		}
	    localTo--;
	    toValue = getPotSigWordContribValue(localTo);
	    while (toValue<pivot) {
	        localTo--;
	        toValue = getPotSigWordContribValue(localTo);
	        }
            // Swop two values
            if (localFrom < localTo) {
                PotentialSigWord temp     = potSigWordList[localFrom];
                potSigWordList[localFrom] = potSigWordList[localTo];
                potSigWordList[localTo]   = temp;
		}
            }
	
	// Return
	return(localTo);
        }
	
    /* ----------------------------------------------------- */
    /*                                                       */
    /*                       OUTPUT                          */
    /*                                                       */
    /* ----------------------------------------------------- */
    
    /* Number of word bin tree and potential significant words outputs options:
    1) Output training data array words (used with keyword mining option).
    2) Output word bin tree Upper Noise Words (UNW).
    3) Output word bin tree Lower Noise Words (LNW).
    4) Output word bin tree Ordinary Words (OW).
    5) Output word bin tree Significant Words (SW).
    6) Output entire word bin tree.
    7) Output word bin tree statistics.
    8) Output keyword N.
    9) Output number of significant words per class.
    10) Output number of potential significant words per class.
    11) Outputs potential significant words list.		
    12) Output words that appear in  one document only (i.e. those with a
    count of 1).	*/
    
    /* OUTPUT TRAINING DATA ARRAY WORDS */

    /** Outputs training data array as sequence of words or phrases.	 
    @param phraseMiningObj the current instance of the class.	 */
    	
    public void outputDataArrayWords(KeyWordMining phraseMiningObj) {
        System.out.println("TRAINING ATTRIBUTE SET (WORDS)");
	System.out.println("================================");
	for (int docIndex=0;docIndex<trainingDataArray.length;docIndex++) {
	    int length = trainingDataArray[docIndex].length-1;
	    // Output attributes
	    for (int index=0;index<length;index++) {
	        outputKeyWordN(trainingDataArray[docIndex][index]);
		System.out.print(" ");
		}
	    // Add class
	    String ClassLiteral = phraseMiningObj.
	               getClassLiteral(trainingDataArray[docIndex][length]);
	    System.out.println(ClassLiteral + "\n");
	    }
	
	// End
        System.out.println("\n");
        }


    /* OUTPUT WORD BIN TREE UPPER NOISE WORDS */
    
    /** Outputs the words in the word bin tree that exceed the upper noise
    threshold. <P> NOTE: when defining documents as phrases the word bin tree 
    gets deleted (so as to gain menmory) once the phrase bin tree has been 
    created. This output method must therefore be included either: (i) in the 
    <TT>loadTrainingSetDocumentBase</TT> method in the <TT>TextMining</TT>
    class after the word bin tree has been created, or (ii) in the 
    <TT>processTrainingSetDocumentBase</TT> method in the <TT>PhraseMining</TT>
    class before the word bin tree is deleted. 		*/
    
    public void outputWordBinTreeUNW() {
        System.out.println("WORD BIN TREE");
	System.out.println("Upper noise threshold words");
	System.out.println("===========================");
        
	if (wordBinTreeStart!=null) {
            int puncCounter=0;
	    outputWordBinTreeUNW(wordBinTreeStart,puncCounter);
	    System.out.println();
	    }
	else System.out.println("EMPTY!\n");

	//End
	System.out.println("\n");
	}

    /** Continues process of outputting upper noise threshold words in word bin 
    tree.
    @param node the current location in the bin tree.	 
    @param puncCounter pinctuation counter.		
    @return punctuation counter sofar. */

    private int outputWordBinTreeUNW(WordBinTreeNode node, int puncCounter) {
	if (node != null) {
	    // Process before branch
	    puncCounter = outputWordBinTreeUNW(node.beforeBranch,puncCounter);
	    // Process node
	    if (node.isUpperNoiseWord) {
	        System.out.print("{" + node.word + " " + node.support);
	        // Classes for which word is significant (Note that 
		// classSupport array have been set to null during pruning of 
		// word Bin tree --- saves space!).
	        if (node.classSupport!=null) {
	            System.out.print(", classes: [");
	            for (int index=0;index<node.classSupport.length;index++) {
	    	        if (index!=0) System.out.print(",");
		        System.out.print(node.classSupport[index]);
	    	        }
	            System.out.print("]");
		    }
	        System.out.print("} ");
		if (puncCounter==5) {
		    System.out.println();
		    puncCounter=0;
		    }
		else puncCounter++;
		}
	    // Process after branch
	    puncCounter = outputWordBinTreeUNW(node.afterBranch,puncCounter);
	    }
	
	// Return
	return(puncCounter);
	}
    
    /* OUTPUT WORD BIN TREE LOWER NOISE WORDS */
    
    /** Outputs the words in the word bin tree that are below the lower noise
    threshold. <P> NOTE: when defining documents as phrases the word bin tree 
    gets deleted (so as to gain menmory) once the phrase bin tree has been 
    created. This output method must therefore be included either: (i) in the 
    <TT>loadTrainingSetDocumentBase</TT> method in the <TT>TextMining</TT>
    class after the word bin tree has been created, or (ii) in the 
    <TT>processTrainingSetDocumentBase</TT> method in the <TT>PhraseMining</TT>
    class before the word bin tree is deleted.		 */
    
    public void outputWordBinTreeLNW() {
        System.out.println("WORD BIN TREE");
	System.out.println("Lower noise threshold words");
	System.out.println("===========================");
        
	if (wordBinTreeStart!=null) {
            int puncCounter=0;
	    outputWordBinTreeLNW(wordBinTreeStart,puncCounter);
	    System.out.println();
	    }
	else System.out.println("EMPTY!\n");

	//End
	System.out.println("\n");
	}

    /** Continues process of outputting lower noise threshold words in word bin 
    tree.
    @param node the current location in the bin tree.	 
    @param puncCounter pinctuation counter.		
    @return punctuation counter sofar.	 */

    private int outputWordBinTreeLNW(WordBinTreeNode node, int puncCounter) {
        if (node != null) {
	    // Process before branch
	    puncCounter = outputWordBinTreeLNW(node.beforeBranch,puncCounter);
	    // Process node
	    if (node.isLowerNoiseWord) {
	        System.out.print("{" + node.word + " " + node.support);
	        // Classes which it is related to.
	        if (node.classSupport!=null) {
	            System.out.print(", classes: [");
	            for (int index=0;index<node.classSupport.length;index++) {
	    	        if (index!=0) System.out.print(",");
		        System.out.print(node.classSupport[index]);
	    	        }
	            System.out.print("]");
		    }
	        System.out.print("} ");
		if (puncCounter==5) {
		    System.out.println();
		    puncCounter=0;
		    }
		else puncCounter++;
		}
	    // Process after branch
	    puncCounter = outputWordBinTreeLNW(node.afterBranch,puncCounter);
	    }
	
	// Return
	return(puncCounter);
	}
	
    /* OUTPUT WORD BIN TREE ORDINARY WORDS */
    
    /** Outputs the words in the word bin tree that are defoned as ordinary
    words. <P> NOTE: when defining documents as phrases the word bin tree gets 
    deleted (so as to gain menmory) once the phrase bin tree has been created. 
    This output method must therefore be included either: (i) in the 
    <TT>loadTrainingSetDocumentBase</TT> method in the <TT>TextMining</TT>
    class after the word bin tree has been created, or (ii) in the 
    <TT>processTrainingSetDocumentBase</TT> method in the <TT>PhraseMining</TT>
    class before the word bin tree is deleted. 		*/
    
    public void outputWordBinTreeOW() {
        System.out.println("WORD BIN TREE");
	System.out.println("Ordinary words");
	System.out.println("==============");
        
	if (wordBinTreeStart!=null) {
            int puncCounter=0;
	    outputWordBinTreeOW(wordBinTreeStart,puncCounter);
	    System.out.println();
	    }
	else System.out.println("EMPTY!\n");

	//End
	System.out.println("\n");
	}

    /** Continues process of outputting ordinary words in word bin tree.
    @param node the current location in the bin tree.	 
    @param puncCounter pinctuation counter.		
    @return punctuation counter sofar.	 */

    private int outputWordBinTreeOW(WordBinTreeNode node, int puncCounter) {
        if (node != null) {
	    // Process before branch
	    puncCounter = outputWordBinTreeOW(node.beforeBranch,puncCounter);
	    // Process node
	    if (node.isOrdWord) {
	        System.out.print("{" + node.word + " " + node.support);
	        // Classes which it is related to.
	        if (node.classSupport!=null) {
	            System.out.print(", classes: [");
	            for (int index=0;index<node.classSupport.length;index++) {
	    	        if (index!=0) System.out.print(",");
		        System.out.print(node.classSupport[index]);
	    	        }
	            System.out.print("]");
		    }
	        System.out.print("} ");
		if (puncCounter==5) {
		    System.out.println();
		    puncCounter=0;
		    }
		else puncCounter++;
		}
	    // Process after branch
	    puncCounter = outputWordBinTreeOW(node.afterBranch,puncCounter);
	    }
	
	// Return
	return(puncCounter);
	}
	
    /* OUTPUT WORD BIN TREE SIGNIFICANT WORDS */
    
    /** Outputs the words in the word bin tree that are defined as significant
    words, i.e. those where the <TT>isSigWord<M/TT>field is set to true, this
    is not necessarily the same as all those words whose significance
    contribution exceeds the significance index (G). 		*/
    
    public void outputWordBinTreeSW() {
        System.out.println("WORD BIN TREE");
	System.out.println("Significant words (support)");
	System.out.println("===========================");
        System.out.println("Format: (N) W S CS Contrib");
	System.out.println("\tN = sequential number, W = word literal,\n\tS " +
	            "= support count, CS = list of support counts per class " +
	              "if available,\n\tContrib = list of contributions per " +
                          "class if available\n\t(* indicates class(es) for " + 
		                                 "which word is significant)");
	if (wordBinTreeStart!=null) {
            int counter=1;
	    outputWordBinTreeSW(wordBinTreeStart,counter);
	    System.out.println();
	    }
	else System.out.println("EMPTY!\n");

	//End
	System.out.println("\n");
	}

    /** Continues process of outputting significant words in word bin tree.
    @param node the current location in the bin tree.	 
    @param counter the counter for the number of significant words.		
    @return punctuation counter sofar.	 */

    private int outputWordBinTreeSW(WordBinTreeNode node, int counter) {
        if (node != null) {
	    // Process before branch
	    counter = outputWordBinTreeSW(node.beforeBranch,counter);
	    // Process node
	    if (node.isSigWord) {
	        // Output word and support
	        System.out.print("(" + counter + ") " + node.word + " " + 
		                                                 node.support);
	        // Classes supports;
	        if (node.classSupport!=null) 
		                     outputSupportClassData(node.classSupport);
	        // Classs contributions
		if (node.contribution!=null) 
		                     outputContribClassData(node.contribution);
	        System.out.println();
		// Increment counter
		counter++;
		}
	    // Process after branch
	    counter = outputWordBinTreeSW(node.afterBranch,counter);
	    }
	
	// Return
	return(counter);
	}
    
     /** Outputs supports per classes if available. 
    @param classData the class support data array*/
    
    private void outputSupportClassData(int[] classData) {
	System.out.print(", Class supportss: [");
	
	// Process class support array
	for (int index=0;index<classData.length;index++) {
	    if (index!=0) System.out.print(",");
	    System.out.print(classData[index]);
	    }
	    
	// End
	System.out.print("]");
	}
	
    /** Outputs contributions per classes if available. 
    @param classData the contribution data array*/
    
    private void outputContribClassData(short[] classData) {
	System.out.print(", Class contrib: [");
	
	// Process class support array
	for (int index=0;index<classData.length;index++) {
	    if (index!=0) System.out.print(",");
	    double contrib = (double) classData[index]/100.0;
	    System.out.print(contrib);
	    if (contrib>sigIndex) System.out.print("*");
	    }
	    
	// End
	System.out.print("]");
	}
     
    /* OUTPUT WORD BIN TREE */
    
    /** Starts recursive process of outputting word bin tree. <P> NOTE: when 
    defining documents as phrases the word bin tree gets deleted (so as to gain 
    menmory) once the phrase bin tree has been created. This output method must 
    therefore be included either: (i) in the 
    <TT>loadTrainingSetDocumentBase</TT> method in the <TT>TextMining</TT>
    class after the word bin tree has been created, or (ii) in the 
    <TT>processTrainingSetDocumentBase</TT> method in the <TT>PhraseMining</TT>
    class before the word bin tree is deleted. */
    
    public void outputWordBinTree() {
        System.out.println("FULL WORD BIN TREE");
	System.out.println("==================");
        
	if (wordBinTreeStart!=null) {
	    int puncCounter = 0;
	    outputWordBinTree(wordBinTreeStart,puncCounter);
	    System.out.println();
	    }
	else System.out.println("EMPTY!\n");

	//End
	System.out.println("\n");
	}

    /** Continues process of outputting word bin tree with indication of nature
    of words stored at nodes (lower noise word (L), upper noise word (U), 
    ordinary word (O), significant word (S)).
    @param node the current location in the bin tree.
    @param puncCounter the punctuation counter sofar.
    @return the current punctuation counter.		 */

    private int outputWordBinTree(WordBinTreeNode node, int puncCounter) {
	
        if (node != null) {
	    // Process before branch
	    puncCounter = outputWordBinTree(node.beforeBranch,puncCounter);
	    // Process node 
            System.out.print("{" + node.word + " " + node.support + " ");
	    // Label
	    if (node.isUpperNoiseWord) System.out.print("-U ");
	    else if (node.isLowerNoiseWord) System.out.print("-L ");
	    else if (node.isOrdWord) System.out.print("-O ");
	    else System.out.print("-S ");
	    // Classes which it is related to.
	    if (node.classSupport!=null) {
	        System.out.print(", classes: [");
	        for (int index=0;index<node.classSupport.length;index++) {
	    	    if (index!=0) System.out.print(",");
		    System.out.print(node.classSupport[index]);
	    	    }
	        System.out.print("]");
		}
	    System.out.print("} ");
	    // Punctuation
	    if (puncCounter==5) {
	    	System.out.println();
		puncCounter = 0;
		}
	    else puncCounter = puncCounter + 1;
	    // Process after branch
	    puncCounter = outputWordBinTree(node.afterBranch,puncCounter);
	    }
	
	// Return
	return(puncCounter);
	}
	
    /* WORD BIN TREE STATISTICS */
	
    /** Outputs word bin tree statistics. */
    
    public void outputWordBinTreeStats() {
    	    System.out.println("WORD BIN TREE STATISTICS\n" +
			                            "------------------------");                     
            System.out.println("Number of words in bin tree     = " + 
                                                    getNumNodesInWordBinTree()); 	
            System.out.println("Number noise words above UNT    = " + 
	                                                         wordsAboveUNT);
            System.out.println("Number noise words below LNT    = " + 
	                                                         wordsBelowLNT);
            System.out.println("Number ordinary words           = " + 
	                                                         ordinaryWords);
            System.out.println("Number potential Sig. words     = " +
	                                                        numPotSigWords);
	    System.out.println("Number significant (key) words  = " + sigWords);
	    }
	    
    /* OUTPUT KEY WORD N */
    
    /** Commences process of outputting a particular key word (identified by a
    sequential attribute number) within the word bin tree. <P> Note used when
    representing documenys as phrases.
    @param num the given phrase id number. */
    
    public void outputKeyWordN(int num) {
        outputKeyWordN(wordBinTreeStart,num);
	}
    
    /** Continues process of outputting a particular keyword (identified by a
    sequential number) within the word bin tree.
    @param node the current location in the bin tree.     
    @param num the given phrase id number. */
    
    private int outputKeyWordN(WordBinTreeNode node, int num) {
	if (node != null) {
	    // Check if word already found
	    if (num==0) return(0);
	    // Process before branch
	    num = outputKeyWordN(node.beforeBranch,num);
	    // Current node
	    if (node.isSigWord) {
		if (num == 1) {	   
	            System.out.print(node.word);
		    return(0);
		    }
		else num = num-1;;
		}
	    // Process after branch
	    num = outputKeyWordN(node.afterBranch,num);
	    // Return
	    return(num);
	    }
	else return(num);
	}
    
    /* OUTPUT NUMBER OF SIGNIFICANT WORDS PER CLASS */
    
    /** Gets and outputs number of significant words per class by processing the
    word bin tree. <P>significant words are those where the <TT>isSigWord<M/TT>
    field is set to true, this is not necessarily the same as all those words 
    whose significance contribution exceeds the significance index (G). 		*/
    
    public void outputSigWordsPerClass() {
	// If no significant word list return
	if (potSigWordList==null) {
	    System.out.println("Empty significant words list\n");
	    return;
	    }
	    	
	// Generate output
	int[] sigWordsPerClass = new int[numClasses];
	int[] duplicates = new int[numClasses];
	
	if (wordBinTreeStart!=null) genSigWdsPerClass(wordBinTreeStart,
	                                         sigWordsPerClass,duplicates);
	
	// Output
	System.out.println("Sig. words per class (same word may feature in " + 
	                                                 "several classes!)");
	System.out.println("Class \t| # Sig. Words \t| Duplicates (G = " + 
	                                                      sigIndex + ")");
	System.out.println("-------------------------------------");
	for (int index=0;index<sigWordsPerClass.length;index++) {
	    System.out.println((index+1) + "\t| " + sigWordsPerClass[index] +
	    		                          "\t| " + duplicates[index]);
	    }
	
	// End
	System.out.println("-------------------------------------");
	}

    /** Continues process of outputting significant words in word bin tree.
    @param node the current location in the bin tree.	 
    @param sigWdsPerClas the counter array to record number of significant 
    words per class.		
    @param duplicates the counter array to record number of significant 
    words per class that are duplicated (i.e. are significant for more than one
    class.	 */

    private void genSigWdsPerClass(WordBinTreeNode node, 
                                    int[] sigWdsPerClass, int[] duplicates) {
        if (node != null) {
	    // Process before branch
	    genSigWdsPerClass(node.beforeBranch,sigWdsPerClass,duplicates);
	    // Process node
	    if (node.isSigWord) {
	        // Count number of classes to which word contributes and
		// update sig. words per class array
		int count=0;
		for (int index=0;index<node.contribution.length;index++) {
		    if (node.contribution[index]>sigIndex) {
		        count++;
			sigWdsPerClass[index]++;
			}
		    }
	        // Process duplicates
		int duplicateCount = count-1;
		if (duplicateCount > 0) {
		    for (int index=0;index<node.contribution.length;index++) {
		        if (node.contribution[index]>sigIndex)
		                                           duplicates[index]++;
		        }
		    }   
		}
	    // Process after branch
	    genSigWdsPerClass(node.afterBranch,sigWdsPerClass,duplicates);
	    }
	}
	
    /* OUTPUT NUMBER OF POTENTIAL SIGNIFICANT WORDS PER CLASS */
    
    /** Gets and outputs number of potential significant words per class.   */
    
    public void outputPotSigWdsPerClass() {
	// If no significant word list return
	if (potSigWordList==null) {
	    System.out.println("Empty significant words list\n");
	    return;
	    }
	    
	// Generate output
        int[] sigWordsPerClass = new int[numClasses];
        for (int index=0;index<potSigWordList.length;index++) {
	   sigWordsPerClass[potSigWordList[index].classIndex]++;
	   }
	
	// Output
	System.out.println("Potential Sig. words per class (same word may " +
			   "feature in several classes)\nClass \t| # Pot. " +
			                "Sig. Words (G = " + sigIndex + ")");
	System.out.println("-------------------------------------");
	int total = 0;
	for (int index=0;index<sigWordsPerClass.length;index++) {
	    total = total+sigWordsPerClass[index]; 
	    System.out.println((index+1) + "\t| " + sigWordsPerClass[index]);
	    }
	    
	// End
	System.out.println("-------------------------------------");
	}
   
    /* OUTPUT TOP N POTENTIAL SIGNIFICANT WORDS PER CLASS */
    
    /** Outputs top 10 potential significant words per class.   
    @param topN the number of potemtial significant words to output.
    @param classLabels an array of class label liteerals. */
        
    public void outputTopNpotSigWords(int topN, String[] classLabels) { 
	System.out.println("\nTop " + topN + " potential significant words per " +
	            "class");
	
	// If no significant word list return
	if (potSigWordList==null) {
	    System.out.println("Empty significant words list\n");
	    return;
	    } 
	
	// Loop through classes		    
	System.out.println("Format Word (support in class, support in doc. " +
	                  "set, contribution)\n" +
		          "----------------------------------------------\n");
	for (int classIndex=0;classIndex<numClasses;classIndex++) {
	    int wordCounter=0;
	    System.out.println(classLabels[classIndex] + "\n----------------");
	    for (int wordIndex=0;wordIndex<potSigWordList.length;wordIndex++) {	
	        if (potSigWordList[wordIndex].classIndex==classIndex) {
		    WordBinTreeNode node = 
		                     potSigWordList[wordIndex].wordBinTreeNode;
		    System.out.print(node.word + " (" +
		                        node.classFrequency[classIndex] + "," + 
		                                     node.wordFrequency + "," + 
		        ((double) node.contribution[classIndex]/100.0) + ") ");
		    wordCounter++;
		    }
		if (wordCounter>=topN) break;
		}
	    System.out.println("\n");
	    }
	}    
		    
    /* OUTPUT POTENTIAL SIGNIFICANT WORDS LIST */
    
    /** Outputs the potential significant words list, i.e. words in bin tree
    whose contribution exceeds the significance index (G) and therefore may be
    eventually catagorized as significant. 		*/
    
    public void outputPotentialSigWords() { 
	System.out.println("Potential significant words\n");
	
	// If no significant word list return
	if (potSigWordList==null) {
	    System.out.println("Empty significant words list\n");
	    return;
	    }
	
	// Start output
	System.out.println("#\t|  Pot. Sig. Wd  | Val.\t| Class\t|" +
		                "Sig (Y/N)\n------------------------" +
	                        "-----------------------------------");
			   
	// Process array
        int total=0;
	for (int index=0;index<potSigWordList.length;index++) {
	    System.out.println(index + "\t| " + potSigWordList[index]);
	    if (potSigWordList[index].wordBinTreeNode.isSigWord) total++;
	    }
	    
	// End
	System.out.println("------------------------------------------");
	}	
	
    /* OUTPUT WORD WITH COUNT OF 1 */
    
    /** Outputs the words in the word bin tree that appear in only one document 
    (i.e. those with a count of 1).	*/
    
    public void outputWordsWithCount1() {
        System.out.println("WORD BIN TREE");
	System.out.println("Words with count of 1");
	System.out.println("=====================");
        
	if (wordBinTreeStart!=null) {
	    int count   = 1;
            int wrdCntr = 0;
	    wrdCntr = outputWordsWithCountN(wordBinTreeStart,count,wrdCntr);
	    System.out.println("Total # words that appear in 1 document " +
	    	                                      "only = " + wrdCntr);
	    }
	else System.out.println("EMPTY WORD BIN TREE!\n");

	//End
	System.out.println("\n");
	}

    /** Continues process of outputting words in the word bin tree that have a 
    count of N.
    @param node the current location in the bin tree.	
    @param count the descrired count. 	 
    @param wrdCntr counter for number of words that appear in 1 documen only
    (doubles up as punctuation counter).		
    @return punctuation counter sofar.	 */

    private int outputWordsWithCountN(WordBinTreeNode node, int count, 
                                                              int wrdCntr) {
        if (node != null) {
	    // Process before branch
	    wrdCntr = outputWordsWithCountN(node.beforeBranch,count,wrdCntr);
	    // Process node
	    if (node.support==count) {
	        System.out.print(node.word + " ");
		if (wrdCntr%10==0) {
		    System.out.println();
		    wrdCntr=0;
		    }
		else wrdCntr++;
		}
	    // Process after branch
	    wrdCntr = outputWordsWithCountN(node.afterBranch,count,wrdCntr);
	    }
	
	// Return
	return(wrdCntr);
	}
	
    /* --------------------------------------------------------------------- */
    /*                                                                       */
    /*            DIAGNOSTIC OUTPUT USED DURINF CEVELOPMENT                  */
    /*                                                                       */
    /* --------------------------------------------------------------------- */
    
    /* OUTPUT TRAINING DATA ARRAY */
    
    /** Outputs training data array as sequence of attribute numbers with each
    number representing either a keyword or phrase.	 */
    
    public void outputDataArrayAttributes() {
        System.out.println("TRAINING ATTRIBUTE SET (ATTRIBUTES)");
	System.out.println("===================================");
	for (int docIndex=0;docIndex<trainingDataArray.length;docIndex++) {
	    System.out.println("DOCUMENT " +  docIndex + ": ");
	    for (int index=0;index<trainingDataArray[docIndex].length;index++) {
	        System.out.print(trainingDataArray[docIndex][index] + " ");
		}
	    System.out.println("\n");
	    }
	
	// End
        System.out.println("\n");
        } 
    }