1 9 package com.vladium.util; 10 11 import java.io.Serializable ; 12 13 24 public 25 final class IntObjectMap implements Serializable 26 { 27 29 32 public IntObjectMap () 33 { 34 this (11, 0.75F); 35 } 36 37 40 public IntObjectMap (final int initialCapacity) 41 { 42 this (initialCapacity, 0.75F); 43 } 44 45 51 public IntObjectMap (int initialCapacity, final float loadFactor) 52 { 53 if (initialCapacity < 0) throw new IllegalArgumentException ("negative input: initialCapacity [" + initialCapacity + "]"); 54 if ((loadFactor <= 0.0) || (loadFactor >= 1.0 + 1.0E-6)) 55 throw new IllegalArgumentException ("loadFactor not in (0.0, 1.0] range: " + loadFactor); 56 57 if (initialCapacity == 0) initialCapacity = 1; 58 59 m_loadFactor = loadFactor > 1.0 ? 1.0F : loadFactor; 60 m_sizeThreshold = (int) (initialCapacity * loadFactor); 61 m_buckets = new Entry [initialCapacity]; 62 } 63 64 65 68 public String toString () 69 { 70 final StringBuffer s = new StringBuffer (); 71 debugDump (s); 72 73 return s.toString (); 74 } 75 76 79 public int size () 80 { 81 return m_size; 82 } 83 84 public boolean contains (final int key) 85 { 86 final Entry [] buckets = m_buckets; 88 final int bucketIndex = (key & 0x7FFFFFFF) % buckets.length; 89 90 for (Entry entry = buckets [bucketIndex]; entry != null; entry = entry.m_next) 92 { 93 if (key == entry.m_key) 94 return true; 95 } 96 97 return false; 98 } 99 100 109 public Object get (final int key) 110 { 111 final Entry [] buckets = m_buckets; 113 final int bucketIndex = (key & 0x7FFFFFFF) % buckets.length; 114 115 for (Entry entry = buckets [bucketIndex]; entry != null; entry = entry.m_next) 117 { 118 if (key == entry.m_key) 119 return entry.m_value; 120 } 121 122 return null; 123 } 124 125 public int [] keys () 126 { 127 if (m_size == 0) 128 return IConstants.EMPTY_INT_ARRAY; 129 else 130 { 131 final int [] result = new int [m_size]; 132 int scan = 0; 133 134 for (int b = 0; b < m_buckets.length; ++ b) 135 { 136 for (Entry entry = m_buckets [b]; entry != null; entry = entry.m_next) 137 { 138 result [scan ++] = entry.m_key; 139 } 140 } 141 142 return result; 143 } 144 } 145 146 154 public Object put (final int key, final Object value) 155 { 156 Entry currentKeyEntry = null; 157 158 160 int bucketIndex = (key & 0x7FFFFFFF) % m_buckets.length; 162 163 Entry [] buckets = m_buckets; 165 for (Entry entry = buckets [bucketIndex]; entry != null; entry = entry.m_next) 166 { 167 if (key == entry.m_key) 168 { 169 currentKeyEntry = entry; 170 break; 171 } 172 } 173 174 if (currentKeyEntry != null) 175 { 176 178 final Object currentKeyValue = currentKeyEntry.m_value; 179 currentKeyEntry.m_value = value; 180 181 return currentKeyValue; 182 } 183 else 184 { 185 187 if (m_size >= m_sizeThreshold) rehash (); 188 189 buckets = m_buckets; 190 bucketIndex = (key & 0x7FFFFFFF) % buckets.length; 191 final Entry bucketListHead = buckets [bucketIndex]; 192 final Entry newEntry = new Entry (key, value, bucketListHead); 193 buckets [bucketIndex] = newEntry; 194 195 ++ m_size; 196 197 return null; 198 } 199 } 200 201 203 205 206 void debugDump (final StringBuffer out) 207 { 208 if (out != null) 209 { 210 out.append (super.toString ()); out.append (EOL); 211 out.append ("size = " + m_size + ", bucket table size = " + m_buckets.length + ", load factor = " + m_loadFactor + EOL); 212 out.append ("size threshold = " + m_sizeThreshold + EOL); 213 } 214 } 215 216 218 219 222 private static final class Entry implements Serializable 223 { 224 Entry (final int key, final Object value, final Entry next) 225 { 226 m_key = key; 227 m_value = value; 228 m_next = next; 229 } 230 231 Object m_value; final int m_key; 233 234 Entry m_next; 236 } 238 239 242 private void rehash () 243 { 244 248 final Entry [] buckets = m_buckets; 249 250 final int newBucketCount = (m_buckets.length << 1) + 1; 251 final Entry [] newBuckets = new Entry [newBucketCount]; 252 253 for (int b = 0; b < buckets.length; ++ b) 255 { 256 for (Entry entry = buckets [b]; entry != null; ) 257 { 258 final Entry next = entry.m_next; final int entryKey = entry.m_key; 260 261 final int newBucketIndex = (entryKey & 0x7FFFFFFF) % newBucketCount; 263 264 final Entry bucketListHead = newBuckets [newBucketIndex]; 265 entry.m_next = bucketListHead; 266 newBuckets [newBucketIndex] = entry; 267 268 entry = next; 269 } 270 } 271 272 273 m_sizeThreshold = (int) (newBucketCount * m_loadFactor); 274 m_buckets = newBuckets; 275 } 276 277 278 private final float m_loadFactor; 280 private Entry [] m_buckets; private int m_size; private int m_sizeThreshold; 284 private static final String EOL = System.getProperty ("line.separator", "\n"); 285 286 } 289 | Popular Tags |