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