BLFMATH is the complete C++ source code
to sample vector and matrix classes, as
given in Chapter 7 of the book "Practical
Data Structures in C++."

BLFMATH is the complete C++ source code
to sample vector and matrix classes, as
given in Chapter 7 of the book "Practical
Data Structures in C++."
M A T R I X P A C K A G E
from the book
"Practical Data Structures in C++"
by Bryan Flamig

README FILE
August 23, 1993

Copyright(c) 1993 Azarona Software
All rights reserved.

INTRODUCTION
============

This is source code in C++ for implementing user-defined vectors and
matrices, as given in Chapter 7 of the book "Practical Data Structures
in C++", by Bryan Flamig, (John Wiley & Sons, ISBN 0-471-55863-X).

The classes as given here illustrate several nifty techniques for
handling vectors and matrices:

1. Both vector and matrix objects are reference counted. This allows
efficient assignment and returns from functions.

2. "Vector strides" are implemented. A vector stride is how many
physical elements of a vector make up one logical element. For
example, in a 4x4 row-major matrix, a row vector has a stride
of 1, a column vector has a stride of 4, and a diagonal vector
has a stride of 5.

3. "Smart pointers" known as vector pointers are introduced, as
invented by the author. These are pointers that know about
vector strides. Very efficient as the vector pointer class is
small and can be completely inlined.

3. Sub-vectors and sub-matrices are supported. These vectors can
matrices share their data with the original vector/matrix.

4. An efficient form of matrix transposition is shown, which does
not have to actually move the matrix elements around to
form the transpose. Smoke and mirrors are used instead 🙂
You can even transpose shared sub-matrices.

5. The matrix class is actually derived from the vector class.
Among other things, this allows the elements of the matrix
to be treated as a giant vector.

6. Vectors are dynamically allocated using overloaded new and
delete operators, to compact the elements and housekeeping
data needed for the vectors as tight as possible. The elements
are constructed using in-place construction via an overloaded
placement new operator.


There are tricks in this code that, as far as I know, have
not been published anywhere else, such as a clean and elegant
way of implementing "smart" pointers that know about vector
strides.

If you like what you see, you may be interested in picking up a
copy of the "Practical Data Structures in C++" book, since it is
chock-full of examples like this.


COPYRIGHTED SOFTWARE
====================

The source code is copyrighted by Azarona Software, but I'm
providing it to you free of charge. You are free to experiment
with the code, include it in your own applications, personal
or commercial. HOWEVER, YOU MAY NOT DISTRIBUTE THE SOURCE CODE
FOR A PROFIT OR FEE OF ANY KIND WITHOUT THE EXPRESS WRITTEN
PERMISSION OF AZARONA SOFTWARE. YOU MAY ONLY DISTRIBUTE THE
CODE IN OBJECT (COMPILED) FORM, AND ONLY IF MADE A PART OF
YOUR PACKAGE, AND NOT BY ITSELF.

You are granted permission to give away the source code to
friends, upload the files to a BBS, etc., AS LONG AS NO FEE
IS CHARGED FOR THE SOFTWARE, AND AS LONG AS THE FILES ARE
DISTRIBUTED EXACTLY AS GIVEN HERE, WITH THE SAME FILE NAMES,
THE SAME NUMBER OF FILES, AND THE COPYRIGHT NOTICES INTACT.
YOU MAY NOT INCLUDE THE SOURCE AS PART OF A COMMERCIAL PACKAGE,
OR ANY PACKAGE SOLD AND DISTRIBUTED FOR ANY FEE OR PROFIT OF
ANY KIND. You may "zip" the files into a single-file archive,
if you wish.


SOURCE CODE PROVIDED AS-IS
==========================

Azarona Software provides this source code as-is. USE THE
SOFTWARE AT YOUR OWN RISK. While the software has been tested
extensively, we make no representations about its suitability
or robustness, and do not take any liability for the use of
the software.


FEATURES OF THIS SOURCE CODE
============================

The source code as provided implements the following classes:

SimpleMatrix A simple matrix class that illustrates
how to construct dynamic, user-defined
matrices, and how to use vector pointers
in conjunction with matrices.

VecPtr A "smart" pointer class that knows about
vector strides. Very slick.

Vector A reference-counted vector class that
forms the backbone of the Matrix class

Matrix A reference-counted matrix class that
supports sub-matrices and transposition
that does not require elements to be
shuffled around.

Shape This is just a test class used to verify
that the constructors/destructors for
vector and matrix elements are called
the right number of times.


WHAT COMPILERS YOU MAY USE
==========================

The code was developed using BC++ 3.1, and was tested with the
latest Cfront compiler in Unix as well. The code uses many
sophisticated C++ features, all of which are legal C++
as defined in the C++ Annotated Reference Manual, (the "ARM",
currently the de facto standard reference for C++). Unfortunately,
some current compilers won't be able to handle what's given
here. Most of the problems are due to the template code. (I use
templates in some "strange" ways, that many compilers complain
about.) This will become less of a problem as time goes on, and
the compilers "catch up" to the standard.


DESIGN OF THE MATRIX CLASS
==========================

The Matrix class implements dynamic, two-dimensional matrices.
These matrices are reference-counted, which allows more convenient
methods of performing assignments and returning matrices from
functions. Integral to the Matrix class is the Vector class.
A Vector object is basically an array whose elements can be
non-contiguous. That is, the stride of a Vector may be greater
than one. Using vector objects, you can conveniently manipulate
the rows, columns, and diagonals of a matrix as though they
were arrays.

With both the vector and matrix class, you can turn range-checking
on for the subscripts, at compile time. With range-checking turned
off, no overhead accrues at run-time. The range-checking uses a
user-defined error handling routine. Obviously, exception handling
would be nice here.

Several forms of subscripting are provided to illustrate
different ways of accessing matrix elements. First, there is
the standard "double-subscripting" method, eg: m[42][17]. Then,
there is the "2-d" method, eg: m(42, 17). Also, you can return
row, column, or diagonal vectors and work with those. Also,
you can return "vector pointers", which are low-level forms
of vectors that do not do range-checking. Using vector pointers,
you can implement operations such as matrix multiply very
efficiently.

Rigorous but slightly obtuse design: The source code was designed
rigorously to handle constant vectors, matrices, etc. Because of
this, and the fact that the classes are all defined as templates,
the source may look a little obtuse at first.


INTENT OF THE MATRIX PACKAGE
============================

This package is provided as an illustration of some important
C++ techniques that can be used for working with vectors and
matrices. While the fundamental design is sound, it isn't
necessarily complete. There are many matrix operations that
obviously aren't supported, (such as taking determinants, etc.)
but ought to be. And vice versa, there are some operations
supported that maybe don't need to be, (such as rigorous handling
of constant objects, sub-matrices, etc.)


SOURCE CODE DOCUMENTATION
=========================

The source code as given is fully described in the "Practical Data
Structures in C++" book. Here we provide documentation only in the
form of comments in the code. (The code is heavily commented,
though.)


SAMPLE TEST PROGRAMS
====================

There are numerous test programs provided that may not do
a whole lot of useful things, but they do exercise the
features of the matrix package. Some of the test programs
use "Shape" objects as the matrix elements. The Shape class
was designed to test how constructors and destructors are
called, and is useful in ensuring that the matrix and
vectors clean up after themselves properly.

Some of the test programs check how efficiently matrix
multiplies are handled, which should give you some idea
on the overhead accrued by these classes. (Any time you
make something general, performance is bound to suffer.)
Using low-level vector pointers, it's possible to make
matrix operations fairly efficient, with roughly a 30%
drop in performance over using hard-coded, statically
sized matrices. It would appear that most of the
performance drop is due to dynamically sizing the matrices,
and not due to that fact that sophisticated operations
such as "smoke and mirrors" transpositions are supported.


PACKING LIST
============

This distribution should contain the following files:


MATRIX.H The matrix template header and "methods" file
MATRIX.MTH

PLACENEW.H Contains a definition for the placement new
operator. With some compilers, you may not
need this.

RANGE.H Header and source files for handling subscript
RANGEERR.CPP range errors.

README This readme file

SHAPE.CPP Source and header file for a "Shape" class used
SHAPE.H for testing proper construction/destruction of
matrix and vector elements.

SIMPMAT.H A simplified matrix class used to illustrate
SIMPMAT.MTH how to create dynamically sized matrices, and
how to use vector pointers.

TSTMAIN.CPP An include file of source used by some of the
test programs that tests proper construction
and destruction of elements.

TSTMAT.CPP First test program for the Matrix class. Tests
TSTMAT.MAK the creation of matrices, and basic operations
TSTMAT.PRJ such as copying, sub-matrices, transpositions, etc.

TSTMAT2.CPP Like tstmat.cpp, except Shape elements are used,
TSTMAT2.MAK to test proper construction/destruction of elements
TSTMAT2.PRJ

TSTMAT3.CPP Tests performance of matrix multiplies, using
TSTMAT3.MAK various forms of accessing the matrix elements.
TSTMAT3.PRJ

TSTMAT4.CPP Like tstmat3, but also includes a full comparison
TSTMAT4.MAK of using hard-coded static matrices versus the
TSTMAT4.PRJ general user-defined matrices.

TSTSMAT.CPP Test program for the SimpleMatrix class.
TSTSMAT.MAK
TSTSMAT.PRJ

TSTSMAT2.CPP Like tstsmat.cpp, except shape elements are used
TSTSMAT2.MAK to test for proper construction/destruction of
TSTSMAT2.PRJ matrix elements.

TSTVEC.CPP Test program for the Vector class. Tests features
TSTVEC.MAK such as sharing slices of other vectors, etc.
TSTVEC.PRJ

TSTVEC2.CPP Like tstvec.cpp, except Shape elements are used to
TSTVEC2.MAK test proper construction/destruction of elements.
TSTVEC2.PRJ

VECPTR.H The vector pointer class template header file

VECTOR.H The vector class header and methods file
VECTOR.MTH


ABOUT THE PRACTICAL DATA STRUCTURES BOOK
========================================

Practical Data Structures in C++
by Bryan Flamig
John Wiley & Sons
ISBN 0-471-55863-X

If you're looking for an eminently readable data structures book
written for C++, you've come to the right place. The book covers
data structures from a practical point of view, with clearly
explained examples. For the topics covered, there are no mysteries
left to the reader to unravel: you won't have to spend days trying
to figure out how to accomplish something described in this book.
For example, some books talk about red-black trees, splay trees,
and B-trees, but neglect to show you how to delete entries from
these trees! In this book, each operation of these data structures
is fully explained and laid out. And since complete code is provided
on the accompanying disk, you can put the code to work immediately.
This book:

* Presents high-quality code, very carefully designed and
crafted specifically for C++, with efficiency and elegance
a top priority.

* Makes extensive use of C++ templates, the first book of its
kind to do so.

* Covers concrete data types, abstract data types, resizable
arrays, smart pointers, strings, vectors, matrices, linked
lists, stacks, queues, binary trees, red-black trees, splay
trees, file-based objects, caching and B-trees.

* Includes several techniques never before published, such as
template-based vector pointers and cached-object pointers,
and in-place construction of array elements.

The programming techniques shown in this book were crafted spec-
ifically for C++, and the code given is not simply a rewrite of
code written in C, Pascal, or some other language. Each data
structure discussed in the text and demonstrated on disk has
been designed to take advantage of the special features of C++.

If C++ is you language of choice, Practical Data Structures in C++
will show you the most effective and practical ways to store data.


ABOUT THE AUTHOR
================

Bryan Flamig is a software developer and consultant specializing in
C++ programming. He is the author of numerous books, including the
popular "Turbo C++: Step by Step", and coauthor of "Object-Oriented
Programming with Turbo C++", and of course, the author of "Practical
Data Structures in C++", all published by John Wiley & Sons.

Besides consulting and writing books, Bryan also gives training
seminars focusing on C++. You may reach Bryan at:

Azarona Software
P.O. Box 768
Conifer, CO 80433

(303) 697-1728 Fax
73057,3172 CompuServe