001: package uk.org.ponder.intutil;
002:
003: /**
004: * The class <code>IntEHInnaBox</code>implements an extendible hash table of
005: * ints to ints that lies in-memory, i.e. inna box. The key value must be hashed
006: * externally. The array used for storage alternates between storing hash values
007: * at even-numbered locations and the required value at odd-numbered ones. A
008: * hash value of 0 is invalid, and represents an empty entry. a stored value of
009: * -1 is invalid, and is returned if the item is not found.
010: *
011: * If hash values are equal, the stored values are indistinguishable and so must
012: * be indexes into some structure which can decide which one was actually
013: * required. Otherwise, hash values should be truly unique, for example
014: * StringVat indices. This is as good as can be done without callbacks such as
015: * equals() and hashCode().
016: */
017:
018: public class IntEHInnaBox {
019: public static final int KNUTH_GOLDEN_CONSTANT = (int) 2654435761L;
020:
021: public static int hash(int smallint) {
022: return smallint * KNUTH_GOLDEN_CONSTANT;
023: }
024:
025: public static final int INVALID_VALUE = -1;
026: private static final int INVALID_HASH = 0;
027: private static final int INITIAL_BITS = 10;
028: private static final double MAXIMUM_LOAD = 0.5;
029:
030: int current_bits = INITIAL_BITS;
031: int[] storage;
032: int current_mask;
033:
034: int filled = 0;
035:
036: public IntEHInnaBox() {
037: allocate();
038: }
039:
040: public IntEHInnaBox(int initialcapacity) {
041: current_bits = (int) (Math.log(initialcapacity) / Math.log(2));
042: allocate();
043: }
044:
045: private void allocate() {
046: storage = new int[1 << current_bits];
047: current_mask = (-1 >>> (32 - current_bits)) ^ 1;
048: }
049:
050: private void checkexpand() {
051: if ((double) (filled + 1) / storage.length > MAXIMUM_LOAD) {
052: int[] oldstorage = storage;
053: ++current_bits;
054:
055: allocate();
056:
057: System.out
058: .println("*******Load factor exceeded: *******: current_mask now "
059: + uk.org.ponder.byteutil.ByteWrap
060: .intToHex(current_mask)
061: + " "
062: + current_bits);
063:
064: for (int i = 0; i < oldstorage.length; i += 2) {
065: if (oldstorage[i] != 0) {
066: put(oldstorage[i], oldstorage[i + 1]);
067: }
068: } // end for each old element
069: } // end if hash overfilled
070: }
071:
072: /*
073: * Get the </code>offset</code>th stored value with the specified hash key.
074: * @param hash The hash value required. @param offset In the case where many
075: * items are stored with identical hash keys, the number of the item with that
076: * hash key that is required. @return The required value, or <code>INVALID_VALID</code>
077: * if there is none found.
078: */
079: // iterate through index numbers sharing hash value
080: // invalid hash value is 0, invalid index is -1
081: public int get(int hash, int offset) {
082: if (hash == INVALID_HASH)
083: ++hash;
084: int initindex = (hash & current_mask);
085: int i = initindex;
086: int curoffset = 0;
087: do {
088: // System.out.println("Found hash value "+ storage[i]+" at location "+ i+
089: // " offset "+curoffset);
090: if (storage[i] == INVALID_HASH)
091: return INVALID_VALUE;
092: if (storage[i] == hash) {
093: if (curoffset == offset)
094: return storage[i + 1];
095: ++curoffset;
096: }
097: i = (i + 2) & current_mask;
098: } while (i != initindex);
099: return INVALID_VALUE;
100: }
101:
102: /*
103: * Enters the specified value into the table with the specified hash key,
104: * unless that value is already stored. @param hash The hash key for the
105: * value. @param value The value that is to be stored. @return <code>true</code>
106: * if the value was successfully stored, <code>false</code> if it was
107: * already present and the table was left unaltered.
108: */
109: public boolean put(int hash, int value) {
110: if (hash == INVALID_HASH)
111: ++hash;
112: checkexpand(); // note that this may change current_mask
113: int initindex = (hash & current_mask);
114: // System.out.println("Putting "+ hash+" value " + value +" at "+
115: // initindex);
116:
117: int i = initindex;
118: do {
119: if (storage[i] == INVALID_HASH)
120: break;
121: if (storage[i + 1] == value)
122: return false;
123: i = (i + 2) & current_mask;
124: } while (i != initindex);
125: // System.out.println("Stored at "+i);
126: storage[i] = hash;
127: storage[i + 1] = value;
128:
129: filled++;
130:
131: return true;
132: }
133: }
|