[Script Info]
Title: 
[Events]
Format: Layer, Start, End, Style, Name, MarginL, MarginR, MarginV, Effect, Text
Dialogue: 0,0:00:00.00,0:00:02.00,Default,,0000,0000,0000,,
Dialogue: 0,0:00:02.00,0:00:10.00,Default,,0000,0000,0000,,
Dialogue: 0,0:00:10.00,0:00:13.00,Default,,0000,0000,0000,,This presentation is delivered by the Stanford Center for Professional
Dialogue: 0,0:00:13.00,0:00:21.00,Default,,0000,0000,0000,,Development.
Dialogue: 0,0:00:21.00,0:00:23.00,Default,,0000,0000,0000,,Let us
Dialogue: 0,0:00:23.00,0:00:25.00,Default,,0000,0000,0000,,refresh about where we were at the end of Wednesday.
Dialogue: 0,0:00:25.00,0:00:29.00,Default,,0000,0000,0000,,As we had talked about the vector form of the buffer, so the editor buffer that's
Dialogue: 0,0:00:29.00,0:00:31.00,Default,,0000,0000,0000,,backing the
Dialogue: 0,0:00:31.00,0:00:34.00,Default,,0000,0000,0000,,word processing client,
Dialogue: 0,0:00:34.00,0:00:37.00,Default,,0000,0000,0000,,and the two stack version, where we're shuffling stuff, often on the before
Dialogue: 0,0:00:37.00,0:00:40.00,Default,,0000,0000,0000,,and after stacks to get things done, right?
Dialogue: 0,0:00:40.00,0:00:43.00,Default,,0000,0000,0000,,And when we were looking at the main six operations, we're looking at the four
Dialogue: 0,0:00:43.00,0:00:47.00,Default,,0000,0000,0000,,cursor movements and the two editing operations, right, that we had traded off.
Dialogue: 0,0:00:47.00,0:00:49.00,Default,,0000,0000,0000,,Where editing had been slow in the vector,
Dialogue: 0,0:00:49.00,0:00:52.00,Default,,0000,0000,0000,,to where editing was now fast, but then these long distance movements were slow,
Dialogue: 0,0:00:52.00,0:00:54.00,Default,,0000,0000,0000,,because of the shuffling.
Dialogue: 0,0:00:54.00,0:00:57.00,Default,,0000,0000,0000,,And then there was a little discussion at the very end about how this probably
Dialogue: 0,0:00:57.00,0:01:00.00,Default,,0000,0000,0000,,increases our space requirements, because we're now keeping two stacks that are
Dialogue: 0,0:01:00.00,0:01:02.00,Default,,0000,0000,0000,,each capable of holding
Dialogue: 0,0:01:02.00,0:01:04.00,Default,,0000,0000,0000,,the entire contents
Dialogue: 0,0:01:04.00,0:01:06.00,Default,,0000,0000,0000,,as opposed to one vector here
Dialogue: 0,0:01:06.00,0:01:09.00,Default,,0000,0000,0000,,with its slop.
Dialogue: 0,0:01:09.00,0:01:10.00,Default,,0000,0000,0000,,So that was where we were at.
Dialogue: 0,0:01:10.00,0:01:13.00,Default,,0000,0000,0000,,We are still in kind of the pursuit of this Holy Grail of could we
Dialogue: 0,0:01:13.00,0:01:16.00,Default,,0000,0000,0000,,get it to where everything is fast. Is it always a matter of tradeoffs or could we just
Dialogue: 0,0:01:16.00,0:01:19.00,Default,,0000,0000,0000,,invest some more smarts and more
Dialogue: 0,0:01:19.00,0:01:20.00,Default,,0000,0000,0000,,cleverness
Dialogue: 0,0:01:20.00,0:01:24.00,Default,,0000,0000,0000,,and hard work and squeeze it down to where we could get everything to perform
Dialogue: 0,0:01:24.00,0:01:26.00,Default,,0000,0000,0000,,efficiently? So typically when computer scientists say they want something to perform
Dialogue: 0,0:01:26.00,0:01:28.00,Default,,0000,0000,0000,,efficiently, they're hoping for log
Dialogue: 0,0:01:28.00,0:01:32.00,Default,,0000,0000,0000,,in time or faster. Constant time is the best. Log in grows so slowly that in fact,
Dialogue: 0,0:01:32.00,0:01:34.00,Default,,0000,0000,0000,,logarithm time is effectively constant
Dialogue: 0,0:01:34.00,0:01:40.00,Default,,0000,0000,0000,,for all reasonable values of N up to millions and billions.
Dialogue: 0,0:01:40.00,0:01:43.00,Default,,0000,0000,0000,,And so typically anything that is linear or higher is often a weak spot that you are
Dialogue: 0,0:01:43.00,0:01:47.00,Default,,0000,0000,0000,,trying to look at, and certainly things that are quadratic or exponential
Dialogue: 0,0:01:47.00,0:01:51.00,Default,,0000,0000,0000,,are definite opportunities for improvement.
Dialogue: 0,0:01:51.00,0:01:53.00,Default,,0000,0000,0000,,So let's look at this idea of the link list,
Dialogue: 0,0:01:53.00,0:01:55.00,Default,,0000,0000,0000,,so that both
Dialogue: 0,0:01:55.00,0:01:56.00,Default,,0000,0000,0000,,the
Dialogue: 0,0:01:56.00,0:01:58.00,Default,,0000,0000,0000,,vector and the stack
Dialogue: 0,0:01:58.00,0:02:03.00,Default,,0000,0000,0000,,- we're relying on this idea that continuous memory is the
Dialogue: 0,0:02:03.00,0:02:06.00,Default,,0000,0000,0000,,weak link that was causing some problems. In the vector, that shuffling to
Dialogue: 0,0:02:06.00,0:02:08.00,Default,,0000,0000,0000,,move things up and down,
Dialogue: 0,0:02:08.00,0:02:12.00,Default,,0000,0000,0000,,or in the case of the stack version, one side to the other
Dialogue: 0,0:02:12.00,0:02:15.00,Default,,0000,0000,0000,,was part of what we were working up against.
Dialogue: 0,0:02:15.00,0:02:18.00,Default,,0000,0000,0000,,And the link list promises to give us this opportunity to have these each
Dialogue: 0,0:02:18.00,0:02:21.00,Default,,0000,0000,0000,,individual character being managed separately,
Dialogue: 0,0:02:21.00,0:02:26.00,Default,,0000,0000,0000,,and flexibility might help resolve some of our problems here.
Dialogue: 0,0:02:26.00,0:02:30.00,Default,,0000,0000,0000,,SO what we're going to look at is the idea of implementing the buffer using a link
Dialogue: 0,0:02:30.00,0:02:32.00,Default,,0000,0000,0000,,list. So if I have
Dialogue: 0,0:02:32.00,0:02:34.00,Default,,0000,0000,0000,,characters A, B, C, D, E,
Dialogue: 0,0:02:34.00,0:02:37.00,Default,,0000,0000,0000,,I could have a link list here where I'm pointing to the head cell, which is A,
Dialogue: 0,0:02:37.00,0:02:40.00,Default,,0000,0000,0000,,which points to B, and C, and D, and E, and down to the null.
Dialogue: 0,0:02:40.00,0:02:43.00,Default,,0000,0000,0000,,SO what I'm modeling it as in the private data section will be a
Dialogue: 0,0:02:43.00,0:02:44.00,Default,,0000,0000,0000,,little
Dialogue: 0,0:02:44.00,0:02:47.00,Default,,0000,0000,0000,,link list node with a character in there, a pointer to the next one.
Dialogue: 0,0:02:47.00,0:02:52.00,Default,,0000,0000,0000,,And then I'm going to keep two pointers, one to the front-most cell, and then that's going to
Dialogue: 0,0:02:52.00,0:02:55.00,Default,,0000,0000,0000,,model where the cursor is within the buffer.
Dialogue: 0,0:02:55.00,0:02:59.00,Default,,0000,0000,0000,,So rather than doing this like an index, an index was handy in the case of vector where we
Dialogue: 0,0:02:59.00,0:03:00.00,Default,,0000,0000,0000,,had direct access, right?
Dialogue: 0,0:03:00.00,0:03:02.00,Default,,0000,0000,0000,,Given the way the link list works,
Dialogue: 0,0:03:02.00,0:03:05.00,Default,,0000,0000,0000,,knowing that it's at the fifth cell, the fourth cell isn't really very helpful. It would be more
Dialogue: 0,0:03:05.00,0:03:09.00,Default,,0000,0000,0000,,helpful to have the pointer kind of directly in the midst of things to give us direct
Dialogue: 0,0:03:09.00,0:03:12.00,Default,,0000,0000,0000,,access to where the cursor is.
Dialogue: 0,0:03:12.00,0:03:14.00,Default,,0000,0000,0000,,But let's think a little bit about that cursor,
Dialogue: 0,0:03:14.00,0:03:17.00,Default,,0000,0000,0000,,because there's an important decision to be made early about helping to
Dialogue: 0,0:03:17.00,0:03:20.00,Default,,0000,0000,0000,,facilitate the later work we have to do.
Dialogue: 0,0:03:20.00,0:03:24.00,Default,,0000,0000,0000,,I have the contents A, B, C, D, E,
Dialogue: 0,0:03:24.00,0:03:28.00,Default,,0000,0000,0000,,so the cursor is actually between two characters.
Dialogue: 0,0:03:28.00,0:03:31.00,Default,,0000,0000,0000,,If the cursor right now is situated
Dialogue: 0,0:03:31.00,0:03:32.00,Default,,0000,0000,0000,,after the A and before the B,
Dialogue: 0,0:03:32.00,0:03:33.00,Default,,0000,0000,0000,,what I'm
Dialogue: 0,0:03:33.00,0:03:36.00,Default,,0000,0000,0000,,modeling is A cursor B,
Dialogue: 0,0:03:36.00,0:03:38.00,Default,,0000,0000,0000,,C, D,
Dialogue: 0,0:03:38.00,0:03:39.00,Default,,0000,0000,0000,,then
Dialogue: 0,0:03:39.00,0:03:42.00,Default,,0000,0000,0000,,it seems like the obvious two choices for where the cursor might point is to
Dialogue: 0,0:03:42.00,0:03:45.00,Default,,0000,0000,0000,,A or to B. And I
Dialogue: 0,0:03:45.00,0:03:50.00,Default,,0000,0000,0000,,had said in the case of the vector that if it were index zero or index one
Dialogue: 0,0:03:50.00,0:03:51.00,Default,,0000,0000,0000,,that
Dialogue: 0,0:03:51.00,0:03:53.00,Default,,0000,0000,0000,,there wasn't a really strong preference for one over the other.
Dialogue: 0,0:03:53.00,0:03:56.00,Default,,0000,0000,0000,,There is going to be a really good reason to pick one for the link list
Dialogue: 0,0:03:56.00,0:03:59.00,Default,,0000,0000,0000,,over the other. Would you rather point to the A
Dialogue: 0,0:03:59.00,0:04:11.00,Default,,0000,0000,0000,,for where the cursor is or would you rather point to the B? [Inaudible]
Dialogue: 0,0:04:11.00,0:04:14.00,Default,,0000,0000,0000,,Exactly, so the idea is that when the cursor position is there, the next edit
Dialogue: 0,0:04:14.00,0:04:18.00,Default,,0000,0000,0000,,actually goes in between the A and the B. So if I insert the character
Dialogue: 0,0:04:18.00,0:04:21.00,Default,,0000,0000,0000,,Z, it really does go right here.
Dialogue: 0,0:04:21.00,0:04:24.00,Default,,0000,0000,0000,,And if I am going to, if effect, wire that in and splice it in then list,
Dialogue: 0,0:04:24.00,0:04:29.00,Default,,0000,0000,0000,,if I'm pointing to B then I'm kind of hosed, because I'm already one past where I need to be able slice in. Because I need to
Dialogue: 0,0:04:29.00,0:04:33.00,Default,,0000,0000,0000,,know what was behind it to bring it in. So I'm pointing to the character behind the
Dialogue: 0,0:04:33.00,0:04:34.00,Default,,0000,0000,0000,,cursor
Dialogue: 0,0:04:34.00,0:04:36.00,Default,,0000,0000,0000,,gives you access to
Dialogue: 0,0:04:36.00,0:04:39.00,Default,,0000,0000,0000,,wiring this down to here and this into there, and then updating the cursor to
Dialogue: 0,0:04:39.00,0:04:40.00,Default,,0000,0000,0000,,point to the Z
Dialogue: 0,0:04:40.00,0:04:44.00,Default,,0000,0000,0000,,without having to do any of the difficult backward looking backward
Dialogue: 0,0:04:44.00,0:04:45.00,Default,,0000,0000,0000,,traversal.
Dialogue: 0,0:04:45.00,0:04:48.00,Default,,0000,0000,0000,,So that strongly suggests what it is, it's going to point to
Dialogue: 0,0:04:48.00,0:04:52.00,Default,,0000,0000,0000,,A when it's between A and B; B when it's between B and C; and so on.
Dialogue: 0,0:04:52.00,0:04:56.00,Default,,0000,0000,0000,,There is another little point here, which is there are actually five letters
Dialogue: 0,0:04:56.00,0:04:59.00,Default,,0000,0000,0000,,in the cursor, but there are six cursor positions. It could be at the very
Dialogue: 0,0:04:59.00,0:05:00.00,Default,,0000,0000,0000,,beginning,
Dialogue: 0,0:05:00.00,0:05:03.00,Default,,0000,0000,0000,,in between all these, or at the very end.
Dialogue: 0,0:05:03.00,0:05:07.00,Default,,0000,0000,0000,,And the way we've chosen it right now, I can identify all of the five
Dialogue: 0,0:05:07.00,0:05:08.00,Default,,0000,0000,0000,,positions
Dialogue: 0,0:05:08.00,0:05:11.00,Default,,0000,0000,0000,,that have at least one character to the left, so being -
Dialogue: 0,0:05:11.00,0:05:12.00,Default,,0000,0000,0000,,pointing to the A means it's
Dialogue: 0,0:05:12.00,0:05:15.00,Default,,0000,0000,0000,,after A; pointing to the B it's after B; and so on, all the way down to the E.
Dialogue: 0,0:05:15.00,0:05:18.00,Default,,0000,0000,0000,,But I don't have a cursor position for
Dialogue: 0,0:05:18.00,0:05:23.00,Default,,0000,0000,0000,,representing when the cursor is at the very beginning of the buffer.
Dialogue: 0,0:05:23.00,0:05:25.00,Default,,0000,0000,0000,,So
Dialogue: 0,0:05:25.00,0:05:28.00,Default,,0000,0000,0000,,one strategy I could use, right, is to say I'll just use the special cursor
Dialogue: 0,0:05:28.00,0:05:29.00,Default,,0000,0000,0000,,position of null. But
Dialogue: 0,0:05:29.00,0:05:32.00,Default,,0000,0000,0000,,I need one more pointer value to hold onto,
Dialogue: 0,0:05:32.00,0:05:36.00,Default,,0000,0000,0000,,and I could make a special case out of this because there's null. Once I've done that though,
Dialogue: 0,0:05:36.00,0:05:40.00,Default,,0000,0000,0000,,I've actually committed myself to this thing that's going to require all of my code to be managing a
Dialogue: 0,0:05:40.00,0:05:41.00,Default,,0000,0000,0000,,special case of,
Dialogue: 0,0:05:41.00,0:05:43.00,Default,,0000,0000,0000,,well when the cursor's null do something a little different than when
Dialogue: 0,0:05:43.00,0:05:46.00,Default,,0000,0000,0000,,the cursor is pointing to some cell. I'm going to
Dialogue: 0,0:05:46.00,0:05:50.00,Default,,0000,0000,0000,,show you a way that we can kind of
Dialogue: 0,0:05:50.00,0:05:54.00,Default,,0000,0000,0000,,avoid the need for making a special case out of it,
Dialogue: 0,0:05:54.00,0:05:55.00,Default,,0000,0000,0000,,by
Dialogue: 0,0:05:55.00,0:05:58.00,Default,,0000,0000,0000,,wasting a little memory and reorganizing our list
Dialogue: 0,0:05:58.00,0:06:01.00,Default,,0000,0000,0000,,to allow for there to be a sixth cell,
Dialogue: 0,0:06:01.00,0:06:04.00,Default,,0000,0000,0000,,and extra cell that we call the dummy cell.
Dialogue: 0,0:06:04.00,0:06:07.00,Default,,0000,0000,0000,,So in this case that cell would go at the very front.
Dialogue: 0,0:06:07.00,0:06:10.00,Default,,0000,0000,0000,,It would have no character, just let the character field be unstatused. It's
Dialogue: 0,0:06:10.00,0:06:13.00,Default,,0000,0000,0000,,not really a character. What it is, is just a placeholder.
Dialogue: 0,0:06:13.00,0:06:16.00,Default,,0000,0000,0000,,And when I created the buffer to begin with, even when it's empty, it's always going to have
Dialogue: 0,0:06:16.00,0:06:20.00,Default,,0000,0000,0000,,that cell. I'm going to create that cell in advance, I'm going to have it sitting ready and waiting, and that cell
Dialogue: 0,0:06:20.00,0:06:24.00,Default,,0000,0000,0000,,never gets deleted or moved or changed. In fact, the list always, the head
Dialogue: 0,0:06:24.00,0:06:28.00,Default,,0000,0000,0000,,of this will always point to the same cell from the beginning of this object's lifetime
Dialogue: 0,0:06:28.00,0:06:32.00,Default,,0000,0000,0000,,to the end. So it will never change this at all, and the cells that follow are
Dialogue: 0,0:06:32.00,0:06:35.00,Default,,0000,0000,0000,,the ones that are going to be changing and growing and rearranging in
Dialogue: 0,0:06:35.00,0:06:38.00,Default,,0000,0000,0000,,response to editing commands.
Dialogue: 0,0:06:38.00,0:06:40.00,Default,,0000,0000,0000,,What this is going to buy us is a couple of things. First off, it's going to make it
Dialogue: 0,0:06:40.00,0:06:42.00,Default,,0000,0000,0000,,so there is a sixth cursor position.
Dialogue: 0,0:06:42.00,0:06:45.00,Default,,0000,0000,0000,,So now when the cursor is at the very beginning,
Dialogue: 0,0:06:45.00,0:06:47.00,Default,,0000,0000,0000,,we can set the cursor to point to this dummy cell.
Dialogue: 0,0:06:47.00,0:06:48.00,Default,,0000,0000,0000,,Okay
Dialogue: 0,0:06:48.00,0:06:51.00,Default,,0000,0000,0000,,that's one thing that we solve by doing that.
Dialogue: 0,0:06:51.00,0:06:55.00,Default,,0000,0000,0000,,Another thing that we've solved is actually we have made all the other
Dialogue: 0,0:06:55.00,0:06:57.00,Default,,0000,0000,0000,,cells on the list, the ones that are being edited and manipulated.
Dialogue: 0,0:06:57.00,0:07:00.00,Default,,0000,0000,0000,,We've made them all totally symmetric.
Dialogue: 0,0:07:00.00,0:07:02.00,Default,,0000,0000,0000,,Previously there was always going to be a little bit of a special case about, well if you're
Dialogue: 0,0:07:02.00,0:07:06.00,Default,,0000,0000,0000,,the front of the list, we're seeing that sometimes we're doing inserts on the
Dialogue: 0,0:07:06.00,0:07:08.00,Default,,0000,0000,0000,,stack in queue link list. That
Dialogue: 0,0:07:08.00,0:07:12.00,Default,,0000,0000,0000,,inserting later in the list involves kind of wiring in two pointers; one to command and one
Dialogue: 0,0:07:12.00,0:07:13.00,Default,,0000,0000,0000,,to go out.
Dialogue: 0,0:07:13.00,0:07:16.00,Default,,0000,0000,0000,,But there was a special case that oh, if you're the very first cell of the list, then
Dialogue: 0,0:07:16.00,0:07:19.00,Default,,0000,0000,0000,,your outpointer is the same, but your incoming pointer is resetting the head.
Dialogue: 0,0:07:19.00,0:07:22.00,Default,,0000,0000,0000,,That piece has actually gone away now,
Dialogue: 0,0:07:22.00,0:07:26.00,Default,,0000,0000,0000,,that now every cell in there always has a predecessor. It always has a previous,
Dialogue: 0,0:07:26.00,0:07:29.00,Default,,0000,0000,0000,,right? Something behind it so that actually they will always be
Dialogue: 0,0:07:29.00,0:07:31.00,Default,,0000,0000,0000,,pulling the pointer in and pulling the pointer out
Dialogue: 0,0:07:31.00,0:07:34.00,Default,,0000,0000,0000,,for every cell with character data that's being modified.
Dialogue: 0,0:07:34.00,0:07:37.00,Default,,0000,0000,0000,,And that means some of that extra little handing of oh, if you're the
Dialogue: 0,0:07:37.00,0:07:39.00,Default,,0000,0000,0000,,very first cell,
Dialogue: 0,0:07:39.00,0:07:40.00,Default,,0000,0000,0000,,have gone away.
Dialogue: 0,0:07:40.00,0:07:44.00,Default,,0000,0000,0000,,The very first cell is always this kind of dummy cell and doesn't require us to go
Dialogue: 0,0:07:44.00,0:07:46.00,Default,,0000,0000,0000,,out of our way to do anything special for it.
Dialogue: 0,0:07:46.00,0:07:49.00,Default,,0000,0000,0000,,So this is going to solve a bunch of problems for us, and it's kind of a neat technique. This thing
Dialogue: 0,0:07:49.00,0:07:51.00,Default,,0000,0000,0000,,is used actually
Dialogue: 0,0:07:51.00,0:07:52.00,Default,,0000,0000,0000,,fairly commonly
Dialogue: 0,0:07:52.00,0:07:57.00,Default,,0000,0000,0000,,in situations just managing a link list just to buy yourself some symmetry in the
Dialogue: 0,0:07:57.00,0:08:02.00,Default,,0000,0000,0000,,remaining cells.
Dialogue: 0,0:08:02.00,0:08:05.00,Default,,0000,0000,0000,,So let me look at some code with you, and I'm going to actually draw some pictures as I
Dialogue: 0,0:08:05.00,0:08:06.00,Default,,0000,0000,0000,,go. I'm
Dialogue: 0,0:08:06.00,0:08:10.00,Default,,0000,0000,0000,,not going to write this code in real time, because I think it's actually more important to
Dialogue: 0,0:08:10.00,0:08:11.00,Default,,0000,0000,0000,,see it
Dialogue: 0,0:08:11.00,0:08:15.00,Default,,0000,0000,0000,,acting on things than it is to see me typing out the characters.
Dialogue: 0,0:08:15.00,0:08:18.00,Default,,0000,0000,0000,,But the mechanism, right, in the case of the buffer here
Dialogue: 0,0:08:18.00,0:08:21.00,Default,,0000,0000,0000,,is it's going to have a head point,
Dialogue: 0,0:08:21.00,0:08:23.00,Default,,0000,0000,0000,,which points to the front most cell; and a
Dialogue: 0,0:08:23.00,0:08:24.00,Default,,0000,0000,0000,,cursor,
Dialogue: 0,0:08:24.00,0:08:28.00,Default,,0000,0000,0000,,which points to the character that proceeds the cursor. So if right now the
Dialogue: 0,0:08:28.00,0:08:31.00,Default,,0000,0000,0000,,contents of the buffer
Dialogue: 0,0:08:31.00,0:08:34.00,Default,,0000,0000,0000,,are
Dialogue: 0,0:08:34.00,0:08:37.00,Default,,0000,0000,0000,,the contents A, D, C.
Dialogue: 0,0:08:37.00,0:08:39.00,Default,,0000,0000,0000,,And let's say that right now
Dialogue: 0,0:08:39.00,0:08:40.00,Default,,0000,0000,0000,,the
Dialogue: 0,0:08:40.00,0:08:42.00,Default,,0000,0000,0000,,cursor is pointing to A.
Dialogue: 0,0:08:42.00,0:08:45.00,Default,,0000,0000,0000,,Actually, I need my
Dialogue: 0,0:08:45.00,0:08:50.00,Default,,0000,0000,0000,,dummy cell. Let me move everybody down one, so you just have dummy
Dialogue: 0,0:08:50.00,0:08:52.00,Default,,0000,0000,0000,,cell and my A and my B.
Dialogue: 0,0:08:52.00,0:08:56.00,Default,,0000,0000,0000,,And so the cursor right now is at the very front of the buffer.
Dialogue: 0,0:08:56.00,0:08:59.00,Default,,0000,0000,0000,,This is kind of what it looks like. It has two characters, the A and the B.
Dialogue: 0,0:08:59.00,0:09:03.00,Default,,0000,0000,0000,,I'm going to trace through the process of inserting a new character
Dialogue: 0,0:09:03.00,0:09:04.00,Default,,0000,0000,0000,,into the buffer. It
Dialogue: 0,0:09:04.00,0:09:07.00,Default,,0000,0000,0000,,is that my local variable CP
Dialogue: 0,0:09:07.00,0:09:11.00,Default,,0000,0000,0000,,is going to point to a new cell allocated out in the heap.
Dialogue: 0,0:09:11.00,0:09:15.00,Default,,0000,0000,0000,,Let's say the character I'm going to insert is the Z, so I'll
Dialogue: 0,0:09:15.00,0:09:16.00,Default,,0000,0000,0000,,assign
Dialogue: 0,0:09:16.00,0:09:18.00,Default,,0000,0000,0000,,CH to the character, the slot right there.
Dialogue: 0,0:09:18.00,0:09:20.00,Default,,0000,0000,0000,,And then the next for this
Dialogue: 0,0:09:20.00,0:09:24.00,Default,,0000,0000,0000,,gets to - what the cursor is - kind of following the cursor. So the
Dialogue: 0,0:09:24.00,0:09:26.00,Default,,0000,0000,0000,,cursor is pointing to the cell before it,
Dialogue: 0,0:09:26.00,0:09:29.00,Default,,0000,0000,0000,,and the next field of that cell tells us what follows it;
Dialogue: 0,0:09:29.00,0:09:31.00,Default,,0000,0000,0000,,so if I trace my cursor's
Dialogue: 0,0:09:31.00,0:09:33.00,Default,,0000,0000,0000,,next field, it points to A,
Dialogue: 0,0:09:33.00,0:09:35.00,Default,,0000,0000,0000,,and so I'm going to go ahead and
Dialogue: 0,0:09:35.00,0:09:41.00,Default,,0000,0000,0000,,set up this new cell's next field to also point to A.
Dialogue: 0,0:09:41.00,0:09:44.00,Default,,0000,0000,0000,,So now I've got two different ways to get to the A cell, tracing off the dummy cell or
Dialogue: 0,0:09:44.00,0:09:46.00,Default,,0000,0000,0000,,tracing off this new cell.
Dialogue: 0,0:09:46.00,0:09:48.00,Default,,0000,0000,0000,,And then I
Dialogue: 0,0:09:48.00,0:09:51.00,Default,,0000,0000,0000,,update the cursor's next field to point to CP.
Dialogue: 0,0:09:51.00,0:09:55.00,Default,,0000,0000,0000,,So I just copied right there that CP's next field was pointing to A. I copied it down here
Dialogue: 0,0:09:55.00,0:09:57.00,Default,,0000,0000,0000,,to kind of do the splice out.
Dialogue: 0,0:09:57.00,0:10:02.00,Default,,0000,0000,0000,,Now I'm going to do the splice in,
Dialogue: 0,0:10:02.00,0:10:05.00,Default,,0000,0000,0000,,causing it to no longer point to A,
Dialogue: 0,0:10:05.00,0:10:06.00,Default,,0000,0000,0000,,but instead to
Dialogue: 0,0:10:06.00,0:10:08.00,Default,,0000,0000,0000,,point to my new cell down here, CP.
Dialogue: 0,0:10:08.00,0:10:10.00,Default,,0000,0000,0000,,And then I update the cursor
Dialogue: 0,0:10:10.00,0:10:13.00,Default,,0000,0000,0000,,to point to this new cell. That just means that subsequent inserts, like the
Dialogue: 0,0:10:13.00,0:10:18.00,Default,,0000,0000,0000,,C is kind of behind the cursor after I've made this
Dialogue: 0,0:10:18.00,0:10:21.00,Default,,0000,0000,0000,,
Dialogue: 0,0:10:21.00,0:10:23.00,Default,,0000,0000,0000,,edit.
Dialogue: 0,0:10:23.00,0:10:25.00,Default,,0000,0000,0000,,That goes away when that one ends,
Dialogue: 0,0:10:25.00,0:10:28.00,Default,,0000,0000,0000,,and so now the new structure that I have here is
Dialogue: 0,0:10:28.00,0:10:31.00,Default,,0000,0000,0000,,head still points to the dummy cell that never changes.
Dialogue: 0,0:10:31.00,0:10:33.00,Default,,0000,0000,0000,,Dummy cell now points to Z,
Dialogue: 0,0:10:33.00,0:10:36.00,Default,,0000,0000,0000,,Z points to A, Z points to B,
Dialogue: 0,0:10:36.00,0:10:41.00,Default,,0000,0000,0000,,and then the cursor in this case is between the Z and the A,
Dialogue: 0,0:10:41.00,0:10:44.00,Default,,0000,0000,0000,,by virtue of the fact that the cursor is pointing to Z.
Dialogue: 0,0:10:44.00,0:10:50.00,Default,,0000,0000,0000,,A subsequent one would kind of do the same thing. If I typed out ZY
Dialogue: 0,0:10:50.00,0:10:51.00,Default,,0000,0000,0000,,after I did this. We'd
Dialogue: 0,0:10:51.00,0:10:55.00,Default,,0000,0000,0000,,make a new cell over here. It would get what
Dialogue: 0,0:10:55.00,0:10:58.00,Default,,0000,0000,0000,,was currently coming out of the cursor's field. The next field, right, we would
Dialogue: 0,0:10:58.00,0:11:02.00,Default,,0000,0000,0000,,update cursor's next field to point
Dialogue: 0,0:11:02.00,0:11:05.00,Default,,0000,0000,0000,,to this new one. And then we would update cursor
Dialogue: 0,0:11:05.00,0:11:08.00,Default,,0000,0000,0000,,to point to this guy. And
Dialogue: 0,0:11:08.00,0:11:10.00,Default,,0000,0000,0000,,so now following the list, right, dummy cell,
Dialogue: 0,0:11:10.00,0:11:11.00,Default,,0000,0000,0000,,Z,
Dialogue: 0,0:11:11.00,0:11:16.00,Default,,0000,0000,0000,,Y, A, B, cursor pointing to the Y, which is the
Dialogue: 0,0:11:16.00,0:11:20.00,Default,,0000,0000,0000,,character directly to the left of the cursor.
Dialogue: 0,0:11:20.00,0:11:22.00,Default,,0000,0000,0000,,And so inserting in any position now,
Dialogue: 0,0:11:22.00,0:11:25.00,Default,,0000,0000,0000,,front cell, middle cell, end cell,
Dialogue: 0,0:11:25.00,0:11:29.00,Default,,0000,0000,0000,,doesn't require any special case handling. So you don't see any if of things.
Dialogue: 0,0:11:29.00,0:11:33.00,Default,,0000,0000,0000,,And you notice that you'll never see an update to the head directly here.
Dialogue: 0,0:11:33.00,0:11:37.00,Default,,0000,0000,0000,,That the head was set up to point to the dummy cell in the constructor
Dialogue: 0,0:11:37.00,0:11:39.00,Default,,0000,0000,0000,,and never needs any adjusting.
Dialogue: 0,0:11:39.00,0:11:42.00,Default,,0000,0000,0000,,It's only the cells after it that requires
Dialogue: 0,0:11:42.00,0:11:43.00,Default,,0000,0000,0000,,
Dialogue: 0,0:11:43.00,0:11:44.00,Default,,0000,0000,0000,,the new
Dialogue: 0,0:11:44.00,0:11:47.00,Default,,0000,0000,0000,,arrangement of the pointers coming in and
Dialogue: 0,0:11:47.00,0:11:49.00,Default,,0000,0000,0000,,out. When I'm ready to delete a cell,
Dialogue: 0,0:11:49.00,0:11:53.00,Default,,0000,0000,0000,,then the mechanism for delete in the buffer is to delete the thing that follows
Dialogue: 0,0:11:53.00,0:11:55.00,Default,,0000,0000,0000,,the cursor. So if I have Z, Y, A, B,
Dialogue: 0,0:11:55.00,0:11:58.00,Default,,0000,0000,0000,,this is the character that delete is supposed to delete, the one after the
Dialogue: 0,0:11:58.00,0:11:59.00,Default,,0000,0000,0000,,cursor.
Dialogue: 0,0:11:59.00,0:12:00.00,Default,,0000,0000,0000,,And so,
Dialogue: 0,0:12:00.00,0:12:04.00,Default,,0000,0000,0000,,the first thing it looks at is to make sure that we're not already at the end.
Dialogue: 0,0:12:04.00,0:12:07.00,Default,,0000,0000,0000,,In the case of the link list form of this, if the cursor was pointing to
Dialogue: 0,0:12:07.00,0:12:09.00,Default,,0000,0000,0000,,the last most cell,
Dialogue: 0,0:12:09.00,0:12:12.00,Default,,0000,0000,0000,,and then we looked at it's next field and saw that it was null, that would be a clue. Oh, it's
Dialogue: 0,0:12:12.00,0:12:15.00,Default,,0000,0000,0000,,pointing to the very last cell, there's nothing that follows it. So we have a
Dialogue: 0,0:12:15.00,0:12:17.00,Default,,0000,0000,0000,,quick test to make sure that there's something there to delete.
Dialogue: 0,0:12:17.00,0:12:19.00,Default,,0000,0000,0000,,There is something following the cursor, and
Dialogue: 0,0:12:19.00,0:12:24.00,Default,,0000,0000,0000,,in this case since the cursor is pointing to the Y, we're good. It says look at its
Dialogue: 0,0:12:24.00,0:12:25.00,Default,,0000,0000,0000,,next field, it points to A.
Dialogue: 0,0:12:25.00,0:12:27.00,Default,,0000,0000,0000,,It says okay,
Dialogue: 0,0:12:27.00,0:12:29.00,Default,,0000,0000,0000,,call this thing old
Dialogue: 0,0:12:29.00,0:12:30.00,Default,,0000,0000,0000,,and point to that A.
Dialogue: 0,0:12:30.00,0:12:33.00,Default,,0000,0000,0000,,Now do a wire around it.
Dialogue: 0,0:12:33.00,0:12:34.00,Default,,0000,0000,0000,,So take the cursor's
Dialogue: 0,0:12:34.00,0:12:36.00,Default,,0000,0000,0000,,next field, and
Dialogue: 0,0:12:36.00,0:12:39.00,Default,,0000,0000,0000,,so this thing is where I'm targeting my overwrite,
Dialogue: 0,0:12:39.00,0:12:44.00,Default,,0000,0000,0000,,and copy out of the old its next. It's
Dialogue: 0,0:12:44.00,0:12:49.00,Default,,0000,0000,0000,,no longer pointing to the A, but instead it's
Dialogue: 0,0:12:49.00,0:12:50.00,Default,,0000,0000,0000,,pointing to the B.
Dialogue: 0,0:12:50.00,0:12:52.00,Default,,0000,0000,0000,,And deleting the old, which
Dialogue: 0,0:12:52.00,0:12:54.00,Default,,0000,0000,0000,,causes this piece of memory to
Dialogue: 0,0:12:54.00,0:12:56.00,Default,,0000,0000,0000,,be reclaimed,
Dialogue: 0,0:12:56.00,0:13:01.00,Default,,0000,0000,0000,,and now the contents of my buffer have been shifted over to
Dialogue: 0,0:13:01.00,0:13:06.00,Default,,0000,0000,0000,,where it goes Z, Y, and straight to D. The cursor in this case doesn't move. It
Dialogue: 0,0:13:06.00,0:13:07.00,Default,,0000,0000,0000,,actually deleted to the right, and so
Dialogue: 0,0:13:07.00,0:13:11.00,Default,,0000,0000,0000,,whatever was to the left of the cursor just stays in place.
Dialogue: 0,0:13:11.00,0:13:15.00,Default,,0000,0000,0000,,So again, no need to update anything special for the first or the last or any of those
Dialogue: 0,0:13:15.00,0:13:15.00,Default,,0000,0000,0000,,cells,
Dialogue: 0,0:13:15.00,0:13:19.00,Default,,0000,0000,0000,,but the symmetry of all the cells past the dummy kind of buys us some convenience
Dialogue: 0,0:13:19.00,0:13:22.00,Default,,0000,0000,0000,,of handling it. What does a dummy cell look like? The
Dialogue: 0,0:13:22.00,0:13:26.00,Default,,0000,0000,0000,,dummy cell looks like just any other cell. It's actually a cell, T, and what you do is
Dialogue: 0,0:13:26.00,0:13:29.00,Default,,0000,0000,0000,,you just don't assign the Christian field, the character field, because it has nothing in it.
Dialogue: 0,0:13:29.00,0:13:32.00,Default,,0000,0000,0000,,So it actually looks just like all the others, it's just another node in the
Dialogue: 0,0:13:32.00,0:13:33.00,Default,,0000,0000,0000,,chain.
Dialogue: 0,0:13:33.00,0:13:36.00,Default,,0000,0000,0000,,But this one, you know you put there purposefully just as the placeholder.
Dialogue: 0,0:13:36.00,0:13:40.00,Default,,0000,0000,0000,,So it doesn't contain any character data. So if you're ready to print the
Dialogue: 0,0:13:40.00,0:13:42.00,Default,,0000,0000,0000,,contents of the buffer, you have to remember the dummy cell is there,
Dialogue: 0,0:13:42.00,0:13:43.00,Default,,0000,0000,0000,,and just skip over it. You
Dialogue: 0,0:13:43.00,0:13:45.00,Default,,0000,0000,0000,,tend to start your list
Dialogue: 0,0:13:45.00,0:13:49.00,Default,,0000,0000,0000,,at heads next, the first interesting cell to look at, then work
Dialogue: 0,0:13:49.00,0:13:51.00,Default,,0000,0000,0000,,your way down to the end. So it's
Dialogue: 0,0:13:51.00,0:13:54.00,Default,,0000,0000,0000,,just like all the others, but you just know
Dialogue: 0,0:13:54.00,0:14:00.00,Default,,0000,0000,0000,,that the character data here is useless, it's not important. You didn't even write anything in there. When you delete, you just go left? It turns out
Dialogue: 0,0:14:00.00,0:14:02.00,Default,,0000,0000,0000,,the delete in this
Dialogue: 0,0:14:02.00,0:14:04.00,Default,,0000,0000,0000,,case goes forward.
Dialogue: 0,0:14:04.00,0:14:07.00,Default,,0000,0000,0000,,So you can imagine that in some other world it does, but all the ones we
Dialogue: 0,0:14:07.00,0:14:11.00,Default,,0000,0000,0000,,have done so far have always deleted forward. So the delete - for example, the stack case,
Dialogue: 0,0:14:11.00,0:14:13.00,Default,,0000,0000,0000,,grabbed from the after stack
Dialogue: 0,0:14:13.00,0:14:16.00,Default,,0000,0000,0000,,- it's done that way, because it happens to simplify some other
Dialogue: 0,0:14:16.00,0:14:19.00,Default,,0000,0000,0000,,things that you can imagine that delete and reverse. What would it take? Well, you'd have to back
Dialogue: 0,0:14:19.00,0:14:22.00,Default,,0000,0000,0000,,the cursor up. And we're going to find out pretty soon that would make it
Dialogue: 0,0:14:22.00,0:14:24.00,Default,,0000,0000,0000,,challenging for the link list. So partly we've picked a delete that
Dialogue: 0,0:14:24.00,0:14:26.00,Default,,0000,0000,0000,,made certain things work out a
Dialogue: 0,0:14:26.00,0:14:29.00,Default,,0000,0000,0000,,little better for us.
Dialogue: 0,0:14:29.00,0:14:31.00,Default,,0000,0000,0000,,So both of these operations
Dialogue: 0,0:14:31.00,0:14:33.00,Default,,0000,0000,0000,,are O of
Dialogue: 0,0:14:33.00,0:14:33.00,Default,,0000,0000,0000,,1;
Dialogue: 0,0:14:33.00,0:14:37.00,Default,,0000,0000,0000,,this is where the link list really shines, right, on this sort of stuff. Because
Dialogue: 0,0:14:37.00,0:14:41.00,Default,,0000,0000,0000,,if you have access to the point at which you want to make a modification, so if you are already kind of
Dialogue: 0,0:14:41.00,0:14:44.00,Default,,0000,0000,0000,,in the midst of the thing you're trying to rearrange,
Dialogue: 0,0:14:44.00,0:14:47.00,Default,,0000,0000,0000,,it's often to the link list's advantage, because it actually can do these this rewiring
Dialogue: 0,0:14:47.00,0:14:51.00,Default,,0000,0000,0000,,in the local context. And even if there's thousands of characters that
Dialogue: 0,0:14:51.00,0:14:52.00,Default,,0000,0000,0000,,follow the cursor.
Dialogue: 0,0:14:52.00,0:14:55.00,Default,,0000,0000,0000,,It doesn't matter. And there can be thousands of characters preceding the cursor
Dialogue: 0,0:14:55.00,0:14:56.00,Default,,0000,0000,0000,,for that matter, too.
Dialogue: 0,0:14:56.00,0:15:00.00,Default,,0000,0000,0000,,The idea that there's a much larger context that's working and doesn't impact
Dialogue: 0,0:15:00.00,0:15:03.00,Default,,0000,0000,0000,,its performance; it's really just doing this local little rearrangement of the pointers.
Dialogue: 0,0:15:03.00,0:15:05.00,Default,,0000,0000,0000,,And that's a real strength of the link list design
Dialogue: 0,0:15:05.00,0:15:11.00,Default,,0000,0000,0000,,is that flexibility that doesn't rely on everything living in contiguous memory.
Dialogue: 0,0:15:11.00,0:15:15.00,Default,,0000,0000,0000,,So let's talk about the movement options for this guy.
Dialogue: 0,0:15:15.00,0:15:19.00,Default,,0000,0000,0000,,So right now I have the contents
Dialogue: 0,0:15:19.00,0:15:21.00,Default,,0000,0000,0000,,Z, Y with
Dialogue: 0,0:15:21.00,0:15:22.00,Default,,0000,0000,0000,,the cursor
Dialogue: 0,0:15:22.00,0:15:27.00,Default,,0000,0000,0000,,between that, and the B following that. So three characters worth,
Dialogue: 0,0:15:27.00,0:15:29.00,Default,,0000,0000,0000,,
Dialogue: 0,0:15:29.00,0:15:30.00,Default,,0000,0000,0000,,and then
Dialogue: 0,0:15:30.00,0:15:31.00,Default,,0000,0000,0000,,the
Dialogue: 0,0:15:31.00,0:15:33.00,Default,,0000,0000,0000,,initial two operations
Dialogue: 0,0:15:33.00,0:15:36.00,Default,,0000,0000,0000,,are pretty simple. The later two are going to be a little bit messier. So let's look at
Dialogue: 0,0:15:36.00,0:15:37.00,Default,,0000,0000,0000,,the easy ones first.
Dialogue: 0,0:15:37.00,0:15:40.00,Default,,0000,0000,0000,,Moving the cursor to the beginning, so that jump that pulls you back to the very
Dialogue: 0,0:15:40.00,0:15:41.00,Default,,0000,0000,0000,,beginning,
Dialogue: 0,0:15:41.00,0:15:44.00,Default,,0000,0000,0000,,very easy in a link list form. If I want to move the cursor to the beginning, all
Dialogue: 0,0:15:44.00,0:15:47.00,Default,,0000,0000,0000,,I need to do is take that cursor pointer,
Dialogue: 0,0:15:47.00,0:15:49.00,Default,,0000,0000,0000,,and reset it
Dialogue: 0,0:15:49.00,0:15:51.00,Default,,0000,0000,0000,,to the head, which is where the dummy cell is. And so, by
Dialogue: 0,0:15:51.00,0:15:54.00,Default,,0000,0000,0000,,virtue of doing that,
Dialogue: 0,0:15:54.00,0:15:57.00,Default,,0000,0000,0000,,
Dialogue: 0,0:15:57.00,0:15:59.00,Default,,0000,0000,0000,,the character it points to is the one that's to the left,
Dialogue: 0,0:15:59.00,0:16:02.00,Default,,0000,0000,0000,,right of that, and to the left of that the dummy cell is one we're not
Dialogue: 0,0:16:02.00,0:16:05.00,Default,,0000,0000,0000,,counting. In fact, it's like nothingness that's there,
Dialogue: 0,0:16:05.00,0:16:07.00,Default,,0000,0000,0000,,and that means that the first character that follows the cursor is Z, which
Dialogue: 0,0:16:07.00,0:16:11.00,Default,,0000,0000,0000,,is the initial character of the buffer. So that reset, easy to do, we have
Dialogue: 0,0:16:11.00,0:16:13.00,Default,,0000,0000,0000,,easy access to the front of the list,
Dialogue: 0,0:16:13.00,0:16:14.00,Default,,0000,0000,0000,,and so
Dialogue: 0,0:16:14.00,0:16:16.00,Default,,0000,0000,0000,,no
Dialogue: 0,0:16:16.00,0:16:17.00,Default,,0000,0000,0000,,special
Dialogue: 0,0:16:17.00,0:16:18.00,Default,,0000,0000,0000,,crazy code required.
Dialogue: 0,0:16:18.00,0:16:21.00,Default,,0000,0000,0000,,Moving the cursor forward, also an easy thing to do, link
Dialogue: 0,0:16:21.00,0:16:24.00,Default,,0000,0000,0000,,list are designed to make it easy to work your way from the front to
Dialogue: 0,0:16:24.00,0:16:28.00,Default,,0000,0000,0000,,the back. And so moving the cursor forward is advancing that cursor by one step. So
Dialogue: 0,0:16:28.00,0:16:32.00,Default,,0000,0000,0000,,in the array form of this, what was a cursor plus, plus, the
Dialogue: 0,0:16:32.00,0:16:36.00,Default,,0000,0000,0000,,comparable form of that in the link list is cursor equals cursor next.
Dialogue: 0,0:16:36.00,0:16:37.00,Default,,0000,0000,0000,,It has a little
Dialogue: 0,0:16:37.00,0:16:40.00,Default,,0000,0000,0000,,if test there, all of the versions actually have something that is
Dialogue: 0,0:16:40.00,0:16:42.00,Default,,0000,0000,0000,,comparable to this. If you're already at the end, then there's
Dialogue: 0,0:16:42.00,0:16:46.00,Default,,0000,0000,0000,,nothing to be done, so you don't advance the cursor off into space.
Dialogue: 0,0:16:46.00,0:16:47.00,Default,,0000,0000,0000,,You
Dialogue: 0,0:16:47.00,0:16:51.00,Default,,0000,0000,0000,,check to make sure that there is something for it to point to. So in this case,
Dialogue: 0,0:16:51.00,0:16:54.00,Default,,0000,0000,0000,,seeing if the cursor's next field is null, it's not, it points to Z. Then we go
Dialogue: 0,0:16:54.00,0:16:58.00,Default,,0000,0000,0000,,ahead and update the cursor to there,
Dialogue: 0,0:16:58.00,0:17:00.00,Default,,0000,0000,0000,,which has the effect of
Dialogue: 0,0:17:00.00,0:17:03.00,Default,,0000,0000,0000,,changing things to where the Z is the character
Dialogue: 0,0:17:03.00,0:17:07.00,Default,,0000,0000,0000,,to the left of the cursor, and then the YB follows it.
Dialogue: 0,0:17:07.00,0:17:10.00,Default,,0000,0000,0000,,So moving this way, getting back to the beginning, and kind of walking our way down is kind of easy
Dialogue: 0,0:17:10.00,0:17:11.00,Default,,0000,0000,0000,,to do.
Dialogue: 0,0:17:11.00,0:17:15.00,Default,,0000,0000,0000,,Now we start to see where the link list causes us a little bit of grief,
Dialogue: 0,0:17:15.00,0:17:18.00,Default,,0000,0000,0000,,moving the cursor to the end.
Dialogue: 0,0:17:18.00,0:17:21.00,Default,,0000,0000,0000,,So now, starting at the beginning or the middle, or wherever I am,
Dialogue: 0,0:17:21.00,0:17:25.00,Default,,0000,0000,0000,,I want to advance my way to the end. I don't know where the end is.
Dialogue: 0,0:17:25.00,0:17:28.00,Default,,0000,0000,0000,,Link lists in general don't keep track of that,
Dialogue: 0,0:17:28.00,0:17:31.00,Default,,0000,0000,0000,,that in the simple form of the single link list, I'm going to have to work to
Dialogue: 0,0:17:31.00,0:17:34.00,Default,,0000,0000,0000,,find it. So I'm going to take where I am and walk my way down.
Dialogue: 0,0:17:34.00,0:17:37.00,Default,,0000,0000,0000,,And this one actually just makes use of an existing
Dialogue: 0,0:17:37.00,0:17:40.00,Default,,0000,0000,0000,,public number function to move cursor forward. It's like while the cursor next does
Dialogue: 0,0:17:40.00,0:17:44.00,Default,,0000,0000,0000,,not equal null, which is to say while we are not pointing at the very last cell of the link list,
Dialogue: 0,0:17:44.00,0:17:46.00,Default,,0000,0000,0000,,then keep going.
Dialogue: 0,0:17:46.00,0:17:49.00,Default,,0000,0000,0000,,So advance cursor equals cursor.
Dialogue: 0,0:17:49.00,0:17:50.00,Default,,0000,0000,0000,,Some will say,
Dialogue: 0,0:17:50.00,0:17:54.00,Default,,0000,0000,0000,,"Is the cursor's next field null?" No, then set the cursor to be the cursor's
Dialogue: 0,0:17:54.00,0:17:56.00,Default,,0000,0000,0000,,next field.
Dialogue: 0,0:17:56.00,0:17:58.00,Default,,0000,0000,0000,,Is the cursor's next field null?
Dialogue: 0,0:17:58.00,0:17:59.00,Default,,0000,0000,0000,,
Dialogue: 0,0:17:59.00,0:18:02.00,Default,,0000,0000,0000,,No it's not, so advance the cursor to the next field.
Dialogue: 0,0:18:02.00,0:18:04.00,Default,,0000,0000,0000,,Is the cursor's next field null? Yes.
Dialogue: 0,0:18:04.00,0:18:06.00,Default,,0000,0000,0000,,So that would
Dialogue: 0,0:18:06.00,0:18:08.00,Default,,0000,0000,0000,,the last thing in the buffer,
Dialogue: 0,0:18:08.00,0:18:10.00,Default,,0000,0000,0000,,and so if we have
Dialogue: 0,0:18:10.00,0:18:13.00,Default,,0000,0000,0000,,hundreds or thousands or
Dialogue: 0,0:18:13.00,0:18:15.00,Default,,0000,0000,0000,,tens of characters, whichever it is, right,
Dialogue: 0,0:18:15.00,0:18:18.00,Default,,0000,0000,0000,,and depending on how close we already were, it will walk through
Dialogue: 0,0:18:18.00,0:18:21.00,Default,,0000,0000,0000,,everything from where the current editing position was to find the end of the
Dialogue: 0,0:18:21.00,0:18:22.00,Default,,0000,0000,0000,,buffer
Dialogue: 0,0:18:22.00,0:18:25.00,Default,,0000,0000,0000,,one by one, working it's way down.
Dialogue: 0,0:18:25.00,0:18:26.00,Default,,0000,0000,0000,,Even more painful
Dialogue: 0,0:18:26.00,0:18:28.00,Default,,0000,0000,0000,,operation
Dialogue: 0,0:18:28.00,0:18:32.00,Default,,0000,0000,0000,,is the simple one of just moving backwards.
Dialogue: 0,0:18:32.00,0:18:34.00,Default,,0000,0000,0000,,If I'm pointing right now to that B,
Dialogue: 0,0:18:34.00,0:18:37.00,Default,,0000,0000,0000,,and I'd like to get back to that Y, the
Dialogue: 0,0:18:37.00,0:18:41.00,Default,,0000,0000,0000,,link list is oblivious about how you got there. It knows where to go from
Dialogue: 0,0:18:41.00,0:18:45.00,Default,,0000,0000,0000,,here, but that backing up is not supported in the simple form.
Dialogue: 0,0:18:45.00,0:18:48.00,Default,,0000,0000,0000,,In order to find out what preceded the V,
Dialogue: 0,0:18:48.00,0:18:51.00,Default,,0000,0000,0000,,our only option right now is to go back to the beginning,
Dialogue: 0,0:18:51.00,0:18:53.00,Default,,0000,0000,0000,,and find it.
Dialogue: 0,0:18:53.00,0:18:56.00,Default,,0000,0000,0000,,So starting this pointer CP at the head,
Dialogue: 0,0:18:56.00,0:18:57.00,Default,,0000,0000,0000,,and saying,
Dialogue: 0,0:18:57.00,0:18:58.00,Default,,0000,0000,0000,,do you point to;
Dialogue: 0,0:18:58.00,0:19:01.00,Default,,0000,0000,0000,,is your next field the cursor?
Dialogue: 0,0:19:01.00,0:19:04.00,Default,,0000,0000,0000,,And this one says, no. And then it says, well okay advance. Does your next field point to
Dialogue: 0,0:19:04.00,0:19:08.00,Default,,0000,0000,0000,,the cursor? No it's not. Go to this one, does your next field point to the same place
Dialogue: 0,0:19:08.00,0:19:12.00,Default,,0000,0000,0000,,as the cursor, yes. Wise next field, points to the same place the cursor
Dialogue: 0,0:19:12.00,0:19:13.00,Default,,0000,0000,0000,,does.
Dialogue: 0,0:19:13.00,0:19:18.00,Default,,0000,0000,0000,,That must mean that Y was the one that preceded the cursor in the link
Dialogue: 0,0:19:18.00,0:19:22.00,Default,,0000,0000,0000,,list. So after having gone back to the beginning and walked all the way down, especially if I'm near
Dialogue: 0,0:19:22.00,0:19:24.00,Default,,0000,0000,0000,,the end, that's a long traversal.
Dialogue: 0,0:19:24.00,0:19:26.00,Default,,0000,0000,0000,,And when I get there, I can say "Oh yeah
Dialogue: 0,0:19:26.00,0:19:34.00,Default,,0000,0000,0000,,that's the one, back it up to there."
Dialogue: 0,0:19:34.00,0:19:37.00,Default,,0000,0000,0000,,Walking it all the way down;
Dialogue: 0,0:19:37.00,0:19:41.00,Default,,0000,0000,0000,,some good link list coding, good practice in there, but
Dialogue: 0,0:19:41.00,0:19:42.00,Default,,0000,0000,0000,,again a funny,
Dialogue: 0,0:19:42.00,0:19:44.00,Default,,0000,0000,0000,,funny set of trade offs, right?
Dialogue: 0,0:19:44.00,0:19:47.00,Default,,0000,0000,0000,,Does anybody have any questions about any part of the code?
Dialogue: 0,0:19:47.00,0:19:49.00,Default,,0000,0000,0000,,At the end
Dialogue: 0,0:19:49.00,0:19:51.00,Default,,0000,0000,0000,,could you just
Dialogue: 0,0:19:51.00,0:19:53.00,Default,,0000,0000,0000,,save the address of the pointer, and then the
Dialogue: 0,0:19:53.00,0:19:54.00,Default,,0000,0000,0000,,person
Dialogue: 0,0:19:54.00,0:19:56.00,Default,,0000,0000,0000,,who wants to go to the end could just
Dialogue: 0,0:19:56.00,0:19:59.00,Default,,0000,0000,0000,,access that? That was a great idea. It's like, so what about
Dialogue: 0,0:19:59.00,0:20:02.00,Default,,0000,0000,0000,,improving this? Right now all we have is a pointer to the front, and each
Dialogue: 0,0:20:02.00,0:20:06.00,Default,,0000,0000,0000,,pointer has only a pointer to the next. It's like, maybe we need to add some
Dialogue: 0,0:20:06.00,0:20:07.00,Default,,0000,0000,0000,,more stuff, track
Dialogue: 0,0:20:07.00,0:20:10.00,Default,,0000,0000,0000,,some more things. What if we tracked the
Dialogue: 0,0:20:10.00,0:20:12.00,Default,,0000,0000,0000,,tail? Would that help us?
Dialogue: 0,0:20:12.00,0:20:16.00,Default,,0000,0000,0000,,If we tracked the tail, we could move to the end quickly. Would
Dialogue: 0,0:20:16.00,0:20:19.00,Default,,0000,0000,0000,,that help us moving backwards?
Dialogue: 0,0:20:19.00,0:20:22.00,Default,,0000,0000,0000,,No. It solves one of our problems though, so you're on to something.
Dialogue: 0,0:20:22.00,0:20:25.00,Default,,0000,0000,0000,,Let's look at what we've got, and then we'll start thinking about ways to fix it, because that's going to be
Dialogue: 0,0:20:25.00,0:20:27.00,Default,,0000,0000,0000,,one of the pieces we're going to think about.
Dialogue: 0,0:20:27.00,0:20:29.00,Default,,0000,0000,0000,,So if I move to link list
Dialogue: 0,0:20:29.00,0:20:31.00,Default,,0000,0000,0000,,relative to what I have,
Dialogue: 0,0:20:31.00,0:20:33.00,Default,,0000,0000,0000,,again, it's like a shell game. The old ends moved.
Dialogue: 0,0:20:33.00,0:20:36.00,Default,,0000,0000,0000,,It used to be that editing was slow and we didn't like that.
Dialogue: 0,0:20:36.00,0:20:38.00,Default,,0000,0000,0000,,Then we made big movement fast,
Dialogue: 0,0:20:38.00,0:20:41.00,Default,,0000,0000,0000,,and now we have this funny thing were moving in certain ways is easy and
Dialogue: 0,0:20:41.00,0:20:45.00,Default,,0000,0000,0000,,moving other ways is bad. So moving
Dialogue: 0,0:20:45.00,0:20:46.00,Default,,0000,0000,0000,,down the document
Dialogue: 0,0:20:46.00,0:20:49.00,Default,,0000,0000,0000,,is good, moving backwards in the document not good.
Dialogue: 0,0:20:49.00,0:20:53.00,Default,,0000,0000,0000,,Moving back to the beginning is good, but moving to the end is bad.
Dialogue: 0,0:20:53.00,0:20:56.00,Default,,0000,0000,0000,,But then editing in all situations is good,
Dialogue: 0,0:20:56.00,0:20:59.00,Default,,0000,0000,0000,,another sort of quirky set of things. It just fells like it's like that game where the
Dialogue: 0,0:20:59.00,0:21:00.00,Default,,0000,0000,0000,,
Dialogue: 0,0:21:00.00,0:21:03.00,Default,,0000,0000,0000,,gophers pop there heads up, and you pound on them. And they just show up somewhere else. As
Dialogue: 0,0:21:03.00,0:21:06.00,Default,,0000,0000,0000,,soon as you get one thing fixed, it seems like something else had
Dialogue: 0,0:21:06.00,0:21:08.00,Default,,0000,0000,0000,,to give.
Dialogue: 0,0:21:08.00,0:21:11.00,Default,,0000,0000,0000,,This, I think, would actually be my ideal editor, because it turns out I
Dialogue: 0,0:21:11.00,0:21:14.00,Default,,0000,0000,0000,,have exactly this working style, which is like, I'll be down at the end of
Dialogue: 0,0:21:14.00,0:21:17.00,Default,,0000,0000,0000,,the document, and I'll have to be generating new things. And
Dialogue: 0,0:21:17.00,0:21:20.00,Default,,0000,0000,0000,,I'm getting tired and I don't like writing, and what I keep wanting to
Dialogue: 0,0:21:20.00,0:21:24.00,Default,,0000,0000,0000,,do is I go back to the beginning. And I read that again, because I worked on that the most and
Dialogue: 0,0:21:24.00,0:21:27.00,Default,,0000,0000,0000,,it's nice. And so I go back to the beginning, and I'm like oh yeah, look at this. Look at how lovely this
Dialogue: 0,0:21:27.00,0:21:28.00,Default,,0000,0000,0000,,is,
Dialogue: 0,0:21:28.00,0:21:31.00,Default,,0000,0000,0000,,and then I never want to go back to the end where all the trouble is. So I just
Dialogue: 0,0:21:31.00,0:21:34.00,Default,,0000,0000,0000,,keep going back to the beginning and editing in the front, and then slowly get
Dialogue: 0,0:21:34.00,0:21:37.00,Default,,0000,0000,0000,,back to the end. And then I don't like it again, and then I go back to the beginning.
Dialogue: 0,0:21:37.00,0:21:39.00,Default,,0000,0000,0000,,But I never actually willingly go to the end
Dialogue: 0,0:21:39.00,0:21:42.00,Default,,0000,0000,0000,,to face my fears. So
Dialogue: 0,0:21:42.00,0:21:46.00,Default,,0000,0000,0000,,this is the editor I need.
Dialogue: 0,0:21:46.00,0:21:47.00,Default,,0000,0000,0000,,Also
Dialogue: 0,0:21:47.00,0:21:51.00,Default,,0000,0000,0000,,has a bit of kicker in terms of space.
Dialogue: 0,0:21:51.00,0:21:56.00,Default,,0000,0000,0000,,So if the space for a character is 1 byte, which it typically is,
Dialogue: 0,0:21:56.00,0:21:58.00,Default,,0000,0000,0000,,and the space for a pointer is 4 bytes, then
Dialogue: 0,0:21:58.00,0:22:03.00,Default,,0000,0000,0000,,each of those link list cells is costing us 5 bytes, right?
Dialogue: 0,0:22:03.00,0:22:03.00,Default,,0000,0000,0000,,Which is
Dialogue: 0,0:22:03.00,0:22:07.00,Default,,0000,0000,0000,,sort of five times the amount of storage that the character itself
Dialogue: 0,0:22:07.00,0:22:10.00,Default,,0000,0000,0000,,would have taken alone,
Dialogue: 0,0:22:10.00,0:22:14.00,Default,,0000,0000,0000,,so in the vector it's fairly tight, a little bit more going up on that. But we've actually kind of blown
Dialogue: 0,0:22:14.00,0:22:18.00,Default,,0000,0000,0000,,it up by another factor of two even beyond the stack, which is not quite a
Dialogue: 0,0:22:18.00,0:22:22.00,Default,,0000,0000,0000,,good direction to be going.
Dialogue: 0,0:22:22.00,0:22:24.00,Default,,0000,0000,0000,,So let's talk about what we can do to fix that.
Dialogue: 0,0:22:24.00,0:22:27.00,Default,,0000,0000,0000,,I'm not going to go through the process of this. I'm just going to kind of give you a thought
Dialogue: 0,0:22:27.00,0:22:29.00,Default,,0000,0000,0000,,exercise, so you can just kind of
Dialogue: 0,0:22:29.00,0:22:30.00,Default,,0000,0000,0000,,visualize it.
Dialogue: 0,0:22:30.00,0:22:34.00,Default,,0000,0000,0000,,What we have here, right, is an information problem. We
Dialogue: 0,0:22:34.00,0:22:37.00,Default,,0000,0000,0000,,only are keeping track of certain
Dialogue: 0,0:22:37.00,0:22:39.00,Default,,0000,0000,0000,,pathways through that link list.
Dialogue: 0,0:22:39.00,0:22:42.00,Default,,0000,0000,0000,,What if we actually increased our access to the list?
Dialogue: 0,0:22:42.00,0:22:46.00,Default,,0000,0000,0000,,We don't need to have the full access of a vector, being able to know the nth
Dialogue: 0,0:22:46.00,0:22:49.00,Default,,0000,0000,0000,,character by number is not actually as far as we need to go. But we
Dialogue: 0,0:22:49.00,0:22:53.00,Default,,0000,0000,0000,,do just need a little bit more coordination between a cell and its neighbors.
Dialogue: 0,0:22:53.00,0:22:56.00,Default,,0000,0000,0000,,So the two things that would buy us out of a lot of the things that we're seeing
Dialogue: 0,0:22:56.00,0:22:58.00,Default,,0000,0000,0000,,here is if we added a tail pointer.
Dialogue: 0,0:22:58.00,0:23:01.00,Default,,0000,0000,0000,,So if I just add a tail pointer that points to the last cell, then I can move to the end
Dialogue: 0,0:23:01.00,0:23:02.00,Default,,0000,0000,0000,,quickly.
Dialogue: 0,0:23:02.00,0:23:05.00,Default,,0000,0000,0000,,You say cursor equals tail; the same that cursor equals head. So what was an O of N
Dialogue: 0,0:23:05.00,0:23:07.00,Default,,0000,0000,0000,,problem now is an O of 1.
Dialogue: 0,0:23:07.00,0:23:08.00,Default,,0000,0000,0000,,The backing up,
Dialogue: 0,0:23:08.00,0:23:12.00,Default,,0000,0000,0000,,not as easily solved by just having one thing that's going on;
Dialogue: 0,0:23:12.00,0:23:13.00,Default,,0000,0000,0000,,I also am going to need,
Dialogue: 0,0:23:13.00,0:23:17.00,Default,,0000,0000,0000,,on a per cell basis this ability to move backwards.
Dialogue: 0,0:23:17.00,0:23:19.00,Default,,0000,0000,0000,,
Dialogue: 0,0:23:19.00,0:23:22.00,Default,,0000,0000,0000,,Well, it's just symmetry, right? If A knows where B is, and B knows where C is, and C knows where D is, what's to stop
Dialogue: 0,0:23:22.00,0:23:25.00,Default,,0000,0000,0000,,it from also just tracking the information going in the other way,
Dialogue: 0,0:23:25.00,0:23:30.00,Default,,0000,0000,0000,,so that D knows that it came from C, and C knows it came from B, and so on.
Dialogue: 0,0:23:30.00,0:23:35.00,Default,,0000,0000,0000,,And so having this completely symmetric parallel set of links that just run the other
Dialogue: 0,0:23:35.00,0:23:35.00,Default,,0000,0000,0000,,direction,
Dialogue: 0,0:23:35.00,0:23:39.00,Default,,0000,0000,0000,,then buys you the ability to move backwards with ease.
Dialogue: 0,0:23:39.00,0:23:42.00,Default,,0000,0000,0000,,The other thing that this would give you is the tail pointer
Dialogue: 0,0:23:42.00,0:23:46.00,Default,,0000,0000,0000,,is almost not quite enough to give you the exact place of the end. It gives it to
Dialogue: 0,0:23:46.00,0:23:47.00,Default,,0000,0000,0000,,you, but you also have to be
Dialogue: 0,0:23:47.00,0:23:49.00,Default,,0000,0000,0000,,careful about what is it going to take to update it?
Dialogue: 0,0:23:49.00,0:23:53.00,Default,,0000,0000,0000,,And so inserting can easily update the tail pointer. It's the deleting that kind of
Dialogue: 0,0:23:53.00,0:23:55.00,Default,,0000,0000,0000,,would get you into trouble. If you were
Dialogue: 0,0:23:55.00,0:23:58.00,Default,,0000,0000,0000,,here and deleting, you would have to kind of keep track of making sure if you were deleting
Dialogue: 0,0:23:58.00,0:24:01.00,Default,,0000,0000,0000,,the thing that was the tail pointer, so you have to be a little about making sure
Dialogue: 0,0:24:01.00,0:24:04.00,Default,,0000,0000,0000,,you don't lose track of your tail.
Dialogue: 0,0:24:04.00,0:24:06.00,Default,,0000,0000,0000,,But once I have both of these in place,
Dialogue: 0,0:24:06.00,0:24:09.00,Default,,0000,0000,0000,,I suddenly have something that can move
Dialogue: 0,0:24:09.00,0:24:10.00,Default,,0000,0000,0000,,forward easily, O of 1;
Dialogue: 0,0:24:10.00,0:24:15.00,Default,,0000,0000,0000,,move to the front easily, O of 1; move to the tail easily, O of 1; move backwards O of 1.
Dialogue: 0,0:24:15.00,0:24:20.00,Default,,0000,0000,0000,,So I can make all of my operations
Dialogue: 0,0:24:20.00,0:24:22.00,Default,,0000,0000,0000,,O of 1.
Dialogue: 0,0:24:22.00,0:24:24.00,Default,,0000,0000,0000,,Deleting, you're still going to have to delete the individual cells, but there's one place where
Dialogue: 0,0:24:24.00,0:24:27.00,Default,,0000,0000,0000,,it suffers, but that's a much more rare occurrence.
Dialogue: 0,0:24:27.00,0:24:31.00,Default,,0000,0000,0000,,And I can get all six; it moves fast, in every dimension;
Dialogue: 0,0:24:31.00,0:24:32.00,Default,,0000,0000,0000,,inserts and deletes
Dialogue: 0,0:24:32.00,0:24:35.00,Default,,0000,0000,0000,,all good.
Dialogue: 0,0:24:35.00,0:24:37.00,Default,,0000,0000,0000,,And there are two places we paid for it.
Dialogue: 0,0:24:37.00,0:24:40.00,Default,,0000,0000,0000,,One is certainly the memory.
Dialogue: 0,0:24:40.00,0:24:45.00,Default,,0000,0000,0000,,So a 4 byte pointer one direction, a 4 byte pointer another direction,
Dialogue: 0,0:24:45.00,0:24:49.00,Default,,0000,0000,0000,,plus the 1 byte for the character means we have a 9 byte per
Dialogue: 0,0:24:49.00,0:24:50.00,Default,,0000,0000,0000,,character
Dialogue: 0,0:24:50.00,0:24:52.00,Default,,0000,0000,0000,,storage usage.
Dialogue: 0,0:24:52.00,0:24:55.00,Default,,0000,0000,0000,,And the other way, which is a little bit hard to represent with some number
Dialogue: 0,0:24:55.00,0:24:57.00,Default,,0000,0000,0000,,in a quantitative way, but actually it's also an important factor, which is
Dialogue: 0,0:24:57.00,0:25:00.00,Default,,0000,0000,0000,,your code got a lot more complicated.
Dialogue: 0,0:25:00.00,0:25:02.00,Default,,0000,0000,0000,,If you looked at the code for the vector of the stack version, it was a few
Dialogue: 0,0:25:02.00,0:25:03.00,Default,,0000,0000,0000,,lines here a few lines there.
Dialogue: 0,0:25:03.00,0:25:06.00,Default,,0000,0000,0000,,If you looked at the code for the link list singly we looked at, it's like you've got
Dialogue: 0,0:25:06.00,0:25:07.00,Default,,0000,0000,0000,,to wire up these pointers.
Dialogue: 0,0:25:07.00,0:25:10.00,Default,,0000,0000,0000,,Now imagine you've got to wire up twice as many pointers.
Dialogue: 0,0:25:10.00,0:25:14.00,Default,,0000,0000,0000,,Not only do you have the in and out going one direction, you'll have the in and out going the
Dialogue: 0,0:25:14.00,0:25:15.00,Default,,0000,0000,0000,,other direction,
Dialogue: 0,0:25:15.00,0:25:17.00,Default,,0000,0000,0000,,and just the
Dialogue: 0,0:25:17.00,0:25:21.00,Default,,0000,0000,0000,,opportunity to make errors with pointers has now gone up by a factor of two.
Dialogue: 0,0:25:21.00,0:25:24.00,Default,,0000,0000,0000,,The idea that you could get a vector version of this up and running in
Dialogue: 0,0:25:24.00,0:25:26.00,Default,,0000,0000,0000,,no time,
Dialogue: 0,0:25:26.00,0:25:30.00,Default,,0000,0000,0000,,compared to several days, let's say, of getting the doubly link one working. It
Dialogue: 0,0:25:30.00,0:25:32.00,Default,,0000,0000,0000,,might be a factor to keep in mind.
Dialogue: 0,0:25:32.00,0:25:36.00,Default,,0000,0000,0000,,If you're kind of investing for the long haul, sure, work hard, but know
Dialogue: 0,0:25:36.00,0:25:41.00,Default,,0000,0000,0000,,that it wasn't for free.
Dialogue: 0,0:25:41.00,0:25:42.00,Default,,0000,0000,0000,,So you've
Dialogue: 0,0:25:42.00,0:25:45.00,Default,,0000,0000,0000,,got 89 percent overhead.
Dialogue: 0,0:25:45.00,0:25:49.00,Default,,0000,0000,0000,,That's a lot of overhead for small bits of data.
Dialogue: 0,0:25:49.00,0:25:53.00,Default,,0000,0000,0000,,More likely, and this is actually the way that most modern word processors
Dialogue: 0,0:25:53.00,0:25:54.00,Default,,0000,0000,0000,,do do this,
Dialogue: 0,0:25:54.00,0:25:58.00,Default,,0000,0000,0000,,is they don't just make one or the other; it's not just a array or a stack or a link list.
Dialogue: 0,0:25:58.00,0:25:59.00,Default,,0000,0000,0000,,They
Dialogue: 0,0:25:59.00,0:26:04.00,Default,,0000,0000,0000,,actually look at ways to combine the features of both to get a hybrid,
Dialogue: 0,0:26:04.00,0:26:05.00,Default,,0000,0000,0000,,where you can take
Dialogue: 0,0:26:05.00,0:26:10.00,Default,,0000,0000,0000,,some of the advantages of one pipe of data, but also try to avoid its worst
Dialogue: 0,0:26:10.00,0:26:13.00,Default,,0000,0000,0000,,weaknesses. So the most common way they're going to do this is some kind of
Dialogue: 0,0:26:13.00,0:26:15.00,Default,,0000,0000,0000,,chunking strategy,
Dialogue: 0,0:26:15.00,0:26:17.00,Default,,0000,0000,0000,,where you have a segment of the
Dialogue: 0,0:26:17.00,0:26:21.00,Default,,0000,0000,0000,,buffer that kind of is moved aside and worked on in one little array. It
Dialogue: 0,0:26:21.00,0:26:25.00,Default,,0000,0000,0000,,might be that those arrays are ten or 20 or a sentence long, or paragraph long.
Dialogue: 0,0:26:25.00,0:26:28.00,Default,,0000,0000,0000,,It might be that they are actually dictated by when you change styles.
Dialogue: 0,0:26:28.00,0:26:30.00,Default,,0000,0000,0000,,All of the code that's in one font
Dialogue: 0,0:26:30.00,0:26:33.00,Default,,0000,0000,0000,,kind of gets moved into one chunk, and as soon as you change styles, it breaks
Dialogue: 0,0:26:33.00,0:26:37.00,Default,,0000,0000,0000,,into a new chunk that follows to kind of keep track of the formatting information. It
Dialogue: 0,0:26:37.00,0:26:40.00,Default,,0000,0000,0000,,depends on some of the other features that are present in the processor
Dialogue: 0,0:26:40.00,0:26:43.00,Default,,0000,0000,0000,,here, but it's likely that rather than having all 1,000 or all 10 million
Dialogue: 0,0:26:43.00,0:26:45.00,Default,,0000,0000,0000,,characters in one
Dialogue: 0,0:26:45.00,0:26:46.00,Default,,0000,0000,0000,,data structure,
Dialogue: 0,0:26:46.00,0:26:47.00,Default,,0000,0000,0000,,they're actually kind of separated
Dialogue: 0,0:26:47.00,0:26:50.00,Default,,0000,0000,0000,,to where you have a little bit of both. So the most likely thing is that
Dialogue: 0,0:26:50.00,0:26:53.00,Default,,0000,0000,0000,,there is some kind of array strategy on a chunk basis.
Dialogue: 0,0:26:53.00,0:26:56.00,Default,,0000,0000,0000,,There's a linking between those chunks.
Dialogue: 0,0:26:56.00,0:26:59.00,Default,,0000,0000,0000,,And what this allows you do is to
Dialogue: 0,0:26:59.00,0:27:01.00,Default,,0000,0000,0000,,share that overhead cost.
Dialogue: 0,0:27:01.00,0:27:05.00,Default,,0000,0000,0000,,So in this case, if I had every sentence in a chunk by itself,
Dialogue: 0,0:27:05.00,0:27:08.00,Default,,0000,0000,0000,,and then if I had next and previous pointer, which pointed to the next sentence and the previous
Dialogue: 0,0:27:08.00,0:27:09.00,Default,,0000,0000,0000,,
Dialogue: 0,0:27:09.00,0:27:11.00,Default,,0000,0000,0000,,sentence, when I need to move the cursor forward or backwards
Dialogue: 0,0:27:11.00,0:27:15.00,Default,,0000,0000,0000,,within a chunk, it's just in changing this index. Oh, it's in index two, but
Dialogue: 0,0:27:15.00,0:27:16.00,Default,,0000,0000,0000,,now it's moving to three, or four, or five.
Dialogue: 0,0:27:16.00,0:27:20.00,Default,,0000,0000,0000,,And then when it gets to the end of that chunk, to the end of that sentence, and you move forward, well then it
Dialogue: 0,0:27:20.00,0:27:23.00,Default,,0000,0000,0000,,follows the next link forward.
Dialogue: 0,0:27:23.00,0:27:25.00,Default,,0000,0000,0000,,Similarly moving backwards, right, so
Dialogue: 0,0:27:25.00,0:27:29.00,Default,,0000,0000,0000,,within a chunk doing array-like manipulations, and then as it crosses the
Dialogue: 0,0:27:29.00,0:27:32.00,Default,,0000,0000,0000,,boundary using a link list steps to get further down.
Dialogue: 0,0:27:32.00,0:27:35.00,Default,,0000,0000,0000,,So when it needs to move to the front or the back, those things are easily
Dialogue: 0,0:27:35.00,0:27:37.00,Default,,0000,0000,0000,,accessible using head and tail pointers.
Dialogue: 0,0:27:37.00,0:27:39.00,Default,,0000,0000,0000,,When I need to do an edit,
Dialogue: 0,0:27:39.00,0:27:42.00,Default,,0000,0000,0000,,it operates in this array-like kind of
Dialogue: 0,0:27:42.00,0:27:44.00,Default,,0000,0000,0000,,way
Dialogue: 0,0:27:44.00,0:27:46.00,Default,,0000,0000,0000,,when there's space within that chunk. So you start editing in a sentence, then it
Dialogue: 0,0:27:46.00,0:27:49.00,Default,,0000,0000,0000,,would kind of do some shifting on that array. But the array itself being pretty
Dialogue: 0,0:27:49.00,0:27:51.00,Default,,0000,0000,0000,,small
Dialogue: 0,0:27:51.00,0:27:53.00,Default,,0000,0000,0000,,means that although you are paying that cost of shuffling,
Dialogue: 0,0:27:53.00,0:27:56.00,Default,,0000,0000,0000,,you are doing it on a smaller chunk. It's not 1,000 characters that have to move, it's
Dialogue: 0,0:27:56.00,0:27:59.00,Default,,0000,0000,0000,,20 or 40 that have to move within that sentence.
Dialogue: 0,0:27:59.00,0:28:02.00,Default,,0000,0000,0000,,And that when
Dialogue: 0,0:28:02.00,0:28:04.00,Default,,0000,0000,0000,,you need to insert a new sentence or a new chunk in the middle, you are doing
Dialogue: 0,0:28:04.00,0:28:08.00,Default,,0000,0000,0000,,link list-like manipulations to build a new chunk and insert and splice,
Dialogue: 0,0:28:08.00,0:28:11.00,Default,,0000,0000,0000,,so you have that flexibility, where the many characters aren't
Dialogue: 0,0:28:11.00,0:28:14.00,Default,,0000,0000,0000,,all affected by it. So you have kind of local array editing
Dialogue: 0,0:28:14.00,0:28:16.00,Default,,0000,0000,0000,,and global link list editing
Dialogue: 0,0:28:16.00,0:28:18.00,Default,,0000,0000,0000,,that gives you kind of the best of both worlds.
Dialogue: 0,0:28:18.00,0:28:19.00,Default,,0000,0000,0000,,
Dialogue: 0,0:28:19.00,0:28:23.00,Default,,0000,0000,0000,,But again, the factor is cost showing up in code complexity.
Dialogue: 0,0:28:23.00,0:28:27.00,Default,,0000,0000,0000,,That what you are looking at is kind of space/time tradeoff. Well, I can throw space at
Dialogue: 0,0:28:27.00,0:28:29.00,Default,,0000,0000,0000,,this, and most people will say that in computer science, "Well I can throw space and this and
Dialogue: 0,0:28:29.00,0:28:31.00,Default,,0000,0000,0000,,get better times." So
Dialogue: 0,0:28:31.00,0:28:35.00,Default,,0000,0000,0000,,the double link list is a good example of something that throws space at a problem to get better
Dialogue: 0,0:28:35.00,0:28:37.00,Default,,0000,0000,0000,,time. There's a lot of overhead.
Dialogue: 0,0:28:37.00,0:28:39.00,Default,,0000,0000,0000,,Moving to the chunk list says I want to get back some of that space. I'm
Dialogue: 0,0:28:39.00,0:28:43.00,Default,,0000,0000,0000,,not willing to invest 90 percent overhead to get this. Can I find a way to
Dialogue: 0,0:28:43.00,0:28:44.00,Default,,0000,0000,0000,,take a
Dialogue: 0,0:28:44.00,0:28:47.00,Default,,0000,0000,0000,,whole sentence worth of things and add a few pointers here? That means that
Dialogue: 0,0:28:47.00,0:28:48.00,Default,,0000,0000,0000,,there's only two
Dialogue: 0,0:28:48.00,0:28:51.00,Default,,0000,0000,0000,,4 byte pointers per each sentence as opposed to each character,
Dialogue: 0,0:28:51.00,0:28:53.00,Default,,0000,0000,0000,,and that really way reduces the overhead.
Dialogue: 0,0:28:53.00,0:28:55.00,Default,,0000,0000,0000,,But then now,
Dialogue: 0,0:28:55.00,0:28:58.00,Default,,0000,0000,0000,,the problem is still back on your shoulders in terms of effort,
Dialogue: 0,0:28:58.00,0:29:02.00,Default,,0000,0000,0000,,now I have both an array, and a link list, and double links, and
Dialogue: 0,0:29:02.00,0:29:03.00,Default,,0000,0000,0000,,a
Dialogue: 0,0:29:03.00,0:29:07.00,Default,,0000,0000,0000,,lot of complicated stuff flying around to make it work.
Dialogue: 0,0:29:07.00,0:29:08.00,Default,,0000,0000,0000,,But it does work out.
Dialogue: 0,0:29:08.00,0:29:11.00,Default,,0000,0000,0000,,It's kind of the process that designers go through when
Dialogue: 0,0:29:11.00,0:29:12.00,Default,,0000,0000,0000,,they're building these kinds of
Dialogue: 0,0:29:12.00,0:29:16.00,Default,,0000,0000,0000,,key structures. It like, what are the options, and do any of the basic
Dialogue: 0,0:29:16.00,0:29:18.00,Default,,0000,0000,0000,,things we know about work? What about
Dialogue: 0,0:29:18.00,0:29:21.00,Default,,0000,0000,0000,,building even fancier things that kind of take the best of both world and mix
Dialogue: 0,0:29:21.00,0:29:23.00,Default,,0000,0000,0000,,them together and have a little bit of the weaknesses of this a little of that, but none of
Dialogue: 0,0:29:23.00,0:29:26.00,Default,,0000,0000,0000,,the really awful
Dialogue: 0,0:29:26.00,0:29:27.00,Default,,0000,0000,0000,,worst cases
Dialogue: 0,0:29:27.00,0:29:28.00,Default,,0000,0000,0000,,present in the end result.
Dialogue: 0,0:29:28.00,0:29:31.00,Default,,0000,0000,0000,,So in this case you'd have a lot of things that were constant time where constant was
Dialogue: 0,0:29:31.00,0:29:33.00,Default,,0000,0000,0000,,defined by the chunk size.
Dialogue: 0,0:29:33.00,0:29:37.00,Default,,0000,0000,0000,,So O of 100, let's say, if that was the maximum chunk size
Dialogue: 0,0:29:37.00,0:29:39.00,Default,,0000,0000,0000,,to do these things, as opposed to O of
Dialogue: 0,0:29:39.00,0:29:42.00,Default,,0000,0000,0000,,N for the whole block net,
Dialogue: 0,0:29:42.00,0:29:43.00,Default,,0000,0000,0000,,so kind of a neat
Dialogue: 0,0:29:43.00,0:29:45.00,Default,,0000,0000,0000,,little thing to think through.
Dialogue: 0,0:29:45.00,0:29:48.00,Default,,0000,0000,0000,,There was a time, just so you can feel
Dialogue: 0,0:29:48.00,0:29:51.00,Default,,0000,0000,0000,,gratified about how I've worked you very hard, but actually in the past I've been
Dialogue: 0,0:29:51.00,0:29:53.00,Default,,0000,0000,0000,,even harsher.
Dialogue: 0,0:29:53.00,0:29:57.00,Default,,0000,0000,0000,,We actually had them build the doubly linked chunked list editor buffer,
Dialogue: 0,0:29:57.00,0:30:00.00,Default,,0000,0000,0000,,and now we have you build the singly linked chunk list PQ, and it's
Dialogue: 0,0:30:00.00,0:30:02.00,Default,,0000,0000,0000,,actually
Dialogue: 0,0:30:02.00,0:30:06.00,Default,,0000,0000,0000,,still very complicated, as you'll find out, but not nearly quite as hairy as the
Dialogue: 0,0:30:06.00,0:30:09.00,Default,,0000,0000,0000,,full in both directions every way
Dialogue: 0,0:30:09.00,0:30:11.00,Default,,0000,0000,0000,,craziness.
Dialogue: 0,0:30:11.00,0:30:14.00,Default,,0000,0000,0000,,And you can kind of imagine in your mind.
Dialogue: 0,0:30:14.00,0:30:16.00,Default,,0000,0000,0000,,Any questions about edited buffer?
Dialogue: 0,0:30:16.00,0:30:18.00,Default,,0000,0000,0000,,We?ve got two more data structures to implement,
Dialogue: 0,0:30:18.00,0:30:20.00,Default,,0000,0000,0000,,two more things that we've been using,
Dialogue: 0,0:30:20.00,0:30:25.00,Default,,0000,0000,0000,,and happy to have in our arsenal that we need to know how they work.
Dialogue: 0,0:30:25.00,0:30:29.00,Default,,0000,0000,0000,,Let's talk about map first, and in
Dialogue: 0,0:30:29.00,0:30:31.00,Default,,0000,0000,0000,,fact the strategy that I'm going to end up showing you for map is actually going to be
Dialogue: 0,0:30:31.00,0:30:35.00,Default,,0000,0000,0000,,the same one we use for set, then we'll come back and think of an even more clever
Dialogue: 0,0:30:35.00,0:30:37.00,Default,,0000,0000,0000,,way to do map, too. So
Dialogue: 0,0:30:37.00,0:30:40.00,Default,,0000,0000,0000,,we've got two things to talk about, which are binary search trees and hashing. We'll
Dialogue: 0,0:30:40.00,0:30:41.00,Default,,0000,0000,0000,,do binary search trees first,
Dialogue: 0,0:30:41.00,0:30:44.00,Default,,0000,0000,0000,,and then we'll get back to the hashing the second time around.
Dialogue: 0,0:30:44.00,0:30:46.00,Default,,0000,0000,0000,,So
Dialogue: 0,0:30:46.00,0:30:49.00,Default,,0000,0000,0000,,map is, next to vector, probably the most useful thing you've got going on in
Dialogue: 0,0:30:49.00,0:30:50.00,Default,,0000,0000,0000,,your class library,
Dialogue: 0,0:30:50.00,0:30:53.00,Default,,0000,0000,0000,,all kinds of things that do look up based
Dialogue: 0,0:30:53.00,0:30:56.00,Default,,0000,0000,0000,,activities; looking up students by ID number,
Dialogue: 0,0:30:56.00,0:30:57.00,Default,,0000,0000,0000,,phone numbers,
Dialogue: 0,0:30:57.00,0:31:00.00,Default,,0000,0000,0000,,by name, any of these kinds of things where you need to have this key at associated satellite
Dialogue: 0,0:31:00.00,0:31:02.00,Default,,0000,0000,0000,,information. And
Dialogue: 0,0:31:02.00,0:31:05.00,Default,,0000,0000,0000,,you'd like to be able to do that retrieval and update quickly.
Dialogue: 0,0:31:05.00,0:31:08.00,Default,,0000,0000,0000,,The map is the one for you.
Dialogue: 0,0:31:08.00,0:31:11.00,Default,,0000,0000,0000,,So if you remember it's key value fears, it's all about key being the
Dialogue: 0,0:31:11.00,0:31:15.00,Default,,0000,0000,0000,,identifying mark that allows you to find the associated value. And then the value
Dialogue: 0,0:31:15.00,0:31:18.00,Default,,0000,0000,0000,,is actually just being stored and kind of retrieved without using it
Dialogue: 0,0:31:18.00,0:31:21.00,Default,,0000,0000,0000,,or examining it in any kind of interesting way.
Dialogue: 0,0:31:21.00,0:31:25.00,Default,,0000,0000,0000,,And what we're really interested in here is how to make this guy work really efficiently. So efficiently
Dialogue: 0,0:31:25.00,0:31:27.00,Default,,0000,0000,0000,,being hopefully log in or better,
Dialogue: 0,0:31:27.00,0:31:31.00,Default,,0000,0000,0000,,if we could get that on both the update operations that add and remove things
Dialogue: 0,0:31:31.00,0:31:33.00,Default,,0000,0000,0000,,from the map, as well as the
Dialogue: 0,0:31:33.00,0:31:34.00,Default,,0000,0000,0000,,look up operation, then
Dialogue: 0,0:31:34.00,0:31:37.00,Default,,0000,0000,0000,,that would please probably all our clients immensely, if we could get both of
Dialogue: 0,0:31:37.00,0:31:41.00,Default,,0000,0000,0000,,those going well.
Dialogue: 0,0:31:41.00,0:31:45.00,Default,,0000,0000,0000,,So I'm going to build you on that. I probably have enough time to do that.
Dialogue: 0,0:31:45.00,0:31:46.00,Default,,0000,0000,0000,,That
Dialogue: 0,0:31:46.00,0:31:48.00,Default,,0000,0000,0000,,attacks it from
Dialogue: 0,0:31:48.00,0:31:53.00,Default,,0000,0000,0000,,using simple tools to start with, just to kind of get a base line for what we can do.
Dialogue: 0,0:31:53.00,0:31:54.00,Default,,0000,0000,0000,,
Dialogue: 0,0:31:54.00,0:31:56.00,Default,,0000,0000,0000,,Vector, our old friend vector,
Dialogue: 0,0:31:56.00,0:31:59.00,Default,,0000,0000,0000,,can't get too much mileage out of vector, apparently, because you can always find a
Dialogue: 0,0:31:59.00,0:32:00.00,Default,,0000,0000,0000,,way to make it do something
Dialogue: 0,0:32:00.00,0:32:01.00,Default,,0000,0000,0000,,useful for you.
Dialogue: 0,0:32:01.00,0:32:02.00,Default,,0000,0000,0000,,It
Dialogue: 0,0:32:02.00,0:32:03.00,Default,,0000,0000,0000,,gives us the convenience
Dialogue: 0,0:32:03.00,0:32:05.00,Default,,0000,0000,0000,,
Dialogue: 0,0:32:05.00,0:32:07.00,Default,,0000,0000,0000,,of managing that thing with low overhead,
Dialogue: 0,0:32:07.00,0:32:09.00,Default,,0000,0000,0000,,direct access is good.
Dialogue: 0,0:32:09.00,0:32:11.00,Default,,0000,0000,0000,,We make a parastruct
Dialogue: 0,0:32:11.00,0:32:13.00,Default,,0000,0000,0000,,that has the key and the value together.
Dialogue: 0,0:32:13.00,0:32:16.00,Default,,0000,0000,0000,,We store it into a vector,
Dialogue: 0,0:32:16.00,0:32:18.00,Default,,0000,0000,0000,,and then we
Dialogue: 0,0:32:18.00,0:32:21.00,Default,,0000,0000,0000,,may or may not sort that vector. But if it's sorted, there's probably some good reasons. Think
Dialogue: 0,0:32:21.00,0:32:22.00,Default,,0000,0000,0000,,about
Dialogue: 0,0:32:22.00,0:32:26.00,Default,,0000,0000,0000,,what order to sort it in, what information to be using to sort that,
Dialogue: 0,0:32:26.00,0:32:28.00,Default,,0000,0000,0000,,and then we'll get value to add. We're just going to go
Dialogue: 0,0:32:28.00,0:32:30.00,Default,,0000,0000,0000,,through doing it, rather than talk about it.
Dialogue: 0,0:32:30.00,0:32:32.00,Default,,0000,0000,0000,,We'll just go over and
Dialogue: 0,0:32:32.00,0:32:36.00,Default,,0000,0000,0000,,make a vector happen.
Dialogue: 0,0:32:36.00,0:32:38.00,Default,,0000,0000,0000,,Let's get over here in X-code.
Dialogue: 0,0:32:38.00,0:32:40.00,Default,,0000,0000,0000,,Let's take a look at
Dialogue: 0,0:32:40.00,0:32:42.00,Default,,0000,0000,0000,,my map dot H,
Dialogue: 0,0:32:42.00,0:32:43.00,Default,,0000,0000,0000,,and all
Dialogue: 0,0:32:43.00,0:32:46.00,Default,,0000,0000,0000,,I'm going to put in there is actually add and get value.
Dialogue: 0,0:32:46.00,0:32:48.00,Default,,0000,0000,0000,,And
Dialogue: 0,0:32:48.00,0:32:50.00,Default,,0000,0000,0000,,the other one contains key and remove."
Dialogue: 0,0:32:50.00,0:32:52.00,Default,,0000,0000,0000,,
Dialogue: 0,0:32:52.00,0:32:55.00,Default,,0000,0000,0000,,But these are these two operations that really matter to us, getting something in there, and
Dialogue: 0,0:32:55.00,0:32:57.00,Default,,0000,0000,0000,,getting something back out.
Dialogue: 0,0:32:57.00,0:32:58.00,Default,,0000,0000,0000,,
Dialogue: 0,0:32:58.00,0:33:00.00,Default,,0000,0000,0000,,And so I'm going to start by
Dialogue: 0,0:33:00.00,0:33:02.00,Default,,0000,0000,0000,,building this thing on vector. So let me go ahead and
Dialogue: 0,0:33:02.00,0:33:14.00,Default,,0000,0000,0000,,indicate that I plan to use vector as part of
Dialogue: 0,0:33:14.00,0:33:15.00,Default,,0000,0000,0000,,what I'm doing. So I defined a little structure
Dialogue: 0,0:33:15.00,0:33:20.00,Default,,0000,0000,0000,,that's the pair. I'm going to call that "pair"
Dialogue: 0,0:33:20.00,0:33:23.00,Default,,0000,0000,0000,,even, that's a nice word for it. So the pair of the key and the value that go together,
Dialogue: 0,0:33:23.00,0:33:29.00,Default,,0000,0000,0000,,and then what I will store here
Dialogue: 0,0:33:29.00,0:33:31.00,Default,,0000,0000,0000,,is a vector of those pairs. They'll
Dialogue: 0,0:33:31.00,0:33:36.00,Default,,0000,0000,0000,,give me a key to value; I'll stick them together in that little struct, stick them into my vector, and
Dialogue: 0,0:33:36.00,0:33:38.00,Default,,0000,0000,0000,,hopefully be able to retrieve them later.
Dialogue: 0,0:33:38.00,0:33:42.00,Default,,0000,0000,0000,,So given that I'm depending only on vector, I don?t have any other
Dialogue: 0,0:33:42.00,0:33:45.00,Default,,0000,0000,0000,,information, I don't technically need to go out of my way to disallow then
Dialogue: 0,0:33:45.00,0:33:48.00,Default,,0000,0000,0000,,memory-wise copying, because vector does a deep copy. But I'm going to leave it in there, because I
Dialogue: 0,0:33:48.00,0:33:52.00,Default,,0000,0000,0000,,plan on going some place that is eventually going to need it. I might as well be safe from
Dialogue: 0,0:33:52.00,0:33:54.00,Default,,0000,0000,0000,,the get go.
Dialogue: 0,0:33:54.00,0:33:55.00,Default,,0000,0000,0000,,The vector
Dialogue: 0,0:33:55.00,0:34:00.00,Default,,0000,0000,0000,,will be set up and destroyed automatically as part of management of my
Dialogue: 0,0:34:00.00,0:34:04.00,Default,,0000,0000,0000,,data member. So I actually don't have any explicit allocation/deallocation, so if I look at my
Dialogue: 0,0:34:04.00,0:34:06.00,Default,,0000,0000,0000,,constructor and destructor they'll be totally empty.
Dialogue: 0,0:34:06.00,0:34:11.00,Default,,0000,0000,0000,,And then add and get value are where I'm going to actually get to do some work.
Dialogue: 0,0:34:11.00,0:34:14.00,Default,,0000,0000,0000,,Before I implement them, I'm just going to think for a second about
Dialogue: 0,0:34:14.00,0:34:16.00,Default,,0000,0000,0000,,how this is going to play out.
Dialogue: 0,0:34:16.00,0:34:20.00,Default,,0000,0000,0000,,Let's say I'm doing a vector that's storing
Dialogue: 0,0:34:20.00,0:34:26.00,Default,,0000,0000,0000,,strings and their length. Let's say, it's just a map of
Dialogue: 0,0:34:26.00,0:34:27.00,Default,,0000,0000,0000,,string,
Dialogue: 0,0:34:27.00,0:34:30.00,Default,,0000,0000,0000,,
Dialogue: 0,0:34:30.00,0:34:34.00,Default,,0000,0000,0000,,and if I do M dot add
Dialogue: 0,0:34:34.00,0:34:37.00,Default,,0000,0000,0000,,car. I'm going to store a three with it,
Dialogue: 0,0:34:37.00,0:34:39.00,Default,,0000,0000,0000,,so on the other side of the wall,
Dialogue: 0,0:34:39.00,0:34:41.00,Default,,0000,0000,0000,,what we're going to do is make a little struct
Dialogue: 0,0:34:41.00,0:34:43.00,Default,,0000,0000,0000,,that has the word car
Dialogue: 0,0:34:43.00,0:34:47.00,Default,,0000,0000,0000,,and the number three with it, and we package it into our ray.
Dialogue: 0,0:34:47.00,0:34:51.00,Default,,0000,0000,0000,,And so then we get a second call to put something in like
Dialogue: 0,0:34:51.00,0:34:55.00,Default,,0000,0000,0000,,dog, also with a three, then we'll make a second one of these and stick it in
Dialogue: 0,0:34:55.00,0:34:58.00,Default,,0000,0000,0000,,our ray.
Dialogue: 0,0:34:58.00,0:35:01.00,Default,,0000,0000,0000,,And so on, so the idea is to have the vector really kind of manage where the storage is going. And
Dialogue: 0,0:35:01.00,0:35:02.00,Default,,0000,0000,0000,,then what
Dialogue: 0,0:35:02.00,0:35:05.00,Default,,0000,0000,0000,,we'll just do is package it up and stick it in there.
Dialogue: 0,0:35:05.00,0:35:08.00,Default,,0000,0000,0000,,The one thing, though, that I have to think a little bit about, because it sounds
Dialogue: 0,0:35:08.00,0:35:11.00,Default,,0000,0000,0000,,like add should be pretty easy. It almost seems like what I need to do is something
Dialogue: 0,0:35:11.00,0:35:13.00,Default,,0000,0000,0000,,as simple as this. And
Dialogue: 0,0:35:13.00,0:35:15.00,Default,,0000,0000,0000,,I'll start to write the code, and then you can tell me why
Dialogue: 0,0:35:15.00,0:35:17.00,Default,,0000,0000,0000,,this isn't what I want to do.
Dialogue: 0,0:35:17.00,0:35:20.00,Default,,0000,0000,0000,,I say pair TP, and I say P dot
Dialogue: 0,0:35:20.00,0:35:23.00,Default,,0000,0000,0000,,key equals key P dot
Dialogue: 0,0:35:23.00,0:35:30.00,Default,,0000,0000,0000,,value equals val, and then I say entries dot add P.
Dialogue: 0,0:35:30.00,0:35:32.00,Default,,0000,0000,0000,,Almost, but not quite what I want,
Dialogue: 0,0:35:32.00,0:35:34.00,Default,,0000,0000,0000,,what have I forgotten
Dialogue: 0,0:35:34.00,0:35:39.00,Default,,0000,0000,0000,,to take care of?
Dialogue: 0,0:35:39.00,0:35:42.00,Default,,0000,0000,0000,,If it's not already in there;
Dialogue: 0,0:35:42.00,0:35:46.00,Default,,0000,0000,0000,,this has to do with just what's the interface for nap. What does nap say about it if you
Dialogue: 0,0:35:46.00,0:35:48.00,Default,,0000,0000,0000,,try to add
Dialogue: 0,0:35:48.00,0:35:51.00,Default,,0000,0000,0000,,for a key a different value. So in the case of this one, it didn't quite make sense that I would add
Dialogue: 0,0:35:51.00,0:35:55.00,Default,,0000,0000,0000,,something, but let's say I accidentally put car in there with a link to the first time that I went
Dialogue: 0,0:35:55.00,0:35:57.00,Default,,0000,0000,0000,,to go fix it, right,
Dialogue: 0,0:35:57.00,0:36:01.00,Default,,0000,0000,0000,,that my subsequent to ask it store car with the proper value,
Dialogue: 0,0:36:01.00,0:36:03.00,Default,,0000,0000,0000,,three,
Dialogue: 0,0:36:03.00,0:36:05.00,Default,,0000,0000,0000,,doesn't create a totally new entry.
Dialogue: 0,0:36:05.00,0:36:09.00,Default,,0000,0000,0000,,It has to find the existing entry that already has car and overwrite it.
Dialogue: 0,0:36:09.00,0:36:13.00,Default,,0000,0000,0000,,So the behavior of mad was it could add when it was not previously existing.
Dialogue: 0,0:36:13.00,0:36:16.00,Default,,0000,0000,0000,,It also could be an overwrite of an existing value. So we do need
Dialogue: 0,0:36:16.00,0:36:17.00,Default,,0000,0000,0000,,to find
Dialogue: 0,0:36:17.00,0:36:20.00,Default,,0000,0000,0000,,if there is an entry that already has that key, and just
Dialogue: 0,0:36:20.00,0:36:21.00,Default,,0000,0000,0000,,replace its value
Dialogue: 0,0:36:21.00,0:36:23.00,Default,,0000,0000,0000,,rather than
Dialogue: 0,0:36:23.00,0:36:26.00,Default,,0000,0000,0000,,add a second entry with the same key. So at any given point, right, in this whole
Dialogue: 0,0:36:26.00,0:36:28.00,Default,,0000,0000,0000,,vector, there should be one entry
Dialogue: 0,0:36:28.00,0:36:30.00,Default,,0000,0000,0000,,for each unique key.
Dialogue: 0,0:36:30.00,0:36:33.00,Default,,0000,0000,0000,,So I have to do a search. And
Dialogue: 0,0:36:33.00,0:36:35.00,Default,,0000,0000,0000,,let me
Dialogue: 0,0:36:35.00,0:36:38.00,Default,,0000,0000,0000,,write this code, and then I'm going to mention why I'm going to decompose it in a
Dialogue: 0,0:36:38.00,0:36:39.00,Default,,0000,0000,0000,,second.
Dialogue: 0,0:36:39.00,0:36:42.00,Default,,0000,0000,0000,,If I do entries dot size, I plus plus
Dialogue: 0,0:36:42.00,0:36:44.00,Default,,0000,0000,0000,,then if
Dialogue: 0,0:36:44.00,0:36:49.00,Default,,0000,0000,0000,,entries of I dot key equals key.
Dialogue: 0,0:36:49.00,0:36:51.00,Default,,0000,0000,0000,,Then
Dialogue: 0,0:36:51.00,0:36:52.00,Default,,0000,0000,0000,,let's break. Let me pull out
Dialogue: 0,0:36:52.00,0:37:00.00,Default,,0000,0000,0000,,I so I can get access to it when I'm done. So after this
Dialogue: 0,0:37:00.00,0:37:01.00,Default,,0000,0000,0000,,loop exits,
Dialogue: 0,0:37:01.00,0:37:06.00,Default,,0000,0000,0000,,if I is less than entries dot size,
Dialogue: 0,0:37:06.00,0:37:06.00,Default,,0000,0000,0000,,then
Dialogue: 0,0:37:06.00,0:37:09.00,Default,,0000,0000,0000,,I know that it found a match.
Dialogue: 0,0:37:09.00,0:37:12.00,Default,,0000,0000,0000,,In the case where it went through all of them, and it never hit the break. Then I will
Dialogue: 0,0:37:12.00,0:37:15.00,Default,,0000,0000,0000,,have gone all the way to where it is exactly equal to entries dot size; if it didn't then I
Dialogue: 0,0:37:15.00,0:37:16.00,Default,,0000,0000,0000,,just
Dialogue: 0,0:37:16.00,0:37:19.00,Default,,0000,0000,0000,,have a place to overwrite. And I can say entries of
Dialogue: 0,0:37:19.00,0:37:21.00,Default,,0000,0000,0000,,I dot val
Dialogue: 0,0:37:21.00,0:37:23.00,Default,,0000,0000,0000,,equals val.
Dialogue: 0,0:37:23.00,0:37:27.00,Default,,0000,0000,0000,,Otherwise I go through this process of adding a new one. I had to
Dialogue: 0,0:37:27.00,0:37:30.00,Default,,0000,0000,0000,,go hunt that thing down
Dialogue: 0,0:37:30.00,0:37:33.00,Default,,0000,0000,0000,,and replace it.
Dialogue: 0,0:37:33.00,0:37:35.00,Default,,0000,0000,0000,,That code,
Dialogue: 0,0:37:35.00,0:37:38.00,Default,,0000,0000,0000,,when you look at it, you can say, "Gosh I feel like that code's going to be familiar."
Dialogue: 0,0:37:38.00,0:37:43.00,Default,,0000,0000,0000,,Because that idea of searching to find a match to the key
Dialogue: 0,0:37:43.00,0:37:45.00,Default,,0000,0000,0000,,probably is going to come in really handy
Dialogue: 0,0:37:45.00,0:37:46.00,Default,,0000,0000,0000,,when I need to do get value,
Dialogue: 0,0:37:46.00,0:37:50.00,Default,,0000,0000,0000,,but it has the same exact problem of oh, I've got to go find that match. So in fact,
Dialogue: 0,0:37:50.00,0:37:55.00,Default,,0000,0000,0000,,that kind of motivates the idea of why don't I just take this little piece of code
Dialogue: 0,0:37:55.00,0:37:59.00,Default,,0000,0000,0000,,and separate it out and do a helper that they can both use. I
Dialogue: 0,0:37:59.00,0:38:02.00,Default,,0000,0000,0000,,may not have planned for this from the beginning, but once I see it happening, I might as well fix
Dialogue: 0,0:38:02.00,0:38:05.00,Default,,0000,0000,0000,,it. So I can say find index
Dialogue: 0,0:38:05.00,0:38:07.00,Default,,0000,0000,0000,,for key that
Dialogue: 0,0:38:07.00,0:38:10.00,Default,,0000,0000,0000,,given a key will return to you
Dialogue: 0,0:38:10.00,0:38:11.00,Default,,0000,0000,0000,,
Dialogue: 0,0:38:11.00,0:38:15.00,Default,,0000,0000,0000,,the vector index at which
Dialogue: 0,0:38:15.00,0:38:19.00,Default,,0000,0000,0000,,that key is or a negative one. I don't know if I need to keep that
Dialogue: 0,0:38:19.00,0:38:22.00,Default,,0000,0000,0000,,one anymore.
Dialogue: 0,0:38:22.00,0:38:24.00,Default,,0000,0000,0000,,If it ever found it, it returns I otherwise
Dialogue: 0,0:38:24.00,0:38:28.00,Default,,0000,0000,0000,,it returned negative one. That can be our not found.
Dialogue: 0,0:38:28.00,0:38:37.00,Default,,0000,0000,0000,,I can actually use that up here,
Dialogue: 0,0:38:37.00,0:38:40.00,Default,,0000,0000,0000,,and then I can say, if found
Dialogue: 0,0:38:40.00,0:38:43.00,Default,,0000,0000,0000,,does not equal negative one.
Dialogue: 0,0:38:43.00,0:38:44.00,Default,,0000,0000,0000,,Then we do that,
Dialogue: 0,0:38:44.00,0:38:46.00,Default,,0000,0000,0000,,and then that
Dialogue: 0,0:38:46.00,0:38:48.00,Default,,0000,0000,0000,,tells us that
Dialogue: 0,0:38:48.00,0:38:51.00,Default,,0000,0000,0000,,this little piece of code is going to come in handy right up here,
Dialogue: 0,0:38:51.00,0:38:55.00,Default,,0000,0000,0000,,get value if found does not equal
Dialogue: 0,0:38:55.00,0:38:56.00,Default,,0000,0000,0000,,negative one, then we can return that
Dialogue: 0,0:38:56.00,0:39:02.00,Default,,0000,0000,0000,,and what is the behavior of get value if it didn't find it? Does anybody remember?
Dialogue: 0,0:39:02.00,0:39:06.00,Default,,0000,0000,0000,,I ask it to get the value in this case for lollipop and it's not
Dialogue: 0,0:39:06.00,0:39:07.00,Default,,0000,0000,0000,,there,
Dialogue: 0,0:39:07.00,0:39:13.00,Default,,0000,0000,0000,,does it turn zero, what does it
Dialogue: 0,0:39:13.00,0:39:22.00,Default,,0000,0000,0000,,do? Untracked forget value, remember?
Dialogue: 0,0:39:22.00,0:39:25.00,Default,,0000,0000,0000,,This is an error.
Dialogue: 0,0:39:25.00,0:39:26.00,Default,,0000,0000,0000,,There is not sort of a
Dialogue: 0,0:39:26.00,0:39:30.00,Default,,0000,0000,0000,,general case return value you can produce here
Dialogue: 0,0:39:30.00,0:39:33.00,Default,,0000,0000,0000,,that will really sort of sufficiently describe to someone who's made
Dialogue: 0,0:39:33.00,0:39:37.00,Default,,0000,0000,0000,,this call in error what happened, right? I can't return zero, because it happens to be
Dialogue: 0,0:39:37.00,0:39:40.00,Default,,0000,0000,0000,,that sometimes I?m putting in, and sometimes I'm putting strings or structs
Dialogue: 0,0:39:40.00,0:39:44.00,Default,,0000,0000,0000,,kinds of things. There's no general zero or negative one to use,
Dialogue: 0,0:39:44.00,0:39:47.00,Default,,0000,0000,0000,,so the behavior of get value is if you ask it to retrieve a value for a key, it ought to be
Dialogue: 0,0:39:47.00,0:39:48.00,Default,,0000,0000,0000,,there. So
Dialogue: 0,0:39:48.00,0:39:52.00,Default,,0000,0000,0000,,the corresponding implementation would likely also just go through
Dialogue: 0,0:39:52.00,0:39:56.00,Default,,0000,0000,0000,,the process of contains key, which we call find index for key and check.
Dialogue: 0,0:39:56.00,0:39:58.00,Default,,0000,0000,0000,,It could be used by the client
Dialogue: 0,0:39:58.00,0:40:01.00,Default,,0000,0000,0000,,if they need to know in advance that it's really there.
Dialogue: 0,0:40:01.00,0:40:04.00,Default,,0000,0000,0000,,So let's see how I'm
Dialogue: 0,0:40:04.00,0:40:06.00,Default,,0000,0000,0000,,doing. Let's go back to my
Dialogue: 0,0:40:06.00,0:40:11.00,Default,,0000,0000,0000,,code here,
Dialogue: 0,0:40:11.00,0:40:13.00,Default,,0000,0000,0000,,and this
Dialogue: 0,0:40:13.00,0:40:15.00,Default,,0000,0000,0000,,being
Dialogue: 0,0:40:15.00,0:40:16.00,Default,,0000,0000,0000,,not my specialty,
Dialogue: 0,0:40:16.00,0:40:20.00,Default,,0000,0000,0000,,and just see that I can put something in and
Dialogue: 0,0:40:20.00,0:40:25.00,Default,,0000,0000,0000,,get it back out would be a good first test to see that things are
Dialogue: 0,0:40:25.00,0:40:29.00,Default,,0000,0000,0000,,going as they should. Oh, no it didn't like that. Oh yeah, find
Dialogue: 0,0:40:29.00,0:40:30.00,Default,,0000,0000,0000,,index for key.
Dialogue: 0,0:40:30.00,0:40:32.00,Default,,0000,0000,0000,,Find index for key
Dialogue: 0,0:40:32.00,0:40:34.00,Default,,0000,0000,0000,,was not
Dialogue: 0,0:40:34.00,0:40:38.00,Default,,0000,0000,0000,,populated clear in my dot H, so let me go move it there. I'll put
Dialogue: 0,0:40:38.00,0:40:42.00,Default,,0000,0000,0000,,it in the private section, because I don?t want this to be something that is
Dialogue: 0,0:40:42.00,0:40:45.00,Default,,0000,0000,0000,,exposed outside of the implementation. The idea that there is an index and
Dialogue: 0,0:40:45.00,0:40:48.00,Default,,0000,0000,0000,,there is a vector is not really something that I would want to make part of my
Dialogue: 0,0:40:48.00,0:40:54.00,Default,,0000,0000,0000,,public interface. It's really just an internal detail of how I'm managing stuff.
Dialogue: 0,0:40:54.00,0:40:56.00,Default,,0000,0000,0000,,Something about what I did, oh yeah, I
Dialogue: 0,0:40:56.00,0:41:00.00,Default,,0000,0000,0000,,used the right name for that.
Dialogue: 0,0:41:00.00,0:41:05.00,Default,,0000,0000,0000,,One more case let
Dialogue: 0,0:41:05.00,0:41:06.00,Default,,0000,0000,0000,,me just take a look at them both
Dialogue: 0,0:41:06.00,0:41:09.00,Default,,0000,0000,0000,,before I let the compiler tell me what is and what isn't right about them. Their both
Dialogue: 0,0:41:09.00,0:41:13.00,Default,,0000,0000,0000,,doing find index for key using linear search. If it comes back at not negative one
Dialogue: 0,0:41:13.00,0:41:17.00,Default,,0000,0000,0000,,pulling out the matching value and overriding it, and then in the case of adding
Dialogue: 0,0:41:17.00,0:41:23.00,Default,,0000,0000,0000,,or replacing the error -
Dialogue: 0,0:41:23.00,0:41:24.00,Default,,0000,0000,0000,,so the
Dialogue: 0,0:41:24.00,0:41:26.00,Default,,0000,0000,0000,,previously stored value for that is three,
Dialogue: 0,0:41:26.00,0:41:29.00,Default,,0000,0000,0000,,and if I go and I do one of those tests it's always good to know what
Dialogue: 0,0:41:29.00,0:41:34.00,Default,,0000,0000,0000,,happens if I ask it for something that doesn't exist.
Dialogue: 0,0:41:34.00,0:41:37.00,Default,,0000,0000,0000,,Making sure that the error handling that I put in there does
Dialogue: 0,0:41:37.00,0:41:43.00,Default,,0000,0000,0000,,what it was supposed to do, right? Are
Dialogue: 0,0:41:43.00,0:41:46.00,Default,,0000,0000,0000,,there any questions about the code that I wrote here?
Dialogue: 0,0:41:46.00,0:41:49.00,Default,,0000,0000,0000,,The vector is always kind of a good starting place for these things, because actually it just
Dialogue: 0,0:41:49.00,0:41:53.00,Default,,0000,0000,0000,,tends to use very simple things, and it tends to lend itself to easy code.
Dialogue: 0,0:41:53.00,0:41:57.00,Default,,0000,0000,0000,,But because of vector constraints being at a contiguous back structure, right, there's likely to
Dialogue: 0,0:41:57.00,0:41:59.00,Default,,0000,0000,0000,,be some
Dialogue: 0,0:41:59.00,0:42:01.00,Default,,0000,0000,0000,,performance implication. And in
Dialogue: 0,0:42:01.00,0:42:02.00,Default,,0000,0000,0000,,particular,
Dialogue: 0,0:42:02.00,0:42:04.00,Default,,0000,0000,0000,,in the unsorted case here,
Dialogue: 0,0:42:04.00,0:42:07.00,Default,,0000,0000,0000,,both add and get value
Dialogue: 0,0:42:07.00,0:42:09.00,Default,,0000,0000,0000,,involve doing a linear search.
Dialogue: 0,0:42:09.00,0:42:12.00,Default,,0000,0000,0000,,In some cases it will find it quickly at the very beginning or even half way
Dialogue: 0,0:42:12.00,0:42:13.00,Default,,0000,0000,0000,,through.
Dialogue: 0,0:42:13.00,0:42:17.00,Default,,0000,0000,0000,,In other cases it won't find it at all and have to search through the whole thing. So on
Dialogue: 0,0:42:17.00,0:42:20.00,Default,,0000,0000,0000,,average, if you figure it's equally likely to be in any position or not there at all,
Dialogue: 0,0:42:20.00,0:42:23.00,Default,,0000,0000,0000,,it's at going to at least have to look at half of them or more.
Dialogue: 0,0:42:23.00,0:42:25.00,Default,,0000,0000,0000,,And so we can say they're both linear.
Dialogue: 0,0:42:25.00,0:42:28.00,Default,,0000,0000,0000,,If we change it to be sorted,
Dialogue: 0,0:42:28.00,0:42:31.00,Default,,0000,0000,0000,,which is the first obvious improvement to make here,
Dialogue: 0,0:42:31.00,0:42:34.00,Default,,0000,0000,0000,,then get value
Dialogue: 0,0:42:34.00,0:42:37.00,Default,,0000,0000,0000,,gets a lot faster, because we can take advantage of binary search.
Dialogue: 0,0:42:37.00,0:42:39.00,Default,,0000,0000,0000,,I sort it by key,
Dialogue: 0,0:42:39.00,0:42:43.00,Default,,0000,0000,0000,,so ignoring the value, values are just satellite data. But stored in order of
Dialogue: 0,0:42:43.00,0:42:44.00,Default,,0000,0000,0000,,key,
Dialogue: 0,0:42:44.00,0:42:48.00,Default,,0000,0000,0000,,then all the A words, B words, C words, D words, what not, so
Dialogue: 0,0:42:48.00,0:42:51.00,Default,,0000,0000,0000,,walking it down the middle and seeing which half you look at, then looking at the
Dialogue: 0,0:42:51.00,0:42:53.00,Default,,0000,0000,0000,,quarter of there and the eight of there. It's going to very quickly narrow down on
Dialogue: 0,0:42:53.00,0:42:57.00,Default,,0000,0000,0000,,where it had to be if it was there or if it wasn't there at all.
Dialogue: 0,0:42:57.00,0:43:00.00,Default,,0000,0000,0000,,So we can implement that in logarithmic time, meaning that if you 1,000
Dialogue: 0,0:43:00.00,0:43:04.00,Default,,0000,0000,0000,,entries, it takes ten comparisons to find it or agree that it's not there.
Dialogue: 0,0:43:04.00,0:43:08.00,Default,,0000,0000,0000,,If you double that it will take one more comparison. If
Dialogue: 0,0:43:08.00,0:43:12.00,Default,,0000,0000,0000,,you go to 2,000, negligibly faster, even numbers in the millions
Dialogue: 0,0:43:12.00,0:43:15.00,Default,,0000,0000,0000,,are still just a handful
Dialogue: 0,0:43:15.00,0:43:19.00,Default,,0000,0000,0000,,of comparisons to work it out, and say,
Dialogue: 0,0:43:19.00,0:43:22.00,Default,,0000,0000,0000,,to the twentieth for example is roughly a million; so 20 comparisons in or out,
Dialogue: 0,0:43:22.00,0:43:25.00,Default,,0000,0000,0000,,and so it didn't look at a million things a million times over.
Dialogue: 0,0:43:25.00,0:43:27.00,Default,,0000,0000,0000,,However,
Dialogue: 0,0:43:27.00,0:43:30.00,Default,,0000,0000,0000,,that didn't improve add,
Dialogue: 0,0:43:30.00,0:43:31.00,Default,,0000,0000,0000,,why not?
Dialogue: 0,0:43:31.00,0:43:33.00,Default,,0000,0000,0000,,Why does keeping an assorted order
Dialogue: 0,0:43:33.00,0:43:37.00,Default,,0000,0000,0000,,not have the same boost for add as it did for get value?
Dialogue: 0,0:43:37.00,0:43:46.00,Default,,0000,0000,0000,,Can I do the same logarithmic search? You have to
Dialogue: 0,0:43:46.00,0:43:50.00,Default,,0000,0000,0000,,move all the elements ?
Dialogue: 0,0:43:50.00,0:43:51.00,Default,,0000,0000,0000,,Yeah,
Dialogue: 0,0:43:51.00,0:43:55.00,Default,,0000,0000,0000,,you can find the place fast, right, you can say returning the word
Dialogue: 0,0:43:55.00,0:43:59.00,Default,,0000,0000,0000,,apple it's like oh, okay. I can very quickly narrow in on where it needed to be. If it
Dialogue: 0,0:43:59.00,0:44:02.00,Default,,0000,0000,0000,,was there I could override it quickly, but in the case where it really needed to do
Dialogue: 0,0:44:02.00,0:44:03.00,Default,,0000,0000,0000,,an add,
Dialogue: 0,0:44:03.00,0:44:04.00,Default,,0000,0000,0000,,it's got to move them down.
Dialogue: 0,0:44:04.00,0:44:05.00,Default,,0000,0000,0000,,So the old add
Dialogue: 0,0:44:05.00,0:44:09.00,Default,,0000,0000,0000,,did all its work in the search and then just tacked it on the end if it didn't find
Dialogue: 0,0:44:09.00,0:44:12.00,Default,,0000,0000,0000,,it, or overrode the middle. But the new add
Dialogue: 0,0:44:12.00,0:44:16.00,Default,,0000,0000,0000,,also has to modify the array to put it in the right place, and putting it in the right place means
Dialogue: 0,0:44:16.00,0:44:18.00,Default,,0000,0000,0000,,shuffling to make space.
Dialogue: 0,0:44:18.00,0:44:20.00,Default,,0000,0000,0000,,So even though it found it quickly,
Dialogue: 0,0:44:20.00,0:44:25.00,Default,,0000,0000,0000,,it was unable to update that quickly, so it still ends up being
Dialogue: 0,0:44:25.00,0:44:26.00,Default,,0000,0000,0000,,linear in that case.
Dialogue: 0,0:44:26.00,0:44:29.00,Default,,0000,0000,0000,,Now this actually not a terrible result,
Dialogue: 0,0:44:29.00,0:44:30.00,Default,,0000,0000,0000,,as it stands
Dialogue: 0,0:44:30.00,0:44:33.00,Default,,0000,0000,0000,,it's probably much more likely that you're going to load up the data
Dialogue: 0,0:44:33.00,0:44:36.00,Default,,0000,0000,0000,,structure once and then do a lot
Dialogue: 0,0:44:36.00,0:44:40.00,Default,,0000,0000,0000,,of searches on it, then infrequent additions. That's a pretty common usage
Dialogue: 0,0:44:40.00,0:44:41.00,Default,,0000,0000,0000,,pattern for a map. It's kind of like you
Dialogue: 0,0:44:41.00,0:44:43.00,Default,,0000,0000,0000,,build a dictionary, right,
Dialogue: 0,0:44:43.00,0:44:46.00,Default,,0000,0000,0000,,loading the dictionary once could be expensive, but then people get tons and tons of
Dialogue: 0,0:44:46.00,0:44:49.00,Default,,0000,0000,0000,,look ups of words later. But you don't change the definitions a lot later or add a
Dialogue: 0,0:44:49.00,0:44:51.00,Default,,0000,0000,0000,,lot of new words.
Dialogue: 0,0:44:51.00,0:44:51.00,Default,,0000,0000,0000,,So
Dialogue: 0,0:44:51.00,0:44:56.00,Default,,0000,0000,0000,,this might actually be quite tolerable in many situations
Dialogue: 0,0:44:56.00,0:44:59.00,Default,,0000,0000,0000,,that the building of it was expensive, but it gave
Dialogue: 0,0:44:59.00,0:45:00.00,Default,,0000,0000,0000,,you
Dialogue: 0,0:45:00.00,0:45:02.00,Default,,0000,0000,0000,,fast search access.
Dialogue: 0,0:45:02.00,0:45:05.00,Default,,0000,0000,0000,,But really what you want to do is say, can we get both of those? So driving to say
Dialogue: 0,0:45:05.00,0:45:08.00,Default,,0000,0000,0000,,what we do with the editor buffer, you say, "Well, what if I just want both of those operations
Dialogue: 0,0:45:08.00,0:45:11.00,Default,,0000,0000,0000,,to be logarithmic or better, what can I do?" So
Dialogue: 0,0:45:11.00,0:45:12.00,Default,,0000,0000,0000,,I'll leave you with kind of just
Dialogue: 0,0:45:12.00,0:45:16.00,Default,,0000,0000,0000,,a little bit of a taste of where we're heading.
Dialogue: 0,0:45:16.00,0:45:19.00,Default,,0000,0000,0000,,Just to think a little bit about what the link
Dialogue: 0,0:45:19.00,0:45:21.00,Default,,0000,0000,0000,,list does and doesn't buy us,
Dialogue: 0,0:45:21.00,0:45:24.00,Default,,0000,0000,0000,,right, that the link list gave us flexibility
Dialogue: 0,0:45:24.00,0:45:29.00,Default,,0000,0000,0000,,at the editing, the local editing site, but it doesn't give us fast searching.
Dialogue: 0,0:45:29.00,0:45:31.00,Default,,0000,0000,0000,,Well maybe we can take this link list and try to
Dialogue: 0,0:45:31.00,0:45:33.00,Default,,0000,0000,0000,,add searching
Dialogue: 0,0:45:33.00,0:45:37.00,Default,,0000,0000,0000,,to the idea of this flexibility to kind of get the best of both
Dialogue: 0,0:45:37.00,0:45:41.00,Default,,0000,0000,0000,,worlds. So that's what we're going to start on Monday, building a tree. So if
Dialogue: 0,0:45:41.00,0:45:44.00,Default,,0000,0000,0000,,you have time today, I'd love to have you come to Truman, and otherwise have a good
Dialogue: 0,0:45:44.00,0:45:45.00,Default,,0000,0000,0000,,weekend, and
Dialogue: 0,0:45:45.00,0:45:50.00,Default,,0000,0000,0000,,get your PQ work in.