During the developement of the braid programme I wanted to work with objects such as
polynomial<bigint>
polynomial<rational<bigint> >
polynomial<mod_p>
but with the selection made at run-time. The polynomial code was written as a template but this normally requires compile-time selection between the above variants. Moreover, I did not want the code bloated with if else clauses based on some enum burried in the polynomial class that would make it both inefficient and difficult to read.
I already had command line selection of tools that determined whether I was working with polynomials or quaternions, as I also wanted to handle
quaternion<bigint>
quaternion<rational<bigint> >
quaternion<mod_p>
with the variant also selected at run-time (again, the quaternion class is a template).
In both the polynomial and quaternion cases, mathematically the object involved scalars: coefficients of polynomial terms, components of quaternions, where one can multiply one of these objects by a scalar in a linear fashion. Thus, what was needed was the ability to write
polynomial<scalar>
quaternion<scalar>
and select the variant of scalar at run-time.
The solution to the above problem is to use an abstract class to provide an interface to scalars (creation, input/output, arithmetic operations etc.) and to produce a set of derived classes that implement these interface functions for the various cases. Then the application code may be written in terms of the abstract base class, independently of underlying type.
This is an unusual situation from the perspective of classes. The class hierarchy was intended to allow the definition of elemental objects from which more complex objects are derived with the application code using the more complex objects. In mathematics at this level the reverse is true: an integer is a special case of a rational, a rational a special case of a real, a real is a complex, a complex a quaternion and a quaternion may be regarded as a polynomial with only zero powers of its variables. Clearly writing a class hierarchy starting with multivariate polynomials in order to derive integers makes no sense!
There is a problem with abstract base class approach however. If the application code is to be based on the abstract base class, then it cannot know about the derived scalar variants, so arithmetic operations for manipulating scalars must return scalars. This polymorphic nature may only be achieved using pointers, since a pointer to an object of the base class may be used as a pointer to an object of one its derived classes.
The approach taken therefore was to create an abstract base class Scalar and a concrete wrapper class scalar that is used by the application code. The scalar class then hides the polymorphic nature of the Scalar class, with the application code calling a member function scalar::set_variant to select between the available variants.
Note: this approach requires dynamic casting to get from a Scalar* to a pointer to a scalar variant. Therefore the application code has to be very careful about where variants are set in relation to to object creation; scalar objects are created as variants whose type is determined by the last call to scalar::set_variant, so if the variant is subsequently changed and that object accessed again, trouble looms and a segmentation fault is almost inevitable.
The abstract base class need only provide the elemental operations, since others may be derived from these in the scalar class. Thus, the + operator for scalar is easily derived from the plus_eq member function of Scalar.
The interface as presented here contains some features specific to the braid programme application, such as nl (number length, a function that returns the length in characters of the scalar when displayed as a string), dump (used for debugging) and sanitize (used to remove redundant information from bigint data structures).
Here's the full definition of the Scalar class:
class Scalar
{
public:
virtual Scalar* plus_eq (Scalar*) = 0;
virtual Scalar* minus_eq (Scalar*) = 0;
virtual Scalar* times_eq (Scalar*) = 0;
virtual Scalar* divide_eq (Scalar*) = 0;
virtual Scalar* remainder_eq (Scalar*) = 0;
virtual bool eq (Scalar*) const = 0;
virtual bool ne (Scalar*) const = 0;
virtual bool gt (Scalar*) const = 0;
virtual bool lt (Scalar*) const = 0;
virtual bool ge (Scalar*) const = 0;
virtual bool le (Scalar*) const = 0;
virtual Scalar* abs_val() = 0;
virtual void increment() = 0;
virtual void decrement() = 0;
virtual void print(ostream&) = 0;
virtual void read(istream&) = 0;
virtual int nl() = 0; // num_len
virtual void dump(ostream&) const = 0;
virtual void sanitize() = 0;
virtual Scalar* clone() = 0; // virtual form of copy constructor
virtual ~Scalar() {}
};
The wrapper class scalar can be described in terms of Scalar pointers. The current implementation supports three variants, identified by an enum
enum scalar_variant {MOD_P, BIGINT, BIGRATIONAL}
The MOD_P variant handles integers mod-p, BIGINT supports a Scalar based version of arbitrary precision integers, and BIGRATIONAL is a Scalar based version of rational<bigint>.
An imporant feature of scalars is that the variant type is not the subject of a conditional clause at any time other than when setting the variant. Having said this, I have included a static data member in the scalar class to aid debugging but that is it's only purpose. Here is the full definition of the scalar class, which builds on the elemental functions of Scalar to produce a more complete set of operators. I know this isn't quite in the spirit of Strustrup, who advocates providing a full set of operators, but I only have the usual excuses for this omission so I won't repeat them here.
class scalar
{
Scalar* C;
static int variant;
public:
enum scalar_variant {MOD_P, BIGINT, BIGRATIONAL};
static void set_variant(scalar_variant t);
static void show_variant(ostream& s);
scalar operator = (const scalar& c) {if (this != &c){if (C) delete C; C = c.C->clone();} return *this;}
scalar operator ++ () {C->increment(); return *this;} // prefix
scalar operator ++ (int) {scalar t = *this; C->increment(); return t;} // postfix
scalar operator -- () {C->decrement(); return *this;}
scalar operator -- (int) {scalar t = *this; C->decrement(); return t;}
scalar operator += (const scalar& c) {C->plus_eq(c.C); return *this;}
scalar operator -= (const scalar& c) {C->minus_eq(c.C); return *this;}
scalar operator *= (const scalar& c) {C->times_eq(c.C); return *this;}
scalar operator /= (const scalar& c) {C->divide_eq(c.C); return *this;}
scalar operator %= (const scalar& c) {C->remainder_eq(c.C); return *this;}
bool operator == (const scalar& c) const {return C->eq(c.C);}
bool operator != (const scalar& c) const {return C->ne(c.C);}
bool operator > (const scalar& c) const {return C->gt(c.C);}
bool operator < (const scalar& c) const {return C->lt(c.C);}
bool operator >= (const scalar& c) const {return C->ge(c.C);}
bool operator <= (const scalar& c) const {return C->le(c.C);}
friend scalar operator + (const scalar& a, const scalar& b) {scalar r(a); r.C = r.C->plus_eq(b.C); return r;}
friend scalar operator - (const scalar& a, const scalar& b) {scalar r(a); r.C = r.C->minus_eq(b.C); return r;}
friend scalar operator * (const scalar& a, const scalar& b) {scalar r(a); r.C = r.C->times_eq(b.C); return r;}
friend scalar operator / (const scalar& a, const scalar& b) {scalar r(a); r.C = r.C->divide_eq(b.C); return r;}
friend scalar operator % (const scalar& a, const scalar& b) {scalar r(a); r.C = r.C->remainder_eq(b.C); return r;}
void dump(ostream& s) const {C->dump(s);}
void sanitize() {C->sanitize();}
friend scalar abs(const scalar& c) {scalar result; result.C = c.C->abs_val(); return result;}
friend ostream& operator << (ostream& s, const scalar& c) {(c.C)->print(s); return s;}
friend istream& operator >> (istream& s, const scalar& c) {(c.C)->read(s); return s;}
friend int num_len (const scalar c) {return c.C->nl();}
scalar();
scalar(const scalar& c) {C = c.C->clone();}
scalar(int);
~scalar() {delete C; C=0;}
};
Construction of an object of type scalar is done via function pointers. As can be seen from th eabove, there are two types of constructor, a default constructor and one that builds a scalar from an int. They are defined as follows:
Scalar* (*make_scalar) ();
Scalar* (*make_scalar_int) (int);
inline scalar::scalar()
{
C=make_scalar();
}
inline scalar::scalar(int a)
{
C=make_scalar_int(a);
}
Where make_scalar and make_scalar_int point at functions that make an objects of the appropriate type. Thereafter the inheritance rules and virtual functions of the base class ensure that the right version of the operators and member functions are called for each object, as required. The functions that actually make the objects simply call the corresponding constructor for the derived class:
Scalar* make_bigint() {return new bigint;}
Scalar* make_bigint(int a) {return new bigint(a);}
Scalar* make_mod_p() {return new mod_p;}
Scalar* make_mod_p(int a) {return new mod_p(a);}
Scalar* make_big_rational() {return new big_rational;}
Scalar* make_big_rational(int a) {return new big_rational(a);}
The function pointers make_scalar make_scalar_int are actually initialized to the default variant, in the case of the braid programme BIGINT. Thereafter the application code will make a call such as:
scalar::set_variant(scalar::MOD_P);
and the variant is changed simply by changing the constructor function pointers:
void scalar::set_variant(scalar_variant t)
{
if (t == BIGINT)
{
make_scalar = make_bigint;
make_scalar_int = make_bigint;
variant = BIGINT;
}
else if (t == BIGRATIONAL)
{
make_scalar = make_big_rational;
make_scalar_int = make_big_rational;
variant = BIGRATIONAL;
}
else
{
make_scalar = make_mod_p;
make_scalar_int = make_mod_p;
variant = MOD_P;
}
}
This is the only time that we need to consider which type of variant we are dealing with. Recall the variant type is recorded only for debugging.
In simple cases like MOD_P, the derived class is trivial, needing only to implement the pure virtual functions of the abstract base class:
class mod_p : public Scalar
{
static int p;
int n; // modulo p
public:
static void set_p (int);
static vector inv;
static int get_p () {return p;}
mod_p(){n=0;}
mod_p(int a){n=(a%p+p)%p;}
mod_p* plus_eq (Scalar* a) {mod_p* ptr = dynamic_cast(a); n+=ptr->n; n %= p; return this;}
mod_p* minus_eq (Scalar* a) {mod_p* ptr = dynamic_cast(a); n=n+p-ptr->n; n %= p; return this;}
mod_p* times_eq (Scalar* a) {mod_p* ptr = dynamic_cast(a); n*=ptr->n; n %= p; return this;}
mod_p* divide_eq (Scalar* a) {mod_p* ptr = dynamic_cast(a); n*=inv[ptr->n]; n%=p; return this;}
mod_p* remainder_eq (Scalar* a) {n=0; return this;}
bool eq (Scalar* a) const {mod_p* ptr = dynamic_cast(a); return n == ptr->n;}
bool ne (Scalar* a) const {mod_p* ptr = dynamic_cast(a); return n != ptr->n;}
bool gt (Scalar* a) const {mod_p* ptr = dynamic_cast(a); return n > ptr->n;}
bool lt (Scalar* a) const {mod_p* ptr = dynamic_cast(a); return n < ptr->n;}
bool ge (Scalar* a) const {mod_p* ptr = dynamic_cast(a); return n >= ptr->n;}
bool le (Scalar* a) const {mod_p* ptr = dynamic_cast(a); return n <= ptr->n;}
mod_p* abs_val() { mod_p* result = new mod_p(*this); result->n = std::abs(result->n); return result;}
void increment() { n++; n%= p;}
void decrement() { n = n+p-1; n%= p;}
void read(istream& s) {s >> n; n %= p; n = (n+p)%p;} // n = (n+p)%p deals with negative input
void print (ostream& s) {s << n;}
int nl(); // num_len
void dump(ostream& s) const {s << n << "(mod " << p << ")";}
void sanitize() {}
mod_p* clone() {return new mod_p(*this);}
};
Here the vector<int> inv is initialized by set_p for use by the divide_eq member function.
In more complicated examples, the derived class can contain a full set of operators itself so that objects of that class may be created independently of the scalar apparatus:
class bigint : public Scalar
{
vector n;
bool negative;
public:
/* Scalar virtuals go here*/
....
/* Now native bigint members */
....
};
Of course, the derived classes have to implement a constructor from an int, and if required a user-defined default constructor, as well.