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 BitMapExtractor { 040 041 /** 042 * Creates a BitMapExtractor from an array of Long. 043 * @param bitMaps the bit maps to return. 044 * @return a BitMapExtractor. 045 */ 046 static BitMapExtractor fromBitMapArray(final long... bitMaps) { 047 return new BitMapExtractor() { 048 @Override 049 public long[] asBitMapArray() { 050 return Arrays.copyOf(bitMaps, bitMaps.length); 051 } 052 053 @Override 054 public boolean processBitMaps(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 processBitMapPairs(final BitMapExtractor other, final LongBiPredicate func) { 065 final CountingLongPredicate p = new CountingLongPredicate(bitMaps, func); 066 return other.processBitMaps(p) && p.processRemaining(); 067 } 068 }; 069 } 070 071 /** 072 * Creates a BitMapExtractor from an IndexExtractor. 073 * @param extractor the IndexExtractor that specifies the indexes of the bits to enable. 074 * @param numberOfBits the number of bits in the Bloom filter. 075 * @return A BitMapExtractor that produces the bit maps equivalent of the Indices from the extractor. 076 */ 077 static BitMapExtractor fromIndexExtractor(final IndexExtractor extractor, final int numberOfBits) { 078 Objects.requireNonNull(extractor, "extractor"); 079 080 final long[] result = new long[BitMaps.numberOfBitMaps(numberOfBits)]; 081 extractor.processIndices(i -> { 082 BitMaps.set(result, i); 083 return true; 084 }); 085 return fromBitMapArray(result); 086 } 087 088 /** 089 * Return a copy of the BitMapExtractor data as a bit map array. 090 * <p> 091 * The default implementation of this method is slow. It is recommended 092 * that implementing classes reimplement this method. 093 * </p> 094 * @return An array of bit map data. 095 */ 096 default long[] asBitMapArray() { 097 final class Bits { 098 private long[] data = new long[16]; 099 private int size; 100 101 boolean add(final long bits) { 102 if (size == data.length) { 103 // This will throw an out-of-memory error if there are too many bits. 104 // Since bits are addressed using 32-bit signed integer indices 105 // the maximum length should be ~2^31 / 2^6 = ~2^25. 106 // Any more is a broken implementation. 107 data = Arrays.copyOf(data, size * 2); 108 } 109 data[size++] = bits; 110 return true; 111 } 112 113 long[] toArray() { 114 // Edge case to avoid a large array copy 115 return size == data.length ? data : Arrays.copyOf(data, size); 116 } 117 } 118 final Bits bits = new Bits(); 119 processBitMaps(bits::add); 120 return bits.toArray(); 121 } 122 123 /** 124 * Each bit map is passed to the predicate in order. The predicate is applied to each 125 * bit map value, if the predicate returns {@code false} the execution is stopped, {@code false} 126 * is returned, and no further bit maps are processed. 127 * 128 * <p>If the extractor is empty this method will return true.</p> 129 * 130 * <p>Any exceptions thrown by the action are relayed to the caller.</p> 131 * 132 * @param predicate the function to execute 133 * @return {@code true} if all bit maps returned {@code true}, {@code false} otherwise. 134 * @throws NullPointerException if the specified consumer is null 135 */ 136 boolean processBitMaps(LongPredicate predicate); 137 138 /** 139 * Applies the {@code func} to each bit map pair in order. Will apply all of the bit maps from the other 140 * BitMapExtractor to this extractor. If this extractor does not have as many bit maps it will provide 0 (zero) 141 * for all excess calls to the LongBiPredicate. 142 * <p> 143 * <em>The default implementation of this method uses {@code asBitMapArray()}. It is recommended that implementations 144 * of BitMapExtractor that have local arrays reimplement this method.</em></p> 145 * 146 * @param other The other BitMapExtractor that provides the y values in the (x,y) pair. 147 * @param func The function to apply. 148 * @return A LongPredicate that tests this BitMapExtractor's bitmap values in order. 149 */ 150 default boolean processBitMapPairs(final BitMapExtractor other, final LongBiPredicate func) { 151 final CountingLongPredicate p = new CountingLongPredicate(asBitMapArray(), func); 152 return other.processBitMaps(p) && p.processRemaining(); 153 } 154}