#### grenier

Licensed under ISC license.

### baltree : Generic balanced-tree

A binary tree with smart constructors that ensure the resulting tree is

balanced.

This data structure can be used as a primitive on top of which one can easily

build balanced data structures, including but not limited to binary search

trees.

For instance, implementing stdlib-like Set/Map is trivial and suffers only a ~5

% overhead (and one gains a O(1) length/cardinal operation).

#### balmap : Alternative to Map & Set implemented on top of baltree

These two modules can be used as a drop-in replacement for `Map`

and `Set`

.

The performance characteristics are slightly different: `cardinal`

is now O(1),

some operations use that as a shortcut (`compare`

, `subset`

, ...).

In addition, the representation is exposed (the internal structure of the tree

can be pattern matched). It is protected by a private modifier, such that

invariants cannot be broken. However, custom operations are much easier to

implement (e.g. `rank`

to access the n'th element, which enables uniform

sampling in O(log n)).

### binder introducer: transform graphs into trees by introducing binding nodes

A generic algorithm that turns a directed graph intro a tree.

It finds where binding nodes should be introduced to make the resulting tree

readable. The idea is described in

this blog post.

For instance, this is useful to print cyclic values

(see Cmon).

### dbseq: fast sequence datastructure for DeBruijn-indexed environments

Dbseq is a small data structure that offers operations halfway between a list

and an immutable array. Most operations have a logarithmic cost. In practice,

it is a log with base 4 and small constant factors.

The name comes from the fact that the data structure is particularly suitable

to associate metadata to variables in De-Bruijn notation when traversing terms.

### trope : Track objects accross rope-like operations

This data structure allows efficient implementation of text markers for text editors (see

Emacs Markers).

More generally it allows to track the movement of objects on a line where

chunks are added and removed, with queries O(log n) amortized time.

Finally, it is persistent so you easily compare markers movement between

different revisions.

### orderme : Order-maintenance problem

See Order-maintenance problem

for a detailed description of what this intent to solve.

Main algorithm follows the amortized solution from "Two Simplified

Algorithms for Maintaining Order in a List", Michael A. Bender, Richard Cole,

Erik D. Demaine, Martín Farach-Colton, and Jack Zito.

A managed implementation provide finer integration with OCaml GC to collect

items that are no longer reachable via the public API.

### binpacking : Maxrects rectangle packing implementation

An implementation of Maxrects packing algorithm in 2D. This algorithm try to

pack a maximum number of 2d boxes inside a 2d rectangle.

See Even More Rectangle Bin Packing

Useful for generating spritesheets, texture atlases, etc.

### doubledouble : Floating points with around 107-bits precision

An implementation of double-double arithmetic.

Code is translated from DD by Martin Davis.

See tsusiatsoftware for more information.

### hll : HyperLogLog

An implementation of the HyperLogLog probabilistic cardinality estimator.

See HyperLogLog.

### jmphash : Jump consistent hashing

An implementation of

"A Fast, Minimal Memory, Consistent Hash Algorithm"

from John Lamping and Eric Veach.

### physh : Physical hashtable

Hashtables indexing OCaml values by their physical indentities. A

proof-of-concept, playing with the GC in tricky ways.

Its main purpose is to efficiently observe sharing, detect cycles, etc, in

arbitrary OCaml values without having to stop and stay out of the OCaml

runtime.

Can be used to experiment and learn about the GC but do expect bugs and don't

expect any kind of compatibility with future OCaml versions.

(Would be nice to have proper upstream support for such feature though!)

### state elimination : convert an e-nfa to a regex

This library converts e-NFA (including NFA and DFA) to regular expressions.

Unfortunately the regular expression is often of exponential size, unless you

extend the language to allow sharing sub-expressions (for instance with let

binders).

### strong : Some strongly typed primitives (typed equality, ordering, finite sets)

This library defines a few strongly typed idioms that are sometimes useful in OCaml codebase:

type-level equality and ordering

unhabitated type

an encoding of type-level naturals

finite sets (the set of numbers less than a given constant)

### valmari : Valmari's DFA minimization algorithm

An implementation of the algorithm desribed in Fast brief practical DFA

minimization by Valmari et al.

The tests and some fixes come from

WalkerCodeRanger/dfaMinimizationComparison, thanks!

### fastdom

An implementation of A Simple, Fast Dominance Algorithm

by Keith D. Cooper, Timothy J. Harvey, and Ken Kennedy.

sha256=e5362e6ad0e888526517415e78b9e8243bb0cc1b0c952201884148832ac4442f

sha512=4e2f16b52b3c2786a1b8e93156184fd69d448cea571ca839b6cb88ab73f380994d1561fe24c1523c43ed8fc42d2ac01b673a13b6151fff4af4f009923d3aaf37