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