package patricia-tree

  1. Overview
  2. Docs
Patricia Tree data structure in OCaml for maps and sets. Supports generic key-value pairs

Install 

dune-project
 Dependency

codex.top Readme Changelog Edit opam file Versions (6)

Authors

  1. M
    Matthieu Lemerre <matthieu.lemerre@cea.fr>
  2. D
    Dorian Lesbre <dorian.lesbre@cea.fr>

Maintainers

  1. D
    Dorian Lesbre <dorian.lesbre@cea.fr>

Sources

patricia-tree-0.14.0.tbz
sha256=32e5639ec6af0f7763d6bf48a8711d8d9cd0d79af1fc8cecf1c73a442c1c1fa7
sha512=749fb6696e83b88b782d70248cb646a8a7ac02d1e781f15d680ff1b41949b936259abd6979680fc9812b9c9cf8406ca24ccf3e785b8b7977519394a04d53f451

doc/patricia-tree/PatriciaTree/MutexProtectNode/argument-1-Node/index.html

Parameter MutexProtectNode.Node

We use a uniform type 'map view to pattern match on maps and sets The actual types 'map t can be a bit different from 'map view to allow for more efficient representations, but view should be a constant time operation for quick conversions.

Types

type 'key key

The type of keys.

type ('key, 'map) value

The type of value, which depends on the type of the key and the type of the map.

type 'map t

The type of the map, which is parameterized by a type.

Constructors: build values

val empty : 'map t

The empty map

val leaf : 'key key -> ('key, 'map) value -> 'map t

A singleton leaf, similar to BASE_MAP.singleton

val branch : prefix:int -> branching_bit:int -> tree0:'map t -> tree1:'map t -> 'map t

A branch node. This shouldn't be called externally unless you know what you're doing! Doing so could easily break the data structure's invariants.

When called, it assumes that:

  • Neither tree0 nor tree1 should be empty.
  • branching_bit should have a single bit set
  • prefix should be normalized (bits below branching_bit set to zero)
  • All elements of tree0 should have their to_int start by prefix followed by 0 at position branching_bit).
  • All elements of tree1 should have their to_int start by prefix followed by 0 at position branching_bit).

Destructors: access the value

type 'map view = private
  1. | Empty : 'map view
    (*

    Can happen only at the toplevel: there is no empty interior node.

    *)
  2. | Branch : {
    1. prefix : int;
    2. branching_bit : int;
    3. tree0 : 'map t;
    4. tree1 : 'map t;
    } -> 'map view
    (*

    Same constraints as branch:

    • branching_bit contains only one bit set; the corresponding mask is (branching_bit - 1).
    • prefix is normalized: the bits below the branching_bit are set to zero (i.e. prefix & (branching_bit - 1) = 0).
    • All elements of tree0 should have their to_int start by prefix followed by 0 at position branching_bit).
    • All elements of tree1 should have their to_int start by prefix followed by 0 at position branching_bit).
    *)
  3. | Leaf : {
    1. key : 'key key;
    2. value : ('key, 'map) value;
    } -> 'map view
    (*

    A key -> value mapping.

    *)

This makes the map nodes accessible to the pattern matching algorithm; this corresponds 1:1 to the SimpleNode implementation. This just needs to be copy-and-pasted for every node type.

val is_empty : 'map t -> bool

Check if the map is empty. Should be constant time.

val view : 'a t -> 'a view

Convert the map to a view. Should be constant time.