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