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.13.0.tbz
sha256=9670bac52dcb93ea1bfc1afaf7846bc100bcdc63a7a468d5eb43f2b7660c2da9
sha512=aa182adb046c50f6e4742e59a18efdae2c3dd5d175a231bd8b84391351b0d4bda8dd9b1e3a4c8e71770dfc8fd1ab4f5f3cb32ab3062953f76faa435b441c3894

doc/patricia-tree/PatriciaTree/NodeWithId/index.html

Module PatriciaTree.NodeWithIdSource

Here, nodes also contain a unique id, e.g. so that they can be used as keys of maps or hash-tables.

Parameters

module Key : sig ... end

Signature

include NODE with type 'a key = 'a Key.t with type ('key, 'map) value = ('key, 'map) Value.t

Types

Sourcetype 'a key = 'a Key.t

The type of keys.

Sourcetype ('key, 'map) value = ('key, 'map) Value.t

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

Sourcetype 'map t

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

Constructors: build values

Sourceval empty : 'map t

The empty map

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

A singleton leaf, similar to BASE_MAP.singleton

Sourceval 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

Sourcetype '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.

Sourceval is_empty : 'map t -> bool

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

Sourceval view : 'a t -> 'a view

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

Sourceval to_int : 'a t -> int

Unique number for each node.

This is not hash-consing. Equal nodes created separately will have different identifiers. On the flip side, nodes with equal identifiers will always be physically equal.