source: git/IntegerProgramming/term_ordering.cc @ eaf4cb

spielwiese
Last change on this file since eaf4cb was 056f98, checked in by Hans Schönemann <hannes@…>, 23 years ago
*hannes:new +memset git-svn-id: file:///usr/local/Singular/svn/trunk@5377 2c84dea3-7e68-4137-9b89-c4e89433aadc
  • Property mode set to 100644
File size: 32.9 KB
Line 
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
12term_ordering::term_ordering(const BOOLEAN& _homogeneous=FALSE)
13    :homogeneous(_homogeneous)
14{
15  weight_vector=NULL;
16  weighted_block_size=0;
17  elimination_block_size=0;
18}
19
20
21
22
23term_ordering::term_ordering(const short& number_of_weighted_variables,
24                             const float* weights,
25                             const short& _weighted_ordering,
26                             const BOOLEAN& _homogeneous=FALSE)
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
83term_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=FALSE)
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
151term_ordering::term_ordering(ifstream& input, const short& _weighted_ordering,
152                             const BOOLEAN& _homogeneous=FALSE)
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
219term_ordering::term_ordering(const short& n, ifstream& input,
220                             const short& _weighted_ordering,
221                             const BOOLEAN& _homogeneous=FALSE)
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
288term_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
311term_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
325short term_ordering::number_of_weighted_variables() const
326{
327  return weighted_block_size;
328}
329
330
331
332short term_ordering::weight_refinement() const
333{
334  return weighted_ordering;
335}
336
337
338
339short term_ordering::number_of_elimination_variables() const
340{
341  return elimination_block_size;
342}
343
344
345
346short term_ordering::elimination_refinement() const
347{
348  return elimination_ordering;
349}
350
351
352
353BOOLEAN term_ordering::is_homogeneous() const
354{
355  return homogeneous;
356}
357
358
359
360short term_ordering::error_status() const
361{
362  if(weighted_block_size<0)
363    return weighted_block_size;
364  return 0;
365}
366
367
368
369BOOLEAN 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
379BOOLEAN 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
395double 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
406short 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
574short 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
1076term_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
1108float 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
1123term_ordering& term_ordering::convert_to_weighted_ordering()
1124{
1125  elimination_block_size=0;
1126  return(*this);
1127}
1128
1129
1130
1131
1132term_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
1159term_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
1187term_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
1214term_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
1238void 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
1256void 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
1310void 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
1328void 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
1382void 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
1401void 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
1451void 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
Note: See TracBrowser for help on using the repository browser.