Add a new "Maxtrie" library: immutable sets and maps over non-negative integers, represented as a very efficient flavor of Patricia tries whose nodes hoist the maximum of their subtree.
Maxtrie.PatSet: sets of integers, with a bitmap per node for dense setsMaxtrie.PatMap: maps, with a Stdlib.Map.S-like interface and changes to quickly list the differences between two versions of a mapMaxtrie.PatMapSharing, PatSet.Sharing: comparisons that make equal subtrees physically sharedPhysh:
physh/RUNTIME_NOTES.mdis_empty, add_if_new, remove, clear, reset, iter, fold, and for maps find_opt, mem and add_overwriteFixes:
split dropped elements, and so did the functions using it (union, inter, diff, merge, Set.map, filter_map, ...); equal returned false on maps that are equal but not physically equalrestore kept the equations assumed after the snapshot when they had not been propagated yetnode and join could build trees that break the balance invariant (the depth stayed logarithmic); this also affected balmaplet recBaltree: faster node and join (2.5x for join).
Balmap: faster add, remove, union, subset, filter, Set.of_list and Set.map, now on par with or faster than Stdlib except for split and subset (5-20% slower) (see balmap/bench). Like Stdlib, operations return their argument when the result is equal to it.
Add randomized tests for balmap, binder_introducer, congre, dbseq, fastdom, jmphash, state_elimination and valmari.
Balmap:
is_singleton to fix compatibility with OCaml 5.5, contributed by @kit-ty-kateFix compatibility with OCaml 5:
add_to_list, to_list, of_list) contributed by @kit-ty-kateHowever physh is disabled for now when compiling with OCaml 5. Thorough reviewing is needed to ensure that the current design is safe with the multicore GC (see #10).
Add a new "Congre" library, a fast congruence closure algorithm with support for backtracking and interpretability of equivalence classes.
Binder introducer: transform a directed graph into a tree by introducing binding nodes.
Fastdom: implementation of a dominance algorithm. Fix various bugs in Valmari DFA minimizer. Get rid of "PCG" unused code. Doubledouble: disable FMADD to strictly stick to 64-bits precision.
Balmap: alternative to Stdlib Maps and Sets based on baltree. Dbseq: fast sequence datastructure for DeBruijn-indexed environments. State elimination: convert e-NFA to regular expressions.
Fixed many bugs in and increased expressiveness of Valmari implementation.
Collect a few type-level idioms in the Strong library. Drop support for OCaml 4.03, OCaml 4.04 is now the oldest supported version. Fix compilation with the first released version of OCaml 4.10.
Fix compilation with OCaml 4.10. Add a low-level interface to Dset.
Add a new algorithm Dset: construct two set of resources and compute their difference efficiently.
Important bugfix in the balancing algorithm of Baltree. Use dune binary instead of jbuilder. Remove references to Pervasives for OCaml 4.08 compatibility.
Dune & dune-release port contributed by Rudi Grinberg. Valmari DFA minimization implementation.
Fix support for safe-string / 4.06
HyperLogLog: add serialization, improve estimation quality