The HP-67 calculator allows the user to enter program steps.  These program steps need not be appended to the existing steps, they can be inserted in the middle of a previously-entered sequence.  These steps have an associated index, their position in the program space, so if a new step is inserted at the beginning, then all steps after it must have their index incremented.

One could do this in an array, but insertions have a high cost as all the higher elements have to be shifted.  One could use a list, but then random access is expensive because it’s not indexed.  The natural way to solve this problem is with ropes.  You can read more about the rope data structure on the Wikipedia page here (but note that, at the time of this posting, the Wikipedia text incorrectly asserted that some operations described required balanced trees, there is no such requirement).

A rope data structure is essentially a tree, the leaves of which contain the subsequences, in order.  Insertion of new elements is done by cutting the tree at the insertion point, after which the insertion is just an append, which is relatively inexpensive.  Afterwards, the cut trees are reassembled.

The code I’ve written for ropes is in a new file, ropes.lisp, in the git repository at the tag v2014-12-08.

You’ll notice in the code that there is a node structure and a rope structure, and that the rope structure contains only a single node.  You might think that it would be more efficient simply to pass around the root node as if it were a rope, and avoid creating a second structure, but there’s a good reason for doing it this way.  The operations that we are performing can modify the tree, and they can result in a  rope that has a different root node.  If the user passed in the node, rather than the rope, modification of that node would require more care, and some copying, to make sure that the user’s handle remained valid.  By wrapping the node in a new structure, the rope manipulation code can modify even the root node without affecting the handle that the user passed.

Here are some sample pieces of code from the file.  See the git repository for the full code:

(defstruct (node)
  (weight               0)
  (parent               nil)
  (left-child           nil)
  (right-child          nil)
  (contents             (make-array 0 :adjustable t)))


(defun right-uncle (node)
  "Returns the node that is the first right child of a parent
   that doesn't return to myself, or nil if there isn't one."
  (when (node-parent node)
    (cond
      ((eq node (node-left-child (node-parent node)))
       (node-right-child (node-parent node)))
      (t
       (right-uncle (node-parent node))))))


(defun leftmost-leaf (node)
  "Returns the leftmost leaf under the node.  Could be self, if
   there are no children."
  (let ((nlc (node-left-child node))
        (nrc (node-right-child node)))
    (cond
      ((and (not nlc) (not nrc))
       node)
      ((not nlc)
       (leftmost-leaf nrc))
      (t
       (leftmost-leaf nlc)))))


(defmacro iterate-over-contents ((rope obj) &body body)
  (let ((cur-node (gensym))
        (cur-pos (gensym)))
    `(let ((,cur-node (leftmost-leaf (rope-root-node ,rope)))
           (,cur-pos 0))
       (do ()
           (nil)
         (cond
           ((>= ,cur-pos (node-weight ,cur-node))
            (let ((uncle (right-uncle ,cur-node)))
              (unless uncle
                (return))
              (setf ,cur-node (leftmost-leaf uncle))
              (setf ,cur-pos 0)))
           (t
            (let ((,obj (aref (node-contents ,cur-node) ,cur-pos)))
              (incf ,cur-pos)
              ,@body)))))))

(defun get-full-contents (rope)
  (let ((rval (make-array (rope-length rope)))
        (pos 0))
    (iterate-over-contents (rope entry)
      (setf (aref rval pos) entry)
      (incf pos))
    rval))