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