include/realroot/sign_variation.hpp

Go to the documentation of this file.

/********************************************************************
 *   This file is part of the source code of the realroot kernel.
 *   Author(s): B. Mourrain, GALAAD, INRIA
 *              Fernando Carreras, Univ. Santander
 *   $Id: sign.h,v 1.2 2005/09/28 06:40:43 mourrain Exp $
 ********************************************************************/
#ifndef mmx_sign_variation_hpp
#define mmx_sign_variation_hpp
/********************************************************************/
#include <iterator>

namespace mmx {

#ifndef MMX_SIGN_FCT
#define MMX_SIGN_FCT
template<typename T> inline
int sign(const T& x)
{
  return ( x < T(0) ? -1 : (T(0) < x ? 1 : 0) );
}
#endif

//--------------------------------------------------------------------
template<typename Iterator>
unsigned sign_variation( Iterator  b, Iterator  e )
{
  unsigned c = 0;
 
  while (  *b == 0 && b != e ) b++;
  
  if ( b != e )
    {
      //Iterator p = b;
      bool v = (*b<0);
      for( ++b; b != e;  ++b )
        if ( (*b != 0) && ( (*b<0) != v ) ) { c++; v = !v; };
    };
  
  return c;
}

template<typename Iterator>
unsigned sign_variation( Iterator  b, Iterator  e, unsigned maxv )
{
  unsigned c = 0;
 
  while (  *b == 0 && b != e ) b++;

  if ( b != e )
    {
      //Iterator p = b;
      bool v = (*b<0);
      for( ++b; c < maxv && b != e;  ++b ) {
        if ( (*b != 0) && ( (*b<0) != v ) ) {
          c++; v = !v; };
      }
    };
  
  return c;
}

template<typename Vector>
unsigned sign_variation_n( const Vector& t, unsigned l, unsigned maxv )
{
 
  unsigned c = 0, i=0;
 
  while (  t[i] == 0 && i< l ) i++;
  if ( i<l )
    {
      //unsigned p = i;
      bool v = (t[i]<0);
      for( ++i; c < maxv && i<l;  ++i ) {
        if ( (t[i] != 0) && ( (t[i]<0) != v ) ) {
          c++; v = !v; };
      }
    };
  return c;
}

template<typename Iterator>
bool has_sign_variation( Iterator  b, Iterator  e)
{
  return (sign_variation(b,e,1)>0);
}

template<typename Vector>
bool has_sign_variation( const Vector& t)
{
  return (sign_variation_n(t,t.size(),1)>0);
}


template<typename Vector>
int sign_of( const Vector& t) {
  int i;
  for (i=0; (i<t.size() && t[i]==0); i++) ;
  if(i==t.size()) return 0;

  bool ng;
  for (ng=(t[i]<=0); i<t.size(); i++) 
    if(ng !=(t[i]<=0)) return 0;
  
  return (ng?-1:1);
}

//--------------------------------------------------------------------
template<typename T> inline
int sign_variation(const T &v) 
{ return sign_variation(v.begin(),v.end()); }
template<typename T> inline
int sign_variation(const T &v, unsigned maxv ) 
{ return sign_variation(v.begin(),v.end(),maxv); };

template<typename C, unsigned N> 
inline unsigned sign_variation( const C (&t)[N] ) 
{ return sign_variation(t,t+N); };

template<typename C, unsigned N> inline
unsigned sign_variation( const C (&t)[N], unsigned maxv ) 
{ return sign_variation(t,t+N,maxv); };

template<typename C> inline
unsigned sign_variation( const C * t, unsigned size )
{ return sign_variation(t,t+size); };

template<typename C> inline 
unsigned sign_variation( const C * t, unsigned size, unsigned maxv ) 
{ return sign_variation(t,t+size,maxv); };

/********************************************************************/
template<typename T>
int Var(const T &v) { return sign_variation(v); }


template<typename T>
int Per(const T &v)
{
  typedef typename T::const_iterator iter;
  int per=0;
  iter it0=v.begin(),it1=it0;++it1;
  for(;it1!=v.end();++it0,++it1)
  {
        if(sign(*it0)*sign(*it1)>0) per++;
  }
  return (per);
}


template<typename T>
int Eps(const T &v)
{
  typedef typename T::const_iterator iter;
  int result=0;
  iter iti, itj=v.begin()+1;
  iti=itj;
  //  std::cout<<(*iti)<<" "<<(*itj)<<std::endl;
  while (itj!=v.end())
  {
    //    std::cout<<"L "<<(*iti)<<" "<<(*itj)<<std::endl;
    if ((*itj)==0)
      {
        iti=itj+1;
        while(iti!=v.end() && (*iti==0)) ++iti;
        if (iti!=v.end())
        {
          //      std::cout<<*iti<<" "<<*itj<<std::endl;          
          if (std::distance(itj,iti)%2==0)
            { 
              int val;
              if (sign(*(itj-1))*sign(*iti)>0) val=1; else val=-1;
              result += val*pow(-1,std::distance(itj,iti)/2);
            }
          itj=iti+1;
        }
        else
          return result;
      }
    else ++itj;
  }
  return result;
}


template<typename T>
int Count(const T &v)
{
  return (Per(v)-Var(v)+Eps(v));
}


template<typename C, typename Iterator>
C min_value( Iterator  b, Iterator  e )
{
  C r = *b;
  for (Iterator i=b; i != e; i++)  r = min(r,*i);
  return r;
}

template<typename C, typename Iterator>
C max_value( Iterator  b, Iterator  e )
{
  C r = *b;
  for (Iterator i=b; i != e; i++)  r = max(r,*i);
  return r;
}
 
} // namespace mmx 

#endif // realroot_ARITHM_SIGN_H_

---