-- This package gives specifications for the TREE and FOREST data types.
-- It assumes that trees are ordered trees with at most 10 children.
-- It assumes that forests contain at most 10 trees.

with text_io; use text_io;

package tree_package is 

  type tree is private;
  type treeptr is access tree;
  type forest is private;
  type forestptr is access forest;
  type strptr is access string;

-- Operations for the TREE data type are:
--   A function MAKE_LEAF that takes a STRING and returns a tree with 
--     no children and with the string as its data element.
--   A function GET_DATA that takes a TREE pointer and returns a pointer
--     to the data.
--   A function GET_CHILD that takes a TREE pointer and an integer I and
--     returns a pointer to the Ith child of the tree.
--   A procedure SET_CHILD that takes two TREE pointers and an integer I
--     and makes the second tree the Ith child of the first tree.
--   Two TRAVERSE procedures, each taking a TREE pointer and printing
--     an indented representation of a preorder traversal of the tree.
--     The second procedure writes this traversal to a specified file
--     (the file argument is the first argument, and is of type FILE_TYPE).
--     The first procedure writes to the standard output file, and takes
--     the pointer to the tree as its only argument.

  function make_leaf(d:string) return treeptr;
  function get_data(t:treeptr) return strptr;
  function get_child(t:treeptr; i:integer) return treeptr;
  procedure set_child(par:in out treeptr; child:treeptr; i:integer);
  procedure traverse(t:treeptr);
  procedure traverse(ft:FILE_TYPE;t:treeptr);


-- Operations for the FOREST data type are:
-- A function of no arguments that returns a pointer to a new, empty
--   FOREST
-- A procedure that given pointers to a TREE and a FOREST, adds the
--   tree to the forest
-- Two procedures that traverse forests by traversing each tree in 
--   the forest.  Both take pointers to forests as arguments; the
--   second takes an argument of FILE_TYPE giving the file to which
--   the traversal is to be printed.  The first prints to standard
--   output.

  function new_forest return forestptr;
  procedure add_to_forest(t:treeptr; f:in out forestptr);
  procedure traverse(f:forestptr);
  procedure traverse(ft:FILE_TYPE;f:forestptr);


private
  type childlist is array(1..10) of treeptr;
  type childptr is access childlist;
  type tree is
     record
       data:  strptr;          -- note that these are pointers
       child: childptr;       -- 
     end record;

-- temporarily assumes that max size of forest = max # of children
  type forest is
    record
      size:integer;            -- the # of trees currently in the forest
      component:childptr;
    end record;

end tree_package;