@@@ more wip

[runlisp] / lib.c

diff --git a/lib.c b/lib.c
index 523ca23..36751ab 100644 (file)
--- a/lib.c
+++ b/lib.c
@@ -436,7 +436,7 @@ void *treap_lookup(const struct treap *t, const char *k, size_t kn)
  * This is similar to `treap_lookup', in that it returns the requested node
  * if it already exists, or null otherwise, but it also records in P
  * information to be used by `treap_insert' to insert a new node with the
- * given key it's not there already.
+ * given key if it's not there already.
  */
 void *treap_probe(struct treap *t, const char *k, size_t kn,
                  struct treap_path *p)
@@ -509,7 +509,7 @@ void treap_insert(struct treap *t, const struct treap_path *p,
      * subtree of U, then we rotate like this:
      *
      *                 |                   |
-     *                 U                   N
+     *                 U                  (N)
      *               /   \               /   \
      *            (N)      Z   --->    X       U
      *           /   \                       /   \
@@ -519,7 +519,7 @@ void treap_insert(struct treap *t, const struct treap_path *p,
      * of U, then we do the opposite rotation:
      *
      *             |                           |
-     *             U                           N
+     *             U                          (N)
      *           /   \                       /   \
      *         X      (N)      --->        U       Z
      *               /   \               /   \
@@ -594,7 +594,7 @@ void *treap_remove(struct treap *t, const char *k, size_t kn)
      *               /   \               /   \
      *             L       R   --->    X      (N)
      *           /   \                       /   \
-     *         X       Y                   Y       Z
+     *         X       Y                   Y       R
      *
      * or
      *
@@ -608,8 +608,10 @@ void *treap_remove(struct treap *t, const char *k, size_t kn)
      * Again, these transformations clearly preserve the ordering of nodes in
      * the binary search tree, and the heap condition.
      */
-    else if (l->wt > r->wt) { *nn = l; n->left = l->right; nn = &l->right; }
-    else { *nn = r; n->right = r->left; nn = &r->left; }
+    else if (l->wt > r->wt)
+      { *nn = l; nn = &l->right; l = n->left = l->right; }
+    else
+      { *nn = r; nn = &r->left; r = n->right = r->left; }
 
   /* Release the key buffer, and return the node that we've now detached. */
   free(n->k); return (n);
@@ -691,9 +693,9 @@ void *treap_next(struct treap_iter *i)
    *
    *   * If the current node's right subtree is not empty, then the next node
    *    to be visited is the leftmost node in that subtree.  All of the
-   *    nodes on the stack are ancestors of the current nodes, and the right
+   *    nodes on the stack are ancestors of the current node, and the right
    *    subtree consists of its descendants, so none of them are already on
-   *    the stack, and they're all greater than the current node, and
+   *    the stack; and they're all greater than the current node, and
    *    therefore haven't been visited.  Therefore, we must push the current
    *    node's right child, its /left/ child, and so on, proceeding
    *    leftwards until we fall off the bottom of the tree.