#ifndef CYCLICH
#define CYCLICH

/* ***************************************************************** *
 *                                                                   *
 *              Cyclic.h  (C) 1999    Michael R. Toth                *
 *                                                                   *
 *    Class for Euclidean domain elements modulo a fixed element,    *
 *  "Kernel". The class parameter "PID" should implement  +, -, *,   *
 *  /, %, ==, !=, =, +=, -=, *=, /=, %=, and << and >> to and from   *
 *  streams. It should be constructable from an "int". The optional  *
 *  dummy  parameter "K" can be used as an index to distinguish      *
 *  Cyclic  types with the same  PID  but different values for       *
 *  Kernel . Use  Cyclic<PID,K>::SetZero  to initialize  Kernel .    *
 *                                                                   *
 * ***************************************************************** */

#include <iostream.h>
#include "Euclid.h"

template<class PID, int K =0> class Cyclic
{
  friend ostream& operator<< ( ostream&, const Cyclic& );
  friend istream& operator>> ( istream&, Cyclic& );
protected:
  static PID Kernel;
  PID value;
  void Reduce( )  { if ( Kernel!=0 )
                         value%=Kernel, value+=Kernel, value%=Kernel; }
public:
  static PID Zero( )  { return Kernel; }
  static void SetZero( const PID& Generator )  { Kernel=Generator; }
  Cyclic( )  { }
  Cyclic( const Cyclic& that ): value(that.value)  { }  
  Cyclic( const PID& v ): value(v)  { Reduce( ); }
  Cyclic( const int n ): value(PID(n))  { Reduce( ); }
  operator PID( )  { return value; }
  Cyclic& operator= ( const Cyclic& that )
          { if ( this!=&that )  value=that.value;  return *this; }
  bool operator== ( const Cyclic& that ) const
       { return  Congruent(value,that.value,Kernel); }
  bool operator!= ( const Cyclic& that ) const
       { return  !operator==(that); }
  Cyclic& operator+= ( const Cyclic& that )
          { value+=that.value, Reduce( );  return *this; } 
  Cyclic& operator-= ( const Cyclic& that )
          { value-=that.value, Reduce( );  return *this; } 
  Cyclic& operator*= ( const Cyclic& that )
          { value*=that.value, Reduce( );  return *this; } 
  Cyclic& operator/= ( const Cyclic& that )
                     {
                       PID v=that.value;
                       PID w=Inverse(v,Kernel);
                       if ( value%v!=0 )  value=0;
                       value/=v, value*=w;
                       Reduce( );
                       return *this;
                     }
  bool operator| ( const Cyclic& that ) const    // "divides".
                 { return  that.value%GCD(value,Kernel)==0; }
  Cyclic operator- ( ) const  { return Cyclic(Kernel-value); }
  Cyclic operator[] ( long ) const;    // Integer power.
  bool Inv( Cyclic& inv ) const // Puts its inverse in  inv  when invertable.
          { inv=*this;  return  Invert(inv.value,Kernel); }
};

template<class PID, int K =0> 
ostream& operator<< ( ostream& out, const Cyclic<PID, K>& x )
                    { out<<x.value;  return out; }

template<class PID, int K =0> 
istream& operator>> ( istream& in, Cyclic<PID, K>& x )
                    { in>>x.value, Reduce( );  return in; }

template<class PID, int K =0> inline
Cyclic<PID, K> operator+ ( Cyclic<PID, K> x, const Cyclic<PID, K>& y )
                         { return  x+=y; }

template<class PID, int K =0> inline
Cyclic<PID, K> operator- ( Cyclic<PID, K> x, const Cyclic<PID, K>& y )
                         { return  x-=y; }

template<class PID, int K =0> inline 
Cyclic<PID, K> operator* ( Cyclic<PID, K> x, const Cyclic<PID, K>& y )
                         { return  x*=y; }

template<class PID, int K =0> inline
Cyclic<PID, K> operator/ ( Cyclic<PID, K> x, const Cyclic<PID, K>& y )
                         { return  x/=y; }

template<class PID, int K =0>
Cyclic<PID, K> Cyclic<PID, K>::operator[] ( long p ) const
               {                
                 Cyclic x;
                 if ( p<0 )  if ( Inv(x) )  p=-p;  else  return 0;
                      else  x=*this;
                 Cyclic y= p&1? x: Cyclic(1);
                 while ( p>>=1 )  { x*=x;  if ( p&1 )  y*=x; }
                 return y;
               }

template<class PID, int K =0>  PID Cyclic<PID, K>::Kernel=0;

#endif CYCLICH