Annotation of OpenXM_contrib/PHC/Ada/Schubert/localization_posets.ads, Revision 1.1
1.1 ! maekawa 1: with Standard_Natural_Vectors; use Standard_Natural_Vectors;
! 2: with Brackets; use Brackets;
! 3:
! 4: package Localization_Posets is
! 5:
! 6: -- DESCRIPTION :
! 7: -- This package provides an abstraction of a poset of localization patterns.
! 8: -- A localization pattern is characterized by top and bottom pivots,
! 9: -- represented by a pair of brackets. In constructing the poset we can
! 10: -- decrement the top pivots or increment the bottom pivots, when moving
! 11: -- to lower-dimensional spaces that contain the special p-planes.
! 12: -- We denote the Grassmannian of all p-planes in n-space by G(p,m+p),
! 13: -- where n = m+p.
! 14:
! 15: -- DATASTRUCTURES :
! 16:
! 17: type Node_Type is (top,bottom,mixed);
! 18:
! 19: type Node;
! 20: type Link_to_Node is access Node;
! 21:
! 22: type Array_of_Nodes is array ( integer range <> ) of Link_to_Node;
! 23: type Link_to_Array_of_Nodes is access Array_of_Nodes;
! 24: type Array_of_Array_of_Nodes is
! 25: array ( integer range <> ) of Link_to_Array_of_Nodes;
! 26:
! 27: type Matrix_of_Nodes is
! 28: array ( integer range <>, integer range <> ) of Link_to_Node;
! 29:
! 30: type Node ( p : natural ) is record
! 31: tp : Node_Type; -- type of node
! 32: level,label : natural; -- coordinates in poset
! 33: roco : integer; -- root count, also as flag
! 34: top,bottom : Bracket(1..p); -- top(i) <= bottom(i)
! 35: prev_sibling : Link_to_Node; -- previous node at same level
! 36: next_sibling : Link_to_Node; -- next node at same level
! 37: children : Matrix_of_Nodes(0..p,0..p);
! 38: child_labels : Link_to_Vector;
! 39: end record;
! 40: -- The level of a node is a natural number between m*p+q*(m+p) and 0,
! 41: -- children nodes have a level number that is one less.
! 42: -- At a leaf in the poset, level = 0 and the p-plane is completely specified.
! 43: -- At the root of the poset, level = m*p and any p-plane will fit it.
! 44: -- For the quantum case, the bottom level is m*p+q*(m+p).
! 45: -- In going up in the poset, the top pivots are incremented and
! 46: -- the bottom pivots are decremented, keeping top(i) <= bottom(i).
! 47: -- The field roco (root count) is determined by the root counting procedure.
! 48: -- At a leaf, roco = 1. At a node, roco = sum of roco's of its children.
! 49: -- The labels of the children are determined in a indexed poset.
! 50:
! 51: -- CREATORS :
! 52:
! 53: function Trivial_Root ( m,p : natural ) return Node;
! 54:
! 55: -- DESCRIPTION :
! 56: -- Returns the root of the localization poset, with top and bottom pivots
! 57: -- for the trivial localization pattern for any p-plane in (m+p)-space.
! 58: -- The level of the trivial root equals m+p.
! 59:
! 60: function Trivial_Root ( m,p,q : natural ) return Node;
! 61:
! 62: -- DESCRIPTION :
! 63: -- Returns the root for the poset to count all curves of degree q.
! 64: -- The case q = 0 is the default, as implemented by the routine above.
! 65:
! 66: procedure Top_Create ( root : in out Link_to_Node; n : in natural );
! 67:
! 68: -- DESCRIPTION :
! 69: -- Creates a poset consistently incrementing top pivots,
! 70: -- where n is the maximal entry in a top pivot.
! 71:
! 72: procedure Q_Top_Create ( root : in out Link_to_Node; n,lag : in natural );
! 73:
! 74: -- DESCRIPTION :
! 75: -- Creates a poset consistently incrementing top pivots,
! 76: -- where n is the maximal entry in a top pivot and lag the maximal
! 77: -- space between first and last entry, typically, lag = m+p.
! 78: -- For root = Trivial_Root(m,p,q) this poset will serve to count all
! 79: -- maps of degree q in G(p,m+p) that meet m*p+q*(m+p) general m-planes.
! 80:
! 81: procedure Top_Create ( root : in out Link_to_Node;
! 82: k : in Bracket; n : in natural );
! 83:
! 84: -- DESCRIPTION :
! 85: -- Creates the poset by incrementing top pivots, with k = co-dimensions.
! 86: -- By default, compared to the other Top_Create, all k's are one.
! 87: -- So all nodes created are of type "top".
! 88:
! 89: procedure Q_Top_Create ( root : in out Link_to_Node;
! 90: k : in Bracket; n,lag : in natural );
! 91:
! 92: -- DESCRIPTION :
! 93: -- Quantum analogue for creation of poset incrementing top pivots
! 94: -- for given co-dimension conditions.
! 95:
! 96: procedure Bottom_Create ( root : in out Link_to_Node );
! 97:
! 98: -- DESCRIPTION :
! 99: -- Creates a poset consistently decrementing bottom pivots.
! 100: -- So all nodes created are of type "bottom".
! 101:
! 102: procedure Q_Bottom_Create ( root : in out Link_to_Node; lag : in natural );
! 103:
! 104: -- DESCRIPTION :
! 105: -- Creates a poset consistently decrementing bottom pivots for counting
! 106: -- all maps of degree q with root = Trivial_Root(m,p,q).
! 107: -- The parameter lag > max space between first and last entry in brackets.
! 108:
! 109: procedure Bottom_Create ( root : in out Link_to_Node; k : in Bracket );
! 110:
! 111: -- DESCRIPTION :
! 112: -- Creates the poset by decrementing bottom pivots, k = co-dimensions.
! 113: -- By default, compared to the other Bottom_Create, all k's are one.
! 114:
! 115: procedure Q_Bottom_Create ( root : in out Link_to_Node; k : in Bracket;
! 116: lag : in natural );
! 117:
! 118: -- DESCRIPTION :
! 119: -- Quantum analogue for creation of poset decrementing bottom pivots
! 120: -- for given co-dimension conditions.
! 121:
! 122: procedure Top_Bottom_Create ( root : in out Link_to_Node; n : in natural );
! 123:
! 124: -- DESCRIPTION :
! 125: -- Creates a poset by incrementing top and decrementing bottom pivots.
! 126:
! 127: procedure Q_Top_Bottom_Create ( root : in out Link_to_Node;
! 128: n,lag : in natural );
! 129:
! 130: -- DESCRIPTION :
! 131: -- Creates a poset by incrementing top and decrementing bottom pivots
! 132: -- to count all maps of degree q in G(p,m+p) that meet m*p+q*(m+p)
! 133: -- general m-planes.
! 134:
! 135: procedure Top_Bottom_Create ( root : in out Link_to_Node;
! 136: k : in Bracket; n : in natural );
! 137:
! 138: -- DESCRIPTION :
! 139: -- Creates a poset by incrementing top and decrementing bottom pivots.
! 140: -- The vector k contains co-dimensions. All nodes are of type "mixed".
! 141:
! 142: procedure Q_Top_Bottom_Create ( root : in out Link_to_Node;
! 143: k : in Bracket; n,lag : in natural );
! 144:
! 145: -- DESCRIPTION :
! 146: -- Quantum analogue for creation of poset in mixed fashion,
! 147: -- for given co-dimension conditions.
! 148:
! 149: function Create_Leveled_Poset ( root : Link_to_Node ) return Array_of_Nodes;
! 150:
! 151: -- DESCRIPTION :
! 152: -- The array on return contains points to the first node at each level.
! 153:
! 154: function Create_Indexed_Poset ( poset : Array_of_Nodes )
! 155: return Array_of_Array_of_Nodes;
! 156:
! 157: -- DESCRIPTION :
! 158: -- Returns the poset structure where every node has a unique label.
! 159: -- Every node contains a vector with labels to the children.
! 160: -- The coordinates of every node in the poset on return is uniquely
! 161: -- determined by level and label, as poset(node.level)(node.label).
! 162:
! 163: -- SELECTORS :
! 164:
! 165: function Equal ( nd1,nd2 : Node ) return boolean;
! 166:
! 167: -- DESCRIPTION :
! 168: -- Returns true if the levels, top and bottom pivots are equal
! 169: -- for both nodes. False is returned otherwise.
! 170:
! 171: function Is_Leaf ( nd : Node ) return boolean;
! 172:
! 173: -- DESCRIPTION :
! 174: -- Returns true if the node has all its children empty.
! 175:
! 176: function Find_Node ( root : Link_to_Node; lvl : natural )
! 177: return Link_to_Node;
! 178:
! 179: -- DESCRIPTION :
! 180: -- Finds the first node at the given level.
! 181:
! 182: function Number_of_Siblings ( nd : Link_to_Node ) return natural;
! 183:
! 184: -- DESCRIPTION :
! 185: -- If nd = null, then 0 is returned else the number of return
! 186: -- equals the number of nonzero siblings plus one.
! 187:
! 188: function Number_of_Children ( nd : Node ) return natural;
! 189:
! 190: -- DESCRIPTION :
! 191: -- Returns the number of children of the node.
! 192:
! 193: -- ITERATORS :
! 194:
! 195: generic
! 196: with procedure Report ( lvlnd : in Node; continue : out boolean );
! 197: procedure Enumerate_Siblings ( nd : in Node );
! 198:
! 199: -- DESCRIPTION :
! 200: -- Visits all siblings of the given node and calls Report on each of them.
! 201:
! 202: generic
! 203: with procedure Report ( lnd : in Link_to_Node; continue : out boolean );
! 204: procedure Enumerate_Grand_Children ( nd : in Node; k : in positive );
! 205:
! 206: -- DESCRIPTION :
! 207: -- Enumerates all grandchildren of the node nd, k generations deep.
! 208: -- For k = 1, these are just the children of nd.
! 209:
! 210: generic
! 211: with procedure Modify ( lvlnd : in out Node; continue : out boolean );
! 212: procedure Modify_Siblings ( nd : in out Node );
! 213:
! 214: -- DESCRIPTION :
! 215: -- Runs through all siblings of the node and calls Modify on each of them.
! 216:
! 217: -- COMBINATORIAL ROOT COUNTING :
! 218:
! 219: procedure Count_Roots ( poset : in out Array_of_Nodes );
! 220:
! 221: -- DESCRIPTION :
! 222: -- Counts the roots by assigning roco fields in the leveled poset.
! 223: -- The total number of roots equals poset(poset'last).roco.
! 224:
! 225: function Row_Root_Count_Sum
! 226: ( poset : Array_of_Nodes; i : natural ) return natural;
! 227:
! 228: -- DESCRIPTION :
! 229: -- Sums up all the root counts at the i-th level in the poset.
! 230:
! 231: function Root_Count_Sum ( poset : Array_of_Nodes ) return natural;
! 232:
! 233: -- DESCRIPTION :
! 234: -- Returns the sum of all root counts over levels 1 and higher.
! 235: -- This amount equals the number of paths that need to be traced.
! 236:
! 237: -- DESTRUCTORS :
! 238:
! 239: procedure Clear ( nd : in out Node );
! 240:
! 241: -- DESCRIPTION :
! 242: -- Deallocation of the siblings.
! 243:
! 244: procedure Clear ( lnd : in out Link_to_Node );
! 245:
! 246: -- DESCRIPTION :
! 247: -- Releases the memory.
! 248:
! 249: procedure Clear ( arrnd : in out Array_of_Nodes );
! 250:
! 251: -- DESCRIPTION :
! 252: -- Deallocation of the memory sibling after sibling.
! 253:
! 254: procedure Clear ( arrnd : in out Link_to_Array_of_Nodes );
! 255:
! 256: -- DESCRIPTION :
! 257: -- Release of the pointers and deallocation of memory.
! 258:
! 259: procedure Clear ( arrnd : in out Array_of_Array_of_Nodes );
! 260:
! 261: -- DESCRIPTION :
! 262: -- Deallocation of all nodes in all arrays.
! 263:
! 264: procedure Clear ( matnd : in out Matrix_of_Nodes );
! 265:
! 266: -- DESCRIPTION :
! 267: -- Applies the nodes destructor to every element in the matrix.
! 268:
! 269: end Localization_Posets;
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to localization_posets.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