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 }