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.text.similarity;
018
019import java.util.Collection;
020import java.util.HashMap;
021import java.util.Map;
022import java.util.Map.Entry;
023import java.util.Set;
024import java.util.function.Function;
025
026/**
027 * Measures the intersection of two sets created from a pair of character sequences.
028 *
029 * <p>It is assumed that the type {@code T} correctly conforms to the requirements for storage
030 * within a {@link Set} or {@link HashMap}. Ideally the type is immutable and implements
031 * {@link Object#equals(Object)} and {@link Object#hashCode()}.</p>
032 *
033 * @param <T> the type of the elements extracted from the character sequence
034 * @since 1.7
035 * @see Set
036 * @see HashMap
037 */
038public class IntersectionSimilarity<T> implements SimilarityScore<IntersectionResult> {
039
040    /**
041     * Mutable counter class for storing the count of elements.
042     */
043    private static final class BagCount {
044
045        /** Private, mutable but must be used as immutable. */
046        private static final BagCount ZERO = new BagCount();
047
048        /** The count. */
049        int count;
050
051        private BagCount() {
052            this.count = 0;
053        }
054    }
055
056    // The following is adapted from commons-collections for a Bag.
057    // A Bag is a collection that can store the count of the number
058    // of copies of each element.
059
060    /**
061     * A minimal implementation of a Bag that can store elements and a count.
062     *
063     * <p>For the intended purpose the Bag does not have to be a {@link Collection}. It does not
064     * even have to know its own size.
065     */
066    private class TinyBag {
067        /** The backing map. */
068        private final Map<T, BagCount> map;
069
070        /**
071         * Create a new tiny bag.
072         *
073         * @param initialCapacity the initial capacity
074         */
075        TinyBag(final int initialCapacity) {
076            map = new HashMap<>(initialCapacity);
077        }
078
079        /**
080         * Adds a new element to the bag, incrementing its count in the underlying map.
081         *
082         * @param object the object to add
083         */
084        void add(final T object) {
085            map.computeIfAbsent(object, k -> new BagCount()).count++;
086        }
087
088        /**
089         * Returns a Set view of the mappings contained in this bag.
090         *
091         * @return The Set view
092         */
093        Set<Entry<T, BagCount>> entrySet() {
094            return map.entrySet();
095        }
096
097        /**
098         * Returns the number of occurrence of the given element in this bag by
099         * looking up its count in the underlying map.
100         *
101         * @param object the object to search for
102         * @return The number of occurrences of the object, zero if not found
103         */
104        int getCount(final Object object) {
105            return map.getOrDefault(object, BagCount.ZERO).count;
106        }
107
108        /**
109         * Get the number of unique elements in the bag.
110         *
111         * @return The unique element size
112         */
113        int uniqueElementSize() {
114            return map.size();
115        }
116    }
117
118    /**
119     * Computes the intersection between two sets. This is the count of all the elements
120     * that are within both sets.
121     *
122     * @param <T> the type of the elements in the set
123     * @param setA the set A
124     * @param setB the set B
125     * @return The intersection
126     */
127    private static <T> int getIntersection(final Set<T> setA, final Set<T> setB) {
128        int intersection = 0;
129        for (final T element : setA) {
130            if (setB.contains(element)) {
131                intersection++;
132            }
133        }
134        return intersection;
135    }
136
137    /** The converter used to create the elements from the characters. */
138    private final Function<CharSequence, Collection<T>> converter;
139
140    /**
141     * Create a new intersection similarity using the provided converter.
142     *
143     * <p>
144     * If the converter returns a {@link Set} then the intersection result will
145     * not include duplicates. Any other {@link Collection} is used to produce a result
146     * that will include duplicates in the intersect and union.
147     * </p>
148     *
149     * @param converter the converter used to create the elements from the characters
150     * @throws IllegalArgumentException if the converter is null
151     */
152    public IntersectionSimilarity(final Function<CharSequence, Collection<T>> converter) {
153        if (converter == null) {
154            throw new IllegalArgumentException("Converter must not be null");
155        }
156        this.converter = converter;
157    }
158
159    /**
160     * Calculates the intersection of two character sequences passed as input.
161     *
162     * @param left first character sequence
163     * @param right second character sequence
164     * @return The intersection result
165     * @throws IllegalArgumentException if either input sequence is {@code null}
166     */
167    @Override
168    public IntersectionResult apply(final CharSequence left, final CharSequence right) {
169        if (left == null || right == null) {
170            throw new IllegalArgumentException("Input cannot be null");
171        }
172
173        // Create the elements from the sequences
174        final Collection<T> objectsA = converter.apply(left);
175        final Collection<T> objectsB = converter.apply(right);
176        final int sizeA = objectsA.size();
177        final int sizeB = objectsB.size();
178
179        // Short-cut if either collection is empty
180        if (Math.min(sizeA, sizeB) == 0) {
181            // No intersection
182            return new IntersectionResult(sizeA, sizeB, 0);
183        }
184
185        // Intersection = count the number of shared elements
186        final int intersection;
187        if (objectsA instanceof Set && objectsB instanceof Set) {
188            // If a Set then the elements will only have a count of 1.
189            // Iterate over the smaller set.
190            intersection = sizeA < sizeB
191                    ? getIntersection((Set<T>) objectsA, (Set<T>) objectsB)
192                    : getIntersection((Set<T>) objectsB, (Set<T>) objectsA);
193        } else  {
194            // Create a bag for each collection
195            final TinyBag bagA = toBag(objectsA);
196            final TinyBag bagB = toBag(objectsB);
197            // Iterate over the smaller number of unique elements
198            intersection = bagA.uniqueElementSize() < bagB.uniqueElementSize()
199                    ? getIntersection(bagA, bagB)
200                    : getIntersection(bagB, bagA);
201        }
202
203        return new IntersectionResult(sizeA, sizeB, intersection);
204    }
205
206    /**
207     * Computes the intersection between two bags. This is the sum of the minimum
208     * count of each element that is within both sets.
209     *
210     * @param bagA the bag A
211     * @param bagB the bag B
212     * @return The intersection
213     */
214    private int getIntersection(final TinyBag bagA, final TinyBag bagB) {
215        int intersection = 0;
216        for (final Entry<T, BagCount> entry : bagA.entrySet()) {
217            final T element = entry.getKey();
218            final int count = entry.getValue().count;
219            // The intersection of this entry in both bags is the minimum count
220            intersection += Math.min(count, bagB.getCount(element));
221        }
222        return intersection;
223    }
224
225    /**
226     * Converts the collection to a bag. The bag will contain the count of each element
227     * in the collection.
228     *
229     * @param objects the objects
230     * @return The bag
231     */
232    private TinyBag toBag(final Collection<T> objects) {
233        final TinyBag bag = new TinyBag(objects.size());
234        objects.forEach(bag::add);
235        return bag;
236    }
237}