Making libGDX's data structures implement JDK interfaces
Some background, first... libGDX has its own data structures, and they're mostly nice to work with. They have fast iteration by
reusing iterators, they are designed to use low memory (both in the way the hashed maps and sets are designed and by allowing
primitive data types for many data structures), and they have some nice features that aren't present in all standard libraries,
like optional insertion-ordering. The problem with libGDX's data structures is that they are extremely limited in what interfaces
they implement, typically implementing no more than java.io.Serializable and java.lang.Iterable. They also are limited to Java
6 or 7 features, despite Java 8 features being available on Android and GWT for some time now, and even reaching iOS soon, if not
already. So what is this? It is a redo of libGDX's data structures so that they implement common JDK interfaces like
java.util.Map, java.util.List, and java.util.Set, plus their parts that can't implement generic interfaces use interfaces
defined here, such as PrimitiveCollection, Ordered, FloatIterator, LongComparator, and so on. It also sharply increases
the number of primitive-backed maps; they don't implement java.util.Map, but often implement other interfaces here. As an
example, com.github.tommyettinger.ds.IntLongOrderedMap implements com.github.tommyettinger.ds.Ordered.OfInt, which specifies
that the order of items (keys here) is represented by a com.github.tommyettinger.ds.IntList containing those keys.
You use jdkgdxds much like the standard JDK collections, just extended for primitive types. The types of data structure offered
here are lists (array-backed, like ArrayList), deques (double-ended queues, like ArrayDeque but also allowing access inside
the deque), sets (allowing only unique items, and coming in unordered and insertion-ordered varieties), maps (allowing unique keys
associated with values, and also coming in unordered and insertion-ordered varieties), bags (unordered lists, with fast removal
but unpredictable iteration order) and some extra types. The Object-based
classes are generic, centered around com.github.tommyettinger.ds.ObjectList, com.github.tommyettinger.ds.ObjectDeque,
com.github.tommyettinger.ds.ObjectSet, and com.github.tommyettinger.ds.ObjectObjectMap; ObjectOrderedSet and
ObjectObjectOrderedMap are also here and extend the other Set and Map. These are effectively replacements for
com.badlogic.gdx.utils.Array, com.badlogic.gdx.utils.Queue, com.badlogic.gdx.utils.ObjectSet,
com.badlogic.gdx.utils.ObjectMap, com.badlogic.gdx.utils.OrderedSet, and com.badlogic.gdx.utils.OrderedMap. As nice as it
would be to just call these by the same names (except Array, that one's just confusing), we have other kinds of Object-keyed Maps,
and other kinds of insertion-ordered Maps, so ObjectMap is now ObjectObjectMap because it has Object keys and Object values,
while OrderedMap is now ObjectObjectOrderedMap, because of the same reason. Primitive-backed collections support int
and long keys, and int, long, or float values; all primitive types are available for lists, deques, and bags. So, there's
IntSet and LongSet, with ordered variants IntOrderedSet and LongOrderedSet, while their map counterparts are more
numerous. Most of the primitive lists are very similar, only changing the numeric type, but there are some small changes for
CharList (which doesn't define math operations on its items) and BooleanList (which defines logical operations but not math
ones). The deques don't currently implement math operations on their items. Each of the bag classes extends a list class, and
changes its behavior on certain operations (like remove(), which takes O(1) time instead of O(n), but rearranges the items),
while keeping the other operations mostly the same. As for the maps...
There's IntFloatMap, IntFloatOrderedMap, IntIntMap, IntIntOrderedMap, IntLongMap, IntLongOrderedMap,
IntObjectMap, IntObjectOrderedMap, LongFloatMap, LongFloatOrderedMap, LongIntMap, LongIntOrderedMap,
LongLongMap, LongLongOrderedMap, LongObjectMap, and LongObjectOrderedMap, so I hope that's enough. Then again, there's
still ObjectFloatMap, ObjectFloatOrderedMap, ObjectIntMap, ObjectIntOrderedMap, ObjectLongMap, and
ObjectLongOrderedMap for the primitive-valued maps with Object keys. There's a CaseInsensitiveMap (and a
CaseInsensitiveOrderedMap) that requires CharSequence keys (such as String or StringBuilder), but treats them as
case-insensitive, and allows a generic Object type for its values. There's IdentityObjectMap and IdentityObjectOrderedMap,
which compare keys by reference identity (not by equals()) and hash their keys using their identity hash code. There's the
unusual HolderSet and HolderOrderedSet, which take an "extractor" function when constructed and use it to hash items by an
extracted value; this lets you, for example, make a HolderSet of "Employee" objects and look up a full Employee given only their
UUID. In that case, an Employee's value could change, and the result of hashCode() on an Employee would change, but as long as the
UUID of the Employee stays the same, the same Employee will be found by methods like get() and contains(). NumberedSet wraps
an ObjectIntOrderedMap and makes it so that Object keys can be looked up by index (using the standard ordered set methods like
getAt()), but also so that their indexOf() method runs in constant time instead of linear time. This is at the expense of
slower removal from the middle of the NumberedSet; that class doesn't implement insertion in the middle of the NumberedSet either.
There's also a close relative of libGDX's BinaryHeap class, but the one here implements the JDK's Queue.
The library includes expanded interfaces for these to implement, like the aforementioned Ordered interface,
PrimitiveCollection is akin to Java 8's PrimitiveIterator, some float-based versions of primitive specializations where
the JDK only offers int, long, and double, and primitive Comparators (which are Java 8 FunctionalInterfaces).
You can extend essentially all classes in jdkgdxds, and it's meant to be friendlier to inherit from than the libGDX collections.
The Object-keyed maps and sets have protected place() and equate() methods to allow changing the behavior of hashing (with
place()) and equality (with equate()). If you, for instance, wanted to use char[] as a key type in a map, the normal
behavior of an array in a hashed collection like a map or set is basically unusable. Arrays are compared by reference rather than
by value, so you would need the exact char[] you had put in to get a value out. They're also hashed by identity, which means
more than just the equality comparison needs to change. Thankfully, in jdkgdxds you can override place() to
return Arrays.hashCode((char[])item) & mask; and equate() to return Objects.deepEquals(left, right);; this uses standard JDK
methods to hash and compare arrays, and will work as long as you don't edit any array keys while they are in the map. There are
other potential uses for this extensibility, like the case-insensitive CharSequence comparison that CaseInsensitiveMap and
related classes use, or some form of fuzzy equality for float or double keys.
Most of the ordered data structures now allow addAll() or putAll() to specify a range with a starting index and count of how
many items to copy from the data structure passed as a parameter (often some kind of Ordered). This also optionally takes a
starting index to add the range at in the order. When constructing one of these ordered data structures with a copy constructor,
you usually have the option to copy only a range of the data structure you are copying. Similarly, there's often a removeRange()
method, also present on all ordered types except deques (and it takes a start and end index, rather than a start index and count,
which imitates the method by that name in the JDK, not the similar one in libGDX's Array class). All of these are intended to be
useful for imitating disjoint sets, and other ways of isolating part of a data structure. You might shuffle an ObjectList, then
make two more distinct ObjectLists by copying different ranges from the shuffled "deck," for example.
An oddity in libGDX's Array classes (such as IntArray, FloatArray, and of course Array) is that their removeAll() method doesn't
act like removeAll() in the JDK List interface. In List.removeAll(Collection), when the Collection c contains an item even
once, every occurrence of that item is removed from the List. In libGDX, if an item appears once in the parameter, it is removed
once from the Array; similarly, if it appears twice, it is removed twice. Here, we have the List behavior for removeAll(), but
also keep the Array behavior in the newly-added removeEach().
Here, we rely on some shared common functionality in two other libraries (by the same author). Digital has core math code, including the BitConversion and Base classes that were here earlier. Funderby provides functional interfaces for primitive types, with a rather large amount of total combinations. Juniper has the random number generators that also used to be here. Having these as external libraries allows someone's LibraryA that really only needs the core math from digital to only use that, but for projects that need both jdkgdxds and LibraryA, the shared dependency won't be duplicated.
Versions of jdkgdxds before 1.0.2 used "Fibonacci hashing" to mix hashCode() results. This involved multiplying the hash by a
specific constant (2 to the 64, divided by the golden ratio) and shifting the resulting bits so only an upper portion was used
(its size depended on the size of the backing table or tables). This works well in most situations, but a few were found where it
had catastrophically bad performance. The easiest case to reproduce was much like this bug in Rust's standard library,
relating to reinserting already-partially-colliding keys in a large map or set. Starting in 1.0.2, we take a different route to
mixing hashCode() results -- instead of multiplying by a specific constant every time, we change the constant every time we need
to resize the backing tables. Everything else is the same. This simple change allows one test, inserting 2 million
specifically-chosen Strings, to complete in under 2 seconds, when without the change, it wouldn't complete given 77 minutes (a
speedup of over 3 orders of magnitude). In 1.1.1, the strategy for picking a constant changed, and now the constant is picked from
a table of 512 known-good multipliers, appropriately called Utilities.GOOD_MULTIPLIERS. You can change the behavior of a map or
set when it chooses its hashMultiplier by overriding resize(int).
You have two options: Maven Central for stable releases, or JitPack to select a commit of your choice to build.
Maven Central uses the Gradle dependency:
api 'com.github.tommyettinger:jdkgdxds:1.3.0'
You can use implementation instead of api if you don't use the java-library plugin.
It does not need any additional repository to be specified in most cases; if it can't be found, you may need the repository
mavenCentral() or to remove the mavenLocal() repo. Jdkgdxds has dependencies on digital (which provides
common math code meant for use by multiple projects), funderby (Java 8 functional interfaces for primitive types), and for
annotations only, checker-qual (the project GitHub page is here.). The
version for the digital dependency is 0.2.0 (you can specify it manually with the core dependency
api "com.github.tommyettinger:digital:0.2.0"). Funderby has only changed a bit since its initial release, and is on version
0.1.1 (you can specify it manually with implementation "com.github.tommyettinger:funderby:0.1.1"). The version for
checker-qual is 3.32.0 , and is expected to go up often because checker-qual rather-frequently updates to handle JDK changes.
Earlier versions of jdkgdxds used jsr305 instead of checker-qual, which had some potential problems on Java 9 and up (not to
mention that JSR305 is currently unmaintained). You can manually specify a checker-qual version with
api "org.checkerframework:checker-qual:3.32.0".
If you have an HTML module, add:
implementation "com.github.tommyettinger:funderby:0.1.1:sources"
implementation "com.github.tommyettinger:digital:0.2.0:sources"
implementation "com.github.tommyettinger:jdkgdxds:1.3.0:sources"
to its
dependencies, and in its GdxDefinition.gwt.xml (in the HTML module), add
<inherits name="com.github.tommyettinger.funderby" />
<inherits name="com.github.tommyettinger.digital" />
<inherits name="com.github.tommyettinger.jdkgdxds" />
in with the other inherits lines. You shouldn't need to specify checker-qual in GWT dependencies.
If you have an Android module, you may need to ensure that multi-dex and desugaring are enabled. Projects generated with gdx-liftoff that target Java 8 or higher have this already, but projects made with gdx-setup or manually do not. Add:
android.defaultConfig.multiDexEnabled true
android.compileOptions.coreLibraryDesugaringEnabled true
// These can be higher versions, but typically no greater than JDK 11
android.compileOptions.sourceCompatibility JavaVersion.VERSION_1_8
android.compileOptions.targetCompatibility JavaVersion.VERSION_1_8
dependencies {
coreLibraryDesugaring 'com.android.tools:desugar_jdk_libs:1.1.5'
}
to whatever module uses an android or com.android.application plugin. The desugar_jdk_libs version should only be updated if
you have checked for compatibility with your Android Gradle Plugin version; see Android docs.
In short, if you use Android Gradle Plugin 7.3.0, you should use 'com.android.tools:desugar_jdk_libs:1.2.2'. If you use Android
Gradle Plugin 7.4.0 or later, you should use 'com.android.tools:desugar_jdk_libs:2.0.0'. You may need to set the minSdkVersion
to a higher value, depending on where it is already; 19 is known to work, and 16 probably works.
The dependency (and inherits line) on digital is not necessary for jdkgdxds 0.2.8, but is necessary starting in 1.0.3 and later.
The dependency and inherits line for funderby is new in 1.0.4 . Versions 1.0.1 and 1.0.2 also depended on
juniper 0.1.0 ; if you intend to use the
randomized algorithms here (like shuffles), then depending on Juniper (0.2.0) might be a good idea, though it is still optional.
The versions are expected to increase somewhat for digital as bugs are found and fixed, but a low version number isn't a bad thing
for that library -- both digital and juniper were both mostly drawn from code in this library, and were tested significantly here.
The version for funderby is expected to stay at or around 0.1.1, since it is a relatively small library and is probably complete.
You can build specific, typically brand-new commits on JitPack.
JitPack has instructions for any recent commit you want here.
To reiterate, you add maven { url 'https://jitpack.io' } to your project's repositories section, just not the one inside
buildscript (that just applies to the Gradle script itself, not your project). Then you can add
implementation 'com.github.tommyettinger:jdkgdxds:a87ee5c520' or api 'com.github.tommyettinger:jdkgdxds:a87ee5c520', depending
on what your other dependencies use, to your project or its core module (if there are multiple modules, as in a typical libGDX
project). If you have an HTML module, add:
implementation "com.github.tommyettinger:funderby:0.1.1:sources"
implementation "com.github.tommyettinger:digital:0.2.0:sources"
implementation "com.github.tommyettinger:jdkgdxds:a87ee5c520:sources"
to its
dependencies, and in its GdxDefinition.gwt.xml (in the HTML module), add
<inherits name="com.github.tommyettinger.funderby" />
<inherits name="com.github.tommyettinger.digital" />
<inherits name="com.github.tommyettinger.jdkgdxds" />
in with the other inherits lines. a87ee5c520 is an example of a recent commit, and can be
replaced with other commits shown on JitPack.
There is an optional dependency, jdkgdxds-interop, that provides code to
transfer libGDX data structures to and from jdkgdxds data structures, and more importantly, to store any* jdkgdxds classes using
libGDX's Json class. *Any, only because IdentityMap and IdentityOrderedMap don't make sense to serialize, while
HolderSet and HolderOrderedSet can't be serialized easily because their behavior depends on a Function. For historical
reasons, jdkgdxds-interop also can serialize classes from digital and juniper. Dependency information is provided in the
jdkgdxds-interop README.md .
Another optional dependency, kryo-more, allows serializing jdkgdxds data structures efficiently on non-GWT platforms (using Kryo 5.x for binary serialization). Dependency information is provided in the kryo-more README.md .
The 1.0.1 release is a more significant set of breaking changes, but thankfully, most of the changes have been very easy to adjust
to in practice. First, the core math utilities in BitConversion and Base were moved into the
digital library. Then, the random number generators that were here were moved to the
juniper library. Because of changes in juniper, jdkgdxds can now just use its
generators as java.util.Random subclasses, so juniper is simply an optional, but recommended, dependency starting in jdkgdxds
1.0.3 . There are various new additions to both of these small libraries to make them more useful as shared libraries for other
libraries to depend on. While digital has common math and trigonometry methods now, the random number generators in juniper
can serialize themselves to Strings without needing external code, and deserialize any of the serialized forms back to the
appropriate generator using Deserializer.
To update to 1.0.1, most of the changes are package-related, and often only need changing import statements. Code that previously imported:
com.github.tommyettinger.ds.support.BitConversionchanges tocom.github.tommyettinger.digital.BitConversioncom.github.tommyettinger.ds.support.Basechanges tocom.github.tommyettinger.digital.Basecom.github.tommyettinger.ds.support.ChopRandomchanges tocom.github.tommyettinger.random.ChopRandomcom.github.tommyettinger.ds.support.DistinctRandomchanges tocom.github.tommyettinger.random.DistinctRandomcom.github.tommyettinger.ds.support.FourWheelRandomchanges tocom.github.tommyettinger.random.FourWheelRandomcom.github.tommyettinger.ds.support.LaserRandomchanges tocom.github.tommyettinger.random.LaserRandomcom.github.tommyettinger.ds.support.MizuchiRandomchanges tocom.github.tommyettinger.random.MizuchiRandomcom.github.tommyettinger.ds.support.RomuTrioRandomchanges tocom.github.tommyettinger.random.RomuTrioRandomcom.github.tommyettinger.ds.support.StrangerRandomchanges tocom.github.tommyettinger.random.StrangerRandomcom.github.tommyettinger.ds.support.TricycleRandomchanges tocom.github.tommyettinger.random.TricycleRandomcom.github.tommyettinger.ds.support.TrimRandomchanges tocom.github.tommyettinger.random.TrimRandomcom.github.tommyettinger.ds.support.Xoshiro256StarStarRandomchanges tocom.github.tommyettinger.random.Xoshiro256StarStarRandomcom.github.tommyettinger.ds.support.EnhancedRandomis slightly more complicated, but it changes tocom.github.tommyettinger.random.EnhancedRandom
EnhancedRandom is now an abstract class, instead of a default-method-heavy interface, which makes it a little less flexible, but
allows it to work smoothly on Java 17 and much earlier Java versions. Extending the new EnhancedRandom only needs the new
getTag() method implemented, and maybe changes to copy(), equals() or toString() could be used as well.
If you are migrating other code to digital's new math functions, you may need to rename some called methods -- the sin_(),
cos_(), and similar trigonometric methods that worked with turns instead of radians now explicitly are called sinTurns() and
cosTurns().
There was a 1.0.0 release, but it mistakenly shadowed the digital code, without super-sourcing BitConversion for GWT support.
So, the first 1.x release is 1.0.1.
Likely less significant than the 1.0.1 update, 1.0.4 still "removed" some classes, though they were only moved to the funderby
library. The com.github.tommyettinger.ds.support.function package is now com.github.tommyettinger.function, and has many more
functional interfaces, but if they were being provided as lambdas, no difference will be noticeable. There are quite a lot more
interfaces in funderby than there ever were in jdkgdxds, which may help in uncommon situations that use primitives in lambdas
(so as if you need a ByteLongPredicate, you'll be ready). Some classes may have had their names changed; you can consult
funderby's README.md for the naming conventions.
Version 1.1.2 has no breaking Java API changes, but if you use GWT, it does change the inherits tags you need in your .gwt.xml
file. This was needed because versions of most "tommyettinger libraries" before about January 9, 2023 placed their .gwt.xml files
in the resources root folder, which turns out to cause unexpected compilation failures on GWT. This wasn't caught because,
strangely enough, these libraries were typically tested with projects that used the package com.github.tommyettinger, which is
shared with the sources in the GWT-affected libraries, and this caused the compilation to mysteriously succeed. After testing on
other packages on GWT, Dmitrii Tikhomirov and Colin Alworth tracked down the odd behavior to this folder situation, and so all the
folders needed to change. They did so in digital 0.1.7, funderby 0.0.2, juniper 0.1.8, and jdkgdxds 1.1.2 , among others.
Version 1.3.0 removes a lot of Java 8 APIs, including all interfaces that require Java 8 code. Language level 8 is still used,
since it's been safe to use on all platforms for a while now, but RoboVM (for iOS support) still doesn't support Java 8 APIs (just
the language level). To update, change any usage of PrimitiveIterator.OfInt, PrimitiveIterator.OfLong, and
PrimitiveIterator.OfDouble to com.github.tommyettinger.ds.support.util.IntIterator,
com.github.tommyettinger.ds.support.util.LongIterator, and com.github.tommyettinger.ds.support.util.DoubleIterator,
respectively. You may also need to change some functional interfaces to use the ones in Funderby, which are named differently:
FunctionbecomesObjToObjFunction,BiFunctionbecomesObjObjToObjBiFunction,ConsumerbecomesObjConsumer,BiConsumerbecomesObjObjBiConsumer,SupplierbecomesObjSupplier, andPredicatebecomesObjPredicate.- The pattern of specifying types in order continues for primitive types, and most combinations are supported.
IntLongToLongBiFunctionandIntIntToLongBiFunctionexist because using one or two primitive types is always supported.- If you were to try
IntLongToFloatBiFunction, it isn't defined because it uses three primitive types.- There is an exception for predicates, which return
boolean;IntLongPredicateis defined.
- There is an exception for predicates, which return
If you get errors about a Java 8 functional interface not being assignable to something in jdkgdxds, it probably should be swapped out for something defined by funderby -- jdkgdxds won't use functional interfaces defined anywhere but there or here.