1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 package org.apache.commons.collections4.bloomfilter;
18
19 import java.util.Arrays;
20 import java.util.Objects;
21 import java.util.function.IntPredicate;
22 import java.util.function.LongPredicate;
23
24
25
26
27
28
29 public final class SimpleBloomFilter implements BloomFilter {
30
31
32
33
34 private final long[] bitMap;
35
36
37
38
39 private final Shape shape;
40
41
42
43
44 private int cardinality;
45
46
47
48
49
50
51 public SimpleBloomFilter(final Shape shape) {
52 Objects.requireNonNull(shape, "shape");
53 this.shape = shape;
54 this.bitMap = new long[BitMap.numberOfBitMaps(shape.getNumberOfBits())];
55 this.cardinality = 0;
56 }
57
58
59
60
61
62 private SimpleBloomFilter(final SimpleBloomFilter source) {
63 this.shape = source.shape;
64 this.bitMap = source.bitMap.clone();
65 this.cardinality = source.cardinality;
66 }
67
68 @Override
69 public long[] asBitMapArray() {
70 return Arrays.copyOf(bitMap, bitMap.length);
71 }
72
73 @Override
74 public int cardinality() {
75
76 int c = cardinality;
77 if (c < 0) {
78 cardinality = c = SetOperations.cardinality(this);
79 }
80 return c;
81 }
82
83 @Override
84 public int characteristics() {
85 return 0;
86 }
87
88 @Override
89 public void clear() {
90 Arrays.fill(bitMap, 0L);
91 cardinality = 0;
92 }
93
94 @Override
95 public boolean contains(final IndexProducer indexProducer) {
96 return indexProducer.forEachIndex(idx -> BitMap.contains(bitMap, idx));
97 }
98
99 @Override
100 public SimpleBloomFilter copy() {
101 return new SimpleBloomFilter(this);
102 }
103
104 @Override
105 public boolean forEachBitMap(final LongPredicate consumer) {
106 Objects.requireNonNull(consumer, "consumer");
107 for (final long l : bitMap) {
108 if (!consumer.test(l)) {
109 return false;
110 }
111 }
112 return true;
113 }
114
115 @Override
116 public boolean forEachBitMapPair(final BitMapProducer other, final LongBiPredicate func) {
117 final CountingLongPredicate p = new CountingLongPredicate(bitMap, func);
118 return other.forEachBitMap(p) && p.forEachRemaining();
119 }
120
121 @Override
122 public boolean forEachIndex(final IntPredicate consumer) {
123 Objects.requireNonNull(consumer, "consumer");
124 return IndexProducer.fromBitMapProducer(this).forEachIndex(consumer);
125 }
126
127 @Override
128 public Shape getShape() {
129 return shape;
130 }
131
132 @Override
133 public boolean isEmpty() {
134 return cardinality == 0 || forEachBitMap(y -> y == 0);
135 }
136
137 @Override
138 public boolean merge(final BitMapProducer bitMapProducer) {
139 Objects.requireNonNull(bitMapProducer, "bitMapProducer");
140 try {
141 final int[] idx = new int[1];
142 bitMapProducer.forEachBitMap(value -> {
143 bitMap[idx[0]++] |= value;
144 return true;
145 });
146
147 idx[0]--;
148 final int idxLimit = BitMap.getLongIndex(shape.getNumberOfBits());
149 if (idxLimit == idx[0]) {
150 final long excess = bitMap[idxLimit] >> shape.getNumberOfBits();
151 if (excess != 0) {
152 throw new IllegalArgumentException(
153 String.format("BitMapProducer set a bit higher than the limit for the shape: %s",
154 shape.getNumberOfBits()));
155 }
156 }
157 cardinality = -1;
158 } catch (final IndexOutOfBoundsException e) {
159 throw new IllegalArgumentException(
160 String.format("BitMapProducer should send at most %s maps", bitMap.length), e);
161 }
162 return true;
163 }
164
165 @Override
166 public boolean merge(final BloomFilter other) {
167 Objects.requireNonNull(other, "other");
168 if ((other.characteristics() & SPARSE) != 0) {
169 merge((IndexProducer) other);
170 } else {
171 merge((BitMapProducer) other);
172 }
173 return true;
174 }
175
176 @Override
177 public boolean merge(final Hasher hasher) {
178 Objects.requireNonNull(hasher, "hasher");
179 return merge(hasher.indices(shape));
180 }
181
182 @Override
183 public boolean merge(final IndexProducer indexProducer) {
184 Objects.requireNonNull(indexProducer, "indexProducer");
185 indexProducer.forEachIndex(idx -> {
186 if (idx < 0 || idx >= shape.getNumberOfBits()) {
187 throw new IllegalArgumentException(String.format(
188 "IndexProducer should only send values in the range[0,%s)", shape.getNumberOfBits()));
189 }
190 BitMap.set(bitMap, idx);
191 return true;
192 });
193 cardinality = -1;
194 return true;
195 }
196 }