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