/[ascend]/trunk/base/generic/compiler/logrel_util.c
ViewVC logotype

Contents of /trunk/base/generic/compiler/logrel_util.c

Parent Directory Parent Directory | Revision Log Revision Log


Revision 122 - (show annotations) (download) (as text)
Mon Dec 19 06:12:40 2005 UTC (13 years, 11 months ago) by johnpye
File MIME type: text/x-csrc
File size: 37520 byte(s)
Refactoring all MAX, MIN, ABS calls to general/mathmacros.
Adding a GCC optimisation for these macros.
1 /*
2 * Logical Relation utility functions for Ascend
3 * by Vicente Rico-Ramirez
4 * Version: $Revision: 1.16 $
5 * Version control file: $RCSfile: logrel_util.c,v $
6 * Date last modified: $Date: 1998/04/10 23:28:35 $
7 * Last modified by: $Author: ballan $
8 *
9 * This file is part of the Ascend Interpreter.
10 *
11 * The Ascend Interpreter is free software; you can redistribute
12 * it and/or modify it under the terms of the GNU General Public License as
13 * published by the Free Software Foundation; either version 2 of the
14 * License, or (at your option) any later version.
15 *
16 * ASCEND is distributed in hope that it will be
17 * useful, but WITHOUT ANY WARRANTY; without even the implied warranty of
18 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
19 * General Public License for more details.
20 *
21 * You should have received a copy of the GNU General Public License
22 * along with the program; if not, write to the Free Software Foundation,
23 * Inc., 675 Mass Ave, Cambridge, MA 02139 USA. Check the file named
24 * COPYING.
25 *
26 */
27 #include <math.h>
28 #include <stdarg.h>
29 #include "utilities/ascConfig.h"
30 #include "utilities/ascPanic.h"
31 #include "utilities/ascMalloc.h"
32 #include "general/list.h"
33 #include "general/dstring.h"
34 #include "compiler/compiler.h"
35 #include "compiler/symtab.h"
36 #include "compiler/instance_enum.h"
37 #include "compiler/fractions.h"
38 #include "compiler/dimen.h"
39 #include "compiler/functype.h"
40 #include "compiler/types.h"
41 #include "compiler/instance_name.h"
42 #include "compiler/find.h"
43 #include "compiler/atomvalue.h"
44 #include "compiler/instance_io.h"
45 #include "compiler/logical_relation.h"
46 #include "compiler/logrelation.h"
47 #include "compiler/logrel_util.h"
48 #include "compiler/extfunc.h"
49 #include "compiler/relation_type.h"
50 #include "compiler/relation.h"
51 #include "compiler/relation_util.h"
52 #include "compiler/instance_io.h"
53 #include "compiler/instquery.h"
54 #include "compiler/visitinst.h"
55 #include "compiler/mathinst.h"
56 #include "general/mathmacros.h"
57
58 #define DEFTOLERANCE 1e-08
59
60 /*********************************************************************\
61 logical relation term queries section.
62 \*********************************************************************/
63
64 enum Expr_enum LogRelRelop(CONST struct logrelation *lrel)
65 {
66 AssertAllocatedMemory(lrel,sizeof(struct logrelation));
67 return lrel->relop;
68 }
69
70
71 unsigned long LogRelLength(CONST struct logrelation *lrel, int lhs)
72 {
73 assert(lrel!=NULL);
74 AssertAllocatedMemory(lrel,sizeof(struct logrelation));
75 if (lhs){
76 if (lrel->token.lhs) return (lrel->token.lhs_len);
77 else return 0;
78 }
79 if (lrel->token.rhs) return (lrel->token.rhs_len);
80 else return 0;
81 }
82
83 /*
84 * This query assumes the
85 * user still thinks tokens number from [1..len].
86 */
87 CONST struct logrel_term *LogRelTerm(CONST struct logrelation *lrel,
88 unsigned long int pos, int lhs)
89 {
90 assert(lrel!=NULL);
91 AssertAllocatedMemory(lrel,sizeof(struct logrelation));
92 if (lhs){
93 if (lrel->token.lhs)
94 return LOGA_TERM(&(lrel->token.lhs[pos-1]));
95 else return NULL;
96 }
97 else{
98 if (lrel->token.rhs)
99 return LOGA_TERM(&(lrel->token.rhs[pos-1]));
100 else return NULL;
101 }
102 }
103
104
105 CONST struct logrel_term
106 *NewLogRelTermF(CONST struct logrelation *lrel, unsigned long pos, int lhs)
107 {
108 assert(lrel!=NULL);
109 AssertAllocatedMemory(lrel,sizeof(struct logrelation));
110 if (lhs){
111 if (lrel->token.lhs != NULL)
112 return LOGA_TERM(&(lrel->token.lhs[pos]));
113 else return NULL;
114 } else {
115 if (lrel->token.rhs != NULL)
116 return LOGA_TERM(&(lrel->token.rhs[pos]));
117 else return NULL;
118 }
119 }
120
121
122 CONST struct logrel_term
123 *LogRelSideTermF(CONST union LogRelTermUnion *side, unsigned long pos)
124 {
125 assert(side!=NULL);
126 return LOGA_TERM(&(side[pos]));
127 }
128
129
130 enum Expr_enum LogRelTermTypeF(CONST struct logrel_term *term)
131 {
132 AssertMemory(term);
133 return term->t;
134 }
135
136 unsigned long LogTermBoolVarNumber(CONST struct logrel_term *term)
137 {
138 assert(term&&term->t == e_var);
139 AssertMemory(term);
140 return LOGBV_TERM(term)->varnum;
141 }
142
143 int LogTermBoolean(CONST struct logrel_term *term)
144 {
145 assert(term&&(term->t==e_boolean));
146 AssertMemory(term);
147 return LOGBC_TERM(term)->bvalue;
148 }
149
150 int LogTermInteger(CONST struct logrel_term *term)
151 {
152 assert(term&&(term->t==e_int));
153 AssertMemory(term);
154 return (LOGI_TERM(term)->ivalue);
155 }
156
157 int LogTermIntegerBoolValue(CONST struct logrel_term *term)
158 {
159 assert(term&&(term->t==e_int));
160 AssertMemory(term);
161 if (LOGI_TERM(term)->ivalue){
162 return 1;
163 }
164 else {
165 return 0;
166 }
167 }
168
169 int
170 LogTermBoolVar(CONST struct logrelation *lrel, CONST struct logrel_term *term)
171 {
172 return
173 GetBooleanAtomValue((struct Instance *)
174 LogRelBoolVar(lrel,LogTermBoolVarNumber(term)));
175 }
176
177 int
178 LogTermSatisfied(CONST struct logrelation *lrel,
179 CONST struct logrel_term *term,
180 int perturb,
181 struct gl_list_t *instances)
182 {
183 struct Instance *inst;
184 struct Instance *relname;
185 CONST struct relation *rel;
186 enum Expr_enum relop;
187 enum safe_err status = safe_ok;
188 double res;
189 double tol;
190 unsigned long len,n;
191 int satisfied,not_satisfied;
192 int logres;
193
194 inst = LogRelRelation(lrel,LogTermSatRelNumber(term));
195 tol = LogTermSatTolerance(term);
196
197 satisfied = 1;
198 not_satisfied = 0;
199
200 if (perturb && (instances!=NULL)) {
201 len = gl_length(instances);
202 for (n=1;n<=len;n++) {
203 relname = (struct Instance *)(gl_fetch(instances,n));
204 if (inst == relname) {
205 satisfied = 0;
206 not_satisfied = 1;
207 break;
208 }
209 }
210 }
211 switch (InstanceKind(inst)) {
212 case REL_INST:
213 status = RelationCalcResidualPostfixSafe(inst,&res);
214 if (status != safe_ok) {
215 FPRINTF(ASCERR,
216 "Something wrong while calculating a residual in Sat Expr\n");
217 return 0;
218 }
219 rel = GetInstanceRelationOnly(inst);
220 relop = RelationRelop(rel);
221 switch(relop) {
222 case e_equal:
223 if (tol != DBL_MAX) {
224 if(fabs(tol)>fabs(res)) {
225 return satisfied;
226 }
227 else {
228 return not_satisfied;
229 }
230 }
231 else {
232 if((DEFTOLERANCE)>fabs(res)) {
233 return satisfied;
234 }
235 else {
236 return not_satisfied;
237 }
238 }
239 case e_notequal:
240 if (tol != DBL_MAX) {
241 if(fabs(tol)>fabs(res)) {
242 return not_satisfied;
243 }
244 else {
245 return satisfied;
246 }
247 }
248 else {
249 if((DEFTOLERANCE)>fabs(res)) {
250 return not_satisfied;
251 }
252 else {
253 return satisfied;
254 }
255 }
256 case e_greater:
257 if (tol != DBL_MAX) {
258 if(fabs(tol)<res) {
259 return satisfied;
260 }
261 else {
262 return not_satisfied;
263 }
264 }
265 else {
266 if((DEFTOLERANCE)<res) {
267 return satisfied;
268 }
269 else {
270 return not_satisfied;
271 }
272 }
273 case e_greatereq:
274 if (tol != DBL_MAX) {
275 if(-fabs(tol)<res) {
276 return satisfied;
277 }
278 else {
279 return not_satisfied;
280 }
281 }
282 else {
283 if(-(DEFTOLERANCE)<res) {
284 return satisfied;
285 }
286 else {
287 return not_satisfied;
288 }
289 }
290 case e_less:
291 if (tol != DBL_MAX) {
292 if(-fabs(tol)>res) {
293 return satisfied;
294 }
295 else {
296 return not_satisfied;
297 }
298 }
299 else {
300 if(-(DEFTOLERANCE)>res) {
301 return satisfied;
302 }
303 else {
304 return not_satisfied;
305 }
306 }
307 case e_lesseq:
308 if (tol != DBL_MAX) {
309 if(fabs(tol)>res) {
310 return satisfied;
311 }
312 else {
313 return not_satisfied;
314 }
315 }
316 else {
317 if((DEFTOLERANCE)>res) {
318 return satisfied;
319 }
320 else {
321 return not_satisfied;
322 }
323 }
324 default:
325 FPRINTF(ASCERR,
326 "Something wrong while calculating a residual in Sat Expr\n");
327 return 0;
328 }
329 case LREL_INST:
330 if (LogRelCalcResidualPostfix(inst,&logres,perturb,instances)) {
331 FPRINTF(ASCERR,
332 "Something wrong while calculating a logical residual in Sat Expr\n");
333 return 0;
334 }
335 if(satisfied) {
336 return logres;
337 } else {
338 return (!logres);
339 }
340 default:
341 FPRINTF(ASCERR,
342 "Incorrect instance name (No Log/Relation) in Satisfied Expr\n");
343 return 0;
344 }
345 }
346
347
348 CONST struct Name *LogTermSatName(CONST struct logrel_term *term)
349 {
350 assert( term && (term->t==e_satisfied) );
351 AssertMemory(term);
352 return LOGS_TERM(term)->ncond;
353 }
354
355
356 unsigned long LogTermSatRelNumber(CONST struct logrel_term *term)
357 {
358 assert(term&&term->t == e_satisfied);
359 AssertMemory(term);
360 return LOGS_TERM(term)->relnum;
361 }
362
363
364 double LogTermSatTolerance(CONST struct logrel_term *term)
365 {
366 assert( term && (term->t==e_satisfied) );
367 AssertMemory(term);
368 return LOGS_TERM(term)->rtol;
369 }
370
371 CONST dim_type *LogTermSatDimensions(CONST struct logrel_term *term)
372 {
373 assert( term && (term->t==e_satisfied) );
374 AssertMemory(term);
375 return LOGS_TERM(term)->dim;
376 }
377
378
379 struct logrel_term *LogRelINF_Lhs(CONST struct logrelation *lrel)
380 {
381 return lrel->token.lhs_term;
382 }
383
384 struct logrel_term *LogRelINF_Rhs(CONST struct logrelation *lrel)
385 {
386 return lrel->token.rhs_term;
387 }
388
389
390
391 CONST struct gl_list_t *LogRelBoolVarList(CONST struct logrelation *lrel)
392 {
393 return (CONST struct gl_list_t *)lrel->bvars;
394 }
395
396
397 CONST struct gl_list_t *LogRelSatRelList(CONST struct logrelation *lrel)
398 {
399 return (CONST struct gl_list_t *)lrel->satrels;
400 }
401
402
403 int LogRelResidual(CONST struct logrelation *lrel)
404 {
405 assert(lrel!=NULL);
406 return lrel->logresidual;
407 }
408
409 void SetLogRelResidual(struct logrelation *lrel, int value)
410 {
411 assert(lrel!=NULL);
412 lrel->logresidual = value;
413 }
414
415 int LogRelNominal(CONST struct logrelation *lrel)
416 {
417 assert(lrel!=NULL);
418 return lrel->lognominal;
419 }
420
421 void SetLogRelNominal(struct logrelation *lrel, int value)
422 {
423 assert(lrel!=NULL);
424 lrel->lognominal = value;
425 }
426
427
428 int LogRelIsCond(CONST struct logrelation *lrel)
429 {
430 assert(lrel!=NULL);
431 return lrel->logiscond;
432 }
433
434 void SetLogRelIsCond(struct logrelation *lrel)
435 {
436 assert(lrel!=NULL);
437 lrel->logiscond = 1;
438 }
439
440
441 unsigned long NumberBoolVars(CONST struct logrelation *lrel)
442 {
443 unsigned long n;
444 assert(lrel!=NULL);
445 n = (lrel->bvars!=NULL) ? gl_length(lrel->bvars) : 0;
446 return n;
447 }
448
449 struct Instance *LogRelBoolVar(CONST struct logrelation *lrel,
450 unsigned long int varnum)
451 {
452 assert(lrel!=NULL);
453 return (struct Instance *)gl_fetch(lrel->bvars,varnum);
454 }
455
456 unsigned long NumberRelations(CONST struct logrelation *lrel)
457 {
458 unsigned long n;
459 assert(lrel!=NULL);
460 n = (lrel->satrels!=NULL) ? gl_length(lrel->satrels) : 0;
461 return n;
462 }
463
464 struct Instance *LogRelRelation(CONST struct logrelation *lrel,
465 unsigned long int relnum)
466 {
467 assert(lrel!=NULL);
468 return (struct Instance *)gl_fetch(lrel->satrels,relnum);
469 }
470
471
472 static void LogCalcDepth(CONST struct logrelation *lrel,
473 int lhs,
474 unsigned long int *depth,
475 unsigned long int *maxdepth)
476 {
477 unsigned long c,length;
478 CONST struct logrel_term *term;
479 length = LogRelLength(lrel,lhs);
480 for(c=0;c<length;c++){
481 term = NewLogRelTerm(lrel,c,lhs);
482 switch(LogRelTermType(term)){
483 case e_boolean:
484 case e_var:
485 if (++(*depth) > *maxdepth) *maxdepth = *depth;
486 break;
487 case e_satisfied:
488 case e_not:
489 break;
490 case e_and:
491 case e_or:
492 (*depth)--;
493 break;
494 default:
495 Asc_Panic(2, NULL,
496 "Don't know this type of logical relation type.\n"
497 "in function LogCalcDepth\n");
498 break;
499 }
500 }
501 }
502
503 unsigned long LogRelDepth(CONST struct logrelation *lrel)
504 {
505 unsigned long depth=0,maxdepth=0;
506 switch(LogRelRelop(lrel)){
507 case e_boolean_eq:
508 case e_boolean_neq:
509 LogCalcDepth(lrel,1,&depth,&maxdepth);
510 LogCalcDepth(lrel,0,&depth,&maxdepth);
511 assert(depth == 2);
512 break;
513 default:
514 Asc_Panic(2, NULL, "Unknown logical relation type.\n");
515 break;
516 }
517 return maxdepth;
518 }
519
520
521 /*********************************************************************\
522 calculation functions
523 \*********************************************************************/
524
525 /* global logical relation pointer to avoid passing a logical relation
526 * recursively
527 */
528 static struct logrelation *glob_lrel;
529
530 /* The next three functions are used for finding the value defined for
531 the tolerance in a SATISFIED term. The relation instance in the
532 satisfied term must be that given by the argument condinst provided
533 by the caller */
534
535 static int FindTolInSatisfiedTerm(struct logrelation *lrel,
536 struct logrel_term *term,
537 struct Instance *condinst,
538 double *tolerance)
539 {
540 struct Instance *inst;
541 double tol;
542
543 inst = LogRelRelation(lrel,LogTermSatRelNumber(term));
544 tol = LogTermSatTolerance(term);
545
546 if (inst == condinst) {
547 *tolerance = tol;
548 return 1;
549 } else {
550 return 0;
551 }
552 }
553
554
555 /* Note that ANY function calling FinTolInLogRelBranch should set
556 * glob_lrel to point at the logical relation being evaluated.
557 * The calling function should also set glob_lrel = NULL when it
558 * is done.
559 */
560
561 static int FindTolInLogRelBranch(struct logrel_term *term,
562 struct Instance *condinst,
563 double *tolerance)
564 {
565 assert(term != NULL);
566 switch(LogRelTermType(term)) {
567 case e_var:
568 case e_int:
569 case e_boolean:
570 return 0;
571 case e_satisfied:
572 if (FindTolInSatisfiedTerm(glob_lrel,term,condinst,tolerance)){
573 return 1;
574 } else {
575 return 0;
576 }
577 case e_and:
578 case e_or:
579 if (FindTolInLogRelBranch(LogTermBinLeft(term),condinst,tolerance)){
580 return 1;
581 } else {
582 if (FindTolInLogRelBranch(LogTermBinRight(term),condinst,tolerance)) {
583 return 1;
584 } else {
585 return 0;
586 }
587 }
588 case e_not:
589 if (FindTolInLogRelBranch(LogTermBinLeft(term),condinst,tolerance)){
590 return 1;
591 } else {
592 return 0;
593 }
594 default:
595 FPRINTF(ASCERR, "error in FindTolInLogRelBranch routine\n");
596 FPRINTF(ASCERR, "logical relation term type not recognized\n");
597 return 0;
598 }
599 }
600
601
602 /* For finding the value defined for the tolerance in a SATISFIED term.
603 * The relation instance in the satisfied term must be that given by
604 * the argument condinst
605 */
606
607 int FindTolInSatTermOfLogRel(struct Instance *lrelinst,
608 struct Instance *condinst, double *tolerance)
609 {
610 int found;
611 glob_lrel = NULL;
612
613 if( lrelinst == NULL ) {
614 FPRINTF(ASCERR, "error in FindTolInSatTermOfLogRel: null instance\n");
615 return 1;
616 }
617
618 if( InstanceKind(lrelinst) != LREL_INST ) {
619 FPRINTF(ASCERR, "error in FindTolInSatTermOfLogRel: not logrelation\n");
620 return 1;
621 }
622
623 glob_lrel = (struct logrelation *)GetInstanceLogRel(lrelinst);
624
625 if( glob_lrel == NULL ) {
626 FPRINTF(ASCERR, "error in FindTolInSatTermOfLogRel: null logrelation\n");
627 return 1;
628 }
629
630 if(Infix_Log_LhsSide(glob_lrel) != NULL) {
631 found = FindTolInLogRelBranch(Infix_Log_LhsSide(glob_lrel),condinst,
632 tolerance);
633 if (found) {
634 glob_lrel = NULL;
635 return 0;
636 }
637 } else {
638 glob_lrel = NULL;
639 return 1;
640 }
641
642 if(Infix_Log_RhsSide(glob_lrel) != NULL) {
643 found= FindTolInLogRelBranch(Infix_Log_RhsSide(glob_lrel),condinst,
644 tolerance);
645 if (found) {
646 glob_lrel = NULL;
647 return 0;
648 } else {
649 glob_lrel = NULL;
650 return 1;
651 }
652 } else {
653 glob_lrel = NULL;
654 return 1;
655 }
656 }
657
658
659 /* Note that ANY function calling LogRelBranchEvaluator should set
660 * glob_lrel to point at the logical relation being evaluated.
661 * The calling function should also set glob_lrel = NULL when it
662 * is done.
663 */
664
665 static int LogRelBranchEvaluator(struct logrel_term *term, int perturb,
666 struct gl_list_t *instances)
667 {
668 assert(term != NULL);
669 switch(LogRelTermType(term)) {
670 case e_var:
671 return LogTermBoolVar(glob_lrel,term);
672 case e_int:
673 return LogTermIntegerBoolValue(term);
674 case e_boolean:
675 return LogTermBoolean(term);
676 case e_satisfied:
677 return LogTermSatisfied(glob_lrel,term,perturb,instances);
678 case e_and:
679 return (LogRelBranchEvaluator(LogTermBinLeft(term),perturb,instances) &&
680 LogRelBranchEvaluator(LogTermBinRight(term),perturb,instances));
681 case e_or:
682 return (LogRelBranchEvaluator(LogTermBinLeft(term),perturb,instances) ||
683 LogRelBranchEvaluator(LogTermBinRight(term),perturb,instances));
684 case e_not:
685 return (!LogRelBranchEvaluator(LogTermBinLeft(term),perturb,instances));
686 /* return (LogRelBranchEvaluator(LogTermBinLeft(term),perturb,instances)
687 ? 0 : 1); */
688 default:
689 FPRINTF(ASCERR, "error in LogRelBranchEvaluator routine\n");
690 FPRINTF(ASCERR, "logical relation term type not recognized\n");
691 return 0;
692 }
693 }
694
695 /* LogRelEvaluatePostfixBranch
696 * This function is passed a logical relation pointer, lrel, a pointer,
697 * pos, to a position in the postfix version of the logical relation
698 * (0<=pos<length), and a flag, lhs, telling whether we are interested
699 * in the left(=1) or right(=0) side of the logical relation.
700 * This function will tranverse and evaluate the subtree rooted at pos
701 * and will return the value as an integer (0,1).
702 * To do its evaluation, this function goes backwards through
703 * the postfix representation of logical relation and calls itself at each
704 * node--creating a stack of function calls.
705 * NOTE: This function changes the value of pos--- to the position of
706 * the deepest leaf visited
707 */
708 static int
709 LogRelEvaluatePostfixBranch(CONST struct logrelation *lrel,
710 unsigned long *pos,
711 int lhs, int perturb,
712 struct gl_list_t *instances)
713 {
714 CONST struct logrel_term *term; /* the current term */
715 int b; /* temporary value */
716
717 term = NewLogRelTerm(lrel,*pos,lhs);
718 assert(term != NULL);
719 switch( LogRelTermType(term) ) {
720 case e_int:
721 return LogTermIntegerBoolValue(term);
722 case e_var:
723 return LogTermBoolVar(lrel, term);
724 case e_boolean:
725 return LogTermBoolean(term);
726 case e_satisfied:
727 return LogTermSatisfied(lrel,term,perturb,instances);
728 case e_and:
729 (*pos)--;
730 b = LogRelEvaluatePostfixBranch(lrel,pos,lhs,perturb,instances);
731 /* b==right-side of 'AND' */
732 (*pos)--;
733 return (LogRelEvaluatePostfixBranch(lrel,pos,lhs,perturb,instances) && b);
734 case e_or:
735 (*pos)--;
736 b = LogRelEvaluatePostfixBranch(lrel,pos,lhs,perturb,instances);
737 /* b==right-side of 'OR' */
738 (*pos)--;
739 return (LogRelEvaluatePostfixBranch(lrel,pos,lhs,perturb,instances) || b);
740 case e_not:
741 (*pos)--;
742 return (!LogRelEvaluatePostfixBranch(lrel,pos,lhs,perturb,instances));
743 /* return (LogRelEvaluatePostfixBranch(lrel,pos,lhs,perturb,instances))
744 ? 0 : 1); */
745 default:
746 Asc_Panic(2, NULL,
747 "Don't know this type of logical relation term\n"
748 "in function LogRelEvaluatePostfixBranch\n");
749 exit(2);/* Needed to keep gcc from whining */
750 }
751 }
752
753
754 /* LogRelEvaluateResidualPostfix
755 * Yet another function for calculating the residual of a logical relation.
756 * This function also uses the postfix version of the logical relations,
757 * but it manages a stack(array) of ints and calculates the residual in this
758 * stack; therefore the function is not recursive. If the funtion
759 * cannot allocate memory for its stack, it returns 0, so there is
760 * currently no way of knowing if this function failed.
761 */
762 static int
763 LogRelEvaluateResidualPostfix(CONST struct logrelation *lrel, int perturb,
764 struct gl_list_t *instances)
765 {
766 unsigned long t; /* the current term in the logical relation lrel */
767 int lhs; /* looking at left(=1) or right(=0) hand side */
768 int *res_stack; /* the stack we use for evaluating the residual */
769 long s = -1; /* the top position in the stacks */
770 unsigned long length_lhs, length_rhs;
771 CONST struct logrel_term *term;
772 enum Expr_enum lrelop;
773
774 length_lhs = LogRelLength(lrel,1);
775 length_rhs = LogRelLength(lrel,0);
776 if( (length_lhs+length_rhs) == 0 ) return 0;
777 lrelop = LogRelRelop(lrel);
778 /* create the stacks */
779 res_stack = tmpalloc_array((1+MAX(length_lhs,length_rhs)),int);
780 if( res_stack == NULL ) return 0;
781
782 lhs = 1;
783 t = 0;
784 while (1) {
785 if( lhs && (t >= length_lhs) ) {
786 /* finished processing left hand side, switch to right if it exists */
787 if( length_rhs ) {
788 lhs = t = 0;
789 }
790 else {
791 /* do not need to check for s>=0, since we know that
792 * (length_lhs+length_rhs>0) and that (length_rhs==0), the
793 * length_lhs must be > 0, thus s>=0
794 */
795 return 0;
796 }
797 }
798 else if( (!lhs) && (t >= length_rhs) ) {
799 /* finished processing right hand side */
800 if( length_lhs ) {
801 /* we know length_lhs and length_rhs are both > 0, since if
802 * length_rhs == 0, we would have exited above.
803 */
804 if (lrelop == e_boolean_eq) {
805 if (res_stack[s-1] == res_stack[s]) {
806 return 1;
807 }
808 else {
809 return 0;
810 }
811 }
812 else if (lrelop == e_boolean_neq) {
813 if (res_stack[s-1] != res_stack[s]) {
814 return 1;
815 }
816 else {
817 return 0;
818 }
819 } else {
820 FPRINTF(ASCERR, "error in LogRelEvaluateResidualPostfix:\n");
821 FPRINTF(ASCERR, "wrong logical relation operator \n");
822 return 0;
823 }
824 }
825 else {
826 /* do not need to check for s>=0, since we know that
827 * (length_lhs+length_rhs>0) and that (length_lhs==0), the
828 * length_rhs must be > 0, thus s>=0
829 */
830 return 0;
831 }
832 }
833
834 term = NewLogRelTerm(lrel,t++,lhs);
835 switch( LogRelTermType(term) ) {
836 case e_boolean:
837 s++;
838 res_stack[s] = LogTermBoolean(term);
839 break;
840 case e_satisfied:
841 s++;
842 res_stack[s] = LogTermSatisfied(lrel,term,perturb,instances);
843 break;
844 case e_int:
845 s++;
846 res_stack[s] = LogTermIntegerBoolValue(term);
847 break;
848 case e_var:
849 s++;
850 res_stack[s] = LogTermBoolVar(lrel,term);
851 break;
852 case e_and:
853 res_stack[s-1] = (res_stack[s-1] && res_stack[s]);
854 s--;
855 break;
856 case e_or:
857 res_stack[s-1] = ( res_stack[s-1] || res_stack[s]);
858 s--;
859 break;
860 case e_uminus:
861 res_stack[s] = ( !res_stack[s] );
862 break;
863 default:
864 Asc_Panic(2, NULL,
865 "Don't know this type of logical relation term\n"
866 "in function LogRelEvaluateResidualPostfix\n");
867 break;
868 }
869 }
870 }
871
872 /*
873 * CALCULATION ROUTINES
874 */
875
876
877 int
878 LogRelCalcResidualPostfix(struct Instance *i, int *res, int perturb,
879 struct gl_list_t *instances)
880 {
881 struct logrelation *lrel;
882 enum Expr_enum lrelop;
883 unsigned long length_lhs, length_rhs;
884
885 #ifndef NDEBUG
886 if( i == NULL ) {
887 FPRINTF(ASCERR, "error in LogRelCalcResidualPostfix: null instance\n");
888 return 1;
889 }
890 if (res == NULL){
891 FPRINTF(ASCERR,"error in LogRelCalcResidualPostfix: null ptr\n");
892 return 1;
893 }
894 if( InstanceKind(i) != LREL_INST ) {
895 FPRINTF(ASCERR, "error in LogRelCalcResidualPostfix: not logrelation\n");
896 return 1;
897 }
898 #endif
899 lrel = (struct logrelation *)GetInstanceLogRel(i);
900 if( lrel == NULL ) {
901 FPRINTF(ASCERR, "error in LogRelCalcResidualPostfix: null logrelation\n");
902 return 1;
903 }
904
905 lrelop = LogRelRelop(lrel);
906 length_lhs = LogRelLength(lrel,1);
907 length_rhs = LogRelLength(lrel,0);
908
909 if( length_lhs > 0 ) {
910 length_lhs--;
911 *res = LogRelEvaluatePostfixBranch(lrel,&length_lhs,1,perturb,instances);
912 }
913 else {
914 *res = 0;
915 }
916
917 if( lrelop == e_boolean_eq ) {
918 if( length_rhs > 0 ) {
919 length_rhs--;
920 if (*res == LogRelEvaluatePostfixBranch(lrel, &length_rhs,
921 0,perturb,instances)) {
922 *res = 1;
923 }
924 else {
925 *res = 0;
926 }
927 }
928 return 0;
929 }
930 else {
931 if(lrelop == e_boolean_neq) {
932 if( length_rhs > 0 ) {
933 length_rhs--;
934 if (*res != LogRelEvaluatePostfixBranch(lrel,&length_rhs,
935 0,perturb,instances)) {
936 *res = 1;
937 }
938 else {
939 *res = 0;
940 }
941 }
942 return 0;
943 }
944 else {
945 FPRINTF(ASCERR, "error in RelationCalcResidualPostfix:\n");
946 FPRINTF(ASCERR, "wrong logical relation operator \n");
947 return 1;
948 }
949 }
950 }
951
952 int
953 LogRelCalcResidualInfix(struct Instance *i, int *res, int perturb,
954 struct gl_list_t *instances)
955 {
956 enum Expr_enum lrelop;
957 glob_lrel = NULL;
958
959 #ifndef NDEBUG
960 if( i == NULL ) {
961 FPRINTF(ASCERR, "error in LogRelCalcResidualInfix: null instance\n");
962 return 1;
963 }
964 if (res == NULL){
965 FPRINTF(ASCERR,"error in LogRelCalcResidualInfix: null ptr\n");
966 return 1;
967 }
968 if( InstanceKind(i) != LREL_INST ) {
969 FPRINTF(ASCERR, "error in LogRelCalcResidualInfix: not logrelation\n");
970 return 1;
971 }
972 #endif
973 glob_lrel = (struct logrelation *)GetInstanceLogRel(i);
974 if( glob_lrel == NULL ) {
975 FPRINTF(ASCERR, "error in LogRelCalcResidualInfix: null logrelation\n");
976 return 1;
977 }
978 lrelop = LogRelRelop(glob_lrel);
979
980 if(Infix_Log_LhsSide(glob_lrel) != NULL) {
981 *res = LogRelBranchEvaluator(Infix_Log_LhsSide(glob_lrel),
982 perturb,instances);
983 } else {
984 *res = 0;
985 }
986
987 if( lrelop == e_boolean_eq ) {
988 if(Infix_Log_RhsSide(glob_lrel) != NULL) {
989 if (*res == LogRelBranchEvaluator(Infix_Log_RhsSide(glob_lrel),
990 perturb,instances)){
991 *res = 1;
992 }
993 else {
994 *res = 0;
995 }
996 }
997 glob_lrel = NULL;
998 return 0;
999 }
1000 else if (lrelop == e_boolean_neq) {
1001 if(Infix_Log_RhsSide(glob_lrel) != NULL) {
1002 if (*res != LogRelBranchEvaluator(Infix_Log_RhsSide(glob_lrel),
1003 perturb,instances)){
1004 *res = 1;
1005 }
1006 else {
1007 *res = 0;
1008 }
1009 }
1010 glob_lrel = NULL;
1011 return 0;
1012 } else {
1013 FPRINTF(ASCERR, "error in LogRelCalcResidualInfix:\n");
1014 FPRINTF(ASCERR, "wrong logical relation operator \n");
1015 glob_lrel = NULL;
1016 return 1;
1017 }
1018 }
1019
1020
1021 /* LogRelCalcResidualPostfix2
1022 * Yes, yet another function to calculate the logical residual
1023 * It is not used anywhere. It does take in account the perturb
1024 * flag of the other routine calculations.
1025 */
1026 int
1027 LogRelCalcResidualPostfix2(struct Instance *i,int *res, int perturb,
1028 struct gl_list_t *instances)
1029 {
1030 struct logrelation *lrel;
1031
1032 #ifndef NDEBUG
1033 if( i == NULL ) {
1034 FPRINTF(ASCERR, "error in LogRelCalcResidualPostfix2: null instance\n");
1035 return 1;
1036 }
1037 if( res == NULL ) {
1038 FPRINTF(ASCERR, "error in LogRelCalcResidualPostfix2: null ptr\n");
1039 return 1;
1040 }
1041 if( InstanceKind(i) != LREL_INST ) {
1042 FPRINTF(ASCERR, "error in LogRelCalcResidualPostfix2: not logrelation\n");
1043 return 1;
1044 }
1045 #endif
1046 lrel = (struct logrelation *)GetInstanceLogRel(i);
1047 if( lrel == NULL ) {
1048 FPRINTF(ASCERR, "error in LogRelCalcResidualPostfix2: null logrelation\n");
1049 return 1;
1050 }
1051
1052 *res = LogRelEvaluateResidualPostfix(lrel,perturb,instances);
1053 return 0;
1054 }
1055
1056
1057 /**
1058 *** The following functions support LogRelFindBoolValues which
1059 *** is the compiler implementation of DirectSolve for Logical
1060 *** relations.
1061 *** These functions can be catagorized as follows:
1062 *** Memory Management and Copying functions:
1063 *** LogRelCreateTmp, LogRelDestroyTmp, LogRelTmpCopySide,
1064 *** LogRelTmpTokenCopy, append_bool_soln
1065 *** Eternal Function:
1066 *** LogRelFindBoolValues
1067 **/
1068
1069 /*************************************************************************\
1070 Memory Management and Copying Functions
1071 \*************************************************************************/
1072
1073 /*
1074 * structure dynamically allocated/reallocated to store the number of
1075 * boolean solutions
1076 */
1077
1078 struct ds_boolsol_list {
1079 int length,capacity;
1080 int *bool_soln;
1081 };
1082
1083
1084 #define alloc_bool_array(nbools,type) \
1085 ((nbools) > 0 ? (type *)ascmalloc((nbools)*sizeof(type)) : NULL)
1086 #define copy_bool_value(from,too,nvalues) \
1087 asc_memcpy((from),(too),(nvalues)*sizeof(int))
1088
1089 /*
1090 * Appends a case_number onto the list
1091 */
1092 static void append_bool_soln( struct ds_boolsol_list *cl, int bool_soln)
1093 {
1094 if( cl->length == cl->capacity ) {
1095 int newcap;
1096 int *newlist;
1097 newcap = cl->capacity + 10;
1098 newlist = alloc_bool_array(newcap,int);
1099 copy_bool_value((char *)cl->bool_soln,(char *)newlist,cl->length);
1100 if( cl->bool_soln != NULL )
1101 ascfree(cl->bool_soln);
1102 cl->bool_soln = newlist;
1103 cl->capacity = newcap;
1104 }
1105 cl->bool_soln[cl->length++] = bool_soln;
1106 }
1107
1108
1109 /**
1110 *** LogRelCreateTmp creates a struct logrelation
1111 *** and passes back a pointer to the logrelation. The lengths of
1112 *** the right and left sides (lhslen and rhslen) of the logrelation
1113 *** are supplied by the calling function.
1114 **/
1115 static struct logrelation *LogRelCreateTmp(int lhslen, int rhslen)
1116 {
1117 struct logrelation *lrel;
1118 lrel = CreateLogRelStructure(e_bol_token);
1119 lrel->token.lhs = (union LogRelTermUnion *)
1120 ascmalloc(lhslen*sizeof(union LogRelTermUnion));
1121 lrel->token.rhs = (union LogRelTermUnion *)
1122 ascmalloc(rhslen*sizeof(union LogRelTermUnion));
1123 return lrel;
1124 }
1125
1126 /**
1127 *** LogRelDestroyTmp deallocates a struct logrelation.
1128 *** The calling function should provide a pointer
1129 *** to the logrelation to be destroyed.
1130 **/
1131 static void LogRelDestroyTmp(struct logrelation *lrel)
1132 {
1133 if (!lrel) return;
1134 if (lrel->token.lhs!=NULL) ascfree(lrel->token.lhs);
1135 if (lrel->token.rhs!=NULL) ascfree(lrel->token.rhs);
1136 ascfree((char *)lrel);
1137 }
1138
1139
1140 /*
1141 * We can now just do a memcopy and the infix pointers
1142 * all adjust by the difference between the token
1143 * arrays that the gl_lists are hiding.
1144 * Note, if any turkey ever tries to delete an individual
1145 * token from these gl_lists AND deallocate it,
1146 * they will get a severe headache.
1147 *
1148 * This is a full blown copy and not copy by reference.
1149 * You do not need to remake the infix pointers after
1150 * calling this function.
1151 */
1152 static int LogRelTmpCopySide(union LogRelTermUnion *old, unsigned long len,
1153 union LogRelTermUnion *arr)
1154 {
1155 struct logrel_term *term;
1156 unsigned long c;
1157 long int delta;
1158
1159 if (old==NULL || !len) return 1;
1160 if (arr==NULL) {
1161 FPRINTF(ASCERR,"LogRelTmpCopySide: null LogRelTermUnion :-(.\n");
1162 return 1;
1163 }
1164 memcpy( (VOIDPTR)arr, (VOIDPTR)old, len*sizeof(union LogRelTermUnion));
1165 /*
1166 * Difference in chars between old and arr ptrs. It should be a multiple
1167 * of sizeof(double) but may not be a multiple of sizeof(union RTU).
1168 * Delta may easily be negative.
1169 * Normally, though arr > old.
1170 */
1171 delta = (char *)arr - (char *)old;
1172 #ifdef ADJLOGPTR
1173 #undef ADJLOGPTR
1174 #endif
1175 #define ADJLOGPTR(p) ( (p) = LOGA_TERM((char *)(p)+delta) )
1176 for (c=0;c<len;c++) {
1177 term = LOGA_TERM(&(arr[c]));
1178 switch (term->t) {
1179 /* unary terms */
1180 case e_not:
1181 ADJLOGPTR(LOGU_TERM(term)->left);
1182 break;
1183 /* binary terms */
1184 case e_and:
1185 case e_or:
1186 ADJLOGPTR(LOGB_TERM(term)->left);
1187 ADJLOGPTR(LOGB_TERM(term)->right);
1188 break;
1189 case e_boolean:
1190 case e_var: /* the var number will be correct */
1191 case e_satisfied:
1192 break;
1193 case e_boolean_eq: case e_boolean_neq:
1194 default:
1195 Asc_Panic(2, "LogRelTmpCopySide",
1196 "Unknown term type in LogRelTmpCopySide\n");
1197 }
1198 }
1199 #undef ADJLOGPTR
1200
1201 return 0;
1202 }
1203
1204 static
1205 struct logrelation *LogRelTmpTokenCopy(CONST struct logrelation *src)
1206 {
1207 struct logrelation *result;
1208 long int delta;
1209 assert(src!=NULL);
1210
1211 result = LogRelCreateTmp(src->token.lhs_len,src->token.rhs_len);
1212
1213 if(LogRelTmpCopySide(src->token.lhs,src->token.lhs_len,
1214 result->token.lhs) == 0) {
1215 delta = LOGUNION_TERM(src->token.lhs_term) - src->token.lhs;
1216 result->token.lhs_term = LOGA_TERM(result->token.lhs+delta);
1217 result->token.lhs_len = src->token.lhs_len;
1218 } else {
1219 result->token.lhs_term = NULL;
1220 result->token.lhs_len = 0;
1221 }
1222
1223 if(LogRelTmpCopySide(src->token.rhs,src->token.rhs_len,
1224 result->token.rhs) == 0) {
1225 delta = LOGUNION_TERM(src->token.rhs_term) - src->token.rhs;
1226 result->token.rhs_term = LOGA_TERM(result->token.rhs+delta);
1227 result->token.rhs_len = src->token.rhs_len;
1228 } else {
1229 result->token.rhs_term = NULL;
1230 result->token.rhs_len = 0;
1231 }
1232
1233 result->bvars = src->bvars;
1234 result->satrels = src->satrels;
1235 result->logresidual = src->logresidual;
1236 result->lognominal = src->lognominal;
1237 return result;
1238 }
1239
1240
1241 /*************************************************************************\
1242 External Function
1243 \*************************************************************************/
1244
1245 /**
1246 *** LogRelFindBoolValues WILL find a boolean value if there is one.
1247 *** It returns 1 for success and 0 for failure. In general compiler
1248 *** functions return 0 for success but this function returns 1 for
1249 *** success because success = 1 is the convention on the solver side.
1250 *** A return of -1 indicates a problem such as var not found.
1251 *** If nsolns > 1 then a list of solutions will be returned.
1252 *** For logical equations, at most two values are expected
1253 **/
1254
1255 /* Note we should recycle the memory used for glob_lrel */
1256
1257 int *LogRelFindBoolValues(struct Instance *i, unsigned long *dvarnum,
1258 int *able,int *nsolns, int perturb,
1259 struct gl_list_t *instances)
1260 {
1261 struct logrelation *lrel;
1262 struct ds_boolsol_list soln_list;
1263 CONST struct gl_list_t *list;
1264 int res,status,bvalue;
1265
1266 soln_list.length = soln_list.capacity = 0;
1267 soln_list.bool_soln = NULL;
1268 append_bool_soln(&soln_list,0);
1269
1270 *able = FALSE;
1271 *nsolns = -1; /* nsolns will be -1 for a very unhappy rootfinder */
1272 glob_lrel = NULL;
1273
1274
1275 #ifndef NDEBUG
1276 if( i == NULL ) {
1277 FPRINTF(ASCERR, "error in LogRelFindBoolValues: null instance\n");
1278 glob_lrel = NULL; return NULL;
1279 }
1280 if (able == NULL){
1281 FPRINTF(ASCERR,"error in LogRelFindBoolValues: null int ptr\n");
1282 glob_lrel = NULL; return NULL;
1283 }
1284 if (dvarnum == NULL){
1285 FPRINTF(ASCERR,"error in LogRelFindBoolValues: null dvarnum\n");
1286 glob_lrel = NULL; return NULL;
1287 }
1288 if( InstanceKind(i) != LREL_INST ) {
1289 FPRINTF(ASCERR, "error in LogRelFindBoolValues: not logrelation\n");
1290 glob_lrel = NULL; return NULL;
1291 }
1292 #endif
1293 lrel = (struct logrelation *)GetInstanceLogRel(i);
1294 if( lrel == NULL ) {
1295 FPRINTF(ASCERR, "error in LogRelFindBoolValues: null logrelation\n");
1296 glob_lrel = NULL; return NULL;
1297 }
1298
1299 glob_lrel = LogRelTmpTokenCopy(lrel);
1300 assert(glob_lrel!=NULL);
1301 list = LogRelBoolVarList(glob_lrel);
1302
1303 if(!(*dvarnum >= 1 && *dvarnum <= gl_length(list))){
1304 FPRINTF(ASCERR, "Error in LogRelFindBoolValues: dvar not found\n");
1305 glob_lrel = NULL;
1306 return NULL;
1307 }
1308
1309 /* Current value */
1310 bvalue = GetBooleanAtomValue((struct Instance *)
1311 gl_fetch(LogRelBoolVarList(glob_lrel),*dvarnum));
1312 status = 1;
1313
1314 /* Assign the value TRUE to the boolean */
1315 SetBooleanAtomValue(
1316 (struct Instance *)gl_fetch(LogRelBoolVarList(glob_lrel),*dvarnum),TRUE,0);
1317
1318 /* Check Residual */
1319 status = LogRelCalcResidualPostfix(i,&res,perturb,instances);
1320 if (!status) {
1321 if (res) {
1322 *nsolns = 1;
1323 append_bool_soln(&soln_list,1);
1324 }
1325
1326 /* Assign the value FALSE to the boolean */
1327 SetBooleanAtomValue(
1328 (struct Instance *)gl_fetch(LogRelBoolVarList(glob_lrel),*dvarnum),FALSE,0);
1329
1330 /* Check Residual */
1331 status = LogRelCalcResidualPostfix(i,&res,perturb,instances);
1332
1333 if (!status) {
1334 if (res) {
1335 if ((*nsolns)== 1) {
1336 *nsolns = 2;
1337 } else {
1338 *nsolns = 1;
1339 }
1340 append_bool_soln(&soln_list,0);
1341 }
1342 }
1343 /* Assign original boolean value */
1344 SetBooleanAtomValue(
1345 (struct Instance *)gl_fetch(LogRelBoolVarList(glob_lrel),*dvarnum),bvalue,0);
1346
1347 }else {
1348 *able = FALSE;
1349 LogRelDestroyTmp(glob_lrel);
1350 return soln_list.bool_soln;
1351 }
1352 *able = TRUE;
1353 LogRelDestroyTmp(glob_lrel);
1354 return soln_list.bool_soln;
1355 }
1356
1357
1358 /*
1359 * Temporary Functions for testing direct solve.
1360 * Remove calls from interface.c when this is removed.
1361 */
1362 void PrintDirectBooleanResult(struct Instance *i)
1363 {
1364 struct logrelation *lrel;
1365 int num,status,n,nsoln;
1366 int *soln_list;
1367 unsigned long dvarnum;
1368 CONST struct gl_list_t *list;
1369
1370 if (InstanceKind(i) == LREL_INST) {
1371 lrel = (struct logrelation *)GetInstanceLogRel(i);
1372 list = LogRelBoolVarList(lrel);
1373 for(num = 1; num <= (int)gl_length(list);++num) {
1374 status = -1;
1375 dvarnum = num;
1376 soln_list = LogRelFindBoolValues(i,&(dvarnum),&(status),&(nsoln),0,NULL);
1377 if (nsoln > 0) {
1378 FPRINTF(stderr,"VAR NUMBER %d\n",num);
1379 for(n =1; n<=nsoln;n++) {
1380 FPRINTF(stderr,"SOLUTION = %d\n",soln_list[n]);
1381 }
1382 }
1383 }
1384 }
1385 }
1386
1387 void PrintDirectSolveBooleanSolutions(struct Instance *i)
1388 {
1389 VisitInstanceTree(i,PrintDirectBooleanResult, 0, 0);
1390 }
1391

john.pye@anu.edu.au
ViewVC Help
Powered by ViewVC 1.1.22