001    /*--------------------------------------------------------------------------+
002    $Id: ArrayBackedMap.java 28496 2010-06-22 09:26:50Z deissenb $
003    |                                                                          |
004    | Copyright 2005-2010 Technische Universitaet Muenchen                     |
005    |                                                                          |
006    | Licensed under the Apache License, Version 2.0 (the "License");          |
007    | you may not use this file except in compliance with the License.         |
008    | You may obtain a copy of the License at                                  |
009    |                                                                          |
010    |    http://www.apache.org/licenses/LICENSE-2.0                            |
011    |                                                                          |
012    | Unless required by applicable law or agreed to in writing, software      |
013    | distributed under the License is distributed on an "AS IS" BASIS,        |
014    | WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
015    | See the License for the specific language governing permissions and      |
016    | limitations under the License.                                           |
017    +--------------------------------------------------------------------------*/
018    package edu.tum.cs.commons.collections;
019    
020    import java.util.Collection;
021    import java.util.HashMap;
022    import java.util.HashSet;
023    import java.util.Map;
024    import java.util.Set;
025    
026    /**
027     * A map implementation based on unsorted arrays. This is by far more memory
028     * efficient than the usual map implementations and has reasonable performance
029     * for small maps. Note that this map violates the map interface by just
030     * returning copies for the set accessor methods ({@link #entrySet()},
031     * {@link #values()}, {@link #keySet()}), i.e. they are not backed by the map.
032     * <p>
033     * Implementation hints:
034     * <ul>
035     * <li>Nearly all operations require a full traversal of the array (resp.
036     * PairList).</li>
037     * <li>Iteration is performed backwards, to avoid frequent calls to size()
038     * method. This also gives more efficient access to recently added elements.</li>
039     * <li>This class is prepared to support subclasses with more specific keys with
040     * more efficient key handling. Thus all keys inserted are preprocessed and
041     * comparison of keys can be overwritten.</li>
042     * </ul>
043     * 
044     * @author hummelb
045     * @author $Author: deissenb $
046     * @version $Rev: 28496 $
047     * @levd.rating GREEN Hash: FD4724FBA572E6336FD0EE8890B9CD58
048     */
049    public class ArrayBackedMap<K, V> implements Map<K, V> {
050    
051            /** The underlying list used for storing the entries. */
052            private final PairList<K, V> list;
053    
054            /** Constructs a new map with an initial capacity of 4. */
055            public ArrayBackedMap() {
056                    this(4);
057            }
058    
059            /** Constructor. */
060            public ArrayBackedMap(int initialCapacity) {
061                    list = new PairList<K, V>(initialCapacity);
062            }
063    
064            /** {@inheritDoc} */
065            @Override
066            public void clear() {
067                    list.clear();
068            }
069    
070            /** {@inheritDoc} */
071            @Override
072            public boolean containsKey(Object key) {
073                    try {
074                            K cleanKey = internKey(key);
075                            for (int i = list.size() - 1; i >= 0; --i) {
076                                    if (areEqual(cleanKey, list.getFirst(i))) {
077                                            return true;
078                                    }
079                            }
080                            return false;
081                    } catch (ClassCastException e) {
082                            return false;
083                    }
084            }
085    
086            /**
087             * Template method for calculating an internal key representation. The
088             * default implementation just performs a cast. This method may throw a
089             * class cast exception if the provided key is not an instance of the key
090             * type.
091             * 
092             * @throws ClassCastException
093             *             if the provided key is not of a suitable class.
094             */
095            @SuppressWarnings("unchecked")
096            protected K internKey(Object key) throws ClassCastException {
097                    return (K) key;
098            }
099    
100            /** Template method for comparing two keys for equality. */
101            protected boolean areEqual(K key1, K key2) {
102                    if (key1 == null) {
103                            return key2 == null;
104                    }
105                    return key1.equals(key2);
106            }
107    
108            /** {@inheritDoc} */
109            @Override
110            public V get(Object key) {
111                    try {
112                            K cleanKey = internKey(key);
113                            for (int i = list.size() - 1; i >= 0; --i) {
114                                    if (areEqual(cleanKey, list.getFirst(i))) {
115                                            return list.getSecond(i);
116                                    }
117                            }
118                            return null;
119                    } catch (ClassCastException e) {
120                            return null;
121                    }
122            }
123    
124            /** {@inheritDoc} */
125            @Override
126            public V put(K key, V value) {
127                    // no catch clause here, as key must be of correct type (interface
128                    // contract)
129                    K cleanKey = internKey(key);
130    
131                    for (int i = list.size() - 1; i >= 0; --i) {
132                            if (areEqual(cleanKey, list.getFirst(i))) {
133                                    V oldValue = list.getSecond(i);
134                                    list.setSecond(i, value);
135                                    return oldValue;
136                            }
137                    }
138    
139                    list.add(cleanKey, value);
140                    return null;
141            }
142    
143            /** {@inheritDoc} */
144            @Override
145            public V remove(Object key) {
146                    try {
147                            K cleanKey = internKey(key);
148                            for (int i = list.size() - 1; i >= 0; --i) {
149                                    if (areEqual(cleanKey, list.getFirst(i))) {
150                                            V oldValue = list.getSecond(i);
151                                            int last = list.size() - 1;
152                                            if (i != last) {
153                                                    list.setFirst(i, list.getFirst(last));
154                                                    list.setSecond(i, list.getSecond(last));
155                                            }
156                                            list.removeLast();
157                                            return oldValue;
158                                    }
159                            }
160                            return null;
161                    } catch (ClassCastException e) {
162                            return null;
163                    }
164            }
165    
166            /** {@inheritDoc} */
167            @Override
168            public boolean containsValue(Object value) {
169                    for (int i = list.size() - 1; i >= 0; --i) {
170    
171                            // can not use areEqual(), as we work on values and not keys here.
172                            if (value == null) {
173                                    if (list.getSecond(i) == null) {
174                                            return true;
175                                    }
176                            } else {
177                                    if (value.equals(list.getSecond(i))) {
178                                            return true;
179                                    }
180                            }
181                    }
182                    return false;
183            }
184    
185            /** {@inheritDoc} */
186            @Override
187            public Set<java.util.Map.Entry<K, V>> entrySet() {
188                    Map<K, V> map = new HashMap<K, V>();
189                    for (int i = list.size() - 1; i >= 0; --i) {
190                            map.put(list.getFirst(i), list.getSecond(i));
191                    }
192                    return map.entrySet();
193            }
194    
195            /** {@inheritDoc} */
196            @Override
197            public boolean isEmpty() {
198                    return list.isEmpty();
199            }
200    
201            /** {@inheritDoc} */
202            @Override
203            public Set<K> keySet() {
204                    return new HashSet<K>(list.extractFirstList());
205            }
206    
207            /** {@inheritDoc} */
208            @Override
209            public void putAll(Map<? extends K, ? extends V> m) {
210                    for (Entry<? extends K, ? extends V> e : m.entrySet()) {
211                            put(e.getKey(), e.getValue());
212                    }
213            }
214    
215            /** {@inheritDoc} */
216            @Override
217            public int size() {
218                    return list.size();
219            }
220    
221            /** {@inheritDoc} */
222            @Override
223            public Collection<V> values() {
224                    return list.extractSecondList();
225            }
226    
227    }