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