Annotation of OpenXM_contrib/PHC/Ada/Schubert/pieri_trees.ads, Revision 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;
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to pieri_trees.ads CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [local] / OpenXM_contrib / PHC / Ada / Schubert