001 /*
002 * $Id: TermOrder.java 3748 2011-08-21 13:53:26Z kredel $
003 */
004
005 package edu.jas.poly;
006
007
008 import java.io.Serializable;
009 import java.util.Arrays;
010 import java.util.Comparator;
011
012 import org.apache.log4j.Logger;
013
014
015 /**
016 * Term order class for ordered polynomials. Implements the most used term
017 * orders: graded, lexicographical, weight aray and block orders. For the
018 * definitions see for example the articles <a
019 * href="http://doi.acm.org/10.1145/43882.43887">Kredel,
020 * "Admissible term orderings used in computer algebra systems"</a> and <a
021 * href="http://doi.acm.org/10.1145/70936.70941">Sit,
022 * "Some comments on term-ordering in Gröbner basis computations"</a>.
023 * <b>Note: </b> the naming is not quite easy to understand: in case of doubt
024 * use the term orders with "I" in the name, like IGRLEX (the default) or
025 * INVLEX. Not all algorithms may work with all term orders, so watch your step.
026 * This class does not jet implement orders by linear forms over Q[t]. Objects
027 * of this class are immutable.
028 *
029 * @author Heinz Kredel
030 */
031
032 public final class TermOrder implements Serializable {
033
034
035 public static final int LEX = 1;
036
037
038 public static final int INVLEX = 2;
039
040
041 public static final int GRLEX = 3;
042
043
044 public static final int IGRLEX = 4;
045
046
047 public static final int REVLEX = 5;
048
049
050 public static final int REVILEX = 6;
051
052
053 public static final int REVTDEG = 7;
054
055
056 public static final int REVITDG = 8;
057
058
059 public final static int DEFAULT_EVORD = IGRLEX;
060
061
062 //public final static int DEFAULT_EVORD = INVLEX;
063
064 private final int evord;
065
066
067 // for split termorders
068 private final int evord2;
069
070
071 private final int evbeg1;
072
073
074 private final int evend1;
075
076
077 private final int evbeg2;
078
079
080 private final int evend2;
081
082
083 private static final Logger logger = Logger.getLogger(TermOrder.class);
084
085
086 private final boolean debug = logger.isDebugEnabled();
087
088
089 /**
090 * Defined array of weight vectors.
091 */
092 private final long[][] weight;
093
094
095 /**
096 * Defined descending order comparator. Sorts the highest terms first.
097 */
098 private final Comparator<ExpVector> horder;
099
100
101 /**
102 * Defined ascending order comparator. Sorts the lowest terms first.
103 */
104 private final Comparator<ExpVector> lorder;
105
106
107 /**
108 * Defined sugar order comparator. Sorts the graded lowest terms first.
109 */
110 private final Comparator<ExpVector> sugar;
111
112
113 /**
114 * Comparator for ExpVectors.
115 */
116 private static abstract class EVorder implements Comparator<ExpVector>, Serializable {
117
118
119 public abstract int compare(ExpVector e1, ExpVector e2);
120 }
121
122
123 /**
124 * Constructor for default term order.
125 */
126 public TermOrder() {
127 this(DEFAULT_EVORD);
128 }
129
130
131 /**
132 * Constructor for given term order.
133 * @param evord requested term order indicator / enumerator.
134 */
135 public TermOrder(int evord) {
136 if (evord < LEX || REVITDG < evord) {
137 throw new IllegalArgumentException("invalid term order: " + evord);
138 }
139 this.evord = evord;
140 this.evord2 = 0;
141 weight = null;
142 evbeg1 = 0;
143 evend1 = Integer.MAX_VALUE;
144 evbeg2 = evend1;
145 evend2 = evend1;
146 switch (evord) { // horder = new EVhorder();
147 case TermOrder.LEX: {
148 horder = new EVorder() {
149
150
151 @Override
152 public int compare(ExpVector e1, ExpVector e2) {
153 return ExpVector.EVILCP(e1, e2);
154 }
155 };
156 break;
157 }
158 case TermOrder.INVLEX: {
159 horder = new EVorder() {
160
161
162 @Override
163 public int compare(ExpVector e1, ExpVector e2) {
164 return -ExpVector.EVILCP(e1, e2);
165 }
166 };
167 break;
168 }
169 case TermOrder.GRLEX: {
170 horder = new EVorder() {
171
172
173 @Override
174 public int compare(ExpVector e1, ExpVector e2) {
175 return ExpVector.EVIGLC(e1, e2);
176 }
177 };
178 break;
179 }
180 case TermOrder.IGRLEX: {
181 horder = new EVorder() {
182
183
184 @Override
185 public int compare(ExpVector e1, ExpVector e2) {
186 return -ExpVector.EVIGLC(e1, e2);
187 }
188 };
189 break;
190 }
191 case TermOrder.REVLEX: {
192 horder = new EVorder() {
193
194
195 @Override
196 public int compare(ExpVector e1, ExpVector e2) {
197 return ExpVector.EVRILCP(e1, e2);
198 }
199 };
200 break;
201 }
202 case TermOrder.REVILEX: {
203 horder = new EVorder() {
204
205
206 @Override
207 public int compare(ExpVector e1, ExpVector e2) {
208 return -ExpVector.EVRILCP(e1, e2);
209 }
210 };
211 break;
212 }
213 case TermOrder.REVTDEG: {
214 horder = new EVorder() {
215
216
217 @Override
218 public int compare(ExpVector e1, ExpVector e2) {
219 return ExpVector.EVRIGLC(e1, e2);
220 }
221 };
222 break;
223 }
224 case TermOrder.REVITDG: {
225 horder = new EVorder() {
226
227
228 @Override
229 public int compare(ExpVector e1, ExpVector e2) {
230 return -ExpVector.EVRIGLC(e1, e2);
231 }
232 };
233 break;
234 }
235 default: {
236 horder = null;
237 }
238 }
239 if (horder == null) {
240 throw new IllegalArgumentException("invalid term order: " + evord);
241 }
242
243 // lorder = new EVlorder();
244 lorder = new EVorder() {
245
246
247 @Override
248 public int compare(ExpVector e1, ExpVector e2) {
249 return -horder.compare(e1, e2);
250 }
251 };
252
253 // sugar = new EVsugar();
254 sugar = new EVorder() {
255
256
257 @Override
258 public int compare(ExpVector e1, ExpVector e2) {
259 return ExpVector.EVIGLC(e1, e2);
260 }
261 };
262 }
263
264
265 /**
266 * Constructor for given exponent weights.
267 * @param w weight vector of longs.
268 */
269 public TermOrder(long[] w) {
270 this(new long[][] { w });
271 }
272
273
274 /**
275 * Constructor for given exponent weights.
276 * @param w weight array of longs.
277 */
278 public TermOrder(long[][] w) {
279 if (w == null || w.length == 0) {
280 throw new IllegalArgumentException("invalid term order weight");
281 }
282 weight = w;
283 this.evord = 0;
284 this.evord2 = 0;
285 evbeg1 = 0;
286 evend1 = weight[0].length;
287 evbeg2 = evend1;
288 evend2 = evend1;
289
290 horder = new EVorder() {
291
292
293 @Override
294 public int compare(ExpVector e1, ExpVector e2) {
295 return -ExpVector.EVIWLC(weight, e1, e2);
296 }
297 };
298
299 // lorder = new EVlorder();
300 lorder = new EVorder() {
301
302
303 @Override
304 public int compare(ExpVector e1, ExpVector e2) {
305 return +ExpVector.EVIWLC(weight, e1, e2);
306 // return - horder.compare( e1, e2 );
307 }
308 };
309
310 // sugar = new EVsugar();
311 sugar = horder;
312 }
313
314
315 /**
316 * Constructor for default split order.
317 * @param r max number of exponents to compare.
318 * @param split index.
319 */
320 public TermOrder(int r, int split) {
321 this(DEFAULT_EVORD, DEFAULT_EVORD, r, split);
322 }
323
324
325 /**
326 * Constructor for given split order.
327 * @param ev1 requested term order indicator for first block.
328 * @param ev2 requested term order indicator for second block.
329 * @param r max number of exponents to compare.
330 * @param split index.
331 */
332 public TermOrder(int ev1, int ev2, int r, int split) {
333 if (ev1 < LEX || REVITDG < ev1) {
334 throw new IllegalArgumentException("invalid term order: " + ev1);
335 }
336 if (ev2 < LEX || REVITDG < ev2) {
337 throw new IllegalArgumentException("invalid term order: " + ev2);
338 }
339 this.evord = ev1;
340 this.evord2 = ev2;
341 weight = null;
342 evbeg1 = 0;
343 evend1 = split; // excluded
344 evbeg2 = split;
345 evend2 = r;
346 if (evbeg2 > evend2) {
347 throw new IllegalArgumentException("invalid term order split, r = " + r + ", split = " + split);
348 }
349 switch (evord) { // horder = new EVhorder();
350 case TermOrder.LEX: {
351 switch (evord2) {
352 case TermOrder.LEX: {
353 horder = new EVorder() {
354
355
356 @Override
357 public int compare(ExpVector e1, ExpVector e2) {
358 int t = ExpVector.EVILCP(e1, e2, evbeg1, evend1);
359 if (t != 0) {
360 return t;
361 }
362 return ExpVector.EVILCP(e1, e2, evbeg2, evend2);
363 }
364 };
365 break;
366 }
367 case TermOrder.INVLEX: {
368 horder = new EVorder() {
369
370
371 @Override
372 public int compare(ExpVector e1, ExpVector e2) {
373 int t = ExpVector.EVILCP(e1, e2, evbeg1, evend1);
374 if (t != 0) {
375 return t;
376 }
377 return -ExpVector.EVILCP(e1, e2, evbeg2, evend2);
378 }
379 };
380 break;
381 }
382 case TermOrder.GRLEX: {
383 horder = new EVorder() {
384
385
386 @Override
387 public int compare(ExpVector e1, ExpVector e2) {
388 int t = ExpVector.EVILCP(e1, e2, evbeg1, evend1);
389 if (t != 0) {
390 return t;
391 }
392 return ExpVector.EVIGLC(e1, e2, evbeg2, evend2);
393 }
394 };
395 break;
396 }
397 case TermOrder.IGRLEX: {
398 horder = new EVorder() {
399
400
401 @Override
402 public int compare(ExpVector e1, ExpVector e2) {
403 int t = ExpVector.EVILCP(e1, e2, evbeg1, evend1);
404 if (t != 0) {
405 return t;
406 }
407 return -ExpVector.EVIGLC(e1, e2, evbeg2, evend2);
408 }
409 };
410 break;
411 }
412 default: {
413 horder = null;
414 }
415 }
416 break;
417 }
418 case TermOrder.INVLEX: {
419 switch (evord2) {
420 case TermOrder.LEX: {
421 horder = new EVorder() {
422
423
424 @Override
425 public int compare(ExpVector e1, ExpVector e2) {
426 int t = -ExpVector.EVILCP(e1, e2, evbeg1, evend1);
427 if (t != 0) {
428 return t;
429 }
430 return ExpVector.EVILCP(e1, e2, evbeg2, evend2);
431 }
432 };
433 break;
434 }
435 case TermOrder.INVLEX: {
436 horder = new EVorder() {
437
438
439 @Override
440 public int compare(ExpVector e1, ExpVector e2) {
441 int t = -ExpVector.EVILCP(e1, e2, evbeg1, evend1);
442 if (t != 0) {
443 return t;
444 }
445 return -ExpVector.EVILCP(e1, e2, evbeg2, evend2);
446 }
447 };
448 break;
449 }
450 case TermOrder.GRLEX: {
451 horder = new EVorder() {
452
453
454 @Override
455 public int compare(ExpVector e1, ExpVector e2) {
456 int t = -ExpVector.EVILCP(e1, e2, evbeg1, evend1);
457 if (t != 0) {
458 return t;
459 }
460 return ExpVector.EVIGLC(e1, e2, evbeg2, evend2);
461 }
462 };
463 break;
464 }
465 case TermOrder.IGRLEX: {
466 horder = new EVorder() {
467
468
469 @Override
470 public int compare(ExpVector e1, ExpVector e2) {
471 int t = -ExpVector.EVILCP(e1, e2, evbeg1, evend1);
472 if (t != 0) {
473 return t;
474 }
475 return -ExpVector.EVIGLC(e1, e2, evbeg2, evend2);
476 }
477 };
478 break;
479 }
480 case TermOrder.REVLEX: {
481 horder = new EVorder() {
482
483
484 @Override
485 public int compare(ExpVector e1, ExpVector e2) {
486 int t = -ExpVector.EVILCP(e1, e2, evbeg1, evend1);
487 if (t != 0) {
488 return t;
489 }
490 return ExpVector.EVRILCP(e1, e2, evbeg2, evend2);
491 }
492 };
493 break;
494 }
495 case TermOrder.REVILEX: {
496 horder = new EVorder() {
497
498
499 @Override
500 public int compare(ExpVector e1, ExpVector e2) {
501 int t = -ExpVector.EVILCP(e1, e2, evbeg1, evend1);
502 if (t != 0) {
503 return t;
504 }
505 return -ExpVector.EVRILCP(e1, e2, evbeg2, evend2);
506 }
507 };
508 break;
509 }
510 case TermOrder.REVTDEG: {
511 horder = new EVorder() {
512
513
514 @Override
515 public int compare(ExpVector e1, ExpVector e2) {
516 int t = -ExpVector.EVILCP(e1, e2, evbeg1, evend1);
517 if (t != 0) {
518 return t;
519 }
520 return ExpVector.EVRIGLC(e1, e2, evbeg2, evend2);
521 }
522 };
523 break;
524 }
525 case TermOrder.REVITDG: {
526 horder = new EVorder() {
527
528
529 @Override
530 public int compare(ExpVector e1, ExpVector e2) {
531 int t = -ExpVector.EVILCP(e1, e2, evbeg1, evend1);
532 if (t != 0) {
533 return t;
534 }
535 return -ExpVector.EVRIGLC(e1, e2, evbeg2, evend2);
536 }
537 };
538 break;
539 }
540 default: {
541 horder = null;
542 }
543 }
544 break;
545 }
546 case TermOrder.GRLEX: {
547 switch (evord2) {
548 case TermOrder.LEX: {
549 horder = new EVorder() {
550
551
552 @Override
553 public int compare(ExpVector e1, ExpVector e2) {
554 int t = ExpVector.EVIGLC(e1, e2, evbeg1, evend1);
555 if (t != 0) {
556 return t;
557 }
558 return ExpVector.EVILCP(e1, e2, evbeg2, evend2);
559 }
560 };
561 break;
562 }
563 case TermOrder.INVLEX: {
564 horder = new EVorder() {
565
566
567 @Override
568 public int compare(ExpVector e1, ExpVector e2) {
569 int t = ExpVector.EVIGLC(e1, e2, evbeg1, evend1);
570 if (t != 0) {
571 return t;
572 }
573 return -ExpVector.EVILCP(e1, e2, evbeg2, evend2);
574 }
575 };
576 break;
577 }
578 case TermOrder.GRLEX: {
579 horder = new EVorder() {
580
581
582 @Override
583 public int compare(ExpVector e1, ExpVector e2) {
584 int t = ExpVector.EVIGLC(e1, e2, evbeg1, evend1);
585 if (t != 0) {
586 return t;
587 }
588 return ExpVector.EVIGLC(e1, e2, evbeg2, evend2);
589 }
590 };
591 break;
592 }
593 case TermOrder.IGRLEX: {
594 horder = new EVorder() {
595
596
597 @Override
598 public int compare(ExpVector e1, ExpVector e2) {
599 int t = ExpVector.EVIGLC(e1, e2, evbeg1, evend1);
600 if (t != 0) {
601 return t;
602 }
603 return -ExpVector.EVIGLC(e1, e2, evbeg2, evend2);
604 }
605 };
606 break;
607 }
608 default: {
609 horder = null;
610 }
611 }
612 break;
613 }
614 case TermOrder.IGRLEX: {
615 switch (evord2) {
616 case TermOrder.LEX: {
617 horder = new EVorder() {
618
619
620 @Override
621 public int compare(ExpVector e1, ExpVector e2) {
622 int t = -ExpVector.EVIGLC(e1, e2, evbeg1, evend1);
623 if (t != 0) {
624 return t;
625 }
626 return ExpVector.EVILCP(e1, e2, evbeg2, evend2);
627 }
628 };
629 break;
630 }
631 case TermOrder.INVLEX: {
632 horder = new EVorder() {
633
634
635 @Override
636 public int compare(ExpVector e1, ExpVector e2) {
637 int t = -ExpVector.EVIGLC(e1, e2, evbeg1, evend1);
638 if (t != 0) {
639 return t;
640 }
641 return -ExpVector.EVILCP(e1, e2, evbeg2, evend2);
642 }
643 };
644 break;
645 }
646 case TermOrder.GRLEX: {
647 horder = new EVorder() {
648
649
650 @Override
651 public int compare(ExpVector e1, ExpVector e2) {
652 int t = -ExpVector.EVIGLC(e1, e2, evbeg1, evend1);
653 if (t != 0) {
654 return t;
655 }
656 return ExpVector.EVIGLC(e1, e2, evbeg2, evend2);
657 }
658 };
659 break;
660 }
661 case TermOrder.IGRLEX: {
662 horder = new EVorder() {
663
664
665 @Override
666 public int compare(ExpVector e1, ExpVector e2) {
667 int t = -ExpVector.EVIGLC(e1, e2, evbeg1, evend1);
668 if (t != 0) {
669 return t;
670 }
671 return -ExpVector.EVIGLC(e1, e2, evbeg2, evend2);
672 }
673 };
674 break;
675 }
676 case TermOrder.REVLEX: {
677 horder = new EVorder() {
678
679
680 @Override
681 public int compare(ExpVector e1, ExpVector e2) {
682 int t = -ExpVector.EVIGLC(e1, e2, evbeg1, evend1);
683 if (t != 0) {
684 return t;
685 }
686 return ExpVector.EVRILCP(e1, e2, evbeg2, evend2);
687 }
688 };
689 break;
690 }
691 case TermOrder.REVILEX: {
692 horder = new EVorder() {
693
694
695 @Override
696 public int compare(ExpVector e1, ExpVector e2) {
697 int t = -ExpVector.EVIGLC(e1, e2, evbeg1, evend1);
698 if (t != 0) {
699 return t;
700 }
701 return -ExpVector.EVRILCP(e1, e2, evbeg2, evend2);
702 }
703 };
704 break;
705 }
706 case TermOrder.REVTDEG: {
707 horder = new EVorder() {
708
709
710 @Override
711 public int compare(ExpVector e1, ExpVector e2) {
712 int t = -ExpVector.EVIGLC(e1, e2, evbeg1, evend1);
713 if (t != 0) {
714 return t;
715 }
716 return ExpVector.EVRIGLC(e1, e2, evbeg2, evend2);
717 }
718 };
719 break;
720 }
721 case TermOrder.REVITDG: {
722 horder = new EVorder() {
723
724
725 @Override
726 public int compare(ExpVector e1, ExpVector e2) {
727 int t = -ExpVector.EVIGLC(e1, e2, evbeg1, evend1);
728 if (t != 0) {
729 return t;
730 }
731 return -ExpVector.EVRIGLC(e1, e2, evbeg2, evend2);
732 }
733 };
734 break;
735 }
736 default: {
737 horder = null;
738 }
739 }
740 break;
741 }
742 //----- begin reversed -----------
743 case TermOrder.REVLEX: {
744 switch (evord2) {
745 case TermOrder.LEX: {
746 horder = new EVorder() {
747
748
749 @Override
750 public int compare(ExpVector e1, ExpVector e2) {
751 int t = ExpVector.EVRILCP(e1, e2, evbeg1, evend1);
752 if (t != 0) {
753 return t;
754 }
755 return ExpVector.EVILCP(e1, e2, evbeg2, evend2);
756 }
757 };
758 break;
759 }
760 case TermOrder.INVLEX: {
761 horder = new EVorder() {
762
763
764 @Override
765 public int compare(ExpVector e1, ExpVector e2) {
766 int t = ExpVector.EVRILCP(e1, e2, evbeg1, evend1);
767 if (t != 0) {
768 return t;
769 }
770 return -ExpVector.EVILCP(e1, e2, evbeg2, evend2);
771 }
772 };
773 break;
774 }
775 case TermOrder.GRLEX: {
776 horder = new EVorder() {
777
778
779 @Override
780 public int compare(ExpVector e1, ExpVector e2) {
781 int t = ExpVector.EVRILCP(e1, e2, evbeg1, evend1);
782 if (t != 0) {
783 return t;
784 }
785 return ExpVector.EVIGLC(e1, e2, evbeg2, evend2);
786 }
787 };
788 break;
789 }
790 case TermOrder.IGRLEX: {
791 horder = new EVorder() {
792
793
794 @Override
795 public int compare(ExpVector e1, ExpVector e2) {
796 int t = ExpVector.EVRILCP(e1, e2, evbeg1, evend1);
797 if (t != 0) {
798 return t;
799 }
800 return -ExpVector.EVIGLC(e1, e2, evbeg2, evend2);
801 }
802 };
803 break;
804 }
805 case TermOrder.REVLEX: {
806 horder = new EVorder() {
807
808
809 @Override
810 public int compare(ExpVector e1, ExpVector e2) {
811 int t = ExpVector.EVRILCP(e1, e2, evbeg1, evend1);
812 if (t != 0) {
813 return t;
814 }
815 return ExpVector.EVRILCP(e1, e2, evbeg2, evend2);
816 }
817 };
818 break;
819 }
820 case TermOrder.REVILEX: {
821 horder = new EVorder() {
822
823
824 @Override
825 public int compare(ExpVector e1, ExpVector e2) {
826 int t = ExpVector.EVRILCP(e1, e2, evbeg1, evend1);
827 if (t != 0) {
828 return t;
829 }
830 return -ExpVector.EVRILCP(e1, e2, evbeg2, evend2);
831 }
832 };
833 break;
834 }
835 case TermOrder.REVTDEG: {
836 horder = new EVorder() {
837
838
839 @Override
840 public int compare(ExpVector e1, ExpVector e2) {
841 int t = ExpVector.EVRILCP(e1, e2, evbeg1, evend1);
842 if (t != 0) {
843 return t;
844 }
845 return ExpVector.EVRIGLC(e1, e2, evbeg2, evend2);
846 }
847 };
848 break;
849 }
850 case TermOrder.REVITDG: {
851 horder = new EVorder() {
852
853
854 @Override
855 public int compare(ExpVector e1, ExpVector e2) {
856 int t = ExpVector.EVRILCP(e1, e2, evbeg1, evend1);
857 if (t != 0) {
858 return t;
859 }
860 return -ExpVector.EVRIGLC(e1, e2, evbeg2, evend2);
861 }
862 };
863 break;
864 }
865 default: {
866 horder = null;
867 }
868 }
869 break;
870 }
871 case TermOrder.REVILEX: {
872 switch (evord2) {
873 case TermOrder.LEX: {
874 horder = new EVorder() {
875
876
877 @Override
878 public int compare(ExpVector e1, ExpVector e2) {
879 int t = -ExpVector.EVRILCP(e1, e2, evbeg1, evend1);
880 if (t != 0) {
881 return t;
882 }
883 return ExpVector.EVILCP(e1, e2, evbeg2, evend2);
884 }
885 };
886 break;
887 }
888 case TermOrder.INVLEX: {
889 horder = new EVorder() {
890
891
892 @Override
893 public int compare(ExpVector e1, ExpVector e2) {
894 int t = -ExpVector.EVRILCP(e1, e2, evbeg1, evend1);
895 if (t != 0) {
896 return t;
897 }
898 return -ExpVector.EVILCP(e1, e2, evbeg2, evend2);
899 }
900 };
901 break;
902 }
903 case TermOrder.GRLEX: {
904 horder = new EVorder() {
905
906
907 @Override
908 public int compare(ExpVector e1, ExpVector e2) {
909 int t = -ExpVector.EVRILCP(e1, e2, evbeg1, evend1);
910 if (t != 0) {
911 return t;
912 }
913 return ExpVector.EVRIGLC(e1, e2, evbeg2, evend2);
914 }
915 };
916 break;
917 }
918 case TermOrder.IGRLEX: {
919 horder = new EVorder() {
920
921
922 @Override
923 public int compare(ExpVector e1, ExpVector e2) {
924 int t = -ExpVector.EVRILCP(e1, e2, evbeg1, evend1);
925 if (t != 0) {
926 return t;
927 }
928 return -ExpVector.EVIGLC(e1, e2, evbeg2, evend2);
929 }
930 };
931 break;
932 }
933 case TermOrder.REVLEX: {
934 horder = new EVorder() {
935
936
937 @Override
938 public int compare(ExpVector e1, ExpVector e2) {
939 int t = -ExpVector.EVRILCP(e1, e2, evbeg1, evend1);
940 if (t != 0) {
941 return t;
942 }
943 return ExpVector.EVRILCP(e1, e2, evbeg2, evend2);
944 }
945 };
946 break;
947 }
948 case TermOrder.REVILEX: {
949 horder = new EVorder() {
950
951
952 @Override
953 public int compare(ExpVector e1, ExpVector e2) {
954 int t = -ExpVector.EVRILCP(e1, e2, evbeg1, evend1);
955 if (t != 0) {
956 return t;
957 }
958 return -ExpVector.EVRILCP(e1, e2, evbeg2, evend2);
959 }
960 };
961 break;
962 }
963 case TermOrder.REVTDEG: {
964 horder = new EVorder() {
965
966
967 @Override
968 public int compare(ExpVector e1, ExpVector e2) {
969 int t = -ExpVector.EVRILCP(e1, e2, evbeg1, evend1);
970 if (t != 0) {
971 return t;
972 }
973 return ExpVector.EVRIGLC(e1, e2, evbeg2, evend2);
974 }
975 };
976 break;
977 }
978 case TermOrder.REVITDG: {
979 horder = new EVorder() {
980
981
982 @Override
983 public int compare(ExpVector e1, ExpVector e2) {
984 int t = -ExpVector.EVRILCP(e1, e2, evbeg1, evend1);
985 if (t != 0) {
986 return t;
987 }
988 return -ExpVector.EVRIGLC(e1, e2, evbeg2, evend2);
989 }
990 };
991 break;
992 }
993 default: {
994 horder = null;
995 }
996 }
997 break;
998 }
999 case TermOrder.REVTDEG: {
1000 switch (evord2) {
1001 case TermOrder.LEX: {
1002 horder = new EVorder() {
1003
1004
1005 @Override
1006 public int compare(ExpVector e1, ExpVector e2) {
1007 int t = ExpVector.EVRIGLC(e1, e2, evbeg1, evend1);
1008 if (t != 0) {
1009 return t;
1010 }
1011 return ExpVector.EVILCP(e1, e2, evbeg2, evend2);
1012 }
1013 };
1014 break;
1015 }
1016 case TermOrder.INVLEX: {
1017 horder = new EVorder() {
1018
1019
1020 @Override
1021 public int compare(ExpVector e1, ExpVector e2) {
1022 int t = ExpVector.EVRIGLC(e1, e2, evbeg1, evend1);
1023 if (t != 0) {
1024 return t;
1025 }
1026 return -ExpVector.EVILCP(e1, e2, evbeg2, evend2);
1027 }
1028 };
1029 break;
1030 }
1031 case TermOrder.GRLEX: {
1032 horder = new EVorder() {
1033
1034
1035 @Override
1036 public int compare(ExpVector e1, ExpVector e2) {
1037 int t = ExpVector.EVRIGLC(e1, e2, evbeg1, evend1);
1038 if (t != 0) {
1039 return t;
1040 }
1041 return ExpVector.EVIGLC(e1, e2, evbeg2, evend2);
1042 }
1043 };
1044 break;
1045 }
1046 case TermOrder.IGRLEX: {
1047 horder = new EVorder() {
1048
1049
1050 @Override
1051 public int compare(ExpVector e1, ExpVector e2) {
1052 int t = ExpVector.EVRIGLC(e1, e2, evbeg1, evend1);
1053 if (t != 0) {
1054 return t;
1055 }
1056 return -ExpVector.EVIGLC(e1, e2, evbeg2, evend2);
1057 }
1058 };
1059 break;
1060 }
1061 case TermOrder.REVLEX: {
1062 horder = new EVorder() {
1063
1064
1065 @Override
1066 public int compare(ExpVector e1, ExpVector e2) {
1067 int t = ExpVector.EVRIGLC(e1, e2, evbeg1, evend1);
1068 if (t != 0) {
1069 return t;
1070 }
1071 return ExpVector.EVRILCP(e1, e2, evbeg2, evend2);
1072 }
1073 };
1074 break;
1075 }
1076 case TermOrder.REVILEX: {
1077 horder = new EVorder() {
1078
1079
1080 @Override
1081 public int compare(ExpVector e1, ExpVector e2) {
1082 int t = ExpVector.EVRIGLC(e1, e2, evbeg1, evend1);
1083 if (t != 0) {
1084 return t;
1085 }
1086 return -ExpVector.EVRILCP(e1, e2, evbeg2, evend2);
1087 }
1088 };
1089 break;
1090 }
1091 case TermOrder.REVTDEG: {
1092 horder = new EVorder() {
1093
1094
1095 @Override
1096 public int compare(ExpVector e1, ExpVector e2) {
1097 int t = ExpVector.EVRIGLC(e1, e2, evbeg1, evend1);
1098 if (t != 0) {
1099 return t;
1100 }
1101 return ExpVector.EVRIGLC(e1, e2, evbeg2, evend2);
1102 }
1103 };
1104 break;
1105 }
1106 case TermOrder.REVITDG: {
1107 horder = new EVorder() {
1108
1109
1110 @Override
1111 public int compare(ExpVector e1, ExpVector e2) {
1112 int t = ExpVector.EVRIGLC(e1, e2, evbeg1, evend1);
1113 if (t != 0) {
1114 return t;
1115 }
1116 return -ExpVector.EVRIGLC(e1, e2, evbeg2, evend2);
1117 }
1118 };
1119 break;
1120 }
1121 default: {
1122 horder = null;
1123 }
1124 }
1125 break;
1126 }
1127 case TermOrder.REVITDG: {
1128 switch (evord2) {
1129 case TermOrder.LEX: {
1130 horder = new EVorder() {
1131
1132
1133 @Override
1134 public int compare(ExpVector e1, ExpVector e2) {
1135 int t = -ExpVector.EVRIGLC(e1, e2, evbeg1, evend1);
1136 if (t != 0) {
1137 return t;
1138 }
1139 return ExpVector.EVILCP(e1, e2, evbeg2, evend2);
1140 }
1141 };
1142 break;
1143 }
1144 case TermOrder.INVLEX: {
1145 horder = new EVorder() {
1146
1147
1148 @Override
1149 public int compare(ExpVector e1, ExpVector e2) {
1150 int t = -ExpVector.EVRIGLC(e1, e2, evbeg1, evend1);
1151 if (t != 0) {
1152 return t;
1153 }
1154 return -ExpVector.EVILCP(e1, e2, evbeg2, evend2);
1155 }
1156 };
1157 break;
1158 }
1159 case TermOrder.GRLEX: {
1160 horder = new EVorder() {
1161
1162
1163 @Override
1164 public int compare(ExpVector e1, ExpVector e2) {
1165 int t = -ExpVector.EVRIGLC(e1, e2, evbeg1, evend1);
1166 if (t != 0) {
1167 return t;
1168 }
1169 return ExpVector.EVIGLC(e1, e2, evbeg2, evend2);
1170 }
1171 };
1172 break;
1173 }
1174 case TermOrder.IGRLEX: {
1175 horder = new EVorder() {
1176
1177
1178 @Override
1179 public int compare(ExpVector e1, ExpVector e2) {
1180 int t = -ExpVector.EVRIGLC(e1, e2, evbeg1, evend1);
1181 if (t != 0) {
1182 return t;
1183 }
1184 return -ExpVector.EVIGLC(e1, e2, evbeg2, evend2);
1185 }
1186 };
1187 break;
1188 }
1189 case TermOrder.REVLEX: {
1190 horder = new EVorder() {
1191
1192
1193 @Override
1194 public int compare(ExpVector e1, ExpVector e2) {
1195 int t = -ExpVector.EVRIGLC(e1, e2, evbeg1, evend1);
1196 if (t != 0) {
1197 return t;
1198 }
1199 return ExpVector.EVRILCP(e1, e2, evbeg2, evend2);
1200 }
1201 };
1202 break;
1203 }
1204 case TermOrder.REVILEX: {
1205 horder = new EVorder() {
1206
1207
1208 @Override
1209 public int compare(ExpVector e1, ExpVector e2) {
1210 int t = -ExpVector.EVRIGLC(e1, e2, evbeg1, evend1);
1211 if (t != 0) {
1212 return t;
1213 }
1214 return -ExpVector.EVRILCP(e1, e2, evbeg2, evend2);
1215 }
1216 };
1217 break;
1218 }
1219 case TermOrder.REVTDEG: {
1220 horder = new EVorder() {
1221
1222
1223 @Override
1224 public int compare(ExpVector e1, ExpVector e2) {
1225 int t = -ExpVector.EVRIGLC(e1, e2, evbeg1, evend1);
1226 if (t != 0) {
1227 return t;
1228 }
1229 return ExpVector.EVRIGLC(e1, e2, evbeg2, evend2);
1230 }
1231 };
1232 break;
1233 }
1234 case TermOrder.REVITDG: {
1235 horder = new EVorder() {
1236
1237
1238 @Override
1239 public int compare(ExpVector e1, ExpVector e2) {
1240 int t = -ExpVector.EVRIGLC(e1, e2, evbeg1, evend1);
1241 if (t != 0) {
1242 return t;
1243 }
1244 return -ExpVector.EVRIGLC(e1, e2, evbeg2, evend2);
1245 }
1246 };
1247 break;
1248 }
1249 default: {
1250 horder = null;
1251 }
1252 }
1253 break;
1254 }
1255 //----- end reversed-----------
1256 default: {
1257 horder = null;
1258 }
1259 }
1260 if (horder == null) {
1261 throw new IllegalArgumentException("invalid term order: " + evord + " 2 " + evord2);
1262 }
1263
1264 lorder = new EVorder() {
1265
1266
1267 @Override
1268 public int compare(ExpVector e1, ExpVector e2) {
1269 return -horder.compare(e1, e2);
1270 }
1271 };
1272
1273 // sugar = new EVsugar();
1274 sugar = new EVorder() {
1275
1276
1277 @Override
1278 public int compare(ExpVector e1, ExpVector e2) {
1279 return ExpVector.EVIGLC(e1, e2);
1280 }
1281 };
1282 }
1283
1284
1285 /**
1286 * Get the first defined order indicator.
1287 * @return evord.
1288 */
1289 public int getEvord() {
1290 return evord;
1291 }
1292
1293
1294 /**
1295 * Get the second defined order indicator.
1296 * @return evord2.
1297 */
1298 public int getEvord2() {
1299 return evord2;
1300 }
1301
1302
1303 /**
1304 * Get the split index.
1305 * @return split.
1306 */
1307 public int getSplit() {
1308 return evend1; // = evbeg2
1309 }
1310
1311
1312 /**
1313 * Get the weight array.
1314 * @return weight.
1315 */
1316 public long[][] getWeight() {
1317 return weight;
1318 }
1319
1320
1321 /**
1322 * Get the descending order comparator. Sorts the highest terms first.
1323 * @return horder.
1324 */
1325 public Comparator<ExpVector> getDescendComparator() {
1326 return horder;
1327 }
1328
1329
1330 /**
1331 * Get the ascending order comparator. Sorts the lowest terms first.
1332 * @return lorder.
1333 */
1334 public Comparator<ExpVector> getAscendComparator() {
1335 return lorder;
1336 }
1337
1338
1339 /**
1340 * Get the sugar order comparator. Sorts the graded lowest terms first.
1341 * @return sugar.
1342 */
1343 public Comparator<ExpVector> getSugarComparator() {
1344 return sugar;
1345 }
1346
1347
1348 /**
1349 * Comparison with any other object.
1350 * @see java.lang.Object#equals(java.lang.Object)
1351 */
1352 @Override
1353 public boolean equals(Object B) {
1354 if (!(B instanceof TermOrder)) {
1355 return false;
1356 }
1357 TermOrder b = (TermOrder) B;
1358 boolean t = evord == b.getEvord() && evord2 == b.evord2 && evbeg1 == b.evbeg1 && evend1 == b.evend1
1359 && evbeg2 == b.evbeg2 && evend2 == b.evend2;
1360 if (!t) {
1361 return t;
1362 }
1363 if (!Arrays.equals(weight, b.weight)) {
1364 return false;
1365 }
1366 return true;
1367 }
1368
1369
1370 /**
1371 * Hash code.
1372 * @see java.lang.Object#hashCode()
1373 */
1374 @Override
1375 public int hashCode() {
1376 int h = evord;
1377 h = (h << 3) + evord2;
1378 h = (h << 4) + evbeg1;
1379 h = (h << 4) + evend1;
1380 h = (h << 4) + evbeg2;
1381 h = (h << 4) + evend2;
1382 if (weight == null) {
1383 return h;
1384 }
1385 h = h * 7 + Arrays.deepHashCode(weight);
1386 return h;
1387 }
1388
1389
1390 /**
1391 * String representation of weight vector.
1392 * @see java.lang.Object#toString()
1393 */
1394 public String weightToString() {
1395 StringBuffer erg = new StringBuffer();
1396 if (weight != null) {
1397 erg.append("weight(");
1398 for (int j = 0; j < weight.length; j++) {
1399 long[] wj = weight[j];
1400 erg.append("(");
1401 for (int i = 0; i < wj.length; i++) {
1402 erg.append("" + wj[wj.length - i - 1]);
1403 if (i < wj.length - 1) {
1404 erg.append(",");
1405 }
1406 }
1407 erg.append(")");
1408 if (j < weight.length - 1) {
1409 erg.append(",");
1410 }
1411 }
1412 erg.append(")");
1413 }
1414 return erg.toString();
1415 }
1416
1417
1418 /**
1419 * String representation of TermOrder.
1420 * @see java.lang.Object#toString()
1421 */
1422 @Override
1423 public String toString() {
1424 StringBuffer erg = new StringBuffer();
1425 if (weight != null) {
1426 erg.append("W(");
1427 for (int j = 0; j < weight.length; j++) {
1428 long[] wj = weight[j];
1429 erg.append("(");
1430 for (int i = 0; i < wj.length; i++) {
1431 erg.append("" + wj[wj.length - i - 1]);
1432 if (i < wj.length - 1) {
1433 erg.append(",");
1434 }
1435 }
1436 erg.append(")");
1437 if (j < weight.length - 1) {
1438 erg.append(",");
1439 }
1440 }
1441 erg.append(")");
1442 if (evend1 == evend2) {
1443 return erg.toString();
1444 }
1445 erg.append("[" + evbeg1 + "," + evend1 + "]");
1446 erg.append("[" + evbeg2 + "," + evend2 + "]");
1447 return erg.toString();
1448 }
1449 switch (evord) {
1450 case LEX:
1451 erg.append("LEX");
1452 break;
1453 case INVLEX:
1454 erg.append("INVLEX");
1455 break;
1456 case GRLEX:
1457 erg.append("GRLEX");
1458 break;
1459 case IGRLEX:
1460 erg.append("IGRLEX");
1461 break;
1462 case REVLEX:
1463 erg.append("REVLEX");
1464 break;
1465 case REVILEX:
1466 erg.append("REVILEX");
1467 break;
1468 case REVTDEG:
1469 erg.append("REVTDEG");
1470 break;
1471 case REVITDG:
1472 erg.append("REVITDG");
1473 break;
1474 default:
1475 erg.append("invalid(" + evord + ")");
1476 break;
1477 }
1478 if (evord2 <= 0) {
1479 return erg.toString();
1480 }
1481 erg.append("[" + evbeg1 + "," + evend1 + "]");
1482 switch (evord2) {
1483 case LEX:
1484 erg.append("LEX");
1485 break;
1486 case INVLEX:
1487 erg.append("INVLEX");
1488 break;
1489 case GRLEX:
1490 erg.append("GRLEX");
1491 break;
1492 case IGRLEX:
1493 erg.append("IGRLEX");
1494 break;
1495 case REVLEX:
1496 erg.append("REVLEX");
1497 break;
1498 case REVILEX:
1499 erg.append("REVILEX");
1500 break;
1501 case REVTDEG:
1502 erg.append("REVTDEG");
1503 break;
1504 case REVITDG:
1505 erg.append("REVITDG");
1506 break;
1507 default:
1508 erg.append("invalid(" + evord2 + ")");
1509 break;
1510 }
1511 erg.append("[" + evbeg2 + "," + evend2 + "]");
1512 return erg.toString();
1513 }
1514
1515
1516 /**
1517 * Extend variables. Used e.g. in module embedding. Extend TermOrder by k
1518 * elements. <b>Note:</b> todo distinguish TOP and POT orders.
1519 * @param r current number of variables.
1520 * @param k number of variables to extend.
1521 * @return extended TermOrder.
1522 */
1523 public TermOrder extend(int r, int k) {
1524 if (weight != null) {
1525 long[][] w = new long[weight.length][];
1526 for (int i = 0; i < weight.length; i++) {
1527 long[] wi = weight[i];
1528 long max = 0;
1529 // long min = Long.MAX_VALUE;
1530 for (int j = 0; j < wi.length; j++) {
1531 if (wi[j] > max)
1532 max = wi[j];
1533 //if ( wi[j] < min ) min = wi[j];
1534 }
1535 max++;
1536 long[] wj = new long[wi.length + k];
1537 for (int j = 0; j < i; j++) {
1538 wj[j] = max;
1539 }
1540 System.arraycopy(wi, 0, wj, i, wi.length);
1541 w[i] = wj;
1542 }
1543 return new TermOrder(w);
1544 }
1545 if (evord2 != 0) {
1546 if (debug) {
1547 logger.warn("TermOrder is already extended");
1548 }
1549 return new TermOrder(evord, evord2, r + k, evend1 + k);
1550 }
1551 //System.out.println("evord = " + evord);
1552 //System.out.println("DEFAULT_EVORD = " + DEFAULT_EVORD);
1553 //System.out.println("tord = " + this);
1554 return new TermOrder(DEFAULT_EVORD/*evord*/, evord, r + k, k); // don't change to evord, cause REVITDG
1555 }
1556
1557
1558 /**
1559 * Extend lower variables. Extend TermOrder by k elements. <b>Note:</b> todo
1560 * distinguish TOP and POT orders.
1561 * @param r current number of variables.
1562 * @param k number of variables to extend.
1563 * @return extended TermOrder.
1564 */
1565 public TermOrder extendLower(int r, int k) {
1566 if (weight != null) {
1567 long[][] w = new long[weight.length][];
1568 for (int i = 0; i < weight.length; i++) {
1569 long[] wi = weight[i];
1570 //long max = 0;
1571 long min = Long.MAX_VALUE;
1572 for (int j = 0; j < wi.length; j++) {
1573 //if ( wi[j] > max ) max = wi[j];
1574 if (wi[j] < min)
1575 min = wi[j];
1576 }
1577 //max++;
1578 long[] wj = new long[wi.length + k];
1579 for (int j = 0; j < i; j++) {
1580 wj[wi.length + j] = min;
1581 }
1582 System.arraycopy(wi, 0, wj, 0, wi.length);
1583 w[i] = wj;
1584 }
1585 return new TermOrder(w);
1586 }
1587 if (evord2 != 0) {
1588 if (debug) {
1589 logger.warn("TermOrder is already extended");
1590 }
1591 return new TermOrder(evord, evord2, r + k, evend1 + k);
1592 }
1593 //System.out.println("evord = " + evord);
1594 //System.out.println("DEFAULT_EVORD = " + DEFAULT_EVORD);
1595 //System.out.println("tord = " + this);
1596 return new TermOrder(evord);
1597 }
1598
1599
1600 /**
1601 * Contract variables. Used e.g. in module embedding. Contract TermOrder to
1602 * non split status.
1603 * @param k position of first element to be copied.
1604 * @param len new length.
1605 * @return contracted TermOrder.
1606 */
1607 public TermOrder contract(int k, int len) {
1608 if (weight != null) {
1609 long[][] w = new long[weight.length][];
1610 for (int i = 0; i < weight.length; i++) {
1611 long[] wi = weight[i];
1612 long[] wj = new long[len];
1613 System.arraycopy(wi, k, wj, 0, len);
1614 w[i] = wj;
1615 }
1616 return new TermOrder(w);
1617 }
1618 if (evord2 == 0) {
1619 if (debug) {
1620 logger.warn("TermOrder is already contracted");
1621 }
1622 return new TermOrder(evord);
1623 }
1624 if (evend1 > k) { // < IntMax since evord2 != 0
1625 int el = evend1 - k;
1626 while ( el > len ) {
1627 el -= len;
1628 }
1629 if ( el == 0L ) {
1630 return new TermOrder(evord);
1631 }
1632 if ( el == len ) {
1633 return new TermOrder(evord);
1634 }
1635 return new TermOrder(evord, evord2, len, el);
1636 }
1637 return new TermOrder(evord2);
1638 }
1639
1640
1641 /**
1642 * Reverse variables. Used e.g. in opposite rings.
1643 * @return TermOrder for reversed variables.
1644 */
1645 public TermOrder reverse() {
1646 return reverse(false);
1647 }
1648
1649
1650 /**
1651 * Reverse variables. Used e.g. in opposite rings.
1652 * @param partial true for partialy reversed term orders.
1653 * @return TermOrder for reversed variables.
1654 */
1655 public TermOrder reverse(boolean partial) {
1656 TermOrder t;
1657 if (weight != null) {
1658 if (partial) {
1659 logger.error("partial reversed weight order not implemented");
1660 }
1661 long[][] w = new long[weight.length][];
1662 for (int i = 0; i < weight.length; i++) {
1663 long[] wi = weight[i];
1664 long[] wj = new long[wi.length];
1665 for (int j = 0; j < wj.length; j++) {
1666 wj[j] = wi[wj.length - 1 - j];
1667 }
1668 w[i] = wj;
1669 }
1670 t = new TermOrder(w);
1671 logger.info("new TO = " + t);
1672 return t;
1673 }
1674 if (evord2 == 0) {
1675 t = new TermOrder(revert(evord));
1676 return t;
1677 }
1678 if (partial) {
1679 t = new TermOrder(revert(evord), revert(evord2), evend2, evend1);
1680 } else {
1681 t = new TermOrder(revert(evord2), revert(evord), evend2, evend2 - evbeg2);
1682 }
1683 logger.info("new TO = " + t);
1684 return t;
1685 }
1686
1687
1688 /**
1689 * Revert exponent order. Used e.g. in opposite rings.
1690 * @param evord exponent order to be reverted.
1691 * @return reverted exponent order.
1692 */
1693 public static int revert(int evord) {
1694 int i = evord;
1695 switch (evord) {
1696 case LEX:
1697 i = REVLEX;
1698 break;
1699 case INVLEX:
1700 i = REVILEX;
1701 break;
1702 case GRLEX:
1703 i = REVTDEG;
1704 break;
1705 case IGRLEX:
1706 i = REVITDG;
1707 break;
1708 case REVLEX:
1709 i = LEX;
1710 break;
1711 case REVILEX:
1712 i = INVLEX;
1713 break;
1714 case REVTDEG:
1715 i = GRLEX;
1716 break;
1717 case REVITDG:
1718 i = IGRLEX;
1719 break;
1720 default:
1721 logger.error("can not revert " + evord);
1722 break;
1723 }
1724 return i;
1725 }
1726
1727 }