    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.map;
    018
    019import java.io.Serializable;
    020
    021import java.util.Collection;
    022import java.util.Map;
    023import java.util.Set;
    024
    025import org.apache.commons.collections4.set.CompositeSet;
    026import org.apache.commons.collections4.CollectionUtils;
    027import org.apache.commons.collections4.collection.CompositeCollection;
    028
    029/**
    030 * Decorates a map of other maps to provide a single unified view.
    031 * <p>
    032 * Changes made to this map will actually be made on the decorated map.
    033 * Add and remove operations require the use of a pluggable strategy. If no
    034 * strategy is provided then add and remove are unsupported.
    035 * <p>
    036 * <strong>Note that CompositeMap is not synchronized and is not thread-safe.</strong>
    037 * If you wish to use this map from multiple threads concurrently, you must use
    038 * appropriate synchronization. The simplest approach is to wrap this map
    039 * using {@link java.util.Collections#synchronizedMap(Map)}. This class may throw
    040 * exceptions when accessed by concurrent threads without synchronization.
    041 *
    042 * @param <K> the type of the keys in this map
    043 * @param <V> the type of the values in this map
    044 * @since 3.0
    045 */
    046public class CompositeMap<K, V> extends AbstractIterableMap<K, V> implements Serializable {
    047
    048    /** Serialization version */
    049    private static final long serialVersionUID = -6096931280583808322L;
    050
    051    /** Array of all maps in the composite */
    052    private Map<K, V>[] composite;
    053
    054    /** Handle mutation operations */
    055    private MapMutator<K, V> mutator;
    056
    057    /**
    058     * Create a new, empty, CompositeMap.
    059     */
    060    @SuppressWarnings("unchecked")
    061    public CompositeMap() {
    062        this(new Map[] {}, null);
    063    }
    064
    065    /**
    066     * Create a new CompositeMap with two composited Map instances.
    067     *
    068     * @param one  the first Map to be composited
    069     * @param two  the second Map to be composited
    070     * @throws IllegalArgumentException if there is a key collision
    071     */
    072    @SuppressWarnings("unchecked")
    073    public CompositeMap(final Map<K, V> one, final Map<K, V> two) {
    074        this(new Map[] { one, two }, null);
    075    }
    076
    077    /**
    078     * Create a new CompositeMap with two composited Map instances.
    079     *
    080     * @param one  the first Map to be composited
    081     * @param two  the second Map to be composited
    082     * @param mutator  MapMutator to be used for mutation operations
    083     */
    084    @SuppressWarnings("unchecked")
    085    public CompositeMap(final Map<K, V> one, final Map<K, V> two, final MapMutator<K, V> mutator) {
    086        this(new Map[] { one, two }, mutator);
    087    }
    088
    089    /**
    090     * Create a new CompositeMap which composites all of the Map instances in the
    091     * argument. It copies the argument array, it does not use it directly.
    092     *
    093     * @param composite  the Maps to be composited
    094     * @throws IllegalArgumentException if there is a key collision
    095     */
    096    public CompositeMap(final Map<K, V>... composite) {
    097        this(composite, null);
    098    }
    099
    100    /**
    101     * Create a new CompositeMap which composites all of the Map instances in the
    102     * argument. It copies the argument array, it does not use it directly.
    103     *
    104     * @param composite  Maps to be composited
    105     * @param mutator  MapMutator to be used for mutation operations
    106     */
    107    @SuppressWarnings("unchecked")
    108    public CompositeMap(final Map<K, V>[] composite, final MapMutator<K, V> mutator) {
    109        this.mutator = mutator;
    110        this.composite = new Map[0];
    111        for (int i = composite.length - 1; i >= 0; --i) {
    112            this.addComposited(composite[i]);
    113        }
    114    }
    115
    116    //-----------------------------------------------------------------------
    117    /**
    118     * Specify the MapMutator to be used by mutation operations.
    119     *
    120     * @param mutator  the MapMutator to be used for mutation delegation
    121     */
    122    public void setMutator(final MapMutator<K, V> mutator) {
    123        this.mutator = mutator;
    124    }
    125
    126    /**
    127     * Add an additional Map to the composite.
    128     *
    129     * @param map  the Map to be added to the composite
    130     * @throws IllegalArgumentException if there is a key collision and there is no
    131     *         MapMutator set to handle it.
    132     */
    133    @SuppressWarnings("unchecked")
    134    public synchronized void addComposited(final Map<K, V> map) throws IllegalArgumentException {
    135        for (int i = composite.length - 1; i >= 0; --i) {
    136            final Collection<K> intersect = CollectionUtils.intersection(this.composite[i].keySet(), map.keySet());
    137            if (intersect.size() != 0) {
    138                if (this.mutator == null) {
    139                    throw new IllegalArgumentException("Key collision adding Map to CompositeMap");
    140                }
    141                this.mutator.resolveCollision(this, this.composite[i], map, intersect);
    142            }
    143        }
    144        final Map<K, V>[] temp = new Map[this.composite.length + 1];
    145        System.arraycopy(this.composite, 0, temp, 0, this.composite.length);
    146        temp[temp.length - 1] = map;
    147        this.composite = temp;
    148    }
    149
    150    /**
    151     * Remove a Map from the composite.
    152     *
    153     * @param map  the Map to be removed from the composite
    154     * @return The removed Map or <code>null</code> if map is not in the composite
    155     */
    156    @SuppressWarnings("unchecked")
    157    public synchronized Map<K, V> removeComposited(final Map<K, V> map) {
    158        final int size = this.composite.length;
    159        for (int i = 0; i < size; ++i) {
    160            if (this.composite[i].equals(map)) {
    161                final Map<K, V>[] temp = new Map[size - 1];
    162                System.arraycopy(this.composite, 0, temp, 0, i);
    163                System.arraycopy(this.composite, i + 1, temp, i, size - i - 1);
    164                this.composite = temp;
    165                return map;
    166            }
    167        }
    168        return null;
    169    }
    170
    171    //-----------------------------------------------------------------------
    172    /**
    173     * Calls <code>clear()</code> on all composited Maps.
    174     *
    175     * @throws UnsupportedOperationException if any of the composited Maps do not support clear()
    176     */
    177    @Override
    178    public void clear() {
    179        for (int i = this.composite.length - 1; i >= 0; --i) {
    180            this.composite[i].clear();
    181        }
    182    }
    183
    184    /**
    185     * Returns {@code true} if this map contains a mapping for the specified
    186     * key.  More formally, returns {@code true} if and only if
    187     * this map contains at a mapping for a key {@code k} such that
    188     * {@code (key==null ? k==null : key.equals(k))}.  (There can be
    189     * at most one such mapping.)
    190     *
    191     * @param key  key whose presence in this map is to be tested.
    192     * @return {@code true} if this map contains a mapping for the specified
    193     *         key.
    194     *
    195     * @throws ClassCastException if the key is of an inappropriate type for
    196     *         this map (optional).
    197     * @throws NullPointerException if the key is {@code null} and this map
    198     *            does not not permit {@code null} keys (optional).
    199     */
    200    @Override
    201    public boolean containsKey(final Object key) {
    202        for (int i = this.composite.length - 1; i >= 0; --i) {
    203            if (this.composite[i].containsKey(key)) {
    204                return true;
    205            }
    206        }
    207        return false;
    208    }
    209
    210    /**
    211     * Returns {@code true} if this map maps one or more keys to the
    212     * specified value.  More formally, returns {@code true} if and only if
    213     * this map contains at least one mapping to a value {@code v} such that
    214     * {@code (value==null ? v==null : value.equals(v))}.  This operation
    215     * will probably require time linear in the map size for most
    216     * implementations of the {@code Map} interface.
    217     *
    218     * @param value value whose presence in this map is to be tested.
    219     * @return {@code true} if this map maps one or more keys to the
    220     *         specified value.
    221     * @throws ClassCastException if the value is of an inappropriate type for
    222     *         this map (optional).
    223     * @throws NullPointerException if the value is {@code null} and this map
    224     *            does not not permit {@code null} values (optional).
    225     */
    226    @Override
    227    public boolean containsValue(final Object value) {
    228        for (int i = this.composite.length - 1; i >= 0; --i) {
    229            if (this.composite[i].containsValue(value)) {
    230                return true;
    231            }
    232        }
    233        return false;
    234    }
    235
    236    /**
    237     * Returns a set view of the mappings contained in this map.  Each element
    238     * in the returned set is a <code>Map.Entry</code>.  The set is backed by the
    239     * map, so changes to the map are reflected in the set, and vice-versa.
    240     * If the map is modified while an iteration over the set is in progress,
    241     * the results of the iteration are undefined.  The set supports element
    242     * removal, which removes the corresponding mapping from the map, via the
    243     * {@code Iterator.remove}, {@code Set.remove}, {@code removeAll},
    244     * {@code retainAll} and {@code clear} operations.  It does not support
    245     * the {@code add} or {@code addAll} operations.
    246     * <p>
    247     * This implementation returns a <code>CompositeSet</code> which
    248     * composites the entry sets from all of the composited maps.
    249     *
    250     * @see CompositeSet
    251     * @return a set view of the mappings contained in this map.
    252     */
    253    @Override
    254    public Set<Map.Entry<K, V>> entrySet() {
    255        final CompositeSet<Map.Entry<K, V>> entries = new CompositeSet<>();
    256        for (int i = composite.length - 1; i >= 0; --i) {
    257            entries.addComposited(composite[i].entrySet());
    258        }
    259        return entries;
    260    }
    261
    262    /**
    263     * Returns the value to which this map maps the specified key.  Returns
    264     * {@code null} if the map contains no mapping for this key.  A return
    265     * value of {@code null} does not <i>necessarily</i> indicate that the
    266     * map contains no mapping for the key; it's also possible that the map
    267     * explicitly maps the key to {@code null}.  The {@code containsKey}
    268     * operation may be used to distinguish these two cases.
    269     *
    270     * <p>More formally, if this map contains a mapping from a key
    271     * {@code k} to a value {@code v} such that <code>(key==null ? k==null :
    272     * key.equals(k))</code>, then this method returns {@code v}; otherwise
    273     * it returns {@code null}.  (There can be at most one such mapping.)
    274     *
    275     * @param key key whose associated value is to be returned.
    276     * @return the value to which this map maps the specified key, or
    277     *         {@code null} if the map contains no mapping for this key.
    278     *
    279     * @throws ClassCastException if the key is of an inappropriate type for
    280     *         this map (optional).
    281     * @throws NullPointerException key is {@code null} and this map does not
    282     *         not permit {@code null} keys (optional).
    283     *
    284     * @see #containsKey(Object)
    285     */
    286    @Override
    287    public V get(final Object key) {
    288        for (int i = this.composite.length - 1; i >= 0; --i) {
    289            if (this.composite[i].containsKey(key)) {
    290                return this.composite[i].get(key);
    291            }
    292        }
    293        return null;
    294    }
    295
    296    /**
    297     * Returns {@code true} if this map contains no key-value mappings.
    298     *
    299     * @return {@code true} if this map contains no key-value mappings.
    300     */
    301    @Override
    302    public boolean isEmpty() {
    303        for (int i = this.composite.length - 1; i >= 0; --i) {
    304            if (!this.composite[i].isEmpty()) {
    305                return false;
    306            }
    307        }
    308        return true;
    309    }
    310
    311    /**
    312     * Returns a set view of the keys contained in this map.  The set is
    313     * backed by the map, so changes to the map are reflected in the set, and
    314     * vice-versa.  If the map is modified while an iteration over the set is
    315     * in progress, the results of the iteration are undefined.  The set
    316     * supports element removal, which removes the corresponding mapping from
    317     * the map, via the {@code Iterator.remove}, {@code Set.remove},
    318     * {@code removeAll} {@code retainAll}, and {@code clear} operations.
    319     * It does not support the add or {@code addAll} operations.
    320     * <p>
    321     * This implementation returns a <code>CompositeSet</code> which
    322     * composites the key sets from all of the composited maps.
    323     *
    324     * @return a set view of the keys contained in this map.
    325     */
    326    @Override
    327    public Set<K> keySet() {
    328        final CompositeSet<K> keys = new CompositeSet<>();
    329        for (int i = this.composite.length - 1; i >= 0; --i) {
    330            keys.addComposited(this.composite[i].keySet());
    331        }
    332        return keys;
    333    }
    334
    335    /**
    336     * Associates the specified value with the specified key in this map
    337     * (optional operation).  If the map previously contained a mapping for
    338     * this key, the old value is replaced by the specified value.  (A map
    339     * {@code m} is said to contain a mapping for a key {@code k} if and only
    340     * if {@link #containsKey(Object) m.containsKey(k)} would return
    341     * {@code true}.))
    342     *
    343     * @param key key with which the specified value is to be associated.
    344     * @param value value to be associated with the specified key.
    345     * @return previous value associated with specified key, or {@code null}
    346     *         if there was no mapping for key.  A {@code null} return can
    347     *         also indicate that the map previously associated {@code null}
    348     *         with the specified key, if the implementation supports
    349     *         {@code null} values.
    350     *
    351     * @throws UnsupportedOperationException if no MapMutator has been specified
    352     * @throws ClassCastException if the class of the specified key or value
    353     *            prevents it from being stored in this map.
    354     * @throws IllegalArgumentException if some aspect of this key or value
    355     *            prevents it from being stored in this map.
    356     * @throws NullPointerException this map does not permit {@code null}
    357     *            keys or values, and the specified key or value is
    358     *            {@code null}.
    359     */
    360    @Override
    361    public V put(final K key, final V value) {
    362        if (this.mutator == null) {
    363            throw new UnsupportedOperationException("No mutator specified");
    364        }
    365        return this.mutator.put(this, this.composite, key, value);
    366    }
    367
    368    /**
    369     * Copies all of the mappings from the specified map to this map
    370     * (optional operation).  The effect of this call is equivalent to that
    371     * of calling {@link #put(Object,Object) put(k, v)} on this map once
    372     * for each mapping from key {@code k} to value {@code v} in the
    373     * specified map.  The behavior of this operation is unspecified if the
    374     * specified map is modified while the operation is in progress.
    375     *
    376     * @param map Mappings to be stored in this map.
    377     *
    378     * @throws UnsupportedOperationException if the {@code putAll} method is
    379     *         not supported by this map.
    380     *
    381     * @throws ClassCastException if the class of a key or value in the
    382     *         specified map prevents it from being stored in this map.
    383     *
    384     * @throws IllegalArgumentException some aspect of a key or value in the
    385     *         specified map prevents it from being stored in this map.
    386     * @throws NullPointerException the specified map is {@code null}, or if
    387     *         this map does not permit {@code null} keys or values, and the
    388     *         specified map contains {@code null} keys or values.
    389     */
    390    @Override
    391    public void putAll(final Map<? extends K, ? extends V> map) {
    392        if (this.mutator == null) {
    393            throw new UnsupportedOperationException("No mutator specified");
    394        }
    395        this.mutator.putAll(this, this.composite, map);
    396    }
    397
    398    /**
    399     * Removes the mapping for this key from this map if it is present
    400     * (optional operation).   More formally, if this map contains a mapping
    401     * from key {@code k} to value {@code v} such that
    402     * <code>(key==null ?  k==null : key.equals(k))</code>, that mapping
    403     * is removed.  (The map can contain at most one such mapping.)
    404     *
    405     * <p>Returns the value to which the map previously associated the key, or
    406     * {@code null} if the map contained no mapping for this key.  (A
    407     * {@code null} return can also indicate that the map previously
    408     * associated {@code null} with the specified key if the implementation
    409     * supports {@code null} values.)  The map will not contain a mapping for
    410     * the specified  key once the call returns.
    411     *
    412     * @param key key whose mapping is to be removed from the map.
    413     * @return previous value associated with specified key, or {@code null}
    414     *         if there was no mapping for key.
    415     *
    416     * @throws ClassCastException if the key is of an inappropriate type for
    417     *         the composited map (optional).
    418     * @throws NullPointerException if the key is {@code null} and the composited map
    419     *            does not not permit {@code null} keys (optional).
    420     * @throws UnsupportedOperationException if the {@code remove} method is
    421     *         not supported by the composited map containing the key
    422     */
    423    @Override
    424    public V remove(final Object key) {
    425        for (int i = this.composite.length - 1; i >= 0; --i) {
    426            if (this.composite[i].containsKey(key)) {
    427                return this.composite[i].remove(key);
    428            }
    429        }
    430        return null;
    431    }
    432
    433    /**
    434     * Returns the number of key-value mappings in this map.  If the
    435     * map contains more than {@code Integer.MAX_VALUE} elements, returns
    436     * {@code Integer.MAX_VALUE}.
    437     *
    438     * @return the number of key-value mappings in this map.
    439     */
    440    @Override
    441    public int size() {
    442        int size = 0;
    443        for (int i = this.composite.length - 1; i >= 0; --i) {
    444            size += this.composite[i].size();
    445        }
    446        return size;
    447    }
    448
    449    /**
    450     * Returns a collection view of the values contained in this map.  The
    451     * collection is backed by the map, so changes to the map are reflected in
    452     * the collection, and vice-versa.  If the map is modified while an
    453     * iteration over the collection is in progress, the results of the
    454     * iteration are undefined.  The collection supports element removal,
    455     * which removes the corresponding mapping from the map, via the
    456     * {@code Iterator.remove}, {@code Collection.remove},
    457     * {@code removeAll}, {@code retainAll} and {@code clear} operations.
    458     * It does not support the add or {@code addAll} operations.
    459     *
    460     * @return a collection view of the values contained in this map.
    461     */
    462    @Override
    463    public Collection<V> values() {
    464        final CompositeCollection<V> values = new CompositeCollection<>();
    465        for (int i = composite.length - 1; i >= 0; --i) {
    466            values.addComposited(composite[i].values());
    467        }
    468        return values;
    469    }
    470
    471    /**
    472     * Checks if this Map equals another as per the Map specification.
    473     *
    474     * @param obj  the object to compare to
    475     * @return true if the maps are equal
    476     */
    477    @Override
    478    public boolean equals(final Object obj) {
    479        if (obj instanceof Map) {
    480            final Map<?, ?> map = (Map<?, ?>) obj;
    481            return this.entrySet().equals(map.entrySet());
    482        }
    483        return false;
    484    }
    485
    486    /**
    487     * Gets a hash code for the Map as per the Map specification.
    488     * {@inheritDoc}
    489     */
    490    @Override
    491    public int hashCode() {
    492        int code = 0;
    493        for (final Map.Entry<K, V> entry : entrySet()) {
    494            code += entry.hashCode();
    495        }
    496        return code;
    497    }
    498
    499    /**
    500     * This interface allows definition for all of the indeterminate
    501     * mutators in a CompositeMap, as well as providing a hook for
    502     * callbacks on key collisions.
    503     *
    504     * @param <K> the type of the keys in the map
    505     * @param <V> the type of the values in the map
    506     */
    507    public interface MapMutator<K, V> extends Serializable {
    508        /**
    509         * Called when adding a new Composited Map results in a
    510         * key collision.
    511         *
    512         * @param composite  the CompositeMap with the collision
    513         * @param existing  the Map already in the composite which contains the
    514         *        offending key
    515         * @param added  the Map being added
    516         * @param intersect  the intersection of the keysets of the existing and added maps
    517         */
    518        void resolveCollision(CompositeMap<K, V> composite, Map<K, V> existing,
    519                Map<K, V> added, Collection<K> intersect);
    520
    521        /**
    522         * Called when the CompositeMap.put() method is invoked.
    523         *
    524         * @param map  the CompositeMap which is being modified
    525         * @param composited  array of Maps in the CompositeMap being modified
    526         * @param key  key with which the specified value is to be associated.
    527         * @param value  value to be associated with the specified key.
    528         * @return previous value associated with specified key, or {@code null}
    529         *         if there was no mapping for key.  A {@code null} return can
    530         *         also indicate that the map previously associated {@code null}
    531         *         with the specified key, if the implementation supports
    532         *         {@code null} values.
    533         *
    534         * @throws UnsupportedOperationException if not defined
    535         * @throws ClassCastException if the class of the specified key or value
    536         *            prevents it from being stored in this map.
    537         * @throws IllegalArgumentException if some aspect of this key or value
    538         *            prevents it from being stored in this map.
    539         * @throws NullPointerException this map does not permit {@code null}
    540         *            keys or values, and the specified key or value is
    541         *            {@code null}.
    542         */
    543        V put(CompositeMap<K, V> map, Map<K, V>[] composited, K key, V value);
    544
    545        /**
    546         * Called when the CompositeMap.putAll() method is invoked.
    547         *
    548         * @param map  the CompositeMap which is being modified
    549         * @param composited  array of Maps in the CompositeMap being modified
    550         * @param mapToAdd  Mappings to be stored in this CompositeMap
    551         *
    552         * @throws UnsupportedOperationException if not defined
    553         * @throws ClassCastException if the class of the specified key or value
    554         *            prevents it from being stored in this map.
    555         * @throws IllegalArgumentException if some aspect of this key or value
    556         *            prevents it from being stored in this map.
    557         * @throws NullPointerException this map does not permit {@code null}
    558         *            keys or values, and the specified key or value is
    559         *            {@code null}.
    560         */
    561        void putAll(CompositeMap<K, V> map, Map<K, V>[] composited,
    562                Map<? extends K, ? extends V> mapToAdd);
    563    }
    564}