fptree.java

java platform java-growth algorithm

    /* ORDER LOCAL HEADER TABLE */
    
    /** Orders local header table (currently unused).  
    @param localHeaderTable the FPgrpwth header table to be ordered.
    @param countArray the csupport for the 1 item sets. */
    
    private void orderLocalHeaderTable(FPgrowthHeaderTable[] localHeaderTable,
    				FPgrowthColumnCounts[] countArray) {    	
	boolean isOrdered; 
	FPgrowthHeaderTable temp;
	int index, place1, place2;
	
	//loop through table
        do {
            index = 1;
	    isOrdered=true;
	    while (index < (localHeaderTable.length-1)) {
	        place1 = localHeaderTable[index].itemName;
                place2 = localHeaderTable[index+1].itemName; 
                if (countArray[place1].support > countArray[place2].support) {
	            isOrdered=false;
		    // Swap
                    temp = localHeaderTable[index];
	            localHeaderTable[index] = localHeaderTable[index+1];
                    localHeaderTable[index+1] = temp;
	            }
		// increment index
		index++;
		} 
	    } while (isOrdered==false);
	}
    
    /* ---------------------------------------------------------------------- */
    /*                                                                        */
    /*                         GENERATE NEW FP-TREE                           */
    /*                                                                        */
    /* ---------------------------------------------------------------------- */  
    	
    /* GENERATE LOCAL FP-tree */
    
    /** Generates a local FP tree 
    @param tableRef reference to start of header table containing links to
    an FP-tree produced during the FP-tree generation process.
    @rerurn reference to the start of the generated FP-tree*/
    
    private FPtreeNode generateLocalFPtree(FPgrowthHeaderTable[] tableRef) {
         FPgrowthSupportedSets ref = startTempSets;
	 FPtreeNode localRoot = new FPtreeNode(); 
	 
	 // Loop

        while(ref != null) { 	 
	    // Add to conditional FP tree   
	    if (ref.itemSet != null) addToFPtree(localRoot,0,ref.itemSet,
	    			ref.support,tableRef);  
       	    ref = ref.nodeLink;
	    }
	
	// Return

	return(localRoot);
	} 
	
    /* ---------------------------------------------------------- */
    /*                                                            */
    /*                     FP-TREE UTILITIES                      */
    /*                                                            */
    /* ---------------------------------------------------------- */
    	
    /* REALLOC 1 FP-TREE */
    
    /** Resizes the given array of FP-tree nodes so that its length is 
    increased by one element and new element inserted.
    @param oldArray the given array of FP-tree nodes.
    @param newNode the given node to be added to the FP-tree
    @return The revised array of FP-tree nodes. */
    
    private FPtreeNode[] reallocFPtreeChildRefs(FPtreeNode[] oldArray, 
    			FPtreeNode newNode) {
            
	// No old array
	
	if (oldArray == null) {
	    FPtreeNode[] newArray = {newNode};
	    tempIndex = 0;
	    return(newArray);
	    }
	
	// Otherwise create new array with length one greater than old array
	
	int oldArrayLength = oldArray.length;
	FPtreeNode[] newArray = new FPtreeNode[oldArrayLength+1];
	
	// Insert new node in correct lexicographic order.
		
	for (int index1=0;index1 < oldArrayLength;index1++) {
	    if (newNode.node.itemName < oldArray[index1].node.itemName) {
		newArray[index1] = newNode;
		for (int index2=index1;index2<oldArrayLength;index2++)
		    newArray[index2+1] = oldArray[index2];
		tempIndex = index1;
		return(newArray);
		}
	    newArray[index1] = oldArray[index1];
	    }
	
	// Default
	
	newArray[oldArrayLength] = newNode;
	tempIndex = oldArrayLength;
	return(newArray);
	}
		
    /*------------------------------------------------------------------ */
    /*                                                                   */
    /*                           OUTPUT METHODS                          */
    /*                                                                   */
    /*------------------------------------------------------------------ */

    /* OUTPUT HEADER TABLE */
    
    /** Commences process of outputting the prefix sub tree to the screen, 
    starting at header table. */
    
    public void outputItemPrefixSubtree() {
        int flag;
        System.out.println("PREFIX SUBTREE FROM HEADER TABLE");
        for(int index=1;index<headerTable.length;index++) {
	    System.out.println("Header = " + 
	                       reconvertItem(headerTable[index].itemName));
	    flag = outputItemPrefixTree(headerTable[index].nodeLink);
	    if (flag!=1) System.out.println();
	    }
	System.out.println();
	}
    
    /** Commences process of outputting a local prefix sub tree to the screen. 
    @param tableRef the reference to the local header table. */
                
    private void outputItemPrefixSubtree(FPgrowthHeaderTable[] tableRef) {
        int flag;
        System.out.println("PREFIX SUBTREE FROM LOCAL HEADER TABLE");
        for(int index=1;index<tableRef.length;index++) {
	    System.out.println("Header = " + 
	                           reconvertItem(tableRef[index].itemName));
	    flag = outputItemPrefixTree(tableRef[index].nodeLink);
	    if (flag!=1) System.out.println();
	    }
	System.out.println();
	}

    /** Outputs the given prefix sub tree. 
    @param ref the reference to the given branch. 
    @return a counter representing the current "node number" (used in 
    output). */	
    
    private int outputItemPrefixTree(FPgrowthItemPrefixSubtreeNode ref) {
        int counter = 1;
	
	// Loop
	
	while (ref != null) {
            System.out.print("(" + counter + ") " + 
	            (reconvertItem(ref.itemName)) + ":" + ref.itemCount + " ");
	    counter++;
	    ref = ref.nodeLink;
	    }
	
	return(counter);
	}
		
    /* OUTPUT FP TREE */
    
    /** Commences process of outputting FP-tree to screen. */
    
    public void outputFPtree() {
        System.out.println("FP TREE");
	outputFPtreeNode1();
        System.out.println();
	}
    
    /** Commences process of outputting a given branch of an FP-tree to the
    screen. 
    @param ref the reference to the given FP-tree branch. */
    
    private void outputFPtreeNode(FPtreeNode ref) {
        System.out.println("LOCAL FP TREE");
	outputFPtreeNode2(ref.childRefs,"");
        System.out.println();
	}

    /** Continues process of outputting FP-tree to screen. */
    	
    private void outputFPtreeNode1() {
	outputFPtreeNode2(rootNode.childRefs,"");
        }

    /** Outputs a given level in an FP-tree to the screen.
    @param ref the reference to the given FP-tree level.
    @param nodeID the root string for the node ID. */
    	
    private void outputFPtreeNode2(FPtreeNode ref[],String nodeID) {
        if (ref == null) return;
	
	// Otherwise process
	
        for (int index=0;index<ref.length;index++) {
	    System.out.print("(" + nodeID + (index+1) + ") ");
	    outputItemPrefixSubtreeNode(ref[index].node);
	    outputFPtreeNode2(ref[index].childRefs,nodeID+(index+1)+".");
	    }
	}
		
    /* OUTPUT ITEM PREFIX SUB-TREE NODE	*/
    
    /** Outputs the given prefix sub tree node. 
    @param ref the reference to the given node. */
    
    public void outputItemPrefixSubtreeNode(FPgrowthItemPrefixSubtreeNode ref) {
        System.out.print((reconvertItem(ref.itemName)) + ":" + ref.itemCount);
	if (ref.nodeLink != null) {
	    System.out.println(" (ref to " + 
	                         (reconvertItem(ref.nodeLink.itemName)) + ":" +
	    	                                 ref.nodeLink.itemCount + ")");
	    }	
	else System.out.println(" (ref to null)");
	}
   
    /* OUTPUT ANCESTER TRAIL */
    
    /** Commence the process of outputting the ancestor trail from the header 
    table */
    
    private void outputAncesterTrail() {
        int flag;
        System.out.println("ANCESTOR TRAIL FROM HEADER TABLE");
        for(int index=1;index<headerTable.length;index++) {
	    System.out.println("Header = " + 
	                         (reconvertItem(headerTable[index].itemName)));
	    outputAncestorTrail1(headerTable[index].nodeLink);
	    }
	System.out.println();
	}
    
    /** Commence the process of outputting the ancestor trail from a local
    header table.
    @param tableRef the reference to the local header table. */
    
    private void outputAncesterTrail(FPgrowthHeaderTable[] tableRef) {
        int flag;
        System.out.println("ANCESTOR TRAIL FROM LOCAL HEADER TABLE");
        for(int index=1;index<tableRef.length;index++) {
	    System.out.println("Header = " + 
	                            (reconvertItem(tableRef[index].itemName)));
	    outputAncestorTrail1(tableRef[index].nodeLink);
	    }
	System.out.println();
	}

    /** Outputs the ancestor trail given a prefix sub tree. 
    @param ref the reference to the given branch. */	
    
    private void outputAncestorTrail1(FPgrowthItemPrefixSubtreeNode ref) {
	while (ref != null) {
	    System.out.print("\t");
            outputAncestorTrail2(ref);
	    ref = ref.nodeLink;
	    System.out.println();
	    }
	}

    /** Outputs the given ancestor trail node in prefix sub tree. 
    @param ref the reference to the given node. */	
   
    private void outputAncestorTrail2(FPgrowthItemPrefixSubtreeNode ref) {
	while (ref != null) {
	    System.out.print("(" + (reconvertItem(ref.itemName)) + ":" + 
	                                                ref.itemCount + ") ");
	    ref = ref.parentRef;
	    }
	}
    
    /* OUTPUT FP TREE STORAGE: */
    
    /** Commence process of determining and outputting FP-tree storage, number 
    of updates and number of nodes. */
      
    public void outputFPtreeStorage() {
        int storage=8;	// 8 Bytes for root node
	numberOfNodes = 1;   // For root node
	storage = calculateStorage(rootNode.childRefs,storage); 
	
	// Add header table.
	
	storage = storage + (headerTable.length*6);
	System.out.println("FP tree storage = " + storage + " (bytes)");
	System.out.println("FP tree updates = " + numUpdates);
	System.out.println("FP tree nodes   = " + numberOfNodes);
	}

    /* CALCULATE STORAGE */
    
    /** Determines storage requirements for FP-tree.
    @param ref the reference to the current portion of the P-tree under
    consideration.
    @param storage the storage requirements so far. 
    @return the storage in Bytes required for the given FP=tree node.*/
     
    private int calculateStorage(FPtreeNode[] ref, int storage) {
	if (ref == null) return(storage);

	// Process, each node has 14+8 bytes of storage, 8 for FP tree
	// links (child and sibling), 14 for prefix tree links (parentRef, 
	// nodeRef, Support, ID
	
        for (int index=0;index<ref.length;index++) {
	    storage = storage + 14 + 8;
	    numberOfNodes++;
	    storage = calculateStorage(ref[index].childRefs,storage);
	    }
	
	// Return
	
	return(storage);
	}
		
    /* OUTPUT LOCAL ARRAY COUNT */
   
    /** Output local array count structure (diagnostic use only). 
    @param countArray the array of <TT>FPgrowthColumnCounts</TT> structures 
    describing the single item sets (in terms of labels and associated 
    support), contained in a linked list of <TT>FPgrowthSupportedSets</TT>
    which in turn describe the ancestor nodes in an FP-tree that preceed the 
    nodes identified by following a trail of links from a particular item in 
    the header table.  */
    
    private void outputColumnCount(FPgrowthColumnCounts[] countArray) {
    	
	for(int index=1;index<countArray.length;index++) {
	    System.out.print("Col " + countArray[index].columnNum + " : ");
	    if (countArray[index].support == 0) 
	    				System.out.println("Unsupported");
	    else System.out.println(countArray[index].support);
	    }
	System.out.println();
	}
    }