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