residue.hpp

Go to the documentation of this file.

/*****************************************************************************
    
    residue.hpp -- Residue representation with dynamically set module.

    This file is a part of the Arageli library.

    Copyright (C) Nikolai Yu. Zolotykh, 1999--2006
    Copyright (C) Sergey S. Lyalin, 2006
    University of Nizhni Novgorod, Russia

*****************************************************************************/

#ifndef _ARAGELI_residue_hpp_
#define _ARAGELI_residue_hpp_

#include "config.hpp"

#include <iostream>
#include <sstream>

#include "_utility.hpp"
#include "factory.hpp"
#include "intalg.hpp"

#include "std_import.hpp"


namespace Arageli
{


template <typename T, typename M>
struct residue_config_default
{
    static void init (T& x, const M& m) { normalize(x, m); }
    static void get_value (const T& x, const M& m) {}
    static void before_oper (const T& x, const M& m) {}
    static void after_oper (T& x, const M& m) { normalize(x, m); }
    static bool is_normal (const T& x, const M& m) { return is_null(m) || is_null(x/m); }
    static void normalize (T& x, const M& m) {if(!is_null(m))x = prrem(x, m);}
};


// Residue class.
template
<
    typename T, typename M = T,
    typename Config = residue_config_default<T, M>
>
class residue
{
    mutable T value_m;  // resudue value itself
    M module_m; // module value
    Config config_m;    // configurator

    template <typename T2, typename M2, typename Config2>
    friend class residue;

public:

    typedef T value_type;
    typedef M module_type;
    typedef Config config_type;

    residue () : value_m(null<T>()), module_m(null<M>()) {}

    template <typename T1>
    residue (const T1& x) : value_m(x), module_m(null<M>()) {}

    // Special copy constructor.
    template <typename T1>
    residue (const residue<T1>& x) : value_m(x.value()), module_m(x.module()) {}

    // Creates residue from the division of x by m.
    residue (const T& x, const M& m) : value_m(x), module_m(m)
    { config_m.init(value_m, module_m); }


    residue (const char* s);


    const T& value () const
    {
        config_m.get_value(value_m, module_m);
        return value_m;
    }

    const M& module () const { return module_m; }

    T& value ()
    {
        config_m.get_value(value_m, module_m);
        return value_m;
    }

    M& module () { return module_m; }


    bool is_normal () const { return config_m.is_normal(value_m, module_m); }

    void normalize () const { config_m.normalize(value_m, module_m); }


    residue operator- () const
    {
        config_m.before_oper(value_m, module_m);
        return residue(-value_m, module_m);
    }
    
    const residue& operator+ () const { return *this; }

    residue& operator++ ()
    {
        config_m.before_oper(value_m, module_m);
        ++value_m;
        config_m.after_oper(value_m, module_m);
        return *this;
    }
    
    residue& operator-- ()
    {
        config_m.before_oper(value_m, module_m);
        --value_m;
        config_m.after_oper(value_m, module_m);
        return *this;
    }
    
    residue operator++ (int) { residue t = *this; operator++(); return t; }
    residue operator-- (int) { residue t = *this; operator--(); return t; }
    
    template <typename T1, typename M1, typename Config1>
    residue& operator+= (const residue<T1, M1, Config1>& x)
    {
        ARAGELI_ASSERT_0
            (module_m == x.module_m || is_null(x.module_m) || is_null(module_m));
        
        config_m.before_oper(value_m, module_m);
        
        value_m += x.value_m;
        if(is_null(module_m) && !is_null(x.module_m))
            module_m = x.module_m;
        
        config_m.after_oper(value_m, module_m);
        return *this;
    }
    
    template <typename T1, typename M1, typename Config1>
    residue& operator-= (const residue<T1, M1, Config1>& x)
    {
        ARAGELI_ASSERT_0
            (module_m == x.module_m || is_null(x.module_m) || is_null(module_m));
        
        config_m.before_oper(value_m, module_m);
        
        value_m -= x.value_m;
        if(is_null(module_m) && !is_null(x.module_m))
            module_m = x.module_m;
        
        config_m.after_oper(value_m, module_m);
        return *this;
    }

    template <typename T1, typename M1, typename Config1>
    residue& operator*= (const residue<T1, M1, Config1>& x)
    {
        ARAGELI_ASSERT_0
            (module_m == x.module_m || is_null(x.module_m) || is_null(module_m));
        
        config_m.before_oper(value_m, module_m);
        
        value_m *= x.value_m;
        if(is_null(module_m) && !is_null(x.module_m))
            module_m = x.module_m;
        
        config_m.after_oper(value_m, module_m);
        return *this;
    }

    template <typename T1, typename M1, typename Config1>
    residue& operator/= (const residue<T1, M1, Config1>& x)
    {
        ARAGELI_ASSERT_0
            (module_m == x.module_m || is_null(x.module_m) || is_null(module_m));
        
        config_m.before_oper(value_m, module_m);
        
        if(is_null(module_m) && !is_null(x.module_m))
            module_m = x.module_m;
        
        if(is_null(module_m))
            value_m /= x.value_m;
        else
            value_m *= inverse_mod(x.value_m, T1(module_m));    // WARNING! A factory needed.
        
        config_m.after_oper(value_m, module_m);
        return *this;
    }

    template <typename T1, typename M1, typename Config1>
    residue& operator%= (const residue<T1, M1, Config1>& x)
    { return residue(null(value_m), module_m); }

    bool operator! () const { return is_null(value_m); }
    operator bool () const { return !!(*this); }

    operator T () const { return value(); }

};


#define ARAGELI_RESIDUE_BINARY_OP(OP, OPASS)                        \
    template                                                        \
    <                                                               \
        typename T1, typename M1, typename Config1,                 \
        typename T2, typename M2, typename Config2                  \
    >                                                               \
    inline residue<T1, M1, Config1> operator OP                     \
    (residue<T1, M1, Config1> a, const residue<T2, M2, Config2>& b) \
    { return a OPASS b; }

ARAGELI_RESIDUE_BINARY_OP(+, +=)
ARAGELI_RESIDUE_BINARY_OP(-, -=)
ARAGELI_RESIDUE_BINARY_OP(*, *=)
ARAGELI_RESIDUE_BINARY_OP(/, /=)
ARAGELI_RESIDUE_BINARY_OP(%, %=)


#define ARAGELI_RESIDUE_LOGIC_OP(OP)                                \
    template                                                        \
    <                                                               \
        typename T1, typename M1, typename Config1,                 \
        typename T2, typename M2, typename Config2                  \
    >                                                               \
    inline bool operator OP                                         \
    (const residue<T1, M1, Config1>& a,                             \
        const residue<T2, M2, Config2>& b)                          \
    { return a.value() OP b.value(); }                              \
                                                                    \
    template                                                        \
    <                                                               \
        typename T1, typename M1, typename Config1,                 \
        typename T2                                                 \
    >                                                               \
    inline bool operator OP                                         \
    (const residue<T1, M1, Config1>& a, const T2& b)                \
    { return a.value() OP b; }                                      \
                                                                    \
    template                                                        \
    <                                                               \
        typename T1,                                                \
        typename T2, typename M2, typename Config2                  \
    >                                                               \
    inline bool operator OP                                         \
    (const T1& a, const residue<T2, M2, Config2>& b)                \
    { return a OP b.value(); }



ARAGELI_RESIDUE_LOGIC_OP(==)
ARAGELI_RESIDUE_LOGIC_OP(!=)
ARAGELI_RESIDUE_LOGIC_OP(<)
ARAGELI_RESIDUE_LOGIC_OP(<=)
ARAGELI_RESIDUE_LOGIC_OP(>)
ARAGELI_RESIDUE_LOGIC_OP(>=)


template                                                        
<                                                               
    typename T1, typename M1, typename Config1,                 
    typename T2, typename M2, typename Config2                  
>                                                               
inline int cmp                      
(residue<T1, M1, Config1> a, const residue<T2, M2, Config2>& b) 
{ return cmp(a.value(), b.value()); }


template <typename T, typename M, typename Config>
inline std::ostream& operator<< (std::ostream& out, const residue<T, M, Config>& x)
{ return out << x.value() << "(mod " << x.module() << ")"; }


template <typename T, typename M, typename Config>
std::istream& operator>> (std::istream& in, residue<T, M, Config>& x)
{
    char ch = 0;
    in >> ch;
    bool brackets = false;
    if(ch == '(')brackets = true;
    else in.putback(ch);

    T value;
    in >> value;

    if(!in)
    {
        in.clear(std::ios_base::badbit);
        return in;
    }

    M module;

    if(_Internal::read_literal(in, "("))
    {
        if(!_Internal::read_literal(in, "mod"))
        {
            in.clear(std::ios_base::badbit);
            return in;
        }

        in >> module;

        if(!in)
        {
            in.clear(std::ios_base::badbit);
            return in;
        }

        if(!_Internal::read_literal(in, ")"))
        {
            in.clear(std::ios_base::badbit);
            return in;
        }
    }
    else module = null<M>(value);

    if(brackets && !_Internal::read_literal(in, ")"))
    {
        in.clear(std::ios_base::badbit);
        return in;
    }

    x = residue<T, M, Config>(value, module);

    return in;
}


template <typename T, typename M, typename Config>
residue<T, M, Config>::residue (const char* s)
{
    std::istringstream buf(s);
    buf >> *this;
}


template <typename T, typename M, typename Config>
const residue<T, M, Config>& abs (const residue<T, M, Config>& x)
{ return x; }



} // namesapce Arageli


//#ifdef ARAGELI_INCLUDE_CPP_WITH_EXPORT_TEMPLATE
//  #define ARAGELI_INCLUDE_CPP_WITH_EXPORT_TEMPLATE_RESIDUE
//  #include "residue.cpp"
//  #undef  ARAGELI_INCLUDE_CPP_WITH_EXPORT_TEMPLATE_RESIDUE
//#endif

#endif

---