www.pudn.com > apriori的vc源代码.zip > HashTree.cpp

// HashTree.cpp: implementation of the CHashTree class. 
// 
////////////////////////////////////////////////////////////////////// 
#include "stdafx.h" 
#include "HashTree.h" 
 
////////////////////////////////////////////////////////////////////// 
// Construction/Destruction 
////////////////////////////////////////////////////////////////////// 
 
CHashTree::CHashTree() 
{ 
 
    root = newnode(LEAF); 
    return; 
 
} 
 
CHashTree::~CHashTree() 
{ 
 
    freenode(root); 
    root = (HashNode *)NULL; 
    return; 
 
} 
 
//  Produces a hash code for a item set. 
int CHashTree::hash(itemSet *itemset, int level) 
{ 
 
    return((int)(itemset->get(level) % TABLE_SIZE)); 
 
} 
 
 
/* creates a new cell accordint to the desired type (t) and fill it with null values*/ 
HashNode* CHashTree::newnode(int nodetype) 
{ 
    HashNode *node; 
 
    node = (HashNode*) new HashNode(); 
    node->nodetype = nodetype; 
     
    if (nodetype == INTERNAL) 
    { 
        for (int i = 0; i < TABLE_SIZE; i++) 
            node->vp.tab[i] = (HashNode *)NULL; 
    } 
    else 
    { 
        node->vp.largeset = (List *)new List(); 
    } 
 
    return(node); 
}; 
 
 
 
/* free the sub hash tree with the root node */ 
void CHashTree::freenode(HashNode *node) 
{ 
 
    if (node->nodetype == INTERNAL) 
    { 
        for (int i = 0; i < TABLE_SIZE; i++) 
        { 
            if(node->vp.tab[i] != (HashNode *)NULL) 
                freenode(node->vp.tab[i]); 
        } 
    } 
    else 
        delete node->vp.largeset; 
 
    delete node; 
 
    return; 
} 
 
 
/*inserts a new itemset - s in the hash tree - cp according to the level lev*/ 
void CHashTree :: insert( HashNode **hp, itemSet *s, int level ) 
{ 
    HashNode *c1; 
    HashNode *head = (HashNode *) *hp; 
    List *prev; 
    itemSet *pset; 
    int i; 
 
    s->support(0); 
 
    if (head == (HashNode *)NULL) 
    { 
        head = newnode(LEAF); 
        head->vp.largeset->add(s); 
    } 
    else if(head->nodetype == INTERNAL) 
    { 
        c1 = head->vp.tab[hash(s, level)]; 
        insert(&c1, s, level+1); 
    } 
    else if( (head->vp.largeset->size() < BUCKET_SIZE) || (level >= (s->size() - 1)) ) 
    { 
        head->vp.largeset->add(s); 
    } 
    else 
    { 
        prev = head->vp.largeset; 
 
        for (i = 0; i < TABLE_SIZE; i++) 
            head->vp.tab[i] = (HashNode *)newnode(LEAF); 
 
        head->nodetype = INTERNAL; 
 
        for(i = 0; i < prev->size(); i++) 
        { 
            pset = (itemSet *)prev->get(i); 
            c1 = head->vp.tab[hash(pset, level)]; 
            c1->vp.largeset->add((itemSet *)pset->clone()); 
        } 
 
        delete prev; 
 
        c1 = head->vp.tab[hash(s, level)]; 
        c1->vp.largeset->add(s); 
    } 
     
    return; 
} 
 
 
 
/* increments the counts of each subset of transaction t which are in the hash tree cp (candidate sets)*/ 
void CHashTree :: subset(HashNode *head, itemSet *t, int m) 
{ 
    itemSet *node; 
    itemSet *visited; 
    int i, j; 
 
    if(m >= t->size()) 
        return; 
 
    if(head != (HashNode *)NULL) 
    { 
        if (head->nodetype == INTERNAL )  
        { 
            visited = new itemSet(); 
 
            for (i = m; i < t->size(); i++) 
            { 
                j = t->get(i); 
                j = j%TABLE_SIZE; 
                if(visited->indexOf(j) < 0) 
                { 
                    visited->add(j); 
                    subset(head->vp.tab[j], t, i+1); 
                } 
            } 
 
            delete visited; 
        } 
        else 
        { 
            for(i = 0; i < head->vp.largeset->size(); i++) 
            { 
                node = (itemSet *)head->vp.largeset->get(i); 
         
                if((node->compare(t) == MAKEUP) || (node->compare(t) == TOTALEQUAL)) 
                    node->support(node->support() + 1); 
            } 
        } 
    } 
 
    return; 
} 
 
 
 
 
 
/*  
   traverses the hash tree - cp, collects the itemsets in a list of itemsets - p1 
   and frees the cells of the hash trees********** stands for go and release 
*/ 
 
void  CHashTree :: scan(HashNode *head, List *result, long minsup)  
{ 
    itemSet *node; 
    int i; 
     
    if(head == (HashNode *)NULL) 
        return; 
 
    if(head->nodetype == INTERNAL) 
    { 
        for (i = 0; i < TABLE_SIZE; i++) 
            scan(head->vp.tab[i], result, minsup); 
    } 
    else 
    { 
        for(i = 0; i < head->vp.largeset->size(); i++) 
        { 
            node = (itemSet *)head->vp.largeset->get(i); 
 
            if(node->support() >= minsup) 
                result->add((itemSet *)node->clone()); 
        } 
    } 
     
    return; 
}