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 * <p> 026 * Each bit map is a little-endian long value representing a block of bits of in a filter. 027 * </p> 028 * <p> 029 * 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 030 * 0-63 are in the first long. A value of 1 at a bit position indicates the bit index is enabled. 031 * </p> 032 * <p> 033 * <em>The default implementations of the {@code makePredicate()} and {@code asBitMapArray} methods are slow and should be reimplemented in the implementing 034 * classes where possible.</em> 035 * </p> 036 * 037 * @since 4.5.0-M2 038 */ 039@FunctionalInterface 040public interface BitMapExtractor { 041 042 /** 043 * Creates a BitMapExtractor from an array of Long. 044 * 045 * @param bitMaps the bit maps to return. 046 * @return a BitMapExtractor. 047 */ 048 static BitMapExtractor fromBitMapArray(final long... bitMaps) { 049 return new BitMapExtractor() { 050 @Override 051 public long[] asBitMapArray() { 052 return Arrays.copyOf(bitMaps, bitMaps.length); 053 } 054 055 @Override 056 public boolean processBitMapPairs(final BitMapExtractor other, final LongBiPredicate func) { 057 final CountingLongPredicate p = new CountingLongPredicate(bitMaps, func); 058 return other.processBitMaps(p) && p.processRemaining(); 059 } 060 061 @Override 062 public boolean processBitMaps(final LongPredicate predicate) { 063 for (final long word : bitMaps) { 064 if (!predicate.test(word)) { 065 return false; 066 } 067 } 068 return true; 069 } 070 }; 071 } 072 073 /** 074 * Creates a BitMapExtractor from an IndexExtractor. 075 * 076 * @param extractor the IndexExtractor that specifies the indexes of the bits to enable. 077 * @param numberOfBits the number of bits in the Bloom filter. 078 * @return A BitMapExtractor that produces the bit maps equivalent of the Indices from the extractor. 079 */ 080 static BitMapExtractor fromIndexExtractor(final IndexExtractor extractor, final int numberOfBits) { 081 Objects.requireNonNull(extractor, "extractor"); 082 083 final long[] result = BitMaps.newBitMap(numberOfBits); 084 extractor.processIndices(i -> { 085 BitMaps.set(result, i); 086 return true; 087 }); 088 return fromBitMapArray(result); 089 } 090 091 /** 092 * Return a copy of the BitMapExtractor data as a bit map array. 093 * <p> 094 * The default implementation of this method is slow. It is recommended 095 * that implementing classes reimplement this method. 096 * </p> 097 * @return An array of bit map data. 098 */ 099 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}