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