with text_io;                            use text_io;
with Generic_Lists;
with Pieri_Trees;                        use Pieri_Trees;

package Pieri_Root_Counts is

-- DESCRIPTION :
--   This package executes the combinatorial root counting method based on
--   the construction of Pieri trees and provides data structures to perform
--   the Pieri deformations.  These deformations start at the leaves that
--   satisfy Pieri's condition for which a triple intersection of planes
--   leads to a unique solution.  They continue following the chains that
--   end at those leaves.  These chains are indexed by the pairs of leaves.
--   So a list of paired nodes suffices to run the Pieri homotopy algorithm.
--   For efficiency one wants to avoid the repeated generation of the same
--   equations at every node.  Therefore a tree of paired nodes is needed.
--   In the creation of this tree, a chain is traversed in increasing order.

-- DATA STRUCTURES :

  type Paired_Nodes is record
    left,right : Link_to_Pieri_Node;
  end record;

  package Lists_of_Paired_Nodes is new Generic_Lists(Paired_Nodes);
  type List_of_Paired_Nodes is new Lists_of_Paired_Nodes.List;

  type Paired_Chain is array ( integer range <> ) of Paired_Nodes;

  type Nodal_Pair;
  type Link_to_Nodal_Pair is access Nodal_Pair;
  type Nodal_Matrix
         is array (integer range <>,integer range <>) of Link_to_Nodal_Pair;

  type Nodal_Pair ( d : natural ) is record
    pnd : Paired_Nodes;
    sols : natural;                       -- #paths arriving at the node
    children : Nodal_Matrix(0..d,0..d);   -- indices in children are jumps
    ancestor : Link_to_Nodal_Pair;
  end record;

-- CREATORS :

  function Create ( n,d : natural; t1,t2 : Pieri_Tree )
                  return List_of_Paired_Nodes;

  -- DESCRIPTION :
  --   Creates a list of paired nodes that satisfy Pieri's condition.

  function Create ( pnd : Paired_Nodes ) return Paired_Chain;

  -- DESCRIPTION :
  --   Returns the chain of nodes that start at the first branch point down
  --   and end at the given pair of leaves pnd.
  --   This is an intermediate data structure in the Create operation below.

  function Create ( d : natural; lp : List_of_Paired_Nodes ) return Nodal_Pair;

  -- DESCRIPTION :
  --   Creates a tree of nodal pairs and returns its root.
  --   The tree structure allows repeated nodes.
  --   A node that occured already once has sols equal to zero.

-- SELECTORS :

  function Height ( pnd : Paired_Nodes ) return natural;

  -- DESCRIPTION :
  --   Returns Max(pnd.left.h,pnd.right.h).

  function Equal ( pnd1,pnd2 : Paired_Nodes ) return boolean;

  -- DESCRIPTION :
  --   Returns true when both nodes are the same.

  function At_First_Branch_Point ( pnd : Paired_Nodes ) return boolean;

  -- DESCRIPTION :
  --   Returns true when the current pair of nodes is at the first
  --   branch point in the Pieri trees.

  function At_Leaves ( pnd : Paired_Nodes ) return boolean;

  -- DESCRIPTION :
  --   Returns true when the current pair of nodes consists of leaves.

  function Ancestor ( pnd : Paired_Nodes ) return Paired_Nodes;

  -- DESCRIPTION :
  --   Returns the pair of ancestor nodes to the given pair of nodes.

  function First_Branch_Point ( pnd : Paired_Nodes ) return Paired_Nodes;

  -- DESCRIPTION :
  --   Returns the pair of nodes down in the chains of pnd where the
  --   first branch point occurs.

  function Height ( np : Nodal_Pair ) return natural;

  -- DESCRIPTION :
  --   Returns the number of nodes above the current nodal pair.

  function Is_In ( root : Nodal_Pair; pnd : Paired_Nodes ) return boolean;

  -- DESCRIPTION :
  --   Returns true if the paired nodes occur somewhere in the tree of
  --   nodal pairs starting at the root.

  function Number_of_Paths ( root : Nodal_Pair ) return natural;

  -- DESCRIPTION :
  --   Returns the number of paths that need to be followed.

-- FORMATTED OUTPUT :

  procedure Write ( file : in file_type; chn : in Paired_Chain );

  -- DESCRIPTION :
  --   Writes the chain of paired nodes in a formatted way.

  procedure Write ( file : in file_type; root : in Nodal_Pair );

  -- DESCRIPTION :
  --   Writes the tree of paired nodes on file in a formatted way.

end Pieri_Root_Counts;