It's quite clear from the first of these that we've put out that people love the Lego model
Or at least a lot of people do find it useful so yeah, we want to take it on a bit further today
We have this
pre-Prepared linked list of
barbecue items which are all in alphabetical order and last time we covered about
How would you insert a new item?
Into this list if it was something that you'd forgotten to buy and you bought it later
This thing called p is pointing at exactly the same structure at the head of the list as start is
So we now have got the problem of inserting burgers alphabetically into this thing list
Now doing that with conventional techniques
Well, we covered that before and it it's ok it works, but it's somewhat messy
I wasn't happy - never have been happy over the years with the way that that's done in the
Conventional single level pointer technique is there anything you can do that's better?
Well yes, there is this came about or was made clear to me many years ago now in that...
I, as many of you know
originally did this in a language in the early 70s called ALGOL 68 and
The people who had done the ALGOL 68 compiler for the machine we were working on was the Royal Radar
Establishment in Malvern in the UK and
One or other people there who did that compiler could be Subhan Kuba Phillip would would just said
To me and my colleague Annie walker at the time. They said you're teaching this stuff now
You do realize that algol 68 can do the triple ref technique?
Which previously has only been available to Assembler programmers?
We said really can it yes?
And yes, it can so what on earth is this well despite that technical name it's actually a pointers to pointers technique
It's very powerful, and you might think well
If you've got pointers why on Earth would you want pointers to pointers?
well the strange thing about this and the really remarkable thing is that in the end it makes your
procedure for doing things
simpler not more complicated
So what do we do? Well,
We've got Burgers here
And we're going to try and put it into the correct place just as before but instead of using a previous single level
pointer and then having to say well
It's all very well they can probe what the strings are
But what you had is the problem was you've forgotten the way you came from
And when you splice burgers into this list you need to know what's ahead of you
But you need to know where you came from it's the previous blue box
And if you're not careful you lose any way of getting on that, so if you look at my solution using traditional techniques
I carefully keep a second pointer to remember where it came from this will no longer be necessary here we go
We introduce a thing which I'm going to call tracer
Tracers contents are of type pointer to pointer to things
So the way you declare that in C, is it's a thing** because we declare things by their contents in C
So inside tracer is a thing **. It's a pointer to a pointer to a thing so therefore
It's absolutely right that you can make and look at this piece of chain here. That's to say that a pointer to a pointer
Although it's a pointer is not the same thing as a single-level pointer to a thing
It's perfectly okay for me to attach that to there
And saying that the contents of tracer is a pointer to a pointer to a thing
So I'm pointing to the address of a box which inside it has got a pointer to the thing which in this case is the head of the list.
You basically use a technique known as casting of pointers, you can
take a jump you can dereference you can follow the link you can either do it once to get to here or
When you've got to there, you can jump the pointer again and get on to an actual thing at the head of the list
So it's two steps removed. Yeah, so starting here
You jump there you then you look along the black hose
And you say I'm looking at something called beer, and I want to put in my thing here
Which is burger and the idea of this is always that you insert ahead
Alphabetically of where you are if that's what fits. No burger isn't earlier than beer in the alphabet
It's later than beer so what you have to do now is to try and look ahead
At the next thing which we will discover is chips now
Here's the really cool thing about using the tracer pointer to pointer technique
Is that if inspecting beers had no we've not gone far enough yet?
What we now do instead of awkwardly moving our single level pointer down the list is take this blessed a great link and do
Wait for it folks. This is
Absolutely cool. Ok if I made tracer
Originally point at a blue box because type wise it was right then it follows that all of these blue boxes
In turn I can make it point through those to take a peek at the next one down in the list
It's as simple as that you see: Type
Theory by colors a green thing can point at the blue thing, but it can't point directly at a red thing
So you look at this and you think?
well
by the
Principle of colored Lego type theory if I can make the green thing point
It's any blue thing I can do that, and then you say, but what does that imply in the program?
It's implies in the program that you've got to be able to find the address of a blue box
That's embedded within a particular thing structure
And now look what you could then do is you start with tracer. You jump to that box
But then you jump down the firemen's hose and you can take a look and you see that the next thing is chips
You see wow
I've just seen beer I'm
Looking ahead by this sneaky technique, and I see chips. That's where I belong
I want the burger thing in there, so this is completely magic
But does it generalize? And does it work? And the answer is yes it does
because
by stepping
One step backwards and going through an intermediate blue box before you do anything the crucial advantage
It gives you is that having decided that burgers does belong in here?
The problem we previously had of saying where the heck did I come from is solved because tracer is still pointing at it
So you say to tracer let me dereference you once and I've then got the address of the box
I want to alter so that it points at the burger thing and we end up just like we did I think last time
but using the tracer technique of saying
There goes burguer. We know we're in the right place, and if you remember
we constructed
Let's get this right do the long one first
That one
Goes here, and then finally you when you complete this splicing in operation by taking that
Pointer the previously came off the beer thing turning it round and putting it on the blue box
there, so
Job done, but the big point is that you were able to keep half a finger on where you came from?
That's the thing. At the same time as using that to look ahead and say yes, alphabetically I'm correct
I'm after beer and before chips. It's like standing at a road sign and knowing that you're standing in London
Yeah. But the road sign says Bristol. Yes. You're standing at the point to where it's pointing
That we see both those things actually. Precisely so, that's right.
So let's just take a quick look and honestly there's very daring of me
I've actually put out the routine that does this in C and will provide this for you if
You don't believe that this works just compile the program. I give you and run it and say wow it does work