IntMap


1   /*
2    * Copyright (c) 1998-2006 Caucho Technology -- all rights reserved
3    *
4    * This file is part of Resin(R) Open Source
5    *
6    * Each copy or derived work must preserve the copyright notice and this
7    * notice unmodified.
8    *
9    * Resin Open Source is free software; you can redistribute it and/or modify
10   * it under the terms of the GNU General Public License as published by
11   * the Free Software Foundation; either version 2 of the License, or
12   * (at your option) any later version.
13   *
14   * Resin Open Source is distributed in the hope that it will be useful,
15   * but WITHOUT ANY WARRANTY; without even the implied warranty of
16   * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE, or any warranty
17   * of NON-INFRINGEMENT.  See the GNU General Public License for more
18   * details.
19   *
20   * You should have received a copy of the GNU General Public License
21   * along with Resin Open Source; if not, write to the
22   *   Free SoftwareFoundation, Inc.
23   *   59 Temple Place, Suite 330
24   *   Boston, MA 02111-1307  USA
25   *
26   * @author Scott Ferguson
27   */
28  
29  package com.caucho.util;
30  
31  import java.util.Iterator  ;
32  /**
33   * The IntMap provides a simple hashmap from keys to integers.  The API is
34   * an abbreviation of the HashMap collection API.
35   *
36   * <p>The convenience of IntMap is avoiding all the silly wrapping of
37   * integers.
38   */
39  public class IntMap {
40    /**
41     * Encoding of a null entry.  Since NULL is equal to Integer.MIN_VALUE, 
42     * it's impossible to distinguish between the two.
43     */
44    public final static int NULL = -65536; // Integer.MIN_VALUE + 1;
45    private static int DELETED = 0x1;
46    private Object   []_keys;
47    private int _nullValue;
48    private int []_values;
49    private int _size;
50    private int _mask;
51  
52    /**
53     * Create a new IntMap.  Default size is 16.
54     */
55    public IntMap()
56    {
57      _keys = new Object  [16];
58      _values = new int[16];
59  
60      _mask = _keys.length - 1;
61      _size = 0;
62  
63      _nullValue = NULL;
64    }
65  
66    /**
67     * Create a new IntMap for cloning.
68     */
69    private IntMap(boolean dummy)
70    {
71    }
72  
73    /**
74     * Clear the hashmap.
75     */
76    public void clear()
77    {
78      _nullValue = NULL;
79      for (int i = 0; i < _values.length; i++) {
80        _keys[i] = null;
81        _values[i] = 0;
82      }
83      _size = 0;
84    }
85    /**
86     * Returns the current number of entries in the map.
87     */
88    public int size() 
89    { 
90      return _size;
91    }
92  
93    /**
94     * Puts a new value in the property table with the appropriate flags
95     */
96    public int get(Object   key)
97    {
98      if (key == null)
99        return _nullValue;
100 
101     int hash = key.hashCode() & _mask;
102     Object   []keys = _keys;
103 
104     for (int i = keys.length; i >= 0; i--) {
105       Object   mapKey = keys[hash];
106 
107       if (mapKey == key)
108     return _values[hash];
109       else if (mapKey == null)
110     return NULL;
111       else if (mapKey.equals(key))
112     return _values[hash];
113 
114       hash = (hash + 1) & _mask;
115     }
116 
117     return NULL;
118   }
119 
120   /**
121    * Expands the property table
122    */
123   private void resize(int newSize)
124   {
125     Object   []newKeys = new Object  [newSize];
126     int []newValues = new int[newSize];
127 
128     _mask = newKeys.length - 1;
129 
130     for (int i = 0; i < _keys.length; i++) {
131       if (_keys[i] == null)
132     continue;
133 
134       int hash = _keys[i].hashCode() & _mask;
135 
136       for (int j = _mask; j >= 0; j--) {
137     if (newKeys[hash] == null) {
138       newKeys[hash] = _keys[i];
139       newValues[hash] = _values[i];
140       break;
141     }
142     hash = (hash + 1) & _mask;
143       }
144     }
145 
146     _keys = newKeys;
147     _values = newValues;
148   }
149 
150   /**
151    * Puts a new value in the property table with the appropriate flags
152    */
153   public int put(Object   key, int value)
154   {
155     if (key == null) {
156       int old = _nullValue;
157       _nullValue = value;
158       return old;
159     }
160 
161     int hash = key.hashCode() & _mask;
162 
163     for (int count = _size; count >= 0; count--) {
164       Object   testKey = _keys[hash];
165 
166       if (testKey == null) {
167     _keys[hash] = key;
168     _values[hash] = value;
169 
170     _size++;
171 
172     if (_keys.length <= 4 * _size)
173       resize(4 * _keys.length);
174 
175     return NULL;
176       }
177       else if (key != testKey && ! testKey.equals(key)) {
178     hash = (hash + 1) & _mask;
179     continue;
180       }
181       else {
182     int old = _values[hash];
183 
184     _values[hash] = value;
185 
186     return old;
187       }
188     }
189 
190     return NULL;
191   }
192 
193   /**
194    * Deletes the entry.  Returns true if successful.
195    */
196   public int remove(Object   key)
197   {
198     if (key == null) {
199       int old = _nullValue;
200       _nullValue = NULL;
201       return old;
202     }
203 
204     int hash = key.hashCode() & _mask;
205 
206     for (int j = _size; j >= 0; j--) {
207       Object   mapKey = _keys[hash];
208 
209       if (mapKey == null)
210     return NULL;
211       else if (mapKey.equals(key)) {
212     _size--;
213 
214     _keys[hash] = null;
215 
216     int value = _values[hash];
217 
218     refillEntries(hash);
219 
220     return value;
221       }
222 
223       hash = (hash + 1) & _mask;
224     }
225 
226     return NULL;
227   }
228 
229   /**
230    * Put the item in the best location available in the hash table.
231    */
232   private void refillEntries(int hash)
233   {
234     for (int count = _size; count >= 0; count--) {
235       hash = (hash + 1) & _mask;
236 
237       if (_keys[hash] == null)
238     return;
239 
240       refillEntry(hash);
241     }
242   }
243   
244   /**
245    * Put the item in the best location available in the hash table.
246    */
247   private void refillEntry(int baseHash)
248   {
249     Object   key = _keys[baseHash];
250     int value = _values[baseHash];
251     
252     int hash = key.hashCode();
253     
254     for (int count = _size; count >= 0; count--) {
255       if (_keys[hash] == null) {
256     _keys[hash] = key;
257     _values[hash] = value;
258     return;
259       }
260 
261       hash = (hash + 1) & _mask;
262     }
263   }
264   /**
265    * Returns an iterator of the keys.
266    */
267   public Iterator   iterator()
268   {
269     return new IntMapIterator();
270   }
271 
272   public Object   clone()
273   {
274     IntMap clone = new IntMap(true);
275 
276     clone._keys = new Object  [_keys.length];
277     System.arraycopy(_keys, 0, clone._keys, 0, _keys.length);
278     
279     clone._values = new int[_values.length];
280     System.arraycopy(_values, 0, clone._values, 0, _values.length);
281     
282     clone._mask = _mask;
283     clone._size = _size;
284 
285     clone._nullValue = _nullValue;
286 
287     return clone;
288   }
289 
290   public String   toString()
291   {
292     StringBuffer   sbuf = new StringBuffer  ();
293 
294     sbuf.append("IntMap[");
295     boolean isFirst = true;
296     for (int i = 0; i <= _mask; i++) {
297       if (_keys[i] != null) {
298     if (! isFirst)
299       sbuf.append(", ");
300     isFirst = false;
301     sbuf.append(_keys[i]);
302     sbuf.append(":");
303     sbuf.append(_values[i]);
304       }
305     }
306     sbuf.append("]");
307     return sbuf.toString();
308   }
309 
310   class IntMapIterator implements Iterator   {
311     int index;
312 
313     public boolean hasNext()
314     {
315       for (; index < _keys.length; index++)
316     if (_keys[index] != null)
317       return true;
318 
319       return false;
320     }
321 
322     public Object   next()
323     {
324       for (; index < _keys.length; index++)
325     if (_keys[index] != null)
326       return _keys[index++];
327 
328       return null;
329     }
330 
331     public void remove()
332     {
333       throw new RuntimeException  ();
334     }
335   }
336 }
337
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags