C++ generic programming question - looking for suggestions (long)

[Master of C++]

Hello Folks,

I have a programming dilemma with templates and "genericity". I can
think of a few solutions, but I am not sure which one is the best in
terms of genetic C++ style. Any suggestions will be greatly
appreciated.

I am writing a template class Polynomial that encapsulates the
functionalities of a Polynomial. Here is a rough sketch for the class:

.. template class<T>
.. class Polynomial
.. {
.. std::vector<T> coeffts; // coefficients
..
.. public:
.. // constructors and destructor.
.. // accessor routines.
.. // arithemtic operators.
.. // utility functions for printing, reduction, etc.,
.. };

This class can be used to represent polynomials like ax^2 + bx + c,
where the coefficients a, b, c can be either built-in types such as
int, double, float etc., or classes which have operators such as +, - ,
*, etc., defined. One of the main reasons for writing the above class
is to handle polynomials over Galois Fields (an abstract algebra
concept, but that is not relevant to the question). I have a class that
encapsulates a Galois Field element, whose sketch is given below:

.. class GFElement
.. {
.. uint32 gfValue;
.. GaloisField *gf;
..
.. public:
.. // constructors and destructor.
.. // accessors.
.. // arithmetic operators.
.. };

All the properties of the field are encapsulated within the class
GaloisField. It has stuff such as addition, subtraction,
multiplication, division, exponentiation and logarithm tables (because
a GaloisField has a finite number of elements, it is possible to
represent all arithmetic operations using tables at the expense of a
little memory). These tables will be used to look-up results of
arithmetic operations in GFElement (basically, the 'gf' pointer defines
the field that 'gfValue' belongs to).

As you can see, in order for a GFElement to be valid, we need to
initialize it with two parameters ('gfValue' and the pointer 'gf' to a
GaloisField object). This becomes a problem if I have code such as:

if (coeffts[i] > (T)0)
....

(or)

T temp = (T) 0;
....
temp += coeffts[i];

in the Polynomial<T> class (with T = GFElement). This is because, I can
only specify one value in the type-conversion constructor for GFElement
(where I initialize 'gfValue' to the argument of the constructor and
set 'gf' equal to NULL). In the above 'if' statement, the 'operator>'
function is comparing two GFElement objects, one with a 'gf' pointer
that points to a valid object and another with a 'gf' pointer that is
set to NULL. Normally, this situation should raise an exception simply
because one of the operands has an invalid 'gf' pointer.

In order to solve this dilemma, I set up an rule that: if 'gfValue' is
zero and the 'gf' pointer is NULL, the GFElement object is valid as
long as the routine that operates on that object does to use the 'gf'
pointer. If the above condition is met I will not raise an exception
and consider that situation as NORMAL.

So, my question would be: Is there a better way this situation could be
resolved ? or am I missing some big picture here ? What would Brian
Boitano do ?

Any suggestions or comments will be greatly appreciated, and thanks for
reading this long post.

Thanks,
Vijay.

--
PS: My id "Master of C++" has more to do with my favorite album "Master
of Puppets" than with my proficiency in C++.

[Victor Bazarov]

Master of C++ wrote:

Hello Folks,

I have a programming dilemma with templates and "genericity". I can
think of a few solutions, but I am not sure which one is the best in
terms of genetic C++ style. Any suggestions will be greatly
appreciated.

I am writing a template class Polynomial that encapsulates the
functionalities of a Polynomial. Here is a rough sketch for the class:

. template class<T>
. class Polynomial
. {
. std::vector<T> coeffts; // coefficients
.
. public:
. // constructors and destructor.
. // accessor routines.
. // arithemtic operators.
. // utility functions for printing, reduction, etc.,
. };

This class can be used to represent polynomials like ax^2 + bx + c,
where the coefficients a, b, c can be either built-in types such as
int, double, float etc., or classes which have operators such as +, - ,
*, etc., defined. One of the main reasons for writing the above class
is to handle polynomials over Galois Fields (an abstract algebra
concept, but that is not relevant to the question). I have a class that
encapsulates a Galois Field element, whose sketch is given below:

. class GFElement
. {
. uint32 gfValue;
. GaloisField *gf;
.
. public:
. // constructors and destructor.
. // accessors.
. // arithmetic operators.
. };

All the properties of the field are encapsulated within the class
GaloisField. It has stuff such as addition, subtraction,
multiplication, division, exponentiation and logarithm tables (because
a GaloisField has a finite number of elements, it is possible to
represent all arithmetic operations using tables at the expense of a
little memory). These tables will be used to look-up results of
arithmetic operations in GFElement (basically, the 'gf' pointer defines
the field that 'gfValue' belongs to).

As you can see, in order for a GFElement to be valid, we need to
initialize it with two parameters ('gfValue' and the pointer 'gf' to a
GaloisField object). This becomes a problem if I have code such as:

if (coeffts[i] > (T)0)
...

(or)

T temp = (T) 0;
...
temp += coeffts[i];

in the Polynomial<T> class (with T = GFElement). This is because, I can
only specify one value in the type-conversion constructor for GFElement
(where I initialize 'gfValue' to the argument of the constructor and
set 'gf' equal to NULL). In the above 'if' statement, the 'operator>'
function is comparing two GFElement objects, one with a 'gf' pointer
that points to a valid object and another with a 'gf' pointer that is
set to NULL. Normally, this situation should raise an exception simply
because one of the operands has an invalid 'gf' pointer.

In order to solve this dilemma, I set up an rule that: if 'gfValue' is
zero and the 'gf' pointer is NULL, the GFElement object is valid as
long as the routine that operates on that object does to use the 'gf'
pointer. If the above condition is met I will not raise an exception
and consider that situation as NORMAL.

So, my question would be: Is there a better way this situation could be
resolved ? or am I missing some big picture here ? What would Brian
Boitano do ?

Any suggestions or comments will be greatly appreciated, and thanks for
reading this long post.

Comparison to "zero" could probably be made a generic function (let's
call it "is_positive") which you specialise for your GFElement (instead
of using operator > where you need the second value):

template<class T> bool is_positive(T const& t) { return t > 0; }
template<> bool is_positive<GFElement>(GFElement const &e) { ???? }

If you need 'temp' for accumulation, perhaps you need another class, like
"GFAccumulator", which will implement += for GFElement, or simply make
sure that the default-constructed GFElement can be used on the left of
the +=. There is no real need to do

T temp = T(0)

just do

T temp = T();

which will default-construct doubles or other arithmetic types and make
them zero.

So, essentially, since I am completely unaware of the requirements for the
Galois Fields elements, I am not sure you need those conversion c-tors,
which seem to give you trouble. Have a default c-tor that creates some
kind of "uninitialised" GFElement that you allow to be used for some of
your operations, and have a proper two-argument constructor.

That's my take on it, after spending two minutes thinking (any more and
my head hurts). HTH, however little.

Victor

[Martin Eisenberg]

Master of C++ wrote:

All the properties of the field are encapsulated within the
class GaloisField. It has stuff such as addition, subtraction,
multiplication, division, exponentiation and logarithm tables
(because a GaloisField has a finite number of elements, it is
possible to represent all arithmetic operations using tables at
the expense of a little memory). These tables will be used to
look-up results of arithmetic operations in GFElement
(basically, the 'gf' pointer defines the field that 'gfValue'
belongs to).
Do the properties of a given GaloisField instance ever actually
change? I find it a bit strange on first sight that it's not a
static (compile time) structure.

Regarding the comparison problem, maybe you can have constant
singleton objects representing special elements that compare to
members of any field, but don't belong to any implementation-wise?
PS: My id "Master of C++" has more to do with my favorite album
"Master of Puppets" than with my proficiency in C++.

I hope the inconvenience of feeling the need to explain
that doesn't harm your taste for the music over time ;)
Martin

--
Quidquid latine dictum sit, altum viditur.

[Ian McCulloch]

Master of C++ wrote:

Hello Folks,

I have a programming dilemma with templates and "genericity". I can
think of a few solutions, but I am not sure which one is the best in
terms of genetic C++ style. Any suggestions will be greatly
appreciated.

I am writing a template class Polynomial that encapsulates the
functionalities of a Polynomial. Here is a rough sketch for the class:

. template class<T>
. class Polynomial
. {
. std::vector<T> coeffts; // coefficients
.
. public:
. // constructors and destructor.
. // accessor routines.
. // arithemtic operators.
. // utility functions for printing, reduction, etc.,
. };

This class can be used to represent polynomials like ax^2 + bx + c,
where the coefficients a, b, c can be either built-in types such as
int, double, float etc., or classes which have operators such as +, - ,
*, etc., defined. One of the main reasons for writing the above class
is to handle polynomials over Galois Fields (an abstract algebra
concept, but that is not relevant to the question). I have a class that
encapsulates a Galois Field element, whose sketch is given below:

. class GFElement
. {
. uint32 gfValue;
. GaloisField *gf;
.
. public:
. // constructors and destructor.
. // accessors.
. // arithmetic operators.
. };

All the properties of the field are encapsulated within the class
GaloisField. It has stuff such as addition, subtraction,
multiplication, division, exponentiation and logarithm tables (because
a GaloisField has a finite number of elements, it is possible to
represent all arithmetic operations using tables at the expense of a
little memory). These tables will be used to look-up results of
arithmetic operations in GFElement (basically, the 'gf' pointer defines
the field that 'gfValue' belongs to).

As you can see, in order for a GFElement to be valid, we need to
initialize it with two parameters ('gfValue' and the pointer 'gf' to a
GaloisField object). This becomes a problem if I have code such as:

if (coeffts[i] > (T)0)
...

(or)

T temp = (T) 0;
...
temp += coeffts[i];

in the Polynomial<T> class (with T = GFElement). This is because, I can
only specify one value in the type-conversion constructor for GFElement
(where I initialize 'gfValue' to the argument of the constructor and
set 'gf' equal to NULL). In the above 'if' statement, the 'operator>'
function is comparing two GFElement objects, one with a 'gf' pointer
that points to a valid object and another with a 'gf' pointer that is
set to NULL. Normally, this situation should raise an exception simply
because one of the operands has an invalid 'gf' pointer.
I think it is quite reasonable in this situation that the polynomial knows
something about the field that it is defined over. How about replacing the
element_type of the polynomial with a type that represents the field? eg,

template <typename Field>
class Polynomial
{
public:
typedef Field field_type;
typedef typename field_type::value_type coefficient_type;

Polynomial(field_type const* F) : F_(F) {}

// ...

field_type const& field() const { return *F; }

private:
field_type const* F_;
std::vector<coefficient_type> Coefficients_;

// ...
};

Here, the field type has a nested typedef value_type which is the element
type of the field. You can also specify that the field class must have a
member function zero() that returns the zero element, and so on. eg,

struct Reals
{
typedef double value_type;
double zero() const { return 0; }
};

class GaloisField
{
public:
typedef GFElement value_type;

GaloisField(...){}// whatever parameters you need to specify the field

GFElement zero() const { return ... }
};

template <typename Field>
void some_function(Polynomial<Field> x)
{
if (x.coeffts[0] > x.field().zero()) ...
// ...
}

Does this sketch help?

In order to solve this dilemma, I set up an rule that: if 'gfValue' is
zero and the 'gf' pointer is NULL, the GFElement object is valid as
long as the routine that operates on that object does to use the 'gf'
pointer. If the above condition is met I will not raise an exception
and consider that situation as NORMAL.
I would think that most/all of the time that you would encounter such a
situation, it would not be a recoverable error but rather a logical error
in the program. Perhaps an assert() would be more appropriate? But if the
polynomial class has knowlege of the field, then it shouldn't be needed at
all.

So, my question would be: Is there a better way this situation could be
resolved ? or am I missing some big picture here ? What would Brian
Boitano do ?

Excuse my ignorance, who is Brian Boitano?

HTH,
Ian McCulloch

[Master of C++]

Thanks for your reply !

Do the properties of a given GaloisField instance ever actually
change? I find it a bit strange on first sight that it's not a
static (compile time) structure.
It is allowed to (and it does) change. There might be instances where I
will have to create Galois Field Elements that operate based on
different types of Galois Fields. So declaring the 'gf' pointer as
'static' is out of the question.
Regarding the comparison problem, maybe you can have constant
singleton objects representing special elements that compare to
members of any field, but don't belong to any implementation-wise?
This looks interesting. I will take a more closer look into it. In
fact, the values of "0" and "1" are common to ALL Galois Fields and
behave exactly the same way in all of them (in fact, they themselves
form a binary Galois Field - also known as a bit).
I hope the inconvenience of feeling the need to explain
that doesn't harm your taste for the music over time ;)

I had to write the postscript because I was flamed in my previous post
by C++ experts.

Thannks.
-Vijay.

[Master of C++]

> I think it is quite reasonable in this situation that the polynomial
knows

something about the field that it is defined over. How about replacing the element_type of the polynomial with a type that represents the field? eg,
...

Does this sketch help?

Definitely yes ! It is a very interesting suggestion. Even though I
have to create field definitions for all the built-in types, this
method is very generic in style and implementation.

I would think that most/all of the time that you would encounter such a situation, it would not be a recoverable error but rather a logical error in the program. Perhaps an assert() would be more appropriate? But if the polynomial class has knowlege of the field, then it shouldn't be needed at all.
Yes. I was initially a bit terrified at the thought of "allowing" an
"unitialized" object (with one of the member variables being a NULL
pointer) silently through a member function without exceptions. But
your suggestion makes this un-necessary.

Excuse my ignorance, who is Brian Boitano?

Brian Boitano is one of the best figure skaters in the world. The term
"What would Brian Boitano do ?" is consistently used in South Park (the
cartoon series) as a satirical take on "What would Jesus do ?". If ever
someone encouters a problem in life, just think - "What would Brian
Boitano do ?"

Thanks for your suggestion.
-Vijay.

[Ian McCulloch]

Master of C++ wrote:

I think it is quite reasonable in this situation that the polynomial

knows

something about the field that it is defined over. How about

replacing the

element_type of the polynomial with a type that represents the field?

eg,

...

Does this sketch help?

Definitely yes ! It is a very interesting suggestion. Even though I
have to create field definitions for all the built-in types, this
method is very generic in style and implementation.

Well, you can create a template class that will work for the builtins.

template <typename T>
struct SimpleField
{
typedef T value_type;
T zero() const { return T(0); }
};

Cheers,
Ian

[red floyd]

Ian McCulloch wrote:

Master of C++ wrote:

I think it is quite reasonable in this situation that the polynomial

knows

something about the field that it is defined over. How about

replacing the

element_type of the polynomial with a type that represents the field?

eg,

...

Does this sketch help?

Definitely yes ! It is a very interesting suggestion. Even though I
have to create field definitions for all the built-in types, this
method is very generic in style and implementation.

Well, you can create a template class that will work for the builtins.

template <typename T>
struct SimpleField
{
typedef T value_type;
T zero() const { return T(0); }
};

Cheers,
Ian

Or to be more general, and to avoid the proliferation of one-off
classes, perhaps a traits class?

template<typename T>
struct MyGenericTraits
{
typedef T value_type;
T zero() const { return T(0); }
bool is_positive(const T&) const { ... };
// etc...
};