(require (quote elib-node)) (provide (quote dll)) (defun dll-get-dummy-node (dll) (byte-code "A‡" [dll] 1)) (defun dll-list-nodes (dll) (byte-code "ÁÅ ! ÆH =?… B‰ˆ ÆH‰ˆ‚ ˆ+‡" [result nil dummy dll node dll-get-dummy-node 0] 4)) (defun dll-set-from-node-list (dll list) (byte-code "Ä!ˆÅ!  …' @Æ Iˆ Ç @Iˆ @‰ˆ A‰ˆ‚ ˆ Ç Iˆ Æ I*‡" [dll dummy left list dll-clear dll-get-dummy-node 0 1] 6)) (defmacro dll-element (dll node) "Get the element of a NODE in a doubly linked list DLL. Args: DLL NODE." (byte-code "ÁD‡" [node elib-node-data] 2)) (defun dll-create nil "\ Create an empty doubly linked list." (byte-code "ÂÁÁÁ#ÃIˆÄIˆÅB)‡" [dummy-node nil vector 1 0 DL-LIST] 4)) (defun dll-p (object) "\ Return t if OBJECT is a doubly linked list, otherwise return nil." (byte-code "Á!Â=‡" [object car-safe DL-LIST] 3)) (defun dll-enter-first (dll element) "\ Add an element first on a doubly linked list. Args: DLL ELEMENT." (byte-code "ÂÃ! #‡" [dll element dll-enter-after dll-get-dummy-node] 5)) (defun dll-enter-last (dll element) "\ Add an element last on a doubly linked list. Args: DLL ELEMENT." (byte-code "ÂÃ! #‡" [dll element dll-enter-before dll-get-dummy-node] 5)) (defun dll-enter-after (dll node element) "\ In the doubly linked list DLL, insert a node containing ELEMENT after NODE. Args: DLL NODE ELEMENT." (byte-code "à ÄH # ÄHÅIˆ ÄI)‡" [new-node node element vector 1 0] 4)) (defun dll-enter-before (dll node element) "\ In the doubly linked list DLL, insert a node containing ELEMENT before NODE. Args: DLL NODE ELEMENT." (byte-code "à ÄH # ÄHÅIˆ ÄI)‡" [new-node node element vector 0 1] 4)) (defun dll-next (dll node) "\ Return the node after NODE, or nil if NODE is the last node. Args: DLL NODE." (byte-code "ÃHÄ !=ƒ‚ÃH‡" [node dll nil 1 dll-get-dummy-node] 3)) (defun dll-previous (dll node) "\ Return the node before NODE, or nil if NODE is the first node. Args: DLL NODE." (byte-code "ÃHÄ !=ƒ‚ÃH‡" [node dll nil 0 dll-get-dummy-node] 3)) (defun dll-delete (dll node) "\ Delete NODE from the doubly linked list DLL. Args: DLL NODE. Return the element of node." (byte-code "ÁHÂÂHIˆÂHÁÁHIˆÃH‡" [node 0 1 2] 4)) (defun dll-delete-first (dll) "\ Delete the first NODE from the doubly linked list DLL. Return the element. Args: DLL. Returns nil if the DLL was empty." (byte-code "ÁÂ!ÃH\"‡" [dll dll-delete dll-get-dummy-node 1] 5)) (defun dll-delete-last (dll) "\ Delete the last NODE from the doubly linked list DLL. Return the element. Args: DLL. Returns nil if the DLL was empty." (byte-code "ÁÂ!ÃH\"‡" [dll dll-delete dll-get-dummy-node 0] 5)) (defun dll-first (dll) "\ Return the first element on the doubly linked list DLL. Return nil if the list is empty. The element is not removed." (byte-code "Â!ÃHÂ!=ƒÁ‚Â!ÃHÄH‡" [dll nil dll-get-dummy-node 1 2] 5)) (defun dll-last (dll) "\ Return the last element on the doubly linked list DLL. Return nil if the list is empty. The element is not removed." (byte-code "Â!ÃHÂ!=ƒÁ‚Â!ÃHÄH‡" [dll nil dll-get-dummy-node 0 2] 5)) (defun dll-nth (dll n) "\ Return the Nth node from the doubly linked list DLL. Args: DLL N N counts from zero. If DLL is not that long, nil is returned. If N is negative, return the -(N+1)th last element. Thus, (dll-nth dll 0) returns the first node, and (dll-nth dll -1) returns the last node." (byte-code "Æ ! ÇWƒÇ‚È H ÇW…É Z‰ˆ =?…* ÇV…; H‰ˆ S‰ˆ‚ ˆ =ƒFÅ‚G +‡" [dummy dll branch n node nil dll-get-dummy-node 0 1 -1] 4)) (defun dll-empty (dll) "\ Return t if the doubly linked list DLL is empty, nil otherwise" (byte-code "Á!ÂHÁ!=‡" [dll dll-get-dummy-node 0] 4)) (defun dll-length (dll) "\ Returns the number of elements in the doubly linked list DLL." (byte-code "Ä !ÅHÆ =?… ÅH‰ˆ T‰ˆ‚ ˆ +‡" [dummy dll node n dll-get-dummy-node 1 0] 4)) (defun dll-copy (dll &optional element-copy-fnc) "\ Return a copy of the doubly linked list DLL. If optional second argument ELEMENT-COPY-FNC is non-nil it should be a function that takes one argument, an element, and returns a copy of it. If ELEMENT-COPY-FNC is not given the elements are not copied." (byte-code "Ä Å Æ\" ƒ' …$ÇÈ ÉH\"\"ˆÊ \"‰ˆ‚ ‚< …<Ç ÉH\"ˆÊ \"‰ˆ‚'ˆ*‡" [result node dll element-copy-fnc dll-create dll-nth 0 dll-enter-last funcall 2 dll-next] 10)) (defun dll-all (dll) "\ Return all elements on the double linked list DLL as an ordinary list." (byte-code "ÁÅ ! ÆH =?…\" ÇHB‰ˆ ÆH‰ˆ‚ ˆ+‡" [result nil dummy dll node dll-get-dummy-node 0 2] 4)) (defun dll-clear (dll) "\ Clear the doubly linked list DLL, i.e. make it completely empty." (byte-code "Á!ÂÁ!IˆÁ!ÃÁ!I‡" [dll dll-get-dummy-node 0 1] 7)) (defun dll-map (map-function dll) "\ Apply MAP-FUNCTION to all elements in the doubly linked list DLL. The function is applied to the first element first." (byte-code "Ä !ÅH =?…Æ ÇH\"ˆ ÅH‰ˆ‚*‡" [dummy dll node map-function dll-get-dummy-node 1 funcall 2] 6)) (defun dll-map-reverse (map-function dll) "\ Apply MAP-FUNCTION to all elements in the doubly linked list DLL. The function is applied to the last element first." (byte-code "Ä !ÅH =?…Æ ÇH\"ˆ ÅH‰ˆ‚*‡" [dummy dll node map-function dll-get-dummy-node 0 funcall 2] 6)) (defun dll-create-from-list (list) "\ Given an elisp LIST create a doubly linked list with the same elements." (byte-code "  …à @\"ˆ A‰ˆ‚ˆ)‡" [dll list dll-create dll-enter-last] 5)) (defun dll-sort (dll predicate) "\ Sort the doubly linked list DLL, stably, comparing elements using PREDICATE. Returns the sorted list. DLL is modified by side effects. PREDICATE is called with two elements of DLL, and should return T if the first element is \"less\" than the second." (byte-code "ÁÂÃ!Ä\"\"ˆ‡" [dll dll-set-from-node-list sort dll-list-nodes (lambda (x1 x2) (byte-code "à ÄH ÄH#‡" [predicate x1 x2 funcall 2] 5))] 6)) (defun dll-filter (dll predicate) "\ Remove all elements in the doubly linked list DLL for which PREDICATE returns nil." (byte-code "Æ !ÇHÅ =?…0 ÇH‰ˆÈ ÉH\"ƒ$Å‚(Ê \"ˆ ‰ˆ‚ +‡" [dummy dll node next predicate nil dll-get-dummy-node 1 funcall 2 dll-delete] 6))