428
+ − 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