Return to pieri_root_counts.ads CVS log

Up to [local] / OpenXM_contrib / PHC / Ada / Schubert

Annotation of OpenXM_contrib/PHC/Ada/Schubert/pieri_root_counts.ads, Revision 1.1.1.1

1.1       maekawa     1: with text_io;                            use text_io;
                      2: with Generic_Lists;
                      3: with Pieri_Trees;                        use Pieri_Trees;
                      4:
                      5: package Pieri_Root_Counts is
                      6:
                      7: -- DESCRIPTION :
                      8: --   This package executes the combinatorial root counting method based on
                      9: --   the construction of Pieri trees and provides data structures to perform
                     10: --   the Pieri deformations.  These deformations start at the leaves that
                     11: --   satisfy Pieri's condition for which a triple intersection of planes
                     12: --   leads to a unique solution.  They continue following the chains that
                     13: --   end at those leaves.  These chains are indexed by the pairs of leaves.
                     14: --   So a list of paired nodes suffices to run the Pieri homotopy algorithm.
                     15: --   For efficiency one wants to avoid the repeated generation of the same
                     16: --   equations at every node.  Therefore a tree of paired nodes is needed.
                     17: --   In the creation of this tree, a chain is traversed in increasing order.
                     18:
                     19: -- DATA STRUCTURES :
                     20:
                     21:   type Paired_Nodes is record
                     22:     left,right : Link_to_Pieri_Node;
                     23:   end record;
                     24:
                     25:   package Lists_of_Paired_Nodes is new Generic_Lists(Paired_Nodes);
                     26:   type List_of_Paired_Nodes is new Lists_of_Paired_Nodes.List;
                     27:
                     28:   type Paired_Chain is array ( integer range <> ) of Paired_Nodes;
                     29:
                     30:   type Nodal_Pair;
                     31:   type Link_to_Nodal_Pair is access Nodal_Pair;
                     32:   type Nodal_Matrix
                     33:          is array (integer range <>,integer range <>) of Link_to_Nodal_Pair;
                     34:
                     35:   type Nodal_Pair ( d : natural ) is record
                     36:     pnd : Paired_Nodes;
                     37:     sols : natural;                       -- #paths arriving at the node
                     38:     children : Nodal_Matrix(0..d,0..d);   -- indices in children are jumps
                     39:     ancestor : Link_to_Nodal_Pair;
                     40:   end record;
                     41:
                     42: -- CREATORS :
                     43:
                     44:   function Create ( n,d : natural; t1,t2 : Pieri_Tree )
                     45:                   return List_of_Paired_Nodes;
                     46:
                     47:   -- DESCRIPTION :
                     48:   --   Creates a list of paired nodes that satisfy Pieri's condition.
                     49:
                     50:   function Create ( pnd : Paired_Nodes ) return Paired_Chain;
                     51:
                     52:   -- DESCRIPTION :
                     53:   --   Returns the chain of nodes that start at the first branch point down
                     54:   --   and end at the given pair of leaves pnd.
                     55:   --   This is an intermediate data structure in the Create operation below.
                     56:
                     57:   function Create ( d : natural; lp : List_of_Paired_Nodes ) return Nodal_Pair;
                     58:
                     59:   -- DESCRIPTION :
                     60:   --   Creates a tree of nodal pairs and returns its root.
                     61:   --   The tree structure allows repeated nodes.
                     62:   --   A node that occured already once has sols equal to zero.
                     63:
                     64: -- SELECTORS :
                     65:
                     66:   function Height ( pnd : Paired_Nodes ) return natural;
                     67:
                     68:   -- DESCRIPTION :
                     69:   --   Returns Max(pnd.left.h,pnd.right.h).
                     70:
                     71:   function Equal ( pnd1,pnd2 : Paired_Nodes ) return boolean;
                     72:
                     73:   -- DESCRIPTION :
                     74:   --   Returns true when both nodes are the same.
                     75:
                     76:   function At_First_Branch_Point ( pnd : Paired_Nodes ) return boolean;
                     77:
                     78:   -- DESCRIPTION :
                     79:   --   Returns true when the current pair of nodes is at the first
                     80:   --   branch point in the Pieri trees.
                     81:
                     82:   function At_Leaves ( pnd : Paired_Nodes ) return boolean;
                     83:
                     84:   -- DESCRIPTION :
                     85:   --   Returns true when the current pair of nodes consists of leaves.
                     86:
                     87:   function Ancestor ( pnd : Paired_Nodes ) return Paired_Nodes;
                     88:
                     89:   -- DESCRIPTION :
                     90:   --   Returns the pair of ancestor nodes to the given pair of nodes.
                     91:
                     92:   function First_Branch_Point ( pnd : Paired_Nodes ) return Paired_Nodes;
                     93:
                     94:   -- DESCRIPTION :
                     95:   --   Returns the pair of nodes down in the chains of pnd where the
                     96:   --   first branch point occurs.
                     97:
                     98:   function Height ( np : Nodal_Pair ) return natural;
                     99:
                    100:   -- DESCRIPTION :
                    101:   --   Returns the number of nodes above the current nodal pair.
                    102:
                    103:   function Is_In ( root : Nodal_Pair; pnd : Paired_Nodes ) return boolean;
                    104:
                    105:   -- DESCRIPTION :
                    106:   --   Returns true if the paired nodes occur somewhere in the tree of
                    107:   --   nodal pairs starting at the root.
                    108:
                    109:   function Number_of_Paths ( root : Nodal_Pair ) return natural;
                    110:
                    111:   -- DESCRIPTION :
                    112:   --   Returns the number of paths that need to be followed.
                    113:
                    114: -- FORMATTED OUTPUT :
                    115:
                    116:   procedure Write ( file : in file_type; chn : in Paired_Chain );
                    117:
                    118:   -- DESCRIPTION :
                    119:   --   Writes the chain of paired nodes in a formatted way.
                    120:
                    121:   procedure Write ( file : in file_type; root : in Nodal_Pair );
                    122:
                    123:   -- DESCRIPTION :
                    124:   --   Writes the tree of paired nodes on file in a formatted way.
                    125:
                    126: end Pieri_Root_Counts;