/[dtapublic]/projs/trunk/shared_source/c_datd/cvxzone.h
ViewVC logotype

Contents of /projs/trunk/shared_source/c_datd/cvxzone.h

Parent Directory Parent Directory | Revision Log Revision Log


Revision 56 - (show annotations) (download)
Sat Oct 29 01:53:01 2016 UTC (6 years, 3 months ago) by dashley
File MIME type: text/plain
File size: 13686 byte(s)
License and property (keyword) changes.
1 //$Header$
2 //-------------------------------------------------------------------------------------------------
3 //This file is part of "David T. Ashley's Shared Source Code", a set of shared components
4 //integrated into many of David T. Ashley's projects.
5 //-------------------------------------------------------------------------------------------------
6 //This source code and any program in which it is compiled/used is provided under the MIT License,
7 //reproduced below.
8 //-------------------------------------------------------------------------------------------------
9 //Permission is hereby granted, free of charge, to any person obtaining a copy of
10 //this software and associated documentation files(the "Software"), to deal in the
11 //Software without restriction, including without limitation the rights to use,
12 //copy, modify, merge, publish, distribute, sublicense, and / or sell copies of the
13 //Software, and to permit persons to whom the Software is furnished to do so,
14 //subject to the following conditions :
15 //
16 //The above copyright notice and this permission notice shall be included in all
17 //copies or substantial portions of the Software.
18 //
19 //THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
20 //IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
21 //FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.IN NO EVENT SHALL THE
22 //AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
23 //LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
24 //OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
25 //SOFTWARE.
26 //-------------------------------------------------------------------------------------------------
27 #ifndef CVXZONE_H_INCLUDED
28 #define CVXZONE_H_INCLUDED
29
30 #ifdef MODULE_CVXZONE
31 #define DECMOD_CVXZONE
32 #else
33 #define DECMOD_CVXZONE extern
34 #endif
35
36 #define CVXZONE_ZONE_CONST_ALLOC_INC (20)
37 /* The allocation increment for constraints which make up
38 ** a convex zone. This is the number of slots that will
39 ** be allocated at a time. A larger value here creates more
40 ** run-time efficiency but wastes more memory.
41 */
42
43 /* Types of equalities and inequalities.
44 */
45 #define CVXZONE_INEQ_LT (0) /* < */
46 #define CVXZONE_INEQ_LE (1) /* <= */
47 #define CVXZONE_INEQ_EQ (2) /* == */
48 #define CVXZONE_INEQ_GE (3) /* > */
49 #define CVXZONE_INEQ_GT (4) /* >= */
50 #define CVXZONE_INEQ_UDF (5) /* Unknown or undefined. */
51 #define CVXZONE_INEQ_MAX (6) /* Max for bounds checking. */
52
53
54 /* Defines a single constraint, i.e. x[a]-x[b] <|<= K as known
55 ** to this module. x[0] is always the value of zero. Any given
56 ** convex region or zone is a conjunction of such inequalities.
57 */
58 typedef struct
59 {
60 unsigned valid : 1;
61 /* TRUE if record is valid, i.e. used.
62 */
63 unsigned eq : 1;
64 /* TRUE if the inequality is <= rather than
65 ** <.
66 */
67 int v1;
68 int v2;
69 /* Subscripts of variables in v1 - v2 <|<= k.
70 */
71 int k;
72 /* The constant involved.
73 */
74 } CVXZONE_constraint, *CVXZONE_constraint_ptr;
75
76 /* Fundamental data structure that is a convex zone bounded
77 ** by inequalities. All of the clock variables are represented
78 ** as integers. The variable with index 0 (i.e. x[0]) is the
79 ** special value 0. Therefore, all clocks must be subscripted
80 ** starting with the value "1" and go contiguously upwards, and
81 ** this inconvenience is visible to the client, i.e. the client
82 ** must communicate with this module in these terms.
83 **
84 ** Note that there is some ambiguity in this data structure
85 ** because the order of the space which is being considered
86 ** is not specified anywhere (because there is no need to
87 ** specify it). This module will fatally terminate
88 ** the program in any context where a constraint exists for a variable
89 ** that can't exist (so far there is only one such place this can
90 ** occur). The caller needs to be consistent in the order of the
91 ** space (i.e. the caller needs to know the assumed order of the
92 ** space).
93 */
94 typedef struct
95 {
96 unsigned is_canonical : 1;
97 /* TRUE if the data structure is in canonical form. This
98 ** flag is maintained so that repeated needs to put in
99 ** canonical form will not take any CPU time. Essentially
100 ** any operation that modifies this data structure will
101 ** violate the canonical form and cause this flag to be
102 ** set to 0.
103 */
104 unsigned is_empty : 1;
105 /* By default, a space with no constraints is taken to be
106 ** full, i.e. to contain all of R-space. This flag negates
107 ** that, i.e. signals the empty set. The canonical form
108 ** of all-space is no constraints and this flag FALSE. The
109 ** canonical form of no-space is no constraints and this
110 ** flag TRUE.
111 */
112 unsigned n_allocd;
113 /* The number of slots allocated for constraints in this
114 ** data structure. This value grows, but never shrinks.
115 ** This is the number allocated, but not necessarily the
116 ** number used. This value grows in steps of
117 ** CVXZONE_ZONE_CONST_ALLOC_INC. If this value is zero,
118 ** the pointer below must be NULL.
119 */
120 unsigned n_used;
121 /* The number of slots which are used. This means that the
122 ** used slots range from 0 through this value - 1.
123 ** This only flags the constraints which must be inspected
124 ** and potentially apply, but not necessarily every constraint
125 ** in this range applies. In addition to the constraint being
126 ** subscripted in 0..n-1, the constraint must also have its
127 ** valid bit set. The set of active constraints is thus
128 ** those in the range of 0..n-1 with their valid bits set.
129 */
130 CVXZONE_constraint_ptr constraints;
131 /* Pointer to the allocated block of constraints. The number
132 ** allocated is realloc'd up by CVXZONE_ZONE_CONST_ALLOC_INC
133 ** slots each time one runs out of memory.
134 */
135 } CVXZONE_zone, *CVXZONE_zone_ptr;
136
137 /**************************************************************************/
138 /***** ALLOCATION, DEALLOCATION, AND COPY FUNCTIONS
139 /**************************************************************************/
140 /* Allocates a new zone and fills in the caller's pointer. The
141 ** pointed-to pointer must be NULL. Zones begin life as "full"--containing
142 ** all of R-space.
143 */
144 DECMOD_CVXZONE void CVXZONE_new(CVXZONE_zone_ptr *arg);
145
146 /* Deallocates a zone and fills in the caller's pointer to NULL. Previous
147 ** pointer to zone must not be NULL.
148 */
149 DECMOD_CVXZONE void CVXZONE_delete(CVXZONE_zone_ptr *arg);
150
151 /* Copies one zone to another. The destination zone, which must
152 ** already exist, is overwritten.
153 */
154 DECMOD_CVXZONE void CVXZONE_copy(CVXZONE_zone_ptr *dst, CVXZONE_zone_ptr *src);
155
156 /* Clones a zone. To clone means to create and copy in one step.
157 */
158 DECMOD_CVXZONE void CVXZONE_clone(CVXZONE_zone_ptr *clone, CVXZONE_zone_ptr *orig);
159
160 /**************************************************************************/
161 /***** MAINTENANCE FUNCTIONS
162 /**************************************************************************/
163 /* Trims extra memory from a zone (but won't convert it to canonical form).
164 ** The default behavior for a zone is that memory is never reclaimed (this is
165 ** probably the desired behavior--reclaiming memory costs time with no real
166 ** benefit). Note that trimming memory goes beyond canonical form ... it is
167 ** not part of making something canonical.
168 */
169 DECMOD_CVXZONE void CVXZONE_maintain_memory_trim(CVXZONE_zone_ptr *arg);
170
171 /* Converts a zone to canonical form. Normally this type of operation is
172 ** never necessary explicitly, because any function call that needs a zone
173 ** to be in canonical form will ensure this first. This function call
174 ** might never be used except for testing.
175 */
176 DECMOD_CVXZONE void CVXZONE_maintain_canonize(CVXZONE_zone_ptr *arg);
177
178
179 /**************************************************************************/
180 /***** ASSIGNMENT FUNCTIONS
181 /**************************************************************************/
182 /* Assigns a zone, which must already exist, to be the empty set.
183 */
184 DECMOD_CVXZONE void CVXZONE_assign_empty(CVXZONE_zone_ptr *arg);
185
186 /* Assigns a zone, which must already exist, to be the full set (all of R^N).
187 */
188 DECMOD_CVXZONE void CVXZONE_assign_full(CVXZONE_zone_ptr *arg);
189
190
191 /**************************************************************************/
192 /***** TEST FUNCTIONS
193 /**************************************************************************/
194 /* Set testing functions. In general these functions may modify even
195 ** operands that are not identified as outputs, because it may be necessary
196 ** to convert sets to canonical form before operations can be performed.
197 ** However, the sets will not be modified so as to change their logical
198 ** value.
199 */
200 /* Tests whether a zone is empty. Returns TRUE if empty.
201 */
202 DECMOD_CVXZONE int CVXZONE_test_empty(CVXZONE_zone_ptr *arg);
203
204 /* Tests whether a zone is full. Returns TRUE if full. "Full" means covers all of
205 ** N-dimensional space.
206 */
207 DECMOD_CVXZONE int CVXZONE_test_full(CVXZONE_zone_ptr *arg);
208
209 /* Tests whether one set is equal to another. Returns TRUE if equal.
210 */
211 DECMOD_CVXZONE int CVXZONE_test_proper_equal(CVXZONE_zone_ptr *set1,
212 CVXZONE_zone_ptr *set2);
213
214 /* Tests whether a point belongs to a set. The point is specified as
215 ** an integer array, with n entries, giving the successive coordinates.
216 ** Element [0] is ignored, and element [1] is the value of x_1, element
217 ** [2] is the value of x_2, etc. Specifying too many coordinates will
218 ** not be detected, as there will be simply no constraints on those
219 ** coordinates and so the extra coordinates will effectively being ignored.
220 ** Specifying too few coordinates may or may not be detected. If a
221 ** constraint is detected which cannot be applied, this will fatally
222 ** terminate the program.
223 */
224 DECMOD_CVXZONE int CVXZONE_test_point_membership(CVXZONE_zone_ptr *base_set,
225 int n_coords,
226 int *coords);
227
228 /* Tests whether one set is a proper subset of another. Returns TRUE if
229 ** it is.
230 */
231 DECMOD_CVXZONE int CVXZONE_test_proper_subset(CVXZONE_zone_ptr *base_set,
232 CVXZONE_zone_ptr *potential_subset);
233
234 /* Tests whether one set is an improper subset of another. Returns TRUE if
235 ** it is. An improper subset is just like a subset, but equality is allowed.
236 */
237 DECMOD_CVXZONE int CVXZONE_test_improper_subset(CVXZONE_zone_ptr *base_set,
238 CVXZONE_zone_ptr *potential_subset);
239
240 /**************************************************************************/
241 /***** MODIFICATION FUNCTIONS
242 /**************************************************************************/
243 /* Adds a constraint to a set. The constraint is of the form
244 ** arg1 - arg2 <|<= k. A variable with index 0 is a special case,
245 ** and this is treated as zero (i.e. it is a fictional variable).
246 ** The "eq" flag makes the difference between "<" and "<=". If "eq" is
247 ** TRUE, then "<=" is assumed.
248 **
249 ** The set is the intersection of all the half-[hyper]regions formed by the
250 ** constraints. Note that forming a set by repeatedly adding constraints
251 ** only works if set used to start is the "full" set. Adding any constraints
252 ** to an empty set will only result in an empty set that will be cleaned up the
253 ** next time it is canonized.
254 */
255 DECMOD_CVXZONE void CVXZONE_modify_add_constraint(CVXZONE_zone_ptr *base_set,
256 int arg1_idx,
257 int arg2_idx,
258 int eq,
259 int k);
260
261
262 /**************************************************************************/
263 /***** CALCULATION FUNCTIONS
264 /**************************************************************************/
265 /* Calculates the intersection of two sets and assigns it to a third set, which
266 ** must exist. (BTW, note that union cannot be calculated in this framework,
267 ** because it might result in a set which is not convex. That is why no unioning
268 ** function is provided here.)
269 */
270 DECMOD_CVXZONE void CVXZONE_calculate_intersection(CVXZONE_zone_ptr *dst,
271 CVXZONE_zone_ptr *src1,
272 CVXZONE_zone_ptr *src2);
273
274 #endif
275
276 //End of ccvxzone.h.

Properties

Name Value
svn:keywords Header

dashley@gmail.com
ViewVC Help
Powered by ViewVC 1.1.25