Annotation of OpenXM_contrib/PHC/Ada/Root_Counts/Dynlift/simplices.ads, Revision 1.1.1.1
1.1 maekawa 1: with Standard_Integer_Vectors; use Standard_Integer_Vectors;
2: with Standard_Integer_VecVecs; use Standard_Integer_VecVecs;
3:
4: package Simplices is
5:
6: -- DESCRIPTION :
7: -- The simplices are facets on the lower hull of a lifted polytope
8: -- spanned by standard integer vectors.
9:
10: -- DATA STRUCTURE :
11:
12: type Simplex is private;
13: Null_Simplex : constant Simplex; -- empty simplex
14:
15: -- CREATORS :
16:
17: function Create ( x : VecVec ) return Simplex;
18:
19: -- DESCRIPTION :
20: -- Given the vertices, the simplex will be created.
21:
22: procedure Update ( s : in out Simplex; x : in Link_to_Vector;
23: k : in natural );
24:
25: -- DESCRIPTION :
26: -- Creates a neighboring simplex by pivoting the kth point in the
27: -- simplex by the given point x.
28:
29: procedure Update ( s : in out Simplex; x : in Link_to_Vector;
30: pos : in Vector );
31:
32: -- DESCRIPTION :
33: -- Creates neighboring simplices by pivoting the points in the
34: -- simplex by the given point x.
35:
36: -- ON ENTRY :
37: -- s simplex, volume(s) > 0;
38: -- x a certain point to be considered for update;
39: -- pos the position vector of x.
40:
41: -- ON RETURN :
42: -- s updated, so that the neighbors of s contain the new
43: -- simplices.
44:
45: procedure Update_One ( s : in out Simplex; x : in Link_to_Vector;
46: pos : in Vector );
47: procedure Update_One ( s : in out Simplex; x : in Link_to_Vector;
48: pos : in Vector; news : out Simplex );
49:
50:
51: -- DESCRIPTION :
52: -- Creates at most one new simplex that contains x.
53: -- It will be assumed that there are no internal points, so no more
54: -- than one new simplex will be constructed. When x already belongs
55: -- to s or to one of its neighbor, then nothing will be done.
56: -- The specifications of s,x and pos are the same as the other
57: -- Update operation, except for the new parameter news wich returns
58: -- the new simplex that contains x.
59:
60: generic
61: with procedure Process ( news : in Simplex; cont : out boolean );
62: procedure Update_All ( s : in out Simplex; x : in Link_to_Vector;
63: pos : in Vector; ancestor : in Simplex );
64:
65: -- DESCRIPTION :
66: -- Computes all new simplices that can be derived from the initial
67: -- simplex s and the new point x.
68: -- The ancestor simplex prevents the walk from turning back.
69:
70: procedure Connect ( s1,s2 : in out Simplex );
71:
72: -- DESCRIPTION :
73: -- Computes the intersection of the two simplices.
74: -- If they are neighbors to each other, then the appropriate
75: -- connections will be made.
76:
77: procedure Flatten ( s : in out Simplex );
78:
79: -- DESCRIPTION :
80: -- All lifting values will become zero and the inner normal changes
81: -- into (0,0,..,0,1).
82:
83: -- SELECTORS :
84:
85: function Dimension ( s : Simplex ) return natural;
86:
87: -- DESCRIPTION :
88: -- Returns the number of points in the simplex.
89:
90: function Normal ( s : Simplex ) return Vector;
91:
92: -- DESCRIPTION :
93: -- Returns the normal to the given simplex.
94:
95: function Is_Flat ( s : Simplex ) return boolean;
96:
97: -- DESCRIPTION :
98: -- Returns true if all components of the normal equal zero,
99: -- except the last one, which must be equal to one.
100: -- Returns false otherwise.
101:
102: function Vertices ( s : Simplex ) return VecVec;
103:
104: -- DESCRIPTION :
105: -- Returns the vertices that span the simplex.
106:
107: function Vertex ( s : Simplex; k : natural ) return Vector;
108:
109: -- DESCRIPTION :
110: -- Returns the kth vector that spans the simplex.
111:
112: function Is_Vertex ( s : Simplex; x : Vector ) return boolean;
113:
114: -- DESCRIPTION :
115: -- Returns true if x is one of the vertices that spans the simplex.
116:
117: function Equal ( s1,s2 : Simplex ) return boolean;
118:
119: -- DESCRIPTION :
120: -- returns true if the representations of both simplices are the same.
121:
122: function Index ( s : Simplex; x : Vector ) return natural;
123:
124: -- DESCRIPTION :
125: -- k := Index(s,x);
126: -- if k = 0 then Is_Vertex(s,x) = false,
127: -- else Neighbor(s,k) is the neighboring simplex of s by pivoting x.
128:
129: function Neighbor ( s : Simplex; k : natural ) return Simplex;
130: function Neighbor ( s : Simplex; k : natural; pos : Vector ) return Simplex;
131:
132: -- DESCRIPTION :
133: -- Returns the neighbor of the kth point of the given simplex.
134: -- If the position vector is supplied, then it will only return
135: -- a non-empty simplex if that is allowed by the position.
136:
137: function Position ( s : Simplex; x : Vector ) return Vector;
138:
139: -- DESCRIPTION :
140: -- Computes the position of the given vector w.r.t. that simplex,
141: -- i.e., if l = Position(pt,s), then sum of l(i)*s(i) + l(l'last)*pt = 0,
142: -- where s(i) = ith point that spans the simplex, and the sum
143: -- of all entries in l equals 1.
144:
145: function Is_In ( s : Simplex; x : Vector ) return boolean;
146: function Is_In ( s : Simplex; x,pos : Vector ) return boolean;
147: function Is_In_All ( s : Simplex; x : Vector ) return boolean;
148: function Is_In_All ( s : Simplex; x : Vector ) return Simplex;
149: function Is_In_All ( s : Simplex; x,pos : Vector ) return boolean;
150: function Is_In_All ( s : Simplex; x,pos : Vector ) return Simplex;
151:
152: -- DESCRIPTION :
153: -- Returns true if the point x is contained in the convex hull of s.
154: -- The function runs more efficiently if the position vector is
155: -- already available, otherwise it will be computed.
156: -- With Is_In_All, also all neighbors of the given simplex are checked.
157: -- Is_In_All(s,x) returns true if x is contained in s or in one of its
158: -- neigbors, or in one of the neighbors of the neigbors...
159: -- Either the simplex which contains x or the empty simplex is returned.
160:
161: generic
162:
163: with procedure Process_Neighbor
164: ( nei : in out Simplex; k : in natural;
165: continue : out boolean );
166:
167: procedure Neighbors ( s : in out Simplex; x : in Vector );
168:
169: -- DESCRIPTION :
170: -- Computes all neighbors (and neighbors of ...) of the simplex s,
171: -- that lie closest to x, i.e. with no other simplices in between.
172: -- This procedure implements a walk from the simplex s to
173: -- a given point x.
174: -- As the parameters are of type 'in out', simplices are
175: -- allowed to be updated.
176:
177: -- To the user defined procedure Process_Neighbor the following
178: -- information is passed:
179:
180: -- ON ENTRY :
181: -- nei a neighboring simplex close to x;
182: -- k index for point in nei that can be replaced by s.
183:
184: -- ON RETURN :
185: -- nei updated simplex;
186: -- continue if true then more neighboring simplices may be delivered;
187: -- if false then the iteration will stop.
188:
189: function Volume ( s : Simplex ) return natural;
190:
191: -- DESCRIPTION :
192: -- Returns n! times the volume of the simplex.
193:
194: -- DESTRUCTORS :
195:
196: procedure Destroy_Neighbor ( s : in out Simplex; k : in natural );
197: procedure Destroy_Neighbors ( s : in out Simplex );
198:
199: -- DESCRIPTION :
200: -- Sets the kth neighbor of the simplex to the empty simplex.
201: -- If k is not specified, then all neighbors will be set to empty.
202:
203: procedure Clear_Neighbor ( s : in out Simplex; k : in natural );
204: procedure Clear_Neighbors ( s : in out Simplex );
205:
206: -- DESCRIPTION :
207: -- Clears the kth neighbor of the simplex s.
208: -- If k is not specified, then all neighbors will be cleared.
209:
210: procedure Clear ( s : in out Simplex );
211:
212: -- DESCRIPTION :
213: -- Makes the allocated memory space available.
214:
215: private
216:
217: type Simplex_Rep ( n : natural );
218: type Simplex is access Simplex_Rep;
219: Null_Simplex : constant Simplex := null;
220:
221: end Simplices;
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to simplices.ads CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [local] / OpenXM_contrib / PHC / Ada / Root_Counts / Dynlift