1 // term_ordering.cc
2
3 // implementation of class term ordering
4
5 #ifndef TERM_ORDERING_CC
6 #define TERM_ORDERING_CC
7
8 #include "binomial__term_ordering.h"
9
10 /////////////// constructors and destructor ///////////////////////////////////
11
term_ordering(const BOOLEAN & _homogeneous)12 term_ordering::term_ordering(const BOOLEAN& _homogeneous)
13 :homogeneous(_homogeneous)
14 {
15 weight_vector=NULL;
16 weighted_block_size=0;
17 elimination_block_size=0;
18 }
19
20
21
22
term_ordering(const short & number_of_weighted_variables,const float * weights,const short & _weighted_ordering,const BOOLEAN & _homogeneous)23 term_ordering::term_ordering(const short& number_of_weighted_variables,
24 const float* weights,
25 const short& _weighted_ordering,
26 const BOOLEAN& _homogeneous)
27 :weighted_block_size(number_of_weighted_variables),
28 homogeneous(_homogeneous)
29 {
30 if((_weighted_ordering<4) || (_weighted_ordering>7))
31 // unknown ordering refining the weight, set "error flag"
32 weighted_block_size=-1;
33 else
34 weighted_ordering=_weighted_ordering;
35
36 if(weighted_block_size<0)
37 // argument out of range, set "error flag"
38 weighted_block_size=-1;
39
40 if(weighted_block_size>0)
41 {
42 weight_vector=new float[weighted_block_size];
43
44 BOOLEAN negative_weight=FALSE;
45 BOOLEAN zero_weight=FALSE;
46 // for checking the input
47
48 for(short i=0;i<weighted_block_size;i++)
49 {
50 weight_vector[i]=weights[i];
51 // initialize weight vector with weights
52
53 if(weight_vector[i]<0)
54 negative_weight=TRUE;
55 if(weight_vector[i]==0)
56 zero_weight=TRUE;
57 }
58
59 if(negative_weight==TRUE)
60 cerr<<"\nWARNING: term_ordering::term_ordering(const short&, "
61 "const float*, const short&):\nWeight vector with negative components"
62 " does not define a well ordering"<<endl;
63
64 if((weighted_ordering==W_REV_LEX) && (zero_weight==TRUE))
65 cerr<<"\nWARNING: term_ordering::term_ordering(const short&, "
66 "const float*, const short&):\nZero weights refined by a reverse "
67 "lexicographical ordering do not define a well ordering"<<endl;
68
69 }
70 else
71 if(weighted_block_size<0)
72 cerr<<"\nWARNING:term_ordering::term_ordering(const short&, "
73 "const float*, const short&):\nBad input in term ordering "
74 "constructor"<<endl;
75
76 elimination_block_size=0;
77
78 }
79
80
81
82
term_ordering(const short & number_of_weighted_variables,const float * weights,const short & _weighted_ordering,const short & number_of_elimination_variables,const short & _elimination_ordering,const BOOLEAN & _homogeneous)83 term_ordering::term_ordering(const short& number_of_weighted_variables,
84 const float* weights,
85 const short& _weighted_ordering,
86 const short& number_of_elimination_variables,
87 const short& _elimination_ordering,
88 const BOOLEAN& _homogeneous)
89 :weighted_block_size(number_of_weighted_variables),
90 elimination_block_size(number_of_elimination_variables),
91 homogeneous(_homogeneous)
92 {
93 if((_weighted_ordering<4) || (_weighted_ordering>7))
94 // unknown ordering refining the weight, set "error flag"
95 weighted_block_size=-1;
96 else
97 weighted_ordering=_weighted_ordering;
98
99 if((_elimination_ordering<1) || (_elimination_ordering>3))
100 // unknown ordering on the elimination variables, set "error flag"
101 weighted_block_size=-1;
102 else
103 elimination_ordering=_elimination_ordering;
104
105 if((weighted_block_size<0)||(elimination_block_size<0))
106 // argument out of range, set "error flag"
107 weighted_block_size=-1;
108
109 if(weighted_block_size>0)
110 {
111 weight_vector=new float[weighted_block_size];
112
113 BOOLEAN negative_weight=FALSE;
114 BOOLEAN zero_weight=FALSE;
115 // for checking the input
116
117 for(short i=0;i<weighted_block_size;i++)
118 {
119 weight_vector[i]=weights[i];
120 // initialize weight vector with weights
121
122 if(weight_vector[i]<0)
123 negative_weight=TRUE;
124 if(weight_vector[i]==0)
125 zero_weight=TRUE;
126 }
127
128 if(negative_weight==TRUE)
129 cerr<<"\nWARNING:term_ordering::term_ordering(const short&, "
130 "const float*, const short&, const short&, const short&):\n"
131 "Weight vector with negative components does not define "
132 "a well ordering"<<endl;
133
134 if((weighted_ordering==W_REV_LEX) && (zero_weight==TRUE))
135 cerr<<"\nWARNING:term_ordering::term_ordering(const short&, "
136 "const float*, const short&, const short&, const short&):\n"
137 "Zero weights refined by a reverse lexicographical "
138 "ordering do not define a well ordering"<<endl;
139
140 }
141 else
142 if(weighted_block_size<0)
143 cerr<<"\nWARNING:term_ordering::term_ordering(const short&, "
144 "const float*, const short&, const short&, const short&):\n"
145 "Bad input in term ordering constructor"<<endl;
146 }
147
148
149
150
term_ordering(ifstream & input,const short & _weighted_ordering,const BOOLEAN & _homogeneous)151 term_ordering::term_ordering(ifstream& input, const short& _weighted_ordering,
152 const BOOLEAN& _homogeneous)
153 :homogeneous(_homogeneous)
154 {
155
156 if((_weighted_ordering<4) || (_weighted_ordering>7))
157 // unknown ordering refining the weight, set "error flag"
158 weighted_block_size=-1;
159 else
160 weighted_ordering=_weighted_ordering;
161
162
163 input>>weighted_block_size;
164 if(!input)
165 // input failure, set "error flag"
166 weighted_block_size=-2;
167 if(weighted_block_size<0)
168 // input out of range, set error flag
169 weighted_block_size=-1;
170
171 if(weighted_block_size>0)
172 {
173 weight_vector=new float[weighted_block_size];
174
175 BOOLEAN negative_weight=FALSE;
176 BOOLEAN zero_weight=FALSE;
177 // for checking the input
178
179 for(short i=0;i<weighted_block_size;i++)
180 {
181 input>>weight_vector[i];
182
183 if(!input)
184 // input failure, set "error flag"
185 {
186 weighted_block_size=-2;
187 cerr<<"\nWARNING: term_ordering::term_ordering(ifstream&, const "
188 "short&):\nInput failed reading term ordering from ofstream"<<endl;
189 break;
190 }
191
192 if(weight_vector[i]<0)
193 negative_weight=TRUE;
194 if(weight_vector[i]==0)
195 zero_weight=TRUE;
196 }
197
198 if(negative_weight==TRUE)
199 cerr<<"\nWARNING: term_ordering::term_ordering(ifstream&, const short&)"
200 ":\nWeight vector with negative components does not define "
201 "a well ordering"<<endl;
202
203 if((weighted_ordering==W_REV_LEX) && (zero_weight==TRUE))
204 cerr<<"\nWARNING: term_ordering::term_ordering(ifstream&, const short&)"
205 ":\nZero weights refined by a reverse lexicographical "
206 "ordering do not define a well ordering"<<endl;
207 }
208 else
209 if(weighted_block_size<0)
210 cerr<<"\nWARNING: term_ordering::term_ordering(ifstream&, const short&)"
211 ":\nBuilding a term ordering from a corrupt one"<<endl;
212
213 elimination_block_size=0;
214 }
215
216
217
218
term_ordering(const short & n,ifstream & input,const short & _weighted_ordering,const BOOLEAN & _homogeneous)219 term_ordering::term_ordering(const short& n, ifstream& input,
220 const short& _weighted_ordering,
221 const BOOLEAN& _homogeneous)
222 :homogeneous(_homogeneous)
223 {
224 if((_weighted_ordering<4) || (_weighted_ordering>7))
225 // unknown ordering refining the weight, set "error flag"
226 weighted_block_size=-1;
227 else
228 weighted_ordering=_weighted_ordering;
229
230 if(n<0)
231 // input out of range, set error flag
232 weighted_block_size=-1;
233 else
234 weighted_block_size=n;
235
236 if(weighted_block_size>0)
237 {
238 weight_vector=new float[weighted_block_size];
239
240 BOOLEAN negative_weight=FALSE;
241 BOOLEAN zero_weight=FALSE;
242 // for checking the input
243
244 for(short i=0;i<weighted_block_size;i++)
245 {
246 input>>weight_vector[i];
247
248 if(!input)
249 // input failure, set "error flag"
250 {
251 weighted_block_size=-2;
252 cerr<<"\nWARNING: term_ordering::term_ordering(const short&, "
253 "ifstream&, const short&):\nInput failed reading term ordering "
254 "from ofstream"<<endl;
255 break;
256 }
257
258 if(weight_vector[i]<0)
259 {
260 cout << "neg found at i="<<i<<":" <<weight_vector[i] <<"\n";
261 negative_weight=TRUE;
262 }
263 if(weight_vector[i]==0)
264 zero_weight=TRUE;
265 }
266
267 if(negative_weight==TRUE)
268 cerr<<"\nWARNING: term_ordering::term_ordering(const short&, ifstream&, "
269 "const short&):\nWeight vector with negative components does not "
270 "define a well ordering"<<endl;
271
272 if((weighted_ordering==W_REV_LEX) && (zero_weight==TRUE))
273 cerr<<"\nWARNING: term_ordering::term_ordering(const short&, ifstream&, "
274 "const short&):\nZero weights refined by a reverse lexicographical "
275 "ordering do not define a well ordering"<<endl;
276 }
277 else
278 if(weighted_block_size<0)
279 cerr<<"\nWARNING: term_ordering::term_ordering(const short&, ifstream&, "
280 "const short&):\n Building a term ordering from a corrupt one"<<endl;
281
282 elimination_block_size=0;
283 }
284
285
286
287
term_ordering(const term_ordering & w)288 term_ordering::term_ordering(const term_ordering& w)
289 :weighted_block_size(w.weighted_block_size),
290 weighted_ordering(w.weighted_ordering),
291 elimination_block_size(w.elimination_block_size),
292 elimination_ordering(w.elimination_ordering),
293 homogeneous(w.homogeneous)
294 {
295 if(weighted_block_size>0)
296 {
297 weight_vector=new float[weighted_block_size];
298 for(short i=0;i<weighted_block_size;i++)
299 weight_vector[i]=w.weight_vector[i];
300 }
301 else
302 if(weighted_block_size<0)
303 cerr<<"\nWARNING: term_ordering::term_ordering(const term_ordering&):\n"
304 "Building a term ordering from a corrupt one"<<endl;
305
306 }
307
308
309
310
~term_ordering()311 term_ordering::~term_ordering()
312 {
313 if(weighted_block_size>0)
314 delete[] weight_vector;
315 }
316
317
318
319
320 /////////////// object properties /////////////////////////////////////////
321
322
323
324
number_of_weighted_variables() const325 short term_ordering::number_of_weighted_variables() const
326 {
327 return weighted_block_size;
328 }
329
330
331
weight_refinement() const332 short term_ordering::weight_refinement() const
333 {
334 return weighted_ordering;
335 }
336
337
338
number_of_elimination_variables() const339 short term_ordering::number_of_elimination_variables() const
340 {
341 return elimination_block_size;
342 }
343
344
345
elimination_refinement() const346 short term_ordering::elimination_refinement() const
347 {
348 return elimination_ordering;
349 }
350
351
352
is_homogeneous() const353 BOOLEAN term_ordering::is_homogeneous() const
354 {
355 return homogeneous;
356 }
357
358
359
error_status() const360 short term_ordering::error_status() const
361 {
362 if(weighted_block_size<0)
363 return weighted_block_size;
364 return 0;
365 }
366
367
368
is_nonnegative() const369 BOOLEAN term_ordering::is_nonnegative() const
370 {
371 for(int i=0;i<weighted_block_size;i++)
372 if(weight_vector[i]<0)
373 return FALSE;
374 return TRUE;
375 }
376
377
378
is_positive() const379 BOOLEAN term_ordering::is_positive() const
380 {
381 for(int i=0;i<weighted_block_size;i++)
382 if(weight_vector[i]<=0)
383 return FALSE;
384 return TRUE;
385 }
386
387
388
389
390 /////////////// frequently used comparison functions //////////////////////
391
392
393
394
weight(const Integer * v) const395 double term_ordering::weight(const Integer* v) const
396 {
397 double result=0;
398 for(short i=0;i<weighted_block_size;i++)
399 result+=(weight_vector[i]*v[i]);
400 return(result);
401 }
402
403
404
405
compare_to_zero(const Integer * v) const406 short term_ordering::compare_to_zero(const Integer* v) const
407 {
408 unsigned short last_index=weighted_block_size+elimination_block_size;
409 double w=0;
410
411 // First check the elimination variables.
412
413 if(elimination_block_size>0)
414 switch(elimination_ordering)
415 {
416 case LEX:
417
418 for(short i=weighted_block_size;i<last_index;i++)
419 {
420 Integer actual_component=v[i];
421 if(actual_component>0)
422 return 1;
423 if(actual_component<0)
424 return -1;
425 }
426
427 break;
428
429 case DEG_LEX:
430
431 // compute the degree
432 for(short i=weighted_block_size;i<last_index;i++)
433 w+=v[i];
434
435 if(w>0)
436 return 1;
437 if(w<0)
438 return -1;
439
440 // if the degree is zero:
441 // tie breaking with the lexicographical ordering
442 for(short i=weighted_block_size;i<last_index;i++)
443 {
444 Integer actual_component=v[i];
445 if(actual_component>0)
446 return 1;
447 if(actual_component<0)
448 return -1;
449 }
450
451 break;
452
453 case DEG_REV_LEX:
454
455 //compute the degree
456 for(short i=weighted_block_size;i<last_index;i++)
457 w+=v[i];
458
459 if(w>0)
460 return 1;
461 if(w<0)
462 return -1;
463 // if the degree is zero:
464 // tie breaking with the reverse lexicographical ordering
465 for(short i=last_index-1;i>=weighted_block_size;i--)
466 {
467 Integer actual_component=v[i];
468 if(actual_component<0)
469 return 1;
470 if(actual_component>0)
471 return -1;
472 }
473 }
474
475
476 // When reaching this line, the vector components corresponding to
477 // elimination variables are all zero.
478 // Compute the weight.
479 // If the term ordering is a homogeneous one, this is superfluous.
480
481 if(!homogeneous)
482 {
483 w=weight(v);
484 if(w>0)
485 return 1;
486 if(w<0)
487 return -1;
488 }
489
490
491 // When reaching this line, the weight of the vector components corresponding
492 // to weighted variables is zero.
493 // Tie breaking with the term ordering refining the weight.
494
495 switch(weighted_ordering)
496 {
497 case W_LEX:
498
499 for(short i=0;i<weighted_block_size;i++)
500 {
501 Integer actual_component=v[i];
502 if(actual_component>0)
503 return 1;
504 if(actual_component<0)
505 return -1;
506 }
507
508 break;
509
510 case W_REV_LEX:
511
512 for(short i=weighted_block_size-1;i>=0;i--)
513 {
514 Integer actual_component=v[i];
515 if(actual_component<0)
516 return 1;
517 if(actual_component>0)
518 return -1;
519 }
520
521 break;
522
523 case W_DEG_LEX:
524
525 for(short i=0;i<weighted_block_size;i++)
526 w+=v[i];
527
528 if(w>0)
529 return 1;
530 if(w<0)
531 return -1;
532
533 for(short i=0;i<weighted_block_size;i++)
534 {
535 Integer actual_component=v[i];
536 if(actual_component>0)
537 return 1;
538 if(actual_component<0)
539 return -1;
540 }
541
542 break;
543
544 case W_DEG_REV_LEX:
545
546 for(short i=0;i<weighted_block_size;i++)
547 w+=v[i];
548
549 if(w>0)
550 return 1;
551 if(w<0)
552 return -1;
553
554 for(short i=weighted_block_size-1;i>=0;i--)
555 {
556 Integer actual_component=v[i];
557 if(actual_component<0)
558 return 1;
559 if(actual_component>0)
560 return -1;
561 }
562
563 }
564
565 // When reaching this line, the argument vector is the zero vector.
566
567 return 0;
568
569 }
570
571
572
573
compare(const binomial & bin1,const binomial & bin2) const574 short term_ordering::compare(const binomial& bin1, const binomial& bin2) const
575 {
576 unsigned short last_index=weighted_block_size+elimination_block_size;
577 double w1=0;
578 double w2=0;
579
580 Integer* v1=bin1.exponent_vector;
581 Integer* v2=bin2.exponent_vector;
582
583 // First compare the heads of the input binomials.
584 // The code is analogous to the routine compare_to_zero(...), except
585 // from the fact that we must consider the sign of the vector components.
586
587 // First check the elimination variables.
588
589 if(elimination_block_size>0)
590 switch(elimination_ordering)
591 {
592 case LEX:
593
594 for(short i=weighted_block_size;i<last_index;i++)
595 {
596 Integer comp1=v1[i];
597 Integer comp2=v2[i];
598
599 if(comp1>0 || comp2>0)
600 {
601 if(comp1>comp2)
602 return 1;
603 if(comp1<comp2)
604 return -1;
605 }
606 }
607
608 break;
609
610 case DEG_LEX:
611
612 // compute the degree of the heads in the elimination variables
613 for(short i=weighted_block_size;i<last_index;i++)
614 {
615 Integer comp1=v1[i];
616 Integer comp2=v2[i];
617
618 if(comp1>0)
619 w1+=comp1;
620 if(comp2>0)
621 w2+=comp2;
622 }
623
624 if(w1>w2)
625 return 1;
626 if(w1<w2)
627 return -1;
628
629 // if the degree is equal:
630 // tie breaking with the lexicographical ordering
631 for(short i=weighted_block_size;i<last_index;i++)
632 {
633 Integer comp1=v1[i];
634 Integer comp2=v2[i];
635
636 if(comp1>0 || comp2>0)
637 {
638 if(comp1>comp2)
639 return 1;
640 if(comp1<comp2)
641 return -1;
642 }
643 }
644
645 break;
646
647 case DEG_REV_LEX:
648
649 //compute the degree of the heads in the elimination variables
650 for(short i=weighted_block_size;i<last_index;i++)
651 {
652 Integer comp1=v1[i];
653 Integer comp2=v2[i];
654
655 if(comp1>0)
656 w1+=comp1;
657 if(comp2>0)
658 w2+=comp2;
659 }
660
661 if(w1>w2)
662 return 1;
663 if(w1<w2)
664 return -1;
665 // if the degree is equal:
666 // tie breaking with the reverse lexicographical ordering
667 for(short i=last_index-1;i>=weighted_block_size;i--)
668 {
669 Integer comp1=v1[i];
670 Integer comp2=v2[i];
671
672 if(comp1>0 || comp2>0)
673 {
674 if(comp1<comp2)
675 return 1;
676 if(comp1>comp2)
677 return -1;
678 }
679 }
680 }
681
682
683 // When reaching this line, the heads are equal in the elimination
684 // variables.
685 // Compute the weight of the heads.
686
687 w1=0;
688 for(short i=0;i<weighted_block_size;i++)
689 {
690 Integer actual_component=v1[i];
691 if(actual_component>0)
692 w1+=actual_component*weight_vector[i];
693 }
694
695 w2=0;
696 for(short i=0;i<weighted_block_size;i++)
697 {
698 Integer actual_component=v2[i];
699 if(actual_component>0)
700 w2+=actual_component*weight_vector[i];
701 }
702
703 if(w1>w2)
704 return 1;
705 if(w1<w2)
706 return -1;
707
708
709 // When reaching this line, the weight of the heads in the weighted
710 // variables are equal.
711 // Tie breaking with the term ordering refining the weight.
712
713 switch(weighted_ordering)
714 {
715 case W_LEX:
716
717 for(short i=0;i<weighted_block_size;i++)
718 {
719 Integer comp1=v1[i];
720 Integer comp2=v2[i];
721
722 if(comp1>0 || comp2>0)
723 {
724 if(comp1>comp2)
725 return 1;
726 if(comp1<comp2)
727 return -1;
728 }
729 }
730
731 break;
732
733 case W_REV_LEX:
734
735 for(short i=weighted_block_size-1;i>=0;i--)
736 {
737 Integer comp1=v1[i];
738 Integer comp2=v2[i];
739
740 if(comp1>0 || comp2>0)
741 {
742 if(comp1<comp2)
743 return 1;
744 if(comp1>comp2)
745 return -1;
746 }
747 }
748
749 break;
750
751 case W_DEG_LEX:
752
753 for(short i=0;i<weighted_block_size;i++)
754 {
755 Integer comp1=v1[i];
756 Integer comp2=v2[i];
757
758 if(comp1>0)
759 w1+=comp1;
760 if(comp2>0)
761 w2+=comp2;
762 }
763
764 if(w1>w2)
765 return 1;
766 if(w1<w2)
767 return -1;
768
769 for(short i=0;i<weighted_block_size;i++)
770 {
771 Integer comp1=v1[i];
772 Integer comp2=v2[i];
773
774 if(comp1>0 || comp2>0)
775 {
776 if(comp1>comp2)
777 return 1;
778 if(comp1<comp2)
779 return -1;
780 }
781 }
782
783 break;
784
785 case W_DEG_REV_LEX:
786
787 for(short i=0;i<weighted_block_size;i++)
788 {
789 Integer comp1=v1[i];
790 Integer comp2=v2[i];
791
792 if(comp1>0)
793 w1+=comp1;
794 if(comp2>0)
795 w2+=comp2;
796 }
797
798 if(w1>w2)
799 return 1;
800 if(w1<w2)
801 return -1;
802
803 for(short i=weighted_block_size-1;i>=0;i--)
804 {
805 Integer comp1=v1[i];
806 Integer comp2=v2[i];
807
808 if(comp1>0 || comp2>0)
809 {
810 if(comp1<comp2)
811 return 1;
812 if(comp1>comp2)
813 return -1;
814 }
815 }
816 }
817
818
819 // When reaching this line, the heads of the binomials are equal.
820 // Now we decide by the tails.
821 // This part of the code could also be omitted in the current context:
822 // The compare(...)-function is only called when dealing with ordered
823 // lists. This is done in two cases:
824 // - When computing with ordered S-pair lists, it doesn't really matter
825 // if such similar binomials are in the right order.
826 // - When outputting a reduced Groebner basis, it cannot happen that two
827 // heads are equal.
828
829 w1=0;
830 w2=0;
831
832 // First check the elimination variables.
833
834 if(elimination_block_size>0)
835 switch(elimination_ordering)
836 {
837 case LEX:
838
839 for(short i=weighted_block_size;i<last_index;i++)
840 {
841 Integer comp1=-v1[i];
842 Integer comp2=-v2[i];
843
844 if(comp1>0 || comp2>0)
845 {
846 if(comp1>comp2)
847 return 1;
848 if(comp1<comp2)
849 return -1;
850 }
851 }
852
853 break;
854
855 case DEG_LEX:
856
857 // compute the degree of the tails in the elimination variables
858 for(short i=weighted_block_size;i<last_index;i++)
859 {
860 Integer comp1=-v1[i];
861 Integer comp2=-v2[i];
862
863 if(comp1>0)
864 w1+=comp1;
865 if(comp2>0)
866 w2+=comp2;
867 }
868
869 if(w1>w2)
870 return 1;
871 if(w1<w2)
872 return -1;
873
874 // if the degree is equal:
875 // tie breaking with the lexicographical ordering
876 for(short i=weighted_block_size;i<last_index;i++)
877 {
878 Integer comp1=-v1[i];
879 Integer comp2=-v2[i];
880
881 if(comp1>0 || comp2>0)
882 {
883 if(comp1>comp2)
884 return 1;
885 if(comp1<comp2)
886 return -1;
887 }
888 }
889
890 break;
891
892 case DEG_REV_LEX:
893
894 // compute the degree of the tails in the elimination variables
895 for(short i=weighted_block_size;i<last_index;i++)
896 {
897 Integer comp1=-v1[i];
898 Integer comp2=-v2[i];
899
900 if(comp1>0)
901 w1+=comp1;
902 if(comp2>0)
903 w2+=comp2;
904 }
905
906 if(w1>w2)
907 return 1;
908 if(w1<w2)
909 return -1;
910 // if the degree is equal:
911 // tie breaking with the reverse lexicographical ordering
912 for(short i=last_index-1;i>=weighted_block_size;i--)
913 {
914 Integer comp1=-v1[i];
915 Integer comp2=-v2[i];
916
917 if(comp1>0 || comp2>0)
918 {
919 if(comp1<comp2)
920 return 1;
921 if(comp1>comp2)
922 return -1;
923 }
924 }
925 }
926
927
928 // When reaching this line, the tails are equal in the elimination
929 // variables.
930 // Compute the weight of the tails.
931
932 w1=0;
933 for(short i=0;i<weighted_block_size;i++)
934 {
935 Integer actual_component=-v1[i];
936 if(actual_component>0)
937 w1+=actual_component*weight_vector[i];
938 }
939
940 w2=0;
941 for(short i=0;i<weighted_block_size;i++)
942 {
943 Integer actual_component=-v2[i];
944 if(actual_component>0)
945 w2+=actual_component*weight_vector[i];
946 }
947
948 if(w1>w2)
949 return 1;
950 if(w1<w2)
951 return -1;
952
953
954 // When reaching this line, the weight of the tails in the weighted
955 // variables are equal.
956 // Tie breaking with the term ordering refining the weight.
957
958 switch(weighted_ordering)
959 {
960 case W_LEX:
961
962 for(short i=0;i<weighted_block_size;i++)
963 {
964 Integer comp1=-v1[i];
965 Integer comp2=-v2[i];
966
967 if(comp1>0 || comp2>0)
968 {
969 if(comp1>comp2)
970 return 1;
971 if(comp1<comp2)
972 return -1;
973 }
974 }
975
976 break;
977
978 case W_REV_LEX:
979
980 for(short i=weighted_block_size-1;i>=0;i--)
981 {
982 Integer comp1=-v1[i];
983 Integer comp2=-v2[i];
984
985 if(comp1>0 || comp2>0)
986 {
987 if(comp1<comp2)
988 return 1;
989 if(comp1>comp2)
990 return -1;
991 }
992 }
993
994 break;
995
996 case W_DEG_LEX:
997
998 for(short i=0;i<weighted_block_size;i++)
999 {
1000 Integer comp1=-v1[i];
1001 Integer comp2=-v2[i];
1002
1003 if(comp1>0)
1004 w1+=comp1;
1005 if(comp2>0)
1006 w2+=comp2;
1007 }
1008
1009 if(w1>w2)
1010 return 1;
1011 if(w1<w2)
1012 return -1;
1013
1014 for(short i=0;i<weighted_block_size;i++)
1015 {
1016 Integer comp1=-v1[i];
1017 Integer comp2=-v2[i];
1018
1019 if(comp1>0 || comp2>0)
1020 {
1021 if(comp1>comp2)
1022 return 1;
1023 if(comp1<comp2)
1024 return -1;
1025 }
1026 }
1027
1028 break;
1029
1030 case W_DEG_REV_LEX:
1031
1032 for(short i=0;i<weighted_block_size;i++)
1033 {
1034 Integer comp1=-v1[i];
1035 Integer comp2=-v2[i];
1036
1037 if(comp1>0)
1038 w1+=comp1;
1039 if(comp2>0)
1040 w2+=comp2;
1041 }
1042
1043 if(w1>w2)
1044 return 1;
1045 if(w1<w2)
1046 return -1;
1047
1048 for(short i=weighted_block_size-1;i>=0;i--)
1049 {
1050 Integer comp1=-v1[i];
1051 Integer comp2=-v2[i];
1052
1053 if(comp1>0 || comp2>0)
1054 {
1055 if(comp1<comp2)
1056 return 1;
1057 if(comp1>comp2)
1058 return -1;
1059 }
1060 }
1061 }
1062
1063 return 0;
1064
1065 }
1066
1067
1068
1069
1070 ///////// operators and routines needed by the IP-algorithms ////////////////
1071 ///////// to manipulate the term ordering ////////////////////////////////
1072
1073
1074
1075
operator =(const term_ordering & w)1076 term_ordering& term_ordering::operator=(const term_ordering& w)
1077 {
1078 if(&w==this)
1079 return *this;
1080
1081 if(weighted_block_size>0)
1082 delete[] weight_vector;
1083
1084 weighted_block_size=w.weighted_block_size;
1085 weighted_ordering=w.weighted_ordering;
1086 elimination_block_size=w.elimination_block_size;
1087 elimination_ordering=w.elimination_ordering;
1088 homogeneous=w.homogeneous;
1089
1090 if(weighted_block_size>0)
1091 {
1092 weight_vector=new float[weighted_block_size];
1093 for(short i=0;i<weighted_block_size;i++)
1094 weight_vector[i]=w.weight_vector[i];
1095 }
1096 else
1097 if(weighted_block_size<0)
1098 cerr<<"\nWARNING: term_ordering& term_ordering::"
1099 "operator=(const term_ordering&):\n"
1100 "assignment from corrupt term ordering"<<endl;
1101
1102 return(*this);
1103 }
1104
1105
1106
1107
operator [](const short & i) const1108 float term_ordering::operator[](const short& i) const
1109 {
1110 if((i<0) || (i>=weighted_block_size))
1111 {
1112 cerr<<"\nWARNING: float term_ordering::operator[](const short& i):\n"
1113 "access to invalid weight vector component"<<endl;
1114 return FLT_MAX;
1115 }
1116 else
1117 return weight_vector[i];
1118 }
1119
1120
1121
1122
convert_to_weighted_ordering()1123 term_ordering& term_ordering::convert_to_weighted_ordering()
1124 {
1125 elimination_block_size=0;
1126 return(*this);
1127 }
1128
1129
1130
1131
convert_to_elimination_ordering(const short & number_of_elimination_variables,const short & _elimination_ordering)1132 term_ordering& term_ordering::convert_to_elimination_ordering
1133 (const short& number_of_elimination_variables,
1134 const short& _elimination_ordering)
1135 {
1136 if((_elimination_ordering<1) || (_elimination_ordering>3))
1137 // unknown ordering on the elimination variables, set "error flag"
1138 weighted_block_size=-1;
1139 else
1140 elimination_ordering=_elimination_ordering;
1141
1142 if(number_of_elimination_variables<0)
1143 // argument out of range, set error flag
1144 weighted_block_size=-1;
1145 else
1146 elimination_block_size=number_of_elimination_variables;
1147
1148 if(weighted_block_size<0)
1149 cerr<<"\nWARNING: term_ordering& term_ordering::"
1150 "convert_to_elimination_ordering(const short&, const short&):\n"
1151 "argument out of range"<<endl;
1152
1153 return(*this);
1154 }
1155
1156
1157
1158
append_weighted_variable(const float & weight)1159 term_ordering& term_ordering::append_weighted_variable(const float& weight)
1160 {
1161 if(weighted_block_size>=0)
1162 {
1163 float *aux=weight_vector;
1164 weight_vector=new float[weighted_block_size+1];
1165
1166 for(short i=0;i<weighted_block_size;i++)
1167 weight_vector[i]=aux[i];
1168 weight_vector[weighted_block_size]=weight;
1169
1170 if(weighted_block_size>0)
1171 delete[] aux;
1172
1173 weighted_block_size++;
1174 }
1175 else
1176 cerr<<"\nWARNING: term_ordering& term_ordering::append_weighted_variable"
1177 "(const float&):\n"
1178 "called for a corrupt term ordering, term ordering not changed"
1179 <<endl;
1180
1181 return(*this);
1182 }
1183
1184
1185
1186
delete_last_weighted_variable()1187 term_ordering& term_ordering::delete_last_weighted_variable()
1188 {
1189 if(weighted_block_size>0)
1190 {
1191 float *aux=weight_vector;
1192
1193 if(weighted_block_size>1)
1194 weight_vector=new float[weighted_block_size-1];
1195
1196 for(short i=0;i<weighted_block_size-1;i++)
1197 weight_vector[i]=aux[i];
1198 weighted_block_size--;
1199
1200 delete[] aux;
1201 }
1202 else
1203 cerr<<"\nWARNING: term_ordering& term_ordering::"
1204 "delete_last_weighted_variable():\n"
1205 "called for a maybe corrupt term ordering without weighted variables,\n"
1206 "term ordering not changed"<<endl;
1207
1208 return(*this);
1209 }
1210
1211
1212
1213
swap_weights(const short & i,const short & j)1214 term_ordering& term_ordering::swap_weights(const short& i, const short& j)
1215 {
1216 if((i<0) || (i>=weighted_block_size) || (j<0) || (j>=weighted_block_size))
1217 {
1218 cout<<"\nWARNING: term_ordering& termordering::swap_weights"
1219 "(const short, const short):\nindex out of range"<<endl;
1220 return *this;
1221 }
1222
1223 float swap=weight_vector[j];
1224 weight_vector[j]=weight_vector[i];
1225 weight_vector[i]=swap;
1226
1227 return *this;
1228 }
1229
1230
1231
1232
1233 /////////////////// output ///////////////////////////////////////////////
1234
1235
1236
1237
print_weight_vector() const1238 void term_ordering::print_weight_vector() const
1239 {
1240 if(weighted_block_size<0)
1241 {
1242 printf("\nWARNING: void term_ordering::print_weight_vector():\n"
1243 "cannot print corrupt term ordering\n");
1244 return;
1245 }
1246
1247 printf("(");
1248 for(short i=0;i<weighted_block_size-1;i++)
1249 printf("%6.2f,",weight_vector[i]);
1250 printf("%6.2f)\n",weight_vector[weighted_block_size-1]);
1251 }
1252
1253
1254
1255
print() const1256 void term_ordering::print() const
1257 {
1258 if(weighted_block_size<0)
1259 {
1260 printf("\n\nWARNING: void term_ordering::print():\n"
1261 "cannot print corrupt term ordering\n");
1262 return;
1263 }
1264
1265 printf("\nelimination variables:%4d\n",elimination_block_size);
1266 printf("weighted variables: %4d\n",weighted_block_size);
1267
1268 printf("weight vector:\n");
1269 print_weight_vector();
1270
1271 if(elimination_block_size>0)
1272 {
1273 printf("ordering on elimination variables: ");
1274 switch(elimination_ordering)
1275 {
1276 case LEX:
1277 printf("LEX\n");
1278 break;
1279 case DEG_LEX:
1280 printf("DEG_LEX\n");
1281 break;
1282 case DEG_REV_LEX:
1283 printf("DEG_REV_LEX\n");
1284 break;
1285 }
1286 }
1287
1288 printf("ordering refining the weight: ");
1289 switch(weighted_ordering)
1290 {
1291 case W_LEX:
1292 printf("W_LEX\n\n");
1293 break;
1294 case W_REV_LEX:
1295 printf("W_REV_LEX\n\n");
1296 break;
1297 case W_DEG_LEX:
1298 printf("W_DEG_LEX\n\n");
1299 break;
1300 case W_DEG_REV_LEX:
1301 printf("W_DEG_REV_LEX\n\n");
1302 break;
1303 }
1304
1305 }
1306
1307
1308
1309
print_weight_vector(FILE * output) const1310 void term_ordering::print_weight_vector(FILE* output) const
1311 {
1312 if(weighted_block_size<0)
1313 {
1314 fprintf(output,"\nWARNING: void term_ordering::print_weight_vector(FILE*)"
1315 ":\ncannot print corrupt term ordering\n");
1316 return;
1317 }
1318
1319 fprintf(output,"(");
1320 for(short i=0;i<weighted_block_size-1;i++)
1321 fprintf(output,"%6.2f,",weight_vector[i]);
1322 fprintf(output,"%6.2f)\n",weight_vector[weighted_block_size-1]);
1323 }
1324
1325
1326
1327
print(FILE * output) const1328 void term_ordering::print(FILE* output) const
1329 {
1330 if(weighted_block_size<0)
1331 {
1332 fprintf(output,"\n\nWARNING: void term_ordering::print(FILE*):\n"
1333 "cannot print corrupt term ordering\n");
1334
1335 return;
1336 }
1337
1338 fprintf(output,"\nelimination variables:%4d\n",elimination_block_size);
1339 fprintf(output,"weighted variables: %4d\n",weighted_block_size);
1340
1341 fprintf(output,"weight_vector:\n");
1342 print_weight_vector(output);
1343
1344 if(elimination_block_size>0)
1345 {
1346 fprintf(output,"ordering on elimination variables: ");
1347 switch(elimination_ordering)
1348 {
1349 case LEX:
1350 fprintf(output,"LEX\n");
1351 break;
1352 case DEG_LEX:
1353 fprintf(output,"DEG_LEX\n");
1354 break;
1355 case DEG_REV_LEX:
1356 fprintf(output,"DEG_REV_LEX\n");
1357 break;
1358 }
1359 }
1360
1361 fprintf(output,"ordering refining the weight: ");
1362 switch(weighted_ordering)
1363 {
1364 case W_LEX:
1365 fprintf(output,"W_LEX\n\n");
1366 break;
1367 case W_REV_LEX:
1368 fprintf(output,"W_REV_LEX\n\n");
1369 break;
1370 case W_DEG_LEX:
1371 fprintf(output,"W_DEG_LEX\n\n");
1372 break;
1373 case W_DEG_REV_LEX:
1374 fprintf(output,"W_DEG_REV_LEX\n\n");
1375 break;
1376 }
1377 }
1378
1379
1380
1381
print_weight_vector(ofstream & output) const1382 void term_ordering::print_weight_vector(ofstream& output) const
1383 {
1384 if(weighted_block_size<0)
1385 {
1386 output<<"\nWARNING: void term_ordering::print_weight_vector(ofstream&):\n"
1387 "cannot print corrupt term ordering"<<endl;
1388 return;
1389 }
1390
1391 output<<"(";
1392 for(short i=0;i<weighted_block_size-1;i++)
1393 output<<setw(6)<<setprecision(2)<<weight_vector[i]<<",";
1394 output<<setw(6)<<setprecision(2)<<weight_vector[weighted_block_size-1]
1395 <<")"<<endl<<endl;
1396 }
1397
1398
1399
1400
print(ofstream & output) const1401 void term_ordering::print(ofstream& output) const
1402 {
1403 if(weighted_block_size<0)
1404 {
1405 output<<"\nWARNING: void term_ordering::print(ofstream&):\n"
1406 "cannot print corrupt term ordering"<<endl;
1407 return;
1408 }
1409
1410 output<<"\nelimination variables:"<<setw(4)<<elimination_block_size<<endl
1411 <<"weighted variables: "<<setw(4)<<weighted_block_size<<endl;
1412
1413 output<<"weight_vector:"<<endl;
1414 print_weight_vector(output);
1415
1416 if(elimination_block_size>0)
1417 {
1418 output<<"ordering on elimination variables: ";
1419 switch(elimination_ordering)
1420 {
1421 case LEX:
1422 output<<"LEX\n"<<endl;
1423 break;
1424 case DEG_LEX:
1425 output<<"DEG_LEX\n"<<endl;
1426 break;
1427 case DEG_REV_LEX:
1428 output<<"DEG_REV_LEX\n"<<endl;
1429 break;
1430 }
1431 }
1432
1433 output<<"ordering refining the weight: ";
1434 switch(weighted_ordering)
1435 {
1436 case W_LEX:
1437 output<<"W_LEX\n"<<endl;
1438 break;
1439 case W_REV_LEX:
1440 output<<"W_REV_LEX\n"<<endl;
1441 break;
1442 case W_DEG_LEX:
1443 output<<"W_DEG_LEX\n"<<endl;
1444 break;
1445 case W_DEG_REV_LEX:
1446 output<<"W_DEG_REV_LEX\n"<<endl;
1447 break;
1448 }
1449 }
1450
format_print_weight_vector(ofstream & output) const1451 void term_ordering::format_print_weight_vector(ofstream& output) const
1452 {
1453 for(short i=0;i<weighted_block_size;i++)
1454 output<<setw(6)<<setprecision(2)<<weight_vector[i];
1455 output<<endl;
1456 }
1457 #endif // TERM_ORDERING_CC
1458