PROGRAMMING IN THE AUTON PROJECT AND SCHENLEY PARK RESEARCH
                                       
   [INLINE]
   
                                   CONTENTS
                                       
     INTRODUCTION
     SIGNALLING ERRORS
     WAITING FOR A KEY PRESS
     RANDOM NUMBERS
     MEMORY ALLOCATION
     PICTURES
     ----- DRAWING FUNCTIONS:
     ----- COLOR FUNCTIONS:
     ----- NOW BACK TO APICTS
     VECTORS AND MATRICES
     ----- Important conventions for using dyms.
     ----- Basic operations on a dym (DYnamic Matrix)
     ----- Numerical operations on a dym (DYnamic Matrix)
     ----- DYVs (DYnamic Vectors)
     ----- Transformations between dyvs , dyms , 1-d arrays of doubles
     and 2-d arrays of doubles.
     ----- Making small dyvs and dyms
     ----- Complex matrix and vector operations
     FORMATTED REPORTS (EXPOS)
     ----- SECTION TYPES
     ----- FONT TYPES
     ----- OPERATIONS ON EXPOS
     
   
   
   [LINK]
   
                                 INTRODUCTION
                                       
   
   
   We use a specific style of C programming, which we call "The Allegheny
   Method" (AM). The basic idea is to put a few standards in place so
   that a group of us can follow each other's code and update it without
   any surprises.
   
   The most important thing is simplicity and understandability of code.
   Also important is modularity. The main formalism we use to achieve
   this is the "Abstract Data Type" style of programming, which could
   also be known as "Very Simple Object Programming Without The Fancy
   Little Crinkles."
   
   Our code will be run on many platforms under many operating systems
   and using many compilers. There must be nothing system-specific in the
   code.
   
   [LINK]
   
                              SIGNALLING ERRORS
                                       
   
   
   Call
   

      void am_error(char *message)

   
   
   This procedure never terminates, but ends the execution of the program
   and delivers the message. On some systems it offers the opportunity to
   enter the debugger.
   
   [LINK]
   
                           WAITING FOR A KEY PRESS
                                       
   
   
   Call
   

      void wait_for_key()

   
   
   When running on a console, prompts the user to hit a key. When running
   under a GUI brings up a dialog box. Words like "modal" and
   "preemptive" are probably involved.
   
   [LINK]
   
                                RANDOM NUMBERS
                                       
   
   
   We want the same sequence of random numbers for a given seed no matter
   which system we're on. The following random library is the one to use
   (thanks, Justin!) it passes randomness tests pretty well.
   

      void am_srand(int seed)

   seeds the random number generator
   

      void am_randomize()

   uses time of day based seed
   

      int int_random(int n)

   returns a random integer between 0 and n-1 inclusive
   

      double range_random(double low, double high)

   returns a uniform random double between low and high inclusive
   

      double gen_gauss()

   gaussian variable, mean 0, variance 1
   
   There exist other random functions, e.g. creating a random direction
   or random rotation matrix. Andrew will document this (Andrew!)
   
   [LINK]
   
                              MEMORY ALLOCATION
                                       
   
   
   We have our own versions of malloc and free. We use lots of allocating
   and freeing in the Allegheny Method style of programming, so we need
   it to be very fast and easy to debug. There are options for helping
   find and report memory allocation errors and memory leaks.
   

      char *am_malloc(int size)
      void am_free(char *memory, int size)

   Note you must tell us what size you are freeing. This is primarily as
   a check: in memory debug mode, am_free will check that the thing you
   are freeing was am_mallocked with the size you claim.
   
   Instead of using the above you will almost always want to use the
   following macros:

      &lttype&gt *AM_MALLOC(&lttype&gt)

   malloc something of type &lttype&gt and returns a pointer to it

      void AM_FREE(&lttype&gt *x, &lttype&gt)

   frees x which we are told is of type &lttype&gt

      &lttype&gt *AM_MALLOC_ARRAY(&lttype&gt, int array_size)
      void AM_FREE_ARRAY(&lttype&gt *x_array, &lttype&gt, int array_size)
      void am_malloc_report()

   put this at the very end of your program. It will warn you if anything
   remains unfreed.
   
   You can use runMLD to find memory leaks. Jeff will document this
   (hello Jeff!)
   
   [LINK]
   
                                   PICTURES
                                       
   
   
   The only abstract data type involved is called an apict. It represents
   a picture. Elements of these pictures may be circles, lines, strings,
   rectangles, and discs (solid circles).
   
   To begin drawing a picture, call void apict_on(). Then you may use any
   of the following functions to draw into a global picture defined on a
   square area of width and height 512.0 units, in which coordinates are
   represented by (x,y) pairs. The origin (0,0) is the bottom left hand
   corner. x (a double) is the horizontal distance. y (also a double) is
   the vertical distance.
   
   
   
DRAWING FUNCTIONS:

   

      void ag_dot(double x, double y)
      void ag_line(double u, double v, double x, double y)
      void ag_circle(double x, double y, double r)
      void ag_box(double x_botleft, double y_botleft, double x_tr, double y_tr)
      double x_topright, double y_topright)
      void ag_disc(double x, double y, double r)
      void ag_print(double x, double y, char *s)

   
   
   
   
COLOR FUNCTIONS:

   
   
   There are 16 colors which may be used (though that number may later be
   reduced to 8). The colors are represented by amut_colors, which are
   #defined integer constants from amxw.h. They have imaginative names
   like AG_RED.
   

      void ag_set_pen_color(int amut_col)
      int ag_pen_color()
      int ag_spectrum_color(double fract)

   fract should be in the range [0, 1.0]; this will return the amut color
   at the specified fraction of the way along an approximate rainbow
   spectrum (0.0 = red end; 1.0 = violet).
   
   
   
NOW BACK TO APICTS

   
   
   To create an apict call

      apict_on()

   , then do as much drawing as you like, then call

      apict *apict_off()

   , which AM_MALLOCs an apict, representing the picture you just drew.
   This also clears the global picture.
   
   To display the picture on Unix under X-windows, call render_apict().
   On Windows NT under Visual C++, the top level user interface has its
   own methods of rendering apicts, and all you have to do is return
   those apicts to the top level user interface.
   
   Here are other functions on apicts:
   

      void free_apict(apict *g)
      apict *mk_copy_apict(apict *ap)

   
   
   There also exist apict_sets for people who wish to produce sequences
   of pictures. Andrew will document this (Andrew!)
   
   There exists a way to turn apicts into compact Postscript files.
   Andrew will document this (Andrew!)
   
   [LINK]
   
                             VECTORS AND MATRICES
                                       
   
   
   Dynamic Matrices and Vectors
   
   The following routines are not clever, just sensible, efficient
   implementations of dynamic matrices. Here's an example of their use:
   

      #include "amdm.h"

      FILE *s = fopen(fname,"r");
      dym *dm = read_dym(s,NULL,NULL);  Creates a dynamic matrix from ascii fil
e
      dym *dmt = mk_dym_transpose(dm);  Creates its transpose
      dym *a = mk_dym_mult(dm,dmt);     Creates a square matrix
      invert_dym(a,a);                  Invert a and store the result in a.
                                        (No dynamic memory allocation... to
                                         dynamically make the inverse, do
                                         dym *ainv = mk_invert_dym(a) )
      fprintf_dym(stdout,"(d d$t)^-1",a,"\n");

      fclose(s);
      free_dym(dm);
      free_dym(dmt);
      free_dym(a);

   
   
   
   
Important conventions for using dyms.

   
   
   Dyms are addressed by (row,column) pairs, 0 < row <num-of-rows and 0 <
   col <number-of-columns.
   
   Some of the dym functions dynamically allocate memory. All such
   functions have names beginning with mk_
   
   Two of the dym functions free memory. They have names beginning with
   free_.
   
   All other named functions simply copy data between already-allocated
   memory.
   
   Many functions have a "mk_" form and a conventional copy form. The
   conventional form places the result in another argument of the call
   (which must have been pre-initialized to have the correct number of
   rows and columns). The name of an argument which gets stuff copied
   into it usually begins with r_ . The mk_ form creates an
   appropriately-shaped dym, computes the result, and returns the new
   dym.
   
   For example, here I explain two functions. The "copy" form of matrix
   addition which copies the sum of d_1 and d_2 into r_d. And the "mk"
   form dynamically creates and returns a matrix in which d_1 + d_2 are
   stored.
   

      void dym_plus(dym *d_1, dym *d_2, dym *r_d)
      dym *mk_dym_plus(dym *d_1,dym *d_2)

   
   
   Adds two matrices.
   
   Notes on using dynamic matrices: Remember that you should always free
   any dynamic matrices you create. Otherwise, their memory will remain
   allocated for the rest of the time the program runs, which may mean
   you run out of memory unexpectedly early.
   
   The functions below all obey what we'll call the "matrix memory
   convention" This means that the arguments to the functions are not
   directly changed, or have any part over-written, except for the result
   matrix, which is usually the last argument to the function, called
   "r_mat". Furthermore it is legal, and fine, to call the function with
   the matrix to be changed as one of the input arguments. For instance,
   to double the values inside a matrix defined by matrix *a you could
   call

      dym_plus(a,a,a)

   and after calling each element of a would be twice its normal value.

      dym_mult(a,a,a)

   squares a etc.
   
   
   
Basic operations on a dym (DYnamic Matrix)

   
   

      dym *mk_dym(int rows, int cols)

   Dynamically allocates the dym. The initial values are undefined.
   

      double dym_ref(dym *dm,int i,int j)

   Returns the (i,j)'th element of the matrix. May be implemented as a
   macro to improve speed. Indexing begins at zero: the jth element of
   the top row is dym_ref(dm,0,j), the ith element of the leftmost column
   is dym_ref(dm,i,0).
   

      double dym_set(dym *dm,int i, int j, double value)

   Sets the (i,j)'th element of the matrix to be value. See dym_ref for
   the indexing convenion.
   
   int dym_rows(dym *dm) gives the number of rows in the dym
   
   int dym_cols(dym *dm) gives the number of cols in the dym
   
   
   
Numerical operations on a dym (DYnamic Matrix)

   
   

      void constant_dym(dym *r_d,double value)
      dym *mk_constant_dym(int rows,int cols,double value)

   Sets all elements to be value
   

      void zero_dym(dym *r_d)
      dym *mk_zero_dym(int rows,int cols)

   Sets all elements to be 0.0
   

      void dym_scalar_mult(dym *d, double alpha, dym *r_d)
      dym *mk_dym_scalar_mult(dym *d,double alpha)

   Multiplies all elements of d by alpha.
   

      void dym_scalar_add(dym *d, double alpha, dym *r_d)
      dym *mk_dym_scalar_add(dym *d,double alpha)

   Adds alpha onto all elements of d.
   

      void copy_dym(dym *d, dym *r_d)
      dym *mk_copy_dym(dym *d)

   Creates a copy of the dym.
   

      void dym_plus(dym *d_1, dym *d_2, dym *r_d)
      dym *mk_dym_plus(dym *a,dym *b)

   Adds two matrices.
   

      void dym_subtract(dym *d_1,dym *d_2,dym *r_d)
      dym *mk_dym_subtract(dym *a,dym *b)

   Subtracts a matrix.
   
   
   
DYVs (DYnamic Vectors)

   
   
   dyvs are just one dimensional matrices. You can conveniently allocate
   and free them too using the same conventions as for dynamic matrices.
   

      dyv *mk_dyv(size)

   CREATES and returns one of the fellows.
   

      int dyv_size(dyv *dv)

   returns the number of elements in the dyv
   

      double dyv_ref(dv,i)

   returns the value of the i'th element. Indexing begins at 0: 0 < i
   <dyv_size(dv).
   
   All the numerical operations on dym's have counterpart numerical
   operations on dyv's:
   

      void constant_dyv(dyv *r_d,double v)
      void zero_dyv(dyv *r_d)
      dyv *mk_constant_dyv(int size,double v)
      dyv *mk_zero_dyv(int size)
      void dyv_scalar_mult(dyv *d, double alpha, dyv *r_d)
      dyv *mk_dyv_scalar_mult(dyv *d,double alpha)
      void dyv_scalar_add(dyv *d, double alpha, dyv *r_d)
      dyv *mk_dyv_scalar_add(dyv *d,double alpha)
      void copy_dyv(dyv *d, dyv *r_d)
      dyv *mk_copy_dyv(dyv *d)
      void dyv_plus(dyv *d_1, dyv *d_2, dyv *r_d)
      dyv *mk_dyv_plus(dyv *a,dyv *b)
      void dyv_subtract(dyv *d_1,dyv *d_2,dyv *r_d)
      dyv *mk_dyv_subtract(dyv *a,dyv *b)

   void dyv_sort(dyv *dv,dyv *r_dv); It is fine, as always, if dy and
   r_dv are the same.

      dyv *mk_dyv_sort(dyv *dv)

   
   
   
   
Transformations between dyvs , dyms , 1-d arrays of doubles and 2-d arrays of
doubles.

   
   
   We define dym = DYnamic Matrix dyv = DYnamic Vector farr = our
   notation for an array of doubles. If a is declared by double *a or
   double a[100], then a is a farr tdarr = our notation for a 2-d array
   of doubles IMPLEMENTED array of POINTERS to array of doubles. For,
   example, something created by am_malloc_2d_realnums(rows,cols). BUT
   NOT SOMETHING DECLARED BY a[100][30] which is implemented as a
   bloacking of 3000 doubles by the C compiler.
   
   There are a huge number of functions to copy, and make items of one of
   the above types into items of another of the above types.
   
   You can do the obvious copying between the following types:
   
   Source ->farr dyv tdarr dym Dest | | V
   
   farr - y - (y) dyv y - (y) (y) tdarr - (y) - y dym (y) (y) y -
   
   The (y)'s in parentheses have two kinds: copying to/from a column of a
   2-d structure to a 1-d structure or copying to/from a row of a 2-d
   structure to a 1-d structure.
   
   Thus, lets make a more complete table for 1-d copying and making:
   
   Source ->farr dyv tdarr_row tdarr_col dym_row dym_col Dest | | V
   
   farr - y - - y y dyv y copy_dyv y y y y tdarr_row - y - - - -
   tdarr_col - y - - - - dym_row y y - - - - dym_col y y - - - -
   
   And for 2-d: Source ->tdarr dym Dest V tdarr - y farr y copy_dym
   
   Including all the combinations of copying and making copies of, there
   are at least 50 such functions. To make life simple, theres are strong
   naming convention for all such functions:
   
   to copy from a &ltSource&gt x, to a &ltDest&gt y, call
   
   copy_&ltSource&gt_to_&ltDest&gt(x,y) e.g; double y[10]; dym *x =
   mk_constant_dyv(6,1.0); / Creates (1.0,1.0,1.0,1.0,1.0,1.0) /
   copy_dyv_to_farr(x,y); / Fills first 6 entries in y with 1.0 /
   
   to make a new thing of type &ltDest&gt from a thing of type
   &ltSource&gt do mk_&ltDest&gt_from_&ltSource&gt(x) e.g; dym *x =
   mk_constant_dym(2,3,9.0); / Creates ( 9.0 , 9.0 , 9.0 ) ( 9.0 , 9.0 ,
   9.0 ) / double *y = mk_tdarr_from_dym(x); / Creates
   
   BUT: Some functions need integer numerical arguments too. These always
   occur after the source and dest argument.
   
   To make a dyv from a farr you need to say how long the farr is, e.g. y
   = mk_dyv_from_farr(x,6) says to make a dyv of size 6 from the first 6
   elements of the array of doubles x. y = mk_dyv_from_dym_row(x,4) says
   to make a dyv from the the row indexed by 4 (which is of course the
   fifth row from the top) of the dym x.
   
   See also:

      dym *mk_dym_from_tdarr(double **tdarr,int rows,int cols)
      dyv *mk_dyv_from_tdarr_row(double **tdarr,int row,int tdarr_cols)

   ..which copies from the row of tdarr indexed by "row", and is told
   that tdarr has "tdarr_cols" columns

      dyv *mk_dyv_from_tdarr_col(double **tdarr,int col,int tdarr_rows)

   
   
   Finally, it is possible to make whole dym's directly from dyvs and
   farrs in the following three ways:
   

      dym *mk_&ltDYMSHAPE&gt_dym_from_dyv(dyv *dv)

   where &ltDYMSHAPE&gt is one of: row (creates a single-row-dym), col
   (creates a single-column-dym), diag (creates a diagonal dym)
   
   and

      dym *mk_&ltDYMSHAPE&gt_dym_from_farr(double *farr,int size)

   
   
   
   
Making small dyvs and dyms

   

      dyv *mk_dyv_1(double x)

   makes a 1-element dyv containing x as its only element

      dyv *mk_dyv_2(double x,double y)

   makes a 2-element dyv containing x as its 0th-indexed element y as its
   1-index element

      dyv *mk_dyv_3(double x,double y , double z)

   .... obvious.
   
   And also you can make any of the 9 smallest matrices thusly:
   

      dym *mk_dym_RC( ... )

   where R and C are each either 1 , 2 or 3
   
   and there are R * C arguments, which initialize (in lexical order x00,
   x01, .. etc) the dym. E.G:
   

      dym *d = mk_dym_32(1.0,2.0,3.0,4.0,5.0,6.0)

   
   
   allocates memory and creates a dym = [ 1.0 2.0 ] [ 3.0 4.0 ] [ 5.0 6.0
   ]
   
   
   
Complex matrix and vector operations

   
   
   See amdm.h for information about additional functions, including:
   
   dyv_scalar_product, dyv_dsqd, dym_times_dyv, mk_dym_times_dyv,
   dym_mult, mk_dym_mult, dyv_outer_product, mk_dyv_outer_product,
   dym_transpose, mk_dym_transpose, dym_scale_rows, mk_dym_scale_rows,
   dym_scale_cols, mk_dym_scale_cols, dym_svd, dym_determinant,
   dym_solve_vector, mk_dym_solve_vector, invert_dym, mk_invert_dym,
   is_dym_symmetric, attempt_cholesky_decomp,
   is_dym_symmetric_positive_definite, fprintf_dym, fprintf_dyv,
   dyv_outer_product, mk_dyv_outer_product, dym_transpose,
   dym_scale_rows, mk_dym_scale_rows, dym_scale_cols, mk_dym_scale_cols,
   dyv_mean, dyv_sdev, dym_min, dym_max, dyv_min, dyv_max, dyv_argmin,
   dyv_argmax, mk_dyv_1, mk_dyv_2, mk_dyv_3, mk_dym_11, mk_dym_12,
   mk_dym_13, mk_dym_21, mk_dym_22, dym mk_dym_23, mk_dym_ptq,
   mk_dym_transpose_times_dyv, mk_identity_dym, mk_dym_from_string,
   mk_nrecipes_matrix_from_dym, mk_nrecipes_vector_from_dyv
   
   [LINK]
   
                          FORMATTED REPORTS (EXPOS)
                                       
   
   
   A great deal of our software involves presenting information to the
   user, and we have a nice device-independent way of doing that. An expo
   is an abstract data type representing a formatted written report,
   which optionally may have multiple paragraphs, enumerated lists,
   indented subsections, a few different fonts, and tables. Functions
   exist to render expos on raw consoles, as HTML documents, and within
   Windows NT Visual C++ applications.
   
   
   
SECTION TYPES

   
   
   These are #defined int constants:
   
   NORMAL_SECTION_TYPE, INDENT, ITEMIZE, ENUMERATE, VERBATIM
   
   
   
FONT TYPES

   
   
   These are #defined int constants:
   
   NORMAL_EXPOFONT, ITALIC_EXPOFONT, BOLD_EXPOFONT, LARGE_EXPOFONT,
   HUGE_EXPOFONT, FIXED_EXPOFONT, HYPERLINK_EXPOFONT
   
   
   
OPERATIONS ON EXPOS

   
   

      expo *mk_empty_expo()

   makes a new empty document

      void free_expo(expo *ex)

   frees the expo

      char *exbuff(expo *ex)

   This is used in conjunction with sprintf for writing text into an
   expo. The programmer calls

      sprintf(exbuff(ex), &ltformat string> &ltprintf-style arguments>

   and the resulting words are placed at the end of the current
   paragraph. If there is no current paragraph, a new one is created.

      void expo_begin(expo *ex,int section_type)

   creates new paragraph of requested section-type

      void expo_end(expo *ex,int section_type)

   ends current section-type

      void expofont_open(expo *ex,int expofont)

   sets current font

      void expofont_close(expo *ex,int expofont)

   ends current font

      void expo_newline(expo *ex)

   forces a newline

      void expo_newpara(expo *ex)

   starts new paragraph of current section-type

      void expo_item(expo *ex)

   Starts new paragraph. Only to be used if section type is itemize (in
   which case new paragraphs begin with bullets) or if the section type
   is enumerate (in which case new paragraphs begin with the item
   number).

      void expo_include(expo *ex,expo *sub_ex)

   include all the text of sub-ex at the end of ex. ex is changed by
   this; sub-ex is not.

      void expo_end_document(expo *ex)

   Call this when you have finished the document. If you forget to do
   this, the text from the final sprintf(exbuff(ex), ...) may not be
   included.

      expo *mk_read_expo(FILE *s)

   read in an expo from a file

      void write_expo(FILE *s,expo *ex)

   write an expo to a file

      expo *mk_copy_expo(expo *ex)
      void expo_render_commented(FILE *s,char *comment,expo *ex)

   Type out the expo in plain text formatted as well as possible; assume
   80 characters per line; each line will begin with the string in
   comment.

      expo *mk_expo_from_string_matrix(string_matrix *sm)

   Use this in conjunction with string matrices to create tables. Andrew
   will document this further.
   
   See expo.h for information about the following functions:
   
   mk_expo_from_words, mk_expo_from_string_array, mk_expo_from_dym,
   mk_expo_from_dyv, expo_incfree, expo_include_fonted_string,
   expo_include_dyv, mk_oneline_expo