001/****************************************************************************** 002 Copyright 2011 See AUTHORS file. 003 004 Licensed under the Apache License, Version 2.0 (the "License"); 005 you may not use this file except in compliance with the License. 006 You may obtain a copy of the License at 007 008 http://www.apache.org/licenses/LICENSE-2.0 009 010 Unless required by applicable law or agreed to in writing, software 011 distributed under the License is distributed on an "AS IS" BASIS, 012 WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 013 See the License for the specific language governing permissions and 014 limitations under the License. 015 */ 016 017package squidpony.squidgrid.gui.gdx; 018 019import com.badlogic.gdx.graphics.Color; 020import com.badlogic.gdx.graphics.g2d.Batch; 021import com.badlogic.gdx.math.Frustum; 022import com.badlogic.gdx.utils.GdxRuntimeException; 023import squidpony.StringKit; 024import squidpony.squidmath.HashCommon; 025import squidpony.squidmath.IntVLA; 026import squidpony.squidmath.NumberTools; 027 028import java.util.Arrays; 029import java.util.Iterator; 030import java.util.NoSuchElementException; 031 032/** 033 * An unordered map where the keys are two positive ints up to 16 bits (x and y, between 0 and 65535) and there are 034 * multiple kinds of value per key, here just a char and a float for color. Can be rendered if given a running Batch 035 * and a TextCellFactory using {@link #draw(Batch, TextCellFactory, Frustum)}. 036 * <br> 037 * 038 * @author Nathan Sweet 039 * @author Tommy Ettinger 040 */ 041public class SparseTextMap implements Iterable<SparseTextMap.Entry> { 042 private static final int EMPTY = 0; 043 044 public int size; 045 046 private int[] keyTable; 047 private char[] charValueTable; 048 private float[] floatValueTable; 049 private final IntVLA keys; 050 051 private char zeroChar; 052 private float zeroFloat; 053 private boolean hasZeroValue; 054 055 private float loadFactor; 056 private int shift, mask, threshold; 057 058 private transient Entries entries1, entries2; 059 private transient CharValues charValues1, charValues2; 060 private transient FloatValues floatValues1, floatValues2; 061 private transient Keys keys1, keys2; 062 063 /** 064 * Creates a new map with an initial capacity of 192 and a load factor of 0.75. 065 */ 066 public SparseTextMap() { 067 this(256, 0.75f); 068 } 069 070 /** 071 * Creates a new map with a load factor of 0.75. 072 * 073 * @param initialCapacity If not a power of two, it is increased to the next nearest power of two. 074 */ 075 public SparseTextMap(int initialCapacity) { 076 this(initialCapacity, 0.75f); 077 } 078 079 /** 080 * Creates a new map with the specified initial capacity and load factor. This map will hold initialCapacity items before 081 * growing the backing table. 082 * 083 * @param initialCapacity If not a power of two, it is increased to the next nearest power of two. 084 */ 085 public SparseTextMap(int initialCapacity, float loadFactor) { 086 if (initialCapacity < 0) 087 throw new IllegalArgumentException("initialCapacity must be >= 0: " + initialCapacity); 088 if (loadFactor <= 0f || loadFactor >= 1f) 089 throw new IllegalArgumentException("loadFactor must be > 0 and < 1: " + loadFactor); 090 initialCapacity = HashCommon.nextPowerOfTwo((int)Math.ceil(initialCapacity / loadFactor)); 091 if (initialCapacity > 1 << 30) 092 throw new IllegalArgumentException("initialCapacity is too large: " + initialCapacity); 093 094 this.loadFactor = loadFactor; 095 096 threshold = (int)(initialCapacity * loadFactor); 097 mask = initialCapacity - 1; 098 shift = Long.numberOfLeadingZeros(mask); 099 100 keyTable = new int[initialCapacity]; 101 charValueTable = new char[initialCapacity]; 102 floatValueTable = new float[initialCapacity]; 103 keys = new IntVLA(initialCapacity); 104 } 105 106 /** 107 * Creates a new map identical to the specified map. 108 */ 109 public SparseTextMap(SparseTextMap map) { 110 loadFactor = map.loadFactor; 111 threshold = map.threshold; 112 mask = map.mask; 113 shift = map.shift; 114 keyTable = new int[map.keyTable.length]; 115 System.arraycopy(map.keyTable, 0, keyTable, 0, map.keyTable.length); 116 charValueTable = new char[map.charValueTable.length]; 117 System.arraycopy(map.charValueTable, 0, charValueTable, 0, map.charValueTable.length); 118 floatValueTable = new float[map.floatValueTable.length]; 119 System.arraycopy(map.floatValueTable, 0, floatValueTable, 0, map.floatValueTable.length); 120 size = map.size; 121 zeroChar = map.zeroChar; 122 zeroFloat = map.zeroFloat; 123 hasZeroValue = map.hasZeroValue; 124 keys = new IntVLA(map.keys); 125 } 126 127 /** 128 * Draws the contents of this SparseTextMap, using the keys as x,y pairs as they would be entered by calling 129 * {@link #place(int, int, char, float)} and drawing the associated char at that x,y position. Uses a 130 * {@link Frustum} object, usually obtained from the current Camera with 131 * {@link com.badlogic.gdx.graphics.Camera#frustum}, to cull anything that would be drawn out of view. Treats the 132 * float value as a color for the char, using the encoding for colors as floats that {@link Color#toFloatBits()} 133 * uses. Relies on the sizing information from the given TextCellFactory (its 134 * {@link TextCellFactory#actualCellWidth} and {@link TextCellFactory#actualCellHeight}, which may differ from its 135 * width and height if either of {@link TextCellFactory#tweakWidth(float)} or 136 * {@link TextCellFactory#tweakHeight(float)} were called). It also, of course, uses the TextCellFactory to 137 * determine what its text will look like (font, size, and so on). The TextCellFactory must have been initialized, 138 * probably with {@link TextCellFactory#initBySize()} after setting the width and height as desired. This method 139 * should be called between {@code batch.begin()} and {@code batch.end()} with the Batch passed to this. 140 * 141 * @param batch the {@link FilterBatch} or other Batch used to draw this; should have already have had begin() called 142 * @param textFactory used to determine the font, size, cell size, and other information; must be initialized 143 */ 144 public void draw(Batch batch, TextCellFactory textFactory) { 145 draw(batch, textFactory, 0f, 0f); 146 } 147 /** 148 * Draws the contents of this SparseTextMap, using the keys as x,y pairs as they would be entered by calling 149 * {@link #place(int, int, char, float)} and drawing the associated char at that x,y position, potentially with an 150 * offset on x and/or y. Uses a {@link Frustum} object, usually obtained from the current Camera with 151 * {@link com.badlogic.gdx.graphics.Camera#frustum}, to cull anything that would be drawn out of view. Treats the 152 * float value as a color for the char, using the encoding for colors as floats that {@link Color#toFloatBits()} 153 * uses. Relies on the sizing information from the given TextCellFactory (its 154 * {@link TextCellFactory#actualCellWidth} and {@link TextCellFactory#actualCellHeight}, which may differ from its 155 * width and height if either of {@link TextCellFactory#tweakWidth(float)} or 156 * {@link TextCellFactory#tweakHeight(float)} were called). It also, of course, uses the TextCellFactory to 157 * determine what its text will look like (font, size, and so on). The TextCellFactory must have been initialized, 158 * probably with {@link TextCellFactory#initBySize()} after setting the width and height as desired. This method 159 * should be called between {@code batch.begin()} and {@code batch.end()} with the Batch passed to this. 160 * 161 * @param batch the {@link FilterBatch} or other Batch used to draw this; should have already have had begin() called 162 * @param textFactory used to determine the font, size, cell size, and other information; must be initialized 163 * @param screenOffsetX offset to apply to the x position of each char rendered; positive moves chars right 164 * @param screenOffsetY offset to apply to the y position of each char rendered; positive moves chars up 165 */ 166 public void draw(Batch batch, TextCellFactory textFactory, float screenOffsetX, float screenOffsetY) { 167 //textFactory.configureShader(batch); 168 final float widthInc = textFactory.actualCellWidth, heightInc = -textFactory.actualCellHeight; 169 int n; 170 for (Entry entry : entries()) { 171 n = entry.key; 172// n ^= n >>> 16; 173// n *= 0xA123B; 174 175// n ^= n << 26; 176// n ^= n >>> 15; 177// n ^= n << 17; 178 textFactory.draw(batch, entry.charValue, entry.floatValue, 179 (n & 0xFFFF) * widthInc + screenOffsetX, (n >>> 16) * heightInc + screenOffsetY); 180 } 181 } 182 /** 183 * Draws the contents of this SparseTextMap, using the keys as x,y pairs as they would be entered by calling 184 * {@link #place(int, int, char, float)} and drawing the associated char at that x,y position. Uses a 185 * {@link Frustum} object, usually obtained from the current Camera with 186 * {@link com.badlogic.gdx.graphics.Camera#frustum}, to cull anything that would be drawn out of view. Treats the 187 * float value as a color for the char, using the encoding for colors as floats that {@link Color#toFloatBits()} 188 * uses. Relies on the sizing information from the given TextCellFactory (its 189 * {@link TextCellFactory#actualCellWidth} and {@link TextCellFactory#actualCellHeight}, which may differ from its 190 * width and height if either of {@link TextCellFactory#tweakWidth(float)} or 191 * {@link TextCellFactory#tweakHeight(float)} were called). It also, of course, uses the TextCellFactory to 192 * determine what its text will look like (font, size, and so on). The TextCellFactory must have been initialized, 193 * probably with {@link TextCellFactory#initBySize()} after setting the width and height as desired. This method 194 * should be called between {@code batch.begin()} and {@code batch.end()} with the Batch passed to this. 195 * 196 * @param batch the {@link FilterBatch} or other Batch used to draw this; should have already have had begin() called 197 * @param textFactory used to determine the font, size, cell size, and other information; must be initialized 198 * @param frustum a {@link Frustum} object to determine culling, almost always obtained from {@link com.badlogic.gdx.graphics.Camera#frustum} 199 */ 200 public void draw(Batch batch, TextCellFactory textFactory, Frustum frustum) { 201 draw(batch, textFactory, frustum, 0f, 0f); 202 } 203 /** 204 * Draws the contents of this SparseTextMap, using the keys as x,y pairs as they would be entered by calling 205 * {@link #place(int, int, char, float)} and drawing the associated char at that x,y position, potentially with an 206 * offset on x and/or y. Uses a {@link Frustum} object, usually obtained from the current Camera with 207 * {@link com.badlogic.gdx.graphics.Camera#frustum}, to cull anything that would be drawn out of view. Treats the 208 * float value as a color for the char, using the encoding for colors as floats that {@link Color#toFloatBits()} 209 * uses. Relies on the sizing information from the given TextCellFactory (its 210 * {@link TextCellFactory#actualCellWidth} and {@link TextCellFactory#actualCellHeight}, which may differ from its 211 * width and height if either of {@link TextCellFactory#tweakWidth(float)} or 212 * {@link TextCellFactory#tweakHeight(float)} were called). It also, of course, uses the TextCellFactory to 213 * determine what its text will look like (font, size, and so on). The TextCellFactory must have been initialized, 214 * probably with {@link TextCellFactory#initBySize()} after setting the width and height as desired. This method 215 * should be called between {@code batch.begin()} and {@code batch.end()} with the Batch passed to this. 216 * 217 * @param batch the {@link FilterBatch} or other Batch used to draw this; should have already have had begin() called 218 * @param textFactory used to determine the font, size, cell size, and other information; must be initialized 219 * @param frustum a {@link Frustum} object to determine culling, almost always obtained from {@link com.badlogic.gdx.graphics.Camera#frustum} 220 * @param screenOffsetX offset to apply to the x position of each char rendered; positive moves chars right 221 * @param screenOffsetY offset to apply to the y position of each char rendered; positive moves chars up 222 */ 223 public void draw(Batch batch, TextCellFactory textFactory, Frustum frustum, float screenOffsetX, float screenOffsetY) { 224 //textFactory.configureShader(batch); 225 final float widthInc = textFactory.actualCellWidth, heightInc = -textFactory.actualCellHeight; 226 float x, y; 227 int n; 228 for (Entry entry : entries()) { 229 n = entry.key; 230// n ^= n >>> 16; 231// n *= 0xA123B; 232 233// n ^= n << 26; 234// n ^= n >>> 15; 235// n ^= n << 17; 236 x = (n & 0xFFFF) * widthInc + screenOffsetX; 237 y = (n >>> 16) * heightInc + screenOffsetY; 238 if(frustum.boundsInFrustum(x, y, 0f, widthInc, -heightInc, 0f)) 239 textFactory.draw(batch, entry.charValue, entry.floatValue, x, y); 240 } 241 } 242 243 /** 244 * Draws the contents of this SparseTextMap, using the keys as x,y pairs as they would be entered by calling 245 * {@link #place(int, int, char, float)} and drawing the char replacement at that x,y position, potentially with an 246 * offset on x and/or y. Uses a {@link Frustum} object, usually obtained from the current Camera with 247 * {@link com.badlogic.gdx.graphics.Camera#frustum}, to cull anything that would be drawn out of view. Treats the 248 * float value as a color for replacement, using the encoding for colors as floats that {@link Color#toFloatBits()} 249 * uses. Relies on the sizing information from the given TextCellFactory (its 250 * {@link TextCellFactory#actualCellWidth} and {@link TextCellFactory#actualCellHeight}, which may differ from its 251 * width and height if either of {@link TextCellFactory#tweakWidth(float)} or 252 * {@link TextCellFactory#tweakHeight(float)} were called). It also, of course, uses the TextCellFactory to 253 * determine what its text will look like (font, size, and so on). The TextCellFactory must have been initialized, 254 * probably with {@link TextCellFactory#initBySize()} after setting the width and height as desired. This method 255 * should be called between {@code batch.begin()} and {@code batch.end()} with the Batch passed to this. 256 * 257 * @param batch the {@link FilterBatch} or other Batch used to draw this; should have already have had begin() called 258 * @param textFactory used to determine the font, size, cell size, and other information; must be initialized 259 * @param frustum a {@link Frustum} object to determine culling, almost always obtained from {@link com.badlogic.gdx.graphics.Camera#frustum} 260 * @param screenOffsetX offset to apply to the x position of each char rendered; positive moves chars right 261 * @param screenOffsetY offset to apply to the y position of each char rendered; positive moves chars up 262 * @param replacement a char that will be used in place of the normal char values stored in this; often the char 263 * with Unicode value 0, which renders as a solid block. 264 */ 265 public void draw(Batch batch, TextCellFactory textFactory, Frustum frustum, float screenOffsetX, float screenOffsetY, char replacement) { 266 //textFactory.configureShader(batch); 267 final float widthInc = textFactory.actualCellWidth, heightInc = -textFactory.actualCellHeight; 268 float x, y; 269 int n; 270 for (Entry entry : entries()) { 271 n = entry.key; 272// n ^= n >>> 16; 273// n *= 0xA123B; 274 275// n ^= n << 26; 276// n ^= n >>> 15; 277// n ^= n << 17; 278// n = ((n & 0x22222222) << 1) | ((n >>> 1) & 0x22222222) | (n & 0x99999999); 279// n = ((n & 0x0c0c0c0c) << 2) | ((n >>> 2) & 0x0c0c0c0c) | (n & 0xc3c3c3c3); 280// n = ((n & 0x00f000f0) << 4) | ((n >>> 4) & 0x00f000f0) | (n & 0xf00ff00f); 281// n = ((n & 0x0000ff00) << 8) | ((n >>> 8) & 0x0000ff00) | (n & 0xff0000ff); 282 x = (n & 0xFFFF) * widthInc + screenOffsetX; 283 y = (n >>> 16) * heightInc + screenOffsetY; 284 if(frustum.boundsInFrustum(x, y, 0f, widthInc, -heightInc, 0f)) 285 textFactory.draw(batch, replacement, entry.floatValue, x, y); 286 } 287 } 288 289 /** 290 * Packs the given x,y position into one int in the type that is used elsewhere in this class. 291 * This requires x and y to each be between 0 and 65535, both inclusive. 292 * 293 * @param x the x component to encode; this must be between 0 and 65535, both inclusive 294 * @param y the y component to encode; this must be between 0 and 65535, both inclusive 295 * @return an encoded form of the x,y pair in the style used elsewhere in this class 296 */ 297 public static int encodePosition(final int x, final int y) { 298 return (x | y << 16); 299// final int n = (x | y << 16) * 0x4F6F3; 300// return n ^ n >>> 16; 301 302// n ^= n << 17; 303// n ^= n >>> 15; 304// n ^= n >>> 30; 305// return n ^ n << 26; 306 //return GreasedRegion.interleaveBits(x, y); 307 } 308 309 /** 310 * Decodes a packed position and gets the x component from it, if it was produced by 311 * {@link #encodePosition(int, int)} or {@link #place(int, int, char, float)}. 312 * 313 * @param encoded a packed position that holds x and y components 314 * @return the x component packed in the parameter 315 */ 316 public static int decodeX(final int encoded) { 317 return encoded & 0xFFFF; 318// return ((encoded ^ encoded >>> 16) * 0xA123B) & 0xFFFF; 319// encoded ^= encoded << 26; 320// return (encoded ^ encoded >>> 15) & 0xFFFF; 321 //return GreasedRegion.disperseBits(encoded) & 0xFFFF; 322 } 323 324 /** 325 * Decodes a packed position and gets the y component from it, if it was produced by 326 * {@link #encodePosition(int, int)} or {@link #place(int, int, char, float)}. 327 * 328 * @param encoded a packed position that holds x and y components 329 * @return the y component packed in the parameter 330 */ 331 public static int decodeY(final int encoded) { 332 return encoded >>> 16; 333// return ((encoded ^ encoded >>> 16) * 0xA123B) >>> 16; 334// encoded ^= encoded << 26; 335// encoded ^= encoded >>> 15; 336// return (encoded ^ encoded << 17) >>> 16; 337 //return GreasedRegion.disperseBits(encoded) >>> 16; 338 } 339 340 private int fibonacci(final int item) { 341 // shift is always greater than 32, less than 64 342 return (int)(item * 0x9E3779B97F4A7C15L >>> shift); 343 } 344 345 private int locateKey (final int key) { 346 return locateKey(key, fibonacci(key)); 347 } 348 349 /** 350 * Given a key and its initial placement to try in an array, this finds the actual location of the key in the array 351 * if it is present, or -1 if the key is not present. This can be overridden if a subclass needs to compare for 352 * equality differently than just by using == with int keys, but only within the same package. 353 * 354 * @param key a K key that will be checked for equality if a similar-seeming key is found 355 * @param placement as calculated by {@link #fibonacci(int)}, almost always with {@code place(key)} 356 * @return the location in the key array of key, if found, or -1 if it was not found. 357 */ 358 private int locateKey (final int key, final int placement) { 359 for (int i = placement; ; i = i + 1 & mask) { 360 // empty space is available 361 if (keyTable[i] == 0) { 362 return -1; 363 } 364 if (key == (keyTable[i])) { 365 return i; 366 } 367 } 368 } 369 370 371 /** 372 * Places a char in the given libGDX Color at the requested x, y position in grid cells, where x and y must each be 373 * between 0 and 65535, both inclusive. The color can also be an SColor, such as one of the many constants in that 374 * class. Returns the int code that can be used to locate the x,y pair as a key in this SparseTextMap. 375 * 376 * @param x the x position of the colorful char; this must be between 0 and 65535, both inclusive 377 * @param y the y position of the colorful char; this must be between 0 and 65535, both inclusive 378 * @param charValue the char to put into the SparseTextMap 379 * @param color the libGDX Color or SColor to use for the char 380 * @return the int that the x,y pair will be stored at, and used as the single key associated with the colorful char 381 */ 382 public int place(int x, int y, char charValue, Color color) { 383 return place(x, y, charValue, color.toFloatBits()); 384 } 385 386 /** 387 * Places a char in the given encoded color at the requested x, y position in grid cells, where x and y must each be 388 * between 0 and 65535, both inclusive, and the encoded color is one produced by {@link Color#toFloatBits()} or any 389 * of several methods in {@link SColor}, such as {@link SColor#floatGetI(int, int, int)}, 390 * {@link SColor#floatGetHSV(float, float, float, float)}, or {@link SColor#lerpFloatColors(float, float, float)}. 391 * Returns the int code that can be used to locate the x,y pair as a key in this SparseTextMap. 392 * 393 * @param x the x position of the colorful char; this must be between 0 and 65535, both inclusive 394 * @param y the y position of the colorful char; this must be between 0 and 65535, both inclusive 395 * @param charValue the char to put into the SparseTextMap 396 * @param encodedColor the encoded color to use for the char, as produced by {@link Color#toFloatBits()} 397 * @return the int that the x,y pair will be stored at, and used as the single key associated with the colorful char 398 */ 399 public int place(int x, int y, char charValue, float encodedColor) { 400 int code = encodePosition(x, y); 401 put(code, charValue, encodedColor); 402 return code; 403 } 404 405 public void put (int key, char charValue, float floatValue) { 406 if (key == 0) { 407 zeroChar = charValue; 408 zeroFloat = floatValue; 409 if (!hasZeroValue) { 410 hasZeroValue = true; 411 keys.add(0); 412 size++; 413 } 414 return; 415 } 416 417 int b = fibonacci(key); 418 int loc = locateKey(key, b); 419 // an identical key already exists 420 if (loc != -1) { 421 charValueTable[loc] = charValue; 422 floatValueTable[loc] = floatValue; 423 return; 424 } 425 final int[] keyTable = this.keyTable; 426 final char[] charValueTable = this.charValueTable; 427 final float[] floatValueTable = this.floatValueTable; 428 keys.add(key); 429 430 for (int i = b; ; i = (i + 1) & mask) { 431 // space is available so we insert and break 432 if (keyTable[i] == 0) { 433 keyTable[i] = key; 434 charValueTable[i] = charValue; 435 floatValueTable[i] = floatValue; 436 437 if (++size >= threshold) { 438 resize(keyTable.length << 1); 439 } 440 return; 441 } 442 } 443 } 444 445 /** 446 * If and only if key is already present, this changes the float associated with it while leaving the char the same. 447 * @param key the encoded key as produced by {@link #encodePosition(int, int)} 448 * @param floatValue the float value to set at the given encoded key 449 */ 450 public void updateFloat(int key, float floatValue) 451 { 452 if (key == 0 && hasZeroValue) { 453 //zeroChar = charValue; 454 zeroFloat = floatValue; 455 return; 456 } 457 458 int loc = locateKey(key); 459 // an identical key already exists 460 if (loc != -1) { 461// charValueTable[loc] = charValue; 462 floatValueTable[loc] = floatValue; 463 } 464 } 465 /** 466 * If and only if key is already present, this changes the char associated with it while leaving the float the same. 467 * @param key the encoded key as produced by {@link #encodePosition(int, int)} 468 * @param charValue the char value to set at the given encoded key 469 */ 470 public void updateChar(int key, char charValue) 471 { 472 if (key == 0 && hasZeroValue) { 473 zeroChar = charValue; 474 //zeroFloat = floatValue; 475 return; 476 } 477 478 int loc = locateKey(key); 479 // an identical key already exists 480 if (loc != -1) { 481 charValueTable[loc] = charValue; 482// floatValueTable[loc] = floatValue; 483 } 484 } 485 486 public void putAll(SparseTextMap map) { 487 ensureCapacity(map.size); 488 final int[] keys = map.keys.items; 489 final char[] chars = map.charValueTable; 490 final float[] floats = map.floatValueTable; 491 int k, loc; 492 for (int i = 0, n = map.keys.size; i < n; i++) { 493 k = keys[i]; 494 loc = map.locateKey(k); 495 put(k, chars[loc], floats[loc]); 496 } 497 498// ensureCapacity(map.size); 499// if (map.hasZeroValue) 500// put(0, map.zeroChar, map.zeroFloat); 501// final int[] keyTable = map.keyTable; 502// final char[] charValueTable = map.charValueTable; 503// final float[] floatValueTable = map.floatValueTable; 504// int k; 505// for (int i = 0, n = keyTable.length; i < n; i++) { 506// if ((k = keyTable[i]) != 0) 507// put(k, charValueTable[i], floatValueTable[i]); 508// } 509 510// for (Entry entry : map.entries()) 511// put(entry.key, entry.charValue, entry.floatValue); 512 } 513 514 /** 515 * Skips checks for existing keys. 516 */ 517 private void putResize(int key, char charValue, float floatValue) { 518 int[] keyTable = this.keyTable; 519 for (int i = fibonacci(key);; i = (i + 1) & mask) { 520 if (keyTable[i] == 0) { 521 keyTable[i] = key; 522 charValueTable[i] = charValue; 523 floatValueTable[i] = floatValue; 524 return; 525 } 526 } 527 } 528 529 /** 530 * @param x the x-component of the position to look up 531 * @param y the y-component of the position to look up 532 * @param defaultValue Returned if the key was not associated with a value. 533 * @return the char associated with the given position, or defaultValue if no char is associated 534 */ 535 public char getChar(int x, int y, char defaultValue) { 536 return getChar(encodePosition(x, y), defaultValue); 537 } 538 539 /** 540 * @param key the encoded key as produced by {@link #encodePosition(int, int)} 541 * @param defaultValue Returned if the key was not associated with a value. 542 * @return the char associated with the given key, or defaultValue if no char is associated 543 */ 544 public char getChar(int key, char defaultValue) { 545 if (key == 0) { 546 if (!hasZeroValue) return defaultValue; 547 return zeroChar; 548 } 549 final int placement = fibonacci(key); 550 for (int i = placement; ; i = i + 1 & mask) { 551 // empty space is available 552 if (keyTable[i] == 0) { 553 return defaultValue; 554 } 555 if (key == (keyTable[i])) { 556 return charValueTable[i]; 557 } 558 } 559 } 560 561 /** 562 * @param x the x-component of the position to look up 563 * @param y the y-component of the position to look up 564 * @param defaultValue Returned if the key was not associated with a value. 565 * @return the float associated with the given position, or defaultValue if no float is associated 566 */ 567 public float getFloat(int x, int y, float defaultValue) { 568 return getFloat(encodePosition(x, y), defaultValue); 569 } 570 571 /** 572 * @param key the encoded key as produced by {@link #encodePosition(int, int)} 573 * @param defaultValue Returned if the key was not associated with a value. 574 * @return the float associated with the given key, or defaultValue if no float is associated 575 */ 576 public float getFloat(int key, float defaultValue) { 577 if (key == 0) { 578 if (!hasZeroValue) return defaultValue; 579 return zeroFloat; 580 } 581 final int placement = fibonacci(key); 582 for (int i = placement; ; i = i + 1 & mask) { 583 // empty space is available 584 if (keyTable[i] == 0) { 585 return defaultValue; 586 } 587 if (key == (keyTable[i])) { 588 return floatValueTable[i]; 589 } 590 } 591 } 592 593 public void remove(int key) { 594 remove(key, '#'); 595 } 596 597 public char remove(int key, char defaultValue) { 598 if (key == 0) { 599 if (!hasZeroValue) return defaultValue; 600 hasZeroValue = false; 601 size--; 602 keys.removeValue(0); 603 return zeroChar; 604 } 605 606 int loc = locateKey(key); 607 if (loc == -1) { 608 return defaultValue; 609 } 610 keys.removeValue(key); 611 final int[] keyTable = this.keyTable; 612 final float[] floatValueTable = this.floatValueTable; 613 final char[] charValueTable = this.charValueTable; 614 char oldChar = charValueTable[loc]; 615 int next = loc + 1 & mask; 616 int placement; 617 while ((key = keyTable[next]) != 0) { 618 placement = fibonacci(key); 619 if((next - placement & mask) > (loc - placement & mask)) { 620 keyTable[loc] = key; 621 floatValueTable[loc] = floatValueTable[next]; 622 charValueTable[loc] = charValueTable[next]; 623 loc = next; 624 } 625 next = next + 1 & mask; 626 } 627 keyTable[loc] = 0; 628 --size; 629 return oldChar; 630 } 631 632 /** 633 * Reduces the size of the backing arrays to be the specified capacity or less. If the capacity is already less, nothing is 634 * done. If the map contains more items than the specified capacity, the next highest power of two capacity is used instead. 635 */ 636 public void shrink(int maximumCapacity) { 637 if (maximumCapacity < 0) throw new IllegalArgumentException("maximumCapacity must be >= 0: " + maximumCapacity); 638 if (size > maximumCapacity) maximumCapacity = size; 639 if (keyTable.length <= maximumCapacity) return; 640 resize(HashCommon.nextPowerOfTwo(maximumCapacity)); 641 } 642 643 /** 644 * Clears the map and reduces the size of the backing arrays to be the specified capacity if they are larger. 645 */ 646 public void clear(int maximumCapacity) { 647 if (keyTable.length <= maximumCapacity) { 648 clear(); 649 return; 650 } 651 hasZeroValue = false; 652 size = 0; 653 keys.clear(); 654 resize(maximumCapacity); 655 } 656 657 public void clear() { 658 if (size == 0) return; 659 keys.clear(); 660 Arrays.fill(keyTable, 0); 661 size = 0; 662 hasZeroValue = false; 663 } 664 665 /** 666 * Returns true if the specified char value is in the map. Note: this traverses the entire map and compares every 667 * value, which may be an expensive operation. 668 */ 669 public boolean containsCharValue(char value) { 670 if (hasZeroValue && zeroChar == value) return true; 671 int[] keyTable = this.keyTable; 672 char[] valueTable = this.charValueTable; 673 for (int i = keyTable.length; i-- > 0; ) 674 if (keyTable[i] != 0 && valueTable[i] == value) return true; 675 return false; 676 } 677 678 /** 679 * Returns true if the specified char value is in the map. Note: this traverses the entire map and compares every 680 * value, which may be an expensive operation. 681 */ 682 public boolean containsFloatValue(float value) { 683 if (hasZeroValue && zeroFloat == value) return true; 684 int[] keyTable = this.keyTable; 685 float[] valueTable = this.floatValueTable; 686 for (int i = keyTable.length; i-- > 0; ) 687 if (keyTable[i] != 0 && valueTable[i] == value) return true; 688 return false; 689 } 690 691 public boolean containsKey(int key) { 692 if (key == 0) return hasZeroValue; 693 return locateKey(key) != -1; 694 } 695 696 /** 697 * Returns the key for the specified char value, or notFound if it is not in the map. Note this traverses the 698 * entire map and compares every value, which may be an expensive operation. 699 */ 700 public int findKey(char value, int notFound) { 701 if (hasZeroValue && zeroChar == value) return 0; 702 int[] keyTable = this.keyTable; 703 char[] valueTable = this.charValueTable; 704 for (int i = keyTable.length; i-- > 0; ) 705 if (keyTable[i] != 0 && valueTable[i] == value) return keyTable[i]; 706 return notFound; 707 } 708 709 /** 710 * Returns the key for the specified float value, or notFound if it is not in the map. Note this traverses the 711 * entire map and compares every value, which may be an expensive operation. 712 */ 713 public int findKey(float value, int notFound) { 714 if (hasZeroValue && zeroFloat == value) return 0; 715 int[] keyTable = this.keyTable; 716 float[] valueTable = this.floatValueTable; 717 for (int i = keyTable.length; i-- > 0; ) 718 if (keyTable[i] != 0 && valueTable[i] == value) return keyTable[i]; 719 return notFound; 720 } 721 722 /** 723 * Increases the size of the backing array to accommodate the specified number of additional items. Useful before adding many 724 * items to avoid multiple backing array resizes. 725 */ 726 public void ensureCapacity(int additionalCapacity) { 727 if (additionalCapacity < 0) 728 throw new IllegalArgumentException("additionalCapacity must be >= 0: " + additionalCapacity); 729 int sizeNeeded = size + additionalCapacity; 730 keys.ensureCapacity(additionalCapacity); 731 if (sizeNeeded >= threshold) 732 resize(HashCommon.nextPowerOfTwo((int)Math.ceil(sizeNeeded / loadFactor))); 733 } 734 735 private void resize(int newSize) { 736 int oldCapacity = keyTable.length; 737 threshold = (int)(newSize * loadFactor); 738 mask = newSize - 1; 739 shift = Long.numberOfLeadingZeros(mask); 740 741 final int[] oldKeyTable = keyTable; 742 final float[] oldFloats = floatValueTable; 743 final char[] oldChars = charValueTable; 744 745 keyTable = new int[newSize]; 746 floatValueTable = new float[newSize]; 747 charValueTable = new char[newSize]; 748 749 if (size > 0) { 750 for (int i = 0; i < oldCapacity; i++) { 751 int key = oldKeyTable[i]; 752 if (key != 0) putResize(key, oldChars[i], oldFloats[i]); 753 } 754 } 755 } 756 757 public int hashCode() { 758 int h = 0; 759 if (hasZeroValue) { 760 h = NumberTools.floatToIntBits(zeroFloat) ^ zeroChar; 761 } 762 int[] keyTable = this.keyTable; 763 char[] charTable = this.charValueTable; 764 float[] floatTable = this.floatValueTable; 765 for (int i = 0, n = keyTable.length; i < n; i++) { 766 int key = keyTable[i]; 767 if (key != EMPTY) { 768 h += key ^ NumberTools.floatToIntBits(floatTable[i]); 769 h ^= charTable[i]; 770 } 771 } 772 return h; 773 } 774 775 public boolean equals(Object obj) { 776 if (obj == this) return true; 777 if (!(obj instanceof SparseTextMap)) return false; 778 SparseTextMap other = (SparseTextMap) obj; 779 if (other.size != size) return false; 780 if (other.hasZeroValue != hasZeroValue) return false; 781 if (hasZeroValue && (other.zeroChar != zeroChar || other.zeroFloat != zeroFloat)) { 782 return false; 783 } 784 int[] keyTable = this.keyTable; 785 char[] charTable = this.charValueTable; 786 float[] floatTable = this.floatValueTable; 787 for (int i = 0, n = keyTable.length; i < n; i++) { 788 int key = keyTable[i]; 789 if (key != EMPTY) { 790 char otherValue = other.getChar(key, '\0'); 791 if (otherValue == 0 && !other.containsKey(key) 792 || otherValue != charTable[i] 793 || other.getFloat(key, Float.NaN) != floatTable[i]) return false; 794 } 795 } 796 return true; 797 } 798 799 public String toString() { 800 if (size == 0) return "{}"; 801 StringBuilder buffer = new StringBuilder(32); 802 buffer.append('{'); 803 int[] keys = this.keys.items; 804 char[] charTable = this.charValueTable; 805 float[] floatTable = this.floatValueTable; 806 int n = size, loc, k = keys[0]; 807 if(k == 0) 808 StringKit.appendHex(buffer.append("0=").append(zeroChar).append(','), zeroFloat); 809 else 810 { 811 loc = locateKey(k); 812 StringKit.appendHex(buffer.append(k).append('=').append(charTable[loc]).append(','), floatTable[loc]); 813 } 814 815 for (int i = 1; i < n; i++) { 816 buffer.append("; "); 817 k = keys[i]; 818 if(k == 0) 819 StringKit.appendHex(buffer.append("0=").append(zeroChar).append(','), zeroFloat); 820 else 821 { 822 loc = locateKey(k); 823 StringKit.appendHex(buffer.append(k).append('=').append(charTable[loc]).append(','), floatTable[loc]); 824 } 825 } 826 buffer.append('}'); 827 return buffer.toString(); 828 } 829 830 public Iterator<Entry> iterator() { 831 return entries(); 832 } 833 834 /** 835 * Returns an iterator for the entries in the map. Remove is supported. Note that the same iterator instance is returned each 836 * time this method is called. Use the {@link Entries} constructor for nested or multithreaded iteration. 837 */ 838 public Entries entries() { 839 if (entries1 == null) { 840 entries1 = new Entries(this); 841 entries2 = new Entries(this); 842 } 843 if (!entries1.valid) { 844 entries1.reset(); 845 entries1.valid = true; 846 entries2.valid = false; 847 return entries1; 848 } 849 entries2.reset(); 850 entries2.valid = true; 851 entries1.valid = false; 852 return entries2; 853 } 854 855 /** 856 * Returns an iterator for the values in the map. Remove is supported. Note that the same iterator instance is returned each 857 * time this method is called. Use the {@link Entries} constructor for nested or multithreaded iteration. 858 */ 859 public CharValues charValues() { 860 if (charValues1 == null) { 861 charValues1 = new CharValues(this); 862 charValues2 = new CharValues(this); 863 } 864 if (!charValues1.valid) { 865 charValues1.reset(); 866 charValues1.valid = true; 867 charValues2.valid = false; 868 return charValues1; 869 } 870 charValues2.reset(); 871 charValues2.valid = true; 872 charValues1.valid = false; 873 return charValues2; 874 } 875 876 /** 877 * Returns an iterator for the values in the map. Remove is supported. Note that the same iterator instance is returned each 878 * time this method is called. Use the {@link Entries} constructor for nested or multithreaded iteration. 879 */ 880 public FloatValues floatValues() { 881 if (floatValues1 == null) { 882 floatValues1 = new FloatValues(this); 883 floatValues2 = new FloatValues(this); 884 } 885 if (!floatValues1.valid) { 886 floatValues1.reset(); 887 floatValues1.valid = true; 888 floatValues2.valid = false; 889 return floatValues1; 890 } 891 floatValues2.reset(); 892 floatValues2.valid = true; 893 floatValues1.valid = false; 894 return floatValues2; 895 } 896 897 /** 898 * Returns an iterator for the keys in the map. Remove is supported. Note that the same iterator instance is returned each time 899 * this method is called. Use the {@link Entries} constructor for nested or multithreaded iteration. 900 */ 901 public Keys keys() { 902 if (keys1 == null) { 903 keys1 = new Keys(this); 904 keys2 = new Keys(this); 905 } 906 if (!keys1.valid) { 907 keys1.reset(); 908 keys1.valid = true; 909 keys2.valid = false; 910 return keys1; 911 } 912 keys2.reset(); 913 keys2.valid = true; 914 keys1.valid = false; 915 return keys2; 916 } 917 918 static public class Entry { 919 public int key; 920 public char charValue; 921 public float floatValue; 922 923 public String toString() { 924 return key + "=" + charValue + "," + floatValue; 925 } 926 } 927 928 static private class MapIterator { 929 public boolean hasNext; 930 931 final SparseTextMap map; 932 final IntVLA keys; 933 int nextIndex, currentIndex; 934 boolean valid = true; 935 936 public MapIterator(SparseTextMap map) { 937 this.map = map; 938 this.keys = map.keys; 939 reset(); 940 } 941 942 public void reset() { 943 currentIndex = -1; 944 nextIndex = 0; 945 hasNext = map.size > 0; 946 } 947 } 948 949 static public class Entries extends MapIterator implements Iterable<Entry>, Iterator<Entry> { 950 private final Entry entry = new Entry(); 951 952 public Entries(SparseTextMap map) { 953 super(map); 954 } 955 956 /** 957 * Note the same entry instance is returned each time this method is called. 958 */ 959 public Entry next() { 960 if (!hasNext) throw new NoSuchElementException(); 961 if (!valid) throw new GdxRuntimeException("#iterator() cannot be used nested."); 962 currentIndex = nextIndex; 963 entry.key = keys.get(nextIndex); 964 if(entry.key == 0) 965 { 966 entry.charValue = map.zeroChar; 967 entry.floatValue = map.zeroFloat; 968 } 969 else { 970 int loc = map.locateKey(entry.key); 971 entry.charValue = map.charValueTable[loc]; 972 entry.floatValue = map.floatValueTable[loc]; 973 } 974 nextIndex++; 975 hasNext = nextIndex < map.size; 976 return entry; 977 } 978 979 public boolean hasNext() { 980 if (!valid) throw new GdxRuntimeException("#iterator() cannot be used nested."); 981 return hasNext; 982 } 983 984 public Iterator<Entry> iterator() { 985 return this; 986 } 987 988 public void remove () { 989 if (currentIndex < 0) 990 throw new IllegalStateException("next must be called before remove."); 991 map.remove(entry.key); 992 nextIndex--; 993 currentIndex = -1; 994 } 995 } 996 997 static public class CharValues extends MapIterator { 998 public CharValues(SparseTextMap map) { 999 super(map); 1000 } 1001 1002 public boolean hasNext() { 1003 if (!valid) throw new GdxRuntimeException("#iterator() cannot be used nested."); 1004 return hasNext; 1005 } 1006 1007 public char next() { 1008 if (!hasNext) throw new NoSuchElementException(); 1009 if (!valid) throw new GdxRuntimeException("#iterator() cannot be used nested."); 1010 char value = map.getChar(keys.get(nextIndex), '\0'); 1011 currentIndex = nextIndex; 1012 nextIndex++; 1013 hasNext = nextIndex < map.size; 1014 return value; 1015 } 1016 1017 /** 1018 * Returns a new array containing the remaining values. 1019 */ 1020 public char[] toArray() { 1021 char[] array = new char[map.size - nextIndex]; 1022 int idx = 0; 1023 while (hasNext && idx < array.length) 1024 array[idx++] = next(); 1025 return array; 1026 } 1027 } 1028 1029 static public class FloatValues extends MapIterator { 1030 public FloatValues(SparseTextMap map) { 1031 super(map); 1032 } 1033 1034 public boolean hasNext() { 1035 if (!valid) throw new GdxRuntimeException("#iterator() cannot be used nested."); 1036 return hasNext; 1037 } 1038 1039 public float next() { 1040 if (!hasNext) throw new NoSuchElementException(); 1041 if (!valid) throw new GdxRuntimeException("#iterator() cannot be used nested."); 1042 float value = map.getFloat(keys.get(nextIndex), '\0'); 1043 currentIndex = nextIndex; 1044 nextIndex++; 1045 hasNext = nextIndex < map.size; 1046 return value; 1047 } 1048 1049 /** 1050 * Returns a new array containing the remaining values. 1051 */ 1052 public float[] toArray() { 1053 float[] array = new float[map.size - nextIndex]; 1054 int idx = 0; 1055 while (hasNext && idx < array.length) 1056 array[idx++] = next(); 1057 return array; 1058 } 1059 } 1060 1061 static public class Keys extends MapIterator { 1062 public Keys(SparseTextMap map) { 1063 super(map); 1064 } 1065 1066 public boolean hasNext() { 1067 if (!valid) throw new GdxRuntimeException("#iterator() cannot be used nested."); 1068 return hasNext; 1069 } 1070 1071 public int next() { 1072 if (!hasNext) throw new NoSuchElementException(); 1073 if (!valid) throw new GdxRuntimeException("#iterator() cannot be used nested."); 1074 int key = keys.get(nextIndex); 1075 currentIndex = nextIndex; 1076 nextIndex++; 1077 hasNext = nextIndex < map.size; 1078 return key; 1079 } 1080 1081 /** 1082 * Returns a new array containing the remaining keys. 1083 */ 1084 public int[] toArray() { 1085 int[] array = new int[map.size - nextIndex]; 1086 int idx = 0; 1087 while (hasNext && idx < array.length) 1088 array[idx++] = next(); 1089 return array; 1090 } 1091 } 1092}