source: git/factory/int_poly.cc @ 3645fc

spielwiese
Last change on this file since 3645fc was ac8e1a, checked in by Martin Lee <martinlee84@…>, 13 years ago
compiler warnings git-svn-id: file:///usr/local/Singular/svn/trunk@14267 2c84dea3-7e68-4137-9b89-c4e89433aadc
  • Property mode set to 100644
File size: 42.8 KB
Line 
1/* emacs edit mode for this file is -*- C++ -*- */
2/* $Id$ */
3
4#include <config.h>
5
6#ifndef NOSTREAMIO
7#include <string.h>
8#if defined(WINNT) && ! defined(__GNUC__)
9#include <strstrea.h>
10#else
11#if __GNUC__ < 3
12#include <strstream.h>
13#else
14#include <strstream>
15using namespace std;
16#endif
17#endif
18#endif /* NOSTREAMIO */
19
20#include "assert.h"
21
22#include "cf_defs.h"
23#include "cf_factory.h"
24#include "int_cf.h"
25#include "int_int.h"
26#include "int_poly.h"
27#include "canonicalform.h"
28#include "variable.h"
29#include "imm.h"
30
31#ifdef HAVE_OMALLOC
32const omBin term::term_bin = omGetSpecBin(sizeof(term));
33const omBin InternalPoly::InternalPoly_bin = omGetSpecBin(sizeof(InternalPoly));
34#endif
35
36InternalPoly::InternalPoly( termList first, termList last, const Variable & v )
37{
38    firstTerm = first;
39    lastTerm = last;
40    var = v;
41}
42
43InternalPoly::InternalPoly()
44{
45    ASSERT( 0, "ups, why do you initialize an empty poly" );
46}
47
48InternalPoly::InternalPoly( const Variable & v, const int e, const CanonicalForm& c )
49{
50    var = v;
51    firstTerm = new term( 0, c, e );
52    lastTerm = firstTerm;
53}
54
55InternalPoly::InternalPoly( const InternalPoly& )
56{
57    ASSERT( 0, "ups there is something wrong in your code" );
58};
59
60InternalPoly::~InternalPoly()
61{
62    freeTermList( firstTerm );
63}
64
65InternalCF*
66InternalPoly::deepCopyObject() const
67{
68    termList first, last;
69    first = deepCopyTermList( firstTerm, last );
70    return new InternalPoly( first, last, var );
71}
72
73InternalCF*
74InternalPoly::genZero()
75{
76    return firstTerm->coeff.genZero().getval();
77}
78
79InternalCF*
80InternalPoly::genOne()
81{
82    return firstTerm->coeff.genOne().getval();
83}
84
85bool
86InternalPoly::isUnivariate() const
87{
88    termList cursor = firstTerm;
89    while ( cursor )
90    {
91        if ( ! cursor->coeff.inCoeffDomain() )
92            return false;
93        cursor = cursor->next;
94    }
95    return true;
96}
97
98//{{{ int InternalPoly::degree ()
99// docu: see CanonicalForm::sign ()
100int
101InternalPoly::degree ()
102{
103    return firstTerm->exp;
104}
105//}}}
106
107//{{{ int InternalPoly::sign () const
108// docu: see CanonicalForm::sign()
109int
110InternalPoly::sign () const
111{
112    return firstTerm->coeff.sign();
113}
114//}}}
115
116//{{{ CanonicalForm InternalPoly::lc (), Lc (), LC ()
117// docu: see CanonicalForm::lc(), Lc(), LC()
118CanonicalForm
119InternalPoly::lc ()
120{
121    return firstTerm->coeff.lc();
122}
123
124CanonicalForm
125InternalPoly::Lc ()
126{
127    return firstTerm->coeff.Lc();
128}
129
130CanonicalForm
131InternalPoly::LC ()
132{
133    return firstTerm->coeff;
134}
135//}}}
136
137//{{{ CanonicalForm InternalPoly::tailcoeff (), int InternalPoly::taildegree ()
138// docu: see CanonicalForm::tailcoeff(), taildegree()
139CanonicalForm
140InternalPoly::tailcoeff ()
141{
142    return lastTerm->coeff;
143}
144
145int
146InternalPoly::taildegree ()
147{
148    return lastTerm->exp;
149}
150//}}}
151
152//{{{ CanonicalForm InternalPoly::coeff ( int i )
153// docu: see CanonicalForm::operator []()
154CanonicalForm
155InternalPoly::coeff ( int i )
156{
157    termList theCursor = firstTerm;
158    while ( theCursor )
159    {
160        if ( theCursor->exp == i )
161            return theCursor->coeff;
162        else if ( theCursor->exp < i )
163            return CanonicalForm( 0 );
164        else
165            theCursor = theCursor->next;
166    }
167    return CanonicalForm( 0 );
168}
169//}}}
170
171#ifndef NOSTREAMIO
172void
173InternalPoly::print(OSTREAM &aStream, char * aString )
174{
175    if ( ! firstTerm )
176        aStream << 0 << aString;
177    else
178    {
179        char * theString;
180        termList theCursor = firstTerm;
181        while ( theCursor )
182        {
183            ostrstream theStream;
184            if ( theCursor->exp == 0 )
185                theCursor->coeff.print( aStream, aString );
186            else  if ( theCursor->coeff.isOne() )
187            {
188                aStream << var;
189                if ( theCursor->exp != 1 )
190                    aStream << '^' << theCursor->exp << aString;
191                else
192                    aStream << aString;
193            }
194            else  if ( theCursor->coeff.sign() < 0 && (-theCursor->coeff).isOne() )
195            {
196                aStream << '-' << var;
197                if ( theCursor->exp != 1 )
198                    aStream << '^' << theCursor->exp << aString;
199                else
200                    aStream << aString;
201            }
202            else
203            {
204                theStream << '*' << var;
205                if ( theCursor->exp != 1 )
206                    theStream << '^' << theCursor->exp << aString << ends;
207                else
208                    theStream << aString << ends; // results from error in GNU strstream
209                theString = theStream.str();
210                theCursor->coeff.print( aStream, theString );
211                theStream.freeze(0);//delete [] theString;
212            }
213            theCursor = theCursor->next;
214            if ( theCursor && ( theCursor->coeff.sign() >= 0 ) )
215                aStream << '+';
216        }
217    }
218}
219#endif /* NOSTREAMIO */
220
221//{{{ InternalCF * InternalPoly::neg ()
222// docu: see CanonicalForm::operator -()
223InternalCF *
224InternalPoly::neg ()
225{
226    if ( getRefCount() <= 1 )
227    {
228        negateTermList( firstTerm );
229        return this;
230    }
231    else
232    {
233        decRefCount();
234        termList last, first = copyTermList( firstTerm, last, true );
235        return new InternalPoly( first, last, var );
236    }
237}
238//}}}
239
240InternalCF*
241InternalPoly::invert()
242{
243    if ( inExtension() && getReduce( var ) )
244    {
245        setReduce( var, false );
246        CanonicalForm a( this->copyObject() );
247        CanonicalForm b = getMipo( var );
248        CanonicalForm u, v;
249        CanonicalForm g = extgcd( a, b, u, v );
250        setReduce( var, true );
251        return u.getval();
252    }
253    else
254        return CFFactory::basic( 0 );
255}
256
257InternalCF*
258InternalPoly::addsame( InternalCF* aCoeff )
259{
260    InternalPoly * aPoly = (InternalPoly*)aCoeff;
261    if ( getRefCount() <= 1 )
262    {
263        firstTerm = addTermList( firstTerm, aPoly->firstTerm, lastTerm, false );
264        if ( firstTerm && firstTerm->exp != 0 )
265            return this;
266        else  if ( firstTerm )
267        {
268            InternalCF * res = firstTerm->coeff.getval();
269            delete this;
270            return res;
271        }
272        else
273        {
274            delete this;
275            return CFFactory::basic( 0 );
276        }
277    }
278    else
279    {
280        decRefCount();
281        termList last, first = copyTermList( firstTerm, last );
282        first = addTermList( first, aPoly->firstTerm, last, false );
283        if ( first && first->exp != 0 )
284            return new InternalPoly( first, last, var );
285        else  if ( first )
286        {
287            InternalCF * res = first->coeff.getval();
288            delete first;
289            return res;
290        }
291        else
292            return CFFactory::basic( 0 );
293
294    }
295}
296
297InternalCF*
298InternalPoly::subsame( InternalCF* aCoeff )
299{
300    InternalPoly * aPoly = (InternalPoly*)aCoeff;
301    if ( getRefCount() <= 1 )
302    {
303        firstTerm = addTermList( firstTerm, aPoly->firstTerm, lastTerm, true );
304        if ( firstTerm && firstTerm->exp != 0 )
305            return this;
306        else  if ( firstTerm )
307        {
308            InternalCF * res = firstTerm->coeff.getval();
309            delete this;
310            return res;
311        }
312        else
313        {
314            delete this;
315            return CFFactory::basic( 0 );
316        }
317    }
318    else
319    {
320        decRefCount();
321        termList last, first = copyTermList( firstTerm, last );
322        first = addTermList( first, aPoly->firstTerm, last, true );
323        if ( first && first->exp != 0 )
324            return new InternalPoly( first, last, var );
325        else  if ( first )
326        {
327            InternalCF * res = first->coeff.getval();
328            delete first;
329            return res;
330        }
331        else
332            return CFFactory::basic( 0 );
333
334    }
335}
336
337InternalCF*
338InternalPoly::mulsame( InternalCF* aCoeff )
339{
340    if (is_imm(aCoeff)) return mulcoeff(aCoeff);
341    InternalPoly *aPoly = (InternalPoly*)aCoeff;
342    termList resultFirst = 0, resultLast = 0;
343    termList theCursor = firstTerm;
344
345    while ( theCursor )
346    {
347        resultFirst = mulAddTermList( resultFirst, aPoly->firstTerm,
348                          theCursor->coeff, theCursor->exp, resultLast, false );
349        theCursor = theCursor->next;
350    }
351    if ( inExtension() && getReduce( var ) )
352    {
353        resultFirst = reduceTermList( resultFirst, (getInternalMipo( var ))->firstTerm, resultLast );
354        if ( resultFirst == 0 )
355        {
356            if ( getRefCount() <= 1 )
357            {
358                delete this;
359                return CFFactory::basic(0);
360            }
361            else
362            {
363                decRefCount();
364                return CFFactory::basic(0);
365            }
366        }
367        else  if ( resultFirst->exp == 0 )
368        {
369            if ( getRefCount() <= 1 )
370            {
371                InternalCF * res = resultFirst->coeff.getval();
372                delete resultFirst;
373                delete this;
374                return res;
375            }
376            else
377            {
378                decRefCount();
379                InternalCF * res = resultFirst->coeff.getval();
380                delete resultFirst;
381                return res;
382            }
383        }
384    }
385    if ( getRefCount() <= 1 )
386    {
387        freeTermList( firstTerm );
388        firstTerm = resultFirst;
389        lastTerm = resultLast;
390        return this;
391    }
392    else
393    {
394        decRefCount();
395        return new InternalPoly( resultFirst, resultLast, var );
396    }
397}
398
399InternalCF*
400InternalPoly::dividesame( InternalCF* aCoeff )
401{
402    return divsame( aCoeff );
403}
404
405
406InternalCF*
407InternalPoly::divsame( InternalCF* aCoeff )
408{
409    if ( inExtension() && getReduce( var ) )
410    {
411        InternalCF * dummy = aCoeff->invert();
412        if (is_imm(dummy)) dummy=this->mulsame(dummy);
413        else dummy = dummy->mulsame( this );
414        if ( getRefCount() <= 1 )
415        {
416             delete this;
417             return dummy;
418        }
419        else
420        {
421            decRefCount();
422            return dummy;
423        }
424    }
425    InternalPoly *aPoly = (InternalPoly*)aCoeff;
426    termList dummy, first, last, resultfirst = 0, resultlast = 0;
427    CanonicalForm coeff, newcoeff;
428    int exp, newexp;
429    bool singleObject;
430
431    if ( getRefCount() <= 1 )
432    {
433        first = firstTerm; last = lastTerm; singleObject = true;
434    }
435    else
436    {
437        first = copyTermList( firstTerm, last ); singleObject = false;
438        decRefCount();
439    }
440    coeff = aPoly->firstTerm->coeff;
441    exp = aPoly->firstTerm->exp;
442    while (first && ( first->exp >= exp ) )
443    {
444        newcoeff = first->coeff / coeff;
445        newexp = first->exp - exp;
446        dummy = first;
447        first = mulAddTermList( first->next, aPoly->firstTerm->next, newcoeff, newexp, last, true );
448        delete dummy;
449        appendTermList( resultfirst, resultlast, newcoeff, newexp );
450    }
451    freeTermList( first );
452    if ( singleObject )
453    {
454        if ( resultfirst && resultfirst->exp != 0 )
455        {
456            firstTerm = resultfirst;
457            lastTerm = resultlast;
458            return this;
459        }
460        else  if ( resultfirst )
461        {
462            InternalCF * res = resultfirst->coeff.getval();
463            delete resultfirst;
464            firstTerm = 0;
465            delete this;
466            return res;
467        }
468        else
469        {
470            // this should not happen (evtl use assertion)
471            ASSERT( 0, "FATAL ERROR, PLEASE INFORM THE AUTHOR" );
472            firstTerm = 0;
473            delete this;
474            return CFFactory::basic( 0 );
475        }
476    }
477    else
478    {
479        if ( resultfirst && resultfirst->exp != 0 )
480            return new InternalPoly( resultfirst, resultlast, var );
481        else  if ( resultfirst )
482        {
483            InternalCF * res = resultfirst->coeff.getval();
484            delete resultfirst;
485            return res;
486        }
487        else
488            return CFFactory::basic( 0 );
489    }
490}
491
492InternalCF*
493InternalPoly::modulosame( InternalCF* aCoeff )
494{
495    return modsame( aCoeff );
496}
497
498InternalCF*
499InternalPoly::modsame( InternalCF* aCoeff )
500{
501    if ( inExtension() && getReduce( var ) )
502    {
503        if ( deleteObject() ) delete this;
504        return CFFactory::basic( 0 );
505    }
506    InternalPoly *aPoly = (InternalPoly*)aCoeff;
507    termList dummy, first, last;
508    CanonicalForm coeff, newcoeff;
509    int exp, newexp;
510    bool singleObject;
511
512    if ( getRefCount() <= 1 )
513    {
514        first = firstTerm; last = lastTerm; singleObject = true;
515    }
516    else
517    {
518        first = copyTermList( firstTerm, last ); singleObject = false;
519        decRefCount();
520    }
521    coeff = aPoly->firstTerm->coeff;
522    exp = aPoly->firstTerm->exp;
523    while (first && ( first->exp >= exp ) )
524    {
525        newcoeff = first->coeff / coeff;
526        newexp = first->exp - exp;
527        dummy = first;
528        first = mulAddTermList( first->next, aPoly->firstTerm->next, newcoeff, newexp, last, true );
529        delete dummy;
530    }
531    if ( singleObject )
532    {
533        if ( first && first->exp != 0 )
534        {
535            firstTerm = first;
536            lastTerm = last;
537            return this;
538        }
539        else  if ( first )
540        {
541            InternalCF * res = first->coeff.getval();
542            delete first;
543            firstTerm = 0;
544            delete this;
545            return res;
546        }
547        else
548        {
549            firstTerm = 0;
550            delete this;
551            return CFFactory::basic( 0 );
552        }
553    }
554    else
555    {
556        if ( first && first->exp != 0 )
557            return new InternalPoly( first, last, var );
558        else  if ( first )
559        {
560            InternalCF * res = first->coeff.getval();
561            delete first;
562            return res;
563        }
564        else
565            return CFFactory::basic( 0 );
566    }
567}
568
569
570void
571InternalPoly::divremsame( InternalCF* acoeff, InternalCF*& quot, InternalCF*& rem )
572{
573    if ( inExtension() && getReduce( var ) )
574    {
575        InternalCF * dummy = acoeff->invert();
576        quot = dummy->mulsame( this );
577        rem = CFFactory::basic( 0 );
578    }
579    else
580    {
581        InternalPoly *aPoly = (InternalPoly*)acoeff;
582        termList dummy, first, last, resultfirst = 0, resultlast = 0;
583        CanonicalForm coeff, newcoeff;
584        int exp, newexp;
585
586        first = copyTermList( firstTerm, last );
587
588        coeff = aPoly->firstTerm->coeff;
589        exp = aPoly->firstTerm->exp;
590        while (first && ( first->exp >= exp ) )
591               {
592            newcoeff = first->coeff / coeff;
593            newexp = first->exp - exp;
594            dummy = first;
595            first = mulAddTermList( first->next, aPoly->firstTerm->next, newcoeff, newexp, last, true );
596            delete dummy;
597            appendTermList( resultfirst, resultlast, newcoeff, newexp );
598        }
599        if ( resultfirst )
600            if ( resultfirst->exp == 0 )
601            {
602                quot = resultfirst->coeff.getval();
603                delete resultfirst;
604            }
605            else
606                quot = new InternalPoly( resultfirst, resultlast, var );
607        else
608            quot = CFFactory::basic( 0 );
609        if ( first )
610            if ( first->exp == 0 )
611            {
612                rem = first->coeff.getval();
613                delete first;
614            }
615            else
616                rem = new InternalPoly( first, last, var );
617        else
618            rem = CFFactory::basic( 0 );
619    }
620}
621
622
623bool
624InternalPoly::divremsamet( InternalCF* acoeff, InternalCF*& quot, InternalCF*& rem )
625{
626    if ( inExtension() && getReduce( var ) )
627    {
628        divremsame( acoeff, quot, rem );
629        return true;
630    }
631    InternalPoly *aPoly = (InternalPoly*)acoeff;
632    termList dummy, first, last, resultfirst = 0, resultlast = 0;
633    CanonicalForm coeff, newcoeff, dummycoeff;
634    int exp, newexp;
635    bool divideok = true;
636
637//    if ( ! ::divremt( lastTerm->coeff, aPoly->lastTerm->coeff, newcoeff, dummycoeff ) )
638//        return false;
639
640    first = copyTermList( firstTerm, last );
641
642    coeff = aPoly->firstTerm->coeff;
643    exp = aPoly->firstTerm->exp;
644    while (first && ( first->exp >= exp ) && divideok )
645    {
646        divideok = divremt( first->coeff, coeff, newcoeff, dummycoeff );
647        if ( divideok && dummycoeff.isZero() )
648        {
649            newexp = first->exp - exp;
650            dummy = first;
651            first = mulAddTermList( first->next, aPoly->firstTerm->next, newcoeff, newexp, last, true );
652            delete dummy;
653            appendTermList( resultfirst, resultlast, newcoeff, newexp );
654        }
655        else
656            divideok = false;
657    }
658    if ( divideok )
659    {
660        if ( resultfirst )
661            if ( resultfirst->exp == 0 )
662            {
663                quot = resultfirst->coeff.getval();
664                delete resultfirst;
665            }
666            else
667                quot = new InternalPoly( resultfirst, resultlast, var );
668        else
669            quot = CFFactory::basic( 0 );
670        if ( first )
671            if ( first->exp == 0 )
672            {
673                rem = first->coeff.getval();
674                delete first;
675            }
676            else
677                rem = new InternalPoly( first, last, var );
678        else
679            rem = CFFactory::basic( 0 );
680    }
681    else
682    {
683        freeTermList( resultfirst );
684        freeTermList( first );
685    }
686    return divideok;
687}
688
689//{{{ int InternalPoly::comparesame, comparecoeff ( InternalCF * acoeff )
690//{{{ docu
691//
692// comparesame(), comparecoeff() - compare with an
693//   InternalPoly.
694//
695// comparecoeff() always returns 1 since CO is defined to be
696// larger than anything which is a coefficient w.r.t. CO.
697//
698// comparesame() compares the coefficient vectors of f=CO and
699// g=acoeff w.r.t to a lexicographic order in the following way:
700// f < g iff there exists an 0 <= i <= max(deg(f),deg(g)) s.t.
701// i) f[j] = g[j] for all i < j <= max(deg(f),deg(g)) and
702// ii) g[i] occurs in g (i.e. is not equal to zero) and
703//     f[i] does not occur in f or f[i] < g[i] if f[i] occurs
704// where f[i] denotes the coefficient to the power x^i of f.
705//
706// As usual, comparesame() returns 1 if CO is larger than c, 0 if
707// CO equals c, and -1 if CO is less than c.  However, this
708// function is optimized to test on equality since this is its
709// most important and frequent usage.
710//
711// See the respective `CanonicalForm'-methods for an explanation
712// why we define such a strange (but total) ordering on
713// polynomials.
714//
715// See also: CanonicalForm::operator <(), CanonicalForm::operator ==()
716//
717//}}}
718int
719InternalPoly::comparesame ( InternalCF * acoeff )
720{
721    ASSERT( ! ::is_imm( acoeff ) && acoeff->level() > LEVELBASE, "incompatible base coefficients" );
722    InternalPoly* apoly = (InternalPoly*)acoeff;
723    // check on triviality
724    if ( this == apoly )
725        return 0;
726    else
727    {
728        termList cursor1 = firstTerm;
729        termList cursor2 = apoly->firstTerm;
730        for ( ; cursor1 && cursor2; cursor1 = cursor1->next, cursor2 = cursor2->next )
731            // we test on inequality of coefficients at this
732            // point instead of testing on "less than" at the
733            // last `else' in the enclosed `if' statement since a
734            // test on inequaltiy in general is cheaper
735            if ( (cursor1->exp != cursor2->exp) || (cursor1->coeff != cursor2->coeff) )
736            {
737                if ( cursor1->exp > cursor2->exp )
738                    return 1;
739                else  if ( cursor1->exp < cursor2->exp )
740                    return -1;
741                else  if ( cursor1->coeff > cursor2->coeff )
742                    return 1;
743                else
744                    return -1;
745             }
746        // check trailing terms
747        if ( cursor1 == cursor2 )
748            return 0;
749        else if ( cursor1 != 0 )
750            return 1;
751        else
752            return -1;
753    }
754}
755
756int
757InternalPoly::comparecoeff ( InternalCF * )
758{
759    return 1;
760}
761//}}}
762
763InternalCF*
764InternalPoly::addcoeff( InternalCF* cc )
765{
766    CanonicalForm c( is_imm(cc) ? cc : cc->copyObject() );
767    if ( c.isZero() )
768        return this;
769    else
770    {
771        if ( getRefCount() <= 1 )
772        {
773            if ( lastTerm->exp == 0 )
774            {
775                lastTerm->coeff += c;
776                if ( lastTerm->coeff.isZero() )
777                {
778                    termList cursor = firstTerm;
779                    while ( cursor->next != lastTerm )
780                        cursor = cursor->next;
781                    delete lastTerm;
782                    cursor->next = 0;
783                    lastTerm = cursor;
784                }
785            }
786            else
787            {
788                lastTerm->next = new term( 0, c, 0 );
789                lastTerm = lastTerm->next;
790            }
791            return this;
792        }
793        else
794        {
795            decRefCount();
796            termList last, first = copyTermList( firstTerm, last, false );
797            if ( last->exp == 0 )
798            {
799                last->coeff += c;
800                if ( last->coeff.isZero() )
801                {
802                    termList cursor = first;
803                    while ( cursor->next != last )
804                        cursor = cursor->next;
805                    delete last;
806                    cursor->next = 0;
807                    last = cursor;
808                }
809            }
810            else
811            {
812                last->next = new term( 0, c, 0 );
813                last = last->next;
814            }
815            return new InternalPoly( first, last, var );
816        }
817    }
818}
819
820InternalCF*
821InternalPoly::subcoeff( InternalCF* cc, bool negate )
822{
823    CanonicalForm c( is_imm(cc) ? cc : cc->copyObject() );
824    if ( c.isZero() )
825        if ( getRefCount() > 1 )
826        {
827            decRefCount();
828            termList last, first = copyTermList( firstTerm, last, negate );
829            return new InternalPoly( first, last, var );
830        }
831        else
832        {
833            if ( negate )
834                negateTermList( firstTerm );
835            return this;
836        }
837    else
838    {
839        if ( getRefCount() <= 1 )
840        {
841            if ( lastTerm->exp == 0 )
842            {
843                if ( negate )
844                {
845                    negateTermList( firstTerm );
846                    lastTerm->coeff += c;
847                }
848                else
849                    lastTerm->coeff -= c;
850                if ( lastTerm->coeff.isZero() )
851                {
852                    termList cursor = firstTerm;
853                    while ( cursor->next != lastTerm )
854                        cursor = cursor->next;
855                    delete lastTerm;
856                    cursor->next = 0;
857                    lastTerm = cursor;
858                }
859            }
860            else
861            {
862                if ( negate )
863                {
864                    negateTermList( firstTerm );
865                    lastTerm->next = new term( 0, c, 0 );
866                }
867                else
868                    lastTerm->next = new term( 0, -c, 0 );
869                lastTerm = lastTerm->next;
870            }
871            return this;
872        }
873        else
874        {
875            decRefCount();
876            termList last, first = copyTermList( firstTerm, last, negate );
877            if ( last->exp == 0 )
878            {
879                if ( negate )
880                    last->coeff += c;
881                else
882                    last->coeff -= c;
883                if ( last->coeff.isZero() )
884                {
885                    termList cursor = first;
886                    while ( cursor->next != last )
887                        cursor = cursor->next;
888                    delete last;
889                    cursor->next = 0;
890                    last = cursor;
891                }
892            }
893            else
894            {
895                if ( negate )
896                    last->next = new term( 0, c, 0 );
897                else
898                    last->next = new term( 0, -c, 0 );
899                last = last->next;
900            }
901            return new InternalPoly( first, last, var );
902        }
903    }
904}
905
906InternalCF*
907InternalPoly::mulcoeff( InternalCF* cc )
908{
909    CanonicalForm c( is_imm(cc) ? cc : cc->copyObject() );
910    if ( c.isZero() )
911    {
912        if ( getRefCount() <= 1 )
913        {
914            delete this;
915            return CFFactory::basic( 0 );
916        }
917        else
918        {
919            decRefCount();
920            return CFFactory::basic( 0 );
921        }
922    }
923    else  if ( c.isOne() )
924        return this;
925    else
926    {
927        if ( getRefCount() <= 1 )
928        {
929            mulTermList( firstTerm, c, 0 );
930            return this;
931        }
932        else
933        {
934            decRefCount();
935            termList last, first = copyTermList( firstTerm, last );
936            mulTermList( first, c, 0 );
937            return new InternalPoly( first, last, var );
938        }
939    }
940}
941
942InternalCF*
943InternalPoly::dividecoeff( InternalCF* cc, bool invert )
944{
945    CanonicalForm c( is_imm(cc) ? cc : cc->copyObject() );
946    if ( inExtension() && getReduce( var ) && invert )
947    {
948        InternalCF * dummy;
949        dummy = this->invert();
950        if (is_imm(dummy))
951        {
952          if (is_imm(cc))
953          {
954            InternalInteger *d=new InternalInteger(imm2int(dummy)*imm2int(cc));
955            dummy=d;
956          }
957          else
958            dummy=cc->mulcoeff(dummy);
959        }
960        else dummy = dummy->mulcoeff( cc );
961        if ( getRefCount() <= 1 )
962        {
963            delete this;
964            return dummy;
965        }
966        else
967        {
968            decRefCount();
969            return dummy;
970        }
971    }
972    if ( invert )
973    {
974        if ( getRefCount() <= 1 )
975        {
976            delete this;
977            return CFFactory::basic( 0 );
978        }
979        else
980        {
981            decRefCount();
982            return CFFactory::basic( 0 );
983        }
984    }
985    if ( c.isOne() )
986        return this;
987    else
988    {
989        if ( getRefCount() <= 1 )
990        {
991            firstTerm = divideTermList( firstTerm, c, lastTerm );
992            if ( firstTerm && firstTerm->exp != 0 )
993                return this;
994            else  if ( firstTerm )
995            {
996                InternalCF * res = firstTerm->coeff.getval();
997                delete this;
998                return res;
999            }
1000            else
1001            {
1002                delete this;
1003                return CFFactory::basic( 0 );
1004            }
1005        }
1006        else
1007        {
1008            decRefCount();
1009            termList last, first = copyTermList( firstTerm, last );
1010            first = divideTermList( first, c, last );
1011            if ( first && first->exp != 0 )
1012                return new InternalPoly( first, last, var );
1013            else  if ( first )
1014            {
1015                InternalCF * res = first->coeff.getval();
1016                delete first;
1017                return res;
1018            }
1019            else
1020            {
1021                delete first;
1022                return CFFactory::basic( 0 );
1023            }
1024        }
1025    }
1026}
1027
1028InternalCF*
1029InternalPoly::divcoeff( InternalCF* cc, bool invert )
1030{
1031    CanonicalForm c( is_imm(cc) ? cc : cc->copyObject() );
1032    if ( inExtension() && getReduce( var ) && invert )
1033    {
1034        InternalCF * dummy;
1035        dummy = this->invert();
1036        dummy = dummy->mulcoeff( cc );
1037        if ( getRefCount() <= 1 )
1038        {
1039            delete this;
1040            return dummy;
1041        }
1042        else
1043        {
1044            decRefCount();
1045            return dummy;
1046        }
1047    }
1048    if ( invert )
1049    {
1050        if ( getRefCount() <= 1 )
1051        {
1052            delete this;
1053            return CFFactory::basic( 0 );
1054        }
1055        else
1056        {
1057            decRefCount();
1058            return CFFactory::basic( 0 );
1059        }
1060    }
1061    if ( c.isOne() )
1062        return this;
1063    else
1064    {
1065        if ( getRefCount() <= 1 )
1066        {
1067            firstTerm = divTermList( firstTerm, c, lastTerm );
1068            if ( firstTerm && firstTerm->exp != 0 )
1069                return this;
1070            else  if ( firstTerm )
1071            {
1072                InternalCF * res = firstTerm->coeff.getval();
1073                delete this;
1074                return res;
1075            }
1076            else
1077            {
1078                delete this;
1079                return CFFactory::basic( 0 );
1080            }
1081        }
1082        else
1083        {
1084            decRefCount();
1085            termList last, first = copyTermList( firstTerm, last );
1086            first = divTermList( first, c, last );
1087            if ( first && first->exp != 0 )
1088                return new InternalPoly( first, last, var );
1089            else  if ( first )
1090            {
1091                InternalCF * res = first->coeff.getval();
1092                delete first;
1093                return res;
1094            }
1095            else
1096            {
1097                delete first;
1098                return CFFactory::basic( 0 );
1099            }
1100        }
1101    }
1102}
1103
1104InternalCF*
1105InternalPoly::modulocoeff( InternalCF* cc, bool invert )
1106{
1107    CanonicalForm c( is_imm(cc) ? cc : cc->copyObject() );
1108    if ( invert )
1109    {
1110        if ( deleteObject() ) delete this;
1111        return c.getval();
1112    }
1113    ASSERT( ! c.isZero(), "divide by zero!" );
1114    if ( deleteObject() ) delete this;
1115    return CFFactory::basic( 0 );
1116}
1117
1118InternalCF*
1119InternalPoly::modcoeff( InternalCF* cc, bool invert )
1120{
1121    CanonicalForm c( is_imm(cc) ? cc : cc->copyObject() );
1122    if ( invert )
1123    {
1124        if ( deleteObject() ) delete this;
1125        return c.getval();
1126    }
1127    ASSERT( ! c.isZero(), "divide by zero!" );
1128    if ( c.isOne() )
1129    {
1130        if ( getRefCount() <= 1 )
1131        {
1132            delete this;
1133            return CFFactory::basic( 0 );
1134        }
1135        else
1136        {
1137            decRefCount();
1138            return CFFactory::basic( 0 );
1139        }
1140    }
1141    else
1142    {
1143        if ( getRefCount() <= 1 )
1144        {
1145            firstTerm = modTermList( firstTerm, c, lastTerm );
1146            if ( firstTerm && firstTerm->exp != 0 )
1147                return this;
1148            else  if ( firstTerm )
1149            {
1150                InternalCF * res = firstTerm->coeff.getval();
1151                delete this;
1152                return res;
1153            }
1154            else
1155            {
1156                delete this;
1157                return CFFactory::basic( 0 );
1158            }
1159        }
1160        else
1161        {
1162            decRefCount();
1163            termList last, first = copyTermList( firstTerm, last );
1164            first = modTermList( first, c, last );
1165            if ( first && first->exp != 0 )
1166                return new InternalPoly( first, last, var );
1167            else  if ( first )
1168            {
1169                InternalCF * res = first->coeff.getval();
1170                delete first;
1171                return res;
1172            }
1173            else
1174            {
1175                delete first;
1176                return CFFactory::basic( 0 );
1177            }
1178        }
1179    }
1180}
1181
1182void
1183InternalPoly::divremcoeff( InternalCF* cc, InternalCF*& quot, InternalCF*& rem, bool invert )
1184{
1185    if ( inExtension() && getReduce( var ) )
1186    {
1187        quot = copyObject();
1188        quot = quot->dividecoeff( cc, invert );
1189        rem = CFFactory::basic( 0 );
1190    }
1191    else  if ( invert )
1192    {
1193        if ( is_imm( cc ) )
1194            rem = cc;
1195        else
1196            rem = cc->copyObject();
1197        quot = CFFactory::basic( 0 );
1198    }
1199    else
1200    {
1201        CanonicalForm c( is_imm(cc) ? cc : cc->copyObject() );
1202        ASSERT( ! c.isZero(), "divide by zero!" );
1203        termList quotlast, quotfirst = copyTermList( firstTerm, quotlast );
1204        quotfirst = divideTermList( quotfirst, c, quotlast );
1205        if ( quotfirst )
1206            if ( quotfirst->exp == 0 )
1207            {
1208                quot = quotfirst->coeff.getval();
1209                delete quotfirst;
1210            }
1211            else
1212                quot = new InternalPoly( quotfirst, quotlast, var );
1213        else
1214            quot = CFFactory::basic( 0 );
1215        rem = CFFactory::basic( 0 );
1216    }
1217}
1218
1219bool
1220InternalPoly::divremcoefft( InternalCF* cc, InternalCF*& quot, InternalCF*& rem, bool invert )
1221{
1222    if ( inExtension() && getReduce( var ) )
1223    {
1224        quot = copyObject();
1225        quot = quot->dividecoeff( cc, invert );
1226        rem = CFFactory::basic( 0 );
1227        return true;
1228    }
1229    else  if ( invert )
1230    {
1231        if ( is_imm( cc ) )
1232            rem = cc;
1233        else
1234            rem = cc->copyObject();
1235        quot = CFFactory::basic( 0 );
1236        return true;
1237    }
1238    CanonicalForm c( is_imm(cc) ? cc : cc->copyObject() );
1239    ASSERT( ! c.isZero(), "divide by zero!" );
1240    termList quotfirst, quotcursor;
1241    termList cursor;
1242    CanonicalForm cquot, crem;
1243    bool divideok = true;
1244
1245    cursor = firstTerm;
1246    quotcursor = quotfirst = new term;
1247
1248    while ( cursor && divideok )
1249    {
1250        divideok = divremt( cursor->coeff, c, cquot, crem );
1251        divideok = divideok && crem.isZero();
1252        if ( divideok )
1253        {
1254            if ( ! cquot.isZero() )
1255            {
1256                quotcursor->next = new term( 0, cquot, cursor->exp );
1257                quotcursor = quotcursor->next;
1258            }
1259            cursor = cursor->next;
1260        }
1261    }
1262    quotcursor->next = 0;
1263    if ( divideok )
1264    {
1265        cursor = quotfirst; quotfirst = quotfirst->next; delete cursor;
1266        if ( quotfirst )
1267            if ( quotfirst->exp == 0 )
1268            {
1269                quot = quotfirst->coeff.getval();
1270                delete quotfirst;
1271            }
1272            else
1273                quot = new InternalPoly( quotfirst, quotcursor, var );
1274        else
1275            quot = CFFactory::basic( 0 );
1276        rem = CFFactory::basic( 0 );
1277    }
1278    else
1279    {
1280        freeTermList( quotfirst );
1281    }
1282    return divideok;
1283}
1284
1285// static functions
1286
1287termList
1288InternalPoly::copyTermList ( termList aTermList, termList& theLastTerm, bool negate )
1289{
1290    if ( aTermList == 0 )
1291        return 0;
1292    else  if ( negate )
1293    {
1294        termList sourceCursor = aTermList;
1295        termList dummy = new term;
1296        termList targetCursor = dummy;
1297
1298        while ( sourceCursor )
1299        {
1300            targetCursor->next = new term( 0, -sourceCursor->coeff, sourceCursor->exp );
1301            targetCursor = targetCursor->next;
1302            sourceCursor = sourceCursor->next;
1303        }
1304        targetCursor->next = 0;
1305        theLastTerm = targetCursor;
1306        targetCursor = dummy->next;
1307        delete dummy;
1308        return targetCursor;
1309    }
1310    else
1311    {
1312        termList sourceCursor = aTermList;
1313        termList dummy = new term;
1314        termList targetCursor = dummy;
1315
1316        while ( sourceCursor )
1317        {
1318            targetCursor->next = new term( 0, sourceCursor->coeff, sourceCursor->exp );
1319            targetCursor = targetCursor->next;
1320            sourceCursor = sourceCursor->next;
1321        }
1322        targetCursor->next = 0;
1323        theLastTerm = targetCursor;
1324        targetCursor = dummy->next;
1325        delete dummy;
1326        return targetCursor;
1327    }
1328}
1329
1330termList
1331InternalPoly::deepCopyTermList ( termList aTermList, termList& theLastTerm )
1332{
1333    if ( aTermList == 0 )
1334        return 0;
1335    else
1336    {
1337        termList sourceCursor = aTermList;
1338        termList dummy = new term;
1339        termList targetCursor = dummy;
1340
1341        while ( sourceCursor )
1342        {
1343            targetCursor->next = new term( 0, sourceCursor->coeff.deepCopy(), sourceCursor->exp );
1344            targetCursor = targetCursor->next;
1345            sourceCursor = sourceCursor->next;
1346        }
1347        targetCursor->next = 0;
1348        theLastTerm = targetCursor;
1349        targetCursor = dummy->next;
1350        delete dummy;
1351        return targetCursor;
1352    }
1353}
1354
1355void
1356InternalPoly::freeTermList ( termList aTermList )
1357{
1358    termList cursor = aTermList;
1359
1360    while ( cursor )
1361    {
1362        cursor = cursor->next;
1363        delete aTermList;
1364        aTermList = cursor;
1365    }
1366}
1367
1368void
1369InternalPoly::negateTermList ( termList terms )
1370{
1371    termList cursor = terms;
1372    while ( cursor )
1373    {
1374        cursor->coeff = -cursor->coeff;
1375        cursor = cursor->next;
1376    }
1377}
1378
1379termList
1380InternalPoly::addTermList ( termList theList, termList aList, termList& lastTerm, bool negate )
1381{
1382    termList theCursor = theList;
1383    termList aCursor = aList;
1384    termList predCursor = 0;
1385
1386    while ( theCursor && aCursor )
1387    {
1388        if ( theCursor->exp == aCursor->exp )
1389        {
1390            if ( negate )
1391                theCursor->coeff -= aCursor->coeff;
1392            else
1393                theCursor->coeff += aCursor->coeff;
1394            if ( theCursor->coeff.isZero() )
1395            {
1396                if ( predCursor )
1397                {
1398                    predCursor->next = theCursor->next;
1399                    delete theCursor;
1400                    theCursor = predCursor->next;
1401                }
1402                else
1403                {
1404                    theList = theList->next;
1405                    delete theCursor;
1406                    theCursor = theList;
1407                }
1408            }
1409            else
1410            {
1411                predCursor = theCursor;
1412                theCursor = theCursor->next;
1413            }
1414            aCursor = aCursor->next;
1415        }
1416        else if ( theCursor->exp < aCursor->exp )
1417        {
1418            if ( negate )
1419                if ( predCursor )
1420                {
1421                    predCursor->next = new term( theCursor, -aCursor->coeff, aCursor->exp );
1422                    predCursor = predCursor->next;
1423                }
1424                else
1425                {
1426                    theList = new term( theCursor, -aCursor->coeff, aCursor->exp );
1427                    predCursor = theList;
1428                }
1429            else
1430                if ( predCursor )
1431                {
1432                    predCursor->next = new term( theCursor, aCursor->coeff, aCursor->exp );
1433                    predCursor = predCursor->next;
1434                }
1435                else
1436                {
1437                    theList = new term( theCursor, aCursor->coeff, aCursor->exp );
1438                    predCursor = theList;
1439                }
1440            aCursor = aCursor->next;
1441        }
1442        else
1443        {
1444            predCursor = theCursor;
1445            theCursor = theCursor->next;
1446        }
1447    }
1448    if ( aCursor )
1449    {
1450        if ( predCursor )
1451            predCursor->next = copyTermList( aCursor, lastTerm, negate );
1452        else
1453            theList = copyTermList( aCursor, lastTerm, negate );
1454    }
1455    else if ( ! theCursor )
1456        lastTerm = predCursor;
1457
1458    return theList;
1459}
1460
1461void
1462InternalPoly::mulTermList ( termList theCursor, const CanonicalForm& coeff, const int exp )
1463{
1464    while ( theCursor )
1465    {
1466        theCursor->coeff *= coeff;
1467        theCursor->exp += exp;
1468        theCursor = theCursor->next;
1469    }
1470}
1471
1472termList
1473InternalPoly::divideTermList ( termList firstTerm, const CanonicalForm& coeff, termList& lastTerm )
1474{
1475    termList theCursor = firstTerm;
1476    lastTerm = 0;
1477    termList dummy;
1478
1479    while ( theCursor )
1480    {
1481        theCursor->coeff /= coeff;
1482        if ( theCursor->coeff.isZero() )
1483        {
1484            if ( theCursor == firstTerm )
1485                firstTerm = theCursor->next;
1486            else
1487                lastTerm->next = theCursor->next;
1488            dummy = theCursor;
1489            theCursor = theCursor->next;
1490            delete dummy;
1491        }
1492        else
1493        {
1494            lastTerm = theCursor;
1495            theCursor = theCursor->next;
1496        }
1497    }
1498    return firstTerm;
1499}
1500
1501termList
1502InternalPoly::divTermList ( termList firstTerm, const CanonicalForm& coeff, termList& lastTerm )
1503{
1504    termList theCursor = firstTerm;
1505    lastTerm = 0;
1506    termList dummy;
1507
1508    while ( theCursor )
1509    {
1510        theCursor->coeff.div( coeff );
1511        if ( theCursor->coeff.isZero() )
1512        {
1513            if ( theCursor == firstTerm )
1514                firstTerm = theCursor->next;
1515            else
1516                lastTerm->next = theCursor->next;
1517            dummy = theCursor;
1518            theCursor = theCursor->next;
1519            delete dummy;
1520        }
1521        else
1522        {
1523            lastTerm = theCursor;
1524            theCursor = theCursor->next;
1525        }
1526    }
1527    return firstTerm;
1528}
1529
1530termList
1531InternalPoly::modTermList ( termList firstTerm, const CanonicalForm& coeff, termList& lastTerm )
1532{
1533    termList theCursor = firstTerm;
1534    lastTerm = 0;
1535    termList dummy;
1536
1537    while ( theCursor )
1538    {
1539        theCursor->coeff.mod( coeff );
1540        if ( theCursor->coeff.isZero() )
1541        {
1542            if ( theCursor == firstTerm )
1543                firstTerm = theCursor->next;
1544            else
1545                lastTerm->next = theCursor->next;
1546            dummy = theCursor;
1547            theCursor = theCursor-> next;
1548            delete dummy;
1549        }
1550        else
1551        {
1552            lastTerm = theCursor;
1553            theCursor = theCursor->next;
1554        }
1555    }
1556    return firstTerm;
1557}
1558
1559void
1560InternalPoly::appendTermList ( termList& first, termList& last, const CanonicalForm& coeff, const int exp )
1561{
1562    if ( last )
1563    {
1564        last->next = new term( 0, coeff, exp );
1565        last = last->next;
1566    }
1567    else
1568    {
1569        first = new term( 0, coeff, exp );
1570        last = first;
1571    }
1572}
1573
1574termList
1575InternalPoly::mulAddTermList ( termList theList, termList aList, const CanonicalForm & c, const int exp, termList & lastTerm, bool negate )
1576{
1577    termList theCursor = theList;
1578    termList aCursor = aList;
1579    termList predCursor = 0;
1580    CanonicalForm coeff;
1581
1582    if ( negate )
1583        coeff = -c;
1584    else
1585        coeff = c;
1586
1587    while ( theCursor && aCursor )
1588    {
1589        if ( theCursor->exp == aCursor->exp + exp )
1590        {
1591            theCursor->coeff += aCursor->coeff * coeff;
1592            if ( theCursor->coeff.isZero() )
1593            {
1594                if ( predCursor )
1595                {
1596                    predCursor->next = theCursor->next;
1597                    delete theCursor;
1598                    theCursor = predCursor->next;
1599                }
1600                else
1601                {
1602                    theList = theList->next;
1603                    delete theCursor;
1604                    theCursor = theList;
1605                }
1606            }
1607            else
1608            {
1609                predCursor = theCursor;
1610                theCursor = theCursor->next;
1611            }
1612            aCursor = aCursor->next;
1613        }
1614        else if ( theCursor->exp < aCursor->exp + exp )
1615        {
1616            if ( predCursor )
1617            {
1618                predCursor->next = new term( theCursor, aCursor->coeff * coeff, aCursor->exp + exp );
1619                predCursor = predCursor->next;
1620            }
1621            else
1622            {
1623                theList = new term( theCursor, aCursor->coeff * coeff, aCursor->exp + exp );
1624                predCursor = theList;
1625            }
1626            aCursor = aCursor->next;
1627        }
1628        else
1629        {
1630            predCursor = theCursor;
1631            theCursor = theCursor->next;
1632        }
1633    }
1634    if ( aCursor )
1635    {
1636        if ( predCursor )
1637        {
1638            predCursor->next = copyTermList( aCursor, lastTerm );
1639            predCursor = predCursor->next;
1640        }
1641        else
1642        {
1643            theList = copyTermList( aCursor, lastTerm );
1644            predCursor = theList;
1645        }
1646        while ( predCursor )
1647        {
1648            predCursor->exp += exp;
1649            predCursor->coeff *= coeff;
1650            predCursor = predCursor->next;
1651        }
1652    }
1653    else if ( ! theCursor )
1654        lastTerm = predCursor;
1655    return theList;
1656}
1657
1658termList
1659InternalPoly::reduceTermList ( termList first, termList redterms, termList & last )
1660{
1661    CanonicalForm coeff = redterms->coeff;
1662    CanonicalForm newcoeff;
1663    int newexp;
1664    int exp = redterms->exp;
1665    termList dummy;
1666    while ( first && ( first->exp >= exp ) )
1667    {
1668        newcoeff = first->coeff / coeff;
1669        newexp = first->exp - exp;
1670        dummy = first;
1671        first = mulAddTermList( first->next, redterms->next, newcoeff, newexp, last, true );
1672        delete dummy;
1673    }
1674    return first;
1675}
Note: See TracBrowser for help on using the repository browser.