source: git/IntegerProgramming/binomial.cc @ 80f8f6c

spielwiese
Last change on this file since 80f8f6c was 88615db, checked in by jgmbenoit <quatermaster@…>, 9 years ago
correct some spelling errors: Correct spelling error as reported by lintian in some binraries; meant to silence lintian.
  • Property mode set to 100644
File size: 42.6 KB
Line 
1// binomial.cc
2
3// implementation of class binomial
4
5#ifndef BINOMIAL_CC
6#define BINOMIAL_CC
7
8#include <climits>
9#include "binomial__term_ordering.h"
10
11///////////////////////// constructors and destructor //////////////////////
12
13// For a better overview, the constructor code is separated for
14// NO_SUPPORT_DRIVEN_METHODS and SUPPORT_DRIVEN_METHODS.
15
16#ifdef NO_SUPPORT_DRIVEN_METHODS
17
18binomial::binomial(const short& number_of_variables)
19    :_number_of_variables(number_of_variables)
20{
21  exponent_vector=new Integer[_number_of_variables];
22}
23
24
25
26
27binomial::binomial(const short& number_of_variables,const Integer* exponents)
28    :_number_of_variables(number_of_variables)
29{
30
31  // range check for rarely used constructors
32  if(_number_of_variables<=0)
33  {
34    cerr<<"\nWARNING: binomial::binomial(const short&, const Integer*):\n"
35      "argument out of range"<<endl;
36    exponent_vector=NULL;
37    // to avoid problems when deleting
38    return;
39  }
40
41  // initialization
42  exponent_vector=new Integer[_number_of_variables];
43  for(short i=0;i<_number_of_variables;i++)
44    exponent_vector[i]=exponents[i];
45}
46
47
48
49
50binomial::binomial(const short& number_of_variables,const Integer* exponents,
51                   const term_ordering& w)
52    :_number_of_variables(number_of_variables)
53{
54
55  // range check for rarely used constructors
56  if(_number_of_variables<=0)
57  {
58    cerr<<"\nWARNING: binomial::binomial(const short&, const Integer*):\n"
59      "argument out of range"<<endl;
60    exponent_vector=NULL;
61    // to avoid problems when deleting
62    return;
63  }
64
65  exponent_vector=new Integer[_number_of_variables];
66
67  // determine head and tail
68  if(w.compare_to_zero(exponents)>=0)
69    for(short i=0;i<_number_of_variables;i++)
70      exponent_vector[i]=exponents[i];
71  else
72    for(short i=0;i<_number_of_variables;i++)
73      exponent_vector[i]=-exponents[i];
74
75}
76
77
78
79
80binomial::binomial(const binomial& b)
81    :_number_of_variables(b._number_of_variables)
82{
83  exponent_vector=new Integer[_number_of_variables];
84  for(short i=0;i<_number_of_variables;i++)
85    exponent_vector[i]=b.exponent_vector[i];
86}
87
88
89
90
91#endif  // NO_SUPPORT_DRIVEN_METHODS
92
93
94
95
96#ifdef SUPPORT_DRIVEN_METHODS
97
98
99
100
101binomial::binomial(const short& number_of_variables)
102    :_number_of_variables(number_of_variables),head_support(0),tail_support(0)
103{
104  exponent_vector=new Integer[_number_of_variables];
105}
106
107
108
109
110binomial::binomial(const short& number_of_variables, const Integer* exponents)
111    :_number_of_variables(number_of_variables),head_support(0),tail_support(0)
112{
113
114  // range check for rarely used constructors
115  if(_number_of_variables<=0)
116  {
117    exponent_vector=NULL;
118    // to avoid problems when deleting
119    cerr<<"\nWARNING: binomial::binomial(const short&, const Integer*):\n"
120      "argument out of range"<<endl;
121    return;
122  }
123
124  exponent_vector=new Integer[_number_of_variables];
125
126  short size_of_support_vectors=CHAR_BIT*sizeof(unsigned long);
127  // number of bits of a long int
128
129
130  for(short i=0;i<_number_of_variables;i++)
131  {
132
133#ifdef SUPPORT_VARIABLES_FIRST
134
135    Integer actual_entry=exponents[i];
136    exponent_vector[i]=actual_entry;
137
138#endif  // SUPPORT_VARIABLES_FIRST
139
140#ifdef SUPPORT_VARIABLES_LAST
141
142    short j=_number_of_variables-1-i;
143    Integer actual_entry=exponents[j];
144    exponent_vector[j]=actual_entry;
145
146#endif  // SUPPORT_VARIABLES_LAST
147
148    if(i<size_of_support_vectors)
149    {
150      // variable i is considered in the support vectors
151      if(actual_entry>0)
152        head_support|=(1<<i);
153        // bit i of head_support is set to 1 (counting from 0)
154      else if(actual_entry<0)
155        tail_support|=(1<<i);
156        // bit i of tail_support is set to 1
157    }
158  }
159
160}
161
162
163
164
165binomial::binomial(const short& number_of_variables, const Integer* exponents,
166                   const term_ordering& w)
167    :_number_of_variables(number_of_variables),head_support(0),tail_support(0)
168{
169  // range check for rarely used constructors
170  if(_number_of_variables<=0)
171  {
172    cerr<<"\nWARNING: binomial::binomial(const short&, const Integer*):\n"
173      "argument out of range"<<endl;
174    exponent_vector=NULL;
175    // to avoid problems when deleting
176    return;
177  }
178
179
180  exponent_vector=new Integer[_number_of_variables];
181
182  short size_of_support_vectors=CHAR_BIT*sizeof(unsigned long);
183  // number of bits of a long int
184
185  // determine head and tail
186  short sign;
187  if(w.compare_to_zero(exponents)>=0)
188    sign=1;
189  else
190    sign=-1;
191
192
193  for(short i=0;i<_number_of_variables;i++)
194  {
195
196#ifdef SUPPORT_VARIABLES_FIRST
197
198    Integer actual_entry=sign*exponents[i];
199    exponent_vector[i]=actual_entry;
200
201#endif  // SUPPORT_VARIABLES_FIRST
202
203#ifdef SUPPORT_VARIABLES_LAST
204
205    short j=_number_of_variables-1-i;
206    Integer actual_entry=sign*exponents[j];
207    exponent_vector[j]=actual_entry;
208
209#endif  // SUPPORT_VARIABLES_LAST
210
211    if(i<size_of_support_vectors)
212    {
213      // variable i is considered in the support vectors
214      if(actual_entry>0)
215        head_support|=(1<<i);
216        // bit i of head_support is set to 1 (counting from 0)
217      else if(actual_entry<0)
218        tail_support|=(1<<i);
219        // bit i of tail_support is set to 1
220    }
221  }
222
223}
224
225
226
227
228binomial::binomial(const binomial& b)
229    :_number_of_variables(b._number_of_variables),
230     head_support(b.head_support),tail_support(b.tail_support)
231{
232  exponent_vector=new Integer[_number_of_variables];
233  for(short i=0;i<_number_of_variables;i++)
234    exponent_vector[i]=b.exponent_vector[i];
235}
236
237
238
239
240#endif  // SUPPORT_DRIVEN_METHODS
241
242
243
244
245binomial::~binomial()
246{
247  delete[] exponent_vector;
248}
249
250
251
252
253/////////////////// object information /////////////////////////////////////
254
255
256
257
258short binomial::number_of_variables() const
259{
260  return _number_of_variables;
261}
262
263
264
265
266short binomial::error_status() const
267{
268  if(_number_of_variables<0)
269    return _number_of_variables;
270  return 0;
271}
272
273
274
275
276//////////////////// assignment and access operators ////////////////////////
277
278
279
280
281binomial& binomial::operator=(const binomial& b)
282{
283
284  if(&b==this)
285    return *this;
286
287
288#ifdef SUPPORT_DRIVEN_METHODS
289
290  head_support=b.head_support;
291  tail_support=b.tail_support;
292
293#endif  // SUPPORT_DRIVEN_METHODS
294
295  if(_number_of_variables!=b._number_of_variables)
296  {
297    delete[] exponent_vector;
298    _number_of_variables=b._number_of_variables;
299
300    if(_number_of_variables<=0)
301    {
302      cerr<<"\nWARNING: binomial& binomial::operator=(const binomial&):\n"
303        "assignment from corrupt binomial"<<endl;
304      exponent_vector=NULL;
305      return (*this);
306    }
307
308    exponent_vector=new Integer[_number_of_variables];
309  }
310
311  for(short i=0;i<_number_of_variables;i++)
312    exponent_vector[i]=b.exponent_vector[i];
313
314  return(*this);
315}
316
317
318
319
320Integer binomial::operator[](const short& i) const
321{
322  return exponent_vector[i];
323}
324
325
326
327
328//////////////////// comparison operators ///////////////////////////////////
329
330
331
332
333BOOLEAN binomial::operator==(const binomial& b) const
334{
335  if(this == &b)
336    return(TRUE);
337
338#ifdef SUPPORT_DRIVEN_METHODS
339
340  if(head_support!=b.head_support)
341    return(FALSE);
342  if(tail_support!=b.tail_support)
343    return(FALSE);
344
345#endif  // SUPPORT_DRIVEN_METHODS
346
347  for(short i=0;i<_number_of_variables;i++)
348    if(exponent_vector[i]!=b.exponent_vector[i])
349      return(FALSE);
350  return(TRUE);
351}
352
353
354
355
356BOOLEAN binomial::operator!=(const binomial& b) const
357{
358  if(this == &b)
359    return(FALSE);
360
361#ifdef SUPPORT_DRIVEN_METHODS
362
363  if(head_support!=b.head_support)
364    return(TRUE);
365  if(tail_support!=b.tail_support)
366    return(TRUE);
367
368#endif  // SUPPORT_DRIVEN_METHODS
369
370  for(short i=0;i<_number_of_variables;i++)
371    if(exponent_vector[i]!=b.exponent_vector[i])
372      return(TRUE);
373  return(FALSE);
374}
375
376
377
378
379// operators for efficient comparisons with the zero binomial (comp_value=0)
380
381BOOLEAN binomial::operator==(const Integer comp_value) const
382{
383
384#ifdef SUPPORT_DRIVEN_METHODS
385
386  if(comp_value==0)
387  {
388    if(head_support!=0)
389      return(FALSE);
390    if(tail_support!=0)
391      return(FALSE);
392  }
393
394#endif  // SUPPORT_DRIVEN_METHODS
395
396  for(short i=0;i<_number_of_variables;i++)
397    if(exponent_vector[i]!=comp_value)
398      return(FALSE);
399  return(TRUE);
400}
401
402
403
404
405BOOLEAN binomial::operator!=(const Integer comp_value) const
406{
407
408#ifdef SUPPORT_DRIVEN_METHODS
409
410  if(comp_value==0)
411  {
412    if(head_support!=0)
413      return(TRUE);
414    if(tail_support!=0)
415      return(TRUE);
416  }
417
418#endif  // SUPPORT_DRIVEN_METHODS
419
420  for(short i=0;i<_number_of_variables;i++)
421    if(exponent_vector[i]!=comp_value)
422      return(TRUE);
423  return(FALSE);
424}
425
426
427
428
429BOOLEAN binomial::operator<=(const Integer comp_value) const
430{
431
432#ifdef SUPPORT_DRIVEN_METHODS
433
434  if(comp_value==0)
435    if(head_support!=0)
436      return(FALSE);
437
438#endif  // SUPPORT_DRIVEN_METHODS
439
440  for(short i=0;i<_number_of_variables;i++)
441    if(exponent_vector[i]>comp_value)
442      return(FALSE);
443  return(TRUE);
444}
445
446
447
448
449BOOLEAN binomial::operator>=(const Integer comp_value) const
450{
451
452#ifdef SUPPORT_DRIVEN_METHODS
453
454  if(comp_value==0)
455    if(tail_support!=0)
456      return(FALSE);
457
458#endif
459
460  for(short i=0;i<_number_of_variables;i++)
461    if(exponent_vector[i]<comp_value)
462      return(FALSE);
463  return(TRUE);
464}
465
466
467
468
469////////////// basic routines for Buchbergers's algorithm //////////////////
470
471
472
473
474Integer binomial::head_reductions_by(const binomial& b) const
475// Returns the number of possible reductions of the actual binomialŽs head
476// by the binomial b. This is the minimum of the quotients
477// exponent_vector[i]/b.exponent_vector[i]
478// where exponent_vector[i]>0 and b.exponent_vector[i]>0
479// (0 if there are no such quotients).
480// A negative return value means b=0 or head(b)=1.
481{
482
483
484#ifdef NO_SUPPORT_DRIVEN_METHODS
485
486  Integer result=-1;
487  Integer new_result=-1;
488  // -1 stands for infinitely many reductions
489
490  for(short i=0;i<_number_of_variables;i++)
491    // explicit sign tests for all components
492  {
493    Integer actual_b_component=b.exponent_vector[i];
494
495    if(actual_b_component>0)
496      // else variable i is not involved in the head of b
497    {
498      Integer actual_component=exponent_vector[i];
499
500      if(actual_component<actual_b_component)
501        return 0;
502
503      new_result=(Integer) (actual_component/actual_b_component);
504
505      // new_result>=1
506      if((new_result<result) || (result==-1))
507        // new (or first) minimum
508        result=new_result;
509    }
510 }
511
512#endif  // NO_SUPPORT_DRIVEN_METHODS
513
514
515#ifdef SUPPORT_DRIVEN_METHODS
516
517  if((head_support&b.head_support)!=b.head_support)
518    // head support of b not contained in head support, no reduction possible
519    return 0;
520
521
522  Integer result=-1;
523  Integer new_result=-1;
524  // -1 stands for infinitely many reductions
525
526
527  short size_of_support_vectors=CHAR_BIT*sizeof(long);
528  // number of bits of a long int
529  if(size_of_support_vectors>_number_of_variables)
530    size_of_support_vectors=_number_of_variables;
531    // number of components of the support vectors
532
533
534#ifdef SUPPORT_VARIABLES_FIRST
535
536  for(short i=0;i<size_of_support_vectors;i++)
537    // test support variables
538
539    if(b.head_support&(1<<i))
540      // bit i of b.head_support is 1
541    {
542      new_result=(Integer) (exponent_vector[i]/b.exponent_vector[i]);
543      // remember that exponent_vector[i]>0 !
544      // (head support contains that of b)
545
546      if(new_result==0)
547        // exponent_vector[i]<b.exponent_vector[i]
548        return 0;
549
550      // new_result>=1
551      if((new_result<result) || (result==-1))
552        // new (or first) minimum
553        result=new_result;
554    }
555
556
557  for(short i=size_of_support_vectors;i<_number_of_variables;i++)
558    // test non-support variables
559    // from now on we need explicit sign tests
560  {
561    Integer actual_b_component=b.exponent_vector[i];
562
563    if(actual_b_component>0)
564      // else variable i is not involved in the head of b
565    {
566      Integer actual_component=exponent_vector[i];
567
568      if(actual_component<actual_b_component)
569        return 0;
570
571      new_result=(Integer) (actual_component/actual_b_component);
572
573      // new_result>=1
574      if((new_result<result) || (result==-1))
575        // new (or first) minimum
576        result=new_result;
577    }
578  }
579
580#endif  // SUPPORT_VARIABLES_FIRST
581
582
583#ifdef SUPPORT_VARIABLES_LAST
584
585  for(short i=0;i<size_of_support_vectors;i++)
586    // test support variables
587
588    if(b.head_support&(1<<i))
589      // bit i of b.head_support is 1
590    {
591      short j=_number_of_variables-1-i;
592      new_result=(Integer) (exponent_vector[j]/ b.exponent_vector[j]);
593      // remember that exponent_vector[_number_of_variables-1-i]>0 !
594      // (head support contains that of b)
595
596      if(new_result==0)
597        // exponent_vector[_number_of_variables-1-i]
598        // <b.exponent_vector[_number_of_variables-1-i]
599        return 0;
600
601      // new_result>=1
602      if((new_result<result) || (result==-1))
603        // new (or first) minimum
604        result=new_result;
605    }
606
607
608  for(short i=size_of_support_vectors;i<_number_of_variables;i++)
609    // test non-support variables
610    // from now on we need explicit sign tests
611  {
612    short j=_number_of_variables-1-i;
613    Integer actual_b_component=b.exponent_vector[j];
614
615    if(actual_b_component>0)
616      // else variable number_of_variables-1-i is not involved in the head of b
617    {
618      Integer actual_component=exponent_vector[j];
619
620      if(actual_component<actual_b_component)
621        return 0;
622
623      new_result=(Integer) (actual_component/actual_b_component);
624
625      // new_result>=1
626      if((new_result<result) || (result==-1))
627        // new (or first) minimum
628        result=new_result;
629    }
630  }
631
632#endif  // SUPPORT_VARIABLES_LAST
633
634
635#endif  // SUPPORT_DRIVEN_METHODS
636
637
638  return(result);
639}
640
641
642
643
644Integer binomial::tail_reductions_by(const binomial& b) const
645// Returns the number of possible reductions of the actual binomialŽs tail
646// by the binomial b. This is the minimum of the quotients
647// - exponent_vector[i]/b.exponent_vector[i]
648// where exponent_vector[i]<0 and b.exponent_vector[i]>0
649// (0 if there are no such quotients).
650// A negative return value means b=0 or head(b)=1.
651{
652
653
654#ifdef NO_SUPPORT_DRIVEN_METHODS
655
656  Integer result=-1;
657  Integer new_result=-1;
658  // -1 stands for infinitely many reductions
659
660  for(short i=0;i<_number_of_variables;i++)
661    // explicit sign tests for all components
662  {
663    Integer actual_b_component=b.exponent_vector[i];
664
665    if(actual_b_component>0)
666      // else variable i is not involved in the head of b
667    {
668      Integer actual_component=-exponent_vector[i];
669
670      if(actual_component<actual_b_component)
671        return 0;
672
673      new_result=(Integer) (actual_component/actual_b_component);
674
675      // new_result>=1
676      if((new_result<result) || (result==-1))
677        // new (or first) minimum
678        result=new_result;
679    }
680 }
681
682#endif  // NO_SUPPORT_DRIVEN_METHODS
683
684
685#ifdef SUPPORT_DRIVEN_METHODS
686
687  if((tail_support&b.head_support)!=b.head_support)
688    // head support of b not contained in tail support, no reduction possible
689    return 0;
690
691
692  Integer result=-1;
693  Integer new_result=-1;
694  // -1 stands for infinitely many reductions
695
696
697  short size_of_support_vectors=CHAR_BIT*sizeof(long);
698  // number of bits of a long int
699  if(size_of_support_vectors>_number_of_variables)
700    size_of_support_vectors=_number_of_variables;
701    // number of components of the support vectors
702
703
704#ifdef SUPPORT_VARIABLES_FIRST
705
706  for(short i=0;i<size_of_support_vectors;i++)
707    // test support variables
708
709    if(b.head_support&(1<<i))
710      // bit i of b.head_support is 1
711    {
712      new_result=(Integer) (-exponent_vector[i]/b.exponent_vector[i]);
713      // remember that exponent_vector[i]<0 !
714      // (tail support contains the head support of b)
715
716      if(new_result==0)
717        // -exponent_vector[i]<b.exponent_vector[i]
718        return 0;
719
720      // new_result>=1
721      if((new_result<result) || (result==-1))
722        // new (or first) minimum
723        result=new_result;
724    }
725
726
727  for(short i=size_of_support_vectors;i<_number_of_variables;i++)
728    // test non-support variables
729    // from now on we need explicit sign tests
730  {
731    Integer actual_b_component=b.exponent_vector[i];
732
733    if(actual_b_component>0)
734      // else variable i is not involved in the head of b
735    {
736      Integer actual_component=-exponent_vector[i];
737
738      if(actual_component<actual_b_component)
739        return 0;
740
741      new_result=(Integer) (actual_component/actual_b_component);
742
743      // new_result>=1
744      if((new_result<result) || (result==-1))
745        // new (or first) minimum
746        result=new_result;
747    }
748  }
749
750#endif  // SUPPORT_VARIABLES_FIRST
751
752
753#ifdef SUPPORT_VARIABLES_LAST
754
755  for(short i=0;i<size_of_support_vectors;i++)
756    // test support variables
757
758    if(b.head_support&(1<<i))
759      // bit i of b.head_support is 1
760    {
761      short j=_number_of_variables-1-i;
762      new_result=(Integer) (-exponent_vector[j] / b.exponent_vector[j]);
763      // remember that exponent_vector[_number_of_variables-1-i]<0 !
764      // (tail support contains the head support of b)
765
766      if(new_result==0)
767        // -exponent_vector[_number_of_variables-1-i]
768        // <b.exponent_vector[_number_of_variables-1-i]
769        return 0;
770
771      // new_result>=1
772      if((new_result<result) || (result==-1))
773        // new (or first) minimum
774        result=new_result;
775    }
776
777
778  for(short i=size_of_support_vectors;i<_number_of_variables;i++)
779    // test non-support variables
780    // from now on we need explicit sign tests
781  {
782    short j=_number_of_variables-1-i;
783    Integer actual_b_component=b.exponent_vector[j];
784
785    if(actual_b_component>0)
786      // else variable number_of_variables-1-i is not involved in the head of b
787    {
788      Integer actual_component=-exponent_vector[j];
789
790      if(actual_component<actual_b_component)
791        return 0;
792
793      new_result=(Integer) (actual_component/actual_b_component);
794
795      // new_result>=1
796      if((new_result<result) || (result==-1))
797        // new (or first) minimum
798        result=new_result;
799    }
800  }
801
802#endif  // SUPPORT_VARIABLES_LAST
803
804
805#endif  // SUPPORT_DRIVEN_METHODS
806
807
808  return(result);
809}
810
811
812
813
814int binomial::reduce_head_by(const binomial& b, const term_ordering& w)
815{
816  Integer reduction_number=head_reductions_by(b);
817  if(reduction_number<=0)
818    return 0;
819
820  for(short i=0;i<_number_of_variables;i++)
821    exponent_vector[i]-=(reduction_number * b.exponent_vector[i]);
822  // multiple reduction
823  // reduction corresponds to subtraction of vectors
824
825  short sign=w.compare_to_zero(exponent_vector);
826
827
828#ifdef NO_SUPPORT_DRIVEN_METHODS
829
830  if(sign==0)
831    // binomial reduced to zero
832    return 2;
833
834  for(short i=0;i<_number_of_variables;i++)
835    exponent_vector[i]*=sign;
836
837#endif  // NO_SUPPORT_DRIVEN_METHODS
838
839
840#ifdef SUPPORT_DRIVEN_METHODS
841
842  head_support=0;
843  tail_support=0;
844
845  if(sign==0)
846    // binomial reduced to zero
847    return 2;
848
849  short size_of_support_vectors=CHAR_BIT*sizeof(unsigned long);
850
851
852  // recompute the support vectors
853
854#ifdef SUPPORT_VARIABLES_FIRST
855
856  for(short i=0;i<_number_of_variables;i++)
857  {
858
859    Integer& actual_entry=exponent_vector[i];
860    // to avoid unnecessary pointer arithmetic
861
862    actual_entry*=sign;
863
864    if(i<size_of_support_vectors)
865      if(actual_entry>0)
866        head_support|=(1<<i);
867      else
868        if(actual_entry<0)
869          tail_support|=(1<<i);
870  }
871
872#endif  // SUPPORT_VARIABLES_FIRST
873
874
875#ifdef SUPPORT_VARIABLES_LAST
876
877  for(short i=0;i<_number_of_variables;i++)
878  {
879    Integer& actual_entry=exponent_vector[_number_of_variables-1-i];
880    // to avoid unneccessary pointer arithmetic
881
882    actual_entry*=sign;
883
884    if(i<size_of_support_vectors)
885    {
886      if(actual_entry>0)
887        head_support|=(1<<i);
888      else if(actual_entry<0)
889        tail_support|=(1<<i);
890    }
891  }
892
893#endif  // SUPPORT_VARIABLES_LAST
894
895
896#endif  // SUPPORT_DRIVEN_METHODS
897
898  return 1;
899}
900
901
902
903
904int binomial::reduce_tail_by(const binomial& b, const term_ordering& w)
905{
906  Integer reduction_number=tail_reductions_by(b);
907  if(reduction_number<=0)
908    return 0;
909
910  for(short i=0;i<_number_of_variables;i++)
911    exponent_vector[i]+=(reduction_number * b.exponent_vector[i]);
912  // multiple reduction
913  // reduction corresponds to addition of vectors
914
915  // a tail reduction does not require a sign check
916
917
918#ifdef SUPPORT_DRIVEN_METHODS
919
920  head_support=0;
921  tail_support=0;
922
923  short size_of_support_vectors=CHAR_BIT*sizeof(unsigned long);
924
925
926  // recompute the support vectors
927
928#ifdef SUPPORT_VARIABLES_FIRST
929
930  for(short i=0;i<_number_of_variables;i++)
931  {
932
933    Integer& actual_entry=exponent_vector[i];
934    // to avoid unnecessary pointer arithmetic
935
936    if(i<size_of_support_vectors)
937    {
938      if(actual_entry>0)
939        head_support|=(1<<i);
940      else if(actual_entry<0)
941        tail_support|=(1<<i);
942    }
943  }
944
945#endif  // SUPPORT_VARIABLES_FIRST
946
947
948#ifdef SUPPORT_VARIABLES_LAST
949
950  for(short i=0;i<_number_of_variables;i++)
951  {
952    Integer& actual_entry=exponent_vector[_number_of_variables-1-i];
953    // to avoid unneccessary pointer arithmetic
954
955    if(i<size_of_support_vectors)
956    {
957      if(actual_entry>0)
958        head_support|=(1<<i);
959      else if(actual_entry<0)
960        tail_support|=(1<<i);
961    }
962  }
963
964#endif  // SUPPORT_VARIABLES_LAST
965
966
967#endif  // SUPPORT_DRIVEN_METHODS
968
969  return 1;
970}
971
972
973
974
975binomial& S_binomial(const binomial& a, const binomial& b,
976                     const term_ordering& w)
977{
978  binomial* S_bin=new binomial(a._number_of_variables);
979  binomial& result=*S_bin;
980  // Note that we allocate memory for the result binomial. We often use
981  // pointers or references as argument and return types because the
982  // generating binomials of an ideal are kept in lists. For the performance
983  // of Buchberger's algorithm it it very important to avoid local copies
984  // of binomials, so a lot of attention is paid on the choice of argument
985  // and return types. As this choice is done in order to improve performance,
986  // it might be a bad choice with respect to code reuse (there are some
987  // dangerous constructions).
988
989  for(short i=0;i<result._number_of_variables;i++)
990    result.exponent_vector[i]=a.exponent_vector[i]-b.exponent_vector[i];
991  // The S-binomial corresponds to the vector difference.
992
993  // compute head and tail
994  short sign=w.compare_to_zero(result.exponent_vector);
995
996
997#ifdef NO_SUPPORT_DRIVEN_METHODS
998
999  if(sign==0)
1000    // binomial reduced to zero
1001    return result;
1002
1003  for(short i=0;i<result._number_of_variables;i++)
1004    result.exponent_vector[i]*=sign;
1005
1006#endif  // NO_SUPPORT_DRIVEN_METHODS
1007
1008
1009#ifdef SUPPORT_DRIVEN_METHODS
1010
1011  result.head_support=0;
1012  result.tail_support=0;
1013
1014  if(sign==0)
1015    // binomial reduced to zero
1016    return result;
1017
1018  short size_of_support_vectors=CHAR_BIT*sizeof(unsigned long);
1019
1020
1021  // recompute the support vectors
1022
1023#ifdef SUPPORT_VARIABLES_FIRST
1024
1025  for(short i=0;i<result._number_of_variables;i++)
1026  {
1027
1028    Integer& actual_entry=result.exponent_vector[i];
1029    // to avoid unnecessary pointer arithmetic
1030
1031    actual_entry*=sign;
1032
1033    if(i<size_of_support_vectors)
1034    {
1035      if(actual_entry>0)
1036        result.head_support|=(1<<i);
1037      else if(actual_entry<0)
1038        result.tail_support|=(1<<i);
1039    }
1040  }
1041
1042#endif  // SUPPORT_VARIABLES_FIRST
1043
1044
1045#ifdef SUPPORT_VARIABLES_LAST
1046
1047  for(short i=0;i<result._number_of_variables;i++)
1048  {
1049    Integer& actual_entry=result.exponent_vector
1050      [result._number_of_variables-1-i];
1051    // to avoid unneccessary pointer arithmetic
1052
1053    actual_entry*=sign;
1054
1055    if(i<size_of_support_vectors)
1056    {
1057      if(actual_entry>0)
1058        result.head_support|=(1<<i);
1059      else if(actual_entry<0)
1060          result.tail_support|=(1<<i);
1061    }
1062  }
1063
1064#endif  // SUPPORT_VARIABLES_LAST
1065
1066
1067#endif  // SUPPORT_DRIVEN_METHODS
1068
1069
1070  return result;
1071}
1072
1073
1074
1075
1076///////////// criteria for unnecessary S-pairs ///////////////////////////////
1077
1078// The criteria are programmed in a way that tries to minimize pointer
1079// arithmetic. Therefore the code may appear a little bit inflated.
1080
1081
1082
1083
1084BOOLEAN relatively_prime(const binomial& a, const binomial& b)
1085{
1086
1087#ifdef NO_SUPPORT_DRIVEN_METHODS
1088
1089  // look at all variables
1090  for(short i=0;i<a._number_of_variables;i++)
1091    if((a.exponent_vector[i]>0) && (b.exponent_vector[i]>0))
1092      return FALSE;
1093
1094  return TRUE;
1095
1096#endif  // NO_SUPPORT_DRIVEN_METHODS
1097
1098
1099#ifdef SUPPORT_DRIVEN_METHODS
1100
1101  if((a.head_support & b.head_support)!=0)
1102  // common support variable in the heads
1103    return FALSE;
1104
1105  // no common support variable in the heads, look at remaining variables
1106  short size_of_support_vectors=CHAR_BIT*sizeof(unsigned long);
1107
1108
1109#ifdef SUPPORT_VARIABLES_FIRST
1110
1111  for(short i=size_of_support_vectors;i<a._number_of_variables;i++)
1112    if((a.exponent_vector[i]>0) && (b.exponent_vector[i]>0))
1113      return FALSE;
1114
1115  return TRUE;
1116
1117#endif  // SUPPORT_VARIABLES_FIRST
1118
1119
1120#ifdef SUPPORT_VARIABLES_LAST
1121
1122  for(short i=a._number_of_variables-1-size_of_support_vectors;i>=0;i--)
1123    if((a.exponent_vector[i]>0) && (b.exponent_vector[i]>0))
1124      return FALSE;
1125
1126  return TRUE;
1127
1128#endif  // SUPPORT_VARIABLES_LAST
1129
1130
1131#endif  // SUPPORT_DRIVEN_METHODS
1132
1133}
1134
1135
1136
1137
1138BOOLEAN M(const binomial& a, const binomial& b, const binomial& c)
1139// Returns TRUE iff lcm(head(a),head(c)) divides properly lcm(head(b),head(c)).
1140// This is checked by comparing the positive components of the exponent
1141// vectors.
1142{
1143
1144
1145#ifdef SUPPORT_DRIVEN_METHODS
1146
1147  long b_or_c=b.head_support|c.head_support;
1148
1149  if((a.head_support|b_or_c) != b_or_c)
1150    return FALSE;
1151  // The support of lcm(head(a),head(c)) equals the union of the head supports
1152  // of a and c. The above condition verifies if the support of
1153  // lcm(head(a),head(c)) is contained in the support of lcm(head(b),head(c))
1154  // by checking if head a involves a variable that is not involved in
1155  // head(b) or head(c).
1156
1157#endif  // SUPPORT_DRIVEN_METHODS
1158
1159
1160  BOOLEAN properly=FALSE;
1161
1162  for(short i=0;i<a._number_of_variables;i++)
1163  {
1164    Integer a_exponent=a.exponent_vector[i];
1165    Integer b_exponent=b.exponent_vector[i];
1166    Integer c_exponent=c.exponent_vector[i];
1167    Integer m1=MAXIMUM(a_exponent,c_exponent);
1168    Integer m2=MAXIMUM(b_exponent,c_exponent);
1169
1170    if(m1>0)
1171    {
1172      if(m1>m2)
1173        return FALSE;
1174      if(m1<m2)
1175        properly=TRUE;
1176    }
1177  }
1178
1179  return properly;
1180}
1181
1182
1183
1184
1185BOOLEAN F(const binomial& a, const binomial& b, const binomial& c)
1186// verifies if lcm(head(a),head(c))=lcm(head(b),head(c))
1187{
1188
1189#ifdef SUPPORT_DRIVEN_METHODS
1190
1191  if((a.head_support|c.head_support)!=(b.head_support|c.head_support))
1192    return FALSE;
1193  // The above condition verifies if the support of lcm(head(a),head(c))
1194  // equals the support of lcm(head(b),head(c)).
1195
1196#endif  // SUPPORT_DRIVEN_METHODS
1197
1198  for(short i=0;i<a._number_of_variables;i++)
1199  {
1200    Integer a_exponent=a.exponent_vector[i];
1201    Integer b_exponent=b.exponent_vector[i];
1202    Integer c_exponent=c.exponent_vector[i];
1203    Integer m1=MAXIMUM(a_exponent,c_exponent);
1204    Integer m2=MAXIMUM(b_exponent,c_exponent);
1205
1206    if((m1!=m2) && (m1>0 || m2>0))
1207      return FALSE;
1208  }
1209
1210  return TRUE;
1211}
1212
1213
1214
1215
1216BOOLEAN B(const binomial& a, const binomial& b, const binomial& c)
1217// verifies if head(a) divides lcm(head(b),head(c)) and
1218// lcm(head(a),head(b))!=lcm(head(b),head(c))!=lcm(head(a),head(c))
1219{
1220
1221#ifdef SUPPORT_DRIVEN_METHODS
1222
1223  long a_or_b=a.head_support|b.head_support;
1224  long a_or_c=a.head_support|c.head_support;
1225  long b_or_c=b.head_support|c.head_support;
1226
1227  if((a.head_support & b_or_c)!=a.head_support)
1228    return FALSE;
1229  // The above condition verifies if the support of head(a) is contained in
1230  // the support of lcm(head(b),head(c)).
1231
1232  if( (a_or_c != b_or_c) && (a_or_b != b_or_c))
1233    // Then the inequality conditions are guaranteed...
1234  {
1235    for(short i=0;i<a._number_of_variables;i++)
1236    {
1237      Integer b_exponent=b.exponent_vector[i];
1238      Integer c_exponent=c.exponent_vector[i];
1239
1240      if(a.exponent_vector[i]>MAXIMUM(b_exponent,c_exponent))
1241        return FALSE;
1242    }
1243
1244    return (TRUE);
1245  }
1246
1247
1248  if(a_or_b != b_or_c)
1249    // Then the first inequality conditions is guaranteed...
1250    // Verifie only the second.
1251  {
1252    BOOLEAN not_equal=FALSE;
1253
1254    for(short i=0;i<a._number_of_variables;i++)
1255    {
1256      Integer a_exponent=a.exponent_vector[i];
1257      Integer b_exponent=b.exponent_vector[i];
1258      Integer c_exponent=c.exponent_vector[i];
1259      Integer m=MAXIMUM(b_exponent, c_exponent);
1260
1261      if(a_exponent>m)
1262        return FALSE;
1263
1264      if(MAXIMUM(a_exponent,c_exponent) != m)
1265         not_equal=TRUE;
1266    }
1267    return(not_equal);
1268  }
1269
1270
1271  if( a_or_c != b_or_c )
1272    // Then the second inequality conditions is guaranteed...
1273    // Verifie only the first.
1274  {
1275    BOOLEAN not_equal=FALSE;
1276
1277    for(short i=0;i<a._number_of_variables;i++)
1278    {
1279      Integer a_exponent=a.exponent_vector[i];
1280      Integer b_exponent=b.exponent_vector[i];
1281      Integer c_exponent=c.exponent_vector[i];
1282      Integer m=MAXIMUM(b_exponent, c_exponent);
1283
1284      if(a_exponent > m)
1285        return FALSE;
1286
1287      if(MAXIMUM(a_exponent,b_exponent) != m)
1288        not_equal=TRUE;
1289    }
1290    return(not_equal);
1291  }
1292
1293#endif  // SUPPORT_DRIVEN_METHODS
1294
1295
1296  BOOLEAN not_equal_1=FALSE;
1297  BOOLEAN not_equal_2=FALSE;
1298
1299  for(short i=0;i<a._number_of_variables;i++)
1300  {
1301    Integer a_exponent=a.exponent_vector[i];
1302    Integer b_exponent=b.exponent_vector[i];
1303    Integer c_exponent=c.exponent_vector[i];
1304    Integer m=MAXIMUM(b_exponent, c_exponent);
1305
1306    if(a_exponent > m)
1307      return FALSE;
1308
1309    if(MAXIMUM(a_exponent,b_exponent) != m)
1310      not_equal_1=TRUE;
1311    if(MAXIMUM(a_exponent,c_exponent) != m)
1312      not_equal_2=TRUE;
1313  }
1314
1315  return (not_equal_1 && not_equal_2);
1316
1317}
1318
1319
1320
1321
1322BOOLEAN second_crit(const binomial& a, const binomial& b,
1323                    const binomial& c)
1324// verifies if head(a) divides lcm(head(b),head(c))
1325{
1326
1327#ifdef SUPPORT_DRIVEN_METHODS
1328
1329  if((a.head_support & (b.head_support|c.head_support))!=a.head_support)
1330    return FALSE;
1331  // The above condition verifies if the support of head(a) is contained in
1332  // the support of lcm(head(b),head(c))
1333
1334#endif  // SUPPORT_DRIVEN_METHODS.
1335
1336  for(short i=0;i<a._number_of_variables;i++)
1337  {
1338    Integer b_exponent=b.exponent_vector[i];
1339    Integer c_exponent=c.exponent_vector[i];
1340
1341    if(a.exponent_vector[i]>MAXIMUM(b_exponent,c_exponent))
1342      return FALSE;
1343  }
1344
1345  return (TRUE);
1346}
1347
1348
1349
1350
1351//////// special routines needed by the IP-algorithms ///////////////////////
1352
1353
1354
1355
1356BOOLEAN binomial::involves_elimination_variables(const term_ordering& w)
1357{
1358// The use of support information would require the distinction of various
1359// cases here (relation between the number of variables to eliminate
1360// and the number of support variables) and be quite difficult.
1361// It is doubtful if this would improve performance.
1362// As this function is not used in BuchbergerŽs algorithm (and therefore
1363// rather rarely), I renounce to implement this.
1364
1365  for(short i=0;i<w.number_of_elimination_variables();i++)
1366    // elimination variables are always the last ones
1367    if(exponent_vector[_number_of_variables-1-i]!=0)
1368      return TRUE;
1369
1370  return FALSE;
1371}
1372
1373
1374
1375
1376BOOLEAN binomial::drop_elimination_variables(const term_ordering& w)
1377{
1378  _number_of_variables-=w.number_of_elimination_variables();
1379  // dangerous (no compatibility check)!!
1380
1381  // copy components of interest to save memory
1382  // the leading term has to be recomputed!!
1383
1384  Integer *aux=exponent_vector;
1385  exponent_vector=new Integer[_number_of_variables];
1386
1387  if(w.weight(aux)>=0)
1388    for(short i=0;i<_number_of_variables;i++)
1389      exponent_vector[i]=aux[i];
1390  else
1391    for(short i=0;i<_number_of_variables;i++)
1392      exponent_vector[i]=-aux[i];
1393
1394  delete[] aux;
1395
1396
1397#ifdef SUPPORT_DRIVEN_METHODS
1398
1399  // Recompute head and tail.
1400  // Normally, this routine is only called for binomials that do not involve
1401  // the variables to eliminate. But if SUPPORT_VARIABLES_LAST is enabled,
1402  // the support changes in spite of this. Therefore, the support is
1403  // recomputed... For the same reasons as mentionned in the preceeding
1404  // routine, the existing support information is not used.
1405
1406  head_support=0;
1407  tail_support=0;
1408  short size_of_support_vectors=CHAR_BIT*sizeof(unsigned long);
1409  if(size_of_support_vectors>_number_of_variables)
1410    size_of_support_vectors=_number_of_variables;
1411
1412
1413#ifdef SUPPORT_VARIABLES_FIRST
1414
1415  for(short i=0;i<size_of_support_vectors;i++)
1416  {
1417    Integer actual_entry=exponent_vector[i];
1418    if(actual_entry>0)
1419      head_support|=(1<<i);
1420    else if(actual_entry[i]<0)
1421      tail_support|=(1<<i);
1422  }
1423
1424#endif  // SUPPORT_VARIABLES_FIRST
1425
1426
1427#ifdef SUPPORT_VARIABLES_LAST
1428
1429  for(short i=0;i<size_of_support_vectors;i++)
1430  {
1431    Integer actual_entry=exponent_vector[_number_of_variables-1-i];
1432    if(actual_entry>0)
1433      head_support|=(1<<i);
1434    else if(actual_entry<0)
1435      tail_support|=(1<<i);
1436  }
1437
1438#endif  // SUPPORT_VARIABLES_LAST
1439
1440
1441#endif  // SUPPORT_DRIVEN_METHODS
1442  return TRUE;
1443
1444}
1445
1446
1447
1448
1449BOOLEAN binomial::drop_last_weighted_variable(const term_ordering& w)
1450{
1451  _number_of_variables--;
1452  // dangerous!!
1453
1454  // copy components of interest to save memory
1455  // the leading term has to be recomputed!!
1456
1457  Integer *aux=exponent_vector;
1458  exponent_vector=new Integer[_number_of_variables];
1459
1460  short last_weighted_variable=w.number_of_weighted_variables()-1;
1461  aux[last_weighted_variable]=0;
1462  // set last component to zero, so it cannot influence the weight
1463
1464  if(w.weight(aux)>=0)
1465  {
1466    for(short i=0;i<last_weighted_variable;i++)
1467      exponent_vector[i]=aux[i];
1468    for(short i=last_weighted_variable;i<_number_of_variables;i++)
1469      exponent_vector[i]=aux[i+1];
1470  }
1471  else
1472  {
1473    for(short i=0;i<last_weighted_variable;i++)
1474      exponent_vector[i]=-aux[i];
1475     for(short i=last_weighted_variable;i<_number_of_variables;i++)
1476      exponent_vector[i]=-aux[i+1];
1477  }
1478
1479  delete[] aux;
1480
1481
1482#ifdef SUPPORT_DRIVEN_METHODS
1483
1484  // Recompute head and tail.
1485  // Normally, this routine is only called for binomials that do not involve
1486  // the variable to be dropped. But if SUPPORT_VARIABLES_LAST is enabled,
1487  // the support changes in spite of this. Therefore, the support is
1488  // recomputed... For the same reasons as mentionned in the preceeding
1489  // routines, the existing support information is not used.
1490
1491  head_support=0;
1492  tail_support=0;
1493  short size_of_support_vectors=CHAR_BIT*sizeof(unsigned long);
1494  if(size_of_support_vectors>_number_of_variables)
1495    size_of_support_vectors=_number_of_variables;
1496
1497
1498#ifdef SUPPORT_VARIABLES_FIRST
1499
1500  for(short i=0;i<size_of_support_vectors;i++)
1501  {
1502    Integer actual_entry=exponent_vector[i];
1503    if(actual_entry>0)
1504      head_support|=(1<<i);
1505    else if(actual_entry<0)
1506      tail_support|=(1<<i);
1507  }
1508
1509#endif  // SUPPORT_VARIABLES_FIRST
1510
1511
1512#ifdef SUPPORT_VARIABLES_LAST
1513
1514  for(short i=0;i<size_of_support_vectors;i++)
1515  {
1516    Integer actual_entry=exponent_vector[_number_of_variables-1-i];
1517    if(actual_entry>0)
1518      head_support|=(1<<i);
1519    else if(actual_entry<0)
1520      tail_support|=(1<<i);
1521  }
1522
1523#endif  // SUPPORT_VARIABLES_LAST
1524
1525#endif  // SUPPORT_DRIVEN_METHODS
1526  return TRUE;
1527}
1528
1529
1530
1531
1532int binomial::adapt_to_term_ordering(const term_ordering& w)
1533{
1534
1535  if(w.compare_to_zero(exponent_vector)<0)
1536  {
1537    // then exchange head and tail
1538    for(short i=0;i<_number_of_variables;i++)
1539      exponent_vector[i]*=(-1);
1540
1541
1542#ifdef SUPPORT_DRIVEN_METHODS
1543
1544    unsigned long swap=head_support;
1545    head_support=tail_support;
1546    tail_support=swap;
1547
1548#endif
1549
1550
1551    return -1;
1552    // binomial changed
1553  }
1554
1555  else
1556    return 1;
1557    // binomial unchanged
1558}
1559
1560
1561
1562
1563binomial& binomial::swap_variables(const short& i, const short& j)
1564{
1565
1566
1567#ifdef SUPPORT_DRIVEN_METHODS
1568
1569  // First adjust head_support and tail_support.
1570
1571  short size_of_support_vectors=CHAR_BIT*sizeof(unsigned long);
1572  if(size_of_support_vectors>_number_of_variables)
1573    size_of_support_vectors=_number_of_variables;
1574
1575
1576#ifdef SUPPORT_VARIABLES_FIRST
1577
1578  if(i<size_of_support_vectors)
1579    // else i is no support variable
1580  {
1581    if(exponent_vector[j]>0)
1582    // bit i will be 1 in the new head_support, 0 in the new tail_support
1583    {
1584      head_support|=(1<<i);
1585      // bit i is set to 1
1586
1587      tail_support&=~(1<<i);
1588      // bit i is set to 0
1589      // (in the complement ~(1<<i) all bits are 1 except from bit i)
1590    }
1591
1592    if(exponent_vector[j]==0)
1593    // bit i will be 0 in the new head_support, 0 in the new tail_support
1594    {
1595      head_support&=~(1<<i);
1596      // bit i is set to 0
1597
1598      tail_support&=~(1<<i);
1599      // bit i is set to 0
1600    }
1601
1602    if(exponent_vector[j]<0)
1603    // bit i will be 0 in the new head_support, 1 in the new tail_support
1604    {
1605      head_support&=~(1<<i);
1606      // bit i is set to 0
1607
1608      tail_support|=(1<<i);
1609      // bit i is set to 1
1610    }
1611  }
1612
1613
1614  if(j<size_of_support_vectors)
1615    // else j is no support variable
1616  {
1617    if(exponent_vector[i]>0)
1618    // bit j will be 1 in the new head_support, 0 in the new tail_support
1619    {
1620      head_support|=(1<<j);
1621      // bit j is set to 1
1622
1623      tail_support&=~(1<<j);
1624      // bit j is set to 0
1625      // (in the complement ~(1<<j) all bits are 1 except from bit j)
1626    }
1627
1628    if(exponent_vector[i]==0)
1629    // bit j will be 0 in the new head_support, 0 in the new tail_support
1630    {
1631      head_support&=~(1<<j);
1632      // bit j is set to 0
1633
1634      tail_support&=~(1<<j);
1635      // bit j is set to 0
1636    }
1637
1638    if(exponent_vector[i]<0)
1639    // bit j will be 0 in the new head_support, 1 in the new tail_support
1640    {
1641      head_support&=~(1<<j);
1642      // bit j is set to 0
1643
1644      tail_support|=(1<<j);
1645      // bit j is set to 1
1646    }
1647  }
1648
1649#endif  // SUPPORT_VARIABLES_FIRST
1650
1651
1652#ifdef SUPPORT_VARIABLES_LAST
1653
1654  // Using SUPPORT_VARIABLES_LAST, bit k of the support vectors
1655  // corresponds to exponent_vector[_number_of_variables-1-k],
1656  // hence bit _number_of_variables-1-i to exponent_vector[i].
1657
1658  if(i>=_number_of_variables-size_of_support_vectors)
1659    // else i is no support variable
1660  {
1661    if(exponent_vector[j]>0)
1662    // bit _number_of_variables-1-i will be 1 in the new head_support,
1663    // 0 in the new tail_support
1664    {
1665      short k=_number_of_variables-1-i;
1666
1667      head_support|=(1<<k);
1668      // bit _number_of_variables-1-i is set to 1
1669
1670      tail_support&=~(1<<k);
1671      // bit _number_of_variables-1-i is set to 0
1672      // (in the complement ~(1<<(_number_of_variables-1-i)) all bits are 1
1673      // except from bit _number_of_variables-1-i)
1674    }
1675
1676    if(exponent_vector[j]==0)
1677    // bit _number_of_variables-1-i will be 0 in the new head_support,
1678    // 0 in the new tail_support
1679    {
1680      short k=_number_of_variables-1-i;
1681
1682      head_support&=~(1<<k);
1683      // bit _number_of_variables-1-i is set to 0
1684
1685      tail_support&=~(1<<k);
1686      // bit _number_of_variables-1-i is set to 0
1687    }
1688
1689    if(exponent_vector[j]<0)
1690    // bit _number_of_variables-1-i will be 0 in the new head_support,
1691     // 1 in the new tail_support
1692    {
1693      short k=_number_of_variables-1-i;
1694
1695      head_support&=~(1<<k);
1696      // bit _number_of_variables-1-i is set to 0
1697
1698      tail_support|=(1<<k);
1699      // bit _number_of_variables-1-i is set to 1
1700    }
1701  }
1702
1703
1704  if(j>=_number_of_variables-size_of_support_vectors)
1705      // else j is no support variable
1706  {
1707   if(exponent_vector[i]>0)
1708    // bit _number_of_variables-1-j will be 1 in the new head_support,
1709    // 0 in the new tail_support
1710    {
1711      short k=_number_of_variables-1-j;
1712
1713      head_support|=(1<<k);
1714      // bit _number_of_variables-1-j is set to 1
1715
1716      tail_support&=~(1<<k);
1717      // bit _number_of_variables-1-j is set to 0
1718      // (in the complement ~(1<<(_number_of_variables-1-j)) all bits are 1
1719      // except from bit _number_of_variables-1-j)
1720    }
1721
1722    if(exponent_vector[i]==0)
1723    // bit _number_of_variables-1-j will be 0 in the new head_support,
1724    // 0 in the new tail_support
1725    {
1726      short k=_number_of_variables-1-j;
1727
1728      head_support&=~(1<<k);
1729      // bit _number_of_variables-1-j is set to 0
1730
1731      tail_support&=~(1<<k);
1732      // bit _number_of_variables-1-j is set to 0
1733    }
1734
1735    if(exponent_vector[i]<0)
1736    // bit _number_of_variables-1-j will be 0 in the new head_support,
1737     // 1 in the new tail_support
1738    {
1739      short k=_number_of_variables-1-j;
1740
1741      head_support&=~(1<<k);
1742      // bit _number_of_variables-1-j is set to 0
1743
1744      tail_support|=(1<<k);
1745      // bit _number_of_variables-1-j is set to 1
1746    }
1747  }
1748
1749#endif  // SUPPORT_VARIABLES_LAST
1750
1751#endif  // SUPPORT_DRIVEN_METHODS
1752
1753
1754// Now swap the components.
1755
1756  Integer swap=exponent_vector[j];
1757  exponent_vector[j]=exponent_vector[i];
1758  exponent_vector[i]=swap;
1759
1760  return *this;
1761
1762}
1763
1764binomial& binomial::flip_variable(const short& i)
1765{
1766
1767  if(exponent_vector[i]==0)
1768    // binomial does not involve variable to flip
1769    return *this;
1770
1771
1772#ifdef SUPPORT_DRIVEN_METHODS
1773
1774// First adjust head_support and tail_support.
1775
1776  short size_of_support_vectors=CHAR_BIT*sizeof(unsigned long);
1777  if(size_of_support_vectors>_number_of_variables)
1778    size_of_support_vectors=_number_of_variables;
1779
1780
1781#ifdef SUPPORT_VARIABLES_FIRST
1782
1783  if(i<size_of_support_vectors)
1784    // else i is no support variable
1785  {
1786    if(exponent_vector[i]>0)
1787      // variable i will be moved from head to tail
1788    {
1789      head_support&=~(1<<i);
1790      // bit i is set to 0
1791
1792      tail_support|=(1<<i);
1793      // bit i is set to 1
1794    }
1795
1796    else
1797      // variable i will be moved from tail to head
1798      // remember that exponent_vector[i]!=0
1799    {
1800      tail_support&=~(1<<i);
1801      // bit i is set to 0
1802
1803      head_support|=(1<<i);
1804      // bit i is set to 1
1805    }
1806  }
1807#endif  // SUPPORT_VARIABLES_FIRST
1808
1809#ifdef SUPPORT_VARIABLES_LAST
1810
1811  // Using SUPPORT_VARIABLES_LAST, bit k of the support vectors
1812  // corresponds to exponent_vector[_number_of_variables-1-k],
1813  // hence bit _number_of_variables-1-i to exponent_vector[i].
1814
1815  if(i>=_number_of_variables-size_of_support_vectors)
1816    // else i is no support variable
1817  {
1818    if(exponent_vector[i]>0)
1819    // variable i will be moved from head to tail
1820    {
1821      short k=_number_of_variables-1-i;
1822
1823      head_support&=~(1<<k);
1824      // bit _number_of_variables-1-i is set to 0
1825
1826      tail_support|=(1<<k);
1827      // bit _number_of_variables-1-i is set to 1
1828
1829     }
1830
1831    else
1832    // variable i will be moved from tail to head
1833    {
1834      short k=_number_of_variables-1-i;
1835
1836      tail_support&=~(1<<k);
1837      // bit _number_of_variables-1-i is set to 0
1838
1839      head_support|=(1<<k);
1840      // bit _number_of_variables-1-i is set to 1
1841
1842    }
1843  }
1844#endif  // SUPPORT_VARIABLES_LAST
1845
1846
1847#endif  // SUPPORT_DRIVEN_METHODS
1848
1849  // Now flip the variable.
1850
1851  exponent_vector[i]*=-1;
1852  return *this;
1853}
1854
1855////////////////////////// output /////////////////////////////////////////
1856
1857void binomial::print() const
1858{
1859  printf("(");
1860  for(short i=0;i<_number_of_variables-1;i++)
1861    printf("%6d,",exponent_vector[i]);
1862  printf("%6d)\n",exponent_vector[_number_of_variables-1]);
1863}
1864
1865void binomial::print_all() const
1866{
1867  print();
1868
1869#ifdef SUPPORT_DRIVEN_METHODS
1870
1871  printf("head: %ld, tail %ld\n",head_support,tail_support);
1872
1873#endif  // SUPPORT_DRIVEN_METHODS
1874}
1875
1876void binomial::print(FILE* output) const
1877{
1878  fprintf(output,"(");
1879  for(short i=0;i<_number_of_variables-1;i++)
1880    fprintf(output,"%6d,",exponent_vector[i]);
1881  fprintf(output,"%6d)\n",exponent_vector[_number_of_variables-1]);
1882}
1883
1884void binomial::print_all(FILE* output) const
1885{
1886  print(output);
1887
1888#ifdef SUPPORT_DRIVEN_METHODS
1889
1890  fprintf(output,"head: %ld, tail %ld\n",head_support,tail_support);
1891
1892#endif  // SUPPORT_DRIVEN_METHODS
1893}
1894
1895void binomial::print(ofstream& output) const
1896{
1897  output<<"(";
1898  for(short i=0;i<_number_of_variables-1;i++)
1899    output<<setw(6)<<exponent_vector[i]<<",";
1900  output<<setw(6)<<exponent_vector[_number_of_variables-1]<<")"<<endl;
1901}
1902
1903void binomial::print_all(ofstream& output) const
1904{
1905  print(output);
1906
1907#ifdef SUPPORT_DRIVEN_METHODS
1908
1909  output<<"head: "<<setw(16)<<head_support<<", tail: "<<setw(16)
1910        <<tail_support<<endl;
1911
1912#endif  // SUPPORT_DRIVEN_METHODS
1913}
1914
1915void binomial::format_print(ofstream& output) const
1916{
1917  for(short i=0;i<_number_of_variables;i++)
1918    output<<setw(6)<<exponent_vector[i];
1919  output<<endl;
1920}
1921
1922#endif  // BINOMIAL_CC
Note: See TracBrowser for help on using the repository browser.