source: git/IntegerProgramming/term_ordering.cc @ 27e935

spielwiese
Last change on this file since 27e935 was 6ba162, checked in by Hans Schönemann <hannes@…>, 24 years ago
This commit was generated by cvs2svn to compensate for changes in r4282, which included commits to RCS files with non-trunk default branches. git-svn-id: file:///usr/local/Singular/svn/trunk@4283 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        negative_weight=TRUE;
260      if(weight_vector[i]==0)
261        zero_weight=TRUE;
262    }
263
264    if(negative_weight==TRUE)
265      cerr<<"\nWARNING: term_ordering::term_ordering(const short&, ifstream&, "
266        "const short&):\nWeight vector with negative components does not "
267        "define a well ordering"<<endl;
268
269    if((weighted_ordering==W_REV_LEX) && (zero_weight==TRUE))
270      cerr<<"\nWARNING: term_ordering::term_ordering(const short&, ifstream&, "
271        "const short&):\nZero weights refined by a reverse lexicographical "
272        "ordering do not define a well ordering"<<endl;
273  }
274  else
275    if(weighted_block_size<0)
276      cerr<<"\nWARNING: term_ordering::term_ordering(const short&, ifstream&, "
277        "const short&):\n Building a term ordering from a corrupt one"<<endl;
278
279  elimination_block_size=0;
280}
281
282
283
284
285term_ordering::term_ordering(const term_ordering& w)
286    :weighted_block_size(w.weighted_block_size),
287     weighted_ordering(w.weighted_ordering),
288     elimination_block_size(w.elimination_block_size),
289     elimination_ordering(w.elimination_ordering),
290     homogeneous(w.homogeneous)
291{
292  if(weighted_block_size>0)
293  {
294    weight_vector=new float[weighted_block_size];
295    for(short i=0;i<weighted_block_size;i++)
296      weight_vector[i]=w.weight_vector[i];
297  }
298  else
299    if(weighted_block_size<0)
300      cerr<<"\nWARNING: term_ordering::term_ordering(const term_ordering&):\n"
301        "Building a term ordering from a corrupt one"<<endl;
302
303}
304
305
306
307
308term_ordering::~term_ordering()
309{
310  if(weighted_block_size>0)
311    delete[] weight_vector;
312}
313
314
315
316
317/////////////// object properties /////////////////////////////////////////
318
319
320
321
322short term_ordering::number_of_weighted_variables() const
323{
324  return weighted_block_size;
325}
326
327
328
329short term_ordering::weight_refinement() const
330{
331  return weighted_ordering;
332}
333
334
335
336short term_ordering::number_of_elimination_variables() const
337{
338  return elimination_block_size;
339}
340
341
342
343short term_ordering::elimination_refinement() const
344{
345  return elimination_ordering;
346}
347
348
349
350BOOLEAN term_ordering::is_homogeneous() const
351{
352  return homogeneous;
353}
354
355
356
357short term_ordering::error_status() const
358{
359  if(weighted_block_size<0)
360    return weighted_block_size;
361  return 0;
362}
363
364
365
366BOOLEAN term_ordering::is_nonnegative() const
367{
368  for(int i=0;i<weighted_block_size;i++)
369    if(weight_vector[i]<0)
370      return FALSE;
371  return TRUE;
372}
373
374
375
376BOOLEAN term_ordering::is_positive() const
377{
378  for(int i=0;i<weighted_block_size;i++)
379    if(weight_vector[i]<=0)
380      return FALSE;
381  return TRUE;
382}
383
384
385
386
387/////////////// frequently used comparison functions //////////////////////
388
389
390
391
392double term_ordering::weight(const Integer* v) const
393{
394  double result=0;
395  for(short i=0;i<weighted_block_size;i++)
396    result+=(weight_vector[i]*v[i]);
397  return(result);
398}
399
400
401
402
403short term_ordering::compare_to_zero(const Integer* v) const
404{
405  unsigned short last_index=weighted_block_size+elimination_block_size;
406  double w=0;
407
408  // First check the elimination variables.
409
410  if(elimination_block_size>0)
411    switch(elimination_ordering)
412    {
413        case LEX:
414
415          for(short i=weighted_block_size;i<last_index;i++)
416          {
417            Integer actual_component=v[i];
418            if(actual_component>0)
419              return 1;
420            if(actual_component<0)
421              return -1;
422          }
423
424        break;
425
426        case DEG_LEX:
427
428          // compute the degree
429          for(short i=weighted_block_size;i<last_index;i++)
430            w+=v[i];
431
432          if(w>0)
433            return 1;
434          if(w<0)
435            return -1;
436
437          // if the degree is zero:
438          // tie breaking with the lexicographical ordering
439          for(short i=weighted_block_size;i<last_index;i++)
440          {
441            Integer actual_component=v[i];
442            if(actual_component>0)
443              return 1;
444            if(actual_component<0)
445              return -1;
446          }
447
448          break;
449
450        case DEG_REV_LEX:
451
452          //compute the degree
453          for(short i=weighted_block_size;i<last_index;i++)
454            w+=v[i];
455
456          if(w>0)
457            return 1;
458          if(w<0)
459            return -1;
460          // if the degree is zero:
461          // tie breaking with the reverse lexicographical ordering
462          for(short i=last_index-1;i>=weighted_block_size;i--)
463          {
464            Integer actual_component=v[i];
465            if(actual_component<0)
466              return 1;
467            if(actual_component>0)
468              return -1;
469          }
470    }
471
472
473  // When reaching this line, the vector components corresponding to
474  // elimination variables are all zero.
475  // Compute the weight.
476  // If the term ordering is a homogeneous one, this is superfluous.
477
478  if(!homogeneous)
479  {
480    w=weight(v);
481    if(w>0)
482      return 1;
483    if(w<0)
484      return -1;
485  }
486
487
488  // When reaching this line, the weight of the vector components corresponding
489  // to weighted variables is zero.
490  // Tie breaking with the term ordering refining the weight.
491
492  switch(weighted_ordering)
493  {
494      case W_LEX:
495
496        for(short i=0;i<weighted_block_size;i++)
497        {
498          Integer actual_component=v[i];
499          if(actual_component>0)
500            return 1;
501          if(actual_component<0)
502            return -1;
503        }
504
505        break;
506
507      case W_REV_LEX:
508
509        for(short i=weighted_block_size-1;i>=0;i--)
510        {
511          Integer actual_component=v[i];
512          if(actual_component<0)
513            return 1;
514          if(actual_component>0)
515            return -1;
516        }
517
518        break;
519
520      case W_DEG_LEX:
521
522        for(short i=0;i<weighted_block_size;i++)
523          w+=v[i];
524
525        if(w>0)
526          return 1;
527        if(w<0)
528          return -1;
529
530        for(short i=0;i<weighted_block_size;i++)
531        {
532          Integer actual_component=v[i];
533          if(actual_component>0)
534            return 1;
535          if(actual_component<0)
536            return -1;
537        }
538
539        break;
540
541      case W_DEG_REV_LEX:
542
543        for(short i=0;i<weighted_block_size;i++)
544          w+=v[i];
545
546        if(w>0)
547          return 1;
548        if(w<0)
549          return -1;
550
551        for(short i=weighted_block_size-1;i>=0;i--)
552        {
553          Integer actual_component=v[i];
554          if(actual_component<0)
555            return 1;
556          if(actual_component>0)
557            return -1;
558        }
559
560  }
561
562  // When reaching this line, the argument vector is the zero vector.
563
564  return 0;
565
566}
567
568
569
570
571short term_ordering::compare(const binomial& bin1, const binomial& bin2) const
572{
573  unsigned short last_index=weighted_block_size+elimination_block_size;
574  double w1=0;
575  double w2=0;
576
577  Integer* v1=bin1.exponent_vector;
578  Integer* v2=bin2.exponent_vector;
579
580  // First compare the heads of the input binomials.
581  // The code is analogous to the routine compare_to_zero(...), except
582  // from the fact that we must consider the sign of the vector components.
583
584  // First check the elimination variables.
585
586  if(elimination_block_size>0)
587    switch(elimination_ordering)
588    {
589        case LEX:
590
591          for(short i=weighted_block_size;i<last_index;i++)
592          {
593            Integer comp1=v1[i];
594            Integer comp2=v2[i];
595
596            if(comp1>0 || comp2>0)
597            {
598              if(comp1>comp2)
599                return 1;
600              if(comp1<comp2)
601                return -1;
602            }
603          }
604
605        break;
606
607        case DEG_LEX:
608
609          // compute the degree of the heads in the elimination variables
610          for(short i=weighted_block_size;i<last_index;i++)
611          {
612            Integer comp1=v1[i];
613            Integer comp2=v2[i];
614
615            if(comp1>0)
616              w1+=comp1;
617            if(comp2>0)
618              w2+=comp2;
619          }
620
621          if(w1>w2)
622            return 1;
623          if(w1<w2)
624            return -1;
625
626          // if the degree is equal:
627          // tie breaking with the lexicographical ordering
628          for(short i=weighted_block_size;i<last_index;i++)
629          {
630            Integer comp1=v1[i];
631            Integer comp2=v2[i];
632
633            if(comp1>0 || comp2>0)
634            {
635              if(comp1>comp2)
636                return 1;
637              if(comp1<comp2)
638                return -1;
639            }
640          }
641
642          break;
643
644        case DEG_REV_LEX:
645
646          //compute the degree of the heads in the elimination variables
647          for(short i=weighted_block_size;i<last_index;i++)
648          {
649            Integer comp1=v1[i];
650            Integer comp2=v2[i];
651
652            if(comp1>0)
653              w1+=comp1;
654            if(comp2>0)
655              w2+=comp2;
656          }
657
658          if(w1>w2)
659            return 1;
660          if(w1<w2)
661            return -1;
662          // if the degree is equal:
663          // tie breaking with the reverse lexicographical ordering
664          for(short i=last_index-1;i>=weighted_block_size;i--)
665          {
666            Integer comp1=v1[i];
667            Integer comp2=v2[i];
668
669            if(comp1>0 || comp2>0)
670            {
671              if(comp1<comp2)
672                return 1;
673              if(comp1>comp2)
674                return -1;
675            }
676          }
677    }
678
679
680  // When reaching this line, the heads are equal in the elimination
681  // variables.
682  // Compute the weight of the heads.
683
684  w1=0;
685  for(short i=0;i<weighted_block_size;i++)
686  {
687    Integer actual_component=v1[i];
688    if(actual_component>0)
689      w1+=actual_component*weight_vector[i];
690  }
691
692  w2=0;
693  for(short i=0;i<weighted_block_size;i++)
694  {
695    Integer actual_component=v2[i];
696    if(actual_component>0)
697      w2+=actual_component*weight_vector[i];
698  }
699
700  if(w1>w2)
701    return 1;
702  if(w1<w2)
703    return -1;
704
705
706  // When reaching this line, the weight of the heads in the weighted
707  // variables are equal.
708  // Tie breaking with the term ordering refining the weight.
709
710  switch(weighted_ordering)
711  {
712      case W_LEX:
713
714        for(short i=0;i<weighted_block_size;i++)
715        {
716          Integer comp1=v1[i];
717          Integer comp2=v2[i];
718
719          if(comp1>0 || comp2>0)
720          {
721            if(comp1>comp2)
722              return 1;
723            if(comp1<comp2)
724              return -1;
725          }
726        }
727
728        break;
729
730      case W_REV_LEX:
731
732        for(short i=weighted_block_size-1;i>=0;i--)
733        {
734          Integer comp1=v1[i];
735          Integer comp2=v2[i];
736
737          if(comp1>0 || comp2>0)
738          {
739            if(comp1<comp2)
740              return 1;
741            if(comp1>comp2)
742              return -1;
743          }
744        }
745
746        break;
747
748      case W_DEG_LEX:
749
750        for(short i=0;i<weighted_block_size;i++)
751        {
752          Integer comp1=v1[i];
753          Integer comp2=v2[i];
754
755          if(comp1>0)
756            w1+=comp1;
757          if(comp2>0)
758            w2+=comp2;
759        }
760
761        if(w1>w2)
762          return 1;
763        if(w1<w2)
764          return -1;
765
766        for(short i=0;i<weighted_block_size;i++)
767        {
768          Integer comp1=v1[i];
769          Integer comp2=v2[i];
770
771          if(comp1>0 || comp2>0)
772          {
773            if(comp1>comp2)
774              return 1;
775            if(comp1<comp2)
776              return -1;
777          }
778        }
779
780        break;
781
782      case W_DEG_REV_LEX:
783
784        for(short i=0;i<weighted_block_size;i++)
785        {
786          Integer comp1=v1[i];
787          Integer comp2=v2[i];
788
789          if(comp1>0)
790            w1+=comp1;
791          if(comp2>0)
792            w2+=comp2;
793        }
794
795        if(w1>w2)
796          return 1;
797        if(w1<w2)
798          return -1;
799
800        for(short i=weighted_block_size-1;i>=0;i--)
801        {
802          Integer comp1=v1[i];
803          Integer comp2=v2[i];
804
805          if(comp1>0 || comp2>0)
806          {
807            if(comp1<comp2)
808              return 1;
809            if(comp1>comp2)
810              return -1;
811          }
812        }
813  }
814
815
816  // When reaching this line, the heads of the binomials are equal.
817  // Now we decide by the tails.
818  // This part of the code could also be omitted in the current context:
819  // The compare(...)-function is only called when dealing with ordered
820  // lists. This is done in two cases:
821  // - When computing with ordered S-pair lists, it doesn't really matter
822  //   if such similar binomials are in the right order.
823  // - When outputting a reduced Groebner basis, it cannot happen that two
824  //   heads are equal.
825
826  w1=0;
827  w2=0;
828
829  // First check the elimination variables.
830
831  if(elimination_block_size>0)
832    switch(elimination_ordering)
833    {
834        case LEX:
835
836          for(short i=weighted_block_size;i<last_index;i++)
837          {
838            Integer comp1=-v1[i];
839            Integer comp2=-v2[i];
840
841            if(comp1>0 || comp2>0)
842            {
843              if(comp1>comp2)
844                return 1;
845              if(comp1<comp2)
846                return -1;
847            }
848          }
849
850        break;
851
852        case DEG_LEX:
853
854          // compute the degree of the tails in the elimination variables
855          for(short i=weighted_block_size;i<last_index;i++)
856          {
857            Integer comp1=-v1[i];
858            Integer comp2=-v2[i];
859
860            if(comp1>0)
861              w1+=comp1;
862            if(comp2>0)
863              w2+=comp2;
864          }
865
866          if(w1>w2)
867            return 1;
868          if(w1<w2)
869            return -1;
870
871          // if the degree is equal:
872          // tie breaking with the lexicographical ordering
873          for(short i=weighted_block_size;i<last_index;i++)
874          {
875            Integer comp1=-v1[i];
876            Integer comp2=-v2[i];
877
878            if(comp1>0 || comp2>0)
879            {
880              if(comp1>comp2)
881                return 1;
882              if(comp1<comp2)
883                return -1;
884            }
885          }
886
887          break;
888
889        case DEG_REV_LEX:
890
891          // compute the degree of the tails in the elimination variables
892          for(short i=weighted_block_size;i<last_index;i++)
893          {
894            Integer comp1=-v1[i];
895            Integer comp2=-v2[i];
896
897            if(comp1>0)
898              w1+=comp1;
899            if(comp2>0)
900              w2+=comp2;
901          }
902
903          if(w1>w2)
904            return 1;
905          if(w1<w2)
906            return -1;
907          // if the degree is equal:
908          // tie breaking with the reverse lexicographical ordering
909          for(short i=last_index-1;i>=weighted_block_size;i--)
910          {
911            Integer comp1=-v1[i];
912            Integer comp2=-v2[i];
913
914            if(comp1>0 || comp2>0)
915            {
916              if(comp1<comp2)
917                return 1;
918              if(comp1>comp2)
919                return -1;
920            }
921          }
922    }
923
924
925  // When reaching this line, the tails are equal in the elimination
926  // variables.
927  // Compute the weight of the tails.
928
929  w1=0;
930  for(short i=0;i<weighted_block_size;i++)
931  {
932    Integer actual_component=-v1[i];
933    if(actual_component>0)
934      w1+=actual_component*weight_vector[i];
935  }
936
937  w2=0;
938  for(short i=0;i<weighted_block_size;i++)
939  {
940    Integer actual_component=-v2[i];
941    if(actual_component>0)
942      w2+=actual_component*weight_vector[i];
943  }
944
945  if(w1>w2)
946    return 1;
947  if(w1<w2)
948    return -1;
949
950
951  // When reaching this line, the weight of the tails in the weighted
952  // variables are equal.
953  // Tie breaking with the term ordering refining the weight.
954
955  switch(weighted_ordering)
956  {
957      case W_LEX:
958
959        for(short i=0;i<weighted_block_size;i++)
960        {
961          Integer comp1=-v1[i];
962          Integer comp2=-v2[i];
963
964          if(comp1>0 || comp2>0)
965          {
966            if(comp1>comp2)
967              return 1;
968            if(comp1<comp2)
969              return -1;
970          }
971        }
972
973        break;
974
975      case W_REV_LEX:
976
977        for(short i=weighted_block_size-1;i>=0;i--)
978        {
979          Integer comp1=-v1[i];
980          Integer comp2=-v2[i];
981
982          if(comp1>0 || comp2>0)
983          {
984            if(comp1<comp2)
985              return 1;
986            if(comp1>comp2)
987              return -1;
988          }
989        }
990
991        break;
992
993      case W_DEG_LEX:
994
995        for(short i=0;i<weighted_block_size;i++)
996        {
997          Integer comp1=-v1[i];
998          Integer comp2=-v2[i];
999
1000          if(comp1>0)
1001            w1+=comp1;
1002          if(comp2>0)
1003            w2+=comp2;
1004        }
1005
1006        if(w1>w2)
1007          return 1;
1008        if(w1<w2)
1009          return -1;
1010
1011        for(short i=0;i<weighted_block_size;i++)
1012        {
1013          Integer comp1=-v1[i];
1014          Integer comp2=-v2[i];
1015
1016          if(comp1>0 || comp2>0)
1017          {
1018            if(comp1>comp2)
1019              return 1;
1020            if(comp1<comp2)
1021              return -1;
1022          }
1023        }
1024
1025        break;
1026
1027      case W_DEG_REV_LEX:
1028
1029        for(short i=0;i<weighted_block_size;i++)
1030        {
1031          Integer comp1=-v1[i];
1032          Integer comp2=-v2[i];
1033
1034          if(comp1>0)
1035            w1+=comp1;
1036          if(comp2>0)
1037            w2+=comp2;
1038        }
1039
1040        if(w1>w2)
1041          return 1;
1042        if(w1<w2)
1043          return -1;
1044
1045        for(short i=weighted_block_size-1;i>=0;i--)
1046        {
1047          Integer comp1=-v1[i];
1048          Integer comp2=-v2[i];
1049
1050          if(comp1>0 || comp2>0)
1051          {
1052            if(comp1<comp2)
1053              return 1;
1054            if(comp1>comp2)
1055              return -1;
1056          }
1057        }
1058  }
1059
1060  return 0;
1061
1062}
1063
1064
1065
1066
1067///////// operators and routines needed by the IP-algorithms ////////////////
1068///////// to manipulate the term ordering ////////////////////////////////
1069
1070
1071
1072
1073term_ordering& term_ordering::operator=(const term_ordering& w)
1074{
1075  if(&w==this)
1076    return *this;
1077
1078  if(weighted_block_size>0)
1079    delete[] weight_vector;
1080
1081  weighted_block_size=w.weighted_block_size;
1082  weighted_ordering=w.weighted_ordering;
1083  elimination_block_size=w.elimination_block_size;
1084  elimination_ordering=w.elimination_ordering;
1085  homogeneous=w.homogeneous;
1086
1087  if(weighted_block_size>0)
1088  {
1089    weight_vector=new float[weighted_block_size];
1090    for(short i=0;i<weighted_block_size;i++)
1091      weight_vector[i]=w.weight_vector[i];
1092  }
1093  else
1094    if(weighted_block_size<0)
1095      cerr<<"\nWARNING: term_ordering& term_ordering::"
1096        "operator=(const term_ordering&):\n"
1097        "assignment from corrupt term ordering"<<endl;
1098
1099  return(*this);
1100}
1101
1102
1103
1104
1105float term_ordering::operator[](const short& i) const
1106{
1107  if((i<0) || (i>=weighted_block_size))
1108  {
1109    cerr<<"\nWARNING: float term_ordering::operator[](const short& i):\n"
1110      "access to invalid weight vector component"<<endl;
1111    return FLT_MAX;
1112  }
1113  else
1114    return weight_vector[i];
1115}
1116
1117
1118
1119
1120term_ordering& term_ordering::convert_to_weighted_ordering()
1121{
1122  elimination_block_size=0;
1123  return(*this);
1124}
1125
1126
1127
1128
1129term_ordering& term_ordering::convert_to_elimination_ordering
1130(const short& number_of_elimination_variables,
1131 const short& _elimination_ordering)
1132{
1133  if((_elimination_ordering<1) || (_elimination_ordering>3))
1134    // unknown ordering on the elimination variables, set "error flag"
1135    weighted_block_size=-1;
1136  else
1137    elimination_ordering=_elimination_ordering;
1138
1139  if(number_of_elimination_variables<0)
1140    // argument out of range, set error flag
1141    weighted_block_size=-1;
1142  else
1143    elimination_block_size=number_of_elimination_variables;
1144
1145  if(weighted_block_size<0)
1146    cerr<<"\nWARNING: term_ordering& term_ordering::"
1147      "convert_to_elimination_ordering(const short&, const short&):\n"
1148      "argument out of range"<<endl;
1149
1150  return(*this);
1151}
1152
1153
1154
1155
1156term_ordering& term_ordering::append_weighted_variable(const float& weight)
1157{
1158  if(weighted_block_size>=0)
1159  {
1160    float *aux=weight_vector;
1161    weight_vector=new float[weighted_block_size+1];
1162
1163    for(short i=0;i<weighted_block_size;i++)
1164      weight_vector[i]=aux[i];
1165    weight_vector[weighted_block_size]=weight;
1166
1167    if(weighted_block_size>0)
1168      delete[] aux;
1169
1170    weighted_block_size++;
1171  }
1172  else
1173    cerr<<"\nWARNING: term_ordering& term_ordering::append_weighted_variable"
1174      "(const float&):\n"
1175      "called for a corrupt term ordering, term ordering not changed"
1176        <<endl;
1177
1178  return(*this);
1179}
1180
1181
1182
1183
1184term_ordering& term_ordering::delete_last_weighted_variable()
1185{
1186  if(weighted_block_size>0)
1187  {
1188    float *aux=weight_vector;
1189
1190    if(weighted_block_size>1)
1191      weight_vector=new float[weighted_block_size-1];
1192
1193    for(short i=0;i<weighted_block_size-1;i++)
1194      weight_vector[i]=aux[i];
1195    weighted_block_size--;
1196
1197    delete[] aux;
1198  }
1199  else
1200    cerr<<"\nWARNING: term_ordering& term_ordering::"
1201      "delete_last_weighted_variable():\n"
1202      "called for a maybe corrupt term ordering without weighted variables,\n"
1203      "term ordering not changed"<<endl;
1204
1205  return(*this);
1206}
1207
1208
1209
1210
1211term_ordering& term_ordering::swap_weights(const short& i, const short& j)
1212{
1213  if((i<0) || (i>=weighted_block_size) || (j<0) || (j>=weighted_block_size))
1214  {
1215    cout<<"\nWARNING: term_ordering& termordering::swap_weights"
1216      "(const short, const short):\nindex out of range"<<endl;
1217    return *this;
1218  }
1219
1220  float swap=weight_vector[j];
1221  weight_vector[j]=weight_vector[i];
1222  weight_vector[i]=swap;
1223
1224  return *this;
1225}
1226
1227
1228
1229
1230/////////////////// output ///////////////////////////////////////////////
1231
1232
1233
1234
1235void term_ordering::print_weight_vector() const
1236{
1237  if(weighted_block_size<0)
1238  {
1239    printf("\nWARNING: void term_ordering::print_weight_vector():\n"
1240           "cannot print corrupt term ordering\n");
1241    return;
1242  }
1243
1244  printf("(");
1245  for(short i=0;i<weighted_block_size-1;i++)
1246    printf("%6.2f,",weight_vector[i]);
1247  printf("%6.2f)\n",weight_vector[weighted_block_size-1]);
1248}
1249
1250
1251
1252
1253void term_ordering::print() const
1254{
1255  if(weighted_block_size<0)
1256  {
1257    printf("\n\nWARNING: void term_ordering::print():\n"
1258           "cannot print corrupt term ordering\n");
1259    return;
1260  }
1261
1262  printf("\nelimination variables:%4d\n",elimination_block_size);
1263  printf("weighted variables:   %4d\n",weighted_block_size);
1264
1265  printf("weight vector:\n");
1266  print_weight_vector();
1267
1268  if(elimination_block_size>0)
1269  {
1270    printf("ordering on elimination variables: ");
1271    switch(elimination_ordering)
1272    {
1273        case LEX:
1274          printf("LEX\n");
1275          break;
1276        case DEG_LEX:
1277          printf("DEG_LEX\n");
1278          break;
1279        case DEG_REV_LEX:
1280          printf("DEG_REV_LEX\n");
1281          break;
1282    }
1283  }
1284
1285  printf("ordering refining the weight:      ");
1286  switch(weighted_ordering)
1287  {
1288      case W_LEX:
1289        printf("W_LEX\n\n");
1290        break;
1291      case W_REV_LEX:
1292        printf("W_REV_LEX\n\n");
1293        break;
1294      case W_DEG_LEX:
1295        printf("W_DEG_LEX\n\n");
1296        break;
1297      case W_DEG_REV_LEX:
1298        printf("W_DEG_REV_LEX\n\n");
1299        break;
1300  }
1301
1302}
1303
1304
1305
1306
1307void term_ordering::print_weight_vector(FILE* output) const
1308{
1309  if(weighted_block_size<0)
1310  {
1311    fprintf(output,"\nWARNING: void term_ordering::print_weight_vector(FILE*)"
1312            ":\ncannot print corrupt term ordering\n");
1313    return;
1314  }
1315
1316  fprintf(output,"(");
1317  for(short i=0;i<weighted_block_size-1;i++)
1318    fprintf(output,"%6.2f,",weight_vector[i]);
1319  fprintf(output,"%6.2f)\n",weight_vector[weighted_block_size-1]);
1320}
1321
1322
1323
1324
1325void term_ordering::print(FILE* output) const
1326{
1327  if(weighted_block_size<0)
1328  {
1329    fprintf(output,"\n\nWARNING: void term_ordering::print(FILE*):\n"
1330           "cannot print corrupt term ordering\n");
1331
1332    return;
1333  }
1334
1335  fprintf(output,"\nelimination variables:%4d\n",elimination_block_size);
1336  fprintf(output,"weighted variables:   %4d\n",weighted_block_size);
1337
1338  fprintf(output,"weight_vector:\n");
1339  print_weight_vector(output);
1340
1341  if(elimination_block_size>0)
1342  {
1343    fprintf(output,"ordering on elimination variables: ");
1344    switch(elimination_ordering)
1345    {
1346        case LEX:
1347          fprintf(output,"LEX\n");
1348          break;
1349        case DEG_LEX:
1350          fprintf(output,"DEG_LEX\n");
1351          break;
1352        case DEG_REV_LEX:
1353          fprintf(output,"DEG_REV_LEX\n");
1354          break;
1355    }
1356  }
1357
1358  fprintf(output,"ordering refining the weight:      ");
1359  switch(weighted_ordering)
1360  {
1361      case W_LEX:
1362        fprintf(output,"W_LEX\n\n");
1363        break;
1364      case W_REV_LEX:
1365        fprintf(output,"W_REV_LEX\n\n");
1366        break;
1367      case W_DEG_LEX:
1368        fprintf(output,"W_DEG_LEX\n\n");
1369        break;
1370      case W_DEG_REV_LEX:
1371        fprintf(output,"W_DEG_REV_LEX\n\n");
1372        break;
1373  }
1374}
1375
1376
1377
1378
1379void term_ordering::print_weight_vector(ofstream& output) const
1380{
1381  if(weighted_block_size<0)
1382  {
1383    output<<"\nWARNING: void term_ordering::print_weight_vector(ofstream&):\n"
1384      "cannot print corrupt term ordering"<<endl;
1385    return;
1386  }
1387
1388  output<<"(";
1389  for(short i=0;i<weighted_block_size-1;i++)
1390    output<<setw(6)<<setprecision(2)<<weight_vector[i]<<",";
1391  output<<setw(6)<<setprecision(2)<<weight_vector[weighted_block_size-1]
1392        <<")"<<endl<<endl;
1393}
1394
1395
1396
1397
1398void term_ordering::print(ofstream& output) const
1399{
1400  if(weighted_block_size<0)
1401  {
1402    output<<"\nWARNING: void term_ordering::print(ofstream&):\n"
1403      "cannot print corrupt term ordering"<<endl;
1404    return;
1405  }
1406
1407  output<<"\nelimination variables:"<<setw(4)<<elimination_block_size<<endl
1408        <<"weighted variables:   "<<setw(4)<<weighted_block_size<<endl;
1409
1410  output<<"weight_vector:"<<endl;
1411  print_weight_vector(output);
1412
1413  if(elimination_block_size>0)
1414  {
1415    output<<"ordering on elimination variables: ";
1416    switch(elimination_ordering)
1417    {
1418        case LEX:
1419          output<<"LEX\n"<<endl;
1420          break;
1421        case DEG_LEX:
1422          output<<"DEG_LEX\n"<<endl;
1423          break;
1424        case DEG_REV_LEX:
1425          output<<"DEG_REV_LEX\n"<<endl;
1426          break;
1427    }
1428  }
1429
1430  output<<"ordering refining the weight:      ";
1431  switch(weighted_ordering)
1432  {
1433      case W_LEX:
1434        output<<"W_LEX\n"<<endl;
1435        break;
1436      case W_REV_LEX:
1437        output<<"W_REV_LEX\n"<<endl;
1438        break;
1439      case W_DEG_LEX:
1440        output<<"W_DEG_LEX\n"<<endl;
1441        break;
1442      case W_DEG_REV_LEX:
1443        output<<"W_DEG_REV_LEX\n"<<endl;
1444        break;
1445  }
1446}
1447
1448void term_ordering::format_print_weight_vector(ofstream& output) const
1449{
1450  for(short i=0;i<weighted_block_size;i++)
1451    output<<setw(6)<<setprecision(2)<<weight_vector[i];
1452  output<<endl;
1453}
1454#endif  // TERM_ORDERING_CC
Note: See TracBrowser for help on using the repository browser.