From c4ffd7746cbd9ec9386adc4a8fc79d09c8d647c0 Mon Sep 17 00:00:00 2001
From: Stephen Adams <edu/mit/csail/zurich/adams>
Date: Wed, 3 Nov 1993 22:57:59 +0000
Subject: [PATCH] Fixed typos in wt-tree documentation

---
 v7/doc/ref-manual/scheme.texinfo | 210 ++++++++++++++++---------------
 1 file changed, 106 insertions(+), 104 deletions(-)

diff --git a/v7/doc/ref-manual/scheme.texinfo b/v7/doc/ref-manual/scheme.texinfo
index 8b9ca6bc9..992516cb3 100644
--- a/v7/doc/ref-manual/scheme.texinfo
+++ b/v7/doc/ref-manual/scheme.texinfo
@@ -2,7 +2,7 @@
 @iftex
 @finalout
 @end iftex
-@comment $Id: scheme.texinfo,v 1.33 1993/11/03 03:37:26 adams Exp $
+@comment $Id: scheme.texinfo,v 1.34 1993/11/03 22:57:59 adams Exp $
 @comment %**start of header (This is for running Texinfo on a region.)
 @setfilename scheme
 @settitle MIT Scheme Reference
@@ -8740,12 +8740,10 @@ with a good constant factor.
 
 @item
 @dfn{Weight-Balanced trees} are a kind of balanced binary.  The
-implementation supports non-destructive operations.  For insertion and
-deletion the implementation is slower than Red-Black trees but weight
-balanced trees support a constant time size operation, and many
-high-level operations such as the set operations union, intersection and
-difference, and indexing of elements by position are implememted
-efficiently.
+implementation provides non-destructive operations.  There is a
+comprehensive set of operations including a constant time size
+operation, many high-level operations such as the set operations union,
+intersection and difference, and indexing of elements by position.
 
 @end itemize
 
@@ -9063,7 +9061,7 @@ customizable growth parameters, and customizable hash procedures.
 
 The average times for the insertion, deletion, and lookup operations on
 a hash table are bounded by a constant.  The space required by the table
-is linearly proportional to the number of associations in the table; the
+is proportional to the number of associations in the table; the
 constant of proportionality is described below (@pxref{Resizing of Hash
 Tables}).
 
@@ -9262,13 +9260,13 @@ Returns the contents of @var{hash-table} as a newly allocated alist.
 Each element of the alist is a pair @code{(@var{key} . @var{datum})}
 where @var{key} is one of the keys of @var{hash-table}, and @var{datum}
 is its associated datum.  The average and worst-case times required by
-this operation are linearly proportional to the number of associations
+this operation are linear in the number of associations
 in the table.
 @end deffn
 
 @deffn {procedure+} hash-table/key-list hash-table
 Returns a newly allocated list of the keys in @var{hash-table}.  The
-average and worst-case times required by this operation are linearly
+average and worst-case times required by this operation are
 proportional to the number of associations in the table.
 @end deffn
 
@@ -9277,7 +9275,7 @@ Returns a newly allocated list of the datums in @var{hash-table}.  Each
 element of the list corresponds to one of the associations in
 @var{hash-table}; if the table contains multiple associations with the
 same datum, so will this list.  The average and worst-case times
-required by this operation are linearly proportional to the number of
+required by this operation are proportional to the number of
 associations in the table.
 @end deffn
 
@@ -9423,12 +9421,12 @@ The default rehash size of a newly constructed hash table is @code{2.0}.
 size is almost always undesirable; this option is provided solely for
 compatibility with the Common Lisp hash-table mechanism.  The reason for
 this has to do with the time penalty for resizing the hash table.  The
-time needed to resize a hash table is linearly proportional to the
+time needed to resize a hash table is proportional to the
 number of associations in the table.  This resizing cost is
 @dfn{amortized} across the insertions required to fill the table to the
 point where it needs to grow again.  If the table grows by an amount
-linearly proportional to the number of associations, then the cost of
-resizing and the increase in size are both linearly proportional to the
+proportional to the number of associations, then the cost of
+resizing and the increase in size are both proportional to the
 number of associations, so the @dfn{amortized cost} of an insertion
 operation is still bounded by a constant.  However, if the table grows
 by a constant amount, this is not true: the amortized cost of an
@@ -9764,7 +9762,7 @@ have two advantages over hash tables:
 @itemize @bullet
 @item
 The contents of a binary tree can be converted to an alist, sorted by
-key, in time linearly proportional to the number of associations in the
+key, in time proportional to the number of associations in the
 tree.  A hash table can be converted into an unsorted alist in linear
 time; sorting it requires additional time.
 
@@ -9844,16 +9842,16 @@ Returns the contents of @var{rb-tree} as a newly allocated alist.  Each
 element of the alist is a pair @code{(@var{key} . @var{datum})} where
 @var{key} is one of the keys of @var{rb-tree}, and @var{datum} is its
 associated datum.  The alist is sorted by key according to the
-@var{key<?} argument used to construct @var{rb-tree}.  The average and
-worst-case times required by this operation are proportional to the
+@var{key<?} argument used to construct @var{rb-tree}.  The
+time required by this operation is proportional to the
 number of associations in the tree.
 @end deffn
 
 @deffn {procedure+} rb-tree/key-list rb-tree
 Returns a newly allocated list of the keys in @var{rb-tree}.  The list
 is sorted by key according to the @var{key<?} argument used to construct
-@var{rb-tree}.  The average and worst-case times required by this
-operation are proportional to the number of associations in the tree.
+@var{rb-tree}.  The time required by this
+operation is proportional to the number of associations in the tree.
 @end deffn
 
 @deffn {procedure+} rb-tree/datum-list rb-tree
@@ -9861,8 +9859,7 @@ Returns a newly allocated list of the datums in @var{rb-tree}.  Each
 element of the list corresponds to one of the associations in
 @var{rb-tree}, so if the tree contains multiple associations with the
 same datum, so will this list.  The list is sorted by the keys of the
-associations, even though they do not appear in the result.  The average
-and worst-case times required by this operation are proportional to the
+associations, even though they do not appear in the result.  The time required by this operation is proportional to the
 number of associations in the tree.
 
 This procedure is equivalent to:
@@ -9915,9 +9912,8 @@ The returned value satisfies the following:
 @deffn {procedure+} rb-tree/copy rb-tree
 Returns a newly allocated copy of @var{rb-tree}.  The copy is identical
 to @var{rb-tree} in all respects, except that changes to @var{rb-tree}
-do not affect the copy, and vice versa.  The average and worst-case
-times required by this operation are proportional to the number of
-associations in the tree.
+do not affect the copy, and vice versa.  The time required by this
+operation is proportional to the number of associations in the tree.
 @end deffn
 
 @deffn {procedure+} alist->rb-tree alist key=? key<?
@@ -9953,10 +9949,10 @@ large aggregates:
 @item
 In addition to the usual element-level operations like insertion,
 deletion and lookup, there is a full complement of collection-level
-operations, like set intersection, union and subset test, all of which
-are implemented with good orders of growth in time and space.  This
-makes weight balanced trees ideal for rapid prototyping of functionally
-derived specifications.
+operations, like set intersection, set union and subset test, all of
+which are implemented with good orders of growth in time and space.
+This makes weight balanced trees ideal for rapid prototyping of
+functionally derived specifications.
 
 @item
 An element in a tree may be indexed by its position under the ordering
@@ -9968,29 +9964,31 @@ Operations to find and remove minimum element make weight balanced trees
 simple to use for priority queues.
 
 @item
-The implementation is @emph{functional} rather than imperative.  This
-means that operations like `inserting' an element in a tree do not
-destroy the old tree, in much the same way that @code{(+ 1 x)} modifies
-neither the constant 1 nor the value bound to @code{x}.  The programmer
-need not worry about copying the trees, and space efficiency is achieved
-by sharing subtrees.
+The implementation is @emph{functional} rather than @emph{imperative}.
+This means that operations like `inserting' an association in a tree do
+not destroy the old tree, in much the same way that @code{(+ 1 x)}
+modifies neither the constant 1 nor the value bound to @code{x}.  The
+trees are referentially transparent thus the programmer need not worry
+about copying the trees.  Referential transparency allows space
+efficiency to be achieved by sharing subtrees.
 
 @end itemize
 
 These features make weight-balanced trees suitable for a wide range of
-applications, especially those structured in such a way that they
+applications, especially those that
 require large numbers of sets or discrete maps.  Applications that have
-a few global databases and concentrate on element-level operations like
+a few global databases and/or concentrate on element-level operations like
 insertion and lookup are probably better off using hash-tables or
 red-black trees.
 
 The @emph{size} of a tree is the number of associations that it
 contains.  Weight balanced binary trees are balanced to keep the sizes
 of the subtrees of each node within a constant factor of each other.
-This ensures logarithmic single-path operations (like lookup and
-insertion).  A weight balanced tree takes space that is proportional to
-the number of associations in the tree.  For the current implementation,
-the constant of proportionality is six words per association.
+This ensures logarithmic times for single-path operations (like lookup
+and insertion).  A weight balanced tree takes space that is proportional
+to the number of associations in the tree.  For the current
+implementation, the constant of proportionality is six words per
+association.
 
 @cindex binary trees, as sets
 @cindex binary trees, as discrete maps
@@ -9999,19 +9997,20 @@ the constant of proportionality is six words per association.
 Weight balanced trees can be used as an implementation for either
 discrete sets or discrete maps (associations).  Sets are implemented by
 ignoring the datum that is associated with the key.  Under this scheme
-associations exist in the tree to indicate that the key of the
-association is a member of the set.  Typically a value such as @code{()}
-or @code{#f} is associated with the key.
-
-Many operations can be viewed as computing a result that has two
-different names, depending on whether the tree arguments are thought of
-as sets or maps.  An example is @code{wt-tree/member?}, which, when
-regarding the tree as a set, computes the set membership operation, but,
+if an associations exists in the tree this indicates that the key of the
+association is a member of the set.  Typically a value such as
+@code{()}, @code{#t} or @code{#f} is associated with the key.
+
+Many operations can be viewed as computing a result that, depending on
+whether the tree arguments are thought of as sets or maps, is known by
+two different names.
+An example is @code{wt-tree/member?}, which, when
+regarding the tree argument as a set, computes the set membership operation, but,
 when regarding the tree as a discrete map, @code{wt-tree/member?} is the
-predicate telling if the map is defined at an element in its domain.
+predicate testing if the map is defined at an element in its domain.
 Most names in this package have been chosen based on interpreting the
-trees as sets (hence the name @code{wt-tree/member?} rather than
-@code{wt-tree/defined-at?}).
+trees as sets, hence the name @code{wt-tree/member?} rather than
+@code{wt-tree/defined-at?}.
 
 
 @cindex run-time-loadable option
@@ -10039,16 +10038,16 @@ once before calling any of the procedures defined here.
 @subsection Construction of Weight-Balanced Trees
 
 Binary trees require there to be a total order on the keys used to
-arrange the elements in the tree.  Weight-balanced trees are organized
+arrange the elements in the tree.  Weight balanced trees are organized
 by @emph{types}, where the type is an object encapsulating the ordering
 relation.  Creating a tree is a two-stage process.  First a tree type
-must be created from a predicate which gives the ordering.  A tree type
+must be created from the predicate which gives the ordering.  The tree type
 is then used for making trees, either empty or singleton trees or trees
 from other aggregate structures like association lists.  Once created, a
 tree `knows' its type and the type is used to test compatibility between
 trees in operations taking two trees.  Usually a small number of tree
 types are created at the beginning of a program and used many times
-throughaout its execution.
+throughout the program's execution.
 
 @deffn {procedure+} make-wt-tree-type key<?
 This procedure creates and returns a new tree type based on the ordering
@@ -10069,9 +10068,10 @@ Two key values are assumed to be equal if neither is less than the other
 by @var{key<?}.
 
 Each call to @code{make-wt-tree-type} returns a distinct value, and
-trees are only compatible if their tree types are @code{eq?}, so trees
-that are intended to be used in binary tree operations must all be
-created with a tree type originating from a single call to
+trees are only compatible if their tree types are @code{eq?}.
+A consequence is 
+that trees that are intended to be used in binary tree operations must all be
+created with a tree type originating from the same call to
 @code{make-wt-tree-type}.
 @end deffn
 
@@ -10139,7 +10139,7 @@ returns @code{#f}.
 @end deffn
 
 @deffn {procedure+} wt-tree/empty? wt-tree
-Returns @code{#t} if @code{wt-tree} contains no associations, otherwise
+Returns @code{#t} if @var{wt-tree} contains no associations, otherwise
 returns @code{#f}.
 @end deffn
 
@@ -10220,46 +10220,48 @@ worst-case times required by this operation are proportional to the
 logarithm of size of @var{wt-tree}.
 @end deffn
 
-@deffn {procedure+} wt-tree/union wt-tree1 wt-tree2
+@deffn {procedure+} wt-tree/union wt-tree-1 wt-tree-2
 Returns a new tree containing all the associations from both trees.
 This operation is asymmetric: when both trees have an association for
-the same key, the returned tree associates the datum from @var{wt-tree2}
+the same key, the returned tree associates the datum from @var{wt-tree-2}
 with the key.  Thus if the trees are viewed as discrete maps then
-@code{wt-tree/union} computes the map override of @var{wt-tree1} by
-@var{wt-tree2}.  If the trees are used as sets the result is the set
+@code{wt-tree/union} computes the map override of @var{wt-tree-1} by
+@var{wt-tree-2}.  If the trees are viewed as sets the result is the set
 union of the arguments.
-The average and worst-case times required by this operation
-are proportional to the sum of the sizes of both trees.
+The worst-case time required by this operation
+is proportional to the sum of the sizes of both trees.
 If the minimum key of one tree is greater than the maximum key of
 the other tree then the time required is at worst proportional to
 the logarithm of the size of the larger tree.
 @end deffn
 
-@deffn {procedure+} wt-tree/intersection wt-tree1 wt-tree2
+@deffn {procedure+} wt-tree/intersection wt-tree-1 wt-tree-2
 Returns a new tree containing all and only those associations from
-@var{wt-tree1} which have keys appearing as the key of in an association
-in @var{wt-tree2}.  If the trees are being used as sets the result is
-the set intersection of the arguments.  As a discrete map operation, it
-computes the domain restriction of @var{wt-tree1} to (the domain of)
-@var{wt-tree2}.  The worst-case time required by this operation is
-proportional to the size of the larger tree.
+@var{wt-tree-1} which have keys appearing as the key of an association
+in @var{wt-tree-2}.  Thus the associated data in the result are those
+from @var{wt-tree-1}.  If the trees are being used as sets the result is
+the set intersection of the arguments.  As a discrete map operation,
+@code{wt-tree/intersection} computes the domain restriction of
+@var{wt-tree-1} to (the domain of) @var{wt-tree-2}.
+The time required by this operation is never worse that proportional to
+the sum of the sizes of the trees.
 @end deffn
 
-@deffn {procedure+} wt-tree/difference wt-tree1 wt-tree2
+@deffn {procedure+} wt-tree/difference wt-tree-1 wt-tree-2
 Returns a new tree containing all and only those associations from
-@var{wt-tree1} which have keys that @emph{do not} appear as the key of
-an association in @var{wt-tree2}.  If the trees are viewed as sets the
+@var{wt-tree-1} which have keys that @emph{do not} appear as the key of
+an association in @var{wt-tree-2}.  If the trees are viewed as sets the
 result is the asymmetric set difference of the arguments.  As a discrete
-map operation, it computes the domain restriction of @var{wt-tree1} to
-the complement of (the domain of) @var{wt-tree2}.  The
-worst-case time required by this operation is proportional to the 
-of the size of @var{wt-tree1}.
+map operation, it computes the domain restriction of @var{wt-tree-1} to
+the complement of (the domain of) @var{wt-tree-2}.
+The time required by this operation is never worse that proportional to
+the sum of the sizes of the trees.
 @end deffn
 
 
-@deffn {procedure+} wt-tree/subset? wt-tree1 wt-tree2
-Returns @code{#t} iff the key of each association in @var{wt-tree1} is
-the key of some association in @var{wt-tree2}, otherwise returns @code{#f}.
+@deffn {procedure+} wt-tree/subset? wt-tree-1 wt-tree-2
+Returns @code{#t} iff the key of each association in @var{wt-tree-1} is
+the key of some association in @var{wt-tree-2}, otherwise returns @code{#f}.
 Viewed as a set operation, @code{wt-tree/subset?} is the improper subset
 predicate.
 A proper subset predicate can be constructed:
@@ -10271,15 +10273,15 @@ A proper subset predicate can be constructed:
 @end example
 
 As a discrete map operation, @code{wt-tree/subset?} is the subset
-operation on the domain(s) of the map(s).  In the worst-case the time
+test on the domain(s) of the map(s).  In the worst-case the time
 required by this operation is proportional to the size of
-@var{wt-tree1}.
+@var{wt-tree-1}.
 @end deffn
 
 
-@deffn {procedure+} wt-tree/set-equal? wt-tree1 wt-tree2
-Returns @code{#t} iff for every association in @var{wt-tree1} there is
-an association in @var{wt-tree2} that has the same key, and @emph{vice
+@deffn {procedure+} wt-tree/set-equal? wt-tree-1 wt-tree-2
+Returns @code{#t} iff for every association in @var{wt-tree-1} there is
+an association in @var{wt-tree-2} that has the same key, and @emph{vice
 versa}.
 
 Viewing the arguments as sets @code{wt-tree/set-equal?} is the set
@@ -10289,8 +10291,8 @@ defined on the same domain.
 This procedure is equivalent to
 
 @example
-(and (wt-tree/subset? @var{wt-tree1} @var{wt-tree2})
-     (wt-tree/subset? @var{wt-tree2} @var{wt-tree1}))
+(and (wt-tree/subset? @var{wt-tree-1} @var{wt-tree-2})
+     (wt-tree/subset? @var{wt-tree-2} @var{wt-tree-1}))
 @end example
 
 In the worst-case the time required by this operation is proportional to
@@ -10306,22 +10308,20 @@ a datum and the accumulated result so far.  Provided @var{combiner}
 takes time bounded by a constant, @code{wt-tree/fold} takes time
 proportional to the size of @var{wt-tree}.
 
-An sorted association list can be derived simply:
+A sorted association list can be derived simply:
 @example
-(define (wt-tree->alist tree)
-  (fold (lambda (key datum list) (cons (cons key datum) list))
-        '()
-        tree))
+(fold (lambda (key datum list)
+        (cons (cons key datum) list))
+      '()
+      @var{wt-tree}))
 @end example
 
 The data in the associations can be summed like this:
 @example
-(define (sum-wt-tree-data tree)
-  (fold  (lambda (key datum sum) (+ sum datum))  0  tree)
+(fold  (lambda (key datum sum) (+ sum datum))  0  @var{wt-tree})
 @end example
 @end deffn
 
-
 @deffn {procedure+} wt-tree/for-each action wt-tree
 This procedure traverses the tree in-order, applying @var{action} to
 each association.
@@ -10334,9 +10334,9 @@ Provided @var{action} takes time bounded by a constant,
 The example prints the tree:
 
 @example
-(define (print-tree tree)
-  (for-each  (lambda (key value) (display (list key value)))
-             tree))
+(for-each (lambda (key value)
+            (display (list key value)))
+          @var{wt-tree}))
 @end example
 @end deffn
 
@@ -10357,7 +10357,7 @@ sorted sequence under the tree's ordering relation on the keys.
 @code{wt-tree/index} returns the @var{index}th key,
 @code{wt-tree/index-datum} returns the datum associated with the
 @var{index}th key and @code{wt-tree/index-pair} returns a new pair
-@code{(@var{key} . @var{datum})} which is the @code{cons} of the minimum
+@code{(@var{key} . @var{datum})} which is the @code{cons} of the @var{index}th
 key and its datum.  The average and worst-case times required by this
 operation are proportional to the logarithm of the number of
 associations in the tree.
@@ -10366,11 +10366,13 @@ These operations signal an error if the tree is empty, if
 @var{index}@code{<0}, or if @var{index} is greater than or equal to the
 number of associations in the tree.
 
-Indexing can be used to find the median key in the tree as follows:
+Indexing can be used to find the median and maximum keys in the tree as
+follows:
 
 @example
-(define (median tree)
-  (wt-tree/index tree (quotient (wt-tree/size tree) 2)))
+median:   (wt-tree/index @var{wt-tree} (quotient (wt-tree/size @var{wt-tree}) 2))
+
+maximum:  (wt-tree/index @var{wt-tree} (-1+ (wt-tree/size @var{wt-tree})))
 @end example
 @end deffn
 
@@ -10390,7 +10392,7 @@ Returns the association of @var{wt-tree} that has the least key under the tree's
 @code{wt-tree/min} returns the least key,
 @code{wt-tree/min-datum} returns the datum associated with the
 least key and @code{wt-tree/min-pair} returns a new pair
-@code{(key . datum) }which is the @code{cons} of the key and the datum.
+@code{(key . datum)} which is the @code{cons} of the minimum key and its datum.
 The average and worst-case times required by this operation are
 proportional to the logarithm of the number of associations in the tree.
 
-- 
2.25.1