Changeset 9952bd in git


Ignore:
Timestamp:
Sep 10, 2012, 2:13:09 PM (10 years ago)
Author:
Oleksandr Motsak <motsak@…>
Branches:
(u'jengelh-datetime', 'ceac47cbc86fe4a15902392bdbb9bd2ae0ea02c6')(u'spielwiese', 'ad2543eab51733612ba7d118afc77edca719600e')
Children:
8d341e5425f8b7b26cdf77eec4ee78cbbb121c5c
Parents:
6dffa9e5b66ac5a81df2b68ff1c38dafc918b1f9
Message:
Changed enumerators to handle empty sets just like C# does

chg: enumerators handle empty sets just like C# does (together with Alexander Dreyer and Bjarke Roune)
fix: fixed comments for the above change
chg: adaptation of and minor changes to n[dl]Clear* implementations
add: introduced IBaseEnumerator::IsValid() = 0 (right now - for debug purpose only)
Location:
libpolys
Files:
1 added
6 edited

Legend:

Unmodified
Added
Removed
  • libpolys/coeffs/Enumerator.h

    r6dffa9 r9952bd  
    2222/** @class IBaseEnumerator
    2323 *
    24  * Base enumerator interface for simple iteration over a generic non-empty collection.
    25  *
    26  * Abstract API of enumerators for non-empty enumerable collections of standalone
    27  * objects. Inspired by IEnumerator from C#. Usage parrten can be as
    28  * follows:
     24 * Base enumerator interface for simple iteration over a generic collection.
     25 *
     26 * Abstract API of enumerators for enumerable collections of standalone objects.
     27 * Just like IEnumerator from C#. Usage pattern can be as follows:
    2928 *
    3029 * @code
    31  *   IBaseEnumerator itr = ...;
    32  *   itr.Reset(); // goes to the first element (must exist)
    33  *   do
     30 *   IBaseEnumerator& itr = ...;
     31 *   itr.Reset(); // goes to the "-1" element
     32 *   // NOTE: itr is not useable here!
     33 *   while( itr.MoveNext() )
    3434 *   {
    3535 *      do something custom with itr...
    3636 *   }
    37  *   while( itr.MoveNext() )
    3837 * @endcode
    3938 *
    40  * Note that the first element must exist and available directly after Reset() call.
     39 * Note that the Reset()
    4140 *
    4241 * @sa IEnumerator
     
    5150    virtual bool MoveNext() = 0;   
    5251
    53     /// Sets the enumerator to its initial position, which is at the first element in the collection.
     52    /// Sets the enumerator to its initial position: -1,
     53    /// which is before the first element in the collection.
    5454    virtual void Reset() = 0;
    55 //    virtual ~IEnumerator() {} // TODO: needed?
     55
     56    virtual ~IBaseEnumerator() {} // TODO: needed?
     57
     58  private:
     59    IBaseEnumerator(const IBaseEnumerator&);
     60    void operator=(const IBaseEnumerator&);
     61
     62  protected:
     63    IBaseEnumerator(){}
     64
     65    /// Current position is inside the collection (not -1 or past the end)
     66    virtual bool IsValid() const = 0;
    5667};
    5768
     
    7889    /// Gets the current element in the collection (read only).
    7990    virtual const_reference Current() const = 0;
     91
     92    virtual ~IAccessor() {} // TODO: needed?
     93 
    8094};
    8195
    8296/** @class IEnumerator
    8397 *
    84  * Templated enumerator interface for simple iteration over a generic non-empty collection of T's.
    85  *
    86  * Abstract API of enumerators for non-empty enumerable collections of standalone
    87  * objects. Inspired by IEnumerator from C#. Usage parrten can be as
     98 * Templated enumerator interface for simple iteration over a generic collection of T's.
     99 *
     100 * Abstract API of enumerators for generic enumerable collections of standalone
     101 * objects of type T. Inspired by IEnumerator from C#. Usage parrten can be as
    88102 * follows:
    89103 *
    90104 * @code
    91  *   IEnumerator<T> itr = ...;
    92  *   itr.Reset(); // goes to the first element (must exist)
    93  *   do
     105 *   IEnumerator<T>& itr = ...;
     106 *   
     107 *   itr.Reset(); // goes before the first element, thus no itr.Current() is available here!
     108 *   
     109 *   while( itr.MoveNext() )
    94110 *   {
    95111 *      use/change itr.Current()...
    96112 *   }
    97  *   while( itr.MoveNext() )
    98113 * @endcode
    99114 *
  • libpolys/coeffs/longrat.cc

    r6dffa9 r9952bd  
    26452645  assume(cf != NULL);
    26462646  assume(getCoeffType(cf) == ID);
     2647
     2648  numberCollectionEnumerator.Reset();
     2649
     2650  if( !numberCollectionEnumerator.MoveNext() ) // empty zero polynomial?
     2651  {
     2652    c = n_Init(1, cf);
     2653    return;
     2654  }
     2655 
    26472656  // all coeffs are given by integers!!!
    26482657
     
    26512660  int s1,s;
    26522661  s=2147483647; // max. int
    2653   numberCollectionEnumerator.Reset();
     2662
     2663 
    26542664  int lc_is_pos=nlGreaterZero(numberCollectionEnumerator.Current(),cf);
     2665
     2666  int normalcount = 0;
    26552667  do
    26562668  {
    2657     cand1= numberCollectionEnumerator.Current();
    2658     if (SR_HDL(cand1)&SR_INT) { cand=cand1;break;}
    2659     assume(cand1->s==3); // all coeffs should be integers
     2669    number& n = numberCollectionEnumerator.Current();
     2670    nlNormalize(n, cf); ++normalcount;
     2671    cand1 = n;
     2672   
     2673    if (SR_HDL(cand1)&SR_INT) { cand=cand1; break; }
     2674    assume(cand1->s==3); // all coeffs should be integers // ==0?!! after printing
    26602675    s1=mpz_size1(cand1->z);
    26612676    if (s>s1)
     
    26662681  } while (numberCollectionEnumerator.MoveNext() );
    26672682
     2683//  assume( nlGreaterZero(cand,cf) ); // cand may be a negative integer!
     2684
    26682685  cand=nlCopy(cand,cf);
    26692686  // part 2: compute gcd(cand,all coeffs)
     2687
    26702688  numberCollectionEnumerator.Reset();
    2671   do
    2672   {
    2673     nlNormalize(numberCollectionEnumerator.Current(),cf);
    2674     nlInpGcd(cand,numberCollectionEnumerator.Current(),cf);
     2689 
     2690  while (numberCollectionEnumerator.MoveNext() )
     2691  {
     2692    number& n = numberCollectionEnumerator.Current();
     2693
     2694    if( (--normalcount) <= 0)
     2695      nlNormalize(n, cf);
     2696
     2697    nlInpGcd(cand, n, cf);
     2698
     2699    assume( nlGreaterZero(cand,cf) );
     2700   
    26752701    if(nlIsOne(cand,cf))
    26762702    {
    2677       c=cand;
     2703      c = cand;
     2704
    26782705      if(!lc_is_pos)
    26792706      {
    26802707        // make the leading coeff positive
    2681         c=nlNeg(c,cf);
     2708        c = nlNeg(c, cf);
    26822709        numberCollectionEnumerator.Reset();
    2683         do
     2710       
     2711        while (numberCollectionEnumerator.MoveNext() )
    26842712        {
    2685           numberCollectionEnumerator.Current()=nlNeg(numberCollectionEnumerator.Current(),cf);
    2686         } while (numberCollectionEnumerator.MoveNext() );
     2713          number& nn = numberCollectionEnumerator.Current();
     2714          nn = nlNeg(nn, cf);
     2715        }
    26872716      }
    26882717      return;
    26892718    }
    2690   } while (numberCollectionEnumerator.MoveNext() );
     2719  }
    26912720
    26922721  // part3: all coeffs = all coeffs / cand
    2693   if (!lc_is_pos) cand=nlNeg(cand,cf);
    2694   c=cand;
     2722  if (!lc_is_pos)
     2723    cand = nlNeg(cand,cf);
     2724 
     2725  c = cand;
    26952726  numberCollectionEnumerator.Reset();
    2696   do
    2697   {
    2698     number t=nlIntDiv(numberCollectionEnumerator.Current(),cand,cf);
    2699     nlDelete(&numberCollectionEnumerator.Current(),cf);
    2700     numberCollectionEnumerator.Current()=t;
    2701   } while (numberCollectionEnumerator.MoveNext() );
    2702 
     2727
     2728  while (numberCollectionEnumerator.MoveNext() )
     2729  {
     2730    number& n = numberCollectionEnumerator.Current();
     2731    number t=nlIntDiv(n, cand, cf); // simple integer exact division, no ratios to remain
     2732    nlDelete(&n, cf);
     2733    n = t;
     2734  }
    27032735}
    27042736
     
    27072739  assume(cf != NULL);
    27082740  assume(getCoeffType(cf) == ID);
     2741
     2742  numberCollectionEnumerator.Reset();
     2743 
     2744  if( !numberCollectionEnumerator.MoveNext() ) // empty zero polynomial?
     2745  {
     2746    c = n_Init(1, cf);
     2747    return;
     2748  }
     2749
    27092750  // all coeffs are given by integers after returning from this routine
    27102751
     
    27122753  number cand;
    27132754  cand=ALLOC_RNUMBER();
    2714   #if defined(LDEBUG)
     2755#if defined(LDEBUG)
    27152756  cand->debug=123456;
    2716   #endif
     2757#endif
    27172758  cand->s=3;
    27182759
    27192760  int s=0;
    2720   mpz_t tmp;
    2721   mpz_init(tmp);
    2722   numberCollectionEnumerator.Reset();
     2761//  mpz_t tmp; mpz_init(tmp); // tmp = GMP int
     2762 
    27232763  int lc_is_pos=nlGreaterZero(numberCollectionEnumerator.Current(),cf);
     2764
    27242765  do
    27252766  {
     
    27302771      nlNormalize(cand1, cf);
    27312772      if ((!(SR_HDL(cand1)&SR_INT)) // not a short int
    2732       && (cand1->s==1))             // and is rational
     2773      && (cand1->s==1))             // and is a normalised rational
    27332774      {
    27342775        if (s==0) // first denom, we meet
    27352776        {
    2736           mpz_init_set(cand->z,cand1->n);
     2777          mpz_init_set(cand->z, cand1->n); // cand->z = cand1->n
    27372778          s=1;
    27382779        }
    27392780        else // we have already something
    27402781        {
    2741           mpz_gcd(tmp,cand->z,cand1->n);
    2742           if (mpz_cmp_si(tmp,1)!=0)
    2743           {
    2744             mpz_divexact(cand->z,cand->z,tmp);
    2745           }
    2746           mpz_mul(cand->z,cand->z,cand1->n);
     2782          mpz_lcm(cand->z, cand->z, cand1->n);
     2783/*                 
     2784          mpz_gcd(tmp,cand->z,cand1->n); // tmp = GCD( cand->z, cand1->n )
     2785         
     2786          if (mpz_cmp_si(tmp,1)!=0)
     2787            mpz_divexact(cand->z,cand->z,tmp); // cand->z /= tmp
     2788         
     2789          mpz_mul(cand->z,cand->z,cand1->n); // cand->z *= cand1->n
     2790*/
    27472791        }
    27482792      }
    27492793    }
    2750   } while (numberCollectionEnumerator.MoveNext() );
     2794  }
     2795  while (numberCollectionEnumerator.MoveNext() );
     2796 
    27512797
    27522798  if (s==0) // nothing to do, all coeffs are already integers
    27532799  {
    2754     mpz_clear(tmp);
     2800//    mpz_clear(tmp);
    27552801    FREE_RNUMBER(cand);
    27562802    if (lc_is_pos)
     
    27602806      // make the leading coeff positive
    27612807      c=nlInit(-1,cf);
     2808
     2809      // TODO: incorporate the following into the loop below?
    27622810      numberCollectionEnumerator.Reset();
    2763       do
    2764       {
    2765         numberCollectionEnumerator.Current()=nlNeg(numberCollectionEnumerator.Current(),cf);
    2766       } while (numberCollectionEnumerator.MoveNext() );
     2811      while (numberCollectionEnumerator.MoveNext() )
     2812      {
     2813        number& n = numberCollectionEnumerator.Current();
     2814        n = nlNeg(n, cf);
     2815      }
    27672816    }
    27682817    return;
    27692818  }
    2770   cand=nlShort3(cand);
     2819
     2820  cand = nlShort3(cand);
    27712821
    27722822  // part2: all coeffs = all coeffs * cand
    27732823  // make the lead coeff positive
    27742824  numberCollectionEnumerator.Reset();
    2775   if (!nlGreaterZero(numberCollectionEnumerator.Current(),cf))
    2776   {
    2777     cand=nlNeg(cand,cf);
    2778   }
     2825 
     2826  if (!lc_is_pos)
     2827    cand = nlNeg(cand, cf);
     2828 
    27792829  c = cand;
    2780   do
     2830 
     2831  while (numberCollectionEnumerator.MoveNext() )
    27812832  {
    27822833    number &n = numberCollectionEnumerator.Current();
    27832834    n_InpMult(n, cand, cf);
    2784   } while (numberCollectionEnumerator.MoveNext() );
     2835  }
    27852836
    27862837}
  • libpolys/coeffs/numbers.cc

    r6dffa9 r9952bd  
    131131  assume(!(  nCoeff_is_Q(r) || nCoeff_is_Q_a(r) ));
    132132  // all coeffs are given by integers!!!
    133   assume( nCoeff_is_Ring(r) || nCoeff_is_Zp(r) || nCoeff_is_numeric(r) || nCoeff_is_GF(r) || nCoeff_is_Zp_a(r) );
    134133
    135134  numberCollectionEnumerator.Reset();
     135
     136  if( !numberCollectionEnumerator.MoveNext() ) // empty zero polynomial?
     137  {
     138    c = n_Init(1, r);
     139    return;
     140  } 
     141
     142  number &curr = numberCollectionEnumerator.Current();
    136143 
    137144#ifdef HAVE_RINGS
     
    141148    if (nCoeff_has_Units(r))
    142149    {
    143       c = n_GetUnit(numberCollectionEnumerator.Current(), r);
     150      c = n_GetUnit(curr, r);
    144151     
    145152      if (!n_IsOne(c, r))
     
    147154        number inv = n_Invers(c, r);
    148155
    149         do
     156        n_InpMult(curr, inv, r);
     157       
     158        while( numberCollectionEnumerator.MoveNext() )
    150159        {
    151           n_InpMult(numberCollectionEnumerator.Current(), inv, r);
     160          number &n = numberCollectionEnumerator.Current();
     161          n_Normalize(n, r); // ?
     162          n_InpMult(n, inv, r); // TODO: either this or directly divide!!!?
    152163        }
    153         while( numberCollectionEnumerator.MoveNext() );
    154164
    155165        n_Delete(&inv, r);       
     
    162172
    163173  assume(!nCoeff_is_Ring(r));
    164 
    165   c = numberCollectionEnumerator.Current();
     174  assume(nCoeff_is_Zp(r) || nCoeff_is_numeric(r) || nCoeff_is_GF(r) || nCoeff_is_Zp_a(r));
     175
     176  c = curr;
    166177 
    167178  n_Normalize(c, r);
     
    169180  if (!n_IsOne(c, r))
    170181  {   
    171     numberCollectionEnumerator.Current() = n_Init(1, r); // ???
     182    curr = n_Init(1, r); // ???
    172183   
    173184    number inv = n_Invers(c, r);
     
    177188      number &n = numberCollectionEnumerator.Current();
    178189      n_Normalize(n, r); // ?
    179       n_InpMult(n, inv, r);
     190      n_InpMult(n, inv, r); // TODO: either this or directly divide!!!?
    180191    }
    181192   
  • libpolys/polys/Makefile.am

    r6dffa9 r9952bd  
    4848        ext_fields/algext.cc ext_fields/transext.cc \
    4949        clapsing.cc clapconv.cc \
    50         nc/old.gring.cc
     50        nc/old.gring.cc PolyEnumerator.cc
    5151
    5252LIBPOLYSHEADERS = monomials/ring.h monomials/monomials.h \
  • libpolys/polys/PolyEnumerator.h

    r6dffa9 r9952bd  
    1919#include <coeffs/Enumerator.h>
    2020#include <polys/monomials/monomials.h>
     21#include <reporter/reporter.h> // for assume etc.
    2122
    2223/** @class CBasePolyEnumerator
    2324 *
    24  * Base polynomial enumerator for simple iteration over terms of
    25  * (non-zero) polynomials.
     25 * Base polynomial enumerator for simple iteration over terms of polynomials.
    2626 *
    27  * Note that the first element must exist directly after Reset() call.
    28  * Moreover, it doesn't inherit from IAccessor and thus doesn't
    29  * override Current().
     27 * Note that the first element desn't exist directly after Reset() call.
     28 *
     29 * The class doesn't inherit from IAccessor and thus doesn't override Current().
    3030 *
    3131 * @sa IBaseEnumerator, @sa CPolyCoeffsEnumerator
     
    3434{
    3535  private:
    36     const poly m_poly;
     36    const poly m_poly; ///< essentially immutable original iterable object
     37   
     38    static const spolyrec m_prevposition_struct; ///< tag for "-1" position
    3739
    3840  protected:
    39     poly m_position;
     41    poly m_position; ///< current position in the iterable object
     42
     43    virtual bool IsValid() const
     44    {
     45      // not -1 or past the end position?
     46      return (m_position != NULL) && (m_position != &m_prevposition_struct);
     47    }
    4048   
    41     inline void Iterate()
     49  public:
     50    CBasePolyEnumerator(poly p):
     51        IBaseEnumerator(), m_poly(p), m_position(const_cast<poly>(&m_prevposition_struct))
    4252    {
    43       if( m_position != NULL )
    44         pIter( m_position );
    45     }   
    46   public:
    47     CBasePolyEnumerator(poly p): m_poly(p), m_position(p) { assume(p != NULL); }
     53      assume( !IsValid() );
     54    }
    4855   
    4956    /// Sets the position marker to the leading term.
    50     virtual void Reset() { assume(m_poly!= NULL); m_position = m_poly; }
     57    virtual void Reset()
     58    {
     59      m_position = const_cast<poly>(&m_prevposition_struct);
     60      assume( !IsValid() );
     61    }
    5162
    5263    /// Advances the position to the next term of the polynomial.
    5364    /// returns true if the position marker was successfully advanced to the
    54     /// next term;
     65    /// next term which can be used;
    5566    /// false if the position marker has passed the end of the
    5667    /// polynomial.
     
    5869    {
    5970      assume( m_position != NULL );
    60       Iterate();
    61       return (m_position != NULL);
     71
     72      {
     73        const poly p_next = pNext(m_position);
     74
     75        if (p_next != NULL) // not the last term?
     76        {
     77          m_position = p_next;
     78          assume( IsValid() );
     79          return true;
     80        }
     81      }
     82     
     83      if (m_position == &m_prevposition_struct) // -1 position?
     84      {
     85        assume( !IsValid() );
     86        m_position = m_poly;
     87        return (m_position != NULL);
     88      }
     89
     90      // else: past the end (or an empty polynomial)
     91      m_position = NULL;
     92      assume( !IsValid() );
     93      return false;
    6294    }
    6395};
     
    71103 *
    72104 * This is a polynomial enumerator for simple iteration over
    73  * coefficients of (non-zero) polynomials.
     105 * coefficients of polynomials.
    74106 *
    75107 * It is required to inherit this class from IEnumerator<number> for
     
    90122    virtual IPolyCoeffsEnumerator::reference Current()
    91123    {
    92       assume( m_position != NULL );
     124      assume( IsValid() );
    93125      return pGetCoeff(m_position);     
    94126    }
     
    97129    virtual IPolyCoeffsEnumerator::const_reference Current() const
    98130    {
    99       assume( m_position != NULL );
     131      assume( IsValid() );
    100132      return pGetCoeff(m_position);
    101133    }
  • libpolys/polys/monomials/monomials.h

    r6dffa9 r9952bd  
    99
    1010#include <omalloc/omalloc.h>
     11#include <reporter/reporter.h> // for assume etc.
    1112
    1213struct snumber;
Note: See TracChangeset for help on using the changeset viewer.