001: package net.sf.saxon.sort;
002:
003: import java.io.Serializable;
004:
005: /**
006: * Set of int values.
007: * <p/>
008: * Not thread safe.
009: *
010: * @author Dominique Devienne
011: * @author Michael Kay: retrofitted to JDK 1.4, added iterator()
012: */
013: public class IntHashSet implements Serializable {
014:
015: private static final int NBIT = 30; // MAX_SIZE = 2^NBIT
016:
017: /**
018: * The maximum number of elements this container can contain.
019: */
020: public static final int MAX_SIZE = 1 << NBIT; // maximum number of keys mapped
021:
022: /**
023: * This set's NO-DATA-VALUE.
024: */
025: public final int ndv;
026:
027: /**
028: * Initializes a set with a capacity of 8 and a load factor of 0,25.
029: *
030: * @see #IntHashSet(int,double,int)
031: */
032: public IntHashSet() {
033: this (8, 0.25, Integer.MIN_VALUE);
034: }
035:
036: /**
037: * Initializes a set with the given capacity and a load factor of 0,25.
038: *
039: * @param capacity the initial capacity.
040: * @see #IntHashSet(int,double,int)
041: */
042: public IntHashSet(int capacity) {
043: this (capacity, 0.25, Integer.MIN_VALUE);
044: }
045:
046: /**
047: * Initializes a set with a load factor of 0,25.
048: *
049: * @param capacity the initial capacity.
050: * @param noDataValue the value to use for non-values.
051: * @see #IntHashSet(int,double,int)
052: */
053: public IntHashSet(int capacity, int noDataValue) {
054: this (capacity, 0.25, noDataValue);
055: }
056:
057: /**
058: * Constructs a new set with initial capacity, and load factor.
059: * <p/>
060: * The capacity is the number of keys that can be mapped without resizing
061: * the arrays in which keys and values are stored. For efficiency, only
062: * a fraction of the elements in those arrays are used. That fraction is
063: * the specified load factor. The initial length of the arrays equals the
064: * smallest power of two not less than the ratio capacity/factor. The
065: * capacity of the set is increased, as necessary. The maximum number
066: * of keys that can be mapped is 2^30.
067: *
068: * @param capacity the initial capacity.
069: * @param factor the load factor.
070: * @param noDataValue the value to use for non-values.
071: */
072: public IntHashSet(int capacity, double factor, int noDataValue) {
073: ndv = noDataValue;
074: _factor = factor;
075: setCapacity(capacity);
076: }
077:
078: /**
079: * {@inheritDoc}
080: */
081: public void clear() {
082: _size = 0;
083: for (int i = 0; i < _nmax; ++i) {
084: _values[i] = ndv;
085: }
086: }
087:
088: /**
089: * {@inheritDoc}
090: */
091: public int size() {
092: return _size;
093: }
094:
095: /**
096: * {@inheritDoc}
097: */
098: public boolean isEmpty() {
099: return _size == 0;
100: }
101:
102: /**
103: * {@inheritDoc}
104: */
105: public int peek(int defaultValue) {
106: for (int v = 0; v < _values.length; v++) {
107: if (_values[v] != ndv) {
108: return _values[v];
109: }
110: }
111: return defaultValue;
112: }
113:
114: /**
115: * {@inheritDoc}
116: */
117: public int[] getValues() {
118: int index = 0;
119: final int[] values = new int[_size];
120: for (int v = 0; v < _values.length; v++) {
121: if (_values[v] != ndv) {
122: values[index++] = _values[v];
123: }
124: }
125: return values;
126: }
127:
128: /**
129: * {@inheritDoc}
130: */
131: public boolean contains(int value) {
132: return (_values[indexOf(value)] != ndv) ? true : false;
133: }
134:
135: /**
136: * {@inheritDoc}
137: */
138: public boolean remove(int value) {
139: // Knuth, v. 3, 527, Algorithm R.
140: int i = indexOf(value);
141: if (_values[i] == ndv) {
142: return false;
143: }
144: --_size;
145: for (;;) {
146: _values[i] = ndv;
147: int j = i;
148: int r;
149: do {
150: i = (i - 1) & _mask;
151: if (_values[i] == ndv) {
152: return true;
153: }
154: r = hash(_values[i]);
155: } while ((i <= r && r < j) || (r < j && j < i)
156: || (j < i && i <= r));
157: _values[j] = _values[i];
158: }
159: }
160:
161: /**
162: * {@inheritDoc}
163: */
164: // public boolean removeAll(int... values) {
165: // boolean modified = false;
166: // for (int v=0; v<_values.length; v++) {
167: // if (_values[v] != ndv) {
168: // modified |= remove(v);
169: // }
170: // }
171: // return modified;
172: // }
173: /**
174: * {@inheritDoc}
175: */
176: public boolean add(int value) {
177: if (value == ndv) {
178: throw new IllegalArgumentException(
179: "Can't add no data value");
180: }
181: int i = indexOf(value);
182: if (_values[i] == ndv) {
183: ++_size;
184: _values[i] = value;
185:
186: // Check new size
187: if (_size > MAX_SIZE) {
188: throw new RuntimeException("Too many elements (> "
189: + MAX_SIZE + ')');
190: }
191: if (_nlo < _size && _size <= _nhi) {
192: setCapacity(_size);
193: }
194: return true;
195: } else {
196: return false; // leave set unchanged
197: }
198: }
199:
200: /**
201: * {@inheritDoc}
202: */
203: // public boolean addAll(int... values) {
204: // boolean modified = false;
205: // for (int value : values) {
206: // modified |= add(value);
207: // }
208: // return modified;
209: // }
210:
211: ///////////////////////////////////////////////////////////////////////////
212: // private
213: private double _factor; // 0.0 <= _factor <= 1.0
214: private int _nmax; // 0 <= _nmax = 2^nbit <= 2^NBIT = MAX_SIZE
215: private int _size; // 0 <= _size <= _nmax <= MAX_SIZE
216: private int _nlo; // _nmax*_factor (_size<=_nlo, if possible)
217: private int _nhi; // MAX_SIZE*_factor (_size< _nhi, if possible)
218: private int _shift; // _shift = 1 + NBIT - nbit (see function hash() below)
219: private int _mask; // _mask = _nmax - 1
220: private int[] _values; // array[_nmax] of values
221:
222: private int hash(int key) {
223: // Knuth, v. 3, 509-510. Randomize the 31 low-order bits of c*key
224: // and return the highest nbits (where nbits <= 30) bits of these.
225: // The constant c = 1327217885 approximates 2^31 * (sqrt(5)-1)/2.
226: return ((1327217885 * key) >> _shift) & _mask;
227: }
228:
229: /**
230: * Gets the index of the value, if it exists, or the index at which
231: * this value would be added if it does not exist yet.
232: */
233: private int indexOf(int value) {
234: int i = hash(value);
235: while (_values[i] != ndv) {
236: if (_values[i] == value) {
237: return i;
238: }
239: i = (i - 1) & _mask;
240: }
241: return i;
242: }
243:
244: private void setCapacity(int capacity) {
245: if (capacity < _size) {
246: capacity = _size;
247: }
248: double factor = (_factor < 0.01) ? 0.01
249: : (_factor > 0.99) ? 0.99 : _factor;
250: int nbit, nmax;
251: for (nbit = 1, nmax = 2; nmax * factor < capacity
252: && nmax < MAX_SIZE; ++nbit, nmax *= 2) {
253: ;
254: }
255: int nold = _nmax;
256: if (nmax == nold) {
257: return;
258: }
259:
260: _nmax = nmax;
261: _nlo = (int) (nmax * factor);
262: _nhi = (int) (MAX_SIZE * factor);
263: _shift = 1 + NBIT - nbit;
264: _mask = nmax - 1;
265:
266: _size = 0;
267: int[] values = _values;
268: _values = new int[nmax];
269: java.util.Arrays.fill(_values, ndv); // empty all values
270: if (values != null) {
271: for (int i = 0; i < nold; ++i) {
272: int value = values[i];
273: if (value != ndv) {
274: // Don't use add, because the capacity is necessarily large enough,
275: // and the value is necessarily unique (since in this set already)!
276: //add(values[i]);
277: ++_size;
278: _values[indexOf(value)] = value;
279: }
280: }
281: }
282: }
283:
284: /**
285: * Get an iterator over the values
286: */
287:
288: public IntIterator iterator() {
289: return new IntHashSetIterator();
290: }
291:
292: /**
293: * Form a new set that is the union of this set with another set.
294: */
295:
296: public IntHashSet union(IntHashSet other) {
297: IntHashSet n = new IntHashSet((int) (size() + other.size()));
298: IntIterator it = iterator();
299: while (it.hasNext()) {
300: n.add(it.next());
301: }
302: it = other.iterator();
303: while (it.hasNext()) {
304: n.add(it.next());
305: }
306: return n;
307: }
308:
309: /**
310: * Form a new set that is the intersection of this set with another set.
311: */
312:
313: public IntHashSet intersect(IntHashSet other) {
314: IntHashSet n = new IntHashSet((int) size());
315: IntIterator it = iterator();
316: while (it.hasNext()) {
317: int v = it.next();
318: if (other.contains(v)) {
319: n.add(it.next());
320: }
321: }
322: return n;
323: }
324:
325: /**
326: * Form a new set that is the difference of this set with another set.
327: */
328:
329: public IntHashSet except(IntHashSet other) {
330: IntHashSet n = new IntHashSet((int) size());
331: IntIterator it = iterator();
332: while (it.hasNext()) {
333: int v = it.next();
334: if (!other.contains(v)) {
335: n.add(it.next());
336: }
337: }
338: return n;
339: }
340:
341: /**
342: * Test if this set is a superset of another set
343: */
344:
345: public boolean containsAll(IntHashSet other) {
346: IntIterator it = other.iterator();
347: while (it.hasNext()) {
348: if (!contains(it.next())) {
349: return false;
350: }
351: }
352: return true;
353: }
354:
355: /**
356: * Test if this set has overlapping membership with another set
357: */
358:
359: public boolean containsSome(IntHashSet other) {
360: IntIterator it = other.iterator();
361: while (it.hasNext()) {
362: if (contains(it.next())) {
363: return true;
364: }
365: }
366: return false;
367: }
368:
369: /**
370: * Test whether this set has exactly the same members as another set
371: */
372:
373: public boolean equals(Object other) {
374: if (other instanceof IntHashSet) {
375: IntHashSet s = (IntHashSet) other;
376: return (size() == s.size() && containsAll(s));
377: } else {
378: return false;
379: }
380: }
381:
382: /**
383: * Construct a hash key that supports the equals() test
384: */
385:
386: public int hashCode() {
387: int h = 936247625;
388: IntIterator it = iterator();
389: while (it.hasNext()) {
390: h += it.next();
391: }
392: return h;
393: }
394:
395: /**
396: * Iterator class
397: */
398:
399: private class IntHashSetIterator implements IntIterator,
400: Serializable {
401:
402: private int i = 0;
403:
404: public IntHashSetIterator() {
405: i = 0;
406: }
407:
408: public boolean hasNext() {
409: while (i < _values.length) {
410: if (_values[i] != ndv) {
411: return true;
412: } else {
413: i++;
414: }
415: }
416: return false;
417: }
418:
419: public int next() {
420: return _values[i++];
421: }
422: }
423:
424: }
425:
426: //
427: // The contents of this file are subject to the Mozilla Public License Version 1.0 (the "License");
428: // you may not use this file except in compliance with the License. You may obtain a copy of the
429: // License at http://www.mozilla.org/MPL/
430: //
431: // Software distributed under the License is distributed on an "AS IS" basis,
432: // WITHOUT WARRANTY OF ANY KIND, either express or implied.
433: // See the License for the specific language governing rights and limitations under the License.
434: //
435: // The Original Code is: all this file.
436: //
437: // The Initial Developer of the Original Code is Dominique Devienne of Landmark Graphics.
438: //
439: // Portions created by (your name) are Copyright (C) (your legal entity). All Rights Reserved.
440: //
441: // Contributor(s): none.
|