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

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

Parent Directory Parent Directory | Revision Log Revision Log


Revision 56 - (hide annotations) (download)
Sat Oct 29 01:53:01 2016 UTC (7 years, 3 months ago) by dashley
File MIME type: text/plain
File size: 13686 byte(s)
License and property (keyword) changes.
1 dashley 56 //$Header$
2 dashley 25 //-------------------------------------------------------------------------------------------------
3 dashley 56 //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 dashley 25 //-------------------------------------------------------------------------------------------------
6 dashley 56 //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 dashley 25 //
16 dashley 56 //The above copyright notice and this permission notice shall be included in all
17     //copies or substantial portions of the Software.
18 dashley 25 //
19 dashley 56 //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 dashley 25 //-------------------------------------------------------------------------------------------------
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 dashley 56 //End of ccvxzone.h.

Properties

Name Value
svn:keywords Header

dashley@gmail.com
ViewVC Help
Powered by ViewVC 1.1.25