From: Kim Nguyễn Date: Tue, 5 Mar 2013 15:35:12 +0000 (+0100) Subject: Add an abstract generic interface for trees (of which Naive is an X-Git-Tag: v0.1~163 X-Git-Url: http://git.nguyen.vg/gitweb/?p=tatoo.git;a=commitdiff_plain;h=74e8f4bcdd9e19a2ec434d82c1a6eb897b826632 Add an abstract generic interface for trees (of which Naive is an implementation). --- diff --git a/src/tree.mlpack b/src/tree.mlpack index 933b481..599b18f 100644 --- a/src/tree.mlpack +++ b/src/tree.mlpack @@ -1 +1,2 @@ tree/Naive +tree/Sig diff --git a/src/tree/naive.ml b/src/tree/naive.ml index 37683f3..db1b202 100644 --- a/src/tree/naive.ml +++ b/src/tree/naive.ml @@ -14,7 +14,7 @@ (***********************************************************************) (* - Time-stamp: + Time-stamp: *) open Utils @@ -72,7 +72,7 @@ struct "NODE " ^ string_of_int n.preorder) let debug_node fmt node = - Format.fprintf fmt "{ tag=%s; preorder=%i; data=%s; first_child=%a; next_sibling=%a; parent=%a }" + Format.fprintf fmt "{ tag=%s; preorder=%i; data=%S; first_child=%a; next_sibling=%a; parent=%a }" (QName.to_string node.tag) node.preorder node.data @@ -264,7 +264,7 @@ let rec print_xml out tree_ node = in print_xml out tree_ node.next_sibling - +let print_xml out tree_ node = print_xml out tree_ { node with next_sibling = nil } let root t = t.root let first_child _ n = n.first_child let next_sibling _ n = n.next_sibling @@ -272,3 +272,5 @@ let parent _ n = n.parent let tag _ n = n.tag let data _ n = n.data let preorder _ n = n.preorder + +let print_node fmt n = Parser.debug_node fmt n diff --git a/src/tree/naive.mli b/src/tree/naive.mli index 60d1258..5e0a52e 100644 --- a/src/tree/naive.mli +++ b/src/tree/naive.mli @@ -14,67 +14,7 @@ (***********************************************************************) (* - Time-stamp: + Time-stamp: *) -(** Implementation of documents as binary trees *) - -type node -(** The type of a tree node *) - -type t -(** The type of trees *) - -val nil : node -(** Nil node, denoting the first/second child of a leaf or the parent of - the root *) - -val dummy : node -(** Dummy node that is guaranteed to never occur in any tree *) - -val load_xml_file : in_channel -> t -(** Takes a file descriptor and returns the XML data stored in the - corresponding file. Start at the current position in the file - descriptor (which is not necessarily the begining of file) -*) - -val load_xml_string : string -> t -(** Loads XML data stored in a string *) - -val print_xml : out_channel -> t -> node -> unit -(** Outputs the tree as an XML document on the given output_channel *) - - -val root : t -> node -(** Returns the root of the tree *) - -val first_child : t -> node -> node -(** [first_child t n] returns the first child of node [n] in tree [t]. - Returns [nil] if [n] is a leaf. Returns [nil] if [n == nil]. -*) - -val next_sibling : t -> node -> node -(** [next_sibling t n] returns the next_sibling of node [n] in tree [t]. - Returns [nil] if [n] is the last child of a node. - Returns [nil] if [n == nil]. -*) - -val parent : t -> node -> node -(** [next_sibling t n] returns the parent of node [n] in tree [t]. - Returns [nil] if [n] is the root of the tree. - Returns [nil] if [n == nil]. -*) - -val tag : t -> node -> Utils.QName.t -(** Returns the label of a given node *) - -val data : t -> node -> string -(** Returns the character data associated with a node. - The only node having character data are those whose label is - QName.text, QName.cdata_section or QName.comment - *) - -val preorder : t -> node -> int -(** Returns the position of a node in pre-order in the tree. The - root has preorder 0. [nil] has pre-order [-1]. -*) +include Sig.S diff --git a/src/tree/sig.ml b/src/tree/sig.ml new file mode 100644 index 0000000..f9bd0b7 --- /dev/null +++ b/src/tree/sig.ml @@ -0,0 +1,84 @@ +(***********************************************************************) +(* *) +(* TAToo *) +(* *) +(* Kim Nguyen, LRI UMR8623 *) +(* Université Paris-Sud & CNRS *) +(* *) +(* Copyright 2010-2012 Université Paris-Sud and Centre National de la *) +(* Recherche Scientifique. All rights reserved. This file is *) +(* distributed under the terms of the GNU Lesser General Public *) +(* License, with the special exception on linking described in file *) +(* ../LICENSE. *) +(* *) +(***********************************************************************) + +(* + Time-stamp: +*) + +(** Implementation of documents as binary trees *) +module type S = +sig + type node + (** The type of a tree node *) + + type t + (** The type of trees *) + + val nil : node + (** Nil node, denoting the first/second child of a leaf or the parent of + the root *) + + val dummy : node + (** Dummy node that is guaranteed to never occur in any tree *) + + val load_xml_file : in_channel -> t + (** Takes a file descriptor and returns the XML data stored in the + corresponding file. Start at the current position in the file + descriptor (which is not necessarily the begining of file) + *) + + val load_xml_string : string -> t + (** Loads XML data stored in a string *) + + val print_xml : out_channel -> t -> node -> unit + (** Outputs the tree as an XML document on the given output_channel *) + + + val root : t -> node + (** Returns the root of the tree *) + + val first_child : t -> node -> node + (** [first_child t n] returns the first child of node [n] in tree [t]. + Returns [nil] if [n] is a leaf. Returns [nil] if [n == nil]. + *) + + val next_sibling : t -> node -> node + (** [next_sibling t n] returns the next_sibling of node [n] in tree [t]. + Returns [nil] if [n] is the last child of a node. + Returns [nil] if [n == nil]. + *) + + val parent : t -> node -> node + (** [next_sibling t n] returns the parent of node [n] in tree [t]. + Returns [nil] if [n] is the root of the tree. + Returns [nil] if [n == nil]. + *) + + val tag : t -> node -> Utils.QName.t + (** Returns the label of a given node *) + + val data : t -> node -> string + (** Returns the character data associated with a node. + The only node having character data are those whose label is + QName.text, QName.cdata_section or QName.comment + *) + + val preorder : t -> node -> int + (** Returns the position of a node in pre-order in the tree. The + root has preorder 0. [nil] has pre-order [-1]. + *) + + val print_node : Format.formatter -> node -> unit +end