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
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
|
package bloom;
/**
* @author Brian Bushnell
* @date Aug 17, 2012
*
*/
public class KCountArray3 extends KCountArray {
/**
*
*/
private static final long serialVersionUID = -5466091642729698944L;
public KCountArray3(long cells_, int bits_){
super(cells_, bits_);
long words=cells/cellsPerWord;
int wordsPerArray=(int)(words/numArrays);
matrix=new int[numArrays][wordsPerArray];
}
@Override
public int read(long key){
if(verbose){System.err.println("Reading "+key);}
// System.out.println("key="+key);
int arrayNum=(int)(key&arrayMask);
// System.out.println("array="+arrayNum);
key>>>=arrayBits;
// System.out.println("key2="+key);
int[] array=matrix[arrayNum];
int index=(int)(key>>>indexShift);
// System.out.println("index="+index);
int word=array[index];
// System.out.println("word="+Integer.toHexString(word));
int cellShift=(int)(cellBits*key);
// System.out.println("cellShift="+cellShift);
int value=(int)((word>>>cellShift)&valueMask);
if(verbose){System.err.println("Read "+value);}
return value;
}
@Override
public void write(long key, int value){
if(verbose){System.err.println("Writing "+key+", "+value);}
int arrayNum=(int)(key&arrayMask);
key>>>=arrayBits;
int[] array=matrix[arrayNum];
int index=(int)(key>>>indexShift);
int word=array[index];
int cellShift=(int)(cellBits*key);
word=(value<<cellShift)|(word&~((valueMask)<<cellShift));
array[index]=word;
}
// static int count138=0;
@Override
public void increment(long key, int incr){
if(verbose){System.err.println("*** Incrementing "+key);}
// if(key==138){
// assert(count138==0) : count138;
// count138++;
// }
int arrayNum=(int)(key&arrayMask);
key>>>=arrayBits;
int[] array=matrix[arrayNum];
int index=(int)(key>>>indexShift);
int word=array[index];
int cellShift=(int)(cellBits*key);
int value=((word>>>cellShift)&valueMask);
if(value==0 && incr>0){cellsUsed++;}
else if(incr<0 && value+incr==0){cellsUsed--;}
value=min(value+incr, maxValue);
word=(value<<cellShift)|(word&~((valueMask)<<cellShift));
array[index]=word;
if(verbose){System.err.println("Returning "+value);}
//return (int)value;
}
/** Returns unincremented value */
@Override
public int incrementAndReturnUnincremented(long key, int incr){
if(verbose){System.err.println("Incrementing2 "+key);}
int arrayNum=(int)(key&arrayMask);
key>>>=arrayBits;
int[] array=matrix[arrayNum];
int index=(int)(key>>>indexShift);
int word=array[index];
int cellShift=(int)(cellBits*key);
final int value=((word>>>cellShift)&valueMask);
final int value2=min(value+incr, maxValue);
word=(value2<<cellShift)|(word&~((valueMask)<<cellShift));
array[index]=word;
if(verbose){System.err.println("Returning "+value);}
return value;
}
@Override
public long[] transformToFrequency(){
return transformToFrequency(matrix);
}
@Override
public String toContentsString(){
StringBuilder sb=new StringBuilder();
sb.append("[");
String comma="";
for(int[] array : matrix){
for(int i=0; i<array.length; i++){
int word=array[i];
for(int j=0; j<cellsPerWord; j++){
int x=word&valueMask;
sb.append(comma);
sb.append(x);
word>>>=cellBits;
comma=", ";
}
}
}
sb.append("]");
return sb.toString();
}
@Override
public double usedFraction(){return cellsUsed/(double)cells;}
@Override
public double usedFraction(int mindepth){return cellsUsed(mindepth)/(double)cells;}
@Override
public long cellsUsed(int mindepth){
long count=0;
for(int[] array : matrix){
if(array!=null){
for(int word : array){
while(word>0){
int x=word&valueMask;
if(x>=mindepth){count++;}
word>>>=cellBits;
}
}
}
}
return count;
}
@Override
long hash(long x, int y) {
assert(false) : "Unsupported.";
return x;
}
private long cellsUsed;
private final int[][] matrix;
}
|
