Changeset 9952bd in git

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:

• coeffs/Enumerator.h (modified) (3 diffs)
• coeffs/longrat.cc (modified) (7 diffs)
• coeffs/numbers.cc (modified) (6 diffs)
• polys/Makefile.am (modified) (1 diff)
• polys/PolyEnumerator.cc (added)
• polys/PolyEnumerator.h (modified) (6 diffs)
• polys/monomials/monomials.h (modified) (1 diff)

libpolys/coeffs/Enumerator.h

@@ -22 +22 @@
 /** @class IBaseEnumerator
  * 
- * Base enumerator interface for simple iteration over a generic non-empty collection.
- *
- * Abstract API of enumerators for non-empty enumerable collections of standalone
- * objects. Inspired by IEnumerator from C#. Usage parrten can be as
- * follows:
+ * Base enumerator interface for simple iteration over a generic collection.
+ *
+ * Abstract API of enumerators for enumerable collections of standalone objects.
+ * Just like IEnumerator from C#. Usage pattern can be as follows:
  *
  * @code
- *   IBaseEnumerator itr = ...;
- *   itr.Reset(); // goes to the first element (must exist)
- *   do
+ *   IBaseEnumerator& itr = ...;
+ *   itr.Reset(); // goes to the "-1" element
+ *   // NOTE: itr is not useable here!
+ *   while( itr.MoveNext() )
  *   {
  *      do something custom with itr...
  *   }
- *   while( itr.MoveNext() )
  * @endcode
  *
- * Note that the first element must exist and available directly after Reset() call.
+ * Note that the Reset() 
  *
  * @sa IEnumerator
@@ -51 +50 @@
     virtual bool MoveNext() = 0;    
 
-    /// Sets the enumerator to its initial position, which is at the first element in the collection.
+    /// Sets the enumerator to its initial position: -1,
+    /// which is before the first element in the collection.
     virtual void Reset() = 0;
-//    virtual ~IEnumerator() {} // TODO: needed?
+
+    virtual ~IBaseEnumerator() {} // TODO: needed?
+
+  private:
+    IBaseEnumerator(const IBaseEnumerator&);
+    void operator=(const IBaseEnumerator&);
+
+  protected:
+    IBaseEnumerator(){}
+
+    /// Current position is inside the collection (not -1 or past the end)
+    virtual bool IsValid() const = 0;
 };
 
@@ -78 +89 @@
     /// Gets the current element in the collection (read only).
     virtual const_reference Current() const = 0;
+
+    virtual ~IAccessor() {} // TODO: needed?
+  
 };
 
 /** @class IEnumerator
  * 
- * Templated enumerator interface for simple iteration over a generic non-empty collection of T's.
- *
- * Abstract API of enumerators for non-empty enumerable collections of standalone
- * objects. Inspired by IEnumerator from C#. Usage parrten can be as
+ * Templated enumerator interface for simple iteration over a generic collection of T's.
+ *
+ * Abstract API of enumerators for generic enumerable collections of standalone
+ * objects of type T. Inspired by IEnumerator from C#. Usage parrten can be as
  * follows:
  *
  * @code
- *   IEnumerator<T> itr = ...;
- *   itr.Reset(); // goes to the first element (must exist)
- *   do
+ *   IEnumerator<T>& itr = ...;
+ *   
+ *   itr.Reset(); // goes before the first element, thus no itr.Current() is available here!
+ *   
+ *   while( itr.MoveNext() )
  *   {
  *      use/change itr.Current()...
  *   }
- *   while( itr.MoveNext() )
  * @endcode
  *

libpolys/coeffs/longrat.cc

@@ -2645 +2645 @@
   assume(cf != NULL);
   assume(getCoeffType(cf) == ID);
+
+  numberCollectionEnumerator.Reset();
+
+  if( !numberCollectionEnumerator.MoveNext() ) // empty zero polynomial?
+  {
+    c = n_Init(1, cf);
+    return;
+  }
+  
   // all coeffs are given by integers!!!
 
@@ -2651 +2660 @@
   int s1,s;
   s=2147483647; // max. int
-  numberCollectionEnumerator.Reset();
+
+  
   int lc_is_pos=nlGreaterZero(numberCollectionEnumerator.Current(),cf);
+
+  int normalcount = 0;
   do
   {
-    cand1= numberCollectionEnumerator.Current();
-    if (SR_HDL(cand1)&SR_INT) { cand=cand1;break;}
-    assume(cand1->s==3); // all coeffs should be integers
+    number& n = numberCollectionEnumerator.Current();
+    nlNormalize(n, cf); ++normalcount;
+    cand1 = n;
+    
+    if (SR_HDL(cand1)&SR_INT) { cand=cand1; break; }
+    assume(cand1->s==3); // all coeffs should be integers // ==0?!! after printing 
     s1=mpz_size1(cand1->z);
     if (s>s1)
@@ -2666 +2681 @@
   } while (numberCollectionEnumerator.MoveNext() );
 
+//  assume( nlGreaterZero(cand,cf) ); // cand may be a negative integer!
+
   cand=nlCopy(cand,cf);
   // part 2: compute gcd(cand,all coeffs)
+
   numberCollectionEnumerator.Reset();
-  do
-  {
-    nlNormalize(numberCollectionEnumerator.Current(),cf);
-    nlInpGcd(cand,numberCollectionEnumerator.Current(),cf);
+  
+  while (numberCollectionEnumerator.MoveNext() )
+  {
+    number& n = numberCollectionEnumerator.Current();
+
+    if( (--normalcount) <= 0)
+      nlNormalize(n, cf);
+
+    nlInpGcd(cand, n, cf);
+
+    assume( nlGreaterZero(cand,cf) );
+    
     if(nlIsOne(cand,cf))
     {
-      c=cand;
+      c = cand;
+
       if(!lc_is_pos)
       {
         // make the leading coeff positive
-        c=nlNeg(c,cf);
+        c = nlNeg(c, cf);
         numberCollectionEnumerator.Reset();
-        do
+        
+        while (numberCollectionEnumerator.MoveNext() )
         {
-          numberCollectionEnumerator.Current()=nlNeg(numberCollectionEnumerator.Current(),cf);
-        } while (numberCollectionEnumerator.MoveNext() );
+          number& nn = numberCollectionEnumerator.Current();
+          nn = nlNeg(nn, cf);
+        }
       }
       return;
     }
-  } while (numberCollectionEnumerator.MoveNext() );
+  } 
 
   // part3: all coeffs = all coeffs / cand
-  if (!lc_is_pos) cand=nlNeg(cand,cf);
-  c=cand;
+  if (!lc_is_pos)
+    cand = nlNeg(cand,cf);
+  
+  c = cand;
   numberCollectionEnumerator.Reset();
-  do
-  {
-    number t=nlIntDiv(numberCollectionEnumerator.Current(),cand,cf);
-    nlDelete(&numberCollectionEnumerator.Current(),cf);
-    numberCollectionEnumerator.Current()=t;
-  } while (numberCollectionEnumerator.MoveNext() );
-
+
+  while (numberCollectionEnumerator.MoveNext() )
+  {
+    number& n = numberCollectionEnumerator.Current();
+    number t=nlIntDiv(n, cand, cf); // simple integer exact division, no ratios to remain
+    nlDelete(&n, cf);
+    n = t;
+  }
 }
 
@@ -2707 +2739 @@
   assume(cf != NULL);
   assume(getCoeffType(cf) == ID);
+
+  numberCollectionEnumerator.Reset();
+  
+  if( !numberCollectionEnumerator.MoveNext() ) // empty zero polynomial?
+  {
+    c = n_Init(1, cf);
+    return;
+  }
+
   // all coeffs are given by integers after returning from this routine
 
@@ -2712 +2753 @@
   number cand;
   cand=ALLOC_RNUMBER();
-  #if defined(LDEBUG)
+#if defined(LDEBUG)
   cand->debug=123456;
-  #endif
+#endif
   cand->s=3;
 
   int s=0;
-  mpz_t tmp;
-  mpz_init(tmp);
-  numberCollectionEnumerator.Reset();
+//  mpz_t tmp; mpz_init(tmp); // tmp = GMP int
+  
   int lc_is_pos=nlGreaterZero(numberCollectionEnumerator.Current(),cf);
+
   do
   {
@@ -2730 +2771 @@
       nlNormalize(cand1, cf);
       if ((!(SR_HDL(cand1)&SR_INT)) // not a short int
-      && (cand1->s==1))             // and is rational
+      && (cand1->s==1))             // and is a normalised rational
       {
         if (s==0) // first denom, we meet
         {
-          mpz_init_set(cand->z,cand1->n);
+          mpz_init_set(cand->z, cand1->n); // cand->z = cand1->n
           s=1;
         }
         else // we have already something
         {
-          mpz_gcd(tmp,cand->z,cand1->n);
-          if (mpz_cmp_si(tmp,1)!=0)
-          {
-            mpz_divexact(cand->z,cand->z,tmp);
-          }
-          mpz_mul(cand->z,cand->z,cand1->n);
+          mpz_lcm(cand->z, cand->z, cand1->n);
+/*                  
+          mpz_gcd(tmp,cand->z,cand1->n); // tmp = GCD( cand->z, cand1->n )
+          
+          if (mpz_cmp_si(tmp,1)!=0) 
+            mpz_divexact(cand->z,cand->z,tmp); // cand->z /= tmp
+          
+          mpz_mul(cand->z,cand->z,cand1->n); // cand->z *= cand1->n
+*/
         }
       }
     }
-  } while (numberCollectionEnumerator.MoveNext() );
+  }
+  while (numberCollectionEnumerator.MoveNext() );
+  
 
   if (s==0) // nothing to do, all coeffs are already integers
   {
-    mpz_clear(tmp);
+//    mpz_clear(tmp);
     FREE_RNUMBER(cand);
     if (lc_is_pos)
@@ -2760 +2806 @@
       // make the leading coeff positive
       c=nlInit(-1,cf);
+
+      // TODO: incorporate the following into the loop below?
       numberCollectionEnumerator.Reset();
-      do
-      {
-        numberCollectionEnumerator.Current()=nlNeg(numberCollectionEnumerator.Current(),cf);
-      } while (numberCollectionEnumerator.MoveNext() );
+      while (numberCollectionEnumerator.MoveNext() )
+      {
+        number& n = numberCollectionEnumerator.Current();
+        n = nlNeg(n, cf);
+      } 
     }
     return;
   }
-  cand=nlShort3(cand);
+
+  cand = nlShort3(cand);
 
   // part2: all coeffs = all coeffs * cand
   // make the lead coeff positive
   numberCollectionEnumerator.Reset();
-  if (!nlGreaterZero(numberCollectionEnumerator.Current(),cf))
-  {
-    cand=nlNeg(cand,cf);
-  }
+  
+  if (!lc_is_pos)
+    cand = nlNeg(cand, cf);
+  
   c = cand;
-  do
+  
+  while (numberCollectionEnumerator.MoveNext() )
   {
     number &n = numberCollectionEnumerator.Current();
     n_InpMult(n, cand, cf);
-  } while (numberCollectionEnumerator.MoveNext() );
+  }
 
 }

libpolys/coeffs/numbers.cc

@@ -131 +131 @@
   assume(!(  nCoeff_is_Q(r) || nCoeff_is_Q_a(r) ));
   // all coeffs are given by integers!!!
-  assume( nCoeff_is_Ring(r) || nCoeff_is_Zp(r) || nCoeff_is_numeric(r) || nCoeff_is_GF(r) || nCoeff_is_Zp_a(r) );
 
   numberCollectionEnumerator.Reset();
+
+  if( !numberCollectionEnumerator.MoveNext() ) // empty zero polynomial?
+  {
+    c = n_Init(1, r);
+    return;
+  }  
+
+  number &curr = numberCollectionEnumerator.Current();
   
 #ifdef HAVE_RINGS
@@ -141 +148 @@
     if (nCoeff_has_Units(r))
     {
-      c = n_GetUnit(numberCollectionEnumerator.Current(), r);
+      c = n_GetUnit(curr, r);
       
       if (!n_IsOne(c, r))
@@ -147 +154 @@
         number inv = n_Invers(c, r);
 
-        do
+        n_InpMult(curr, inv, r);
+        
+        while( numberCollectionEnumerator.MoveNext() )
         {
-          n_InpMult(numberCollectionEnumerator.Current(), inv, r);
+          number &n = numberCollectionEnumerator.Current();
+          n_Normalize(n, r); // ?
+          n_InpMult(n, inv, r); // TODO: either this or directly divide!!!?
         }
-        while( numberCollectionEnumerator.MoveNext() );
 
         n_Delete(&inv, r);        
@@ -162 +172 @@
 
   assume(!nCoeff_is_Ring(r));
-
-  c = numberCollectionEnumerator.Current();
+  assume(nCoeff_is_Zp(r) || nCoeff_is_numeric(r) || nCoeff_is_GF(r) || nCoeff_is_Zp_a(r));
+
+  c = curr;
   
   n_Normalize(c, r);
@@ -169 +180 @@
   if (!n_IsOne(c, r))
   {    
-    numberCollectionEnumerator.Current() = n_Init(1, r); // ???
+    curr = n_Init(1, r); // ???
     
     number inv = n_Invers(c, r);
@@ -177 +188 @@
       number &n = numberCollectionEnumerator.Current();
       n_Normalize(n, r); // ?
-      n_InpMult(n, inv, r);
+      n_InpMult(n, inv, r); // TODO: either this or directly divide!!!?
     }
     

libpolys/polys/Makefile.am

@@ -48 +48 @@
         ext_fields/algext.cc ext_fields/transext.cc \
         clapsing.cc clapconv.cc \
-        nc/old.gring.cc
+        nc/old.gring.cc PolyEnumerator.cc
 
 LIBPOLYSHEADERS = monomials/ring.h monomials/monomials.h \

libpolys/polys/PolyEnumerator.h

@@ -19 +19 @@
 #include <coeffs/Enumerator.h>
 #include <polys/monomials/monomials.h>
+#include <reporter/reporter.h> // for assume etc.
 
 /** @class CBasePolyEnumerator
  * 
- * Base polynomial enumerator for simple iteration over terms of
- * (non-zero) polynomials.
+ * Base polynomial enumerator for simple iteration over terms of polynomials.
  *
- * Note that the first element must exist directly after Reset() call.
- * Moreover, it doesn't inherit from IAccessor and thus doesn't
- * override Current().
+ * Note that the first element desn't exist directly after Reset() call.
+ * 
+ * The class doesn't inherit from IAccessor and thus doesn't override Current().
  *
  * @sa IBaseEnumerator, @sa CPolyCoeffsEnumerator
@@ -34 +34 @@
 {
   private:
-    const poly m_poly;
+    const poly m_poly; ///< essentially immutable original iterable object
+    
+    static const spolyrec m_prevposition_struct; ///< tag for "-1" position
 
   protected:
-    poly m_position;
+    poly m_position; ///< current position in the iterable object
+
+    virtual bool IsValid() const
+    {
+      // not -1 or past the end position?
+      return (m_position != NULL) && (m_position != &m_prevposition_struct);
+    }
     
-    inline void Iterate()
+  public:
+    CBasePolyEnumerator(poly p):
+        IBaseEnumerator(), m_poly(p), m_position(const_cast<poly>(&m_prevposition_struct))
     {
-      if( m_position != NULL )
-        pIter( m_position );
-    }    
-  public:
-    CBasePolyEnumerator(poly p): m_poly(p), m_position(p) { assume(p != NULL); }
+      assume( !IsValid() ); 
+    }
     
     /// Sets the position marker to the leading term.
-    virtual void Reset() { assume(m_poly!= NULL); m_position = m_poly; }
+    virtual void Reset()
+    {
+      m_position = const_cast<poly>(&m_prevposition_struct);
+      assume( !IsValid() ); 
+    }
 
     /// Advances the position to the next term of the polynomial.
     /// returns true if the position marker was successfully advanced to the
-    /// next term;
+    /// next term which can be used;
     /// false if the position marker has passed the end of the
     /// polynomial.
@@ -58 +69 @@
     {
       assume( m_position != NULL );
-      Iterate();
-      return (m_position != NULL);
+
+      {
+        const poly p_next = pNext(m_position);
+
+        if (p_next != NULL) // not the last term?
+        {
+          m_position = p_next;
+          assume( IsValid() );
+          return true;
+        }
+      }
+      
+      if (m_position == &m_prevposition_struct) // -1 position?
+      {
+        assume( !IsValid() );
+        m_position = m_poly;
+        return (m_position != NULL);
+      }
+
+      // else: past the end (or an empty polynomial)
+      m_position = NULL;
+      assume( !IsValid() );
+      return false;
     }
 };
@@ -71 +103 @@
  * 
  * This is a polynomial enumerator for simple iteration over
- * coefficients of (non-zero) polynomials.
+ * coefficients of polynomials.
  * 
  * It is required to inherit this class from IEnumerator<number> for
@@ -90 +122 @@
     virtual IPolyCoeffsEnumerator::reference Current()
     {
-      assume( m_position != NULL );
+      assume( IsValid() );
       return pGetCoeff(m_position);      
     }
@@ -97 +129 @@
     virtual IPolyCoeffsEnumerator::const_reference Current() const
     {
-      assume( m_position != NULL );
+      assume( IsValid() );
       return pGetCoeff(m_position);
     }

libpolys/polys/monomials/monomials.h

@@ -9 +9 @@
 
 #include <omalloc/omalloc.h>
+#include <reporter/reporter.h> // for assume etc.
 
 struct snumber;