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