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