001/* 002 * BioJava development code 003 * 004 * This code may be freely distributed and modified under the 005 * terms of the GNU Lesser General Public Licence. This should 006 * be distributed with the code. If you do not have a copy, 007 * see: 008 * 009 * http://www.gnu.org/copyleft/lesser.html 010 * 011 * Copyright for this code is held jointly by the individual 012 * authors. These should be listed in @author doc comments. 013 * 014 * For more information on the BioJava project and its aims, 015 * or to join the biojava-l mailing list, visit the home page 016 * at: 017 * 018 * http://www.biojava.org/ 019 * 020 */ 021package org.biojava.nbio.ontology.utils; 022 023import java.io.Serializable; 024import java.util.*; 025 026/** 027 * Lightweight implementation of Map which uses little memory to store a 028 * small number of mappings, at the expense of scalability. Not recommended 029 * for more than 20-30 mappings. 030 * 031 * <p> 032 * This implementation has the useful property that the iteration order is 033 * the same as the order in which mappings are added. 034 * </p> 035 * 036 * @author Thomas Down 037 * @author Len Trigg 038 */ 039 040public class SmallMap extends AbstractMap implements Serializable { 041 private Object[] mappings = null; 042 private int numMappings = 0; 043 044 public SmallMap() { 045 super(); 046 } 047 048 public SmallMap(int size) { 049 super(); 050 mappings = new Object[size * 2]; 051 } 052 053 public SmallMap(Map m) { 054 this(m.size()); 055 for (Iterator i = m.entrySet().iterator(); i.hasNext(); ) { 056 Map.Entry me = (Map.Entry) i.next(); 057 put(me.getKey(), me.getValue()); 058 } 059 } 060 061 /** 062 * @throws NullPointerException if key is null 063 */ 064 @Override 065 public Object get(Object key) { 066 // Doesn't actually need to check if mappings is null, since numMappings 067 // will necessarily be zero. 068 069 int keyHash = key.hashCode(); 070 for (int i = 0; i < numMappings * 2; i += 2) { 071 if (keyHash == mappings[i].hashCode() && key.equals(mappings[i])) { 072 return mappings[i + 1]; 073 } 074 } 075 return null; 076 } 077 078 /** 079 * @throws NullPointerException if key is null 080 */ 081 @Override 082 public Object put(Object key, Object value) { 083 int keyHash = key.hashCode(); 084 085 for (int i = 0; i < numMappings * 2; i += 2) { 086 if (keyHash == mappings[i].hashCode() && key.equals(mappings[i])) { 087 Object oldValue = mappings[i+1]; 088 mappings[i+1] = value; 089 return oldValue; 090 } 091 } 092 093 int newPos = numMappings * 2; 094 int oldLength = 0; 095 if (mappings != null) { 096 oldLength = mappings.length; 097 } 098 if (newPos + 1 >= oldLength) { 099 Object[] newMappings = new Object[oldLength + 6]; 100 if (oldLength > 0) { 101 System.arraycopy(mappings, 0, newMappings, 0, mappings.length); 102 } 103 mappings = newMappings; 104 } 105 106 mappings[newPos] = key; 107 mappings[newPos + 1] = value; 108 numMappings++; 109 110 return null; 111 } 112 113 @Override 114 public Set keySet() { 115 return new KeySet(); 116 } 117 118 @Override 119 public Set entrySet() { 120 return new EntrySet(); 121 } 122 123 @Override 124 public int size() { 125 return numMappings; 126 } 127 128 @Override 129 public boolean containsKey(Object key) { 130 int keyHash = key.hashCode(); 131 for (int i = 0; i < numMappings * 2; i += 2) { 132 if (keyHash == mappings[i].hashCode() && key.equals(mappings[i])) { 133 return true; 134 } 135 } 136 return false; 137 } 138 139 140 // num ranges from 1 to numMappings 141 private void removeMapping(int num) { 142 if (num < numMappings) { 143 System.arraycopy(mappings, num * 2, mappings, (num - 1) * 2, (numMappings - num) * 2); 144 } 145 mappings[numMappings * 2 - 1] = null; 146 mappings[numMappings * 2 - 2] = null; 147 numMappings--; 148 } 149 150 private class KeySet extends AbstractSet { 151 @Override 152 public Iterator iterator() { 153 return new KeyIterator(); 154 } 155 156 @Override 157 public int size() { 158 return numMappings; 159 } 160 } 161 162 private class KeyIterator implements Iterator { 163 int pos = 0; 164 165 @Override 166 public boolean hasNext() { 167 return pos < numMappings; 168 } 169 170 @Override 171 public Object next() { 172 if (pos >= numMappings) { 173 throw new NoSuchElementException(); 174 } 175 int offset = pos * 2; 176 ++pos; 177 return mappings[offset]; 178 } 179 180 @Override 181 public void remove() { 182 removeMapping(pos); 183 pos -= 1; 184 } 185 } 186 187 private class EntrySet extends AbstractSet { 188 @Override 189 public Iterator iterator() { 190 return new EntryIterator(); 191 } 192 193 @Override 194 public int size() { 195 return numMappings; 196 } 197 } 198 199 private class EntryIterator implements Iterator { 200 int pos = 0; 201 202 @Override 203 public boolean hasNext() { 204 return pos < numMappings; 205 } 206 207 @Override 208 public Object next() { 209 if (pos >= numMappings) { 210 throw new NoSuchElementException(); 211 } 212 int offset = pos * 2; 213 ++pos; 214 return new MapEntry(offset); 215 } 216 217 @Override 218 public void remove() { 219 removeMapping(pos); 220 pos -= 1; 221 } 222 } 223 224 private class MapEntry implements Map.Entry { 225 private int offset; 226 227 private MapEntry(int offset) { 228 this.offset = offset; 229 } 230 231 @Override 232 public Object getKey() { 233 return mappings[offset]; 234 } 235 236 @Override 237 public Object getValue() { 238 return mappings[offset + 1]; 239 } 240 241 @Override 242 public Object setValue(Object v) { 243 Object oldValue = mappings[offset + 1]; 244 mappings[offset + 1] = v; 245 return oldValue; 246 } 247 248 @Override 249 public boolean equals(Object o) { 250 if (! (o instanceof Map.Entry)) { 251 return false; 252 } 253 254 Map.Entry mo = (Map.Entry) o; 255 return ((getKey() == null ? mo.getKey() == null : getKey().equals(mo.getKey())) && 256 (getValue() == null ? mo.getValue() == null : getValue().equals(mo.getValue()))); 257 } 258 259 @Override 260 public int hashCode() { 261 return (getKey() == null ? 0 : getKey().hashCode()) ^ (getValue() == null ? 0 : getValue().hashCode()); 262 } 263 } 264}