Java data structures for primitive and/or Object items
APACHE-2.0 License
Bot releases are hidden (Show)
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]
[1.4.7]
Published by tommyettinger 11 months ago
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]
[1.4.5]
[1.4.4]
[1.4.3]
BitConversion.countTrailingZeros()
; we use it in OffsetBitSet.Utilities.longHashCodeIgnoreCase()
methods now are much closer to how Hasher
implements them in digital; the results are different.[1.4.2]
BitConversion.countLeadingZeros()
method that we use here to speed things up on GWT a bit.[1.4.1]
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.ObjectList.sortJdk()
method will use the default List.sort()
method rather than the in-place mergesort used by ObjectList.sort()
.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!
Published by tommyettinger over 1 year ago
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.
Published by tommyettinger over 1 year ago
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.
Published by tommyettinger over 1 year ago
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 .
Published by tommyettinger over 1 year ago
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!
Published by tommyettinger almost 2 years ago
This release is not especially small, but isn't huge either.
equals()
fixed.equals()
correctly (I hope it's correct, at least; there isn't a standard to go by in the JDK).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.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.Nonnull
needs to be changed to NonNull
, and so on.That should be everything. Happy New Year!
Published by tommyettinger almost 2 years ago
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:
appendInto()
.toList()
.reset()
, or one of its inner Keys, Values, or Entries data structures, using resetIterator()
.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.
Published by tommyettinger almost 2 years ago
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.
Published by tommyettinger about 2 years ago
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.
Published by tommyettinger over 2 years ago
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 .
Published by tommyettinger over 2 years ago
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.
Published by tommyettinger over 2 years ago
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.
Published by tommyettinger over 2 years ago
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.
Published by tommyettinger over 2 years ago
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.
Published by tommyettinger almost 3 years ago
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.
Published by tommyettinger almost 3 years ago
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.
Published by tommyettinger almost 3 years ago
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.
Published by tommyettinger almost 3 years ago
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 OutOfMemoryError
s 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).
Published by tommyettinger almost 3 years ago
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)
andnextSignedInt(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!