Borland Programmer's Resource

home *** CD-ROM | disk | FTP | other *** search

/ Borland Programmer's Resource / Borland_Programmers_Resource_CD_1995.iso / code / bcpp / file19 / readme < prev next >

Wrap

Text File | 1995-05-19 | 14.0 KB | 354 lines

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