I am using an avl-tree to maintain a sorted list, e.g.:

(require 'avl-tree)

(let ((tree (avl-tree-create (lambda (a b) (string-lessp (car a) (car b))))))
  (avl-tree-enter tree (cons "b" 0))
  (avl-tree-enter tree (cons "a" 1))
  (avl-tree-enter tree (cons  "A" 2))
  (avl-tree-enter tree (cons  "d" 3))
  (avl-tree-enter tree (cons  "c" 4))
  (avl-tree-enter tree (cons  "C" 5))

  (avl-tree-flatten tree))

leads to this sorted list

((A . 2) (C . 5) (a . 1) (b . 0) (c . 4) (d . 3))

sorted by the car of each cons cell.

I can use a command like:

(avl-tree-member tree '("b"))

which returns the cell (b . 0), but what I really want is to get the next or previous cons cell. I usually do this by finding the index of that cell in the sorted list, e.g. (-find-index) or (cl-position), but neither of these seem to take advantage of the sorted nature of the list. Is there a way to get the next/previous node out of avl-tree (or something similar)?

The real application of this is I have a list of hundreds of journal files sorted by date, and I want to be able to find the next or previous entry like this.


You could use this function to find the smallest entry strictly larger than a given datum:

(defun avl-above (tree data)
  (let ((cmp (avl-tree--cmpfun tree)))
    (cl-labels ((above (node)
                   (when node
                     (if (funcall cmp data (avl-tree--node-data node))
                         (let ((left-above (above (avl-tree--node-left node))))
                           (if (and left-above
                                    (funcall cmp
                                             (avl-tree--node-data left-above)
                                             (avl-tree--node-data node)))
                       (above (avl-tree--node-right node))))))
      (let ((node-above (above (avl-tree--root tree))))
        (and node-above (avl-tree--node-data node-above))))))

With your sample tree you'd have, for example:

(avl-above tree '(""))  ; => ("A" . 2)
(avl-above tree '("A")  ; => ("C" . 5)
(avl-above tree '("c")) ; => ("d" . 3)
(avl-above tree '("d")) ; => nil

(And, of course, to get the largest entry below a given datum you'd write a completely symmetrical function.)

Note that this is even slightly better than being able to find the next or previous entry after a given entry, you can also find the next entry after a "non-entry". In your application, you could use this to find the first journal file strictly after or before a given date.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.