    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.set;
    018
    019import java.io.Serializable;
    020import java.lang.reflect.Array;
    021import java.util.ArrayList;
    022import java.util.Collection;
    023import java.util.HashSet;
    024import java.util.Iterator;
    025import java.util.List;
    026import java.util.Objects;
    027import java.util.Set;
    028import java.util.function.Predicate;
    029
    030import org.apache.commons.collections4.CollectionUtils;
    031import org.apache.commons.collections4.IterableUtils;
    032import org.apache.commons.collections4.collection.CompositeCollection;
    033import org.apache.commons.collections4.iterators.EmptyIterator;
    034import org.apache.commons.collections4.iterators.IteratorChain;
    035import org.apache.commons.collections4.list.UnmodifiableList;
    036
    037/**
    038 * Decorates a set of other sets to provide a single unified view.
    039 * <p>
    040 * Changes made to this set will actually be made on the decorated set.
    041 * Add operations require the use of a pluggable strategy.
    042 * If no strategy is provided then add is unsupported.
    043 * </p>
    044 * <p>
    045 * From version 4.0, this class does not extend
    046 * {@link CompositeCollection CompositeCollection}
    047 * anymore due to its input restrictions (only accepts Sets).
    048 * See <a href="https://issues.apache.org/jira/browse/COLLECTIONS-424">COLLECTIONS-424</a>
    049 * for more details.
    050 * </p>
    051 *
    052 * @param <E> The type of the elements in this set
    053 * @since 3.0
    054 */
    055public class CompositeSet<E> implements Set<E>, Serializable {
    056
    057    /**
    058     * Defines callbacks for mutation operations.
    059     *
    060     * @param <E> The type of the elements in this instance.
    061     */
    062    public interface SetMutator<E> extends Serializable {
    063
    064        /**
    065         * Called when an object is to be added to the composite.
    066         *
    067         * @param composite  The CompositeSet being changed
    068         * @param sets  all of the Set instances in this CompositeSet
    069         * @param obj  The object being added
    070         * @return true if the collection is changed
    071         * @throws UnsupportedOperationException if add is unsupported
    072         * @throws ClassCastException if the object cannot be added due to its type
    073         * @throws NullPointerException if the object cannot be added because its null
    074         * @throws IllegalArgumentException if the object cannot be added
    075         */
    076        boolean add(CompositeSet<E> composite, List<Set<E>> sets, E obj);
    077
    078        /**
    079         * Called when a collection is to be added to the composite.
    080         *
    081         * @param composite  The CompositeSet being changed
    082         * @param sets  all of the Set instances in this CompositeSet
    083         * @param coll  The collection being added
    084         * @return true if the collection is changed
    085         * @throws UnsupportedOperationException if add is unsupported
    086         * @throws ClassCastException if the object cannot be added due to its type
    087         * @throws NullPointerException if the object cannot be added because its null
    088         * @throws IllegalArgumentException if the object cannot be added
    089         */
    090        boolean addAll(CompositeSet<E> composite,
    091                              List<Set<E>> sets,
    092                              Collection<? extends E> coll);
    093
    094        /**
    095         * Called when a Set is added to the CompositeSet and there is a
    096         * collision between existing and added sets.
    097         * <p>
    098         * If {@code added} and {@code existing} still have any intersects
    099         * after this method returns an IllegalArgumentException will be thrown.
    100         *
    101         * @param comp  The CompositeSet being modified
    102         * @param existing  The Set already existing in the composite
    103         * @param added  The Set being added to the composite
    104         * @param intersects  The intersection of the existing and added sets
    105         */
    106        void resolveCollision(CompositeSet<E> comp,
    107                                     Set<E> existing,
    108                                     Set<E> added,
    109                                     Collection<E> intersects);
    110    }
    111
    112    /** Serialization version */
    113    private static final long serialVersionUID = 5185069727540378940L;
    114
    115    /** SetMutator to handle changes to the collection */
    116    private SetMutator<E> mutator;
    117
    118    /** Sets in the composite */
    119    private final List<Set<E>> all = new ArrayList<>();
    120
    121    /**
    122     * Creates an empty CompositeSet.
    123     */
    124    public CompositeSet() {
    125    }
    126
    127    /**
    128     * Creates a CompositeSet with just {@code set} composited.
    129     *
    130     * @param set  The initial set in the composite
    131     */
    132    public CompositeSet(final Set<E> set) {
    133        addComposited(set);
    134    }
    135
    136    /**
    137     * Creates a composite set with sets as the initial set of composited Sets.
    138     *
    139     * @param sets  The initial sets in the composite
    140     */
    141    public CompositeSet(final Set<E>... sets) {
    142        addComposited(sets);
    143    }
    144
    145    /**
    146     * Adds an object to the collection, throwing UnsupportedOperationException
    147     * unless a SetMutator strategy is specified.
    148     *
    149     * @param obj  The object to add
    150     * @return {@code true} if the collection was modified
    151     * @throws UnsupportedOperationException if SetMutator hasn't been set or add is unsupported
    152     * @throws ClassCastException if the object cannot be added due to its type
    153     * @throws NullPointerException if the object cannot be added because its null
    154     * @throws IllegalArgumentException if the object cannot be added
    155     */
    156    @Override
    157    public boolean add(final E obj) {
    158        if (mutator == null) {
    159            throw new UnsupportedOperationException(
    160                "add() is not supported on CompositeSet without a SetMutator strategy");
    161        }
    162        return mutator.add(this, all, obj);
    163    }
    164
    165    /**
    166     * Adds a collection of elements to this composite, throwing
    167     * UnsupportedOperationException unless a SetMutator strategy is specified.
    168     *
    169     * @param coll  The collection to add
    170     * @return true if the composite was modified
    171     * @throws UnsupportedOperationException if SetMutator hasn't been set or add is unsupported
    172     * @throws ClassCastException if the object cannot be added due to its type
    173     * @throws NullPointerException if the object cannot be added because its null
    174     * @throws IllegalArgumentException if the object cannot be added
    175     */
    176    @Override
    177    public boolean addAll(final Collection<? extends E> coll) {
    178        if (mutator == null) {
    179            throw new UnsupportedOperationException(
    180                "addAll() is not supported on CompositeSet without a SetMutator strategy");
    181        }
    182        return mutator.addAll(this, all, coll);
    183    }
    184
    185    /**
    186     * Adds a Set to this composite.
    187     *
    188     * @param set  The set to add
    189     * @throws IllegalArgumentException if a SetMutator is set, but fails to resolve a collision
    190     * @throws UnsupportedOperationException if there is no SetMutator set
    191     * @see SetMutator
    192     */
    193    public synchronized void addComposited(final Set<E> set) {
    194        if (set != null) {
    195            for (final Set<E> existingSet : getSets()) {
    196                final Collection<E> intersects = CollectionUtils.intersection(existingSet, set);
    197                if (!intersects.isEmpty()) {
    198                    if (mutator == null) {
    199                        throw new UnsupportedOperationException(
    200                                "Collision adding composited set with no SetMutator set");
    201                    }
    202                    getMutator().resolveCollision(this, existingSet, set, intersects);
    203                    if (!CollectionUtils.intersection(existingSet, set).isEmpty()) {
    204                        throw new IllegalArgumentException(
    205                                "Attempt to add illegal entry unresolved by SetMutator.resolveCollision()");
    206                    }
    207                }
    208            }
    209            all.add(set);
    210        }
    211    }
    212
    213    /**
    214     * Adds these Sets to the list of sets in this composite
    215     *
    216     * @param sets  The Sets to be appended to the composite
    217     */
    218    public void addComposited(final Set<E>... sets) {
    219        if (sets != null) {
    220            for (final Set<E> set : sets) {
    221                addComposited(set);
    222            }
    223        }
    224    }
    225
    226    /**
    227     * Adds these Sets to the list of sets in this composite.
    228     *
    229     * @param set1  The first Set to be appended to the composite
    230     * @param set2  The second Set to be appended to the composite
    231     */
    232    public void addComposited(final Set<E> set1, final Set<E> set2) {
    233        addComposited(set1);
    234        addComposited(set2);
    235    }
    236
    237    /**
    238     * Removes all of the elements from this composite set.
    239     * <p>
    240     * This implementation calls {@code clear()} on each set.
    241     *
    242     * @throws UnsupportedOperationException if clear is unsupported
    243     */
    244    @Override
    245    public void clear() {
    246        for (final Collection<E> coll : all) {
    247            coll.clear();
    248        }
    249    }
    250
    251    /**
    252     * Checks whether this composite set contains the object.
    253     * <p>
    254     * This implementation calls {@code contains()} on each set.
    255     *
    256     * @param obj  The object to search for
    257     * @return true if obj is contained in any of the contained sets
    258     */
    259    @Override
    260    public boolean contains(final Object obj) {
    261        for (final Set<E> item : all) {
    262            if (item.contains(obj)) {
    263                return true;
    264            }
    265        }
    266        return false;
    267    }
    268
    269    /**
    270     * Checks whether this composite contains all the elements in the specified collection.
    271     * <p>
    272     * This implementation calls {@code contains()} for each element in the
    273     * specified collection.
    274     *
    275     * @param coll  The collection to check for
    276     * @return true if all elements contained
    277     */
    278    @Override
    279    public boolean containsAll(final Collection<?> coll) {
    280        if (coll == null) {
    281            return false;
    282        }
    283        for (final Object item : coll) {
    284            if (!contains(item)) {
    285                return false;
    286            }
    287        }
    288        return true;
    289    }
    290
    291    /**
    292     * {@inheritDoc}
    293     *
    294     * @see java.util.Set#equals
    295     */
    296    @Override
    297    public boolean equals(final Object obj) {
    298        if (obj instanceof Set) {
    299            final Set<?> set = (Set<?>) obj;
    300            return set.size() == this.size() && set.containsAll(this);
    301        }
    302        return false;
    303    }
    304
    305    /**
    306     * Gets the set mutator to be used for this CompositeSet.
    307     *
    308     * @return The set mutator
    309     */
    310    protected SetMutator<E> getMutator() {
    311        return mutator;
    312    }
    313
    314    /**
    315     * Gets the sets being decorated.
    316     *
    317     * @return Unmodifiable list of all sets in this composite.
    318     */
    319    public List<Set<E>> getSets() {
    320        return UnmodifiableList.unmodifiableList(all);
    321    }
    322
    323    /**
    324     * {@inheritDoc}
    325     *
    326     * @see java.util.Set#hashCode
    327     */
    328    @Override
    329    public int hashCode() {
    330        int code = 0;
    331        for (final E e : this) {
    332            code += e == null ? 0 : e.hashCode();
    333        }
    334        return code;
    335    }
    336
    337    /**
    338     * Checks whether this composite set is empty.
    339     * <p>
    340     * This implementation calls {@code isEmpty()} on each set.
    341     *
    342     * @return true if all of the contained sets are empty
    343     */
    344    @Override
    345    public boolean isEmpty() {
    346        for (final Set<E> item : all) {
    347            if (!item.isEmpty()) {
    348                return false;
    349            }
    350        }
    351        return true;
    352    }
    353
    354    /**
    355     * Gets an iterator over all the sets in this composite.
    356     * <p>
    357     * This implementation uses an {@code IteratorChain}.
    358     *
    359     * @return An {@code IteratorChain} instance which supports
    360     *  {@code remove()}. Iteration occurs over contained collections in
    361     *  the order they were added, but this behavior should not be relied upon.
    362     * @see IteratorChain
    363     */
    364    @Override
    365    public Iterator<E> iterator() {
    366        if (all.isEmpty()) {
    367            return EmptyIterator.<E>emptyIterator();
    368        }
    369        final IteratorChain<E> chain = new IteratorChain<>();
    370        all.forEach(item -> chain.addIterator(item.iterator()));
    371        return chain;
    372    }
    373
    374    /**
    375     * If a {@code CollectionMutator} is defined for this CompositeSet then this
    376     * method will be called anyway.
    377     *
    378     * @param obj  object to be removed
    379     * @return true if the object is removed, false otherwise
    380     */
    381    @Override
    382    public boolean remove(final Object obj) {
    383        for (final Set<E> set : getSets()) {
    384            if (set.contains(obj)) {
    385                return set.remove(obj);
    386            }
    387        }
    388        return false;
    389    }
    390
    391    /**
    392     * Removes the elements in the specified collection from this composite set.
    393     * <p>
    394     * This implementation calls {@code removeAll} on each collection.
    395     *
    396     * @param coll  The collection to remove
    397     * @return true if the composite was modified
    398     * @throws UnsupportedOperationException if removeAll is unsupported
    399     */
    400    @Override
    401    public boolean removeAll(final Collection<?> coll) {
    402        if (CollectionUtils.isEmpty(coll)) {
    403            return false;
    404        }
    405        boolean changed = false;
    406        for (final Collection<E> item : all) {
    407            changed |= item.removeAll(coll);
    408        }
    409        return changed;
    410    }
    411
    412    /**
    413     * Removes a set from those being decorated in this composite.
    414     *
    415     * @param set  set to be removed
    416     */
    417    public void removeComposited(final Set<E> set) {
    418        all.remove(set);
    419    }
    420
    421    /**
    422     * @since 4.4
    423     */
    424    @Override
    425    public boolean removeIf(final Predicate<? super E> filter) {
    426        if (Objects.isNull(filter)) {
    427            return false;
    428        }
    429        boolean changed = false;
    430        for (final Collection<E> item : all) {
    431            changed |= item.removeIf(filter);
    432        }
    433        return changed;
    434    }
    435
    436    /**
    437     * Retains all the elements in the specified collection in this composite set,
    438     * removing all others.
    439     * <p>
    440     * This implementation calls {@code retainAll()} on each collection.
    441     *
    442     * @param coll  The collection to remove
    443     * @return true if the composite was modified
    444     * @throws UnsupportedOperationException if retainAll is unsupported
    445     */
    446    @Override
    447    public boolean retainAll(final Collection<?> coll) {
    448        boolean changed = false;
    449        for (final Collection<E> item : all) {
    450            changed |= item.retainAll(coll);
    451        }
    452        return changed;
    453    }
    454
    455    /**
    456     * Specify a SetMutator strategy instance to handle changes.
    457     *
    458     * @param mutator  The mutator to use
    459     */
    460    public void setMutator(final SetMutator<E> mutator) {
    461        this.mutator = mutator;
    462    }
    463
    464    /**
    465     * Gets the size of this composite set.
    466     * <p>
    467     * This implementation calls {@code size()} on each set.
    468     *
    469     * @return total number of elements in all contained containers, or
    470     *         {@code Integer.MAX_VALUE} if the total exceeds it
    471     */
    472    @Override
    473    public int size() {
    474        return IterableUtils.sumSizesToInt(all);
    475    }
    476
    477    /**
    478     * Returns an array containing all of the elements in this composite.
    479     *
    480     * @return An object array of all the elements in the collection
    481     */
    482    @Override
    483    public Object[] toArray() {
    484        final Object[] result = new Object[size()];
    485        int i = 0;
    486        for (final Iterator<E> it = iterator(); it.hasNext(); i++) {
    487            result[i] = it.next();
    488        }
    489        return result;
    490    }
    491
    492    /**
    493     * Returns an object array, populating the supplied array if possible.
    494     * See {@code Collection} interface for full details.
    495     *
    496     * @param <T>  the type of the elements in the collection
    497     * @param array  The array to use, populating if possible
    498     * @return An array of all the elements in the collection
    499     */
    500    @Override
    501    @SuppressWarnings("unchecked")
    502    public <T> T[] toArray(final T[] array) {
    503        final int size = size();
    504        Object[] result = null;
    505        if (array.length >= size) {
    506            result = array;
    507        } else {
    508            result = (Object[]) Array.newInstance(array.getClass().getComponentType(), size);
    509        }
    510
    511        int offset = 0;
    512        for (final Collection<E> item : all) {
    513            for (final E e : item) {
    514                result[offset++] = e;
    515            }
    516        }
    517        if (result.length > size) {
    518            result[size] = null;
    519        }
    520        return (T[]) result;
    521    }
    522
    523    /**
    524     * Returns a new Set containing all of the elements.
    525     *
    526     * @return A new HashSet containing all of the elements in this composite.
    527     *   The new collection is <em>not</em> backed by this composite.
    528     */
    529    public Set<E> toSet() {
    530        return new HashSet<>(this);
    531    }
    532}