Annotation of OpenXM_contrib/PHC/Ada/Root_Counts/Dynlift/enumerate_faces_of_polytope.adb, Revision 1.1.1.1
1.1 maekawa 1: with Integer_Face_Enumerators; use Integer_Face_Enumerators;
2:
3: package body Enumerate_Faces_of_Polytope is
4:
5: -- UTILITIES :
6:
7: function Is_In ( i : natural; v : Vector ) return boolean is
8: begin
9: for j in v'range loop
10: if v(j) = i
11: then return true;
12: end if;
13: end loop;
14: return false;
15: end Is_In;
16:
17: -- TARGET ROUTINES :
18:
19: procedure Enumerate_Faces_in_List
20: ( l : in List; point : in Link_to_Vector; k : in natural ) is
21:
22: verpts : constant VecVec := Shallow_Create(l);
23: face : VecVec(0..k);
24:
25: procedure Enumerate_Vertices ( l,start : in natural ) is
26:
27: -- DESCRIPTION :
28: -- Already l vectors have been choosen out of verpts and
29: -- are in face(0..l). In indices(0..l) the position of the
30: -- ith face in the vector of vertices is given by indices(i).
31: -- The parameter start indices from which vertex on, the
32: -- enumeration has to start.
33: -- In this way, the faces are enumerated in lexicographic order.
34:
35: begin
36: if l >= k
37: then Process(face);
38: elsif (verpts'last-start+1) >= k-l
39: then
40: for j in start..verpts'last loop
41: face(l+1) := verpts(j);
42: Enumerate_Vertices(l+1,j+1);
43: end loop;
44: end if;
45: end Enumerate_Vertices;
46:
47: begin
48: face(0) := point;
49: Enumerate_Vertices(0,verpts'first);
50: end Enumerate_Faces_in_List;
51:
52: procedure Enumerate_Lower_Faces_in_List
53: ( l : in List; point : in Link_to_Vector; k : in natural ) is
54:
55: verpts : VecVec(1..Length_Of(l)+1);
56: face : VecVec(0..k);
57:
58: begin
59: verpts(1) := point;
60: verpts(2..verpts'last) := Shallow_Create(l);
61: face(0) := point;
62: if k = 1
63: then
64: declare
65: procedure Low_Edge ( i,j : in integer; cont : out boolean ) is
66: begin
67: if i = 1
68: then face(1) := verpts(j);
69: Process(face); cont := true;
70: else cont := false;
71: end if;
72: end Low_Edge;
73: procedure Enum_Low_Edges is new Enumerate_Lower_Edges(Low_Edge);
74: begin
75: Enum_Low_Edges(verpts);
76: end;
77: else
78: declare
79: procedure Low_Face ( f : in Vector; cont : out boolean ) is
80: begin
81: if f(f'first) = 1
82: then for i in 1..f'last loop
83: face(i) := verpts(f(i));
84: end loop;
85: Process(face); cont := true;
86: else cont := false;
87: end if;
88: end Low_Face;
89: procedure Enum_Low_Faces is new Enumerate_Lower_Faces(Low_Face);
90: begin
91: Enum_Low_Faces(k,verpts);
92: end;
93: end if;
94: end Enumerate_Lower_Faces_in_List;
95:
96: procedure Enumerate_Faces_in_Simplex
97: ( s : in Simplex; point : in Link_to_Vector; k : in natural ) is
98:
99: verpts : constant VecVec := Vertices(s);
100: face : VecVec(0..k);
101: indices : Vector(0..k);
102:
103: procedure Enumerate_Vertices ( l,start : in natural ) is
104:
105: -- DESCRIPTION :
106: -- Already l vectors have been choosen out of verpts and
107: -- are in face(0..l). In indices(0..l) the position of the
108: -- ith face in the vector of vertices is given by indices(i).
109: -- The parameter start indices from which vertex on, the
110: -- enumeration has to start.
111: -- In this way, the faces are enumerated in lexicographic order.
112:
113: begin
114: if l >= k
115: then Process(face);
116: elsif (verpts'last-start+1) >= k-l
117: then
118: for j in start..verpts'last loop
119: if not Is_In(j,indices(0..l))
120: then indices(l+1) := j;
121: face(l+1) := verpts(j);
122: Enumerate_Vertices(l+1,j+1);
123: end if;
124: end loop;
125: end if;
126: end Enumerate_Vertices;
127:
128: begin
129: -- SEARCH FOR THE INDEX OF THE POINT :
130: indices(0) := verpts'first - 1;
131: for i in verpts'range loop
132: if verpts(i).all = point.all
133: then indices(0) := i;
134: end if;
135: exit when indices(0) >= verpts'first;
136: end loop;
137: -- ENUMERATE ALL OTHER k CHOICES OF POINTS :
138: if indices(0) >= verpts'first
139: then
140: face(0) := point;
141: Enumerate_Vertices(0,verpts'first);
142: end if;
143: end Enumerate_Faces_in_Simplex;
144:
145: procedure Enumerate_Lower_Faces_in_Simplex
146: ( s : in Simplex; point : in Link_to_Vector; k : in natural ) is
147:
148: verpts : constant VecVec := Vertices(s);
149: face : VecVec(0..k);
150: indices : Vector(0..k);
151:
152: begin
153: null;
154: end Enumerate_Lower_Faces_in_Simplex;
155:
156: procedure Enumerate_Faces_in_Triangulation
157: ( t : in Triangulation;
158: point : in Link_to_Vector; k : in natural ) is
159:
160: verpts : constant VecVec := Vertices(t,point.all);
161: face : VecVec(0..k);
162: indices : Vector(0..k);
163:
164: procedure Enumerate_Vertices ( l,start : in natural ) is
165:
166: -- DESCRIPTION :
167: -- Already l vectors have been choosen out of verpts and
168: -- are in face(0..l). In indices(0..l) the position of the
169: -- ith face in the vector of vertices is given by indices(i).
170: -- The parameter start indices from which vertex on, the
171: -- enumeration has to start.
172: -- In this way, the faces are enumerated in lexicographic order.
173:
174: begin
175: if l >= k
176: then Process(face);
177: elsif (verpts'last-start+1) >= k-l
178: then
179: for j in start..verpts'last loop
180: if not Is_In(j,indices(0..l))
181: then indices(l+1) := j;
182: face(l+1) := verpts(j);
183: Enumerate_Vertices(l+1,j+1);
184: end if;
185: end loop;
186: end if;
187: end Enumerate_Vertices;
188:
189: begin
190: -- SEARCH FOR THE INDEX OF THE POINT :
191: indices(0) := verpts'first - 1;
192: for i in verpts'range loop
193: if verpts(i).all = point.all
194: then indices(0) := i;
195: end if;
196: exit when indices(0) >= verpts'first;
197: end loop;
198: -- ENUMERATE ALL OTHER k CHOICES OF POINTS :
199: if indices(0) >= verpts'first
200: then
201: face(0) := point;
202: Enumerate_Vertices(0,verpts'first);
203: end if;
204: end Enumerate_Faces_in_Triangulation;
205:
206: procedure Enumerate_Lower_Faces_in_Triangulation
207: ( t : in Triangulation;
208: point : in Link_to_Vector; k : in natural ) is
209:
210: verpts : constant VecVec := Vertices(t,point.all);
211: face : VecVec(0..k);
212: indices : Vector(0..k);
213:
214: begin
215: null;
216: end Enumerate_Lower_Faces_in_Triangulation;
217:
218: end Enumerate_Faces_of_Polytope;
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>