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 887892 2013-11-24 13:43:45Z tn $
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    public void clear() {
177        for (int i = this.composite.length - 1; i >= 0; --i) {
178            this.composite[i].clear();
179        }
180    }
181
182    /**
183     * Returns <tt>true</tt> if this map contains a mapping for the specified
184     * key.  More formally, returns <tt>true</tt> if and only if
185     * this map contains at a mapping for a key <tt>k</tt> such that
186     * <tt>(key==null ? k==null : key.equals(k))</tt>.  (There can be
187     * at most one such mapping.)
188     *
189     * @param key  key whose presence in this map is to be tested.
190     * @return <tt>true</tt> if this map contains a mapping for the specified
191     *         key.
192     *
193     * @throws ClassCastException if the key is of an inappropriate type for
194     *         this map (optional).
195     * @throws NullPointerException if the key is <tt>null</tt> and this map
196     *            does not not permit <tt>null</tt> keys (optional).
197     */
198    public boolean containsKey(final Object key) {
199        for (int i = this.composite.length - 1; i >= 0; --i) {
200            if (this.composite[i].containsKey(key)) {
201                return true;
202            }
203        }
204        return false;
205    }
206
207    /**
208     * Returns <tt>true</tt> if this map maps one or more keys to the
209     * specified value.  More formally, returns <tt>true</tt> if and only if
210     * this map contains at least one mapping to a value <tt>v</tt> such that
211     * <tt>(value==null ? v==null : value.equals(v))</tt>.  This operation
212     * will probably require time linear in the map size for most
213     * implementations of the <tt>Map</tt> interface.
214     *
215     * @param value value whose presence in this map is to be tested.
216     * @return <tt>true</tt> if this map maps one or more keys to the
217     *         specified value.
218     * @throws ClassCastException if the value is of an inappropriate type for
219     *         this map (optional).
220     * @throws NullPointerException if the value is <tt>null</tt> and this map
221     *            does not not permit <tt>null</tt> values (optional).
222     */
223    public boolean containsValue(final Object value) {
224        for (int i = this.composite.length - 1; i >= 0; --i) {
225            if (this.composite[i].containsValue(value)) {
226                return true;
227            }
228        }
229        return false;
230    }
231
232    /**
233     * Returns a set view of the mappings contained in this map.  Each element
234     * in the returned set is a <code>Map.Entry</code>.  The set is backed by the
235     * map, so changes to the map are reflected in the set, and vice-versa.
236     * If the map is modified while an iteration over the set is in progress,
237     * the results of the iteration are undefined.  The set supports element
238     * removal, which removes the corresponding mapping from the map, via the
239     * <tt>Iterator.remove</tt>, <tt>Set.remove</tt>, <tt>removeAll</tt>,
240     * <tt>retainAll</tt> and <tt>clear</tt> operations.  It does not support
241     * the <tt>add</tt> or <tt>addAll</tt> operations.
242     * <p>
243     * This implementation returns a <code>CompositeSet</code> which
244     * composites the entry sets from all of the composited maps.
245     *
246     * @see CompositeSet
247     * @return a set view of the mappings contained in this map.
248     */
249    public Set<Map.Entry<K, V>> entrySet() {
250        final CompositeSet<Map.Entry<K, V>> entries = new CompositeSet<Map.Entry<K,V>>();
251        for (int i = composite.length - 1; i >= 0; --i) {
252            entries.addComposited(composite[i].entrySet());
253        }
254        return entries;
255    }
256
257    /**
258     * Returns the value to which this map maps the specified key.  Returns
259     * <tt>null</tt> if the map contains no mapping for this key.  A return
260     * value of <tt>null</tt> does not <i>necessarily</i> indicate that the
261     * map contains no mapping for the key; it's also possible that the map
262     * explicitly maps the key to <tt>null</tt>.  The <tt>containsKey</tt>
263     * operation may be used to distinguish these two cases.
264     *
265     * <p>More formally, if this map contains a mapping from a key
266     * <tt>k</tt> to a value <tt>v</tt> such that <tt>(key==null ? k==null :
267     * key.equals(k))</tt>, then this method returns <tt>v</tt>; otherwise
268     * it returns <tt>null</tt>.  (There can be at most one such mapping.)
269     *
270     * @param key key whose associated value is to be returned.
271     * @return the value to which this map maps the specified key, or
272     *         <tt>null</tt> if the map contains no mapping for this key.
273     *
274     * @throws ClassCastException if the key is of an inappropriate type for
275     *         this map (optional).
276     * @throws NullPointerException key is <tt>null</tt> and this map does not
277     *         not permit <tt>null</tt> keys (optional).
278     *
279     * @see #containsKey(Object)
280     */
281    public V get(final Object key) {
282        for (int i = this.composite.length - 1; i >= 0; --i) {
283            if (this.composite[i].containsKey(key)) {
284                return this.composite[i].get(key);
285            }
286        }
287        return null;
288    }
289
290    /**
291     * Returns <tt>true</tt> if this map contains no key-value mappings.
292     *
293     * @return <tt>true</tt> if this map contains no key-value mappings.
294     */
295    public boolean isEmpty() {
296        for (int i = this.composite.length - 1; i >= 0; --i) {
297            if (!this.composite[i].isEmpty()) {
298                return false;
299            }
300        }
301        return true;
302    }
303
304    /**
305     * Returns a set view of the keys contained in this map.  The set is
306     * backed by the map, so changes to the map are reflected in the set, and
307     * vice-versa.  If the map is modified while an iteration over the set is
308     * in progress, the results of the iteration are undefined.  The set
309     * supports element removal, which removes the corresponding mapping from
310     * the map, via the <tt>Iterator.remove</tt>, <tt>Set.remove</tt>,
311     * <tt>removeAll</tt> <tt>retainAll</tt>, and <tt>clear</tt> operations.
312     * It does not support the add or <tt>addAll</tt> operations.
313     * <p>
314     * This implementation returns a <code>CompositeSet</code> which
315     * composites the key sets from all of the composited maps.
316     *
317     * @return a set view of the keys contained in this map.
318     */
319    public Set<K> keySet() {
320        final CompositeSet<K> keys = new CompositeSet<K>();
321        for (int i = this.composite.length - 1; i >= 0; --i) {
322            keys.addComposited(this.composite[i].keySet());
323        }
324        return keys;
325    }
326
327    /**
328     * Associates the specified value with the specified key in this map
329     * (optional operation).  If the map previously contained a mapping for
330     * this key, the old value is replaced by the specified value.  (A map
331     * <tt>m</tt> is said to contain a mapping for a key <tt>k</tt> if and only
332     * if {@link #containsKey(Object) m.containsKey(k)} would return
333     * <tt>true</tt>.))
334     *
335     * @param key key with which the specified value is to be associated.
336     * @param value value to be associated with the specified key.
337     * @return previous value associated with specified key, or <tt>null</tt>
338     *         if there was no mapping for key.  A <tt>null</tt> return can
339     *         also indicate that the map previously associated <tt>null</tt>
340     *         with the specified key, if the implementation supports
341     *         <tt>null</tt> values.
342     *
343     * @throws UnsupportedOperationException if no MapMutator has been specified
344     * @throws ClassCastException if the class of the specified key or value
345     *            prevents it from being stored in this map.
346     * @throws IllegalArgumentException if some aspect of this key or value
347     *            prevents it from being stored in this map.
348     * @throws NullPointerException this map does not permit <tt>null</tt>
349     *            keys or values, and the specified key or value is
350     *            <tt>null</tt>.
351     */
352    public V put(final K key, final V value) {
353        if (this.mutator == null) {
354            throw new UnsupportedOperationException("No mutator specified");
355        }
356        return this.mutator.put(this, this.composite, key, value);
357    }
358
359    /**
360     * Copies all of the mappings from the specified map to this map
361     * (optional operation).  The effect of this call is equivalent to that
362     * of calling {@link #put(Object,Object) put(k, v)} on this map once
363     * for each mapping from key <tt>k</tt> to value <tt>v</tt> in the
364     * specified map.  The behavior of this operation is unspecified if the
365     * specified map is modified while the operation is in progress.
366     *
367     * @param map Mappings to be stored in this map.
368     *
369     * @throws UnsupportedOperationException if the <tt>putAll</tt> method is
370     *         not supported by this map.
371     *
372     * @throws ClassCastException if the class of a key or value in the
373     *         specified map prevents it from being stored in this map.
374     *
375     * @throws IllegalArgumentException some aspect of a key or value in the
376     *         specified map prevents it from being stored in this map.
377     * @throws NullPointerException the specified map is <tt>null</tt>, or if
378     *         this map does not permit <tt>null</tt> keys or values, and the
379     *         specified map contains <tt>null</tt> keys or values.
380     */
381    public void putAll(final Map<? extends K, ? extends V> map) {
382        if (this.mutator == null) {
383            throw new UnsupportedOperationException("No mutator specified");
384        }
385        this.mutator.putAll(this, this.composite, map);
386    }
387
388    /**
389     * Removes the mapping for this key from this map if it is present
390     * (optional operation).   More formally, if this map contains a mapping
391     * from key <tt>k</tt> to value <tt>v</tt> such that
392     * <code>(key==null ?  k==null : key.equals(k))</code>, that mapping
393     * is removed.  (The map can contain at most one such mapping.)
394     *
395     * <p>Returns the value to which the map previously associated the key, or
396     * <tt>null</tt> if the map contained no mapping for this key.  (A
397     * <tt>null</tt> return can also indicate that the map previously
398     * associated <tt>null</tt> with the specified key if the implementation
399     * supports <tt>null</tt> values.)  The map will not contain a mapping for
400     * the specified  key once the call returns.
401     *
402     * @param key key whose mapping is to be removed from the map.
403     * @return previous value associated with specified key, or <tt>null</tt>
404     *         if there was no mapping for key.
405     *
406     * @throws ClassCastException if the key is of an inappropriate type for
407     *         the composited map (optional).
408     * @throws NullPointerException if the key is <tt>null</tt> and the composited map
409     *            does not not permit <tt>null</tt> keys (optional).
410     * @throws UnsupportedOperationException if the <tt>remove</tt> method is
411     *         not supported by the composited map containing the key
412     */
413    public V remove(final Object key) {
414        for (int i = this.composite.length - 1; i >= 0; --i) {
415            if (this.composite[i].containsKey(key)) {
416                return this.composite[i].remove(key);
417            }
418        }
419        return null;
420    }
421
422    /**
423     * Returns the number of key-value mappings in this map.  If the
424     * map contains more than <tt>Integer.MAX_VALUE</tt> elements, returns
425     * <tt>Integer.MAX_VALUE</tt>.
426     *
427     * @return the number of key-value mappings in this map.
428     */
429    public int size() {
430        int size = 0;
431        for (int i = this.composite.length - 1; i >= 0; --i) {
432            size += this.composite[i].size();
433        }
434        return size;
435    }
436
437    /**
438     * Returns a collection view of the values contained in this map.  The
439     * collection is backed by the map, so changes to the map are reflected in
440     * the collection, and vice-versa.  If the map is modified while an
441     * iteration over the collection is in progress, the results of the
442     * iteration are undefined.  The collection supports element removal,
443     * which removes the corresponding mapping from the map, via the
444     * <tt>Iterator.remove</tt>, <tt>Collection.remove</tt>,
445     * <tt>removeAll</tt>, <tt>retainAll</tt> and <tt>clear</tt> operations.
446     * It does not support the add or <tt>addAll</tt> operations.
447     *
448     * @return a collection view of the values contained in this map.
449     */
450    public Collection<V> values() {
451        final CompositeCollection<V> values = new CompositeCollection<V>();
452        for (int i = composite.length - 1; i >= 0; --i) {
453            values.addComposited(composite[i].values());
454        }
455        return values;
456    }
457
458    /**
459     * Checks if this Map equals another as per the Map specification.
460     *
461     * @param obj  the object to compare to
462     * @return true if the maps are equal
463     */
464    @Override
465    public boolean equals(final Object obj) {
466        if (obj instanceof Map) {
467            final Map<?, ?> map = (Map<?, ?>) obj;
468            return this.entrySet().equals(map.entrySet());
469        }
470        return false;
471    }
472
473    /**
474     * Gets a hash code for the Map as per the Map specification.
475     * {@inheritDoc}
476     */
477    @Override
478    public int hashCode() {
479        int code = 0;
480        for (final Map.Entry<K, V> entry : entrySet()) {
481            code += entry.hashCode();
482        }
483        return code;
484    }
485
486    /**
487     * This interface allows definition for all of the indeterminate
488     * mutators in a CompositeMap, as well as providing a hook for
489     * callbacks on key collisions.
490     */
491    public static interface MapMutator<K, V> extends Serializable {
492        /**
493         * Called when adding a new Composited Map results in a
494         * key collision.
495         *
496         * @param composite  the CompositeMap with the collision
497         * @param existing  the Map already in the composite which contains the
498         *        offending key
499         * @param added  the Map being added
500         * @param intersect  the intersection of the keysets of the existing and added maps
501         */
502        void resolveCollision(CompositeMap<K, V> composite, Map<K, V> existing,
503                Map<K, V> added, Collection<K> intersect);
504
505        /**
506         * Called when the CompositeMap.put() method is invoked.
507         *
508         * @param map  the CompositeMap which is being modified
509         * @param composited  array of Maps in the CompositeMap being modified
510         * @param key  key with which the specified value is to be associated.
511         * @param value  value to be associated with the specified key.
512         * @return previous value associated with specified key, or <tt>null</tt>
513         *         if there was no mapping for key.  A <tt>null</tt> return can
514         *         also indicate that the map previously associated <tt>null</tt>
515         *         with the specified key, if the implementation supports
516         *         <tt>null</tt> values.
517         *
518         * @throws UnsupportedOperationException if not defined
519         * @throws ClassCastException if the class of the specified key or value
520         *            prevents it from being stored in this map.
521         * @throws IllegalArgumentException if some aspect of this key or value
522         *            prevents it from being stored in this map.
523         * @throws NullPointerException this map does not permit <tt>null</tt>
524         *            keys or values, and the specified key or value is
525         *            <tt>null</tt>.
526         */
527        V put(CompositeMap<K, V> map, Map<K, V>[] composited, K key, V value);
528
529        /**
530         * Called when the CompositeMap.putAll() method is invoked.
531         *
532         * @param map  the CompositeMap which is being modified
533         * @param composited  array of Maps in the CompositeMap being modified
534         * @param mapToAdd  Mappings to be stored in this CompositeMap
535         *
536         * @throws UnsupportedOperationException if not defined
537         * @throws ClassCastException if the class of the specified key or value
538         *            prevents it from being stored in this map.
539         * @throws IllegalArgumentException if some aspect of this key or value
540         *            prevents it from being stored in this map.
541         * @throws NullPointerException this map does not permit <tt>null</tt>
542         *            keys or values, and the specified key or value is
543         *            <tt>null</tt>.
544         */
545        void putAll(CompositeMap<K, V> map, Map<K, V>[] composited,
546                Map<? extends K, ? extends V> mapToAdd);
547    }
548}