Parent Directory | Revision Log

Revision **56** -
(**show annotations**)
(**download**)

*Sat Oct 29 01:53:01 2016 UTC*
(7 years, 6 months ago)
by *dashley*

File MIME type: text/plain

File size: 13686 byte(s)

File MIME type: text/plain

File size: 13686 byte(s)

License and property (keyword) changes.

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

Name | Value |
---|---|

svn:keywords |
Header |

dashley@gmail.com | ViewVC Help |

Powered by ViewVC 1.1.25 |