1/* 2 * Copyright (c) 2009-2010 jMonkeyEngine 3 * All rights reserved. 4 * 5 * Redistribution and use in source and binary forms, with or without 6 * modification, are permitted provided that the following conditions are 7 * met: 8 * 9 * * Redistributions of source code must retain the above copyright 10 * notice, this list of conditions and the following disclaimer. 11 * 12 * * Redistributions in binary form must reproduce the above copyright 13 * notice, this list of conditions and the following disclaimer in the 14 * documentation and/or other materials provided with the distribution. 15 * 16 * * Neither the name of 'jMonkeyEngine' nor the names of its contributors 17 * may be used to endorse or promote products derived from this software 18 * without specific prior written permission. 19 * 20 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 21 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED 22 * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 23 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR 24 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, 25 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, 26 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR 27 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF 28 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING 29 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS 30 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 31 */ 32 33package com.jme3.util; 34 35import com.jme3.util.IntMap.Entry; 36import java.util.Iterator; 37import java.util.Map; 38 39/** 40 * Similar to a {@link Map} except that ints are used as keys. 41 * 42 * Taken from <a href="http://code.google.com/p/skorpios/">http://code.google.com/p/skorpios/</a> 43 * 44 * @author Nate 45 */ 46public final class IntMap<T> implements Iterable<Entry<T>>, Cloneable { 47 48 private Entry[] table; 49 private final float loadFactor; 50 private int size, mask, capacity, threshold; 51 52 public IntMap() { 53 this(16, 0.75f); 54 } 55 56 public IntMap(int initialCapacity) { 57 this(initialCapacity, 0.75f); 58 } 59 60 public IntMap(int initialCapacity, float loadFactor) { 61 if (initialCapacity > 1 << 30){ 62 throw new IllegalArgumentException("initialCapacity is too large."); 63 } 64 if (initialCapacity < 0){ 65 throw new IllegalArgumentException("initialCapacity must be greater than zero."); 66 } 67 if (loadFactor <= 0){ 68 throw new IllegalArgumentException("initialCapacity must be greater than zero."); 69 } 70 capacity = 1; 71 while (capacity < initialCapacity){ 72 capacity <<= 1; 73 } 74 this.loadFactor = loadFactor; 75 this.threshold = (int) (capacity * loadFactor); 76 this.table = new Entry[capacity]; 77 this.mask = capacity - 1; 78 } 79 80 @Override 81 public IntMap<T> clone(){ 82 try{ 83 IntMap<T> clone = (IntMap<T>) super.clone(); 84 Entry[] newTable = new Entry[table.length]; 85 for (int i = table.length - 1; i >= 0; i--){ 86 if (table[i] != null) 87 newTable[i] = table[i].clone(); 88 } 89 clone.table = newTable; 90 return clone; 91 }catch (CloneNotSupportedException ex){ 92 } 93 return null; 94 } 95 96 public boolean containsValue(Object value) { 97 Entry[] table = this.table; 98 for (int i = table.length; i-- > 0;){ 99 for (Entry e = table[i]; e != null; e = e.next){ 100 if (e.value.equals(value)){ 101 return true; 102 } 103 } 104 } 105 return false; 106 } 107 108 public boolean containsKey(int key) { 109 int index = ((int) key) & mask; 110 for (Entry e = table[index]; e != null; e = e.next){ 111 if (e.key == key){ 112 return true; 113 } 114 } 115 return false; 116 } 117 118 public T get(int key) { 119 int index = key & mask; 120 for (Entry e = table[index]; e != null; e = e.next){ 121 if (e.key == key){ 122 return (T) e.value; 123 } 124 } 125 return null; 126 } 127 128 public T put(int key, T value) { 129 int index = key & mask; 130 // Check if key already exists. 131 for (Entry e = table[index]; e != null; e = e.next){ 132 if (e.key != key){ 133 continue; 134 } 135 Object oldValue = e.value; 136 e.value = value; 137 return (T) oldValue; 138 } 139 table[index] = new Entry(key, value, table[index]); 140 if (size++ >= threshold){ 141 // Rehash. 142 int newCapacity = 2 * capacity; 143 Entry[] newTable = new Entry[newCapacity]; 144 Entry[] src = table; 145 int bucketmask = newCapacity - 1; 146 for (int j = 0; j < src.length; j++){ 147 Entry e = src[j]; 148 if (e != null){ 149 src[j] = null; 150 do{ 151 Entry next = e.next; 152 index = e.key & bucketmask; 153 e.next = newTable[index]; 154 newTable[index] = e; 155 e = next; 156 }while (e != null); 157 } 158 } 159 table = newTable; 160 capacity = newCapacity; 161 threshold = (int) (newCapacity * loadFactor); 162 mask = capacity - 1; 163 } 164 return null; 165 } 166 167 public T remove(int key) { 168 int index = key & mask; 169 Entry prev = table[index]; 170 Entry e = prev; 171 while (e != null){ 172 Entry next = e.next; 173 if (e.key == key){ 174 size--; 175 if (prev == e){ 176 table[index] = next; 177 }else{ 178 prev.next = next; 179 } 180 return (T) e.value; 181 } 182 prev = e; 183 e = next; 184 } 185 return null; 186 } 187 188 public int size() { 189 return size; 190 } 191 192 public void clear() { 193 Entry[] table = this.table; 194 for (int index = table.length; --index >= 0;){ 195 table[index] = null; 196 } 197 size = 0; 198 } 199 200 public Iterator<Entry<T>> iterator() { 201 IntMapIterator it = new IntMapIterator(); 202 it.beginUse(); 203 return it; 204 } 205 206 final class IntMapIterator implements Iterator<Entry<T>> { 207 208 /** 209 * Current entry. 210 */ 211 private Entry cur; 212 213 /** 214 * Entry in the table 215 */ 216 private int idx = 0; 217 218 /** 219 * Element in the entry 220 */ 221 private int el = 0; 222 223 public IntMapIterator() { 224 } 225 226 public void beginUse(){ 227 cur = table[0]; 228 idx = 0; 229 el = 0; 230 } 231 232 public boolean hasNext() { 233 return el < size; 234 } 235 236 public Entry next() { 237 if (el >= size) 238 throw new IllegalStateException("No more elements!"); 239 240 if (cur != null){ 241 Entry e = cur; 242 cur = cur.next; 243 el++; 244 return e; 245 } 246// if (cur != null && cur.next != null){ 247 // if we have a current entry, continue to the next entry in the list 248// cur = cur.next; 249// el++; 250// return cur; 251// } 252 253 do { 254 // either we exhausted the current entry list, or 255 // the entry was null. find another non-null entry. 256 cur = table[++idx]; 257 } while (cur == null); 258 259 Entry e = cur; 260 cur = cur.next; 261 el ++; 262 263 return e; 264 } 265 266 public void remove() { 267 } 268 269 } 270 271 public static final class Entry<T> implements Cloneable { 272 273 final int key; 274 T value; 275 Entry next; 276 277 Entry(int k, T v, Entry n) { 278 key = k; 279 value = v; 280 next = n; 281 } 282 283 public int getKey(){ 284 return key; 285 } 286 287 public T getValue(){ 288 return value; 289 } 290 291 @Override 292 public String toString(){ 293 return key + " => " + value; 294 } 295 296 @Override 297 public Entry<T> clone(){ 298 try{ 299 Entry<T> clone = (Entry<T>) super.clone(); 300 clone.next = next != null ? next.clone() : null; 301 return clone; 302 }catch (CloneNotSupportedException ex){ 303 } 304 return null; 305 } 306 } 307} 308