package plebeia

  1. Overview
  2. Docs
package plebeia
Legend:
Page
Library
Module
Module type
Parameter
Class
Class type
Source

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
OCaml

Innovation. Community. Security.

GitHub Discord Twitter Peertube RSS
About
Changelog Releases Industrial Users Academic Users Why OCaml
Ecosystem
Packages Community Events OCaml Planet Jobs
Resources
Install OCaml Get Started Platform Tools Language Manual Standard Library API Books Exercises Papers OCaml Playground Logo
Policies
Carbon Footprint Governance Privacy Code of Conduct