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