ChiLib Library Documentation

1. Introduction

1.1. Library contents and limitations

This library is a mixture of classes, some advanced, some simple, to 
accompany the book `Mastering Object-Oriented Design in C++'. It is called 
ChiLib, which of course is an acronym for `Cay Horstmann's Interesting 
Library'. This name was chosen in desperation after it was noticed that 
every single word in the English language containing the letter sequence 
`oo' was already in use by some vendor as an acronym for an object-oriented 
product. 

The graphics classes are not intended to be a professional-level set of 
classes. They are directly tailored to this book, and its many 
inefficiencies make them unsuitable for general-purpose programming. The 
same holds for the date class, the graphics editor and simulation 
frameworks, and the persistent stream class. The code for all these classes 
(with the possible exception of some wizardry in the persistent streams) is 
intended to be read and understood by students. 

The list, queue, and priority queue templates are not particularly 
efficient, but the code is accessible to the interested reader. Like most 
libraries on the market, they are also somewhat unsafe: Iterators can point 
to deleted elements or be attached to destroyed lists. Using such iterators 
leads to `undefined behavior'. Professional-level templates should use copy 
on write and safe iterators, but that would make the code much harder to 
read. 

The array template and string classes are highly optimized for efficiency, 
and the code is neither accessible nor particularly interesting from the 
perspective of object-oriented design. They have proven to be marvelous 
tools to eliminate the drudgery of managing pointers and heap memory. They 
are quite efficient--certainly ample for instructional and prototyping use.

The class for argument parsing is a simplified version of a professional-
level class, with some of the more confusing options removed. In this book, 
it is used only to eliminate the need to use C strings in parsing command 
line arguments.

1.2. Name prefixes

The names in the library (Array, String, List, Date) are, of course, highly 
susceptible to clashes with other names in the compiler vendor's library. 
Unfortunately, at the time of this writing, no compiler actually supports 
name spaces. Eventually, the library will use a 

      namespace Cay_Horstmanns_Interesting_Library

but at the time of this writing, all classes and templates are prefixed 
with Chi_, such as Chi_Array, Chi_String, Chi_List, Chi_Date. 

In all documentation and printed code samples in this book, the Chi_ prefix 
is not included because it just clutters up the code. (Of course, the code 
on the disk has the prefix.) Library users must remember to supply the 
prefix in actual code. This sounds like yet another nuisance, but it has 
proven not to be a problem in practice.

1.3. Error handling

At the time of this writing, the majority of compilers did not yet support 
exception handling. The library error handling throws exceptions when they 
are available and generates assertion failures when they are not. 
Exceptions are reported through classes derived from Error (that is, 
Chi_Error--this won't be mentioned again). This is independent of compiler 
support for exceptions. If the compiler doesn't support them, the library 
just won't throw the Error object but instead print it to cerr and 
terminate. 

If no exception support is available from the compiler, the library ensures 
that assertion failures are raised from a specific function Error::abort. 
Set a breakpoint in that function to trap the error and inspect the call 
stack. Once the program is aborted, the call stack is gone and it is 
difficult to find the cause of the error. (Of course, the error object 
stores and prints the file name and line number of the code that generated 
the error, but that is the library code. Knowing that an array bounds error 
occurred in file chiarray.cpp, line number 151, doesn't help much.) 

1.4. Organization of files

The ChiLib files are distributed on three directories: include, source, and 
sample. A fourth directory, lib, should be built if a library archive of 
the code is desired. 

The optimal setup is the following: 

      Place a directory, chilib, at an appropriate place (under /usr/local 
       or \spring95\cs151 or whereever), and make subdirectories include, 
       source, sample, and lib. 

      Compile all files in the source directory and make them into a 
       library archive. Place it into the lib directory. A make file to 
       build the library for some compilers is supplied. 

      Add the path to the chilib\include subdirectory to the compiler's 
       path for searching include files, the path to chilib\lib to the 
       linker's path for searching libraries. The method for achieving that 
       differs from one compiler to the next. 

To use the library, the user simply includes the appropriate header file, 
such as <chiarray.h>, and builds the program in the normal way. 

The optimal setup requires more control over the computing environment than 
instructors and students typically have. An alternate setup is less 
efficient but does not require system administration knowledge or 
privileges. This setup presumes that you have a private directory to work 
on the book lessons. Do the following. 

      Copy the source and include files onto the work directory. They all 
       start with chi....., to make them easy to identify if you want to 
       move to them to another computer or (gasp!) delete them. 

      Make a subdirectory sample under your current directory to hold the 
       sample files. 

1.5. Building programs

The library contains the following header files:

     Header file Purpose                                                                                         
     chiargs.h   Command line arguments                     
     chiarray.h  Arrays                                     
     chidate.h   Date                                       
     chierror.h  Error handling                             
     chigcxxx.h  Graphics context                           
     chilist.h   Linked lists                               
     chiprioq.h  Priority queues                            
     chimap.h    Maps                                       
     chiqueue.h  Queues                                     
     chisetup.h  General setup--included by other headers   
     chishape.h  Shapes                                     
     chistrng.h  Strings                                                                                         

You should include them in the normal way, with the preprocessor directive 

      #include "chixxxxx.h" 

(You can use #include <chixxxxx.h> if the chilib\include directory has been 
added to the search path for header files. That saves a millisecond or so 
by skipping the search on the current directory.) When including chigc.h, 
you must #define one of CHI_BGI, CHI_WIN, or CHI_X11.

To build a program containing one or more library components, you have two 
choices. The simpler one for everyday work requires that you (or a 
knowledgeable person such as the system administrator) precompile all 
library sources to a library archive (chilib.lib or chilib.a). You then 
direct the compiler to search that library. Instructions differ for each 
compiler. Make files for some compilers have been provided. Under DOS and 
Windows the memory model matters, and you need to specify chilibs for small 
and chilibl for large model. 

The other choice is to add all source files that you need to the current 
project. For example, if you use shapes, you need to include chishape.cpp, 
chigc.cpp, chiarray.cpp, chistr.cpp, and chierror.cpp, and of course the 
source file(s) including your own code. The old-fashioned method is to 
write a make file, but most modern compilation environment have a tool to 
specify projects in a more convenient way. 

All modules require that chierror be present. There are several different 
implementations of the graphics context: chigcbgi for the Borland Graphics 
Interface under DOS, chigcwin for Windows, and chigcx11 for Xlib. If you 
forget to include a module in the project, the linker will complain about 
unresolved external names. The names should give you a hint which module is 
missing.

2. Arrays

2.1. Introduction

Array is a `smart array' class template.  Unlike the more dangerous and 
inconvenient C arrays, Array objects handle their own storage: They have 
associated operations that make accessing and manipulating their contents 
less prone to memory overruns and indexing mistakes.

An Array object is a container and so `contains' other objects: usually 
user-defined classes, but also pointers or numeric types (doubles, for 
instance). Here is an array of Customer objects:



      Customer joe, harry, tran;

      Array<Customer> a(1, 10); // declare an array of 10 Customers
      Array<double> d(0,4); // an array of five doubles.
      a[1] = joe;
      a[10] = tran;
      Array<Customer> b = a; // declare another array as a copy of a
      // b has space for elements 1...10, just like a.
      // b[1] contains joe, b[10] contains tran
      b[1] = harry;
      // a[1] still contains joe, b[1] now contains harry.  

Contrast this with C arrays and pointers:

      Customer a[11];   // C arrays always start at 0
      a[1] = joe;
      a[10] = tran;
      Customer* b = a; // Customer b[11] = a;  is illegal
      b[1] = harry;
      // now both a[1] and b[1] contain harry

The documentation just refers to the template as Array. Of course, you must 
add the <...> to instantiate a specific array class.

2.2. Construction

      Array();
      Array(int low, int high);

The default constructor initializes the instance to an empty array; you 
must use the set or grow operation (described in the following section) to 
allocate a range for elements.  The second constructor establishes the 
initial low and high indices of the array. Note that any integers are valid 
as long as low  high. In particular, low need not be zero, and low, high, 
or both can be negative.

      Array<Customer> a; 
         // creates an empty array
      Array<double> b(-10, 10);      
         // an array, with valid range b[-10]..b[10]

2.3. Resizing

      void grow(int low, int high);
      void shrink(int low, int high);
      void empty();

The grow operation ensures that the array contains at least the index range 
low ... high, expanding the low or high bound, or both, as necessary. The 
array is not reduced in size. That is, elements that are below low or above 
high are not removed. 

The shrink operation ensures that the array contains no more than the index 
range low ... high, reducing the low or high bound, or both, as necessary. 
The array is not increased in size. That is, no new elements are created if 
the bounds are already less than those specified in the arguments.

The empty operation removes all elements of the array, making it into an 
empty array. 

2.4. Element access

      void set(int i, const X& t);
      X get(int i) const;
      X& operator[](int i);
      const X& operator[](int i) const;

The set operation sets the ith element of the array to the value of t. If i 
is not within the current array bounds, the array grows to include i. 

The get operation returns a copy of the value at position i. If i is not 
within the current array bounds, a default value is returned. Don't use get 
to try to change an array element. The code

      a.get(i).change(); // DON'T

changes the copy of a[i] that get returns and then abandons the copy. 

The [] operator allows both read and write access to the element at 
position i. But applying [] does not grow the array. Instead, it triggers a 
bounds error. This was not done just to be difficult, but for technical 
reasons. 

Use get/set when possible. They are always safe. 

There is, however, one reason to use []: for in-place modification. It is 
easier and more efficient to change an object in place,

      a[i].change();

than it is to do a get/change/set sequence,

      X x = a.get(i);
      x.change();
      a.set(i, x);

Here are some examples:

      Array<double> a(1, 10); // a is a 10-element array, a[1]...a[10]
      a.set(20, 400.0); // now bounds are 1...20
      a[30] = 900.0;  // NO--Bounds error
      double x = a.get(30); // OK--x is set to 0
      x = a[30]; // NO--Bounds error
      a[20] += 10.5; // In-place modification. Now a[20] is 410.5

2.5. Bounds range

      int length() const;
      int low() const;
      int high() const;

The length operation returns the number of elements in the array. The low 
and high operations return the lowest and highest array index, 
respectively. The latter are typically used to traverse an array:

      for (int i = a.low(); i <= a.high(); i++)
         do something with a[i];

An empty array arbitrarily has low bound 0, high bound -1, and, of course, 
length 0. 

2.6. Inserting elements

Inserting elements into the middle of an array is not efficient. The 
elements above the insertion point must be moved up, or the entire array 
needs to be reallocated if there isn't enough space to hold the inserted 
values. Nevertheless, it is a convenient operation, and for many programs 
the inefficiency is not important. 

    void insert(int i, X x)
    void insert_range(int start, int count);
    void append(X t);

The insert operation inserts x at location i, moving the  elements above i 
up by 1. The insert_range operation inserts count elements, beginning at 
element start, and shifts higher elements up as appropriate. The newly 
created elements are filled with default values of type X. 

The append operation places x into the element with index high()+1. No 
elements are shifted. If the array is empty, x is inserted at location 0. 

      Array<int> a(1, 10);
      a[3] = 100;
      a.insert(3, 90); // a[3] is now 90, a[4] is now 100, etc.
      a.append(410); // a[11] is 410
      a.insert_range(3, 10); // now a has 20 elements
         // a[3] ... a[12] are 0, a[13] is 90

2.7. Removing elements

      X remove(int i);
      void remove_range(int start, int count);
      void empty();

The remove operation removes the element at index i from the array, 
shifting higher element down as needed, and returning the value. If i is 
out of bounds, a default value is returned. The remove_range operation 
removes count elements, beginning with the position start, shifting 
elements with higher index down.

The empty operation removes all elements from the array.

      Array<int> a(1, 10);
      for (int j = a.low(); j <= a.high(); j++)
         a[j] = j*j;
      int c = a.remove(5); // c is 25
      a.remove_range(2, 4);
      int d = a.get(2); // d is 49
      a.empty(); // now a is empty

2.8. Sorting

    void qsort (int (*compare) (const X&, const X&));
    void qsort (int (*compare) (const X&, const X&), 
         int from, int count);

These perform a quicksort on the array. In the latter, only the subrange of 
count elements of the array, beginning at from, is sorted. 

To sort an array, you must specify how to compare elements. You do that by 
supplying a comparison function. A comparison function takes two objects a 
and b of type X and compares them. (Actually, for efficiency, the 
comparison function takes two constant references to the objects.) It 
should behave like this:

      if a < b, then return an integer less than 0
      if a = b, then return 0
      if a > b, then return an integer greater than 0

Here is a typical example. We want to sort an array of customers, first by 
age, and by name within the same age. Write the following function:

      int compare_cust(const Customer& a, const Customer& b)
      {  int d = a.age() - b.age();
         if (d != 0) return d;
         return a.name().compare(b.name());
      }

Then call

      Array<Customer> a;
      a.sort(compare_cust);

2.9. Array parameters

You can use smart arrays as function parameters. Like all C++ objects, but 
unlike C arrays, the array parameter is a copy of the array that is passed 
to the function. Modifying the copy is legal but has no effect on the array 
supplied by the caller. If you want to write a function that modifies the 
array, then pass it by reference:

      void raise_salaries(Array<Employee>& staff, double perc)
      {  for (int i = staff.low(); i <= staff.high(); i++)
            staff[i].raise_salary(perc); 
      }

If you do not write to the array, it is strongly recommend that you do not 
use [] to access the array for reading. The [] operator cannot tell whether 
it is invoked for reading or for writing, so it forces a copy of all array 
elements the first time it is applied. Just use get. 

      double average_salary(Array<Employee> staff)
      {  double d = 0;
         for (int i = staff.low(); i <= staff.high(); i++)
            d += staff.get(i).salary();
         if (staff.length() > 0) d = d / staff.length();
         return d;
      }

Alternatively, if you declare the array argument as a const or const&, you 
can use [] because the const version of [] cannot be used for writing. 

      double average_salary(const Array<Employee>& staff)
      {  double d = 0;
         for (int i = staff.low(); i <= staff.high(); i++)
            d += staff.get(i).salary();
         if (staff.length() > 0) d = d / staff.length();
         return d;
      }

This is a subtle point, and you can ignore it if you are not concerned 
about efficiency. 

2.10. Reallocation

An array object always stores its elements as a single block of contiguous 
memory. That makes element access efficient, and it also makes it easy to 
locate and inspect elements during debugging. When a block is allocated, a 
few additional elements are supplied to anticipate further growth. 
(However, upon construction the array is sized exactly as specified in the 
construction arguments.) Eventually, as the array grows, it runs out of 
space, and the associated memory block must be reallocated. 

This means that you should never take the address of an array element a[i]. 
That address becomes invalid as soon as the memory block relocates, and the 
element is moved elsewhere. This is the reason the [] operator does not 
grow the array. If it did, statements like 

      swap(a[i], a[i + 100]);

would fail mysteriously if the compiler evaluated the reference a[i], and 
then a[i+100], and the array was relocated during the second computation. 

All functions that relocate the array have been designed to have a void 
return value. Hence, no subexpression can trigger array relocation and 
invalidate a [] reference in another subexpression. 

2.11. Template variants

A PtrArray template implements arrays of pointers. Semantically, 
PtrArray<X> is equivalent to Array<X*>. A NumArray<X> template implements 
arrays of numeric types (int, double, and so forth). For types without a 
copy constructor and destructor, NumArray<X> and Array<X> are semantically 
equivalent.

There are two reasons to use the template variants. First, they are much 
more efficient, by sharing common code and performing bitwise copies. More 
importantly, some compilers have faulty template implementations that make 
it impossible to use the Array template on non-class types. However, the 
template variants have one major disadvantage: The code sharing is achieved 
through the use of char blocks or void* pointers, and the array elements 
cannot be inspected in the debugger. 

2.12. Default values

A few operations on arrays, as well as the other containers, are designed 
to return a default value when an out-of-range access is performed. That 
default value is guaranteed to be zero for numeric types and pointers. For 
class types, it is an object constructed with the default constructors. If 
a class doesn't have a default constructor, you cannot store it in a ChiLib 
container. The remedy is usually simple: Add a default constructor that 
does nothing to the fields of class type, but zeroes out the numeric and 
pointer fields:

      class Customer
      {
      public:
         Customer(); 
         Customer(String _name, int _age);
         // ...
      private:
         int _age;
         String _name;
      };

      Customer::Customer() 
      :  _age(0) 
      {}

That is not always acceptable, and it may be impossible to produce a 
reasonable default that fulfills the class invariant. (The Date class has 
that problem, and it `solves' it by producing an unreasonable default.) 

If you cannot add a default constructor, you can still store pointers to 
classes in the containers, but you are then responsible for heap allocation 
and deallocation of the objects to which those pointers point.

3. Strings

3.1. Introduction

ChiLib provides a convenient String class that implements strings with 
complete memory management and value copy semantics, replacing the need for 
char* C strings. The string class has essentially the same interface as the 
proposed ANSI string class, and you may want to use the latter if your 
compiler supports it. The major addition is support for fields or tokens. 

3.2. Construction

      String();
      String(const char s[]);
      String(char ch);

The default constructor creates an empty string (of length zero).  The 
second variant accepts a C string--usually a literal "...". The third 
variant accepts a single character--variable or literal. 

Most string operations are similarly overloaded to take C strings and 
characters. For simplicity, these overloaded versions are not listed in 
this documentation.

      char h[] = "Hell";
      char w = ' ';
      String a(h);
      String b('o');

      String c(w);
      String d("World");
      String e;
      String f('!');

      cout << a << b << c << d << e << f << endl;
         // prints Hello World!

3.3. Element access

      char get(int i) const;
      void set(int i, char ch);
      char String::operator[](int i) const;
      char& String::operator[](int i);

The get and set operations return and change, respectively, a particular 
character in a string.  To prevent C programmers from going mad, the first 
character is at index 0. If the index i is out of the string's current 
range, set will grow the string to include the character within the string 
(padding with spaces) if necessary.

The bracket operator behaves as one would expect, except that it does not 
grow the string. Attempting to access an element of the string outside the 
string's current range with brackets results in a run-time error.

      String s("Brisco");
      char c1 = s.get(5); // c1 is o
      char c2 = s[5]; // ditto for c2
      s.set(0, 'F'); // Frisco
      s[2] = 'e'; // Fresco
      s[10] = 'L'; // error caught
      s.set(11, 'B'); // string is grown

3.4. Length

      int length() const;
      Bool is_empty() const;

The length function returns the number of characters in the string. The 
is_empty returns true if and only if the the string has zero length.

s[s.length()] is legal and returns a zero. Any attempt to modify that value 
has no effect. Strings may contain zero bytes, so length() is not 
necessarily the offset of the first 0 in the string.

      String a("Foo");
      int i = a.length(); // i equals 3
      if (!a.is_empty()) cout << a << endl;

3.5. Comparison

      int compare(const String& b) const;
      int compare(const String& b, int n) const;
      int compare_insens(const String& b) const;

      static int compare(const String& a, const String& b);
      static int compare_insens(const String& a, const String& b);
      static int hash(const String& a);

The single-argument compare functions perform a lexicographic comparison 
between the instance's string and the argument's.  If the strings are 
equal, the functions return 0.  If the instance's string is 
lexicographically less than the argument's, the function returns an integer 
less than 0.  Otherwise, the function returns an integer greater than 0.  
The dual-argument versions behave the same way, except that only a maximum 
of n characters are compared.

The compare_insens operation performs case-insensitive comparisons.

      String s("abcdexg");
      int i = s.compare_insens("XYZ"); // a negative number
      int j = s.compare("XYZ"); // a positive number

The operators == != < <= > >= are overloaded to call compare.

      String s("abcdexg");
      if (s < "XYZ") ... // the condition is FALSE

The shared (static) functions are used as comparison functions for sorting. 
They are functions, not class operations, because several templates require 
function pointers as arguments. 

      Map<String, double> m(String::hash, String::compare);

3.6. Concatenation

      void append(const String& s);

The overloaded + operator concatenates two strings, returning a new string 
holding the result. The append operation modifies a string by appending 
another. The += operator is a synonym for append.

      String s = "What";
      String t = s + "'s";
      t.append(" up, ");
      t += "Doc?";
      cout << t; // prints What's up, Doc?

3.7. Inserting and removing characters

      void insert(int at, char ch);
      char remove_char(int at);

The insert operation inserts a character at position at, shifting all other 
characters up by 1. If at is beyond the end of the string, the string is 
padded with spaces up to position at - 1.

The remove operation removes and returns the character at position at. If 
at is beyond the end of the string, remove returns 0 and does not change 
the string.

3.8. Substrings

      String substr(int from, int n) const;
      void insert(int at, const String& s);
      String remove(int from, int n);
      void replace(int from, int n, const String& s);
      void replace(int from, int n, char ch);

The substr operation returns a copy of the substring starting at from and 
containing up to n characters (fewer if the end of the string is reached 
first); remove returns that substring and removes it from the original. If 
n is not specified, the substring extends to the end of the string. The 
insert operation inserts a substring at position at, padding with spaces if 
at is beyond the end of the string.

The replace functions replace the instance's substring that starts at from 
and is n characters long with s or ch. 

3.9. Fields

      String field(int n) const;
      String insert_field(int n, String s);
      String remove_field(int n);
      String replace_field(int n, String s);

These operations consider a string as a sequence of fields, or tokens, 
delimited by white space. The field operation returns a copy of the nth 
token, whereas remove_field returns the token and removes it from the 
string. The insert_field operation inserts another field s before the nth 
field. The replace_field operation replaces one field with another. The 
first field of a string has index zero. 

      String t = "What's up, Doc?"
      cout << t.field(1); // prints up,
      t.remove_field(0); // t is "up, Doc?"
      t.insert_field(0, "Hands"); // t is "Hands up, Doc?"
      t.replace_field(2, "Doc!"); // t is "Hands up, Doc!"

3.10. Input and output

      int read_line(istream& is);
      int read_delimited(istream& is);
      void write_delimited(ostream& os);

The read_line function reads characters from the input stream until it 
reaches a newline character or the end of file. The newline character is 
not placed into the string. The function returns the number of characters 
placed into the string or -1 at the end of the file. 

      String s;
      cout << s.read_line(cin); // entering "FORTRAN" causes "7" to be 
      printed
      cout << s; // prints "FORTRAN" and no newline

The read_delimited and write_delimited operations read and write strings 
enclosed in "...". Use these operations for strings containing white space.

3.11. Finding 

      int find(char c, int from = 0) const;
      int find(const String& s, int from = 0) const;
      int rfind(char c, int from = NPOS) const;

The find functions return the index of a character or string found within 
the instance's string.  The default starting index is from the string's 
beginning.  The rfind operation performs a search backwards from from 
toward the string's beginning.  The functions return NPOS if they do not 
find the substring or character.

      int find_first_of(const String& s, int from = 0) const;
      int find_first_not_of(const String& s, int from = 0) const;

These functions treat s as a set of characters.  Starting from from (or the 
string's beginning if nothing is specified), find_first_of returns the 
index to the first character that matches any character in s. The 
find_first_not_of operation returns the index to the first character that 
does not match any character in s.

      String s("abcdexg");
      cout << s.find_first_not_of("xyzb"); // prints 0
      cout << s.find_first_of("xyzb"); // prints 1

3.12. Case conversion

      String& to_lower();
      String& to_upper();

These change all characters in the instance to lowercase or uppercase, 
respectively. 

      String s("Harry");
      s.to_upper();
      cout << s; // prints HARRY
      s.to_lower();
      cout << s; // prints harry

3.13. Numeric conversion

      long to_long() const;
      double to_double() const;
      void from_long(long n);
      void from_double(double d);

These functions convert longs or doubles to strings, or strings to longs or 
doubles.

3.14. Conversion to C strings

      char* c_array(char buf[], size_t buflen, 
         int from = 0, int n = NPOS) const;
      const char* c_str() const;
      char* new_c_array() const;

Occasionally, you need a C-style string, usually as an argument to a 
library function. These functions provide this to you.

The c_array operation copies n bytes of the instance's string, beginning at 
index from. You must specify the size of the buffer pointed to by buf.  If 
you specify  no from or n, the the entire string is copied.

The c_str returns a pointer to the string's internal data representation. 
Because the string's storage may not be in a permanent memory location, 
c_str's pointer should be understood as having an extremely short lifetime.  
You should never store the pointer, or write to its contents.

The new_c_array operation creates a copy of the string's internal data 
representation and returns a pointer to the newly allocated block.  After 
using the block, you must call delete[] on the block.

4. Date

4.1. Constructors

      Date();
      Date(int d, int m, int y);

The Date default constructor initializes the date to day 0 of the Julian 
day number sequence: Jan 1, 4713 B.C. The second version initializes the 
day, month, and year to values you provide. Specify years B.C. as negative 
numbers, that is, use -1 for the year 1 B.C. If the values do not 
correspond to a legal date, a precondition error is raised.

4.2. Accessors

      int day() const;
      int month() const;
      int year() const;
      Weekday weekday() const;

      String months = "Jan Feb Mar Apr May Jun Jul Aug Sep Oct Nov Dec";
      String days = "Mon Tue Wed Thu Fri Sat Sun";

      Date d(30, 4, 1777); 
      cout << "Carl Friedrich Gauss was born on "
         << days.field(d.weekday()) << ", " 
         << months.field(d.month() - 1) << " " 
         << d.day() << ", " << d.year();
      // Carl Friedrich Gauss was born on Wednesday, Apr 30, 1777

4.3. Date arithmetic

      Date add_days(long n) const;
      void advance(long d);
      long days_between(Date d);

The add_days operation returns the date that is n days from the current 
stored date. In order to advance the date by d days , use the mutator 
operation advance.

      Date d(10, 5, 1994);
      cout << d.add_days(3); // OH NO! Friday the 13th in 3 days!
      d.advance(10); 
      // let's skip it and set our date to May 20, the next Friday.

The days_between operation returns the number of days between the 
instance's date and Date d. If d is earlier than the instance's date, the 
number returned is positive; if later, the number is negative.

      Date labor_day(1, 9, 1994);
      Date xmas_day(25, 12, 1994);
      cout << "There are " << xmas_day.days_between(labor_day) 
        << " days between Labor Day and Christmas.";
      // days_between returns 115

4.4. Comparison

      int compare(const Date& b) const
      static int compare(const Date& a, const Date& b);
      static int hash(const Date& a);

The compare operations determine whether another Date is less than, equal 
to, or greater than that of the instance, returning an integer < 0, zero, 
or an integer > 0. 

The operators == != < <= > >= are overloaded to call compare.

The shared (static) functions are used as comparison functions for sorting. 
They are functions, not class operations, because several templates require 
function pointers as arguments. 

      Map<Date, String> m(Date::hash, Date::compare);

6. Graphics context

6.1. Introduction

The graphics context class is a simple interface to a graphics subsystem 
that is convenient and vendor-independent. It is, however, not particularly 
efficient, particularly because of its use of floating-point coordinates. 
The graphics context contains just enough functionality for the programs 
and exercises in the book. It simply is not meant to be an industrial-
strength graphics interface. 

At the time of this writing, there are two implementations of the graphics 
context class: one for the DOS Borland Graphics Interface (BGI) routines, 
which are specific to the Borland family of compilers, and one for 
Microsoft Windows. An Xlib implementation is planned. 

6.2. Constructor

      GraphicsContext(); 
      GraphicsContext(double xmin, double ymin, double xmax, double ymax);

The constructor opens and initializes the graphics system.  Under BGI, it 
switches to graphics mode. Under Windows, it opens a window to display the 
graphics. If there is a problem that prevents the graphics display from 
opening, the program terminates with an error message.  In particular, 
under BGI, the graphics context requires the that appropriate BGI driver 
(extension .BGI) and two character font files (SANS.CHR and TRIP.CHR) be 
present in the program's executing directory. 

The default contructor initializes the user's upper left window coordinates 
to (0, 0) and and lower right to (20, 15). Of course, that does not mean 
that the window has 21 * 16 pixels; it just specifies the mapping from user 
coordinates to pixel coordinates. The (20,15) value was chosen because most 
displays have a 4 : 3 aspect ratio (for example VGA has 640 * 480 pixels) 
and because it is easy to remember. To choose a different coordinate 
system, use the second constructor or the set_window_coord operation, 
described subsequently. 

The initial pen and fill colors are white.  The initial brush pattern (the 
pattern used to fill areas) is SOLID_BRUSH. The font style is set to 
SYS_FONT. 

You should create an instance of GraphicsContext at the beginning of your 
use of the graphics system. Under DOS, do not create more than one 
instance.

      GraphicsContext gc; // opens the graphics system

6.3. Shutdown

      void close(Bool wait = TRUE); 

This function should be called when you are finished with your graphing 
work. If the wait flag is set to FALSE, the graphics window is closed 
immediately. Otherwise, you must press a key (under DOS) or close the 
window.

      GraphicsContext gc; 
      // graphics routines here 
      gc.close(); 

6.4. Changing the coordinate system

      void set_window_coord(double xmin, double ymin, 
         double xmax, double ymax); 

This sets the coordinates for the viewport.  The upper left coordinate 
becomes (xmin, ymin), and the lower right coordinate becomes (xmax, ymax). 
You can then plot, draw, or write anywhere within these new coordinates. 

There are two reasons for changing the coordinate system. The first is that 
your problem may have a very natural coordinate system, and you should 
change to use it. Suppose you draw a bar graph with ten horizontal bars, 
each of which is between 0 and 100%. Then change (xmax, ymax) to (100, 10). 
The ith bar now has corners (i, 0) and (i+1, percentage[i]). If you find 
yourself scaling values, think of changing the coordinate system to let the 
graphics context do it for you instead.

The other reason for changing the coordinate is zooming. If you want to 
zoom in or out, just change the coordinate system and redisplay. 

      gc.set_window_coord(0, 0, 100, 75); // panoramic view
      simulation.plot(gc);

      gc.set_window_coord(40, 60, 50, 65); // zoom in
      simulation.plot(gc); 

The graphics context clips any portion that falls outside the display. Let 
the graphics context do the clipping. For simple applications, it can do so 
faster than you could. 

Because of limitations with text directions, we enforce that xmin < xmax 
and ymin < ymax. If xmin > xmax, the values are swapped. If xmin = xmax, a 
precondition error is raised. The same holds for ymin and ymax.

6.5. Drawing

      void point(double x, double y); 
      void line(double xfrom, double yfrom, double xto, double yto); 
      void rectangle(double x1, double y1, double x2, double y2); 
      void ellipse(double x, double y, double ra, double rb); 
      void arc(double x, double y, double ra, double rb, 
         double x1, double y1, double x2, double y2);
      void piesegment(double x, double y, double ra, double rb, 
         double x1, double y1, double x2, double y2);

These functions draw various shapes. Lines and arcs are drawn with the 
current pen style and color, and closed shapes are filled with the current 
brush. Coordinates use the current window coordinate system.

The point operation draws a fat dot at (x,y). 

The line operation draws a line from points (xfrom, yfrom) to (xto, yto). 

The rectangle operation draws the rectangle with verticies at (x1, y1), 
(x1, y2), (x2, y1), (x2, y2). 

The ellipse operation draws the ellipse with center at (x, y), and with ra 
and rb radii in the x- and y-directions, respectively. That is, the ellipse 
passes through the points (x  ra, y  rb). 

The arc operation draws an arc of the ellipse with center (x, y) and radii 
ra and rb.  The arc starts at the intersection of the line joining (x, y) 
with (x1, y1) and the ellipse, moves clockwise, and ends at the 
intersection of the line joining (x, y) with (x2, y2) and the ellipse. 

       Figure 1. Drawing an arc

The piesegment operation draws a sector of an ellipse by first drawing the 
arc as described for the arc operation, and then joining its end points 
with the center of the ellipse.

      GraphicsContext gc; 

      gc.rectangle(5, 5, 10, 10); 
         // draw a rectangle 
      gc.point(7.5, 7.5); 
         // ...with a point in the middle
      gc.line(5, 10, 10, 5); 
         // ... and a diagonal through it
      gc.ellipse(2, 2, 2, 2); 
         // draws a circle in the upper-left corner 
      gc.ellipse(17, 11, 1, 3); 
         // draws an elongated ellipse, lower-right 
      gc.piesegment(15, 10, 5, 5, 10, 5, 15, 5); 


       Figure 2. Output of the sample graphics code

6.6. Text

      void text(String t, double x, double y)
      void text_extent(String t, double& x, double& y); 
      void set_font_size(double s);
      void set_font_style(FontStyle);

The text operation writes the string t at (x, y) using the current pen 
color and font style and size. 

To determine the size a given string will need on the graphics context, use 
text_extent. It returns the x- and y-size of the text.

      // draw red text inside a yellow box with center (c, c) 
      GraphicsContext gc; 
      String t = "Hello!"; 
      double x, y; 
      double c = 6; // center the text at (6, 6) 
      gc.rectangle(0, 0, 20, 15);
      gc.set_pen_color(GraphicsContext::YELLOW); 
      gc.text_extent(t, x, y); 
      gc.rectangle(c - (x/2) - 0.2, c - (y/2), c + (x/2), c + (y/2) + 0.2); 
      gc.set_pen_color(GraphicsContext::RED); 
      gc.text(t, c - (x/2), c - (y/2)); 
      gc.close(); 

The set_font_size and set_font_style operations determine the current font. 
Three fonts are available: SERIF_FONT, SANS_SERIF_FONT, SYS_FONT. (A serif 
is the small horizontal cross bar on the stems of letters.  A sans serif 
character is one without serifs.) The first two are scalable. Font size 1 
means that each character is one y-unit tall. 

6.7. Brushes and pens

      void set_brush_style(BrushStyle); 
      void set_brush_color(Color);
      void set_pen_style(PenStyle); 
      void set_pen_color(Color); 

The set_brush_style and set_brush_color operations set the style and color 
for those functions that fill shapes: ellipse, arc, piesegment.  Use the 
BrushStyle and Color enumerations to specify preferences. The following 
brush styles are available: EMPTY_BRUSH, SOLID_BRUSH, HORIZ_BRUSH, 
FDIAG_BRUSH, BDIAG_BRUSH, XDIAG_BRUSH.

The set_pen_style and set_pen_color operations set the style and color for 
those functions that draw: point, line, rectangle, text. Use the PenStyle 
and Color enumerations to specify preferences. The following pen styles are 
avaliable: NORMAL_PEN, THICK_PEN, DOTTED_PEN, DASHED_PEN.

6.8. Raster operation mode

      void set_rop_mode(RopMode); 

The set_rop_mode operation sets the mode that the drawing operations use.  
COPY_ROP causes drawing operations to draw on top of the current display 
contents. XOR_ROP forms an exclusive OR between the pixels on the display 
and those of the pixels being rendered. In particular, drawing the same 
shape twice in XOR_ROP mode erases it completely. (In contrast, drawing it 
in the background color may affect other overlapping shapes.).

You can use the XOR_ROP mode to `move' an image without `trails':

      double i; 
      GraphicsContext gc; 
      // draw box without trails 
      gc.set_rop_mode(GraphicsContext::XOR_ROP); 
      for (i = 3; i <= 6; i += 0.1) 
      {  gc.rectangle(i, i, i + 1, i + 1); // draw the box
         gc.rectangle(i, i, i + 1, i + 1); 
            // draw it again to erase in XOR mode 
      } 
      // now draw, leaving trails 
      gc.set_rop_mode(GraphicsContext::COPY_ROP); 
      for (i = 9; i <= 12; i += 0.1) 
      {  gc.rectangle(i, i, i + 1, i + 1); 
         gc.rectangle(i, i, i + 1, i + 1); 
      } 
      gc.close(); 

7. Shapes

7.1. Limitations

The shape classes form a polymorphic collection to display graphical shapes 
on a graphics window. They are used for many examples and exercises in this 
book. 

These classes are definitely not a model for a professional graphics 
library. In particular, the Point class (and, to a lesser degree, the 
Segment and Rectangle classes) serve double duty: both for the actual 
shapes to be plotted and for geometric computation. For the latter role, 
the polymorphism overhead is entirely unnecessary. For example, a polygon 
is stored as an array of Point objects, each of which has a pointer to an 
unneeded virtual function table. It would make more sense to distinguish 
between a Point (an object representing a point in the plane, with 
geometric operations such as distance and angle measurement), and a 
PointShape (a blob on the graphics screen). For simplicity, ChiLib does not 
make this distinction.

The class pairs Rectangle/FilledRect and Text/ScalableText had been 
introduced in the book as examples for inheritance. In practice, fixed-size 
text is nearly useless, and it would make sense to make all text scalable. 
If a distinction between rectangles and rectangle shapes were made, one 
might also decide to make all rectangle shapes filled. 

For geometric calculations, and as the argument to the move operation, it 
would have been very convenient to have a Vector class, with overloaded 
operators for vector addition, scaling and dot product. But the distinction 
between points and vectors is subtle. For example, it makes no sense to add 
two points, whereas the difference between two points is defined--it is a 
vector. It was reluctantly decided that introducing vectors would obscure 
those issues that this library intends to illustrate.

The classes and class operations have further been restricted by the 
rudimentary capabilities of the least capable of the graphics library that 
ChiLib supports. That library does not offer rotated text; hence we do not 
implement a rotate operation on shapes, although that would be an 
interesting and natural operation to carry out. If it were added, the 
implementation of ellipses and rectangles would be affected. Professional 
graphics libraries support arbitrary affine transformations of the plane. 

Mathematical purity demands geometric operations to be independent from a 
particular coordinate system. Our interface succeeds, with two exceptions. 
The Point default constructor constructs a point at the origin, and the 
rectangles, the ellipses and the move operation depend on the direction of 
the x- and y-axes. 

7.2. Input and output

      void read(istream& is);
      void plot(GraphicsContext& gc) const;
      void print(ostream& os) const;

These three operations must be defined for every class deriving from Shape. 
The most important output routine is plotting on a graphics context. Use 
the graphics context operations to render the shape. If you modify the 
state of the graphics context, restore it to the default. 

To print on a stream, write the object state in a form that is both humanly 
readable (for easier debugging) and easy to read back in. The read 
operation restores an object from the information in a file in the format 
produced by print. The old contents of the object are lost. If the contents 
of the input file do not match the expected format, the stream state should 
be set to `fail'. 

7.3. Transformations

      void scale(Point center, double s);
      void move(double x, double y);

In addition to being plottable, shapes can be transformed. We support two 
transformations only: moving and scaling. Moving is the easiest. The shape 
is transported by a given x- and y-offset. In figure 3, we represent the 
shape as an amorphous blob to indicate that any shape can be transformed in 
this way.  


       Figure 3. The move operation

The scale operation has two ingredients: the center of projection and a 
scale factor. All points of the shape are moved further away from the 
center, if the scale factor is > 1, or closer to the center, if the scale 
factor is < 1. (Only positive scale factors are allowed.) Note that the 
center can be any point and need not be the origin of the coordinate 
system. 


       Figure 4. The scale operation

Each class that derives from Shape must supply its own move and scale 
operations. Moving is usually easy--just move the points that define the 
shape. To scale, scale the points, and multiply all length measurements 
(such as the radius of a circle) by the scale factor.

For most shapes, the only operations that can change them after 
construction are move and scale. (The exception is the polygon, whose 
vertices can be set individually.)

7.4. Default constructors

All shape classes have default constructors, but they all construct objects 
that are not useful. The Point constructor constructs a point on the 
origin. Since the interface is independent of the choice of an origin, this 
is not likely ever to be useful. If you mean to place a point at (0, 0), 
construct it with explicit arguments. 

The Segment default constructor makes an empty segment joining two copies 
of the origin. The default Ellipse is centered on the origin, with radii 0. 
Neither shape is useful for anything.

We supplied the default constructors for two reasons. Some applications may 
need arrays of certain shapes; for example, a maze may be an array of 
segments. Second, it is necessary to construct an object first before 
invoking the read operation. 

7.5. Cloning

Every class deriving from Shape should redefine the virtual clone function 
as follows:

      class MyShape : public Shape
      {
      public:
         // ...
         MyShape* clone() const; 
      };

      MyShape* clone() const { return new MyShape(self); }

(Older compilers may require that you declare the return value as Shape*, 
not MyShape*. If the compiler demands that, make the modification. It does 
not affect our applications.) 

Cloning is needed for the graph editor framework and for any application in 
which a deep copy of a shape is required. 

The Shape base class defines clone to return 0. As long as you are not 
interested in cloning, you need not redefine it. In particular, it is not 
an issue for the first eight chapters.

7.6. Points

      Point(double xx, double yy);
      double x() const;
      double y() const;
      double distance(Point b) const;
      double angle(Point b) const;

The x and y accessors report the coordinates of the point. 

The distance operation measures the distance between to another point. The 
angle operation computes the angle between the x-axis and the segment 
joining this point with the point b, counted clockwise. (This is the 
opposite of the mathematical convention because the screen y-axis points 
downward.) The angle is measured in radians. 

7.7. Segments

      Segment(Point f, Point t);
      Point from() const;
      Point to() const;
      Point center() const;
      Bool intersect(Segment s, Point& p) const;
      Point closest(Point p) const;
      double distance(Point p) const;
      void reflect(double& x, double& y) const;

A segment is an interval on a line joining two points. The from and to 
accessors return the end points, and center returns the point halfway 
between. 

The intersect operation computes the intersection between two segments. It 
returns TRUE, and sets p to the point of intersection, if the segments 
intersect. Otherwise it returns FALSE and leaves p unchanged.


       Figure 5. Intersection of segments

The closest operation computes the point on the segment that is closest to 
p. 


       Figure 6. Closest point on a segment

This is the point c such that the segment cp is perpendicular to the 
segment ab, provided c lies between a and b. Otherwise the operation 
returns the closer of the end points a, b.

The distance operation computes the distance between p and the closest 
point to p on the segment. If the distance is (approximately) 0, then p 
lies on the segment. 

The reflect operation reflects a vector, given by its x- and y-coordinates, 
along the segment. 


       Figure 7. Reflection along a segment

The x and y arguments are changed to the reflected vector. This operation 
is useful for bouncing shapes off a boundary. 

7.8. Rectangles

      Rectangle(Point, Point);
      Point left_top() const;
      Point left_bottom() const;
      Point right_top() const;
      Point right_bottom() const;
      Point center() const;
      double xsize() const;
      double ysize() const;
      Bool is_inside(Point p) const;
      Point boundary_point(Point p) const;

All rectangles have their sides parallel to the coordinate axes and can 
thus be defined by any two corner points (not necessarily top left and 
bottom right). The four corner points are returned as left_top, 
left_bottom, right_top, right_bottom. (The left/right comes first because 
it depends on the x value, and top/bottom depends on the y value.) 

The center operation returns the center of the rectangle. 

The xsize, xysize operations return the lengths of the sides of the 
rectangle.

The is_inside operation checks whether p is inside the rectangle. The 
boundary_point operation returns the point on the boundary of the rectangle 
intersecting the segment joining p and the center of the rectangle. It 
returns p if p is inside the rectangle.

7.9. Filled rectangles

      FilledRect(Point, Point, GraphicsContext::BrushStyle);

Filled rectangles are just like rectangles, except that the fill pattern 
must be specified in the constructor.

7.10. Ellipses

      Ellipse(Point center, double xrad, double yrad);
      Point center() const;
      double xradius() const;
      double yradius() const;
      Bool is_inside(Point p) const;
      Point boundary_point(Point p) const;

All ellipses have their axes parallel to the coordinate axes. To construct 
an ellipse, specify the center and the radii. If the radii are equal, a 
circle is obtained.

The center operation returns the center of the ellipse, The xradius and 
yradius operations return the radii of the ellipse.

The is_inside operation checks whether p is inside the ellipse. The 
boundary_point operation returns the point on the boundary of the ellipse 
intersecting the segment joining p and the center of the ellipse. The 
operation returns p if p is inside the ellipse.

7.11. Polygons

      Polygon(int);
      void set_vertex(int, Point);
      Point vertex(int i) const;
      Point center() const;

To construct a polygon, specify the number of vertices that is desired. 
(Admittedly, this constructor violates the rule that a constructor should 
not have a single integer argument.) Then call set_vertex to set each 
vertex. 

The vertex operation returns the ith vertex. center computes the center of 
gravity.

7.12. Text

      Text(Point, String);
      Rectangle extent(GraphicsContext& gc) const;

Text is a string placed on a specific location on the screen. To construct 
a text object, specify both the top left corner and the contents. 

The extent operation returns the rectangle enclosing the text. You must 
supply a graphics context to enable measurement. 

7.13. Scalable text

      ScalableText(Point, String, double yheight = 1.0);

The characters of Text shapes are formed with the default system font. 
Their size is not affected by scaling. The ScalableText characters overcome 
that problem. You can specify the character height in the constructor, and 
it is correctly updated when the shape is scaled. For example, character 
height 1 means that the character box (including ascenders and descenders) 
is one unit high. 

The plot and extent operations of the Text class are redefined to work with 
scalable text.

8. Command line arguments

8.1. Types of arguments

In an environment in which the user interacts with the operating system 
through a shell, such as Unix or DOS, programs are invoked by the user who 
types their name at the shell prompt. The program name is optionally 
followed by command line arguments that contain directions to the program. 
Even in graphical user interfaces such as Windows there are ways of 
supplying command line arguments. The Args class offers a convenient way of 
parsing these command line arguments. 

Arguments come in two kinds: argument values and options. Argument values 
are typically file names with which the program is to work. Options modify 
the behavior of the program in some way. For example, a sort program may be 
invoked with 

      sort -v info.dat

to sort the file info.dat. The -v indicates that the sorting should proceed 
in reverse order.

For simplicity, we require that all options start with a `-' character and 
conversely, that no argument value start with a `-'. We further require 
that after the hyphen all options consist of a single character, which may 
be followed by a value. No white space may come between the option and its 
value. Option characters are case-sensitive. Options and arguments can be 
mixed in any order. For the scope of this book, these rules are sufficient. 

We distinguish three kinds of options: Boolean, integer, and string 
options. 

A Boolean option is turned on by being present, or off when followed by a 
`-'. For example,

      prog -s -t-

turns s on and t off.

An integer option is followed by an integer. If the option character is 
present and the integer is missing, it is assumed to be 0:

      prog -a1 -b

sets a to 1 and b to 0.

A string option is followed by a string. If the option character is present 
and the string is missing, it is assumed to be the empty string:

      prog -aharry -b

sets a to "harry" and b to "".

8.2. Construction

The purpose of the Args class is to parse the command line arguments of 
main, without having to deal with the C array of C strings. You initialize 
an Args with the arguments from main:

      int main(int argc, char* argv[])
      {  Args args(argc, argv);
         // ...
      }

The command line can be parsed in main, or you can pass the args object to 
a function that deals with it.

For example, if a program named sort is invoked on the command line as

      sort -v -s10 input.dat

then args.prog_name() is the string "sort", args.option('v') is TRUE, 
args.option('s', n) sets n to 10, and args.arg(1) is the string 
"input.dat".

8.3. Parsing

      String prog_name();
      String prog_path();
      String arg(int i = - 1);
      Bool int_option(char c, int& x, int i = -1);
      Bool bool_option(char c, Bool& x, int i = -1);
      Bool option(char c, String& x, int i = -1);

The prog_name operation returns the name of the program, whereas prog_path 
returns the whole path. The availability of these items is dependent on the 
operating system. 

The arg operation returns the ith argument value. If none is present, an 
empty string is returned. That means that there is no way of passing an 
empty argument value; this should not be a serious restriction. A program 
expecting a variable number of arguments should call args until an empty 
string is returned. If i is not specified, args gets the last argument, 
because some programs take the attitude that the last argument or option 
overrides all others.

The int_option operation reads the ith integer option associated with the 
character c. If i is not specified, the last option is read. If none is 
present, the operation returns FALSE and leaves x unchanged. If the option 
is present, the operation returns TRUE and sets x to the value of the 
option. An option with a default value can simply be read as follows:

      int tab_stops = 3; // default for tab stops is 3
      args.int_option('t', tab_stops); // can be overridden with -t

The bool_option and option operations do the same for Boolean and string 
options. 

9. Lists

9.1. Introduction

List<T> is a template to construct a linked list of elements of type T. T 
can be any type--numerical, pointer or class. 

The default constructor constructs an empty list. The empty operation 
empties an existing list. The length operation returns the number of 
elements currently stored in the list. 

Lists are copied by value. To keep the code simple and understandable, copy 
on write is not used. Therefore copies get expensive, and you should pass 
lists (and objects containing lists) by constant reference, not by value, 
to functions that do not change them. 

9.2. Access to head and tail

     void insert_head(T t);
     void insert_tail(T t);
     T remove_head();
     T remove_tail();
     T head() const;
     T tail() const;

This class allows editing at both the head and the tail of the list. The 
insert_head operation makes a new link containing t that becomes the head 
of the list. The insert_tail operation makes a new link containing t that 
becomes the tail of the list. The head and tail operations report the 
contents of the head and the tail, whereas remove_head and remove_tail 
return and remove the head or tail.

This portion of the interface implements a deque (a double-ended queue). 

9.3. Traversal

What distinguishes a list from a deque is the ability to inspect and modify 
arbitrary elements inside it. For this purpose, each list object contains a 
cursor--a pointer to a current element. 

      void insert(T t); // insert before current position
      T remove(); // remove current position
      T current() const; // contents of current element
      T& current(); // reference to current element

These operations insert and remove elements at the cursor position. To see 
the interaction between the cursor and the inserted or removed element, 
think of the cursor on a terminal. Insertion inserts before the cursor, and 
removal deletes the element under the cursor and moves the cursor to the 
next element. It is legal to insert when the cursor is at the end of the 
list. A list with n elements has n + 1 cursor positions: before each 
element and after the last one. 

      void reset();
      void next(); // advance cursor to next position
      Bool at_end() const;

These operations move the cursor and test whether it is already at the end 
of the list. Advancing past the end has no effect. 

The typical traversal loop has the form

      for (l.reset(); !l.at_end(); l.next())
         do something with l.current();

9.4. Iteration

Using the cursor to traverse a list has one disadvantage: it modifies the 
list. In particular, a function receiving a constant reference to a list 
cannot modify the cursor. The solution is to attach an external iterator, 
an object that can traverse a list without modifying it.

ListIterator<T> is a template for iterators through List<T> lists. (It 
would make more sense if each list class had a nested class 
List<T>::Iterator, but that broke several template implementations.)

      ListIterator(const List<T>&);
      void next(); // advance cursor to next position
      void reset();
      Bool at_end() const;
      T current() const; // contents of current element

An iterator is constructed from a list. It starts out pointing to the first 
list element. Its cursor is controlled just as the list cursor. The typical 
traversal loop is 

      for (ListIterator<T> it(l); !it.at_end(); it.next())
         do something with it.current();

Any number of iterators can be attached to a list. The iterators can only 
be used to inspect the list contents, not to modify it.

If a list is edited (through insert, remove), emptied or destroyed, all 
iterators to it are in an unstable state. If the list still exists, invoke 
reset on the iterator before using it again. If the list has been 
destroyed, the iterator can no longer be used. A professional 
implementation would implement communication between the list and its 
iterators, but that was omitted to keep the code simple and understandable.

10. Other containers

10.1. Queues

     Queue();
     void insert(T n);
     T remove();
     void empty();
     T head() const;
     int length() const;

Queue<T> is a template to construct a queue of elements of type T. T can be 
any type--numerical, pointer or class. 

The default constructor constructs an empty queue. The empty operation 
empties an existing queue. The length operation returns the number of 
elements currently stored in the queue. 

The insert operation adds an element to the tail of the queue, whereas 
remove removes an element from the head. The head and tail operations 
return the elements stored at the head and tail.

10.2. Priority queues

     PriorityQueue(int(*comp)(const T&, constT&));
     void insert(T n);
     T remove();
     void empty();
     T head() const;
     int length() const;

PriorityQueue<T> is a template to construct a queue of elements of type T. 
T can be any type--numerical, pointer or class. 

To construct a priority queue, a comparison function comp must be 
specified. Like all comparison functions in this library, it returns zero 
if the elements to be compared are undistinguishable, a negative integer if 
the first argument comes before the second, and a positive integer 
otherwise. 

The length operation returns the number of elements currently stored in the 
queue. 

The insert operation adds an element to the queue. remove removes the 
smallest element from the priority queue. head returns a copy of the 
smallest element stored in the priority queue. 

10.3. Maps

      Map(int (*hash)(const K&), int (*comp)(const K&, const K&));
      void set(const K& key, const V& value);
      Bool find(const K& key) const;
      Bool find(const K& key, V& value) const;
      V get(const K& key) const;
      V operator[](const K& key) const;
      V& operator[](const K& key);
      void empty();

Map<K,V> is a map storing (key, value) pairs. For each key in K there is at 
most one map value in V. The add operation adds a (key, value) pair, 
removing any previous value that may have been associated with key. The 
find operation checks whether a value has been associated with key. If so, 
it returns TRUE. The second version of find sets value to that value. If 
not, both operations return FALSE and leave value unchanged. The get 
operation and the overloaded [] operator retrieve a value. Using a 
nonexistent key with [] is an error. The empty operation removes all 
entries from the map object.

To construct a map, two functions must be specified: a hash function for 
the key values, and a comparison function. The comparison function must 
return 0 if the keys are to be considered identical and a nonzero value 
otherwise. This is not very intuitive but it is the same protocol used for 
sort functions. The hash function must return some integer, which should be 
somewhat randomly distributed, for each key. Don't reduce the hash value by 
a modulus; the map will take care of that. Of course, keys that compare to 
be identical must have identical hash values. 

      Map<String, double> m(String::hash, String::compare);

11. Errors and assertions

11.1. Error reporting classes

The error reporting classes derive from the base class Error.

      Error(const char* filename, int lineno, 
         const char expr[] = 0, const char msg[] = 0);
      void abort();
      virtual void message(ostream& os) const;

Error objects are usually constructed by the ASSERT macros, which supply 
the file and line information.

The message operation sends an error message to a stream. It is redefined 
by those classes that have interesting details in their error report. For 
example, BoundsError reports on the legal bounds and the value of the 
offending index. 

If your compiler supports exceptions, the assert macros throw the error 
object. You should have main catch every object derived from Error, then 
inspect the call stack to see who threw it. 

If your compiler does not support exceptions, the assert macros call abort 
on the error object. The abort operation prints a diagnostic message to 
cerr and terminates. Set a breakpoint here and then inspect the stack to 
find out who caused the error, or call message to get an error diagnostic.

The classes 

      PrecondError
      PostcondError
      InvariantError
      BoundsError
      MemError

are derived from Error. You can derive your own classes from Error. 

11.2. Assertions

We supply the following macros to generate error reporting. 

      ASSERT(expr);
      ASSERT_PRECOND(expr);
      ASSERT_POSTCOND(expr);
      ASSERT_INVARIANT(expr);
      ASSERT_MEM(pointer);
      ASSERT_BOUNDS(i, low, high);

The first four macros test the expression and report the error, with 
varying error messages. 

The ASSERT_MEM argument tests the pointer, which presumably was returned 
from new, and tests whether it is non-null. This macro is not useful for 
compilers with exceptions because new throws an xalloc exception when it 
runs out of memory. 

The ASSERT_BOUNDS macro is used in the string and array classes. It is not 
likely to be useful elsewhere. It tests whether low  i  high. 

If NDEBUG is defined during compilation, none of these macros generate 
code. In particular, you are still responsible for doing something sensible 
to return from the operation. 

12. Sample code

12.1. Polymorphic shapes

The shapes1 program demonstrates graphics shapes and the move and scale 
transformations. The shapes2 program draws a bar chart from rectangles and 
filled rectangles to show the difference between static and dynamic 
binding. The shapes3 program utilizes polymorphism to transform an array of 
arbitrary shapes. The shapes4 program uses multiple inheritance to define 
the text and traffic sign classes.

12.2. Streams

The grstream program implements the GraphicStream class which derives from 
ostream to display text on a graphics context. The pstream program 
implements the persistent streams mechanism. 

Each program can be compiled with the preprocessor variable TEST defined to 
obtain a sample run. Leave TEST undefined to use the stream classes in 
other programs.

12.3. Simulation

The bank1 program implements the bank simulation without using the 
simulation framework. The simulation framework code is contained in 
simfrmwk. The bank2 program uses the framework for the bank simulation.

12.4. Graph editor framework

The gedfrmwk module contains the graph editor framework. The module mouse 
is required for mouse handling. The graphed1 program implements a very 
simple instance of the graph editor, using the framework.

13. Debugging hints

13.1. Inspecting containers

During debugging it is often helpful or necessary to inspect the contents 
of containers. Every debugger has a command to show the fields of an 
object, given either the name of the object or a pointer to it. In fact, 
most debuggers have two: an inspect command to see the fields briefly, and 
a watch command, to put the object onto a permanent watch list. The inspect 
command is better for peeking inside a data structure.

To see the contents of a String object, inspect the _str pointer. It is a C 
character pointer, and the debugger should just show the string contents. 
There is a reference count somewhere, but you cannot see it. 

To see the contents of an Array<X> object, inspect the _elements pointer. 
It is an X* pointer. Now you need to tell the debugger to expand the 
pointer to an array. Every debugger has such a command. You need to specify 
the number of elements you want to see. To find out how many you want, 
inspect the _low and _high fields of the array object. They give the 
current array range. You need to subtract _low from the index to translate 
between array indices and offsets into the _elements array. 

To see the contents of a list or queue, inspect the _head pointer. It 
points to the first link. Follow it and you see the first link, with an 
_info and _next field. Inspect the _info field to see the first element, 
and follow the _next field to get to the next link. Keep doing that until 
_next is 0. 

13.2. Inspecting self

ChiLib uses self to denote the implicit argument, but you need to tell the 
debugger to inspect this, the official C++ name for a pointer to the 
implicit argument. 

A useful trick is to put *this onto the watch list. That way, you always 
see the current implicit argument. 

13.3. Trapping errors

The errors you are most likely interested in trapping are precondition and 
bounds errors, because they are your fault. In contrast, there is little 
you can do about memory errors. If you run out of memory, the exact 
location where the exhaustion occurred is not too interesting. Invariant or 
postcondition errors can signify programming errors, and you will want to 
trap those that come from your code. They can also signify that an object 
has been overwritten by a wild pointer, in which case they are just a 
symptom of a worse problem elsewhere.

The trapping strategy depends on whether your compiler supports exception 
handling. If it does, run the debugger, wait for the exception to occur, 
and then inspect the call stack. It will contain the function producing the 
error. If not, place a breakpoint into Error::abort. When the breakpoint 
gets triggered, inspect the call stack. Don't wait until after abort 
actually aborts the program. Debuggers don't usually keep the call stack 
information after the program terminates. 
