001: package net.sf.saxon.sort;
002:
003: import java.io.Serializable;
004: import java.util.Iterator;
005:
006: /**
007: * A hash table that maps int keys to Object values.
008: *
009: * @author Dave Hale, Landmark Graphics
010: * @author Dominique Devienne
011: * @author Michael Kay: retrofitted to JDK 1.4, added iterator(), modified to disallow null values
012: */
013:
014: public class IntHashMap implements Serializable {
015:
016: /**
017: * Initializes a map with a capacity of 8 and a load factor of 0,25.
018: */
019: public IntHashMap() {
020: this (8, 0.25);
021: }
022:
023: /**
024: * Initializes a map with the given capacity and a load factor of 0,25.
025: *
026: * @param capacity the initial capacity.
027: */
028: public IntHashMap(int capacity) {
029: this (capacity, 0.25);
030: }
031:
032: /**
033: * Constructs a new map with initial capacity, and load factor.
034: * <p/>
035: * The capacity is the number of keys that can be mapped without resizing
036: * the arrays in which keys and values are stored. For efficiency, only
037: * a fraction of the elements in those arrays are used. That fraction is
038: * the specified load factor. The initial length of the arrays equals the
039: * smallest power of two not less than the ratio capacity/factor. The
040: * capacity of the map is increased, as necessary. The maximum number
041: * of keys that can be mapped is 2^30.
042: *
043: * @param capacity the initial capacity.
044: * @param factor the load factor.
045: */
046: public IntHashMap(int capacity, double factor) {
047: _factor = factor;
048: setCapacity(capacity);
049: }
050:
051: /**
052: * Clears the map.
053: */
054: public void clear() {
055: _n = 0;
056: for (int i = 0; i < _nmax; ++i) {
057: //_filled[i] = false;
058: _value[i] = null;
059: }
060: }
061:
062: /**
063: * Finds a key in the map.
064: *
065: * @param key Key
066: * @return true if the key is mapped
067: */
068: // public boolean find(int key) {
069: // return _filled[indexOf(key)] ? true : false;
070: // }
071: /**
072: * Gets the value for this key.
073: *
074: * @param key Key
075: * @return the value, null if not found.
076: */
077: public Object get(int key) {
078: // int i = indexOf(key);
079: // return _filled[i] ? _value[i] : null;
080: return _value[indexOf(key)];
081: }
082:
083: /**
084: * Gets the size of the map.
085: *
086: * @return the size (the number of entries in the map)
087: */
088: public int size() {
089: return _n;
090: }
091:
092: /**
093: * Removes a key from the map.
094: *
095: * @param key Key to remove
096: * @return true if the value was removed
097: */
098: public boolean remove(int key) {
099: // Knuth, v. 3, 527, Algorithm R.
100: int i = indexOf(key);
101: //if (!_filled[i]) {
102: if (_value[i] == null) {
103: return false;
104: }
105: --_n;
106: for (;;) {
107: //_filled[i] = false;
108: _value[i] = null;
109: int j = i;
110: int r;
111: do {
112: i = (i - 1) & _mask;
113: //if (!_filled[i]) {
114: if (_value[i] == null) {
115: return true;
116: }
117: r = hash(_key[i]);
118: } while ((i <= r && r < j) || (r < j && j < i)
119: || (j < i && i <= r));
120: _key[j] = _key[i];
121: _value[j] = _value[i];
122: //_filled[j] = _filled[i];
123: }
124: }
125:
126: /**
127: * Adds a key-value pair to the map.
128: *
129: * @param key Key
130: * @param value Value
131: */
132: public void put(int key, Object value) {
133: if (value == null) {
134: throw new NullPointerException(
135: "IntHashMap does not allow null values");
136: }
137: int i = indexOf(key);
138: //if (_filled[i]) {
139: if (_value[i] != null) {
140: _value[i] = value;
141: } else {
142: _key[i] = key;
143: _value[i] = value;
144: //_filled[i] = true;
145: grow();
146: }
147: }
148:
149: ///////////////////////////////////////////////////////////////////////////
150: // private
151:
152: private static final int NBIT = 30; // NMAX = 2^NBIT
153: private static final int NMAX = 1 << NBIT; // maximum number of keys mapped
154: private double _factor; // 0.0 <= _factor <= 1.0
155: private int _nmax; // 0 <= _nmax = 2^nbit <= 2^NBIT = NMAX
156: private int _n; // 0 <= _n <= _nmax <= NMAX
157: private int _nlo; // _nmax*_factor (_n<=_nlo, if possible)
158: private int _nhi; // NMAX*_factor (_n< _nhi, if possible)
159: private int _shift; // _shift = 1 + NBIT - nbit (see function hash() below)
160: private int _mask; // _mask = _nmax - 1
161: private int[] _key; // array[_nmax] of keys
162: //@SuppressWarnings(value = {"unchecked"})
163: private Object[] _value; // array[_nmax] of values
164:
165: //private boolean[] _filled; // _filled[i]==true iff _key[i] is mapped
166:
167: private int hash(int key) {
168: // Knuth, v. 3, 509-510. Randomize the 31 low-order bits of c*key
169: // and return the highest nbits (where nbits <= 30) bits of these.
170: // The constant c = 1327217885 approximates 2^31 * (sqrt(5)-1)/2.
171: return ((1327217885 * key) >> _shift) & _mask;
172: }
173:
174: private int indexOf(int key) {
175: int i = hash(key);
176: //while (_filled[i]) {
177: while (_value[i] != null) {
178: if (_key[i] == key) {
179: return i;
180: }
181: i = (i - 1) & _mask;
182: }
183: return i;
184: }
185:
186: private void grow() {
187: ++_n;
188: if (_n > NMAX) {
189: throw new RuntimeException("number of keys mapped exceeds "
190: + NMAX);
191: }
192: if (_nlo < _n && _n <= _nhi) {
193: setCapacity(_n);
194: }
195: }
196:
197: private void setCapacity(int capacity) {
198: if (capacity < _n) {
199: capacity = _n;
200: }
201: double factor = (_factor < 0.01) ? 0.01
202: : (_factor > 0.99) ? 0.99 : _factor;
203: int nbit, nmax;
204: for (nbit = 1, nmax = 2; nmax * factor < capacity
205: && nmax < NMAX; ++nbit, nmax *= 2) {
206: ;
207: }
208: int nold = _nmax;
209: if (nmax == nold) {
210: return;
211: }
212: _nmax = nmax;
213: _nlo = (int) (nmax * factor);
214: _nhi = (int) (NMAX * factor);
215: _shift = 1 + NBIT - nbit;
216: _mask = nmax - 1;
217: int[] key = _key;
218: Object[] value = _value;
219: //boolean[] filled = _filled;
220: _n = 0;
221: _key = new int[nmax];
222: // semantically equivalent to _value = new V[nmax]
223: _value = new Object[nmax];
224: //_filled = new boolean[nmax];
225: if (key != null) {
226: for (int i = 0; i < nold; ++i) {
227: //if (filled[i]) {
228: if (value[i] != null) {
229: put(key[i], value[i]);
230: }
231: }
232: }
233: }
234:
235: /**
236: * Get an iterator over the keys
237: */
238:
239: public IntIterator keyIterator() {
240: return new IntHashMapKeyIterator();
241: }
242:
243: /**
244: * Get an iterator over the values
245: */
246:
247: public Iterator valueIterator() {
248: return new IntHashMapValueIterator();
249: }
250:
251: /**
252: * Create a copy of the IntHashMap
253: */
254:
255: public IntHashMap copy() {
256: IntHashMap n = new IntHashMap(size());
257: IntIterator it = keyIterator();
258: while (it.hasNext()) {
259: int k = it.next();
260: n.put(k, get(k));
261: }
262: return n;
263: }
264:
265: /**
266: * Iterator over keys
267: */
268: private class IntHashMapKeyIterator implements IntIterator,
269: Serializable {
270:
271: private int i = 0;
272:
273: public IntHashMapKeyIterator() {
274: i = 0;
275: }
276:
277: public boolean hasNext() {
278: while (i < _key.length) {
279: if (_value[i] != null) {
280: return true;
281: } else {
282: i++;
283: }
284: }
285: return false;
286: }
287:
288: public int next() {
289: return _key[i++];
290: }
291: }
292:
293: /**
294: * Iterator over values
295: */
296: private class IntHashMapValueIterator implements Iterator,
297: Serializable {
298:
299: private IntHashMapKeyIterator k;
300:
301: public IntHashMapValueIterator() {
302: k = new IntHashMapKeyIterator();
303: }
304:
305: public boolean hasNext() {
306: return k.hasNext();
307: }
308:
309: public Object next() {
310: return get(k.next());
311: }
312:
313: public void remove() {
314: throw new UnsupportedOperationException(
315: "remove() is not supported on IntHashMapValueIterator");
316: }
317: }
318: }
319:
320: //
321: // The contents of this file are subject to the Mozilla Public License Version 1.0 (the "License");
322: // you may not use this file except in compliance with the License. You may obtain a copy of the
323: // License at http://www.mozilla.org/MPL/
324: //
325: // Software distributed under the License is distributed on an "AS IS" basis,
326: // WITHOUT WARRANTY OF ANY KIND, either express or implied.
327: // See the License for the specific language governing rights and limitations under the License.
328: //
329: // The Original Code is: all this file.
330: //
331: // The Initial Developer of the Original Code is Dave Hale and Dominique Devienne of Landmark Graphics;
332: // the code was retrofitted to JDK 1.4 by Michael Kay, Saxonica.
333: //
334: // Portions created by (your name) are Copyright (C) (your legal entity). All Rights Reserved.
335: //
336: // Contributor(s): none.
|