tree.mli (3060B)
1 (* Unison file synchronizer: src/tree.mli *) 2 (* Copyright 1999-2020, Benjamin C. Pierce (see COPYING for details) *) 3 4 (* An ('a, 'b) t is a tree with 'a-labeled arcs and 'b-labeled nodes. *) 5 (* Labeling for the internal nodes is optional *) 6 type ('a, 'b) t = 7 Node of ('a * ('a, 'b) t) list * 'b option 8 | Leaf of 'b 9 10 val m : 'a Umarshal.t -> 'b Umarshal.t -> ('a, 'b) t Umarshal.t 11 12 (* An "unfinished" tree *) 13 type ('a, 'b) u 14 15 (* ------------------------------------------------------------------------- *) 16 (* Functions for unfinished tree (u-tree) *) 17 (* ------------------------------------------------------------------------- *) 18 19 (* start an empty u-tree *) 20 val start : ('a, 'b) u 21 22 (* add t v: add a node with label "v" at the current position *) 23 val add : ('a, 'b) u -> 'b -> ('a, 'b) u 24 25 (* enter t n: create a new subtree, with leading arc labeled "v", at the *) 26 (* current position *) 27 val enter : ('a, 'b) u -> 'a -> ('a, 'b) u 28 29 (* go up one-level *) 30 val leave : ('a, 'b) u -> ('a, 'b) u 31 32 (* ------------------------------------------------------------------------- *) 33 (* From u-trees to trees *) 34 (* ------------------------------------------------------------------------- *) 35 36 (* "finish" up the tree construction and deliver a tree precondition: *) 37 (* already at the top-level of the tree *) 38 val finish : ('a, 'b) u -> ('a, 'b) t 39 40 (* from the u-tree, deliver a tree (by going back to top-level and "finish") *) 41 (* and the skeleton u-tree, which represents the current position *) 42 val slice : ('a, 'b) u -> ('a, 'b) t * ('a, 'b) u 43 44 (* ------------------------------------------------------------------------- *) 45 (* Functions for trees *) 46 (* ------------------------------------------------------------------------- *) 47 48 (* Test if the tree is empty *) 49 val is_empty : ('a, 'b) t -> bool 50 51 (* pointwise renaming of arcs and nodes *) 52 val map : ('a -> 'c) -> ('b -> 'd) -> ('a, 'b) t -> ('c, 'd) t 53 54 (* DFT the tree, keeping an accumulator for the path, and apply a function *) 55 (* to all the partial paths ended by a labeled node *) 56 val iteri : ('a, 'b) t -> 'c -> ('c -> 'a -> 'c) -> ('c -> 'b -> unit) -> unit 57 58 (* count the number of labeled nodes *) 59 val size : ('a, 'b) t -> int 60 61 (* DFT the tree, keep an accumulator for the path, and record all the *) 62 (* partial paths ended by a labeled node *) 63 val flatten : 64 ('a, 'b) t -> 'c -> ('c -> 'a -> 'c) -> ('c * 'b) list -> ('c * 'b) list