this repo has no description
anil.recoil.org
1opam-version: "2.0"
2maintainer: "Frederic Bour <frederic.bour@lakaban.net>"
3authors: "Frederic Bour <frederic.bour@lakaban.net>"
4homepage: "https://github.com/let-def/grenier"
5bug-reports: "https://github.com/let-def/grenier"
6license: "ISC"
7dev-repo: "git+https://github.com/let-def/grenier.git"
8doc: "https://let-def.github.io/grenier/doc"
9build: [
10 ["dune" "subst"] {dev}
11 ["dune" "build" "-p" name "-j" jobs]
12 ["dune" "runtest" "-p" name "-j" jobs] {with-test}
13]
14depends: [
15 "ocaml" {>= "4.04" & < "5.1"}
16 "dune" {>= "1.2.0"}
17]
18synopsis: "A collection of various algorithms in OCaml"
19description: """
20Licensed under ISC license.
21
22## baltree : Generic balanced-tree
23
24A binary tree with smart constructors that ensure the resulting tree is
25balanced.
26
27This data structure can be used as a primitive on top of which one can easily
28build balanced data structures, including but not limited to binary search
29trees.
30
31For instance, implementing stdlib-like Set/Map is trivial and suffers only a ~5
32% overhead (and one gains a O(1) length/cardinal operation).
33
34## trope : Track objects accross rope-like operations
35
36This data structure allows efficient implementation of text markers for text editors (see
37[Emacs Markers](http://www.gnu.org/software/emacs/manual/html_node/elisp/Markers.html)).
38
39More generally it allows to track the movement of objects on a line where
40chunks are added and removed, with queries O(log n) amortized time.
41
42Finally, it is persistent so you easily compare markers movement between
43different revisions.
44
45## orderme : Order-maintenance problem
46
47See [Order-maintenance problem](https://en.wikipedia.org/wiki/Order-maintenance_problem)
48for a detailed description of what this intent to solve.
49
50Main algorithm follows the amortized solution from "Two Simplified
51Algorithms for Maintaining Order in a List", Michael A. Bender, Richard Cole,
52Erik D. Demaine, Martín Farach-Colton, and Jack Zito..
53
54A managed implementation provide finer integration with OCaml GC to collect
55items that are no longer reachable via the public API.
56
57## binpacking : Maxrects rectangle packing implementation
58
59An implementation of Maxrects packing algorithm in 2D. This algorithm try to
60pack a maximum number of 2d boxes inside a 2d rectangle.
61
62See [Even More Rectangle Bin Packing](http://clb.demon.fi/projects/even-more-rectangle-bin-packing)
63
64Useful for generating spritesheets, texture atlases, etc.
65
66## doubledouble : Floating points with around 107-bits precision
67
68An implementation of [double-double arithmetic](https://en.wikipedia.org/wiki/Quadruple-precision_floating-point_format#Double-double_arithmetic).
69
70Code is translated from [DD](http://tsusiatsoftware.net/dd/main.html) by Martin Davis.
71See [tsusiatsoftware](http://tsusiatsoftware.net) for more information.
72
73## dset : Diff-set
74
75Combinators to construct abstract sets and compute symmetric differences.
76
77Although not formally proven, when used in a linear fashion the cost of the
78difference should be O(n) in the number of differences.
79
80For interactive applications like user interfaces, this means we can track
81usage of resources at a O(1) cost.
82
83## hll : HyperLogLog
84
85An implementation of the HyperLogLog probabilistic cardinality estimator.
86See [HyperLogLog](https://en.wikipedia.org/wiki/HyperLogLog).
87
88## jmphash : Jump consistent hashing
89
90An implementation of
91["A Fast, Minimal Memory, Consistent Hash Algorithm"](http://arxiv.org/abs/1406.2294)
92from John Lamping and Eric Veach.
93
94## physh : Physical hashtable
95
96Hashtables indexing OCaml values by their physical indentities. A
97proof-of-concept, playing with the GC in tricky ways.
98
99Its main purpose is to efficiently observe sharing, detect cycles, etc, in
100arbitrary OCaml values without having to stop and stay out of the OCaml
101runtime.
102
103Can be used to experiment and learn about the GC but do expect bugs and don't
104expect any kind of compatibility with future OCaml versions.
105(Would be nice to have proper upstream support for such feature though!)
106
107## strong : Some strongly typed primitives (typed equality, ordering, finite sets)
108
109This library defines a few strongly typed idioms that are sometimes useful in OCaml codebase:
110- type-level equality and ordering
111- unhabitated type
112- an encoding of type-level naturals
113- finite sets (the set of numbers less than a given constant)
114
115## valmari : Valmari's DFA minimization algorithm
116
117An implementation of the algorithm desribed in [Fast brief practical DFA
118minimization](https://dl.acm.org/citation.cfm?id=2109576) by Valmari et al.
119
120The tests and some fixes come from
121[WalkerCodeRanger/dfaMinimizationComparison](https://github.com/WalkerCodeRanger/dfaMinimizationComparison), thanks!
122
123## pcg : PCG random generator
124
125Playing with [PCG generators](http://www.pcg-random.org/) in OCaml.
126Not even alpha, consider this doesn't exist."""
127url {
128 src:
129 "https://github.com/let-def/grenier/releases/download/v0.11/grenier-v0.11.tbz"
130 checksum: [
131 "sha256=658e1ad6fc5fdce0871975b3ebcb3ec760248be63cdb9ea965e3121cc7478d77"
132 "sha512=d9ff83f1b025f34c22af5921444993df219761dcee8d8cb5a940f266df8677278967434b22314c5c82d5d983e4c94c04cd52c4717d5c1f22fbd3a022631fae1c"
133 ]
134}