Annotation of OpenXM_contrib/PHC/Ada/Root_Counts/Dynlift/simplices.ads, Revision 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