Implementing Undo - Computerphile Transcript, AI Summary & Key Points

00:00 So, I thought we'd it would be interesting to talk about probably a a feature that's in pretty much every software application that people use that they probably use all the time and probably have never given a second thought about. Undo. Not all software uh let's put it another way. Let's undo that and let's put it another way. I'm old enough to remember when software didn't have undo as a feature.

00:23 On the computer behind me there's a there's a word processor there and even though the computer has an actual undo key, this software doesn't appear to do anything when you press the undo key. There doesn't seem to be any menu option for undoing. It's a it's a word processor without undo. Um you can imagine how annoying that was. I think it's only recently implemented in Photoshop.

00:46 It's definitely been there since I've been using it. There was been the history >> History >> panel >> but not undo. >> I think it's still undo it when you press the >> Yeah, yeah, but oh sorry. The point is there wasn't literally didn't have a thing called undo. >> Yeah, you have the history panel on the side. The interesting thing about undo is you don't think about it, but when you do start to wonder about it, you start to realize that there's actually quite a lot that's involved and you have to think about it at

01:10 different levels of computer science. There's the user expectation. There's the user experience as they press undo. What do they expect to happen when you press undo? Uh and that might not be what you might think in the first place. Um and then there's well, how do I go about implementing that in the software? How do I do that? Um and how do I do it in a way so that I can also then redo it if the user wants to undo the undo?

01:36 Uh and and so on and capture that. And then of course, you've got the sort of the question well, what if I want to have multiple levels of undo? Well, I want to undo that and then undo the previous step and so on and then redo them as we do like the history panel in Photoshop as you talked about earlier. How do you go about implementing that? And so I think it it's actually something that the more you think about it, the more involved it gets and it's perhaps one of the more interesting things to actually ever program

02:02 up. Uh because it touches on so many different aspects of what you have to think about. >> One of the things you're doing is just increasing how much data you're storing over and over. >> Absolutely. And that's And that's another aspect we'll get to when we talk about multiple levels of undo, particularly in something like um Photoshop or other image editors are available.

02:19 Um but we all use Photoshop. Uh and so on. The you're dealing with big data. These files get very big. Um not as in big data. Um and so if you're not careful, you can fill up your memory, your hard disk with all the undo history. And so you need to take that into account. So let's start with something simple. Um I've got one open on screen here or we'll have in a second.

02:40 Let's start with something simple. Let's think about a text editor. So I've got a text editor here. Um and if I type some text into it, the cat sat on the mat. This is a long bit of text that I am typing in. So I've typed this text in. If I press undo, what should be undone? Shawn, what do you think should be undone? >> At the very least, the last character you typed.

03:04 >> Yeah. So the last character I typed. But if we just undo the last character, what's the point? We've got the backspace key. And so actually it's it we probably expect more than that. So guess again. >> Uh the last word. >> Okay. So the last word. So you start So we're now starting to actually think, well okay, we need the computer to actually think about what it's going to be undoing.

03:26 We need to program it cuz computers can't think. Um we need to program it so that actually there's a specific action happening. So already we've gone from being this was something simple to Okay, we need to put something into our code to make this work. So if I do this on here, click undo, everything's gone. Okay, let's undo that. Um and let's just fix this.

03:44 I'm typing into the computer. Now what gets undone? >> Probably just the thing that changed since the last undo. >> Okay, so the last edit. So, there we are, the last edit. But, what's interestingly, it still left in what we've typed over, and so on. So, actually, we're starting to see that what we expect to happen is something like that. >> I mean, I'm assuming what's going on here is the computer is putting kind of, I don't know, almost way markers, waypoints in as you go.

04:12 >> Exactly. >> where it goes back. >> But, we've got to write that into our program. So, what we're going to say is, actually, when we do this, we're doing here, save at that point, and then, okay, then we can do back to that point. But, the interesting thing is, how do we decide what that point is going to be. So, we've looked at a simple text editor.

04:29 Let's just switch to a word processor, something like Microsoft Word. All the word processors are editable, if I can find my mouse. There we go. Um got Microsoft Word there. Let's do the same thing there. Let's type some similar text in and see what it undoes, too. So, the cat sat on the mat. This is some text I'm typing into the computer. And I've made some mistakes, but I'm not changing them, although it has just done a spelling error check on that, just to make the point.

05:00 So, what do we think it's going to undo now when I um press undo? >> I I would, before I saw the the spelling check pop up, I would have said the same as the text editor, it goes straight back to having nothing on the screen. But, now I'm wondering if it's cleverer than that. So, >> Yeah, so if we do that, if we undo now, it's undone the spelling error change.

05:24 If we undo again, then it's gone back to where the apostrophe was. But, why where the apostrophe was? Well, that's because, again, there was a hidden edit there, because Word changed it from a normal single pull apostrophe to a smart quote type right to put closing apostrophe, so it looked nice on screen. And then, it undoes, so I've gone back, undoes the whole lot.

05:42 And that's what we would expect to happen is that it's keeping track of points in the document, points as we're editing it where and effectively what you need to keep track of where's the edit change. So, where have we gone from typing text to deleting text, where have we gone from typing text to the spelling checker happen, where have we gone from pasting text in because we paste text in we want the whole block to be undone or the deletion to be undone and so on.

06:08 So, we need to keep track of what's happening. So, let's have a look at something else. Let's have a look at a graphics package and and a bit map specifically a bit map graphics package. Um so, got one on my iPad here. Let's just draw a house. Um there we are. There's a a house. Here's a door, windows one two three four. What would we expect to be undone now?

06:40 >> Probably this the last time the pen >> Yeah. >> came in contact. >> we click undo now, we lose a window. If we click redo, we gain the window. Now, that makes sense. Actually, in terms of the user interaction, it makes far more sense looking at a a bit map thing because we put the pen down, we draw something, pen comes off, we've got a complete action there.

06:59 That's what we'd expect to be undone. So, actually a text editor is trickier to work out what we undo with than a bit map graphics package. If it was a vector graphics package, well, same sort of thing, but it'd be easier in some ways as we'll see in a second. What becomes harder though is how you store that so that you can undo it. So, with a text editor we type the text in and all we need to keep track of is we inserted these characters at this point in the document and then we can just delete those characters from

07:32 the document. So, we can just undo that and then by deleting those characters and if we want to redo what we stored what characters we typed in, um we can then store them back in. And in fact, what you could do is just store every key press and then amalgamate them together and then you can undo those key presses or replay those key presses. So, that's relatively straightforward to store.

07:57 While it's conceptually easier to with the bit map to work out what to undo, we have a big problem because as soon as I change that bit map, I don't have the original to go back to and I can't undraw what I've drawn because I've modified it and unless you draw in a very specific graphics mode, um, using XOR, it's not possible and that would look weird anyway.

08:22 So, what you have to do is before you start drawing on there, take a backup effectively, copy it into another location what was previously there or the whole image or just the bit that you've drawn over, update that so that you can then copy back what was previously there, um, which is why we're talking about memory earlier because that copy is going to take up copy, um, space.

08:47 And so, while it is easier to work out what you want to undo, you actually have to do more work in your program because before you can start drawing on the screen, you have to save that screen somewhere, either in memory or onto disk and so on, so that you can go back onto it. So, actually, as you think about undo, it becomes an absolute pain, um, to implement because you have to think about all sorts of different things and think about how you structure your program and so on to make that work.

09:18 >> How much of this is the programmer who's doing the program doing and how much is the OS doing, the operating system? >> Um, so, that's a really good question. There is often support for undo in some of the frameworks. We'll talk about how they might offer multi-level undo in a second and how that's implemented. But, the operating system doesn't know what you're trying to write.

09:35 Uh, it's sending you key presses. A was pressed, A was released, B was pressed, B was released, and so on to your to your program. It doesn't know you're a word processor or text editor. Um, what it might provide is the ability to group them and then replay them. But, you still need to tell it what you want to group and replay and so on. If you're writing something like a graphics editor like this, you need to copy your program needs to copy this somewhere else so that you can restore it at other point and so on.

10:08 Now, you talked about what sort of support might be offered. Um, and what often is supported, and if you look at something like AppKit on the Mac or on iOS or the equivalent on iOS in UI Kit, um, they do provide support for undo. And what they really are supporting is doing multi-level undo. So, as we saw when we click undo multiple times, we can go back further into the document.

10:31 Now, how do you think we might implement that? Thinking about all the computer science stuff you've covered on computer file. >> I'm thinking linked list is going to be coming up somewhere. >> Close. Yeah, you might need to use that. Probably about a data structure would be to use a stack. What do you think? A stack is last in, first out. And that's exactly what we want to do when we click undo.

10:48 When we want to click undo, >> you pop that bit >> we pop that bit off the stack. That tells us what we want to undo. We can do that. We pop the next one off the stack and so on. So, what we'd probably end up doing either in the frameworks for the GUI or um, in our program itself is whenever we make an edit and we work out what that edit is, as we've talked about, that's very much dependent on what the software is, but you can work it out.

11:13 We'd probably encapsulate it in some sort of object. Let's go to the text editor. Let's say, add the cat. That's what we've done in there. So, we do that. We pop that onto the stack. Um, because then if we wanted to undo it, as we said, we can just pop that off the stack. Um, look at it and say, "Well, we just added the cat." So, we can remove those characters.

11:35 We'd also keep track of um probably the location. Hopefully you can read what I'm writing, but you can see it. We store the location of where it was, and so we can undo that. If it's a graphics thing like we saw earlier, if we're doing something with the graphics, then we would store the previous bit of the image or what we've changed and so on. Probably we can pop that in so we can then do that and undo it by replaying it in the opposite direction.

12:03 If we then added some more text, of course, we just add another object on top, and that would be add sat on or sat one. In which case then we might say, "Well, we'll delete the E." So, we would have another object on here, um which would be delete and then E, and then again all these would store the location. Now, as we said, you would need to program your program to say, "Well, actually this is where I began editing from.

12:26 This is where all these came together one after the other." And you might, as Word and the text editor we looked at do, just decide to do it based on well, we've done a deletion, we've changed what we're doing is doing that. Personally, if I was implementing it, I would probably do something different. I would say, "Well, actually if I'm undoing something, this probably been a point where I've paused, where writing or done something."

12:50 And so, I'd probably have a timer that was timing every time I press the key, you'd set the timer off, and then you'd reset it. Well, if there's any fit ran for a certain amount of time, let's say a second, then I would stop that as a point because actually if I'm typing fast, I probably don't want to undo all of that. Um, but if I've paused and thought and then typed some more and clicked undo, I probably actually just want to go back to that point.

13:12 And so, actually you can implement things in different ways to get different experiences for the user and make life more difficult for you as a programmer, which is probably why they don't do it um in things like Word. Now, actually if I was implementing this, we could just use a stack, but actually I'd probably use two stacks. We'd have the undo stack.

13:33 >> Yeah, you need a redo stack as well. >> And then you could have a redo stack um here, so that when we delete this, we can then push it onto when we undo the delete to be more accurate, we can then push it onto the redo stack, so that we can then replay it in the opposite direction, i.e. do the same action again. So, we're moving things from one stack to the other.

13:52 Now, that would work, but there would be a problem with it, and so you probably wouldn't necessarily want to implement it directly like that, because particularly if you're implementing something like Photoshop or a bitmap editor, because the problem would be each of these things will be storing chunks of the image that you wanted to undo back to, and actually in the case of an image editor, the redo wouldn't just be moving it to the other stack, you'd actually have to replace the bit of image that was stored there, so

14:22 that you could go back to what you've just drawn. >> In the In the example you've just done with the with the house there, that I suppose that that that window, for instance, could be stored as a kind of data rather than the actual bitmap. >> Well, yeah, I mean, almost so you could store the mouse positions again, but that it could end up bigger than the depending on how cuz obviously people are moving around.

14:42 Or, you'd probably work out and crop and then you store parts of the bitmap and stick them where you they go back in, but again, you'd need to store all that information, gather it up into an object, and then push it onto the stack, but if you think about how big images get in Photoshop, I mean, and remember that bitmap editors are dealing with the uncompressed image, they're not dealing with a JPEG, which may be a few hundred K, they're dealing with the uncompressed image, which may be a few hundred megabytes, um

15:10 potentially even gigabytes if you're working in pre-press in a publishing house. [snorts] Everything you store to be able to undo is going to take up more memory, um and then everything that you level you have is taking your memory. So, actually you're probably going to need something a bit more The works in the same way as a stack, but also has a limit on how much data it stored, and so knows what's stored in it so that it can go away and say, "Well, actually we're running out of memory.

15:39 Let's get rid of those really old things from 3 hours ago where he just put a dot on the screen, um, and so on. And then get rid of them so they still got the more recent things, which is what he's likely to want to undo, um, and not 4 GB worth of history or 16 GB worth of history that he's never likely to go back to. Now, the other thing that can help, going back to the text editor and the example we looked at last year, was how you actually store the data.

16:05 We looked last year at how a gap buffer worked, and with a gap buffer you would probably need to actually keep track of things in separate objects. But, there are other ways of storing data in a text editor, um, which make undo almost come for free. And in a future video we'll look at the piece table, which is what things like Microsoft Word, Visual Studio use to actually store the data, uh, which is a more more interesting data structure that enables you to sort of get undo effectively for free.

16:44 If we decided we wanted to add some text here, or let's say we wanted to, yeah, add some text here, then what we'd do is we come to this point, we'd shuffle all this back up um, before the gap. Where was it I was going to say it was going to have to be at that point, wasn't it? That it.