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 }