home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Professional / OS2PRO194.ISO / os2 / prgramer / unix / info / libgpp.i05 (.txt) < prev    next >
GNU Info File  |  1993-06-12  |  14KB  |  289 lines
  1. This is Info file libgpp, produced by Makeinfo-1.47 from the input file
  2. libgpp.tex.
  3. START-INFO-DIR-ENTRY
  4. * Libg++: (libg++).        The g++ library.
  5. END-INFO-DIR-ENTRY
  6.    This file documents the features and implementation of The GNU C++
  7. library
  8.    Copyright (C) 1988, 1991, 1992 Free Software Foundation, Inc.
  9.    Permission is granted to make and distribute verbatim copies of this
  10. manual provided the copyright notice and this permission notice are
  11. preserved on all copies.
  12.    Permission is granted to copy and distribute modified versions of
  13. this manual under the conditions for verbatim copying, provided also
  14. that the section entitled "GNU Library General Public License" is
  15. included exactly as in the original, and provided that the entire
  16. resulting derived work is distributed under the terms of a permission
  17. notice identical to this one.
  18.    Permission is granted to copy and distribute translations of this
  19. manual into another language, under the above conditions for modified
  20. versions, except that the section entitled "GNU Library General Public
  21. License" and this permission notice may be included in translations
  22. approved by the Free Software Foundation instead of in the original
  23. English.
  24. File: libgpp,  Node: Bag,  Next: Map,  Prev: Set,  Up: Top
  25. Bag class prototypes
  26. ********************
  27.    Bag classes maintain unbounded collections of items potentially
  28. containing  duplicate elements.
  29.    These are currently implemented in several ways, differing in
  30. representation strategy, algorithmic efficiency, and appropriateness for
  31. various tasks. (Listed next to each are average (followed by worst-case,
  32. if different) time complexities for [a] adding, [f] finding (via seek,
  33. contains), [d] deleting elements).
  34. `XPBags'
  35.      implement unordered Bags via XPlexes. ([a O(1)], [f O(n)], [d
  36.      O(n)]).
  37. `OXPBags'
  38.      implement ordered Bags via XPlexes. ([a O(n)], [f O(log n)], [d
  39.      O(n)]).
  40. `SLBags'
  41.      implement unordered Bags via linked lists ([a O(1)], [f O(n)], [d
  42.      O(n)]).
  43. `OSLBags'
  44.      implement ordered Bags via linked lists ([a O(n)], [f O(n)], [d
  45.      O(n)]).
  46. `SplayBags'
  47.      implement ordered Bags via Sleater and Tarjan's (JACM 1985) splay
  48.      trees. The algorithms use a version of "simple top-down splaying"
  49.      (described on page 669 of the article). (Amortized: [a O(log n)],
  50.      [f O(log n)], [d O(log n)]).
  51. `VHBags'
  52.      implement unordered Bags via hash tables. The tables are
  53.      automatically resized when their capacity is exhausted. ([a
  54.      O(1)/O(n)], [f O(1)/O(n)], [d O(1)/O(n)]).
  55. `CHBags'
  56.      implement unordered Bags via chained hash tables. ([a O(1)/O(n)],
  57.      [f O(1)/O(n)], [d O(1)/O(n)]).
  58.    The implementations differ in whether their constructors require an
  59. argument to specify their initial capacity. Initial capacities are
  60. required for plex and hash table based Bags.  If none is given
  61. `DEFAULT_INITIAL_CAPACITY' (from `<T>defs.h') is used.
  62.    Bags support the following operations, for some class `Bag',
  63. instances `a' and `b', `Pix ind', and base element `x'. Since all
  64. implementations are virtual derived classes of the `<T>Bag' class, it
  65. is possible to mix and match operations across different
  66. implementations, although, as usual, operations are generally faster
  67. when the particular classes are specified in functions operating on
  68. Bags.
  69.    Pix-based operations are more fully described in the section on
  70. Pixes. *Note Pix::
  71. `Bag a; or Bag a(int initial_size)'
  72.      Declares a to be an empty Bag. The second version is allowed in
  73.      Bag classes that require initial capacity or sizing specifications.
  74. `a.empty()'
  75.      returns true if a is empty.
  76. `a.length()'
  77.      returns the number of elements in a.
  78. `ind = a.add(x)'
  79.      inserts x into a, returning its index.
  80. `a.del(x)'
  81.      deletes one occurrence of x from a.
  82. `a.remove(x)'
  83.      deletes all occurrences of x from a.
  84. `a.clear()'
  85.      deletes all elements from a;
  86. `a.contains(x)'
  87.      returns true if x is in a.
  88. `a.nof(x)'
  89.      returns the number of occurrences of x in a.
  90. `a(ind)'
  91.      returns a reference to the item indexed by ind.
  92. `int = a.first()'
  93.      returns the Pix of first item in the Bag or 0 if the Bag is empty.
  94.      For ordered Bags, this is the Pix of the least element.
  95. `a.next(ind)'
  96.      advances ind to the Pix of next element, or 0 if there are no more.
  97. `ind = a.seek(x. Pix from = 0)'
  98.      Sets ind to the Pix of the next occurrence x, or 0 if there are
  99.      none. If from is 0, the first occurrence is returned, else the
  100.      following from.
  101. File: libgpp,  Node: Map,  Next: GetOpt,  Prev: Bag,  Up: Top
  102. Map Class Prototypes
  103. ********************
  104.    Maps support associative array operations (insertion, deletion, and
  105. membership of records based on an associated key). They require the
  106. specification of two types, the key type and the contents type.
  107.    These are currently implemented in several ways, differing in
  108. representation strategy, algorithmic efficiency, and appropriateness for
  109. various tasks. (Listed next to each are average (followed by worst-case,
  110. if different) time complexities for [a] accessing (via op [],
  111. contains), [d] deleting elements).
  112. `AVLMaps'
  113.      implement ordered Maps via threaded AVL trees ([a O(log n)], [d
  114.      O(log n)]).
  115. `RAVLMaps'
  116.      Similar, but also maintain ranking information, used via
  117.      `ranktoPix(int r)', that returns the `Pix' of the item at rank r,
  118.      and `rank(key)' that returns the rank of the corresponding item.
  119.      ([a O(log n)], [d O(log n)]).
  120. `SplayMaps'
  121.      implement ordered Maps via Sleater and Tarjan's (JACM 1985) splay
  122.      trees. The algorithms use a version of "simple top-down splaying"
  123.      (described on page 669 of the article). (Amortized: [a O(log n)],
  124.      [d O(log n)]).
  125. `VHMaps'
  126.      implement unordered Maps via hash tables. The tables are
  127.      automatically resized when their capacity is exhausted. ([a
  128.      O(1)/O(n)], [d O(1)/O(n)]).
  129. `CHMaps'
  130.      implement unordered Maps via chained hash tables. ([a O(1)/O(n)],
  131.      [d O(1)/O(n)]).
  132.    The different implementations differ in whether their constructors
  133. require an argument specifying their initial capacity. Initial
  134. capacities are required for hash table based Maps.  If none is given
  135. `DEFAULT_INITIAL_CAPACITY' (from `<T>defs.h') is used.
  136.    All Map classes share the following operations (for some Map class,
  137. `Map' instance `d', `Pix ind' and key variable `k', and contents
  138. variable `x').
  139.    Pix-based operations are more fully described in the section on
  140. Pixes. *Note Pix::
  141. `Map d(x);  Map d(x, int initial_capacity)'
  142.      Declare d to be an empty Map. The required argument, x, specifies
  143.      the default contents, i.e., the contents of an otherwise
  144.      uninitialized location. The second version, specifying initial
  145.      capacity is allowed for Maps with an initial capacity argument.
  146. `d.empty()'
  147.      returns true if d contains no items.
  148. `d.length()'
  149.      returns the number of items in d.
  150. `d[k]'
  151.      returns a reference to the contents of item with key k. If no such
  152.      item exists, it is installed with the default contents. Thus d[k]
  153.      = x installs x, and x = d[k] retrieves it.
  154. `d.contains(k)'
  155.      returns true if an item with key field k exists in d.
  156. `d.del(k)'
  157.      deletes the item with key k.
  158. `d.clear()'
  159.      deletes all items from the table.
  160. `x = d.dflt()'
  161.      returns the default contents.
  162. `k = d.key(ind)'
  163.      returns a reference to the key at Pix ind.
  164. `x = d.contents(ind)'
  165.      returns a reference to the contents at Pix ind.
  166. `ind = d.first()'
  167.      returns the Pix of the first element in d, or 0 if d is empty.
  168. `d.next(ind)'
  169.      advances ind to the next element, or 0 if there are no more.
  170. `ind = d.seek(k)'
  171.      returns the Pix of element with key k, or 0 if k is not in d.
  172. File: libgpp,  Node: GetOpt,  Next: Projects,  Prev: Map,  Up: Top
  173. C++ version of the GNU getopt function
  174. **************************************
  175.    The GetOpt class provides an efficient and structured mechanism for
  176. processing command-line options from an application program.  The sample
  177. program fragment below illustrates a typical use of the GetOpt class
  178. for some hypothetical application program:
  179.      #include <stdio.h>
  180.      #include <GetOpt.h>
  181.      //...
  182.      int debug_flag, compile_flag, size_in_bytes;
  183.      
  184.      int
  185.      main (int argc, char **argv)
  186.      {
  187.        // Invokes ctor `GetOpt (int argc, char **argv,
  188.        //                       char *optstring);'
  189.        GetOpt getopt (argc, argv, "dcs:");
  190.        int option_char;
  191.      
  192.        // Invokes member function `int operator ()(void);'
  193.        while ((option_char = getopt ()) != EOF)
  194.          switch (option_char)
  195.            {
  196.               case 'd': debug_flag = 1; break;
  197.               case 'c': compile_flag = 1; break;
  198.               case 's': size_in_bytes = atoi (getopt.optarg); break;
  199.               case '?': fprintf (stderr,
  200.                                  "usage: %s [dcs<size>]\n", argv[0]);
  201.            }
  202.      }
  203.    Unlike the C library version, the libg++ GetOpt class uses its
  204. constructor to initialize class data members containing the argument
  205. count, argument vector, and the option string.  This simplifies the
  206. interface for each subsequent call to member function `int operator
  207. ()(void)'.
  208.    The C version, on the other hand, uses hidden static variables to
  209. retain the option string and argument list values between calls to
  210. `getopt'.  This complicates the `getopt' interface since the argument
  211. count, argument vector, and option string must be passed as parameters
  212. for each invocation.  For the C version, the loop in the previous
  213. example becomes:
  214.        while ((option_char = getopt (argc, argv, "dcs:")) != EOF)
  215.          // ...
  216.    which requires extra overhead to pass the parameters for every call.
  217.    Along with the GetOpt constructor and `int operator ()(void)', the
  218. other relevant elements of class GetOpt are:
  219. `char *optarg'
  220.      Used for communication from `operator ()(void)' to the caller.
  221.      When `operator ()(void)' finds an option that takes an argument,
  222.      the argument value is stored here.
  223. `int optind'
  224.      Index in `argv' of the next element to be scanned. This is used
  225.      for communication to and from the caller and for communication
  226.      between successive calls to `operator ()(void)'.
  227.      When `operator ()(void)' returns EOF, this is the index of the
  228.      first of the non-option elements that the caller should itself
  229.      scan.
  230.      Otherwise, `optind' communicates from one call to the next how much
  231.      of `argv' has been scanned so far.
  232.    The libg++ version of GetOpt acts like standard UNIX `getopt' for
  233. the calling routine, but it behaves differently for the user, since it
  234. allows the user to intersperse the options with the other arguments.
  235.    As GetOpt works, it permutes the elements of `argv' so that, when it
  236. is done, all the options precede everything else.  Thus all application
  237. programs are extended to handle flexible argument order.
  238.    Setting the environment variable _POSIX_OPTION_ORDER disables
  239. permutation.  Then the behavior is completely standard.
  240. File: libgpp,  Node: Projects,  Prev: GetOpt,  Up: Top
  241. Projects and other things left to do
  242. ************************************
  243. Coming Attractions
  244. ==================
  245.    Some things that will probably be available in libg++ in the near
  246. future:
  247.    * Revamped C-compatibility header files that will be compatible with
  248.      the forthcoming (ANSI-based) GNU libc.a
  249.    * A revision of the File-based classes that will use the GNU stdio
  250.      library, and also be 100% compatible (even at the streambuf level)
  251.      with the AT&T 2.0 stream classes.
  252.    * Additional container class prototypes.
  253.    * generic Matrix class prototypes.
  254.    * A task package probably based on Dirk Grunwald's threads package.
  255. Wish List
  256. =========
  257.    Some things that people have mentioned that they would like to see
  258. in libg++, but for which there have not been any offers:
  259.    * Class-based interfaces to Sun RPC using g++ wrappers.
  260.    * A method to automatically convert or incorporate libg++ classes so
  261.      they can be used directly in Gorlen's OOPS environment.
  262.    * A class browser.
  263.    * A better general exception-handling strategy.
  264.    * Better documentation.
  265. How to contribute
  266. =================
  267.    Programmers who have written C++ classes that they believe to be of
  268. general interest are encourage to write to dl at rocky.oswego.edu.
  269. Contributing code is not difficult. Here are some general guidelines:
  270.    * FSF must maintain the right to accept or reject potential
  271.      contributions. Generally, the only reasons for rejecting
  272.      contributions are cases where they duplicate existing or
  273.      nearly-released code, contain unremovable specific machine
  274.      dependencies, or are somehow incompatible with the rest of the
  275.      library.
  276.    * Acceptance of contributions means that the code is accepted for
  277.      adaptation into libg++.  FSF must reserve the right to make
  278.      various editorial changes in code. Very often, this merely entails
  279.      formatting, maintenance of various conventions, etc. Contributors
  280.      are always given authorship credit and shown the final version for
  281.      approval.
  282.    * Contributors must assign their copyright to FSF via a form sent out
  283.      upon acceptance. Assigning copyright to FSF ensures that the code
  284.      may be freely distributed.
  285.    * Assistance in providing documentation, test files, and debugging
  286.      support is strongly encouraged.
  287.    Extensions, comments, and suggested modifications of existing libg++
  288. features are also very welcome.
  289.