Annotation of OpenXM_contrib/PHC/Ada/Schubert/localization_posets.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 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