Mercurial > hg > xemacs-beta

comparison lisp/pcl-cvs/dll-debug.el @ 0:376386a54a3c r19-14

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Import from CVS: tag r19-14
author cvs
date Mon, 13 Aug 2007 08:45:50 +0200
parents
children 131b0175ea99
comparison
equal deleted inserted replaced
-1:000000000000 0:376386a54a3c
1 ;;; dll-debug -- A slow implementation of dll for debugging.
2 ;;; $Id: dll-debug.el,v 1.1.1.1 1996/12/18 03:32:26 steve Exp $
3
4 ;; Copyright (C) 1991-1995 Free Software Foundation
5
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
10
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.
15 ;;;
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.
20 ;;;
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
25
26 ;;; Commentary:
27
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.
31 (provide 'dll)
32
33 ;;;
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...
39 ;;;
40
41 ;;; Code:
42
43 ;;; ================================================================
44 ;;; Internal functions for use in the doubly linked list package
45
46 (defun dll-get-dummy-node (dll)
47
48 ;; Return the dummy node. INTERNAL USE ONLY.
49 dll)
50
51 (defun dll-list-nodes (dll)
52
53 ;; Return a list of all nodes in DLL. INTERNAL USE ONLY.
54
55 (cdr dll))
56
57 (defun dll-set-from-node-list (dll list)
58
59 ;; Set the contents of DLL to the nodes in LIST.
60 ;; INTERNAL USE ONLY.
61
62 (setcdr dll list))
63
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.
67 ;; INTERNAL USE ONLY.
68 (while (and dll (not (eq (cdr dll) node)))
69 (setq dll (cdr dll)))
70 (if (not dll)
71 (error "Node not on list"))
72 dll)
73
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))))))))
80
81 ;;; ===================================================================
82 ;;; The public functions which operate on doubly linked lists.
83
84 (defmacro dll-element (dll node)
85
86 "Get the element of a NODE in a doubly linked list DLL.
87 Args: DLL NODE."
88
89 (` (car (, node))))
90
91
92 (defun dll-create ()
93 "Create an empty doubly linked list."
94 (cons 'DL-LIST nil))
95
96
97 (defun dll-p (object)
98 "Return t if OBJECT is a doubly linked list, otherwise return nil."
99 (eq (car-safe object) 'DL-LIST))
100
101
102 (defun dll-enter-first (dll element)
103 "Add an element first on a doubly linked list.
104 Args: DLL ELEMENT."
105 (setcdr dll (cons element (cdr dll))))
106
107
108 (defun dll-enter-last (dll element)
109 "Add an element last on a doubly linked list.
110 Args: DLL ELEMENT."
111 (dll-insert-after (dll-get-node-before dll nil) element))
112
113
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."
117
118 (dll-get-node-before dll node)
119 (dll-insert-after node element))
120
121
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."
125
126 (dll-insert-after (dll-get-node-before dll node) element))
127
128
129
130 (defun dll-next (dll node)
131 "Return the node after NODE, or nil if NODE is the last node.
132 Args: DLL NODE."
133
134 (dll-get-node-before dll node)
135 (cdr node))
136
137
138 (defun dll-previous (dll node)
139 "Return the node before NODE, or nil if NODE is the first node.
140 Args: DLL NODE."
141
142 (let ((prev (dll-get-node-before dll node)))
143 (if (eq dll prev)
144 nil
145 prev)))
146
147
148 (defun dll-delete (dll node)
149
150 "Delete NODE from the doubly linked list DLL.
151 Args: DLL NODE. Return the element of node."
152
153 (setcdr (dll-get-node-before dll node) (cdr node))
154 (car node))
155
156
157 (defun dll-delete-first (dll)
158
159 "Delete the first NODE from the doubly linked list DLL.
160 Return the element. Args: DLL. Returns nil if the DLL was empty."
161
162 (prog1
163 (car (cdr dll))
164 (setcdr dll (cdr (cdr dll)))))
165
166
167 (defun dll-delete-last (dll)
168
169 "Delete the last NODE from the doubly linked list DLL.
170 Return the element. Args: DLL. Returns nil if the DLL was empty."
171
172 (let* ((last (dll-get-node-before dll nil))
173 (semilast (dll-get-node-before dll last)))
174 (if (eq last dll)
175 nil
176 (setcdr semilast nil)
177 (car last))))
178
179
180 (defun dll-first (dll)
181
182 "Return the first element on the doubly linked list DLL.
183 Return nil if the list is empty. The element is not removed."
184
185 (car (cdr dll)))
186
187
188
189
190 (defun dll-last (dll)
191
192 "Return the last element on the doubly linked list DLL.
193 Return nil if the list is empty. The element is not removed."
194
195 (let ((last (dll-get-node-before dll nil)))
196 (if (eq last dll)
197 nil
198 (car last))))
199
200
201
202 (defun dll-nth (dll n)
203
204 "Return the Nth node from the doubly linked list DLL.
205 Args: DLL N
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."
210
211 ;; Branch 0 ("follow left pointer") is used when n is negative.
212 ;; Branch 1 ("follow right pointer") is used otherwise.
213
214 (if (>= n 0)
215 (nthcdr n (cdr dll))
216 (unwind-protect
217 (progn (setcdr dll (nreverse (cdr dll)))
218 (nthcdr (- n) dll))
219 (setcdr dll (nreverse (cdr dll))))))
220
221 (defun dll-empty (dll)
222
223 "Return t if the doubly linked list DLL is empty, nil otherwise"
224
225 (not (cdr dll)))
226
227 (defun dll-length (dll)
228
229 "Returns the number of elements in the doubly linked list DLL."
230
231 (length (cdr dll)))
232
233
234
235 (defun dll-copy (dll &optional element-copy-fnc)
236
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."
241
242 (if element-copy-fnc
243 (cons 'DL-LIST (mapcar element-copy-fnc (cdr dll)))
244 (copy-sequence dll)))
245
246
247 (defun dll-all (dll)
248
249 "Return all elements on the double linked list DLL as an ordinary list."
250
251 (cdr dll))
252
253
254 (defun dll-clear (dll)
255
256 "Clear the doubly linked list DLL, i.e. make it completely empty."
257
258 (setcdr dll nil))
259
260
261 (defun dll-map (map-function dll)
262
263 "Apply MAP-FUNCTION to all elements in the doubly linked list DLL.
264 The function is applied to the first element first."
265
266 (mapcar map-function (cdr dll)))
267
268
269 (defun dll-map-reverse (map-function dll)
270
271 "Apply MAP-FUNCTION to all elements in the doubly linked list DLL.
272 The function is applied to the last element first."
273
274 (unwind-protect
275 (setcdr dll (nreverse (cdr dll)))
276 (mapcar map-function (cdr dll))
277 (setcdr dll (nreverse (cdr dll)))))
278
279
280 (defun dll-create-from-list (list)
281
282 "Given an elisp LIST create a doubly linked list with the same elements."
283
284 (cons 'DL-LIST list))
285
286
287
288 (defun dll-sort (dll predicate)
289
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."
294
295 (setcdr dll (sort (cdr dll) predicate))
296 dll)
297
298
299 (defun dll-filter (dll predicate)
300
301 "Remove all elements in the doubly linked list DLL for which PREDICATE
302 return nil."
303
304 (let* ((prev dll)
305 (node (cdr dll)))
306
307 (while node
308 (cond
309 ((funcall predicate (car node))
310 (setq prev node))
311 (t
312 (setcdr prev (cdr node))))
313 (setq node (cdr node)))))
314
315 ;; dll-debug.el ends here