# JUtil history

## 2.0 (2026-10-31)

* JDK 21 or later is required, to build and to run JUtil.
* Published on Maven Central, as `net.cscott:jutil`; `ant release`
  builds the bundle to upload.  The jar is an automatic module,
  `net.cscott.jutil`.  The jar and the sources jar hold the license,
  as `META-INF/COPYING`.
* The tests use JUnit 6, and are in `test/` instead of the jar.  They
  replace `TestMap`, `TestSet`, and the `main()` self-test methods of
  `BinaryHeap`, `BinomialHeap`, `FibonacciHeap`, `BinaryTree` (with its
  public `test()` method), `RedBlackTree`, `IntervalTree`,
  `DisjointSet`, `BitString`, `HashEnvironment` and
  `PersistentTreeNode`.
* Fixed: removing an element from a `BinaryTree`, `RedBlackTree` or
  `IntervalTree` could corrupt the tree when the element's successor
  was its child.  `BinaryTree.swapPositions()` now requires both nodes
  to be in the tree.
* Fixed: `IntervalTree` could miss overlapping intervals, because it
  did not keep the maximum endpoint of each subtree up to date.
* Fixed: `BinaryTree.successor()` of a node with no right child.
* Fixed: the entry set, key set and values of a `HashEnvironment`
  support `Iterator.remove()` and `Map.Entry.setValue()`.
* Fixed: the `toString()` of a multimap with a `null` key or value.
* `BinaryTree` and `RedBlackTree` take a type parameter for their
  elements, and `IntervalTree` is a `RedBlackTree<Interval>`; its
  `allOverlapping()` returns an `Iterator<Interval>`.  Code which uses
  the raw types still compiles and runs, but a subclass of
  `IntervalTree` must override `makeNode(Interval)` instead of
  `makeNode(Object)`.
* Fixed: `IntervalTree` ordered intervals by subtracting their low
  ends, which overflows for very large or very small values.
* `AggregateSetFactory` and `AggregateMapFactory` no longer use
  `finalize()`, which is deprecated for removal.  The entries of a set
  or map which has been garbage-collected are now removed from the
  factory's backing store the next time the factory adds an entry, on
  the thread that uses the factory; `finalize()` modified the backing
  store from the finalizer thread, which could corrupt it.
* Deprecated, with notes on the JDK methods to use instead:
  `Default.comparator` and `Default.comparator()`, which are now
  `Comparator.nullsFirst(Comparator.naturalOrder())`;
  `Default.nullIterator` and `Default.nullIterator()`, for
  `Collections.emptyIterator()`; and the raw `Default.EMPTY_MULTIMAP`,
  for `Default.EMPTY_MULTIMAP()`.  The deprecated `EMPTY_SET` and
  `EMPTY_MAP` now point to `Collections.emptySortedSet()` and
  `Collections.emptySortedMap()`.
* Deprecated: the raw-typed constants of `Factories`, such as
  `Factories.hashSetFactory`, for the parameterized methods of the
  same name, such as `Factories.hashSetFactory()`; and
  `Factories.workSetFactory()`, for `linkedHashSetFactory()`, since
  `WorkSet` is deprecated for `LinkedHashSet`.
* The `GenericInvertibleMultiMap` constructors which take factories
  take wildcard types, such as `MultiMapFactory<?,?>`, instead of raw
  types.
* `UniqueVector` and `UniqueStack` have a `spliterator()` which reports
  `DISTINCT`.
* Fixed: `Util.ffs(0)` and `Util.ffs(0L)` return 0, as documented,
  instead of 24 and 56.  `Util`'s bit operations use the JDK's
  `numberOfLeadingZeros()`, `numberOfTrailingZeros()` and
  `bitCount()`.
* Deprecated: `Util.repeatString()`, for `String.repeat()`;
  `Util.popcount()`, for `Integer.bitCount()` and `Long.bitCount()`;
  and `Util.zerocount()`, for `bitCount(~v)`.
* Fixed: `BitString.setUpTo()`, `clearUpTo()`, `or_upTo()` and
  `numberOfOnes(int)` ignored a whole unit of 32 bits when given the
  last bit of a unit, such as 31 or 63.
* Deprecated: `BitString`, for `java.util.BitSet`, which no longer
  has the bugs that `BitString` was written to avoid.  Its
  documentation says which `BitSet` method replaces each of its
  methods.  `BitSetFactory` still uses it.
* `Environment.Mark` is `AutoCloseable`: closing a mark of a
  `HashEnvironment` or a `PersistentEnvironment` undoes all changes
  since the mark, so `try (Environment.Mark scope = env.getMark())`
  makes a scope.  A mark of another `Environment` implementation
  inherits a `close()` which throws `UnsupportedOperationException`.
* `HashEnvironment.undoToMark()` and `PersistentEnvironment.undoToMark()`
  throw `IllegalArgumentException` for a mark of another
  environment, which used to corrupt a `HashEnvironment` and replace
  the contents of a `PersistentEnvironment`.
* Every serializable class declares its `serialVersionUID`.  Objects
  serialized by JUtil 1.x, other than a `Default.PairList`, cannot be
  read by 2.0.
* Heaps take a `Comparator<? super K>`, so a heap of `Integer` keys
  can be ordered by a `Comparator<Number>` or `Comparator<Object>`.
  `Heap.comparator()` returns a `Comparator<? super K>`: code which
  assigns it to a `Comparator<K>` no longer compiles.
* `Heap` is `Iterable` over its entries, in no particular order.
* Fixed: `BinomialHeap.union()` and `FibonacciHeap.union()` overflowed
  the stack when given a heap of their own class with an equal
  comparator, and `BinaryHeap.union()` did not empty the heap it was
  given.
* Fixed: a heap was not `equals()` to itself, and its `hashCode()`
  changed from call to call.  Heaps are equal when they have the same
  entries, in any order, and the hash code is one more than the sum of
  the entries' hash codes.
* `Pair`, an immutable, serializable record of two values, with
  `left()` and `right()`.  Deprecated: `Default.PairList` and
  `Default.pair()`, for `Pair`.  A `PairList` is a mutable `List`,
  which a record cannot be, so `Pair` is a new class.
* Deprecated: `Default.entry()`, for
  `AbstractMap.SimpleImmutableEntry`, which it now returns, or
  `Map.entry()`, which does not permit `null`s.
* `CollectionFactory`, `SetFactory`, `ListFactory`, `MapFactory` and
  `MultiMapFactory` are functional interfaces instead of abstract
  classes, so a copy constructor or a lambda is a factory:
  `SetFactory<V> sf = HashSet::new`, or
  `MultiMapFactory<K,V> mmf = GenericMultiMap::new`.  A class which
  extended a factory must implement it instead, and code compiled
  against 1.x must be recompiled.  `MultiMapFactory.makeMultiMap()`
  is the method to implement; a subclass which implemented only
  `makeMultiMap(MultiMap)` must implement `makeMultiMap()` too.
  `ListFactory.concatenate()` is no longer inherited by
  implementations of `ListFactory`: call it as
  `ListFactory.concatenate()`.
* `FilterIterator` takes a `Predicate` and a `Function`, which can be
  lambdas, and has `FilterIterator.filter()` and
  `FilterIterator.map()` for just one of them.  Deprecated:
  `FilterIterator.Filter`, and the constructor which takes one.
* `CombineIterator`'s constructors take wildcard types, such as an
  `Iterator<? extends Iterator<? extends E>>`.  Its `remove()` throws
  `IllegalStateException` instead of `NullPointerException` before
  the first call to `next()`.
* Fixed: a multimap made by `PersistentMultiMapFactory` threw
  `NullPointerException` when the last value of a key was removed,
  by `remove(key, value)` or through `getValues()` or `keySet()`.
* `MultiMap.replace(key, oldValue, newValue)` and
  `MultiMap.replaceAll()` change each mapping separately, and keep a
  key's other values; the `Map` defaults they replace used `put()`,
  which removes them.  The documentation of `MultiMap` says how the
  other `Map` defaults, such as `merge()`, treat a key with many
  values.
* `GenericMultiMap` has public copy constructors, which take a
  `GenericMultiMap` (and keep its map and collection factories), a
  `MultiMap` or a `Map`.  The copy has value collections of its own.
* Fixed: a `LinearMap` made by `new LinearMap(map)` shared the
  entries of `map`, so a `put()` on one map changed the other.  The
  constructor takes a `Map<? extends K,? extends V>`.
* Deprecated: `UnmodifiableIterator`, for implementing `Iterator`,
  whose default `remove()` throws `UnsupportedOperationException`;
  and `UnmodifiableIterator.proxy()`, for
  `Default.unmodifiableIterator()`, which takes an
  `Iterator<? extends E>`.  `FilterIterator` and `SnapshotIterator`
  implement `Iterator` instead of extending `UnmodifiableIterator`,
  so code which assigns one to an `UnmodifiableIterator` no longer
  compiles.
* `SnapshotIterator` and `IteratorEnumerator` take an
  `Iterator<? extends E>`.
* Each deprecated class and member says which release deprecated it,
  as `@Deprecated(since="1.3")` or `@Deprecated(since="2.0")`.
  Classes and members added after 1.0 say which release added them,
  with `@since`, and the API documentation lists them by release on
  its "New API" page.
* The documentation of `MultiMap`, `PersistentMap` and `DisjointSet`
  has examples, which `ant test` runs with [JDoctest].

## 1.5 (2026-10-30)

The last release of the 1.x line, which builds on JDK 1.5 through 8.
The jar runs on Java 1.5 and later.

* `Factories.treeMapFactory()`, and `treeSetFactory()` and
  `treeMapFactory()` variants which take a `Comparator`.
* `Factories.treeSetFactory()` now requires a `Comparable` element type.
* The javadoc and the distribution build on JDK 8: javadoc is run with
  `-Xdoclint:none` on JDK 8 and later.

## 1.4 (2009-02-14)

* The jar is binary compatible with JDK 1.5, and compiled with debug
  information.
* More assertions in `WorkSet`, which check that the hash codes of its
  elements don't change.
* Moved from CVS to git.

## 1.3 (2006-10-30)

* JDK 1.5 or later is required: the build now uses ant (or Eclipse)
  instead of autoconf and the JSR-14 prototype compiler, and the
  workarounds for its bugs are gone.
* `PersistentMultiMapFactory`, whose multimaps (and their value sets)
  can be cloned in constant time.  `PersistentSet` implements
  `Iterable`.
* Factories for `EnumSet`, `EnumMap`, `LinkedHashSet` and
  `LinkedHashMap`.
* `MultiMapFactory` no longer creates `GenericMultiMap`s; use the new
  `GenericMultiMapFactory`.  `AbstractMultiMap` was factored out of
  `GenericMultiMap`.
* `CollectionWrapper`, `SetWrapper` and `ListWrapper` are abstract, with
  a `wrapped()` method which subclasses can narrow.
* `UnmodifiableMap`, `UnmodifiableMapSet` and `UnmodifiableMultiMapSet`,
  which protect these types from mutation; `UnmodifiableMultiMap` is now
  safe too.
  Unlike `Collections.unmodifiableMap()`, the `entrySet()` of an
  `UnmodifiableMap` is an `UnmodifiableMapSet`.
* `UnmodifiableIterator.proxy()`.
* `BitSetFactory` constructors take a `Collection` instead of a `Set`.
* Deprecated `WorkSet` (use `java.util.LinkedHashSet`),
  `ListFactory.singleton` (use `java.util.Collections.singletonList`),
  and `Default.EMPTY_SET`, `Default.EMPTY_LIST()` and
  `Default.EMPTY_MAP` (use the empty collections of
  `java.util.Collections`).
* Fixed a `NullPointerException` in `containsAll()` of the sets made by
  `PersistentSetFactory`.
* `jutil-source.jar`, for Eclipse.

## 1.2 (2004-02-07)

Built, but not released publicly at the time.

* `EMPTY_MAP` and `EMPTY_MULTIMAP` are parameterized.
* Constant-time `clone()` for `PersistentMap` and `PersistentSet`.
* Constructors use wildcards instead of explicit type parameters.
* More precise return type for `LinearSet.clone()`.
* Documentation improvements.

## 1.1 (2004-01-24)

* Interfaces match the wildcard signatures of the standard library
  collection classes.  Requires the JSR-14 2.4 alpha 1 prototype
  compiler.
* Updated with the changes made to the FLEX sources since 1.0.
* `PersistentMapFactory` and `PersistentSetFactory`.
* Uses the new `for` loop.
* Fixed `PersistentTreeNode.putAll`.

## 1.0 (2003-04-26)

* Initial release: the generic collection classes of the [FLEX]
  compiler, packaged as a library.  Requires a JSR-14 prototype
  compiler.
* `java -jar jutil.jar` prints the library version.

[FLEX]: http://flex.cscott.net/
[JDoctest]: https://github.com/cscott/JDoctest