/
chashtable.cpp
125 lines (107 loc) · 3.41 KB
/
chashtable.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
#include <algorithm>
#include "eclat.h"
#include "chashtable.h"
cHashItem::cHashItem(vector<int> &iary, int lit, int isup, int ihval) {
iset=iary;
//cout << "sz " << iset.size() << " -- " << iset << endl;
//iset.resize(iary.size()+1);
//if (lit != -1) iset[iset.size()-1] = lit;
if (lit != -1) iset.push_back(lit);
//cout << "sz2 " << iset.size() << " -- " << iset << endl;
sort(iset.begin(), iset.end());
sup=isup;
hval = ihval;
}
bool cHashItem::subset (cHashItem *ia)
{
unsigned int i,j;
if (iset.size() > ia->iset.size()) return false;
for (i=0,j=0; i < iset.size();){
if (iset[i] < ia->iset[j]) return false;
else if (iset[i] > ia->iset[j]) ++j;
else{
++i;
++j;
}
}
return true;
}
int cHashItem::compare (cHashItem *ia, cHashItem *ib) {
if (ia->support() > ib->support()) return 1;
else if (ia->support() < ib->support()) return -1;
else if (ia->itemset().size() > ib->itemset().size() ) return 1;
else if( ia->subset(ib) ) return 0;
else if (ia->itemset().size() < ib->itemset().size() ) return -1;
else return 1;
}
ostream& operator << (ostream& fout, cHashItem& hitem)
{
fout << hitem.itemset() << " - " << hitem.support() << " "
<< hitem.hashval() << endl;
return fout;
}
//try to add new closed set to hash table
bool cHashTable::add(vector<int> &iset, int lit, int isup, int ihval)
{
cHashItem *Hitem= new cHashItem(iset, lit, isup, ihval);
bool res = list_add(Hitem);
if (res){
delete Hitem;
return false;
}
else return true;
}
/*
//return false if Hitem not subsumed by another closed set
bool cHashTable::list_add(cHashItem *Hitem)
{
//if (Hitem->hashval() == 2840690)
// cout << "list add " << chtable.size() << " "
// << chtable.bucket_count() << " -- " << *Hitem << endl;
int hres = chtable.hash_funct()(Hitem->hashval()+Hitem->support());
//cout << "HRES " << Hitem->hashval() << " "<< hres << endl;
cHTable::iterator hi = chtable.find(hres);
if (hi == chtable.end()){
//cout << "NOT FOUND\n";
chtable[hres] = new list<cHashItem *>;
chtable[hres]->push_back(Hitem);
return false;
}
else{
//cout << " FOUND :\n";
list<cHashItem *>::iterator li;
int res;
li = (*hi).second->begin();
for (; li != (*hi).second->end(); ++li){
res = cHashItem::compare(Hitem, *li);
//cout << "LOOK AT " << res << " -- " << *(*li) << endl;
if (res == 0) return true;
else if (res == -1){
(*hi).second->insert(li, Hitem);
return false;
}
}
(*hi).second->push_back(Hitem);
return false;
}
}
*/
//return false if Hitem not subsumed by another closed set
bool cHashTable::list_add(cHashItem *Hitem)
{
//if (Hitem->hashval() == 2840690)
// cout << "list add " << chtable.size() << " "
// << chtable.bucket_count() << " -- " << *Hitem << endl;
int hres = chtable.hash_funct()(Hitem->hashval());
//cout << "HRES " << Hitem->hashval() << " "<< hres << endl;
cHTFind p = chtable.equal_range(hres);
cHTable:: iterator hi = p.first;
int res;
for (; hi!=p.second; ++hi){
res = cHashItem::compare(Hitem, (*hi).second);
//cout << "LOOK AT " << res << " -- " << *(*li) << endl;
if (res == 0) return true;
}
chtable.insert(cHTPair(hres, Hitem));
return false;
}