1 package com.quadcap.util.collections; 2 3 40 41 import java.util.Iterator ; 42 43 48 public class IntMap { 49 int size; 50 Entry[] entries; 51 Entry freeList; 52 53 public IntMap(int initSize) { 54 this.size = initSize | 1; 55 while (!isPrime(size)) size += 2; 56 entries = new Entry[size]; 57 } 58 59 public final Object get(int key) { 60 int h = hash(key); 61 for (Entry entry = entries[h]; entry != null; entry = entry.next) { 62 if (entry.key == key) return entry.val; 63 } 64 return null; 65 } 66 67 public final void put(int key, Object val) { 68 int h = hash(key); 69 Entry entry = getEntry(key, val); 70 entry.next = entries[h]; 71 entries[h] = entry; 72 } 73 74 public final void remove(int key) { 75 int h = hash(key); 76 Entry prev = null; 77 for (Entry entry = entries[h]; entry != null; entry = entry.next) { 78 if (entry.key == key) { 79 if (prev == null) { 80 entries[h] = entry.next; 81 } else { 82 prev.next = entry.next; 83 } 84 freeEntry(entry); 85 } 86 prev = entry; 87 } 88 } 89 90 final Entry getEntry(int key, Object val) { 91 Entry entry = freeList; 92 if (entry == null) { 93 entry = new Entry(); 94 } else { 95 freeList = entry.next; 96 } 97 entry.key = key; 98 entry.val = val; 99 return entry; 100 } 101 102 final void freeEntry(Entry entry) { 103 entry.next = freeList; 104 freeList = entry; 105 } 106 107 public final static boolean isPrime(int x) { 108 if ((x & 1) == 0) return false; 109 for (int i = 3; i*i <= x; i += 2) { 110 if ((x % i) == 0) return false; 111 } 112 return true; 113 } 114 115 public Iterator keys() { 116 return new IntMapIterator(this); 117 } 118 119 final int hash(int key) { 120 int h = key % size; 121 if (h < 0) { 122 h = 0 - h; 123 } 124 return h; 125 } 126 127 class Entry { 128 int key; 129 Object val; 130 Entry next; 131 } 132 133 class IntMapIterator implements Iterator { 134 IntMap map; 135 int epos = 0; 136 Entry entry = null; 137 138 public IntMapIterator(IntMap map) { this.map = map; } 139 140 public boolean hasNext() { 141 while (epos < map.size && entry == null) { 142 entry = map.entries[epos++]; 143 } 144 return entry != null; 145 } 146 147 public Object next() { 148 Integer ret = null; 149 if (hasNext()) { 150 ret = new Integer (entry.key); 151 entry = entry.next; 152 } 153 return ret; 154 } 155 156 public void remove() {} 157 } 158 159 } 160 | Popular Tags |