package plebeia

  1. Overview
  2. Docs
Legend:
Library
Module
Module type
Parameter
Class
Class type

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

type side =
  1. | Left
  2. | Right
    (*

    Binary tree, by convention when a bool or a bit is used, 0 = false = Left and 1 = true = Right

    *)
val string_of_side : side -> string

For human readability. "L" or "R"

val string_of_sides : side list -> string

Human readable string representation of a side list, e.g. "LLLRLLRL"

2 Segment

type segment
type t = segment
val normalize : t -> t

Normalize it using Encoding

val max_short_segment_length : int

Maximum length of sides which fits with one cell with an index: 215

val max_length : int

Maximum length of sides for a segment: 1815

val empty : t

The empty segment.

val is_empty : t -> bool
val cut : t -> (side * t) option

Cuts a path into a head and tail if not empty. Also known as "snoc".

val get_side : t -> int -> side option
val drop : int -> t -> t
type fat = [ `Left | `Right | `Segment of t ] list
val unfat : fat -> t
val equal : t -> t -> bool

Normal (=) does not work

val equal_list : t list -> t list -> bool
val compare : t -> t -> int

Normal compare does not work. Note: this may call to_sides internally and therefore is not very light operaiton.

val common_prefix : t -> t -> t * t * t

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 of_sides : side list -> t

Converts a list of side to a segment.

val to_sides : t -> side list
val unsafe_of_bits : int -> string -> t

Fast 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 * string
val to_string : t -> string

Human readable string representation of a segment, e.g. "LLLRLLRL"

val of_string : string -> t option

Parse the string representation of a segment, e.g. "LLRLLRL"

val string_of_segments : t list -> string

Human readable string representation of segments: "LLRLRLL/RRRLL/.."

val pp : Format.formatter -> t -> unit
val pp_debug : Format.formatter -> t -> unit
val pp_segments : Format.formatter -> t list -> unit
val length : t -> int
val append : t -> t -> t
val concat : t list -> t
module Serialization : sig ... end

3 Serialization

3 Data encoding

val encoding : t Data_encoding.t

For 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 ... end

append friendly segment list

module StringEnc : sig ... end