jdkgdxds

This release started out being needed to fix a bug in the deque types, when the initial capacity was 0. It soon expanded to include many new overloads of addAll, removeAll, containsAll, containsAny, and sometimes removeEach, all able to take array or range of array (with an offset and length) arguments. From 1.4.7, there's more constructors available for FilteredString types. They also use a faster hashing algorithm that may also be better for the limited needs FilteredString sets and maps have. The dependency on digital is now up to 0.4.7 .

[1.4.8]

• Deque types can be initialized with capacity 0, and now won't suddenly crash when an item is added.
• Almost every type got some new methods, thanks to PrimitiveCollection adding overloads that take arrays or ranges of arrays.
• The above change was also applied manually to Object-based Collection types.
• Where appropriate, types have removeAll() and removeEach(), as well as containsAll() and containsAny().

[1.4.7]

• The dependency on digital was updated to 0.4.7, which adds some potentially useful features, and has many more null checks.
• Filtered sets and maps have the full range of constructors that maps and sets usually have, now.
• The Filtered-String sets and maps use a different hashing algorithm now that takes advantage of how small a char is relative to a long.

This release mostly exists so the FilteredString Sets and Maps can be serialized. But wait, I haven't done a release with those classes yet! To recap, here's the changelog (in reverse order...):

[1.4.6]

• [BREAKING CHANGE] The Filtered-String sets and maps now use a CharFilter object to group their filter and editor, allowing them to be serialized and deserialized.

[1.4.5]

• The dependency on digital was updated... again... to 0.4.5, though this time it brings several new features. None used here.
• Filtered-String sets and maps! These are like the CaseInsensitive ones, but allow configuring how characters are used and modified.
• Filtered-Iterable sets and maps, too! These are like the Filtered-String ones but work on an Iterable of sub-items instead of a String of characters.
• FilteredComparators provides ways to sort the ordered filtered types.
• NumberedSet.addOrIndex() was broken, and now is fixed.
• Nullity annotations were put in the right places pretty much everywhere.
• I think this is the point Gradle was updated to 8.5; nothing broke, and it shouldn't affect user projects.

[1.4.4]

• The dependency on digital was updated again to 0.4.3 because of a break in GWT compilation in digital 0.4.2; it is fine now.

[1.4.3]

• The dependency on digital was updated to 0.4.2, which includes BitConversion.countTrailingZeros(); we use it in OffsetBitSet.
• A bug in getAndIncrement() for ordered maps with int and long keys was fixed; before, it didn't handle zero keys correctly.
• The Utilities.longHashCodeIgnoreCase() methods now are much closer to how Hasher implements them in digital; the results are different.

[1.4.2]

• The dependency on digital was updated to 0.4.1, which includes a new BitConversion.countLeadingZeros() method that we use here to speed things up on GWT a bit.
• The dependency on checker-qual was updated to 3.39.0, which shouldn't break or really even change anything here.

[1.4.1]

• [POSSIBLE BREAKING CHANGE] The dependency on digital was increased to 0.4.0, and that version changes what Hasher.hash() and Hasher.hash64() return for the same arguments. This doesn't affect jdkgdxds code, but may affect users who rely on digital transitively.
• New ObjectList.sortJdk() method will use the default List.sort() method rather than the in-place mergesort used by ObjectList.sort().
• Updated to Gradle 8.3 and Checker Framework 3.37.0 .

So, there's a lot that has changed since the last release here on GitHub, but new releases have been published to Maven Central all this time. Mostly new are the four FilteredString types and the four FilteredIterable types. I have no hope of serializing FilteredIterable (Ordered) (Set/Map), so those will just be treated as unserializable (at least, to JSON) due to their use of functional interfaces. However, FilteredString (Ordered) (Set/Map) classes can be serialized using jdkgdxds-interop or (soon) kryo-more. This takes advantage of how, starting in 1.4.6, you can register CharFilter types by name, and ser/deser uses that name to get the right CharFilter. But what even is a CharFilter?

A CharFilter is used by each of the FilteredString classes to use a filter to potentially ignore some characters in a String item/key, and an editor to potentially change the characters that aren't ignored (but not destructively editing). A common use for the editor is to convert every character to upper-case if possible (typically using Character::toUpperCase), which makes the FilteredString class act like one of the existing CaseInsensitive ones. You can go further and use the filter to only consider letter characters by using Character::isLetter as the filter, or only alphanumeric chars with Character::isLetterOrDigit.

There's similar behavior in the FilteredIterable types, but instead of a FilteredString type works on a String made of chars, a FilteredIterable works on an Iterable of a generic sub-item type. You still have a filter that can exclude sub-items and an editor that can make a different sub-item get used. I don't expect FilteredIterable types to be used as much as the String ones.

Well, there's that release!

This release includes the ability to combine whole maps according to a value-merging function (like the existing merge() does for single values in some map types). The merge() method is sometimes present, but now only when it acts how it is documented in the JDK -- if it can't remove values as well as add them, the similar method is called combine(). This is somewhat of a breaking change, since merge() has changed to combine() in some classes that optionally implemented it; all of these classes had primitive keys or values and didn't actually implement Map. To avoid JDK8 functional interfaces, which are undefined on RoboVM, each combine() implementation takes a functional interface defined by funderby. Also new are no-arg with() methods on most map types, meant for code-generation situations where the amount of arguments isn't known beforehand.

The release also fixes some dependency issues (actually done in 1.3.1, which removed unnecessary sources deps, and 1.3.2, which updated the digital dependency to work on GWT). In the test sources, which you would need to access from this repo and not from a JAR download, there are now enum-keyed maps and sets. I didn't think these were significant enough to warrant inclusion in the main repository, since an Object-keyed map can use enums just fine, but if you want the classes, they're a tiny bit more efficient.

This release is meant to ease compatibility with RoboVM, and it does so by removing usage of interfaces defined only in Java 8 or higher. Language level 8 is still required, since we use default methods heavily, among other niceties in 8. This updates to Funderby 0.1.1 and stays using digital 0.2.0. See the updating section in README.md for notes on what needs changing.

We have Bags! These are just like the List classes, and each extends its counterpart List, but the Bags are unordered, and have faster deletion (from any index) as a result. These were the main thing added in 1.2.0 . I screwed up ObjectList.equals(), and then fixed it! That fix happened in 1.2.1. I screwed up clear() on all primitive-keyed maps, and they would never properly remove the zero key or its value! That happened a long time ago, but the fix only happened just now, in release 1.2.2 .

This release is extremely minor on its own, but updates the release I forgot to post on GitHub before it (1.1.2 is on Maven Central, though). The release before this is actually significant for GWT, so I'll summarize it here. The GWT inherits lines have now changed to include com.github.tommyettinger. in the packages, because without a package, all sorts of very strange problems could occur in code that used jdkgdxds or its dependencies. Other than that change from 1.1.2, 1.1.3 updates digital to 0.1.8 and checker-qual to 3.30.0 , and not much else. It seems like jdkgdxds is pretty stable now in terms of API, and I think that's good!

This release is not especially small, but isn't huge either.

• It adds IdentitySet (and its Ordered variant).
• It fixes some bugs in HolderSet and CaseInsensitiveMap.
  • Most of these are in HolderSet, and affect various operations that take a T or K object but were coded to take a K or T.
  • Both had their equals() fixed.
• It makes the inner Entries, Keys, and Values types of various maps all implement equals() correctly (I hope it's correct, at least; there isn't a standard to go by in the JDK).
• It changes the internal hash mixing (again) so it should always use a relatively high-quality multiplier, chosen from a table of 512 numbers.
  • The only hash multiplier used in libGDX is 0x9E3779B97F4A7C15L, which mathematically should do extremely well, but has a caveat that it collides frequently when used to mix hashCodes that are Fibonacci numbers. With enough items, Fibonacci numbers tend to show up, and then that only multiplier becomes a liability.
  • Switching between hash multipliers when we resize() means no extra work has to be done to re-hash existing items (only the re-hashing that has to be done during resizing already). Since any situation with hash flooding would cause resize() to be called, changing our multiplier (and thus changing any weakness) only there seems to work.
• It switches from the ancient JSR305 nullity annotations to the newer, well-maintained checker-qual annotations.
  • This is a breaking change if you used JSR305 annotations, because jdkgdxds no longer provides them as a transitive dependency. Migrating to checker-qual isn't hard, and can mostly be done with find-and-replace. Nonnull needs to be changed to NonNull, and so on.

That should be everything. Happy New Year!

Christmas came early, it looks like, with... what could be a disappointing stuffing for your stocking. Unless you like niche features, that is, or bit sets (which are also a niche feature). On the plus side, there's a few potential bugs squashed here, so there's no reason to avoid an update. Some important things to note:

• OffsetBitSet is new; it acts like a primitive collection of ints, but starts counting at a specified offset (which can be negative, but defaults to 0). It only uses one bit per int it stores, but also requires one bit for every int in the range it doesn't store. For dense int sets with a known range, it makes sense.
• There have been numerous improvements to iterators and other less-often-considered parts of sets and maps.
  • You can get the remaining items from an iterator appended into a Collection (or PrimitiveCollection) of the appropriate type using appendInto().
  • You can also get those remaining items as a new list with toList().
  • You can always set the position of a map or set iterator, using reset(), or one of its inner Keys, Values, or Entries data structures, using resetIterator().
• There's various improvements to toString() and appendTo(), which appends from a set to a StringBuilder.
• The dependency on digital is now 0.1.5; the suggested (but not necessary) dependency on juniper is 0.1.7 or higher.

This is mostly release 1.1.0, suggesting it is more major, because I should have given the previous release a more "major" version number, but didn't. This is actually a fairly minor update compared to some earlier releases, since it mostly fills in missing functionality without changing much.

Just before Halloween, we have a new release that exorcises iterators and gets the deques nice and shining. All of the list iterators and deque iterators, plus NumberedSet's iterator, now handle removal via iterator correctly, as well as add() and set() when using an iterator as a ListIterator or its primitive equivalent. The deques needed a lot of code changed, because several key methods (including addLast()) didn't always work. Deques also have an insert() method now (which is equivalent to calling add() with an index argument), which is used by the new iterators they have.

This release only updates some dependencies and moves the com.github.tommyettinger.ds.support.function package to com.github.tommyettinger.function, in the new funderby library that is now a dependency. There are many more functional interfaces supported by funderby than ever were supported by jdkgdxds, though probably not too many, because each one is so small. Most code that uses functional interfaces via lambdas won't need any changes.

This release removes the required dependency on juniper (it is still recommended if you use any randomized methods, though) and improves the behavior of the hash multiplier changes to work a little better with problematic Strings. Now jdkgdxds only depends on digital 0.0.3 at runtime, plus jsr305 3.0.2 (for common annotations). There aren't many other changes here, though there is one breaking change as a result of not depending on juniper -- Arrangeable.rearrange(EnhancedRandom) is now Arrangeable.rearrange(long), and it doesn't need to attempt to reset the state of an EnhancedRandom now that it can simply generate random numbers from a long seed. Other breaking changes happened earlier; if you rely on EnhancedRandom being an interface (which is a property from before 1.0.1), then you may need to change to using the java.util.Random class instead, or the EnhancedRandom abstract class from juniper.

The map and set methods may be a little slower on average, but should be drastically faster in the worst-case. You can always override the place() method and replace it with a hash mixer of your choice, such as the older place() method from jdkgdxds 1.0.1 .

This release has virtually no public API changes, but instead is meant to protect maps and sets against some uncommon (but severe) cases that could make normally-quick operations take hours. It changes the Fibonacci hashing to use a different multiplier after each time resize() is called. That's about it! The actual change to each affected class is quite small, and there will actually be no change for maps and sets that are created with enough capacity that they don't need to resize(). Performance should be about the same; because the different multiplier chosen on each resize could be better or worse for any particular data, it's hard to generalize how much the change in multiplier will affect most maps and sets. We do know that this helps prevent a specific DoS vector, so it's probably worthwhile to update.

Note that this depends on the same versions of juniper and digital as release 1.0.1 did.

It's the first[citation needed] 1.x release of jdkgdxds! Ignore that the version number isn't 1.0.0, but pay attention to the several small breaking changes! Now jdkgdxds depends on digital and juniper, two other libraries by the same author (tommyettinger), so external code can depend on just common math code in digital or just that and random number generators with juniper. You will likely need to change some import statements; see README.md for more. Other changes aren't especially likely; other than one method which moved from EnhancedRandom to Arrangeable, there aren't any other known breaking changes here. There aren't many new features here, though there are in the new libraries. Arrangeable has a rearrange(EnhancedRandom) method, I guess. But hey, go wild, it's 1.0.1! Any additional major breaking changes will go into another major version increase.

This release adds a few new random number generators (including one optimized for GWT performance, ChopRandom), adds some more API to QuickSelect and NumberedSet, and most importantly, makes removeAll() act the same for ObjectList and the various primitive lists, such as IntList and DoubleList. The problem before was that the JDK List method removeAll() removes any occurrences of any items that appear in the Collection parameter, while IntList matched libGDX's IntArray behavior and would only remove occurrences on a one-for-one basis with the parameter. That is, if an item occurred once, it would only be removed once from the IntList, and if it occurred twice, it would be removed twice. The old removeAll() behavior (matching libGDX to at least version 1.10.0) is still available as removeEach(), and removeAll() should act like the JDK version everywhere here now.

This release fixes the shrink() method in maps and sets when the shrink would have reduced the table's capacity to less than what it needed to hold its current items. Because some usage may want to indiscriminately (or by iteration order, from the end, for ordered maps and sets) remove items until a specific size has been reached, there is now a truncate() method on all maps and sets. There was already a very similar truncate() on lists.

There are some fixes and additions to the random number generator code. To help ease conversion between the similar codebases of ShaiRandom and jdkgdxds, MizuchiRandom was added here. Mizuchi is similar to LaserRandom in that it has two states, but has less correlation between initial seeds and the resulting sequence; it is, however, slightly slower than LaserRandom usually, and does not allow skip(long). TrimRandom changed slightly in what constants it uses and has become much more robust as a result; it is now considered stable. FourWheelRandom.previousLong() was badly broken before and is now fixed.

If you're looking in the tests, there is an actually-working map that uses Cuckoo Hashing with a Stash (ObjectObjectCuckooMap), and it can take 500,000 keys with identical hashes but different equality (albeit slowly). This was something that everyone tried to find and no one fully solved before I decided to bite the bullet and reimplement all of libGDX's hash-based data structures. Now it is solved, but because insertion into a cuckoo-hashed map is just generally several times slower than the style jdkgdxds uses, without any operations being drastically faster, it's best that jdkgdxds sticks with what it has already.

This release rolls back a change in 0.2.4 and 0.2.5, where addAll() methods were defined for both the current data structure type's parent when passed as an argument (such as ObjectOrderedSet.addAll(ObjectSet<T>)) and for the more general case taking an Ordered implementation (such as ObjectOrderedSet.addAll(Ordered<T>). This caused a conflict when passing an ObjectOrderedSet to addAll(), because it satisfies both types. The same was true for enough other types that this newly-added Ordered overload caused pretty severe problems in the largest project that uses jdkgdxds, to my knowledge (SquidSquad), so a new release was in order. No other changes are present.

This is a bit of a hasty release to fix the entirely broken WrapperRandom in 0.2.4, and realign some documentation and implementations so they all match regarding removeRange(). Now all removeRange() methods follow the behavior of ArrayList, where start is inclusive and end is exclusive. About WrapperRandom, it wasn't tested before and is now. There was a severe problem in how its constructor called Random's super-constructor, and though it is resolved now, in 0.2.4 constructing a WrapperRandom would have resulted in an exception.

Here's to a more stable release next time.

This release adds a bit of support for ranges in addAll(), putAll(), to some extent removeRange(), and copy constructors in most of the ordered data structures. Some example usage is described in the README.md. There's also the new (but not yet stable) TrimRandom, and WrapperRandom for making EnhancedRandom implementations act like Random subclasses. Some bugs were fixed in ensureCapacity(), which didn't act as its docs described in some classes. In the tests (not actually part of this release), there's some experiments that might actually fix the Cuckoo Hashing based maps used by libGDX 1.9.10 and sometimes by Kryo still. This library exists because I was familiar with the libGDX data structures when I replaced the 1.9.10 maps and sets and wrote the versions that went into 1.9.11, so having finally come closer to fixing the original Cuckoo-based maps/sets is a nice feeling. It's entirely possible the fixed version still crashes and burns with an OutOfMemoryError in some cases, which is part of why it isn't used in the regular library (the other part being that insertions are very slow compared to what we have now).

Note: The removeRange() methods are a work in progress, and may change names, semantics, return types, etc. in future versions. The other new constructors, methods, and overloads should be considered more stable and usable.

This release mostly contains fixes for the iteration through int- and long-keyed maps, as well as fixing two-argument nextInt() and nextSignedInt() for EnhancedRandom, adding BooleanDeque, and some miscellaneous other improvements. The iteration fixes are the most important of these to have in a stable release, though it's also nice to have rand.nextInt(low, high) not return some large, out-of-range value.

I also was able to finally fix the issue that precipitated jdkgdxds existing: libGDX 1.9.10's cuckoo-hashed maps would produce OutOfMemoryErrors in some situations (that could be exploited easily by unskilled malicious actors). Now there's a ObjectObjectCuckooMap in the tests that includes a fix for that... but benchmarks showed that even with cuckoo's supposedly better algorithm that guarantees constant-time containsKey(), if the cuckoo-map can't fail, it can't have constant-time operations as a tradeoff. They also showed that it's significantly slower at insertions (0.5x throughput) and not significantly faster at anything (nothing over 1.1x throughput). So, we can be fully satisfied with the algorithm used currently in jdkgdxds (and libGDX).

This release fixes one bug in the just-added Base class, but it was a bug that made Base significantly less useful, so here's a small fix release. Specifically, when a base was requested to be case-insensitive, it would effectively be ignored in the last release, and will be correctly case-insensitive in this release. The notes from the previous release, 0.2.1, still apply:

This release mostly improves the random number generators; it adds StrangerRandom and Xoshiro256StarStarRandom, and fixes the nextInt(int, int) and nextSignedInt(int, int) methods (only the two-argument ones were broken, and only for some arguments). It adds a nice natural-text sort in NaturalTextComparator, using mostly this code as a basis. It also adds the Base class for numeral/base systems, which generalizes code that deals with decimal, binary, hexadecimal, base-64, and all sorts of other radices. I hope this is useful!