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