Mercurial > hg > xemacs-beta

comparison lisp/prim/undo-stack.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 ac2d302a0011
comparison
equal deleted inserted replaced
-1:000000000000 0:376386a54a3c
1 ;;; undo-stack.el --- An "undoable stack" object.
2 ;; Keywords: extensions
3
4 ;; Copyright (C) 1996 Ben Wing.
5
6 ;; This file is part of XEmacs.
7
8 ;; XEmacs is free software; you can redistribute it and/or modify it
9 ;; under the terms of the GNU General Public License as published by
10 ;; the Free Software Foundation; either version 2, or (at your option)
11 ;; any later version.
12
13 ;; XEmacs is distributed in the hope that it will be useful, but
14 ;; WITHOUT ANY WARRANTY; without even the implied warranty of
15 ;; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
16 ;; General Public License for more details.
17
18 ;; You should have received a copy of the GNU General Public License
19 ;; along with XEmacs; see the file COPYING. If not, write to the Free
20 ;; Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.
21
22 ;;; Synched up with: Not in FSF.
23
24 ;;; Commentary:
25
26 ;;; An "undoable stack" is an object that can be used to implement
27 ;;; a history of positions, with undo and redo. Conceptually, it
28 ;;; is the kind of data structure used to keep track of (e.g.)
29 ;;; visited Web pages, so that the "Back" and "Forward" operations
30 ;;; in the browser work. Basically, I can successively visit a
31 ;;; number of Web pages through links, and then hit "Back" a
32 ;;; few times to go to previous positions, and then "Forward" a
33 ;;; few times to reverse this process. This is similar to an
34 ;;; "undo" and "redo" mechanism.
35 ;;;
36 ;;; Note that Emacs does not standardly contain structures like
37 ;;; this. Instead, it implements history using either a ring
38 ;;; (the kill ring, the mark ring), or something like the undo
39 ;;; stack, where successive "undo" operations get recorded as
40 ;;; normal modifications, so that if you do a bunch of successive
41 ;;; undo's, then something else, then start undoing, you will
42 ;;; be redoing all your undo's back to the point before you did
43 ;;; the undo's, and then further undo's will act like the previous
44 ;;; round of undo's. I think that both of these paradigms are
45 ;;; inferior to the "undoable-stack" paradigm because they're
46 ;;; confusing and difficult to keep track of.
47 ;;;
48 ;;; Conceptually, imagine a position history like this:
49 ;;;
50 ;;; 1 -> 2 -> 3 -> 4 -> 5 -> 6
51 ;;; ^^
52 ;;;
53 ;;; where the arrow indicates where you currently are. "Going back"
54 ;;; and "going forward" just amount to moving the arrow. However,
55 ;;; what happens if the history state is this:
56 ;;;
57 ;;; 1 -> 2 -> 3 -> 4 -> 5 -> 6
58 ;;; ^^
59 ;;;
60 ;;; and then I visit new positions (7) and (8)? In the most general
61 ;;; implementation, you've just caused a new branch like this:
62 ;;;
63 ;;; 1 -> 2 -> 3 -> 4 -> 5 -> 6
64 ;;; |
65 ;;; |
66 ;;; 7 -> 8
67 ;;; ^^
68 ;;;
69 ;;; But then you can end up with a whole big tree, and you need
70 ;;; more sophisticated ways of navigating ("Forward" might involve
71 ;;; a choice of paths to follow) and managing its size (if you don't
72 ;;; want to keep unlimited history, you have to truncate at some point,
73 ;;; and how do you truncate a tree?)
74 ;;;
75 ;;; My solution to this is just to insert the new positions like
76 ;;; this:
77 ;;;
78 ;;; 1 -> 2 -> 3 -> 4 -> 7 -> 8 -> 5 -> 6
79 ;;; ^^
80 ;;;
81 ;;; (Netscape, I think, would just truncate 5 and 6 completely,
82 ;;; but that seems a bit drastic. In the Emacs-standard "ring"
83 ;;; structure, this problem is avoided by simply moving 5 and 6
84 ;;; to the beginning of the ring. However, it doesn't seem
85 ;;; logical to me to have "going back past 1" get you to 6.)
86 ;;;
87 ;;; Now what if we have a "maximum" size of (say) 7 elements?
88 ;;; When we add 8, we could truncate either 1 or 6. Since 5 and
89 ;;; 6 are "undone" positions, we should presumably truncate
90 ;;; them before 1. So, adding 8 truncates 6, adding 9 truncates
91 ;;; 5, and adding 10 truncates 1 because there is nothing more
92 ;;; that is forward of the insertion point.
93 ;;;
94 ;;; Interestingly, this method of truncation is almost like
95 ;;; how a ring would truncate. A ring would move 5 and 6
96 ;;; around to the back, like this:
97 ;;;
98 ;;; 5 -> 6 -> 1 -> 2 -> 3 -> 4 -> 7 -> 8
99 ;;; ^^
100 ;;;
101 ;;; However, when 8 is added, the ring truncates 5 instead of
102 ;;; 6, which is less than optimal.
103 ;;;
104 ;;; Conceptually, we can implement the "undoable stack" using
105 ;;; two stacks of a sort called "truncatable stack", which are
106 ;;; just simple stacks, but where you can truncate elements
107 ;;; of of the bottom of the stack. Then, the undoable stack
108 ;;;
109 ;;; 1 -> 2 -> 3 -> 4 -> 5 -> 6
110 ;;; ^^
111 ;;;
112 ;;; is equivalent to two truncatable stacks:
113 ;;;
114 ;;; 4 <- 3 <- 2 <- 1
115 ;;; 5 <- 6
116 ;;;
117 ;;; where I reversed the direction to accord with the probable
118 ;;; implementation of a standard list. To do another undo,
119 ;;; I pop 4 off of the first stack and move it to the top of
120 ;;; the second stack. A redo operation does the opposite.
121 ;;; To truncate to the proper size, first chop off 6, then 5,
122 ;;; then 1 -- in all cases, truncating off the bottom.
123
124 (define-error 'trunc-stack-bottom "Bottom of stack reached.")
125
126 (defsubst trunc-stack-stack (stack)
127 ;; return the list representing the trunc-stack's elements.
128 ;; the head of the list is the most recent element.
129 (aref stack 1))
130
131 (defsubst trunc-stack-length (stack)
132 ;; return the number of elements in the trunc-stack.
133 (aref stack 2))
134
135 (defsubst set-trunc-stack-stack (stack new)
136 ;; set the list representing the trunc-stack's elements.
137 (aset stack 1 new))
138
139 (defsubst set-trunc-stack-length (stack new)
140 ;; set the length of the trunc-stack.
141 (aset stack 2 new))
142
143 ;; public functions:
144
145 (defun make-trunc-stack ()
146 ;; make an empty trunc-stack.
147 (vector 'trunc-stack nil 0))
148
149 (defun trunc-stack-push (stack el)
150 ;; push a new element onto the head of the trunc-stack.
151 (set-trunc-stack-stack stack (cons el (trunc-stack-stack stack)))
152 (set-trunc-stack-length stack (1+ (trunc-stack-length stack))))
153
154 (defun trunc-stack-top (stack &optional n)
155 ;; return the nth topmost element from the trunc-stack.
156 ;; signal an error if the stack doesn't have that many elements.
157 (or n (setq n 0))
158 (if (>= n (trunc-stack-length stack))
159 (signal-error 'trunc-stack-bottom (list stack))
160 (nth n (trunc-stack-stack stack))))
161
162 (defun trunc-stack-pop (stack)
163 ;; pop and return the topmost element from the stack.
164 (prog1 (trunc-stack-top stack)
165 (set-trunc-stack-stack stack (cdr (trunc-stack-stack stack)))
166 (set-trunc-stack-length stack (1- (trunc-stack-length stack)))))
167
168 (defun trunc-stack-truncate (stack &optional n)
169 ;; truncate N items off the bottom of the stack. If the stack is
170 ;; not that big, it just becomes empty.
171 (or n (setq n 1))
172 (if (> n 0)
173 (let ((len (trunc-stack-length stack)))
174 (if (>= n len)
175 (progn
176 (set-trunc-stack-length stack 0)
177 (set-trunc-stack-stack stack nil))
178 (setcdr (nthcdr (1- (- len n)) (trunc-stack-stack stack)) nil)
179 (set-trunc-stack-length stack (- len n))))))
180
181 ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
182
183 ;;; FMH! FMH! FMH! This object-oriented stuff doesn't really work
184 ;;; properly without built-in structures (vectors suck) and without
185 ;;; public and private functions and fields. Bogons descend on
186 ;;; RMS for not believing in any of this.
187
188 (defsubst undoable-stack-max (stack)
189 (aref stack 1))
190
191 (defsubst undoable-stack-a (stack)
192 (aref stack 2))
193
194 (defsubst undoable-stack-b (stack)
195 (aref stack 3))
196
197 ;; public functions:
198
199 (defun make-undoable-stack (max)
200 ;; make an empty undoable stack of max size MAX.
201 (vector 'undoable-stack max (make-trunc-stack) (make-trunc-stack)))
202
203 (defsubst set-undoable-stack-max (stack new)
204 ;; change the max size of an undoable stack.
205 (aset stack 1 new))
206
207 (defun undoable-stack-a-top (stack)
208 ;; return the topmost element off the "A" stack of an undoable stack.
209 ;; this is the most recent position pushed on the undoable stack.
210 (trunc-stack-top (undoable-stack-a stack)))
211
212 (defun undoable-stack-a-length (stack)
213 (trunc-stack-length (undoable-stack-a stack)))
214
215 (defun undoable-stack-b-top (stack)
216 ;; return the topmost element off the "B" stack of an undoable stack.
217 ;; this is the position that will become the most recent position,
218 ;; after a redo operation.
219 (trunc-stack-top (undoable-stack-b stack)))
220
221 (defun undoable-stack-b-length (stack)
222 (trunc-stack-length (undoable-stack-b stack)))
223
224 (defun undoable-stack-push (stack el)
225 ;; push an element onto the stack.
226 (let*
227 ((lena (trunc-stack-length (undoable-stack-a stack)))
228 (lenb (trunc-stack-length (undoable-stack-b stack)))
229 (max (undoable-stack-max stack))
230 (len (+ lena lenb)))
231 ;; maybe truncate some elements. We have to deal with the
232 ;; possibility that we have more elements than our max
233 ;; (someone might have reduced the max).
234 (if (>= len max)
235 (let ((must-nuke (1+ (- len max))))
236 ;; chop off must-nuke elements from the B stack.
237 (trunc-stack-truncate (undoable-stack-b stack) must-nuke)
238 ;; but if there weren't that many elements to chop,
239 ;; take the rest off the A stack.
240 (if (< lenb must-nuke)
241 (trunc-stack-truncate (undoable-stack-a stack)
242 (- must-nuke lenb)))))
243 (trunc-stack-push (undoable-stack-a stack) el)))
244
245 (defun undoable-stack-pop (stack)
246 ;; pop an element off the stack.
247 (trunc-stack-pop (undoable-stack-a stack)))
248
249 (defun undoable-stack-undo (stack)
250 ;; transfer an element from the top of A to the top of B.
251 ;; return value is undefined.
252 (trunc-stack-push (undoable-stack-b stack)
253 (trunc-stack-pop (undoable-stack-a stack))))
254
255 (defun undoable-stack-redo (stack)
256 ;; transfer an element from the top of B to the top of A.
257 ;; return value is undefined.
258 (trunc-stack-push (undoable-stack-a stack)
259 (trunc-stack-pop (undoable-stack-b stack))))
260
261
262
263