Return to pieri_trees.ads CVS log

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

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

1.1       maekawa     1: with Standard_Natural_Vectors;           use Standard_Natural_Vectors;
                      2: with Brackets;                           use Brackets;
                      3:
                      4: package Pieri_Trees is
                      5:
                      6: -- DESCRIPTION :
                      7: --   A Pieri tree is a combinatorial model for the Pieri homotopy algorithm.
                      8: --   The nodes contain brackets.  The root of a Pieri tree is the bracket
                      9: --   [1 2 .. d], which is the bracket with the lowest sum of entries.
                     10: --   Nodes situated at the same height in the tree all have the same sum
                     11: --   of their entries.  If this sum is S, then nodes at the next level
                     12: --   have sum S+1, nodes at the previous level have sum S-1.
                     13: --   Given a vector r(r(0),r(1),..,r(r'last)), the Pieri tree t(r) collects
                     14: --   all chains of length r(0)+r(1)+..+r(r'last) or equivalently of height
                     15: --   r(0)+r(1)+..+r(r'last)+1, that increase everywhere, except possibly
                     16: --   at levels r(0)+1, r(0)+r(1)+1, .., and r(0)+r(1)+..+r(r'last-1)+1.
                     17:
                     18: -- DATA STRUCTURES :
                     19:
                     20:   type Pieri_Node;
                     21:   type Link_to_Pieri_Node is access Pieri_Node;
                     22:   type Array_of_Pieri_Nodes is Array (integer range <>) of Link_to_Pieri_Node;
                     23:
                     24:   type Pieri_Node ( d : natural ) is record
                     25:     c,i,h : natural;
                     26:     node : Bracket(1..d);
                     27:     children : Array_of_Pieri_Nodes(1..d);
                     28:     ancestor : Link_to_Pieri_Node;
                     29:   end record;
                     30:   -- The "c" is the number of the plane that is folded in at the closest
                     31:   -- node down that is a jumping-decreasing node.
                     32:   -- A jumping-decreasing node is a node where decreasing may occur.
                     33:   -- The "i" indicates how close the node is to the next jumping-decreasing
                     34:   -- node down in the Pieri tree.  At such a node, i = 0.
                     35:   -- The "h" is the height of the node in the Pieri tree, at the root h = 0.
                     36:   -- When children(i) /= null, the ith index has increased by one.
                     37:
                     38:   type Pieri_Tree ( d,a : natural ) is record
                     39:     branches : Vector(0..a);          -- # branching-with-decrease levels
                     40:     root : Link_to_Pieri_Node;
                     41:   end record;
                     42:
                     43:   type Bracket_Array is array ( integer range <> ) of Link_to_Bracket;
                     44:
                     45: -- CREATOR :
                     46:
                     47:   function Create ( n,d : natural; r : Vector ) return Pieri_Tree;
                     48:
                     49:   -- DESCRIPTION :
                     50:   --   Returns a Pieri tree T(r(0),r(1),..,r(r'last)), where the nodes
                     51:   --   contain brackets with d entries chosen from {1,2,..,n}.
                     52:   --   The Pieri tree contains r(0)+r(1)+..+r(r'last)+1 levels of nodes.
                     53:   --   Decreasing may occur at levels r(0)+1,r(0)+r(1)+1,.., up to
                     54:   --   level r(0)+r(1)+..+r(r'last-1)+1.
                     55:
                     56: -- SELECTORS :
                     57:
                     58:   function Height ( t : Pieri_Tree ) return natural;
                     59:
                     60:   -- DESCRIPTION :
                     61:   --   Returns the number of levels in the Pieri tree t.
                     62:
                     63:   function Is_Leaf ( nd : Pieri_Node ) return boolean;
                     64:
                     65:   -- DESCRIPTION :
                     66:   --   Returns true if the node has no children.
                     67:
                     68:   function Jump ( b1,b2 : Bracket ) return natural;
                     69:
                     70:   -- DESCRIPTION :
                     71:   --   Returns the largest index j such that b1(j) < b2(j),
                     72:   --   or zero when no such index exists.
                     73:
                     74:   function Jump ( nd : Pieri_Node ) return natural;
                     75:
                     76:   -- DESCRIPTION :
                     77:   --   Returns the largest index of increase with the ancestor nodes,
                     78:   --   or zero when there is no ancestor.
                     79:
                     80:   function Lower_Jump_Decrease ( nd : Pieri_Node ) return Bracket;
                     81:
                     82:   -- DESCRIPTION :
                     83:   --   Returns a bracket at the node where decreasing may occur.
                     84:   --   If the current node is such a jumping-decreasing node,
                     85:   --   then the bracket at the node nd is returned,
                     86:   --   otherwise, the bracket at the next jumping-decreasing node
                     87:   --   down the tree is returned.
                     88:   --   In case nd.c = 0, or nd has no ancestors, then also nd.node
                     89:   --   is returned.
                     90:
                     91:   function Lowest_Jump_Decrease ( nd : Pieri_Node ) return Bracket;
                     92:
                     93:   -- DESCRIPTION :
                     94:   --    Returns the bracket at the lowest node where decreasing may occur.
                     95:
                     96:   function Upper_Jump_Decrease ( nd : Pieri_Node ) return Bracket;
                     97:
                     98:   -- DESCRIPTION :
                     99:   --   Returns a bracket at the node where decreasing may occur,
                    100:   --   similarly as the function above, but now up in the tree,
                    101:   --   each time taking the last index in the brackets to jump.
                    102:
                    103:   generic
                    104:     with procedure Visit_Node ( lnd : in Link_to_Pieri_Node;
                    105:                                 continue : out boolean );
                    106:   procedure Enumerate_Nodes ( t : in Pieri_Tree; level : in natural );
                    107:
                    108:   -- DESCRIPTION :
                    109:   --   Enumerates all nodes at the same level.  The root is at level 1.
                    110:
                    111:   generic
                    112:     with procedure Visit_Chain ( b : in Bracket_Array; continue : out boolean );
                    113:   procedure Enumerate_Chains ( t : in Pieri_Tree );
                    114:
                    115:   -- DESCRIPTION :
                    116:   --   Enumerates all chains in the Pieri tree.
                    117:
                    118:   generic
                    119:     with procedure Visit_Paired_Chain ( b1,b2 : in Bracket_Array;
                    120:                                         continue : out boolean );
                    121:   procedure Enumerate_Paired_Chains ( t1,t2 : in Pieri_Tree );
                    122:
                    123:   -- DESCRIPTION :
                    124:   --   Enumerates all pairs of chains.
                    125:
                    126:   function Pieri_Condition ( n : natural; b1,b2 : Bracket ) return boolean;
                    127:
                    128:   -- DESCRIPTION :
                    129:   --   Returns true if the pair of brackets satisfies Pieri's condition.
                    130:   --   The number n equals m+p, and is the range of numbers to choose from.
                    131:
                    132:   -- REQUIRED : b1'range = b2'range and b1(i) <= n >= b2(i).
                    133:
                    134: -- DESTRUCTORS :
                    135:
                    136:   procedure Clear ( nd : in out Link_to_Pieri_Node );
                    137:
                    138:   -- DESCRIPTION :
                    139:   --   Deallocation of the memory space occupied by the node.
                    140:
                    141:   procedure Clear ( t : in out Pieri_Tree );
                    142:
                    143:   -- DESCRIPTION :
                    144:   --   Deallocation of the memory space occupied by the Pieri tree t.
                    145:
                    146: end Pieri_Trees;