1 22 23 package com.sosnoski.util.hashset; 24 25 36 37 public class IntHashSet extends PrimitiveSetBase 38 { 39 40 protected int[] m_keyTable; 41 42 48 49 public IntHashSet(int count, double fill) { 50 super(count, fill, int.class); 51 } 52 53 59 60 public IntHashSet(int count) { 61 this(count, DEFAULT_FILL); 62 } 63 64 67 68 public IntHashSet() { 69 this(0, DEFAULT_FILL); 70 } 71 72 77 78 public IntHashSet(IntHashSet base) { 79 super(base); 80 } 81 82 89 90 protected Object getKeyArray() { 91 return m_keyTable; 92 } 93 94 101 102 protected void setKeyArray(Object array) { 103 m_keyTable = (int[])array; 104 } 105 106 115 116 protected final boolean reinsert(int slot) { 117 m_flagTable[slot] = false; 118 return assignSlot(m_keyTable[slot]) != slot; 119 } 120 121 131 132 protected void restructure(boolean[] flags, Object karray) { 133 int[] keys = (int[])karray; 134 for (int i = 0; i < flags.length; i++) { 135 if (flags[i]) { 136 assignSlot(keys[i]); 137 } 138 } 139 } 140 141 147 148 protected final int computeSlot(int key) { 149 return (key * KEY_MULTIPLIER & Integer.MAX_VALUE) % m_flagTable.length; 150 } 151 152 162 163 protected int assignSlot(int key) { 164 int offset = freeSlot(computeSlot(key)); 165 m_flagTable[offset] = true; 166 m_keyTable[offset] = key; 167 return offset; 168 } 169 170 177 178 public boolean add(int key) { 179 ensureCapacity(m_entryCount+1); 180 int offset = -internalFind(key) - 1; 181 if (offset >= 0) { 182 m_entryCount++; 183 m_flagTable[offset] = true; 184 m_keyTable[offset] = key; 185 return true; 186 } else { 187 return false; 188 } 189 } 190 191 198 199 protected final int internalFind(int key) { 200 int slot = computeSlot(key); 201 while (m_flagTable[slot]) { 202 if (key == m_keyTable[slot]) { 203 return slot; 204 } 205 slot = stepSlot(slot); 206 } 207 return -slot - 1; 208 } 209 210 217 218 public boolean contains(int key) { 219 return internalFind(key) >= 0; 220 } 221 222 229 230 public boolean remove(int key) { 231 int slot = internalFind(key); 232 if (slot >= 0) { 233 m_flagTable[slot] = false; 234 m_entryCount--; 235 while (m_flagTable[(slot = stepSlot(slot))]) { 236 reinsert(slot); 237 } 238 return true; 239 } else { 240 return false; 241 } 242 } 243 244 249 250 public Object clone() { 251 return new IntHashSet(this); 252 } 253 } 254
| Popular Tags
|