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     ! 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;