So continuing on with collections with our theater class.
So looking at the top of it, up here.
We've set on line 10 private list seat.
And we're using an array list.
So we can easily now change that format to a linked list.
Linked list and the code will still work.
We can still run that.
And everything still works as it did before,
we can see the first time it was reserved.
The second time you need to pay because it's already been reserved,
so clearly the implementation's still working.
But we can be even more generic than that, cuz we can change List to a Collection.
So we could do something like this, we can change The list clear to collection.
And that's really using just that.
It's making it really really generic by making it of type collection.
So the advantage doing that is it enables us to use any of the collection classes
to hold our seats.
Now before we go ahead and do that, what I want you to do is have a look at
the interface hierarchy of the collections framework and the Java docs are pretty
good here, so I'm gonna take a copy of this link off the screen.
So I'm just gonna fire up a browser and past the link in and the link will
also be in the resources section, so you can see here this little diagram,
it gives you a little, good overview Of the collections classes.
So, the interfaces set list q and dq all extend the collection interface.
And there's also sorted set, as you can see there, and that extend set.
Now incidentally, the framework also contains a separate [INAUDIBLE] Hierarchy
for maps, and I'll be discussing those later.
So when we declare seats to be of type collection.
We can implement the list of seats in a theater using any concrete
class that implements one of the interfaces that extend collection,
[INAUDIBLE] you can see on the screen there.
Now we've already used a ray list and
link list that implements the list interface previously.
And we can also use a hash set or
a linked hash set that implements set if we want to.
And as it turns out, I'm gonna use each in turn and
verify that the program still runs.
Let's try it first with a hash set.
So I'm gonna go back.
To my code. Now that we've set it as Collection,
we can change that over here from LinkedList to a HashSet.
HashSet, and we can go back and run this.
Still works, as you can see there.
We can get rid of the commented-out code.
So in other words we can see the seats and rows.
You can see they're all still there, noting that now we're in a different order
but they are still there and that's because we're using sets.
We can also go back and use the LinkedHashset.
So LinkedHashset as you can see there.
We can run that.
Notice how that returns an order this time.
Now we're gonna be looking at sets in more detail shortly, but
at the moment hopefully this should really demonstrate how array list and link list
fit into the Collections framework, and that they can be replaced with other data
structures if that structure provides benefit for a particular task.
Now with that said however you must remain on the same level of the hierarchy.
So going back to our little diagram, although we can
use any what we can't do is drop down a level and still expect things to work so
the collection also includes a which is actually on the screen there.
But that implements sorted set.
So that's sort of one level down.
But if you go ahead and try and use that tree set, try and run that.
We actually get an error.
And the error there is it's a class cast exception And it's having trouble casting
to the Comparable, because we're using TreeSet, which again is one level down.
So, TreeSet would be below SortedSet.
So, any of these you can use, but you can't use the ones below that directly.
Directly, so I'm just gonna close that and move this over a bit,
close this down, and undo that change, unlink that set.
Now, tree set, as it turns out, that we tried to use implement sorted set,
and Actually what it does, it's navigable set, which extends sorted set.
It's got an additional requirement that elements in it must contain or
must be comparable.
That's how the set is sorted.
Because we didn't make the seat class comparable,
that's why we got that class cast exception,
if you try to add a little tree set Now as we move down the hierarchy,
the interfaces become more specialized, so we can only replace classes with other
classes that implement one of the core collection interfaces at the same level.
So the diagram that I was in a few times that we looked at, and
I'll just go back to it again And you can see below that,
it's actually got the text set is a special kind of collection.
Assorted set is a special kind of set and so on.
And that's why we've got that issue with making sure things are at the same level
when we're trying to replace and use them.
Now before we move on to look at what other classes are and
why we might want to prefer to use one instead of our lists.
Let's talk about some of the remaining methods provided by the collections
framework to work with lists.
Although there's not really that many seats in our theater,
getting back to our code.
The reserve seat method isn't really efficient the way we've written it.
To see how many seats it has to check in order to find H2.
I'm going to make a little bit of a change here to print a full stop every time
the loop goes around and I'm going to do that on line 31.
So I'm going to change that and do a print of the system out message dot and
that's going to be so that's going to put a dot on the screen so
we know how many it's had to check to find the relevant seed.
And what we'll also do is we'll go back,
change it to the ray list, which is what we started with.
So if you go back and run that, and the other thing I'll do is I'll comment out
the skit seats method again so we don't see all the seats on the screen, so
if we run this, you can see that
there was a lot of dots on the screen, a heck of a lot of dots from seed 11.
So it's very inefficient, the way it's been Designed at the moment,
and you can more or less say it's referred to as a brute force search
in that it scans every element until it finds the one we want.
Now, the collections class provides a blimey search method that performs
much better.
So that as a result we can improve the reserve seat method and its performance.
Now in order to get that to work we need to implement the comparable interface in
our seats class, and that's so that Java knows how to compare two seats.
So what we need to do is Theater again, and we need to change our definition.
And we've got public class Seat down here.
We've got Seat, we want to change that to implements, Comparable, comparable.
And we're gonna compare on seat, of course, which is the subject.
And then what we need to do is add the comparable code so that,
again, Java knows how to compare two seats.
So what we're gonna do is just below here
is we're gonna add the override to compare to.
And we need that, of course, so that the comparison will work.
So we're gonna override To be compared to through here.
Actually it's an interface and we're implementing it.
So I compare to, you can see it's a parameter, it's a seat.
I'm gonna change or it's got owed to seat so it makes more sense for us.
And what we can do to figure out the comparison,
it's actually a one liner we can do here.
Instead of returning zero we're gonna return this
.seatnumber.compareto ignore
case seat.getseatnumber.
So that's gonna return the number lesson zero, number
zero with a recall intercourse, a number greater than zero if it's greater than.
And we saw that before.
We've used comparable previously in the course.
But doing it this way now, what we've got is a comparison
that fulfills the interface, and it means that we can now be able to use
a different type of sex for our searching, which is a lot more efficient.
So now that we've done this it's now a lot more efficient.
We've added a compare to and we can start implementing this binary list,
a binary search I should say and it's going to be a lot more efficient.
And as you can see, with the compare to method we're really just using the compare
to method that's built in to the string class.
Then we'll make it, it's not anything specialized other than that.
But the important thing here is that the seat class could contain more than
one field.
And if that was the case, java wouldn't have any idea which one would be used for
comparison.
So if you have a more complex class, this is where you put your code in for
testing that comparable interface and then you provide a compare to method,
that the framerate can use, which we've done here now.
Now that we've done that, if we go back up and check our reserve seat.
We can change this a little bit now.
I can go back to the top.
The first bit is we're going to create a requested seat.
So instead of making that null, that's going to be equal to new seat.
Cuz we're gonna be using comparison now.
Seat is going to be seat number, number that's past on.
So that's going to give us the object For comparison purposes,
like so and what we wanna do is change this completely so
I'm gonna put int foundSeat equals collections.binarySearch and the search
is gonna be on seats, which is our list of seats and on the seat that we want to
search it against which is the requested seat we've just created online 29.
And then we're passing null cuz we're gonna use in built
comparison operation there, so once we do that we're gonna get a number back and
the other thing I'll need to do to avoid this error here is we need to change this
collection back to a list cuz that's what we were working on initially,
and the error should then go away.
So that's gonna run use to the comparable interface and it's gonna
use the method that we implemented to check using the string compare to operator
We'll compare to ignore case method to the comparison for us.
Then all we need to do after that is just check for
a number that's greater than to zero.
So if found, c is greater or equal to zero.
Return, seat dot get.
Found seat dot reserve.
Then we'll put an else in here.
Else there is no seat,
past seat number to enforce.
We'll just ignore this extra code here now that we don't need.
Show comment out.
That's all been replaced now with the collections binary search which is
a lot more efficient.
Now the reason that the binary search is more It's really the fastest way to find
an item in a sorted list, and
it works by checking the element in the midpoint of the list.
So the method basically plays higher or lower with the list.
So if the middle element is greater than the item that we're looking for
Then it knows the one we want must be in the first part of the list.
[INAUDIBLE] then it performs a binary search on that
half of the list in the same way.
So the list of is reduced to half each time.
So that's a result that will take no more than 10 checks to find an item.
Or decide it's not present in a list of 1,024 elements,
2 to the power of 10 is 1,024.
So over a million items, actually,
1,048,576 can be checked in no more than 20 comparisons,
and 64 comparisons are all that's required to search a list With an absolutely huge
number, so 1.844 to 10 to the 19th element, so a number like this.
So that would only take 64 comparisons.
So it is blindingly fast compared to the brute force approach that we took earlier,
where we were just going through each and every record.
So you're not really gonna have to see too much in terms of a performance.
If we actually run this just to confirm that it does work.
You can see that it does certainly work as it did before.
But what I'm gonna do is paste some code in, which is the code from
The actual binary search Java source code that comes with Java.
And we're gonna past that into our theater method.
Now, we could go ahead and make a change to the Java source files, but
that wouldn't be a good idea in this case,
because we'd be changing the official Java source code.
So it's easier to just convert or just to copy the code in there but
it's really a useful exercise to see how that works.
And one of the reasons we want to do that is so that we can see the full stop.
We can put some full stops in to see the Progress in how many times it takes
compared to our previous attempt as to how many seats it needed to search for.
Because obviously when we use Collections.binarySearch,
we haven't directly got a way of getting access to seeing that part.
If we change the code, we can do it.
So, what I'm gonna do is copy and paste this code to replace our method,
and then we'll be able to see it working in action.
So I'm going to come here and I'll copy all of this commented-out code.
We'll Overwrite I should say so there's nothing there.
I'll paste that in.
This is the source code that is part of the search that comes with java so
you can see what it's doing.
It's, and obviously it's been adapted for our particular purposes but
essentially all the code is exactly the same.
So we're accepting the seat number.
And you can see it's using the low-high approach and
starting with the low is the number zero.
The high is the last element minus one.
And it's using this high limit to determine the comparison and sort of
splitting it in half each time there, finding the midpoint as I talked about.
And it's going through and
returning the relevant comparison operator depending on the result.
And I'll just fix that little error up there.
So consequently now, we should be able to run this and
see how many dots it printed compared to the last attempt of our codes.
So if you run that, you can see that In this case, seat 11 was found in only.
What's that, six dots?
Significantly faster than the last case.
So let's try booking a few other things just to see the different results here.
So we could try booking D12.
That's probably going to give us one of the best cases if we try D12.
D12. and what I'll do is
I'll just take this second part out of there because we don't need that anymore,
just to run to see how fast it is.
So if you try that, obviously there was something significantly, it was
either the second time, went through once, and then on the second time it threw.
It found D12, so that's much, much faster.
H12 or 8 or B11 are two of the worst.
And also try it when it doesn't exist.
Let's try something like B13.
We'll run that You can see that it didn't go through all the elements.
It's still only, what's that, one, two, three, four, five, six, seven iterations,
including the last one, that there's no seat B13.
So it's significantly faster than our other attempt at searching.
Now, obviously, in this particular case,
with only 96 seats in our theater, It's not really in it's shoe, but when you
start talking thousands of records using features like this in this case binary
search which is part of the collections framework, it makes a lot more sense.
Now, the other thing I wanna point out is, going back to this code, normally,
you wouldn’t copy the collections message like this, we just call them
like we did with the binary search earlier, before I copy and paste it over.
But it’s just really interesting to see how efficient the binary search
algorithm is And we did that by adding the adopt
to show us how many iterations it took to where we wanted to go to.
And it's also good to know that we don't have to write our own versions of
the algorithms that are included in the Collections class.
So I'm gonna end the video here now.
In the next video I'm gonna go on and talk some more about the binary search and
how it works, and we'll go on to the next step.
So I'll see you in the next video.