I am a bit confused on ambiguous wording in the comments, maybe or anyone else could clarify, when Zach says:

an operation with sets of different density should return a combined set with the lower density

which direction of leafSize is he considering “lower”? Is 4096 “higher density” than 128 or is 4096 “lower density” than 128? My guess would be that 128 is “lower density” because “dense sets” in the library have the 4096 leaf size.

More broadly, there are correctness issues for difference and intersection when mixing up dense and non-dense sets:

Makes sense.

Looking at the code I wasn't sure whether the check/exception is part of the "public API" or was intended as a "fail early" signal to yourself that an internal invariant has been violated.

Thanks again for the quick response. A note in the README should be enough. Intersection and difference don't throw exceptions since they don't use the merge operation. From my reading of the code though the resulting sets have the density (leafSize) of the this argument.

Could this be used instead? Is it worth the trouble?

The exception could be made more explicit "Cannot compute the union of an int-set and a dense-int-set."

Using the "constructor" names and the name of the operation that failed (union instead of merge) could make it clearer the end-user where the problem is.

Offtopic: This doesn't really affect my program anymore - only the 1st implementation uses union/difference/intersection. The 2nd and 3rd only use disj. The 1st implementation has served it's purpose - making sure the 2nd is correct. Now the 2nd can be used to verify the correctness of the 3rd, over an even more diverse set of inputs, for some of which a dense-set makes sense.

This is slightly non-trivial to implement, so I may just clarify that it can't be done in the documentation to begin, but the expected behavior is that an operation with sets of different density should return a combined set with the lower density.