jdkgdxds

Taking libGDX's data structures and implementing JDK interfaces.

Primitive-backed? Insertion-ordered? Value-sortable? Double-ended? Case-insensitive? WE HAVE IT ALL! Lists, Bags, Deques, Sets, Maps! This library supplies most of the common varieties of data structures, and tries to reduce how much memory it allocates all over. It works on all common and not-so-common platforms, including HotSpot JDKs, Graal Native Image, Android, iOS via RoboVM or Multi-OS Engine, browsers via Google Web Toolkit or TeaVM, etc. Reflection is entirely avoided. Variants on maps and sets are available to treat keys as case-insensitive, ignore/edit certain characters in String keys while hashing/comparing, or use Enum keys efficiently and without breaking normal serialization rules. We have an EnumMap and EnumSet that actually have zero-argument constructors! We have an all-around improvement to java.util.ArrayDeque that implements both Deque and List, allows O(1) lookup at any index, and didn't forget to implement equals() and hashCode(): ObjectDeque ! For every unordered map or set, an insertion-ordered variant is provided. These ordered variants can also be sorted offline, including by key or by value for maps. We have a CharList that can fill in for a StringBuilder in some ways while still being used as a collection.

The library and all its dependencies should be under 2MB in size, and can be easily reduced in size further by tools like R8 or ProGuard that perform dead code elimination. Compare that with FastUtil Core, if you want! This library uses some code from FastUtil for sorting, and both projects are Apache-licensed. Note that FastUtil won't work on all platforms jdkgdxds targets, such as RoboVM.

JavaDocs are here.

tl;dr Instructions

Gradle dependency (for all platforms except GWT):

api "com.github.tommyettinger:jdkgdxds:2.1.2"

For GWT, see "How do I get it?" below, or use TeaVM instead.

If you use libGDX, you can let gdx-liftoff set up the dependency by checking the jdkgdxds checkbox under third-party extensions. This also can optionally allow you to depend on jdkgdxds-interop for JSON saving/loading, kryo-jdkgdxds for Kryo saving/loading, or tantrum-jdkgdxds for Apache Fory saving/loading.

What is this?

Some background, first... libGDX has its own data structures, and they're mostly nice to work with. 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.

OK, how do I use it?

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 and Queue, those are 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. A minor point to note is that libGDX also supplies primitive arrays for all types, except that it doesn't have DoubleArray, where this library does provide DoubleList (as well as DoubleBag and DoubleQueue). 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 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.

There are some useful varieties of Map and Set here that don't show up very often in libraries. There's a CaseInsensitiveMap and a CaseInsensitiveOrderedMap that require CharSequence keys (such as String or StringBuilder), but treat them as case-insensitive, and allows a generic Object type for its values. A more generic solution to the same sort of problem lies in FilteredStringSet, FilteredStringOrderedSet, FilteredStringMap, and FilteredStringOrderedMap. These filtered-String data structures contain a filter (a predicate that determines if a char in a String should be read or skipped for hashing and equality comparison purposes) and an editor (a function that can change what char is actually used in a hash or equality comparison). These data structures can be used to implement the CaseInsensitive maps and sets (except one needs a key to be a String and where the other uses a CharSequence) if the editor is Character::toUpperCase. In addition, they can do something like filter the Strings so only the letter characters are considered (whitespace, punctuation, and numbers could all be skipped) using Character::isLetter as the filter (or RegExodus' Category.L::contains for GWT compatibility). This goes on, to even more filtered data structures: FilteredIterableSet, FilteredIterableOrderedSet, FilteredIterableMap, and FilteredIterableOrderedMap, which act like the filtered-String data structures but work on keys or items that are each an Iterable (type I) of sub-items/sub-keys (type T or K). The Iterable must not be modified while it is