001/* 002 * Licensed to the Apache Software Foundation (ASF) under one or more 003 * contributor license agreements. See the NOTICE file distributed with 004 * this work for additional information regarding copyright ownership. 005 * The ASF licenses this file to You under the Apache License, Version 2.0 006 * (the "License"); you may not use this file except in compliance with 007 * the License. You may obtain a copy of the License at 008 * 009 * http://www.apache.org/licenses/LICENSE-2.0 010 * 011 * Unless required by applicable law or agreed to in writing, software 012 * distributed under the License is distributed on an "AS IS" BASIS, 013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 014 * See the License for the specific language governing permissions and 015 * limitations under the License. 016 */ 017package org.apache.commons.collections4.bloomfilter; 018 019import java.util.Arrays; 020import java.util.Objects; 021import java.util.function.LongPredicate; 022 023/** 024 * Produces bit map longs for a Bloom filter. 025 * 026 * Each bit map is a little-endian long value representing a block of bits of in a filter. 027 * 028 * <p>The returned array will have length {@code ceil(m / 64)} where {@code m} is the 029 * number of bits in the filter and {@code ceil} is the ceiling function. 030 * Bits 0-63 are in the first long. A value of 1 at a bit position indicates the bit 031 * index is enabled. 032 * </p><p><em> 033 * The default implementations of the {@code makePredicate()} and {@code asBitMapArray} methods 034 * are slow and should be reimplemented in the implementing classes where possible.</em></p> 035 * 036 * @since 4.5 037 */ 038@FunctionalInterface 039public interface BitMapProducer { 040 041 /** 042 * Creates a BitMapProducer from an array of Long. 043 * @param bitMaps the bit maps to return. 044 * @return a BitMapProducer. 045 */ 046 static BitMapProducer fromBitMapArray(final long... bitMaps) { 047 return new BitMapProducer() { 048 @Override 049 public long[] asBitMapArray() { 050 return Arrays.copyOf(bitMaps, bitMaps.length); 051 } 052 053 @Override 054 public boolean forEachBitMap(final LongPredicate predicate) { 055 for (final long word : bitMaps) { 056 if (!predicate.test(word)) { 057 return false; 058 } 059 } 060 return true; 061 } 062 063 @Override 064 public boolean forEachBitMapPair(final BitMapProducer other, final LongBiPredicate func) { 065 final CountingLongPredicate p = new CountingLongPredicate(bitMaps, func); 066 return other.forEachBitMap(p) && p.forEachRemaining(); 067 } 068 }; 069 } 070 071 /** 072 * Creates a BitMapProducer from an IndexProducer. 073 * @param producer the IndexProducer that specifies the indexes of the bits to enable. 074 * @param numberOfBits the number of bits in the Bloom filter. 075 * @return A BitMapProducer that produces the bit maps equivalent of the Indices from the producer. 076 */ 077 static BitMapProducer fromIndexProducer(final IndexProducer producer, final int numberOfBits) { 078 Objects.requireNonNull(producer, "producer"); 079 Objects.requireNonNull(numberOfBits, "numberOfBits"); 080 081 final long[] result = new long[BitMap.numberOfBitMaps(numberOfBits)]; 082 producer.forEachIndex(i -> { 083 BitMap.set(result, i); 084 return true; 085 }); 086 return fromBitMapArray(result); 087 } 088 089 /** 090 * Return a copy of the BitMapProducer data as a bit map array. 091 * <p> 092 * The default implementation of this method is slow. It is recommended 093 * that implementing classes reimplement this method. 094 * </p> 095 * @return An array of bit map data. 096 */ 097 default long[] asBitMapArray() { 098 class Bits { 099 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}