home *** CD-ROM | disk | FTP | other *** search
/ Frozen Fish 1: Amiga / FrozenFish-Apr94.iso / bbs / gnu / libg++-2.5.3-bin.lha / info / libg++.info-4 (.txt) < prev    next >
GNU Info File  |  1994-02-27  |  51KB  |  1,140 lines
  1. This is Info file libg++.info, produced by Makeinfo-1.55 from the input
  2. file ./libg++.texi.
  3. START-INFO-DIR-ENTRY
  4. * Libg++::                      The g++ class 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: libg++.info,  Node: Data,  Next: Curses,  Prev: Random,  Up: Top
  25. Data Collection
  26. ***************
  27.    Libg++ currently provides two classes for *data collection* and
  28. analysis of the collected data.
  29. SampleStatistic
  30. ===============
  31.    Class `SampleStatistic' provides a means of accumulating samples of
  32. `double' values and providing common sample statistics.
  33.    Assume declaration of `double x'.
  34. `SampleStatistic a;'
  35.      declares and initializes a.
  36. `a.reset();'
  37.      re-initializes a.
  38. `a += x;'
  39.      adds sample x.
  40. `int n = a.samples();'
  41.      returns the number of samples.
  42. `x = a.mean;'
  43.      returns the means of the samples.
  44. `x = a.var()'
  45.      returns the sample variance of the samples.
  46. `x = a.stdDev()'
  47.      returns the sample standard deviation of the samples.
  48. `x = a.min()'
  49.      returns the minimum encountered sample.
  50. `x = a.max()'
  51.      returns the maximum encountered sample.
  52. `x = a.confidence(int p)'
  53.      returns the p-percent (0 <= p < 100) confidence interval.
  54. `x = a.confidence(double p)'
  55.      returns the p-probability (0 <= p < 1) confidence interval.
  56. SampleHistogram
  57. ===============
  58.    Class `SampleHistogram' is a derived class of `SampleStatistic' that
  59. supports collection and display of samples in bucketed intervals. It
  60. supports the following in addition to `SampleStatisic' operations.
  61. `SampleHistogram h(double lo, double hi, double width);'
  62.      declares and initializes h to have buckets of size width from lo
  63.      to hi.  If the optional argument width is not specified, 10
  64.      buckets are created. The first bucket and also holds samples less
  65.      than lo, and the last one holds samples greater than hi.
  66. `int n = h.similarSamples(x)'
  67.      returns the number of samples in the same bucket as x.
  68. `int n = h.inBucket(int i)'
  69.      returns the number of samples in  bucket i.
  70. `int b = h.buckets()'
  71.      returns the number of buckets.
  72. `h.printBuckets(ostream s)'
  73.      prints bucket counts on ostream s.
  74. `double bound = h.bucketThreshold(int i)'
  75.      returns the upper bound of bucket i.
  76. File: libg++.info,  Node: Curses,  Next: List,  Prev: Data,  Up: Top
  77. Curses-based classes
  78. ********************
  79.    The `CursesWindow' class is a repackaging of standard curses library
  80. features into a class. It relies on `curses.h'.
  81.    The supplied `curses.h' is a fairly conservative declaration of
  82. curses library features, and does not include features like "screen" or
  83. X-window support. It is, for the most part, an adaptation, rather than
  84. an improvement of C-based `curses.h' files. The only substantive
  85. changes are the declarations of many functions as inline functions
  86. rather than macros, which was done solely to allow overloading.
  87.    The `CursesWindow' class encapsulates curses window functions within
  88. a class. Only those functions that control windows are included:
  89. Terminal control functions and macros like `cbreak' are not part of the
  90. class.  All `CursesWindows' member functions have names identical to
  91. the corresponding curses library functions, except that the "w" prefix
  92. is generally dropped. Descriptions of these functions may be found in
  93. your local curses library documentation.
  94.    A `CursesWindow' may be declared via
  95. `CursesWindow w(WINDOW* win)'
  96.      attaches w to the existing WINDOW* win. This is constructor is
  97.      normally used only in the following special case.
  98. `CursesWindow w(stdscr)'
  99.      attaches w to the default curses library standard screen window.
  100. `CursesWindow w(int lines, int cols, int begin_y, int begin_x)'
  101.      attaches to an allocated curses window with the indicated size and
  102.      screen position.
  103. `CursesWindow sub(CursesWindow& w,int l,int c,int by,int bx,char ar='a')'
  104.      attaches to a subwindow of w created via the curses `subwin'
  105.      command.  If ar is sent as `r', the origin (by, bx) is relative to
  106.      the parent window, else it is absolute.
  107.    The class maintains a static counter that is used in order to
  108. automatically call the curses library `initscr' and `endscr' functions
  109. at the proper times. These need not, and should not be called
  110. "manually".
  111.    `CursesWindow's maintain a tree of their subwindows. Upon
  112. destruction of a `CursesWindow', all of their subwindows are also
  113. invalidated if they had not previously been destroyed.
  114.    It is possible to traverse trees of subwindows via the following
  115. member functions
  116. `CursesWindow* w.parent()'
  117.      returns a pointer to the parent of the subwindow, or 0 if there is
  118.      none.
  119. `CursesWindow* w.child()'
  120.      returns the first child subwindow of the window, or 0 if there is
  121.      none.
  122. `CursesWindow* w.sibling()'
  123.      returns the next sibling of the subwindow, or 0 if there is none.
  124.    For example, to call some function `visit' for all subwindows of a
  125. window, you could write
  126.      void traverse(CursesWindow& w)
  127.      {
  128.        visit(w);
  129.        if (w.child() != 0) traverse(*w.child);
  130.        if (w.sibling() != 0) traverse(*w.sibling);
  131.      }
  132. File: libg++.info,  Node: List,  Next: LinkList,  Prev: Curses,  Up: Top
  133. List classes
  134. ************
  135.    The files `g++-include/List.hP' and `g++-include/List.ccP' provide
  136. pseudo-generic Lisp-type List classes.  These lists are homogeneous
  137. lists, more similar to lists in statically typed functional languages
  138. like ML than Lisp, but support operations very similar to those found
  139. in Lisp.  Any particular kind of list class may be generated via the
  140. `genclass' shell command. However, the implementation assumes that the
  141. base class supports an equality operator `=='.  All equality tests use
  142. the `==' operator, and are thus equivalent to the use of `equal', not
  143. `eq' in Lisp.
  144.    All list nodes are created dynamically, and managed via reference
  145. counts.  `List' variables are actually pointers to these list nodes.
  146. Lists may also be traversed via Pixes, as described in the section
  147. describing Pixes. *Note Pix::
  148.    Supported operations are mirrored closely after those in Lisp.
  149. Generally, operations with functional forms are constructive,
  150. functional operations, while member forms (often with the same name)
  151. are sometimes procedural, possibly destructive operations.
  152.    As with Lisp, destructive operations are supported. Programmers are
  153. allowed to change head and tail fields in any fashion, creating
  154. circular structures and the like. However, again as with Lisp, some
  155. operations implicitly assume that they are operating on pure lists, and
  156. may enter infinite loops when presented with improper lists. Also, the
  157. reference-counting storage management facility may fail to reclaim
  158. unused circularly-linked nodes.
  159.    Several Lisp-like higher order functions are supported (e.g., `map').
  160. Typedef declarations for the required functional forms are provided int
  161. the `.h' file.
  162.    For purposes of illustration, assume the specification of class
  163. `intList'.  Common Lisp versions of supported operations are shown in
  164. brackets for comparison purposes.
  165. Constructors and assignment
  166. ===========================
  167. `intList a;           [ (setq a nil) ]'
  168.      Declares a to be a nil intList.
  169. `intList b(2);        [ (setq b (cons 2 nil)) ]'
  170.      Declares b to be an intList with a head value of 2, and a nil tail.
  171. `intList c(3, b);     [ (setq c (cons 3 b)) ]'
  172.      Declares c to be an intList with a head value of 3, and b as its
  173.      tail.
  174. `b = a;               [ (setq b a) ]'
  175.      Sets b to be the same list as a.
  176.    Assume the declarations of intLists a, b, and c in the following.
  177. *Note Pix::.
  178. List status
  179. ===========
  180. `a.null(); OR !a;      [ (null a) ]'
  181.      returns true if a is null.
  182. `a.valid();            [ (listp a) ]'
  183.      returns true if a is non-null. Inside a conditional test, the
  184.      `void*' coercion may also be used as in `if (a) ...'.
  185. `intList();            [ nil ]'
  186.      intList() may be used to null terminate a list, as in `intList
  187.      f(int x) {if (x == 0) return intList(); ... } '.
  188. `a.length();           [ (length a) ]'
  189.      returns the length of a.
  190. `a.list_length();      [ (list-length a) ]'
  191.      returns the length of a, or -1 if a is circular.
  192. heads and tails
  193. ===============
  194. `a.get(); OR a.head()  [ (car a) ]'
  195.      returns a reference to the head field.
  196. `a[2];                 [ (elt a 2) ]'
  197.      returns a reference to the second (counting from zero) head field.
  198. `a.tail();             [ (cdr a) ]'
  199.      returns the intList that is the tail of a.
  200. `a.last();             [ (last a) ]'
  201.      returns the intList that is the last node of a.
  202. `a.nth(2);             [ (nth a 2) ]'
  203.      returns the intList that is the nth node of a.
  204. `a.set_tail(b);        [ (rplacd a b) ]'
  205.      sets a's tail to b.
  206. `a.push(2);            [ (push 2 a) ]'
  207.      equivalent to a = intList(2, a);
  208. `int x = a.pop()       [ (setq x (car a)) (pop a) ]'
  209.      returns the head of a, also setting a to its tail.
  210. Constructive operations
  211. =======================
  212. `b = copy(a);          [ (setq b (copy-seq a)) ]'
  213.      sets b to a copy of a.
  214. `b = reverse(a);       [ (setq b (reverse a)) ]'
  215.      Sets b to a reversed copy of a.
  216. `c = concat(a, b);     [ (setq c (concat a b)) ]'
  217.      Sets c to a concatenated copy of a and b.
  218. `c = append(a, b);     [ (setq c (append a b)) ]'
  219.      Sets c to a concatenated copy of a and b. All nodes of a are
  220.      copied, with the last node pointing to b.
  221. `b = map(f, a);        [ (setq b (mapcar f a)) ]'
  222.      Sets b to a new list created by applying function f to each node
  223.      of a.
  224. `c = combine(f, a, b);'
  225.      Sets c to a new list created by applying function f to successive
  226.      pairs of a and b. The resulting list has length the shorter of a
  227.      and b.
  228. `b = remove(x, a);     [ (setq b (remove x a)) ]'
  229.      Sets b to a copy of a, omitting all occurrences of x.
  230. `b = remove(f, a);     [ (setq b (remove-if f a)) ]'
  231.      Sets b to a copy of a, omitting values causing function f to
  232.      return true.
  233. `b = select(f, a);     [ (setq b (remove-if-not f a)) ]'
  234.      Sets b to a copy of a, omitting values causing function f to
  235.      return false.
  236. `c = merge(a, b, f);   [ (setq c (merge a b f)) ]'
  237.      Sets c to a list containing the ordered elements (using the
  238.      comparison function f) of the sorted lists a and b.
  239. Destructive operations
  240. ======================
  241. `a.append(b);          [ (rplacd (last a) b) ]'
  242.      appends b to the end of a. No new nodes are constructed.
  243. `a.prepend(b);         [ (setq a (append b a)) ]'
  244.      prepends b to the beginning of a.
  245. `a.del(x);             [ (delete x a) ]'
  246.      deletes all nodes with value x from a.
  247. `a.del(f);             [ (delete-if f a) ]'
  248.      deletes all nodes causing function f to return true.
  249. `a.select(f);          [ (delete-if-not f a) ]'
  250.      deletes all nodes causing function f to return false.
  251. `a.reverse();          [ (nreverse a) ]'
  252.      reverses a in-place.
  253. `a.sort(f);            [ (sort a f) ]'
  254.      sorts a in-place using ordering (comparison) function f.
  255. `a.apply(f);           [ (mapc f a) ]'
  256.      Applies void function f (int x) to each element of a.
  257. `a.subst(int old, int repl); [ (nsubst repl old a) ]'
  258.      substitutes repl for each occurrence of old in a. Note the
  259.      different argument order than the Lisp version.
  260. Other operations
  261. ================
  262. `a.find(int x);       [ (find x a) ]'
  263.      returns the intList at the first occurrence of x.
  264. `a.find(b);           [ (find b a) ]'
  265.      returns the intList at the first occurrence of sublist b.
  266. `a.contains(int x);    [ (member x a) ]'
  267.      returns true if a contains x.
  268. `a.contains(b);        [ (member b a) ]'
  269.      returns true if a contains sublist b.
  270. `a.position(int x);    [ (position x a) ]'
  271.      returns the zero-based index of x in a, or -1 if x does not occur.
  272. `int x = a.reduce(f, int base); [ (reduce f a :initial-value base) ]'
  273.      Accumulates the result of applying int function f(int, int) to
  274.      successive elements of a, starting with base.
  275. File: libg++.info,  Node: LinkList,  Next: Vector,  Prev: List,  Up: Top
  276. Linked Lists
  277. ************
  278.    SLLists provide pseudo-generic singly linked lists.  DLLists provide
  279. doubly linked lists.  The lists are designed for the simple maintenance
  280. of elements in a linked structure, and do not provide the more extensive
  281. operations (or node-sharing) of class `List'. They behave similarly to
  282. the `slist' and similar classes described by Stroustrup.
  283.    All list nodes are created dynamically. Assignment is performed via
  284. copying.
  285.    Class `DLList' supports all `SLList' operations, plus additional
  286. operations described below.
  287.    For purposes of illustration, assume the specification of class
  288. `intSLList'. In addition to the operations listed here, SLLists support
  289. traversal via Pixes. *Note Pix::
  290. `intSLList a;'
  291.      Declares a to be an empty list.
  292. `intSLList b = a;'
  293.      Sets b to an element-by-element copy of a.
  294. `a.empty()'
  295.      returns true if a contains no elements
  296. `a.length();'
  297.      returns the number of elements in a.
  298. `a.prepend(x);'
  299.      places x at the front of the list.
  300. `a.append(x);'
  301.      places x at the end of the list.
  302. `a.join(b)'
  303.      places all nodes from b to the end of a, simultaneously destroying
  304.      b.
  305. `x = a.front()'
  306.      returns a reference to the item stored at the head of the list, or
  307.      triggers an error if the list is empty.
  308. `a.rear()'
  309.      returns a reference to the rear of the list, or triggers an error
  310.      if the list is empty.
  311. `x = a.remove_front()'
  312.      deletes and returns the item stored at the head of the list.
  313. `a.del_front()'
  314.      deletes the first element, without returning it.
  315. `a.clear()'
  316.      deletes all items from the list.
  317. `a.ins_after(Pix i, item);'
  318.      inserts item after position i. If i is null, insertion is at the
  319.      front.
  320. `a.del_after(Pix i);'
  321.      deletes the element following i. If i is 0, the first item is
  322.      deleted.
  323. Doubly linked lists
  324. ===================
  325.    Class `DLList' supports the following additional operations, as well
  326. as backward traversal via Pixes.
  327. `x = a.remove_rear();'
  328.      deletes and returns the item stored at the rear of the list.
  329. `a.del_rear();'
  330.      deletes the last element, without returning it.
  331. `a.ins_before(Pix i, x)'
  332.      inserts x before the i.
  333. `a.del(Pix& iint dir = 1)'
  334.      deletes the item at the current position, then advances forward if
  335.      dir is positive, else backward.
  336. File: libg++.info,  Node: Vector,  Next: Plex,  Prev: LinkList,  Up: Top
  337. Vector classes
  338. **************
  339.    The files `g++-include/Vec.ccP' and `g++-include/AVec.ccP' provide
  340. pseudo-generic standard array-based vector operations.  The
  341. corresponding header files are `g++-include/Vec.hP' and
  342. `g++-include/AVec.hP'.  Class `Vec' provides operations suitable for
  343. any base class that includes an equality operator. Subclass `AVec'
  344. provides additional arithmetic operations suitable for base classes
  345. that include the full complement of arithmetic operators.
  346.    `Vecs' are constructed and assigned by copying. Thus, they should
  347. normally be passed by reference in applications programs.
  348.    Several mapping functions are provided that allow programmers to
  349. specify operations on vectors as a whole.
  350.    For illustrative purposes assume that classes `intVec' and `intAVec'
  351. have been generated via `genclass'.
  352. Constructors and assignment
  353. ===========================
  354. `intVec a;'
  355.      declares a to be an empty vector. Its size may be changed via
  356.      resize.
  357. `intVec a(10);'
  358.      declares a to be an uninitialized vector of ten elements (numbered
  359.      0-9).
  360. `intVec b(6, 0);'
  361.      declares b to be a vector of six elements, all initialized to
  362.      zero. Any value can be used as the initial fill argument.
  363. `a = b;'
  364.      Copies b to a. a is resized to be the same as b.
  365. `a = b.at(2, 4)'
  366.      constructs a from the 4 elements of b starting at b[2].
  367.    Assume declarations of `intVec a, b, c' and `int i, x' in the
  368. following.
  369. Status and access
  370. =================
  371. `a.capacity();'
  372.      returns the number of elements that can be held in a.
  373. `a.resize(20);'
  374.      sets a's length to 20. All elements are unchanged, except that if
  375.      the new size is smaller than the original, than trailing elements
  376.      are deleted, and if greater, trailing elements are uninitialized.
  377. `a[i];'
  378.      returns a reference to the i'th element of a, or produces an error
  379.      if i is out of range.
  380. `a.elem(i)'
  381.      returns a reference to the i'th element of a. Unlike the `[]'
  382.      operator, i is not checked to ensure that it is within range.
  383. `a == b;'
  384.      returns true if a and b contain the same elements in the same
  385.      order.
  386. `a != b;'
  387.      is the converse of a == b.
  388. Constructive operations
  389. =======================
  390. `c = concat(a, b);'
  391.      sets c to the new vector constructed from all of the elements of a
  392.      followed by all of b.
  393. `c = map(f, a);'
  394.      sets c to the new vector constructed by applying int function
  395.      f(int) to each element of a.
  396. `c = merge(a, b, f);'
  397.      sets c to the new vector constructed by merging the elements of
  398.      ordered vectors a and b using ordering (comparison) function f.
  399. `c = combine(f, a, b);'
  400.      sets c to the new vector constructed by applying int function
  401.      f(int, int) to successive pairs of a and b. The result has length
  402.      the shorter of a and b.
  403. `c = reverse(a)'
  404.      sets c to a, with elements in reverse order.
  405. Destructive operations
  406. ======================
  407. `a.reverse();'
  408.      reverses a in-place.
  409. `a.sort(f)'
  410.      sorts a in-place using comparison function f. The sorting method
  411.      is a variation of the quicksort functions supplied with GNU emacs.
  412. `a.fill(0, 4, 2)'
  413.      fills the 2 elements starting at a[4] with zero.
  414. Other operations
  415. ================
  416. `a.apply(f)'
  417.      applies function f to each element in a.
  418. `x = a.reduce(f, base)'
  419.      accumulates the results of applying function f to successive
  420.      elements of a starting with base.
  421. `a.index(int targ);'
  422.      returns the index of the leftmost occurrence of the target, or -1,
  423.      if it does not occur.
  424. `a.error(char* msg)'
  425.      invokes the error handler. The default version prints the error
  426.      message, then aborts.
  427. AVec operations.
  428. ================
  429.    AVecs provide additional arithmetic operations.  All vector-by-vector
  430. operators generate an error if the vectors are not the same length. The
  431. following operations are provided, for `AVecs a, b' and base element
  432. (scalar) `s'.
  433. `a = b;'
  434.      Copies b to a. a and b must be the same size.
  435. `a = s;'
  436.      fills all elements of a with the value s. a is not resized.
  437. `a + s; a - s; a * s; a / s'
  438.      adds, subtracts, multiplies, or divides each element of a with the
  439.      scalar.
  440. `a += s; a -= s; a *= s; a /= s;'
  441.      adds, subtracts, multiplies, or divides the scalar into a.
  442. `a + b; a - b; product(a, b), quotient(a, b)'
  443.      adds, subtracts, multiplies, or divides corresponding elements of
  444.      a and b.
  445. `a += b; a -= b; a.product(b); a.quotient(b);'
  446.      adds, subtracts, multiplies, or divides corresponding elements of
  447.      b into a.
  448. `s = a * b;'
  449.      returns the inner (dot) product of a and b.
  450. `x = a.sum();'
  451.      returns the sum of elements of a.
  452. `x = a.sumsq();'
  453.      returns the sum of squared elements of a.
  454. `x = a.min();'
  455.      returns the minimum element of a.
  456. `x = a.max();'
  457.      returns the maximum element of a.
  458. `i = a.min_index();'
  459.      returns the index of the minimum element of a.
  460. `i = a.max_index();'
  461.      returns the index of the maximum element of a.
  462.      Note that it is possible to apply vector versions other arithmetic
  463.      operators via the mapping functions. For example, to set vector b
  464.      to the  cosines of doubleVec a, use `b = map(cos, a);'.  This is
  465.      often more efficient than performing the operations in an
  466.      element-by-element fashion.
  467. File: libg++.info,  Node: Plex,  Next: Stack,  Prev: Vector,  Up: Top
  468. Plex classes
  469. ************
  470.    A "Plex" is a kind of array with the following properties:
  471.    * Plexes may have arbitrary upper and lower index bounds. For example
  472.      a Plex may be declared to run from indices -10 .. 10.
  473.    * Plexes may be dynamically expanded at both the lower and upper
  474.      bounds of the array in steps of one element.
  475.    * Only elements that have been specifically initialized or added may
  476.      be accessed.
  477.    * Elements may be accessed via indices. Indices are always checked
  478.      for validity at run time.  Plexes may be traversed via simple
  479.      variations of standard array indexing loops.
  480.    * Plex elements may be accessed and traversed via Pixes.
  481.    * Plex-to-Plex assignment and related operations on entire Plexes
  482.      are supported.
  483.    * Plex classes contain methods to help programmers check the validity
  484.      of indexing and pointer operations.
  485.    * Plexes form "natural" base classes for many restricted-access data
  486.      structures relying on logically contiguous indices, such as
  487.      array-based stacks and queues.
  488.    * Plexes are implemented as pseudo-generic classes, and must be
  489.      generated via the `genclass' utility.
  490.    Four subclasses of Plexes are supported: A `FPlex' is a Plex that
  491. may only grow or shrink within declared bounds; an `XPlex' may
  492. dynamically grow or shrink without bounds; an `RPlex' is the same as an
  493. `XPlex' but better supports indexing with poor locality of reference; a
  494. `MPlex' may grow or shrink, and additionally allows the logical
  495. deletion and restoration of elements. Because these classes are virtual
  496. subclasses of the "abstract" class `Plex', it is possible to write user
  497. code such as `void f(Plex& a) ...' that operates on any kind of Plex.
  498. However, as with nearly any virtual class, specifying the particular
  499. Plex class being used results in more efficient code.
  500.    Plexes are implemented as a linked list of `IChunks'.  Each chunk
  501. contains a part of the array. Chunk sizes may be specified within Plex
  502. constructors.  Default versions also exist, that use a `#define'd'
  503. default.  Plexes grow by filling unused space in existing chunks, if
  504. possible, else, except for FPlexes, by adding another chunk.  Whenever
  505. Plexes grow by a new chunk, the default element constructors (i.e.,
  506. those which take no arguments) for all chunk elements are called at
  507. once. When Plexes shrink, destructors for the elements are not called
  508. until an entire chunk is freed. For this reason, Plexes (like C++
  509. arrays) should only be used for elements with default constructors and
  510. destructors that have no side effects.
  511.    Plexes may be indexed and used like arrays, although traversal
  512. syntax is slightly different. Even though Plexes maintain elements in
  513. lists of chunks, they are implemented so that iteration and other
  514. constructs that maintain locality of reference require very little
  515. overhead over that for simple array traversal Pix-based traversal is
  516. also supported. For example, for a plex, p, of ints, the following
  517. traversal methods could be used.
  518.      for (int i = p.low(); i < p.fence(); p.next(i)) use(p[i]);
  519.      for (int i = p.high(); i > p.ecnef(); p.prev(i)) use(p[i]);
  520.      for (Pix t = p.first(); t != 0; p.next(t)) use(p(i));
  521.      for (Pix t = p.last(); t != 0; p.prev(t)) use(p(i));
  522.    Except for MPlexes, simply using `++i' and `--i' works just as well
  523. as `p.next(i)' and `p.prev(i)' when traversing by index.  Index-based
  524. traversal is generally a bit faster than Pix-based traversal.
  525.    `XPlexes' and `MPlexes' are less than optimal for applications in
  526. which widely scattered elements are indexed, as might occur when using
  527. Plexes as hash tables or "manually" allocated linked lists.  In such
  528. applications, `RPlexes' are often preferable. `RPlexes' use a secondary
  529. chunk index table that requires slightly greater, but entirely uniform
  530. overhead per index operation.
  531.    Even though they may grow in either direction, Plexes are normally
  532. constructed so that their "natural" growth direction is upwards, in
  533. that default chunk construction leaves free space, if present, at the
  534. end of the plex. However, if the chunksize arguments to constructors
  535. are negative, they leave space at the beginning.
  536.    All versions of Plexes support the following basic capabilities.
  537. (letting `Plex' stand for the type name constructed via the genclass
  538. utility (e.g., `intPlex', `doublePlex')).  Assume declarations of `Plex
  539. p, q', `int i, j', base element `x', and Pix `pix'.
  540. `Plex p;'
  541.      Declares p to be an initially zero-sized Plex with low index of
  542.      zero, and the default chunk size. For FPlexes, chunk sizes
  543.      represent maximum sizes.
  544. `Plex p(int size);'
  545.      Declares p to be an initially zero-sized Plex with low index of
  546.      zero, and the indicated chunk size. If size is negative, then the
  547.      Plex is created with free space at the beginning of the Plex,
  548.      allowing more efficient add_low() operations. Otherwise, it leaves
  549.      space at the end.
  550. `Plex p(int low, int size);'
  551.      Declares p to be an initially zero-sized Plex with low index of
  552.      low, and the indicated chunk size.
  553. `Plex p(int low, int high, Base initval, int size = 0);'
  554.      Declares p to be a Plex with indices from low to high, initially
  555.      filled with initval, and the indicated chunk size if specified,
  556.      else the default or (high - low + 1), whichever is greater.
  557. `Plex q(p);'
  558.      Declares q to be a copy of p.
  559. `p = q;'
  560.      Copies Plex q into p, deleting its previous contents.
  561. `p.length()'
  562.      Returns the number of elements in the Plex.
  563. `p.empty()'
  564.      Returns true if Plex p contains no elements.
  565. `p.full()'
  566.      Returns true if Plex p cannot be expanded. This always returns
  567.      false for XPlexes and MPlexes.
  568. `p[i]'
  569.      Returns a reference to the i'th element of p. An exception (error)
  570.      occurs if i is not a valid index.
  571. `p.valid(i)'
  572.      Returns true if i is a valid index into Plex p.
  573. `p.low(); p.high();'
  574.      Return the minimum (maximum) valid index of the Plex, or the high
  575.      (low) fence if the plex is empty.
  576. `p.ecnef(); p.fence();'
  577.      Return the index one position past the minimum (maximum) valid
  578.      index.
  579. `p.next(i); i = p.prev(i);'
  580.      Set i to the next (previous) index. This index may not be within
  581.      bounds.
  582. `p(pix)'
  583.      returns a reference to the item at Pix pix.
  584. `pix = p.first(); pix = p.last();'
  585.      Return the minimum (maximum) valid Pix of the Plex, or 0 if the
  586.      plex is empty.
  587. `p.next(pix); p.prev(pix);'
  588.      set pix to the next (previous) Pix, or 0 if there is none.
  589. `p.owns(pix)'
  590.      Returns true if the Plex contains the element associated with pix.
  591. `p.Pix_to_index(pix)'
  592.      If pix is a valid Pix to an element of the Plex, returns its
  593.      corresponding index, else raises an exception.
  594. `ptr = p.index_to_Pix(i)'
  595.      if i is a valid index, returns a the corresponding Pix.
  596. `p.low_element(); p.high_element();'
  597.      Return a reference to the element at the minimum (maximum) valid
  598.      index.  An exception occurs if the Plex is empty.
  599. `p.can_add_low();  p.can_add_high();'
  600.      Returns true if the plex can be extended one element downward
  601.      (upward).  These always return true for XPlex and MPlex.
  602. `j = p.add_low(x); j = p.add_high(x);'
  603.      Extend the Plex by one element downward (upward). The new minimum
  604.      (maximum) index is returned.
  605. `j = p.del_low(); j = p.del_high()'
  606.      Shrink the Plex by one element on the low (high) end. The new
  607.      minimum (maximum) element is returned. An exception occurs if the
  608.      Plex is empty.
  609. `p.append(q);'
  610.      Append all of Plex q to the high side of p.
  611. `p.prepend(q);'
  612.      Prepend all of q to the low side of p.
  613. `p.clear()'
  614.      Delete all elements, resetting p to a zero-sized Plex.
  615. `p.reset_low(i);'
  616.      Resets p to be indexed starting at low() = i. For example.  if p
  617.      were initially declared via `Plex p(0, 10, 0)', and then
  618.      re-indexed via `p.reset_low(5)', it could then be indexed from
  619.      indices 5 .. 14.
  620. `p.fill(x)'
  621.      sets all p[i] to x.
  622. `p.fill(x, lo, hi)'
  623.      sets all of p[i] from lo to hi, inclusive, to x.
  624. `p.reverse()'
  625.      reverses p in-place.
  626. `p.chunk_size()'
  627.      returns the chunk size used for the plex.
  628. `p.error(const char * msg)'
  629.      calls the resettable error handler.
  630.    MPlexes are plexes with bitmaps that allow items to be logically
  631. deleted and restored. They behave like other plexes, but also support
  632. the following additional and modified capabilities:
  633. `p.del_index(i); p.del_Pix(pix)'
  634.      logically deletes p[i] (p(pix)). After deletion, attempts to
  635.      access p[i] generate a error. Indexing via low(), high(), prev(),
  636.      and next() skip the element. Deleting an element never changes the
  637.      logical bounds of the plex.
  638. `p.undel_index(i); p.undel_Pix(pix)'
  639.      logically undeletes p[i] (p(pix)).
  640. `p.del_low(); p.del_high()'
  641.      Delete the lowest (highest) undeleted element, resetting the
  642.      logical bounds of the plex to the next lowest (highest) undeleted
  643.      index. Thus, MPlex del_low() and del_high() may shrink the bounds
  644.      of the plex by more than one index.
  645. `p.adjust_bounds()'
  646.      Resets the low and high bounds of the Plex to the indexes of the
  647.      lowest and highest actual undeleted elements.
  648. `int i = p.add(x)'
  649.      Adds x in an unused index, if possible, else performs add_high.
  650. `p.count()'
  651.      returns the number of valid (undeleted) elements.
  652. `p.available()'
  653.      returns the number of available (deleted) indices.
  654. `int i = p.unused_index()'
  655.      returns the index of some deleted element, if one exists, else
  656.      triggers an error. An unused element may be reused via undel.
  657. `pix = p.unused_Pix()'
  658.      returns the pix of some deleted element, if one exists, else 0.
  659.      An unused element may be reused via undel.
  660. File: libg++.info,  Node: Stack,  Next: Queue,  Prev: Plex,  Up: Top
  661. Stacks
  662. ******
  663.    Stacks are declared as an "abstract" class. They are currently
  664. implemented in any of three ways.
  665. `VStack'
  666.      implement fixed sized stacks via arrays.
  667. `XPStack'
  668.      implement dynamically-sized stacks via XPlexes.
  669. `SLStack'
  670.      implement dynamically-size stacks via linked lists.
  671.    All possess the same capabilities. They differ only in constructors.
  672. VStack constructors require a fixed maximum capacity argument.  XPStack
  673. constructors optionally take a chunk size argument.  SLStack
  674. constructors take no argument.
  675.    Assume the declaration of a base element `x'.
  676. `Stack s;  or Stack s(int capacity)'
  677.      declares a Stack.
  678. `s.empty()'
  679.      returns true if stack s is empty.
  680. `s.full()'
  681.      returns true if stack s is full. XPStacks and SLStacks never
  682.      become full.
  683. `s.length()'
  684.      returns the current number of elements in the stack.
  685. `s.push(x)'
  686.      pushes x on stack s.
  687. `x = s.pop()'
  688.      pops and returns the top of stack
  689. `s.top()'
  690.      returns a reference to the top of stack.
  691. `s.del_top()'
  692.      pops, but does not return the top of stack. When large items are
  693.      held on the stack it is often a good idea to use `top()' to
  694.      inspect and use the top of stack, followed by a `del_top()'
  695. `s.clear()'
  696.      removes all elements from the stack.
  697. File: libg++.info,  Node: Queue,  Next: Deque,  Prev: Stack,  Up: Top
  698. Queues
  699. ******
  700.    Queues are declared as an "abstract" class. They are currently
  701. implemented in any of three ways.
  702. `VQueue'
  703.      implement fixed sized Queues via arrays.
  704. `XPQueue'
  705.      implement dynamically-sized Queues via XPlexes.
  706. `SLQueue'
  707.      implement dynamically-size Queues via linked lists.
  708.    All possess the same capabilities; they differ only in constructors.
  709. `VQueue' constructors require a fixed maximum capacity argument.
  710. `XPQueue' constructors optionally take a chunk size argument.
  711. `SLQueue' constructors take no argument.
  712.    Assume the declaration of a base element `x'.
  713. `Queue q; or Queue q(int capacity);'
  714.      declares a queue.
  715. `q.empty()'
  716.      returns true if queue q is empty.
  717. `q.full()'
  718.      returns true if queue q is full. XPQueues and SLQueues are never
  719.      full.
  720. `q.length()'
  721.      returns the current number of elements in the queue.
  722. `q.enq(x)'
  723.      enqueues x on queue q.
  724. `x = q.deq()'
  725.      dequeues and returns the front of queue
  726. `q.front()'
  727.      returns a reference to the front of queue.
  728. `q.del_front()'
  729.      dequeues, but does not return the front of queue
  730. `q.clear()'
  731.      removes all elements from the queue.
  732. File: libg++.info,  Node: Deque,  Next: PQ,  Prev: Queue,  Up: Top
  733. Double ended Queues
  734. *******************
  735.    Deques are declared as an "abstract" class. They are currently
  736. implemented in two ways.
  737. `XPDeque'
  738.      implement dynamically-sized Deques via XPlexes.
  739. `DLDeque'
  740.      implement dynamically-size Deques via linked lists.
  741.    All possess the same capabilities. They differ only in constructors.
  742. XPDeque constructors optionally take a chunk size argument.  DLDeque
  743. constructors take no argument.
  744.    Double-ended queues support both stack-like and queue-like
  745. capabilities:
  746.    Assume the declaration of a base element `x'.
  747. `Deque d; or Deque d(int initial_capacity)'
  748.      declares a deque.
  749. `d.empty()'
  750.      returns true if deque d is empty.
  751. `d.full()'
  752.      returns true if deque d is full.  Always returns false in current
  753.      implementations.
  754. `d.length()'
  755.      returns the current number of elements in the deque.
  756. `d.enq(x)'
  757.      inserts x at the rear of deque d.
  758. `d.push(x)'
  759.      inserts x at the front of deque d.
  760. `x = d.deq()'
  761.      dequeues and returns the front of deque
  762. `d.front()'
  763.      returns a reference to the front of deque.
  764. `d.rear()'
  765.      returns a reference to the rear of the deque.
  766. `d.del_front()'
  767.      deletes, but does not return the front of deque
  768. `d.del_rear()'
  769.      deletes, but does not return the rear of the deque.
  770. `d.clear()'
  771.      removes all elements from the deque.
  772. File: libg++.info,  Node: PQ,  Next: Set,  Prev: Deque,  Up: Top
  773. Priority Queue class prototypes.
  774. ********************************
  775.    Priority queues maintain collections of objects arranged for fast
  776. access to the least element.
  777.    Several prototype implementations of priority queues are supported.
  778. `XPPQs'
  779.      implement 2-ary heaps via XPlexes.
  780. `SplayPQs'
  781.      implement  PQs via Sleator and Tarjan's (JACM 1985) splay trees.
  782.      The algorithms use a version of "simple top-down splaying"
  783.      (described on page 669 of the article).  The simple-splay
  784.      mechanism for priority queue functions is loosely based on the one
  785.      used by D. Jones in the C splay tree functions available from
  786.      volume 14 of the uunet.uu.net archives.
  787. `PHPQs'
  788.      implement pairing heaps (as described by Fredman and Sedgewick in
  789.      `Algorithmica', Vol 1, p111-129).  Storage for heap elements is
  790.      managed via an internal freelist technique. The constructor allows
  791.      an initial capacity estimate for freelist space.  The storage is
  792.      automatically expanded if necessary to hold new items. The
  793.      deletion technique is a fast "lazy deletion" strategy that marks
  794.      items as deleted, without reclaiming space until the items come to
  795.      the top of the heap.
  796.    All PQ classes support the following operations, for some PQ class
  797. `Heap', instance `h', `Pix ind', and base class variable `x'.
  798. `h.empty()'
  799.      returns true if there are no elements in the PQ.
  800. `h.length()'
  801.      returns the number of elements in h.
  802. `ind = h.enq(x)'
  803.      Places x in the PQ, and returns its index.
  804. `x = h.deq()'
  805.      Dequeues the minimum element of the PQ into x, or generates an
  806.      error if the PQ is empty.
  807. `h.front()'
  808.      returns a reference to the minimum element.
  809. `h.del_front()'
  810.      deletes the minimum element.
  811. `h.clear();'
  812.      deletes all elements from h;
  813. `h.contains(x)'
  814.      returns true if x is in h.
  815. `h(ind)'
  816.      returns a reference to the item indexed by ind.
  817. `ind = h.first()'
  818.      returns the Pix of first item in the PQ or 0 if empty.  This need
  819.      not be the Pix of the least element.
  820. `h.next(ind)'
  821.      advances ind to the Pix of next element, or 0 if there are no more.
  822. `ind = h.seek(x)'
  823.      Sets ind to the Pix of x, or 0 if x is not in h.
  824. `h.del(ind)'
  825.      deletes the item with Pix ind.
  826. File: libg++.info,  Node: Set,  Next: Bag,  Prev: PQ,  Up: Top
  827. Set class prototypes
  828. ********************
  829.    Set classes maintain unbounded collections of items containing no
  830. duplicate elements.
  831.    These are currently implemented in several ways, differing in
  832. representation strategy, algorithmic efficiency, and appropriateness for
  833. various tasks. (Listed next to each are average (followed by worst-case,
  834. if different) time complexities for [a] adding, [f] finding (via seek,
  835. contains), [d] deleting, elements, and [c] comparing (via ==, <=) and
  836. [m] merging (via |=, -=, &=) sets).
  837. `XPSets'
  838.      implement unordered sets via XPlexes.  ([a O(n)], [f O(n)], [d
  839.      O(n)], [c O(n^2)] [m O(n^2)]).
  840. `OXPSets'
  841.      implement ordered sets via XPlexes.  ([a O(n)], [f O(log n)], [d
  842.      O(n)], [c O(n)] [m O(n)]).
  843. `SLSets'
  844.      implement unordered sets via linked lists ([a O(n)], [f O(n)], [d
  845.      O(n)], [c O(n^2)] [m O(n^2)]).
  846. `OSLSets'
  847.      implement ordered sets via linked lists ([a O(n)], [f O(n)], [d
  848.      O(n)], [c O(n)] [m O(n)]).
  849. `AVLSets'
  850.      implement ordered sets via threaded AVL trees ([a O(log n)], [f
  851.      O(log n)], [d O(log n)], [c O(n)] [m O(n)]).
  852. `BSTSets'
  853.      implement ordered sets via binary search trees. The trees may be
  854.      manually rebalanced via the O(n) `balance()' member function.  ([a
  855.      O(log n)/O(n)], [f O(log n)/O(n)], [d O(log n)/O(n)], [c O(n)] [m
  856.      O(n)]).
  857. `SplaySets'
  858.      implement ordered sets via Sleator and Tarjan's (JACM 1985) splay
  859.      trees. The algorithms use a version of "simple top-down splaying"
  860.      (described on page 669 of the article).  (Amortized: [a O(log n)],
  861.      [f O(log n)], [d O(log n)], [c O(n)] [m O(n log n)]).
  862. `VHSets'
  863.      implement unordered sets via hash tables.  The tables are
  864.      automatically resized when their capacity is exhausted.  ([a
  865.      O(1)/O(n)], [f O(1)/O(n)], [d O(1)/O(n)], [c O(n)/O(n^2)] [m
  866.      O(n)/O(n^2)]).
  867. `VOHSets'
  868.      implement unordered sets via ordered hash tables The tables are
  869.      automatically resized when their capacity is exhausted.  ([a
  870.      O(1)/O(n)], [f O(1)/O(n)], [d O(1)/O(n)], [c O(n)/O(n^2)] [m
  871.      O(n)/O(n^2)]).
  872. `CHSets'
  873.      implement unordered sets via chained hash tables.  ([a O(1)/O(n)],
  874.      [f O(1)/O(n)], [d O(1)/O(n)], [c O(n)/O(n^2)] [m O(n)/O(n^2)]).
  875.    The different implementations differ in whether their constructors
  876. require an argument specifying their initial capacity. Initial
  877. capacities are required for plex and hash table based Sets.  If none is
  878. given `DEFAULT_INITIAL_CAPACITY' (from `<T>defs.h') is used.
  879.    Sets support the following operations, for some class `Set',
  880. instances `a' and `b', `Pix ind', and base element `x'. Since all
  881. implementations are virtual derived classes of the `<T>Set' class, it
  882. is possible to mix and match operations across different
  883. implementations, although, as usual, operations are generally faster
  884. when the particular classes are specified in functions operating on
  885. Sets.
  886.    Pix-based operations are more fully described in the section on
  887. Pixes. *Note Pix::
  888. `Set a; or Set a(int initial_size);'
  889.      Declares a to be an empty Set. The second version is allowed in
  890.      set classes that require initial capacity or sizing specifications.
  891. `a.empty()'
  892.      returns true if a is empty.
  893. `a.length()'
  894.      returns the number of elements in a.
  895. `Pix ind = a.add(x)'
  896.      inserts x into a, returning its index.
  897. `a.del(x)'
  898.      deletes x from a.
  899. `a.clear()'
  900.      deletes all elements from a;
  901. `a.contains(x)'
  902.      returns true if x is in a.
  903. `a(ind)'
  904.      returns a reference to the item indexed by ind.
  905. `ind = a.first()'
  906.      returns the Pix of first item in the set or 0 if the Set is empty.
  907.      For ordered Sets, this is the Pix of the least element.
  908. `a.next(ind)'
  909.      advances ind to the Pix of next element, or 0 if there are no more.
  910. `ind = a.seek(x)'
  911.      Sets ind to the Pix of x, or 0 if x is not in a.
  912. `a == b'
  913.      returns true if a and b contain all the same elements.
  914. `a != b'
  915.      returns true if a and b do not contain all the same elements.
  916. `a <= b'
  917.      returns true if a is a subset of b.
  918. `a |= b'
  919.      Adds all elements of b to a.
  920. `a -= b'
  921.      Deletes all elements of b from a.
  922. `a &= b'
  923.      Deletes all elements of a not occurring in b.
  924. File: libg++.info,  Node: Bag,  Next: Map,  Prev: Set,  Up: Top
  925. Bag class prototypes
  926. ********************
  927.    Bag classes maintain unbounded collections of items potentially
  928. containing  duplicate elements.
  929.    These are currently implemented in several ways, differing in
  930. representation strategy, algorithmic efficiency, and appropriateness for
  931. various tasks. (Listed next to each are average (followed by worst-case,
  932. if different) time complexities for [a] adding, [f] finding (via seek,
  933. contains), [d] deleting elements).
  934. `XPBags'
  935.      implement unordered Bags via XPlexes.  ([a O(1)], [f O(n)], [d
  936.      O(n)]).
  937. `OXPBags'
  938.      implement ordered Bags via XPlexes.  ([a O(n)], [f O(log n)], [d
  939.      O(n)]).
  940. `SLBags'
  941.      implement unordered Bags via linked lists ([a O(1)], [f O(n)], [d
  942.      O(n)]).
  943. `OSLBags'
  944.      implement ordered Bags via linked lists ([a O(n)], [f O(n)], [d
  945.      O(n)]).
  946. `SplayBags'
  947.      implement ordered Bags via Sleator and Tarjan's (JACM 1985) splay
  948.      trees. The algorithms use a version of "simple top-down splaying"
  949.      (described on page 669 of the article).  (Amortized: [a O(log n)],
  950.      [f O(log n)], [d O(log n)]).
  951. `VHBags'
  952.      implement unordered Bags via hash tables.  The tables are
  953.      automatically resized when their capacity is exhausted.  ([a
  954.      O(1)/O(n)], [f O(1)/O(n)], [d O(1)/O(n)]).
  955. `CHBags'
  956.      implement unordered Bags via chained hash tables.  ([a O(1)/O(n)],
  957.      [f O(1)/O(n)], [d O(1)/O(n)]).
  958.    The implementations differ in whether their constructors require an
  959. argument to specify their initial capacity. Initial capacities are
  960. required for plex and hash table based Bags.  If none is given
  961. `DEFAULT_INITIAL_CAPACITY' (from `<T>defs.h') is used.
  962.    Bags support the following operations, for some class `Bag',
  963. instances `a' and `b', `Pix ind', and base element `x'. Since all
  964. implementations are virtual derived classes of the `<T>Bag' class, it
  965. is possible to mix and match operations across different
  966. implementations, although, as usual, operations are generally faster
  967. when the particular classes are specified in functions operating on
  968. Bags.
  969.    Pix-based operations are more fully described in the section on
  970. Pixes. *Note Pix::
  971. `Bag a; or Bag a(int initial_size)'
  972.      Declares a to be an empty Bag. The second version is allowed in
  973.      Bag classes that require initial capacity or sizing specifications.
  974. `a.empty()'
  975.      returns true if a is empty.
  976. `a.length()'
  977.      returns the number of elements in a.
  978. `ind = a.add(x)'
  979.      inserts x into a, returning its index.
  980. `a.del(x)'
  981.      deletes one occurrence of x from a.
  982. `a.remove(x)'
  983.      deletes all occurrences of x from a.
  984. `a.clear()'
  985.      deletes all elements from a;
  986. `a.contains(x)'
  987.      returns true if x is in a.
  988. `a.nof(x)'
  989.      returns the number of occurrences of x in a.
  990. `a(ind)'
  991.      returns a reference to the item indexed by ind.
  992. `int = a.first()'
  993.      returns the Pix of first item in the Bag or 0 if the Bag is empty.
  994.      For ordered Bags, this is the Pix of the least element.
  995. `a.next(ind)'
  996.      advances ind to the Pix of next element, or 0 if there are no more.
  997. `ind = a.seek(x. Pix from = 0)'
  998.      Sets ind to the Pix of the next occurrence x, or 0 if there are
  999.      none.  If from is 0, the first occurrence is returned, else the
  1000.      following from.
  1001. File: libg++.info,  Node: Map,  Next: GetOpt,  Prev: Bag,  Up: Top
  1002. Map Class Prototypes
  1003. ********************
  1004.    Maps support associative array operations (insertion, deletion, and
  1005. membership of records based on an associated key). They require the
  1006. specification of two types, the key type and the contents type.
  1007.    These are currently implemented in several ways, differing in
  1008. representation strategy, algorithmic efficiency, and appropriateness for
  1009. various tasks. (Listed next to each are average (followed by worst-case,
  1010. if different) time complexities for [a] accessing (via op [],
  1011. contains), [d] deleting elements).
  1012. `AVLMaps'
  1013.      implement ordered Maps via threaded AVL trees ([a O(log n)], [d
  1014.      O(log n)]).
  1015. `RAVLMaps'
  1016.      Similar, but also maintain ranking information, used via
  1017.      `ranktoPix(int r)', that returns the `Pix' of the item at rank r,
  1018.      and `rank(key)' that returns the rank of the corresponding item.
  1019.      ([a O(log n)], [d O(log n)]).
  1020. `SplayMaps'
  1021.      implement ordered Maps via Sleator and Tarjan's (JACM 1985) splay
  1022.      trees. The algorithms use a version of "simple top-down splaying"
  1023.      (described on page 669 of the article).  (Amortized: [a O(log n)],
  1024.      [d O(log n)]).
  1025. `VHMaps'
  1026.      implement unordered Maps via hash tables.  The tables are
  1027.      automatically resized when their capacity is exhausted.  ([a
  1028.      O(1)/O(n)], [d O(1)/O(n)]).
  1029. `CHMaps'
  1030.      implement unordered Maps via chained hash tables.  ([a O(1)/O(n)],
  1031.      [d O(1)/O(n)]).
  1032.    The different implementations differ in whether their constructors
  1033. require an argument specifying their initial capacity. Initial
  1034. capacities are required for hash table based Maps.  If none is given
  1035. `DEFAULT_INITIAL_CAPACITY' (from `<T>defs.h') is used.
  1036.    All Map classes share the following operations (for some Map class,
  1037. `Map' instance `d', `Pix ind' and key variable `k', and contents
  1038. variable `x').
  1039.    Pix-based operations are more fully described in the section on
  1040. Pixes. *Note Pix::
  1041. `Map d(x);  Map d(x, int initial_capacity)'
  1042.      Declare d to be an empty Map. The required argument, x, specifies
  1043.      the default contents, i.e., the contents of an otherwise
  1044.      uninitialized location. The second version, specifying initial
  1045.      capacity is allowed for Maps with an initial capacity argument.
  1046. `d.empty()'
  1047.      returns true if d contains no items.
  1048. `d.length()'
  1049.      returns the number of items in d.
  1050. `d[k]'
  1051.      returns a reference to the contents of item with key k. If no such
  1052.      item exists, it is installed with the default contents.  Thus d[k]
  1053.      = x installs x, and x = d[k] retrieves it.
  1054. `d.contains(k)'
  1055.      returns true if an item with key field k exists in d.
  1056. `d.del(k)'
  1057.      deletes the item with key k.
  1058. `d.clear()'
  1059.      deletes all items from the table.
  1060. `x = d.dflt()'
  1061.      returns the default contents.
  1062. `k = d.key(ind)'
  1063.      returns a reference to the key at Pix ind.
  1064. `x = d.contents(ind)'
  1065.      returns a reference to the contents at Pix ind.
  1066. `ind = d.first()'
  1067.      returns the Pix of the first element in d, or 0 if d is empty.
  1068. `d.next(ind)'
  1069.      advances ind to the next element, or 0 if there are no more.
  1070. `ind = d.seek(k)'
  1071.      returns the Pix of element with key k, or 0 if k is not in d.
  1072. File: libg++.info,  Node: GetOpt,  Next: Projects,  Prev: Map,  Up: Top
  1073. C++ version of the GNU getopt function
  1074. **************************************
  1075.    The GetOpt class provides an efficient and structured mechanism for
  1076. processing command-line options from an application program.  The sample
  1077. program fragment below illustrates a typical use of the GetOpt class
  1078. for some hypothetical application program:
  1079.      #include <stdio.h>
  1080.      #include <GetOpt.h>
  1081.      //...
  1082.      int debug_flag, compile_flag, size_in_bytes;
  1083.      
  1084.      int
  1085.      main (int argc, char **argv)
  1086.      {
  1087.        // Invokes ctor `GetOpt (int argc, char **argv,
  1088.        //                       char *optstring);'
  1089.        GetOpt getopt (argc, argv, "dcs:");
  1090.        int option_char;
  1091.      
  1092.        // Invokes member function `int operator ()(void);'
  1093.        while ((option_char = getopt ()) != EOF)
  1094.          switch (option_char)
  1095.            {
  1096.               case 'd': debug_flag = 1; break;
  1097.               case 'c': compile_flag = 1; break;
  1098.               case 's': size_in_bytes = atoi (getopt.optarg); break;
  1099.               case '?': fprintf (stderr,
  1100.                                  "usage: %s [dcs<size>]\n", argv[0]);
  1101.            }
  1102.      }
  1103.    Unlike the C library version, the libg++ GetOpt class uses its
  1104. constructor to initialize class data members containing the argument
  1105. count, argument vector, and the option string.  This simplifies the
  1106. interface for each subsequent call to member function `int operator
  1107. ()(void)'.
  1108.    The C version, on the other hand, uses hidden static variables to
  1109. retain the option string and argument list values between calls to
  1110. `getopt'.  This complicates the `getopt' interface since the argument
  1111. count, argument vector, and option string must be passed as parameters
  1112. for each invocation.  For the C version, the loop in the previous
  1113. example becomes:
  1114.        while ((option_char = getopt (argc, argv, "dcs:")) != EOF)
  1115.          // ...
  1116.    which requires extra overhead to pass the parameters for every call.
  1117.    Along with the GetOpt constructor and `int operator ()(void)', the
  1118. other relevant elements of class GetOpt are:
  1119. `char *optarg'
  1120.      Used for communication from `operator ()(void)' to the caller.
  1121.      When `operator ()(void)' finds an option that takes an argument,
  1122.      the argument value is stored here.
  1123. `int optind'
  1124.      Index in `argv' of the next element to be scanned.  This is used
  1125.      for communication to and from the caller and for communication
  1126.      between successive calls to `operator ()(void)'.
  1127.      When `operator ()(void)' returns EOF, this is the index of the
  1128.      first of the non-option elements that the caller should itself
  1129.      scan.
  1130.      Otherwise, `optind' communicates from one call to the next how much
  1131.      of `argv' has been scanned so far.
  1132.    The libg++ version of GetOpt acts like standard UNIX `getopt' for
  1133. the calling routine, but it behaves differently for the user, since it
  1134. allows the user to intersperse the options with the other arguments.
  1135.    As GetOpt works, it permutes the elements of `argv' so that, when it
  1136. is done, all the options precede everything else.  Thus all application
  1137. programs are extended to handle flexible argument order.
  1138.    Setting the environment variable _POSIX_OPTION_ORDER disables
  1139. permutation.  Then the behavior is completely standard.
  1140.