001package squidpony.squidmath; 002 003import squidpony.ArrayTools; 004 005import java.io.Serializable; 006import java.util.Iterator; 007import java.util.SortedSet; 008 009/** 010 * An ordered bidirectional map-like data structure, with unique A keys and unique B keys updated together like a map 011 * that can be queried by A keys, B keys, or int indices. Does not implement any interfaces that you would expect for a 012 * data structure, because almost every method it has needs to specify whether it applies to A or B items, but you can 013 * get collections that implement SortedSet of its A or B keys. 014 * <br> 015 * Called K2 because it has 2 key sets; other collections can have other keys or have values, like K2V1. 016 * Created by Tommy Ettinger on 10/25/2016. 017 */ 018public class K2<A, B> implements Serializable { 019 private static final long serialVersionUID = 1L; 020 public Arrangement<A> keysA; 021 public Arrangement<B> keysB; 022 023 /** 024 * Constructs an empty K2. 025 */ 026 public K2() 027 { 028 this(Arrangement.DEFAULT_INITIAL_SIZE, Arrangement.DEFAULT_LOAD_FACTOR); 029 } 030 031 /** 032 * Constructs a K2 with the expected number of indices to hold (the number of A and number of B items is always 033 * the same, and this will be more efficient if expected is greater than that number). 034 * @param expected 035 */ 036 public K2(int expected) 037 { 038 this(expected, Arrangement.DEFAULT_LOAD_FACTOR); 039 } 040 041 /** 042 * Constructs a K2 with the expected number of indices to hold (the number of A and number of B items is always 043 * the same, and this will be more efficient if expected is greater than that number) and the load factor to use, 044 * between 0.1f and 0.8f usually (using load factors higher than 0.8f can cause problems). 045 * @param expected the amount of indices (the count of A items is the same as the count of B items) this should hold 046 * @param f the load factor, probably between 0.1f and 0.8f 047 */ 048 public K2(int expected, float f) 049 { 050 keysA = new Arrangement<>(expected, f); 051 keysB = new Arrangement<>(expected, f); 052 } 053 054 /** 055 * Constructs a K2 with the expected number of indices to hold (the number of A and number of B items are always 056 * equal, and this will be more efficient if expected is greater than that number), the load factor to use, 057 * between 0.1f and 0.8f usually (using load factors higher than 0.8f can cause problems), and two IHasher 058 * implementations, such as {@link CrossHash#generalHasher}, that will be used to hash and compare for equality with 059 * A keys and B keys, respectively. Specifying an IHasher is usually needed if your keys are arrays (there are 060 * existing implementations for 1D arrays of all primitive types, CharSequence, and Object in CrossHash), or if you 061 * want hashing by identity and reference equality (which would use {@link CrossHash#identityHasher}, and might be 062 * useful if keys are mutable). Other options are possible with custom IHashers, like hashing Strings but ignoring, 063 * or only considering, a certain character for the hash and equality checks. 064 * @param expected the amount of indices (the count of A items is the same as the count of B items) this should hold 065 * @param f the load factor, probably between 0.1f and 0.8f 066 * @param hasherA an implementation of CrossHash.IHasher meant for A keys 067 * @param hasherB an implementation of CrossHash.IHasher meant for B keys 068 */ 069 public K2(int expected, float f, CrossHash.IHasher hasherA, CrossHash.IHasher hasherB) 070 { 071 keysA = new Arrangement<>(expected, f, hasherA); 072 keysB = new Arrangement<>(expected, f, hasherB); 073 } 074 075 /** 076 * Constructs a K2 from a pair of Iterables that will be processed in pairs, adding a unique A from aKeys if and 077 * only if it can also add a unique B from bKeys, otherwise skipping that pair. 078 * @param aKeys an Iterable of A that should all be unique 079 * @param bKeys an Iterable of B that should all be unique 080 */ 081 public K2(Iterable<? extends A> aKeys, Iterable<? extends B> bKeys) 082 { 083 keysA = new Arrangement<>(); 084 keysB = new Arrangement<>(); 085 if(aKeys != null && bKeys != null) 086 putAll(aKeys, bKeys); 087 } 088 089 public K2(K2<? extends A, ? extends B> other) 090 { 091 if(other == null) 092 { 093 keysA = new Arrangement<>(); 094 keysB = new Arrangement<>(); 095 } 096 else 097 { 098 keysA = new Arrangement<>(other.keysA); 099 keysB = new Arrangement<>(other.keysB); 100 } 101 } 102 103 public K2(Arrangement<A> aItems, Arrangement<B> bItems) 104 { 105 if(aItems == null || bItems == null) 106 { 107 keysA = new Arrangement<>(); 108 keysB = new Arrangement<>(); 109 } 110 else 111 { 112 int amt = Math.min(aItems.size, bItems.size); 113 keysA = aItems.take(amt); 114 keysB = bItems.take(amt); 115 } 116 } 117 /** 118 * Returns true if this contains the A, key, in its collection of A items. 119 * @param key the A to check the presence of 120 * @return true if key is present in this; false otherwise 121 */ 122 public boolean containsA(A key) { return keysA.containsKey(key); } 123 /** 124 * Returns true if this contains the B, key, in its collection of B items. 125 * @param key the B to check the presence of 126 * @return true if key is present in this; false otherwise 127 */ 128 public boolean containsB(B key) { return keysB.containsKey(key); } 129 130 /** 131 * Returns true if index is between 0 (inclusive) and {@link #size()} (exclusive), or false otherwise. 132 * @param index the index to check 133 * @return true if index is a valid index in the ordering of this K2 134 */ 135 public boolean containsIndex(int index) { return keysA.containsValue(index); } 136 137 /** 138 * Given an A object key, finds the position in the ordering that A has, or -1 if key is not present. 139 * Unlike {@link java.util.List#indexOf(Object)}, this runs in constant time. 140 * @param key the A to find the position of 141 * @return the int index of key in the ordering, or -1 if it is not present 142 */ 143 public int indexOfA(Object key) 144 { 145 return keysA.getInt(key); 146 } 147 /** 148 * Given a B object key, finds the position in the ordering that B has, or -1 if key is not present. 149 * Unlike {@link java.util.List#indexOf(Object)}, this runs in constant time. 150 * @param key the B to find the position of 151 * @return the int index of key in the ordering, or -1 if it is not present 152 */ 153 public int indexOfB(Object key) 154 { 155 return keysB.getInt(key); 156 } 157 158 /** 159 * Given an int index, finds the associated A key (using index as a point in the ordering). 160 * @param index an int index into this K2 161 * @return the A object with index for its position in the ordering, or null if index was invalid 162 */ 163 public A getAAt(int index) 164 { 165 return keysA.keyAt(index); 166 } 167 /** 168 * Given an int index, finds the associated B key (using index as a point in the ordering). 169 * @param index an int index into this K2 170 * @return the B object with index for its position in the ordering, or null if index was invalid 171 */ 172 public B getBAt(int index) 173 { 174 return keysB.keyAt(index); 175 } 176 177 /** 178 * Given an A object, finds the associated B object (it will be at the same point in the ordering). 179 * @param key an A object to use as a key 180 * @return the B object associated with key, or null if key was not present 181 */ 182 public B getBFromA(Object key) 183 { 184 return keysB.keyAt(keysA.getInt(key)); 185 } 186 187 /** 188 * Given a B object, finds the associated A object (it will be at the same point in the ordering). 189 * @param key a B object to use as a key 190 * @return the A object associated with key, or null if key was not present 191 */ 192 public A getAFromB(Object key) 193 { 194 return keysA.keyAt(keysB.getInt(key)); 195 } 196 197 /** 198 * Gets a random A from this K2 using the given IRNG. 199 * @param random generates a random index to get an A with 200 * @return a randomly chosen A, or null if this is empty 201 */ 202 public A randomA(IRNG random) 203 { 204 return keysA.randomKey(random); 205 } 206 207 /** 208 * Gets a random B from this K2 using the given IRNG. 209 * @param random generates a random index to get a B with 210 * @return a randomly chosen B, or null if this is empty 211 */ 212 public B randomB(IRNG random) 213 { 214 return keysB.randomKey(random); 215 } 216 /** 217 * Changes an existing A key, {@code past}, to another A key, {@code future}, if past exists in this K2 218 * and future does not yet exist in this K2. This will retain past's point in the ordering for future, so 219 * the associated other key(s) will still be associated in the same way. 220 * @param past an A key, that must exist in this K2's A keys, and will be changed 221 * @param future an A key, that cannot currently exist in this K2's A keys, but will if this succeeds 222 * @return this for chaining 223 */ 224 public K2<A, B> alterA(A past, A future) 225 { 226 if(keysA.containsKey(past) && !keysA.containsKey(future)) 227 keysA.alter(past, future); 228 return this; 229 } 230 231 /** 232 * Changes an existing B key, {@code past}, to another B key, {@code future}, if past exists in this K2 233 * and future does not yet exist in this K2. This will retain past's point in the ordering for future, so 234 * the associated other key(s) will still be associated in the same way. 235 * @param past a B key, that must exist in this K2's B keys, and will be changed 236 * @param future a B key, that cannot currently exist in this K2's B keys, but will if this succeeds 237 * @return this for chaining 238 */ 239 public K2<A, B> alterB(B past, B future) 240 { 241 if(keysB.containsKey(past) && !keysB.containsKey(future)) 242 keysB.alter(past, future); 243 return this; 244 } 245 246 /** 247 * Changes the A key at {@code index} to another A key, {@code future}, if index is valid and future does not 248 * yet exist in this K2. The position in the ordering for future will be the same as index, and the same 249 * as the key this replaced, if this succeeds, so the other key(s) at that position will still be associated in 250 * the same way. 251 * @param index a position in the ordering to change; must be at least 0 and less than {@link #size()} 252 * @param future an A key, that cannot currently exist in this K2's A keys, but will if this succeeds 253 * @return this for chaining 254 */ 255 public K2<A, B> alterAAt(int index, A future) 256 { 257 if(!keysA.containsKey(future) && index >= 0 && index < keysA.size) 258 keysA.alter(keysA.keyAt(index), future); 259 return this; 260 } 261 262 263 /** 264 * Changes the B key at {@code index} to another B key, {@code future}, if index is valid and future does not 265 * yet exist in this K2. The position in the ordering for future will be the same as index, and the same 266 * as the key this replaced, if this succeeds, so the other key(s) at that position will still be associated in 267 * the same way. 268 * @param index a position in the ordering to change; must be at least 0 and less than {@link #size()} 269 * @param future a B key, that cannot currently exist in this K2's B keys, but will if this succeeds 270 * @return this for chaining 271 */ 272 public K2<A, B> alterBAt(int index, B future) 273 { 274 if(!keysB.containsKey(future) && index >= 0 && index < keysB.size) 275 keysB.alter(keysB.keyAt(index), future); 276 return this; 277 } 278 /** 279 * Adds an A key and a B key at the same point in the ordering (the end) to this K2. Neither parameter can be 280 * present in this collection before this is called. If you want to change or update an existing key, use 281 * {@link #alterA(Object, Object)} or {@link #alterB(Object, Object)}. 282 * @param a an A key to add; cannot already be present 283 * @param b a B key to add; cannot already be present 284 * @return true if this collection changed as a result of this call 285 */ 286 public boolean put(A a, B b) 287 { 288 if(!keysA.containsKey(a) && !keysB.containsKey(b)) 289 { 290 keysA.add(a); 291 keysB.add(b); 292 return true; 293 } 294 return false; 295 } 296 297 /** 298 * Puts all unique A and B keys in {@code aKeys} and {@code bKeys} into this K2 at the end. If an A in aKeys or a B 299 * in bKeys is already present when this would add one, this will not put the A and B keys at that point in the 300 * iteration order, and will place the next unique A and B it finds in the arguments at that position instead. 301 * @param aKeys an Iterable or Collection of A keys to add; should all be unique (like a Set) 302 * @param bKeys an Iterable or Collection of B keys to add; should all be unique (like a Set) 303 * @return true if this collection changed as a result of this call 304 */ 305 public boolean putAll(Iterable<? extends A> aKeys, Iterable<? extends B> bKeys) 306 { 307 if(aKeys == null || bKeys == null) return false; 308 Iterator<? extends A> aIt = aKeys.iterator(); 309 Iterator<? extends B> bIt = bKeys.iterator(); 310 boolean changed = false; 311 while (aIt.hasNext() && bIt.hasNext()) 312 { 313 changed = put(aIt.next(), bIt.next()) || changed; 314 } 315 return changed; 316 } 317 /** 318 * Puts all unique A and B keys in {@code other} into this K2, respecting other's ordering. If an A or a B in other 319 * is already present when this would add one, this will not put the A and B keys at that point in the iteration 320 * order, and will place the next unique A and B it finds in the arguments at that position instead. 321 * @param other another K2 collection with the same A and B types 322 * @return true if this collection changed as a result of this call 323 */ 324 public boolean putAll(K2<? extends A, ? extends B> other) 325 { 326 if(other == null) return false; 327 boolean changed = false; 328 int sz = other.size(); 329 for (int i = 0; i < sz; i++) { 330 changed = put(other.getAAt(i), other.getBAt(i)) || changed; 331 } 332 return changed; 333 } 334 335 /** 336 * Adds an A key and a B key at the given index in the ordering to this K2. Neither a nor b can be 337 * present in this collection before this is called. If you want to change or update an existing key, use 338 * {@link #alterA(Object, Object)} or {@link #alterB(Object, Object)}. The index this is given should be at 339 * least 0 and no greater than {@link #size()}. 340 * @param index the point in the ordering to place a and b into; later entries will be shifted forward 341 * @param a an A key to add; cannot already be present 342 * @param b a B key to add; cannot already be present 343 * @return true if this collection changed as a result of this call 344 */ 345 public boolean putAt(int index, A a, B b) 346 { 347 if(!keysA.containsKey(a) && !keysB.containsKey(b)) 348 { 349 keysA.addAt(index, a); 350 keysB.addAt(index, b); 351 return true; 352 } 353 return false; 354 } 355 356 /** 357 * Removes a given A key, if {@code removing} exists in this K2's A keys, and also removes any keys 358 * associated with its point in the ordering. 359 * @param removing the A key to remove 360 * @return this for chaining 361 */ 362 public K2<A, B> removeA(A removing) 363 { 364 keysB.removeAt(keysA.removeInt(removing)); 365 return this; 366 } 367 /** 368 * Removes a given B key, if {@code removing} exists in this K2's B keys, and also removes any keys 369 * associated with its point in the ordering. 370 * @param removing the B key to remove 371 * @return this for chaining 372 */ 373 public K2<A, B> removeB(B removing) 374 { 375 keysA.removeAt(keysB.removeInt(removing)); 376 return this; 377 } 378 /** 379 * Removes a given point in the ordering, if {@code index} is at least 0 and less than {@link #size()}. 380 * @param index the position in the ordering to remove 381 * @return this for chaining 382 */ 383 public K2<A, B> removeAt(int index) 384 { 385 keysA.removeAt(index); 386 keysB.removeAt(index); 387 return this; 388 } 389 390 /** 391 * Reorders this K2 using {@code ordering}, which have the same length as this K2's {@link #size()} 392 * and can be generated with {@link ArrayTools#range(int)} (which, if applied, would produce no 393 * change to the current ordering), {@link IRNG#randomOrdering(int)} (which gives a random ordering, and if 394 * applied immediately would be the same as calling {@link #shuffle(IRNG)}), or made in some other way. If you 395 * already have an ordering and want to make a different ordering that can undo the change, you can use 396 * {@link ArrayTools#invertOrdering(int[])} called on the original ordering. 397 * @param ordering an int array or vararg that should contain each int from 0 to {@link #size()} (or less) 398 * @return this for chaining 399 */ 400 public K2<A, B> reorder(int... ordering) 401 { 402 keysA.reorder(ordering); 403 keysB.reorder(ordering); 404 return this; 405 } 406 407 /** 408 * Generates a random ordering with rng and applies the same ordering to all kinds of keys this has; they will 409 * maintain their current association to other keys but their ordering/indices will change. 410 * @param rng an IRNG to produce the random ordering this will use 411 * @return this for chaining 412 */ 413 public K2<A, B> shuffle(IRNG rng) 414 { 415 int[] ordering = rng.randomOrdering(keysA.size); 416 keysA.reorder(ordering); 417 keysB.reorder(ordering); 418 return this; 419 } 420 421 /** 422 * Creates a new iterator over the A keys this holds. This can be problematic for garbage collection if called very 423 * frequently; it may be better to access items by index (which also lets you access other keys associated with that 424 * index) using {@link #getAAt(int)} in a for(int i=0...) loop. 425 * @return a newly-created iterator over this K2's A keys 426 */ 427 public Iterator<A> iteratorA() 428 { 429 return keysA.iterator(); 430 } 431 /** 432 * Creates a new iterator over the B keys this holds. This can be problematic for garbage collection if called very 433 * frequently; it may be better to access items by index (which also lets you access other keys associated with that 434 * index) using {@link #getBAt(int)} in a for(int i=0...) loop. 435 * @return a newly-created iterator over this K2's B keys 436 */ 437 public Iterator<B> iteratorB() 438 { 439 return keysB.iterator(); 440 } 441 442 /** 443 * Gets and caches the A keys as a Collection that implements SortedSet (and so also implements Set). This Set is 444 * shared with this collection; it is not a copy. 445 * @return the A keys as a SortedSet 446 */ 447 public SortedSet<A> getSetA() { 448 return keysA.keySet(); 449 } 450 /** 451 * Gets and caches the B keys as a Collection that implements SortedSet (and so also implements Set). This Set is 452 * shared with this collection; it is not a copy. 453 * @return the B keys as a SortedSet 454 */ 455 public SortedSet<B> getSetB() { 456 return keysB.keySet(); 457 } 458 459 /** 460 * Returns a separate (shallow) copy of the set of A keys as an {@link OrderedSet}. 461 * To be called sparingly, since this allocates a new OrderedSet instead of reusing one. This can be useful if you 462 * were going to copy the set produced by {@link #getSetA()} anyway. 463 * @return the A keys as an OrderedSet 464 */ 465 public OrderedSet<A> getOrderedSetA() { 466 return keysA.keysAsOrderedSet(); 467 } 468 469 /** 470 * Returns a separate (shallow) copy of the set of B keys as an {@link OrderedSet}. 471 * To be called sparingly, since this allocates a new OrderedSet instead of reusing one. This can be useful if you 472 * were going to copy the set produced by {@link #getSetB()} anyway. 473 * @return the B keys as an OrderedSet 474 */ 475 public OrderedSet<B> getOrderedSetB() { 476 return keysB.keysAsOrderedSet(); 477 } 478 479 public int keyCount() { 480 return 2; 481 } 482 public int valueCount() { 483 return 0; 484 } 485 486 public int size() { 487 return keysA.size; 488 } 489 490 public boolean isEmpty() 491 { 492 return keysA.isEmpty(); 493 } 494 495}