Annotation of OpenXM_contrib/PHC/Ada/Root_Counts/Implift/arrays_of_lists_utilities.adb, Revision 1.1.1.1
1.1 maekawa 1: with Integer_Support_Functions; use Integer_Support_Functions;
2: with Transformations; use Transformations;
3: with Transforming_Integer_Vector_Lists; use Transforming_Integer_Vector_Lists;
4: with Lists_of_Vectors_Utilities; use Lists_of_Vectors_Utilities;
5:
6: package body Arrays_of_Lists_Utilities is
7:
8: function All_Equal ( al : Array_of_Lists ) return boolean is
9: begin
10: for i in (al'first+1)..al'last loop
11: if not Is_Equal(al(al'first),al(i))
12: then return false;
13: end if;
14: end loop;
15: return true;
16: end All_Equal;
17:
18: function Interchange2 ( al : Array_of_Lists ) return Array_of_Lists is
19:
20: res : Array_of_Lists(al'range);
21: index : integer;
22:
23: begin
24: if Length_Of(al(al'first)) <= 2
25: then res := al;
26: else index := al'first;
27: for i in al'first+1..al'last loop
28: if Length_Of(al(i)) <= 2
29: then index := i;
30: else res(i) := al(i);
31: end if;
32: exit when index > al'first;
33: end loop;
34: if index = al'first
35: then res(index) := al(index);
36: else res(index) := al(al'first);
37: res(res'first) := al(index);
38: res(index+1..res'last) := al(index+1..al'last);
39: end if;
40: end if;
41: return res;
42: end Interchange2;
43:
44: function Index2 ( al : Array_of_Lists ) return integer is
45: begin
46: for i in al'range loop
47: if Length_Of(al(i)) <= 2
48: then return i;
49: end if;
50: end loop;
51: return al'first;
52: end Index2;
53:
54: procedure Mixture ( al : in Array_of_Lists;
55: perm,mix : out Link_to_Vector ) is
56:
57: wrkper,wrkmix : vector(al'range); -- intermediate results
58: nbd : natural := 0; -- # different sets
59: ind,min : integer;
60:
61: procedure Sort ( indal,indmix : in natural ) is
62:
63: -- DESCRIPTION :
64: -- Puts all lists which are equal to al(perm(index)) together.
65:
66: -- ON ENTRY :
67: -- indal the current entry in al;
68: -- indmix the current entry in wrkmix.
69:
70: begin
71: for j in indal+1..al'last loop
72: if Is_Equal(al(wrkper(indal)),al(wrkper(j)))
73: then if j /= indal + wrkmix(indmix)
74: then declare
75: pos : natural := indal + wrkmix(indmix);
76: tmppos : natural;
77: begin
78: tmppos := wrkper(j);
79: wrkper(j) := wrkper(pos);
80: wrkper(pos) := tmppos;
81: end;
82: end if;
83: wrkmix(indmix) := wrkmix(indmix) + 1;
84: end if;
85: end loop;
86: end Sort;
87:
88: procedure Permute ( ind,nb : in natural ) is
89:
90: -- DESCRIPTION :
91: -- Changes the permutation vector such that the entry given by
92: -- the index stands in front. The number of different supports is
93: -- given by the parameter nb.
94:
95: newper : vector(wrkper'range);
96: cntnew : natural := newper'first + wrkmix(ind);
97: cntwrk : natural := wrkper'first;
98:
99: begin
100: for i in 1..nb loop
101: if i /= ind
102: then for j in 0..wrkmix(i)-1 loop
103: newper(cntnew+j) := wrkper(cntwrk+j);
104: end loop;
105: cntnew := cntnew + wrkmix(i);
106: else for j in 0..wrkmix(ind)-1 loop
107: newper(newper'first+j) := wrkper(cntwrk+j);
108: end loop;
109: end if;
110: cntwrk := cntwrk + wrkmix(i);
111: end loop;
112: wrkper := newper;
113: end Permute;
114:
115: begin
116: -- INITIALIZATIONS :
117: for i in wrkper'range loop
118: wrkper(i) := i;
119: end loop;
120: wrkmix := (wrkmix'range => 1);
121: -- SORTING THE SETS :
122: ind := al'first;
123: while ind <= al'last loop
124: nbd := nbd + 1;
125: Sort(ind,nbd);
126: ind := ind + wrkmix(nbd);
127: end loop;
128: -- MINIMAL OCCURENCE SHOULD APPEAR FIRST :
129: ind := wrkmix'first;
130: min := wrkmix(ind);
131: for i in wrkmix'first+1..nbd loop
132: if wrkmix(i) < min
133: then min := wrkmix(i); ind := i;
134: end if;
135: end loop;
136: -- put("The type of mixture : " ); put(wrkmix(wrkmix'first..nbd)); new_line;
137: -- put("The permutation vector : "); put(wrkper); new_line;
138: if ind /= wrkmix'first
139: then Permute(ind,nbd);
140: wrkmix(ind) := wrkmix(wrkmix'first);
141: wrkmix(wrkmix'first) := min;
142: end if;
143: -- put("The type of mixture : " ); put(wrkmix(wrkmix'first..nbd)); new_line;
144: -- put("The permutation vector : "); put(wrkper); new_line;
145: -- RETURNING THE RESULTS :
146: perm := new Vector'(wrkper);
147: mix := new Vector'(wrkmix(wrkmix'first..nbd));
148: end Mixture;
149:
150: function Permute ( perm : Vector; al : in Array_of_Lists )
151: return Array_of_Lists is
152:
153: res : Array_of_Lists(al'range);
154:
155: begin
156: for i in al'range loop
157: res(i) := al(perm(i));
158: end loop;
159: return res;
160: end Permute;
161:
162: function Different_Points ( al : Array_of_Lists ) return List is
163:
164: tmp,res,res_last : List;
165:
166: begin
167: for i in (al'first+1)..al'last loop
168: tmp := al(i);
169: while not Is_Null(tmp) loop
170: declare
171: lv : Link_to_Vector := Head_Of(tmp);
172: begin
173: if not Is_In(res,lv.all)
174: then Append(res,res_last,lv.all);
175: end if;
176: end;
177: tmp := Tail_Of(tmp);
178: end loop;
179: end loop;
180: return res;
181: end Different_Points;
182:
183: function Different_Points ( al : Array_of_Lists ) return Array_of_Lists is
184:
185: res : Array_of_Lists(al'range);
186:
187: begin
188: res(res'first) := al(al'first);
189: for i in (al'first+1)..al'last loop
190: res(i) := Different_Points(al(i));
191: end loop;
192: return res;
193: end Different_Points;
194:
195: procedure Remove_Duplicates ( al : in out Array_of_Lists ) is
196: begin
197: for i in al'range loop
198: Remove_Duplicates(al(i));
199: end loop;
200: end Remove_Duplicates;
201:
202: procedure Shift ( al : in out Array_of_Lists; shiftvecs : in VecVec ) is
203: begin
204: for k in al'range loop
205: Shift(al(k),shiftvecs(k));
206: end loop;
207: end Shift;
208:
209: function Shift ( al : Array_of_Lists; shiftvecs : VecVec )
210: return Array_of_Lists is
211:
212: res : Array_of_Lists(al'range);
213:
214: begin
215: for k in res'range loop
216: res(k) := Shift(al(k),shiftvecs(k));
217: end loop;
218: return res;
219: end Shift;
220:
221: procedure Projection ( al : in Array_of_Lists; v : in Vector;
222: ind : integer; res : in out Array_of_Lists;
223: degenerate : out boolean ) is
224:
225: pv : integer;
226: t : Transfo := Build_Transfo(v,ind);
227:
228: procedure Clean ( i : in integer ) is
229: begin
230: for j in res'first..i loop
231: Deep_Clear(res(j));
232: end loop;
233: Clear(t);
234: end Clean;
235:
236: begin
237: degenerate := false;
238: for i in res'range loop
239: declare
240: pvl : List;
241: l : List renames al(i+1);
242: begin
243: pv := Maximal_Support(l,v);
244: pvl := Face(l,v,pv);
245: if Length_Of(pvl) <= 1
246: then degenerate := true;
247: Deep_Clear(pvl); Clean(i);
248: return;
249: else res(i) := Transform_and_Reduce(t,ind,pvl);
250: Remove_Duplicates(res(i));
251: if Length_Of(res(i)) <= 1
252: then degenerate := true;
253: Deep_Clear(pvl); Clean(i);
254: return;
255: end if;
256: end if;
257: Deep_Clear(pvl);
258: end;
259: end loop;
260: Clear(t);
261: end Projection;
262:
263: end Arrays_of_Lists_Utilities;
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>