    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.function.LongBinaryOperator;
    020
    021/**
    022 * Implementations of set operations on BitMapExtractors.
    023 *
    024 * @since 4.5.0-M1
    025 */
    026public final class SetOperations {
    027
    028    /**
    029     * Calculates the cardinality of the logical {@code AND} of the bit maps for the two filters.
    030     *
    031     * @param first  The first BitMapExtractor.
    032     * @param second The second BitMapExtractor
    033     * @return The cardinality of the {@code AND} of the filters.
    034     */
    035    public static int andCardinality(final BitMapExtractor first, final BitMapExtractor second) {
    036        return cardinality(first, second, (x, y) -> x & y);
    037    }
    038
    039    /**
    040     * Calculates the cardinality of a BitMapExtractor. By necessity this method will visit each bit map created by the bitMapExtractor.
    041     *
    042     * @param bitMapExtractor The extractor to calculate the cardinality for.
    043     * @return The cardinality of the bit maps produced by the bitMapExtractor.
    044     */
    045    public static int cardinality(final BitMapExtractor bitMapExtractor) {
    046        final int[] cardinality = new int[1];
    047        bitMapExtractor.processBitMaps(l -> {
    048            cardinality[0] += Long.bitCount(l);
    049            return true;
    050        });
    051        return cardinality[0];
    052    }
    053
    054    /**
    055     * Calculates the cardinality of the result of a LongBinaryOperator using the {@code BitMapExtractor.makePredicate} method.
    056     *
    057     * @param first  The first BitMapExtractor
    058     * @param second The second BitMapExtractor
    059     * @param op     A long binary operation on where x = {@code first} and y = {@code second} bitmap extractors.
    060     * @return The calculated cardinality.
    061     */
    062    private static int cardinality(final BitMapExtractor first, final BitMapExtractor second, final LongBinaryOperator op) {
    063        final int[] cardinality = new int[1];
    064
    065        first.processBitMapPairs(second, (x, y) -> {
    066            cardinality[0] += Long.bitCount(op.applyAsLong(x, y));
    067            return true;
    068        });
    069        return cardinality[0];
    070    }
    071
    072    /**
    073     * Calculates the Cosine distance between two BitMapExtractor.
    074     * <p>
    075     * Cosine distance is defined as {@code 1 - Cosine similarity}
    076     * </p>
    077     *
    078     * @param first  The first BitMapExtractor.
    079     * @param second The second BitMapExtractor.
    080     * @return The jaccard distance.
    081     */
    082    public static double cosineDistance(final BitMapExtractor first, final BitMapExtractor second) {
    083        return 1.0 - cosineSimilarity(first, second);
    084    }
    085
    086    /**
    087     * Calculates the Cosine similarity between two BitMapExtractors.
    088     * <p>
    089     * Also known as Orchini similarity and the Tucker coefficient of congruence or Ochiai similarity.
    090     * </p>
    091     * <p>
    092     * If either extractor is empty the result is 0 (zero)
    093     * </p>
    094     *
    095     * @param first  The first BitMapExtractor.
    096     * @param second The second BitMapExtractor.
    097     * @return The Cosine similarity.
    098     */
    099    public static double cosineSimilarity(final BitMapExtractor first, final BitMapExtractor second) {
    100        final int numerator = andCardinality(first, second);
    101        // Given that the cardinality is an int then the product as a double will not
    102        // overflow, we can use one sqrt:
    103        return numerator == 0 ? 0 : numerator / Math.sqrt((double) cardinality(first) * cardinality(second));
    104    }
    105
    106    /**
    107     * Calculates the Cosine similarity between two Bloom filters.
    108     * <p>
    109     * Also known as Orchini similarity and the Tucker coefficient of congruence or Ochiai similarity.
    110     * </p>
    111     * <p>
    112     * If either filter is empty (no enabled bits) the result is 0 (zero)
    113     * </p>
    114     * <p>
    115     * This is a version of cosineSimilarity optimized for Bloom filters.
    116     * </p>
    117     *
    118     * @param first  The first Bloom filter.
    119     * @param second The second Bloom filter.
    120     * @return The Cosine similarity.
    121     */
    122    public static double cosineSimilarity(final BloomFilter<?> first, final BloomFilter<?> second) {
    123        final int numerator = andCardinality(first, second);
    124        // Given that the cardinality is an int then the product as a double will not
    125        // overflow, we can use one sqrt:
    126        return numerator == 0 ? 0 : numerator / Math.sqrt((double) first.cardinality() * second.cardinality());
    127    }
    128
    129    /**
    130     * Calculates the Hamming distance between two BitMapExtractors.
    131     *
    132     * @param first  The first BitMapExtractor.
    133     * @param second The second BitMapExtractor.
    134     * @return The Hamming distance.
    135     */
    136    public static int hammingDistance(final BitMapExtractor first, final BitMapExtractor second) {
    137        return xorCardinality(first, second);
    138    }
    139
    140    /**
    141     * Calculates the Jaccard distance between two BitMapExtractor.
    142     * <p>
    143     * Jaccard distance is defined as {@code 1 - Jaccard similarity}
    144     * </p>
    145     *
    146     * @param first  The first BitMapExtractor.
    147     * @param second The second BitMapExtractor.
    148     * @return The Jaccard distance.
    149     */
    150    public static double jaccardDistance(final BitMapExtractor first, final BitMapExtractor second) {
    151        return 1.0 - jaccardSimilarity(first, second);
    152    }
    153
    154    /**
    155     * Calculates the Jaccard similarity between two BitMapExtractor.
    156     * <p>
    157     * Also known as Jaccard index, Intersection over Union, and Jaccard similarity coefficient
    158     * </p>
    159     *
    160     * @param first  The first BitMapExtractor.
    161     * @param second The second BitMapExtractor.
    162     * @return The Jaccard similarity.
    163     */
    164    public static double jaccardSimilarity(final BitMapExtractor first, final BitMapExtractor second) {
    165        final int[] cardinality = new int[2];
    166        first.processBitMapPairs(second, (x, y) -> {
    167            cardinality[0] += Long.bitCount(x & y);
    168            cardinality[1] += Long.bitCount(x | y);
    169            return true;
    170        });
    171        final int intersection = cardinality[0];
    172        return intersection == 0 ? 0 : intersection / (double) cardinality[1];
    173    }
    174
    175    /**
    176     * Calculates the cardinality of the logical {@code OR} of the bit maps for the two filters.
    177     *
    178     * @param first  The first BitMapExtractor.
    179     * @param second The second BitMapExtractor
    180     * @return The cardinality of the {@code OR} of the filters.
    181     */
    182    public static int orCardinality(final BitMapExtractor first, final BitMapExtractor second) {
    183        return cardinality(first, second, (x, y) -> x | y);
    184    }
    185
    186    /**
    187     * Calculates the cardinality of the logical {@code XOR} of the bit maps for the two filters.
    188     *
    189     * @param first  The first BitMapExtractor.
    190     * @param second The second BitMapExtractor
    191     * @return The cardinality of the {@code XOR} of the filters.
    192     */
    193    public static int xorCardinality(final BitMapExtractor first, final BitMapExtractor second) {
    194        return cardinality(first, second, (x, y) -> x ^ y);
    195    }
    196
    197    /**
    198     * Do not instantiate.
    199     */
    200    private SetOperations() {
    201    }
    202}