Skip to content

Instantly share code, notes, and snippets.

@alphapapa
Forked from jordonbiondo/dll-fifo.el
Created January 1, 2019 01:39
Show Gist options
  • Save alphapapa/4151116c5374b24733cba3bdc0679ea0 to your computer and use it in GitHub Desktop.
Save alphapapa/4151116c5374b24733cba3bdc0679ea0 to your computer and use it in GitHub Desktop.
A fifo queue in emacs lisp using a cyclic doubly linked list.
;; FIFO queue implementation using cyclic doubly linked lists
;;
;; This data structure is a bit overkill for a queue,
;; but it has many other uses
;; a doubly linked list cell look like (val . (prev-cell next-cell))
;;
;; a FIFO queue object looks like ('fifo . cyclic-doubly-linked-list)
;;
;; An empty FIFO queue would be: ('fifo . nil)
;; example useage:
;; (let ((my-fifo (fifo '(1 2))))
;; (print (fifo-pop my-fifo)) ;; => 1
;; (fifo-push my-fifo 3)
;; (print (fifo-pop my-fifo)) ;; => 2
;; (print (fifo-pop my-fifo))) ;; => 3
(defun dll (list)
"Create a doubly linked list with LIST's elements."
(let* ((dll (cons (pop list) (cons nil nil)))
(prev dll))
(dolist (v list)
(let ((next (cons v (cons nil nil))))
(dll-set-next prev next)
(dll-set-prev next prev)
(setq prev next)))
dll))
(defun dll-nth-node (dll n)
"Get Nth node of the doubly linked list DLL.
N may be negative to look backwards."
(let ((node dll))
(dotimes (i (abs n))
(setq node
(if (< n 0)
(car (cdr node))
(cdr (cdr node)))))
node))
(defun cyclic-dll (list)
"Make a cyclic doubly linked list from LIST."
(let* ((x (dll list))
(end (dll-nth-node x (1- (length list)))))
(dll-set-next end x)
(dll-set-prev x end)
x))
(defun fifo (list)
"Create a new FIFO queue containing LIST initially."
(let ((f (cons 'fifo nil)))
(dolist (e list)
(fifo-push f e))
f))
(defun fifo-push (fifo elem)
"Push ELEM onto the back of FIFO."
(if (cdr-safe fifo)
(let ((n (dll (list elem))))
(dll-set-next (dll-prev (cdr fifo)) n)
(dll-set-prev n (dll-prev (cdr fifo)))
(dll-set-prev (cdr fifo) n)
(dll-set-next n (cdr fifo))
fifo)
(setcdr fifo (cyclic-dll (list elem)))))
(defun fifo-pop (fifo)
"Pop and return the first element off FIFO."
(let ((val (car-safe (cdr-safe fifo)))
(dll (cdr fifo)))
(if (eql dll (dll-next dll))
(setcdr fifo nil)
(dll-set-next (dll-prev dll) (dll-next dll))
(dll-set-prev (dll-next dll) (dll-prev dll))
(setcdr fifo (dll-next dll)))
val))
(defun fifo-length (fifo)
"Return the number of elements in FIFO."
(let* ((dll (cdr fifo))
(next (dll-next dll))
(len (if next 1 0)))
(while (and dll next (not (eql dll next)))
(incf len)
(setq next (dll-next next)))
len))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment