writes:

Quote:

>I'm dreaming of something that would have the effect of the following line,

>if the following line were legal for declaring the variable matrix (which,

>of course, it is not):

>if( matrixType == SPARSE ){

> SparseMatrixType *matrix; /* this is what I want to do */

>} else

> DenseMatrixType *matrix;

>}

In fact, those lines *are* okay; the problem is that the variable "matrix"

disappears after each "}", so that there is no variable "matrix" below

that. :-)

Quote:

>Last time I dared to dream of doing something fancy like this, I gave up,

>and was subsequently told by you guys not to give up so easily. So, do any

>of you smarty pants ;) know how to do this?

There *is* a way to do this in C, provided you are willing to change

your concept of "this" slightly.

Consider the following definitions:

typedef struct matrix mat;

/* operations on existing matrices */

struct matrix_ops {

mat * (*mo_copy)(mat *source); /* copy all data */

mat * (*mo_newzero)(mat *srcshape); /* copy shape only */

void (*mo_destroy)(mat *m); /* free */

void (*mo_add)(mat *result, mat *a, mat *b); /* r=a+b */

void (*mo_neg)(mat *result, mat *a); /* r = -a */

void (*mo_mul)(mat *result, mat *a, mat *b); /* r=a*b */

void (*mo_invert)(mat *result, mat *a); /* r = a^-1 */

/* maybe need an error code -- some matrices have no inverse */

};

(You might want to have add, neg, mul, and invert make new matrices

and return them, rather than writing their results into an existing

matrix, particularly since "mul" makes a matrix whose shape is

determined by the *two* matrices, not just a copy of a previous

matrix's shape. You must also decide, if you are going to write

the result to a "mat *result", whether "result" must be disjoint

from the two inputs. This is all just storage management mechanics,

though -- important mechanics, but not part of the "how do I do

dense and sparse through a single interface" problem.)

Now for the key parts:

/* extern struct matrix_ops denseops; -- these can be in */

/* extern struct matrix_ops sparseops; -- other files */

struct matrix {

/* m_type here is optional: */

/* int m_type; -- M_SPARSE or M_DENSE */

/* and could be an "enum" instead of an int */

int m_rows; /* number of rows */

int m_cols; /* number of colums */

struct matrix_ops *m_ops; /* operations on this matrix */

void *m_data; /* private to m_ops */

};

/* create new dense or sparse matrix */

mat *new_dense_matrix(int rows, int cols);

mat *new_sparse_matrix(int rows, int cols);

/* destroy existing matrix */

#define mat_free(m) (((m)->m_ops->mo_free)(m), free(m))

/* operate on existing matrices */

#define mat_copy(mat) (((mat)->m_ops->mo_copy)(mat))

#define mat_neg(r, a) (((a)->m_ops->mo_neg)(r, a))

#define mat_mul(r, a, b) (((a)->m_ops->mo_mul)(r, a, b))

#define mat_inv(r, a) (((a)->m_ops->mo_inv)(r, a))

/* etc */

Note that the choice of operand (a vs b) for reaching "mo_ops" in

mat_mul is arbitrary, but the target function ("dense multiply" or

"sparse multiply") should check that both operands have the same

type (same "m_ops" pointer, if m_type is omitted). The same

applies to mat_add and any other two-operand functions you decide

to have (mat_sub?).

If you want to be able to multiply sparse by dense (or vice versa),

you need to change the above slightly. You might as well take out

"mo_mul" and instead have a normal function that looks at both

operands and decides how to do the multiply. In this case, "struct

matrix" probably should also have the "m_type" field. You might

also want an element-accessor function in matrix_ops:

double *(*mo_locate)(mat *m, int row, int col);

/* fetch &m[r][c], as it were */

although for speed, you probably want to just "know about" the

internal representations for both sparse and dense matrices.

(Having an accessor also immediately exposes the matrix-element-type

-- here "double" -- although there are ways to hide that again as

well.)

The code to implement "new dense matrix", "new sparse matrix",

"invert sparse matrix", etc., can all go in one big file, or in

many separate little files, or in two separate files such as

"densemat.c" and "sparsemat.c". All that is really important

is that "new_dense_matrix" create a "struct matrix", fill in

the m_* fields, and point its m_ops at &denseops. Some source

file must initialize denseops.mo_copy, denseops.mo_invert, etc.,

as appropriate.

Some of this *looks* a lot nicer when done in languages with

operator and function overloading, but the actual details are

identical. In C++ you might say:

val = mat[i][j];

but it will compile to (in effect):

val = *mat->m_ops->mo_locate(mat, i, j);

just as you might write in C. The storage-management issues are

also messier in C, especially if you choose to have each function

allocate a new matrix for its result. This is where object-oriented

"automatic destructor" and/or garbage-collecting languages shine.

(On the other hand, storage management details often have an enormous

effect on speed, or lack thereof, and languages that hide it from

you also remove it from your control.)

--

In-Real-Life: Chris Torek, Berkeley Software Design Inc

--