Module Plebeia.SegmentSource

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

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

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

    *)
Sourceval string_of_side : side -> string

For human readability. "L" or "R"

Sourceval string_of_sides : side list -> string

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

2 Segment

Sourcetype segment
Sourcetype t = segment
Sourceval normalize : t -> t

Normalize it using Encoding

Sourceval max_short_segment_length : int

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

Sourceval max_length : int

Maximum length of sides for a segment: 1815

Sourceval empty : t

The empty segment.

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

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

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

Normal (=) does not work

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

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

Sourceval 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'

Sourceval of_sides : side list -> t

Converts a list of side to a segment.

Sourceval to_sides : t -> side list
Sourceval unsafe_of_encoding : 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.

Sourceval to_encoding : t -> int * string
Sourceval to_string : t -> string

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

Sourceval of_string : string -> t option

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

Sourceval string_of_segments : t list -> string

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

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

3 Serialization

3 Data encoding

Sourceval 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

Sourcemodule Segs : sig ... end

append friendly segment list

Sourcemodule StringEnc : sig ... end