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.
|