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