A module encapsulating the concept of a path through the Patricia tree. A path is a sequence of n full segments. The n-1 first segments end in a bud and the nth ends in a leaf. Internal segments are bit of paths encoded in the internal nodes of the Patricia tree while tip segments represent the bits of path encoded close to the leaf.
2 Side
val string_of_side : side -> stringFor human readability. "L" or "R"
val string_of_sides : side list -> stringHuman readable string representation of a side list, e.g. "LLLRLLRL"
2 Segment
type t = segmentMaximum length of sides which fits with one cell with an index: 215
val empty : tThe empty segment.
val is_empty : t -> boolCuts a path into a head and tail if not empty. Also known as "snoc".
type fat = [ `Left | `Right | `Segment of t ] listNormal compare does not work. Note: this may call to_sides internally and therefore is not very light operaiton.
Factors a common prefix between two segments.
common_prefix t1 t2 = (prefix, t1', t2') then, t1 = append prefix t1' and t2 = append prefix t2'
val unsafe_of_bits : int -> string -> tFast build of a segment from a raw encoding data: the length and a string of LR bits postfixed by 0
,7
. No sanity check.
val to_bits : t -> int * stringval to_string : t -> stringHuman readable string representation of a segment, e.g. "LLLRLLRL"
val of_string : string -> t optionParse the string representation of a segment, e.g. "LLRLLRL"
val string_of_segments : t list -> stringHuman readable string representation of segments: "LLRLRLL/RRRLL/.."
val pp : Stdlib.Format.formatter -> t -> unitval pp_debug : Stdlib.Format.formatter -> t -> unitval pp_segments : Stdlib.Format.formatter -> t list -> unitval length : t -> intmodule Serialization : sig ... end 3 Serialization
3 Data encoding
val encoding : t Data_encoding.tFor encoding to JSON or binary using data-encoding.
Binary encoding:
<1B> <------- len bytes --------> +----+------------------------------+ |len |<- serialized segment sides ->| +----+------------------------------+
* The first byte is the length of the serialized segment sides part (1 .. 255) * The rest is the string of the serialized segment sides, which is the stream of segment bits (Left: 0, Right: 1) postfixed 10n (0 <= n <= 7) to make the stream fit in a string.
Example:
data | binary ---------------------- empty segment | 0180 LRLRLRLRL | 025540 LRLRLRLR | 025580 RRRRRRRRRRRRRRRRRRRR | 03fffff8
2 Segs: append friendly segment list
module Segs : sig ... endappend friendly segment list
module StringEnc : sig ... end