1 /*
2 * Licensed to the Apache Software Foundation (ASF) under one or more
3 * contributor license agreements. See the NOTICE file distributed with
4 * this work for additional information regarding copyright ownership.
5 * The ASF licenses this file to You under the Apache License, Version 2.0
6 * (the "License"); you may not use this file except in compliance with
7 * the License. You may obtain a copy of the License at
8 *
9 * http://www.apache.org/licenses/LICENSE-2.0
10 *
11 * Unless required by applicable law or agreed to in writing, software
12 * distributed under the License is distributed on an "AS IS" BASIS,
13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 * See the License for the specific language governing permissions and
15 * limitations under the License.
16 */
17 package org.apache.commons.collections4.bloomfilter;
18
19 import java.util.Arrays;
20 import java.util.Objects;
21 import java.util.function.LongPredicate;
22
23 /**
24 * Produces bit map longs for a Bloom filter.
25 * <p>
26 * Each bit map is a little-endian long value representing a block of bits of in a filter.
27 * </p>
28 * <p>
29 * The returned array will have length {@code ceil(m / 64)} where {@code m} is the number of bits in the filter and {@code ceil} is the ceiling function. Bits
30 * 0-63 are in the first long. A value of 1 at a bit position indicates the bit index is enabled.
31 * </p>
32 * <p>
33 * <em>The default implementations of the {@code makePredicate()} and {@code asBitMapArray} methods are slow and should be reimplemented in the implementing
34 * classes where possible.</em>
35 * </p>
36 *
37 * @since 4.5.0-M2
38 */
39 @FunctionalInterface
40 public interface BitMapExtractor {
41
42 /**
43 * Creates a BitMapExtractor from an array of Long.
44 *
45 * @param bitMaps the bit maps to return.
46 * @return a BitMapExtractor.
47 */
48 static BitMapExtractor fromBitMapArray(final long... bitMaps) {
49 return new BitMapExtractor() {
50 @Override
51 public long[] asBitMapArray() {
52 return Arrays.copyOf(bitMaps, bitMaps.length);
53 }
54
55 @Override
56 public boolean processBitMapPairs(final BitMapExtractor other, final LongBiPredicate func) {
57 final CountingLongPredicate p = new CountingLongPredicate(bitMaps, func);
58 return other.processBitMaps(p) && p.processRemaining();
59 }
60
61 @Override
62 public boolean processBitMaps(final LongPredicate predicate) {
63 for (final long word : bitMaps) {
64 if (!predicate.test(word)) {
65 return false;
66 }
67 }
68 return true;
69 }
70 };
71 }
72
73 /**
74 * Creates a BitMapExtractor from an IndexExtractor.
75 *
76 * @param extractor the IndexExtractor that specifies the indexes of the bits to enable.
77 * @param numberOfBits the number of bits in the Bloom filter.
78 * @return A BitMapExtractor that produces the bit maps equivalent of the Indices from the extractor.
79 */
80 static BitMapExtractor fromIndexExtractor(final IndexExtractor extractor, final int numberOfBits) {
81 Objects.requireNonNull(extractor, "extractor");
82
83 final long[] result = BitMaps.newBitMap(numberOfBits);
84 extractor.processIndices(i -> {
85 BitMaps.set(result, i);
86 return true;
87 });
88 return fromBitMapArray(result);
89 }
90
91 /**
92 * Return a copy of the BitMapExtractor data as a bit map array.
93 * <p>
94 * The default implementation of this method is slow. It is recommended
95 * that implementing classes reimplement this method.
96 * </p>
97 * @return An array of bit map data.
98 */
99 default long[] asBitMapArray() {
100 final class Bits {
101 private long[] data = new long[16];
102 private int size;
103
104 boolean add(final long bits) {
105 if (size == data.length) {
106 // This will throw an out-of-memory error if there are too many bits.
107 // Since bits are addressed using 32-bit signed integer indices
108 // the maximum length should be ~2^31 / 2^6 = ~2^25.
109 // Any more is a broken implementation.
110 data = Arrays.copyOf(data, size * 2);
111 }
112 data[size++] = bits;
113 return true;
114 }
115
116 long[] toArray() {
117 // Edge case to avoid a large array copy
118 return size == data.length ? data : Arrays.copyOf(data, size);
119 }
120 }
121 final Bits bits = new Bits();
122 processBitMaps(bits::add);
123 return bits.toArray();
124 }
125
126 /**
127 * Applies the {@code func} to each bit map pair in order. Will apply all of the bit maps from the other BitMapExtractor to this extractor. If this
128 * extractor does not have as many bit maps it will provide 0 (zero) for all excess calls to the LongBiPredicate.
129 * <p>
130 * <em>The default implementation of this method uses {@code asBitMapArray()}. It is recommended that implementations of BitMapExtractor that have local
131 * arrays reimplement this method.</em>
132 * </p>
133 *
134 * @param other The other BitMapExtractor that provides the y values in the (x,y) pair.
135 * @param func The function to apply.
136 * @return A LongPredicate that tests this BitMapExtractor's bitmap values in order.
137 */
138 default boolean processBitMapPairs(final BitMapExtractor other, final LongBiPredicate func) {
139 final CountingLongPredicate p = new CountingLongPredicate(asBitMapArray(), func);
140 return other.processBitMaps(p) && p.processRemaining();
141 }
142
143 /**
144 * Each bit map is passed to the predicate in order. The predicate is applied to each
145 * bit map value, if the predicate returns {@code false} the execution is stopped, {@code false}
146 * is returned, and no further bit maps are processed.
147 *
148 * <p>If the extractor is empty this method will return true.</p>
149 *
150 * <p>Any exceptions thrown by the action are relayed to the caller.</p>
151 *
152 * @param predicate the function to execute
153 * @return {@code true} if all bit maps returned {@code true}, {@code false} otherwise.
154 * @throws NullPointerException if the specified consumer is null
155 */
156 boolean processBitMaps(LongPredicate predicate);
157 }