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.BitSet; 021import java.util.Objects; 022import java.util.function.IntPredicate; 023import java.util.function.LongPredicate; 024 025/** 026 * An object that produces indices of a Bloom filter. 027 * <p><em> 028 * The default implementation of {@code asIndexArray} is slow. Implementers should reimplement the 029 * method where possible.</em></p> 030 * 031 * @since 4.5 032 */ 033@FunctionalInterface 034public interface IndexProducer { 035 036 /** 037 * Creates an IndexProducer from a {@code BitMapProducer}. 038 * @param producer the {@code BitMapProducer} 039 * @return a new {@code IndexProducer}. 040 */ 041 static IndexProducer fromBitMapProducer(final BitMapProducer producer) { 042 Objects.requireNonNull(producer, "producer"); 043 return consumer -> { 044 final LongPredicate longPredicate = new LongPredicate() { 045 int wordIdx; 046 047 @Override 048 public boolean test(long word) { 049 int i = wordIdx; 050 while (word != 0) { 051 if ((word & 1) == 1 && !consumer.test(i)) { 052 return false; 053 } 054 word >>>= 1; 055 i++; 056 } 057 wordIdx += 64; 058 return true; 059 } 060 }; 061 return producer.forEachBitMap(longPredicate::test); 062 }; 063 } 064 065 /** 066 * Creates an IndexProducer from an array of integers. 067 * @param values the index values 068 * @return an IndexProducer that uses the values. 069 */ 070 static IndexProducer fromIndexArray(final int... values) { 071 return new IndexProducer() { 072 073 @Override 074 public int[] asIndexArray() { 075 return values.clone(); 076 } 077 078 @Override 079 public boolean forEachIndex(final IntPredicate predicate) { 080 for (final int value : values) { 081 if (!predicate.test(value)) { 082 return false; 083 } 084 } 085 return true; 086 } 087 }; 088 } 089 090 /** 091 * Return a copy of the IndexProducer data as an int array. 092 * 093 * <p>Indices ordering and uniqueness is not guaranteed.</p> 094 * 095 * <p><em> 096 * The default implementation of this method creates an array and populates 097 * it. Implementations that have access to an index array should consider 098 * returning a copy of that array if possible. 099 * </em></p> 100 * 101 * @return An int array of the data. 102 */ 103 default int[] asIndexArray() { 104 class Indices { 105 private int[] data = new int[32]; 106 private int size; 107 108 boolean add(final int index) { 109 data = IndexUtils.ensureCapacityForAdd(data, size); 110 data[size++] = index; 111 return true; 112 } 113 114 int[] toArray() { 115 // Edge case to avoid a large array copy 116 return size == data.length ? data : Arrays.copyOf(data, size); 117 } 118 } 119 final Indices indices = new Indices(); 120 forEachIndex(indices::add); 121 return indices.toArray(); 122 } 123 124 /** 125 * Each index is passed to the predicate. The predicate is applied to each 126 * index value, if the predicate returns {@code false} the execution is stopped, {@code false} 127 * is returned, and no further indices are processed. 128 * 129 * <p>Any exceptions thrown by the action are relayed to the caller.</p> 130 * 131 * <p>Indices ordering and uniqueness is not guaranteed.</p> 132 * 133 * @param predicate the action to be performed for each non-zero bit index. 134 * @return {@code true} if all indexes return true from consumer, {@code false} otherwise. 135 * @throws NullPointerException if the specified action is null 136 */ 137 boolean forEachIndex(IntPredicate predicate); 138 139 /** 140 * Creates an IndexProducer comprising the unique indices for this producer. 141 * 142 * <p>By default creates a new producer with some overhead to remove 143 * duplicates. IndexProducers that return unique indices by default 144 * should override this to return {@code this}.</p> 145 * 146 * <p>The default implementation will filter the indices from this instance 147 * and return them in ascending order.</p> 148 * 149 * @return the IndexProducer of unique values. 150 * @throws IndexOutOfBoundsException if any index is less than zero. 151 */ 152 default IndexProducer uniqueIndices() { 153 final BitSet bitSet = new BitSet(); 154 forEachIndex(i -> { 155 bitSet.set(i); 156 return true; 157 }); 158 159 return new IndexProducer() { 160 @Override 161 public boolean forEachIndex(final IntPredicate predicate) { 162 for (int idx = bitSet.nextSetBit(0); idx >= 0; idx = bitSet.nextSetBit(idx + 1)) { 163 if (!predicate.test(idx)) { 164 return false; 165 } 166 } 167 return true; 168 } 169 170 @Override 171 public IndexProducer uniqueIndices() { 172 return this; 173 } 174 }; 175 } 176}