Programming Methodology-Lecture16

Instructor (Mehran Sahami): All righty. Welcome back to yet another fun-filled, exciting day of CS106A.

So itís the day before the midterm. This is kind of like, you know, the calm before Ė well I shouldnít even say the calm before the storm. Itís a probably a lot more calm for me than it is for you. But hopefully youíre getting prepared for the midterm, so a few announcements before we start.

Thereís one handout. You still have sections this week, so sections will happening after the midterm. The section problem is the handout for this week. The midterm is tomorrow night and hopefully you should already know this by now, but just one more time just to drive the point home: midterm tomorrow night, Tuesday, October 30th, 7:00 to 8:30 p.m. in Cresby auditorium.

If you had emailed me before and let me know that you had a conflict with the midterm, you shouldíve already gotten an email from me this weekend letting you know about the alternate exam, what time it was, what the instructions are for the alternate exam. So if you think you emailed me about a conflict and you never heard from me this weekend, please let me know right away, like right after class.

Right now, if you heard this and you think you have a conflict and you didnít get an email from me this weekend, you should be panicking because I think Iíve reached everyone who said they have a conflict. And invariably, as you can imagine, there wasnít just one time that worked for everyone, so we ended up doing a little bit of gymnastics to make it work, but hopefully everyone has a time they can actually make.

If youíre an SEPD student, email me by 7:00 p.m. tonight if you plan on taking the exam at your site remotely. If I donít get email from you by 7:00 p.m. tonight, I will just assume that you are coming into campus for the regular exam, which is perfectly fine. If you want to send me an email verifying that youíre coming in for the regular exam, thatís great too.

I always love to hear from the SEPD students, but youíre not required to but you are required to send me email if youíre gonna take the exam at your site. Otherwise, I wonít know to send the exam to your site. So send me email by 7:00 tonight letting me know if youíre taking it remotely, and let me know who your site administrator is, their name and email. Thatís critical because your site administrator will be administering the exam to you.

All righty. So any questions about anything before we dive into our next great topic? All right, letís get started on our next great topic then. And tonight Ė today I should say, I think itís tonight because like the lights are on; itís actually daytime. So today, there is a whole new concept that weíre gonna be getting into called an array. Okay?

And all an array is, is basically a way to keep track of a whole bunch of information at once. So what weíve done so far in class is like when you wanted to keep track of information you had some variable, and you had like an int, or you had a double, or you had a g-oval, or whatever it was. And it was you kept track of some small piece of information, but in the real world, really want you want to do is keep track of a whole bunch of information.

Like say youíre gonna take your midterm, we would want to keep track of all of your midterm scores. And it would be a real pain, for example, to say int Midterm 1, int Midterm 2, int Midterm 3. You can just see how monotonous it is. And by the time I got to Ėint Midterm 150 youíd be ready to kill, but we couldnít stop then because weíd have to go up to like int Midterm 325. Right? And so we just donít want to do that and computers are really good at dealing with lots of information. So the way they allow us to keep track of a whole bunch of information at once is something called an array.

And so the two key concepts for an array is that an array is ordered, so it has some natural ordering, and that means we can refer to the elements of the array using some index based on that ordering, and itís also homogeneous, which means that everything in the array that we store is of the same type. So we can have an array, for example, that stores integers, and we could say, ďHey, we want an array that stores 500 integers.Ē But itís only gonna store integers; itís not gonna store a couple integers and a couple doubles and some strings. All the types are the same so itís homogeneous. Okay?

So how do we actually create one of these things?

Weíll erase some announcements. Weíll slide this puppy over here. Itís actually the first time Iím sliding boards around. And the reason why I always hesitate to slide boards around is all it takes is one really nasty time to get your finger crushed by a board, and you never want to slide boards around again because you canít write for a couple days and itís real fun to do class, especially for you with the left hand.

All right, so how do we actually declare an array? First, we specify the type of the thing we want to have in that array. Then we have an open bracket and closed bracket. Thatís gonna indicate to the computer that this is an array of this type int. Then we give it a name, so letís just call this Ė Iím gonna call it My ARR, for My Array. Okay?

And then what we need to do is basically tell the machine, ďHey, create some space for the array for me.Ē Okay? So the way we specify that is we use our friend new, then we say the name of the type again, which may seem a little bit redundant because we just said it over here. But the reason why we have to say it over here again is because when you tell the machine, ďHey, I want you to setup some space for some integers, and the place Iím assigning that to is an array of integers.Ē Okay? So these two types over here actually generally need to match, but you need to have that redundancy.

And then the thing that we specify over here is we actually specify what the size is of our array. So for example, we could have five. So what this is actually giving to us is itís giving us an array of five integers. Okay? And the way you can actually think about this is an array is basically like a big list that has a bunch of cells in it, or what we refer to as the elements of that array. Okay?

So this is my array, My ARR, and itís spaced for five integers. And the way we refer to these particular integers, or the elements of the array, and each one of these boxes hold one integer, is theyíre indexed because this is an ordered collection. Right? Itís homogeneous because theyíre all integers, itís ordered, and itís indexed starting from zero. Because as computer scientists, we always start counting from zero.

So if I ask for an array of five elements, theyíre actually indexed from zero up to the size of the array minus one. [Inaudible]. Just like a string, right, like the characters in a string, where zero up to length of the string minus one. Same idea with an array.

And each one of these things in it is storing an integer. And when you create a new array, the values actually in the array get initialized. They get initialized to whatever the default is for that type. What does that mean? Well, it means for things like integers, the default value is zero. For things like Booleans, the default value if false.

And thereís a whole list of what the default values are, but weíre gonna just stick with integers right now, so all these things start with the value zero in them. One of the niceties, Java gives you the arrays in this life. So if youíve worked with other languages, like C or C++, itís one of those things you have to just let go because the syntax is different, the initialization is different, let go of your old C ways and just adopt the happiness that is Java. Okay?

So how do I refer to these individual elements? The way I refer to the individual elements is through the indexes. Okay? So I could say something like My ARR zero; and I put this inside square brackets, so itís square brackets over here and square brackets over here. And what this is now referring to is this particular cell, which stores one integer. Which means I can use that just like would use a variable of type int anywhere else in my program. I can assign to it, I can use them in use them in expressions, whatever the case may be.

So if I say my array equals five, what itís actually doing is just sticking the value five into this cell. Okay? So any questions about that? Hopefully fairly straightforward? All right.

So the thing you want to think about for these arrays, and what makes them kind of funky, is first of all I get a whole bunch of values very quickly just by specifying the size of the array. The other thing is that this little index thatís in here doesnít necessarily have to be a constant value like zero. I could actually put a variable in there.

So I could, for example, have a for-loop that goes through all the elements in my array: for int I equals zero. I, in this case, Iím just gonna size is less than five, which is the size but weíll get to how we actually want to deal with that in just second. I-plus-plus and then inside here Iíd say my array sub I which is that particular I element. Maybe I want to read this, for example, from the user: equals read int, and Iíll just, you know, put the little question mark to ask the user for a value.

And so what this does is it goes through and essentially asks the user for five integer values, and stores them in the indexes of the array from zero up to four. Okay? So one quick loop does all the work, right? If I have 300 values, I change this to a 300, I change this to a 300. Iíd be good to go, thatís all I need to change in my program. So thatís kinda the power of arrays. Okay?

So the more general form of arrays, this is how we might actually use them and in this case, Iím just thinking about integer arrays. The more general form of thinking about arrays is sort of like this.

Ooh, a lot of chalk dust.

Youíll notice here, weíll just map to kind of general form. This is the type that you want to specify. Okay? Then we have open bracket, close bracket, your angle, then you have the name of your array. Then you say equals new, and you specify the same type again, and end size brackets you have the size, so thatís kind of the general form.

So we could have an array of doubles, right? We could have an array of Booleans. We could have an array of strings, for example, by saying string bracket-bracket. Iíll call this s-list for string list equals new string. Oh, letís say I want 100 strings. Okay? Life is pretty easy. All right? So any questions about that? All right. Hopefully this is all fairly straightforward.

Now the other thing thatís kinda easy is one Ė or that I should mention is you can have, as you might notice, a string is an object. I could have an array, for example, of g-ovals, or g-rects. So I could actually say something like g-oval, maybe is my type, and then Iím gonna have an array of these things. And Iíll call this, you know, my circles because Iím just gonna have a whole bunch of these ovals that maybe represent circles. And then Iíll say new g-oval. And hereís where things get a little funky. I say new g-oval, and then letís say I wanna have ten of these things, I put a ten.

Notice this looks different, even though I use the new itís different than the syntax for creating one new oval. Right? If I wanted to create one new oval, I would say something like, Iíll put it down here, g-oval, and Iíll just call this O for oval, equals new g-oval. And then I could give it the parameters for the constructor, like some original X, Y location and some size, maybe 100-comma-100.

What this is doing is creating one object of type g-oval and assigning it to the value O. What this is doing is creating space for ten g-ovals, none of which have been created yet. Okay? So what does that actually mean? Let me make this a little bit smaller so I don't have to draw ten boxes; Iím gonna make this four, okay, but same effect.

When I do this declaration, what I now have is this thing called circles, which is an array. Itís an array thatís got four cells in it. Okay? And each one of these cells is basically gonna be able to store a g-oval. But each one of these cells right now doesnít actually have a g-oval in it. Why: because I havenít created a new g-oval in each one of those cells. Each one of these cells, or elements, all it has in it is the ability to store a g-oval.

Itís kind of like if you just said g-oval, and Iíll call this empty. Okay? What happens when I say g-oval empty? I get this thing called empty over here, which is space for a g-oval but I havenít done new on it yet which means this thing doesnít actually point to any object that is a g-oval. Its value, for example, is null. Right? Thereís no actual g-oval there. I just say, ďHey, get me the box thatís gonna store a g-oval in it,Ē but Iím not actually putting any g-oval in it yet.

So when I do this declaration, Iím essentially doing the same thing as this except rather than getting one box, Iím getting for boxes. So each one of these boxes to begin with has a null in it, okay? So I have space to store four g-ovals but I have not yet constructed the g-ovals. So if I actually want to construct the g-ovals, Iím just gonna make use of this little line right here. I could say, for example, circles sub zero equals new g-oval. And what this will now do is say, ďHey, this is circle sub zero over here. Go and create some new oval and stick it in that box.Ē So now, it actually has an oval to deal with. Okay?

Or if you want to think about it from the memory point of view, what really is happening is this is some pointer somewhere that points off to some piece of memory thatís storing the information for an oval. Okay?

So any questions about that? Thatís a critical distinction between creating the array, which is just creating the space for essentially these pointers or references to objects, and actually creating the object. Which you still need to do, you can just create objects in each one of the individual elements of the array if you want to. But if you just create the array, you donít actually get space for the objects themselves, you just get space for the references to the objects. Much in the same way you do when you just declare a variable of some object type.

Uh huh?

Student:Is there a more efficient way [inaudible] an array [inaudible] spaces to [inaudible]?

Instructor (Mehran Sahami): To create new ovals, for example?

Student:Yeah, [inaudible].

Instructor (Mehran Sahami): Absolutely. So let me erase this and I will just put in one extra line up here four int I equals zero, I less than, in this case, four I-plus-plus circle sub-I equals new g-oval. So thatís the beauty of arrays, right, is the fact that you can use them with objects just in the same way you could do them with ints. And so, you can go through and, for example, construct all your objects and now youíve created a whole Ė all these ovals are the same, you know, size. Right? Theyíre add zero-zero and they size 100-comma-100 but theyíre all distinct ovals.

So what Iíve actually gotten in here is this points off to some oval and this points off to some oval and this, and theyíre all distinct ovals. They just happen to have the same dimensions. Okay? But thatís one way I can create all the objects very quickly if I actually want.

Uh huh?

Student:[Inaudible] ovals and then array [inaudible] oval [inaudible] array [inaudible] refer to it [inaudible]?

Instructor (Mehran Sahami): Yeah, so once Iíve created all the ovals, I have all these pointers. Youíre saying like if I pass it to a function? Yeah, if I Ė the thing about object is or any time I pass an object, Iím passing a reference. So if I change the object that Iím referring to, Iíll always be changing the real actual underlying object.

The important thing that weíll get to in, oh, about ten minutes, is that fact that when we get into primitive types in arrays, I can actually pass an array of primitive types and change the primitives types in the arrays, which I couldnít do before. So thatís part of the beauty of arrays. Okay?

So Iím gonna go Ė give you a brief digression on one topic before you kinda launch into the next thing. And this brief digression is this operator that youíve actually been using the whole time with tact and verb, as a matter of fact, we just used it on that board over there. And now youíre old enough to sort of understand what it really does.

Youíre like, ďBut Mehran, I thought I knew what it did,Ē this little operator called plus-plus. ďIt was nice, I just added one, I used it since the days of KARO when I had for loops in KARO, I had a plus-plus. I didnít know what it did then. Then you told me what it did and life was good. I could add one to things.Ē Now Iím gonna tell you what it really does and youíre like, ďIt does something besides add one to something?Ē Yeah, itís this very tiny difference.

The thing with this plus-plus is thereís actually a bunch of different places I can put it. And youíre like, ďYeah, I can imagine some places Iíd want to put it, Mehran.Ē Yeah, no itís not going there. All right? So here is X equals five. Thatís just terrible and itís on video.

All right, so I have X, it has the value five. Now somewhere in my program, I come along and I say, ďYou know what?Ē Let me draw my X five over here so I can have more of my program. My X five, I say X-plus-plus. What is that doing? It turns out plus-plus is actually a method. And youíre like, ďWhoa, itís a method?Ē Yeah, and it returns something. And youíre like, ďOh thatís even weirder.Ē

So what it does is it adds one to this variable, okay, so it turns it into six. But this is actually returning a value, and the value itís returning is the value of variable before you did the plus-plus so it returns a five. Okay? In the past, we just never used that value. We said like I-plus-plus and it added one to I and said, ďOh hereís your return value,Ē and we said, ďYeah, weíre not assigning that anywhere, we donít actually care.Ē

But we could actually assign it somewhere, okay? So I could actually do something like say int Y equals X-plus-plus, and so Y will get the value five, X will start off as five, Iíll add one to it, itíll become six. And you might think, ďHey, isnít this whole thing six now? Doesnít that get assigned to Y?Ē No. When I put the plus-plus after a variable, I get back the old value of the variable. This form is what we refer to as a post-increment.

Why is it post-increments, because the plus-plus comes after, thatís where the post comes from, and it adds one, so increments. So the way you can think of it is I add one but after I return a value. Okay?

So you might say, ďHey Mehran, if thereís a post-increment isnít there also a pre-increment?Ē And you would be right. And the way a pre-increment looks is we take our friend the plus-plus and we put it before the variable. So we say plus-plus X. Okay? In terms of the effect it has on X, itís exactly the same; it adds one to X. So when I say X equals five, I put in the five here, then I say Ė

That looks like just a whole bunch of Ė let me make that all a bit more clear; I just looked at that and Iím like, ďI canít even read what that is.Ē

Plus-plus X, so what it does is it adds one to X and it returns the value after adding one. So it actually returns six and thatís what gets assigned to Y. And this is called a pre-increment. And the reason why itís called pre-increment is I do the incrementing first; I add the one then I return the new value. Okay? So any questions about that?

And youíre like, ďBut Mehran, why are you telling me about this?Ē And the reason why Iím telling you about this is that this little form, this X-plus-plus form and the fact that it returns a value, actually gets used a whole bunch with arrays. And Iíll show you some examples of that, but you need to Ė thatís why you need to understand what itís actually doing. Itís adding one to the value X but returning the old value when I do the post-increment. And thatís the version you usually see with arrays. Okay? But now you know.

So any questions about post-increment versus pre-increment? All righty.

Then letís actually put a bunch of this stuff together into a slightly larger program. And as part of that slightly larger program, we can discuss a couple more concepts that come up with arrays. Arrays hopefully arenít too hard. Like in the past, every time Iíve taught arrays, like it seems like, yeah, most people generally get arrays and they generally work the way you think they would work, so hopefully you should be feeling like okay with arrays.

If youíre feeling okay with arrays, nod your head. If youíre not feeling okay with arrays, and itís okay if youíre not feeling okay with arrays, shake your head. All righty, letís go on then.

Thereís this notion of the actual size of the array versus what we refer to as the effective size of the array. Okay? The notion of the actual size of the array is this is how big Iíve declared the array to be. So when I setup my array here, the actual size is five. Okay? Itís how big itís declared. The effective size is how much of it Iím really using in my program.

So the idea is how much are you really using because sometimes what you do is you say, ďHey, you know what, Iím gonna have some program that computes the average midterm scores. But I donít actually know how many people are in this class,Ē frightening as that may be, right? And I probably wonít know until I see how many people actually take the midterm because some people might withdraw or whatever at the last minute. Hopefully you wonít but sometimes it happens.

So when Iím writing my program, I canít just stick in some value operator that I know. One thing I do know is thereís probably less than 500 people taking the exam, so I can set my actual size to be 500. And then thereís some number of midterms that weíll actually grade and Iíll have the scores for, and thatís how many Iím really gonna be using. Thatís gonna be my effective size. And I need to keep track of this to distinguish it from this in my program. So letís write a little program that actually does that.

Oh, I think I can fit it all on this board. Letís try anyway.

So what Iím gonna do is write a program that basically asks the user to enter values until they give some sentinel to stop. Okay? So my sentinel: private static final end, you have to say it kinda like youíre singing a dirge, sentinel equals minus one. Because I really hope no oneís gonna get a minus-one on the exam. I don't know how you would do that. Itís like you donít do any of the problems and somehow you manage to like upset the instructor. Right? Itís just like, ďOkay, youíre getting a minus-one. Thanks for playing.Ē

I used to get one free point if you spelled your name right, and someone got it wrong once so I donít do that any more. No joke, it really happened. I think just too much stress or something, or maybe I couldnít read the writing but I was like, ďThatís is not the name.Ē All right.

So one of the other things that weíre actually gonna do is keep track of how large the arrayís gonna be in itís declared size. So Iíll keep track of some maximum size, which Iíll just call max size. And maybe Iíll set max size to be equal to 500. So I know Iím gonna have at most 500 scores that Iím gonna store.

And so when Iím gonna create my array, Iím gonna create an array whose size is max-size and then keep track of how many elements Iím actually using. So in my program, all right so let me put this in public void run. And inside here, what Iím gonna say is Iím gonna have some integer array that Iím gonna keep track of.

Actually, thereís no space in here, so let me just rewrite that.

Some integer array and Iíll call this Midterm; Iíll just call it Mid to keep it short. Itís gonna be the midterm scores. And what this is, is Iím going to declare, basically, a new array of integers thatís size is this constant over here, max size. Okay?

So I set that up and now I get an array of 500 integers just created for me and life is good. And I say, ďOh thatís great but I don't know how many scores I actually have,Ē so I want to keep track of the effective size to remember how many scores I have. So Iím gonna keep track of an extra integer in here called Num Scores, and Iím gonna set that equal to zero because to begin with I don't have any scores that the userís given me. Okay?

Now Iím gonna have a while loop thatís gonna read in scores from the user. So I might while true, because Iím basically keep reading scores until the user gives me the sentinel value over here and that indicates that I should stop, [inaudible] score, so Iíll read one score at a time, equals read int, and Iíll ask the user for a score by just putting in a question mark.

Then I say if that score is equal-equal to the sentinel then Iím done. Right? Just gave me a negative one, I know thatís not a real score so I can just break. But if they gave me a score that was not a negative one, so itís some valid score, okay, then I want to store that in my array. And so the way Iím gonna store in my array is Iím say mid sub, and hereís where Iím gonna get funky with my plus-plus operator, num scores plus-plus.

Let me write that a little more clearly.

Num scores plus-plus equals score. And thereís the end of my while loop. Okay? And then my program will go on after that.

So whatís going on here, okay? And the reason why I show you this is you will see this on, if you look at real Java programs, this kind of thing happens all the time where you do a plus-plus inside the index for an array. So what happens, this array gets setup, itís got size 500, so zero, one, two, three. I wonít write it all out. We have a big break in here. This is 499 over here. All right?

So we have this huge big array and num score starts off as zero. So hereís num scores. Iíll just abbreviate NS for num scores. It comes in and says read some score from the user, so itís get an integer. And I say, ďOh, someone got 100 on the exam,Ē wonderful thing. Is 100 equal to minus one? No, so I donít break out of the loop. And now Iím gong set midterm sub num scores plus-plus to score. So whatís that gonna do?

First itís gonna come over here and say, ďWhat score?Ē because it always evaluates the right-hand first. That scoreís 100, thatís all you need to do. Where am I gonna store scores? Iím gonna store it over here. How do I evaluate this? I say, ďOkay, Iím gonna store it somewhere in my array Mid,Ē hereís the array Mid, ďwhich one of these cells am I gonna store it into?Ē Iím gonna store it into the cell given by num scores plus-plus. So what do I do? This is a post-increment. I add one to num scores, num scores now becomes one, but what value actually gets returned there from the plus-plus?


Instructor (Mehran Sahami): Zero, right? Thatís a social, all around, except like thereís three pieces of candy right there.

It returns a zero so Mid sub-zero is what gets score, so this gets 100. And Iíve gotten the nice effect where Iíve gotten the score stored in the location I want, and at the same time Iíve incremented num scores to tell me how many scores in this array have actually been entered that I care about. Okay? Thatís why you see this all the time with arrays, especially in Java or other Java-like languages like C or C++ because itís a shorthand thatís so common to say, ďYeah, the next time you get a score put it in the next available spot and increment the number of scores you have.Ē

So the next time I go through the loop, it gets another score. Letís say someone got a 30. Sorry, just didnít work out. Study. You get the 30; itís not equal to the sentinel. Where am I gonna store that? Mid sum num scores plus-plus. Num scores is currently one. I add one to it, I get two, but I return the old value, which is one, and so I stick in the 30 in Mid sub one. Okay?

So num scores here is the effective size of my array. Itís how many elements of that array I actually care about using. So if I want to now go compute the average of all the scores, Iím not gonna go through all 500 elements because not all 500 elements have valid scores that I care about. Iím just gonna go through num scores number of scores, the effective size of my array, even though I might have some declared size thatís larger. Okay?

So any questions about effective versus actual size or using this plus-plus operator to keep track of things? Uh huh?

Student:[Inaudible] num scores [inaudible]?

Instructor (Mehran Sahami): Ah, good question. Is that what you were gonna ask back there too?


Instructor (Mehran Sahami): Yeah, what if like, you know someone just enrolled a whole bunch of times in the class.


Instructor (Mehran Sahami): Yeah, I can get to you.

Thatís an excellent question. What do you think would happen if I try to access, say, mid sub 500? Youíre like, ďI don't know. I get candy?Ē No. You get an exception. Okay? But this time itís not a little exception, youíre getting a big honking exception. And so if Iím getting ready to throw this out somewhere, itís gonna be bad. Itís gonna hurt. Okay? So thatís an exception you first of all you donít want to get, and second of all, if you get it, you probably donít want to deal with it in your program unless youíre writing some very advanced program. You want to figure out that there was some problem with your logic and go fix the problem with the logic. All right?

Itís kinda like eventually someone will get this exception somewhere and theyíre like, ďOh. I am disturbed by your lack of bounds checking on the array.Ē You know, itís just one of those things where you want to check Ė

Donít worry, Iím not gonna give the whole lecture like this because if I did I couldnít see after a while.

But itís an evil, evil exception to get. Itís not that bad but you should be careful of that exception. Itís a big one not to be confused with the small exceptions. Thanks for asking. Yeah, itís not a plant. Valid question. Figured someone might ask it.

So let me show you an example of how we actually deal with that in a program. Okay? So in a program, we can get around this in some slightly more interesting way and avoid the exception. So hereís a more complicated version of the program we just wrote. Rather than setting a maximum size to be a size thatís declared as a constant, Iím actually gonna use Ė ask the user for a maximum size.

Because letís say maybe I wanna run this program for 106A and then I wanna give the program to some other instructor somewhere and they can run it for their class, and they donít want to have recompile the program. They just want to start the program and say, ďYeah, I don't know how big class is either, but its maximum size is like 4,000,Ē right? Itís like ECON1 or something like that. ďAnd so just give me an array.Ē

So hereís one of the things thatís interesting. I have int max length and Iím gonna ask the user for the maximum size of the array, rather than having it set as a constant. I now declare my array, Iíll call it Midterm Scores here, to be a size thatís this max length thatís given to me by the user.

If youíve programmed in another language like C or C++, at this point you should going, ďOh Mehran, I couldnít do that in C or C++.Ē And if you never programmed in C or C++, you should be going, ďYeah Mehran, I don't care what you can do in C or C++ because Iím programming in Java.Ē And Java allows you to declare an array like this where the size is actually something thatís dynamic, thatís only known at the runtime when the user enters it. Okay?

Hereís my number of actual scores, thatís gonna be my effective size for the array, how many elements of the array I actually care about. And now rather than having a while loop which may allow me to just potentially go off the end of the array, Iím gonna have a for loop and this for loop is gonna count up to the maximum length. So itís gonna guarantee if I ever get to the maximum size of the array, Iím gonna stop asking the user for any more values because I will have exhausted the for loop.

But if I havenít yet exhausted the for loop, what Iíll do inside here is I will get a score from the user, so Iíll read in the next score into midterm score, if that score is the sentinel I will break out of the loop. If the scoreís not the sentinel, then I will increment my number of actual scores and iterate this over and over. Okay?

Now the interesting thing here is if the user actually enters the sentinel before they get to filling in all the elements of the array, the max length, I break. Break always takes you out of the closest encompassing loop. So this whole time youíve been using break with, for example, while loops. This will actually break out of a for loop; you can break out of for loops as well.

Itís not the greatest style in the world but sometimes in rare occasions like this, it actually makes sense because you wanna say, ďThe most Iím ever count up to is max length. Guarantee me that Iím gonna go any higher than that, otherwise Iím get the Darth Vader exception and life is gonna be bad, but I might break out earlier if the user actually gives me the sentinel.Ē Okay?

And Iíll only increment num scores if they didnít give me the sentinel, so Iím not gonna count num score Ė Iím not gonna count the sentinel as one of the values I actually care about. Even though it gets stored in the array, Iím not actually gonna say thatís a valid value because I break out before I actually increment num scores.

Okay, any questions about that? Uh huh?


Instructor (Mehran Sahami): If they enter a negative score for the maximum? Well, try it and see what happens. All right? Itís not never happen in real life and so if Ė ooh, if youíre really interested Ė

I might just peg her because it makes me angry. I canít reach you but Iím gonna keep trying.

Try it yourself and see what happens. Itíll probably give you some something that wonít work, right?

So whatís something else that I want to do? And Iíll get to do that right now but let me do it on the board before I show it to you in this program because thereís something else I might actually want to do in the program. What happens if I pass an array as a parameter? Right? So this whole time weíve been talking about arrays, weíve sort of had the array inside your run method and life was good. And we were like, ďOh array. Yeah, I can do all this stuff with it.Ē

What if I want to pass an array, which is a common thing to do, as an actual parameter to a function? Okay? So letís say I have public void run. Inside here, I have int bracket bracket. Iíll call it ARR, for my array, equals new int ten, so I get an array of ten elements. And now I wanna pass this array. I wanna say, ďHey Mehran, rather than reading in all the values from the user in your main program or in run, I wanna decompose the program. I want to have some function that actually reads all the values for me. Can I do that?Ē

Yes, you can. And so let me have some method called read array, and what Iím going to pass to it is the array. When I pass an array, if I wanna pass the whole thing, I just specify the name of the array. I do not specify an individual index on the array because if I specify an individual index I would just be passing a single element of the array, which would be a single int. If I want to pass the whole array, I give the name of the array with no other brackets. Okay? So this is gonna pass array method.

So somewhere down here, letís just say thatís the end of my run method, maybe I have some more stuff in here, I have private void read array. And read array is gonna take in some parameter. How do I specify a parameter array? I say int bracket bracket. That indicates the thing that is getting passed to me is an array of integers. Okay? And then I give it a name for the parameter. Here Iíll call it A, just to distinguish it from ARR. All right?

So inside here I get A, and so Iím gonna have some for loop inside here, for int I equals zero. And you might say, ďOh Mehran, how do you know how big the array is? How do you know how many elements to ask the user for,Ē right, ďbecause you just passed the array? Where is the size of the array? You didnít specify Ė if you had it specified as a constant, like you did before with max size, then I could refer to that constant over here. But you didnít specify it with a constant, so what do I do?Ē

I would normally give you concentration music and let you decide. But in fact arrays, and this is one of the nice things about arrays in Java, they carry around their size with them. Okay? So what I can say is array dot length. Okay? And the funky thing here, to distinguish it from strings, when you ask the string for its length you put in an open brace or an open bracket or open paren/closed paren. Here you donít specify open paren/closed paren. Length is actually some internal variable of an array that is public so it is available to you.

So youíre actually referring directly to this public variable of the array. So array dot length, I want to say actually I is less than array dot length, so let me set this to be zero. I is less than array dot length, I-plus-plus. And so if I pass arrays of different length here, their length, their declared length, right, I don't know itís effective size is, itís declared length is ten. And so what I might do inside here is say: A sub I equals read int, to get an integer from the user. And thatís supposed to be a question mark inside double quotes.

Now you might see this and say, ďOh Mehran, I thought you told me when I pass around primitive types I get a copy of the primitive type. Right? So when I pass an int, I get a copy of the int, and if I try to muck with that int, Iím just mucking with the copy. And so when I return to my calling Ė the location from where I called that particular method, that value hasnít changed.Ē Yeah, thatís for primitive type not for an array, even if the array is of primitive type.

So the thing you want to think about passing arrays is arrays always get passed by reference, just like object. If you pass an array, youíre getting the actual array because it says, ďHey you know what, arrays are big. I don't want to copy ten integers. Iím lazy. Iím just gonna let you know where that array actually lives in memory.Ē And so, when you make any changes to that array, youíre actually changing in memory at the place where this array actually lives.

So it does it mainly for efficiency reasons, right? Because if this was an array of a million elements, if you got a copy you would have to copy a million elements every time you made this call. Rather than copying them it says, ďHey, Iím just gonna let you know where those million elements live. You want to mess with them, you mess with them. Youíre gonna change the actual one. If donít want to mess with them, then donít mess with them.Ē

Uh huh?

Student:[Inaudible] variable is public, can you change the length [inaudible] code?

Instructor (Mehran Sahami): You shouldnít try.

Student:I mean I just wondered if that would happen if you actually did that.

Instructor (Mehran Sahami): Yeah. I wouldnít encourage you try it. I would just say donít try it; itís a bad time. But if you really want to see what happens, try it. Just itís never something you would want to do.

Uh huh?

Student:Can arrays be ivars?

Instructor (Mehran Sahami): Yeah, arrays can be ivars. So if you want to have an array declared inside a class and actually store an array inside a class, thatís perfectly fine. So arrays you can use just like any other variables, you just get a whole bunch of stuff. Okay?

So but the important thing is any changes you make to the array, the changes persist; arrays always get passed by reference. Okay? So at this point, you could also say, ďHey Mehran, that means if I wanted to change around some integer, and I just had a single integer, could I actually have an array of one integer and pass that array of one integer and change that one value, and I could change an integer that way?Ē

Yeah, you could. It would be horrendous style but you could do it. Okay? So donít do it in this class and donít ever do it as a software engineer because if you do this as a software engineer, people will look at that and say, ďWhere did you learn this?Ē And youíll say, ďOh, that Sahami guy at Stanford told me this.Ē And then theyíll come and hunt me down, and kill me. And thatís bad; at least for me, may not be for you. Donít do it. Itís not how we try to pass integers by reference.

Uh huh?

Student:Can you make arrays of arrays? Like if you wanted to add all of our test scores divided by [inaudible] tests.

Instructor (Mehran Sahami): You can and youíre actually one day ahead of me. So next time, weíll talk about multidimensional arrays, where you can have arrays of arrays of arrays of arrays. And it can just Ė till the cows come home. You have like four-dimensional arrays. You can have like 12-dimensional arrays and just expand your view of the universe. Itís like string theory with arrays.

Yeah, the other dimensionís just wrapped so tightly you canít actually stick integers in them, but thatís not important right now. Thereís like a few string theory people who are like, ďHo-ho-ho, thatís funny Mehran.Ē Everyone else is like, ďWhat?Ē All right, so not that Iím a string theorist, but I like to play one on TV.

All right, so what else can we do with arrays? If arrays, when we pass them around weíre actually passing references to arrays that means other funky things are sort of possible. So let me show you another example of something thatís possible, if we return to our program. This oneís not so funky. This one just says, ďHey, what I want to do is after you give me all those scores I want to compute an average score.Ē

So Iím gonna have some method where I want to pass to this method is the Midterm Scores array that I had before. Right? Thatís just this array that we declared up here. And I also want to pass to you the actual number of values that Iím using, the effective size of the array. The reason why Iím doing that is because if I donít pass you the effective size of the array, you donít know the effective size of the array. The only thing you know that the array gives you is declare its size; it doesnít keep track of, oh, which element youíre using or which element youíre not using.

It says, ďHey, I know Iím this big. And if youíre not using the whole size of me, then you do need to pass the effective size.Ē So inside compute average, itís getting passed an array of integers and itís getting passed the act number Ė actual scores that we care about. And it just goes through a loop that counts up all the actual scores, adds them to this thing called Average that weíre sort of adding up as we go along. Right? So itís adding all the individual elements of the array to average.

And then when weíre done going through all the elements we care about, we just set average equal to average divided by num actual scores. And because average is a double, it does real value division so we get the average and we return the average here. Okay? And so all this prints out is average score and then it will actually print out what the real average of those scores were a sum double. Okay?

So important thing to keep in mind, even though you get this facility where you know the declared size of the array, sometimes you still need to pass the actual Ė the effective size, if you have Ė if youíre not using all the elements of your array. If youíre always guaranteed that youíre always gonna have, you know, ďYeah, this is the Olympics and thereís always seven judges. And I know itís always gonna be seven and thatís just the way it is, unless there were some kind of payoff scandal,Ē then you know itís seven, the declared size and the effective size are the same. Okay?

One of the other things I can also do Ė now in this case, notice Ė in this array example case, I didnít actually change any of the values inside the array. Okay? Even though I didnít change any of the values, the array still got passed by reference so I still had the real array. If I changed any values, they wouldíve persisted. But I still get a copy no matter Ė or still always get the actual array, I donít get a copy whenever I pass it whether or not I change the values. In most cases, you donít change the values, which is why itís actually more efficient and Iíll give you a copy to give you the actual thing.

Sometimes what I might want to do is say, ďHey you know what, I want to swap two values around.Ē And so you might think, ďHey you know what, if I have some array, hereís some integer array that I declare here thatís got five elements in it. And I set its first two values to be one and two, respectively. So array sub zero is one, array sub one is two.Ē Okay?

Then I say, ďHey, I want to swap the two values.Ē So I have some function that Mehran wrote for me, some method called Swap Elements Buggy. And why did he name it that? Yeah not because itís a little baby thatís inside a little stroller that we push around, that in the days of yore we used to call a buggy, because itís got an error. This not the way you want to do it. And I do want to make it explicitly clear so this is the buggy version.

The buggy version says, ďI pass in these two elements of the arrays as the two parameters.Ē Which means when I want to do swap, hereís the buggy version, the buggy version says, ďHey, I get passed an integer X and an integer Y.Ē Why do I get an integer X and an integer Y? Because the elements that I passed in were array sub zero and array sub one, those are integers. They are primitive values. Iím not passing the whole array; Iím passing individual elements of the array. The individual elements of the array are primitive types, which means we go back to our old case of passing copies.

Anytime the things here are just straightforward ints, rather than being an integer array, for example, all youíre getting are copies. So I get copies of array sub zero and array sub one, and I go through this little exercise where I swap them. So I have some temporary where I put one of them in, then I take that one and I replace it with the other one, and then I assign the temporary back to the other one. Itís not a big deal how it actually works.

As a matter of fact, let me just draw it for you, how it works so you know how it works and weíre all on the same page. I get X and Y, they have values, letís say four and five to start with. I have some temporary. I start of by saying: temporary equals X, so temporary gets the value four, then X gets Y, so X gets the value five, then Y gets temp so Y gets the value four. And for all intents and purposes, it looks like I swapped the values. Good times, now Iím done with this function and this all goes away because theyíre copies and theyíre all temporary. And they just vanish and nothing is actually changed in the array because I passed the individual elements of the array, which are primitive types.

So if you pass primitive types, even if theyíre individual elements of an array, you are still getting copies. If you really want to do the swap, the right way to do it, is Swap Elements Happy because it will make you happy. What you do is you say, ďHey, Iím gonna pass the whole array.Ē Once you get the whole array, youíve gotten a reference to the array, you can change stuff around in the array and it will persist. So you say, ďHey, Iím gonna give you the whole array, and Iím gonna give you the two positions of the elements in the array that I want to swap.Ē

So when I actually do the swap here Iím doing the same logic, except Iím actually doing the swap with values in the array rather than copies of values that are passed in as primitives. So this version actually works because Iím modifying the array itself.

Okay, and questions about that? Uh huh?

Student:If there are objects [inaudible]?

Instructor (Mehran Sahami): If theyíre objects are actually getting references to the object so you donít need to do the same thing. Itís just for primitives that you need to worry about it.

So let me just run this program just to show you, in its painful detail, what itís actually doing. Weíre running. Weíre running. Oh, itís Ė sometimes itís just slow and painful, but at the end of the day, you know, we get the little warm fuzzy. So I want to do the Swap Example. And so the Buggy Swap, notice Element 1 is still Ė or Element 0 is still one, Element 1 is still two. Happy Swap, theyíve actually swapped in place because I passed the array, which was a reference.

Okay, so any questions about that? If that all made sense, nod your head. Exellente.

All right, so a couple more quick things. One quick thing, this is super-minor. Youíll probably never end up doing this in your life, but if you see someone else do it youíll know what theyíre doing. Which is you can create an array thatís initialized with particular values you give it by saying int bracket array, so we have some array of integers. And rather than specifying new or specifying some size, I just say, ďYeah, this array actually has the values two, four, six, and eight in it.Ē

So inside braces I put the initial values, from the number of values that I give it, the values are separated by commas, it figures out, ďOh, this is an array of four elements, so let me create an array of four elements for you, stick in those initial values to initialize it, and youíre good to go from there.Ē You virtually never see this, but just in case you do, now you know what itís like. All right?

So itís time for one last great topic. And this last great topic, Iím gonna give you very briefly just enough for right now that you need to know to do your hangman program. On Wednesday, weíll through all this is excruciating detail. So if youíre not starting hangman before Wednesday, youíre perfectly fine. Youíll see way more detail than you need for hangman on Wednesday. But just in case you were like, ďHey Mehran, yeah Iím studying for the midterm, and right after the midterm Iím totally pumped up. Iím just gonna go do all of hangman,Ē this is what you need for Part 3 of hangman.

So Part 1 and 2 you already know everything you need to know. Part 3, thereís this thing called the array list. How many people have already gotten to Part 3 of hangman, by the way? Yeah, just one person in the back; did you read about array list yourself or have you not done it yet?


Instructor (Mehran Sahami): I canít hear you but thatís okay. If youíve already gotten to Part 3 youíre so far ahead you just donít even need to worry. Itís good times. Just come after class, Iíll give you all the chocolate you want. All right.

So array list. Because these array things are sometimes bulky to work with, especially when you think about, ďOh, I need this effective size versus actual size, and wouldnít it be great if when I needed more elements the array just grew for me?Ē So I said, ďHey, I start off with no elements and I read in like five values for midterm scores and I kinda store that.Ē And I say, ďThatís great.Ē Oh, I got these Ė I found these like late midterms somewhere, well thereís five more I need to add.

And the array would just come along and say, ďOh thatís fine. Youíve been so good to me this whole time, Iím just gonna expand my size to give you more space.Ē Like wouldnít that be great? And youíre like, ďOh yeah, thatíd be so good.Ē Like the birds would be singing and everything. But real arrays donít do that. Yeah, sorry, birds all been shot down.

Array lists bring the birds back to life and now theyíre singing again. It will do this for you, so what you need to know about an array list. First of all, what you need to do is you need to import java-dot-util-dot-star because this thing called an array list comes from the Java util package. Okay?

Once you do that, you get access to our friend the array list. And the array list as described in the book comes in two flavors. It comes in the super-cool Java 5.0, also known as Java 1.5. Because sometimes the numbers for Java is 1-point-something, like 1.x and sometimes itís just X; and itís super confusing but thatís the way it is. So Java 1.5 is the same thing is the same thing as Java 5. And youíre like, ďThat makes no sense at all.Ē Yeah, it doesnít. Thatís just the way it is.

So thereís the super-cool Java 5.0 or later version, and then thereís yes still kind of useful but not quite as cool pre-Java 5.0 version. And the only thing you need to know is the super-cool Java 5.0 or later version, so you donít need to worry about the pre-5.0 version.

So in the super-cool 5.0 or later version, an array list is something called a template, which means when Iím creating an array list, an array list is actually a class that I specify the type that that class is gonna operate on, which is kind of a funky thing. But the way I declare an array list is I say: array list with AL because this is actually a class that exists inside Java-util-dot-star. And then I use essentially the less-than sign or what we sometimes refer to as angle brackets if weíre not using it as a less-than sign. And then the type that I wanna store in this array list.

So essentially, I wanna have an array list of strings. And you can kind of think of this almost like an array of strings but cooler. And so, this is inside the less-than/greater-than signs. Okay? Then you give it the name; I might call this STR List, for string list. And then I say that is a new, and hereís where the syntax gets kind of very funky, array list angle bracket string close angle bracket, open paren close paren. And you look at that and youíre like, ďWhat? Why would I do that?Ē

Thatís just the way the syntax is. What this is saying is Iím gonna have an array list. What am I gonna store in the array list? Iím gonna store strings. Whatís the name of my variable that is that array list? It is STR List, so thatís the name of the variable. The type is an array list of strings. Okay? Once I set this up, all I get is my little space for a STR List and so I need to actually say, ďHey, create the new array list for me.Ē

What kind of array list do I want? I need an array list that stores strings. Iím calling a constructor that takes no parameters. So I still need to specify an argument list for that constructor, which is where the open paren/close paren comes from. So the name of the constructor, the way you can think of it, is actually array list with the type specified, as funky as that may seem, and then the parameters are nothing. Okay?

And so what this now gives me is STR List point somewhere in memory that stores my array list, which is some object thatís gonna store strings in it. Okay? How do I use that? Let me show you a real quick example.

So because an array list is an object, it has methods on it. Okay? One of the methods I can do is I can say STR List dot add. And what add does, I would give it some string. So I might have some string line that is Hello, and I add line. What the add method does is it adds that element to the end of the array and grows the size of the array by one. So if I want to add a whole bunch of things to some STR List, I start off by creating a STR List, which is empty. So when I do this I get an array list, which is empty called STR List. And as soon as I do this add it grows to size one, and it now has the line Hello as the first element.

If I were to do another add, like say STR List dot add, and maybe I say There as another string and now it grows to size two and There is the second element. So add adds it, appends to the end, and grows the size by one.

Some other things I can do with STR Lists. I can ask STR Lists, or array lists in general, for their size. So thereís a method called size open paren close paren. What this does is it gives you back as an integer how many elements are inside your STR List based on how many youíve added. Okay?

Another thing you can also do is you can say, ďWell, itís great to be able to add all these elements, Mehran, but how do I actually get information out of my array of STR Lists?Ē What you say is: STR List dot get. So there is like getter, much like thereís a setter, and you pass it in an index, I. And so, what this says is get the element at the I position. So if Iíve added line here, which is Hello, thatís a position zero. When I add There thatís a position one. You can think of it an array thatís just dynamically growing as I add more stuff to the end. And the way I refer to the individual elements is with get and I still specify an index that starts from zero.

Okay? And this is pretty much all you need to know to be able to do Part 3 of hangman. And youíll see it in much more excruciating detail on Wednesday, but thatís all you need for now.

Any questions about array lists? All righty, then good luck on the midterm, Iíll see you tomorrow night.

[End of Audio]

Duration: 52 minutes