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.BitSet;
21 import java.util.Objects;
22 import java.util.function.IntPredicate;
23 import java.util.function.LongPredicate;
24
25 /**
26 * An object that produces indices of a Bloom filter.
27 * <p><em>
28 * The default implementation of {@code asIndexArray} is slow. Implementers should reimplement the
29 * method where possible.</em></p>
30 *
31 * @since 4.5
32 */
33 @FunctionalInterface
34 public interface IndexProducer {
35
36 /**
37 * Creates an IndexProducer from a {@code BitMapProducer}.
38 * @param producer the {@code BitMapProducer}
39 * @return a new {@code IndexProducer}.
40 */
41 static IndexProducer fromBitMapProducer(final BitMapProducer producer) {
42 Objects.requireNonNull(producer, "producer");
43 return consumer -> {
44 final LongPredicate longPredicate = new LongPredicate() {
45 int wordIdx;
46
47 @Override
48 public boolean test(long word) {
49 int i = wordIdx;
50 while (word != 0) {
51 if ((word & 1) == 1 && !consumer.test(i)) {
52 return false;
53 }
54 word >>>= 1;
55 i++;
56 }
57 wordIdx += 64;
58 return true;
59 }
60 };
61 return producer.forEachBitMap(longPredicate::test);
62 };
63 }
64
65 /**
66 * Creates an IndexProducer from an array of integers.
67 * @param values the index values
68 * @return an IndexProducer that uses the values.
69 */
70 static IndexProducer fromIndexArray(final int... values) {
71 return new IndexProducer() {
72
73 @Override
74 public int[] asIndexArray() {
75 return values.clone();
76 }
77
78 @Override
79 public boolean forEachIndex(final IntPredicate predicate) {
80 for (final int value : values) {
81 if (!predicate.test(value)) {
82 return false;
83 }
84 }
85 return true;
86 }
87 };
88 }
89
90 /**
91 * Return a copy of the IndexProducer data as an int array.
92 *
93 * <p>Indices ordering and uniqueness is not guaranteed.</p>
94 *
95 * <p><em>
96 * The default implementation of this method creates an array and populates
97 * it. Implementations that have access to an index array should consider
98 * returning a copy of that array if possible.
99 * </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 }