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 }