home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 22 gnu / 22-gnu.zip / gnumans.zip / libgpp.inf (.txt) < prev   
OS/2 Help File  |  1997-07-02  |  137KB  |  4,153 lines

  1.  
  2. ΓòÉΓòÉΓòÉ 1. Title page ΓòÉΓòÉΓòÉ
  3.  
  4.                                   User's Guide
  5.  
  6.                              to the GNU C++ Library
  7.  
  8.                            last updated April 29, 1992
  9.  
  10.                                  for version 2.0
  11.  
  12.                             Doug Lea (dl@g.oswego.edu)
  13.  
  14. Copyright (C) 1988, 1991, 1992 Free Software Foundation, Inc. 
  15.  
  16. Permission is granted to make and distribute verbatim copies of this manual 
  17. provided the copyright notice and this permission notice are preserved on all 
  18. copies. 
  19.  
  20. Permission is granted to copy and distribute modified versions of this manual 
  21. under the conditions for verbatim copying, provided also that the section 
  22. entitled ``GNU Library General Public License'' is included exactly as in the 
  23. original, and provided that the entire resulting derived work is distributed 
  24. under the terms of a permission notice identical to this one. 
  25.  
  26. Permission is granted to copy and distribute translations of this manual into 
  27. another language, under the above conditions for modified versions, except that 
  28. the section entitled ``GNU Library General Public License'' may be included in 
  29. a translation approved by the author instead of in the original English. 
  30.  
  31. Note: The GNU C++ library is still in test release. You will be performing a 
  32. valuable service if you report any bugs you encounter. 
  33.  
  34.  
  35. ΓòÉΓòÉΓòÉ 2. Top ΓòÉΓòÉΓòÉ
  36.  
  37. Introduction ************ 
  38.  
  39. This manual documents how to install and use the GNU C++ library. 
  40.  
  41.  Copying                                 GNU Library Public License says how 
  42.                                          you can copy 
  43.            and share the GNU C++ library. 
  44.  
  45.  Contributors                            People who have contributed to GNU C++ 
  46.                                          library. 
  47.  Installation                            How to configure, compile and install 
  48.                                          GNU C++ library 
  49.  Trouble                                 If you have trouble installing GNU C++ 
  50.                                          library. 
  51.  General                                 Aims, objectives, and limitations of 
  52.                                          the GNU C++ library 
  53.  Conventions                             Stylistic conventions 
  54.  OK                                      Support for representation invariants 
  55.  Proto                                   Introduction to container class 
  56.                                          prototypes 
  57.  Pix                                     Pseudo-indexes 
  58.  Representations                         How variable-sized objects are 
  59.                                          represented 
  60.  Expressions                             Some guidance on programming 
  61.                                          expression-oriented classes 
  62.  Headers                                 Header files and other support for 
  63.                                          interfacing C++ to C 
  64.  Builtin                                 Utility functions for builtin types 
  65.  New                                     Library dynamic allocation primitives 
  66.  * IOStream:(iostream)Top.           The input/output library (istreams and 
  67.  ostreams). 
  68.  
  69.  Stream                                  obsolete I/O library 
  70.  Obstack                                 Obstacks and their uses. 
  71.  AllocRing                               A place to store objects for a while 
  72.  String                                  String, SubString, and Regex classes. 
  73.  Integer                                 Multiple precision Integer class. 
  74.  Rational                                Multiple precision Rational class 
  75.  Complex                                 Complex number class 
  76.  Fix                                     Fixed point proportion classes 
  77.  Bit                                     BitSet and BitString classes 
  78.  Random                                  Random number generators 
  79.  Data                                    SampleStatistic and related classes 
  80.                                          for data collection 
  81.  Curses                                  CursesWindow class 
  82.  List                                    Lisp-like List prototype 
  83.  LinkList                                Singly and doubly linked list class 
  84.                                          prototypes 
  85.  Vector                                  Vector prototypes 
  86.  Plex                                    Plex (adjustable array) prototypes 
  87.  Stack                                   Stack prototypes 
  88.  Queue                                   Queue prototypes 
  89.  Deque                                   Double ended queue prototypes 
  90.  PQ                                      Heap (priority queue) class prototypes 
  91.  Set                                     Set class prototypes 
  92.  Bag                                     Bag class prototypes 
  93.  Map                                     Map (Associative array) prototypes 
  94.  GetOpt                                  C++ class-based version of the 
  95.                                          GNU/UNIX getopt function 
  96.  Projects                                Things Still Left to do 
  97.  
  98.  
  99. ΓòÉΓòÉΓòÉ 3. Contributors to GNU C++ library ΓòÉΓòÉΓòÉ
  100.  
  101. Aside from Michael Tiemann, who worked out the front end for GNU C++, and 
  102. Richard Stallman, who worked out the back end, the following people (not 
  103. including those who have made their contributions to GNU CC) should not go 
  104. unmentioned. 
  105.  
  106.      Doug Lea contributed most otherwise unattributed classes. 
  107.  
  108.      Per Bothner contributed the iostream I/O classes. 
  109.  
  110.      Dirk Grunwald contributed the Random number generation classes, and 
  111.       PairingHeaps. 
  112.  
  113.      Kurt Baudendistel contributed Fixed precision reals. 
  114.  
  115.      Doug Schmidt contributed ordered hash tables, a perfect hash function 
  116.       generator, and several other utilities. 
  117.  
  118.      Marc Shapiro contributed the ideas and preliminary code for Plexes. 
  119.  
  120.      Eric Newton contributed the curses window classes. 
  121.  
  122.      Some of the I/O code is derived from BSD 4.4, and was developed by the 
  123.       University of California, Berkeley. 
  124.  
  125.      The code for converting accurately between floating point numbers and 
  126.       their string representations was written by David M. Gay of AT&T. 
  127.  
  128.  
  129. ΓòÉΓòÉΓòÉ 4. Installing GNU C++ library ΓòÉΓòÉΓòÉ
  130.  
  131.    1. Read through the README file and the Makefile. Make sure that all paths, 
  132.       system-dependent compile switches, and program names are correct. 
  133.  
  134.    2. Check that files  `values.h', `stdio.h', and `math.h' declare and define 
  135.       values appropriate for your system. 
  136.  
  137.    3. Type `make all' to compile the library, test, and install. Current 
  138.       details about contents of the tests and utilities are in the `README' 
  139.       file. 
  140.  
  141.  
  142. ΓòÉΓòÉΓòÉ 5. Trouble in Installation ΓòÉΓòÉΓòÉ
  143.  
  144. Here are some of the things that have caused trouble for people installing GNU 
  145. C++ library. 
  146.  
  147.    1. Make sure that your GNU C++ version number is at least as high as your 
  148.       libg++ version number. For example, libg++ 1.22.0 requires g++ 1.22.0 or 
  149.       later releases. 
  150.  
  151.    2. Double-check system constants in the header files mentioned above. 
  152.  
  153.  
  154. ΓòÉΓòÉΓòÉ 6. GNU C++ library aims, objectives, and limitations ΓòÉΓòÉΓòÉ
  155.  
  156. The GNU C++ library, libg++ is an attempt to provide a variety of C++ 
  157. programming tools and other support to GNU C++ programmers. 
  158.  
  159. Differences in distribution policy are only part of the difference between 
  160. libg++.a and AT&T libC.a.  libg++ is not intended to be an exact clone of libC. 
  161. For one, libg++ contains bits of code that depend on special features of GNU 
  162. g++ that are either different or lacking in the AT&T version, including 
  163. slightly different inlining and overloading strategies, dynamic local arrays, 
  164. etc.  All of these differences are minor. For example, while the AT&T and GNU 
  165. stream classes are implemented in very different ways, the vast majority of C++ 
  166. programs compile and run under either version with no visible difference. 
  167. Additionally, all g++-specific constructs are conditionally compiled; The 
  168. library is designed to be compatible with any 2.0 C++ compiler. 
  169.  
  170. libg++ has also contained workarounds for some limitations in g++: both g++ and 
  171. libg++ are still undergoing rapid development and testing---a task that is 
  172. helped tremendously by the feedback of active users.  This manual is also still 
  173. under development; it has some catching up to do to include all the facilities 
  174. now in the library. 
  175.  
  176. libg++ is not the only freely available source of C++ class libraries. Some 
  177. notable alternative sources are Interviews and NIHCL. (InterViews has been 
  178. available on the X-windows X11 tapes and also from interviews.stanford.edu. 
  179. NIHCL is available by anonymous ftp from GNU archives (such as the pub 
  180. directory of prep.ai.mit.edu), although it is not supported by the FSF - and 
  181. needs some work before it will work with g++.) 
  182.  
  183. As every C++ programmer knows, the design (moreso than the implementation) of a 
  184. C++ class library is something of a challenge. Part of the reason is that C++ 
  185. supports two, partially incompatible, styles of object-oriented programming -- 
  186. The "forest" approach, involving a collection of free-standing classes that can 
  187. be mixed and matched, versus the completely hierarchical (smalltalk style) 
  188. approach, in which all classes are derived from a common ancestor.  Of course, 
  189. both styles have advantages and disadvantages.  So far, libg++ has adopted the 
  190. "forest" approach.  Keith Gorlen's OOPS library adopts the hierarchical 
  191. approach, and may be an attractive alternative for C++ programmers who prefer 
  192. this style. 
  193.  
  194. Currently (and/or in the near future) libg++ provides support for a few basic 
  195. kinds of classes: 
  196.  
  197. The first kind of support provides an interface between C++ programs and C 
  198. libraries. This includes basic header files (like `stdio.h') as well as things 
  199. like the File and stream classes. Other classes that interface to other aspects 
  200. of C libraries (like those that maintain environmental information) are in 
  201. various stages of development; all will undergo implementation modifications 
  202. when the forthcoming GNU libc library is released. 
  203.  
  204. The second kind of support contains general-purpose basic classes that 
  205. transparently manage variable-sized objects on the freestore.  This includes 
  206. Obstacks, multiple-precision Integers and Rationals, arbitrary length Strings, 
  207. BitSets, and BitStrings. 
  208.  
  209. Third, several classes and utilities of common interest (e.g., Complex numbers) 
  210. are provided. 
  211.  
  212. Fourth, a set of pseudo-generic prototype files are available as a mechanism 
  213. for generating common container classes. These are described in more detail in 
  214. the introduction to container prototypes. Currently, only a textual 
  215. substitution mechanism is available for generic class creation. 
  216.  
  217.  
  218. ΓòÉΓòÉΓòÉ 7. GNU C++ library stylistic conventions ΓòÉΓòÉΓòÉ
  219.  
  220.      C++ source files have file extension `.cc'. Both C-compatibility header 
  221.       files and class declaration files have extension `.h'. 
  222.  
  223.      C++ class names begin with capital letters, except for istream and 
  224.       ostream, for AT&T C++ compatibility. Multi-word class names capitalize 
  225.       each word, with no underscore separation. 
  226.  
  227.      Include files that define C++ classes begin with capital letters (as do 
  228.       the names of the classes themselves).  `stream.h' is uncapitalized for 
  229.       AT&T C++ compatibility. 
  230.  
  231.      Include files that supply function prototypes for other C functions 
  232.       (system calls and libraries) are all lower case. 
  233.  
  234.      All include files define a preprocessor variable _X_h, where X is the 
  235.       name of the file, and conditionally compile only if this has not been 
  236.       already defined. The #pragma once facility is also used to avoid 
  237.       re-inclusion. 
  238.  
  239.      Structures and objects that must be publicly defined, but are not 
  240.       intended for public use have names beginning with an underscore. (for 
  241.       example, the _Srep struct, which is used only by the String and SubString 
  242.       classes.) 
  243.  
  244.      The underscore is used to separate components of long function names, 
  245.       e.g., set_File_exception_handler(). 
  246.  
  247.      When a function could be usefully defined either as a member or a friend, 
  248.       it is generally a member if it modifies and/or returns itself, else it is 
  249.       a friend. There are cases where naturalness of expression wins out over 
  250.       this rule. 
  251.  
  252.      Class declaration files are formatted so that it is easy to quickly check 
  253.       them to determine function names, parameters, and so on. Because of the 
  254.       different kinds of things that may appear in class declarations, there is 
  255.       no perfect way to do this. Any suggestions on developing a common class 
  256.       declaration formatting style are welcome. 
  257.  
  258.      All classes use the same simple error (exception) handling strategy. 
  259.       Almost every class has a member function named error(char* msg) that 
  260.       invokes an associated error handler function via a pointer to that 
  261.       function, so that the error handling function may be reset by 
  262.       programmers. By default nearly all call *lib_error_handler, which prints 
  263.       the message and then aborts execution. This system is subject to change. 
  264.       In general, errors are assumed to be non-recoverable: Library classes do 
  265.       not include code that allows graceful continuation after exceptions. 
  266.  
  267.  
  268. ΓòÉΓòÉΓòÉ 8. Support for representation invariants ΓòÉΓòÉΓòÉ
  269.  
  270. Most GNU C++ library classes possess a method named OK(), that is useful in 
  271. helping to verify correct performance of class operations. 
  272.  
  273. The OK() operations checks the ``representation invariant'' of a class object. 
  274. This is a test to check whether the object is in a valid state. In effect, it 
  275. is a (sometimes partial) verification of the library's promise that (1) class 
  276. operations always leave objects in valid states, and (2) the class protects 
  277. itself so that client functions cannot corrupt this state. 
  278.  
  279. While no simple validation technique can assure that all operations perform 
  280. correctly, calls to OK() can at least verify that operations do not corrupt 
  281. representations. For example for String a, b, c; ... a = b + c;, a call to 
  282. a.OK(); will guarantee that a is a valid String, but does not guarantee that it 
  283. contains the concatenation of b + c. However, given that a is known to be 
  284. valid, it is possible to further verify its properties, for example via 
  285. a.after(b) == c && a.before(c) == b. In other words, OK() generally checks only 
  286. those internal representation properties that are otherwise inaccessible to 
  287. users of the class. Other class operations are often useful for further 
  288. validation. 
  289.  
  290. Failed calls to OK() call a class's error method if one exists, else directly 
  291. call abort. Failure indicates an implementation error that should be reported. 
  292.  
  293. With only rare exceptions, the internal support functions for a class never 
  294. themselves call OK() (although many of the test files in the distribution call 
  295. OK() extensively). 
  296.  
  297. Verification of representational invariants can sometimes be very time 
  298. consuming for complicated data structures. 
  299.  
  300.  
  301. ΓòÉΓòÉΓòÉ 9. Introduction to container class prototypes ΓòÉΓòÉΓòÉ
  302.  
  303. As a temporary mechanism enabling the support of generic classes, the GNU C++ 
  304. Library distribution contains a directory (`g++-include') of files designed to 
  305. serve as the basis for generating container classes of specified elements. 
  306. These files can be used to generate `.h' and `.cc' files in the current 
  307. directory via a supplied shell script program that performs simple textual 
  308. substitution to create specific classes. 
  309.  
  310. While these classes are generated independently, and thus share no code, it is 
  311. possible to create versions that do share code among subclasses. For example, 
  312. using typedef void* ent, and then generating a entList class, other derived 
  313. classes could be created using the void* coercion method described in 
  314. Stroustrup, pp204-210. 
  315.  
  316. This very simple class-generation facility is useful enough to serve current 
  317. purposes, but will be replaced with a more coherent mechanism for handling C++ 
  318. generics in a way that minimally disrupts current usage. Without knowing 
  319. exactly when or how parametric classes might be added to the C++ language, 
  320. provision of this simplest possible mechanism, textual substitution, appears to 
  321. be the safest strategy, although it does require certain redundancies and 
  322. awkward constructions. 
  323.  
  324. Specific classes may be generated via the `genclass' shell script program. This 
  325. program has arguments specifying the kinds of base types(s) to be used. 
  326. Specifying base types requires two arguments. The first is the name of the base 
  327. type, which may be any named type, like int or String. Only named types are 
  328. supported; things like int* are not accepted. However, pointers like this may 
  329. be used by supplying the appropriate typedefs (e.g., editing the resulting 
  330. files to include typedef int* intp;). The type name must be followed by one of 
  331. the words val or ref, to indicate whether the base elements should be passed to 
  332. functions by-value or by-reference. 
  333.  
  334. You can specify basic container classes using genclass base [val,ref] proto, 
  335. where proto is the name of the class being generated.  Container classes like 
  336. dictionaries and maps that require two types may be specified via genclass -2 
  337. keytype [val, ref], basetype [val, ref] proto, where the key type is specified 
  338. first and the contents type second.  The resulting classnames and filenames are 
  339. generated by prepending the specified type names to the prototype names, and 
  340. separating the filename parts with dots.  For example, genclass int val List 
  341. generates class intList residing in files `int.List.h' and `int.List.cc'. 
  342. genclass -2 String ref int val VHMap generates (the awkward, but unavoidable) 
  343. class name StringintVHMap. Of course, programmers may use typedef or simple 
  344. editing to create more appropriate names.  The existence of dot seperators in 
  345. file names allows the use of GNU make to help automate configuration and 
  346. recompilation. An example Makefile exploiting such capabilities may be found in 
  347. the `libg++/proto-kit' directory. 
  348.  
  349. The genclass utility operates via simple text substitution using sed. All 
  350. occurrences of the pseudo-types <T> and <C> (if there are two types) are 
  351. replaced with the indicated type, and occurrences of <T&> and <C&> are replaced 
  352. by just the types, if val is specified, or types followed by ``&'' if ref is 
  353. specified. 
  354.  
  355. Programmers will frequently need to edit the `.h' file in order to insert 
  356. additional #include directives or other modifications.  A simple utility, 
  357. `prepend-header' to prepend other `.h' files to generated files is provided in 
  358. the distribution. 
  359.  
  360. One dubious virtue of the prototyping mechanism is that, because sources files, 
  361. not archived library classes, are generated, it is relatively simple for 
  362. programmers to modify container classes in the common case where slight 
  363. variations of standard container classes are required. 
  364.  
  365. It is often a good idea for programmers to archive (via ar) generated classes 
  366. into `.a' files so that only those class functions actually used in a given 
  367. application will be loaded. The test subdirectory of the distribution shows an 
  368. example of this. 
  369.  
  370. Because of #pragma interface directives, the `.cc' files should be compiled 
  371. with -O or -DUSE_LIBGXX_INLINES enabled. 
  372.  
  373. Many container classes require specifications over and above the base class 
  374. type. For example, classes that maintain some kind of ordering of elements 
  375. require specification of a comparison function upon which to base the ordering. 
  376. This is accomplished via a prototype file `defs.hP' that contains macros for 
  377. these functions. While these macros default to perform reasonable actions, they 
  378. can and should be changed in particular cases. Most prototypes require only one 
  379. or a few of these. No harm is done if unused macros are defined to perform 
  380. nonsensical actions. The macros are: 
  381.  
  382.  DEFAULT_INITIAL_CAPACITY 
  383.            The initial capacity for containers (e.g., hash tables) that require 
  384.            an initial capacity argument for constructors. Default: 100 
  385.  
  386.  <T>EQ(a, b) 
  387.            return true if a is considered equal to b for the purposes of 
  388.            locating, etc., an element in a container. Default: (a == b) 
  389.  
  390.  <T>LE(a, b) 
  391.            return true if a is less than or equal to b Default: (a <= b) 
  392.  
  393.  <T>CMP(a, b) 
  394.            return an integer < 0 if a<b, 0 if a==b, or > 0 if a>b. Default: (a 
  395.            <= b)? (a==b)? 0 : -1 : 1 
  396.  
  397.  <T>HASH(a) 
  398.            return an unsigned integer representing the hash of a. Default: 
  399.            hash(a) ; where extern unsigned int hash(<T&>). (note: several 
  400.            useful hash functions are declared in builtin.h and defined in 
  401.            hash.cc) 
  402.  
  403.  Nearly all prototypes container classes support container traversal via Pix 
  404.  pseudo indices, as described elsewhere. 
  405.  
  406.  All object containers must perform either a X::X(X&) (or X::X() followed by 
  407.  X::operator =(X&)) to copy objects into containers.  (The latter form is used 
  408.  for containers built from C++ arrays, like VHSets). When containers are 
  409.  destroyed, they invoke X::~X().  Any objects used in containers must have well 
  410.  behaved constructors and destructors. If you want to create containers that 
  411.  merely reference (point to) objects that reside elsewhere, and are not copied 
  412.  or destroyed inside the container, you must use containers of pointers, not 
  413.  containers of objects. 
  414.  
  415.  All prototypes are designed to generate HOMOGENOUS container classes.  There 
  416.  is no universally applicable method in C++ to support heterogenous object 
  417.  collections with elements of various subclasses of some specified base class. 
  418.  The only way to get heterogenous structures is to use collections of 
  419.  pointers-to-objects, not collections of objects (which also requires you to 
  420.  take responsibility for managing storage for the objects pointed to yourself). 
  421.  
  422.  For example, the following usage illustrates a commonly encountered danger in 
  423.  trying to use container classes for heterogenous structures: 
  424.  
  425.   class Base { int x; ...}
  426.   class Derived : public Base { int y; ... }
  427.  
  428.   BaseVHSet s; // class BaseVHSet generated via something like
  429.                // `genclass Base ref VHSet'
  430.  
  431.   void f()
  432.   {
  433.     Base b;
  434.     s.add(b); // OK
  435.  
  436.     Derived d;
  437.     s.add(d);  // (CHOP!)
  438.   }
  439.  
  440.  At the line flagged with `(CHOP!)', a Base::Base(Base&) is called inside 
  441.  Set::add(Base&)---not Derived::Derived(Derived&).  Actually, in VHSet, a 
  442.  Base::operator =(Base&), is used instead to place the element in an array 
  443.  slot, but with the same effect.  So only the Base part is copied as a VHSet 
  444.  element (a so-called chopped-copy). In this case, it has an x part, but no y 
  445.  part; and a Base, not Derived, vtable. Objects formed via chopped copies are 
  446.  rarely sensible. 
  447.  
  448.  To avoid this, you must resort to pointers: 
  449.  
  450.   typedef Base* BasePtr;
  451.  
  452.   BasePtrVHSet s; // class BaseVHSet generated via something like
  453.                   // `genclass BasePtr val VHSet'
  454.  
  455.   void f()
  456.   {
  457.     Base* bp = new Base;
  458.     s.add(b);
  459.  
  460.     Base* dp = new Derived;
  461.     s.add(d);  // works fine.
  462.  
  463.     // Don't forget to delete bp and dp sometime.
  464.     // The VHSet won't do this for you.
  465.   }
  466.  
  467.  
  468. ΓòÉΓòÉΓòÉ 9.1. Example ΓòÉΓòÉΓòÉ
  469.  
  470. The prototypes can be difficult to use on first attempt. Here is an example 
  471. that may be helpful. The utilities in the `proto-kit' simplify much of the 
  472. actions described, but are not used here. 
  473.  
  474. Suppose you create a class Person, and want to make an Map that links the 
  475. social security numbers associated with each person. You start off with a file 
  476. `Person.h' 
  477.  
  478.  
  479. #include <String.h>
  480.  
  481. class Person
  482. {
  483.   String nm;
  484.   String addr;
  485.   //...
  486. public:
  487.   const String& name() { return nm; }
  488.   const String& address() { return addr; }
  489.   void          print() { ... }
  490.   //...
  491. }
  492.  
  493. And in file `SSN.h', 
  494.  
  495. typedef unsigned int SSN;
  496.  
  497. Your first decision is what storage/usage strategy to use. There are several 
  498. reasonable alternatives here: You might create an ``object collection'' of 
  499. Persons, a ``pointer collection'' of pointers-to-Persons, or even a simple 
  500. String map, housing either copies of pointers to the names of Persons, since 
  501. other fields are unused for purposes of the Map. In an object collection, 
  502. instances of class Person ``live'' inside the Map, while in a pointer 
  503. collection, the instances live elsewhere. Also, as above, if instances of 
  504. subclasses of Person are to be used inside the Map, you must use pointers. In a 
  505. String Map, the same difference holds, but now only for the name fields. Any of 
  506. these choices might make sense in particular applications. 
  507.  
  508. The second choice is the Map implementation strategy. Either a tree or a hash 
  509. table might make sense. Suppose you want an AVL tree Map. There are two things 
  510. to now check. First, as an object collection, the AVLMap requires that the 
  511. elsement class contain an X(X&) constructor. In C++, if you don't specify such 
  512. a constructor, one is constructed for you, but it is a very good idea to always 
  513. do this yourself, to avoid surprises. In this example, you'd use something like 
  514.  
  515. class Person
  516. { ...;
  517.     Person(const Person& p) :nm(p.nm), addr(p.addr) {}
  518. };
  519.  
  520. Also, an AVLMap requires a comparison function for elements in order to 
  521. maintain order. Rather than requiring you to write a particular comparison 
  522. function, a `defs' file is consulted to determine how to compare items. You 
  523. must create and edit such a file. 
  524.  
  525. Before creating `Person.defs.h', you must first make one additional decision. 
  526. Should the Map member functions like m.contains(p) take arguments (p) by 
  527. reference (i.e., typed as int Map::contains(const Person& p) or by value (i.e., 
  528. typed as int Map::contains(const Person p). Generally, for user-defined 
  529. classes, you want to pass by reference, and for builtins and pointers, to pass 
  530. by value. SO you should pick by-reference. 
  531.  
  532. You can now create `Person.defs.h' via genclass Person ref defs. This creates a 
  533. simple skeleton that you must edit. First, add #include "Person.h" to the top. 
  534. Second, edit the <T>CMP(a,b) macro to compare on name, via 
  535.  
  536. #define <T>CMP(a, b) ( compare(a.name(), b.name()) )
  537.  
  538. which invokes the int compare(const String&, const String&) function from 
  539. `String.h'. Of course, you could define this in any other way as well. In fact, 
  540. the default versions in the skeleton turn out to be OK (albeit inefficient) in 
  541. this particular example. 
  542.  
  543. You may also want to create file `SSN.defs.h'. Here, choosing call-by-value 
  544. makes sense, and since no other capabilities (like comparison functions) of the 
  545. SSNs are used (and the defaults are OK anyway), you'd type 
  546.  
  547. genclass SSN val defs
  548.  
  549. and then edit to place #include "SSN.h" at the top. 
  550.  
  551. Finally, you can generate the classes. First, generate the base class for Maps 
  552. via 
  553.  
  554. genclass -2 Person ref SSN val Map
  555.  
  556. This generates only the abstract class, not the implementation, in file 
  557. `Person.SSN.Map.h' and `Person.SSN.Map.cc'.  To create the AVL implementation, 
  558. type 
  559.  
  560. genclass -2 Person ref SSN val AVLMap
  561.  
  562. This creates the class PersonSSNAVLMap, in `Person.SSN.AVLMap.h' and 
  563. `Person.SSN.AVLMap.cc'. 
  564.  
  565. To use the AVL implementation, compile the two generated `.cc' files, and 
  566. specify `#include "Person.SSN.AVLMap.h"' in the application program. All other 
  567. files are included in the right ways automatically. 
  568.  
  569. One last consideration, peculiar to Maps, is to pick a reasonable default 
  570. contents when declaring an AVLMap. Zero might be appropriate here, so you might 
  571. declare a Map, 
  572.  
  573. PersonSSNAVLMap m((SSN)0);
  574.  
  575. Suppose you wanted a VHMap instead of an AVLMap Besides generating different 
  576. implementations, there are two differences in how you should prepare the `defs' 
  577. file. First, because a VHMap uses a C++ array internally, and because C++ array 
  578. slots are initialized differently than single elements, you must ensure that 
  579. class Person contains (1) a no-argument constructor, and (2) an assignment 
  580. operator. You could arrange this via 
  581.  
  582. class Person
  583. { ...;
  584.     Person() {}
  585.   void operator = (const Person& p) { nm = p.nm; addr = p.addr; }
  586. };
  587.  
  588. (The lack of action in the constructor is OK here because Strings possess 
  589. usable no-argument constructors.) 
  590.  
  591. You also need to edit `Person.defs.h' to indicate a usable hash function and 
  592. default capacity, via something like 
  593.  
  594. #include <builtin.h>
  595. #define <T>HASH(x)  (hashpjw(x.name().chars()))
  596. #define DEFAULT_INITIAL_CAPACITY 1000
  597.  
  598. Since the hashpjw function from `builtin.h' is appropriate here. Changing the 
  599. default capacity to a value expected to exceed the actual capacity helps to 
  600. avoid ``hidden'' inefficiencies when a new VHMap is created without overriding 
  601. the default, which is all too easy to do. 
  602.  
  603. Otherwise, everything is the same as above, substituting VHMap for AVLMap. 
  604.  
  605.  
  606. ΓòÉΓòÉΓòÉ 10. Variable-Sized Object Representation ΓòÉΓòÉΓòÉ
  607.  
  608. One of the first goals of the GNU C++ library is to enrich the kinds of basic 
  609. classes that may be considered as (nearly) ``built into'' C++. A good deal of 
  610. the inspiration for these efforts is derived from considering features of other 
  611. type-rich languages, particularly Common Lisp and Scheme. The general 
  612. characteristics of most class and friend operators and functions supported by 
  613. these classes has been heavily influenced by such languages. 
  614.  
  615. Four of these types, Strings, Integers, BitSets, and BitStrings (as well as 
  616. associated and/or derived classes) require representations suitable for 
  617. managing variable-sized objects on the free-store. The basic technique used for 
  618. all of these is the same, although various details necessarily differ from 
  619. class to class. 
  620.  
  621. The general strategy for representing such objects is to create chunks of 
  622. memory that include both header information (e.g., the size of the object), as 
  623. well as the variable-size data (an array of some sort) at the end of the chunk. 
  624. Generally the maximum size of an object is limited to something less than all 
  625. of addressable memory, as a safeguard. The minimum size is also limited so as 
  626. not to waste allocations expanding very small chunks. Internally, chunks are 
  627. allocated in blocks well-tuned to the performance of the new operator. 
  628.  
  629. Class elements themselves are merely pointers to these chunks. Most class 
  630. operations are performed via inline ``translation'' functions that perform the 
  631. required operation on the corresponding representation. However, constructors 
  632. and assignments operate by copying entire representations, not just pointers. 
  633.  
  634. No attempt is made to control temporary creation in expressions and functions 
  635. involving these classes. Users of previous versions of the classes will note 
  636. the disappearance of both ``Tmp'' classes and reference counting. These were 
  637. dropped because, while they did improve performance in some cases, they obscure 
  638. class mechanics, lead programmers into the false belief that they need not 
  639. worry about such things, and occasionally have paradoxical behavior. 
  640.  
  641. These variable-sized object classes are integrated as well as possible into 
  642. C++. Most such classes possess converters that allow automatic coercion both 
  643. from and to builtin basic types. (e.g., char* to and from String, long int to 
  644. and from Integer, etc.). There are pro's and con's to circular converters, 
  645. since they can sometimes lead to the conversion from a builtin type through to 
  646. a class function and back to a builtin type without any special attention on 
  647. the part of the programmer, both for better and worse. 
  648.  
  649. Most of these classes also provide special-case operators and functions mixing 
  650. basic with class types, as a way to avoid constructors in cases where the 
  651. operations do not rely on anything special about the representations.  For 
  652. example, there is a special case concatenation operator for a String 
  653. concatenated with a char, since building the result does not rely on anything 
  654. about the String header. Again, there are arguments both for and against this 
  655. approach. Supporting these cases adds a non-trivial degree of (mainly inline) 
  656. function proliferation, but results in more efficient operations. Efficiency 
  657. wins out over parsimony here, as part of the goal to produce classes that 
  658. provide sufficient functionality and efficiency so that programmers are not 
  659. tempted to try to manipulate or bypass the underlying representations. 
  660.  
  661.  
  662. ΓòÉΓòÉΓòÉ 11. Some guidelines for using expression-oriented classes ΓòÉΓòÉΓòÉ
  663.  
  664. The fact that C++ allows operators to be overloaded for user-defined classes 
  665. can make programming with library classes like Integer, String, and so on very 
  666. convenient. However, it is worth becoming familiar with some of the inherent 
  667. limitations and problems associated with such operators. 
  668.  
  669. Many operators are constructive, i.e., create a new object based on some 
  670. function of some arguments. Sometimes the creation of such objects is wasteful. 
  671. Most library classes supporting expressions contain facilities that help you 
  672. avoid such waste. 
  673.  
  674. For example, for Integer a, b, c; ...;  c = a + b + a;, the plus operator is 
  675. called to sum a and b, creating a new temporary object as its result. This 
  676. temporary is then added with a, creating another temporary, which is finally 
  677. copied into c, and the temporaries are then deleted. In other words, this code 
  678. might have an effect similar to Integer a, b, c; ...; Integer t1(a); t1 += b; 
  679. Integer t2(t1); t2 += a; c = t2;. 
  680.  
  681. For small objects, simple operators, and/or non-time/space critical programs, 
  682. creation of temporaries is not a big problem. However, often, when fine-tuning 
  683. a program, it may be a good idea to rewrite such code in a less pleasant, but 
  684. more efficient manner. 
  685.  
  686. For builtin types like ints, and floats, C and C++ compilers already know how 
  687. to optimize such expressions to reduce the need for temporaries. Unfortunately, 
  688. this is not true for C++ user defined types, for the simple (but very annoying, 
  689. in this context) reason that nothing at all is guaranteed about the semantics 
  690. of overloaded operators and their interrelations. For example, if the above 
  691. expression just involved ints, not Integers, a compiler might internally 
  692. convert the statement into something like c = a; c += b; c+= a; , or perhaps 
  693. something even more clever.  But since C++ does not know that Integer operator 
  694. += has any relation to Integer operator +, A C++ compiler cannot do this kind 
  695. of expression optimization itself. 
  696.  
  697. In many cases, you can avoid construction of temporaries simply by using the 
  698. assignment versions of operators whenever possible, since these versions create 
  699. no temporaries. However, for maximum flexibility, most classes provide a set of 
  700. ``embedded assembly code'' procedures that you can use to fully control time, 
  701. space, and evaluation strategies. Most of these procedures are 
  702. ``three-address'' procedures that take two const source arguments, and a 
  703. destination argument. The procedures perform the appropriate actions, placing 
  704. the results in the destination (which is may involve overwriting old contents). 
  705. These procedures are designed to be fast and robust. In particular, aliasing is 
  706. always handled correctly, so that, for example add(x, x, x);  is perfectly OK. 
  707. (The names of these procedures are listed along with the classes.) 
  708.  
  709. For example, suppose you had an Integer expression a = (b - a) * -(d / c); 
  710.  
  711. This would be compiled as if it were Integer t1=b-a; Integer t2=d/c; Integer 
  712. t3=-t2; Integer t4=t1*t3; a=t4; 
  713.  
  714. But, with some manual cleverness, you might yourself some up with sub(a, b, a); 
  715. mul(a, d, a); div(a, c, a); 
  716.  
  717. A related phenomenon occurs when creating your own constructive functions 
  718. returning instances of such types. Suppose you wanted to write function Integer 
  719. f(const Integer& a) { Integer r = a;  r += a; return r; } 
  720.  
  721. This function, when called (as in a = f(a); ) demonstrates a similar kind of 
  722. wasted copy. The returned value r must be copied out of the function before it 
  723. can be used by the caller. In GNU C++, there is an alternative via the use of 
  724. named return values. Named return values allow you to manipulate the returned 
  725. object directly, rather than requiring you to create a local inside a function 
  726. and then copy it out as the returned value. In this example, this can be done 
  727. via Integer f(const Integer& a) return r(a) { r += a; return; } 
  728.  
  729. A final guideline: The overloaded operators are very convenient, and much 
  730. clearer to use than procedural code. It is almost always a good idea to make it 
  731. right, then make it fast, by translating expression code into procedural code 
  732. after it is known to be correct. 
  733.  
  734.  
  735. ΓòÉΓòÉΓòÉ 12. Pseudo-indexes ΓòÉΓòÉΓòÉ
  736.  
  737. Many useful classes operate as containers of elements. Techniques for accessing 
  738. these elements from a container differ from class to class. In the GNU C++ 
  739. library, access methods have been partially standardized across different 
  740. classes via the use of pseudo-indexes called Pixes.  A Pix acts in some ways 
  741. like an index, and in some ways like a pointer. (Their underlying 
  742. representations are just void* pointers). A Pix is a kind of ``key'' that is 
  743. translated into an element access by the class.  In virtually all cases, Pixes 
  744. are pointers to some kind internal storage cells. The containers use these 
  745. pointers to extract items. 
  746.  
  747. Pixes support traversal and inspection of elements in a collection using 
  748. analogs of array indexing. However, they are pointer-like in that 0 is treated 
  749. as an invalid Pix, and unsafe insofar as programmers can attempt to access 
  750. nonexistent elements via dangling or otherwise invalid Pixes without first 
  751. checking for their validity. 
  752.  
  753. In general it is a very bad idea to perform traversals in the the midst of 
  754. destructive modifications to containers. 
  755.  
  756. Typical applications might include code using the idiom 
  757.  
  758. for (Pix i = a.first(); i != 0; a.next(i)) use(a(i));
  759.  
  760. for some container a and function use. 
  761.  
  762. Classes supporting the use of Pixes always contain the following methods, 
  763. assuming a container a of element types of Base. 
  764.  
  765.  Pix i = a.first() 
  766.            Set i to index the first element of a or 0 if a is empty. 
  767.  
  768.  a.next(i) 
  769.            advance i to the next element of a or 0 if there is no next element; 
  770.  
  771.  Base x = a(i); a(i) = x; 
  772.            a(i) returns a reference to the element indexed by i. 
  773.  
  774.  int present = a.owns(i) 
  775.            returns true if Pix i is a valid Pix in a. This is often a 
  776.            relatively slow operation, since the collection must usually 
  777.            traverse through elements to see if any correspond to the Pix. 
  778.  
  779.  Some container classes also support backwards traversal via 
  780.  
  781.  Pix i = a.last() 
  782.            Set i to the last element of a or 0 if a is empty. 
  783.  
  784.  a.prev(i) 
  785.            sets i to the previous element in a, or 0 if there is none. 
  786.  
  787.  Collections supporting elements with an equality operation possess 
  788.  
  789.  Pix j = a.seek(x) 
  790.            sets j to the index of the first occurrence of x, or 0 if x is not 
  791.            contained in a. 
  792.  
  793.  Bag classes possess 
  794.  
  795.  Pix j = a.seek(x, Pix from = 0) 
  796.            sets j to the index of the next occurrence of x following i, or 0 if 
  797.            x is not contained in a. If i == 0, the first occurrence is 
  798.            returned. 
  799.  
  800.  Set, Bag, and PQ classes possess 
  801.  
  802.  Pix j = a.add(x) (or a.enq(x) for priority queues) 
  803.            add x to the collection, returning its Pix. The Pix of an item can 
  804.            change in collections where further additions and deletions involve 
  805.            the actual movement of elements (currently in OXPSet, OXPBag, XPPQ, 
  806.            VOHSet), but in all other cases, an item's Pix may be considered a 
  807.            permanent key to its location. 
  808.  
  809.  
  810. ΓòÉΓòÉΓòÉ 13. Header files for interfacing C++ to C ΓòÉΓòÉΓòÉ
  811.  
  812. The following files are provided so that C++ programmers may invoke common C 
  813. library and system calls. The names and contents of these files are subject to 
  814. change in order to be compatible with the forthcoming GNU C library. Other 
  815. files, not listed here, are simply C++-compatible interfaces to corresponding C 
  816. library files. 
  817.  
  818.  `values.h' 
  819.            A collection of constants defining the numbers of bits in builtin 
  820.            types, minimum and maximum values, and the like. Most names are the 
  821.            same as those found in `values.h' found on Sun systems. 
  822.  
  823.  `std.h' 
  824.            A collection of common system calls and `libc.a' functions. Only 
  825.            those functions that can be declared without introducing new type 
  826.            definitions (socket structures, for example) are provided. Common 
  827.            char* functions (like strcmp) are among the declarations. All 
  828.            functions are declared along with their library names, so that they 
  829.            may be safely overloaded. 
  830.  
  831.  `string.h' 
  832.            This file merely includes `<std.h>', where string function 
  833.            prototypes are declared. This is a workaround for the fact that 
  834.            system `string.h' and `strings.h' files often differ in contents. 
  835.  
  836.  `osfcn.h' 
  837.            This file merely includes `<std.h>', where system function 
  838.            prototypes are declared. 
  839.  
  840.  `libc.h' 
  841.            This file merely includes `<std.h>', where C library function 
  842.            prototypes are declared. 
  843.  
  844.  `math.h' 
  845.            A collection of prototypes for functions usually found in libm.a, 
  846.            plus some #defined constants that appear to be consistent with those 
  847.            provided in the AT&T version. The value of HUGE should be checked 
  848.            before using. Declarations of all common math functions are preceded 
  849.            with overload declarations, since these are commonly overloaded. 
  850.  
  851.  `stdio.h' 
  852.            Declaration of FILE (_iobuf), common macros (like getc), and 
  853.            function prototypes for `libc.a' functions that operate on FILE*'s. 
  854.            The value BUFSIZ and the declaration of _iobuf should be checked 
  855.            before using. 
  856.  
  857.  `assert.h' 
  858.            C++ versions of assert macros. 
  859.  
  860.  `generic.h' 
  861.            String concatenation macros useful in creating generic classes. They 
  862.            are similar in function to the AT&T CC versions. 
  863.  
  864.  `new.h' 
  865.            Declarations of the default global operator new, the two-argument 
  866.            placement version, and associated error handlers. 
  867.  
  868.  
  869. ΓòÉΓòÉΓòÉ 14. Utility functions for built in types ΓòÉΓòÉΓòÉ
  870.  
  871. Files `builtin.h' and corresponding `.cc' implementation files contain various 
  872. convenient inline and non-inline utility functions. These include useful 
  873. enumeration types, such as TRUE, FALSE ,the type definition for pointers to 
  874. libg++ error handling functions, and the following functions. 
  875.  
  876.  long abs(long x); double abs(double x); 
  877.            inline versions of abs. Note that the standard libc.a version, int 
  878.            abs(int) is not declared as inline. 
  879.  
  880.  void clearbit(long& x, long b); 
  881.            clears the b'th bit of x (inline). 
  882.  
  883.  void setbit(long& x, long b); 
  884.            sets the b'th bit of x (inline) 
  885.  
  886.  int testbit(long x, long b); 
  887.            returns the b'th bit of x (inline). 
  888.  
  889.  int even(long y); 
  890.            returns true if x is even (inline). 
  891.  
  892.  int odd(long y); 
  893.            returns true is x is odd (inline). 
  894.  
  895.  int sign(long x); int sign(double x); 
  896.            returns -1, 0, or 1, indicating whether x is less than, equal to, or 
  897.            greater than zero (inline). 
  898.  
  899.  long gcd(long x, long y); 
  900.            returns the greatest common divisor of x and y. 
  901.  
  902.  long lcm(long x, long y); 
  903.            returns the least common multiple of x and y. 
  904.  
  905.  long lg(long x); 
  906.            returns the floor of the base 2 log of x. 
  907.  
  908.  long pow(long x, long y); double pow(double x, long y); 
  909.            returns x to the integer power y using via the iterative O(log y) 
  910.            ``Russian peasant'' method. 
  911.  
  912.  long sqr(long x); double sqr(double x); 
  913.            returns x squared (inline). 
  914.  
  915.  long sqrt(long y); 
  916.            returns the floor of the square root of x. 
  917.  
  918.  unsigned int hashpjw(const char* s); 
  919.            a hash function for null-terminated char* strings using the method 
  920.            described in Aho, Sethi, & Ullman, p 436. 
  921.  
  922.  unsigned int multiplicativehash(int x); 
  923.            a hash function for integers that returns the lower bits of 
  924.            multiplying x by the golden ratio times pow(2, 32). See Knuth, Vol 
  925.            3, p 508. 
  926.  
  927.  unsigned int foldhash(double x); 
  928.            a hash function for doubles that exclusive-or's the first and second 
  929.            words of x, returning the result as an integer. 
  930.  
  931.  double start_timer() 
  932.            Starts a process timer. 
  933.  
  934.  double return_elapsed_time(double last_time) 
  935.            Returns the process time since last_time. If last_time == 0 returns 
  936.            the time since the last start_timer. Returns -1 if start_timer was 
  937.            not first called. 
  938.  
  939.  File `Maxima.h' includes versions of MAX, MIN for builtin types. 
  940.  
  941.  File `compare.h' includes versions of compare(x, y) for builtin types. These 
  942.  return negative if the first argument is less than the second, zero for equal, 
  943.  and positive for greater. 
  944.  
  945.  
  946. ΓòÉΓòÉΓòÉ 15. Library dynamic allocation primitives ΓòÉΓòÉΓòÉ
  947.  
  948. Libg++ contains versions of malloc, free, realloc that were designed to be 
  949. well-tuned to C++ applications. The source file `malloc.c' contains some design 
  950. and implementation details. Here are the major user-visible differences from 
  951. most system malloc routines: 
  952.  
  953.    1. These routines overwrite storage of freed space. This means that it is 
  954.       never permissible to use a delete'd object in any way. Doing so will 
  955.       either result in trapped fatal errors or random aborts within malloc, 
  956.       free, or realloc. 
  957.  
  958.    2. The routines tend to perform well when a large number of objects of the 
  959.       same size are allocated and freed. You may find that it is not worth it 
  960.       to create your own special allocation schemes in such cases. 
  961.  
  962.    3. The library sets top-level operator new() to call malloc and operator 
  963.       delete() to call free. Of course, you may override these definitions in 
  964.       C++ programs by creating your own operators that will take precedence 
  965.       over the library versions. However, if you do so, be sure to define both 
  966.       operator new() and operator delete(). 
  967.  
  968.    4. These routines do not support the odd convention, maintained by some 
  969.       versions of malloc, that you may call realloc with a pointer that has 
  970.       been free'd. 
  971.  
  972.    5. The routines automatically perform simple checks on free'd pointers that 
  973.       can often determine whether users have accidentally written beyond the 
  974.       boundaries of allocated space, resulting in a fatal error. 
  975.  
  976.    6. The function malloc_usable_size(void* p) returns the number of bytes 
  977.       actually allocated for p. For a valid pointer (i.e., one that has been 
  978.       malloc'd or realloc'd but not yet free'd) this will return a number 
  979.       greater than or equal to the requested size, else it will normally return 
  980.       0. Unfortunately, a non-zero return can not be an absolutely perfect 
  981.       indication of lack of error. If a chunk has been free'd but then 
  982.       re-allocated for a different purpose somewhere elsewhere, then 
  983.       malloc_usable_size will return non-zero. Despite this, the function can 
  984.       be very valuable for performing run-time consistency checks. 
  985.  
  986.    7. malloc requires 8 bytes of overhead per allocated chunk, plus a mmaximum 
  987.       alignment adjustment of 8 bytes. The number of bytes of usable space is 
  988.       exactly as requested, rounded to the nearest 8 byte boundary. 
  989.  
  990.    8. The routines do not contain any synchronization support for 
  991.       multiprocessing. If you perform global allocation on a shared memory 
  992.       multiprocessor, you should disable compilation and use of libg++ malloc 
  993.       in the distribution `Makefile' and use your system version of malloc. 
  994.  
  995.  
  996. ΓòÉΓòÉΓòÉ 16. The old I/O library ΓòÉΓòÉΓòÉ
  997.  
  998. WARNING: This chapter describes classes that are obsolete. These classes are 
  999. normally not available when libg++ is installed normally.  The sources are 
  1000. currently included in the distribution, and you can configure libg++ to use 
  1001. these classes instead of the new iostream classes. This is only a temporary 
  1002. measure; you should convert your code to use iostreams as soon as possible. 
  1003. The iostream classes provide some compatibility support, but it is very 
  1004. incomplete (there is no longer a File class). 
  1005.  
  1006.  
  1007. ΓòÉΓòÉΓòÉ 16.1. File-based classes ΓòÉΓòÉΓòÉ
  1008.  
  1009. The File class supports basic IO on Unix files.  Operations are based on common 
  1010. C stdio library functions. 
  1011.  
  1012. File serves as the base class for istreams, ostreams, and other derived 
  1013. classes. It contains the interface between the Unix stdio file library and 
  1014. these more structured classes.  Most operations are implemented as simple calls 
  1015. to stdio functions. File class operations are also fully compatible with raw 
  1016. system file reads and writes (like the system read and lseek calls) when 
  1017. buffering is disabled (see below). The FILE* stdio file pointer is, however 
  1018. maintained as protected. Classes derived from File may only use the IO 
  1019. operations provided by File, which encompass essentially all stdio 
  1020. capabilities. 
  1021.  
  1022. The class contains four general kinds of functions: methods for binding Files 
  1023. to physical Unix files, basic IO methods, file and buffer control methods, and 
  1024. methods for maintaining logical and physical file status. 
  1025.  
  1026. Binding and related tasks are accomplished via File constructors and 
  1027. destructors, and member functions open, close, remove, filedesc, name, setname. 
  1028.  
  1029. If a file name is provided in a constructor or open, it is maintained as class 
  1030. variable nm and is accessible via name.  If no name is provided, then nm 
  1031. remains null, except that Files bound to the default files stdin, stdout, and 
  1032. stderr are automatically given the names (stdin), (stdout), (stderr) 
  1033. respectively. The function setname may be used to change the internal name of 
  1034. the File. This does not change the name of the physical file bound to the File. 
  1035.  
  1036. The member function close closes a file.  The ~File destructor closes a file if 
  1037. it is open, except that stdin, stdout, and stderr are flushed but left open for 
  1038. the system to close on program exit since some systems may require this, and on 
  1039. others it does not matter.  remove closes the file, and then deletes it if 
  1040. possible by calling the system function to delete the file with the name 
  1041. provided in the nm field. 
  1042.  
  1043.  
  1044. ΓòÉΓòÉΓòÉ 16.2. Basic IO ΓòÉΓòÉΓòÉ
  1045.  
  1046.      read and write perform binary IO via stdio fread and fwrite. 
  1047.  
  1048.      get and put for chars invoke stdio getc and putc macros. 
  1049.  
  1050.      put(const char* s) outputs a null-terminated string via stdio fputs. 
  1051.  
  1052.      unget and putback are synonyms.  Both call stdio ungetc. 
  1053.  
  1054.  
  1055. ΓòÉΓòÉΓòÉ 16.3. File Control ΓòÉΓòÉΓòÉ
  1056.  
  1057. flush, seek, tell, and tell call the corresponding stdio functions. 
  1058.  
  1059. flush(char) and fill() call stdio _flsbuf and _filbuf respectively. 
  1060.  
  1061. setbuf is mainly useful to turn off buffering in cases where nonsequential 
  1062. binary IO is being performed. raw is a synonym for setbuf(_IONBF).  After a 
  1063. f.raw(), using the stdio functions instead of the system read, write, etc., 
  1064. calls entails very little overhead.  Moreover, these become fully compatible 
  1065. with intermixed system calls (e.g., lseek(f.filedesc(), 0, 0)). While 
  1066. intermixing File and system IO calls is not at all recommended, this technique 
  1067. does allow the File class to be used in conjunction with other functions and 
  1068. libraries already set up to operate on file descriptors. setbuf should be 
  1069. called at most once after a constructor or open, but before any IO. 
  1070.  
  1071.  
  1072. ΓòÉΓòÉΓòÉ 16.4. File Status ΓòÉΓòÉΓòÉ
  1073.  
  1074. File status is maintained in several ways. 
  1075.  
  1076. A File may be checked for accessibility via is_open(), which returns true if 
  1077. the File is bound to a usable physical file, readable(), which returns true if 
  1078. the File can be read from (opened for reading, and not in a _fail state), or 
  1079. writable(), which returns true if the File can be written to. 
  1080.  
  1081. File operations return their status via two means: failure and success are 
  1082. represented via the logical state. Also, the return values of invoked stdio and 
  1083. system functions that return useful numeric values (not just failure/success 
  1084. flags) are held in a class variable accessible via iocount. (This is useful, 
  1085. for example, in determining the number of items actually read by the read 
  1086. function.) 
  1087.  
  1088. Like the AT&T i/o-stream classes, but unlike the description in the Stroustrup 
  1089. book, p238, rdstate() returns the bitwise OR of _eof, _fail and _bad, not 
  1090. necessarily distinct values. The functions eof(), fail(), bad(), and good() can 
  1091. be used to test for each of these conditions independently. 
  1092.  
  1093. _fail becomes set for any input operation that could not read in the desired 
  1094. data, and for other failed operations. As with all Unix IO, _eof becomes true 
  1095. only when an input operations fails because of an end of file. Therefore, _eof 
  1096. is not immediately true after the last successful read of a file, but only 
  1097. after one final read attempt. Thus, for input operations, _fail and _eof almost 
  1098. always become true at the same time.  bad is set for unbound files, and may 
  1099. also be set by applications in order to communicate input corruption. 
  1100. Conversely, _good is defined as 0 and is returned by rdstate() if all is well. 
  1101.  
  1102. The state may be modified via clear(flag), which, despite its name, sets the 
  1103. corresponding state_value flag. clear() with no arguments resets the state to 
  1104. _good. failif(int cond) sets the state to _fail only if cond is true. 
  1105.  
  1106. Errors occuring during constructors and file opens also invoke the function 
  1107. error.  error in turn calls a resetable error handling function pointed to by 
  1108. the non-member global variable File_error_handler only if a system error has 
  1109. been generated. Since error cannot tell if the current system error is actually 
  1110. responsible for a failure, it may at times print out spurious messages. Three 
  1111. error handlers are provided. The default, verbose_File_error_handler calls the 
  1112. system function perror to print the corresponding error message on standard 
  1113. error, and then returns to the caller.  quiet_File_error_handler does nothing, 
  1114. and simply returns.  fatal_File_error_handler prints the error and then aborts 
  1115. execution. These three handlers, or any other user-defined error handlers can 
  1116. be selected via the non-member function set_File_error_handler. 
  1117.  
  1118. All read and write operations communicate either logical or physical failure by 
  1119. setting the _fail flag.  All further operations are blocked if the state is in 
  1120. a _fail or_bad condition. Programmers must explicitly use clear() to reset the 
  1121. state in order to continue IO processing after either a logical or physical 
  1122. failure.  C programmers who are unfamiliar with these conventions should note 
  1123. that, unlike the stdio library, File functions indicate IO success, status, or 
  1124. failure solely through the state, not via return values of the functions.  The 
  1125. void* operator or rdstate() may be used to test success.  In particular, 
  1126. according to c++ conversion rules, the void* coercion is automatically applied 
  1127. whenever the File& return value of any File function is tested in an if or 
  1128. while.  Thus, for example, an easy way to copy all of stdin to stdout until eof 
  1129. (at which point get fails) or some error is char c; while(cin.get(c) && 
  1130. cout.put(c));. The current version of istreams and ostreams differs 
  1131. significantly 
  1132.  
  1133. from previous versions in order to obtain compatibility with AT&T 1.2 streams. 
  1134. Most code using previous versions should still work. However, the following 
  1135. features of File are not incorporated in streams (they are still present in 
  1136. File): scan(const char* fmt...), remove(), read(), write(), setbuf(), raw(). 
  1137. Additionally, the feature of previous streams that allowed free intermixing of 
  1138. stream and stdio input and output is no longer guaranteed to always behave as 
  1139. desired. 
  1140.  
  1141.  
  1142. ΓòÉΓòÉΓòÉ 17. The Obstack class ΓòÉΓòÉΓòÉ
  1143.  
  1144. The Obstack class is a simple rewrite of the C obstack macros and functions 
  1145. provided in the GNU CC compiler source distribution. 
  1146.  
  1147. Obstacks provide a simple method of creating and maintaining a string table, 
  1148. optimized for the very frequent task of building strings 
  1149. character-by-character, and sometimes keeping them, and sometimes not. They 
  1150. seem especially useful in any parsing application. One of the test files 
  1151. demonstrates usage. 
  1152.  
  1153. A brief summary: 
  1154.  
  1155.  grow 
  1156.            places something on the obstack without committing to wrap it up as 
  1157.            a single entity yet. 
  1158.  
  1159.  finish 
  1160.            wraps up a constructed object as a single entity, and returns the 
  1161.            pointer to its start address. 
  1162.  
  1163.  copy 
  1164.            places things on the obstack, and does wrap them up. copy is always 
  1165.            equivalent to first grow, then finish. 
  1166.  
  1167.  free 
  1168.            deletes something, and anything else put on the obstack since its 
  1169.            creation. 
  1170.  
  1171.  The other functions are less commonly needed: 
  1172.  
  1173.  blank 
  1174.            is like grow, except it just grows the space by size units without 
  1175.            placing anything into this space 
  1176.  
  1177.  alloc 
  1178.            is like blank, but it wraps up the object and returns its starting 
  1179.            address. 
  1180.  
  1181.  chunk_size, base, next_free, alignment_mask, size, room 
  1182.            returns the appropriate class variables. 
  1183.  
  1184.  grow_fast 
  1185.            places a character on the obstack without checking if there is 
  1186.            enough room. 
  1187.  
  1188.  blank_fast 
  1189.            like blank, but without checking if there is enough room. 
  1190.  
  1191.  shrink(int n) 
  1192.            shrink the current chunk by n bytes. 
  1193.  
  1194.  contains(void* addr) 
  1195.            returns true if the Obstack holds the address addr. 
  1196.  
  1197.  Here is a lightly edited version of the original C documentation: 
  1198.  
  1199.  These functions operate a stack of objects.  Each object starts life small, 
  1200.  and may grow to maturity.  (Consider building a word syllable by syllable.) 
  1201.  An object can move while it is growing.  Once it has been ``finished'' it 
  1202.  never changes address again.  So the ``top of the stack'' is typically an 
  1203.  immature growing object, while the rest of the stack is of mature, fixed size 
  1204.  and fixed address objects. 
  1205.  
  1206.  These routines grab large chunks of memory, using the GNU C++ new operator. 
  1207.  On occasion, they free chunks, via delete. 
  1208.  
  1209.  Each independent stack is represented by a Obstack. 
  1210.  
  1211.  One motivation for this package is the problem of growing char strings in 
  1212.  symbol tables.  Unless you are a ``fascist pig with a read-only mind'' 
  1213.  [Gosper's immortal quote from HAKMEM item 154, out of context] you would not 
  1214.  like to put any arbitrary upper limit on the length of your symbols. 
  1215.  
  1216.  In practice this often means you will build many short symbols and a few long 
  1217.  symbols.  At the time you are reading a symbol you don't know how long it is. 
  1218.  One traditional method is to read a symbol into a buffer, realloc()ating the 
  1219.  buffer every time you try to read a symbol that is longer than the buffer. 
  1220.  This is beaut, but you still will want to copy the symbol from the buffer to a 
  1221.  more permanent symbol-table entry say about half the time. 
  1222.  
  1223.  With obstacks, you can work differently.  Use one obstack for all symbol 
  1224.  names.  As you read a symbol, grow the name in the obstack gradually. When the 
  1225.  name is complete, finalize it.  Then, if the symbol exists already, free the 
  1226.  newly read name. 
  1227.  
  1228.  The way we do this is to take a large chunk, allocating memory from low 
  1229.  addresses.  When you want to build a symbol in the chunk you just add chars 
  1230.  above the current ``high water mark'' in the chunk.  When you have finished 
  1231.  adding chars, because you got to the end of the symbol, you know how long the 
  1232.  chars are, and you can create a new object. Mostly the chars will not burst 
  1233.  over the highest address of the chunk, because you would typically expect a 
  1234.  chunk to be (say) 100 times as long as an average object. 
  1235.  
  1236.  In case that isn't clear, when we have enough chars to make up the object, 
  1237.  they are already contiguous in the chunk (guaranteed) so we just point to it 
  1238.  where it lies.  No moving of chars is needed and this is the second win: 
  1239.  potentially long strings need never be explicitly shuffled. Once an object is 
  1240.  formed, it does not change its address during its lifetime. 
  1241.  
  1242.  When the chars burst over a chunk boundary, we allocate a larger chunk, and 
  1243.  then copy the partly formed object from the end of the old chunk to the 
  1244.  beginning of the new larger chunk.  We then carry on accreting characters to 
  1245.  the end of the object as we normally would. 
  1246.  
  1247.  A special version of grow is provided to add a single char at a time to a 
  1248.  growing object. 
  1249.  
  1250.  Summary: 
  1251.  
  1252.      We allocate large chunks. 
  1253.  
  1254.      We carve out one object at a time from the current chunk. 
  1255.  
  1256.      Once carved, an object never moves. 
  1257.  
  1258.      We are free to append data of any size to the currently growing object. 
  1259.  
  1260.      Exactly one object is growing in an obstack at any one time. 
  1261.  
  1262.      You can run one obstack per control block. 
  1263.  
  1264.      You may have as many control blocks as you dare. 
  1265.  
  1266.      Because of the way we do it, you can `unwind' a obstack back to a 
  1267.       previous state. (You may remove objects much as you would with a stack.) 
  1268.  
  1269.  The obstack data structure is used in many places in the GNU C++ compiler. 
  1270.  
  1271.  Differences from the the GNU C version 
  1272.  
  1273.    1. The obvious differences stemming from the use of classes and inline 
  1274.       functions instead of structs and macros. The C init and begin macros are 
  1275.       replaced by constructors. 
  1276.  
  1277.    2. Overloaded function names are used for grow (and others), rather than the 
  1278.       C grow, grow0, etc. 
  1279.  
  1280.    3. All dynamic allocation uses the the built-in new operator. This restricts 
  1281.       flexibility by a little, but maintains compatibility with usual C++ 
  1282.       conventions. 
  1283.  
  1284.    4. There are now two versions of finish: 
  1285.  
  1286.         a. finish() behaves like the C version. 
  1287.  
  1288.         b. finish(char terminator) adds terminator, and then calls finish(). 
  1289.            This enables the normal invocation of finish(0) to wrap up a string 
  1290.            being grown character-by-character. 
  1291.  
  1292.    5. There are special versions of grow(const char* s) and copy(const char* s) 
  1293.       that add the null-terminated string s after computing its length. 
  1294.  
  1295.    6. The shrink and contains functions are provided. 
  1296.  
  1297.  
  1298. ΓòÉΓòÉΓòÉ 18. The AllocRing class ΓòÉΓòÉΓòÉ
  1299.  
  1300. An AllocRing is a bounded ring (circular list), each of whose elements contains 
  1301. a pointer to some space allocated via new char[some_size]. The entries are used 
  1302. cyclicly.  The size, n, of the ring is fixed at construction. After that, every 
  1303. nth use of the ring will reuse (or reallocate) the same space. AllocRings are 
  1304. needed in order to temporarily hold chunks of space that are needed 
  1305. transiently, but across constructor-destructor scopes. They mainly useful for 
  1306. storing strings containing formatted characters to print across various 
  1307. functions and coercions. These strings are needed across routines, so may not 
  1308. be deleted in any one of them, but should be recovered at some point. In other 
  1309. words, an AllocRing is an extremely simple minded garbage collection mechanism. 
  1310. The GNU C++ library used to use one AllocRing for such formatting purposes, but 
  1311. it is being phased out, and is now only used by obsolete functions. These days, 
  1312. AllocRings are probably not very useful. 
  1313.  
  1314. Support includes: 
  1315.  
  1316.  AllocRing a(int n) 
  1317.            constructs an Alloc ring with n entries, all null. 
  1318.  
  1319.  void* mem = a.alloc(sz) 
  1320.            moves the ring pointer to the next entry, and reuses the space if 
  1321.            their is enough, also allocates space via new char[sz]. 
  1322.  
  1323.  int present = a.contains(void* ptr) 
  1324.            returns true if ptr is held in one of the ring entries. 
  1325.  
  1326.  a.clear() 
  1327.            deletes all space pointed to in any entry. This is called 
  1328.            automatically upon destruction. 
  1329.  
  1330.  a.free(void* ptr) 
  1331.            If ptr is one of the entries, calls delete of the pointer, and 
  1332.            resets to entry pointer to null. 
  1333.  
  1334.  
  1335. ΓòÉΓòÉΓòÉ 19. The String class ΓòÉΓòÉΓòÉ
  1336.  
  1337. The String class is designed to extend GNU C++ to support string processing 
  1338. capabilities similar to those in languages like Awk.  The class provides 
  1339. facilities that ought to be convenient and efficient enough to be useful 
  1340. replacements for char* based processing via the C string library (i.e., strcpy, 
  1341. strcmp, etc.) in many applications. Many details about String representations 
  1342. are described in the Representation section. 
  1343.  
  1344. A separate SubString class supports substring extraction and modification 
  1345. operations. This is implemented in a way that user programs never directly 
  1346. construct or represent substrings, which are only used indirectly via String 
  1347. operations. 
  1348.  
  1349. Another separate class, Regex is also used indirectly via String operations in 
  1350. support of regular expression searching, matching, and the like.  The Regex 
  1351. class is based entirely on the GNU Emacs regex functions. See Syntax of Regular 
  1352. Expressions, for a full explanation of regular expression syntax.  (For 
  1353. implementation details, see the internal documentation in files `regex.h' and 
  1354. `regex.c'.) 
  1355.  
  1356.  
  1357. ΓòÉΓòÉΓòÉ 19.1. Constructors ΓòÉΓòÉΓòÉ
  1358.  
  1359. Strings are initialized and assigned as in the following examples: 
  1360.  
  1361.  String x;  String y = 0; String z = ""; 
  1362.            Set x, y, and z to the nil string. Note that either 0 or "" may 
  1363.            always be used to refer to the nil string. 
  1364.  
  1365.  String x = "Hello"; String y("Hello"); 
  1366.            Set x and y to a copy of the string "Hello". 
  1367.  
  1368.  String x = 'A'; String y('A'); 
  1369.            Set x and y to the string value "A" 
  1370.  
  1371.  String u = x; String v(x); 
  1372.            Set u and v to the same string as String x 
  1373.  
  1374.  String u = x.at(1,4); String v(x.at(1,4)); 
  1375.            Set u and v to the length 4 substring of x starting at position 1 
  1376.            (counting indexes from 0). 
  1377.  
  1378.  String x("abc", 2); 
  1379.            Sets x to "ab", i.e., the first 2 characters of "abc". 
  1380.  
  1381.  String x = dec(20); 
  1382.            Sets x to "20". As here, Strings may be initialized or assigned the 
  1383.            results of any char* function. 
  1384.  
  1385.  There are no directly accessible forms for declaring SubString variables. 
  1386.  
  1387.  The declaration Regex r("[a-zA-Z_][a-zA-Z0-9_]*"); creates a compiled regular 
  1388.  expression suitable for use in String operations described below. (In this 
  1389.  case, one that matches any C++ identifier). The first argument may also be a 
  1390.  String. Be careful in distinguishing the role of backslashes in quoted GNU C++ 
  1391.  char* constants versus those in Regexes. For example, a Regex that matches 
  1392.  either one or more tabs or all strings beginning with "ba" and ending with any 
  1393.  number of occurrences of "na" could be declared as Regex r = 
  1394.  "\\(\t+\\)\\|\\(ba\\(na\\)*\\)" Note that only one backslash is needed to 
  1395.  signify the tab, but two are needed for the parenthesization and virgule, 
  1396.  since the GNU C++ lexical analyzer decodes and strips backslashes before they 
  1397.  are seen by Regex. 
  1398.  
  1399.  There are three additional optional arguments to the Regex constructor that 
  1400.  are less commonly useful: 
  1401.  
  1402.  fast (default 0) 
  1403.            fast may be set to true (1) if the Regex should be "fast-compiled". 
  1404.            This causes an additional compilation step that is generally 
  1405.            worthwhile if the Regex will be used many times. 
  1406.  
  1407.  bufsize (default max(40, length of the string)) 
  1408.            This is an estimate of the size of the internal compiled expression. 
  1409.            Set it to a larger value if you know that the expression will 
  1410.            require a lot of space. If you do not know, do not worry: realloc is 
  1411.            used if necessary. 
  1412.  
  1413.  transtable (default none == 0) 
  1414.            The address of a byte translation table (a char[256]) that 
  1415.            translates each character before matching. 
  1416.  
  1417.  As a convenience, several Regexes are predefined and usable in any program. 
  1418.  Here are their declarations from `String.h'. 
  1419.  
  1420.   extern Regex RXwhite;      // = "[ \n\t]+"
  1421.   extern Regex RXint;        // = "-?[0-9]+"
  1422.   extern Regex RXdouble;     // = "-?\\(\\([0-9]+\\.[0-9]*\\)\\|
  1423.                              //    \\([0-9]+\\)\\|
  1424.                              //    \\(\\.[0-9]+\\)\\)
  1425.                              //    \\([eE][---+]?[0-9]+\\)?"
  1426.   extern Regex RXalpha;      // = "[A-Za-z]+"
  1427.   extern Regex RXlowercase;  // = "[a-z]+"
  1428.   extern Regex RXuppercase;  // = "[A-Z]+"
  1429.   extern Regex RXalphanum;   // = "[0-9A-Za-z]+"
  1430.   extern Regex RXidentifier; // = "[A-Za-z_][A-Za-z0-9_]*"
  1431.  
  1432.  
  1433. ΓòÉΓòÉΓòÉ 19.2. Examples ΓòÉΓòÉΓòÉ
  1434.  
  1435. Most String class capabilities are best shown via example. The examples below 
  1436. use the following declarations. 
  1437.  
  1438.     String x = "Hello";
  1439.     String y = "world";
  1440.     String n = "123";
  1441.     String z;
  1442.     char*  s = ",";
  1443.     String lft, mid, rgt;
  1444.     Regex  r = "e[a-z]*o";
  1445.     Regex  r2("/[a-z]*/");
  1446.     char   c;
  1447.     int    i, pos, len;
  1448.     double f;
  1449.     String words[10];
  1450.     words[0] = "a";
  1451.     words[1] = "b";
  1452.     words[2] = "c";
  1453.  
  1454.  
  1455. ΓòÉΓòÉΓòÉ 19.3. Comparing, Searching and Matching ΓòÉΓòÉΓòÉ
  1456.  
  1457. The usual lexicographic relational operators (==, !=, <, <=, >, >=) are 
  1458. defined. A functional form compare(String, String) is also provided, as is 
  1459. fcompare(String, String), which compares Strings without regard for upper vs. 
  1460. lower case. 
  1461.  
  1462. All other matching and searching operations are based on some form of the 
  1463. (non-public) match and search functions.  match and search differ in that match 
  1464. attempts to match only at the given starting position, while search starts at 
  1465. the position, and then proceeds left or right looking for a match.  As seen in 
  1466. the following examples, the second optional startpos argument to functions 
  1467. using match and search specifies the starting position of the search: If 
  1468. non-negative, it results in a left-to-right search starting at position 
  1469. startpos, and if negative, a right-to-left search starting at position 
  1470. x.length() + startpos. In all cases, the index returned is that of the 
  1471. beginning of the match, or -1 if there is no match. 
  1472.  
  1473. Three String functions serve as front ends to search and match. index performs 
  1474. a search, returning the index, matches performs a match, returning nonzero 
  1475. (actually, the length of the match) on success, and contains is a boolean 
  1476. function performing either a search or match, depending on whether an index 
  1477. argument is provided: 
  1478.  
  1479.  x.index("lo") 
  1480.            returns the zero-based index of the leftmost occurrence of substring 
  1481.            "lo" (3, in this case).  The argument may be a String, SubString, 
  1482.            char, char*, or Regex. 
  1483.  
  1484.  x.index("l", 2) 
  1485.            returns the index of the first of the leftmost occurrence of "l" 
  1486.            found starting the search at position x[2], or 2 in this case. 
  1487.  
  1488.  x.index("l", -1) 
  1489.            returns the index of the rightmost occurrence of "l", or 3 here. 
  1490.  
  1491.  x.index("l", -3) 
  1492.            returns the index of the rightmost occurrence of "l" found by 
  1493.            starting the search at the 3rd to the last position of x, returning 
  1494.            2 in this case. 
  1495.  
  1496.  pos = r.search("leo", 3, len, 0) 
  1497.            returns the index of r in the char* string of length 3, starting at 
  1498.            position 0, also placing the  length of the match in reference 
  1499.            parameter len. 
  1500.  
  1501.  x.contains("He") 
  1502.            returns nonzero if the String x contains the substring "He". The 
  1503.            argument may be a String, SubString, char, char*, or Regex. 
  1504.  
  1505.  x.contains("el", 1) 
  1506.            returns nonzero if x contains the substring "el" at position 1. As 
  1507.            in this example, the second argument to contains, if present, means 
  1508.            to match the substring only at that position, and not to search 
  1509.            elsewhere in the string. 
  1510.  
  1511.  x.contains(RXwhite); 
  1512.            returns nonzero if x contains any whitespace (space, tab, or 
  1513.            newline). Recall that RXwhite is a global whitespace Regex. 
  1514.  
  1515.  x.matches("lo", 3) 
  1516.            returns nonzero if x starting at position 3 exactly matches "lo", 
  1517.            with no trailing characters (as it does in this example). 
  1518.  
  1519.  x.matches(r) 
  1520.            returns nonzero if String x as a whole matches Regex r. 
  1521.  
  1522.  int f = x.freq("l") 
  1523.            returns the number of distinct, nonoverlapping matches to the 
  1524.            argument (2 in this case). 
  1525.  
  1526.  
  1527. ΓòÉΓòÉΓòÉ 19.4. Substring extraction ΓòÉΓòÉΓòÉ
  1528.  
  1529. Substrings may be extracted via the at, before, through, from, and after 
  1530. functions. These behave as either lvalues or rvalues. 
  1531.  
  1532.  z = x.at(2, 3) 
  1533.            sets String z to be equal to the length 3 substring of String x 
  1534.            starting at zero-based position 2, setting z to "llo" in this case. 
  1535.            A nil String is returned if the arguments don't make sense. 
  1536.  
  1537.  x.at(2, 2) = "r" 
  1538.            Sets what was in positions 2 to 3 of x to "r", setting x to "Hero" 
  1539.            in this case. As indicated here, SubString assignments may be of 
  1540.            different lengths. 
  1541.  
  1542.  x.at("He") = "je"; 
  1543.            x("He") is the substring of x that matches the first occurrence of 
  1544.            it's argument. The substitution sets x to "jello". If "He" did not 
  1545.            occur, the substring would be nil, and the assignment would have no 
  1546.            effect. 
  1547.  
  1548.  x.at("l", -1) = "i"; 
  1549.            replaces the rightmost occurrence of "l" with "i", setting x to 
  1550.            "Helio". 
  1551.  
  1552.  z = x.at(r) 
  1553.            sets String z to the first match in x of Regex r, or "ello" in this 
  1554.            case. A nil String is returned if there is no match. 
  1555.  
  1556.  z = x.before("o") 
  1557.            sets z to the part of x to the left of the first occurrence of "o", 
  1558.            or "Hell" in this case. The argument may also be a String, 
  1559.            SubString, or Regex.  (If there is no match, z is set to "".) 
  1560.  
  1561.  x.before("ll") = "Bri"; 
  1562.            sets the part of x to the left of "ll" to "Bri", setting x to 
  1563.            "Brillo". 
  1564.  
  1565.  z = x.before(2) 
  1566.            sets z to the part of x to the left of x[2], or "He" in this case. 
  1567.  
  1568.  z = x.after("Hel") 
  1569.            sets z to the part of x to the right of "Hel", or "lo" in this case. 
  1570.  
  1571.  z = x.through("el") 
  1572.            sets z to the part of x up and including "el", or "Hel" in this 
  1573.            case. 
  1574.  
  1575.  z = x.from("el") 
  1576.            sets z to the part of x from "el" to the end, or "ello" in this 
  1577.            case. 
  1578.  
  1579.  x.after("Hel") = "p"; 
  1580.            sets x to "Help"; 
  1581.  
  1582.  z = x.after(3) 
  1583.            sets z to the part of x to the right of x[3] or "o" in this case. 
  1584.  
  1585.  z = "  ab c"; z = z.after(RXwhite) 
  1586.            sets z to the part of its old string to the right of the first group 
  1587.            of whitespace, setting z to "ab c"; Use gsub(below) to strip out 
  1588.            multiple occurrences of whitespace or any pattern. 
  1589.  
  1590.  x[0] = 'J'; 
  1591.            sets the first element of x to 'J'. x[i] returns a reference to the 
  1592.            ith element of x, or triggers an error if i is out of range. 
  1593.  
  1594.  common_prefix(x, "Help") 
  1595.            returns the String containing the common prefix of the two Strings 
  1596.            or "Hel" in this case. 
  1597.  
  1598.  common_suffix(x, "to") 
  1599.            returns the String containing the common suffix of the two Strings 
  1600.            or "o" in this case. 
  1601.  
  1602.  
  1603. ΓòÉΓòÉΓòÉ 19.5. Concatenation ΓòÉΓòÉΓòÉ
  1604.  
  1605.  z = x + s + ' ' + y.at("w") + y.after("w") + "."; 
  1606.            sets z to "Hello, world." 
  1607.  
  1608.  x += y; 
  1609.            sets x to "Helloworld" 
  1610.  
  1611.  cat(x, y, z) 
  1612.            A faster way to say z = x + y. 
  1613.  
  1614.  cat(z, y, x, x) 
  1615.            Double concatenation; A faster way to say x = z + y + x. 
  1616.  
  1617.  y.prepend(x); 
  1618.            A faster way to say y = x + y. 
  1619.  
  1620.  z = replicate(x, 3); 
  1621.            sets z to "HelloHelloHello". 
  1622.  
  1623.  z = join(words, 3, "/") 
  1624.            sets z to the concatenation of the first 3 Strings in String array 
  1625.            words, each separated by "/", setting z to "a/b/c" in this case. 
  1626.            The last argument may be "" or 0, indicating no separation. 
  1627.  
  1628.  
  1629. ΓòÉΓòÉΓòÉ 19.6. Other manipulations ΓòÉΓòÉΓòÉ
  1630.  
  1631.  z = "this string has five words"; i = split(z, words, 10, RXwhite); 
  1632.            sets up to 10 elements of String array words to the parts of z 
  1633.            separated by whitespace, and returns the number of parts actually 
  1634.            encountered (5 in this case). Here, words[0] = "this", words[1] = 
  1635.            "string", etc.  The last argument may be any of the usual. If there 
  1636.            is no match, all of z ends up in words[0]. The words array is not 
  1637.            dynamically created by split. 
  1638.  
  1639.  int nmatches x.gsub("l","ll") 
  1640.            substitutes all original occurrences of "l" with "ll", setting x to 
  1641.            "Hellllo". The first argument may be any of the usual, including 
  1642.            Regex.  If the second argument is "" or 0, all occurrences are 
  1643.            deleted. gsub returns the number of matches that were replaced. 
  1644.  
  1645.  z = x + y;  z.del("loworl"); 
  1646.            deletes the leftmost occurrence of "loworl" in z, setting z to 
  1647.            "Held". 
  1648.  
  1649.  z = reverse(x) 
  1650.            sets z to the reverse of x, or "olleH". 
  1651.  
  1652.  z = upcase(x) 
  1653.            sets z to x, with all letters set to uppercase, setting z to "HELLO" 
  1654.  
  1655.  z = downcase(x) 
  1656.            sets z to x, with all letters set to lowercase, setting z to "hello" 
  1657.  
  1658.  z = capitalize(x) 
  1659.            sets z to x, with the first letter of each word set to uppercase, 
  1660.            and all others to lowercase, setting z to "Hello" 
  1661.  
  1662.  x.reverse(), x.upcase(), x.downcase(), x.capitalize() 
  1663.            in-place, self-modifying versions of the above. 
  1664.  
  1665.  
  1666. ΓòÉΓòÉΓòÉ 19.7. Reading, Writing and Conversion ΓòÉΓòÉΓòÉ
  1667.  
  1668.  cout << x 
  1669.            writes out x. 
  1670.  
  1671.  cout << x.at(2, 3) 
  1672.            writes out the substring "llo". 
  1673.  
  1674.  cin >> x 
  1675.            reads a whitespace-bounded string into x. 
  1676.  
  1677.  x.length() 
  1678.            returns the length of String x (5, in this case). 
  1679.  
  1680.  s = (const char*)x 
  1681.            can be used to extract the char* char array. This coercion is useful 
  1682.            for sending a String as an argument to any function expecting a 
  1683.            const char* argument (like atoi, and File::open). This operator must 
  1684.            be used with care, since the conversion returns a pointer to String 
  1685.            internals without copying the characters: The resulting (char*) is 
  1686.            only valid until the next String operation,  and you must not modify 
  1687.            it. (The conversion is defined to return a const value so that GNU 
  1688.            C++ will produce warning and/or error messages if changes are 
  1689.            attempted.) 
  1690.  
  1691.  
  1692. ΓòÉΓòÉΓòÉ 20. The Integer class. ΓòÉΓòÉΓòÉ
  1693.  
  1694. The Integer class provides multiple precision integer arithmetic facilities. 
  1695. Some representation details are discussed in the Representation section. 
  1696.  
  1697. Integers may be up to b * ((1 << b) - 1) bits long, where b is the number of 
  1698. bits per short (typically 1048560 bits when b = 16).  The implementation 
  1699. assumes that a long is at least twice as long as a short. This assumption hides 
  1700. beneath almost all primitive operations, and would be very difficult to change. 
  1701. It also relies on correct behavior of unsigned arithmetic operations. 
  1702.  
  1703. Some of the arithmetic algorithms are very loosely based on those provided in 
  1704. the MIT Scheme `bignum.c' release, which is Copyright (c) 1987 Massachusetts 
  1705. Institute of Technology. Their use here falls within the provisions described 
  1706. in the Scheme release. 
  1707.  
  1708. Integers may be constructed in the following ways: 
  1709.  
  1710.  Integer x; 
  1711.            Declares an uninitialized Integer. 
  1712.  
  1713.  Integer x = 2; Integer y(2); 
  1714.            Set x and y to the Integer value 2; 
  1715.  
  1716.  Integer u(x); Integer v = x; 
  1717.            Set u and v to the same value as x. 
  1718.  
  1719.  Method: long Integer::as_long() const 
  1720.  Used to coerce an Integer back into longs via the long coercion operator. If 
  1721.  the Integer cannot fit into a long, this returns MINLONG or MAXLONG (depending 
  1722.  on the sign) where MINLONG is the most negative, and MAXLONG is the most 
  1723.  positive representable long. 
  1724.  
  1725.  Method: int Integer::fits_in_long() const 
  1726.  Returns true iff the Integer is < MAXLONG and > MINLONG. 
  1727.  
  1728.  Method: double Integer::as_double() const 
  1729.  Coerce the Integer to a double, with potential loss of precision. +/-HUGE is 
  1730.  returned if the Integer cannot fit into a double. 
  1731.  
  1732.  Method: int Integer::fits_in_double() const 
  1733.  Returns true iff the Integer can fit into a double. 
  1734.  
  1735.  All of the usual arithmetic operators are provided (+, -, *, /, %, +=, ++, -=, 
  1736.  --, *=, /=, %=, ==, !=, <, <=, >, >=).  All operators support special versions 
  1737.  for mixed arguments of Integers and regular C++ longs in order to avoid 
  1738.  useless coercions, as well as to allow automatic promotion of shorts and ints 
  1739.  to longs, so that they may be applied without additional Integer coercion 
  1740.  operators.  The only operators that behave differently than the corresponding 
  1741.  int or long operators are ++ and --.  Because C++ does not distinguish prefix 
  1742.  from postfix application, these are declared as void operators, so that no 
  1743.  confusion can result from applying them as postfix.  Thus, for Integers x and 
  1744.  y, ++x; y = x;  is correct, but y = ++x;  and y = x++;  are not. 
  1745.  
  1746.  Bitwise operators (~, &, |, ^, <<, >>, &=, |=, ^=, <<=, >>=) are also 
  1747.  provided.  However, these operate on sign-magnitude, rather than two's 
  1748.  complement representations. The sign of the result is arbitrarily taken as the 
  1749.  sign of the first argument. For example, Integer(-3) & Integer(5) returns 
  1750.  Integer(-1), not -3, as it would using two's complement. Also, ~, the 
  1751.  complement operator, complements only those bits needed for the 
  1752.  representation.  Bit operators are also provided in the BitSet and BitString 
  1753.  classes. One of these classes should be used instead of Integers when the 
  1754.  results of bit manipulations are not interpreted numerically. 
  1755.  
  1756.  The following utility functions are also provided. (All arguments are Integers 
  1757.  unless otherwise noted). 
  1758.  
  1759.  Function: void divide(const Integer& x, const Integer& y, Integer& q, Integer& 
  1760.  r) 
  1761.  Sets q to the quotient and r to the remainder of x and y. (q and r are 
  1762.  returned by reference). 
  1763.  
  1764.  Function: Integer pow(const Integer& x, const Integer& p) 
  1765.  Returns x raised to the power p. 
  1766.  
  1767.  Function: Integer Ipow(long x, long p) 
  1768.  Returns x raised to the power p. 
  1769.  
  1770.  Function: Integer gcd(const Integer& x, const Integer& p) 
  1771.  Returns the greatest common divisor of x and y. 
  1772.  
  1773.  Function: Integer lcm(const Integer& x, const Integer& p) 
  1774.  Returns the least common multiple of x and y. 
  1775.  
  1776.  Function: Integer abs(const Integer& x 
  1777.  Returns the absolute value of x. 
  1778.  
  1779.  Method: void Integer::negate() 
  1780.  Negates this in place. 
  1781.  
  1782.  Integer sqr(x) 
  1783.            returns x * x; 
  1784.  
  1785.  Integer sqrt(x) 
  1786.            returns the floor of the  square root of x. 
  1787.  
  1788.  long lg(x); 
  1789.            returns the floor of the base 2 logarithm of abs(x) 
  1790.  
  1791.  int sign(x) 
  1792.            returns -1 if x is negative, 0 if zero, else +1. Using if (sign(x) 
  1793.            == 0) is a generally faster method of testing for zero than using 
  1794.            relational operators. 
  1795.  
  1796.  int even(x) 
  1797.            returns true if x is an even number 
  1798.  
  1799.  int odd(x) 
  1800.            returns true if x is an odd number. 
  1801.  
  1802.  void setbit(Integer& x, long b) 
  1803.            sets the b'th bit (counting right-to-left from zero) of x to 1. 
  1804.  
  1805.  void clearbit(Integer& x, long b) 
  1806.            sets the b'th bit of x to 0. 
  1807.  
  1808.  int testbit(Integer x, long b) 
  1809.            returns true if the b'th bit of x is 1. 
  1810.  
  1811.  Integer atoI(char* asciinumber, int base = 10); 
  1812.            converts the base base char* string into its Integer form. 
  1813.  
  1814.  void Integer::printon(ostream& s, int base = 10, int width = 0); 
  1815.            prints the ascii string value of (*this) as a base base number, in 
  1816.            field width at least width. 
  1817.  
  1818.  ostream << x; 
  1819.            prints x in base ten format. 
  1820.  
  1821.  istream >> x; 
  1822.            reads x as a base ten number. 
  1823.  
  1824.  int compare(Integer x, Integer y) 
  1825.            returns a negative number if x<y, zero if x==y, or positive if x>y. 
  1826.  
  1827.  int ucompare(Integer x, Integer y) 
  1828.            like compare, but performs unsigned comparison. 
  1829.  
  1830.  add(x, y, z) 
  1831.            A faster way to say z = x + y. 
  1832.  
  1833.  sub(x, y, z) 
  1834.            A faster way to say z = x - y. 
  1835.  
  1836.  mul(x, y, z) 
  1837.            A faster way to say z = x * y. 
  1838.  
  1839.  div(x, y, z) 
  1840.            A faster way to say z = x / y. 
  1841.  
  1842.  mod(x, y, z) 
  1843.            A faster way to say z = x % y. 
  1844.  
  1845.  and(x, y, z) 
  1846.            A faster way to say z = x & y. 
  1847.  
  1848.  or(x, y, z) 
  1849.            A faster way to say z = x | y. 
  1850.  
  1851.  xor(x, y, z) 
  1852.            A faster way to say z = x ^ y. 
  1853.  
  1854.  lshift(x, y, z) 
  1855.            A faster way to say z = x << y. 
  1856.  
  1857.  rshift(x, y, z) 
  1858.            A faster way to say z = x >> y. 
  1859.  
  1860.  pow(x, y, z) 
  1861.            A faster way to say z = pow(x, y). 
  1862.  
  1863.  complement(x, z) 
  1864.            A faster way to say z = ~x. 
  1865.  
  1866.  negate(x, z) 
  1867.            A faster way to say z = -x. 
  1868.  
  1869.  
  1870. ΓòÉΓòÉΓòÉ 21. The Rational Class ΓòÉΓòÉΓòÉ
  1871.  
  1872. Class Rational provides multiple precision rational number arithmetic. All 
  1873. rationals are maintained in simplest form (i.e., with the numerator and 
  1874. denominator relatively prime, and with the denominator strictly positive). 
  1875. Rational arithmetic and relational operators are provided (+, -, *, /, +=, -=, 
  1876. *=, /=, ==, !=, <, <=, >, >=). Operations resulting in a rational number with 
  1877. zero denominator trigger an exception. 
  1878.  
  1879. Rationals may be constructed and used in the following ways: 
  1880.  
  1881.  Rational x; 
  1882.            Declares an uninitialized Rational. 
  1883.  
  1884.  Rational x = 2; Rational y(2); 
  1885.            Set x and y to the Rational value 2/1; 
  1886.  
  1887.  Rational x(2, 3); 
  1888.            Sets x to the Rational value 2/3; 
  1889.  
  1890.  Rational x = 1.2; 
  1891.            Sets x to a Rational value close to 1.2. Any double precision value 
  1892.            may be used to construct a Rational. The Rational will possess 
  1893.            exactly as much precision as the double. Double values that do not 
  1894.            have precise floating point equivalents (like 1.2) produce similarly 
  1895.            imprecise rational values. 
  1896.  
  1897.  Rational x(Integer(123), Integer(4567)); 
  1898.            Sets x to the Rational value 123/4567. 
  1899.  
  1900.  Rational u(x); Rational v = x; 
  1901.            Set u and v to the same value as x. 
  1902.  
  1903.  double(Rational x) 
  1904.            A Rational may be coerced to a double with potential loss of 
  1905.            precision. +/-HUGE is returned if it will not fit. 
  1906.  
  1907.  Rational abs(x) 
  1908.            returns the absolute value of x. 
  1909.  
  1910.  void x.negate() 
  1911.            negates x. 
  1912.  
  1913.  void x.invert() 
  1914.            sets x to 1/x. 
  1915.  
  1916.  int sign(x) 
  1917.            returns 0 if x is zero, 1 if positive, and -1 if negative. 
  1918.  
  1919.  Rational sqr(x) 
  1920.            returns x * x. 
  1921.  
  1922.  Rational pow(x, Integer y) 
  1923.            returns x to the y power. 
  1924.  
  1925.  Integer x.numerator() 
  1926.            returns the numerator. 
  1927.  
  1928.  Integer x.denominator() 
  1929.            returns the denominator. 
  1930.  
  1931.  Integer floor(x) 
  1932.            returns the greatest Integer less than x. 
  1933.  
  1934.  Integer ceil(x) 
  1935.            returns the least Integer greater than x. 
  1936.  
  1937.  Integer trunc(x) 
  1938.            returns the Integer part of x. 
  1939.  
  1940.  Integer round(x) 
  1941.            returns the nearest Integer to x. 
  1942.  
  1943.  int compare(x, y) 
  1944.            returns a negative, zero, or positive number signifying whether x is 
  1945.            less than, equal to, or greater than y. 
  1946.  
  1947.  ostream << x; 
  1948.            prints x in the form num/den, or just num if the denominator is one. 
  1949.  
  1950.  istream >> x; 
  1951.            reads x in the form num/den, or just num in which case the 
  1952.            denominator is set to one. 
  1953.  
  1954.  add(x, y, z) 
  1955.            A faster way to say z = x + y. 
  1956.  
  1957.  sub(x, y, z) 
  1958.            A faster way to say z = x - y. 
  1959.  
  1960.  mul(x, y, z) 
  1961.            A faster way to say z = x * y. 
  1962.  
  1963.  div(x, y, z) 
  1964.            A faster way to say z = x / y. 
  1965.  
  1966.  pow(x, y, z) 
  1967.            A faster way to say z = pow(x, y). 
  1968.  
  1969.  negate(x, z) 
  1970.            A faster way to say z = -x. 
  1971.  
  1972.  
  1973. ΓòÉΓòÉΓòÉ 22. The Complex class. ΓòÉΓòÉΓòÉ
  1974.  
  1975. Class Complex is implemented in a way similar to that described by Stroustrup. 
  1976. In keeping with libg++ conventions, the class is named Complex, not complex. 
  1977. Complex arithmetic and relational operators are provided (+, -, *, /, +=, -=, 
  1978. *=, /=, ==, !=). Attempted division by (0, 0) triggers an exception. 
  1979.  
  1980. Complex numbers may be constructed and used in the following ways: 
  1981.  
  1982.  Complex x; 
  1983.            Declares an uninitialized Complex. 
  1984.  
  1985.  Complex x = 2; Complex y(2.0); 
  1986.            Set x and y to the Complex value (2.0, 0.0); 
  1987.  
  1988.  Complex x(2, 3); 
  1989.            Sets x to the Complex value (2, 3); 
  1990.  
  1991.  Complex u(x); Complex v = x; 
  1992.            Set u and v to the same value as x. 
  1993.  
  1994.  double real(Complex& x); 
  1995.            returns the real part of x. 
  1996.  
  1997.  double imag(Complex& x); 
  1998.            returns the imaginary part of x. 
  1999.  
  2000.  double abs(Complex& x); 
  2001.            returns the magnitude of x. 
  2002.  
  2003.  double norm(Complex& x); 
  2004.            returns the square of the magnitude of x. 
  2005.  
  2006.  double arg(Complex& x); 
  2007.            returns the argument (amplitude) of x. 
  2008.  
  2009.  Complex polar(double r, double t = 0.0); 
  2010.            returns a Complex with abs of r and arg of t. 
  2011.  
  2012.  Complex conj(Complex& x); 
  2013.            returns the complex conjugate of x. 
  2014.  
  2015.  Complex cos(Complex& x); 
  2016.            returns the complex cosine of x. 
  2017.  
  2018.  Complex sin(Complex& x); 
  2019.            returns the complex sine of x. 
  2020.  
  2021.  Complex cosh(Complex& x); 
  2022.            returns the complex hyperbolic cosine of x. 
  2023.  
  2024.  Complex sinh(Complex& x); 
  2025.            returns the complex hyperbolic sine of x. 
  2026.  
  2027.  Complex exp(Complex& x); 
  2028.            returns the exponential of x. 
  2029.  
  2030.  Complex log(Complex& x); 
  2031.            returns the natural log of x. 
  2032.  
  2033.  Complex pow(Complex& x, long p); 
  2034.            returns x raised to the p power. 
  2035.  
  2036.  Complex pow(Complex& x, Complex& p); 
  2037.            returns x raised to the p power. 
  2038.  
  2039.  Complex sqrt(Complex& x); 
  2040.            returns the square root of x. 
  2041.  
  2042.  ostream << x; 
  2043.            prints x in the form (re, im). 
  2044.  
  2045.  istream >> x; 
  2046.            reads x in the form (re, im), or just (re) or re in which case the 
  2047.            imaginary part is set to zero. 
  2048.  
  2049.  
  2050. ΓòÉΓòÉΓòÉ 23. Fixed precision numbers ΓòÉΓòÉΓòÉ
  2051.  
  2052. Classes Fix16, Fix24, Fix32, and Fix48 support operations on 16, 24, 32, or 48 
  2053. bit quantities that are considered as real numbers in the range [-1, +1).  Such 
  2054. numbers are often encountered in digital signal processing applications. The 
  2055. classes may be be used in isolation or together.  Class Fix32 operations are 
  2056. entirely self-contained.  Class Fix16 operations are self-contained except that 
  2057. the multiplication operation Fix16 * Fix16 returns a Fix32. Fix24 and Fix48 are 
  2058. similarly related. 
  2059.  
  2060. The standard arithmetic and relational operations are supported (=, +, -, *, /, 
  2061. <<, >>, +=, -=, *=, /=, <<=, >>=, ==, !=, <, <=, >, >=). All operations include 
  2062. provisions for special handling in cases where the result exceeds +/- 1.0. 
  2063. There are two cases that may be handled separately: ``overflow'' where the 
  2064. results of addition and subtraction operations go out of range, and all other 
  2065. ``range errors'' in which resulting values go off-scale (as with division 
  2066. operations, and assignment or initialization with off-scale values). In signal 
  2067. processing applications, it is often useful to handle these two cases 
  2068. differently. Handlers take one argument, a reference to the integer mantissa of 
  2069. the offending value, which may then be manipulated.  In cases of overflow, this 
  2070. value is the result of the (integer) arithmetic computation on the mantissa; in 
  2071. others it is a fully saturated (i.e., most positive or most negative) value. 
  2072. Handling may be reset to any of several provided functions or any other 
  2073. user-defined function via set_overflow_handler and set_range_error_handler. The 
  2074. provided functions for Fix16 are as follows (corresponding functions are also 
  2075. supported for the others). 
  2076.  
  2077.  Fix16_overflow_saturate 
  2078.            The default overflow handler. Results are ``saturated'': positive 
  2079.            results are set to the largest representable value (binary 
  2080.            0.111111...), and negative values to -1.0. 
  2081.  
  2082.  Fix16_ignore 
  2083.            Performs no action. For overflow, this will allow addition and 
  2084.            subtraction operations to ``wrap around'' in the same manner as 
  2085.            integer arithmetic, and for saturation, will leave values saturated. 
  2086.  
  2087.  Fix16_overflow_warning_saturate 
  2088.            Prints a warning message on standard error, then saturates the 
  2089.            results. 
  2090.  
  2091.  Fix16_warning 
  2092.            The default range_error handler. Prints a warning message on 
  2093.            standard error; otherwise leaving the argument unmodified. 
  2094.  
  2095.  Fix16_abort 
  2096.            prints an error message on standard error, then aborts execution. 
  2097.  
  2098.  In addition to arithmetic operations, the following are provided: 
  2099.  
  2100.  Fix16 a = 0.5; 
  2101.            Constructs fixed precision objects from double precision values. 
  2102.            Attempting to initialize to a value outside the range invokes the 
  2103.            range_error handler, except, as a convenience, initialization to 1.0 
  2104.            sets the variable to the most positive representable value (binary 
  2105.            0.1111111...) without invoking the handler. 
  2106.  
  2107.  short& mantissa(a); long& mantissa(b); 
  2108.            return a * pow(2, 15) or b * pow(2, 31) as an integer. These are 
  2109.            returned by reference, to enable ``manual'' data manipulation. 
  2110.  
  2111.  double value(a); double value(b); 
  2112.            return a or b as floating point numbers. 
  2113.  
  2114.  
  2115. ΓòÉΓòÉΓòÉ 24. Classes for Bit manipulation ΓòÉΓòÉΓòÉ
  2116.  
  2117. libg++ provides several different classes supporting the use and manipulation 
  2118. of collections of bits in different ways. 
  2119.  
  2120.      Class Integer provides ``integer'' semantics. It supports manipulation of 
  2121.       bits in ways that are often useful when treating bit arrays as numerical 
  2122.       (integer) quantities.  This class is described elsewhere. 
  2123.  
  2124.      Class BitSet provides ``set'' semantics. It supports operations useful 
  2125.       when treating collections of bits as representing potentially infinite 
  2126.       sets of integers. 
  2127.  
  2128.      Class BitSet32 supports fixed-length BitSets holding exactly 32 bits. 
  2129.  
  2130.      Class BitSet256 supports fixed-length BitSets holding exactly 256 bits. 
  2131.  
  2132.      Class BitString provides ``string'' (or ``vector'') semantics. It 
  2133.       supports operations useful when treating collections of bits as strings 
  2134.       of zeros and ones. 
  2135.  
  2136.  These classes also differ in the following ways: 
  2137.  
  2138.      BitSets are logically infinite. Their space is dynamically altered to 
  2139.       adjust to the smallest number of consecutive bits actually required to 
  2140.       represent the sets. Integers also have this property. BitStrings are 
  2141.       logically finite, but their sizes are internally dynamically managed to 
  2142.       maintain proper length. This means that, for example, BitStrings are 
  2143.       concatenatable while BitSets and Integers are not. 
  2144.  
  2145.      BitSet32 and BitSet256 have precisely the same properties as BitSets, 
  2146.       except that they use constant fixed length bit vectors. 
  2147.  
  2148.      While all classes support basic unary and binary operations ~, &, |, ^, 
  2149.       -, the semantics differ. BitSets perform bit operations that precisely 
  2150.       mirror those for infinite sets. For example, complementing an empty 
  2151.       BitSet returns one representing an infinite number of set bits. 
  2152.       Operations on BitStrings and Integers operate only on those bits actually 
  2153.       present in the representation.  For BitStrings and Integers, the the & 
  2154.       operation returns a BitString with a length equal to the minimum length 
  2155.       of the operands, and |, ^ return one with length of the maximum. 
  2156.  
  2157.      Only BitStrings support substring extraction and bit pattern matching. 
  2158.  
  2159.  
  2160. ΓòÉΓòÉΓòÉ 24.1. BitSet ΓòÉΓòÉΓòÉ
  2161.  
  2162. BitSets are objects that contain logically infinite sets of nonnegative 
  2163. integers.  Representational details are discussed in the Representation 
  2164. chapter. Because they are logically infinite, all BitSets possess a trailing, 
  2165. infinitely replicated 0 or 1 bit, called the ``virtual bit'', and indicated via 
  2166. 0* or 1*. 
  2167.  
  2168. BitSet32 and BitSet256 have they same properties, except they are of fixed 
  2169. length, and thus have no virtual bit. 
  2170.  
  2171. BitSets may be constructed as follows: 
  2172.  
  2173.  BitSet a; 
  2174.            declares an empty BitSet. 
  2175.  
  2176.  BitSet a = atoBitSet("001000"); 
  2177.            sets a to the BitSet 0010*, reading left-to-right. The ``0*'' 
  2178.            indicates that the set ends with an infinite number of zero (clear) 
  2179.            bits. 
  2180.  
  2181.  BitSet a = atoBitSet("00101*"); 
  2182.            sets a to the BitSet 00101*, where ``1*'' means that the set ends 
  2183.            with an infinite number of one (set) bits. 
  2184.  
  2185.  BitSet a = longtoBitSet((long)23); 
  2186.            sets a to the BitSet 111010*, the binary representation of decimal 
  2187.            23. 
  2188.  
  2189.  BitSet a = utoBitSet((unsigned)23); 
  2190.            sets a to the BitSet 111010*, the binary representation of decimal 
  2191.            23. 
  2192.  
  2193.  The following functions and operators are provided (Assume the declaration of 
  2194.  BitSets a = 0011010*, b = 101101*, throughout, as examples). 
  2195.  
  2196.  ~a 
  2197.            returns the complement of a, or 1100101* in this case. 
  2198.  
  2199.  a.complement() 
  2200.            sets a to ~a. 
  2201.  
  2202.  a & b; a &= b; 
  2203.            returns a intersected with b, or 0011010*. 
  2204.  
  2205.  a | b; a |= b; 
  2206.            returns a unioned with b, or 1011111*. 
  2207.  
  2208.  a - b; a -= b; 
  2209.            returns the set difference of a and b, or 000010*. 
  2210.  
  2211.  a ^ b; a ^= b; 
  2212.            returns the symmetric difference of a and b, or 1000101*. 
  2213.  
  2214.  a.empty() 
  2215.            returns true if a is an empty set. 
  2216.  
  2217.  a == b; 
  2218.            returns true if a and b contain the same set. 
  2219.  
  2220.  a <= b; 
  2221.            returns true if a is a subset of b. 
  2222.  
  2223.  a < b; 
  2224.            returns true if a is a proper subset of b; 
  2225.  
  2226.  a != b; a >= b; a > b; 
  2227.            are the converses of the above. 
  2228.  
  2229.  a.set(7) 
  2230.            sets the 7th (counting from 0) bit of a, setting a to 001111010* 
  2231.  
  2232.  a.clear(2) 
  2233.            clears the 2nd bit bit of a, setting a to 00011110* 
  2234.  
  2235.  a.clear() 
  2236.            clears all bits of a; 
  2237.  
  2238.  a.set() 
  2239.            sets all bits of a; 
  2240.  
  2241.  a.invert(0) 
  2242.            complements the 0th bit of a, setting a to 10011110* 
  2243.  
  2244.  a.set(0,1) 
  2245.            sets the 0th through 1st bits of a, setting a to 110111110* The 
  2246.            two-argument versions of clear and invert are similar. 
  2247.  
  2248.  a.test(3) 
  2249.            returns true if the 3rd bit of a is set. 
  2250.  
  2251.  a.test(3, 5) 
  2252.            returns true if any of bits 3 through 5 are set. 
  2253.  
  2254.  int i = a[3]; a[3] = 0; 
  2255.            The subscript operator allows bits to be inspected and changed via 
  2256.            standard subscript semantics, using a friend class BitSetBit. The 
  2257.            use of the subscript operator a[i] rather than a.test(i) requires 
  2258.            somewhat greater overhead. 
  2259.  
  2260.  a.first(1) or a.first() 
  2261.            returns the index of the first set bit of a (2 in this case), or -1 
  2262.            if no bits are set. 
  2263.  
  2264.  a.first(0) 
  2265.            returns the index of the first clear bit of a (0 in this case), or 
  2266.            -1 if no bits are clear. 
  2267.  
  2268.  a.next(2, 1) or a.next(2) 
  2269.            returns the index of the next bit after position 2 that is set (3 in 
  2270.            this case) or -1. first and next may be used as iterators, as in for 
  2271.            (int i = a.first(); i >= 0; i = a.next(i)).... 
  2272.  
  2273.  a.last(1) 
  2274.            returns the index of the rightmost set bit, or -1 if there or no set 
  2275.            bits or all set bits. 
  2276.  
  2277.  a.prev(3, 0) 
  2278.            returns the index of the previous clear bit before position 3. 
  2279.  
  2280.  a.count(1) 
  2281.            returns the number of set bits in a, or -1 if there are an infinite 
  2282.            number. 
  2283.  
  2284.  a.virtual_bit() 
  2285.            returns the trailing (infinitely replicated) bit of a. 
  2286.  
  2287.  a = atoBitSet("ababX", 'a', 'b', 'X'); 
  2288.            converts the char* string into a bitset, with 'a' denoting false, 
  2289.            'b' denoting true, and 'X' denoting infinite replication. 
  2290.  
  2291.  a.printon(cout, '-', '.', 0) 
  2292.            prints a to cout represented with '-' for falses, '.' for trues, and 
  2293.            no replication marker. 
  2294.  
  2295.  cout << a 
  2296.            prints a to cout (representing lases by 'f', trues by 't', and using 
  2297.            '*' as the replication marker). 
  2298.  
  2299.  
  2300. ΓòÉΓòÉΓòÉ 24.2. BitString ΓòÉΓòÉΓòÉ
  2301.  
  2302. BitStrings are objects that contain arbitrary-length strings of zeroes and 
  2303. ones. BitStrings possess some features that make them behave like sets, and 
  2304. others that behave as strings. They are useful in applications (such as 
  2305. signature-based algorithms) where both capabilities are needed. 
  2306. Representational details are discussed in the Representation chapter.  Most 
  2307. capabilities are exact analogs of those supported in the BitSet and String 
  2308. classes.  A BitSubString is used with substring operations along the same lines 
  2309. as the String SubString class.  A BitPattern class is used for masked bit 
  2310. pattern searching. 
  2311.  
  2312. Only a default constructor is supported.  The declaration BitString a; 
  2313. initializes a to be an empty BitString. BitStrings may often be initialized via 
  2314. atoBitString and longtoBitString. 
  2315.  
  2316. Set operations (~, complement, &, &=, |, |=, -, ^, ^=) behave just as the 
  2317. BitSet versions, except that there is no ``virtual bit'': complementing 
  2318. complements only those bits in the BitString, and all binary operations across 
  2319. unequal length BitStrings assume a virtual bit of zero. The & operation returns 
  2320. a BitString with a length equal to the minimum length of the operands, and |, ^ 
  2321. return one with length of the maximum. 
  2322.  
  2323. Set-based relational operations (==, !=, <=, <, >=, >) follow the same rules. A 
  2324. string-like lexicographic comparison function, lcompare, tests the 
  2325. lexicographic relation between two BitStrings. For example, lcompare(1100, 
  2326. 0101) returns 1, since the first BitString starts with 1 and the second with 0. 
  2327.  
  2328. Individual bit setting, testing, and iterator operations (set, clear, invert, 
  2329. test, first, next, last, prev) are also like those for BitSets. BitStrings are 
  2330. automatically expanded when setting bits at positions greater than their 
  2331. current length. 
  2332.  
  2333. The string-based capabilities are just as those for class String. BitStrings 
  2334. may be concatenated (+, +=), searched (index, contains, matches), and extracted 
  2335. into BitSubStrings (before, at, after) which may be assigned and otherwise 
  2336. manipulated. Other string-based utility functions (reverse, common_prefix, 
  2337. common_suffix) are also provided. These have the same capabilities and 
  2338. descriptions as those for Strings. 
  2339.  
  2340. String-oriented operations can also be performed with a mask via class 
  2341. BitPattern. BitPatterns consist of two BitStrings, a pattern and a mask. On 
  2342. searching and matching, bits in the pattern that correspond to 0 bits in the 
  2343. mask are ignored. (The mask may be shorter than the pattern, in which case 
  2344. trailing mask bits are assumed to be 0). The pattern and mask are both public 
  2345. variables, and may be individually subjected to other bit operations. 
  2346.  
  2347. Converting to char* and printing ((atoBitString, atoBitPattern, printon, 
  2348. ostream <<)) are also as in BitSets, except that no virtual bit is used, and an 
  2349. 'X' in a BitPattern means that the pattern bit is masked out. 
  2350.  
  2351. The following features are unique to BitStrings. 
  2352.  
  2353. Assume declarations of BitString a = atoBitString("01010110") and b = 
  2354. atoBitSTring("1101"). 
  2355.  
  2356.  a = b + c; 
  2357.            Sets a to the concatenation of b and c; 
  2358.  
  2359.  a = b + 0; a = b + 1; 
  2360.            sets a to b, appended with a zero (one). 
  2361.  
  2362.  a += b; 
  2363.            appends b to a; 
  2364.  
  2365.  a += 0; a += 1; 
  2366.            appends a zero (one) to a. 
  2367.  
  2368.  a << 2; a <<= 2 
  2369.            return a with 2 zeros prepended, setting a to 0001010110. (Note the 
  2370.            necessary confusion of << and >> operators. For consistency with the 
  2371.            integer versions, << shifts low bits to high, even though they are 
  2372.            printed low bits first.) 
  2373.  
  2374.  a >> 3; a >>= 3 
  2375.            return a with the first 3 bits deleted, setting a to 10110. 
  2376.  
  2377.  a.left_trim(0) 
  2378.            deletes all 0 bits on the left of a, setting a to 1010110. 
  2379.  
  2380.  a.right_trim(0) 
  2381.            deletes all trailing 0 bits of a, setting a to 0101011. 
  2382.  
  2383.  cat(x, y, z) 
  2384.            A faster way to say z = x + y. 
  2385.  
  2386.  diff(x, y, z) 
  2387.            A faster way to say z = x - y. 
  2388.  
  2389.  and(x, y, z) 
  2390.            A faster way to say z = x & y. 
  2391.  
  2392.  or(x, y, z) 
  2393.            A faster way to say z = x | y. 
  2394.  
  2395.  xor(x, y, z) 
  2396.            A faster way to say z = x ^ y. 
  2397.  
  2398.  lshift(x, y, z) 
  2399.            A faster way to say z = x << y. 
  2400.  
  2401.  rshift(x, y, z) 
  2402.            A faster way to say z = x >> y. 
  2403.  
  2404.  complement(x, z) 
  2405.            A faster way to say z = ~x. 
  2406.  
  2407.  
  2408. ΓòÉΓòÉΓòÉ 25. Random Number Generators and related classes ΓòÉΓòÉΓòÉ
  2409.  
  2410. The two classes RNG and Random are used together to generate a variety of 
  2411. random number distributions.  A distinction must be made between random number 
  2412. generators, implemented by class RNG, and random number distributions.  A 
  2413. random number generator produces a series of randomly ordered bits.  These bits 
  2414. can be used directly, or cast to other representations, such as a floating 
  2415. point value.  A random number generator should produce a uniform distribution. 
  2416. A random number distribution, on the other hand, uses the randomly generated 
  2417. bits of a generator to produce numbers from a distribution with specific 
  2418. properties.  Each instance of Random uses an instance of class RNG to provide 
  2419. the raw, uniform distribution used to produce the specific distribution. 
  2420. Several instances of Random classes can share the same instance of RNG, or each 
  2421. instance can use its own copy. 
  2422.  
  2423.  
  2424. ΓòÉΓòÉΓòÉ 25.1. RNG ΓòÉΓòÉΓòÉ
  2425.  
  2426. Random distributions are constructed from members of class RNG, the actual 
  2427. random number generators.  The RNG class contains no data; it only serves to 
  2428. define the interface to random number generators.  The RNG::asLong member 
  2429. returns an unsigned long (typically 32 bits) of random bits.  Applications that 
  2430. require a number of random bits can use this directly.  More often, these 
  2431. random bits are transformed to a uniform random number: 
  2432.  
  2433.     //
  2434.     // Return random bits converted to either a float or a double
  2435.     //
  2436.     float asFloat();
  2437.     double asDouble();
  2438. };
  2439.  
  2440. using either asFloat or asDouble.  It is intended that asFloat and asDouble 
  2441. return differing precisions; typically, asDouble will draw two random longwords 
  2442. and transform them into a legal double, while asFloat will draw a single 
  2443. longword and transform it into a legal float.  These members are used by 
  2444. subclasses of the Random class to implement a variety of random number 
  2445. distributions. 
  2446.  
  2447.  
  2448. ΓòÉΓòÉΓòÉ 25.2. ACG ΓòÉΓòÉΓòÉ
  2449.  
  2450. Class ACG is a variant of a Linear Congruential Generator (Algorithm M) 
  2451. described in Knuth, Art of Computer Programming, Vol III.  This result is 
  2452. permuted with a Fibonacci Additive Congruential Generator to get good 
  2453. independence between samples.  This is a very high quality random number 
  2454. generator, although it requires a fair amount of memory for each instance of 
  2455. the generator. 
  2456.  
  2457. The ACG::ACG constructor takes two parameters: the seed and the size.  The seed 
  2458. is any number to be used as an initial seed. The performance of the generator 
  2459. depends on having a distribution of bits through the seed.  If you choose a 
  2460. number in the range of 0 to 31, a seed with more bits is chosen. Other values 
  2461. are deterministically modified to give a better distribution of bits.  This 
  2462. provides a good random number generator while still allowing a sequence to be 
  2463. repeated given the same initial seed. 
  2464.  
  2465. The size parameter determines the size of two tables used in the generator. The 
  2466. first table is used in the Additive Generator; see the algorithm in Knuth for 
  2467. more information. In general, this table is size longwords long. The default 
  2468. value, used in the algorithm in Knuth, gives a table of 220 bytes. The table 
  2469. size affects the period of the generators; smaller values give shorter periods 
  2470. and larger tables give longer periods. The smallest table size is 7 longwords, 
  2471. and the longest is 98 longwords. The size parameter also determines the size of 
  2472. the table used for the Linear Congruential Generator. This value is chosen 
  2473. implicitly based on the size of the Additive Congruential Generator table. It 
  2474. is two powers of two larger than the power of two that is larger than size. 
  2475. For example, if size is 7, the ACG table is 7 longwords and the LCG table is 
  2476. 128 longwords. Thus, the default size (55) requires 55 + 256 longwords, or 1244 
  2477. bytes. The largest table requires 2440 bytes and the smallest table requires 
  2478. 100 bytes.  Applications that require a large number of generators or 
  2479. applications that aren't so fussy about the quality of the generator may elect 
  2480. to use the MLCG generator. 
  2481.  
  2482.  
  2483. ΓòÉΓòÉΓòÉ 25.3. MLCG ΓòÉΓòÉΓòÉ
  2484.  
  2485. The MLCG class implements a Multiplicative Linear Congruential Generator. In 
  2486. particular, it is an implementation of the double MLCG described in ``Efficient 
  2487. and Portable Combined Random Number Generators'' by Pierre L'Ecuyer, appearing 
  2488. in Communications of the ACM, Vol. 31. No. 6. This generator has a fairly long 
  2489. period, and has been statistically analyzed to show that it gives good 
  2490. inter-sample independence. 
  2491.  
  2492. The MLCG::MLCG constructor has two parameters, both of which are seeds for the 
  2493. generator. As in the MLCG generator, both seeds are modified to give a 
  2494. ``better'' distribution of seed digits. Thus, you can safely use values such as 
  2495. `0' or `1' for the seeds. The MLCG generator used much less state than the ACG 
  2496. generator; only two longwords (8 bytes) are needed for each generator. 
  2497.  
  2498.  
  2499. ΓòÉΓòÉΓòÉ 25.4. Random ΓòÉΓòÉΓòÉ
  2500.  
  2501. A random number generator may be declared by first declaring a RNG and then a 
  2502. Random. For example, ACG gen(10, 20); NegativeExpntl rnd (1.0, &gen); declares 
  2503. an additive congruential generator with seed 10 and table size 20, that is used 
  2504. to generate exponentially distributed values with mean of 1.0. 
  2505.  
  2506. The virtual member Random::operator() is the common way of extracting a random 
  2507. number from a particular distribution.  The base class, Random does not 
  2508. implement operator(). This is performed by each of the subclasses. Thus, given 
  2509. the above declaration of rnd, new random values may be obtained via, for 
  2510. example, double next_exp_rand = rnd(); Currently, the following subclasses are 
  2511. provided. 
  2512.  
  2513.  
  2514. ΓòÉΓòÉΓòÉ 25.5. Binomial ΓòÉΓòÉΓòÉ
  2515.  
  2516. The binomial distribution models successfully drawing items from a pool.  The 
  2517. first parameter to the constructor, n, is the number of items in the pool, and 
  2518. the second parameter, u, is the probability of each item being successfully 
  2519. drawn.  The member asDouble returns the number of samples drawn from the pool. 
  2520. Although it is not checked, it is assumed that n>0 and 0 <= u <= 1.  The 
  2521. remaining members allow you to read and set the parameters. 
  2522.  
  2523.  
  2524. ΓòÉΓòÉΓòÉ 25.6. Erlang ΓòÉΓòÉΓòÉ
  2525.  
  2526. The Erlang class implements an Erlang distribution with mean mean and variance 
  2527. variance. 
  2528.  
  2529.  
  2530. ΓòÉΓòÉΓòÉ 25.7. Geometric ΓòÉΓòÉΓòÉ
  2531.  
  2532. The Geometric class implements a discrete geometric distribution.  The first 
  2533. parameter to the constructor, mean, is the mean of the distribution.  Although 
  2534. it is not checked, it is assumed that 0 <= mean <= 1. Geometric() returns the 
  2535. number of uniform random samples that were drawn before the sample was larger 
  2536. than mean. This quantity is always greater than zero. 
  2537.  
  2538.  
  2539. ΓòÉΓòÉΓòÉ 25.8. HyperGeometric ΓòÉΓòÉΓòÉ
  2540.  
  2541. The HyperGeometric class implements the hypergeometric distribution.  The first 
  2542. parameter to the constructor, mean, is the mean and the second, variance, is 
  2543. the variance.  The remaining members allow you to inspect and change the mean 
  2544. and variance. 
  2545.  
  2546.  
  2547. ΓòÉΓòÉΓòÉ 25.9. NegativeExpntl ΓòÉΓòÉΓòÉ
  2548.  
  2549. The NegativeExpntl class implements the negative exponential distribution.  The 
  2550. first parameter to the constructor is the mean.  The remaining members allow 
  2551. you to inspect and change the mean. 
  2552.  
  2553.  
  2554. ΓòÉΓòÉΓòÉ 25.10. Normal ΓòÉΓòÉΓòÉ
  2555.  
  2556. The Normalclass implements the normal distribution.  The first parameter to the 
  2557. constructor, mean, is the mean and the second, variance, is the variance.  The 
  2558. remaining members allow you to inspect and change the mean and variance. The 
  2559. LogNormal class is a subclass of Normal. 
  2560.  
  2561.  
  2562. ΓòÉΓòÉΓòÉ 25.11. LogNormal ΓòÉΓòÉΓòÉ
  2563.  
  2564. The LogNormalclass implements the logarithmic normal distribution.  The first 
  2565. parameter to the constructor, mean, is the mean and the second, variance, is 
  2566. the variance.  The remaining members allow you to inspect and change the mean 
  2567. and variance.  The LogNormal class is a subclass of Normal. 
  2568.  
  2569.  
  2570. ΓòÉΓòÉΓòÉ 25.12. Poisson ΓòÉΓòÉΓòÉ
  2571.  
  2572. The Poisson class implements the poisson distribution. The first parameter to 
  2573. the constructor is the mean.  The remaining members allow you to inspect and 
  2574. change the mean. 
  2575.  
  2576.  
  2577. ΓòÉΓòÉΓòÉ 25.13. DiscreteUniform ΓòÉΓòÉΓòÉ
  2578.  
  2579. The DiscreteUniform class implements a uniform random variable over the closed 
  2580. interval ranging from [low..high].  The first parameter to the constructor is 
  2581. low, and the second is high, although the order of these may be reversed.  The 
  2582. remaining members allow you to inspect and change low and high. 
  2583.  
  2584.  
  2585. ΓòÉΓòÉΓòÉ 25.14. Uniform ΓòÉΓòÉΓòÉ
  2586.  
  2587. The Uniform class implements a uniform random variable over the open interval 
  2588. ranging from [low..high).  The first parameter to the constructor is low, and 
  2589. the second is high, although the order of these may be reversed.  The remaining 
  2590. members allow you to inspect and change low and high. 
  2591.  
  2592.  
  2593. ΓòÉΓòÉΓòÉ 25.15. Weibull ΓòÉΓòÉΓòÉ
  2594.  
  2595. The Weibull class implements a weibull distribution with parameters alpha and 
  2596. beta.  The first parameter to the class constructor is alpha, and the second 
  2597. parameter is beta.  The remaining members allow you to inspect and change alpha 
  2598. and beta. 
  2599.  
  2600.  
  2601. ΓòÉΓòÉΓòÉ 25.16. RandomInteger ΓòÉΓòÉΓòÉ
  2602.  
  2603. The RandomInteger class is not a subclass of Random, but a stand-alone 
  2604. integer-oriented class that is dependent on the RNG classes. RandomInteger 
  2605. returns random integers uniformly from the closed interval [low..high].  The 
  2606. first parameter to the constructor is low, and the second is high, although 
  2607. both are optional.  The last argument is always a generator. Additional members 
  2608. allow you to inspect and change low and high.  Random integers are generated 
  2609. using asInt() or asLong().  Operator syntax (()) is also available as a 
  2610. shorthand for asLong().  Because RandomInteger is often used in simulations for 
  2611. which uniform random integers are desired over a variety of ranges, asLong() 
  2612. and asInt have high as an optional argument.  Using this optional argument 
  2613. produces a single value from the new range, but does not change the default 
  2614. range. 
  2615.  
  2616.  
  2617. ΓòÉΓòÉΓòÉ 26. Data Collection ΓòÉΓòÉΓòÉ
  2618.  
  2619. Libg++ currently provides two classes for data collection and analysis of the 
  2620. collected data. 
  2621.  
  2622.  
  2623. ΓòÉΓòÉΓòÉ 26.1. SampleStatistic ΓòÉΓòÉΓòÉ
  2624.  
  2625. Class SampleStatistic provides a means of accumulating samples of double values 
  2626. and providing common sample statistics. 
  2627.  
  2628. Assume declaration of double x. 
  2629.  
  2630.  SampleStatistic a; 
  2631.            declares and initializes a. 
  2632.  
  2633.  a.reset(); 
  2634.            re-initializes a. 
  2635.  
  2636.  a += x; 
  2637.            adds sample x. 
  2638.  
  2639.  int n = a.samples(); 
  2640.            returns the number of samples. 
  2641.  
  2642.  x = a.mean; 
  2643.            returns the means of the samples. 
  2644.  
  2645.  x = a.var() 
  2646.            returns the sample variance of the samples. 
  2647.  
  2648.  x = a.stdDev() 
  2649.            returns the sample standard deviation of the samples. 
  2650.  
  2651.  x = a.min() 
  2652.            returns the minimum encountered sample. 
  2653.  
  2654.  x = a.max() 
  2655.            returns the maximum encountered sample. 
  2656.  
  2657.  x = a.confidence(int p) 
  2658.            returns the p-percent (0 <= p < 100) confidence interval. 
  2659.  
  2660.  x = a.confidence(double p) 
  2661.            returns the p-probability (0 <= p < 1) confidence interval. 
  2662.  
  2663.  
  2664. ΓòÉΓòÉΓòÉ 26.2. SampleHistogram ΓòÉΓòÉΓòÉ
  2665.  
  2666. Class SampleHistogram is a derived class of SampleStatistic that supports 
  2667. collection and display of samples in bucketed intervals. It supports the 
  2668. following in addition to SampleStatisic operations. 
  2669.  
  2670.  SampleHistogram h(double lo, double hi, double width); 
  2671.            declares and initializes h to have buckets of size width from lo to 
  2672.            hi. If the optional argument width is not specified, 10 buckets are 
  2673.            created. The first bucket and also holds samples less than lo, and 
  2674.            the last one holds samples greater than hi. 
  2675.  
  2676.  int n = h.similarSamples(x) 
  2677.            returns the number of samples in the same bucket as x. 
  2678.  
  2679.  int n = h.inBucket(int i) 
  2680.            returns the number of samples in  bucket i. 
  2681.  
  2682.  int b = h.buckets() 
  2683.            returns the number of buckets. 
  2684.  
  2685.  h.printBuckets(ostream s) 
  2686.            prints bucket counts on ostream s. 
  2687.  
  2688.  double bound = h.bucketThreshold(int i) 
  2689.            returns the upper bound of bucket i. 
  2690.  
  2691.  
  2692. ΓòÉΓòÉΓòÉ 27. Curses-based classes ΓòÉΓòÉΓòÉ
  2693.  
  2694. The CursesWindow class is a repackaging of standard curses library features 
  2695. into a class. It relies on `curses.h'. 
  2696.  
  2697. The supplied `curses.h' is a fairly conservative declaration of curses library 
  2698. features, and does not include features like ``screen'' or X-window support. It 
  2699. is, for the most part, an adaptation, rather than an improvement of C-based 
  2700. `curses.h' files. The only substantive changes are the declarations of many 
  2701. functions as inline functions rather than macros, which was done solely to 
  2702. allow overloading. 
  2703.  
  2704. The CursesWindow class encapsulates curses window functions within a class. 
  2705. Only those functions that control windows are included: Terminal control 
  2706. functions and macros like cbreak are not part of the class.  All CursesWindows 
  2707. member functions have names identical to the corresponding curses library 
  2708. functions, except that the ``w'' prefix is generally dropped. Descriptions of 
  2709. these functions may be found in your local curses library documentation. 
  2710.  
  2711. A CursesWindow may be declared via 
  2712.  
  2713.  CursesWindow w(WINDOW* win) 
  2714.            attaches w to the existing WINDOW* win. This is constructor is 
  2715.            normally used only in the following special case. 
  2716.  
  2717.  CursesWindow w(stdscr) 
  2718.            attaches w to the default curses library standard screen window. 
  2719.  
  2720.  CursesWindow w(int lines, int cols, int begin_y, int begin_x) 
  2721.            attaches to an allocated curses window with the indicated size and 
  2722.            screen position. 
  2723.  
  2724.  CursesWindow sub(CursesWindow& w,int l,int c,int by,int bx,char ar='a') 
  2725.            attaches to a subwindow of w created via the curses `subwin' 
  2726.            command. If ar is sent as `r', the origin (by, bx) is relative to 
  2727.            the parent window, else it is absolute. 
  2728.  
  2729.  The class maintains a static counter that is used in order to automatically 
  2730.  call the curses library initscr and endscr functions at the proper times. 
  2731.  These need not, and should not be called ``manually''. 
  2732.  
  2733.  CursesWindows maintain a tree of their subwindows. Upon destruction of a 
  2734.  CursesWindow, all of their subwindows are also invalidated if they had not 
  2735.  previously been destroyed. 
  2736.  
  2737.  It is possible to traverse trees of subwindows via the following member 
  2738.  functions 
  2739.  
  2740.  CursesWindow* w.parent() 
  2741.            returns a pointer to the parent of the subwindow, or 0 if there is 
  2742.            none. 
  2743.  
  2744.  CursesWindow* w.child() 
  2745.            returns the first child subwindow of the window, or 0 if there is 
  2746.            none. 
  2747.  
  2748.  CursesWindow* w.sibling() 
  2749.            returns the next sibling of the subwindow, or 0 if there is none. 
  2750.  
  2751.  For example, to call some function visit for all subwindows of a window, you 
  2752.  could write 
  2753.  
  2754.  
  2755.   void traverse(CursesWindow& w)
  2756.   {
  2757.     visit(w);
  2758.     if (w.child() != 0) traverse(*w.child);
  2759.     if (w.sibling() != 0) traverse(*w.sibling);
  2760.   }
  2761.  
  2762.  
  2763. ΓòÉΓòÉΓòÉ 28. List classes ΓòÉΓòÉΓòÉ
  2764.  
  2765. The files `g++-include/List.hP' and `g++-include/List.ccP' provide 
  2766. pseudo-generic Lisp-type List classes.  These lists are homogeneous lists, more 
  2767. similar to lists in statically typed functional languages like ML than Lisp, 
  2768. but support operations very similar to those found in Lisp. Any particular kind 
  2769. of list class may be generated via the genclass shell command. However, the 
  2770. implementation assumes that the base class supports an equality operator ==. 
  2771. All equality tests use the == operator, and are thus equivalent to the use of 
  2772. equal, not eq in Lisp. 
  2773.  
  2774. All list nodes are created dynamically, and managed via reference counts. List 
  2775. variables are actually pointers to these list nodes. Lists may also be 
  2776. traversed via Pixes, as described in the section describing Pixes. See Pix 
  2777.  
  2778. Supported operations are mirrored closely after those in Lisp. Generally, 
  2779. operations with functional forms are constructive, functional operations, while 
  2780. member forms (often with the same name) are sometimes procedural, possibly 
  2781. destructive operations. 
  2782.  
  2783. As with Lisp, destructive operations are supported. Programmers are allowed to 
  2784. change head and tail fields in any fashion, creating circular structures and 
  2785. the like. However, again as with Lisp, some operations implicitly assume that 
  2786. they are operating on pure lists, and may enter infinite loops when presented 
  2787. with improper lists. Also, the reference-counting storage management facility 
  2788. may fail to reclaim unused circularly-linked nodes. 
  2789.  
  2790. Several Lisp-like higher order functions are supported (e.g., map). Typedef 
  2791. declarations for the required functional forms are provided int the `.h' file. 
  2792.  
  2793. For purposes of illustration, assume the specification of class intList. 
  2794. Common Lisp versions of supported operations are shown in brackets for 
  2795. comparison purposes. 
  2796.  
  2797.  
  2798. ΓòÉΓòÉΓòÉ 28.1. Constructors and assignment ΓòÉΓòÉΓòÉ
  2799.  
  2800.  intList a;      [ (setq a nil) ] 
  2801.            Declares a to be a nil intList. 
  2802.  
  2803.  intList b(2);     [ (setq b (cons 2 nil)) ] 
  2804.            Declares b to be an intList with a head value of 2, and a nil tail. 
  2805.  
  2806.  intList c(3, b);   [ (setq c (cons 3 b)) ] 
  2807.            Declares c to be an intList with a head value of 3, and b as its 
  2808.            tail. 
  2809.  
  2810.  b = a;        [ (setq b a) ] 
  2811.            Sets b to be the same list as a. 
  2812.  
  2813.  Assume the declarations of intLists a, b, and c in the following. See Pix. 
  2814.  
  2815.  
  2816. ΓòÉΓòÉΓòÉ 28.2. List status ΓòÉΓòÉΓòÉ
  2817.  
  2818.  a.null(); OR !a;    [ (null a) ] 
  2819.            returns true if a is null. 
  2820.  
  2821.  a.valid();       [ (listp a) ] 
  2822.            returns true if a is non-null. Inside a conditional test, the void* 
  2823.            coercion may also be used as in if (a) .... 
  2824.  
  2825.  intList();       [ nil ] 
  2826.            intList() may be used to null terminate a list, as in intList f(int 
  2827.            x) {if (x == 0) return intList(); ... } . 
  2828.  
  2829.  a.length();      [ (length a) ] 
  2830.            returns the length of a. 
  2831.  
  2832.  a.list_length();    [ (list-length a) ] 
  2833.            returns the length of a, or -1 if a is circular. 
  2834.  
  2835.  
  2836. ΓòÉΓòÉΓòÉ 28.3. heads and tails ΓòÉΓòÉΓòÉ
  2837.  
  2838.  a.get(); OR a.head()  [ (car a) ] 
  2839.            returns a reference to the head field. 
  2840.  
  2841.  a[2];         [ (elt a 2) ] 
  2842.            returns a reference to the second (counting from zero) head field. 
  2843.  
  2844.  a.tail();       [ (cdr a) ] 
  2845.            returns the intList that is the tail of a. 
  2846.  
  2847.  a.last();       [ (last a) ] 
  2848.            returns the intList that is the last node of a. 
  2849.  
  2850.  a.nth(2);       [ (nth a 2) ] 
  2851.            returns the intList that is the nth node of a. 
  2852.  
  2853.  a.set_tail(b);     [ (rplacd a b) ] 
  2854.            sets a's tail to b. 
  2855.  
  2856.  a.push(2);       [ (push 2 a) ] 
  2857.            equivalent to a = intList(2, a); 
  2858.  
  2859.  int x = a.pop()    [ (setq x (car a)) (pop a) ] 
  2860.            returns the head of a, also setting a to its tail. 
  2861.  
  2862.  
  2863. ΓòÉΓòÉΓòÉ 28.4. Constructive operations ΓòÉΓòÉΓòÉ
  2864.  
  2865.  b = copy(a);      [ (setq b (copy-seq a)) ] 
  2866.            sets b to a copy of a. 
  2867.  
  2868.  b = reverse(a);    [ (setq b (reverse a)) ] 
  2869.            Sets b to a reversed copy of a. 
  2870.  
  2871.  c = concat(a, b);   [ (setq c (concat a b)) ] 
  2872.            Sets c to a concatenated copy of a and b. 
  2873.  
  2874.  c = append(a, b);   [ (setq c (append a b)) ] 
  2875.            Sets c to a concatenated copy of a and b. All nodes of a are copied, 
  2876.            with the last node pointing to b. 
  2877.  
  2878.  b = map(f, a);     [ (setq b (mapcar f a)) ] 
  2879.            Sets b to a new list created by applying function f to each node of 
  2880.            a. 
  2881.  
  2882.  c = combine(f, a, b); 
  2883.            Sets c to a new list created by applying function f to successive 
  2884.            pairs of a and b. The resulting list has length the shorter of a and 
  2885.            b. 
  2886.  
  2887.  b = remove(x, a);   [ (setq b (remove x a)) ] 
  2888.            Sets b to a copy of a, omitting all occurrences of x. 
  2889.  
  2890.  b = remove(f, a);   [ (setq b (remove-if f a)) ] 
  2891.            Sets b to a copy of a, omitting values causing function f to return 
  2892.            true. 
  2893.  
  2894.  b = select(f, a);   [ (setq b (remove-if-not f a)) ] 
  2895.            Sets b to a copy of a, omitting values causing function f to return 
  2896.            false. 
  2897.  
  2898.  c = merge(a, b, f);  [ (setq c (merge a b f)) ] 
  2899.            Sets c to a list containing the ordered elements (using the 
  2900.            comparison function f) of the sorted lists a and b. 
  2901.  
  2902.  
  2903. ΓòÉΓòÉΓòÉ 28.5. Destructive operations ΓòÉΓòÉΓòÉ
  2904.  
  2905.  a.append(b);      [ (rplacd (last a) b) ] 
  2906.            appends b to the end of a. No new nodes are constructed. 
  2907.  
  2908.  a.prepend(b);     [ (setq a (append b a)) ] 
  2909.            prepends b to the beginning of a. 
  2910.  
  2911.  a.del(x);       [ (delete x a) ] 
  2912.            deletes all nodes with value x from a. 
  2913.  
  2914.  a.del(f);       [ (delete-if f a) ] 
  2915.            deletes all nodes causing function f to return true. 
  2916.  
  2917.  a.select(f);      [ (delete-if-not f a) ] 
  2918.            deletes all nodes causing function f to return false. 
  2919.  
  2920.  a.reverse();      [ (nreverse a) ] 
  2921.            reverses a in-place. 
  2922.  
  2923.  a.sort(f);       [ (sort a f) ] 
  2924.            sorts a in-place using ordering (comparison) function f. 
  2925.  
  2926.  a.apply(f);      [ (mapc f a) ] 
  2927.            Applies void function f (int x) to each element of a. 
  2928.  
  2929.  a.subst(int old, int repl); [ (nsubst repl old a) ] 
  2930.            substitutes repl for each occurrence of old in a. Note the different 
  2931.            argument order than the Lisp version. 
  2932.  
  2933.  
  2934. ΓòÉΓòÉΓòÉ 28.6. Other operations ΓòÉΓòÉΓòÉ
  2935.  
  2936.  a.find(int x);    [ (find x a) ] 
  2937.            returns the intList at the first occurrence of x. 
  2938.  
  2939.  a.find(b);      [ (find b a) ] 
  2940.            returns the intList at the first occurrence of sublist b. 
  2941.  
  2942.  a.contains(int x);   [ (member x a) ] 
  2943.            returns true if a contains x. 
  2944.  
  2945.  a.contains(b);     [ (member b a) ] 
  2946.            returns true if a contains sublist b. 
  2947.  
  2948.  a.position(int x);   [ (position x a) ] 
  2949.            returns the zero-based index of x in a, or -1 if x does not occur. 
  2950.  
  2951.  int x = a.reduce(f, int base); [ (reduce f a :initial-value base) ] 
  2952.            Accumulates the result of applying int function f(int, int) to 
  2953.            successive elements of a, starting with base. 
  2954.  
  2955.  
  2956. ΓòÉΓòÉΓòÉ 29. Linked Lists ΓòÉΓòÉΓòÉ
  2957.  
  2958. SLLists provide pseudo-generic singly linked lists.  DLLists provide doubly 
  2959. linked lists.  The lists are designed for the simple maintenance of elements in 
  2960. a linked structure, and do not provide the more extensive operations (or 
  2961. node-sharing) of class List. They behave similarly to the slist and similar 
  2962. classes described by Stroustrup. 
  2963.  
  2964. All list nodes are created dynamically. Assignment is performed via copying. 
  2965.  
  2966. Class DLList supports all SLList operations, plus additional operations 
  2967. described below. 
  2968.  
  2969. For purposes of illustration, assume the specification of class intSLList. In 
  2970. addition to the operations listed here, SLLists support traversal via Pixes. 
  2971. See Pix 
  2972.  
  2973.  intSLList a; 
  2974.            Declares a to be an empty list. 
  2975.  
  2976.  intSLList b = a; 
  2977.            Sets b to an element-by-element copy of a. 
  2978.  
  2979.  a.empty() 
  2980.            returns true if a contains no elements 
  2981.  
  2982.  a.length(); 
  2983.            returns the number of elements in a. 
  2984.  
  2985.  a.prepend(x); 
  2986.            places x at the front of the list. 
  2987.  
  2988.  a.append(x); 
  2989.            places x at the end of the list. 
  2990.  
  2991.  a.join(b) 
  2992.            places all nodes from b to the end of a, simultaneously destroying 
  2993.            b. 
  2994.  
  2995.  x = a.front() 
  2996.            returns a reference to the item stored at the head of the list, or 
  2997.            triggers an error if the list is empty. 
  2998.  
  2999.  a.rear() 
  3000.            returns a reference to the rear of the list, or triggers an error if 
  3001.            the list is empty. 
  3002.  
  3003.  x = a.remove_front() 
  3004.            deletes and returns the item stored at the head of the list. 
  3005.  
  3006.  a.del_front() 
  3007.            deletes the first element, without returning it. 
  3008.  
  3009.  a.clear() 
  3010.            deletes all items from the list. 
  3011.  
  3012.  a.ins_after(Pix i, item); 
  3013.            inserts item after position i. If i is null, insertion is at the 
  3014.            front. 
  3015.  
  3016.  a.del_after(Pix i); 
  3017.            deletes the element following i. If i is 0, the first item is 
  3018.            deleted. 
  3019.  
  3020.  
  3021. ΓòÉΓòÉΓòÉ 29.1. Doubly linked lists ΓòÉΓòÉΓòÉ
  3022.  
  3023. Class DLList supports the following additional operations, as well as backward 
  3024. traversal via Pixes. 
  3025.  
  3026.  x = a.remove_rear(); 
  3027.            deletes and returns the item stored at the rear of the list. 
  3028.  
  3029.  a.del_rear(); 
  3030.            deletes the last element, without returning it. 
  3031.  
  3032.  a.ins_before(Pix i, x) 
  3033.            inserts x before the i. 
  3034.  
  3035.  a.del(Pix& iint dir = 1) 
  3036.            deletes the item at the current position, then advances forward if 
  3037.            dir is positive, else backward. 
  3038.  
  3039.  
  3040. ΓòÉΓòÉΓòÉ 30. Vector classes ΓòÉΓòÉΓòÉ
  3041.  
  3042. The files `g++-include/Vec.ccP' and `g++-include/AVec.ccP' provide 
  3043. pseudo-generic standard array-based vector operations.  The corresponding 
  3044. header files are `g++-include/Vec.hP' and `g++-include/AVec.hP'.  Class Vec 
  3045. provides operations suitable for any base class that includes an equality 
  3046. operator. Subclass AVec provides additional arithmetic operations suitable for 
  3047. base classes that include the full complement of arithmetic operators. 
  3048.  
  3049. Vecs are constructed and assigned by copying. Thus, they should normally be 
  3050. passed by reference in applications programs. 
  3051.  
  3052. Several mapping functions are provided that allow programmers to specify 
  3053. operations on vectors as a whole. 
  3054.  
  3055. For illustrative purposes assume that classes intVec and intAVec have been 
  3056. generated via genclass. 
  3057.  
  3058.  
  3059. ΓòÉΓòÉΓòÉ 30.1. Constructors and assignment ΓòÉΓòÉΓòÉ
  3060.  
  3061.  intVec a; 
  3062.            declares a to be an empty vector. Its size may be changed via 
  3063.            resize. 
  3064.  
  3065.  intVec a(10); 
  3066.            declares a to be an uninitialized vector of ten elements (numbered 
  3067.            0-9). 
  3068.  
  3069.  intVec b(6, 0); 
  3070.            declares b to be a vector of six elements, all initialized to zero. 
  3071.            Any value can be used as the initial fill argument. 
  3072.  
  3073.  a = b; 
  3074.            Copies b to a. a is resized to be the same as b. 
  3075.  
  3076.  a = b.at(2, 4) 
  3077.            constructs a from the 4 elements of b starting at b[2]. 
  3078.  
  3079.  Assume declarations of intVec a, b, c and int i, x in the following. 
  3080.  
  3081.  
  3082. ΓòÉΓòÉΓòÉ 30.2. Status and access ΓòÉΓòÉΓòÉ
  3083.  
  3084.  a.capacity(); 
  3085.            returns the number of elements that can be held in a. 
  3086.  
  3087.  a.resize(20); 
  3088.            sets a's length to 20. All elements are unchanged, except that if 
  3089.            the new size is smaller than the original, than trailing elements 
  3090.            are deleted, and if greater, trailing elements are uninitialized. 
  3091.  
  3092.  a[i]; 
  3093.            returns a reference to the i'th element of a, or produces an error 
  3094.            if i is out of range. 
  3095.  
  3096.  a.elem(i) 
  3097.            returns a reference to the i'th element of a. Unlike the [] 
  3098.            operator, i is not checked to ensure that it is within range. 
  3099.  
  3100.  a == b; 
  3101.            returns true if a and b contain the same elements in the same order. 
  3102.  
  3103.  a != b; 
  3104.            is the converse of a == b. 
  3105.  
  3106.  
  3107. ΓòÉΓòÉΓòÉ 30.3. Constructive operations ΓòÉΓòÉΓòÉ
  3108.  
  3109.  c = concat(a, b); 
  3110.            sets c to the new vector constructed from all of the elements of a 
  3111.            followed by all of b. 
  3112.  
  3113.  c = map(f, a); 
  3114.            sets c to the new vector constructed by applying int function f(int) 
  3115.            to each element of a. 
  3116.  
  3117.  c = merge(a, b, f); 
  3118.            sets c to the new vector constructed by merging the elements of 
  3119.            ordered vectors a and b using ordering (comparison) function f. 
  3120.  
  3121.  c = combine(f, a, b); 
  3122.            sets c to the new vector constructed by applying int function f(int, 
  3123.            int) to successive pairs of a and b. The result has length the 
  3124.            shorter of a and b. 
  3125.  
  3126.  c = reverse(a) 
  3127.            sets c to a, with elements in reverse order. 
  3128.  
  3129.  
  3130. ΓòÉΓòÉΓòÉ 30.4. Destructive operations ΓòÉΓòÉΓòÉ
  3131.  
  3132.  a.reverse(); 
  3133.            reverses a in-place. 
  3134.  
  3135.  a.sort(f) 
  3136.            sorts a in-place using comparison function f. The sorting method is 
  3137.            a variation of the quicksort functions supplied with GNU emacs. 
  3138.  
  3139.  a.fill(0, 4, 2) 
  3140.            fills the 2 elements starting at a[4] with zero. 
  3141.  
  3142.  
  3143. ΓòÉΓòÉΓòÉ 30.5. Other operations ΓòÉΓòÉΓòÉ
  3144.  
  3145.  a.apply(f) 
  3146.            applies function f to each element in a. 
  3147.  
  3148.  x = a.reduce(f, base) 
  3149.            accumulates the results of applying function f to successive 
  3150.            elements of a starting with base. 
  3151.  
  3152.  a.index(int targ); 
  3153.            returns the index of the leftmost occurrence of the target, or -1, 
  3154.            if it does not occur. 
  3155.  
  3156.  a.error(char* msg) 
  3157.            invokes the error handler. The default version prints the error 
  3158.            message, then aborts. 
  3159.  
  3160.  
  3161. ΓòÉΓòÉΓòÉ 30.6. AVec operations. ΓòÉΓòÉΓòÉ
  3162.  
  3163. AVecs provide additional arithmetic operations.  All vector-by-vector operators 
  3164. generate an error if the vectors are not the same length. The following 
  3165. operations are provided, for AVecs a, b and base element (scalar) s. 
  3166.  
  3167.  a = b; 
  3168.            Copies b to a. a and b must be the same size. 
  3169.  
  3170.  a = s; 
  3171.            fills all elements of a with the value s. a is not resized. 
  3172.  
  3173.  a + s; a - s; a * s; a / s 
  3174.            adds, subtracts, multiplies, or divides each element of a with the 
  3175.            scalar. 
  3176.  
  3177.  a += s; a -= s; a *= s; a /= s; 
  3178.            adds, subtracts, multiplies, or divides the scalar into a. 
  3179.  
  3180.  a + b; a - b; product(a, b), quotient(a, b) 
  3181.            adds, subtracts, multiplies, or divides corresponding elements of a 
  3182.            and b. 
  3183.  
  3184.  a += b; a -= b; a.product(b); a.quotient(b); 
  3185.            adds, subtracts, multiplies, or divides corresponding elements of b 
  3186.            into a. 
  3187.  
  3188.  s = a * b; 
  3189.            returns the inner (dot) product of a and b. 
  3190.  
  3191.  x = a.sum(); 
  3192.            returns the sum of elements of a. 
  3193.  
  3194.  x = a.sumsq(); 
  3195.            returns the sum of squared elements of a. 
  3196.  
  3197.  x = a.min(); 
  3198.            returns the minimum element of a. 
  3199.  
  3200.  x = a.max(); 
  3201.            returns the maximum element of a. 
  3202.  
  3203.  i = a.min_index(); 
  3204.            returns the index of the minimum element of a. 
  3205.  
  3206.  i = a.max_index(); 
  3207.            returns the index of the maximum element of a. 
  3208.  
  3209.            Note that it is possible to apply vector versions other arithmetic 
  3210.            operators via the mapping functions. For example, to set vector b to 
  3211.            the  cosines of doubleVec a, use b = map(cos, a);. This is often 
  3212.            more efficient than performing the operations in an 
  3213.            element-by-element fashion. 
  3214.  
  3215.  
  3216. ΓòÉΓòÉΓòÉ 31. Plex classes ΓòÉΓòÉΓòÉ
  3217.  
  3218. A ``Plex'' is a kind of array with the following properties: 
  3219.  
  3220.      Plexes may have arbitrary upper and lower index bounds. For example a 
  3221.       Plex may be declared to run from indices -10 .. 10. 
  3222.  
  3223.      Plexes may be dynamically expanded at both the lower and upper bounds of 
  3224.       the array in steps of one element. 
  3225.  
  3226.      Only elements that have been specifically initialized or added may be 
  3227.       accessed. 
  3228.  
  3229.      Elements may be accessed via indices. Indices are always checked for 
  3230.       validity at run time.  Plexes may be traversed via simple variations of 
  3231.       standard array indexing loops. 
  3232.  
  3233.      Plex elements may be accessed and traversed via Pixes. 
  3234.  
  3235.      Plex-to-Plex assignment and related operations on entire Plexes are 
  3236.       supported. 
  3237.  
  3238.      Plex classes contain methods to help programmers check the validity of 
  3239.       indexing and pointer operations. 
  3240.  
  3241.      Plexes form ``natural'' base classes for many restricted-access data 
  3242.       structures relying on logically contiguous indices, such as array-based 
  3243.       stacks and queues. 
  3244.  
  3245.      Plexes are implemented as pseudo-generic classes, and must be generated 
  3246.       via the genclass utility. 
  3247.  
  3248.  Four subclasses of Plexes are supported: A FPlex is a Plex that may only grow 
  3249.  or shrink within declared bounds; an XPlex may dynamically grow or shrink 
  3250.  without bounds; an RPlex is the same as an XPlex but better supports indexing 
  3251.  with poor locality of reference; a MPlex may grow or shrink, and additionally 
  3252.  allows the logical deletion and restoration of elements. Because these classes 
  3253.  are virtual subclasses of the ``abstract'' class Plex, it is possible to write 
  3254.  user code such as void f(Plex& a) ... that operates on any kind of Plex. 
  3255.  However, as with nearly any virtual class, specifying the particular Plex 
  3256.  class being used results in more efficient code. 
  3257.  
  3258.  Plexes are implemented as a linked list of IChunks.  Each chunk contains a 
  3259.  part of the array. Chunk sizes may be specified within Plex constructors. 
  3260.  Default versions also exist, that use a #define'd default.  Plexes grow by 
  3261.  filling unused space in existing chunks, if possible, else, except for 
  3262.  FPlexes, by adding another chunk.  Whenever Plexes grow by a new chunk, the 
  3263.  default element constructors (i.e., those which take no arguments) for all 
  3264.  chunk elements are called at once. When Plexes shrink, destructors for the 
  3265.  elements are not called until an entire chunk is freed. For this reason, 
  3266.  Plexes (like C++ arrays) should only be used for elements with default 
  3267.  constructors and destructors that have no side effects. 
  3268.  
  3269.  Plexes may be indexed and used like arrays, although traversal syntax is 
  3270.  slightly different. Even though Plexes maintain elements in lists of chunks, 
  3271.  they are implemented so that iteration and other constructs that maintain 
  3272.  locality of reference require very little overhead over that for simple array 
  3273.  traversal Pix-based traversal is also supported. For example, for a plex, p, 
  3274.  of ints, the following traversal methods could be used. 
  3275.  
  3276.   for (int i = p.low(); i < p.fence(); p.next(i)) use(p[i]);
  3277.   for (int i = p.high(); i > p.ecnef(); p.prev(i)) use(p[i]);
  3278.   for (Pix t = p.first(); t != 0; p.next(t)) use(p(i));
  3279.   for (Pix t = p.last(); t != 0; p.prev(t)) use(p(i));
  3280.  
  3281.  Except for MPlexes, simply using ++i and --i works just as well as p.next(i) 
  3282.  and p.prev(i) when traversing by index. Index-based traversal is generally a 
  3283.  bit faster than Pix-based traversal. 
  3284.  
  3285.  XPlexes and MPlexes are less than optimal for applications in which widely 
  3286.  scattered elements are indexed, as might occur when using Plexes as hash 
  3287.  tables or ``manually'' allocated linked lists. In such applications, RPlexes 
  3288.  are often preferable. RPlexes use a secondary chunk index table that requires 
  3289.  slightly greater, but entirely uniform overhead per index operation. 
  3290.  
  3291.  Even though they may grow in either direction, Plexes are normally constructed 
  3292.  so that their ``natural'' growth direction is upwards, in that default chunk 
  3293.  construction leaves free space, if present, at the end of the plex. However, 
  3294.  if the chunksize arguments to constructors are negative, they leave space at 
  3295.  the beginning. 
  3296.  
  3297.  All versions of Plexes support the following basic capabilities. (letting Plex 
  3298.  stand for the type name constructed via the genclass utility (e.g., intPlex, 
  3299.  doublePlex)).  Assume declarations of Plex p, q, int i, j, base element x, and 
  3300.  Pix pix. 
  3301.  
  3302.  Plex p; 
  3303.            Declares p to be an initially zero-sized Plex with low index of 
  3304.            zero, and the default chunk size. For FPlexes, chunk sizes represent 
  3305.            maximum sizes. 
  3306.  
  3307.  Plex p(int size); 
  3308.            Declares p to be an initially zero-sized Plex with low index of 
  3309.            zero, and the indicated chunk size. If size is negative, then the 
  3310.            Plex is created with free space at the beginning of the Plex, 
  3311.            allowing more efficient add_low() operations. Otherwise, it leaves 
  3312.            space at the end. 
  3313.  
  3314.  Plex p(int low, int size); 
  3315.            Declares p to be an initially zero-sized Plex with low index of low, 
  3316.            and the indicated chunk size. 
  3317.  
  3318.  Plex p(int low, int high, Base initval, int size = 0); 
  3319.            Declares p to be a Plex with indices from low to high, initially 
  3320.            filled with initval, and the indicated chunk size if specified, else 
  3321.            the default or (high - low + 1), whichever is greater. 
  3322.  
  3323.  Plex q(p); 
  3324.            Declares q to be a copy of p. 
  3325.  
  3326.  p = q; 
  3327.            Copies Plex q into p, deleting its previous contents. 
  3328.  
  3329.  p.length() 
  3330.            Returns the number of elements in the Plex. 
  3331.  
  3332.  p.empty() 
  3333.            Returns true if Plex p contains no elements. 
  3334.  
  3335.  p.full() 
  3336.            Returns true if Plex p cannot be expanded. This always returns false 
  3337.            for XPlexes and MPlexes. 
  3338.  
  3339.  p[i] 
  3340.            Returns a reference to the i'th element of p. An exception (error) 
  3341.            occurs if i is not a valid index. 
  3342.  
  3343.  p.valid(i) 
  3344.            Returns true if i is a valid index into Plex p. 
  3345.  
  3346.  p.low(); p.high(); 
  3347.            Return the minimum (maximum) valid index of the Plex, or the high 
  3348.            (low) fence if the plex is empty. 
  3349.  
  3350.  p.ecnef(); p.fence(); 
  3351.            Return the index one position past the minimum (maximum) valid 
  3352.            index. 
  3353.  
  3354.  p.next(i); i = p.prev(i); 
  3355.            Set i to the next (previous) index. This index may not be within 
  3356.            bounds. 
  3357.  
  3358.  p(pix) 
  3359.            returns a reference to the item at Pix pix. 
  3360.  
  3361.  pix = p.first(); pix = p.last(); 
  3362.            Return the minimum (maximum) valid Pix of the Plex, or 0 if the plex 
  3363.            is empty. 
  3364.  
  3365.  p.next(pix); p.prev(pix); 
  3366.            set pix to the next (previous) Pix, or 0 if there is none. 
  3367.  
  3368.  p.owns(pix) 
  3369.            Returns true if the Plex contains the element associated with pix. 
  3370.  
  3371.  p.Pix_to_index(pix) 
  3372.            If pix is a valid Pix to an element of the Plex, returns its 
  3373.            corresponding index, else raises an exception. 
  3374.  
  3375.  ptr = p.index_to_Pix(i) 
  3376.            if i is a valid index, returns a the corresponding Pix. 
  3377.  
  3378.  p.low_element(); p.high_element(); 
  3379.            Return a reference to the element at the minimum (maximum) valid 
  3380.            index. An exception occurs if the Plex is empty. 
  3381.  
  3382.  p.can_add_low();  p.can_add_high(); 
  3383.            Returns true if the plex can be extended one element downward 
  3384.            (upward). These always return true for XPlex and MPlex. 
  3385.  
  3386.  j = p.add_low(x); j = p.add_high(x); 
  3387.            Extend the Plex by one element downward (upward). The new minimum 
  3388.            (maximum) index is returned. 
  3389.  
  3390.  j = p.del_low(); j = p.del_high() 
  3391.            Shrink the Plex by one element on the low (high) end. The new 
  3392.            minimum (maximum) element is returned. An exception occurs if the 
  3393.            Plex is empty. 
  3394.  
  3395.  p.append(q); 
  3396.            Append all of Plex q to the high side of p. 
  3397.  
  3398.  p.prepend(q); 
  3399.            Prepend all of q to the low side of p. 
  3400.  
  3401.  p.clear() 
  3402.            Delete all elements, resetting p to a zero-sized Plex. 
  3403.  
  3404.  p.reset_low(i); 
  3405.            Resets p to be indexed starting at low() = i. For example. if p were 
  3406.            initially declared via Plex p(0, 10, 0), and then re-indexed via 
  3407.            p.reset_low(5), it could then be indexed from indices 5 .. 14. 
  3408.  
  3409.  p.fill(x) 
  3410.            sets all p[i] to x. 
  3411.  
  3412.  p.fill(x, lo, hi) 
  3413.            sets all of p[i] from lo to hi, inclusive, to x. 
  3414.  
  3415.  p.reverse() 
  3416.            reverses p in-place. 
  3417.  
  3418.  p.chunk_size() 
  3419.            returns the chunk size used for the plex. 
  3420.  
  3421.  p.error(const char * msg) 
  3422.            calls the resettable error handler. 
  3423.  
  3424.  MPlexes are plexes with bitmaps that allow items to be logically deleted and 
  3425.  restored. They behave like other plexes, but also support the following 
  3426.  additional and modified capabilities: 
  3427.  
  3428.  p.del_index(i); p.del_Pix(pix) 
  3429.            logically deletes p[i] (p(pix)). After deletion, attempts to access 
  3430.            p[i] generate a error. Indexing via low(), high(), prev(), and 
  3431.            next() skip the element. Deleting an element never changes the 
  3432.            logical bounds of the plex. 
  3433.  
  3434.  p.undel_index(i); p.undel_Pix(pix) 
  3435.            logically undeletes p[i] (p(pix)). 
  3436.  
  3437.  p.del_low(); p.del_high() 
  3438.            Delete the lowest (highest) undeleted element, resetting the logical 
  3439.            bounds of the plex to the next lowest (highest) undeleted index. 
  3440.            Thus, MPlex del_low() and del_high() may shrink the bounds of the 
  3441.            plex by more than one index. 
  3442.  
  3443.  p.adjust_bounds() 
  3444.            Resets the low and high bounds of the Plex to the indexes of the 
  3445.            lowest and highest actual undeleted elements. 
  3446.  
  3447.  int i = p.add(x) 
  3448.            Adds x in an unused index, if possible, else performs add_high. 
  3449.  
  3450.  p.count() 
  3451.            returns the number of valid (undeleted) elements. 
  3452.  
  3453.  p.available() 
  3454.            returns the number of available (deleted) indices. 
  3455.  
  3456.  int i = p.unused_index() 
  3457.            returns the index of some deleted element, if one exists, else 
  3458.            triggers an error. An unused element may be reused via undel. 
  3459.  
  3460.  pix = p.unused_Pix() 
  3461.            returns the pix of some deleted element, if one exists, else 0. An 
  3462.            unused element may be reused via undel. 
  3463.  
  3464.  
  3465. ΓòÉΓòÉΓòÉ 32. Stacks ΓòÉΓòÉΓòÉ
  3466.  
  3467. Stacks are declared as an ``abstract'' class. They are currently implemented in 
  3468. any of three ways. 
  3469.  
  3470.  VStack 
  3471.            implement fixed sized stacks via arrays. 
  3472.  
  3473.  XPStack 
  3474.            implement dynamically-sized stacks via XPlexes. 
  3475.  
  3476.  SLStack 
  3477.            implement dynamically-size stacks via linked lists. 
  3478.  
  3479.  All possess the same capabilities. They differ only in constructors. VStack 
  3480.  constructors require a fixed maximum capacity argument. XPStack constructors 
  3481.  optionally take a chunk size argument. SLStack constructors take no argument. 
  3482.  
  3483.  Assume the declaration of a base element x. 
  3484.  
  3485.  Stack s;  or Stack s(int capacity) 
  3486.            declares a Stack. 
  3487.  
  3488.  s.empty() 
  3489.            returns true if stack s is empty. 
  3490.  
  3491.  s.full() 
  3492.            returns true if stack s is full. XPStacks and SLStacks never become 
  3493.            full. 
  3494.  
  3495.  s.length() 
  3496.            returns the current number of elements in the stack. 
  3497.  
  3498.  s.push(x) 
  3499.            pushes x on stack s. 
  3500.  
  3501.  x = s.pop() 
  3502.            pops and returns the top of stack 
  3503.  
  3504.  s.top() 
  3505.            returns a reference to the top of stack. 
  3506.  
  3507.  s.del_top() 
  3508.            pops, but does not return the top of stack. When large items are 
  3509.            held on the stack it is often a good idea to use top() to inspect 
  3510.            and use the top of stack, followed by a del_top() 
  3511.  
  3512.  s.clear() 
  3513.            removes all elements from the stack. 
  3514.  
  3515.  
  3516. ΓòÉΓòÉΓòÉ 33. Queues ΓòÉΓòÉΓòÉ
  3517.  
  3518. Queues are declared as an ``abstract'' class. They are currently implemented in 
  3519. any of three ways. 
  3520.  
  3521.  VQueue 
  3522.            implement fixed sized Queues via arrays. 
  3523.  
  3524.  XPQueue 
  3525.            implement dynamically-sized Queues via XPlexes. 
  3526.  
  3527.  SLQueue 
  3528.            implement dynamically-size Queues via linked lists. 
  3529.  
  3530.  All possess the same capabilities; they differ only in constructors. VQueue 
  3531.  constructors require a fixed maximum capacity argument. XPQueue constructors 
  3532.  optionally take a chunk size argument. SLQueue constructors take no argument. 
  3533.  
  3534.  Assume the declaration of a base element x. 
  3535.  
  3536.  Queue q; or Queue q(int capacity); 
  3537.            declares a queue. 
  3538.  
  3539.  q.empty() 
  3540.            returns true if queue q is empty. 
  3541.  
  3542.  q.full() 
  3543.            returns true if queue q is full. XPQueues and SLQueues are never 
  3544.            full. 
  3545.  
  3546.  q.length() 
  3547.            returns the current number of elements in the queue. 
  3548.  
  3549.  q.enq(x) 
  3550.            enqueues x on queue q. 
  3551.  
  3552.  x = q.deq() 
  3553.            dequeues and returns the front of queue 
  3554.  
  3555.  q.front() 
  3556.            returns a reference to the front of queue. 
  3557.  
  3558.  q.del_front() 
  3559.            dequeues, but does not return the front of queue 
  3560.  
  3561.  q.clear() 
  3562.            removes all elements from the queue. 
  3563.  
  3564.  
  3565. ΓòÉΓòÉΓòÉ 34. Double ended Queues ΓòÉΓòÉΓòÉ
  3566.  
  3567. Deques are declared as an ``abstract'' class. They are currently implemented in 
  3568. two ways. 
  3569.  
  3570.  XPDeque 
  3571.            implement dynamically-sized Deques via XPlexes. 
  3572.  
  3573.  DLDeque 
  3574.            implement dynamically-size Deques via linked lists. 
  3575.  
  3576.  All possess the same capabilities. They differ only in constructors. XPDeque 
  3577.  constructors optionally take a chunk size argument. DLDeque constructors take 
  3578.  no argument. 
  3579.  
  3580.  Double-ended queues support both stack-like and queue-like capabilities: 
  3581.  
  3582.  Assume the declaration of a base element x. 
  3583.  
  3584.  Deque d; or Deque d(int initial_capacity) 
  3585.            declares a deque. 
  3586.  
  3587.  d.empty() 
  3588.            returns true if deque d is empty. 
  3589.  
  3590.  d.full() 
  3591.            returns true if deque d is full. Always returns false in current 
  3592.            implementations. 
  3593.  
  3594.  d.length() 
  3595.            returns the current number of elements in the deque. 
  3596.  
  3597.  d.enq(x) 
  3598.            inserts x at the rear of deque d. 
  3599.  
  3600.  d.push(x) 
  3601.            inserts x at the front of deque d. 
  3602.  
  3603.  x = d.deq() 
  3604.            dequeues and returns the front of deque 
  3605.  
  3606.  d.front() 
  3607.            returns a reference to the front of deque. 
  3608.  
  3609.  d.rear() 
  3610.            returns a reference to the rear of the deque. 
  3611.  
  3612.  d.del_front() 
  3613.            deletes, but does not return the front of deque 
  3614.  
  3615.  d.del_rear() 
  3616.            deletes, but does not return the rear of the deque. 
  3617.  
  3618.  d.clear() 
  3619.            removes all elements from the deque. 
  3620.  
  3621.  
  3622. ΓòÉΓòÉΓòÉ 35. Priority Queue class prototypes. ΓòÉΓòÉΓòÉ
  3623.  
  3624. Priority queues maintain collections of objects arranged for fast access to the 
  3625. least element. 
  3626.  
  3627. Several prototype implementations of priority queues are supported. 
  3628.  
  3629.  XPPQs 
  3630.            implement 2-ary heaps via XPlexes. 
  3631.  
  3632.  SplayPQs 
  3633.            implement  PQs via Sleator and Tarjan's (JACM 1985) splay trees. The 
  3634.            algorithms use a version of ``simple top-down splaying'' (described 
  3635.            on page 669 of the article).  The simple-splay mechanism for 
  3636.            priority queue functions is loosely based on the one used by D. 
  3637.            Jones in the C splay tree functions available from volume 14 of the 
  3638.            uunet.uu.net archives. 
  3639.  
  3640.  PHPQs 
  3641.            implement pairing heaps (as described by Fredman and Sedgewick in 
  3642.            Algorithmica, Vol 1, p111-129).  Storage for heap elements is 
  3643.            managed via an internal freelist technique. The constructor allows 
  3644.            an initial capacity estimate for freelist space.  The storage is 
  3645.            automatically expanded if necessary to hold new items. The deletion 
  3646.            technique is a fast ``lazy deletion'' strategy that marks items as 
  3647.            deleted, without reclaiming space until the items come to the top of 
  3648.            the heap. 
  3649.  
  3650.  All PQ classes support the following operations, for some PQ class Heap, 
  3651.  instance h, Pix ind, and base class variable x. 
  3652.  
  3653.  h.empty() 
  3654.            returns true if there are no elements in the PQ. 
  3655.  
  3656.  h.length() 
  3657.            returns the number of elements in h. 
  3658.  
  3659.  ind = h.enq(x) 
  3660.            Places x in the PQ, and returns its index. 
  3661.  
  3662.  x = h.deq() 
  3663.            Dequeues the minimum element of the PQ into x, or generates an error 
  3664.            if the PQ is empty. 
  3665.  
  3666.  h.front() 
  3667.            returns a reference to the minimum element. 
  3668.  
  3669.  h.del_front() 
  3670.            deletes the minimum element. 
  3671.  
  3672.  h.clear(); 
  3673.            deletes all elements from h; 
  3674.  
  3675.  h.contains(x) 
  3676.            returns true if x is in h. 
  3677.  
  3678.  h(ind) 
  3679.            returns a reference to the item indexed by ind. 
  3680.  
  3681.  ind = h.first() 
  3682.            returns the Pix of first item in the PQ or 0 if empty. This need not 
  3683.            be the Pix of the least element. 
  3684.  
  3685.  h.next(ind) 
  3686.            advances ind to the Pix of next element, or 0 if there are no more. 
  3687.  
  3688.  ind = h.seek(x) 
  3689.            Sets ind to the Pix of x, or 0 if x is not in h. 
  3690.  
  3691.  h.del(ind) 
  3692.            deletes the item with Pix ind. 
  3693.  
  3694.  
  3695. ΓòÉΓòÉΓòÉ 36. Set class prototypes ΓòÉΓòÉΓòÉ
  3696.  
  3697. Set classes maintain unbounded collections of items containing no duplicate 
  3698. elements. 
  3699.  
  3700. These are currently implemented in several ways, differing in representation 
  3701. strategy, algorithmic efficiency, and appropriateness for various tasks. 
  3702. (Listed next to each are average (followed by worst-case, if different) time 
  3703. complexities for [a] adding, [f] finding (via seek, contains), [d] deleting, 
  3704. elements, and [c] comparing (via ==, <=) and [m] merging (via |=, -=, &=) 
  3705. sets). 
  3706.  
  3707.  XPSets 
  3708.            implement unordered sets via XPlexes. ([a O(n)], [f O(n)], [d O(n)], 
  3709.            [c O(n^2)] [m O(n^2)]). 
  3710.  
  3711.  OXPSets 
  3712.            implement ordered sets via XPlexes. ([a O(n)], [f O(log n)], [d 
  3713.            O(n)], [c O(n)] [m O(n)]). 
  3714.  
  3715.  SLSets 
  3716.            implement unordered sets via linked lists ([a O(n)], [f O(n)], [d 
  3717.            O(n)], [c O(n^2)] [m O(n^2)]). 
  3718.  
  3719.  OSLSets 
  3720.            implement ordered sets via linked lists ([a O(n)], [f O(n)], [d 
  3721.            O(n)], [c O(n)] [m O(n)]). 
  3722.  
  3723.  AVLSets 
  3724.            implement ordered sets via threaded AVL trees ([a O(log n)], [f 
  3725.            O(log n)], [d O(log n)], [c O(n)] [m O(n)]). 
  3726.  
  3727.  BSTSets 
  3728.            implement ordered sets via binary search trees. The trees may be 
  3729.            manually rebalanced via the O(n) balance() member function. ([a 
  3730.            O(log n)/O(n)], [f O(log n)/O(n)], [d O(log n)/O(n)], [c O(n)] [m 
  3731.            O(n)]). 
  3732.  
  3733.  SplaySets 
  3734.            implement ordered sets via Sleator and Tarjan's (JACM 1985) splay 
  3735.            trees. The algorithms use a version of ``simple top-down splaying'' 
  3736.            (described on page 669 of the article). (Amortized: [a O(log n)], [f 
  3737.            O(log n)], [d O(log n)], [c O(n)] [m O(n log n)]). 
  3738.  
  3739.  VHSets 
  3740.            implement unordered sets via hash tables. The tables are 
  3741.            automatically resized when their capacity is exhausted. ([a 
  3742.            O(1)/O(n)], [f O(1)/O(n)], [d O(1)/O(n)], [c O(n)/O(n^2)] [m 
  3743.            O(n)/O(n^2)]). 
  3744.  
  3745.  VOHSets 
  3746.            implement unordered sets via ordered hash tables The tables are 
  3747.            automatically resized when their capacity is exhausted. ([a 
  3748.            O(1)/O(n)], [f O(1)/O(n)], [d O(1)/O(n)], [c O(n)/O(n^2)] [m 
  3749.            O(n)/O(n^2)]). 
  3750.  
  3751.  CHSets 
  3752.            implement unordered sets via chained hash tables. ([a O(1)/O(n)], [f 
  3753.            O(1)/O(n)], [d O(1)/O(n)], [c O(n)/O(n^2)] [m O(n)/O(n^2)]). 
  3754.  
  3755.  The different implementations differ in whether their constructors require an 
  3756.  argument specifying their initial capacity. Initial capacities are required 
  3757.  for plex and hash table based Sets.  If none is given DEFAULT_INITIAL_CAPACITY 
  3758.  (from `<T>defs.h') is used. 
  3759.  
  3760.  Sets support the following operations, for some class Set, instances a and b, 
  3761.  Pix ind, and base element x. Since all implementations are virtual derived 
  3762.  classes of the <T>Set class, it is possible to mix and match operations across 
  3763.  different implementations, although, as usual, operations are generally faster 
  3764.  when the particular classes are specified in functions operating on Sets. 
  3765.  
  3766.  Pix-based operations are more fully described in the section on Pixes. See Pix 
  3767.  
  3768.  Set a; or Set a(int initial_size); 
  3769.            Declares a to be an empty Set. The second version is allowed in set 
  3770.            classes that require initial capacity or sizing specifications. 
  3771.  
  3772.  a.empty() 
  3773.            returns true if a is empty. 
  3774.  
  3775.  a.length() 
  3776.            returns the number of elements in a. 
  3777.  
  3778.  Pix ind = a.add(x) 
  3779.            inserts x into a, returning its index. 
  3780.  
  3781.  a.del(x) 
  3782.            deletes x from a. 
  3783.  
  3784.  a.clear() 
  3785.            deletes all elements from a; 
  3786.  
  3787.  a.contains(x) 
  3788.            returns true if x is in a. 
  3789.  
  3790.  a(ind) 
  3791.            returns a reference to the item indexed by ind. 
  3792.  
  3793.  ind = a.first() 
  3794.            returns the Pix of first item in the set or 0 if the Set is empty. 
  3795.            For ordered Sets, this is the Pix of the least element. 
  3796.  
  3797.  a.next(ind) 
  3798.            advances ind to the Pix of next element, or 0 if there are no more. 
  3799.  
  3800.  ind = a.seek(x) 
  3801.            Sets ind to the Pix of x, or 0 if x is not in a. 
  3802.  
  3803.  a == b 
  3804.            returns true if a and b contain all the same elements. 
  3805.  
  3806.  a != b 
  3807.            returns true if a and b do not contain all the same elements. 
  3808.  
  3809.  a <= b 
  3810.            returns true if a is a subset of b. 
  3811.  
  3812.  a |= b 
  3813.            Adds all elements of b to a. 
  3814.  
  3815.  a -= b 
  3816.            Deletes all elements of b from a. 
  3817.  
  3818.  a &= b 
  3819.            Deletes all elements of a not occurring in b. 
  3820.  
  3821.  
  3822. ΓòÉΓòÉΓòÉ 37. Bag class prototypes ΓòÉΓòÉΓòÉ
  3823.  
  3824. Bag classes maintain unbounded collections of items potentially containing 
  3825. duplicate elements. 
  3826.  
  3827. These are currently implemented in several ways, differing in representation 
  3828. strategy, algorithmic efficiency, and appropriateness for various tasks. 
  3829. (Listed next to each are average (followed by worst-case, if different) time 
  3830. complexities for [a] adding, [f] finding (via seek, contains), [d] deleting 
  3831. elements). 
  3832.  
  3833.  XPBags 
  3834.            implement unordered Bags via XPlexes. ([a O(1)], [f O(n)], [d 
  3835.            O(n)]). 
  3836.  
  3837.  OXPBags 
  3838.            implement ordered Bags via XPlexes. ([a O(n)], [f O(log n)], [d 
  3839.            O(n)]). 
  3840.  
  3841.  SLBags 
  3842.            implement unordered Bags via linked lists ([a O(1)], [f O(n)], [d 
  3843.            O(n)]). 
  3844.  
  3845.  OSLBags 
  3846.            implement ordered Bags via linked lists ([a O(n)], [f O(n)], [d 
  3847.            O(n)]). 
  3848.  
  3849.  SplayBags 
  3850.            implement ordered Bags via Sleator and Tarjan's (JACM 1985) splay 
  3851.            trees. The algorithms use a version of ``simple top-down splaying'' 
  3852.            (described on page 669 of the article). (Amortized: [a O(log n)], [f 
  3853.            O(log n)], [d O(log n)]). 
  3854.  
  3855.  VHBags 
  3856.            implement unordered Bags via hash tables. The tables are 
  3857.            automatically resized when their capacity is exhausted. ([a 
  3858.            O(1)/O(n)], [f O(1)/O(n)], [d O(1)/O(n)]). 
  3859.  
  3860.  CHBags 
  3861.            implement unordered Bags via chained hash tables. ([a O(1)/O(n)], [f 
  3862.            O(1)/O(n)], [d O(1)/O(n)]). 
  3863.  
  3864.  The implementations differ in whether their constructors require an argument 
  3865.  to specify their initial capacity. Initial capacities are required for plex 
  3866.  and hash table based Bags.  If none is given DEFAULT_INITIAL_CAPACITY (from 
  3867.  `<T>defs.h') is used. 
  3868.  
  3869.  Bags support the following operations, for some class Bag, instances a and b, 
  3870.  Pix ind, and base element x. Since all implementations are virtual derived 
  3871.  classes of the <T>Bag class, it is possible to mix and match operations across 
  3872.  different implementations, although, as usual, operations are generally faster 
  3873.  when the particular classes are specified in functions operating on Bags. 
  3874.  
  3875.  Pix-based operations are more fully described in the section on Pixes. See Pix 
  3876.  
  3877.  Bag a; or Bag a(int initial_size) 
  3878.            Declares a to be an empty Bag. The second version is allowed in Bag 
  3879.            classes that require initial capacity or sizing specifications. 
  3880.  
  3881.  a.empty() 
  3882.            returns true if a is empty. 
  3883.  
  3884.  a.length() 
  3885.            returns the number of elements in a. 
  3886.  
  3887.  ind = a.add(x) 
  3888.            inserts x into a, returning its index. 
  3889.  
  3890.  a.del(x) 
  3891.            deletes one occurrence of x from a. 
  3892.  
  3893.  a.remove(x) 
  3894.            deletes all occurrences of x from a. 
  3895.  
  3896.  a.clear() 
  3897.            deletes all elements from a; 
  3898.  
  3899.  a.contains(x) 
  3900.            returns true if x is in a. 
  3901.  
  3902.  a.nof(x) 
  3903.            returns the number of occurrences of x in a. 
  3904.  
  3905.  a(ind) 
  3906.            returns a reference to the item indexed by ind. 
  3907.  
  3908.  int = a.first() 
  3909.            returns the Pix of first item in the Bag or 0 if the Bag is empty. 
  3910.            For ordered Bags, this is the Pix of the least element. 
  3911.  
  3912.  a.next(ind) 
  3913.            advances ind to the Pix of next element, or 0 if there are no more. 
  3914.  
  3915.  ind = a.seek(x, Pix from = 0) 
  3916.            Sets ind to the Pix of the next occurrence x, or 0 if there are 
  3917.            none. If from is 0, the first occurrence is returned, else the 
  3918.            following from. 
  3919.  
  3920.  
  3921. ΓòÉΓòÉΓòÉ 38. Map Class Prototypes ΓòÉΓòÉΓòÉ
  3922.  
  3923. Maps support associative array operations (insertion, deletion, and membership 
  3924. of records based on an associated key). They require the specification of two 
  3925. types, the key type and the contents type. 
  3926.  
  3927. These are currently implemented in several ways, differing in representation 
  3928. strategy, algorithmic efficiency, and appropriateness for various tasks. 
  3929. (Listed next to each are average (followed by worst-case, if different) time 
  3930. complexities for [a] accessing (via op [], contains), [d] deleting elements). 
  3931.  
  3932.  AVLMaps 
  3933.            implement ordered Maps via threaded AVL trees ([a O(log n)], [d 
  3934.            O(log n)]). 
  3935.  
  3936.  RAVLMaps 
  3937.            Similar, but also maintain ranking information, used via 
  3938.            ranktoPix(int r), that returns the Pix of the item at rank r, and 
  3939.            rank(key) that returns the rank of the corresponding item. ([a O(log 
  3940.            n)], [d O(log n)]). 
  3941.  
  3942.  SplayMaps 
  3943.            implement ordered Maps via Sleator and Tarjan's (JACM 1985) splay 
  3944.            trees. The algorithms use a version of ``simple top-down splaying'' 
  3945.            (described on page 669 of the article). (Amortized: [a O(log n)], [d 
  3946.            O(log n)]). 
  3947.  
  3948.  VHMaps 
  3949.            implement unordered Maps via hash tables. The tables are 
  3950.            automatically resized when their capacity is exhausted. ([a 
  3951.            O(1)/O(n)], [d O(1)/O(n)]). 
  3952.  
  3953.  CHMaps 
  3954.            implement unordered Maps via chained hash tables. ([a O(1)/O(n)], [d 
  3955.            O(1)/O(n)]). 
  3956.  
  3957.  The different implementations differ in whether their constructors require an 
  3958.  argument specifying their initial capacity. Initial capacities are required 
  3959.  for hash table based Maps.  If none is given DEFAULT_INITIAL_CAPACITY (from 
  3960.  `<T>defs.h') is used. 
  3961.  
  3962.  All Map classes share the following operations (for some Map class, Map 
  3963.  instance d, Pix ind and key variable k, and contents variable x). 
  3964.  
  3965.  Pix-based operations are more fully described in the section on Pixes. See Pix 
  3966.  
  3967.  Map d(x);  Map d(x, int initial_capacity) 
  3968.            Declare d to be an empty Map. The required argument, x, specifies 
  3969.            the default contents, i.e., the contents of an otherwise 
  3970.            uninitialized location. The second version, specifying initial 
  3971.            capacity is allowed for Maps with an initial capacity argument. 
  3972.  
  3973.  d.empty() 
  3974.            returns true if d contains no items. 
  3975.  
  3976.  d.length() 
  3977.            returns the number of items in d. 
  3978.  
  3979.  d[k] 
  3980.            returns a reference to the contents of item with key k. If no such 
  3981.            item exists, it is installed with the default contents. Thus d[k] = 
  3982.            x installs x, and x = d[k] retrieves it. 
  3983.  
  3984.  d.contains(k) 
  3985.            returns true if an item with key field k exists in d. 
  3986.  
  3987.  d.del(k) 
  3988.            deletes the item with key k. 
  3989.  
  3990.  d.clear() 
  3991.            deletes all items from the table. 
  3992.  
  3993.  x = d.dflt() 
  3994.            returns the default contents. 
  3995.  
  3996.  k = d.key(ind) 
  3997.            returns a reference to the key at Pix ind. 
  3998.  
  3999.  x = d.contents(ind) 
  4000.            returns a reference to the contents at Pix ind. 
  4001.  
  4002.  ind = d.first() 
  4003.            returns the Pix of the first element in d, or 0 if d is empty. 
  4004.  
  4005.  d.next(ind) 
  4006.            advances ind to the next element, or 0 if there are no more. 
  4007.  
  4008.  ind = d.seek(k) 
  4009.            returns the Pix of element with key k, or 0 if k is not in d. 
  4010.  
  4011.  
  4012. ΓòÉΓòÉΓòÉ 39. C++ version of the GNU getopt function ΓòÉΓòÉΓòÉ
  4013.  
  4014. The GetOpt class provides an efficient and structured mechanism for processing 
  4015. command-line options from an application program.  The sample program fragment 
  4016. below illustrates a typical use of the GetOpt class for some hypothetical 
  4017. application program: 
  4018.  
  4019. #include <stdio.h>
  4020. #include <GetOpt.h>
  4021. //...
  4022. int debug_flag, compile_flag, size_in_bytes;
  4023.  
  4024. int
  4025. main (int argc, char **argv)
  4026. {
  4027.   // Invokes ctor `GetOpt (int argc, char **argv,
  4028.   //                       char *optstring);'
  4029.   GetOpt getopt (argc, argv, "dcs:");
  4030.   int option_char;
  4031.  
  4032.   // Invokes member function `int operator ()(void);'
  4033.   while ((option_char = getopt ()) != EOF)
  4034.     switch (option_char)
  4035.       {
  4036.          case 'd': debug_flag = 1; break;
  4037.          case 'c': compile_flag = 1; break;
  4038.          case 's': size_in_bytes = atoi (getopt.optarg); break;
  4039.          case '?': fprintf (stderr,
  4040.                             "usage: %s [dcs<size>]\n", argv[0]);
  4041.       }
  4042. }
  4043.  
  4044. Unlike the C library version, the libg++ GetOpt class uses its constructor to 
  4045. initialize class data members containing the argument count, argument vector, 
  4046. and the option string.  This simplifies the interface for each subsequent call 
  4047. to member function int operator ()(void). 
  4048.  
  4049. The C version, on the other hand, uses hidden static variables to retain the 
  4050. option string and argument list values between calls to getopt.  This 
  4051. complicates the getopt interface since the argument count, argument vector, and 
  4052. option string must be passed as parameters for each invocation.  For the C 
  4053. version, the loop in the previous example becomes: 
  4054.  
  4055.   while ((option_char = getopt (argc, argv, "dcs:")) != EOF)
  4056.     // ...
  4057.  
  4058. which requires extra overhead to pass the parameters for every call. 
  4059.  
  4060. Along with the GetOpt constructor and int operator ()(void), the other relevant 
  4061. elements of class GetOpt are: 
  4062.  
  4063.  char *optarg 
  4064.            Used for communication from operator ()(void) to the caller. When 
  4065.            operator ()(void) finds an option that takes an argument, the 
  4066.            argument value is stored here. 
  4067.  
  4068.  int optind 
  4069.            Index in argv of the next element to be scanned. This is used for 
  4070.            communication to and from the caller and for communication between 
  4071.            successive calls to operator ()(void). 
  4072.  
  4073.            When operator ()(void) returns EOF, this is the index of the first 
  4074.            of the non-option elements that the caller should itself scan. 
  4075.  
  4076.            Otherwise, optind communicates from one call to the next how much of 
  4077.            argv has been scanned so far. 
  4078.  
  4079.  The libg++ version of GetOpt acts like standard UNIX getopt for the calling 
  4080.  routine, but it behaves differently for the user, since it allows the user to 
  4081.  intersperse the options with the other arguments. 
  4082.  
  4083.  As GetOpt works, it permutes the elements of argv so that, when it is done, 
  4084.  all the options precede everything else.  Thus all application programs are 
  4085.  extended to handle flexible argument order. 
  4086.  
  4087.  Setting the environment variable _POSIX_OPTION_ORDER disables permutation. 
  4088.  Then the behavior is completely standard. 
  4089.  
  4090.  
  4091. ΓòÉΓòÉΓòÉ 40. Projects and other things left to do ΓòÉΓòÉΓòÉ
  4092.  
  4093.  
  4094. ΓòÉΓòÉΓòÉ 40.1. Coming Attractions ΓòÉΓòÉΓòÉ
  4095.  
  4096. Some things that will probably be available in libg++ in the near future: 
  4097.  
  4098.      Revamped C-compatibility header files that will be compatible with the 
  4099.       forthcoming (ANSI-based) GNU libc.a 
  4100.  
  4101.      A revision of the File-based classes that will use the GNU stdio library, 
  4102.       and also be 100% compatible (even at the streambuf level) with the AT&T 
  4103.       2.0 stream classes. 
  4104.  
  4105.      Additional container class prototypes. 
  4106.  
  4107.      generic Matrix class prototypes. 
  4108.  
  4109.      A task package probably based on Dirk Grunwald's threads package. 
  4110.  
  4111.  
  4112. ΓòÉΓòÉΓòÉ 40.2. Wish List ΓòÉΓòÉΓòÉ
  4113.  
  4114. Some things that people have mentioned that they would like to see in libg++, 
  4115. but for which there have not been any offers: 
  4116.  
  4117.      A method to automatically convert or incorporate libg++ classes so they 
  4118.       can be used directly in Gorlen's OOPS environment. 
  4119.  
  4120.      A class browser. 
  4121.  
  4122.      A better general exception-handling strategy. 
  4123.  
  4124.      Better documentation. 
  4125.  
  4126.  
  4127. ΓòÉΓòÉΓòÉ 40.3. How to contribute ΓòÉΓòÉΓòÉ
  4128.  
  4129. Programmers who have written C++ classes that they believe to be of general 
  4130. interest are encourage to write to dl at rocky.oswego.edu. Contributing code is 
  4131. not difficult. Here are some general guidelines: 
  4132.  
  4133.      FSF must maintain the right to accept or reject potential contributions. 
  4134.       Generally, the only reasons for rejecting contributions are cases where 
  4135.       they duplicate existing or nearly-released code, contain unremovable 
  4136.       specific machine dependencies, or are somehow incompatible with the rest 
  4137.       of the library. 
  4138.  
  4139.      Acceptance of contributions means that the code is accepted for 
  4140.       adaptation into libg++.  FSF must reserve the right to make various 
  4141.       editorial changes in code. Very often, this merely entails formatting, 
  4142.       maintenance of various conventions, etc. Contributors are always given 
  4143.       authorship credit and shown the final version for approval. 
  4144.  
  4145.      Contributors must assign their copyright to FSF via a form sent out upon 
  4146.       acceptance. Assigning copyright to FSF ensures that the code may be 
  4147.       freely distributed. 
  4148.  
  4149.      Assistance in providing documentation, test files, and debugging support 
  4150.       is strongly encouraged. 
  4151.  
  4152.  Extensions, comments, and suggested modifications of existing libg++ features 
  4153.  are also very welcome.