diff options
Diffstat (limited to 'reference/CPLUSPLUS/CONTRIB/GNU_STDLIB/libgpp.html')
| -rw-r--r-- | reference/CPLUSPLUS/CONTRIB/GNU_STDLIB/libgpp.html | 5110 |
1 files changed, 5110 insertions, 0 deletions
diff --git a/reference/CPLUSPLUS/CONTRIB/GNU_STDLIB/libgpp.html b/reference/CPLUSPLUS/CONTRIB/GNU_STDLIB/libgpp.html new file mode 100644 index 0000000..de8f981 --- /dev/null +++ b/reference/CPLUSPLUS/CONTRIB/GNU_STDLIB/libgpp.html @@ -0,0 +1,5110 @@ +<!-- This HTML file has been created by texi2html 1.27 + from libgpp.texi on 3 March 1994 --> + +<TITLE>to the GNU C++ Library</TITLE> +<H1>to the GNU C++ Library</H1> +<P> +Copyright (C) 1988, 1991, 1992 Free Software Foundation, Inc. +<P> +Permission is granted to make and distribute verbatim copies of +this manual provided the copyright notice and this permission notice +are preserved on all copies. +<P> +Permission is granted to copy and distribute modified versions of this +manual under the conditions for verbatim copying, provided also that the +section entitled "GNU Library General Public License" is included exactly as +in the original, and provided that the entire resulting derived work is +distributed under the terms of a permission notice identical to this one. +<P> +Permission is granted to copy and distribute translations of this manual +into another language, under the above conditions for modified versions, +except that the section entitled "GNU Library General Public License" may be +included in a translation approved by the author instead of in the original +English. +<P> +<STRONG>Note: The GNU C++ library is still in test release. You will +be performing a valuable service if you report any bugs you encounter.</STRONG> +<P> +<H1><A NAME="SEC1" HREF="libgpp_toc.html#SEC1">GNU LIBRARY GENERAL PUBLIC LICENSE</A></H1> +Version 2, June 1991 +<P> +<PRE> +Copyright (C) 1991 Free Software Foundation, Inc. +675 Mass Ave, Cambridge, MA 02139, USA +Everyone is permitted to copy and distribute verbatim copies +of this license document, but changing it is not allowed. + +[This is the first released version of the library GPL. It is + numbered 2 because it goes with version 2 of the ordinary GPL.] +</PRE> +<P> +<H2><A NAME="SEC2" HREF="libgpp_toc.html#SEC2">Preamble</A></H2> +<P> + The licenses for most software are designed to take away your +freedom to share and change it. By contrast, the GNU General Public +Licenses are intended to guarantee your freedom to share and change +free software--to make sure the software is free for all its users. +<P> + This license, the Library General Public License, applies to some +specially designated Free Software Foundation software, and to any +other libraries whose authors decide to use it. You can use it for +your libraries, too. +<P> + When we speak of free software, we are referring to freedom, not +price. Our General Public Licenses are designed to make sure that you +have the freedom to distribute copies of free software (and charge for +this service if you wish), that you receive source code or can get it +if you want it, that you can change the software or use pieces of it +in new free programs; and that you know you can do these things. +<P> + To protect your rights, we need to make restrictions that forbid +anyone to deny you these rights or to ask you to surrender the rights. +These restrictions translate to certain responsibilities for you if +you distribute copies of the library, or if you modify it. +<P> + For example, if you distribute copies of the library, whether gratis +or for a fee, you must give the recipients all the rights that we gave +you. You must make sure that they, too, receive or can get the source +code. If you link a program with the library, you must provide +complete object files to the recipients so that they can relink them +with the library, after making changes to the library and recompiling +it. And you must show them these terms so they know their rights. +<P> + Our method of protecting your rights has two steps: (1) copyright +the library, and (2) offer you this license which gives you legal +permission to copy, distribute and/or modify the library. +<P> + Also, for each distributor's protection, we want to make certain +that everyone understands that there is no warranty for this free +library. If the library is modified by someone else and passed on, we +want its recipients to know that what they have is not the original +version, so that any problems introduced by others will not reflect on +the original authors' reputations. +<P> + Finally, any free program is threatened constantly by software +patents. We wish to avoid the danger that companies distributing free +software will individually obtain patent licenses, thus in effect +transforming the program into proprietary software. To prevent this, +we have made it clear that any patent must be licensed for everyone's +free use or not licensed at all. +<P> + Most GNU software, including some libraries, is covered by the ordinary +GNU General Public License, which was designed for utility programs. This +license, the GNU Library General Public License, applies to certain +designated libraries. This license is quite different from the ordinary +one; be sure to read it in full, and don't assume that anything in it is +the same as in the ordinary license. +<P> + The reason we have a separate public license for some libraries is that +they blur the distinction we usually make between modifying or adding to a +program and simply using it. Linking a program with a library, without +changing the library, is in some sense simply using the library, and is +analogous to running a utility program or application program. However, in +a textual and legal sense, the linked executable is a combined work, a +derivative of the original library, and the ordinary General Public License +treats it as such. +<P> + Because of this blurred distinction, using the ordinary General +Public License for libraries did not effectively promote software +sharing, because most developers did not use the libraries. We +concluded that weaker conditions might promote sharing better. +<P> + However, unrestricted linking of non-free programs would deprive the +users of those programs of all benefit from the free status of the +libraries themselves. This Library General Public License is intended to +permit developers of non-free programs to use free libraries, while +preserving your freedom as a user of such programs to change the free +libraries that are incorporated in them. (We have not seen how to achieve +this as regards changes in header files, but we have achieved it as regards +changes in the actual functions of the Library.) The hope is that this +will lead to faster development of free libraries. +<P> + The precise terms and conditions for copying, distribution and +modification follow. Pay close attention to the difference between a +"work based on the library" and a "work that uses the library". The +former contains code derived from the library, while the latter only +works together with the library. +<P> + Note that it is possible for a library to be covered by the ordinary +General Public License rather than by this special one. +<P> +<H2><A NAME="SEC3" HREF="libgpp_toc.html#SEC3">TERMS AND CONDITIONS FOR COPYING, DISTRIBUTION AND MODIFICATION</A></H2> +<P> +<OL> +<LI> +This License Agreement applies to any software library which +contains a notice placed by the copyright holder or other authorized +party saying it may be distributed under the terms of this Library +General Public License (also called "this License"). Each licensee is +addressed as "you". +<P> + A "library" means a collection of software functions and/or data +prepared so as to be conveniently linked with application programs +(which use some of those functions and data) to form executables. +<P> + The "Library", below, refers to any such software library or work +which has been distributed under these terms. A "work based on the +Library" means either the Library or any derivative work under +copyright law: that is to say, a work containing the Library or a +portion of it, either verbatim or with modifications and/or translated +straightforwardly into another language. (Hereinafter, translation is +included without limitation in the term "modification".) +<P> + "Source code" for a work means the preferred form of the work for +making modifications to it. For a library, complete source code means +all the source code for all modules it contains, plus any associated +interface definition files, plus the scripts used to control compilation +and installation of the library. +<P> + Activities other than copying, distribution and modification are not +covered by this License; they are outside its scope. The act of +running a program using the Library is not restricted, and output from +such a program is covered only if its contents constitute a work based +on the Library (independent of the use of the Library in a tool for +writing it). Whether that is true depends on what the Library does +and what the program that uses the Library does. + +<LI> +You may copy and distribute verbatim copies of the Library's +complete source code as you receive it, in any medium, provided that +you conspicuously and appropriately publish on each copy an +appropriate copyright notice and disclaimer of warranty; keep intact +all the notices that refer to this License and to the absence of any +warranty; and distribute a copy of this License along with the +Library. +<P> + You may charge a fee for the physical act of transferring a copy, +and you may at your option offer warranty protection in exchange for a +fee. +<P> +<LI> +You may modify your copy or copies of the Library or any portion +of it, thus forming a work based on the Library, and copy and +distribute such modifications or work under the terms of Section 1 +above, provided that you also meet all of these conditions: +<P> +<OL> +<LI> +The modified work must itself be a software library. +<P> +<LI> +You must cause the files modified to carry prominent notices +stating that you changed the files and the date of any change. +<P> +<LI> +You must cause the whole of the work to be licensed at no +charge to all third parties under the terms of this License. +<P> +<LI> +If a facility in the modified Library refers to a function or a +table of data to be supplied by an application program that uses +the facility, other than as an argument passed when the facility +is invoked, then you must make a good faith effort to ensure that, +in the event an application does not supply such function or +table, the facility still operates, and performs whatever part of +its purpose remains meaningful. +<P> +(For example, a function in a library to compute square roots has +a purpose that is entirely well-defined independent of the +application. Therefore, Subsection 2d requires that any +application-supplied function or table used by this function must +be optional: if the application does not supply it, the square +root function must still compute square roots.) +</OL> +<P> +These requirements apply to the modified work as a whole. If +identifiable sections of that work are not derived from the Library, +and can be reasonably considered independent and separate works in +themselves, then this License, and its terms, do not apply to those +sections when you distribute them as separate works. But when you +distribute the same sections as part of a whole which is a work based +on the Library, the distribution of the whole must be on the terms of +this License, whose permissions for other licensees extend to the +entire whole, and thus to each and every part regardless of who wrote +it. +<P> +Thus, it is not the intent of this section to claim rights or contest +your rights to work written entirely by you; rather, the intent is to +exercise the right to control the distribution of derivative or +collective works based on the Library. +<P> +In addition, mere aggregation of another work not based on the Library +with the Library (or with a work based on the Library) on a volume of +a storage or distribution medium does not bring the other work under +the scope of this License. +<P> +<LI> +You may opt to apply the terms of the ordinary GNU General Public +License instead of this License to a given copy of the Library. To do +this, you must alter all the notices that refer to this License, so +that they refer to the ordinary GNU General Public License, version 2, +instead of to this License. (If a newer version than version 2 of the +ordinary GNU General Public License has appeared, then you can specify +that version instead if you wish.) Do not make any other change in +these notices. +<P> + Once this change is made in a given copy, it is irreversible for +that copy, so the ordinary GNU General Public License applies to all +subsequent copies and derivative works made from that copy. +<P> + This option is useful when you wish to copy part of the code of +the Library into a program that is not a library. +<P> +<LI> +You may copy and distribute the Library (or a portion or +derivative of it, under Section 2) in object code or executable form +under the terms of Sections 1 and 2 above provided that you accompany +it with the complete corresponding machine-readable source code, which +must be distributed under the terms of Sections 1 and 2 above on a +medium customarily used for software interchange. +<P> + If distribution of object code is made by offering access to copy +from a designated place, then offering equivalent access to copy the +source code from the same place satisfies the requirement to +distribute the source code, even though third parties are not +compelled to copy the source along with the object code. +<P> +<LI> +A program that contains no derivative of any portion of the +Library, but is designed to work with the Library by being compiled or +linked with it, is called a "work that uses the Library". Such a +work, in isolation, is not a derivative work of the Library, and +therefore falls outside the scope of this License. +<P> + However, linking a "work that uses the Library" with the Library +creates an executable that is a derivative of the Library (because it +contains portions of the Library), rather than a "work that uses the +library". The executable is therefore covered by this License. +Section 6 states terms for distribution of such executables. +<P> + When a "work that uses the Library" uses material from a header file +that is part of the Library, the object code for the work may be a +derivative work of the Library even though the source code is not. +Whether this is true is especially significant if the work can be +linked without the Library, or if the work is itself a library. The +threshold for this to be true is not precisely defined by law. +<P> + If such an object file uses only numerical parameters, data +structure layouts and accessors, and small macros and small inline +functions (ten lines or less in length), then the use of the object +file is unrestricted, regardless of whether it is legally a derivative +work. (Executables containing this object code plus portions of the +Library will still fall under Section 6.) +<P> + Otherwise, if the work is a derivative of the Library, you may +distribute the object code for the work under the terms of Section 6. +Any executables containing that work also fall under Section 6, +whether or not they are linked directly with the Library itself. +<P> +<LI> +As an exception to the Sections above, you may also compile or +link a "work that uses the Library" with the Library to produce a +work containing portions of the Library, and distribute that work +under terms of your choice, provided that the terms permit +modification of the work for the customer's own use and reverse +engineering for debugging such modifications. +<P> + You must give prominent notice with each copy of the work that the +Library is used in it and that the Library and its use are covered by +this License. You must supply a copy of this License. If the work +during execution displays copyright notices, you must include the +copyright notice for the Library among them, as well as a reference +directing the user to the copy of this License. Also, you must do one +of these things: +<P> +<OL> +<LI> +Accompany the work with the complete corresponding +machine-readable source code for the Library including whatever +changes were used in the work (which must be distributed under +Sections 1 and 2 above); and, if the work is an executable linked +with the Library, with the complete machine-readable "work that +uses the Library", as object code and/or source code, so that the +user can modify the Library and then relink to produce a modified +executable containing the modified Library. (It is understood +that the user who changes the contents of definitions files in the +Library will not necessarily be able to recompile the application +to use the modified definitions.) +<P> +<LI> +Accompany the work with a written offer, valid for at +least three years, to give the same user the materials +specified in Subsection 6a, above, for a charge no more +than the cost of performing this distribution. +<P> +<LI> +If distribution of the work is made by offering access to copy +from a designated place, offer equivalent access to copy the above +specified materials from the same place. +<P> +<LI> +Verify that the user has already received a copy of these +materials or that you have already sent this user a copy. +</OL> +<P> + For an executable, the required form of the "work that uses the +Library" must include any data and utility programs needed for +reproducing the executable from it. However, as a special exception, +the source code distributed need not include anything that is normally +distributed (in either source or binary form) with the major +components (compiler, kernel, and so on) of the operating system on +which the executable runs, unless that component itself accompanies +the executable. +<P> + It may happen that this requirement contradicts the license +restrictions of other proprietary libraries that do not normally +accompany the operating system. Such a contradiction means you cannot +use both them and the Library together in an executable that you +distribute. +<P> +<LI> +You may place library facilities that are a work based on the +Library side-by-side in a single library together with other library +facilities not covered by this License, and distribute such a combined +library, provided that the separate distribution of the work based on +the Library and of the other library facilities is otherwise +permitted, and provided that you do these two things: +<P> +<OL> +<LI> +Accompany the combined library with a copy of the same work +based on the Library, uncombined with any other library +facilities. This must be distributed under the terms of the +Sections above. +<P> +<LI> +Give prominent notice with the combined library of the fact +that part of it is a work based on the Library, and explaining +where to find the accompanying uncombined form of the same work. +</OL> +<P> +<LI> +You may not copy, modify, sublicense, link with, or distribute +the Library except as expressly provided under this License. Any +attempt otherwise to copy, modify, sublicense, link with, or +distribute the Library is void, and will automatically terminate your +rights under this License. However, parties who have received copies, +or rights, from you under this License will not have their licenses +terminated so long as such parties remain in full compliance. +<P> +<LI> +You are not required to accept this License, since you have not +signed it. However, nothing else grants you permission to modify or +distribute the Library or its derivative works. These actions are +prohibited by law if you do not accept this License. Therefore, by +modifying or distributing the Library (or any work based on the +Library), you indicate your acceptance of this License to do so, and +all its terms and conditions for copying, distributing or modifying +the Library or works based on it. +<P> +<LI> +Each time you redistribute the Library (or any work based on the +Library), the recipient automatically receives a license from the +original licensor to copy, distribute, link with or modify the Library +subject to these terms and conditions. You may not impose any further +restrictions on the recipients' exercise of the rights granted herein. +You are not responsible for enforcing compliance by third parties to +this License. +<P> +<LI> +If, as a consequence of a court judgment or allegation of patent +infringement or for any other reason (not limited to patent issues), +conditions are imposed on you (whether by court order, agreement or +otherwise) that contradict the conditions of this License, they do not +excuse you from the conditions of this License. If you cannot +distribute so as to satisfy simultaneously your obligations under this +License and any other pertinent obligations, then as a consequence you +may not distribute the Library at all. For example, if a patent +license would not permit royalty-free redistribution of the Library by +all those who receive copies directly or indirectly through you, then +the only way you could satisfy both it and this License would be to +refrain entirely from distribution of the Library. +<P> +If any portion of this section is held invalid or unenforceable under any +particular circumstance, the balance of the section is intended to apply, +and the section as a whole is intended to apply in other circumstances. +<P> +It is not the purpose of this section to induce you to infringe any +patents or other property right claims or to contest validity of any +such claims; this section has the sole purpose of protecting the +integrity of the free software distribution system which is +implemented by public license practices. Many people have made +generous contributions to the wide range of software distributed +through that system in reliance on consistent application of that +system; it is up to the author/donor to decide if he or she is willing +to distribute software through any other system and a licensee cannot +impose that choice. +<P> +This section is intended to make thoroughly clear what is believed to +be a consequence of the rest of this License. +<P> +<LI> +If the distribution and/or use of the Library is restricted in +certain countries either by patents or by copyrighted interfaces, the +original copyright holder who places the Library under this License may add +an explicit geographical distribution limitation excluding those countries, +so that distribution is permitted only in or among countries not thus +excluded. In such case, this License incorporates the limitation as if +written in the body of this License. +<P> +<LI> +The Free Software Foundation may publish revised and/or new +versions of the Library General Public License from time to time. +Such new versions will be similar in spirit to the present version, +but may differ in detail to address new problems or concerns. +<P> +Each version is given a distinguishing version number. If the Library +specifies a version number of this License which applies to it and +"any later version", you have the option of following the terms and +conditions either of that version or of any later version published by +the Free Software Foundation. If the Library does not specify a +license version number, you may choose any version ever published by +the Free Software Foundation. +<P> +<LI> +If you wish to incorporate parts of the Library into other free +programs whose distribution conditions are incompatible with these, +write to the author to ask for permission. For software which is +copyrighted by the Free Software Foundation, write to the Free +Software Foundation; we sometimes make exceptions for this. Our +decision will be guided by the two goals of preserving the free status +of all derivatives of our free software and of promoting the sharing +and reuse of software generally. +<P> +<H2>NO WARRANTY</H2> +<P> +<LI> +BECAUSE THE LIBRARY IS LICENSED FREE OF CHARGE, THERE IS NO +WARRANTY FOR THE LIBRARY, TO THE EXTENT PERMITTED BY APPLICABLE LAW. +EXCEPT WHEN OTHERWISE STATED IN WRITING THE COPYRIGHT HOLDERS AND/OR +OTHER PARTIES PROVIDE THE LIBRARY "AS IS" WITHOUT WARRANTY OF ANY +KIND, EITHER EXPRESSED OR IMPLIED, INCLUDING, BUT NOT LIMITED TO, THE +IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR +PURPOSE. THE ENTIRE RISK AS TO THE QUALITY AND PERFORMANCE OF THE +LIBRARY IS WITH YOU. SHOULD THE LIBRARY PROVE DEFECTIVE, YOU ASSUME +THE COST OF ALL NECESSARY SERVICING, REPAIR OR CORRECTION. +<P> +<LI> +IN NO EVENT UNLESS REQUIRED BY APPLICABLE LAW OR AGREED TO IN +WRITING WILL ANY COPYRIGHT HOLDER, OR ANY OTHER PARTY WHO MAY MODIFY +AND/OR REDISTRIBUTE THE LIBRARY AS PERMITTED ABOVE, BE LIABLE TO YOU +FOR DAMAGES, INCLUDING ANY GENERAL, SPECIAL, INCIDENTAL OR +CONSEQUENTIAL DAMAGES ARISING OUT OF THE USE OR INABILITY TO USE THE +LIBRARY (INCLUDING BUT NOT LIMITED TO LOSS OF DATA OR DATA BEING +RENDERED INACCURATE OR LOSSES SUSTAINED BY YOU OR THIRD PARTIES OR A +FAILURE OF THE LIBRARY TO OPERATE WITH ANY OTHER SOFTWARE), EVEN IF +SUCH HOLDER OR OTHER PARTY HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH +DAMAGES. +</OL> +<P> +<H2>END OF TERMS AND CONDITIONS</H2> +<P> +<H2><A NAME="SEC4" HREF="libgpp_toc.html#SEC4">How to Apply These Terms to Your New Libraries</A></H2> +<P> + If you develop a new library, and you want it to be of the greatest +possible use to the public, we recommend making it free software that +everyone can redistribute and change. You can do so by permitting +redistribution under these terms (or, alternatively, under the terms of the +ordinary General Public License). +<P> + To apply these terms, attach the following notices to the library. It is +safest to attach them to the start of each source file to most effectively +convey the exclusion of warranty; and each file should have at least the +"copyright" line and a pointer to where the full notice is found. +<P> +<PRE> +<VAR>one line to give the library's name and an idea of what it does.</VAR> +Copyright (C) <VAR>year</VAR> <VAR>name of author</VAR> + +This library is free software; you can redistribute it and/or +modify it under the terms of the GNU Library General Public +License as published by the Free Software Foundation; either +version 2 of the License, or (at your option) any later version. + +This library is distributed in the hope that it will be useful, +but WITHOUT ANY WARRANTY; without even the implied warranty of +MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU +Library General Public License for more details. + +You should have received a copy of the GNU Library General Public +License along with this library; if not, write to the +Free Software Foundation, Inc., 675 Mass Ave, Cambridge, +MA 02139, USA. +</PRE> +<P> +Also add information on how to contact you by electronic and paper mail. +<P> +You should also get your employer (if you work as a programmer) or your +school, if any, to sign a "copyright disclaimer" for the library, if +necessary. Here is a sample; alter the names: +<P> +<PRE> +Yoyodyne, Inc., hereby disclaims all copyright interest in +the library `Frob' (a library for tweaking knobs) written +by James Random Hacker. + +<VAR>signature of Ty Coon</VAR>, 1 April 1990 +Ty Coon, President of Vice +</PRE> +<P> +That's all there is to it! +<P> +<H1><A NAME="SEC5" HREF="libgpp_toc.html#SEC5">Contributors to GNU C++ library</A></H1> +<P> +Aside from Michael Tiemann, who worked out the front end for GNU C++, and +Richard Stallman, who worked out the back end, the following people (not +including those who have made their contributions to GNU CC) should not go +unmentioned. +<P> +<UL> +<LI> +Doug Lea contributed most otherwise unattributed classes. +<P> +<LI> +Per Bothner contributed the iostream I/O classes. +<P> +<LI> +Dirk Grunwald contributed the Random number generation classes, +and PairingHeaps. +<P> +<LI> +Kurt Baudendistel contributed Fixed precision reals. +<P> +<LI> +Doug Schmidt contributed ordered hash tables, a perfect +hash function generator, and several other utilities. +<P> +<LI> +Marc Shapiro contributed the ideas and preliminary code for Plexes. +<P> +<LI> +Eric Newton contributed the curses window classes. +<P> +<LI> +Some of the I/O code is derived from BSD 4.4, +and was developed by the University of California, Berkeley. +<P> +<LI> +The code for converting accurately between floating point numbers +and their string representations was written by David M. Gay of AT&T. +</UL> +<P> +<H1><A NAME="SEC6" HREF="libgpp_toc.html#SEC6">Installing GNU C++ library</A></H1> +<P> +<OL> +<LI> +Read through the README file and the Makefile. Make sure that all +paths, system-dependent compile switches, and program names are correct. +<P> +<LI> +Check that files <TT>`values.h'</TT>, <TT>`stdio.h'</TT>, +and <TT>`math.h'</TT> declare and define values appropriate for your +system. +<P> +<LI> +Type <SAMP>`make all'</SAMP> to compile the library, test, and install. +Current details about contents of the tests and utilities are in the +<TT>`README'</TT> file. +<P> +</OL> +<P> +<H1><A NAME="SEC7" HREF="libgpp_toc.html#SEC7">Trouble in Installation</A></H1> +<P> +Here are some of the things that have caused trouble for people installing +GNU C++ library. +<P> +<OL> +<LI> +Make sure that your GNU C++ version number is at least as high as your +libg++ version number. For example, libg++ 1.22.0 requires g++ 1.22.0 or +later releases. +<P> +<LI> +Double-check system constants in the header files mentioned above. +<P> +</OL> +<P> +<H1><A NAME="SEC8" HREF="libgpp_toc.html#SEC8">GNU C++ library aims, objectives, and limitations</A></H1> +<P> +The GNU C++ library, libg++ is an attempt to provide a variety of C++ +programming tools and other support to GNU C++ programmers. +<P> +Differences in distribution policy are only part of the difference +between libg++.a and AT&T libC.a. libg++ is not intended to be an +exact clone of libC. For one, libg++ contains bits of code that depend +on special features of GNU g++ that are either different or lacking in +the AT&T version, including slightly different inlining and overloading +strategies, dynamic local arrays, etc. All of these +differences are minor. For example, while the AT&T and GNU stream +classes are implemented in very different ways, the vast majority of +C++ programs compile and run under either version with no visible +difference. Additionally, all g++-specific constructs are conditionally +compiled; The library is designed to be compatible with any 2.0 C++ +compiler. +<P> +libg++ has also contained workarounds for some limitations in g++: both +g++ and libg++ are still undergoing rapid development and testing--a +task that is helped tremendously by the feedback of active users. This +manual is also still under development; it has some catching up to do +to include all the facilities now in the library. +<P> +libg++ is not the only freely available source of C++ class libraries. +Some notable alternative sources are Interviews and NIHCL. +(InterViews has been available on the X-windows X11 tapes and also +from interviews.stanford.edu. NIHCL is available by anonymous +ftp from GNU archives (such as the pub directory of prep.ai.mit.edu), +although it is not supported by the FSF - and needs some work +before it will work with g++.) +<P> +As every C++ programmer knows, the design (moreso than the +implementation) of a C++ class library is something of a challenge. +Part of the reason is that C++ supports two, partially incompatible, +styles of object-oriented programming -- The "forest" approach, +involving a collection of free-standing classes that can be mixed and +matched, versus the completely hierarchical (smalltalk style) +approach, in which all classes are derived from a common ancestor. Of +course, both styles have advantages and disadvantages. So far, libg++ +has adopted the "forest" approach. Keith Gorlen's OOPS library adopts +the hierarchical approach, and may be an attractive alternative for C++ +programmers who prefer this style. +<P> +Currently (and/or in the near future) libg++ provides support for a +few basic kinds of classes: +<P> +The first kind of support provides an interface between C++ programs and +C libraries. This includes basic header files (like <TT>`stdio.h'</TT>) as +well as things like the File and stream classes. Other classes that +interface to other aspects of C libraries (like those that maintain +environmental information) are in various stages of development; all +will undergo implementation modifications when the forthcoming GNU libc +library is released. +<P> +The second kind of support contains general-purpose basic classes that +transparently manage variable-sized objects on the freestore. This +includes Obstacks, multiple-precision Integers and Rationals, +arbitrary length Strings, BitSets, and BitStrings. +<P> +Third, several classes and utilities of common interest (e.g., +Complex numbers) are provided. +<P> +Fourth, a set of pseudo-generic prototype files are available +as a mechanism for generating common container classes. These +are described in more detail in the introduction to container +prototypes. Currently, only a textual substitution +mechanism is available for generic class creation. +<P> +<H1><A NAME="SEC9" HREF="libgpp_toc.html#SEC9">GNU C++ library stylistic conventions</A></H1> +<P> +<UL> +<P> +<LI> +C++ source files have file extension <TT>`.cc'</TT>. Both C-compatibility +header files and class declaration files have extension <TT>`.h'</TT>. +<P> +<LI> +C++ class names begin with capital letters, except for <CODE>istream</CODE> +and <CODE>ostream</CODE>, for AT&T C++ compatibility. Multi-word class +names capitalize each word, with no underscore separation. +<P> +<LI> +Include files that define C++ classes begin with capital letters +(as do the names of the classes themselves). <TT>`stream.h'</TT> is +uncapitalized for AT&T C++ compatibility. +<P> +<LI> +Include files that supply function prototypes for other C +functions (system calls and libraries) are all lower case. +<P> +<LI> +All include files define a preprocessor variable _X_h, where X +is the name of the file, and conditionally compile only if this +has not been already defined. The <CODE>#pragma once</CODE> facility +is also used to avoid re-inclusion. +<P> +<LI> +Structures and objects that must be publicly defined, +but are not intended for public use have names beginning +with an underscore. (for example, the <CODE>_Srep</CODE> struct, which +is used only by the String and SubString classes.) +<P> +<LI> +The underscore is used to separate components of long function +names, <BR>e.g., <CODE>set_File_exception_handler()</CODE>. +<P> +<LI> +When a function could be usefully defined either as a +member or a friend, it is generally a member if it modifies +and/or returns itself, else it is a friend. There are cases +where naturalness of expression wins out over this rule. +<P> +<LI> +Class declaration files are formatted so that it is easy +to quickly check them to determine function names, parameters, +and so on. Because of the different kinds of things that may +appear in class declarations, there is no perfect way to do +this. Any suggestions on developing a common class +declaration formatting style are welcome. +<P> +<LI> +All classes use the same simple error (exception) handling strategy. +Almost every class has a member function named <CODE>error(char* msg)</CODE> +that invokes an associated error handler function via a pointer to that +function, so that the error handling function may be reset by +programmers. By default nearly all call <CODE>*lib_error_handler</CODE>, which +prints the message and then aborts execution. This system is subject +to change. In general, errors are assumed to be non-recoverable: +Library classes do not include code that allows graceful continuation +after exceptions. +<P> +</UL> +<P> +<H1><A NAME="SEC10" HREF="libgpp_toc.html#SEC10">Support for representation invariants</A></H1> +<P> +Most GNU C++ library classes possess a method named <CODE>OK()</CODE>, +that is useful in helping to verify correct performance of class +operations. +<P> +The <CODE>OK()</CODE> operations checks the "representation invariant" of a +class object. This is a test to check whether the object is in a valid +state. In effect, it is a (sometimes partial) verification of the +library's promise that (1) class operations always leave objects in +valid states, and (2) the class protects itself so that client functions +cannot corrupt this state. +<P> +While no simple validation technique can assure that all operations +perform correctly, calls to <CODE>OK()</CODE> can at least verify that +operations do not corrupt representations. For example for <CODE>String +a, b, c; ... a = b + c;</CODE>, a call to <CODE>a.OK();</CODE> will guarantee that +<CODE>a</CODE> is a valid <CODE>String</CODE>, but does not guarantee that it +contains the concatenation of <CODE>b + c</CODE>. However, given that <CODE>a</CODE> +is known to be valid, it is possible to further verify its properties, +for example via <CODE>a.after(b) == c && a.before(c) == b</CODE>. In other +words, <CODE>OK()</CODE> generally checks only those internal representation +properties that are otherwise inaccessible to users of the class. Other +class operations are often useful for further validation. +<P> +Failed calls to <CODE>OK()</CODE> call a class's <CODE>error</CODE> method if +one exists, else directly call <CODE>abort</CODE>. Failure indicates +an implementation error that should be reported. +<P> +With only rare exceptions, the internal support functions for a class +never themselves call <CODE>OK()</CODE> (although many of the test files +in the distribution call <CODE>OK()</CODE> extensively). +<P> +Verification of representational invariants can sometimes be +very time consuming for complicated data structures. +<P> +<H1><A NAME="SEC11" HREF="libgpp_toc.html#SEC11">Introduction to container class prototypes</A></H1> +<P> +As a temporary mechanism enabling the support of generic classes, the GNU +C++ Library distribution contains a directory (<TT>`g++-include'</TT>) of files +designed to serve as the basis for generating container classes of +specified elements. These files can be used to generate <TT>`.h'</TT> and +<TT>`.cc'</TT> files in the current directory via a supplied shell script +program that performs simple textual substitution to create specific +classes. +<P> +While these classes are generated independently, and thus share no code, +it is possible to create versions that do share code among subclasses. For +example, using <CODE>typedef void* ent</CODE>, and then generating a +<CODE>entList</CODE> class, other derived classes could be created using the +<CODE>void*</CODE> coercion method described in Stroustrup, pp204-210. +<P> +This very simple class-generation facility is useful enough to serve +current purposes, but will be replaced with a more coherent mechanism for +handling C++ generics in a way that minimally disrupts current usage. +Without knowing exactly when or how parametric classes might be +added to the C++ language, provision of this simplest possible +mechanism, textual substitution, appears to be the safest strategy, +although it does require certain redundancies and awkward constructions. +<P> +Specific classes may be generated via the <TT>`genclass'</TT> shell script +program. This program has arguments specifying the kinds of base types(s) +to be used. Specifying base types requires two arguments. The first is the +name of the base type, which may be any named type, like <CODE>int</CODE> or +<CODE>String</CODE>. Only named types are supported; things like <CODE>int*</CODE> are +not accepted. However, pointers like this may be used by supplying the +appropriate typedefs (e.g., editing the resulting files to include +<CODE>typedef int* intp;</CODE>). The type name must be followed by one of the +words <CODE>val</CODE> or <CODE>ref</CODE>, to indicate whether the base elements +should be passed to functions by-value or by-reference. +<P> +You can specify basic container classes using <CODE>genclass base +[val,ref] proto</CODE>, where <CODE>proto</CODE> is the name of the class being +generated. Container classes like dictionaries and maps that require +two types may be specified via <CODE>genclass -2 keytype [val, ref], +basetype [val, ref] proto</CODE>, where the key type is specified first and +the contents type second. The resulting classnames and filenames are +generated by prepending the specified type names to the prototype names, +and separating the filename parts with dots. For example, +<CODE>genclass int val List</CODE> generates class <CODE>intList</CODE> residing in +files <TT>`int.List.h'</TT> and <TT>`int.List.cc'</TT>. <CODE>genclass -2 String +ref int val VHMap</CODE> generates (the awkward, but unavoidable) class name +<CODE>StringintVHMap</CODE>. Of course, programmers may use <CODE>typedef</CODE> or +simple editing to create more appropriate names. The existence of dot +seperators in file names allows the use of GNU make to help automate +configuration and recompilation. An example Makefile exploiting such +capabilities may be found in the <TT>`libg++/proto-kit'</TT> directory. +<P> +The <CODE>genclass</CODE> utility operates via simple text substitution using +<CODE>sed</CODE>. All occurrences of the pseudo-types <CODE><T></CODE> and <CODE><C></CODE> +(if there are two types) are replaced with the indicated type, and +occurrences of <CODE><T&></CODE> and <CODE><C&></CODE> are replaced by just the types, +if <CODE>val</CODE> is specified, or types followed by "&" if <CODE>ref</CODE> is +specified. +<P> +Programmers will frequently need to edit the <TT>`.h'</TT> file in order to +insert additional <CODE>#include</CODE> directives or other modifications. A +simple utility, <TT>`prepend-header'</TT> to prepend other <TT>`.h'</TT> files +to generated files is provided in the distribution. +<P> +One dubious virtue of the prototyping mechanism is that, because sources files, +not archived library classes, are generated, it is relatively simple for +programmers to modify container classes in the common case where slight +variations of standard container classes are required. +<P> +It is often a good idea for programmers to archive (via <CODE>ar</CODE>) +generated classes into <TT>`.a'</TT> files so that only those class +functions actually used in a given application will be loaded. +The test subdirectory of the distribution shows an example of this. +<P> +Because of <CODE>#pragma interface</CODE> directives, the <TT>`.cc'</TT> files +should be compiled with <CODE>-O</CODE> or <CODE>-DUSE_LIBGXX_INLINES</CODE> +enabled. +<P> +Many container classes require specifications over and above the base +class type. For example, classes that maintain some kind of ordering of +elements require specification of a comparison function upon which to +base the ordering. This is accomplished via a prototype file +<TT>`defs.hP'</TT> that contains macros for these functions. While these +macros default to perform reasonable actions, they can and should be +changed in particular cases. Most prototypes require only one or a few +of these. No harm is done if unused macros are defined to perform +nonsensical actions. The macros are: +<P> +<DL COMPACT> +<P> +<DT><CODE>DEFAULT_INITIAL_CAPACITY</CODE> +<DD>The initial capacity for containers (e.g., hash tables) that require +an initial capacity argument for constructors. +Default: 100 +<P> +<DT><CODE><T>EQ(a, b)</CODE> +<DD>return true if a is considered equal to b for the purposes of +locating, etc., an element in a container. +Default: (a == b) +<P> +<DT><CODE><T>LE(a, b)</CODE> +<DD>return true if a is less than or equal to b +Default: (a <= b) +<P> +<DT><CODE><T>CMP(a, b)</CODE> +<DD>return an integer < 0 if a<b, 0 if a==b, or > 0 if a>b. +Default: (a <= b)? (a==b)? 0 : -1 : 1 +<P> +<DT><CODE><T>HASH(a)</CODE> +<DD>return an unsigned integer representing the hash of a. +Default: hash(a) ; where extern unsigned int hash(<T&>). +(note: several useful hash functions are declared in builtin.h +and defined in hash.cc) +<P> +</DL> +<P> +Nearly all prototypes container classes support container +traversal via <CODE>Pix</CODE> pseudo indices, as described elsewhere. +<P> +All object containers must perform either a <CODE>X::X(X&)</CODE> (or +<CODE>X::X()</CODE> followed by <CODE>X::operator =(X&)</CODE>) to copy objects into +containers. (The latter form is used for containers built from C++ +arrays, like <CODE>VHSets</CODE>). When containers are destroyed, they invoke +<CODE>X::~X()</CODE>. Any objects used in containers must have well behaved +constructors and destructors. If you want to create containers that +merely reference (point to) objects that reside elsewhere, and are not +copied or destroyed inside the container, you must use containers +of pointers, not containers of objects. +<P> +All prototypes are designed to generate <EM>HOMOGENOUS</EM> container +classes. There is no universally applicable method in C++ to support +heterogenous object collections with elements of various subclasses of +some specified base class. The only way to get heterogenous structures +is to use collections of pointers-to-objects, not collections of objects +(which also requires you to take responsibility for managing storage for +the objects pointed to yourself). +<P> +For example, the following usage illustrates a commonly encountered +danger in trying to use container classes for heterogenous structures: +<P> +<PRE> +class Base { int x; ...} +class Derived : public Base { int y; ... } + +BaseVHSet s; // class BaseVHSet generated via something like + // `genclass Base ref VHSet' + +void f() +{ + Base b; + s.add(b); // OK + + Derived d; + s.add(d); // (CHOP!) +} +</PRE> +<P> +At the line flagged with <SAMP>`(CHOP!)'</SAMP>, a <CODE>Base::Base(Base&)</CODE> is +called inside <CODE>Set::add(Base&)</CODE>---<EM>not</EM> +<CODE>Derived::Derived(Derived&)</CODE>. Actually, in <CODE>VHSet</CODE>, a +<CODE>Base::operator =(Base&)</CODE>, is used instead to place the element in +an array slot, but with the same effect. So only the Base part is +copied as a <CODE>VHSet</CODE> element (a so-called chopped-copy). In this +case, it has an <CODE>x</CODE> part, but no <CODE>y</CODE> part; and a Base, not +Derived, vtable. Objects formed via chopped copies are rarely +sensible.<P> +To avoid this, you must resort to pointers: +<P> +<PRE> +typedef Base* BasePtr; + +BasePtrVHSet s; // class BaseVHSet generated via something like + // `genclass BasePtr val VHSet' + +void f() +{ + Base* bp = new Base; + s.add(b); + + Base* dp = new Derived; + s.add(d); // works fine. + + // Don't forget to delete bp and dp sometime. + // The VHSet won't do this for you. +} +</PRE> +<P> +<H2><A NAME="SEC12" HREF="libgpp_toc.html#SEC12">Example</A></H2> +<P> +The prototypes can be difficult to use on first attempt. Here is an +example that may be helpful. The utilities in the <TT>`proto-kit'</TT> +simplify much of the actions described, but are not used here. +<P> +Suppose you create a class <CODE>Person</CODE>, and want to make an Map that +links the social security numbers associated with each person. You start +off with a file <TT>`Person.h'</TT> +<P> +<PRE> + +#include <String.h> + +class Person +{ + String nm; + String addr; + //... +public: + const String& name() { return nm; } + const String& address() { return addr; } + void print() { ... } + //... +} + +</PRE> +<P> +And in file <TT>`SSN.h'</TT>, +<P> +<PRE> +typedef unsigned int SSN; +</PRE> +<P> +Your first decision is what storage/usage strategy to use. There are +several reasonable alternatives here: You might create an "object +collection" of Persons, a "pointer collection" of +pointers-to-Persons, or even a simple String map, housing either copies +of pointers to the names of Persons, since other fields are unused for +purposes of the Map. In an object collection, instances of class Person +"live" inside the Map, while in a pointer collection, the instances +live elsewhere. Also, as above, if instances of subclasses of Person are +to be used inside the Map, you must use pointers. In a String Map, the +same difference holds, but now only for the name fields. Any of these +choices might make sense in particular applications. +<P> +The second choice is the Map implementation strategy. Either a tree +or a hash table might make sense. Suppose you want an AVL tree Map. +There are two things to now check. First, as an object collection, +the AVLMap requires that the elsement class contain an <CODE>X(X&)</CODE> +constructor. In C++, if you don't specify such a constructor, one +is constructed for you, but it is a very good idea to always do this +yourself, to avoid surprises. In this example, you'd use something like +<PRE> +class Person +{ ...; + Person(const Person& p) :nm(p.nm), addr(p.addr) {} +}; +</PRE> +<P> +Also, an AVLMap requires a comparison function for elements in order +to maintain order. Rather than requiring you to write a particular +comparison function, a <TT>`defs'</TT> file is consulted to determine how to +compare items. You must create and edit such a file. +<P> +Before creating <TT>`Person.defs.h'</TT>, you must first make one additional +decision. Should the Map member functions like <CODE>m.contains(p)</CODE> +take arguments (<CODE>p</CODE>) by reference (i.e., typed as +<CODE>int Map::contains(const Person& p)</CODE> or by value (i.e., typed as +<CODE>int Map::contains(const Person p)</CODE>. Generally, for user-defined +classes, you want to pass by reference, and for builtins and pointers, +to pass by value. SO you should pick by-reference. +<P> +You can now create <TT>`Person.defs.h'</TT> via <CODE>genclass Person ref defs</CODE>. +This creates a simple skeleton that you must edit. First, add +<CODE>#include "Person.h"</CODE> to the top. Second, edit the <CODE><T>CMP(a,b)</CODE> +macro to compare on name, via +<P> +<PRE> +#define <T>CMP(a, b) ( compare(a.name(), b.name()) ) +</PRE> +<P> +which invokes the <CODE>int compare(const String&, const String&)</CODE> +function from <TT>`String.h'</TT>. Of course, you could define this in any +other way as well. In fact, the default versions in the skeleton turn +out to be OK (albeit inefficient) in this particular example. +<P> +You may also want to create file <TT>`SSN.defs.h'</TT>. Here, choosing +call-by-value makes sense, and since no other capabilities (like +comparison functions) of the SSNs are used (and the defaults are OK +anyway), you'd type +<P> +<PRE> +genclass SSN val defs +</PRE> +<P> +and then edit to place <CODE>#include "SSN.h"</CODE> at the top. +<P> +Finally, you can generate the classes. First, generate the base +class for Maps via +<P> +<PRE> +genclass -2 Person ref SSN val Map +</PRE> +<P> +This generates only the abstract class, not the implementation, in file +<TT>`Person.SSN.Map.h'</TT> and <TT>`Person.SSN.Map.cc'</TT>. To create the +AVL implementation, type +<P> +<PRE> +genclass -2 Person ref SSN val AVLMap +</PRE> +<P> +This creates the class <CODE>PersonSSNAVLMap</CODE>, in +<TT>`Person.SSN.AVLMap.h'</TT> and <TT>`Person.SSN.AVLMap.cc'</TT>. +<P> +To use the AVL implementation, compile the two generated <TT>`.cc'</TT> files, and +specify <SAMP>`#include "Person.SSN.AVLMap.h"'</SAMP> in the application program. +All other files are included in the right ways automatically. +<P> +One last consideration, peculiar to Maps, is to pick a reasonable +default contents when declaring an AVLMap. Zero might be appropriate +here, so you might declare a Map, +<P> +<PRE> +PersonSSNAVLMap m((SSN)0); +</PRE> +<P> +Suppose you wanted a <CODE>VHMap</CODE> instead of an <CODE>AVLMap</CODE> Besides +generating different implementations, there are two differences in +how you should prepare the <TT>`defs'</TT> file. First, because a VHMap +uses a C++ array internally, and because C++ array slots are initialized +differently than single elements, you must ensure that class Person +contains (1) a no-argument constructor, and (2) an assignment operator. +You could arrange this via +<P> +<PRE> +class Person +{ ...; + Person() {} + void operator = (const Person& p) { nm = p.nm; addr = p.addr; } +}; +</PRE> +<P> +(The lack of action in the constructor is OK here because <CODE>Strings</CODE> +possess usable no-argument constructors.) +<P> +You also need to edit <TT>`Person.defs.h'</TT> to indicate a usable hash +function and default capacity, via something like +<P> +<PRE> +#include <builtin.h> +#define <T>HASH(x) (hashpjw(x.name().chars())) +#define DEFAULT_INITIAL_CAPACITY 1000 +</PRE> +<P> +Since the <CODE>hashpjw</CODE> function from <TT>`builtin.h'</TT> is +appropriate here. Changing the default capacity to a value +expected to exceed the actual capacity helps to avoid +"hidden" inefficiencies when a new VHMap is created without +overriding the default, which is all too easy to do. +<P> +Otherwise, everything is the same as above, substituting +<CODE>VHMap</CODE> for <CODE>AVLMap</CODE>. +<P> +<H1><A NAME="SEC13" HREF="libgpp_toc.html#SEC13">Variable-Sized Object Representation</A></H1> +<P> +One of the first goals of the GNU C++ library is to enrich the kinds of +basic classes that may be considered as (nearly) "built into" C++. A good +deal of the inspiration for these efforts is derived from considering +features of other type-rich languages, particularly Common Lisp and Scheme. +The general characteristics of most class and friend operators and +functions supported by these classes has been heavily influenced +by such languages. +<P> +Four of these types, Strings, Integers, BitSets, and BitStrings (as well as +associated and/or derived classes) require representations suitable for +managing variable-sized objects on the free-store. The basic technique used +for all of these is the same, although various details necessarily differ +from class to class. +<P> +The general strategy for representing such objects is to create chunks of +memory that include both header information (e.g., the size of the object), +as well as the variable-size data (an array of some sort) at the end +of the chunk. Generally the maximum size of an object is limited to +something less than all of addressable memory, as a safeguard. The minimum +size is also limited so as not to waste allocations expanding very small +chunks. Internally, chunks are allocated in blocks well-tuned to the +performance of the <CODE>new</CODE> operator. +<P> +Class elements themselves are merely pointers to these chunks. +Most class operations are performed via inline "translation" +functions that perform the required operation on the corresponding +representation. However, constructors and assignments operate by +copying entire representations, not just pointers. +<P> +No attempt is made to control temporary creation in expressions +and functions involving these classes. Users of previous versions +of the classes will note the disappearance of both "Tmp" classes +and reference counting. These were dropped because, while they +did improve performance in some cases, they obscure class +mechanics, lead programmers into the false belief that they need not +worry about such things, and occasionally have paradoxical behavior. +<P> +These variable-sized object classes are integrated as well as possible +into C++. Most such classes possess converters that allow automatic +coercion both from and to builtin basic types. (e.g., char* to and from +String, long int to and from Integer, etc.). There are pro's and con's +to circular converters, since they can sometimes lead to the conversion +from a builtin type through to a class function and back to a builtin +type without any special attention on the part of the programmer, both +for better and worse. +<P> +Most of these classes also provide special-case operators and functions +mixing basic with class types, as a way to avoid constructors in cases +where the operations do not rely on anything special about the +representations. For example, there is a special case concatenation +operator for a String concatenated with a char, since building the +result does not rely on anything about the String header. Again, there +are arguments both for and against this approach. Supporting these cases +adds a non-trivial degree of (mainly inline) function proliferation, but +results in more efficient operations. Efficiency wins out over parsimony +here, as part of the goal to produce classes that provide sufficient +functionality and efficiency so that programmers are not tempted to try +to manipulate or bypass the underlying representations. +<P> +<H1><A NAME="SEC14" HREF="libgpp_toc.html#SEC14">Some guidelines for using expression-oriented classes</A></H1> +<P> +The fact that C++ allows operators to be overloaded for user-defined +classes can make programming with library classes like <CODE>Integer</CODE>, +<CODE>String</CODE>, and so on very convenient. However, it is worth +becoming familiar with some of the inherent limitations and problems +associated with such operators. +<P> +Many operators are <EM>constructive</EM>, i.e., create a new object +based on some function of some arguments. Sometimes the creation +of such objects is wasteful. Most library classes supporting +expressions contain facilities that help you avoid such waste. +<P> +For example, for <CODE>Integer a, b, c; ...; c = a + b + a;</CODE>, the +plus operator is called to sum a and b, creating a new temporary object +as its result. This temporary is then added with a, creating another +temporary, which is finally copied into c, and the temporaries are then +deleted. In other words, this code might have an effect similar to +<CODE>Integer a, b, c; ...; Integer t1(a); t1 += b; Integer t2(t1); +t2 += a; c = t2;</CODE>. +<P> +For small objects, simple operators, and/or non-time/space critical +programs, creation of temporaries is not a big problem. However, often, +when fine-tuning a program, it may be a good idea to rewrite such +code in a less pleasant, but more efficient manner. +<P> +For builtin types like ints, and floats, C and C++ compilers already +know how to optimize such expressions to reduce the need for +temporaries. Unfortunately, this is not true for C++ user defined +types, for the simple (but very annoying, in this context) reason that +nothing at all is guaranteed about the semantics of overloaded operators +and their interrelations. For example, if the above expression just +involved ints, not Integers, a compiler might internally convert the +statement into something like <CODE> c += a; c += b; c+= a; </CODE>, or +perhaps something even more clever. But since C++ does not know that +Integer operator += has any relation to Integer operator +, A C++ +compiler cannot do this kind of expression optimization itself. +<P> +In many cases, you can avoid construction of temporaries simply by +using the assignment versions of operators whenever possible, since +these versions create no temporaries. However, for maximum flexibility, +most classes provide a set of "embedded assembly code" procedures +that you can use to fully control time, space, and evaluation strategies. +Most of these procedures are "three-address" procedures that take +two <CODE>const</CODE> source arguments, and a destination argument. The +procedures perform the appropriate actions, placing the results in +the destination (which is may involve overwriting old contents). These +procedures are designed to be fast and robust. In particular, aliasing +is always handled correctly, so that, for example +<CODE>add(x, x, x); </CODE> is perfectly OK. (The names of these procedures +are listed along with the classes.) +<P> +For example, suppose you had an Integer expression +<CODE> a = (b - a) * -(d / c); </CODE> +<P> +This would be compiled as if it were +<CODE> Integer t1=b-a; Integer t2=d/c; Integer t3=-t2; Integer t4=t1*t3; a=t4;</CODE> +<P> +But, with some manual cleverness, you might yourself some up with +<CODE> sub(a, b, a); mul(a, d, a); div(a, c, a); </CODE> +<P> +A related phenomenon occurs when creating your own constructive +functions returning instances of such types. Suppose you wanted +to write function +<CODE>Integer f(const Integer& a) { Integer r = a; r += a; return r; }</CODE> +<P> +This function, when called (as in <CODE> a = f(a); </CODE>) demonstrates a +similar kind of wasted copy. The returned value r must be copied +out of the function before it can be used by the caller. In GNU +C++, there is an alternative via the use of named return values. +Named return values allow you to manipulate the returned object +directly, rather than requiring you to create a local inside +a function and then copy it out as the returned value. In this +example, this can be done via +<CODE>Integer f(const Integer& a) return r(a) { r += a; return; }</CODE> +<P> +A final guideline: The overloaded operators are very convenient, and +much clearer to use than procedural code. It is almost always a good +idea to make it right, <EM>then</EM> make it fast, by translating +expression code into procedural code after it is known to be correct. +<P> +<H1><A NAME="SEC15" HREF="libgpp_toc.html#SEC15">Pseudo-indexes</A></H1> +<P> +Many useful classes operate as containers of elements. Techniques for +accessing these elements from a container differ from class to class. +In the GNU C++ library, access methods have been partially standardized +across different classes via the use of pseudo-indexes called +<CODE>Pixes</CODE>. A <CODE>Pix</CODE> acts in some ways like an index, and in some +ways like a pointer. (Their underlying representations are just +<CODE>void*</CODE> pointers). A <CODE>Pix</CODE> is a kind of "key" that is +translated into an element access by the class. In virtually all cases, +<CODE>Pixes</CODE> are pointers to some kind internal storage cells. The +containers use these pointers to extract items. +<P> +<CODE>Pixes</CODE> support traversal and inspection of elements in a +collection using analogs of array indexing. However, they are +pointer-like in that <CODE>0</CODE> is treated as an invalid <CODE>Pix</CODE>, and +unsafe insofar as programmers can attempt to access nonexistent elements +via dangling or otherwise invalid <CODE>Pixes</CODE> without first checking +for their validity. +<P> +In general it is a very bad idea to perform traversals in the the midst +of destructive modifications to containers. +<P> +Typical applications might include code using the idiom +<PRE> +for (Pix i = a.first(); i != 0; a.next(i)) use(a(i)); +</PRE> +for some container <CODE>a</CODE> and function <CODE>use</CODE>. +<P> +Classes supporting the use of <CODE>Pixes</CODE> always contain the following +methods, assuming a container <CODE>a</CODE> of element types of <CODE>Base</CODE>. +<P> +<DL COMPACT> +<P> +<DT><CODE>Pix i = a.first()</CODE> +<DD>Set i to index the first element of a or 0 if a is empty. +<P> +<DT><CODE>a.next(i)</CODE> +<DD>advance i to the next element of a or 0 if there is no next element; +<P> +<DT><CODE>Base x = a(i); a(i) = x;</CODE> +<DD>a(i) returns a reference to the element indexed by i. +<P> +<DT><CODE>int present = a.owns(i)</CODE> +<DD>returns true if Pix i is a valid Pix in a. This is often a +relatively slow operation, since the collection must usually +traverse through elements to see if any correspond to the Pix. +<P> +</DL> +<P> +Some container classes also support backwards traversal via +<P> +<DL COMPACT> +<DT><CODE>Pix i = a.last()</CODE> +<DD>Set i to the last element of a or 0 if a is empty. +<P> +<DT><CODE>a.prev(i)</CODE> +<DD>sets i to the previous element in a, or 0 if there is none. +</DL> +<P> +Collections supporting elements with an equality operation possess +<P> +<DL COMPACT> +<DT><CODE>Pix j = a.seek(x)</CODE> +<DD>sets j to the index of the first occurrence of x, or 0 if x is +not contained in a. +</DL> +<P> +Bag classes possess +<P> +<DL COMPACT> +<DT><CODE>Pix j = a.seek(x, Pix from = 0)</CODE> +<DD>sets j to the index of the next occurrence of x following i, +or 0 if x is not contained in a. If i == 0, the first occurrence +is returned. +</DL> +<P> +Set, Bag, and PQ classes possess +<P> +<DL COMPACT> +<DT><CODE>Pix j = a.add(x) (or a.enq(x) for priority queues)</CODE> +<DD>add x to the collection, returning its Pix. The Pix of an item +can change in collections where further additions and deletions +involve the actual movement of elements (currently in OXPSet, +OXPBag, XPPQ, VOHSet), but in all other cases, an item's Pix may +be considered a permanent key to its location. +</DL> +<P> +<H1><A NAME="SEC16" HREF="libgpp_toc.html#SEC16">Header files for interfacing C++ to C</A></H1> +<P> +The following files are provided so that C++ programmers may +invoke common C library and system calls. The names and contents +of these files are subject to change in order to be compatible +with the forthcoming GNU C library. Other files, not listed +here, are simply C++-compatible interfaces to corresponding C +library files. +<P> +<DL COMPACT> +<DT><TT>`values.h'</TT> +<DD>A collection of constants defining the numbers of bits in builtin +types, minimum and maximum values, and the like. Most names are +the same as those found in <TT>`values.h'</TT> found on Sun systems. +<P> +<DT><TT>`std.h'</TT> +<DD>A collection of common system calls and <TT>`libc.a'</TT> functions. +Only those functions that can be declared without introducing +new type definitions (socket structures, for example) are +provided. Common <CODE>char*</CODE> functions (like <CODE>strcmp</CODE>) are among +the declarations. All functions are declared along with their +library names, so that they may be safely overloaded. +<P> +<DT><TT>`string.h'</TT> +<DD>This file merely includes <TT>`<std.h>'</TT>, where string function +prototypes are declared. This is a workaround for the fact that +system <TT>`string.h'</TT> and <TT>`strings.h'</TT> files often differ +in contents. +<P> +<DT><TT>`osfcn.h'</TT> +<DD>This file merely includes <TT>`<std.h>'</TT>, where system function +prototypes are declared. +<P> +<DT><TT>`libc.h'</TT> +<DD>This file merely includes <TT>`<std.h>'</TT>, where C library function +prototypes are declared. +<P> +<DT><TT>`math.h'</TT> +<DD>A collection of prototypes for functions usually found in +libm.a, plus some <CODE>#define</CODE>d constants that appear to be +consistent with those provided in the AT&T version. The value +of <CODE>HUGE</CODE> should be checked before using. Declarations of +all common math functions are preceded with <CODE>overload</CODE> +declarations, since these are commonly overloaded. +<P> +<DT><TT>`stdio.h'</TT> +<DD>Declaration of <CODE>FILE</CODE> (<CODE>_iobuf</CODE>), common macros (like +<CODE>getc</CODE>), and function prototypes for <TT>`libc.a'</TT> +functions that operate on <CODE>FILE*</CODE>'s. The value +<CODE>BUFSIZ</CODE> and the declaration of <CODE>_iobuf</CODE> should be +checked before using. +<P> +<DT><TT>`assert.h'</TT> +<DD>C++ versions of assert macros. +<P> +<DT><TT>`generic.h'</TT> +<DD>String concatenation macros useful in creating generic classes. +They are similar in function to the AT&T CC versions. +<P> +<DT><TT>`new.h'</TT> +<DD>Declarations of the default global operator new, the two-argument +placement version, and associated error handlers. +</DL> +<P> +<H1><A NAME="SEC17" HREF="libgpp_toc.html#SEC17">Utility functions for built in types</A></H1> +<P> +Files <TT>`builtin.h'</TT> and corresponding <TT>`.cc'</TT> implementation +files contain various convenient +inline and non-inline utility functions. These include useful +enumeration types, such as <CODE>TRUE</CODE>, <CODE>FALSE</CODE> ,the type +definition for pointers to libg++ error handling functions, and +the following functions. +<P> +<DL COMPACT> +<DT><CODE>long abs(long x); double abs(double x);</CODE> +<DD>inline versions of abs. Note that the standard libc.a version, +<CODE>int abs(int)</CODE> is <EM>not</EM> declared as inline. +<P> +<DT><CODE>void clearbit(long& x, long b);</CODE> +<DD>clears the b'th bit of x (inline). +<P> +<DT><CODE>void setbit(long& x, long b);</CODE> +<DD>sets the b'th bit of x (inline) +<P> +<DT><CODE>int testbit(long x, long b);</CODE> +<DD>returns the b'th bit of x (inline). +<P> +<DT><CODE>int even(long y);</CODE> +<DD>returns true if x is even (inline). +<P> +<DT><CODE>int odd(long y);</CODE> +<DD>returns true is x is odd (inline). +<P> +<DT><CODE>int sign(long x); int sign(double x);</CODE> +<DD>returns -1, 0, or 1, indicating whether x is less than, equal to, or +greater than zero (inline). +<P> +<DT><CODE>long gcd(long x, long y);</CODE> +<DD>returns the greatest common divisor of x and y. +<P> +<DT><CODE>long lcm(long x, long y);</CODE> +<DD>returns the least common multiple of x and y. +<P> +<DT><CODE>long lg(long x);</CODE> +<DD>returns the floor of the base 2 log of x. +<P> +<DT><CODE>long pow(long x, long y); double pow(double x, long y);</CODE> +<DD>returns x to the integer power y using via the iterative O(log y) +"Russian peasant" method. +<P> +<DT><CODE>long sqr(long x); double sqr(double x);</CODE> +<DD>returns x squared (inline). +<P> +<DT><CODE>long sqrt(long y);</CODE> +<DD>returns the floor of the square root of x. +<P> +<DT><CODE>unsigned int hashpjw(const char* s);</CODE> +<DD>a hash function for null-terminated char* strings using the +method described in Aho, Sethi, & Ullman, p 436. +<P> +<DT><CODE>unsigned int multiplicativehash(int x);</CODE> +<DD>a hash function for integers that returns the lower bits of +multiplying x by the golden ratio times pow(2, 32). +See Knuth, Vol 3, p 508. +<P> +<DT><CODE>unsigned int foldhash(double x);</CODE> +<DD>a hash function for doubles that exclusive-or's the first and +second words of x, returning the result as an integer. +<P> +<DT><CODE>double start_timer()</CODE> +<DD>Starts a process timer. +<P> +<DT><CODE>double return_elapsed_time(double last_time)</CODE> +<DD>Returns the process time since last_time. +If last_time == 0 returns the time since the last start_timer. +Returns -1 if start_timer was not first called. +<P> +</DL> +<P> +File <TT>`Maxima.h'</TT> includes versions of <CODE>MAX, MIN</CODE> +for builtin types. +<P> +File <TT>`compare.h'</TT> includes versions of <CODE>compare(x, y)</CODE> +for builtin types. These return negative if the first argument +is less than the second, zero for equal, and positive for greater. +<P> +<H1><A NAME="SEC18" HREF="libgpp_toc.html#SEC18">Library dynamic allocation primitives</A></H1> +<P> +Libg++ contains versions of <CODE>malloc, free, realloc</CODE> that were +designed to be well-tuned to C++ applications. The source file +<TT>`malloc.c'</TT> contains some design and implementation details. +Here are the major user-visible differences from most system +malloc routines: +<P> +<OL> +<P> +<LI> +These routines <EM>overwrite</EM> storage of freed space. This +means that it is never permissible to use a <CODE>delete</CODE>'d +object in any way. Doing so will either result in trapped +fatal errors or random aborts within malloc, free, or realloc. +<P> +<LI> +The routines tend to perform well when a large number +of objects of the same size are allocated and freed. You +may find that it is not worth it to create your +own special allocation schemes in such cases. +<P> +<LI> +The library sets top-level <CODE>operator new()</CODE> to call malloc and +<CODE>operator delete()</CODE> to call free. Of course, you may override these +definitions in C++ programs by creating your own operators that will +take precedence over the library versions. However, if you do so, be +sure to define <EM>both</EM> <CODE>operator new()</CODE> and <CODE>operator +delete()</CODE>. +<P> +<LI> +These routines do <EM>not</EM> support the odd convention, maintained by +some versions of malloc, that you may call <CODE>realloc</CODE> with a pointer +that has been <CODE>free</CODE>'d. +<P> +<LI> +The routines automatically perform simple checks on <CODE>free</CODE>'d +pointers that can often determine whether users have accidentally +written beyond the boundaries of allocated space, resulting in a fatal +error. +<P> +<LI> +The function <CODE>malloc_usable_size(void* p)</CODE> returns the number of +bytes actually allocated for <CODE>p</CODE>. For a valid pointer (i.e., one +that has been <CODE>malloc</CODE>'d or <CODE>realloc</CODE>'d but not yet +<CODE>free</CODE>'d) this will return a number greater than or equal to the +requested size, else it will normally return 0. Unfortunately, a +non-zero return can not be an absolutely perfect indication of lack of +error. If a chunk has been <CODE>free</CODE>'d but then re-allocated for a +different purpose somewhere elsewhere, then <CODE>malloc_usable_size</CODE> +will return non-zero. Despite this, the function can be very valuable +for performing run-time consistency checks. +<P> +<LI> +<CODE>malloc</CODE> requires 8 bytes of overhead per allocated chunk, plus a +mmaximum alignment adjustment of 8 bytes. The number of bytes of usable +space is exactly as requested, rounded to the nearest 8 byte boundary. +<P> +<LI> +The routines do <EM>not</EM> contain any synchronization support for +multiprocessing. If you perform global allocation on a shared +memory multiprocessor, you should disable compilation and use +of libg++ malloc in the distribution <TT>`Makefile'</TT> and use your +system version of malloc. +<P> +</OL> +<P> +<H1><A NAME="SEC19" HREF="libgpp_toc.html#SEC19">The new input/output classes</A></H1> +<P> +The iostream classes implement most of the features of AT&T +version 2.0 iostream library classes, and most of the features +of the ANSI X3J16 library draft (which is based on the AT&T design). +These classes are available in <CODE>libg++</CODE> for convenience and for +compatibility with older releases; however, since the iostream classes +are licensed under less stringent terms than <CODE>libg++</CODE>, they are now +also available in a separate library called <CODE>libio</CODE>---and +documented in a separate manual, corresponding to that library. +<P> +See section 'Introduction' in <CITE>The GNU C++ Iostream Library</CITE>. +<P> +<H1><A NAME="SEC20" HREF="libgpp_toc.html#SEC20">The old I/O library</A></H1> +<P> +WARNING: This chapter describes classes that are <EM>obsolete</EM>. +These classes are normally not available when libg++ +is installed normally. The sources are currently included +in the distribution, and you can configure libg++ to use +these classes instead of the new iostream classes. +This is only a temporary measure; you should convert your +code to use iostreams as soon as possible. The iostream +classes provide some compatibility support, but it is +very incomplete (there is no longer a <CODE>File</CODE> class). +<P> +<H2><A NAME="SEC21" HREF="libgpp_toc.html#SEC21">File-based classes</A></H2> + +The <CODE>File</CODE> class supports basic IO on Unix files. Operations are +based on common C stdio library functions. +<P> +<CODE>File</CODE> serves as the base class for istreams, ostreams, and other +derived classes. It contains the interface between the Unix stdio file +library and these more structured classes. Most operations are implemented +as simple calls to stdio functions. <CODE>File</CODE> class operations are also fully +compatible with raw system file reads and writes (like the system +<CODE>read</CODE> and <CODE>lseek</CODE> calls) when buffering is disabled (see below). +The <CODE>FILE*</CODE> stdio file pointer is, however maintained as protected. +Classes derived from File may only use the IO operations provided by File, +which encompass essentially all stdio capabilities. +<P> +The class contains four general kinds of functions: methods for binding +<CODE>File</CODE>s to physical Unix files, basic IO methods, file and buffer +control methods, and methods for maintaining logical and physical file +status. +<P> +Binding and related tasks are accomplished via <CODE>File</CODE> constructors and +destructors, and member functions <CODE>open, close, remove, filedesc, +name, setname</CODE>. +<P> +If a file name is provided in a constructor or open, it is +maintained as class variable <CODE>nm</CODE> and is accessible +via <CODE>name</CODE>. If no name is provided, then <CODE>nm</CODE> remains +null, except that <CODE>Files</CODE> bound to the default files stdin, +stdout, and stderr are automatically given the names +<CODE>(stdin), (stdout), (stderr)</CODE> respectively. +The function <CODE>setname</CODE> may be used to change the +internal name of the <CODE>File</CODE>. This does not change the name +of the physical file bound to the File. + +The member function <CODE>close</CODE> closes a file. The +<CODE>~File</CODE> destructor closes a file if it is open, except +that stdin, stdout, and stderr are flushed but left open for +the system to close on program exit since some systems may +require this, and on others it does not matter. <CODE>remove</CODE> +closes the file, and then deletes it if possible by calling the +system function to delete the file with the name provided in +the <CODE>nm</CODE> field. +<P> +<H2><A NAME="SEC22" HREF="libgpp_toc.html#SEC22">Basic IO</A></H2> +<P> +<UL> +<P> +<LI> +<CODE>read</CODE> and <CODE>write</CODE> perform binary IO via stdio +<CODE>fread</CODE> and <CODE>fwrite</CODE>. +<P> +<LI> +<CODE>get</CODE> and <CODE>put</CODE> for chars invoke stdio <CODE>getc</CODE> +and <CODE>putc</CODE> macros. +<P> +<LI> +<CODE>put(const char* s)</CODE> outputs a null-terminated string via +stdio <CODE>fputs</CODE>. +<P> +<LI> +<CODE>unget</CODE> and <CODE>putback</CODE> are synonyms. Both call stdio +<CODE>ungetc</CODE>. +<P> +</UL> +<P> +<H2><A NAME="SEC23" HREF="libgpp_toc.html#SEC23">File Control</A></H2> +<P> +<CODE>flush</CODE>, <CODE>seek</CODE>, <CODE>tell</CODE>, and <CODE>tell</CODE> call the +corresponding stdio functions. +<P> +<CODE>flush(char)</CODE> and <CODE>fill()</CODE> call stdio <CODE>_flsbuf</CODE> +and <CODE>_filbuf</CODE> respectively. +<P> +<CODE>setbuf</CODE> is mainly useful to turn off buffering in cases +where nonsequential binary IO is being performed. <CODE>raw</CODE> is a +synonym for <CODE>setbuf(_IONBF)</CODE>. After a <CODE>f.raw()</CODE>, using +the stdio functions instead of the system <CODE>read, write</CODE>, +etc., calls entails very little overhead. Moreover, these become +fully compatible with intermixed system calls (e.g., +<CODE>lseek(f.filedesc(), 0, 0)</CODE>). While intermixing <CODE>File</CODE> +and system IO calls is not at all recommended, this technique +does allow the <CODE>File</CODE> class to be used in conjunction with +other functions and libraries already set up to operate on file +descriptors. <CODE>setbuf</CODE> should be called at most once after a +constructor or open, but before any IO. +<P> +<H2><A NAME="SEC24" HREF="libgpp_toc.html#SEC24">File Status</A></H2> +<P> +File status is maintained in several ways. +<P> +A <CODE>File</CODE> may be checked for accessibility via +<CODE>is_open()</CODE>, which returns true if the File is bound to a +usable physical file, <CODE>readable()</CODE>, which returns true if +the File can be read from (opened for reading, and not in a +_fail state), or <CODE>writable()</CODE>, which returns true if the +File can be written to. +<P> +<CODE>File</CODE> operations return their status via two means: failure and +success are represented via the logical state. Also, the +return values of invoked stdio and system functions that +return useful numeric values (not just failure/success flags) +are held in a class variable accessible via <CODE>iocount</CODE>. +(This is useful, for example, in determining the number of +items actually read by the <CODE>read</CODE> function.) +<P> +Like the AT&T i/o-stream classes, but unlike the description in +the Stroustrup book, p238, <CODE>rdstate()</CODE> returns the bitwise +OR of <CODE>_eof</CODE>, <CODE>_fail</CODE> and <CODE>_bad</CODE>, not necessarily +distinct values. The functions <CODE>eof()</CODE>, <CODE>fail()</CODE>, +<CODE>bad()</CODE>, and <CODE>good()</CODE> can be used to test for each of +these conditions independently. +<P> +<CODE>_fail</CODE> becomes set for any input operation that could not +read in the desired data, and for other failed operations. As +with all Unix IO, <CODE>_eof</CODE> becomes true only when an input +operations fails because of an end of file. Therefore, +<CODE>_eof</CODE> is not immediately true after the last successful +read of a file, but only after one final read attempt. Thus, for +input operations, <CODE>_fail</CODE> and <CODE>_eof</CODE> almost always +become true at the same time. <CODE>bad</CODE> is set for unbound +files, and may also be set by applications in order to communicate +input corruption. Conversely, <CODE>_good</CODE> is defined as 0 and +is returned by <CODE>rdstate()</CODE> if all is well. +<P> +The state may be modified via <CODE>clear(flag)</CODE>, which, +despite its name, sets the corresponding state_value flag. +<CODE>clear()</CODE> with no arguments resets the state to <CODE>_good</CODE>. +<CODE>failif(int cond)</CODE> sets the state to <CODE>_fail</CODE> only if +<CODE>cond</CODE> is true. +<P> +Errors occuring during constructors and file opens also invoke the +function <CODE>error</CODE>. <CODE>error</CODE> in turn calls a resetable error +handling function pointed to by the non-member global variable +<CODE>File_error_handler</CODE> only if a system error has been generated. +Since <CODE>error</CODE> cannot tell if the current system error is actually +responsible for a failure, it may at times print out spurious messages. +Three error handlers are provided. The default, +<CODE>verbose_File_error_handler</CODE> calls the system function +<CODE>perror</CODE> to print the corresponding error message on standard +error, and then returns to the caller. <CODE>quiet_File_error_handler</CODE> +does nothing, and simply returns. <CODE>fatal_File_error_handler</CODE> +prints the error and then aborts execution. These three handlers, or any +other user-defined error handlers can be selected via the non-member +function <CODE>set_File_error_handler</CODE>. +<P> +All read and write operations communicate either logical or +physical failure by setting the <CODE>_fail</CODE> flag. All further +operations are blocked if the state is in a <CODE>_fail</CODE> or<CODE>_bad</CODE> +condition. Programmers must explicitly use <CODE>clear()</CODE> to +reset the state in order to continue IO processing after +either a logical or physical failure. C programmers who are +unfamiliar with these conventions should note that, unlike +the stdio library, <CODE>File</CODE> functions indicate IO success, +status, or failure solely through the state, not via return values of +the functions. The <CODE>void*</CODE> operator or <CODE>rdstate()</CODE> +may be used to test success. In particular, according to c++ +conversion rules, the <CODE>void*</CODE> coercion is automatically +applied whenever the <CODE>File&</CODE> return value of any <CODE>File</CODE> +function is tested in an <CODE>if</CODE> or <CODE>while</CODE>. Thus, +for example, an easy way to copy all of stdin to stdout until +eof (at which point <CODE>get</CODE> fails) or some error is +<CODE>char c; while(cin.get(c) && cout.put(c));</CODE>. +<P> +The current version of istreams and ostreams differs significantly +from previous versions in order to obtain compatibility with +AT&T 1.2 streams. Most code using previous versions should still +work. However, the following features of <CODE>File</CODE> are not +incorporated in streams (they are still present in <CODE>File</CODE>): +<CODE>scan(const char* fmt...), remove(), read(), write(), +setbuf(), raw()</CODE>. Additionally, the feature of previous streams +that allowed free intermixing of stream and stdio input and output +is no longer guaranteed to always behave as desired. +<P> +<H1><A NAME="SEC25" HREF="libgpp_toc.html#SEC25">The Obstack class</A></H1> +<P> +The <CODE>Obstack</CODE> class is a simple rewrite of the C obstack macros and +functions provided in the GNU CC compiler source distribution. +<P> +Obstacks provide a simple method of creating and maintaining a string +table, optimized for the very frequent task of building strings +character-by-character, and sometimes keeping them, and sometimes +not. They seem especially useful in any parsing application. One of the +test files demonstrates usage. +<P> +A brief summary: +<DL COMPACT> +<P> +<DT><CODE>grow</CODE> +<DD>places something on the obstack without committing to wrap +it up as a single entity yet. +<P> +<DT><CODE>finish</CODE> +<DD>wraps up a constructed object as a single entity, +and returns the pointer to its start address. +<P> +<DT><CODE>copy</CODE> +<DD>places things on the obstack, and <EM>does</EM> wrap them up. +<CODE>copy</CODE> is always equivalent to first grow, then finish. +<P> +<DT><CODE>free</CODE> +<DD>deletes something, and anything else put on the obstack since its creation. +</DL> +<P> +The other functions are less commonly needed: +<DL COMPACT> +<DT><CODE>blank</CODE> +<DD>is like grow, except it just grows the space by size units +without placing anything into this space +<DT><CODE>alloc</CODE> +<DD>is like <CODE>blank</CODE>, but it wraps up the object and returns its starting +address. +<DT><CODE>chunk_size, base, next_free, alignment_mask, size, room</CODE> +<DD>returns the appropriate class variables. +<DT><CODE>grow_fast</CODE> +<DD>places a character on the obstack without checking if there is enough room. +<DT><CODE>blank_fast</CODE> +<DD>like <CODE>blank</CODE>, but without checking if there is enough room. +<DT><CODE>shrink(int n)</CODE> +<DD>shrink the current chunk by n bytes. +<DT><CODE>contains(void* addr)</CODE> +<DD>returns true if the Obstack holds the address addr. +</DL> +<P> +Here is a lightly edited version of the original C documentation: +<P> +These functions operate a stack of objects. Each object starts life +small, and may grow to maturity. (Consider building a word syllable +by syllable.) An object can move while it is growing. Once it has +been "finished" it never changes address again. So the "top of the +stack" is typically an immature growing object, while the rest of the +stack is of mature, fixed size and fixed address objects. +<P> +These routines grab large chunks of memory, using the GNU C++ <CODE>new</CODE> +operator. On occasion, they free chunks, via <CODE>delete</CODE>. +<P> +Each independent stack is represented by a Obstack. +<P> +One motivation for this package is the problem of growing char strings +in symbol tables. Unless you are a "fascist pig with a read-only mind" +[Gosper's immortal quote from HAKMEM item 154, out of context] you +would not like to put any arbitrary upper limit on the length of your +symbols. +<P> +In practice this often means you will build many short symbols and a +few long symbols. At the time you are reading a symbol you don't know +how long it is. One traditional method is to read a symbol into a +buffer, <CODE>realloc()</CODE>ating the buffer every time you try to read a +symbol that is longer than the buffer. This is beaut, but you still will +want to copy the symbol from the buffer to a more permanent +symbol-table entry say about half the time. +<P> +With obstacks, you can work differently. Use one obstack for all symbol +names. As you read a symbol, grow the name in the obstack gradually. +When the name is complete, finalize it. Then, if the symbol exists already, +free the newly read name. +<P> +The way we do this is to take a large chunk, allocating memory from +low addresses. When you want to build a symbol in the chunk you just +add chars above the current "high water mark" in the chunk. When you +have finished adding chars, because you got to the end of the symbol, +you know how long the chars are, and you can create a new object. +Mostly the chars will not burst over the highest address of the chunk, +because you would typically expect a chunk to be (say) 100 times as +long as an average object. +<P> +In case that isn't clear, when we have enough chars to make up +the object, <EM>they are already contiguous in the chunk</EM> (guaranteed) +so we just point to it where it lies. No moving of chars is +needed and this is the second win: potentially long strings need +never be explicitly shuffled. Once an object is formed, it does not +change its address during its lifetime. +<P> +When the chars burst over a chunk boundary, we allocate a larger +chunk, and then copy the partly formed object from the end of the old +chunk to the beginning of the new larger chunk. We then carry on +accreting characters to the end of the object as we normally would. +<P> +A special version of grow is provided to add a single char at a time +to a growing object. +<P> +Summary: +<P> +<UL> +<LI> +We allocate large chunks. +<LI> +We carve out one object at a time from the current chunk. +<LI> +Once carved, an object never moves. +<LI> +We are free to append data of any size to the currently growing object. +<LI> +Exactly one object is growing in an obstack at any one time. +<LI> +You can run one obstack per control block. +<LI> +You may have as many control blocks as you dare. +<LI> +Because of the way we do it, you can `unwind' a obstack back to a +previous state. (You may remove objects much as you would with a stack.) +</UL> +<P> +The obstack data structure is used in many places in the GNU C++ compiler. +<P> +Differences from the the GNU C version +<OL> +<LI> +The obvious differences stemming from the use of classes and +inline functions instead of structs and macros. The C +<CODE>init</CODE> and <CODE>begin</CODE> macros are replaced by constructors. +<P> +<LI> +Overloaded function names are used for grow (and others), +rather than the C <CODE>grow</CODE>, <CODE>grow0</CODE>, etc. +<P> +<LI> +All dynamic allocation uses the the built-in <CODE>new</CODE> operator. +This restricts flexibility by a little, but maintains compatibility +with usual C++ conventions. +<P> +<LI> +There are now two versions of finish: +<P> +<OL> +<LI> +finish() behaves like the C version. +<P> +<LI> +finish(char terminator) adds <CODE>terminator</CODE>, and then calls +<CODE>finish()</CODE>. This enables the normal invocation of <CODE>finish(0)</CODE> to +wrap up a string being grown character-by-character. +</OL> +<P> +<LI> +There are special versions of grow(const char* s) and +copy(const char* s) that add the null-terminated string <CODE>s</CODE> +after computing its length. +<P> +<LI> +The shrink and contains functions are provided. +<P> +</OL> +<P> +<H1><A NAME="SEC26" HREF="libgpp_toc.html#SEC26">The AllocRing class</A></H1> +<P> +An AllocRing is a bounded ring (circular list), each of whose elements +contains a pointer to some space allocated via <CODE>new +char[some_size]</CODE>. The entries are used cyclicly. The size, n, of the +ring is fixed at construction. After that, every nth use of the ring +will reuse (or reallocate) the same space. AllocRings are needed in +order to temporarily hold chunks of space that are needed transiently, +but across constructor-destructor scopes. They mainly useful for storing +strings containing formatted characters to print across various +functions and coercions. These strings are needed across routines, so +may not be deleted in any one of them, but should be recovered at some +point. In other words, an AllocRing is an extremely simple minded +garbage collection mechanism. The GNU C++ library used to use one +AllocRing for such formatting purposes, but it is being phased out, +and is now only used by obsolete functions. +These days, AllocRings are probably not very useful. +<P> +Support includes: +<P> +<DL COMPACT> +<P> +<DT><CODE>AllocRing a(int n)</CODE> +<DD>constructs an Alloc ring with n entries, all null. +<P> +<DT><CODE>void* mem = a.alloc(sz)</CODE> +<DD>moves the ring pointer to the next entry, and reuses the space +if their is enough, also allocates space via new char[sz]. +<P> +<DT><CODE>int present = a.contains(void* ptr)</CODE> +<DD>returns true if ptr is held in one of the ring entries. +<P> +<DT><CODE>a.clear()</CODE> +<DD>deletes all space pointed to in any entry. This is called +automatically upon destruction. +<P> +<DT><CODE>a.free(void* ptr)</CODE> +<DD>If ptr is one of the entries, calls delete of the pointer, +and resets to entry pointer to null. +<P> +</DL> +<P> +<H1><A NAME="SEC27" HREF="libgpp_toc.html#SEC27">The String class</A></H1> +<P> +The <CODE>String</CODE> class is designed to extend GNU C++ to support +string processing capabilities similar to those in languages like +Awk. The class provides facilities that ought to be convenient +and efficient enough to be useful replacements for <CODE>char*</CODE> +based processing via the C string library (i.e., <CODE>strcpy, +strcmp,</CODE> etc.) in many applications. Many details about String +representations are described in the Representation section. +<P> +A separate <CODE>SubString</CODE> class supports substring extraction +and modification operations. This is implemented in a way that +user programs never directly construct or represent substrings, +which are only used indirectly via String operations. +<P> +Another separate class, <CODE>Regex</CODE> is also used indirectly via String +operations in support of regular expression searching, matching, and the +like. The Regex class is based entirely on the GNU Emacs regex +functions. See section 'Syntax of Regular Expressions' in <CITE>GNU Emacs Manual</CITE>, for a full +explanation of regular expression syntax. (For implementation details, +see the internal documentation in files <TT>`regex.h'</TT> and +<TT>`regex.c'</TT>.) +<P> +<H2><A NAME="SEC28" HREF="libgpp_toc.html#SEC28">Constructors</A></H2> +<P> +Strings are initialized and assigned as in the following examples: +<P> +<DL COMPACT> +<P> +<DT><CODE>String x; String y = 0; String z = "";</CODE> +<DD>Set x, y, and z to the nil string. Note that either 0 or "" may +always be used to refer to the nil string. +<P> +<DT><CODE>String x = "Hello"; String y("Hello");</CODE> +<DD>Set x and y to a copy of the string "Hello". +<P> +<DT><CODE>String x = 'A'; String y('A');</CODE> +<DD>Set x and y to the string value "A" +<P> +<DT><CODE>String u = x; String v(x);</CODE> +<DD>Set u and v to the same string as String x +<P> +<DT><CODE>String u = x.at(1,4); String v(x.at(1,4));</CODE> +<DD>Set u and v to the length 4 substring of x starting at position 1 +(counting indexes from 0). +<P> +<DT><CODE>String x("abc", 2);</CODE> +<DD>Sets x to "ab", i.e., the first 2 characters of "abc". +<P> +<DT><CODE>String x = dec(20);</CODE> +<DD>Sets x to "20". As here, Strings may be initialized or assigned +the results of any <CODE>char*</CODE> function. +<P> +</DL> +<P> +There are no directly accessible forms for declaring SubString +variables. +<P> +The declaration <CODE>Regex r("[a-zA-Z_][a-zA-Z0-9_]*");</CODE> creates +a compiled regular expression suitable for use in String +operations described below. (In this case, one that matches any +C++ identifier). The first argument may also be a String. +Be careful in distinguishing the role of backslashes in quoted +GNU C++ char* constants versus those in Regexes. For example, a Regex +that matches either one or more tabs or all strings beginning +with "ba" and ending with any number of occurrences of "na" +could be declared as <CODE>Regex r = "\\(\t+\\)\\|\\(ba\\(na\\)*\\)"</CODE> +Note that only one backslash is needed to signify the tab, but +two are needed for the parenthesization and virgule, since the +GNU C++ lexical analyzer decodes and strips backslashes before +they are seen by Regex. +<P> +There are three additional optional arguments to the Regex constructor +that are less commonly useful: +<P> +<DL COMPACT> +<DT><CODE>fast (default 0)</CODE> +<DD><CODE>fast</CODE> may be set to true (1) if the Regex should be +"fast-compiled". This causes an additional compilation step that +is generally worthwhile if the Regex will be used many times. +<P> +<DT><CODE>bufsize (default max(40, length of the string))</CODE> +<DD>This is an estimate of the size of the internal compiled +expression. Set it to a larger value if you know that the +expression will require a lot of space. If you do not know, +do not worry: realloc is used if necessary. +<P> +<DT><CODE>transtable (default none == 0)</CODE> +<DD>The address of a byte translation table (a char[256]) that +translates each character before matching. +<P> +</DL> +<P> +As a convenience, several Regexes are predefined and usable in +any program. Here are their declarations from <TT>`String.h'</TT>. +<P> +<PRE> +extern Regex RXwhite; // = "[ \n\t]+" +extern Regex RXint; // = "-?[0-9]+" +extern Regex RXdouble; // = "-?\\(\\([0-9]+\\.[0-9]*\\)\\| + // \\([0-9]+\\)\\| + // \\(\\.[0-9]+\\)\\) + // \\([eE][---+]?[0-9]+\\)?" +extern Regex RXalpha; // = "[A-Za-z]+" +extern Regex RXlowercase; // = "[a-z]+" +extern Regex RXuppercase; // = "[A-Z]+" +extern Regex RXalphanum; // = "[0-9A-Za-z]+" +extern Regex RXidentifier; // = "[A-Za-z_][A-Za-z0-9_]*" + +</PRE> +<P> +<H2><A NAME="SEC29" HREF="libgpp_toc.html#SEC29">Examples</A></H2> +<P> +Most <CODE>String</CODE> class capabilities are best shown via example. +The examples below use the following declarations. +<P> +<PRE> + String x = "Hello"; + String y = "world"; + String n = "123"; + String z; + char* s = ","; + String lft, mid, rgt; + Regex r = "e[a-z]*o"; + Regex r2("/[a-z]*/"); + char c; + int i, pos, len; + double f; + String words[10]; + words[0] = "a"; + words[1] = "b"; + words[2] = "c"; + +</PRE> +<P> +<H2><A NAME="SEC30" HREF="libgpp_toc.html#SEC30">Comparing, Searching and Matching</A></H2> +<P> +The usual lexicographic relational operators (<CODE>==, !=, <, <=, >, >=</CODE>) +are defined. A functional form <CODE>compare(String, String)</CODE> is also +provided, as is <CODE>fcompare(String, String)</CODE>, which compares +Strings without regard for upper vs. lower case. +<P> +All other matching and searching operations are based on some form of the +(non-public) <CODE>match</CODE> and <CODE>search</CODE> functions. <CODE>match</CODE> and +<CODE>search</CODE> differ in that <CODE>match</CODE> attempts to match only at the +given starting position, while <CODE>search</CODE> starts at the position, and +then proceeds left or right looking for a match. As seen in the following +examples, the second optional <CODE>startpos</CODE> argument to functions using +<CODE>match</CODE> and <CODE>search</CODE> specifies the starting position of the +search: If non-negative, it results in a left-to-right search starting at +position <CODE>startpos</CODE>, and if negative, a right-to-left search starting +at position <CODE>x.length() + startpos</CODE>. In all cases, the index returned +is that of the beginning of the match, or -1 if there is no match. +<P> +Three String functions serve as front ends to <CODE>search</CODE> and <CODE>match</CODE>. +<CODE>index</CODE> performs a search, returning the index, <CODE>matches</CODE> performs +a match, returning nonzero (actually, the length of the match) on success, +and <CODE>contains</CODE> is a boolean function performing either a search or +match, depending on whether an index argument is provided: +<P> +<DL COMPACT> +<P> +<DT><CODE>x.index("lo")</CODE> +<DD>returns the zero-based index of the leftmost occurrence of +substring "lo" (3, in this case). The argument may be a +String, SubString, char, char*, or Regex. +<P> +<DT><CODE>x.index("l", 2)</CODE> +<DD>returns the index of the first of the leftmost occurrence of "l" +found starting the search at position x[2], or 2 in this case. +<P> +<DT><CODE>x.index("l", -1)</CODE> +<DD>returns the index of the rightmost occurrence of "l", or 3 here. +<P> +<DT><CODE>x.index("l", -3)</CODE> +<DD>returns the index of the rightmost occurrence of "l" found by +starting the search at the 3rd to the last position of x, +returning 2 in this case. +<P> +<DT><CODE>pos = r.search("leo", 3, len, 0)</CODE> +<DD>returns the index of r in the <CODE>char*</CODE> string of length 3, +starting at position 0, also placing the length of the match +in reference parameter len. +<P> +<DT><CODE>x.contains("He")</CODE> +<DD>returns nonzero if the String x contains the substring "He". The +argument may be a String, SubString, char, char*, or Regex. +<P> +<DT><CODE>x.contains("el", 1)</CODE> +<DD>returns nonzero if x contains the substring "el" at position 1. +As in this example, the second argument to <CODE>contains</CODE>, +if present, means to match the substring only at that position, +and not to search elsewhere in the string. +<P> +<DT><CODE>x.contains(RXwhite);</CODE> +<DD>returns nonzero if x contains any whitespace (space, tab, or +newline). Recall that <CODE>RXwhite</CODE> is a global whitespace Regex. +<P> +<DT><CODE>x.matches("lo", 3)</CODE> +<DD>returns nonzero if x starting at position 3 exactly matches "lo", with +no trailing characters (as it does in this example). +<P> +<DT><CODE>x.matches(r)</CODE> +<DD>returns nonzero if String x as a whole matches Regex r. +<P> +<DT><CODE>int f = x.freq("l")</CODE> +<DD>returns the number of distinct, nonoverlapping matches to the argument +(2 in this case). +<P> +</DL> +<P> +<H2><A NAME="SEC31" HREF="libgpp_toc.html#SEC31">Substring extraction</A></H2> +<P> +Substrings may be extracted via the <CODE>at</CODE>, <CODE>before</CODE>, +<CODE>through</CODE>, <CODE>from</CODE>, and <CODE>after</CODE> functions. +These behave as either lvalues or rvalues. +<P> +<DL COMPACT> +<P> +<DT><CODE>z = x.at(2, 3)</CODE> +<DD>sets String z to be equal to the length 3 substring of String x +starting at zero-based position 2, setting z to "llo" in this +case. A nil String is returned if the arguments don't make sense. +<P> +<DT><CODE>x.at(2, 2) = "r"</CODE> +<DD>Sets what was in positions 2 to 3 of x to "r", setting x to +"Hero" in this case. As indicated here, SubString assignments may +be of different lengths. +<P> +<DT><CODE>x.at("He") = "je";</CODE> +<DD>x("He") is the substring of x that matches the first occurrence of +it's argument. The substitution sets x to "jello". If "He" did +not occur, the substring would be nil, and the assignment would +have no effect. +<P> +<DT><CODE>x.at("l", -1) = "i";</CODE> +<DD>replaces the rightmost occurrence of "l" with "i", setting x to +"Helio". +<P> +<DT><CODE>z = x.at(r)</CODE> +<DD>sets String z to the first match in x of Regex r, or "ello" in this +case. A nil String is returned if there is no match. +<P> +<DT><CODE>z = x.before("o")</CODE> +<DD>sets z to the part of x to the left of the first occurrence of +"o", or "Hell" in this case. The argument may also be a String, +SubString, or Regex. (If there is no match, z is set to "".) +<P> +<DT><CODE>x.before("ll") = "Bri";</CODE> +<DD>sets the part of x to the left of "ll" to "Bri", setting x to +"Brillo". +<P> +<DT><CODE>z = x.before(2)</CODE> +<DD>sets z to the part of x to the left of x[2], or "He" in this +case. +<P> +<DT><CODE>z = x.after("Hel")</CODE> +<DD>sets z to the part of x to the right of "Hel", or "lo" in this +case. +<P> +<DT><CODE>z = x.through("el")</CODE> +<DD>sets z to the part of x up and including "el", or "Hel" in this case. +<P> +<DT><CODE>z = x.from("el")</CODE> +<DD>sets z to the part of x from "el" to the end, or "ello" in this case. +<P> +<DT><CODE>x.after("Hel") = "p";</CODE> +<DD>sets x to "Help"; +<P> +<DT><CODE>z = x.after(3)</CODE> +<DD>sets z to the part of x to the right of x[3] or "o" in this case. +<P> +<DT><CODE>z = " ab c"; z = z.after(RXwhite)</CODE> +<DD>sets z to the part of its old string to the right of the first +group of whitespace, setting z to "ab c"; Use gsub(below) to +strip out multiple occurrences of whitespace or any pattern. +<P> +<DT><CODE>x[0] = 'J';</CODE> +<DD>sets the first element of x to 'J'. x[i] returns a reference to +the ith element of x, or triggers an error if i is out of range. +<P> +<DT><CODE>common_prefix(x, "Help")</CODE> +<DD>returns the String containing the common prefix of the two Strings +or "Hel" in this case. +<P> +<DT><CODE>common_suffix(x, "to")</CODE> +<DD>returns the String containing the common suffix of the two Strings +or "o" in this case. +<P> +</DL> +<P> +<H2><A NAME="SEC32" HREF="libgpp_toc.html#SEC32">Concatenation</A></H2> +<P> +<DL COMPACT> +<P> +<DT><CODE>z = x + s + ' ' + y.at("w") + y.after("w") + ".";</CODE> +<DD>sets z to "Hello, world." +<P> +<DT><CODE>x += y;</CODE> +<DD>sets x to "Helloworld" +<P> +<DT><CODE>cat(x, y, z)</CODE> +<DD>A faster way to say z = x + y. +<P> +<DT><CODE>cat(z, y, x, x)</CODE> +<DD>Double concatenation; A faster way to say x = z + y + x. +<P> +<DT><CODE>y.prepend(x);</CODE> +<DD>A faster way to say y = x + y. +<P> +<DT><CODE>z = replicate(x, 3);</CODE> +<DD>sets z to "HelloHelloHello". +<P> +<DT><CODE>z = join(words, 3, "/")</CODE> +<DD>sets z to the concatenation of the first 3 Strings in String +array words, each separated by "/", setting z to "a/b/c" in this +case. The last argument may be "" or 0, indicating no separation. +<P> +</DL> +<P> +<H2><A NAME="SEC33" HREF="libgpp_toc.html#SEC33">Other manipulations</A></H2> +<P> +<DL COMPACT> +<P> +<DT><CODE>z = "this string has five words"; i = split(z, words, 10, RXwhite);</CODE> +<DD>sets up to 10 elements of String array words to the parts of z +separated by whitespace, and returns the number of parts actually +encountered (5 in this case). Here, words[0] = "this", words[1] = +"string", etc. The last argument may be any of the usual. +If there is no match, all of z ends up in words[0]. The words array +is <EM>not</EM> dynamically created by split. +<P> +<DT><CODE>int nmatches x.gsub("l","ll")</CODE> +<DD>substitutes all original occurrences of "l" with "ll", setting x +to "Hellllo". The first argument may be any of the usual, +including Regex. If the second argument is "" or 0, all +occurrences are deleted. gsub returns the number of matches +that were replaced. +<P> +<DT><CODE>z = x + y; z.del("loworl");</CODE> +<DD>deletes the leftmost occurrence of "loworl" in z, setting z to +"Held". +<P> +<DT><CODE>z = reverse(x)</CODE> +<DD>sets z to the reverse of x, or "olleH". +<P> +<DT><CODE>z = upcase(x)</CODE> +<DD>sets z to x, with all letters set to uppercase, setting z to "HELLO" +<P> +<DT><CODE>z = downcase(x)</CODE> +<DD>sets z to x, with all letters set to lowercase, setting z to "hello" +<P> +<DT><CODE>z = capitalize(x)</CODE> +<DD>sets z to x, with the first letter of each word set to uppercase, +and all others to lowercase, setting z to "Hello" +<P> +<DT><CODE>x.reverse(), x.upcase(), x.downcase(), x.capitalize()</CODE> +<DD>in-place, self-modifying versions of the above. +<P> +</DL> +<P> +<H2><A NAME="SEC34" HREF="libgpp_toc.html#SEC34">Reading, Writing and Conversion</A></H2> +<P> +<DL COMPACT> +<P> +<DT><CODE>cout << x</CODE> +<DD>writes out x. +<P> +<DT><CODE>cout << x.at(2, 3)</CODE> +<DD>writes out the substring "llo". +<P> +<DT><CODE>cin >> x</CODE> +<DD>reads a whitespace-bounded string into x. +<P> +<DT><CODE>x.length()</CODE> +<DD>returns the length of String x (5, in this case). +<P> +<DT><CODE>s = (const char*)x</CODE> +<DD>can be used to extract the <CODE>char*</CODE> char array. This +coercion is useful for sending a String as an argument to any +function expecting a <CODE>const char*</CODE> argument (like +<CODE>atoi</CODE>, and <CODE>File::open</CODE>). This operator must be +used with care, since the conversion returns a pointer +to <CODE>String</CODE> internals without copying the characters: +The resulting <CODE>(char*)</CODE> is only valid until +the next String operation, and you must not modify it. +(The conversion is defined to return a const +value so that GNU C++ will produce warning and/or error +messages if changes are attempted.) +<P> +</DL> +<P> +<H1><A NAME="SEC35" HREF="libgpp_toc.html#SEC35">The Integer class.</A></H1> +<P> +The <CODE>Integer</CODE> class provides multiple precision integer arithmetic +facilities. Some representation details are discussed in the +Representation section. +<P> +<CODE>Integers</CODE> may be up to <CODE>b * ((1 << b) - 1)</CODE> bits long, where +<CODE>b</CODE> is the number of bits per short (typically 1048560 bits when +<CODE>b = 16</CODE>). The implementation assumes that a <CODE>long</CODE> is at least +twice as long as a <CODE>short</CODE>. This assumption hides beneath almost all +primitive operations, and would be very difficult to change. It also relies +on correct behavior of <EM>unsigned</EM> arithmetic operations. +<P> +Some of the arithmetic algorithms are very loosely based on those +provided in the MIT Scheme <TT>`bignum.c'</TT> release, which is +Copyright (c) 1987 Massachusetts Institute of Technology. Their use +here falls within the provisions described in the Scheme release. +<P> +Integers may be constructed in the following ways: +<DL COMPACT> +<P> +<DT><CODE>Integer x;</CODE> +<DD>Declares an uninitialized Integer. +<P> +<DT><CODE>Integer x = 2; Integer y(2);</CODE> +<DD>Set x and y to the Integer value 2; +<P> +<DT><CODE>Integer u(x); Integer v = x;</CODE> +<DD>Set u and v to the same value as x. +<P> +</DL> +<P> +<A NAME="IDX1"></A> +<U>Method:</U> long <B>Integer::as_long()</B> <I>const</I><P> +Used to coerce an <CODE>Integer</CODE> back into longs via the <CODE>long</CODE> +coercion operator. If the Integer cannot fit into a long, this returns +MINLONG or MAXLONG (depending on the sign) where MINLONG is the most +negative, and MAXLONG is the most positive representable long. +<P> +<A NAME="IDX2"></A> +<U>Method:</U> int <B>Integer::fits_in_long()</B> <I>const</I><P> +Returns true iff the <CODE>Integer</CODE> is <CODE>< MAXLONG</CODE> and <CODE>> MINLONG</CODE>. +<P> +<A NAME="IDX3"></A> +<U>Method:</U> double <B>Integer::as_double()</B> <I>const</I><P> +Coerce the <CODE>Integer</CODE> to a <CODE>double</CODE>, with potential +loss of precision. +<CODE>+/-HUGE</CODE> is returned if the Integer cannot fit into a double. +<P> +<A NAME="IDX4"></A> +<U>Method:</U> int <B>Integer::fits_in_double()</B> <I>const</I><P> +Returns true iff the <CODE>Integer</CODE> can fit into a double. +<P> +All of the usual arithmetic operators are provided (<CODE>+, -, *, /, +%, +=, ++, -=, --, *=, /=, %=, ==, !=, <, <=, >, >=</CODE>). All operators +support special versions for mixed arguments of Integers and regular +C++ longs in order to avoid useless coercions, as well as to allow +automatic promotion of shorts and ints to longs, so that they may be +applied without additional Integer coercion operators. The only +operators that behave differently than the corresponding int or long +operators are <CODE>++</CODE> and <CODE>--</CODE>. Because C++ does not +distinguish prefix from postfix application, these are declared as +<CODE>void</CODE> operators, so that no confusion can result from applying +them as postfix. Thus, for Integers x and y, <CODE> ++x; y = x; </CODE> is +correct, but <CODE> y = ++x; </CODE> and <CODE> y = x++; </CODE> are not. +<P> +Bitwise operators (<CODE>~</CODE>, <CODE>&</CODE>, <CODE>|</CODE>, <CODE>^</CODE>, <CODE><<</CODE>, +<CODE>>></CODE>, <CODE>&=</CODE>, <CODE>|=</CODE>, <CODE>^=</CODE>, <CODE><<=</CODE>, <CODE>>>=</CODE>) are +also provided. However, these operate on sign-magnitude, rather than +two's complement representations. The sign of the result is arbitrarily +taken as the sign of the first argument. For example, <CODE>Integer(-3) +& Integer(5)</CODE> returns <CODE>Integer(-1)</CODE>, not -3, as it would using +two's complement. Also, <CODE>~</CODE>, the complement operator, complements +only those bits needed for the representation. Bit operators are also +provided in the BitSet and BitString classes. One of these classes +should be used instead of Integers when the results of bit manipulations +are not interpreted numerically. +<P> +The following utility functions are also provided. (All arguments +are Integers unless otherwise noted). +<P> +<A NAME="IDX5"></A> +<U>Function:</U> void <B>divide(const</B> <I>Integer& <VAR>x</VAR>, const Integer& <VAR>y</VAR>, Integer& <VAR>q</VAR>, Integer& <VAR>r</VAR>)</I><P> +Sets <VAR>q</VAR> to the quotient and <VAR>r</VAR> to the remainder of <VAR>x</VAR> and <VAR>y</VAR>. +(<VAR>q</VAR> and <VAR>r</VAR> are returned by reference). +<P> +<A NAME="IDX6"></A> +<U>Function:</U> Integer <B>pow(const</B> <I>Integer& <VAR>x</VAR>, const Integer& <VAR>p</VAR>)</I><P> +Returns <VAR>x</VAR> raised to the power <VAR>p</VAR>. +<P> +<A NAME="IDX7"></A> +<U>Function:</U> Integer <B>Ipow(long</B> <I><VAR>x</VAR>, long <VAR>p</VAR>)</I><P> +Returns <VAR>x</VAR> raised to the power <VAR>p</VAR>. +<P> +<A NAME="IDX8"></A> +<U>Function:</U> Integer <B>gcd(const</B> <I>Integer& <VAR>x</VAR>, const Integer& <VAR>p</VAR>)</I><P> +Returns the greatest common divisor of <VAR>x</VAR> and <VAR>y</VAR>. +<P> +<A NAME="IDX9"></A> +<U>Function:</U> Integer <B>lcm(const</B> <I>Integer& <VAR>x</VAR>, const Integer& <VAR>p</VAR>)</I><P> +Returns the least common multiple of <VAR>x</VAR> and <VAR>y</VAR>. +<P> +<A NAME="IDX10"></A> +<U>Function:</U> Integer <B>abs(const</B> <I>Integer& <VAR>x</VAR></I><P> +Returns the absolute value of <VAR>x</VAR>. +<P> +<A NAME="IDX11"></A> +<U>Method:</U> void <B>Integer::negate()</B><P> +Negates <CODE>this</CODE> in place. +<P> +<DL COMPACT> +<P> +<DT><CODE>Integer sqr(x)</CODE> +<DD>returns x * x; +<P> +<DT><CODE>Integer sqrt(x)</CODE> +<DD>returns the floor of the square root of x. +<P> +<DT><CODE>long lg(x);</CODE> +<DD>returns the floor of the base 2 logarithm of abs(x) +<P> +<DT><CODE>int sign(x)</CODE> +<DD>returns -1 if x is negative, 0 if zero, else +1. +Using <CODE>if (sign(x) == 0)</CODE> is a generally faster method +of testing for zero than using relational operators. +<P> +<DT><CODE>int even(x)</CODE> +<DD>returns true if x is an even number +<P> +<DT><CODE>int odd(x)</CODE> +<DD>returns true if x is an odd number. +<P> +<DT><CODE>void setbit(Integer& x, long b)</CODE> +<DD>sets the b'th bit (counting right-to-left from zero) of x to 1. +<P> +<DT><CODE>void clearbit(Integer& x, long b)</CODE> +<DD>sets the b'th bit of x to 0. +<P> +<DT><CODE>int testbit(Integer x, long b)</CODE> +<DD>returns true if the b'th bit of x is 1. +<P> +<DT><CODE>Integer atoI(char* asciinumber, int base = 10);</CODE> +<DD>converts the base base char* string into its Integer form. +<P> +<DT><CODE>void Integer::printon(ostream& s, int base = 10, int width = 0);</CODE> +<DD>prints the ascii string value of <CODE>(*this)</CODE> as a base <CODE>base</CODE> +number, in field width at least <CODE>width</CODE>. +<P> +<DT><CODE>ostream << x;</CODE> +<DD>prints x in base ten format. +<P> +<DT><CODE>istream >> x;</CODE> +<DD>reads x as a base ten number. +<P> +<DT><CODE>int compare(Integer x, Integer y)</CODE> +<DD>returns a negative number if x<y, zero if x==y, or positive if x>y. +<P> +<DT><CODE>int ucompare(Integer x, Integer y)</CODE> +<DD>like compare, but performs unsigned comparison. +<P> +<DT><CODE>add(x, y, z)</CODE> +<DD>A faster way to say z = x + y. +<P> +<DT><CODE>sub(x, y, z)</CODE> +<DD>A faster way to say z = x - y. +<P> +<DT><CODE>mul(x, y, z)</CODE> +<DD>A faster way to say z = x * y. +<P> +<DT><CODE>div(x, y, z)</CODE> +<DD>A faster way to say z = x / y. +<P> +<DT><CODE>mod(x, y, z)</CODE> +<DD>A faster way to say z = x % y. +<P> +<DT><CODE>and(x, y, z)</CODE> +<DD>A faster way to say z = x & y. +<P> +<DT><CODE>or(x, y, z)</CODE> +<DD>A faster way to say z = x | y. +<P> +<DT><CODE>xor(x, y, z)</CODE> +<DD>A faster way to say z = x ^ y. +<P> +<DT><CODE>lshift(x, y, z)</CODE> +<DD>A faster way to say z = x << y. +<P> +<DT><CODE>rshift(x, y, z)</CODE> +<DD>A faster way to say z = x >> y. +<P> +<DT><CODE>pow(x, y, z)</CODE> +<DD>A faster way to say z = pow(x, y). +<P> +<DT><CODE>complement(x, z)</CODE> +<DD>A faster way to say z = ~x. +<P> +<DT><CODE>negate(x, z)</CODE> +<DD>A faster way to say z = -x. +<P> +</DL> +<P> +<H1><A NAME="SEC36" HREF="libgpp_toc.html#SEC36">The Rational Class</A></H1> +<P> +Class <CODE>Rational</CODE> provides multiple precision rational +number arithmetic. All rationals are maintained in simplest +form (i.e., with the numerator and denominator relatively +prime, and with the denominator strictly positive). +Rational arithmetic and relational operators are provided +(<CODE>+, -, *, /, +=, -=, *=, /=, ==, !=, <, <=, >, >=</CODE>). +Operations resulting in a rational number with zero denominator +trigger an exception. +<P> +Rationals may be constructed and used in the following ways: +<P> +<DL COMPACT> +<P> +<DT><CODE>Rational x;</CODE> +<DD>Declares an uninitialized Rational. +<P> +<DT><CODE>Rational x = 2; Rational y(2);</CODE> +<DD>Set x and y to the Rational value 2/1; +<P> +<DT><CODE>Rational x(2, 3);</CODE> +<DD>Sets x to the Rational value 2/3; +<P> +<DT><CODE>Rational x = 1.2;</CODE> +<DD>Sets x to a Rational value close to 1.2. Any double precision value +may be used to construct a Rational. The Rational will possess +exactly as much precision as the double. Double values that do +not have precise floating point equivalents (like 1.2) produce +similarly imprecise rational values. +<P> +<DT><CODE>Rational x(Integer(123), Integer(4567));</CODE> +<DD>Sets x to the Rational value 123/4567. +<P> +<DT><CODE>Rational u(x); Rational v = x;</CODE> +<DD>Set u and v to the same value as x. +<P> +<DT><CODE>double(Rational x)</CODE> +<DD>A Rational may be coerced to a double with potential +loss of precision. +/-HUGE is returned if it will not fit. +<P> +<DT><CODE>Rational abs(x)</CODE> +<DD>returns the absolute value of x. +<P> +<DT><CODE>void x.negate()</CODE> +<DD>negates x. +<P> +<DT><CODE>void x.invert()</CODE> +<DD>sets x to 1/x. +<P> +<DT><CODE>int sign(x)</CODE> +<DD>returns 0 if x is zero, 1 if positive, and -1 if negative. +<P> +<DT><CODE>Rational sqr(x)</CODE> +<DD>returns x * x. +<P> +<DT><CODE>Rational pow(x, Integer y)</CODE> +<DD>returns x to the y power. +<P> +<DT><CODE>Integer x.numerator()</CODE> +<DD>returns the numerator. +<P> +<DT><CODE>Integer x.denominator()</CODE> +<DD>returns the denominator. +<P> +<DT><CODE>Integer floor(x)</CODE> +<DD>returns the greatest Integer less than x. +<P> +<DT><CODE>Integer ceil(x)</CODE> +<DD>returns the least Integer greater than x. +<P> +<DT><CODE>Integer trunc(x)</CODE> +<DD>returns the Integer part of x. +<P> +<DT><CODE>Integer round(x)</CODE> +<DD>returns the nearest Integer to x. +<P> +<DT><CODE>int compare(x, y)</CODE> +<DD>returns a negative, zero, or positive number signifying whether x is +less than, equal to, or greater than y. +<P> +<DT><CODE>ostream << x;</CODE> +<DD>prints x in the form num/den, or just num if the denominator is one. +<P> +<DT><CODE>istream >> x;</CODE> +<DD>reads x in the form num/den, or just num in which case the +denominator is set to one. +<P> +<DT><CODE>add(x, y, z)</CODE> +<DD>A faster way to say z = x + y. +<P> +<DT><CODE>sub(x, y, z)</CODE> +<DD>A faster way to say z = x - y. +<P> +<DT><CODE>mul(x, y, z)</CODE> +<DD>A faster way to say z = x * y. +<P> +<DT><CODE>div(x, y, z)</CODE> +<DD>A faster way to say z = x / y. +<P> +<DT><CODE>pow(x, y, z)</CODE> +<DD>A faster way to say z = pow(x, y). +<P> +<DT><CODE>negate(x, z)</CODE> +<DD>A faster way to say z = -x. +<P> +</DL> +<P> +<H1><A NAME="SEC37" HREF="libgpp_toc.html#SEC37">The Complex class.</A></H1> +<P> +Class <CODE>Complex</CODE> is implemented in a way similar to that +described by Stroustrup. In keeping with libg++ conventions, +the class is named <CODE>Complex</CODE>, not <CODE>complex</CODE>. +Complex arithmetic and relational operators are provided +(<CODE>+, -, *, /, +=, -=, *=, /=, ==, !=</CODE>). +Attempted division by (0, 0) triggers an exception. +<P> +Complex numbers may be constructed and used in the following ways: +<P> +<DL COMPACT> +<P> +<DT><CODE>Complex x;</CODE> +<DD>Declares an uninitialized Complex. +<P> +<DT><CODE>Complex x = 2; Complex y(2.0);</CODE> +<DD>Set x and y to the Complex value (2.0, 0.0); +<P> +<DT><CODE>Complex x(2, 3);</CODE> +<DD>Sets x to the Complex value (2, 3); +<P> +<DT><CODE>Complex u(x); Complex v = x;</CODE> +<DD>Set u and v to the same value as x. +<P> +<DT><CODE>double real(Complex& x);</CODE> +<DD>returns the real part of x. +<P> +<DT><CODE>double imag(Complex& x);</CODE> +<DD>returns the imaginary part of x. +<P> +<DT><CODE>double abs(Complex& x);</CODE> +<DD>returns the magnitude of x. +<P> +<DT><CODE>double norm(Complex& x);</CODE> +<DD>returns the square of the magnitude of x. +<P> +<DT><CODE>double arg(Complex& x);</CODE> +<DD>returns the argument (amplitude) of x. +<P> +<DT><CODE>Complex polar(double r, double t = 0.0);</CODE> +<DD>returns a Complex with abs of r and arg of t. +<P> +<DT><CODE>Complex conj(Complex& x);</CODE> +<DD>returns the complex conjugate of x. +<P> +<DT><CODE>Complex cos(Complex& x);</CODE> +<DD>returns the complex cosine of x. +<P> +<DT><CODE>Complex sin(Complex& x);</CODE> +<DD>returns the complex sine of x. +<P> +<DT><CODE>Complex cosh(Complex& x);</CODE> +<DD>returns the complex hyperbolic cosine of x. +<P> +<DT><CODE>Complex sinh(Complex& x);</CODE> +<DD>returns the complex hyperbolic sine of x. +<P> +<DT><CODE>Complex exp(Complex& x);</CODE> +<DD>returns the exponential of x. +<P> +<DT><CODE>Complex log(Complex& x);</CODE> +<DD>returns the natural log of x. +<P> +<DT><CODE>Complex pow(Complex& x, long p);</CODE> +<DD>returns x raised to the p power. +<P> +<DT><CODE>Complex pow(Complex& x, Complex& p);</CODE> +<DD>returns x raised to the p power. +<P> +<DT><CODE>Complex sqrt(Complex& x);</CODE> +<DD>returns the square root of x. +<P> +<DT><CODE>ostream << x;</CODE> +<DD>prints x in the form (re, im). +<P> +<DT><CODE>istream >> x;</CODE> +<DD>reads x in the form (re, im), or just (re) or re in which case the +imaginary part is set to zero. +<P> +</DL> +<P> +<H1><A NAME="SEC38" HREF="libgpp_toc.html#SEC38">Fixed precision numbers</A></H1> +<P> +Classes <CODE>Fix16</CODE>, <CODE>Fix24</CODE>, <CODE>Fix32</CODE>, and <CODE>Fix48</CODE> +support operations on 16, 24, 32, or 48 bit quantities that are +considered as real numbers in the range [-1, +1). Such numbers are +often encountered in digital signal processing applications. The classes +may be be used in isolation or together. Class <CODE>Fix32</CODE> +operations are entirely self-contained. Class <CODE>Fix16</CODE> operations +are self-contained except that the multiplication operation <CODE>Fix16 +* Fix16</CODE> returns a <CODE>Fix32</CODE>. <CODE>Fix24</CODE> and <CODE>Fix48</CODE> are +similarly related. +<P> +The standard arithmetic and relational operations are supported +(<CODE>=</CODE>, <CODE>+</CODE>, <CODE>-</CODE>, <CODE>*</CODE>, <CODE>/</CODE>, <CODE><<</CODE>, <CODE>>></CODE>, +<CODE>+=</CODE>, <CODE>-=</CODE>, <CODE>*=</CODE>, <CODE>/=</CODE>, <CODE><<=</CODE>, <CODE>>>=</CODE>, +<CODE>==</CODE>, <CODE>!=</CODE>, <CODE><</CODE>, <CODE><=</CODE>, <CODE>></CODE>, <CODE>>=</CODE>). +All operations include provisions for special handling in cases where +the result exceeds +/- 1.0. There are two cases that may be handled +separately: "overflow" where the results of addition and subtraction +operations go out of range, and all other "range errors" in which +resulting values go off-scale (as with division operations, and +assignment or initialization with off-scale values). In signal +processing applications, it is often useful to handle these two cases +differently. Handlers take one argument, a reference to the integer +mantissa of the offending value, which may then be manipulated. In +cases of overflow, this value is the result of the (integer) arithmetic +computation on the mantissa; in others it is a fully saturated (i.e., +most positive or most negative) value. Handling may be reset to any of +several provided functions or any other user-defined function via +<CODE>set_overflow_handler</CODE> and <CODE>set_range_error_handler</CODE>. The +provided functions for <CODE>Fix16</CODE> are as follows (corresponding +functions are also supported for the others). +<P> +<DL COMPACT> +<P> +<DT><CODE>Fix16_overflow_saturate</CODE> +<DD>The default overflow handler. Results are "saturated": positive results +are set to the largest representable value (binary 0.111111...), and +negative values to -1.0. +<P> +<DT><CODE>Fix16_ignore</CODE> +<DD>Performs no action. For overflow, this will allow addition and +subtraction operations to "wrap around" in the same manner +as integer arithmetic, and for saturation, will leave values saturated. +<P> +<DT><CODE>Fix16_overflow_warning_saturate</CODE> +<DD>Prints a warning message on standard error, then saturates the results. +<P> +<DT><CODE>Fix16_warning</CODE> +<DD>The default range_error handler. Prints a warning message +on standard error; otherwise leaving the argument unmodified. +<P> +<DT><CODE>Fix16_abort</CODE> +<DD>prints an error message on standard error, then aborts execution. +<P> +</DL> +<P> +In addition to arithmetic operations, the following are provided: +<P> +<DL COMPACT> +<P> +<DT><CODE>Fix16 a = 0.5;</CODE> +<DD>Constructs fixed precision objects from double precision values. +Attempting to initialize to a value outside the range invokes +the range_error handler, except, as a convenience, +initialization to 1.0 sets the variable to the most positive +representable value (binary 0.1111111...) without invoking the handler. +<P> +<DT><CODE>short& mantissa(a); long& mantissa(b);</CODE> +<DD>return a * pow(2, 15) or b * pow(2, 31) as an integer. These +are returned by reference, to enable "manual" data manipulation. +<P> +<DT><CODE>double value(a); double value(b);</CODE> +<DD>return a or b as floating point numbers. +<P> +</DL> +<P> +<H1><A NAME="SEC39" HREF="libgpp_toc.html#SEC39">Classes for Bit manipulation</A></H1> +<P> +libg++ provides several different classes supporting the use +and manipulation of collections of bits in different ways. +<P> +<UL> +<P> +<LI> +Class <CODE>Integer</CODE> provides "integer" semantics. It supports +manipulation of bits in ways that are often useful when treating bit arrays +as numerical (integer) quantities. This class is described elsewhere. +<P> +<LI> +Class <CODE>BitSet</CODE> provides "set" semantics. It supports operations +useful when treating collections of bits as representing potentially +infinite sets of integers. +<P> +<LI> +Class <CODE>BitSet32</CODE> supports fixed-length BitSets holding exactly +32 bits. +<P> +<LI> +Class <CODE>BitSet256</CODE> supports fixed-length BitSets holding exactly +256 bits. +<P> +<LI> +Class <CODE>BitString</CODE> provides "string" (or "vector") semantics. +It supports operations useful when treating collections of bits as +strings of zeros and ones. +<P> +</UL> +<P> +These classes also differ in the following ways: +<P> +<UL> +<P> +<LI> +BitSets are logically infinite. Their space is dynamically altered to +adjust to the smallest number of consecutive bits actually required to +represent the sets. Integers also have this property. BitStrings are +logically finite, but their sizes are internally dynamically managed to +maintain proper length. This means that, for example, BitStrings are +concatenatable while BitSets and Integers are not. +<P> +<LI> +BitSet32 and BitSet256 have precisely the same properties as BitSets, +except that they use constant fixed length bit vectors. +<P> +<LI> +While all classes support basic unary and binary operations <CODE>~, &, +|, ^, -</CODE>, the semantics differ. BitSets perform bit operations that +precisely mirror those for infinite sets. For example, complementing an +empty BitSet returns one representing an infinite number of set bits. +Operations on BitStrings and Integers operate only on those bits +actually present in the representation. For BitStrings and Integers, +the the <CODE>&</CODE> operation returns a BitString with a length equal to +the minimum length of the operands, and <CODE>|, ^</CODE> return one with +length of the maximum. +<P> +<LI> +Only BitStrings support substring extraction and bit pattern matching. +<P> +</UL> +<P> +<H2><A NAME="SEC40" HREF="libgpp_toc.html#SEC40">BitSet</A></H2> +<P> +BitSets are objects that contain logically infinite sets of nonnegative +integers. Representational details are discussed in the Representation +chapter. Because they are logically infinite, all BitSets possess a +trailing, infinitely replicated 0 or 1 bit, called the "virtual bit", and +indicated via 0* or 1*. +<P> +BitSet32 and BitSet256 have they same properties, except they are +of fixed length, and thus have no virtual bit. +<P> +BitSets may be constructed as follows: +<P> +<DL COMPACT> +<P> +<DT><CODE>BitSet a;</CODE> +<DD>declares an empty BitSet. +<P> +<DT><CODE>BitSet a = atoBitSet("001000");</CODE> +<DD>sets a to the BitSet 0010*, reading left-to-right. The "0*" +indicates that the set ends with an infinite number of zero +(clear) bits. +<P> +<DT><CODE>BitSet a = atoBitSet("00101*");</CODE> +<DD>sets a to the BitSet 00101*, where "1*" means that the set ends +with an infinite number of one (set) bits. +<P> +<DT><CODE>BitSet a = longtoBitSet((long)23);</CODE> +<DD>sets a to the BitSet 111010*, the binary representation of decimal 23. +<P> +<DT><CODE>BitSet a = utoBitSet((unsigned)23);</CODE> +<DD>sets a to the BitSet 111010*, the binary representation of decimal 23. +<P> +</DL> +<P> +The following functions and operators are provided (Assume the +declaration of BitSets a = 0011010*, b = 101101*, throughout, as +examples). +<P> +<DL COMPACT> +<P> +<DT><CODE>~a</CODE> +<DD>returns the complement of a, or 1100101* in this case. +<P> +<DT><CODE>a.complement()</CODE> +<DD>sets a to ~a. +<P> +<DT><CODE>a & b; a &= b;</CODE> +<DD>returns a intersected with b, or 0011010*. +<P> +<DT><CODE>a | b; a |= b;</CODE> +<DD>returns a unioned with b, or 1011111*. +<P> +<DT><CODE>a - b; a -= b;</CODE> +<DD>returns the set difference of a and b, or 000010*. +<P> +<DT><CODE>a ^ b; a ^= b;</CODE> +<DD>returns the symmetric difference of a and b, or 1000101*. +<P> +<DT><CODE>a.empty()</CODE> +<DD>returns true if a is an empty set. +<P> +<DT><CODE>a == b;</CODE> +<DD>returns true if a and b contain the same set. +<P> +<DT><CODE>a <= b;</CODE> +<DD>returns true if a is a subset of b. +<P> +<DT><CODE>a < b;</CODE> +<DD>returns true if a is a proper subset of b; +<P> +<DT><CODE>a != b; a >= b; a > b;</CODE> +<DD>are the converses of the above. +<P> +<DT><CODE>a.set(7)</CODE> +<DD>sets the 7th (counting from 0) bit of a, setting a to 001111010* +<P> +<DT><CODE>a.clear(2)</CODE> +<DD>clears the 2nd bit bit of a, setting a to 00011110* +<P> +<DT><CODE>a.clear()</CODE> +<DD>clears all bits of a; +<P> +<DT><CODE>a.set()</CODE> +<DD>sets all bits of a; +<P> +<DT><CODE>a.invert(0)</CODE> +<DD>complements the 0th bit of a, setting a to 10011110* +<P> +<DT><CODE>a.set(0,1)</CODE> +<DD>sets the 0th through 1st bits of a, setting a to 110111110* +The two-argument versions of clear and invert are similar. +<P> +<DT><CODE>a.test(3)</CODE> +<DD>returns true if the 3rd bit of a is set. +<P> +<DT><CODE>a.test(3, 5)</CODE> +<DD>returns true if any of bits 3 through 5 are set. +<P> +<DT><CODE>int i = a[3]; a[3] = 0;</CODE> +<DD>The subscript operator allows bits to be inspected and changed +via standard subscript semantics, using a friend class BitSetBit. +The use of the subscript operator a[i] rather than a.test(i) +requires somewhat greater overhead. +<P> +<DT><CODE>a.first(1) or a.first()</CODE> +<DD>returns the index of the first set bit of a (2 in this case), +or -1 if no bits are set. +<P> +<DT><CODE>a.first(0)</CODE> +<DD>returns the index of the first clear bit of a (0 in this case), +or -1 if no bits are clear. +<P> +<DT><CODE>a.next(2, 1) or a.next(2)</CODE> +<DD>returns the index of the next bit after position 2 that is set (3 +in this case) or -1. <CODE>first</CODE> and <CODE>next</CODE> may be used as +iterators, as in +<CODE>for (int i = a.first(); i >= 0; i = a.next(i))...</CODE>. +<P> +<DT><CODE>a.last(1)</CODE> +<DD>returns the index of the rightmost set bit, or -1 if there or no set +bits or all set bits. +<P> +<DT><CODE>a.prev(3, 0)</CODE> +<DD>returns the index of the previous clear bit before position 3. +<P> +<DT><CODE>a.count(1)</CODE> +<DD>returns the number of set bits in a, or -1 if there are +an infinite number. +<P> +<DT><CODE>a.virtual_bit()</CODE> +<DD>returns the trailing (infinitely replicated) bit of a. +<P> +<DT><CODE>a = atoBitSet("ababX", 'a', 'b', 'X');</CODE> +<DD>converts the char* string into a bitset, with 'a' denoting false, +'b' denoting true, and 'X' denoting infinite replication. +<P> +<DT><CODE>a.printon(cout, '-', '.', 0)</CODE> +<DD>prints <CODE>a</CODE> to <CODE>cout</CODE> represented with +<CODE>'-'</CODE> for falses, <CODE>'.'</CODE> for trues, and no replication marker. +<P> +<DT><CODE>cout << a</CODE> +<DD>prints <CODE>a</CODE> to <CODE>cout</CODE> (representing lases by <CODE>'f'</CODE>, +trues by <CODE>'t'</CODE>, and using <CODE>'*'</CODE> as the replication marker). +<P> +<DT><CODE>diff(x, y, z)</CODE> +<DD>A faster way to say z = x - y. +<P> +<DT><CODE>and(x, y, z)</CODE> +<DD>A faster way to say z = x & y. +<P> +<DT><CODE>or(x, y, z)</CODE> +<DD>A faster way to say z = x | y. +<P> +<DT><CODE>xor(x, y, z)</CODE> +<DD>A faster way to say z = x ^ y. +<P> +<DT><CODE>complement(x, z)</CODE> +<DD>A faster way to say z = ~x. +<P> +</DL> +<P> +<H2><A NAME="SEC41" HREF="libgpp_toc.html#SEC41">BitString</A></H2> +<P> +BitStrings are objects that contain arbitrary-length strings of +zeroes and ones. BitStrings possess some features that make them +behave like sets, and others that behave as strings. They are +useful in applications (such as signature-based algorithms) where +both capabilities are needed. Representational details are +discussed in the Representation chapter. Most capabilities are +exact analogs of those supported in the BitSet and String +classes. A BitSubString is used with substring operations along +the same lines as the String SubString class. A BitPattern class +is used for masked bit pattern searching. +<P> +Only a default constructor is supported. The declaration +<CODE>BitString a;</CODE> initializes a to be an empty BitString. +BitStrings may often be initialized via <CODE>atoBitString</CODE> +and <CODE>longtoBitString</CODE>. +<P> +Set operations (<CODE> ~, complement, &, &=, |, |=, -, ^, ^=</CODE>) +behave just as the BitSet versions, except that there is no +"virtual bit": complementing complements only those bits in the +BitString, and all binary operations across unequal length +BitStrings assume a virtual bit of zero. The <CODE>&</CODE> operation +returns a BitString with a length equal to the minimum length of +the operands, and <CODE>|, ^</CODE> return one with length of the +maximum. +<P> +Set-based relational operations (<CODE>==, !=, <=, <, >=, ></CODE>) +follow the same rules. A string-like lexicographic comparison +function, <CODE>lcompare</CODE>, tests the lexicographic relation between +two BitStrings. For example, lcompare(1100, 0101) returns 1, +since the first BitString starts with 1 and the second with 0. +<P> +Individual bit setting, testing, and iterator operations +(<CODE>set, clear, invert, test, first, next, last, prev</CODE>) +are also like those for BitSets. BitStrings are automatically +expanded when setting bits at positions greater than their +current length. +<P> +The string-based capabilities are just as those for class String. +BitStrings may be concatenated (<CODE>+, +=</CODE>), searched +(<CODE>index, contains, matches</CODE>), and extracted into +BitSubStrings (<CODE>before, at, after</CODE>) which may be assigned and +otherwise manipulated. Other string-based utility functions +(<CODE>reverse, common_prefix, common_suffix</CODE>) are also provided. +These have the same capabilities and descriptions as those +for Strings. +<P> +String-oriented operations can also be performed with a mask via +class BitPattern. BitPatterns consist of two BitStrings, a +pattern and a mask. On searching and matching, bits in the pattern +that correspond to 0 bits in the mask are ignored. (The mask may +be shorter than the pattern, in which case trailing mask bits are +assumed to be 0). The pattern and mask are both public variables, +and may be individually subjected to other bit operations. +<P> +Converting to char* and printing (<CODE>(atoBitString, +atoBitPattern, printon, ostream <<)</CODE>) are also as in BitSets, +except that no virtual bit is used, and an 'X' in a BitPattern means +that the pattern bit is masked out. +<P> +The following features are unique to BitStrings. +<P> +Assume declarations of BitString a = atoBitString("01010110") and b = +atoBitSTring("1101"). +<P> +<DL COMPACT> +<P> +<DT><CODE>a = b + c;</CODE> +<DD>Sets a to the concatenation of b and c; +<P> +<DT><CODE>a = b + 0; a = b + 1;</CODE> +<DD>sets a to b, appended with a zero (one). +<P> +<DT><CODE>a += b;</CODE> +<DD>appends b to a; +<P> +<DT><CODE>a += 0; a += 1;</CODE> +<DD>appends a zero (one) to a. +<P> +<DT><CODE>a << 2; a <<= 2</CODE> +<DD>return a with 2 zeros prepended, setting a to 0001010110. (Note +the necessary confusion of << and >> operators. For consistency +with the integer versions, << shifts low bits to high, even though +they are printed low bits first.) +<P> +<DT><CODE>a >> 3; a >>= 3</CODE> +<DD>return a with the first 3 bits deleted, setting a to 10110. +<P> +<DT><CODE>a.left_trim(0)</CODE> +<DD>deletes all 0 bits on the left of a, setting a to 1010110. +<P> +<DT><CODE>a.right_trim(0)</CODE> +<DD>deletes all trailing 0 bits of a, setting a to 0101011. +<P> +<DT><CODE>cat(x, y, z)</CODE> +<DD>A faster way to say z = x + y. +<P> +<DT><CODE>diff(x, y, z)</CODE> +<DD>A faster way to say z = x - y. +<P> +<DT><CODE>and(x, y, z)</CODE> +<DD>A faster way to say z = x & y. +<P> +<DT><CODE>or(x, y, z)</CODE> +<DD>A faster way to say z = x | y. +<P> +<DT><CODE>xor(x, y, z)</CODE> +<DD>A faster way to say z = x ^ y. +<P> +<DT><CODE>lshift(x, y, z)</CODE> +<DD>A faster way to say z = x << y. +<P> +<DT><CODE>rshift(x, y, z)</CODE> +<DD>A faster way to say z = x >> y. +<P> +<DT><CODE>complement(x, z)</CODE> +<DD>A faster way to say z = ~x. +<P> +</DL> +<P> +<H1><A NAME="SEC42" HREF="libgpp_toc.html#SEC42">Random Number Generators and related classes</A></H1> +<P> +The two classes <CODE>RNG</CODE> and <CODE>Random</CODE> are used together to +generate a variety of random number distributions. A distinction must +be made between <EM>random number generators</EM>, implemented by class +<CODE>RNG</CODE>, and <EM>random number distributions</EM>. A random number +generator produces a series of randomly ordered bits. These bits can be +used directly, or cast to other representations, such as a floating +point value. A random number generator should produce a <EM>uniform</EM> +distribution. A random number distribution, on the other hand, uses the +randomly generated bits of a generator to produce numbers from a +distribution with specific properties. Each instance of <CODE>Random</CODE> +uses an instance of class <CODE>RNG</CODE> to provide the raw, uniform +distribution used to produce the specific distribution. Several +instances of <CODE>Random</CODE> classes can share the same instance of +<CODE>RNG</CODE>, or each instance can use its own copy. +<P> +<H2><A NAME="SEC43" HREF="libgpp_toc.html#SEC43">RNG</A></H2> +<P> +Random distributions are constructed from members of class <CODE>RNG</CODE>, +the actual random number generators. The <CODE>RNG</CODE> class contains no +data; it only serves to define the interface to random number +generators. The <CODE>RNG::asLong</CODE> member returns an unsigned long +(typically 32 bits) of random bits. Applications that require a number +of random bits can use this directly. More often, these random bits are +transformed to a uniform random number: +<P> +<PRE> + // + // Return random bits converted to either a float or a double + // + float asFloat(); + double asDouble(); +}; +</PRE> +<P> +using either <CODE>asFloat</CODE> or <CODE>asDouble</CODE>. It is intended that +<CODE>asFloat</CODE> and <CODE>asDouble</CODE> return differing precisions; +typically, <CODE>asDouble</CODE> will draw two random longwords and transform +them into a legal <CODE>double</CODE>, while <CODE>asFloat</CODE> will draw a single +longword and transform it into a legal <CODE>float</CODE>. These members are +used by subclasses of the <CODE>Random</CODE> class to implement a variety of +random number distributions. +<P> +<H2><A NAME="SEC44" HREF="libgpp_toc.html#SEC44">ACG</A></H2> +<P> +Class <CODE>ACG</CODE> is a variant of a Linear Congruential Generator +(Algorithm M) described in Knuth, <EM>Art of Computer Programming, Vol +III</EM>. This result is permuted with a Fibonacci Additive Congruential +Generator to get good independence between samples. This is a very high +quality random number generator, although it requires a fair amount of +memory for each instance of the generator. +<P> +The <CODE>ACG::ACG</CODE> constructor takes two parameters: the seed and the +size. The seed is any number to be used as an initial seed. The +performance of the generator depends on having a distribution of bits +through the seed. If you choose a number in the range of 0 to 31, a +seed with more bits is chosen. Other values are deterministically +modified to give a better distribution of bits. This provides a good +random number generator while still allowing a sequence to be repeated +given the same initial seed. +<P> +The <CODE>size</CODE> parameter determines the size of two tables used in the +generator. The first table is used in the Additive Generator; see the +algorithm in Knuth for more information. In general, this table is +<CODE>size</CODE> longwords long. The default value, used in the algorithm in +Knuth, gives a table of 220 bytes. The table size affects the period of +the generators; smaller values give shorter periods and larger tables +give longer periods. The smallest table size is 7 longwords, and the +longest is 98 longwords. The <CODE>size</CODE> parameter also determines the +size of the table used for the Linear Congruential Generator. This value +is chosen implicitly based on the size of the Additive Congruential +Generator table. It is two powers of two larger than the power of two +that is larger than <CODE>size</CODE>. For example, if <CODE>size</CODE> is 7, the +ACG table is 7 longwords and the LCG table is 128 longwords. Thus, the +default size (55) requires 55 + 256 longwords, or 1244 bytes. The +largest table requires 2440 bytes and the smallest table requires 100 +bytes. Applications that require a large number of generators or +applications that aren't so fussy about the quality of the generator may +elect to use the <CODE>MLCG</CODE> generator. +<P> +<H2><A NAME="SEC45" HREF="libgpp_toc.html#SEC45">MLCG</A></H2> +<P> +The <CODE>MLCG</CODE> class implements a <EM>Multiplicative Linear +Congruential Generator</EM>. In particular, it is an implementation of the +double MLCG described in <EM>"Efficient and Portable Combined Random +Number Generators"</EM> by Pierre L'Ecuyer, appearing in +<EM>Communications of the ACM, Vol. 31. No. 6</EM>. This generator has a +fairly long period, and has been statistically analyzed to show that it +gives good inter-sample independence. +<P> +The <CODE>MLCG::MLCG</CODE> constructor has two parameters, both of which are +seeds for the generator. As in the <CODE>MLCG</CODE> generator, both seeds are +modified to give a "better" distribution of seed digits. Thus, you can +safely use values such as `0' or `1' for the seeds. The <CODE>MLCG</CODE> +generator used much less state than the <CODE>ACG</CODE> generator; only two +longwords (8 bytes) are needed for each generator. +<P> +<H2><A NAME="SEC46" HREF="libgpp_toc.html#SEC46">Random</A></H2> +<P> +A random number generator may be declared by first declaring a +<CODE>RNG</CODE> and then a <CODE>Random</CODE>. For example, <CODE>ACG gen(10, 20); +NegativeExpntl rnd (1.0, &gen);</CODE> declares an additive congruential +generator with seed 10 and table size 20, that is used to generate +exponentially distributed values with mean of 1.0. +<P> +The virtual member <CODE>Random::operator()</CODE> is the common way of +extracting a random number from a particular distribution. The base +class, <CODE>Random</CODE> does not implement <CODE>operator()</CODE>. This is +performed by each of the subclasses. Thus, given the above declaration +of <CODE>rnd</CODE>, new random values may be obtained via, for example, +<CODE>double next_exp_rand = rnd();</CODE> Currently, the following subclasses +are provided. +<P> +<H2><A NAME="SEC47" HREF="libgpp_toc.html#SEC47">Binomial</A></H2> +<P> +The binomial distribution models successfully drawing items from +a pool. The first parameter to the constructor, <CODE>n</CODE>, is the +number of items in the pool, and the second parameter, <CODE>u</CODE>, +is the probability of each item being successfully drawn. The +member <CODE>asDouble</CODE> returns the number of samples drawn from +the pool. Although it is not checked, it is assumed that +<CODE>n>0</CODE> and <CODE>0 <= u <= 1</CODE>. The remaining members allow +you to read and set the parameters. +<P> +<H2><A NAME="SEC48" HREF="libgpp_toc.html#SEC48">Erlang</A></H2> +<P> +The <CODE>Erlang</CODE> class implements an Erlang distribution with +mean <CODE>mean</CODE> and variance <CODE>variance</CODE>. +<P> +<H2><A NAME="SEC49" HREF="libgpp_toc.html#SEC49">Geometric</A></H2> +<P> +The <CODE>Geometric</CODE> class implements a discrete geometric +distribution. The first parameter to the constructor, +<CODE>mean</CODE>, is the mean of the distribution. Although it is not +checked, it is assumed that <CODE>0 <= mean <= 1</CODE>. +<CODE>Geometric()</CODE> returns the number of uniform random samples +that were drawn before the sample was larger than <CODE>mean</CODE>. +This quantity is always greater than zero. +<P> +<H2><A NAME="SEC50" HREF="libgpp_toc.html#SEC50">HyperGeometric</A></H2> +<P> +The <CODE>HyperGeometric</CODE> class implements the hypergeometric +distribution. The first parameter to the constructor, +<CODE>mean</CODE>, is the mean and the second, <CODE>variance</CODE>, is the +variance. The remaining members allow you to inspect and change +the mean and variance. +<P> +<H2><A NAME="SEC51" HREF="libgpp_toc.html#SEC51">NegativeExpntl</A></H2> +<P> +The <CODE>NegativeExpntl</CODE> class implements the negative +exponential distribution. The first parameter to the constructor +is the mean. The remaining members allow you to inspect and +change the mean. +<P> +<H2><A NAME="SEC52" HREF="libgpp_toc.html#SEC52">Normal</A></H2> +<P> +The <CODE>Normal</CODE>class implements the normal distribution. The +first parameter to the constructor, <CODE>mean</CODE>, is the mean and +the second, <CODE>variance</CODE>, is the variance. The remaining +members allow you to inspect and change the mean and variance. +The <CODE>LogNormal</CODE> class is a subclass of <CODE>Normal</CODE>. +<P> +<H2><A NAME="SEC53" HREF="libgpp_toc.html#SEC53">LogNormal</A></H2> +<P> +The <CODE>LogNormal</CODE>class implements the logarithmic normal +distribution. The first parameter to the constructor, +<CODE>mean</CODE>, is the mean and the second, <CODE>variance</CODE>, is the +variance. The remaining members allow you to inspect and change +the mean and variance. The <CODE>LogNormal</CODE> class is a subclass +of <CODE>Normal</CODE>. +<P> +<H2><A NAME="SEC54" HREF="libgpp_toc.html#SEC54">Poisson</A></H2> +<P> +The <CODE>Poisson</CODE> class implements the poisson distribution. +The first parameter to the constructor is the mean. The +remaining members allow you to inspect and change the mean. +<P> +<H2><A NAME="SEC55" HREF="libgpp_toc.html#SEC55">DiscreteUniform</A></H2> +<P> +The <CODE>DiscreteUniform</CODE> class implements a uniform random variable over +the closed interval ranging from <CODE>[low..high]</CODE>. The first parameter +to the constructor is <CODE>low</CODE>, and the second is <CODE>high</CODE>, although +the order of these may be reversed. The remaining members allow you to +inspect and change <CODE>low</CODE> and <CODE>high</CODE>. +<P> +<H2><A NAME="SEC56" HREF="libgpp_toc.html#SEC56">Uniform</A></H2> +<P> +The <CODE>Uniform</CODE> class implements a uniform random variable over the +open interval ranging from <CODE>[low..high)</CODE>. The first parameter to +the constructor is <CODE>low</CODE>, and the second is <CODE>high</CODE>, although +the order of these may be reversed. The remaining members allow you to +inspect and change <CODE>low</CODE> and <CODE>high</CODE>.<P> +<H2><A NAME="SEC57" HREF="libgpp_toc.html#SEC57">Weibull</A></H2> +<P> +The <CODE>Weibull</CODE> class implements a weibull distribution with +parameters <CODE>alpha</CODE> and <CODE>beta</CODE>. The first parameter to +the class constructor is <CODE>alpha</CODE>, and the second parameter +is <CODE>beta</CODE>. The remaining members allow you to inspect and +change <CODE>alpha</CODE> and <CODE>beta</CODE>. +<P> +<H2><A NAME="SEC58" HREF="libgpp_toc.html#SEC58">RandomInteger</A></H2> +<P> +The <CODE>RandomInteger</CODE> class is <EM>not</EM> a subclass of Random, +but a stand-alone integer-oriented class that is dependent on the +RNG classes. RandomInteger returns random integers uniformly from +the closed interval <CODE>[low..high]</CODE>. The first parameter to the +constructor is <CODE>low</CODE>, and the second is <CODE>high</CODE>, although +both are optional. The last argument is always a generator. +Additional members allow you to inspect and change <CODE>low</CODE> and +<CODE>high</CODE>. Random integers are generated using <CODE>asInt()</CODE> or +<CODE>asLong()</CODE>. Operator syntax (<CODE>()</CODE>) is also available as a +shorthand for <CODE>asLong()</CODE>. Because <CODE>RandomInteger</CODE> is often +used in simulations for which uniform random integers are desired over +a variety of ranges, <CODE>asLong()</CODE> and <CODE>asInt</CODE> have <CODE>high</CODE> +as an optional argument. Using this optional argument produces a +single value from the new range, but does not change the default +range. +<P> +<H1><A NAME="SEC59" HREF="libgpp_toc.html#SEC59">Data Collection</A></H1> +Libg++ currently provides two classes for <EM>data collection</EM> +and analysis of the collected data. +<P> +<H2><A NAME="SEC60" HREF="libgpp_toc.html#SEC60">SampleStatistic</A></H2> +<P> +Class <CODE>SampleStatistic</CODE> provides a means of accumulating +samples of <CODE>double</CODE> values and providing common sample statistics. +<P> +Assume declaration of <CODE>double x</CODE>. +<P> +<DL COMPACT> +<P> +<DT><CODE>SampleStatistic a;</CODE> +<DD>declares and initializes a. +<P> +<DT><CODE>a.reset();</CODE> +<DD>re-initializes a. +<P> +<DT><CODE>a += x;</CODE> +<DD>adds sample x. +<P> +<DT><CODE>int n = a.samples();</CODE> +<DD>returns the number of samples. +<P> +<DT><CODE>x = a.mean;</CODE> +<DD>returns the means of the samples. +<P> +<DT><CODE>x = a.var()</CODE> +<DD>returns the sample variance of the samples. +<P> +<DT><CODE>x = a.stdDev()</CODE> +<DD>returns the sample standard deviation of the samples. +<P> +<DT><CODE>x = a.min()</CODE> +<DD>returns the minimum encountered sample. +<P> +<DT><CODE>x = a.max()</CODE> +<DD>returns the maximum encountered sample. +<P> +<DT><CODE>x = a.confidence(int p)</CODE> +<DD>returns the p-percent (0 <= p < 100) confidence interval. +<P> +<DT><CODE>x = a.confidence(double p)</CODE> +<DD>returns the p-probability (0 <= p < 1) confidence interval. +<P> +</DL> +<P> +<H2><A NAME="SEC61" HREF="libgpp_toc.html#SEC61">SampleHistogram</A></H2> +<P> +Class <CODE>SampleHistogram</CODE> is a derived class of +<CODE>SampleStatistic</CODE> that supports collection and display of samples +in bucketed intervals. It supports the following in addition to +<CODE>SampleStatisic</CODE> operations. +<P> +<DL COMPACT> +<P> +<DT><CODE>SampleHistogram h(double lo, double hi, double width);</CODE> +<DD>declares and initializes h to have buckets of size width from lo to hi. +If the optional argument width is not specified, 10 buckets are +created. The first bucket and also holds samples less than lo, +and the last one holds samples greater than hi. +<P> +<DT><CODE>int n = h.similarSamples(x)</CODE> +<DD>returns the number of samples in the same bucket as x. +<P> +<DT><CODE>int n = h.inBucket(int i)</CODE> +<DD>returns the number of samples in bucket i. +<P> +<DT><CODE>int b = h.buckets()</CODE> +<DD>returns the number of buckets. +<P> +<DT><CODE>h.printBuckets(ostream s)</CODE> +<DD>prints bucket counts on ostream s. +<P> +<DT><CODE>double bound = h.bucketThreshold(int i)</CODE> +<DD>returns the upper bound of bucket i. +<P> +</DL> +<P> +<H1><A NAME="SEC62" HREF="libgpp_toc.html#SEC62">Curses-based classes</A></H1> +<P> +The <CODE>CursesWindow</CODE> class is a repackaging of standard +curses library features into a class. It relies on <TT>`curses.h'</TT>. +<P> +The supplied <TT>`curses.h'</TT> is a fairly conservative declaration +of curses library features, and does not include features like +"screen" or X-window support. It is, for the most part, an +adaptation, rather than an improvement of C-based <TT>`curses.h'</TT> +files. The only substantive changes are the declarations of +many functions as inline functions rather than macros, which +was done solely to allow overloading. +<P> +The <CODE>CursesWindow</CODE> class encapsulates curses window functions +within a class. Only those functions that control windows are included: +Terminal control functions and macros like <CODE>cbreak</CODE> are not part +of the class. All <CODE>CursesWindows</CODE> member functions have names +identical to the corresponding curses library functions, except that the +"w" prefix is generally dropped. Descriptions of these functions may +be found in your local curses library documentation. +<P> +A <CODE>CursesWindow</CODE> may be declared via +<P> +<DL COMPACT> +<P> +<DT><CODE>CursesWindow w(WINDOW* win)</CODE> +<DD>attaches w to the existing WINDOW* win. This is constructor is normally +used only in the following special case. +<P> +<DT><CODE>CursesWindow w(stdscr)</CODE> +<DD>attaches w to the default curses library standard screen window. +<P> +<DT><CODE>CursesWindow w(int lines, int cols, int begin_y, int begin_x)</CODE> +<DD>attaches to an allocated curses window with the indicated size and +screen position. +<P> +<DT><CODE>CursesWindow sub(CursesWindow& w,int l,int c,int by,int bx,char ar='a')</CODE> +<DD>attaches to a subwindow of w created via the curses `subwin' command. +If ar is sent as `r', the origin (by, bx) is relative to the parent +window, else it is absolute. +<P> +</DL> +<P> +The class maintains a static counter that is used in order to +automatically call the curses library <CODE>initscr</CODE> and <CODE>endscr</CODE> +functions at the proper times. These need not, and should not be +called "manually". +<P> +<CODE>CursesWindow</CODE>s maintain a tree of their subwindows. Upon +destruction of a <CODE>CursesWindow</CODE>, all of their subwindows are +also invalidated if they had not previously been destroyed. +<P> +It is possible to traverse trees of subwindows via the following +member functions +<P> +<DL COMPACT> +<P> +<DT><CODE>CursesWindow* w.parent()</CODE> +<DD>returns a pointer to the parent of the subwindow, or 0 if there is none. +<P> +<DT><CODE>CursesWindow* w.child()</CODE> +<DD>returns the first child subwindow of the window, or 0 if there is none. +<P> +<DT><CODE>CursesWindow* w.sibling()</CODE> +<DD>returns the next sibling of the subwindow, or 0 if there is none. +<P> +</DL> +<P> +For example, to call some function <CODE>visit</CODE> for all subwindows +of a window, you could write +<P> +<PRE> + +void traverse(CursesWindow& w) +{ + visit(w); + if (w.child() != 0) traverse(*w.child); + if (w.sibling() != 0) traverse(*w.sibling); +} + +</PRE> + +<H1><A NAME="SEC63" HREF="libgpp_toc.html#SEC63">List classes</A></H1> +<P> +The files <TT>`g++-include/List.hP'</TT> and <TT>`g++-include/List.ccP'</TT> +provide pseudo-generic Lisp-type List classes. These lists are homogeneous +lists, more similar to lists in statically typed functional languages like +ML than Lisp, but support operations very similar to those found in Lisp. +Any particular kind of list class may be generated via the <CODE>genclass</CODE> +shell command. However, the implementation assumes that the base class +supports an equality operator <CODE>==</CODE>. All equality tests use the +<CODE>==</CODE> operator, and are thus equivalent to the use of <CODE>equal</CODE>, not +<CODE>eq</CODE> in Lisp.<P> +All list nodes are created dynamically, and managed via reference counts. +<CODE>List</CODE> variables are actually pointers to these list nodes. +Lists may also be traversed via Pixes, as described in the section +describing Pixes. See section <A HREF="libgpp.html#SEC15">Pseudo-indexes</A> +<P> +Supported operations are mirrored closely after those in Lisp. Generally, +operations with functional forms are constructive, functional operations, +while member forms (often with the same name) are sometimes +procedural, possibly destructive operations. +<P> +As with Lisp, destructive operations are supported. Programmers +are allowed to change head and tail fields in any fashion, creating +circular structures and the like. However, again as with Lisp, some +operations implicitly assume that they are operating on pure lists, and +may enter infinite loops when presented with improper lists. Also, the +reference-counting storage management facility may fail to reclaim +unused circularly-linked nodes. +<P> +Several Lisp-like higher order functions are supported (e.g., <CODE>map</CODE>). +Typedef declarations for the required functional forms are provided +int the <TT>`.h'</TT> file. +<P> +For purposes of illustration, assume the specification of class +<CODE>intList</CODE>. Common Lisp versions of supported operations are shown +in brackets for comparison purposes. +<P> +<H2><A NAME="SEC64" HREF="libgpp_toc.html#SEC64">Constructors and assignment</A></H2> +<P> +<DL COMPACT> +<P> +<DT><CODE>intList a; [ (setq a nil) ]</CODE> +<DD>Declares a to be a nil intList. +<P> +<DT><CODE>intList b(2); [ (setq b (cons 2 nil)) ]</CODE> +<DD>Declares b to be an intList with a head value of 2, and a nil tail. +<P> +<DT><CODE>intList c(3, b); [ (setq c (cons 3 b)) ]</CODE> +<DD>Declares c to be an intList with a head value of 3, and b as its tail. +<P> +<DT><CODE>b = a; [ (setq b a) ]</CODE> +<DD>Sets b to be the same list as a. +<P> +</DL> +<P> +Assume the declarations of intLists a, b, and c in the following. +See section <A HREF="libgpp.html#SEC15">Pseudo-indexes</A>. +<P> +<H2><A NAME="SEC65" HREF="libgpp_toc.html#SEC65">List status</A></H2> +<P> +<DL COMPACT> +<P> +<DT><CODE>a.null(); OR !a; [ (null a) ]</CODE> +<DD>returns true if a is null. +<P> +<DT><CODE>a.valid(); [ (listp a) ]</CODE> +<DD>returns true if a is non-null. Inside a conditional test, the +<CODE>void*</CODE> coercion may also be used as in <CODE>if (a) ...</CODE>. +<P> +<DT><CODE>intList(); [ nil ]</CODE> +<DD>intList() may be used to null terminate a list, as in +<CODE>intList f(int x) {if (x == 0) return intList(); ... } </CODE>. +<P> +<DT><CODE>a.length(); [ (length a) ]</CODE> +<DD>returns the length of a. +<P> +<DT><CODE>a.list_length(); [ (list-length a) ]</CODE> +<DD>returns the length of a, or -1 if a is circular. +</DL> +<P> +<H2><A NAME="SEC66" HREF="libgpp_toc.html#SEC66">heads and tails</A></H2> +<P> +<DL COMPACT> +<P> +<DT><CODE>a.get(); OR a.head() [ (car a) ]</CODE> +<DD>returns a reference to the head field. +<P> +<DT><CODE>a[2]; [ (elt a 2) ]</CODE> +<DD>returns a reference to the second (counting from zero) head field. +<P> +<DT><CODE>a.tail(); [ (cdr a) ]</CODE> +<DD>returns the intList that is the tail of a. +<P> +<DT><CODE>a.last(); [ (last a) ]</CODE> +<DD>returns the intList that is the last node of a. +<P> +<DT><CODE>a.nth(2); [ (nth a 2) ]</CODE> +<DD>returns the intList that is the nth node of a. +<P> +<DT><CODE>a.set_tail(b); [ (rplacd a b) ]</CODE> +<DD>sets a's tail to b. +<P> +<DT><CODE>a.push(2); [ (push 2 a) ]</CODE> +<DD>equivalent to a = intList(2, a); +<P> +<DT><CODE>int x = a.pop() [ (setq x (car a)) (pop a) ]</CODE> +<DD>returns the head of a, also setting a to its tail. +<P> +</DL> +<P> +<H2><A NAME="SEC67" HREF="libgpp_toc.html#SEC67">Constructive operations</A></H2> +<P> +<DL COMPACT> +<P> +<DT><CODE>b = copy(a); [ (setq b (copy-seq a)) ]</CODE> +<DD>sets b to a copy of a. +<P> +<DT><CODE>b = reverse(a); [ (setq b (reverse a)) ]</CODE> +<DD>Sets b to a reversed copy of a. +<P> +<DT><CODE>c = concat(a, b); [ (setq c (concat a b)) ]</CODE> +<DD>Sets c to a concatenated copy of a and b. +<P> +<DT><CODE>c = append(a, b); [ (setq c (append a b)) ]</CODE> +<DD>Sets c to a concatenated copy of a and b. All nodes of a are +copied, with the last node pointing to b. +<P> +<DT><CODE>b = map(f, a); [ (setq b (mapcar f a)) ]</CODE> +<DD>Sets b to a new list created by applying function f to each node +of a. +<P> +<DT><CODE>c = combine(f, a, b);</CODE> +<DD>Sets c to a new list created by applying function f to successive +pairs of a and b. The resulting list has length the shorter of a +and b. +<P> +<DT><CODE>b = remove(x, a); [ (setq b (remove x a)) ]</CODE> +<DD>Sets b to a copy of a, omitting all occurrences of x. +<P> +<DT><CODE>b = remove(f, a); [ (setq b (remove-if f a)) ]</CODE> +<DD>Sets b to a copy of a, omitting values causing function f to +return true. +<P> +<DT><CODE>b = select(f, a); [ (setq b (remove-if-not f a)) ]</CODE> +<DD>Sets b to a copy of a, omitting values causing function f to +return false. +<P> +<DT><CODE>c = merge(a, b, f); [ (setq c (merge a b f)) ]</CODE> +<DD>Sets c to a list containing the ordered elements (using the +comparison function f) of the sorted lists a and b. +<P> +</DL> +<P> +<H2><A NAME="SEC68" HREF="libgpp_toc.html#SEC68">Destructive operations</A></H2> +<P> +<DL COMPACT> +<P> +<DT><CODE>a.append(b); [ (rplacd (last a) b) ]</CODE> +<DD>appends b to the end of a. No new nodes are constructed. +<P> +<DT><CODE>a.prepend(b); [ (setq a (append b a)) ]</CODE> +<DD>prepends b to the beginning of a. +<P> +<DT><CODE>a.del(x); [ (delete x a) ]</CODE> +<DD>deletes all nodes with value x from a. +<P> +<DT><CODE>a.del(f); [ (delete-if f a) ]</CODE> +<DD>deletes all nodes causing function f to return true. +<P> +<DT><CODE>a.select(f); [ (delete-if-not f a) ]</CODE> +<DD>deletes all nodes causing function f to return false. +<P> +<DT><CODE>a.reverse(); [ (nreverse a) ]</CODE> +<DD>reverses a in-place. +<P> +<DT><CODE>a.sort(f); [ (sort a f) ]</CODE> +<DD>sorts a in-place using ordering (comparison) function f. +<P> +<DT><CODE>a.apply(f); [ (mapc f a) ]</CODE> +<DD>Applies void function f (int x) to each element of a. +<P> +<DT><CODE>a.subst(int old, int repl); [ (nsubst repl old a) ]</CODE> +<DD>substitutes repl for each occurrence of old in a. Note the +different argument order than the Lisp version. +<P> +</DL> +<P> +<H2><A NAME="SEC69" HREF="libgpp_toc.html#SEC69">Other operations</A></H2> +<P> +<DL COMPACT> +<P> +<DT><CODE>a.find(int x); [ (find x a) ]</CODE> +<DD>returns the intList at the first occurrence of x. +<P> +<DT><CODE>a.find(b); [ (find b a) ]</CODE> +<DD>returns the intList at the first occurrence of sublist b. +<P> +<DT><CODE>a.contains(int x); [ (member x a) ]</CODE> +<DD>returns true if a contains x. +<P> +<DT><CODE>a.contains(b); [ (member b a) ]</CODE> +<DD>returns true if a contains sublist b. +<P> +<DT><CODE>a.position(int x); [ (position x a) ]</CODE> +<DD>returns the zero-based index of x in a, or -1 if x does not occur. +<P> +<DT><CODE>int x = a.reduce(f, int base); [ (reduce f a :initial-value base) ]</CODE> +<DD>Accumulates the result of applying int function f(int, int) to +successive elements of a, starting with base. +<P> +</DL> +<P> +<H1><A NAME="SEC70" HREF="libgpp_toc.html#SEC70">Linked Lists</A></H1> +<P> +SLLists provide pseudo-generic singly linked lists. DLLists provide +doubly linked lists. The lists are designed for the simple maintenance +of elements in a linked structure, and do not provide the more extensive +operations (or node-sharing) of class <CODE>List</CODE>. They behave similarly +to the <CODE>slist</CODE> and similar classes described by Stroustrup.<P> +All list nodes are created dynamically. Assignment is performed via +copying. +<P> +Class <CODE>DLList</CODE> supports all <CODE>SLList</CODE> operations, plus +additional operations described below. +<P> +For purposes of illustration, assume the specification of class +<CODE>intSLList</CODE>. In addition to the operations listed here, +SLLists support traversal via Pixes. See section <A HREF="libgpp.html#SEC15">Pseudo-indexes</A> +<P> +<DL COMPACT> +<P> +<DT><CODE>intSLList a;</CODE> +<DD>Declares a to be an empty list. +<P> +<DT><CODE>intSLList b = a;</CODE> +<DD>Sets b to an element-by-element copy of a. +<P> +<DT><CODE>a.empty()</CODE> +<DD>returns true if a contains no elements +<P> +<DT><CODE>a.length();</CODE> +<DD>returns the number of elements in a. +<P> +<DT><CODE>a.prepend(x);</CODE> +<DD>places x at the front of the list. +<P> +<DT><CODE>a.append(x);</CODE> +<DD>places x at the end of the list. +<P> +<DT><CODE>a.join(b)</CODE> +<DD>places all nodes from b to the end of a, simultaneously destroying b. +<P> +<DT><CODE>x = a.front()</CODE> +<DD>returns a reference to the item stored at the head of the list, +or triggers an error if the list is empty. +<P> +<DT><CODE>a.rear()</CODE> +<DD>returns a reference to the rear of the list, or triggers an error if the +list is empty. +<P> +<DT><CODE>x = a.remove_front()</CODE> +<DD>deletes and returns the item stored at the head of the list. +<P> +<DT><CODE>a.del_front()</CODE> +<DD>deletes the first element, without returning it. +<P> +<DT><CODE>a.clear()</CODE> +<DD>deletes all items from the list. +<P> +<DT><CODE>a.ins_after(Pix i, item);</CODE> +<DD>inserts item after position i. If i is null, insertion is at the front. +<P> +<DT><CODE>a.del_after(Pix i);</CODE> +<DD>deletes the element following i. If i is 0, the first item is deleted. +<P> +</DL> +<P> +<H2><A NAME="SEC71" HREF="libgpp_toc.html#SEC71">Doubly linked lists</A></H2> +<P> +Class <CODE>DLList</CODE> supports the following additional operations, +as well as backward traversal via Pixes. +<P> +<DL COMPACT> +<P> +<DT><CODE>x = a.remove_rear();</CODE> +<DD>deletes and returns the item stored at the rear of the list. +<P> +<DT><CODE>a.del_rear();</CODE> +<DD>deletes the last element, without returning it. +<P> +<DT><CODE>a.ins_before(Pix i, x)</CODE> +<DD>inserts x before the i. +<P> +<DT><CODE>a.del(Pix& iint dir = 1)</CODE> +<DD>deletes the item at the current position, then advances forward +if dir is positive, else backward. +<P> +</DL> +<P> +<H1><A NAME="SEC72" HREF="libgpp_toc.html#SEC72">Vector classes</A></H1> +<P> +The files <TT>`g++-include/Vec.ccP'</TT> and <TT>`g++-include/AVec.ccP'</TT> +provide pseudo-generic standard array-based vector operations. The +corresponding header files are <TT>`g++-include/Vec.hP'</TT> and +<TT>`g++-include/AVec.hP'</TT>. Class <CODE>Vec</CODE> provides operations +suitable for any base class that includes an equality operator. Subclass +<CODE>AVec</CODE> provides additional arithmetic operations suitable for base +classes that include the full complement of arithmetic operators. +<P> +<CODE>Vecs</CODE> are constructed and assigned by copying. Thus, they should +normally be passed by reference in applications programs. +<P> +Several mapping functions are provided that allow programmers to +specify operations on vectors as a whole. +<P> +For illustrative purposes assume that classes <CODE>intVec</CODE> and +<CODE>intAVec</CODE> have been generated via <CODE>genclass</CODE>. +<P> +<H2><A NAME="SEC73" HREF="libgpp_toc.html#SEC73">Constructors and assignment</A></H2> +<P> +<DL COMPACT> +<DT><CODE>intVec a;</CODE> +<DD>declares a to be an empty vector. Its size may be changed via resize. +<P> +<DT><CODE>intVec a(10);</CODE> +<DD>declares a to be an uninitialized vector of ten elements (numbered 0-9). +<P> +<DT><CODE>intVec b(6, 0);</CODE> +<DD>declares b to be a vector of six elements, all initialized to zero. Any +value can be used as the initial fill argument. +<P> +<DT><CODE>a = b;</CODE> +<DD>Copies b to a. a is resized to be the same as b. +<P> +<DT><CODE>a = b.at(2, 4)</CODE> +<DD>constructs a from the 4 elements of b starting at b[2]. +</DL> +<P> +Assume declarations of <CODE>intVec a, b, c</CODE> and <CODE>int i, x</CODE> in +the following. +<P> +<H2><A NAME="SEC74" HREF="libgpp_toc.html#SEC74">Status and access</A></H2> +<P> +<DL COMPACT> +<DT><CODE>a.capacity();</CODE> +<DD>returns the number of elements that can be held in a. +<P> +<DT><CODE>a.resize(20);</CODE> +<DD>sets a's length to 20. All elements are unchanged, except that if +the new size is smaller than the original, than trailing elements +are deleted, and if greater, trailing elements are uninitialized. +<P> +<DT><CODE>a[i];</CODE> +<DD>returns a reference to the i'th element of a, or produces an error +if i is out of range. +<P> +<DT><CODE>a.elem(i)</CODE> +<DD>returns a reference to the i'th element of a. Unlike the <CODE>[]</CODE> operator, +i is not checked to ensure that it is within range. +<P> +<DT><CODE>a == b;</CODE> +<DD>returns true if a and b contain the same elements in the same order. +<P> +<DT><CODE>a != b;</CODE> +<DD>is the converse of a == b. +</DL> +<P> +<H2><A NAME="SEC75" HREF="libgpp_toc.html#SEC75">Constructive operations</A></H2> +<P> +<DL COMPACT> +<DT><CODE>c = concat(a, b);</CODE> +<DD>sets c to the new vector constructed from all of the elements of +a followed by all of b. +<P> +<DT><CODE>c = map(f, a);</CODE> +<DD>sets c to the new vector constructed by applying int function f(int) +to each element of a. +<P> +<DT><CODE>c = merge(a, b, f);</CODE> +<DD>sets c to the new vector constructed by merging the elements of +ordered vectors a and b using ordering (comparison) function f. +<P> +<DT><CODE>c = combine(f, a, b);</CODE> +<DD>sets c to the new vector constructed by applying int function f(int, int) +to successive pairs of a and b. The result has length the shorter of +a and b. +<P> +<DT><CODE>c = reverse(a)</CODE> +<DD>sets c to a, with elements in reverse order. +</DL> +<P> +<H2><A NAME="SEC76" HREF="libgpp_toc.html#SEC76">Destructive operations</A></H2> +<P> +<DL COMPACT> +<DT><CODE>a.reverse();</CODE> +<DD>reverses a in-place. +<P> +<DT><CODE>a.sort(f)</CODE> +<DD>sorts a in-place using comparison function f. The sorting method is a +variation of the quicksort functions supplied with GNU emacs. +<P> +<DT><CODE>a.fill(0, 4, 2)</CODE> +<DD>fills the 2 elements starting at a[4] with zero. +<P> +</DL> +<P> +<H2><A NAME="SEC77" HREF="libgpp_toc.html#SEC77">Other operations</A></H2> +<P> +<DL COMPACT> +<P> +<DT><CODE>a.apply(f)</CODE> +<DD>applies function f to each element in a. +<P> +<DT><CODE>x = a.reduce(f, base)</CODE> +<DD>accumulates the results of applying function f to successive elements +of a starting with base. +<P> +<DT><CODE>a.index(int targ);</CODE> +<DD>returns the index of the leftmost occurrence of the target, or -1, +if it does not occur. +<P> +<DT><CODE>a.error(char* msg)</CODE> +<DD>invokes the error handler. The default version prints the error message, +then aborts. +</DL> +<P> +<H2><A NAME="SEC78" HREF="libgpp_toc.html#SEC78">AVec operations.</A></H2> +<P> +AVecs provide additional arithmetic operations. All vector-by-vector +operators generate an error if the vectors are not the same length. The +following operations are provided, for <CODE>AVecs a, b</CODE> and +base element (scalar) <CODE>s</CODE>. +<P> +<DL COMPACT> +<DT><CODE>a = b;</CODE> +<DD>Copies b to a. a and b must be the same size. +<P> +<DT><CODE>a = s;</CODE> +<DD>fills all elements of a with the value s. a is not resized. +<P> +<DT><CODE>a + s; a - s; a * s; a / s</CODE> +<DD>adds, subtracts, multiplies, or divides each element of a with the scalar. +<P> +<DT><CODE>a += s; a -= s; a *= s; a /= s;</CODE> +<DD>adds, subtracts, multiplies, or divides the scalar into a. +<P> +<DT><CODE>a + b; a - b; product(a, b), quotient(a, b)</CODE> +<DD>adds, subtracts, multiplies, or divides corresponding elements of a and b. +<P> +<DT><CODE>a += b; a -= b; a.product(b); a.quotient(b);</CODE> +<DD>adds, subtracts, multiplies, or divides corresponding elements of b into a. +<P> +<DT><CODE>s = a * b;</CODE> +<DD>returns the inner (dot) product of a and b. +<P> +<DT><CODE>x = a.sum();</CODE> +<DD>returns the sum of elements of a. +<P> +<DT><CODE>x = a.sumsq();</CODE> +<DD>returns the sum of squared elements of a. +<P> +<DT><CODE>x = a.min();</CODE> +<DD>returns the minimum element of a. +<P> +<DT><CODE>x = a.max();</CODE> +<DD>returns the maximum element of a. +<P> +<DT><CODE>i = a.min_index();</CODE> +<DD>returns the index of the minimum element of a. +<P> +<DT><CODE>i = a.max_index();</CODE> +<DD>returns the index of the maximum element of a. +<P> +Note that it is possible to apply vector versions other arithmetic +operators via the mapping functions. For example, to set vector b +to the cosines of doubleVec a, use <CODE>b = map(cos, a);</CODE>. +This is often more efficient than performing the operations +in an element-by-element fashion. +</DL> +<P> +<H1><A NAME="SEC79" HREF="libgpp_toc.html#SEC79">Plex classes</A></H1> +<P> +A "Plex" is a kind of array with the following properties: +<P> +<UL> +<LI> +Plexes may have arbitrary upper and lower index bounds. For example +a Plex may be declared to run from indices -10 .. 10. +<P> +<LI> +Plexes may be dynamically expanded at both the lower and upper bounds +of the array in steps of one element. +<P> +<LI> +Only elements that have been specifically initialized or added may +be accessed. +<P> +<LI> +Elements may be accessed via indices. Indices are always checked for +validity at run time. Plexes may be traversed via simple variations of +standard array indexing loops. +<P> +<LI> +Plex elements may be accessed and traversed via Pixes. +<P> +<LI> +Plex-to-Plex assignment and related operations on entire Plexes +are supported. +<P> +<LI> +Plex classes contain methods to help programmers check the validity +of indexing and pointer operations. +<P> +<LI> +Plexes form "natural" base classes for many restricted-access data +structures relying on logically contiguous indices, such as array-based +stacks and queues. +<P> +<LI> +Plexes are implemented as pseudo-generic classes, and must be generated +via the <CODE>genclass</CODE> utility. +</UL> +<P> +Four subclasses of Plexes are supported: A <CODE>FPlex</CODE> is a Plex that +may only grow or shrink within declared bounds; an <CODE>XPlex</CODE> may +dynamically grow or shrink without bounds; an <CODE>RPlex</CODE> is the +same as an <CODE>XPlex</CODE> but better supports indexing with poor +locality of reference; a <CODE>MPlex</CODE> may grow +or shrink, and additionally allows the logical deletion and restoration +of elements. Because these classes are virtual subclasses of the +"abstract" class <CODE>Plex</CODE>, it is possible to write user code +such as <CODE>void f(Plex& a) ...</CODE> that operates on any kind of +Plex. However, as with nearly any virtual class, specifying the +particular Plex class being used results in more efficient code. +<P> +Plexes are implemented as a linked list of <CODE>IChunks</CODE>. Each chunk +contains a part of the array. Chunk sizes may be specified within Plex +constructors. Default versions also exist, that use a <CODE>#define'd</CODE> +default. Plexes grow by filling unused space in existing chunks, if +possible, else, except for FPlexes, by adding another chunk. Whenever +Plexes grow by a new chunk, the default element constructors (i.e., +those which take no arguments) for all chunk elements are called at +once. When Plexes shrink, destructors for the elements are not called +until an entire chunk is freed. For this reason, Plexes (like C++ +arrays) should only be used for elements with default constructors and +destructors that have no side effects. +<P> +Plexes may be indexed and used like arrays, although traversal +syntax is slightly different. Even though Plexes maintain elements +in lists of chunks, they are implemented so that iteration and +other constructs that maintain locality of reference require very +little overhead over that for simple array traversal +Pix-based traversal is also supported. For example, for a plex, p, +of ints, the following traversal methods could be used. +<P> +<PRE> +for (int i = p.low(); i < p.fence(); p.next(i)) use(p[i]); +for (int i = p.high(); i > p.ecnef(); p.prev(i)) use(p[i]); +for (Pix t = p.first(); t != 0; p.next(t)) use(p(i)); +for (Pix t = p.last(); t != 0; p.prev(t)) use(p(i)); +</PRE> +<P> +Except for MPlexes, simply using <CODE>++i</CODE> and <CODE>--i</CODE> works just as +well as <CODE>p.next(i)</CODE> and <CODE>p.prev(i)</CODE> when traversing by index. +Index-based traversal is generally a bit faster than Pix-based +traversal. +<P> +<CODE>XPlexes</CODE> and <CODE>MPlexes</CODE> are less than optimal for applications +in which widely scattered elements are indexed, as might occur when +using Plexes as hash tables or "manually" allocated linked lists. +In such applications, <CODE>RPlexes</CODE> are often preferable. <CODE>RPlexes</CODE> +use a secondary chunk index table that requires slightly greater, +but entirely uniform overhead per index operation. +<P> +Even though they may grow in either direction, Plexes are normally +constructed so that their "natural" growth direction is upwards, +in that default chunk construction leaves free space, if present, +at the end of the plex. However, if the chunksize arguments to +constructors are negative, they leave space at the beginning. +<P> +All versions of Plexes support the following basic capabilities. +(letting <CODE>Plex</CODE> stand for the type name constructed via the +genclass utility (e.g., <CODE>intPlex</CODE>, <CODE>doublePlex</CODE>)). Assume +declarations of <CODE>Plex p, q</CODE>, <CODE>int i, j</CODE>, base element +<CODE>x</CODE>, and Pix <CODE>pix</CODE>. +<P> +<DL COMPACT> +<P> +<DT><CODE>Plex p;</CODE> +<DD>Declares p to be an initially zero-sized Plex with low index of zero, +and the default chunk size. For FPlexes, chunk sizes represent maximum +sizes. +<P> +<DT><CODE>Plex p(int size);</CODE> +<DD>Declares p to be an initially zero-sized Plex with low index of zero, +and the indicated chunk size. If size is negative, then the Plex +is created with free space at the beginning of the Plex, +allowing more efficient add_low() operations. Otherwise, it +leaves space at the end. +<P> +<DT><CODE>Plex p(int low, int size);</CODE> +<DD>Declares p to be an initially zero-sized Plex with low index of low, +and the indicated chunk size. +<P> +<DT><CODE>Plex p(int low, int high, Base initval, int size = 0);</CODE> +<DD>Declares p to be a Plex with indices from low to high, initially +filled with initval, and the indicated chunk size if specified, +else the default or (high - low + 1), whichever is greater. +<P> +<DT><CODE>Plex q(p);</CODE> +<DD>Declares q to be a copy of p. +<P> +<DT><CODE>p = q;</CODE> +<DD>Copies Plex q into p, deleting its previous contents. +<P> +<DT><CODE>p.length()</CODE> +<DD>Returns the number of elements in the Plex. +<P> +<DT><CODE>p.empty()</CODE> +<DD>Returns true if Plex p contains no elements. +<P> +<DT><CODE>p.full()</CODE> +<DD>Returns true if Plex p cannot be expanded. This always returns +false for XPlexes and MPlexes. +<P> +<DT><CODE>p[i]</CODE> +<DD>Returns a reference to the i'th element of p. An exception (error) occurs +if i is not a valid index. +<P> +<DT><CODE>p.valid(i)</CODE> +<DD>Returns true if i is a valid index into Plex p. +<P> +<DT><CODE>p.low(); p.high();</CODE> +<DD>Return the minimum (maximum) valid index of the Plex, or the high (low) +fence if the plex is empty. +<P> +<DT><CODE>p.ecnef(); p.fence();</CODE> +<DD>Return the index one position past the minimum (maximum) valid index. +<P> +<DT><CODE>p.next(i); i = p.prev(i);</CODE> +<DD>Set i to the next (previous) index. This index may not be within bounds. +<P> +<DT><CODE>p(pix)</CODE> +<DD>returns a reference to the item at Pix pix. +<P> +<DT><CODE>pix = p.first(); pix = p.last();</CODE> +<DD>Return the minimum (maximum) valid Pix of the Plex, or 0 +if the plex is empty. +<P> +<DT><CODE>p.next(pix); p.prev(pix);</CODE> +<DD>set pix to the next (previous) Pix, or 0 if there is none. +<P> +<DT><CODE>p.owns(pix)</CODE> +<DD>Returns true if the Plex contains the element associated with pix. +<P> +<DT><CODE>p.Pix_to_index(pix)</CODE> +<DD>If pix is a valid Pix to an element of the Plex, +returns its corresponding index, else raises an exception. +<P> +<DT><CODE>ptr = p.index_to_Pix(i)</CODE> +<DD>if i is a valid index, returns a the corresponding Pix. +<P> +<DT><CODE>p.low_element(); p.high_element();</CODE> +<DD>Return a reference to the element at the minimum (maximum) valid index. +An exception occurs if the Plex is empty. +<P> +<DT><CODE>p.can_add_low(); p.can_add_high();</CODE> +<DD>Returns true if the plex can be extended one element downward (upward). +These always return true for XPlex and MPlex. +<P> +<DT><CODE>j = p.add_low(x); j = p.add_high(x);</CODE> +<DD>Extend the Plex by one element downward (upward). The new minimum +(maximum) index is returned. +<P> +<DT><CODE>j = p.del_low(); j = p.del_high()</CODE> +<DD>Shrink the Plex by one element on the low (high) end. The new +minimum (maximum) element is returned. An exception occurs if the +Plex is empty. +<P> +<DT><CODE>p.append(q);</CODE> +<DD>Append all of Plex q to the high side of p. +<P> +<DT><CODE>p.prepend(q);</CODE> +<DD>Prepend all of q to the low side of p. +<P> +<DT><CODE>p.clear()</CODE> +<DD>Delete all elements, resetting p to a zero-sized Plex. +<P> +<DT><CODE>p.reset_low(i);</CODE> +<DD>Resets p to be indexed starting at low() = i. For example. +if p were initially declared via <CODE>Plex p(0, 10, 0)</CODE>, +and then re-indexed via <CODE>p.reset_low(5)</CODE>, +it could then be indexed from indices 5 .. 14. +<P> +<DT><CODE>p.fill(x)</CODE> +<DD>sets all p[i] to x. +<P> +<DT><CODE>p.fill(x, lo, hi)</CODE> +<DD>sets all of p[i] from lo to hi, inclusive, to x. +<P> +<DT><CODE>p.reverse()</CODE> +<DD>reverses p in-place. +<P> +<DT><CODE>p.chunk_size()</CODE> +<DD>returns the chunk size used for the plex. +<P> +<DT><CODE>p.error(const char * msg)</CODE> +<DD>calls the resettable error handler. +<P> +</DL> +<P> +MPlexes are plexes with bitmaps that allow items to be logically +deleted and restored. They behave like other plexes, but +also support the following additional and modified capabilities: +<P> +<DL COMPACT> +<P> +<DT><CODE>p.del_index(i); p.del_Pix(pix)</CODE> +<DD>logically deletes p[i] (p(pix)). After deletion, attempts to access p[i] +generate a error. Indexing via low(), high(), prev(), +and next() skip the element. Deleting an element never changes the +logical bounds of the plex. +<P> +<DT><CODE>p.undel_index(i); p.undel_Pix(pix)</CODE> +<DD>logically undeletes p[i] (p(pix)). +<P> +<DT><CODE>p.del_low(); p.del_high()</CODE> +<DD>Delete the lowest (highest) undeleted element, resetting the +logical bounds of the plex to the next lowest (highest) undeleted +index. Thus, MPlex del_low() and del_high() may shrink the bounds +of the plex by more than one index. +<P> +<DT><CODE>p.adjust_bounds()</CODE> +<DD>Resets the low and high bounds of the Plex to the indexes of +the lowest and highest actual undeleted elements. +<P> +<DT><CODE>int i = p.add(x)</CODE> +<DD>Adds x in an unused index, if possible, else performs add_high. +<P> +<DT><CODE>p.count()</CODE> +<DD>returns the number of valid (undeleted) elements. +<P> +<DT><CODE>p.available()</CODE> +<DD>returns the number of available (deleted) indices. +<P> +<DT><CODE>int i = p.unused_index()</CODE> +<DD>returns the index of some deleted element, if one exists, +else triggers an error. An unused element may be reused via undel. +<P> +<DT><CODE>pix = p.unused_Pix()</CODE> +<DD>returns the pix of some deleted element, if one exists, else 0. +An unused element may be reused via undel. +<P> +</DL> +<P> +<H1><A NAME="SEC80" HREF="libgpp_toc.html#SEC80">Stacks</A></H1> +<P> +Stacks are declared as an "abstract" class. They are currently +implemented in any of three ways. +<P> +<DL COMPACT> +<P> +<DT><CODE>VStack</CODE> +<DD>implement fixed sized stacks via arrays. +<P> +<DT><CODE>XPStack</CODE> +<DD>implement dynamically-sized stacks via XPlexes. +<P> +<DT><CODE>SLStack</CODE> +<DD>implement dynamically-size stacks via linked lists. +<P> +</DL> +<P> +All possess the same capabilities. They differ only in constructors. +VStack constructors require a fixed maximum capacity argument. +XPStack constructors optionally take a chunk size argument. +SLStack constructors take no argument. +<P> +Assume the declaration of a base element <CODE>x</CODE>. +<P> +<DL COMPACT> +<P> +<DT><CODE>Stack s; or Stack s(int capacity)</CODE> +<DD>declares a Stack. +<P> +<DT><CODE>s.empty()</CODE> +<DD>returns true if stack s is empty. +<P> +<DT><CODE>s.full()</CODE> +<DD>returns true if stack s is full. XPStacks and SLStacks never become full. +<P> +<DT><CODE>s.length()</CODE> +<DD>returns the current number of elements in the stack. +<P> +<DT><CODE>s.push(x)</CODE> +<DD>pushes x on stack s. +<P> +<DT><CODE>x = s.pop()</CODE> +<DD>pops and returns the top of stack +<P> +<DT><CODE>s.top()</CODE> +<DD>returns a reference to the top of stack. +<P> +<DT><CODE>s.del_top()</CODE> +<DD>pops, but does not return the top of stack. When large items are held +on the stack it is often a good idea to use <CODE>top()</CODE> to inspect and use +the top of stack, followed by a <CODE>del_top()</CODE> +<P> +<DT><CODE>s.clear()</CODE> +<DD>removes all elements from the stack. +<P> +</DL> +<P> +<H1><A NAME="SEC81" HREF="libgpp_toc.html#SEC81">Queues</A></H1> +<P> +Queues are declared as an "abstract" class. They are currently +implemented in any of three ways. +<P> +<DL COMPACT> +<DT><CODE>VQueue</CODE> +<DD>implement fixed sized Queues via arrays. +<P> +<DT><CODE>XPQueue</CODE> +<DD>implement dynamically-sized Queues via XPlexes. +<P> +<DT><CODE>SLQueue</CODE> +<DD>implement dynamically-size Queues via linked lists. +</DL> +<P> +All possess the same capabilities; they differ only in constructors. +<CODE>VQueue</CODE> constructors require a fixed maximum capacity argument. +<CODE>XPQueue</CODE> constructors optionally take a chunk size argument. +<CODE>SLQueue</CODE> constructors take no argument. +<P> +Assume the declaration of a base element <CODE>x</CODE>. +<P> +<DL COMPACT> +<DT><CODE>Queue q; or Queue q(int capacity);</CODE> +<DD>declares a queue. +<P> +<DT><CODE>q.empty()</CODE> +<DD>returns true if queue q is empty. +<P> +<DT><CODE>q.full()</CODE> +<DD>returns true if queue q is full. XPQueues and SLQueues are never full. +<P> +<DT><CODE>q.length()</CODE> +<DD>returns the current number of elements in the queue. +<P> +<DT><CODE>q.enq(x)</CODE> +<DD>enqueues x on queue q. +<P> +<DT><CODE>x = q.deq()</CODE> +<DD>dequeues and returns the front of queue +<P> +<DT><CODE>q.front()</CODE> +<DD>returns a reference to the front of queue. +<P> +<DT><CODE>q.del_front()</CODE> +<DD>dequeues, but does not return the front of queue +<P> +<DT><CODE>q.clear()</CODE> +<DD>removes all elements from the queue. +</DL> +<P> +<H1><A NAME="SEC82" HREF="libgpp_toc.html#SEC82">Double ended Queues</A></H1> +<P> +Deques are declared as an "abstract" class. They are currently +implemented in two ways. +<P> +<DL COMPACT> +<P> +<DT><CODE>XPDeque</CODE> +<DD>implement dynamically-sized Deques via XPlexes. +<P> +<DT><CODE>DLDeque</CODE> +<DD>implement dynamically-size Deques via linked lists. +<P> +</DL> +<P> +All possess the same capabilities. They differ only in constructors. +XPDeque constructors optionally take a chunk size argument. +DLDeque constructors take no argument. +<P> +Double-ended queues support both stack-like and queue-like capabilities: +<P> +Assume the declaration of a base element <CODE>x</CODE>. +<P> +<DL COMPACT> +<P> +<DT><CODE>Deque d; or Deque d(int initial_capacity)</CODE> +<DD>declares a deque. +<P> +<DT><CODE>d.empty()</CODE> +<DD>returns true if deque d is empty. +<P> +<DT><CODE>d.full()</CODE> +<DD>returns true if deque d is full. +Always returns false in current implementations. +<P> +<DT><CODE>d.length()</CODE> +<DD>returns the current number of elements in the deque. +<P> +<DT><CODE>d.enq(x)</CODE> +<DD>inserts x at the rear of deque d. +<P> +<DT><CODE>d.push(x)</CODE> +<DD>inserts x at the front of deque d. +<P> +<DT><CODE>x = d.deq()</CODE> +<DD>dequeues and returns the front of deque +<P> +<DT><CODE>d.front()</CODE> +<DD>returns a reference to the front of deque. +<P> +<DT><CODE>d.rear()</CODE> +<DD>returns a reference to the rear of the deque. +<P> +<DT><CODE>d.del_front()</CODE> +<DD>deletes, but does not return the front of deque +<P> +<DT><CODE>d.del_rear()</CODE> +<DD>deletes, but does not return the rear of the deque. +<P> +<DT><CODE>d.clear()</CODE> +<DD>removes all elements from the deque. +<P> +</DL> +<P> +<H1><A NAME="SEC83" HREF="libgpp_toc.html#SEC83">Priority Queue class prototypes.</A></H1> +<P> +Priority queues maintain collections of objects arranged for fast +access to the least element. +<P> +Several prototype implementations of priority queues are supported. +<P> +<DL COMPACT> +<P> +<DT><CODE>XPPQs</CODE> +<DD>implement 2-ary heaps via XPlexes. +<P> +<DT><CODE>SplayPQs</CODE> +<DD>implement PQs via Sleator and Tarjan's (JACM 1985) +splay trees. The algorithms use a version of "simple top-down +splaying" (described on page 669 of the article). The simple-splay +mechanism for priority queue functions is loosely based on the one used +by D. Jones in the C splay tree functions available from volume 14 of +the uunet.uu.net archives. +<P> +<DT><CODE>PHPQs</CODE> +<DD>implement pairing heaps (as described by Fredman and +Sedgewick in <CITE>Algorithmica</CITE>, Vol 1, p111-129). Storage for heap elements +is managed via an internal freelist technique. The constructor allows an +initial capacity estimate for freelist space. The storage is automatically +expanded if necessary to hold new items. The deletion technique is a fast +"lazy deletion" strategy that marks items as deleted, without reclaiming +space until the items come to the top of the heap. +<P> +</DL> +<P> +All PQ classes support the following operations, for some PQ class +<CODE>Heap</CODE>, instance <CODE>h</CODE>, <CODE>Pix ind</CODE>, and base class +variable <CODE>x</CODE>. +<P> +<DL COMPACT> +<P> +<DT><CODE>h.empty()</CODE> +<DD>returns true if there are no elements in the PQ. +<P> +<DT><CODE>h.length()</CODE> +<DD>returns the number of elements in h. +<P> +<DT><CODE>ind = h.enq(x)</CODE> +<DD>Places x in the PQ, and returns its index. +<P> +<DT><CODE>x = h.deq()</CODE> +<DD>Dequeues the minimum element of the PQ into x, or generates an error +if the PQ is empty. +<P> +<DT><CODE>h.front()</CODE> +<DD>returns a reference to the minimum element. +<P> +<DT><CODE>h.del_front()</CODE> +<DD>deletes the minimum element. +<P> +<DT><CODE>h.clear();</CODE> +<DD>deletes all elements from h; +<P> +<DT><CODE>h.contains(x)</CODE> +<DD>returns true if x is in h. +<P> +<DT><CODE>h(ind)</CODE> +<DD>returns a reference to the item indexed by ind. +<P> +<DT><CODE>ind = h.first()</CODE> +<DD>returns the Pix of first item in the PQ or 0 if empty. +This need not be the Pix of the least element. +<P> +<DT><CODE>h.next(ind)</CODE> +<DD>advances ind to the Pix of next element, or 0 if there are no more. +<P> +<DT><CODE>ind = h.seek(x)</CODE> +<DD>Sets ind to the Pix of x, or 0 if x is not in h. +<P> +<DT><CODE>h.del(ind)</CODE> +<DD>deletes the item with Pix ind. +<P> +</DL> +<P> +<H1><A NAME="SEC84" HREF="libgpp_toc.html#SEC84">Set class prototypes</A></H1> +<P> +Set classes maintain unbounded collections of items containing +no duplicate elements. +<P> +These are currently implemented in several ways, differing in +representation strategy, algorithmic efficiency, and appropriateness for +various tasks. (Listed next to each are average (followed by worst-case, +if different) time complexities for [a] adding, [f] finding (via seek, +contains), [d] deleting, elements, and [c] comparing (via ==, <=) and +[m] merging (via |=, -=, &=) sets). +<P> +<DL COMPACT> +<DT><CODE>XPSets</CODE> +<DD>implement unordered sets via XPlexes. +([a O(n)], [f O(n)], [d O(n)], [c O(n^2)] [m O(n^2)]). +<P> +<DT><CODE>OXPSets</CODE> +<DD>implement ordered sets via XPlexes. +([a O(n)], [f O(log n)], [d O(n)], [c O(n)] [m O(n)]). +<P> +<DT><CODE>SLSets</CODE> +<DD>implement unordered sets via linked lists +([a O(n)], [f O(n)], [d O(n)], [c O(n^2)] [m O(n^2)]). +<P> +<DT><CODE>OSLSets</CODE> +<DD>implement ordered sets via linked lists +([a O(n)], [f O(n)], [d O(n)], [c O(n)] [m O(n)]). +<P> +<DT><CODE>AVLSets</CODE> +<DD>implement ordered sets via threaded AVL trees +([a O(log n)], [f O(log n)], [d O(log n)], [c O(n)] [m O(n)]). +<P> +<DT><CODE>BSTSets</CODE> +<DD>implement ordered sets via binary search trees. The trees may +be manually rebalanced via the O(n) <CODE>balance()</CODE> member function. +([a O(log n)/O(n)], [f O(log n)/O(n)], [d O(log n)/O(n)], [c O(n)] [m O(n)]). +<P> +<DT><CODE>SplaySets</CODE> +<DD>implement ordered sets via Sleator and Tarjan's (JACM 1985) +splay trees. The algorithms use a version of "simple top-down +splaying" (described on page 669 of the article). +(Amortized: [a O(log n)], [f O(log n)], [d O(log n)], [c O(n)] [m O(n log n)]). +<P> +<DT><CODE>VHSets</CODE> +<DD>implement unordered sets via hash tables. +The tables are automatically resized when their capacity is exhausted. +([a O(1)/O(n)], [f O(1)/O(n)], [d O(1)/O(n)], [c O(n)/O(n^2)] [m O(n)/O(n^2)]). +<P> +<DT><CODE>VOHSets</CODE> +<DD>implement unordered sets via ordered hash tables +The tables are automatically resized when their capacity is exhausted. +([a O(1)/O(n)], [f O(1)/O(n)], [d O(1)/O(n)], [c O(n)/O(n^2)] [m O(n)/O(n^2)]). +<P> +<DT><CODE>CHSets</CODE> +<DD>implement unordered sets via chained hash tables. +([a O(1)/O(n)], [f O(1)/O(n)], [d O(1)/O(n)], [c O(n)/O(n^2)] [m O(n)/O(n^2)]). +</DL> +<P> +The different implementations differ in whether their constructors +require an argument specifying their initial capacity. Initial +capacities are required for plex and hash table based Sets. If none is +given <CODE>DEFAULT_INITIAL_CAPACITY</CODE> (from <TT>`<T>defs.h'</TT>) is +used.<P> +Sets support the following operations, for some class <CODE>Set</CODE>, +instances <CODE>a</CODE> and <CODE>b</CODE>, <CODE>Pix ind</CODE>, and base +element <CODE>x</CODE>. Since all implementations are virtual derived classes +of the <CODE><T>Set</CODE> class, it is possible to mix and match operations +across different implementations, although, as usual, operations +are generally faster when the particular classes are specified +in functions operating on Sets. +<P> +Pix-based operations are more fully described in the section +on Pixes. See section <A HREF="libgpp.html#SEC15">Pseudo-indexes</A> +<P> +<DL COMPACT> +<P> +<DT><CODE>Set a; or Set a(int initial_size);</CODE> +<DD>Declares a to be an empty Set. The second version is allowed in +set classes that require initial capacity or sizing specifications. +<P> +<DT><CODE>a.empty()</CODE> +<DD>returns true if a is empty. +<P> +<DT><CODE>a.length()</CODE> +<DD>returns the number of elements in a. +<P> +<DT><CODE>Pix ind = a.add(x)</CODE> +<DD>inserts x into a, returning its index. +<P> +<DT><CODE>a.del(x)</CODE> +<DD>deletes x from a. +<P> +<DT><CODE>a.clear()</CODE> +<DD>deletes all elements from a; +<P> +<DT><CODE>a.contains(x)</CODE> +<DD>returns true if x is in a. +<P> +<DT><CODE>a(ind)</CODE> +<DD>returns a reference to the item indexed by ind. +<P> +<DT><CODE>ind = a.first()</CODE> +<DD>returns the Pix of first item in the set or 0 if the Set is empty. +For ordered Sets, this is the Pix of the least element. +<P> +<DT><CODE>a.next(ind)</CODE> +<DD>advances ind to the Pix of next element, or 0 if there are no more. +<P> +<DT><CODE>ind = a.seek(x)</CODE> +<DD>Sets ind to the Pix of x, or 0 if x is not in a. +<P> +<DT><CODE>a == b</CODE> +<DD>returns true if a and b contain all the same elements. +<P> +<DT><CODE>a != b</CODE> +<DD>returns true if a and b do not contain all the same elements. +<P> +<DT><CODE>a <= b</CODE> +<DD>returns true if a is a subset of b. +<P> +<DT><CODE>a |= b</CODE> +<DD>Adds all elements of b to a. +<P> +<DT><CODE>a -= b</CODE> +<DD>Deletes all elements of b from a. +<P> +<DT><CODE>a &= b</CODE> +<DD>Deletes all elements of a not occurring in b. +<P> +</DL> +<P> +<H1><A NAME="SEC85" HREF="libgpp_toc.html#SEC85">Bag class prototypes</A></H1> +<P> +Bag classes maintain unbounded collections of items potentially +containing duplicate elements. +<P> +These are currently implemented in several ways, differing in +representation strategy, algorithmic efficiency, and appropriateness for +various tasks. (Listed next to each are average (followed by worst-case, +if different) time complexities for [a] adding, [f] finding (via seek, +contains), [d] deleting elements). +<P> +<DL COMPACT> +<P> +<DT><CODE>XPBags</CODE> +<DD>implement unordered Bags via XPlexes. +([a O(1)], [f O(n)], [d O(n)]). +<P> +<DT><CODE>OXPBags</CODE> +<DD>implement ordered Bags via XPlexes. +([a O(n)], [f O(log n)], [d O(n)]). +<P> +<DT><CODE>SLBags</CODE> +<DD>implement unordered Bags via linked lists +([a O(1)], [f O(n)], [d O(n)]). +<P> +<DT><CODE>OSLBags</CODE> +<DD>implement ordered Bags via linked lists +([a O(n)], [f O(n)], [d O(n)]). +<P> +<DT><CODE>SplayBags</CODE> +<DD>implement ordered Bags via Sleator and Tarjan's (JACM 1985) +splay trees. The algorithms use a version of "simple top-down +splaying" (described on page 669 of the article). +(Amortized: [a O(log n)], [f O(log n)], [d O(log n)]). +<P> +<DT><CODE>VHBags</CODE> +<DD>implement unordered Bags via hash tables. +The tables are automatically resized when their capacity is exhausted. +([a O(1)/O(n)], [f O(1)/O(n)], [d O(1)/O(n)]). +<P> +<DT><CODE>CHBags</CODE> +<DD>implement unordered Bags via chained hash tables. +([a O(1)/O(n)], [f O(1)/O(n)], [d O(1)/O(n)]). +<P> +</DL> +<P> +The implementations differ in whether their constructors +require an argument to specify their initial capacity. Initial +capacities are required for plex and hash table based Bags. If none is +given <CODE>DEFAULT_INITIAL_CAPACITY</CODE> (from <TT>`<T>defs.h'</TT>) is used.<P> +Bags support the following operations, for some class <CODE>Bag</CODE>, +instances <CODE>a</CODE> and <CODE>b</CODE>, <CODE>Pix ind</CODE>, and base +element <CODE>x</CODE>. Since all implementations are virtual derived classes +of the <CODE><T>Bag</CODE> class, it is possible to mix and match operations +across different implementations, although, as usual, operations +are generally faster when the particular classes are specified +in functions operating on Bags. +<P> +Pix-based operations are more fully described in the section +on Pixes. See section <A HREF="libgpp.html#SEC15">Pseudo-indexes</A> +<P> +<DL COMPACT> +<P> +<DT><CODE>Bag a; or Bag a(int initial_size)</CODE> +<DD>Declares a to be an empty Bag. The second version is allowed in +Bag classes that require initial capacity or sizing specifications. +<P> +<DT><CODE>a.empty()</CODE> +<DD>returns true if a is empty. +<P> +<DT><CODE>a.length()</CODE> +<DD>returns the number of elements in a. +<P> +<DT><CODE>ind = a.add(x)</CODE> +<DD>inserts x into a, returning its index. +<P> +<DT><CODE>a.del(x)</CODE> +<DD>deletes one occurrence of x from a. +<P> +<DT><CODE>a.remove(x)</CODE> +<DD>deletes all occurrences of x from a. +<P> +<DT><CODE>a.clear()</CODE> +<DD>deletes all elements from a; +<P> +<DT><CODE>a.contains(x)</CODE> +<DD>returns true if x is in a. +<P> +<DT><CODE>a.nof(x)</CODE> +<DD>returns the number of occurrences of x in a. +<P> +<DT><CODE>a(ind)</CODE> +<DD>returns a reference to the item indexed by ind. +<P> +<DT><CODE>int = a.first()</CODE> +<DD>returns the Pix of first item in the Bag or 0 if the Bag is empty. +For ordered Bags, this is the Pix of the least element. +<P> +<DT><CODE>a.next(ind)</CODE> +<DD>advances ind to the Pix of next element, or 0 if there are no more. +<P> +<DT><CODE>ind = a.seek(x. Pix from = 0)</CODE> +<DD>Sets ind to the Pix of the next occurrence x, or 0 if there are none. +If from is 0, the first occurrence is returned, else the following from. +<P> +</DL> +<P> +<H1><A NAME="SEC86" HREF="libgpp_toc.html#SEC86">Map Class Prototypes</A></H1> +<P> +Maps support associative array operations (insertion, deletion, and +membership of records based on an associated key). They require +the specification of two types, the key type and the contents type. +<P> +These are currently implemented in several ways, differing in +representation strategy, algorithmic efficiency, and appropriateness for +various tasks. (Listed next to each are average (followed by worst-case, +if different) time complexities for [a] accessing (via op [], +contains), [d] deleting elements). +<P> +<DL COMPACT> +<P> +<DT><CODE>AVLMaps</CODE> +<DD>implement ordered Maps via threaded AVL trees +([a O(log n)], [d O(log n)]). +<P> +<DT><CODE>RAVLMaps</CODE> +<DD>Similar, but also maintain ranking information, used via +<CODE>ranktoPix(int r)</CODE>, that returns the <CODE>Pix</CODE> of the +item at rank r, and <CODE>rank(key)</CODE> that returns the +rank of the corresponding item. +([a O(log n)], [d O(log n)]). +<P> +<DT><CODE>SplayMaps</CODE> +<DD>implement ordered Maps via Sleator and Tarjan's (JACM 1985) +splay trees. The algorithms use a version of "simple top-down +splaying" (described on page 669 of the article). +(Amortized: [a O(log n)], [d O(log n)]). +<P> +<DT><CODE>VHMaps</CODE> +<DD>implement unordered Maps via hash tables. +The tables are automatically resized when their capacity is exhausted. +([a O(1)/O(n)], [d O(1)/O(n)]). +<P> +<DT><CODE>CHMaps</CODE> +<DD>implement unordered Maps via chained hash tables. +([a O(1)/O(n)], [d O(1)/O(n)]). +<P> +</DL> +<P> +The different implementations differ in whether their constructors +require an argument specifying their initial capacity. Initial +capacities are required for hash table based Maps. If none is +given <CODE>DEFAULT_INITIAL_CAPACITY</CODE> (from <TT>`<T>defs.h'</TT>) is +used.<P> +All Map classes share the following operations (for some Map class, +<CODE>Map</CODE> instance <CODE>d</CODE>, <CODE>Pix ind</CODE> and key variable <CODE>k</CODE>, +and contents variable <CODE>x</CODE>). +<P> +Pix-based operations are more fully described in the section +on Pixes. See section <A HREF="libgpp.html#SEC15">Pseudo-indexes</A> +<P> +<DL COMPACT> +<P> +<DT><CODE>Map d(x); Map d(x, int initial_capacity)</CODE> +<DD>Declare d to be an empty Map. The required argument, x, specifies +the default contents, i.e., the contents of an otherwise +uninitialized location. The second version, specifying +initial capacity is allowed for Maps with an initial capacity +argument. +<P> +<DT><CODE>d.empty()</CODE> +<DD>returns true if d contains no items. +<P> +<DT><CODE>d.length()</CODE> +<DD>returns the number of items in d. +<P> +<DT><CODE>d[k]</CODE> +<DD>returns a reference to the contents of item with key k. If no +such item exists, it is installed with the default contents. +Thus d[k] = x installs x, and x = d[k] retrieves it. +<P> +<DT><CODE>d.contains(k)</CODE> +<DD>returns true if an item with key field k exists in d. +<P> +<DT><CODE>d.del(k)</CODE> +<DD>deletes the item with key k. +<P> +<DT><CODE>d.clear()</CODE> +<DD>deletes all items from the table. +<P> +<DT><CODE>x = d.dflt()</CODE> +<DD>returns the default contents. +<P> +<DT><CODE>k = d.key(ind)</CODE> +<DD>returns a reference to the key at Pix ind. +<P> +<DT><CODE>x = d.contents(ind)</CODE> +<DD>returns a reference to the contents at Pix ind. +<P> +<DT><CODE>ind = d.first()</CODE> +<DD>returns the Pix of the first element in d, or 0 if d is empty. +<P> +<DT><CODE>d.next(ind)</CODE> +<DD>advances ind to the next element, or 0 if there are no more. +<P> +<DT><CODE>ind = d.seek(k)</CODE> +<DD>returns the Pix of element with key k, or 0 if k is not in d. +<P> +</DL> +<P> +<H1><A NAME="SEC87" HREF="libgpp_toc.html#SEC87">C++ version of the GNU getopt function</A></H1> +<P> +The GetOpt class provides an efficient and structured mechanism for +processing command-line options from an application program. The sample +program fragment below illustrates a typical use of the GetOpt class +for some hypothetical application program: +<P> +<PRE> +#include <stdio.h> +#include <GetOpt.h> +//... +int debug_flag, compile_flag, size_in_bytes; + +int +main (int argc, char **argv) +{ + // Invokes ctor `GetOpt (int argc, char **argv, + // char *optstring);' + GetOpt getopt (argc, argv, "dcs:"); + int option_char; + + // Invokes member function `int operator ()(void);' + while ((option_char = getopt ()) != EOF) + switch (option_char) + { + case 'd': debug_flag = 1; break; + case 'c': compile_flag = 1; break; + case 's': size_in_bytes = atoi (getopt.optarg); break; + case '?': fprintf (stderr, + "usage: %s [dcs<size>]\n", argv[0]); + } +} +</PRE> +<P> +Unlike the C library version, the libg++ GetOpt class uses its +constructor to initialize class data members containing the argument +count, argument vector, and the option string. This simplifies the +interface for each subsequent call to member function <CODE>int operator +()(void)</CODE>. +<P> +The C version, on the other hand, uses hidden static variables to retain +the option string and argument list values between calls to +<CODE>getopt</CODE>. This complicates the <CODE>getopt</CODE> interface since the +argument count, argument vector, and option string must be passed as +parameters for each invocation. For the C version, the loop in the +previous example becomes: +<P> +<PRE> + while ((option_char = getopt (argc, argv, "dcs:")) != EOF) + // ... +</PRE> +<P> +which requires extra overhead to pass the parameters for every call. +<P> +Along with the GetOpt constructor and <CODE>int operator ()(void)</CODE>, +the other relevant elements of class GetOpt are: +<P> +<DL COMPACT> +<DT><CODE>char *optarg</CODE> +<DD>Used for communication from <CODE>operator ()(void)</CODE> to the caller. +When <CODE>operator ()(void)</CODE> finds an option that takes an argument, the +argument value is stored here. +<DT><CODE>int optind</CODE> +<DD>Index in <CODE>argv</CODE> of the next element to be scanned. +This is used for communication to and from the caller +and for communication between successive calls to <CODE>operator ()(void)</CODE>. + +When <CODE>operator ()(void)</CODE> returns EOF, this is the index of the +first of the non-option elements that the caller should itself scan. + +Otherwise, <CODE>optind</CODE> communicates from one call to the next how much +of <CODE>argv</CODE> has been scanned so far. +</DL> +<P> +The libg++ version of GetOpt acts like standard UNIX <CODE>getopt</CODE> for +the calling routine, but it behaves differently for the user, since it +allows the user to intersperse the options with the other arguments. + +As GetOpt works, it permutes the elements of <CODE>argv</CODE> so that, when +it is done, all the options precede everything else. Thus all +application programs are extended to handle flexible argument order. +<P> +Setting the environment variable _POSIX_OPTION_ORDER disables +permutation. Then the behavior is completely standard. +<P> +<H1><A NAME="SEC88" HREF="libgpp_toc.html#SEC88">Projects and other things left to do</A></H1> +<P> +<H2><A NAME="SEC89" HREF="libgpp_toc.html#SEC89">Coming Attractions</A></H2> +<P> +Some things that will probably be available in libg++ in the near future: +<P> +<UL> +<P> +<LI> +Revamped C-compatibility header files that will be compatible with +the forthcoming (ANSI-based) GNU libc.a +<P> +<LI> +A revision of the File-based classes that will use the GNU stdio library, +and also be 100% compatible (even at the streambuf level) with the AT&T +2.0 stream classes. +<P> +<LI> +Additional container class prototypes. +<P> +<LI> +generic Matrix class prototypes. +<P> +<LI> +A task package probably based on Dirk Grunwald's threads package. +<P> +</UL> +<P> +<H2><A NAME="SEC90" HREF="libgpp_toc.html#SEC90">Wish List</A></H2> +<P> +Some things that people have mentioned that they would like to +see in libg++, but for which there have not been any offers: +<P> +<UL> +<P> +<LI> +A method to automatically convert or incorporate libg++ classes +so they can be used directly in Gorlen's OOPS environment. +<P> +<LI> +A class browser. +<P> +<LI> +A better general exception-handling strategy. +<P> +<LI> +Better documentation. +<P> +</UL> +<P> +<H2><A NAME="SEC91" HREF="libgpp_toc.html#SEC91">How to contribute</A></H2> +<P> +Programmers who have written C++ classes that they believe to +be of general interest are encourage to write to dl at rocky.oswego.edu. +Contributing code is not difficult. Here are some general guidelines: +<P> +<UL> +<P> +<LI> +FSF must maintain the right to accept or reject potential contributions. +Generally, the only reasons for rejecting contributions are cases where +they duplicate existing or nearly-released code, contain unremovable +specific machine dependencies, or are somehow incompatible with the +rest of the library. +<P> +<LI> +Acceptance of contributions means that the code is accepted for adaptation +into libg++. FSF must reserve the right to make various editorial changes +in code. Very often, this merely entails formatting, maintenance of various +conventions, etc. Contributors are always given authorship credit and shown +the final version for approval. +<P> +<LI> +Contributors must assign their copyright to FSF via a form sent out +upon acceptance. Assigning copyright to FSF ensures that the code +may be freely distributed. +<P> +<LI> +Assistance in providing documentation, test files, and debugging +support is strongly encouraged. +<P> +</UL> +<P> +Extensions, comments, and suggested modifications of existing libg++ +features are also very welcome. |