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 Iterator>
bool has_no_strict_sign_variation( Iterator  b, Iterator  e )
{
    bool no_var = true;

    //while (  *b == 0 && b != e ) b++;

    if(*b==0) return false;

    if ( b != e )
    {
        bool v = (*b<0);
        for( ++b; b != e && no_var;  ++b )
            if ( (*b<0) != v ) { no_var=false; };
    };

    return no_var;
}

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_