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