001/*-------------------------------------------------------------------------+
002|                                                                          |
003| Copyright 2005-2011 The ConQAT Project                                   |
004|                                                                          |
005| Licensed under the Apache License, Version 2.0 (the "License");          |
006| you may not use this file except in compliance with the License.         |
007| 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.conqat.lib.commons.collections;
018
019import java.util.Collection;
020import java.util.HashMap;
021import java.util.HashSet;
022import java.util.Map;
023import java.util.Set;
024
025/**
026 * A map implementation based on unsorted arrays. This is by far more memory
027 * efficient than the usual map implementations and has reasonable performance
028 * for small maps. Note that this map violates the map interface by just
029 * returning copies for the set accessor methods ({@link #entrySet()},
030 * {@link #values()}, {@link #keySet()}), i.e. they are not backed by the map.
031 * <p>
032 * Implementation hints:
033 * <ul>
034 * <li>Nearly all operations require a full traversal of the array (resp.
035 * PairList).</li>
036 * <li>Iteration is performed backwards, to avoid frequent calls to size()
037 * method. This also gives more efficient access to recently added
038 * 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 */
044public class ArrayBackedMap<K, V> implements Map<K, V> {
045
046        /** The underlying list used for storing the entries. */
047        private final PairList<K, V> list;
048
049        /** Constructs a new map with an initial capacity of 4. */
050        public ArrayBackedMap() {
051                this(4);
052        }
053
054        /** Constructor. */
055        public ArrayBackedMap(int initialCapacity) {
056                list = new PairList<K, V>(initialCapacity);
057        }
058
059        /** Copy constructor. */
060        public ArrayBackedMap(ArrayBackedMap<K, V> other) {
061                list = new PairList<K, V>(other.list);
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                                        
157                                        // explicitly set to null, to allow GC
158                                        list.setFirst(last, null);
159                                        list.setSecond(last, null);
160                                        list.removeLast();
161
162                                        return oldValue;
163                                }
164                        }
165                        return null;
166                } catch (ClassCastException e) {
167                        return null;
168                }
169        }
170
171        /** {@inheritDoc} */
172        @Override
173        public boolean containsValue(Object value) {
174                for (int i = list.size() - 1; i >= 0; --i) {
175
176                        // can not use areEqual(), as we work on values and not keys here.
177                        if (value == null) {
178                                if (list.getSecond(i) == null) {
179                                        return true;
180                                }
181                        } else {
182                                if (value.equals(list.getSecond(i))) {
183                                        return true;
184                                }
185                        }
186                }
187                return false;
188        }
189
190        /** {@inheritDoc} */
191        @Override
192        public Set<java.util.Map.Entry<K, V>> entrySet() {
193                Map<K, V> map = new HashMap<K, V>();
194                for (int i = list.size() - 1; i >= 0; --i) {
195                        map.put(list.getFirst(i), list.getSecond(i));
196                }
197                return map.entrySet();
198        }
199
200        /** {@inheritDoc} */
201        @Override
202        public boolean isEmpty() {
203                return list.isEmpty();
204        }
205
206        /** {@inheritDoc} */
207        @Override
208        public Set<K> keySet() {
209                return new HashSet<K>(list.extractFirstList());
210        }
211
212        /** {@inheritDoc} */
213        @Override
214        public void putAll(Map<? extends K, ? extends V> m) {
215                for (Entry<? extends K, ? extends V> e : m.entrySet()) {
216                        put(e.getKey(), e.getValue());
217                }
218        }
219
220        /** {@inheritDoc} */
221        @Override
222        public int size() {
223                return list.size();
224        }
225
226        /** {@inheritDoc} */
227        @Override
228        public Collection<V> values() {
229                return list.extractSecondList();
230        }
231
232        /** {@inheritDoc} */
233        @Override
234        public String toString() {
235                return list.toString();
236        }
237
238        /** {@inheritDoc} */
239        @Override
240        public int hashCode() {
241                return list.hashCode();
242        }
243
244        /** {@inheritDoc} */
245        @Override
246        public boolean equals(Object obj) {
247                if (this == obj) {
248                        return true;
249                }
250                if (!(obj instanceof ArrayBackedMap)) {
251                        return false;
252                }
253                return list.equals(((ArrayBackedMap<?, ?>) obj).list);
254        }
255
256}