hashtree.cpp

关联规则发现vc源代码

// 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;
}