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.TreeMap;
020import java.util.function.IntPredicate;
021
022
023/**
024 * Some Bloom filter implementations use a count rather than a bit flag. The term {@code Cell} is used to
025 * refer to these counts and their associated index.  This class is the equivalent of the index extractor except
026 * that it produces cells.
027 *
028 * <p>Note that a CellExtractor must not return duplicate indices and must be ordered.</p>
029 *
030 * <p>Implementations must guarantee that:</p>
031 *
032 * <ul>
033 * <li>The IndexExtractor implementation returns unique ordered indices.</li>
034 * <li>The cells are produced in IndexExtractor order.</li>
035 * <li>For every value produced by the IndexExtractor there will be only one matching
036 * cell produced by the CellExtractor.</li>
037 * <li>The CellExtractor will not generate cells with indices that are not output by the IndexExtractor.</li>
038 * <li>The IndexExtractor will not generate indices that have a zero count for the cell.</li>
039 * </ul>
040 *
041 * @since 4.5.0-M2
042 */
043@FunctionalInterface
044public interface CellExtractor extends IndexExtractor {
045
046    /**
047     * Represents an operation that accepts an {@code <index, count>} pair.
048     * Returns {@code true} if processing should continue, {@code false} otherwise.
049     *
050     * <p>Note: This is a functional interface as a specialization of
051     * {@link java.util.function.BiPredicate} for {@code int}.</p>
052     */
053    @FunctionalInterface
054    interface CellPredicate {
055        /**
056         * Performs an operation on the given {@code <index, count>} pair.
057         *
058         * @param index the bit index.
059         * @param count the cell value at the specified bit index.
060         * @return {@code true} if processing should continue, {@code false} if processing should stop.
061         */
062        boolean test(int index, int count);
063    }
064
065    /**
066     * Creates a CellExtractor from an IndexExtractor.
067     *
068     * <p>Note the following properties:</p>
069     * <ul>
070     * <li>Each index returned from the IndexExtractor is assumed to have a cell value of 1.</li>
071     * <li>The CellExtractor aggregates duplicate indices from the IndexExtractor.</li>
072     * </ul>
073     *
074     * <p>A CellExtractor that outputs the mapping [(1,2),(2,3),(3,1)] can be created from many combinations
075     * of indices including:</p>
076     * <pre>
077     * [1, 1, 2, 2, 2, 3]
078     * [1, 3, 1, 2, 2, 2]
079     * [3, 2, 1, 2, 1, 2]
080     * ...
081     * </pre>
082     *
083     * @param indexExtractor An index indexExtractor.
084     * @return A CellExtractor with the same indices as the IndexExtractor.
085     */
086    static CellExtractor from(final IndexExtractor indexExtractor) {
087        return new CellExtractor() {
088            /**
089             * Class to track cell values in the TreeMap.
090             */
091            final class CounterCell implements Comparable<CounterCell> {
092                final int idx;
093                int count;
094
095                CounterCell(final int idx, final int count) {
096                    this.idx = idx;
097                    this.count = count;
098                }
099
100                @Override
101                public int compareTo(final CounterCell other) {
102                    return Integer.compare(idx, other.idx);
103                }
104            }
105
106            TreeMap<CounterCell, CounterCell> counterCells = new TreeMap<>();
107
108            @Override
109            public int[] asIndexArray() {
110                populate();
111                return counterCells.keySet().stream().mapToInt(c -> c.idx).toArray();
112            }
113
114            private void populate() {
115                if (counterCells.isEmpty()) {
116                    indexExtractor.processIndices(idx -> {
117                        final CounterCell cell = new CounterCell(idx, 1);
118                        final CounterCell counter = counterCells.get(cell);
119                        if (counter == null) {
120                            counterCells.put(cell, cell);
121                        } else {
122                            counter.count++;
123                        }
124                        return true;
125                    });
126                }
127            }
128
129            @Override
130            public boolean processCells(final CellPredicate consumer) {
131                populate();
132                for (final CounterCell cell : counterCells.values()) {
133                    if (!consumer.test(cell.idx, cell.count)) {
134                        return false;
135                    }
136                }
137                return true;
138            }
139        };
140    }
141
142    /**
143     * Performs the given action for each {@code cell}  where the cell count is non-zero.
144     *
145     * <p>Some Bloom filter implementations use a count rather than a bit flag.  The term {@code Cell} is used to
146     * refer to these counts.</p>
147     *
148     * <p>Any exceptions thrown by the action are relayed to the caller. The consumer is applied to each
149     * cell. If the consumer returns {@code false} the execution is stopped, {@code false}
150     * is returned, and no further pairs are processed.</p>
151     *
152     * @param consumer the action to be performed for each non-zero cell.
153     * @return {@code true} if all cells return true from consumer, {@code false} otherwise.
154     * @throws NullPointerException if the specified consumer is null
155     */
156    boolean processCells(CellPredicate consumer);
157
158    /**
159     * The default implementation returns distinct and ordered indices for all cells with a non-zero count.
160     */
161    @Override
162    default boolean processIndices(final IntPredicate predicate) {
163        return processCells((i, v) -> predicate.test(i));
164    }
165
166    @Override
167    default IndexExtractor uniqueIndices() {
168        return this;
169    }
170}
171