001 /*
002 NGramJ - n-gram based text classification
003 Copyright (C) 2001 Frank S. Nestel (frank at spieleck.de)
004
005 This program is free software; you can redistribute it and/or modify
006 it under the terms of the GNU Lesser General Public License as published
007 by the Free Software Foundation; either version 2.1 of the License, or
008 (at your option) any later version.
009
010 This program is distributed in the hope that it will be useful,
011 but WITHOUT ANY WARRANTY; without even the implied warranty of
012 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
013 GNU General Public License for more details.
014
015 You should have received a copy of the GNU Lesser General Public License
016 along with this program (lesser.txt); if not, write to the Free Software
017 Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
018 */
019
020 package de.spieleck.util;
021
022 import java.lang.StringBuffer;
023 import java.util.Enumeration;
024 import java.util.Iterator;
025
026 /**
027 * The IntMap provides a simple hashmap from keys to integers.
028 * The API is simplified of the HashMap/Hashtable collection API.
029 * Additionally there are call to do simple arithmetic with entries
030 * in the map.
031 *
032 * <p>The convenience of IntMap is avoiding all wrapping of integers.
033 * </p>
034 * <B>Note:</B> This class is completely unsynchronized for speed!
035 */
036 public class IntMap
037 {
038 /**
039 * Encoding of a null entry. Since NULL is equal to Integer.MIN_VALUE,
040 * it's impossible to distinguish between the two.
041 */
042 public final static int NULL = Integer.MIN_VALUE;
043
044 protected Object [] keys;
045 protected int nullValue;
046 protected int []values;
047 protected int size;
048 protected int mask;
049 protected int limit;
050
051 /**
052 * Create a new IntMap. Default size is 16.
053 */
054 public IntMap()
055 {
056 this(16);
057 }
058
059 public IntMap(int size)
060 {
061 this(size, NULL);
062 }
063
064 public IntMap(int size, int nullValue)
065 {
066 if ( size < 8 )
067 size = 8;
068 int z = 0;
069 while ( size > 1 )
070 {
071 z++;
072 size /= 2;
073 }
074 size = 2 << z;
075 keys = new Object[size];
076 values = new int[size];
077
078 mask = keys.length - 1;
079 limit = 3 * keys.length / 4;
080 size = 0;
081 this.nullValue = nullValue;
082 }
083
084 /**
085 *
086 */
087 public int getNullValue()
088 {
089 return nullValue;
090 }
091
092 /**
093 * This only works with binary indizes
094 */
095 protected int firstIndex(Object key)
096 {
097 return key.hashCode() & mask;
098 }
099
100 protected int nextIndex(int index)
101 {
102 return (index + 5) & mask;
103 }
104
105 /**
106 * Clear the hashmap.
107 * XXX Or should we let the GC the work an use keys = new Object[..]???
108 */
109 public void clear()
110 {
111 for (int i = 0; i < values.length; i++)
112 keys[i] = null;
113 size = 0;
114 }
115
116 /**
117 * Returns the current number of entries in the map.
118 */
119 public int size()
120 {
121 return size;
122 }
123
124 /**
125 * Get an Element
126 */
127 public int getElement(Object key)
128 {
129 return get(key);
130 }
131
132 /**
133 * Get an Element
134 */
135 public int get(Object key)
136 {
137 if ( key == null )
138 return nullValue;
139 for (int i = firstIndex(key); keys[i] != null; i = nextIndex(i))
140 {
141 if ( keys[i] == key || key.equals(keys[i]) )
142 return values[i];
143 }
144 return nullValue;
145 }
146
147 /**
148 * Optimized operations.
149 * avoid get change put cycles.
150 */
151 public int inc(Object key)
152 {
153 return add(key, 1);
154 }
155
156 /**
157 * Optimized operations.
158 * avoid get change put cycles.
159 */
160 public int dec(Object key)
161 {
162 return add(key, -1);
163 }
164
165 /**
166 * Optimized operations.
167 * avoid get change put cycles.
168 */
169 public int add(Object key, int off)
170 {
171 if ( key == null )
172 return nullValue;
173 int i;
174 for (i = firstIndex(key); keys[i] != null; i = nextIndex(i))
175 {
176 if ( keys[i] == key || key.equals(keys[i]) )
177 {
178 values[i] += off;
179 return values[i];
180 }
181 }
182 return nullValue;
183 }
184
185
186 /**
187 * Expands the table
188 */
189 protected void grow()
190 {
191 int newSize = 2 * keys.length;
192 Object[] oldKeys = keys;
193 int[] oldValues = values;
194 //
195 keys = new Object[newSize];
196 values = new int[newSize];
197 mask = newSize - 1;
198 size = 0; // We recound the size below!
199 for (int i = 0; i < oldKeys.length; i++)
200 if (oldKeys[i] != null)
201 internalPut(oldKeys[i], oldValues[i]);
202 limit = 3 * newSize / 4;
203 }
204
205 /**
206 * Puts a new value in the property table with the appropriate flags
207 */
208 public int putElement(Object key, int value)
209 {
210 return put(key, value);
211 }
212
213 public int put(Object key, int value)
214 {
215 if (key == null)
216 return nullValue;
217 if ( size >= limit )
218 grow();
219 return internalPut(key, value);
220 }
221
222 protected int internalPut(Object key, int value)
223 {
224 for(int i = firstIndex(key); true; i = nextIndex(i))
225 {
226 Object testKey = keys[i];
227 if ( testKey == null )
228 {
229 keys[i] = key;
230 values[i] = value;
231 size++;
232 return nullValue;
233 }
234 else if ( key == testKey || testKey.equals(key))
235 {
236 int old = values[i];
237 values[i] = value;
238 return old;
239 }
240 }
241 }
242
243 /**
244 * Deletes the entry.
245 */
246 public int remove(Object key)
247 {
248 if (key == null || size == 0)
249 return nullValue;
250
251 int i;
252 for (i = firstIndex(key); keys[i] != null; i = nextIndex(i))
253 {
254 Object testKey = keys[i];
255 if (key == testKey || key.equals(testKey) )
256 {
257 int value = values[i];
258 do
259 {
260 keys[i] = null;
261 int j = i;
262 int r;
263 do
264 {
265 i = nextIndex(i);
266 if (keys[i] == null)
267 break;
268 r = firstIndex(keys[i]);
269 }
270 while ( (i <= r && r < j)
271 || (r < j && j < i)
272 || (j < i && i <= r)
273 );
274 keys[j] = keys[i];
275 values[j] = values[i];
276 }
277 while (keys[i] != null);
278 --size;
279 return value;
280 }
281 }
282 return nullValue;
283 }
284
285 public Enumeration keys()
286 {
287 return new IntMapEnumeration();
288 }
289
290 public Iterator iterator()
291 {
292 return new IntMapIterator();
293 }
294
295 public String toString()
296 {
297 StringBuffer sbuf = new StringBuffer();
298 sbuf.append("IntMap[");
299 boolean isFirst = true;
300 for (int i = 0; i < keys.length; i++)
301 {
302 if (keys[i] != null)
303 {
304 if (! isFirst)
305 sbuf.append(", ");
306 isFirst = false;
307 sbuf.append(keys[i]);
308 sbuf.append(":");
309 sbuf.append(values[i]);
310 }
311 }
312 sbuf.append("]");
313 return sbuf.toString();
314 }
315
316 private class IntMapEnumeration
317 implements Enumeration
318 {
319 protected int index = 0;
320
321 public boolean hasMoreElements()
322 {
323 for (; index < keys.length; index++)
324 if (keys[index] != null )
325 return true;
326 return false;
327 }
328
329 public Object nextElement()
330 {
331 for (; index < keys.length; index++)
332 if (keys[index] != null )
333 return keys[index++];
334 return null;
335 }
336 }
337
338 private class IntMapIterator
339 implements Iterator
340 {
341 protected int index = 0;
342
343 public boolean hasNext()
344 {
345 for (; index < keys.length; index++)
346 if (keys[index] != null )
347 return true;
348 return false;
349 }
350
351 public Object next()
352 {
353 for (; index < keys.length; index++)
354 if (keys[index] != null )
355 return keys[index++];
356 return null;
357 }
358
359 public void remove()
360 {
361 throw new java.lang.UnsupportedOperationException(
362 "IntMapIterator.remove()");
363 }
364 }
365
366 }
367