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 *
26 * Each bit map is a little-endian long value representing a block of bits of in a filter.
27 *
28 * <p>The returned array will have length {@code ceil(m / 64)} where {@code m} is the
29 * number of bits in the filter and {@code ceil} is the ceiling function.
30 * Bits 0-63 are in the first long. A value of 1 at a bit position indicates the bit
31 * index is enabled.
32 * </p><p><em>
33 * The default implementations of the {@code makePredicate()} and {@code asBitMapArray} methods
34 * are slow and should be reimplemented in the implementing classes where possible.</em></p>
35 *
36 * @since 4.5
37 */
38 @FunctionalInterface
39 public interface BitMapProducer {
40
41 /**
42 * Creates a BitMapProducer from an array of Long.
43 * @param bitMaps the bit maps to return.
44 * @return a BitMapProducer.
45 */
46 static BitMapProducer fromBitMapArray(final long... bitMaps) {
47 return new BitMapProducer() {
48 @Override
49 public long[] asBitMapArray() {
50 return Arrays.copyOf(bitMaps, bitMaps.length);
51 }
52
53 @Override
54 public boolean forEachBitMap(final LongPredicate predicate) {
55 for (final long word : bitMaps) {
56 if (!predicate.test(word)) {
57 return false;
58 }
59 }
60 return true;
61 }
62
63 @Override
64 public boolean forEachBitMapPair(final BitMapProducer other, final LongBiPredicate func) {
65 final CountingLongPredicate p = new CountingLongPredicate(bitMaps, func);
66 return other.forEachBitMap(p) && p.forEachRemaining();
67 }
68 };
69 }
70
71 /**
72 * Creates a BitMapProducer from an IndexProducer.
73 * @param producer the IndexProducer that specifies the indexes of the bits to enable.
74 * @param numberOfBits the number of bits in the Bloom filter.
75 * @return A BitMapProducer that produces the bit maps equivalent of the Indices from the producer.
76 */
77 static BitMapProducer fromIndexProducer(final IndexProducer producer, final int numberOfBits) {
78 Objects.requireNonNull(producer, "producer");
79 Objects.requireNonNull(numberOfBits, "numberOfBits");
80
81 final long[] result = new long[BitMap.numberOfBitMaps(numberOfBits)];
82 producer.forEachIndex(i -> {
83 BitMap.set(result, i);
84 return true;
85 });
86 return fromBitMapArray(result);
87 }
88
89 /**
90 * Return a copy of the BitMapProducer data as a bit map array.
91 * <p>
92 * The default implementation of this method is slow. It is recommended
93 * that implementing classes reimplement this method.
94 * </p>
95 * @return An array of bit map data.
96 */
97 default long[] asBitMapArray() {
98 class Bits {
99 private long[] data = new long[16];
100 private int size;
101
102 boolean add(final long bits) {
103 if (size == data.length) {
104 // This will throw an out-of-memory error if there are too many bits.
105 // Since bits are addressed using 32-bit signed integer indices
106 // the maximum length should be ~2^31 / 2^6 = ~2^25.
107 // Any more is a broken implementation.
108 data = Arrays.copyOf(data, size * 2);
109 }
110 data[size++] = bits;
111 return true;
112 }
113
114 long[] toArray() {
115 // Edge case to avoid a large array copy
116 return size == data.length ? data : Arrays.copyOf(data, size);
117 }
118 }
119 final Bits bits = new Bits();
120 forEachBitMap(bits::add);
121 return bits.toArray();
122 }
123
124 /**
125 * Each bit map is passed to the predicate in order. The predicate is applied to each
126 * bit map value, if the predicate returns {@code false} the execution is stopped, {@code false}
127 * is returned, and no further bit maps are processed.
128 *
129 * <p>If the producer is empty this method will return true.</p>
130 *
131 * <p>Any exceptions thrown by the action are relayed to the caller.</p>
132 *
133 * @param predicate the function to execute
134 * @return {@code true} if all bit maps returned {@code true}, {@code false} otherwise.
135 * @throws NullPointerException if the specified consumer is null
136 */
137 boolean forEachBitMap(LongPredicate predicate);
138
139 /**
140 * Applies the {@code func} to each bit map pair in order. Will apply all of the bit maps from the other
141 * BitMapProducer to this producer. If this producer does not have as many bit maps it will provide 0 (zero)
142 * for all excess calls to the LongBiPredicate.
143 * <p>
144 * <em>The default implementation of this method uses {@code asBitMapArray()}. It is recommended that implementations
145 * of BitMapProducer that have local arrays reimplement this method.</em></p>
146 *
147 * @param other The other BitMapProducer that provides the y values in the (x,y) pair.
148 * @param func The function to apply.
149 * @return A LongPredicate that tests this BitMapProducers bitmap values in order.
150 */
151 default boolean forEachBitMapPair(final BitMapProducer other, final LongBiPredicate func) {
152 final CountingLongPredicate p = new CountingLongPredicate(asBitMapArray(), func);
153 return other.forEachBitMap(p) && p.forEachRemaining();
154 }
155 }