[Script Info]
Title: 
[Events]
Format: Layer, Start, End, Style, Name, MarginL, MarginR, MarginV, Effect, Text
Dialogue: 0,0:00:00.00,0:00:10.00,Default,,0000,0000,0000,,
Dialogue: 0,0:00:10.00,0:00:11.00,Default,,0000,0000,0000,,
Dialogue: 0,0:00:11.00,0:00:15.00,Default,,0000,0000,0000,,This presentation is delivered by the Stanford Center for Professional
Dialogue: 0,0:00:15.00,0:00:23.00,Default,,0000,0000,0000,,Development.
Dialogue: 0,0:00:23.00,0:00:25.00,Default,,0000,0000,0000,,Hey there! Oh,
Dialogue: 0,0:00:25.00,0:00:29.00,Default,,0000,0000,0000,,we're back. We're back and now we're getting down and dirty. We'll do more pointers, and link
Dialogue: 0,0:00:29.00,0:00:33.00,Default,,0000,0000,0000,,list, and implementations. It's actually going to be like our life for the next
Dialogue: 0,0:00:33.00,0:00:36.00,Default,,0000,0000,0000,,week and half. There's just even more implementation, trying to think about how those
Dialogue: 0,0:00:36.00,0:00:37.00,Default,,0000,0000,0000,,things work on the backside. So
Dialogue: 0,0:00:37.00,0:00:41.00,Default,,0000,0000,0000,,I will do another alternate implementation of the stack today.
Dialogue: 0,0:00:41.00,0:00:44.00,Default,,0000,0000,0000,,So we did one based on vector and we're going to do one based on a link list.
Dialogue: 0,0:00:44.00,0:00:47.00,Default,,0000,0000,0000,,And then I'm going to do a cube based on link list, as well,
Dialogue: 0,0:00:47.00,0:00:48.00,Default,,0000,0000,0000,,to kind of just mix
Dialogue: 0,0:00:48.00,0:00:51.00,Default,,0000,0000,0000,,and match a little bit. And then, we're still at the end of the case study, which the
Dialogue: 0,0:00:51.00,0:00:55.00,Default,,0000,0000,0000,,material is covered in Chapter 9. I probably won't get thorough all of that today. What we
Dialogue: 0,0:00:55.00,0:00:57.00,Default,,0000,0000,0000,,don't finish today we'll be talking about on Friday,
Dialogue: 0,0:00:57.00,0:01:00.00,Default,,0000,0000,0000,,and then we'll go on to start talking about map implementation and look at
Dialogue: 0,0:01:00.00,0:01:02.00,Default,,0000,0000,0000,,binary search trees. How many
Dialogue: 0,0:01:02.00,0:01:05.00,Default,,0000,0000,0000,,people started [inaudible]? How many of
Dialogue: 0,0:01:05.00,0:01:08.00,Default,,0000,0000,0000,,you got somewhere feeling good?
Dialogue: 0,0:01:08.00,0:01:09.00,Default,,0000,0000,0000,,Not just yet. One thing I will
Dialogue: 0,0:01:09.00,0:01:12.00,Default,,0000,0000,0000,,tell you is that there are two implementations you're working on
Dialogue: 0,0:01:12.00,0:01:16.00,Default,,0000,0000,0000,,and I listed them in the order of the one that the material we've seen the most, right.
Dialogue: 0,0:01:16.00,0:01:19.00,Default,,0000,0000,0000,,We've talked about link list more than we have talked about things that are tree and
Dialogue: 0,0:01:19.00,0:01:22.00,Default,,0000,0000,0000,,heat based. So I listed that one first. But, in fact, actually, in terms of difficulty of coding,
Dialogue: 0,0:01:22.00,0:01:27.00,Default,,0000,0000,0000,,I think, the second one is little bit more attractable than the first. So
Dialogue: 0,0:01:27.00,0:01:30.00,Default,,0000,0000,0000,,there's no reason you can't do them in either order if it feels good to you to start on the second one
Dialogue: 0,0:01:30.00,0:01:32.00,Default,,0000,0000,0000,,before you come back to the first one.
Dialogue: 0,0:01:32.00,0:01:35.00,Default,,0000,0000,0000,,Or just trade off between working on them if one of them is giving you fits just look
Dialogue: 0,0:01:35.00,0:01:37.00,Default,,0000,0000,0000,,at the other one to clear your head,
Dialogue: 0,0:01:37.00,0:01:41.00,Default,,0000,0000,0000,,so just a thought about how to approach it. Okay.
Dialogue: 0,0:01:41.00,0:01:46.00,Default,,0000,0000,0000,,So I am going to do some coding. I'm going to come back to my slides in a little bit here.
Dialogue: 0,0:01:46.00,0:01:50.00,Default,,0000,0000,0000,,But to pick up where we left off last time, was we had written a
Dialogue: 0,0:01:50.00,0:01:55.00,Default,,0000,0000,0000,,vector based implementation of the stack
Dialogue: 0,0:01:55.00,0:01:56.00,Default,,0000,0000,0000,,abstraction
Dialogue: 0,0:01:56.00,0:02:01.00,Default,,0000,0000,0000,,and so looking at the main operations here for a stack or push and pop array
Dialogue: 0,0:02:01.00,0:02:04.00,Default,,0000,0000,0000,,that its mechanism here is just to add to the end of the vector that we've
Dialogue: 0,0:02:04.00,0:02:08.00,Default,,0000,0000,0000,,got. So I'm letting the vector handle all the growing, and resizing,
Dialogue: 0,0:02:08.00,0:02:11.00,Default,,0000,0000,0000,,and memory, and manipulations that are needed for that.
Dialogue: 0,0:02:11.00,0:02:14.00,Default,,0000,0000,0000,,And then, when asked to pop one, we just take the one that was last most added,
Dialogue: 0,0:02:14.00,0:02:16.00,Default,,0000,0000,0000,,which will be at the far end of the array.
Dialogue: 0,0:02:16.00,0:02:19.00,Default,,0000,0000,0000,,And so given the way vector behaves, knowing that we know it's a continuous
Dialogue: 0,0:02:19.00,0:02:21.00,Default,,0000,0000,0000,,array based
Dialogue: 0,0:02:21.00,0:02:25.00,Default,,0000,0000,0000,,backing behind it, then we're getting this O of one access to that last element
Dialogue: 0,0:02:25.00,0:02:27.00,Default,,0000,0000,0000,,to either add a new one down there
Dialogue: 0,0:02:27.00,0:02:30.00,Default,,0000,0000,0000,,or to retrieve one and remove it from the end
Dialogue: 0,0:02:30.00,0:02:33.00,Default,,0000,0000,0000,,so that push and pop operations will both being in constant time no matter how many elements are in the
Dialogue: 0,0:02:33.00,0:02:36.00,Default,,0000,0000,0000,,stack, 10, 15, 6 million,
Dialogue: 0,0:02:36.00,0:02:40.00,Default,,0000,0000,0000,,the little bit of work we're doing is affecting only the far end of the array
Dialogue: 0,0:02:40.00,0:02:44.00,Default,,0000,0000,0000,,and not causing the rest of the configured storage to be jostled whatsoever so
Dialogue: 0,0:02:44.00,0:02:46.00,Default,,0000,0000,0000,,pretty easy to get up and running.
Dialogue: 0,0:02:46.00,0:02:50.00,Default,,0000,0000,0000,,So in general, once you have one abstraction you can start leveraging it into
Dialogue: 0,0:02:50.00,0:02:52.00,Default,,0000,0000,0000,,building other attractions and the vector manages a lot of the things that
Dialogue: 0,0:02:52.00,0:02:56.00,Default,,0000,0000,0000,,any array based implementation would need. So rather than using a raw array,
Dialogue: 0,0:02:56.00,0:02:57.00,Default,,0000,0000,0000,,there's very little reason to kind of,
Dialogue: 0,0:02:57.00,0:03:00.00,Default,,0000,0000,0000,,you know, ditch vector and go the straight raw array in this case because all it basically does
Dialogue: 0,0:03:00.00,0:03:03.00,Default,,0000,0000,0000,,it open up opportunities for error and kind of management and
Dialogue: 0,0:03:03.00,0:03:08.00,Default,,0000,0000,0000,,the kind of efficiency you can gain back by removing vectors intermediate
Dialogue: 0,0:03:08.00,0:03:11.00,Default,,0000,0000,0000,,stuff is really not very profound so not worth,
Dialogue: 0,0:03:11.00,0:03:12.00,Default,,0000,0000,0000,,probably,
Dialogue: 0,0:03:12.00,0:03:13.00,Default,,0000,0000,0000,,taking on.
Dialogue: 0,0:03:13.00,0:03:16.00,Default,,0000,0000,0000,,What we do is consider the only link limitation. We had talked about a link
Dialogue: 0,0:03:16.00,0:03:20.00,Default,,0000,0000,0000,,list for a vector and we kind of discarded it as likely not to lead anywhere
Dialogue: 0,0:03:20.00,0:03:21.00,Default,,0000,0000,0000,,interesting.
Dialogue: 0,0:03:21.00,0:03:24.00,Default,,0000,0000,0000,,I actually, am going to fully pursue it for this stack because it actually turns out that a link list
Dialogue: 0,0:03:24.00,0:03:28.00,Default,,0000,0000,0000,,is a good fit for what the behavior that a stack needs in terms of the
Dialogue: 0,0:03:28.00,0:03:29.00,Default,,0000,0000,0000,,manipulations and flexibility.
Dialogue: 0,0:03:29.00,0:03:33.00,Default,,0000,0000,0000,,So if I have a stack of enterers where I push 10, 20, and 30. I'm going to
Dialogue: 0,0:03:33.00,0:03:37.00,Default,,0000,0000,0000,,do that same diagram we did for the vector one as I did for the stack is
Dialogue: 0,0:03:37.00,0:03:38.00,Default,,0000,0000,0000,,
Dialogue: 0,0:03:38.00,0:03:40.00,Default,,0000,0000,0000,,one possibility
Dialogue: 0,0:03:40.00,0:03:42.00,Default,,0000,0000,0000,,is that I put them in the list
Dialogue: 0,0:03:42.00,0:03:47.00,Default,,0000,0000,0000,,in this order.
Dialogue: 0,0:03:47.00,0:03:50.00,Default,,0000,0000,0000,,Another possibility
Dialogue: 0,0:03:50.00,0:03:51.00,Default,,0000,0000,0000,,is that I put them in,
Dialogue: 0,0:03:51.00,0:03:58.00,Default,,0000,0000,0000,,in this order. We'll call this Strategy A; we'll call this Strategy B.
Dialogue: 0,0:03:58.00,0:04:01.00,Default,,0000,0000,0000,,They seem, you know, fairly symmetric, right.
Dialogue: 0,0:04:01.00,0:04:05.00,Default,,0000,0000,0000,,If they're going to be a strong reason that
Dialogue: 0,0:04:05.00,0:04:09.00,Default,,0000,0000,0000,,leaves us to prefer Strategy A over B, or are they just equally
Dialogue: 0,0:04:09.00,0:04:12.00,Default,,0000,0000,0000,,easy to get the things done that we need to do?
Dialogue: 0,0:04:12.00,0:04:16.00,Default,,0000,0000,0000,,Anybody want to make an argument for me.
Dialogue: 0,0:04:16.00,0:04:18.00,Default,,0000,0000,0000,,Help me out. Last in, first out.
Dialogue: 0,0:04:18.00,0:04:22.00,Default,,0000,0000,0000,,Last in, first out.
Dialogue: 0,0:04:22.00,0:04:25.00,Default,,0000,0000,0000,,[Inaudible]. Be careful here. So 10, 20, 30 means the way the stack works is like
Dialogue: 0,0:04:25.00,0:04:26.00,Default,,0000,0000,0000,,this, 10,
Dialogue: 0,0:04:26.00,0:04:28.00,Default,,0000,0000,0000,,20, 30
Dialogue: 0,0:04:28.00,0:04:31.00,Default,,0000,0000,0000,,and so it's at the top that we're interested in, right? Um hm.
Dialogue: 0,0:04:31.00,0:04:34.00,Default,,0000,0000,0000,,That the top is where activity is taking place. Oh.
Dialogue: 0,0:04:34.00,0:04:37.00,Default,,0000,0000,0000,,So we want to be adding things and losing from the top. So do we want to put the top at
Dialogue: 0,0:04:37.00,0:04:41.00,Default,,0000,0000,0000,,the end of our list or at the front of our list?
Dialogue: 0,0:04:41.00,0:04:46.00,Default,,0000,0000,0000,,Which is the easier to access in the link list design? [Inaudible].
Dialogue: 0,0:04:46.00,0:04:48.00,Default,,0000,0000,0000,,The front, right?
Dialogue: 0,0:04:48.00,0:04:52.00,Default,,0000,0000,0000,,So in the array format we prefer this, putting the top of the vector on the far end
Dialogue: 0,0:04:52.00,0:04:54.00,Default,,0000,0000,0000,,because then there is the only jostling of
Dialogue: 0,0:04:54.00,0:04:58.00,Default,,0000,0000,0000,,that. But needing access to the top here in the front is actually going to be the better way to get the link
Dialogue: 0,0:04:58.00,0:05:00.00,Default,,0000,0000,0000,,list strategy
Dialogue: 0,0:05:00.00,0:05:04.00,Default,,0000,0000,0000,,you work in. Let me actually go through both the push and the pop to convince
Dialogue: 0,0:05:04.00,0:05:05.00,Default,,0000,0000,0000,,you why this is true.
Dialogue: 0,0:05:05.00,0:05:09.00,Default,,0000,0000,0000,,So if I have access in the 10, 20, 30 case I could actually keep a separate
Dialogue: 0,0:05:09.00,0:05:12.00,Default,,0000,0000,0000,,additional pointer, one to the front and one to the back. So it could actually
Dialogue: 0,0:05:12.00,0:05:13.00,Default,,0000,0000,0000,,become maintaining at
Dialogue: 0,0:05:13.00,0:05:15.00,Default,,0000,0000,0000,,all times as pointing to the back. If I
Dialogue: 0,0:05:15.00,0:05:19.00,Default,,0000,0000,0000,,did that, right, then subsequent push up to a 40, it's pretty easy to tack on a 40.
Dialogue: 0,0:05:19.00,0:05:20.00,Default,,0000,0000,0000,,So it turns out it would be that
Dialogue: 0,0:05:20.00,0:05:24.00,Default,,0000,0000,0000,,the adding it's the push operation that actually isn't really a problem on this
Dialogue: 0,0:05:24.00,0:05:26.00,Default,,0000,0000,0000,,Strategy A. We can still kind of easily, and over
Dialogue: 0,0:05:26.00,0:05:30.00,Default,,0000,0000,0000,,time, if we have that tail pointer just tack one on to the end. As
Dialogue: 0,0:05:30.00,0:05:32.00,Default,,0000,0000,0000,,for the pop operation,
Dialogue: 0,0:05:32.00,0:05:33.00,Default,,0000,0000,0000,,
Dialogue: 0,0:05:33.00,0:05:34.00,Default,,0000,0000,0000,,if I have to pop that 30,
Dialogue: 0,0:05:34.00,0:05:39.00,Default,,0000,0000,0000,,I need to adjust that tail pointer and move it back a cell. And that's where we
Dialogue: 0,0:05:39.00,0:05:41.00,Default,,0000,0000,0000,,start to get into trouble. If I have a pointer to
Dialogue: 0,0:05:41.00,0:05:45.00,Default,,0000,0000,0000,,the tail cell there is no mechanism in the singly linked list to back
Dialogue: 0,0:05:45.00,0:05:46.00,Default,,0000,0000,0000,,up. If I
Dialogue: 0,0:05:46.00,0:05:48.00,Default,,0000,0000,0000,,say it's time to pop 30,
Dialogue: 0,0:05:48.00,0:05:49.00,Default,,0000,0000,0000,,then I would actually need
Dialogue: 0,0:05:49.00,0:05:52.00,Default,,0000,0000,0000,,to delete the 30, get the value out, but then I need to update this tail pointer to
Dialogue: 0,0:05:52.00,0:05:55.00,Default,,0000,0000,0000,,point to 20, and 30 doesn't know
Dialogue: 0,0:05:55.00,0:05:57.00,Default,,0000,0000,0000,,where 20 is, 30's oblivious about these things.
Dialogue: 0,0:05:57.00,0:06:00.00,Default,,0000,0000,0000,,And so the only way to find 20 in singly linked list would be go back to the very
Dialogue: 0,0:06:00.00,0:06:03.00,Default,,0000,0000,0000,,beginning, walk your way down, and find the one that pointed to the cell you just took out of
Dialogue: 0,0:06:03.00,0:06:05.00,Default,,0000,0000,0000,,the list
Dialogue: 0,0:06:05.00,0:06:08.00,Default,,0000,0000,0000,,and that's going to be an operation we want to avoid.
Dialogue: 0,0:06:08.00,0:06:11.00,Default,,0000,0000,0000,,In the Strategy B case, right, adding a cell, this
Dialogue: 0,0:06:11.00,0:06:15.00,Default,,0000,0000,0000,,means putting a 40 in allocating a new cell and then attaching it,
Dialogue: 0,0:06:15.00,0:06:18.00,Default,,0000,0000,0000,,splicing it in, right between wiring in two pointers, and we can do these links in
Dialogue: 0,0:06:18.00,0:06:19.00,Default,,0000,0000,0000,,constant time,
Dialogue: 0,0:06:19.00,0:06:24.00,Default,,0000,0000,0000,,and then popping one is taking that front row cell off. Easy to get to, easy to update, and
Dialogue: 0,0:06:24.00,0:06:25.00,Default,,0000,0000,0000,,splice out
Dialogue: 0,0:06:25.00,0:06:29.00,Default,,0000,0000,0000,,so no traversal, no extra pointers needed.
Dialogue: 0,0:06:29.00,0:06:31.00,Default,,0000,0000,0000,,The idea that there are,
Dialogue: 0,0:06:31.00,0:06:34.00,Default,,0000,0000,0000,,you know, 100 or 1,000 elements following the one that's on
Dialogue: 0,0:06:34.00,0:06:36.00,Default,,0000,0000,0000,,top is irrelevant. It
Dialogue: 0,0:06:36.00,0:06:38.00,Default,,0000,0000,0000,,doesn't have any impact, whatsoever, on the running time
Dialogue: 0,0:06:38.00,0:06:42.00,Default,,0000,0000,0000,,to access the front, or stuff another front, or taking it on or off the front.
Dialogue: 0,0:06:42.00,0:06:45.00,Default,,0000,0000,0000,,So it is Strategy B
Dialogue: 0,0:06:45.00,0:06:47.00,Default,,0000,0000,0000,,that gives us the best setup when it's
Dialogue: 0,0:06:47.00,0:06:50.00,Default,,0000,0000,0000,,in the back of the linked list.
Dialogue: 0,0:06:50.00,0:06:55.00,Default,,0000,0000,0000,,So let me go ahead and do it. I think it's kind of
Dialogue: 0,0:06:55.00,0:06:58.00,Default,,0000,0000,0000,,good to see. Oh, like, what is it like to just write code and make stuff work.
Dialogue: 0,0:06:58.00,0:07:04.00,Default,,0000,0000,0000,,And so I'm kind of fond of this and you can tell me.
Dialogue: 0,0:07:04.00,0:07:07.00,Default,,0000,0000,0000,,I make a cell C
Dialogue: 0,0:07:07.00,0:07:08.00,Default,,0000,0000,0000,,it has an L type
Dialogue: 0,0:07:08.00,0:07:12.00,Default,,0000,0000,0000,,value and it has a soft T next
Dialogue: 0,0:07:12.00,0:07:15.00,Default,,0000,0000,0000,,right there.
Dialogue: 0,0:07:15.00,0:07:19.00,Default,,0000,0000,0000,,And then I have a pointer to the front linked list cell.
Dialogue: 0,0:07:19.00,0:07:21.00,Default,,0000,0000,0000,,So in addition, you know,
Dialogue: 0,0:07:21.00,0:07:25.00,Default,,0000,0000,0000,,it might that in order to make something like size operate
Dialogue: 0,0:07:25.00,0:07:26.00,Default,,0000,0000,0000,,efficiently,
Dialogue: 0,0:07:26.00,0:07:27.00,Default,,0000,0000,0000,,I might also want to catch the
Dialogue: 0,0:07:27.00,0:07:30.00,Default,,0000,0000,0000,,number of cells that update, or added or renew. I can also decide to
Dialogue: 0,0:07:30.00,0:07:33.00,Default,,0000,0000,0000,,just leave it out for now. Maybe
Dialogue: 0,0:07:33.00,0:07:36.00,Default,,0000,0000,0000,,I'll actually even change this to be the easier function, right, which
Dialogue: 0,0:07:36.00,0:07:38.00,Default,,0000,0000,0000,,is empty form.
Dialogue: 0,0:07:38.00,0:07:40.00,Default,,0000,0000,0000,,That way I don't even have to go down that road
Dialogue: 0,0:07:40.00,0:07:44.00,Default,,0000,0000,0000,,for now.
Dialogue: 0,0:07:44.00,0:07:46.00,Default,,0000,0000,0000,,Go back over here to
Dialogue: 0,0:07:46.00,0:07:49.00,Default,,0000,0000,0000,,this side and I've got to make everything now consistent with what's going on
Dialogue: 0,0:07:49.00,0:07:50.00,Default,,0000,0000,0000,,there.
Dialogue: 0,0:07:50.00,0:07:51.00,Default,,0000,0000,0000,,Okay.
Dialogue: 0,0:07:51.00,0:07:54.00,Default,,0000,0000,0000,,Let's start off with our constructor, which is a good place to make sure you get
Dialogue: 0,0:07:54.00,0:07:56.00,Default,,0000,0000,0000,,into a valid state.
Dialogue: 0,0:07:56.00,0:07:59.00,Default,,0000,0000,0000,,In this case, we're going to use the empty list so the head pointer points and tells us
Dialogue: 0,0:07:59.00,0:08:03.00,Default,,0000,0000,0000,,we have no cells whatsoever in the list. So we don't pre allocate anything,
Dialogue: 0,0:08:03.00,0:08:04.00,Default,,0000,0000,0000,,we don't get ready.
Dialogue: 0,0:08:04.00,0:08:07.00,Default,,0000,0000,0000,,What's kind of nice with this linked list is to allocate on demand
Dialogue: 0,0:08:07.00,0:08:10.00,Default,,0000,0000,0000,,each individual cell that's asked to be added to the list.
Dialogue: 0,0:08:10.00,0:08:13.00,Default,,0000,0000,0000,,The delete operation actually does show we need to do some work. I'm actually not
Dialogue: 0,0:08:13.00,0:08:15.00,Default,,0000,0000,0000,,going to implement it but I'm going to mention here that I would need to delete the
Dialogue: 0,0:08:15.00,0:08:16.00,Default,,0000,0000,0000,,entire list,
Dialogue: 0,0:08:16.00,0:08:19.00,Default,,0000,0000,0000,,which would involve, either iterates or recursion my way down to kind of
Dialogue: 0,0:08:19.00,0:08:21.00,Default,,0000,0000,0000,,do all the work.
Dialogue: 0,0:08:21.00,0:08:25.00,Default,,0000,0000,0000,,And then I changed this from size to iterate.
Dialogue: 0,0:08:25.00,0:08:28.00,Default,,0000,0000,0000,,I'd like to know if my list is empty.
Dialogue: 0,0:08:28.00,0:08:30.00,Default,,0000,0000,0000,,So I can just test for head
Dialogue: 0,0:08:30.00,0:08:33.00,Default,,0000,0000,0000,,is equal, equal
Dialogue: 0,0:08:33.00,0:08:36.00,Default,,0000,0000,0000,,to null. If it's null we have no list. Let
Dialogue: 0,0:08:36.00,0:08:41.00,Default,,0000,0000,0000,,me work on push before I work on pop. I'll
Dialogue: 0,0:08:41.00,0:08:45.00,Default,,0000,0000,0000,,turn them around. The push operation is, make myself a new cell. All
Dialogue: 0,0:08:45.00,0:08:47.00,Default,,0000,0000,0000,,right, let's go through the steps for that. New
Dialogue: 0,0:08:47.00,0:08:50.00,Default,,0000,0000,0000,,cell equals new cell
Dialogue: 0,0:08:50.00,0:08:54.00,Default,,0000,0000,0000,,T. [Inaudible] the size to hold a value
Dialogue: 0,0:08:54.00,0:08:56.00,Default,,0000,0000,0000,,and an X link. I'm going to set
Dialogue: 0,0:08:56.00,0:08:59.00,Default,,0000,0000,0000,,the new styles val to be the
Dialogue: 0,0:08:59.00,0:09:01.00,Default,,0000,0000,0000,,perimeter that came in.
Dialogue: 0,0:09:01.00,0:09:05.00,Default,,0000,0000,0000,,And now, I'm going to splice this guy onto the front of my list.
Dialogue: 0,0:09:05.00,0:09:10.00,Default,,0000,0000,0000,,So the outgoing pointer I'm doing first to the new cell is allocated and
Dialogue: 0,0:09:10.00,0:09:15.00,Default,,0000,0000,0000,,leads to what was previously the front row cell.
Dialogue: 0,0:09:15.00,0:09:19.00,Default,,0000,0000,0000,,And then it is now updated to point to this
Dialogue: 0,0:09:19.00,0:09:21.00,Default,,0000,0000,0000,,one. We've got pointer wired, one value
Dialogue: 0,0:09:21.00,0:09:23.00,Default,,0000,0000,0000,,assigned, and we've got a new
Dialogue: 0,0:09:23.00,0:09:28.00,Default,,0000,0000,0000,,cell on the front. The
Dialogue: 0,0:09:28.00,0:09:29.00,Default,,0000,0000,0000,,inverse of that,
Dialogue: 0,0:09:29.00,0:09:32.00,Default,,0000,0000,0000,,taking something off my list, I'm going to need
Dialogue: 0,0:09:32.00,0:09:35.00,Default,,0000,0000,0000,,to kind of detach that front row cell, delete its memory, get its value, things like
Dialogue: 0,0:09:35.00,0:09:38.00,Default,,0000,0000,0000,,that. So the error checking is still the same at the very beginning. Like, if I've
Dialogue: 0,0:09:38.00,0:09:41.00,Default,,0000,0000,0000,,got an empty staff I want to be sure I don't just kind of do reference no
Dialogue: 0,0:09:41.00,0:09:42.00,Default,,0000,0000,0000,,and get into
Dialogue: 0,0:09:42.00,0:09:48.00,Default,,0000,0000,0000,,some bad situations. So I report that error back using error, which will halt the program
Dialogue: 0,0:09:48.00,0:09:49.00,Default,,0000,0000,0000,,there.
Dialogue: 0,0:09:49.00,0:09:51.00,Default,,0000,0000,0000,,Otherwise, right,
Dialogue: 0,0:09:51.00,0:09:52.00,Default,,0000,0000,0000,,the element on
Dialogue: 0,0:09:52.00,0:09:57.00,Default,,0000,0000,0000,,top is the one that's in the value field of the head cell. So knowing that head's
Dialogue: 0,0:09:57.00,0:09:59.00,Default,,0000,0000,0000,,null is a safety reference to do there.
Dialogue: 0,0:09:59.00,0:10:03.00,Default,,0000,0000,0000,,And then I'm going to go ahead and
Dialogue: 0,0:10:03.00,0:10:06.00,Default,,0000,0000,0000,,get a hold of what that thing is and I'm
Dialogue: 0,0:10:06.00,0:10:09.00,Default,,0000,0000,0000,,going update
Dialogue: 0,0:10:09.00,0:10:13.00,Default,,0000,0000,0000,,the head to point to the cell after it. So splicing it out
Dialogue: 0,0:10:13.00,0:10:14.00,Default,,0000,0000,0000,,
Dialogue: 0,0:10:14.00,0:10:17.00,Default,,0000,0000,0000,,and then deleting the
Dialogue: 0,0:10:17.00,0:10:20.00,Default,,0000,0000,0000,,old cell.
Dialogue: 0,0:10:20.00,0:10:23.00,Default,,0000,0000,0000,,Just take a look at these. Once we start doing
Dialogue: 0,0:10:23.00,0:10:25.00,Default,,0000,0000,0000,,pointers, right, there's just opportunities for error.
Dialogue: 0,0:10:25.00,0:10:28.00,Default,,0000,0000,0000,,I feel kind of good about what I did here but I am going to just do a little bit of
Dialogue: 0,0:10:28.00,0:10:30.00,Default,,0000,0000,0000,,tracing to kind of
Dialogue: 0,0:10:30.00,0:10:33.00,Default,,0000,0000,0000,,confirm for myself that the most likely situations that get you in trouble with link list is you'll
Dialogue: 0,0:10:33.00,0:10:36.00,Default,,0000,0000,0000,,handle the mainstream case but somehow forget one of the edge
Dialogue: 0,0:10:36.00,0:10:40.00,Default,,0000,0000,0000,,cases. Such as, what if the list was totally empty or just had a single cell?
Dialogue: 0,0:10:40.00,0:10:43.00,Default,,0000,0000,0000,,Is there some special case handling that needs to be dealt with?
Dialogue: 0,0:10:43.00,0:10:45.00,Default,,0000,0000,0000,,So if I think about it in terms of the push case,
Dialogue: 0,0:10:45.00,0:10:48.00,Default,,0000,0000,0000,,you know, I might say, well, if there's an existing set of cells,
Dialogue: 0,0:10:48.00,0:10:50.00,Default,,0000,0000,0000,,so we're using Strategy B here, let me
Dialogue: 0,0:10:50.00,0:10:54.00,Default,,0000,0000,0000,,erase A so I know what I'm looking at,
Dialogue: 0,0:10:54.00,0:10:58.00,Default,,0000,0000,0000,,that its head is currently pointing to a set of cells, right, that my
Dialogue: 0,0:10:58.00,0:11:00.00,Default,,0000,0000,0000,,allocation of the new cell out here,
Dialogue: 0,0:11:00.00,0:11:02.00,Default,,0000,0000,0000,,right, assigning its value,
Dialogue: 0,0:11:02.00,0:11:07.00,Default,,0000,0000,0000,,assigning its next field to be where head points two, and then sending head to
Dialogue: 0,0:11:07.00,0:11:08.00,Default,,0000,0000,0000,,this new guy, it
Dialogue: 0,0:11:08.00,0:11:10.00,Default,,0000,0000,0000,,looks to be good.
Dialogue: 0,0:11:10.00,0:11:14.00,Default,,0000,0000,0000,,If I also do that tracing on the - what if the list that we were looking at was
Dialogue: 0,0:11:14.00,0:11:17.00,Default,,0000,0000,0000,,just null to begin with.
Dialogue: 0,0:11:17.00,0:11:20.00,Default,,0000,0000,0000,,So there were no cells in there. This is the very first cell. It isn't going to have any kind of trouble
Dialogue: 0,0:11:20.00,0:11:24.00,Default,,0000,0000,0000,,stumbling over this case. So I would allocate that new cell 40, assign
Dialogue: 0,0:11:24.00,0:11:25.00,Default,,0000,0000,0000,,its value.
Dialogue: 0,0:11:25.00,0:11:28.00,Default,,0000,0000,0000,,Set the next field to be what head is, so that just basically sets the
Dialogue: 0,0:11:28.00,0:11:32.00,Default,,0000,0000,0000,,trail coming out of 40 to be null and then updates the head there. So we've
Dialogue: 0,0:11:32.00,0:11:35.00,Default,,0000,0000,0000,,produced a single linked list, right, with one cell.
Dialogue: 0,0:11:35.00,0:11:37.00,Default,,0000,0000,0000,,It looks like
Dialogue: 0,0:11:37.00,0:11:39.00,Default,,0000,0000,0000,,we're doing okay on the push behaviors.
Dialogue: 0,0:11:39.00,0:11:43.00,Default,,0000,0000,0000,,Now, the pop behavior, in this sort of case may be relevant to think about, if it's
Dialogue: 0,0:11:43.00,0:11:46.00,Default,,0000,0000,0000,,totally empty. All right, we come in and we've got an empty cell,
Dialogue: 0,0:11:46.00,0:11:49.00,Default,,0000,0000,0000,,then the empty test should cause it to error and get down to the rest of the
Dialogue: 0,0:11:49.00,0:11:50.00,Default,,0000,0000,0000,,code.
Dialogue: 0,0:11:50.00,0:11:52.00,Default,,0000,0000,0000,,Let's say that B points to
Dialogue: 0,0:11:52.00,0:11:55.00,Default,,0000,0000,0000,,some sequence of things, 30, 20,
Dialogue: 0,0:11:55.00,0:11:56.00,Default,,0000,0000,0000,,10,
Dialogue: 0,0:11:56.00,0:12:02.00,Default,,0000,0000,0000,,that
Dialogue: 0,0:12:02.00,0:12:05.00,Default,,0000,0000,0000,,taking the head value off and kind of writing it down somewhere, saying, okay,
Dialogue: 0,0:12:05.00,0:12:07.00,Default,,0000,0000,0000,,30 was the top value.
Dialogue: 0,0:12:07.00,0:12:10.00,Default,,0000,0000,0000,,The old cell is currently the head so we're
Dialogue: 0,0:12:10.00,0:12:13.00,Default,,0000,0000,0000,,keeping a temporary on this thing.
Dialogue: 0,0:12:13.00,0:12:17.00,Default,,0000,0000,0000,,And then head equals head error next,
Dialogue: 0,0:12:17.00,0:12:19.00,Default,,0000,0000,0000,,which splices out
Dialogue: 0,0:12:19.00,0:12:23.00,Default,,0000,0000,0000,,the cell around so we no longer have a pointer into this 30. The only place
Dialogue: 0,0:12:23.00,0:12:27.00,Default,,0000,0000,0000,,we can get back to it is with this temporary variable we assigned right here of old
Dialogue: 0,0:12:27.00,0:12:30.00,Default,,0000,0000,0000,,and then we delete that
Dialogue: 0,0:12:30.00,0:12:31.00,Default,,0000,0000,0000,,old to reclaim that storage
Dialogue: 0,0:12:31.00,0:12:33.00,Default,,0000,0000,0000,,and then our list now is
Dialogue: 0,0:12:33.00,0:12:37.00,Default,,0000,0000,0000,,the values 20 and 10, which followed it later in the list. To, also,
Dialogue: 0,0:12:37.00,0:12:41.00,Default,,0000,0000,0000,,do a little check what if it was the very last cell
Dialogue: 0,0:12:41.00,0:12:44.00,Default,,0000,0000,0000,,in the list that we're trying to pop? Does that
Dialogue: 0,0:12:44.00,0:12:46.00,Default,,0000,0000,0000,,have any special handling that we have overlooked
Dialogue: 0,0:12:46.00,0:12:50.00,Default,,0000,0000,0000,,if we just have a ten here with a null after it? I'll go
Dialogue: 0,0:12:50.00,0:12:55.00,Default,,0000,0000,0000,,through the process of writing down the ten.
Dialogue: 0,0:12:55.00,0:12:59.00,Default,,0000,0000,0000,,Assigning old to where head is,
Dialogue: 0,0:12:59.00,0:13:05.00,Default,,0000,0000,0000,,and assigning head-to-head error next, where head error of next cell is null
Dialogue: 0,0:13:05.00,0:13:08.00,Default,,0000,0000,0000,,but pointing to that, and then we set our list to null, and then we delete this cell. And so after
Dialogue: 0,0:13:08.00,0:13:11.00,Default,,0000,0000,0000,,we're done, right, we have the empty list again, the
Dialogue: 0,0:13:11.00,0:13:12.00,Default,,0000,0000,0000,,head pointer back to null.
Dialogue: 0,0:13:12.00,0:13:16.00,Default,,0000,0000,0000,,So it seems like we're doing pretty good job. Have a bunch of cells. Have one cell.
Dialogue: 0,0:13:16.00,0:13:25.00,Default,,0000,0000,0000,,No cells. Different things kind of seem to be going through here doing the right thing. Let's do it. A little bit
Dialogue: 0,0:13:25.00,0:13:34.00,Default,,0000,0000,0000,,of code on this side. [Inaudible]. Okay. Pop empty cell. I've
Dialogue: 0,0:13:34.00,0:13:37.00,Default,,0000,0000,0000,,got that. Oh,
Dialogue: 0,0:13:37.00,0:13:40.00,Default,,0000,0000,0000,,I think I may have proved, oh, it deliberately makes the error, in
Dialogue: 0,0:13:40.00,0:13:41.00,Default,,0000,0000,0000,,fact.
Dialogue: 0,0:13:41.00,0:13:43.00,Default,,0000,0000,0000,,That it
Dialogue: 0,0:13:43.00,0:13:48.00,Default,,0000,0000,0000,,was designed to test on that. [Inaudible] up
Dialogue: 0,0:13:48.00,0:13:52.00,Default,,0000,0000,0000,,to the end. So let's
Dialogue: 0,0:13:52.00,0:13:54.00,Default,,0000,0000,0000,,
Dialogue: 0,0:13:54.00,0:13:57.00,Default,,0000,0000,0000,,see if
Dialogue: 0,0:13:57.00,0:14:03.00,Default,,0000,0000,0000,,we get back a three, two, one out of this guy. Okay. So
Dialogue: 0,0:14:03.00,0:14:08.00,Default,,0000,0000,0000,,we manage to do okay even on that.
Dialogue: 0,0:14:08.00,0:14:10.00,Default,,0000,0000,0000,,So looking at this piece of code, all
Dialogue: 0,0:14:10.00,0:14:14.00,Default,,0000,0000,0000,,right, the two operations we're most interested in, push and pop, right,
Dialogue: 0,0:14:14.00,0:14:19.00,Default,,0000,0000,0000,,are each oh of one, right. The number of elements out there, right, aren't
Dialogue: 0,0:14:19.00,0:14:21.00,Default,,0000,0000,0000,,changing anything about its performance. It does a little bit of
Dialogue: 0,0:14:21.00,0:14:23.00,Default,,0000,0000,0000,,imagination and a little bit of pointer arrangement up here to the front to
Dialogue: 0,0:14:23.00,0:14:24.00,Default,,0000,0000,0000,,the end
Dialogue: 0,0:14:24.00,0:14:28.00,Default,,0000,0000,0000,,and so it has a very nice tight allocation strategy, too, which is appealing relative
Dialogue: 0,0:14:28.00,0:14:29.00,Default,,0000,0000,0000,,to what
Dialogue: 0,0:14:29.00,0:14:33.00,Default,,0000,0000,0000,,the vector-based strategy was doing. It's like, now, it's doing things in advance on our behalf like
Dialogue: 0,0:14:33.00,0:14:36.00,Default,,0000,0000,0000,,extending our capacity so that every now and then we had some
Dialogue: 0,0:14:36.00,0:14:39.00,Default,,0000,0000,0000,,little glitch right when you were doing that big resize operation that happened infrequently,
Dialogue: 0,0:14:39.00,0:14:41.00,Default,,0000,0000,0000,,you won't have that same
Dialogue: 0,0:14:41.00,0:14:44.00,Default,,0000,0000,0000,,concern with this one because it does exactly what it needs at any given
Dialogue: 0,0:14:44.00,0:14:47.00,Default,,0000,0000,0000,,time, which is allocate a single cell, deletes a single cell,
Dialogue: 0,0:14:47.00,0:14:51.00,Default,,0000,0000,0000,,and also keeping the allocation very tidy in that way. So they'll both
Dialogue: 0,0:14:51.00,0:14:54.00,Default,,0000,0000,0000,,end of being oh of one. And both of these are
Dialogue: 0,0:14:54.00,0:14:58.00,Default,,0000,0000,0000,,commonly used viable strategies for how a stack is implemented. Right. Depending on the,
Dialogue: 0,0:14:58.00,0:14:59.00,Default,,0000,0000,0000,,
Dialogue: 0,0:14:59.00,0:15:02.00,Default,,0000,0000,0000,,you know, just the inclination of the program or they may have decided
Dialogue: 0,0:15:02.00,0:15:05.00,Default,,0000,0000,0000,,one way was the way to go versus another
Dialogue: 0,0:15:05.00,0:15:07.00,Default,,0000,0000,0000,,that
Dialogue: 0,0:15:07.00,0:15:09.00,Default,,0000,0000,0000,,you will see both used in common practice because there really isn't
Dialogue: 0,0:15:09.00,0:15:12.00,Default,,0000,0000,0000,,one of them that's obviously better or obviously worse, right.
Dialogue: 0,0:15:12.00,0:15:16.00,Default,,0000,0000,0000,,Now, this uses a little bit more memory per cell, but then you have excess capacity
Dialogue: 0,0:15:16.00,0:15:21.00,Default,,0000,0000,0000,,and vector has excess capacity but no overhead per cell.
Dialogue: 0,0:15:21.00,0:15:23.00,Default,,0000,0000,0000,,There's a few other things to kind of think about trading off. You say, well, the code,
Dialogue: 0,0:15:23.00,0:15:27.00,Default,,0000,0000,0000,,itself, is a little harder to write if you're using only [inaudible].
Dialogue: 0,0:15:27.00,0:15:30.00,Default,,0000,0000,0000,,That means it's a little bit more error prone
Dialogue: 0,0:15:30.00,0:15:33.00,Default,,0000,0000,0000,,and more likely, you'll make a mistake and have to do debug your way through it and the way with the
Dialogue: 0,0:15:33.00,0:15:35.00,Default,,0000,0000,0000,,vector it was pretty easy to get without tearing out your
Dialogue: 0,0:15:35.00,0:15:36.00,Default,,0000,0000,0000,,hair. Now, if
Dialogue: 0,0:15:36.00,0:15:40.00,Default,,0000,0000,0000,,we can
Dialogue: 0,0:15:40.00,0:15:42.00,Default,,0000,0000,0000,,do
Dialogue: 0,0:15:42.00,0:15:44.00,Default,,0000,0000,0000,,stack and queue that fast -
Dialogue: 0,0:15:44.00,0:15:45.00,Default,,0000,0000,0000,,I mean, stack that fast, then you figure queue
Dialogue: 0,0:15:45.00,0:15:47.00,Default,,0000,0000,0000,,must be
Dialogue: 0,0:15:47.00,0:15:51.00,Default,,0000,0000,0000,,not so crazy either. Let me
Dialogue: 0,0:15:51.00,0:15:59.00,Default,,0000,0000,0000,,draw you a picture of queue.
Dialogue: 0,0:15:59.00,0:16:02.00,Default,,0000,0000,0000,,Okay.
Dialogue: 0,0:16:02.00,0:16:08.00,Default,,0000,0000,0000,,I've got my
Dialogue: 0,0:16:08.00,0:16:12.00,Default,,0000,0000,0000,,queue and I can use the
Dialogue: 0,0:16:12.00,0:16:14.00,Default,,0000,0000,0000,,End queue operation on it to put in a 10, to put
Dialogue: 0,0:16:14.00,0:16:16.00,Default,,0000,0000,0000,,in a 20, to put in a 30.
Dialogue: 0,0:16:16.00,0:16:18.00,Default,,0000,0000,0000,,And
Dialogue: 0,0:16:18.00,0:16:20.00,Default,,0000,0000,0000,,I'm going to try and get back out what was
Dialogue: 0,0:16:20.00,0:16:23.00,Default,,0000,0000,0000,,front most.
Dialogue: 0,0:16:23.00,0:16:25.00,Default,,0000,0000,0000,,Okay. So queue is FIFO, first in
Dialogue: 0,0:16:25.00,0:16:27.00,Default,,0000,0000,0000,,first out,
Dialogue: 0,0:16:27.00,0:16:30.00,Default,,0000,0000,0000,,and waiting in line, whoever's been in the queue longest is the first one to come
Dialogue: 0,0:16:30.00,0:16:31.00,Default,,0000,0000,0000,,out,
Dialogue: 0,0:16:31.00,0:16:33.00,Default,,0000,0000,0000,,very fair handling of things.
Dialogue: 0,0:16:33.00,0:16:37.00,Default,,0000,0000,0000,,And so if were to think about this in terms of let's go straight across the
Dialogue: 0,0:16:37.00,0:16:39.00,Default,,0000,0000,0000,,linked list. We just got our head around the link list with the stack. Let's see if there's a link list for the
Dialogue: 0,0:16:39.00,0:16:40.00,Default,,0000,0000,0000,,queue
Dialogue: 0,0:16:40.00,0:16:44.00,Default,,0000,0000,0000,,provide the same kind of easy access to the things we need to do the work.
Dialogue: 0,0:16:44.00,0:16:48.00,Default,,0000,0000,0000,,So it seems like the
Dialogue: 0,0:16:48.00,0:16:51.00,Default,,0000,0000,0000,,two strategies that we looked at for stack
Dialogue: 0,0:16:51.00,0:16:55.00,Default,,0000,0000,0000,,are probably the same two to look at for this one, right, which we go in the front
Dialogue: 0,0:16:55.00,0:16:57.00,Default,,0000,0000,0000,,ways orders. I mean the front of the queue accessible
Dialogue: 0,0:16:57.00,0:17:01.00,Default,,0000,0000,0000,,in there and reversing our way down to the tail
Dialogue: 0,0:17:01.00,0:17:05.00,Default,,0000,0000,0000,,or the other way around. Right. I mean, the tail of the queue up
Dialogue: 0,0:17:05.00,0:17:09.00,Default,,0000,0000,0000,,here in the front
Dialogue: 0,0:17:09.00,0:17:15.00,Default,,0000,0000,0000,,leading the way to the head of the queue. So this is head - I'll call it
Dialogue: 0,0:17:15.00,0:17:17.00,Default,,0000,0000,0000,,front of queue,
Dialogue: 0,0:17:17.00,0:17:20.00,Default,,0000,0000,0000,,and this is back,
Dialogue: 0,0:17:20.00,0:17:24.00,Default,,0000,0000,0000,,this is the back
Dialogue: 0,0:17:24.00,0:17:27.00,Default,,0000,0000,0000,,and that's the front. Okay. So that will be GA that will be GB. But first off,
Dialogue: 0,0:17:27.00,0:17:29.00,Default,,0000,0000,0000,,ask yourself,
Dialogue: 0,0:17:29.00,0:17:30.00,Default,,0000,0000,0000,,where does the queue do its work?
Dialogue: 0,0:17:30.00,0:17:38.00,Default,,0000,0000,0000,,Does it do it at the front or does it do it at the back?
Dialogue: 0,0:17:38.00,0:17:41.00,Default,,0000,0000,0000,,It does it at both.
Dialogue: 0,0:17:41.00,0:17:44.00,Default,,0000,0000,0000,,But when you're end queuing, right, you're manipulating the back of the queue, adding
Dialogue: 0,0:17:44.00,0:17:47.00,Default,,0000,0000,0000,,something to the tail end of the line. When
Dialogue: 0,0:17:47.00,0:17:51.00,Default,,0000,0000,0000,,you are de queuing, you're adding something to the front of the queue. So like unlike the stack where both the
Dialogue: 0,0:17:51.00,0:17:53.00,Default,,0000,0000,0000,,actions were happening in the same place, and that kind of unified your thinking
Dialogue: 0,0:17:53.00,0:17:56.00,Default,,0000,0000,0000,,about where to
Dialogue: 0,0:17:56.00,0:17:57.00,Default,,0000,0000,0000,,allow for that,
Dialogue: 0,0:17:57.00,0:18:00.00,Default,,0000,0000,0000,,you know, easy access to the top, the one thing the stack cared
Dialogue: 0,0:18:00.00,0:18:03.00,Default,,0000,0000,0000,,about, but the bottom of the stack, right, was, you know,
Dialogue: 0,0:18:03.00,0:18:04.00,Default,,0000,0000,0000,,buried and it didn't matter.
Dialogue: 0,0:18:04.00,0:18:06.00,Default,,0000,0000,0000,,The queue actually needs accesses to both.
Dialogue: 0,0:18:06.00,0:18:07.00,Default,,0000,0000,0000,,So that
Dialogue: 0,0:18:07.00,0:18:10.00,Default,,0000,0000,0000,,sort of sounds like that both these strategies, right, have the potential to be
Dialogue: 0,0:18:10.00,0:18:14.00,Default,,0000,0000,0000,,trouble for us. Because it's like in the link list form, right, you know the idea that
Dialogue: 0,0:18:14.00,0:18:17.00,Default,,0000,0000,0000,,access to the head is easy, access to the tail that is a little bit more tricky.
Dialogue: 0,0:18:17.00,0:18:20.00,Default,,0000,0000,0000,,Now, I said we could add a tail pointer. And maybe that's actually going to be part of the
Dialogue: 0,0:18:20.00,0:18:22.00,Default,,0000,0000,0000,,answer to this, right,
Dialogue: 0,0:18:22.00,0:18:26.00,Default,,0000,0000,0000,,but as it is, with no head pointers in here, that adding an item to A would
Dialogue: 0,0:18:26.00,0:18:30.00,Default,,0000,0000,0000,,involve traversing that queue to find the end to put a new one on.
Dialogue: 0,0:18:30.00,0:18:34.00,Default,,0000,0000,0000,,Similarly, if indeed, the inverse operation is going to be our trouble, which
Dialogue: 0,0:18:34.00,0:18:38.00,Default,,0000,0000,0000,,is de queuing, we have to kind of walk its way down to find the last element
Dialogue: 0,0:18:38.00,0:18:41.00,Default,,0000,0000,0000,,in the link list ordering, which is [inaudible] queue.
Dialogue: 0,0:18:41.00,0:18:43.00,Default,,0000,0000,0000,,So what say we add a
Dialogue: 0,0:18:43.00,0:18:44.00,Default,,0000,0000,0000,,tail pointer in both cases? So we
Dialogue: 0,0:18:44.00,0:18:46.00,Default,,0000,0000,0000,,have a head that
Dialogue: 0,0:18:46.00,0:18:48.00,Default,,0000,0000,0000,,points to here and a tail that points to there, it's
Dialogue: 0,0:18:48.00,0:18:50.00,Default,,0000,0000,0000,,like that will make our
Dialogue: 0,0:18:50.00,0:18:53.00,Default,,0000,0000,0000,,problem a little bit easier to deal with. So
Dialogue: 0,0:18:53.00,0:18:55.00,Default,,0000,0000,0000,,let me look at B first.
Dialogue: 0,0:18:55.00,0:18:58.00,Default,,0000,0000,0000,,That adding to the back of the queue is easy. We saw how we did that with the stack,
Dialogue: 0,0:18:58.00,0:18:59.00,Default,,0000,0000,0000,,right, so that
Dialogue: 0,0:18:59.00,0:19:01.00,Default,,0000,0000,0000,,the End queue
Dialogue: 0,0:19:01.00,0:19:05.00,Default,,0000,0000,0000,,operation doesn't need that tail pointer and it already kind of wasn't a problem for us.
Dialogue: 0,0:19:05.00,0:19:08.00,Default,,0000,0000,0000,,Now, the D queue operation would mean, okay, using our tail pointer to know where the
Dialogue: 0,0:19:08.00,0:19:11.00,Default,,0000,0000,0000,,last close value is tells us it's ten.
Dialogue: 0,0:19:11.00,0:19:14.00,Default,,0000,0000,0000,,But we have the same problem I had pointed out with the stack, which is,
Dialogue: 0,0:19:14.00,0:19:18.00,Default,,0000,0000,0000,,we can get to this value, we can return this value, you know, we can delete this
Dialogue: 0,0:19:18.00,0:19:23.00,Default,,0000,0000,0000,,cell, but what we need to do, also, in the operation, update our tail pointer so a
Dialogue: 0,0:19:23.00,0:19:25.00,Default,,0000,0000,0000,,subsequent D queue can do its work efficiently.
Dialogue: 0,0:19:25.00,0:19:28.00,Default,,0000,0000,0000,,And it's that backing up of the tail pointer that
Dialogue: 0,0:19:28.00,0:19:29.00,Default,,0000,0000,0000,,is the sticky point
Dialogue: 0,0:19:29.00,0:19:33.00,Default,,0000,0000,0000,,that given that ten doesn't know who points into it, the single link list if very
Dialogue: 0,0:19:33.00,0:19:35.00,Default,,0000,0000,0000,,asymmetric that way.
Dialogue: 0,0:19:35.00,0:19:37.00,Default,,0000,0000,0000,,But you only know what's follows you, not what proceeds,
Dialogue: 0,0:19:37.00,0:19:40.00,Default,,0000,0000,0000,,but backing up this pointer is not easy. It
Dialogue: 0,0:19:40.00,0:19:44.00,Default,,0000,0000,0000,,involves the reversal of going back to the beginning, walking your way down to find somebody who
Dialogue: 0,0:19:44.00,0:19:46.00,Default,,0000,0000,0000,,points to the last [inaudible].
Dialogue: 0,0:19:46.00,0:19:50.00,Default,,0000,0000,0000,,So it seems like this tail pointer didn't buy us a lot. It helped a little bit, you know,
Dialogue: 0,0:19:50.00,0:19:53.00,Default,,0000,0000,0000,,to get some of the operation up and running, but in the end, keeping and maintaining
Dialogue: 0,0:19:53.00,0:19:56.00,Default,,0000,0000,0000,,that tail pointer sort of came back to bite us.
Dialogue: 0,0:19:56.00,0:19:58.00,Default,,0000,0000,0000,,In the case of the Strategy A,
Dialogue: 0,0:19:58.00,0:20:02.00,Default,,0000,0000,0000,,the tail pointer gives us immediate access to the back, which we're going to need for
Dialogue: 0,0:20:02.00,0:20:05.00,Default,,0000,0000,0000,,the end queue. If I go to end queue of 40, in this case,
Dialogue: 0,0:20:05.00,0:20:10.00,Default,,0000,0000,0000,,then what I'm going to need to do is make a new cell, attach it off of the
Dialogue: 0,0:20:10.00,0:20:11.00,Default,,0000,0000,0000,,current cell,
Dialogue: 0,0:20:11.00,0:20:13.00,Default,,0000,0000,0000,,and then update the tail,
Dialogue: 0,0:20:13.00,0:20:17.00,Default,,0000,0000,0000,,right, to point to that cell while that update's moving forward down the list,
Dialogue: 0,0:20:17.00,0:20:20.00,Default,,0000,0000,0000,,right. If you're on the third cell and you add a fourth cell, you need to move the tail
Dialogue: 0,0:20:20.00,0:20:24.00,Default,,0000,0000,0000,,from the third to the fourth. Moving that direction's easy. It's the backing
Dialogue: 0,0:20:24.00,0:20:27.00,Default,,0000,0000,0000,,up where we got into trouble. So in fact, this
Dialogue: 0,0:20:27.00,0:20:31.00,Default,,0000,0000,0000,,suggests that Strategy A is the one we can make both these operations
Dialogue: 0,0:20:31.00,0:20:33.00,Default,,0000,0000,0000,,manipulate in constant time in a way
Dialogue: 0,0:20:33.00,0:20:35.00,Default,,0000,0000,0000,,that this one got
Dialogue: 0,0:20:35.00,0:20:37.00,Default,,0000,0000,0000,,us into trouble.
Dialogue: 0,0:20:37.00,0:20:41.00,Default,,0000,0000,0000,,I think we can do it.
Dialogue: 0,0:20:41.00,0:20:44.00,Default,,0000,0000,0000,,Let's switch it over. I've got an
Dialogue: 0,0:20:44.00,0:20:49.00,Default,,0000,0000,0000,,empty queue here.
Dialogue: 0,0:20:49.00,0:20:53.00,Default,,0000,0000,0000,,Also, it is empty in size. This is the same problem with size, which is either you have to go count them
Dialogue: 0,0:20:53.00,0:20:55.00,Default,,0000,0000,0000,,or you have to
Dialogue: 0,0:20:55.00,0:20:55.00,Default,,0000,0000,0000,,
Dialogue: 0,0:20:55.00,0:20:57.00,Default,,0000,0000,0000,,cache the size.
Dialogue: 0,0:20:57.00,0:21:01.00,Default,,0000,0000,0000,,I will build the same exactly structure, in fact.
Dialogue: 0,0:21:01.00,0:21:11.00,Default,,0000,0000,0000,,Now, I'll type
Dialogue: 0,0:21:11.00,0:21:12.00,Default,,0000,0000,0000,,next. It's going to have both a
Dialogue: 0,0:21:12.00,0:21:14.00,Default,,0000,0000,0000,,head and a tail pointer
Dialogue: 0,0:21:14.00,0:21:18.00,Default,,0000,0000,0000,,so we can keep track of the two ends we've got going. I think I'm
Dialogue: 0,0:21:18.00,0:21:24.00,Default,,0000,0000,0000,,missing my [inaudible]. Slip over.
Dialogue: 0,0:21:24.00,0:21:29.00,Default,,0000,0000,0000,,Okay. And
Dialogue: 0,0:21:29.00,0:21:32.00,Default,,0000,0000,0000,,then I will make the same comment here about, yeah, you need to delete all cells.
Dialogue: 0,0:21:32.00,0:21:34.00,Default,,0000,0000,0000,,So I set the head and the tail to null. I'm
Dialogue: 0,0:21:34.00,0:21:41.00,Default,,0000,0000,0000,,now in my empty state that tells me I've got nothing in the queue, nothing at all, so far. And
Dialogue: 0,0:21:41.00,0:21:48.00,Default,,0000,0000,0000,,my Y is empty. Oh.
Dialogue: 0,0:21:48.00,0:21:50.00,Default,,0000,0000,0000,,We'll check that
Dialogue: 0,0:21:50.00,0:21:53.00,Default,,0000,0000,0000,,return equals, equals null, just like
Dialogue: 0,0:21:53.00,0:21:54.00,Default,,0000,0000,0000,,it did. In fact, it looks a lot like
Dialogue: 0,0:21:54.00,0:21:55.00,Default,,0000,0000,0000,,the stack, actually.
Dialogue: 0,0:21:55.00,0:21:59.00,Default,,0000,0000,0000,,And here I'm going to show you something kind of funny. If I go take
Dialogue: 0,0:21:59.00,0:22:04.00,Default,,0000,0000,0000,,my stack CCPs pop.
Dialogue: 0,0:22:04.00,0:22:08.00,Default,,0000,0000,0000,,So if you remember what pop did over here, is it took the front most cell off the
Dialogue: 0,0:22:08.00,0:22:11.00,Default,,0000,0000,0000,,list. And
Dialogue: 0,0:22:11.00,0:22:12.00,Default,,0000,0000,0000,,in the case of the queue
Dialogue: 0,0:22:12.00,0:22:16.00,Default,,0000,0000,0000,,that was the
Dialogue: 0,0:22:16.00,0:22:18.00,Default,,0000,0000,0000,,popping operation. And
Dialogue: 0,0:22:18.00,0:22:21.00,Default,,0000,0000,0000,,it turns out the D queue
Dialogue: 0,0:22:21.00,0:22:25.00,Default,,0000,0000,0000,,operation is exactly the same.
Dialogue: 0,0:22:25.00,0:22:29.00,Default,,0000,0000,0000,,If we're empty, right, then we want to raise there. Otherwise, we take the head's
Dialogue: 0,0:22:29.00,0:22:29.00,Default,,0000,0000,0000,,value.
Dialogue: 0,0:22:29.00,0:22:33.00,Default,,0000,0000,0000,,We move around the head, we delete the old memory. So it's not
Dialogue: 0,0:22:33.00,0:22:36.00,Default,,0000,0000,0000,,actually the top element. I should, actually, be a little bit more
Dialogue: 0,0:22:36.00,0:22:39.00,Default,,0000,0000,0000,,careful about my copying and pasting here. I could really call that
Dialogue: 0,0:22:39.00,0:22:41.00,Default,,0000,0000,0000,,front. It's the front-most element on the top.
Dialogue: 0,0:22:41.00,0:22:43.00,Default,,0000,0000,0000,,But it's like the exact same mechanics work
Dialogue: 0,0:22:43.00,0:22:48.00,Default,,0000,0000,0000,,to take a cell off the front in that way. Well, that's sort of
Dialogue: 0,0:22:48.00,0:22:48.00,Default,,0000,0000,0000,,nice.
Dialogue: 0,0:22:48.00,0:22:51.00,Default,,0000,0000,0000,,And it's like, yeah, well, since I have some code around I want to go try it.
Dialogue: 0,0:22:51.00,0:22:55.00,Default,,0000,0000,0000,,My stack, also, kind of does some things useful in push that I might be able to use. It's not
Dialogue: 0,0:22:55.00,0:22:58.00,Default,,0000,0000,0000,,exactly the same because it's adding it to the front, but it is
Dialogue: 0,0:22:58.00,0:23:00.00,Default,,0000,0000,0000,,setting up a new cell. So I'm going to
Dialogue: 0,0:23:00.00,0:23:05.00,Default,,0000,0000,0000,,make a new cell and I set its value. Then, it's attaching
Dialogue: 0,0:23:05.00,0:23:07.00,Default,,0000,0000,0000,,looks a little different. Let's take a look.
Dialogue: 0,0:23:07.00,0:23:11.00,Default,,0000,0000,0000,,We omitted a cell, copied the value in,
Dialogue: 0,0:23:11.00,0:23:16.00,Default,,0000,0000,0000,,now the goal is giving our pointer to the tail, we want to attach onto the tail.
Dialogue: 0,0:23:16.00,0:23:22.00,Default,,0000,0000,0000,,So we know that it's always going to have a next of null, the new cell. So no
Dialogue: 0,0:23:22.00,0:23:23.00,Default,,0000,0000,0000,,matter what,
Dialogue: 0,0:23:23.00,0:23:26.00,Default,,0000,0000,0000,,it will be the new last cell and it defiantly needs that value that tells
Dialogue: 0,0:23:26.00,0:23:28.00,Default,,0000,0000,0000,,us we're at the end of the list.
Dialogue: 0,0:23:28.00,0:23:32.00,Default,,0000,0000,0000,,And then we have to attach it to our tail. I'm going to write this code first and it's going to be
Dialogue: 0,0:23:32.00,0:23:35.00,Default,,0000,0000,0000,,wrong. So just go along with me in this case.
Dialogue: 0,0:23:35.00,0:23:37.00,Default,,0000,0000,0000,,If the tail's next is the new cell.
Dialogue: 0,0:23:37.00,0:23:40.00,Default,,0000,0000,0000,,So if I'm wiring in the pointer from the tail onto the cell we have
Dialogue: 0,0:23:40.00,0:23:41.00,Default,,0000,0000,0000,,there,
Dialogue: 0,0:23:41.00,0:23:48.00,Default,,0000,0000,0000,,and then we want to update the tail to point to the cell. So
Dialogue: 0,0:23:48.00,0:23:48.00,Default,,0000,0000,0000,,almost,
Dialogue: 0,0:23:48.00,0:23:53.00,Default,,0000,0000,0000,,but not quite, everything I need to do.
Dialogue: 0,0:23:53.00,0:23:56.00,Default,,0000,0000,0000,,Someone want to point out to me what it is I have failed
Dialogue: 0,0:23:56.00,0:24:05.00,Default,,0000,0000,0000,,to consider in this situation. [Inaudible].
Dialogue: 0,0:24:05.00,0:24:09.00,Default,,0000,0000,0000,,It's the what? [Inaudible]. Yeah. ? trying to make null point to something [inaudible]. Exactly. So if my queue is totally empty. So in these cases like
Dialogue: 0,0:24:09.00,0:24:12.00,Default,,0000,0000,0000,,- one thing you can often think about whenever you see yourself with this
Dialogue: 0,0:24:12.00,0:24:15.00,Default,,0000,0000,0000,,error, and you're dereferencing something, you have to considered, well, is there a possibility
Dialogue: 0,0:24:15.00,0:24:20.00,Default,,0000,0000,0000,,that that value is null. And if so I'd better do something
Dialogue: 0,0:24:20.00,0:24:23.00,Default,,0000,0000,0000,,to protect against it. So in the case of the new cell here, I'm setting aside and
Dialogue: 0,0:24:23.00,0:24:27.00,Default,,0000,0000,0000,,not clearing that cell. We know it's valid, [inaudible], we've got good memory.
Dialogue: 0,0:24:27.00,0:24:30.00,Default,,0000,0000,0000,,That part's good but the access to the tail, and that's assuming
Dialogue: 0,0:24:30.00,0:24:34.00,Default,,0000,0000,0000,,there is a tail, that there is at least one cell already in the queue that the tail
Dialogue: 0,0:24:34.00,0:24:35.00,Default,,0000,0000,0000,,is pointing to.
Dialogue: 0,0:24:35.00,0:24:37.00,Default,,0000,0000,0000,,When that's not true,
Dialogue: 0,0:24:37.00,0:24:39.00,Default,,0000,0000,0000,,this is going to blow up. It's going to try to dereference it.
Dialogue: 0,0:24:39.00,0:24:43.00,Default,,0000,0000,0000,,So what we can do here is we can just check for that. We can say
Dialogue: 0,0:24:43.00,0:24:45.00,Default,,0000,0000,0000,,if the queue is empty
Dialogue: 0,0:24:45.00,0:24:48.00,Default,,0000,0000,0000,,then
Dialogue: 0,0:24:48.00,0:24:50.00,Default,,0000,0000,0000,,what we want to do is say that head
Dialogue: 0,0:24:50.00,0:24:53.00,Default,,0000,0000,0000,,equals tail equals new
Dialogue: 0,0:24:53.00,0:24:54.00,Default,,0000,0000,0000,,cell.
Dialogue: 0,0:24:54.00,0:25:00.00,Default,,0000,0000,0000,,Otherwise, we've got some existing tail and we
Dialogue: 0,0:25:00.00,0:25:02.00,Default,,0000,0000,0000,,just need to attach to it.
Dialogue: 0,0:25:02.00,0:25:05.00,Default,,0000,0000,0000,,Now, this is what I meant about that often there are little bit
Dialogue: 0,0:25:05.00,0:25:10.00,Default,,0000,0000,0000,,of special cases for certain
Dialogue: 0,0:25:10.00,0:25:12.00,Default,,0000,0000,0000,,different inputs. In particular, the most common ones are
Dialogue: 0,0:25:12.00,0:25:16.00,Default,,0000,0000,0000,,an empty list or a single link list being distinguished from a list that has
Dialogue: 0,0:25:16.00,0:25:20.00,Default,,0000,0000,0000,,two or more elements. So sometimes it's all about - a single link list has problems and
Dialogue: 0,0:25:20.00,0:25:23.00,Default,,0000,0000,0000,,so does the empty list. In this case, it's exactly the empty list. Like a
Dialogue: 0,0:25:23.00,0:25:27.00,Default,,0000,0000,0000,,single cell is actually fine, you know, one, ten, 6,000
Dialogue: 0,0:25:27.00,0:25:31.00,Default,,0000,0000,0000,,all work equally well. It's that empty case that we have to work on
Dialogue: 0,0:25:31.00,0:25:36.00,Default,,0000,0000,0000,,setting our head and tail to that. So with
Dialogue: 0,0:25:36.00,0:25:38.00,Default,,0000,0000,0000,,this plan we go back to my
Dialogue: 0,0:25:38.00,0:25:40.00,Default,,0000,0000,0000,,use of this. And
Dialogue: 0,0:25:40.00,0:25:47.00,Default,,0000,0000,0000,,stop talking about my stack and change into my queue,
Dialogue: 0,0:25:47.00,0:25:56.00,Default,,0000,0000,0000,,end queuing instead
Dialogue: 0,0:25:56.00,0:25:58.00,Default,,0000,0000,0000,,of pushing. [Inaudible]. Oh, 591 errors.
Dialogue: 0,0:25:58.00,0:26:01.00,Default,,0000,0000,0000,,Well,
Dialogue: 0,0:26:01.00,0:26:15.00,Default,,0000,0000,0000,,that's really - 591, what is that? [Inaudible].
Dialogue: 0,0:26:15.00,0:26:17.00,Default,,0000,0000,0000,,Oh, yeah, this is the year I was going
Dialogue: 0,0:26:17.00,0:26:20.00,Default,,0000,0000,0000,,to talk about but I
Dialogue: 0,0:26:20.00,0:26:23.00,Default,,0000,0000,0000,,failed to do.
Dialogue: 0,0:26:23.00,0:26:26.00,Default,,0000,0000,0000,,So this is the kind of thing you'll get
Dialogue: 0,0:26:26.00,0:26:30.00,Default,,0000,0000,0000,,from failing to protect your [inaudible] from
Dialogue: 0,0:26:30.00,0:26:31.00,Default,,0000,0000,0000,,being revisited.
Dialogue: 0,0:26:31.00,0:26:33.00,Default,,0000,0000,0000,,And so I'll
Dialogue: 0,0:26:33.00,0:26:36.00,Default,,0000,0000,0000,,be - if I haven't deft this
Dialogue: 0,0:26:36.00,0:26:39.00,Default,,0000,0000,0000,,funny little symbol I just made up then I want to find it in the
Dialogue: 0,0:26:39.00,0:26:42.00,Default,,0000,0000,0000,,end deft. So if it came back around and it saw this same header file, it was
Dialogue: 0,0:26:42.00,0:26:45.00,Default,,0000,0000,0000,,supposed to say I already seen that symbol and I won't do it. But, in fact, I had
Dialogue: 0,0:26:45.00,0:26:47.00,Default,,0000,0000,0000,,accidentally named one of them
Dialogue: 0,0:26:47.00,0:26:50.00,Default,,0000,0000,0000,,with a capital H and one with a lowercase H. It says if this symbol's not been
Dialogue: 0,0:26:50.00,0:26:53.00,Default,,0000,0000,0000,,identified then define this other symbol and keep going. And so the next time it saw
Dialogue: 0,0:26:53.00,0:26:57.00,Default,,0000,0000,0000,,the header files it said if that this lowercase H hasn't been
Dialogue: 0,0:26:57.00,0:27:00.00,Default,,0000,0000,0000,,defined, well it hadn't so it made it again and then it kept doing that until it got really
Dialogue: 0,0:27:00.00,0:27:03.00,Default,,0000,0000,0000,,totally twisted up about it. So I will
Dialogue: 0,0:27:03.00,0:27:06.00,Default,,0000,0000,0000,,make them match, with any
Dialogue: 0,0:27:06.00,0:27:07.00,Default,,0000,0000,0000,,luck,
Dialogue: 0,0:27:07.00,0:27:11.00,Default,,0000,0000,0000,,without the caps lock on. Three times is a charm.
Dialogue: 0,0:27:11.00,0:27:12.00,Default,,0000,0000,0000,,And then one, two, three
Dialogue: 0,0:27:12.00,0:27:21.00,Default,,0000,0000,0000,,pop out the other side of queue, as I was hoping. Okay.
Dialogue: 0,0:27:21.00,0:27:24.00,Default,,0000,0000,0000,,So you know what I'm going to do, actually? I'm actually not going
Dialogue: 0,0:27:24.00,0:27:27.00,Default,,0000,0000,0000,,to go through the alternate implementation of queue. I'm just saying
Dialogue: 0,0:27:27.00,0:27:30.00,Default,,0000,0000,0000,,like given that it works so well for stack, right, to have this kind of
Dialogue: 0,0:27:30.00,0:27:34.00,Default,,0000,0000,0000,,single link list, you know, efficient allocation, it's not surprising that queue,
Dialogue: 0,0:27:34.00,0:27:35.00,Default,,0000,0000,0000,,like, given to us. And what
Dialogue: 0,0:27:35.00,0:27:37.00,Default,,0000,0000,0000,,this is, like I said earlier, I said, well,
Dialogue: 0,0:27:37.00,0:27:41.00,Default,,0000,0000,0000,,you know you can do things with vector, you can do things with
Dialogue: 0,0:27:41.00,0:27:44.00,Default,,0000,0000,0000,,stack, anything you do with stack you can do with vector if you were just being
Dialogue: 0,0:27:44.00,0:27:48.00,Default,,0000,0000,0000,,careful. Right. The pushing, and popping, and the queue D queue, are operations that you could express
Dialogue: 0,0:27:48.00,0:27:52.00,Default,,0000,0000,0000,,in other terms of vector adds and removes and inserts that things.
Dialogue: 0,0:27:52.00,0:27:55.00,Default,,0000,0000,0000,,But one of the nice things about providing a structure like a stack or queue is it says
Dialogue: 0,0:27:55.00,0:27:58.00,Default,,0000,0000,0000,,these are the only things you're allowed to add at this end, remove from that end,
Dialogue: 0,0:27:58.00,0:28:02.00,Default,,0000,0000,0000,,it gives you options as a implementer that don't make sense for the general
Dialogue: 0,0:28:02.00,0:28:06.00,Default,,0000,0000,0000,,purpose case. That the vector as a link list had some compromises
Dialogue: 0,0:28:06.00,0:28:10.00,Default,,0000,0000,0000,,that probably weren't worth making. But in the case of stack and queue it actually came out
Dialogue: 0,0:28:10.00,0:28:13.00,Default,,0000,0000,0000,,very cleanly and very nicely, like this tidy little access to one end, or the
Dialogue: 0,0:28:13.00,0:28:15.00,Default,,0000,0000,0000,,other end, or both, right,
Dialogue: 0,0:28:15.00,0:28:17.00,Default,,0000,0000,0000,,was easily managed with a link list and then it didn't have any of the constraints of
Dialogue: 0,0:28:17.00,0:28:20.00,Default,,0000,0000,0000,,the continuous memory to fight with.
Dialogue: 0,0:28:20.00,0:28:21.00,Default,,0000,0000,0000,,And so often having a structure
Dialogue: 0,0:28:21.00,0:28:25.00,Default,,0000,0000,0000,,that actually offers less gives you some different options as an
Dialogue: 0,0:28:25.00,0:28:28.00,Default,,0000,0000,0000,,implementer because you know you don't have to support access into the middle in
Dialogue: 0,0:28:28.00,0:28:31.00,Default,,0000,0000,0000,,an efficient way because
Dialogue: 0,0:28:31.00,0:28:33.00,Default,,0000,0000,0000,,the stack and queue don't let you. They don't let you riffle through the
Dialogue: 0,0:28:33.00,0:28:35.00,Default,,0000,0000,0000,,middle of the stack or the queue to do things
Dialogue: 0,0:28:35.00,0:28:38.00,Default,,0000,0000,0000,,and that gives you some freedom as an implementer, which is neat to take advantage
Dialogue: 0,0:28:38.00,0:28:43.00,Default,,0000,0000,0000,,of. Yes, sir. [Inaudible] in Java
Dialogue: 0,0:28:43.00,0:28:55.00,Default,,0000,0000,0000,,that, you know, we supposed to use an Array whenever we could because Array uses more
Dialogue: 0,0:28:55.00,0:29:00.00,Default,,0000,0000,0000,,memory ? Um hm. Does the queue
Dialogue: 0,0:29:00.00,0:29:03.00,Default,,0000,0000,0000,,and stack use more memory than an Array, for example? So typically they'll be about the same, because of exactly this one thing, which is it allocates tightly so it asks for one cell per entry that's in there, right. And that cell has this overhead in the form of this extra pointer.
Dialogue: 0,0:29:03.00,0:29:06.00,Default,,0000,0000,0000,,Right. So in effect it means that everything got a little bit bigger because
Dialogue: 0,0:29:06.00,0:29:08.00,Default,,0000,0000,0000,,everything's carrying a little overhead.
Dialogue: 0,0:29:08.00,0:29:11.00,Default,,0000,0000,0000,,Okay. So there's a little bit more memory. The thing the Array is doing is it tends to be
Dialogue: 0,0:29:11.00,0:29:15.00,Default,,0000,0000,0000,,allocating extra slots that aren't being used. So it's not usually tightly allocated
Dialogue: 0,0:29:15.00,0:29:18.00,Default,,0000,0000,0000,,either. So in any given situation it could be as much as twice as big
Dialogue: 0,0:29:18.00,0:29:19.00,Default,,0000,0000,0000,,because it had that extra space.
Dialogue: 0,0:29:19.00,0:29:22.00,Default,,0000,0000,0000,,So kind of in the tradeoff they tend to be in the same
Dialogue: 0,0:29:22.00,0:29:25.00,Default,,0000,0000,0000,,general range. This one has about twice the space, I think it's about four
Dialogue: 0,0:29:25.00,0:29:28.00,Default,,0000,0000,0000,,bites it has a four-byte pointer. The thing's much bigger
Dialogue: 0,0:29:28.00,0:29:30.00,Default,,0000,0000,0000,,and it turns out actually this four bite pointer might be a smaller percentage of
Dialogue: 0,0:29:30.00,0:29:35.00,Default,,0000,0000,0000,,the overhead and will be a larger amount of the capacity in the excess case.
Dialogue: 0,0:29:35.00,0:29:37.00,Default,,0000,0000,0000,,So for a lot of things they're going to be about the same range. And then there's
Dialogue: 0,0:29:37.00,0:29:40.00,Default,,0000,0000,0000,,a few isolated situations where,
Dialogue: 0,0:29:40.00,0:29:43.00,Default,,0000,0000,0000,,yeah, if you have very big things being stored having a lot of excess capacity
Dialogue: 0,0:29:43.00,0:29:45.00,Default,,0000,0000,0000,,is likely to be a more expensive
Dialogue: 0,0:29:45.00,0:29:48.00,Default,,0000,0000,0000,,part of the vector strategy than the link list. But the
Dialogue: 0,0:29:48.00,0:29:51.00,Default,,0000,0000,0000,,link list does have this built in overhead for every element.
Dialogue: 0,0:29:51.00,0:29:54.00,Default,,0000,0000,0000,,And so it's not the case where you would say right off the bat,
Dialogue: 0,0:29:54.00,0:29:55.00,Default,,0000,0000,0000,,well,
Dialogue: 0,0:29:55.00,0:29:58.00,Default,,0000,0000,0000,,definitely an array over link list because that the allocation space.
Dialogue: 0,0:29:58.00,0:30:01.00,Default,,0000,0000,0000,,It's like, hey, you have to think about the whole picture.
Dialogue: 0,0:30:01.00,0:30:05.00,Default,,0000,0000,0000,,That is going to be the whole next lectures. Well, you
Dialogue: 0,0:30:05.00,0:30:06.00,Default,,0000,0000,0000,,know, it's about tradeoffs.
Dialogue: 0,0:30:06.00,0:30:09.00,Default,,0000,0000,0000,,It's not that one strategy's always going to be
Dialogue: 0,0:30:09.00,0:30:12.00,Default,,0000,0000,0000,,the clearly better one. If it is, then we don't need to think about
Dialogue: 0,0:30:12.00,0:30:14.00,Default,,0000,0000,0000,,anything else. There are times when
Dialogue: 0,0:30:14.00,0:30:16.00,Default,,0000,0000,0000,,you know
Dialogue: 0,0:30:16.00,0:30:16.00,Default,,0000,0000,0000,,
Dialogue: 0,0:30:16.00,0:30:19.00,Default,,0000,0000,0000,,that one is just great and there's no reason to think about anything else. And then
Dialogue: 0,0:30:19.00,0:30:20.00,Default,,0000,0000,0000,,there's other times when
Dialogue: 0,0:30:20.00,0:30:24.00,Default,,0000,0000,0000,,there are reasons to think about different ways to solve the same problem.
Dialogue: 0,0:30:24.00,0:30:26.00,Default,,0000,0000,0000,,So let me
Dialogue: 0,0:30:26.00,0:30:27.00,Default,,0000,0000,0000,,propose a case study
Dialogue: 0,0:30:27.00,0:30:31.00,Default,,0000,0000,0000,,that has some
Dialogue: 0,0:30:31.00,0:30:34.00,Default,,0000,0000,0000,,meat. You may think along the way, but you're going to really have to pretend that
Dialogue: 0,0:30:34.00,0:30:38.00,Default,,0000,0000,0000,,this is going to be relevant at first because it's going to seem like you've been
Dialogue: 0,0:30:38.00,0:30:41.00,Default,,0000,0000,0000,,transferred back to
Dialogue: 0,0:30:41.00,0:30:44.00,Default,,0000,0000,0000,,1970, which was a very bad year, long before you born.
Dialogue: 0,0:30:44.00,0:30:49.00,Default,,0000,0000,0000,,I want you to think about the idea of a text setter. So Microsoft Word,
Dialogue: 0,0:30:49.00,0:30:50.00,Default,,0000,0000,0000,,or
Dialogue: 0,0:30:50.00,0:30:53.00,Default,,0000,0000,0000,,you know your email send window, or
Dialogue: 0,0:30:53.00,0:30:57.00,Default,,0000,0000,0000,,BB edit, or X code. All these things, right, have some backing of
Dialogue: 0,0:30:57.00,0:31:00.00,Default,,0000,0000,0000,,what usually is called a buffer,
Dialogue: 0,0:31:00.00,0:31:02.00,Default,,0000,0000,0000,,a buffer, sort of a funny word, right,
Dialogue: 0,0:31:02.00,0:31:06.00,Default,,0000,0000,0000,,but a buffer of characters behind it.
Dialogue: 0,0:31:06.00,0:31:07.00,Default,,0000,0000,0000,,Okay. And that buffer
Dialogue: 0,0:31:07.00,0:31:11.00,Default,,0000,0000,0000,,is used as the kind of document storage for all the characters
Dialogue: 0,0:31:11.00,0:31:12.00,Default,,0000,0000,0000,,
Dialogue: 0,0:31:12.00,0:31:15.00,Default,,0000,0000,0000,,that you're editing and moving around. As you kind of bop around and move around there's
Dialogue: 0,0:31:15.00,0:31:19.00,Default,,0000,0000,0000,,something often called the cursor where you type characters
Dialogue: 0,0:31:19.00,0:31:21.00,Default,,0000,0000,0000,,and characters get moved as you insert.
Dialogue: 0,0:31:21.00,0:31:25.00,Default,,0000,0000,0000,,You can select things, and delete them, and cut, copy, and paste, and all that sort of stuff.
Dialogue: 0,0:31:25.00,0:31:28.00,Default,,0000,0000,0000,,So what does that data structure look like? What is the kind of thing that wants to
Dialogue: 0,0:31:28.00,0:31:29.00,Default,,0000,0000,0000,,back
Dialogue: 0,0:31:29.00,0:31:30.00,Default,,0000,0000,0000,,a buffer?
Dialogue: 0,0:31:30.00,0:31:33.00,Default,,0000,0000,0000,,What kinds of things are important in that
Dialogue: 0,0:31:33.00,0:31:35.00,Default,,0000,0000,0000,,context to be able to support
Dialogue: 0,0:31:35.00,0:31:40.00,Default,,0000,0000,0000,,and what operations needs to be optimized for that tool to field [inaudible]?
Dialogue: 0,0:31:40.00,0:31:44.00,Default,,0000,0000,0000,,So what we're going to look at is a real simplification kind of taking that problem, kind of
Dialogue: 0,0:31:44.00,0:31:48.00,Default,,0000,0000,0000,,distilling it down to its essences and looking at just six operations that are kind
Dialogue: 0,0:31:48.00,0:31:50.00,Default,,0000,0000,0000,,of at the core of any text editor
Dialogue: 0,0:31:50.00,0:31:54.00,Default,,0000,0000,0000,,about moving the cursor forward and backwards with these commands.
Dialogue: 0,0:31:54.00,0:31:57.00,Default,,0000,0000,0000,,Jumping to the front and the back of the entire buffer and then inserting and
Dialogue: 0,0:31:57.00,0:32:00.00,Default,,0000,0000,0000,,deleting in relative to the cursor
Dialogue: 0,0:32:00.00,0:32:01.00,Default,,0000,0000,0000,,within that buffer.
Dialogue: 0,0:32:01.00,0:32:04.00,Default,,0000,0000,0000,,And we're going to do this with an extremely old school interface that's
Dialogue: 0,0:32:04.00,0:32:08.00,Default,,0000,0000,0000,,actually command base. It's like VI comes back from the dead for those of you who
Dialogue: 0,0:32:08.00,0:32:11.00,Default,,0000,0000,0000,,have ever heard of such things as VI and E Max.
Dialogue: 0,0:32:11.00,0:32:13.00,Default,,0000,0000,0000,,And so we're going to look at this because there's actually a lot of ways
Dialogue: 0,0:32:13.00,0:32:15.00,Default,,0000,0000,0000,,you can approach that,
Dialogue: 0,0:32:15.00,0:32:18.00,Default,,0000,0000,0000,,that take advantage of some of the things that we've already built like the vector, and stacking queue,
Dialogue: 0,0:32:18.00,0:32:21.00,Default,,0000,0000,0000,,and the link list. And sort of think about what
Dialogue: 0,0:32:21.00,0:32:24.00,Default,,0000,0000,0000,,kind of options play out well.
Dialogue: 0,0:32:24.00,0:32:28.00,Default,,0000,0000,0000,,What I'm going to show you first off is just what the tool looks like
Dialogue: 0,0:32:28.00,0:32:31.00,Default,,0000,0000,0000,,so you can really feel
Dialogue: 0,0:32:31.00,0:32:33.00,Default,,0000,0000,0000,,schooled in the old way of doing things.
Dialogue: 0,0:32:33.00,0:32:34.00,Default,,0000,0000,0000,,So I insert
Dialogue: 0,0:32:34.00,0:32:38.00,Default,,0000,0000,0000,,the characters A, B, C, D, E, F, G into the editor.
Dialogue: 0,0:32:38.00,0:32:41.00,Default,,0000,0000,0000,,And then I can use the command B to backup.
Dialogue: 0,0:32:41.00,0:32:44.00,Default,,0000,0000,0000,,I can use the command J to jump to the beginning, E to jump to the end,
Dialogue: 0,0:32:44.00,0:32:46.00,Default,,0000,0000,0000,,and so F and B,
Dialogue: 0,0:32:46.00,0:32:50.00,Default,,0000,0000,0000,,B moving me backwards, F moving me forwards, and then once I'm at a place, let's say I jump
Dialogue: 0,0:32:50.00,0:32:53.00,Default,,0000,0000,0000,,to the end, I can insert Z, Z,
Dialogue: 0,0:32:53.00,0:32:58.00,Default,,0000,0000,0000,,Y, X here at the beginning and it'll slide things over, and then I can delete characters
Dialogue: 0,0:32:58.00,0:33:00.00,Default,,0000,0000,0000,,shuffling things down.
Dialogue: 0,0:33:00.00,0:33:04.00,Default,,0000,0000,0000,,So that's what we've got. Imagine now, it's like building
Dialogue: 0,0:33:04.00,0:33:07.00,Default,,0000,0000,0000,,Microsoft Word on top of this. There's a lot of stuff that goes, you know, between here
Dialogue: 0,0:33:07.00,0:33:11.00,Default,,0000,0000,0000,,and there. but it does give you an idea that the kind of core data requirements
Dialogue: 0,0:33:11.00,0:33:12.00,Default,,0000,0000,0000,,every word processor
Dialogue: 0,0:33:12.00,0:33:16.00,Default,,0000,0000,0000,,needs some tool like this some abstraction underneath it to manage the
Dialogue: 0,0:33:16.00,0:33:23.00,Default,,0000,0000,0000,,character data. Okay. Where do we start? Where do
Dialogue: 0,0:33:23.00,0:33:31.00,Default,,0000,0000,0000,,we start?
Dialogue: 0,0:33:31.00,0:33:33.00,Default,,0000,0000,0000,,Anyone want to propose an implementation.
Dialogue: 0,0:33:33.00,0:33:37.00,Default,,0000,0000,0000,,What's the easiest thing to do? [Inaudible]. In a
Dialogue: 0,0:33:37.00,0:33:40.00,Default,,0000,0000,0000,,way. Something like that. You know, and if you think Array,
Dialogue: 0,0:33:40.00,0:33:43.00,Default,,0000,0000,0000,,then you should immediately think after it, no, I don't want to deal with Array, I want a vector.
Dialogue: 0,0:33:43.00,0:33:44.00,Default,,0000,0000,0000,,I'd like a vector.
Dialogue: 0,0:33:44.00,0:33:45.00,Default,,0000,0000,0000,,Vector please.
Dialogue: 0,0:33:45.00,0:33:47.00,Default,,0000,0000,0000,,Right. So I'm going to show you what the interface looks like, here, that we
Dialogue: 0,0:33:47.00,0:33:50.00,Default,,0000,0000,0000,,have a buffer in these six operations. We're going
Dialogue: 0,0:33:50.00,0:33:52.00,Default,,0000,0000,0000,,to think about what the private part looks like,
Dialogue: 0,0:33:52.00,0:33:54.00,Default,,0000,0000,0000,,and we say, what about vector.
Dialogue: 0,0:33:54.00,0:33:57.00,Default,,0000,0000,0000,,Vector handles big, you know,
Dialogue: 0,0:33:57.00,0:34:00.00,Default,,0000,0000,0000,,chunky things indexed
Dialogue: 0,0:34:00.00,0:34:01.00,Default,,0000,0000,0000,,by slots.
Dialogue: 0,0:34:01.00,0:34:05.00,Default,,0000,0000,0000,,That might be a good idea. So if I had the buffer contents A, B, C, D, E,
Dialogue: 0,0:34:05.00,0:34:08.00,Default,,0000,0000,0000,,right, and if I could slam those into a vector,
Dialogue: 0,0:34:08.00,0:34:10.00,Default,,0000,0000,0000,,and then I would need one other little bit of information here, which is
Dialogue: 0,0:34:10.00,0:34:14.00,Default,,0000,0000,0000,,where is the cursor in any given point because the cursor is actually where the
Dialogue: 0,0:34:14.00,0:34:16.00,Default,,0000,0000,0000,,uncertain lead operations take place relative to the cursor.
Dialogue: 0,0:34:16.00,0:34:19.00,Default,,0000,0000,0000,,The buffer's also going to manage that, knowing where the insertion point is
Dialogue: 0,0:34:19.00,0:34:22.00,Default,,0000,0000,0000,,and then deleting it and inserting relative to that.
Dialogue: 0,0:34:22.00,0:34:23.00,Default,,0000,0000,0000,,So I say, okay.
Dialogue: 0,0:34:23.00,0:34:25.00,Default,,0000,0000,0000,,I need some index.
Dialogue: 0,0:34:25.00,0:34:29.00,Default,,0000,0000,0000,,The cursor actually is between two character positions.
Dialogue: 0,0:34:29.00,0:34:31.00,Default,,0000,0000,0000,,
Dialogue: 0,0:34:31.00,0:34:31.00,Default,,0000,0000,0000,,
Dialogue: 0,0:34:31.00,0:34:33.00,Default,,0000,0000,0000,,This is like slot zero, one, and two.
Dialogue: 0,0:34:33.00,0:34:37.00,Default,,0000,0000,0000,,And the cursor is between, actually, one
Dialogue: 0,0:34:37.00,0:34:41.00,Default,,0000,0000,0000,,and two. And there's just a minor detail to kind of have worked out
Dialogue: 0,0:34:41.00,0:34:46.00,Default,,0000,0000,0000,,before we start trying to write this code, which is do we want the
Dialogue: 0,0:34:46.00,0:34:49.00,Default,,0000,0000,0000,,cursor to hold the index on the character that's to the left of it or to the
Dialogue: 0,0:34:49.00,0:34:50.00,Default,,0000,0000,0000,,right of it.
Dialogue: 0,0:34:50.00,0:34:52.00,Default,,0000,0000,0000,,It's totally symmetric, right.
Dialogue: 0,0:34:52.00,0:34:55.00,Default,,0000,0000,0000,,If I have these five characters, it could be that my cursor then goes from
Dialogue: 0,0:34:55.00,0:34:56.00,Default,,0000,0000,0000,,zero
Dialogue: 0,0:34:56.00,0:34:58.00,Default,,0000,0000,0000,,to four, it could be that it goes
Dialogue: 0,0:34:58.00,0:35:01.00,Default,,0000,0000,0000,,from zero to five, or it could be it goes from negative one to four, depending on
Dialogue: 0,0:35:01.00,0:35:05.00,Default,,0000,0000,0000,,which way I'm doing it. I'm going to happen to use the one that does zero
Dialogue: 0,0:35:05.00,0:35:07.00,Default,,0000,0000,0000,,to five
Dialogue: 0,0:35:07.00,0:35:12.00,Default,,0000,0000,0000,,where it's actually recorded as the character that's after it. Okay.
Dialogue: 0,0:35:12.00,0:35:16.00,Default,,0000,0000,0000,,So that's just kind of the staring point. I'm going to write some code and
Dialogue: 0,0:35:16.00,0:35:20.00,Default,,0000,0000,0000,,make it happen.
Dialogue: 0,0:35:20.00,0:35:23.00,Default,,0000,0000,0000,,So I'm going
Dialogue: 0,0:35:23.00,0:35:25.00,Default,,0000,0000,0000,,to remove
Dialogue: 0,0:35:25.00,0:35:34.00,Default,,0000,0000,0000,,this. Reference it, that's okay.
Dialogue: 0,0:35:34.00,0:35:36.00,Default,,0000,0000,0000,,And then I'm going to add the
Dialogue: 0,0:35:36.00,0:35:37.00,Default,,0000,0000,0000,,things I want to
Dialogue: 0,0:35:37.00,0:35:39.00,Default,,0000,0000,0000,,replace it with. So I put in the
Dialogue: 0,0:35:39.00,0:35:45.00,Default,,0000,0000,0000,,editor code and to put in the buffer code. Was buffer already in here? I think buffer's already here.
Dialogue: 0,0:35:45.00,0:35:51.00,Default,,0000,0000,0000,,Okay. Let's take a look. I get my buffer.
Dialogue: 0,0:35:51.00,0:36:02.00,Default,,0000,0000,0000,,So
Dialogue: 0,0:36:02.00,0:36:08.00,Default,,0000,0000,0000,,right now, let's take a look what's in buffered. I think I have the
Dialogue: 0,0:36:08.00,0:36:11.00,Default,,0000,0000,0000,,starting set information. So it has move cursor over, you know move the
Dialogue: 0,0:36:11.00,0:36:14.00,Default,,0000,0000,0000,,cursor around, it has the delete, and it has - let
Dialogue: 0,0:36:14.00,0:36:18.00,Default,,0000,0000,0000,,me make it have
Dialogue: 0,0:36:18.00,0:36:20.00,Default,,0000,0000,0000,,some variables that I want. I've got
Dialogue: 0,0:36:20.00,0:36:23.00,Default,,0000,0000,0000,,my cursor. I've got my vector of characters. Right now, it has
Dialogue: 0,0:36:23.00,0:36:26.00,Default,,0000,0000,0000,,a lot of copying, I think, just in anticipation of going places
Dialogue: 0,0:36:26.00,0:36:29.00,Default,,0000,0000,0000,,where copying is going to be required.
Dialogue: 0,0:36:29.00,0:36:31.00,Default,,0000,0000,0000,,Right now, because it's using vector and vector has deep copying behavior, I'm
Dialogue: 0,0:36:31.00,0:36:37.00,Default,,0000,0000,0000,,actually okay if I let windows copy and go through. But I'm actually going to
Dialogue: 0,0:36:37.00,0:36:39.00,Default,,0000,0000,0000,,not do that right away.
Dialogue: 0,0:36:39.00,0:36:45.00,Default,,0000,0000,0000,,All right. So then let's look at the implementation side of this and I have an
Dialogue: 0,0:36:45.00,0:36:47.00,Default,,0000,0000,0000,,implementation in here I want to get rid of. Sorry about this but I
Dialogue: 0,0:36:47.00,0:36:54.00,Default,,0000,0000,0000,,left the old one in here. That will do all the things that will need to
Dialogue: 0,0:36:54.00,0:36:56.00,Default,,0000,0000,0000,,get done.
Dialogue: 0,0:36:56.00,0:36:58.00,Default,,0000,0000,0000,,Okay. So let's deal with
Dialogue: 0,0:36:58.00,0:37:06.00,Default,,0000,0000,0000,,at the beginning. Starting off, right, we will set the cursor to zero. So that's
Dialogue: 0,0:37:06.00,0:37:08.00,Default,,0000,0000,0000,,the vector gets started,
Dialogue: 0,0:37:08.00,0:37:11.00,Default,,0000,0000,0000,,initialize empty, and nothing else I need to do with the vector.
Dialogue: 0,0:37:11.00,0:37:16.00,Default,,0000,0000,0000,,A character [inaudible] cursor position in that, and then moving the cursor position
Dialogue: 0,0:37:16.00,0:37:17.00,Default,,0000,0000,0000,,forward,
Dialogue: 0,0:37:17.00,0:37:21.00,Default,,0000,0000,0000,,it's mostly just doing this, right, cursor plus, plus, right. It's just
Dialogue: 0,0:37:21.00,0:37:23.00,Default,,0000,0000,0000,,an easy index to move it down. But
Dialogue: 0,0:37:23.00,0:37:26.00,Default,,0000,0000,0000,,I do need to make sure that the cursor isn't already at the end. So if
Dialogue: 0,0:37:26.00,0:37:29.00,Default,,0000,0000,0000,,the cursor is less than
Dialogue: 0,0:37:29.00,0:37:36.00,Default,,0000,0000,0000,,the size of the vector then I will let it advance. But it never gets beyond the
Dialogue: 0,0:37:36.00,0:37:38.00,Default,,0000,0000,0000,,
Dialogue: 0,0:37:38.00,0:37:40.00,Default,,0000,0000,0000,,size itself. So
Dialogue: 0,0:37:40.00,0:37:43.00,Default,,0000,0000,0000,,like all of these are going to have same problems. Like, if I'm already at the end and somebody asks me to advance, I don't
Dialogue: 0,0:37:43.00,0:37:46.00,Default,,0000,0000,0000,,want to suddenly get my cursor in some lax stated that
Dialogue: 0,0:37:46.00,0:37:52.00,Default,,0000,0000,0000,,sort of back that. Similarly, on this one, if the cursor
Dialogue: 0,0:37:52.00,0:37:56.00,Default,,0000,0000,0000,,is greater than zero, all right, then we can back it up and
Dialogue: 0,0:37:56.00,0:37:58.00,Default,,0000,0000,0000,,move the cursor around.
Dialogue: 0,0:37:58.00,0:38:01.00,Default,,0000,0000,0000,,Moving the cursor at the start is very easy.
Dialogue: 0,0:38:01.00,0:38:03.00,Default,,0000,0000,0000,,Moving the cursor to the end is, also,
Dialogue: 0,0:38:03.00,0:38:05.00,Default,,0000,0000,0000,,very easy, right. We have a
Dialogue: 0,0:38:05.00,0:38:08.00,Default,,0000,0000,0000,,convention about what it is.
Dialogue: 0,0:38:08.00,0:38:11.00,Default,,0000,0000,0000,,And so then inserting a character
Dialogue: 0,0:38:11.00,0:38:15.00,Default,,0000,0000,0000,,is, also, pretty easy because all the hard work is done
Dialogue: 0,0:38:15.00,0:38:17.00,Default,,0000,0000,0000,,by the vector.
Dialogue: 0,0:38:17.00,0:38:18.00,Default,,0000,0000,0000,,
Dialogue: 0,0:38:18.00,0:38:20.00,Default,,0000,0000,0000,,When I say insert this new character
Dialogue: 0,0:38:20.00,0:38:23.00,Default,,0000,0000,0000,,at the cursor position, right, then this character advance the
Dialogue: 0,0:38:23.00,0:38:26.00,Default,,0000,0000,0000,,cursor to be kind of past it, and then
Dialogue: 0,0:38:26.00,0:38:31.00,Default,,0000,0000,0000,,deleting the character, also, pretty easy. Let
Dialogue: 0,0:38:31.00,0:38:34.00,Default,,0000,0000,0000,,me show you, before I go finishing the cursor, I just want to show
Dialogue: 0,0:38:34.00,0:38:38.00,Default,,0000,0000,0000,,you this little diagram of what's happening while I'm doing stuff. So this is kind of a
Dialogue: 0,0:38:38.00,0:38:41.00,Default,,0000,0000,0000,,visualization of the things that are happening. So this is showing the vector and
Dialogue: 0,0:38:41.00,0:38:45.00,Default,,0000,0000,0000,,its length. And then the cursor position
Dialogue: 0,0:38:45.00,0:38:48.00,Default,,0000,0000,0000,,as we've done things. Inserted six characters, the cursor's currently sitting
Dialogue: 0,0:38:48.00,0:38:52.00,Default,,0000,0000,0000,,at the end, and for the length of the cursor, actually, the same value right now. If
Dialogue: 0,0:38:52.00,0:38:56.00,Default,,0000,0000,0000,,I issue a back command, right, that deducts the cursor by
Dialogue: 0,0:38:56.00,0:38:58.00,Default,,0000,0000,0000,,one, it shows another one backs up by one,
Dialogue: 0,0:38:58.00,0:39:01.00,Default,,0000,0000,0000,,and then eventually the cursor gets to the position zero and subsequent backs don't
Dialogue: 0,0:39:01.00,0:39:04.00,Default,,0000,0000,0000,,do anything to it, it just kind of bounces off the edge. And
Dialogue: 0,0:39:04.00,0:39:08.00,Default,,0000,0000,0000,,moving forward, things are easier to deal with. It will advance until the gets to the length,
Dialogue: 0,0:39:08.00,0:39:10.00,Default,,0000,0000,0000,,the size of that text, and it won't go any further.
Dialogue: 0,0:39:10.00,0:39:14.00,Default,,0000,0000,0000,,And that jumping to the front in the end are just a matter of updating that
Dialogue: 0,0:39:14.00,0:39:17.00,Default,,0000,0000,0000,,cursor position from zero to the size and whatnot.
Dialogue: 0,0:39:17.00,0:39:19.00,Default,,0000,0000,0000,,The operation where
Dialogue: 0,0:39:19.00,0:39:21.00,Default,,0000,0000,0000,,things get a little
Dialogue: 0,0:39:21.00,0:39:22.00,Default,,0000,0000,0000,,more
Dialogue: 0,0:39:22.00,0:39:25.00,Default,,0000,0000,0000,,bogged down is on this insert
Dialogue: 0,0:39:25.00,0:39:30.00,Default,,0000,0000,0000,,where I need to insert a position. If I insert the X, Y, Z
Dialogue: 0,0:39:30.00,0:39:32.00,Default,,0000,0000,0000,,into the middle there and you can see it kind of
Dialogue: 0,0:39:32.00,0:39:37.00,Default,,0000,0000,0000,,chopping those characters down, making that space to insert those things in the
Dialogue: 0,0:39:37.00,0:39:37.00,Default,,0000,0000,0000,,middle.
Dialogue: 0,0:39:37.00,0:39:41.00,Default,,0000,0000,0000,,Similarly, doing delete operations, if I jump
Dialogue: 0,0:39:41.00,0:39:43.00,Default,,0000,0000,0000,,to the
Dialogue: 0,0:39:43.00,0:39:45.00,Default,,0000,0000,0000,,beginning I start doing deletes here.
Dialogue: 0,0:39:45.00,0:39:48.00,Default,,0000,0000,0000,,It has to copy all those characters over and
Dialogue: 0,0:39:48.00,0:39:53.00,Default,,0000,0000,0000,,deduct that length, right, so that the vectors do that work for us on remove that.
Dialogue: 0,0:39:53.00,0:39:55.00,Default,,0000,0000,0000,,That means that if the vector's very large, which is
Dialogue: 0,0:39:55.00,0:39:58.00,Default,,0000,0000,0000,,not a typical in a word processor situation, you could have you PhD theses
Dialogue: 0,0:39:58.00,0:40:00.00,Default,,0000,0000,0000,,which has hundreds of pages,
Dialogue: 0,0:40:00.00,0:40:03.00,Default,,0000,0000,0000,,if you go back to the beginning and you start deleting characters you'd hate to think it was just
Dialogue: 0,0:40:03.00,0:40:05.00,Default,,0000,0000,0000,,taking this massive shuffle time
Dialogue: 0,0:40:05.00,0:40:09.00,Default,,0000,0000,0000,,to get the work done. So
Dialogue: 0,0:40:09.00,0:40:13.00,Default,,0000,0000,0000,,let's see my - I'm going
Dialogue: 0,0:40:13.00,0:40:14.00,Default,,0000,0000,0000,,to
Dialogue: 0,0:40:14.00,0:40:24.00,Default,,0000,0000,0000,,bring in the display that
Dialogue: 0,0:40:24.00,0:40:38.00,Default,,0000,0000,0000,,-
Dialogue: 0,0:40:38.00,0:40:40.00,Default,,0000,0000,0000,,whoops,
Dialogue: 0,0:40:40.00,0:40:42.00,Default,,0000,0000,0000,,I don't like something here. [Inaudible]. Now, what do we have? Oh, look at this. Well, well, we will continue on.
Dialogue: 0,0:40:42.00,0:41:00.00,Default,,0000,0000,0000,,This inside - okay. Hello. [Inaudible]. I have no idea. I'm not going to try to [inaudible].
Dialogue: 0,0:41:00.00,0:41:02.00,Default,,0000,0000,0000,,Okay.
Dialogue: 0,0:41:02.00,0:41:08.00,Default,,0000,0000,0000,,It's inside.
Dialogue: 0,0:41:08.00,0:41:21.00,Default,,0000,0000,0000,,That's got me totally upset. Okay. We still have our old code somewhere. Okay. Why do I still have the wrong - what is - okay. Oh,
Dialogue: 0,0:41:21.00,0:41:25.00,Default,,0000,0000,0000,,well. Today's not my lucky day. I'm not going to worry about that too much. I'm just going to show [inaudible]. Okay.
Dialogue: 0,0:41:25.00,0:41:27.00,Default,,0000,0000,0000,,So
Dialogue: 0,0:41:27.00,0:41:29.00,Default,,0000,0000,0000,,seeing what's actually happening, right, it's like just mostly
Dialogue: 0,0:41:29.00,0:41:31.00,Default,,0000,0000,0000,,
Dialogue: 0,0:41:31.00,0:41:34.00,Default,,0000,0000,0000,,kind of moving that stuff back and forth, and then having the vector do the big
Dialogue: 0,0:41:34.00,0:41:37.00,Default,,0000,0000,0000,,work, right, of inserting and deleting those characters, and doing all the copying
Dialogue: 0,0:41:37.00,0:41:40.00,Default,,0000,0000,0000,,to get the thing done.
Dialogue: 0,0:41:40.00,0:41:43.00,Default,,0000,0000,0000,,We'll come back over here
Dialogue: 0,0:41:43.00,0:41:47.00,Default,,0000,0000,0000,,and kind of see what good it does and what things it's not so hot
Dialogue: 0,0:41:47.00,0:41:48.00,Default,,0000,0000,0000,,at, right,
Dialogue: 0,0:41:48.00,0:41:51.00,Default,,0000,0000,0000,,is that it is easy to move the cursor wherever you want.
Dialogue: 0,0:41:51.00,0:41:54.00,Default,,0000,0000,0000,,You know, that moving it a long distance or a short distance, moving it is a little
Dialogue: 0,0:41:54.00,0:41:55.00,Default,,0000,0000,0000,,bit
Dialogue: 0,0:41:55.00,0:41:56.00,Default,,0000,0000,0000,,
Dialogue: 0,0:41:56.00,0:41:59.00,Default,,0000,0000,0000,,or to the beginning to the end, equally easy as by just resetting
Dialogue: 0,0:41:59.00,0:42:01.00,Default,,0000,0000,0000,,some variable.
Dialogue: 0,0:42:01.00,0:42:05.00,Default,,0000,0000,0000,,It's the enter and delete, right where this one actually really suffers, right,
Dialogue: 0,0:42:05.00,0:42:08.00,Default,,0000,0000,0000,,based on how many characters, right, follow that cursor,
Dialogue: 0,0:42:08.00,0:42:11.00,Default,,0000,0000,0000,,right you could potentially be moving the entire contents of the buffer.
Dialogue: 0,0:42:11.00,0:42:14.00,Default,,0000,0000,0000,,Adding at the end is actually going to be relatively fast. So if you have
Dialogue: 0,0:42:14.00,0:42:17.00,Default,,0000,0000,0000,,to type in order, like you just type you theses out
Dialogue: 0,0:42:17.00,0:42:19.00,Default,,0000,0000,0000,,and never go back to edit anything,
Dialogue: 0,0:42:19.00,0:42:22.00,Default,,0000,0000,0000,,then it would be fine, adding those characters at the end. But at any
Dialogue: 0,0:42:22.00,0:42:25.00,Default,,0000,0000,0000,,point, if you move the cursor back into the mid of the body, somewhere in
Dialogue: 0,0:42:25.00,0:42:28.00,Default,,0000,0000,0000,,the front, somewhere in the middle, right, a lot of characters get shuffled as you
Dialogue: 0,0:42:28.00,0:42:30.00,Default,,0000,0000,0000,,change, makes edits in the middle there.
Dialogue: 0,0:42:30.00,0:42:35.00,Default,,0000,0000,0000,,And so what this seems that it actually has good movement but bad editing
Dialogue: 0,0:42:35.00,0:42:38.00,Default,,0000,0000,0000,,as a buffer strategy.
Dialogue: 0,0:42:38.00,0:42:39.00,Default,,0000,0000,0000,,That's
Dialogue: 0,0:42:39.00,0:42:40.00,Default,,0000,0000,0000,,probably,
Dialogue: 0,0:42:40.00,0:42:43.00,Default,,0000,0000,0000,,you know, given that we have these six operations we'll all interested in,
Dialogue: 0,0:42:43.00,0:42:46.00,Default,,0000,0000,0000,,this is probably not the mix that seems to make the most sense for something
Dialogue: 0,0:42:46.00,0:42:49.00,Default,,0000,0000,0000,,that's called an editor, right. It is the editing operations are the ones that is
Dialogue: 0,0:42:49.00,0:42:52.00,Default,,0000,0000,0000,,weakest on, it has its most
Dialogue: 0,0:42:52.00,0:42:53.00,Default,,0000,0000,0000,,
Dialogue: 0,0:42:53.00,0:42:54.00,Default,,0000,0000,0000,,debilitating performance,
Dialogue: 0,0:42:54.00,0:42:58.00,Default,,0000,0000,0000,,it wouldn't make that good of an editor, right, if that was going to be your behavior. It
Dialogue: 0,0:42:58.00,0:43:02.00,Default,,0000,0000,0000,,has one advantage that we're going see, actually, we're going to have to kind of
Dialogue: 0,0:43:02.00,0:43:06.00,Default,,0000,0000,0000,,make compromises on it, which it actually uses very little extra space, though, but
Dialogue: 0,0:43:06.00,0:43:08.00,Default,,0000,0000,0000,,it's using the vector,
Dialogue: 0,0:43:08.00,0:43:12.00,Default,,0000,0000,0000,,which potentially might have excess capacity up to twice that. So maybe it's
Dialogue: 0,0:43:12.00,0:43:14.00,Default,,0000,0000,0000,,about two bites per char in the very worse case.
Dialogue: 0,0:43:14.00,0:43:18.00,Default,,0000,0000,0000,,But it actually has no per character overhead that's already imbedded
Dialogue: 0,0:43:18.00,0:43:23.00,Default,,0000,0000,0000,,in the data structure from this side.
Dialogue: 0,0:43:23.00,0:43:31.00,Default,,0000,0000,0000,,Now, I'm just going to go totally somewhere else. Okay.
Dialogue: 0,0:43:31.00,0:43:34.00,Default,,0000,0000,0000,,So instead of
Dialogue: 0,0:43:34.00,0:43:37.00,Default,,0000,0000,0000,,thinking of it as vector, thinking of it as continuous block,
Dialogue: 0,0:43:37.00,0:43:41.00,Default,,0000,0000,0000,,is to kind of realize the editing operations, right,
Dialogue: 0,0:43:41.00,0:43:44.00,Default,,0000,0000,0000,,that comes back to the idea, like if I were working at the very end of my document that I
Dialogue: 0,0:43:44.00,0:43:47.00,Default,,0000,0000,0000,,can edit there efficiently.
Dialogue: 0,0:43:47.00,0:43:48.00,Default,,0000,0000,0000,,
Dialogue: 0,0:43:48.00,0:43:51.00,Default,,0000,0000,0000,,It kind of inspires me to think of, how do I think I can make it so
Dialogue: 0,0:43:51.00,0:43:55.00,Default,,0000,0000,0000,,the insertion point is somehow in the efficient place. Like the
Dialogue: 0,0:43:55.00,0:43:58.00,Default,,0000,0000,0000,,edits that are happening on the insertion point, can I somehow make it to where
Dialogue: 0,0:43:58.00,0:44:01.00,Default,,0000,0000,0000,,access to the insertion point is easy?
Dialogue: 0,0:44:01.00,0:44:04.00,Default,,0000,0000,0000,,That rather than bearing that in the middle of my vector, if I can expose that
Dialogue: 0,0:44:04.00,0:44:08.00,Default,,0000,0000,0000,,to make it accessible easily in the way the code manipulates the internal of the
Dialogue: 0,0:44:08.00,0:44:09.00,Default,,0000,0000,0000,,buffer.
Dialogue: 0,0:44:09.00,0:44:14.00,Default,,0000,0000,0000,,And so the idea here is to break up the text into two pieces.
Dialogue: 0,0:44:14.00,0:44:17.00,Default,,0000,0000,0000,,Things that are to the left of the cursor, things that are to the right, and I'm calling this
Dialogue: 0,0:44:17.00,0:44:19.00,Default,,0000,0000,0000,,the before and the after.
Dialogue: 0,0:44:19.00,0:44:20.00,Default,,0000,0000,0000,,And then
Dialogue: 0,0:44:20.00,0:44:24.00,Default,,0000,0000,0000,,organize those so they're actually averted from each other to where all the
Dialogue: 0,0:44:24.00,0:44:27.00,Default,,0000,0000,0000,,characters that lead up to the cursor
Dialogue: 0,0:44:27.00,0:44:31.00,Default,,0000,0000,0000,,are set up to where B is very close, assessable at the top of, in this
Dialogue: 0,0:44:31.00,0:44:32.00,Default,,0000,0000,0000,,case, a stack,
Dialogue: 0,0:44:32.00,0:44:36.00,Default,,0000,0000,0000,,and that the things that are farther away are buried further down in the stack in that
Dialogue: 0,0:44:36.00,0:44:37.00,Default,,0000,0000,0000,,inaccessible region.
Dialogue: 0,0:44:37.00,0:44:41.00,Default,,0000,0000,0000,,And similarly over here, but inverted, that C is the top of this stack and D
Dialogue: 0,0:44:41.00,0:44:44.00,Default,,0000,0000,0000,,and E, and things are further down, they are buried
Dialogue: 0,0:44:44.00,0:44:46.00,Default,,0000,0000,0000,,away from me,
Dialogue: 0,0:44:46.00,0:44:50.00,Default,,0000,0000,0000,,figuring the things I really need access to are right next to the cursor
Dialogue: 0,0:44:50.00,0:44:55.00,Default,,0000,0000,0000,,that I'm willing to kind of move those other things father away to gain that access.
Dialogue: 0,0:44:55.00,0:45:00.00,Default,,0000,0000,0000,,And so what this buffer does is it uses two stacks, a
Dialogue: 0,0:45:00.00,0:45:01.00,Default,,0000,0000,0000,,before stack,
Dialogue: 0,0:45:01.00,0:45:03.00,Default,,0000,0000,0000,,an after stack,
Dialogue: 0,0:45:03.00,0:45:07.00,Default,,0000,0000,0000,,and that the operations for moving the data around
Dialogue: 0,0:45:07.00,0:45:09.00,Default,,0000,0000,0000,,become
Dialogue: 0,0:45:09.00,0:45:10.00,Default,,0000,0000,0000,,transferring things
Dialogue: 0,0:45:10.00,0:45:13.00,Default,,0000,0000,0000,,from the before to the after stack.
Dialogue: 0,0:45:13.00,0:45:16.00,Default,,0000,0000,0000,,Where's the cursor?
Dialogue: 0,0:45:16.00,0:45:19.00,Default,,0000,0000,0000,,How does the cursor represent it? Do I need some more data here?
Dialogue: 0,0:45:19.00,0:45:25.00,Default,,0000,0000,0000,,Some integer some ?
Dialogue: 0,0:45:25.00,0:45:28.00,Default,,0000,0000,0000,,It's really kind of odd to think about but there is no explicit cursor, right,
Dialogue: 0,0:45:28.00,0:45:31.00,Default,,0000,0000,0000,,being stored here but the cursor is, in this case, right, like
Dialogue: 0,0:45:31.00,0:45:34.00,Default,,0000,0000,0000,,modeled by what's on the before stack or all the things to the left of the cursor.
Dialogue: 0,0:45:34.00,0:45:38.00,Default,,0000,0000,0000,,What's on the after stack is following the cursor. So in
Dialogue: 0,0:45:38.00,0:45:39.00,Default,,0000,0000,0000,,fact,
Dialogue: 0,0:45:39.00,0:45:42.00,Default,,0000,0000,0000,,the cursor is represented as the empty space between these two
Dialogue: 0,0:45:42.00,0:45:45.00,Default,,0000,0000,0000,,where you have,
Dialogue: 0,0:45:45.00,0:45:48.00,Default,,0000,0000,0000,,you know, how many ever characters wrong before is actually the index of where
Dialogue: 0,0:45:48.00,0:45:51.00,Default,,0000,0000,0000,,the cursor is. So kind of a
Dialogue: 0,0:45:51.00,0:45:54.00,Default,,0000,0000,0000,,wacky way of thinking about it, but one that actually have some pretty neat properties
Dialogue: 0,0:45:54.00,0:45:57.00,Default,,0000,0000,0000,,in terms of making it run efficiently.
Dialogue: 0,0:45:57.00,0:46:01.00,Default,,0000,0000,0000,,So let me show you
Dialogue: 0,0:46:01.00,0:46:02.00,Default,,0000,0000,0000,,the
Dialogue: 0,0:46:02.00,0:46:03.00,Default,,0000,0000,0000,,
Dialogue: 0,0:46:03.00,0:46:05.00,Default,,0000,0000,0000,,diagram of it happening.
Dialogue: 0,0:46:05.00,0:46:09.00,Default,,0000,0000,0000,,So insert A, B, C, D, E, F, G.
Dialogue: 0,0:46:09.00,0:46:12.00,Default,,0000,0000,0000,,And so, the operation of inserting
Dialogue: 0,0:46:12.00,0:46:15.00,Default,,0000,0000,0000,,a new character into this form of the buffer
Dialogue: 0,0:46:15.00,0:46:19.00,Default,,0000,0000,0000,,is pushing something on the before stack.
Dialogue: 0,0:46:19.00,0:46:23.00,Default,,0000,0000,0000,,So if I want to move the cursor, let's say I want to move it back one,
Dialogue: 0,0:46:23.00,0:46:25.00,Default,,0000,0000,0000,,then I pop
Dialogue: 0,0:46:25.00,0:46:27.00,Default,,0000,0000,0000,,the top off of the before push it on the after.
Dialogue: 0,0:46:27.00,0:46:32.00,Default,,0000,0000,0000,,I keep doing that and it transfers the G to the H, you know, the E and so on, as I
Dialogue: 0,0:46:32.00,0:46:33.00,Default,,0000,0000,0000,,back up.
Dialogue: 0,0:46:33.00,0:46:37.00,Default,,0000,0000,0000,,Moving forward does that same operation in the inverse. If I want to move forward I take
Dialogue: 0,0:46:37.00,0:46:40.00,Default,,0000,0000,0000,,something off the top of the after and push it on before. So it's kind of shuffling it
Dialogue: 0,0:46:40.00,0:46:42.00,Default,,0000,0000,0000,,from one side to the other.
Dialogue: 0,0:46:42.00,0:46:46.00,Default,,0000,0000,0000,,Given that these push and pop operations are constant on both implementations of
Dialogue: 0,0:46:46.00,0:46:47.00,Default,,0000,0000,0000,,the stack we saw,
Dialogue: 0,0:46:47.00,0:46:52.00,Default,,0000,0000,0000,,then that means that our cursor movement is also of one so I can do
Dialogue: 0,0:46:52.00,0:46:55.00,Default,,0000,0000,0000,,this. And if I do deletes it's actually just popping from the after stack and
Dialogue: 0,0:46:55.00,0:46:57.00,Default,,0000,0000,0000,,throwing it away.
Dialogue: 0,0:46:57.00,0:47:00.00,Default,,0000,0000,0000,,So also easy to do edits
Dialogue: 0,0:47:00.00,0:47:04.00,Default,,0000,0000,0000,,because I'm talking about adding things to the before and deleting things from after,
Dialogue: 0,0:47:04.00,0:47:06.00,Default,,0000,0000,0000,,both of which can be done very efficiently.
Dialogue: 0,0:47:06.00,0:47:07.00,Default,,0000,0000,0000,,The one operation
Dialogue: 0,0:47:07.00,0:47:10.00,Default,,0000,0000,0000,,that this guy has trouble with
Dialogue: 0,0:47:10.00,0:47:14.00,Default,,0000,0000,0000,,is big cursor movement.
Dialogue: 0,0:47:14.00,0:47:17.00,Default,,0000,0000,0000,,If I want to go all the way to the beginning
Dialogue: 0,0:47:17.00,0:47:19.00,Default,,0000,0000,0000,,or all the way to the end,
Dialogue: 0,0:47:19.00,0:47:22.00,Default,,0000,0000,0000,,then everything's got to go. No
Dialogue: 0,0:47:22.00,0:47:23.00,Default,,0000,0000,0000,,matter
Dialogue: 0,0:47:23.00,0:47:28.00,Default,,0000,0000,0000,,how many things I have to empty out the entire after stack to position the
Dialogue: 0,0:47:28.00,0:47:29.00,Default,,0000,0000,0000,,cursor at the end,
Dialogue: 0,0:47:29.00,0:47:31.00,Default,,0000,0000,0000,,or empty out the entire before stack
Dialogue: 0,0:47:31.00,0:47:35.00,Default,,0000,0000,0000,,to get it all the way over here.
Dialogue: 0,0:47:35.00,0:47:38.00,Default,,0000,0000,0000,,So I could of sort of talk you though this code, and actually, I won't type it
Dialogue: 0,0:47:38.00,0:47:41.00,Default,,0000,0000,0000,,just because I actually want to talk about its analysis more than I want to see its code. Each of
Dialogue: 0,0:47:41.00,0:47:43.00,Default,,0000,0000,0000,,these actually becomes a one liner.
Dialogue: 0,0:47:43.00,0:47:46.00,Default,,0000,0000,0000,,Insert is push on the before stack.
Dialogue: 0,0:47:46.00,0:47:49.00,Default,,0000,0000,0000,,Delete is pop from the after stack. The cursor movement is popping
Dialogue: 0,0:47:49.00,0:47:53.00,Default,,0000,0000,0000,,from one and pushing on the other depending on the direction and then that same code
Dialogue: 0,0:47:53.00,0:47:56.00,Default,,0000,0000,0000,,just for the Y loop, like wild or something on the one stack, just keep
Dialogue: 0,0:47:56.00,0:47:59.00,Default,,0000,0000,0000,,pushing and popping from one empty to the other.
Dialogue: 0,0:47:59.00,0:48:02.00,Default,,0000,0000,0000,,So very little code to write, right,
Dialogue: 0,0:48:02.00,0:48:05.00,Default,,0000,0000,0000,,depending a lot on the stacks abstractions coming through for us
Dialogue: 0,0:48:05.00,0:48:09.00,Default,,0000,0000,0000,,and then making this ultra fit that we've managed to get editing suddenly,
Dialogue: 0,0:48:09.00,0:48:10.00,Default,,0000,0000,0000,,like, a lot more efficient
Dialogue: 0,0:48:10.00,0:48:15.00,Default,,0000,0000,0000,,but the cost of sacrificing one of our other operations. Let's take a look at what that
Dialogue: 0,0:48:15.00,0:48:19.00,Default,,0000,0000,0000,,look like, right.
Dialogue: 0,0:48:19.00,0:48:22.00,Default,,0000,0000,0000,,Suddenly I can do all this insert and delete
Dialogue: 0,0:48:22.00,0:48:23.00,Default,,0000,0000,0000,,at the insertion point
Dialogue: 0,0:48:23.00,0:48:24.00,Default,,0000,0000,0000,,
Dialogue: 0,0:48:24.00,0:48:25.00,Default,,0000,0000,0000,,with very little trouble,
Dialogue: 0,0:48:25.00,0:48:29.00,Default,,0000,0000,0000,,and I suddenly made this other operation, oddly enough,
Dialogue: 0,0:48:29.00,0:48:30.00,Default,,0000,0000,0000,,slow.
Dialogue: 0,0:48:30.00,0:48:33.00,Default,,0000,0000,0000,,All a sudden it's like if you go back to the beginning of your document you're in the
Dialogue: 0,0:48:33.00,0:48:36.00,Default,,0000,0000,0000,,middle of editing, you're at the bottom. You say, oh, I want to go back to the beginning
Dialogue: 0,0:48:36.00,0:48:39.00,Default,,0000,0000,0000,,and you can imagine how that would feel if you were typing
Dialogue: 0,0:48:39.00,0:48:42.00,Default,,0000,0000,0000,,it would actually be the act of going up and clicking up in the top right by where you made
Dialogue: 0,0:48:42.00,0:48:44.00,Default,,0000,0000,0000,,the insertion and all a sudden you'd see the white cursor
Dialogue: 0,0:48:44.00,0:48:45.00,Default,,0000,0000,0000,,and you'd be like,
Dialogue: 0,0:48:45.00,0:48:49.00,Default,,0000,0000,0000,,why is that taking so long. How could that possibly be, you know,
Dialogue: 0,0:48:49.00,0:48:51.00,Default,,0000,0000,0000,,that it's doing this kind of rearrangement, but yet it made
Dialogue: 0,0:48:51.00,0:48:54.00,Default,,0000,0000,0000,,editing even on a million character document fast. But
Dialogue: 0,0:48:54.00,0:48:55.00,Default,,0000,0000,0000,,that movement
Dialogue: 0,0:48:55.00,0:48:58.00,Default,,0000,0000,0000,,long distances, you know, jumping a couple of pages or
Dialogue: 0,0:48:58.00,0:48:59.00,Default,,0000,0000,0000,,front to back,
Dialogue: 0,0:48:59.00,0:49:05.00,Default,,0000,0000,0000,,suddenly, having to do this big transfer behind the scenes, so
Dialogue: 0,0:49:05.00,0:49:08.00,Default,,0000,0000,0000,,different, right. So now I had six operations, I had four fast,
Dialogue: 0,0:49:08.00,0:49:09.00,Default,,0000,0000,0000,,two slow,
Dialogue: 0,0:49:09.00,0:49:12.00,Default,,0000,0000,0000,,now I have four fast, two slow.
Dialogue: 0,0:49:12.00,0:49:16.00,Default,,0000,0000,0000,,It still might be that, actually, this is an interesting improvement, though, because
Dialogue: 0,0:49:16.00,0:49:19.00,Default,,0000,0000,0000,,we have decided those are operations that we're willing to tolerate,
Dialogue: 0,0:49:19.00,0:49:23.00,Default,,0000,0000,0000,,being slower, especially, if it means some operation that we're more interested in, if
Dialogue: 0,0:49:23.00,0:49:24.00,Default,,0000,0000,0000,,performance being faster.
Dialogue: 0,0:49:24.00,0:49:28.00,Default,,0000,0000,0000,,And that likely seems like it's moving in the right direction because editing, right, being
Dialogue: 0,0:49:28.00,0:49:31.00,Default,,0000,0000,0000,,the whole purpose, right, behind what we're trying to do is
Dialogue: 0,0:49:31.00,0:49:32.00,Default,,0000,0000,0000,,a text setter,
Dialogue: 0,0:49:32.00,0:49:34.00,Default,,0000,0000,0000,,that seems like that might be a good call.
Dialogue: 0,0:49:34.00,0:49:38.00,Default,,0000,0000,0000,,What I'm going to start looking at and it's going to be something I want to talk about
Dialogue: 0,0:49:38.00,0:49:39.00,Default,,0000,0000,0000,,next time,
Dialogue: 0,0:49:39.00,0:49:42.00,Default,,0000,0000,0000,,is what can a link list do for us?
Dialogue: 0,0:49:42.00,0:49:46.00,Default,,0000,0000,0000,,Both of those are fighting against that continuous thing, the copying and the
Dialogue: 0,0:49:46.00,0:49:48.00,Default,,0000,0000,0000,,shuffling, and the inserting
Dialogue: 0,0:49:48.00,0:49:51.00,Default,,0000,0000,0000,,is there something about that flexibility of the rewiring
Dialogue: 0,0:49:51.00,0:49:53.00,Default,,0000,0000,0000,,that can kind of get us out of this
Dialogue: 0,0:49:53.00,0:49:55.00,Default,,0000,0000,0000,,some operations having to be slow
Dialogue: 0,0:49:55.00,0:50:00.00,Default,,0000,0000,0000,,because other operations are fast. Question. [Inaudible]. Yeah.
Dialogue: 0,0:50:00.00,0:50:03.00,Default,,0000,0000,0000,,Why is space used for stacks when
Dialogue: 0,0:50:03.00,0:50:04.00,Default,,0000,0000,0000,,those are half? Yeah.
Dialogue: 0,0:50:04.00,0:50:08.00,Default,,0000,0000,0000,,So in this case, right, depending on how you're
Dialogue: 0,0:50:08.00,0:50:09.00,Default,,0000,0000,0000,,modeling your stack, if it is with
Dialogue: 0,0:50:09.00,0:50:12.00,Default,,0000,0000,0000,,vectors, right, then you're likely to have the before and the after stack, both
Dialogue: 0,0:50:12.00,0:50:16.00,Default,,0000,0000,0000,,have capacity for everything, even when they're not used, right. And so it's very
Dialogue: 0,0:50:16.00,0:50:17.00,Default,,0000,0000,0000,,likely that either right
Dialogue: 0,0:50:17.00,0:50:20.00,Default,,0000,0000,0000,,give 100 characters they're either on one stack or the other, but the other one might be kind of
Dialogue: 0,0:50:20.00,0:50:23.00,Default,,0000,0000,0000,,harboring the 100 spots for them when they come back.
Dialogue: 0,0:50:23.00,0:50:27.00,Default,,0000,0000,0000,,Or it could just be that you have the link list, which are allocating and de allocating but
Dialogue: 0,0:50:27.00,0:50:30.00,Default,,0000,0000,0000,,has the overhead of that. So it's likely that no matter which implementation the stack
Dialogue: 0,0:50:30.00,0:50:33.00,Default,,0000,0000,0000,,you have, you probably have about twice the storage that you need because of the
Dialogue: 0,0:50:33.00,0:50:38.00,Default,,0000,0000,0000,,two sides and the overhead that's kind of coming and going there.
Dialogue: 0,0:50:38.00,0:50:41.00,Default,,0000,0000,0000,,So we will see the link list and we'll talk that guy through on
Dialogue: 0,0:50:41.00,0:50:46.00,Default,,0000,0000,0000,,Friday. I'll see you then.