shared_source/c_datd/cvxzone.h

//$Header$
//-------------------------------------------------------------------------------------------------
//This file is part of "David T. Ashley's Shared Source Code", a set of shared components
//integrated into many of David T. Ashley's projects.
//-------------------------------------------------------------------------------------------------
//This source code and any program in which it is compiled/used is provided under the MIT License,
//reproduced below.
//-------------------------------------------------------------------------------------------------
//Permission is hereby granted, free of charge, to any person obtaining a copy of
//this software and associated documentation files(the "Software"), to deal in the
//Software without restriction, including without limitation the rights to use,
//copy, modify, merge, publish, distribute, sublicense, and / or sell copies of the
//Software, and to permit persons to whom the Software is furnished to do so,
//subject to the following conditions :
//
//The above copyright notice and this permission notice shall be included in all
//copies or substantial portions of the Software.
//
//THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
//IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
//FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.IN NO EVENT SHALL THE
//AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
//LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
//OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
//SOFTWARE.
//-------------------------------------------------------------------------------------------------
#ifndef CVXZONE_H_INCLUDED
   #define CVXZONE_H_INCLUDED

   #ifdef MODULE_CVXZONE
      #define DECMOD_CVXZONE
   #else
      #define DECMOD_CVXZONE extern
   #endif

   #define CVXZONE_ZONE_CONST_ALLOC_INC       (20)
      /* The allocation increment for constraints which make up
      ** a convex zone.  This is the number of slots that will
      ** be allocated at a time.  A larger value here creates more
      ** run-time efficiency but wastes more memory.
      */

   /* Types of equalities and inequalities.
   */
   #define CVXZONE_INEQ_LT                 (0)  /* <  */
   #define CVXZONE_INEQ_LE                 (1)  /* <= */
   #define CVXZONE_INEQ_EQ                 (2)  /* == */
   #define CVXZONE_INEQ_GE                 (3)  /* >  */
   #define CVXZONE_INEQ_GT                 (4)  /* >= */
   #define CVXZONE_INEQ_UDF                (5)  /* Unknown or undefined. */
   #define CVXZONE_INEQ_MAX                (6)  /* Max for bounds checking. */


   /* Defines a single constraint, i.e. x[a]-x[b] <|<= K as known
   ** to this module.  x[0] is always the value of zero.  Any given
   ** convex region or zone is a conjunction of such inequalities.
   */
   typedef struct
      {
      unsigned valid   :   1;
         /* TRUE if record is valid, i.e. used.
         */
      unsigned eq      :   1;
         /* TRUE if the inequality is <= rather than
         ** <.
         */
      int v1; 
      int v2;
         /* Subscripts of variables in v1 - v2 <|<= k.
         */
      int k;
         /* The constant involved.
         */
      } CVXZONE_constraint, *CVXZONE_constraint_ptr;

   /* Fundamental data structure that is a convex zone bounded
   ** by inequalities.  All of the clock variables are represented
   ** as integers.  The variable with index 0 (i.e. x[0]) is the
   ** special value 0.  Therefore, all clocks must be subscripted
   ** starting with the value "1" and go contiguously upwards, and
   ** this inconvenience is visible to the client, i.e. the client
   ** must communicate with this module in these terms.
   **
   ** Note that there is some ambiguity in this data structure 
   ** because the order of the space which is being considered
   ** is not specified anywhere (because there is no need to 
   ** specify it).  This module will fatally terminate
   ** the program in any context where a constraint exists for a variable
   ** that can't exist (so far there is only one such place this can
   ** occur).  The caller needs to be consistent in the order of the
   ** space (i.e. the caller needs to know the assumed order of the
   ** space).
   */
   typedef struct
      {
      unsigned is_canonical : 1;
         /* TRUE if the data structure is in canonical form.  This
         ** flag is maintained so that repeated needs to put in
         ** canonical form will not take any CPU time.  Essentially
         ** any operation that modifies this data structure will
         ** violate the canonical form and cause this flag to be
         ** set to 0.
         */
      unsigned is_empty     : 1;
         /* By default, a space with no constraints is taken to be
         ** full, i.e. to contain all of R-space.  This flag negates
         ** that, i.e. signals the empty set.  The canonical form
         ** of all-space is no constraints and this flag FALSE.  The
         ** canonical form of no-space is no constraints and this
         ** flag TRUE.
         */
      unsigned n_allocd;
         /* The number of slots allocated for constraints in this
         ** data structure.  This value grows, but never shrinks.
         ** This is the number allocated, but not necessarily the
         ** number used.  This value grows in steps of 
         ** CVXZONE_ZONE_CONST_ALLOC_INC.  If this value is zero,
         ** the pointer below must be NULL.
         */
      unsigned n_used;
         /* The number of slots which are used.  This means that the
         ** used slots range from 0 through this value - 1.
         ** This only flags the constraints which must be inspected
         ** and potentially apply, but not necessarily every constraint
         ** in this range applies.  In addition to the constraint being
         ** subscripted in 0..n-1, the constraint must also have its
         ** valid bit set.  The set of active constraints is thus
         ** those in the range of 0..n-1 with their valid bits set.
         */
      CVXZONE_constraint_ptr constraints;
         /* Pointer to the allocated block of constraints.  The number
         ** allocated is realloc'd up by CVXZONE_ZONE_CONST_ALLOC_INC
         ** slots each time one runs out of memory.
         */
      } CVXZONE_zone, *CVXZONE_zone_ptr;

   /**************************************************************************/
   /***** ALLOCATION, DEALLOCATION, AND COPY FUNCTIONS
   /**************************************************************************/
   /* Allocates a new zone and fills in the caller's pointer.  The
   ** pointed-to pointer must be NULL.  Zones begin life as "full"--containing
   ** all of R-space.
   */
   DECMOD_CVXZONE void CVXZONE_new(CVXZONE_zone_ptr *arg);

   /* Deallocates a zone and fills in the caller's pointer to NULL.  Previous
   ** pointer to zone must not be NULL.
   */
   DECMOD_CVXZONE void CVXZONE_delete(CVXZONE_zone_ptr *arg);

   /* Copies one zone to another.  The destination zone, which must
   ** already exist, is overwritten.
   */
   DECMOD_CVXZONE void CVXZONE_copy(CVXZONE_zone_ptr *dst, CVXZONE_zone_ptr *src);

   /* Clones a zone.  To clone means to create and copy in one step.
   */
   DECMOD_CVXZONE void CVXZONE_clone(CVXZONE_zone_ptr *clone, CVXZONE_zone_ptr *orig);

   /**************************************************************************/
   /***** MAINTENANCE FUNCTIONS                        
   /**************************************************************************/
   /* Trims extra memory from a zone (but won't convert it to canonical form).
   ** The default behavior for a zone is that memory is never reclaimed (this is
   ** probably the desired behavior--reclaiming memory costs time with no real
   ** benefit).  Note that trimming memory goes beyond canonical form ... it is
   ** not part of making something canonical.
   */
   DECMOD_CVXZONE void CVXZONE_maintain_memory_trim(CVXZONE_zone_ptr *arg);

   /* Converts a zone to canonical form.  Normally this type of operation is
   ** never necessary explicitly, because any function call that needs a zone 
   ** to be in canonical form will ensure this first.  This function call
   ** might never be used except for testing.
   */
   DECMOD_CVXZONE void CVXZONE_maintain_canonize(CVXZONE_zone_ptr *arg);


   /**************************************************************************/
   /***** ASSIGNMENT FUNCTIONS                         
   /**************************************************************************/
   /* Assigns a zone, which must already exist, to be the empty set.
   */
   DECMOD_CVXZONE void CVXZONE_assign_empty(CVXZONE_zone_ptr *arg);

   /* Assigns a zone, which must already exist, to be the full set (all of R^N).
   */
   DECMOD_CVXZONE void CVXZONE_assign_full(CVXZONE_zone_ptr *arg);


   /**************************************************************************/
   /***** TEST FUNCTIONS
   /**************************************************************************/
   /* Set testing functions.  In general these functions may modify even 
   ** operands that are not identified as outputs, because it may be necessary
   ** to convert sets to canonical form before operations can be performed.
   ** However, the sets will not be modified so as to change their logical
   ** value.
   */
   /* Tests whether a zone is empty.  Returns TRUE if empty.
   */
   DECMOD_CVXZONE int CVXZONE_test_empty(CVXZONE_zone_ptr *arg);

   /* Tests whether a zone is full.  Returns TRUE if full.  "Full" means covers all of
   ** N-dimensional space.
   */
   DECMOD_CVXZONE int CVXZONE_test_full(CVXZONE_zone_ptr *arg);

   /* Tests whether one set is equal to another.  Returns TRUE if equal.
   */
   DECMOD_CVXZONE int CVXZONE_test_proper_equal(CVXZONE_zone_ptr *set1,
                                                CVXZONE_zone_ptr *set2);

   /* Tests whether a point belongs to a set.  The point is specified as
   ** an integer array, with n entries, giving the successive coordinates.
   ** Element [0] is ignored, and element [1] is the value of x_1, element
   ** [2] is the value of x_2, etc.  Specifying too many coordinates will
   ** not be detected, as there will be simply no constraints on those
   ** coordinates and so the extra coordinates will effectively being ignored.
   ** Specifying too few coordinates may or may not be detected.  If a 
   ** constraint is detected which cannot be applied, this will fatally
   ** terminate the program.
   */
   DECMOD_CVXZONE int CVXZONE_test_point_membership(CVXZONE_zone_ptr *base_set,
                                                    int n_coords,
                                                    int *coords);

   /* Tests whether one set is a proper subset of another.  Returns TRUE if
   ** it is.
   */
   DECMOD_CVXZONE int CVXZONE_test_proper_subset(CVXZONE_zone_ptr *base_set,
                                                 CVXZONE_zone_ptr *potential_subset);

   /* Tests whether one set is an improper subset of another.  Returns TRUE if
   ** it is.  An improper subset is just like a subset, but equality is allowed.
   */
   DECMOD_CVXZONE int CVXZONE_test_improper_subset(CVXZONE_zone_ptr *base_set,
                                                   CVXZONE_zone_ptr *potential_subset);

   /**************************************************************************/
   /***** MODIFICATION FUNCTIONS
   /**************************************************************************/
   /* Adds a constraint to a set.  The constraint is of the form 
   ** arg1 - arg2 <|<= k.  A variable with index 0 is a special case,
   ** and this is treated as zero (i.e. it is a fictional variable).
   ** The "eq" flag makes the difference between "<" and "<=".  If "eq" is
   ** TRUE, then "<=" is assumed.
   **
   ** The set is the intersection of all the half-[hyper]regions formed by the
   ** constraints.  Note that forming a set by repeatedly adding constraints
   ** only works if set used to start is the "full" set.  Adding any constraints
   ** to an empty set will only result in an empty set that will be cleaned up the
   ** next time it is canonized.
   */
   DECMOD_CVXZONE void CVXZONE_modify_add_constraint(CVXZONE_zone_ptr *base_set,
                                                     int arg1_idx,
                                                     int arg2_idx,
                                                     int eq,
                                                     int k);


   /**************************************************************************/
   /***** CALCULATION FUNCTIONS
   /**************************************************************************/
   /* Calculates the intersection of two sets and assigns it to a third set, which
   ** must exist.  (BTW, note that union cannot be calculated in this framework,
   ** because it might result in a set which is not convex.  That is why no unioning
   ** function is provided here.)
   */
   DECMOD_CVXZONE void CVXZONE_calculate_intersection(CVXZONE_zone_ptr *dst,
                                                      CVXZONE_zone_ptr *src1,
                                                      CVXZONE_zone_ptr *src2);

#endif

//End of ccvxzone.h.
1	dashley	71	//$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.