TotalSupptree.java

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

public class TotalSuppTree extends reorder {

// Data structures
/** The reference to start of t-tree. */
protected TtreeNode[] startTtreeRef;

/** The number of frequent sets (nodes in t-tree with above minimum
support) generated so far. */
protected int numFrequentsets =0;
/** The number of updates required to generate the T-tree. */

/** Processes command line arguments. */
public TotalSuppTree(String[] args) {
super(args);
}

/** Commences process of adding an itemset with its support value to a
T-tree when using a T-tree either as a storage mechanism, or when adding to
an existing T-tree.
@param itemSet The given itemset. Listed in numeric order .
@param support The support value associated with the given itemset. */

public void addToTtree(short[] itemSet, int support) {
// Determine index of last elemnt in itemSet.
int endIndex = itemSet.length-1;

// Add itemSet to T-tree.
startTtreeRef = addToTtree(startTtreeRef,numOneItemSets+1,
endIndex,itemSet,support);
}

/** Inserts a node into a T-tree. Recursive procedure.
@param linkRef the reference to the current array in Ttree.
@param size the size of the current array in T-tree.
@param endIndex the index of the last attribute in the itemset,
which is also used as a level counter.
@param itemSet the given itemset.
@param support the support value associated with the given itemset.
@return the reference to the revised sub-branch of t-tree. */

protected TtreeNode[] addToTtree(TtreeNode[] linkRef, int size, int endIndex,
short[] itemSet, int support) {
// If no array describing current level in the T-tree or T-tree
// sub-branch create one with "null" nodes.
if (linkRef == null) {
linkRef = new TtreeNode[size];
for(int index=1;index linkRef[index] = null;
}

// If null node at index of array describing current level in T-tree
// (T-tree sub-branch) create a T-tree node describing the current
// itemset sofar.
int currentAttribute = itemSet[endIndex];
if (linkRef[currentAttribute] == null)
linkRef[currentAttribute] = new TtreeNode();

// If at right level add support
if (endIndex == 0) {
linkRef[currentAttribute].support =
linkRef[currentAttribute].support + support;
return(linkRef);
}

// Otherwise proceed down branch and return
linkRef[currentAttribute].childRef =
addToTtree(linkRef[currentAttribute].childRef,
currentAttribute,endIndex-1,itemSet,support);
// Return
return(linkRef);
}

/** Commences process of outputting T-tree structure contents to screen. */
public void outputTtree() {
int number = 1;

// Loop

for (short index=1; index < startTtreeRef.length; index++) {
if (startTtreeRef[index] !=null) {
String itemSetSofar =
new Short(reconvertItem(index)).toString();
System.out.print("[" + number + "] {" + itemSetSofar);
System.out.println("} = " + startTtreeRef[index].support);
outputTtree(new Integer(number).toString(),itemSetSofar,
startTtreeRef[index].childRef);
number++;
}
}
}


/** Continue process of outputting T-tree. Operates in a recursive
manner.
@param number the ID number of a particular node.
@param itemSetSofar the label for a T-tree node as generated sofar.
@param linkRef the reference to the current array level in the T-tree. */

private void outputTtree(String number, String itemSetSofar,
TtreeNode[] linkRef) {
// Set output local variables.
int num=1;
number = number + ".";
itemSetSofar = itemSetSofar + " ";

// Check for empty branch/sub-branch.
if (linkRef == null) return;

// Loop through current level of branch/sub-branch.
for (short index=1;index if (linkRef[index] != null) {
String newItemSet = itemSetSofar + (reconvertItem(index));
System.out.print("[" + number + num + "] {" + newItemSet);
System.out.println("} = " + linkRef[index].support);
outputTtree(number + num,newItemSet,linkRef[index].childRef);
num++;
}
}
}
/** Outputs T-tree frequent sets. Operates in a recursive manner.
@param number the number of frequent sets so far.
@param itemSetSofar the label for a T-treenode as generated sofar.
@param size the length/size of the current array level in the T-tree.
@param linkRef the reference to the current array level in the T-tree.
@return the incremented number the number of frequent sets so
far. */

private int outputFrequentSets(int number, String itemSetSofar, int size,
TtreeNode[] linkRef) {

// No more nodes

if (linkRef == null) return(number);

// Otherwise process

itemSetSofar = itemSetSofar + " ";
for (short index=1; index < size; index++) {
if (linkRef[index] != null) {
if (linkRef[index].support >= minSupport) {
String newItemSet = itemSetSofar + (reconvertItem(index));
System.out.println("[" + number + "] {" + newItemSet +
"} = " + linkRef[index].support);
number = outputFrequentSets(number + 1,newItemSet,index,
linkRef[index].childRef);
}
}
}

// Return

return(number);
}

/** Commences the process of counting and outputing number of supported
nodes in the T-tree.A supported set is assumed to be a non null node in
the T-tree. */

public void outputNumFreqSets() {

// If empty tree (i.e. no supported sets) do nothing
if (startTtreeRef== null) System.out.println("Number of frequent " +
"sets = 0");
// Otherwise count and output
else System.out.println("Number of frequent sets = " +
countNumFreqSets());
}

/* COUNT NUMBER OF FRQUENT SETS */
/** Commences process of counting the number of frequent supported
sets contained in the T-tree. */

protected int countNumFreqSets() {
// If empty tree return 0
if (startTtreeRef == null) return(0);

// Otherwise loop through T-tree starting with top level
int num=0;
for (int index=1; index <= numOneItemSets; index++) {
// Check for null valued top level Ttree node.
if (startTtreeRef[index] !=null) {
if (startTtreeRef[index].support >= minSupport)
num = countNumFreqSets(index,
startTtreeRef[index].childRef,num+1);
}
}

// Return
return(num);
}

/** Counts the number of supported nodes in a sub branch of the T-tree.
@param size the length/size of the current array level in the T-tree.
@param linkRef the reference to the current array level in the T-tree.
@param num the number of frequent sets sofar. */

protected int countNumFreqSets(int size, TtreeNode[] linkRef, int num) {

if (linkRef == null) return(num);
for (int index=1; index < size; index++) {
if (linkRef[index] != null) {
if (linkRef[index].support >= minSupport)
num = countNumFreqSets(index,
linkRef[index].childRef,num+1);
}
}

// Return

return(num);
}

/** Commences the process of determining and outputting the storage
requirements (in bytes) for the T-tree. */

public void outputStorage() {

// If empty tree (i.e. no supported sets) do nothing
if (startTtreeRef == null) return;

/* Otherwise calculate storage */
System.out.println("T-tree Storage = " + calculateStorage() +
" (Bytes)");
}


/* CALCULATE STORAGE */
/** Commences process of calculating storage requirements for T-tree. */

protected int calculateStorage() {
// If emtpy tree (i.e. no supported sets) return 0
if (startTtreeRef == null) return(0);

/* Step through top level */
int storage = 4; // For element 0
for (int index=1; index <= numOneItemSets; index++) {
if (startTtreeRef[index] !=null) storage = storage + 12 +
calculateStorage(0,startTtreeRef[index].childRef);
else storage = storage+4;
}
// Return
return(storage);
}

/** Calculate storage requirements for a sub-branch of the T-tree.
@param localStorage the storage as calculated sofar.
@param linkRef the reference to the current sub-branch of the T-tree. */

private int calculateStorage(int localStorage, TtreeNode[] linkRef) {

if (linkRef == null) return(0);

for (int index=1; index < linkRef.length; index++) {
if (linkRef[index] !=null) localStorage = localStorage + 12 +
calculateStorage(0,linkRef[index].childRef);
else localStorage = localStorage + 4;
}

/* Return */

return(localStorage+4); // For element 0
}


}