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