1 ;;; dll-debug -- A slow implementation of dll for debugging.
2 ;;; $Id: dll-debug.el,v 1.1.1.1 1998-10-07 11:10:57 jareth Exp $
4 ;; Copyright (C) 1991-1995 Free Software Foundation
6 ;; Author: Per Cederqvist <ceder@lysator.liu.se>
7 ;; Maintainer: elib-maintainers@lysator.liu.se
8 ;; Created: before 24 Sep 1991
9 ;; Keywords: extensions, lisp
11 ;;; This program is free software; you can redistribute it and/or modify
12 ;;; it under the terms of the GNU General Public License as published by
13 ;;; the Free Software Foundation; either version 2 of the License, or
14 ;;; (at your option) any later version.
16 ;;; This program is distributed in the hope that it will be useful,
17 ;;; but WITHOUT ANY WARRANTY; without even the implied warranty of
18 ;;; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
19 ;;; GNU General Public License for more details.
21 ;;; You should have received a copy of the GNU General Public License
22 ;;; along with GNU Elib; see the file COPYING. If not, write to
23 ;;; the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
24 ;;; Boston, MA 02111-1307, USA
28 ;;; This is a plug-in replacement for dll.el. It is dreadfully
29 ;;; slow, but it facilitates debugging. Don't trust the comments in
30 ;;; this file too much.
34 ;;; A doubly linked list consists of one cons cell which holds the tag
35 ;;; 'DL-LIST in the car cell and the list in the cdr
36 ;;; cell. The doubly linked list is implemented as a normal list. You
37 ;;; should use dll.el and not this package in debugged code. This
38 ;;; package is not written for speed...
43 ;;; ================================================================
44 ;;; Internal functions for use in the doubly linked list package
46 (defun dll-get-dummy-node (dll)
48 ;; Return the dummy node. INTERNAL USE ONLY.
51 (defun dll-list-nodes (dll)
53 ;; Return a list of all nodes in DLL. INTERNAL USE ONLY.
57 (defun dll-set-from-node-list (dll list)
59 ;; Set the contents of DLL to the nodes in LIST.
64 (defun dll-get-node-before (dll node)
65 ;; Return the node in DLL that points to NODE. Use
66 ;; (dll-get-node-before some-list nil) to get the last node.
68 (while (and dll (not (eq (cdr dll) node)))
71 (error "Node not on list"))
74 (defmacro dll-insert-after (node element)
75 (let ((node-v (make-symbol "node"))
76 (element-v (make-symbol "element")))
77 (` (let (((, node-v) (, node))
78 ((, element-v) (, element)))
79 (setcdr (, node-v) (cons (, element-v) (cdr (, node-v))))))))
81 ;;; ===================================================================
82 ;;; The public functions which operate on doubly linked lists.
84 (defmacro dll-element (dll node)
86 "Get the element of a NODE in a doubly linked list DLL.
93 "Create an empty doubly linked list."
98 "Return t if OBJECT is a doubly linked list, otherwise return nil."
99 (eq (car-safe object) 'DL-LIST))
102 (defun dll-enter-first (dll element)
103 "Add an element first on a doubly linked list.
105 (setcdr dll (cons element (cdr dll))))
108 (defun dll-enter-last (dll element)
109 "Add an element last on a doubly linked list.
111 (dll-insert-after (dll-get-node-before dll nil) element))
114 (defun dll-enter-after (dll node element)
115 "In the doubly linked list DLL, insert a node containing ELEMENT after NODE.
116 Args: DLL NODE ELEMENT."
118 (dll-get-node-before dll node)
119 (dll-insert-after node element))
122 (defun dll-enter-before (dll node element)
123 "In the doubly linked list DLL, insert a node containing ELEMENT before NODE.
124 Args: DLL NODE ELEMENT."
126 (dll-insert-after (dll-get-node-before dll node) element))
130 (defun dll-next (dll node)
131 "Return the node after NODE, or nil if NODE is the last node.
134 (dll-get-node-before dll node)
138 (defun dll-previous (dll node)
139 "Return the node before NODE, or nil if NODE is the first node.
142 (let ((prev (dll-get-node-before dll node)))
148 (defun dll-delete (dll node)
150 "Delete NODE from the doubly linked list DLL.
151 Args: DLL NODE. Return the element of node."
153 (setcdr (dll-get-node-before dll node) (cdr node))
157 (defun dll-delete-first (dll)
159 "Delete the first NODE from the doubly linked list DLL.
160 Return the element. Args: DLL. Returns nil if the DLL was empty."
164 (setcdr dll (cdr (cdr dll)))))
167 (defun dll-delete-last (dll)
169 "Delete the last NODE from the doubly linked list DLL.
170 Return the element. Args: DLL. Returns nil if the DLL was empty."
172 (let* ((last (dll-get-node-before dll nil))
173 (semilast (dll-get-node-before dll last)))
176 (setcdr semilast nil)
180 (defun dll-first (dll)
182 "Return the first element on the doubly linked list DLL.
183 Return nil if the list is empty. The element is not removed."
190 (defun dll-last (dll)
192 "Return the last element on the doubly linked list DLL.
193 Return nil if the list is empty. The element is not removed."
195 (let ((last (dll-get-node-before dll nil)))
202 (defun dll-nth (dll n)
204 "Return the Nth node from the doubly linked list DLL.
206 N counts from zero. If DLL is not that long, nil is returned.
207 If N is negative, return the -(N+1)th last element.
208 Thus, (dll-nth dll 0) returns the first node,
209 and (dll-nth dll -1) returns the last node."
211 ;; Branch 0 ("follow left pointer") is used when n is negative.
212 ;; Branch 1 ("follow right pointer") is used otherwise.
217 (progn (setcdr dll (nreverse (cdr dll)))
219 (setcdr dll (nreverse (cdr dll))))))
221 (defun dll-empty (dll)
223 "Return t if the doubly linked list DLL is empty, nil otherwise"
227 (defun dll-length (dll)
229 "Returns the number of elements in the doubly linked list DLL."
235 (defun dll-copy (dll &optional element-copy-fnc)
237 "Return a copy of the doubly linked list DLL.
238 If optional second argument ELEMENT-COPY-FNC is non-nil it should be
239 a function that takes one argument, an element, and returns a copy of it.
240 If ELEMENT-COPY-FNC is not given the elements are not copied."
243 (cons 'DL-LIST (mapcar element-copy-fnc (cdr dll)))
244 (copy-sequence dll)))
249 "Return all elements on the double linked list DLL as an ordinary list."
254 (defun dll-clear (dll)
256 "Clear the doubly linked list DLL, i.e. make it completely empty."
261 (defun dll-map (map-function dll)
263 "Apply MAP-FUNCTION to all elements in the doubly linked list DLL.
264 The function is applied to the first element first."
266 (mapcar map-function (cdr dll)))
269 (defun dll-map-reverse (map-function dll)
271 "Apply MAP-FUNCTION to all elements in the doubly linked list DLL.
272 The function is applied to the last element first."
275 (setcdr dll (nreverse (cdr dll)))
276 (mapcar map-function (cdr dll))
277 (setcdr dll (nreverse (cdr dll)))))
280 (defun dll-create-from-list (list)
282 "Given an elisp LIST create a doubly linked list with the same elements."
284 (cons 'DL-LIST list))
288 (defun dll-sort (dll predicate)
290 "Sort the doubly linked list DLL, stably, comparing elements using PREDICATE.
291 Returns the sorted list. DLL is modified by side effects.
292 PREDICATE is called with two elements of DLL, and should return T
293 if the first element is \"less\" than the second."
295 (setcdr dll (sort (cdr dll) predicate))
299 (defun dll-filter (dll predicate)
301 "Remove all elements in the doubly linked list DLL for which PREDICATE
309 ((funcall predicate (car node))
312 (setcdr prev (cdr node))))
313 (setq node (cdr node)))))
315 ;; dll-debug.el ends here