OS/2 Professional

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

/ OS/2 Professional / OS2PRO194.ISO / os2 / prgramer / unix / info / libgpp.i05 < prev next >

Wrap

GNU Info File | 1993-06-12 | 13.6 KB | 392 lines

This is Info file libgpp, produced by Makeinfo-1.47 from the input file libgpp.tex. START-INFO-DIR-ENTRY * Libg++: (libg++). The g++ library. END-INFO-DIR-ENTRY This file documents the features and implementation of The GNU C++ library Copyright (C) 1988, 1991, 1992 Free Software Foundation, Inc. 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. 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. 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" and this permission notice may be included in translations approved by the Free Software Foundation instead of in the original English. File: libgpp, Node: Bag, Next: Map, Prev: Set, Up: Top Bag class prototypes ******************** Bag classes maintain unbounded collections of items potentially containing duplicate elements. 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). `XPBags' implement unordered Bags via XPlexes. ([a O(1)], [f O(n)], [d O(n)]). `OXPBags' implement ordered Bags via XPlexes. ([a O(n)], [f O(log n)], [d O(n)]). `SLBags' implement unordered Bags via linked lists ([a O(1)], [f O(n)], [d O(n)]). `OSLBags' implement ordered Bags via linked lists ([a O(n)], [f O(n)], [d O(n)]). `SplayBags' implement ordered Bags via Sleater 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)]). `VHBags' 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)]). `CHBags' implement unordered Bags via chained hash tables. ([a O(1)/O(n)], [f O(1)/O(n)], [d O(1)/O(n)]). 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 `DEFAULT_INITIAL_CAPACITY' (from `<T>defs.h') is used. Bags support the following operations, for some class `Bag', instances `a' and `b', `Pix ind', and base element `x'. Since all implementations are virtual derived classes of the `<T>Bag' 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. Pix-based operations are more fully described in the section on Pixes. *Note Pix:: `Bag a; or Bag a(int initial_size)' Declares a to be an empty Bag. The second version is allowed in Bag classes that require initial capacity or sizing specifications. `a.empty()' returns true if a is empty. `a.length()' returns the number of elements in a. `ind = a.add(x)' inserts x into a, returning its index. `a.del(x)' deletes one occurrence of x from a. `a.remove(x)' deletes all occurrences of x from a. `a.clear()' deletes all elements from a; `a.contains(x)' returns true if x is in a. `a.nof(x)' returns the number of occurrences of x in a. `a(ind)' returns a reference to the item indexed by ind. `int = a.first()' 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. `a.next(ind)' advances ind to the Pix of next element, or 0 if there are no more. `ind = a.seek(x. Pix from = 0)' 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. File: libgpp, Node: Map, Next: GetOpt, Prev: Bag, Up: Top Map Class Prototypes ******************** 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. 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). `AVLMaps' implement ordered Maps via threaded AVL trees ([a O(log n)], [d O(log n)]). `RAVLMaps' Similar, but also maintain ranking information, used via `ranktoPix(int r)', that returns the `Pix' of the item at rank r, and `rank(key)' that returns the rank of the corresponding item. ([a O(log n)], [d O(log n)]). `SplayMaps' implement ordered Maps via Sleater 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)]). `VHMaps' 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)]). `CHMaps' implement unordered Maps via chained hash tables. ([a O(1)/O(n)], [d O(1)/O(n)]). 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 `DEFAULT_INITIAL_CAPACITY' (from `<T>defs.h') is used. All Map classes share the following operations (for some Map class, `Map' instance `d', `Pix ind' and key variable `k', and contents variable `x'). Pix-based operations are more fully described in the section on Pixes. *Note Pix:: `Map d(x); Map d(x, int initial_capacity)' 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. `d.empty()' returns true if d contains no items. `d.length()' returns the number of items in d. `d[k]' 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. `d.contains(k)' returns true if an item with key field k exists in d. `d.del(k)' deletes the item with key k. `d.clear()' deletes all items from the table. `x = d.dflt()' returns the default contents. `k = d.key(ind)' returns a reference to the key at Pix ind. `x = d.contents(ind)' returns a reference to the contents at Pix ind. `ind = d.first()' returns the Pix of the first element in d, or 0 if d is empty. `d.next(ind)' advances ind to the next element, or 0 if there are no more. `ind = d.seek(k)' returns the Pix of element with key k, or 0 if k is not in d. File: libgpp, Node: GetOpt, Next: Projects, Prev: Map, Up: Top C++ version of the GNU getopt function ************************************** 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: #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]); } } 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 `int operator ()(void)'. The C version, on the other hand, uses hidden static variables to retain the option string and argument list values between calls to `getopt'. This complicates the `getopt' 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: while ((option_char = getopt (argc, argv, "dcs:")) != EOF) // ... which requires extra overhead to pass the parameters for every call. Along with the GetOpt constructor and `int operator ()(void)', the other relevant elements of class GetOpt are: `char *optarg' Used for communication from `operator ()(void)' to the caller. When `operator ()(void)' finds an option that takes an argument, the argument value is stored here. `int optind' Index in `argv' of the next element to be scanned. This is used for communication to and from the caller and for communication between successive calls to `operator ()(void)'. When `operator ()(void)' returns EOF, this is the index of the first of the non-option elements that the caller should itself scan. Otherwise, `optind' communicates from one call to the next how much of `argv' has been scanned so far. The libg++ version of GetOpt acts like standard UNIX `getopt' 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 `argv' so that, when it is done, all the options precede everything else. Thus all application programs are extended to handle flexible argument order. Setting the environment variable _POSIX_OPTION_ORDER disables permutation. Then the behavior is completely standard. File: libgpp, Node: Projects, Prev: GetOpt, Up: Top Projects and other things left to do ************************************ Coming Attractions ================== Some things that will probably be available in libg++ in the near future: * Revamped C-compatibility header files that will be compatible with the forthcoming (ANSI-based) GNU libc.a * 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. * Additional container class prototypes. * generic Matrix class prototypes. * A task package probably based on Dirk Grunwald's threads package. Wish List ========= Some things that people have mentioned that they would like to see in libg++, but for which there have not been any offers: * Class-based interfaces to Sun RPC using g++ wrappers. * A method to automatically convert or incorporate libg++ classes so they can be used directly in Gorlen's OOPS environment. * A class browser. * A better general exception-handling strategy. * Better documentation. How to contribute ================= 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: * 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. * 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. * 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. * Assistance in providing documentation, test files, and debugging support is strongly encouraged. Extensions, comments, and suggested modifications of existing libg++ features are also very welcome.