cs046 ยป

Contents

ArrayLists

Hello, and welcome to this new lesson. Today we're going to be taking about Array Lists. An Array List collects objects and all the objects in the Array List need to be of the same type. Now what would we like to collect? Me, personally I'd like to collect valuable paintings. So let's see how we would do that in Java. Here you see the rather long declaration of an Array List that can collect pictures. Let's work through the pieces. We're declaring a variable, called gallery, its type is an ArrayList, but whenever we have an ArrayList we need to also specify the type of the objects that it collects. That's the pictures here, so the whole thing here, ArrayList of picture, is the type of the gallery object. To the right you simply have a constructor call, where you again have to type ArrayList of picture. We have the new operator, because we make a new object off the ArrayList type and the parenthesis here simply mean that we pass nothing to the constructor. What we get is an empty ArrayList, which can, as we add them in, hold as many pictures as we like. Here, we add a couple of pictures to the gallery. The add method, takes as its argument, the object that we want to add. Once you've added objects to an Array List, you'll want to be able to do something with the contents. Let's look at that next

Elements

An ArrayList collects objects. We call those objects the elements of the list. Here's one way of thinking about an ArrayList. You can think of it as a sequence of mailboxes. Here is how you get an element out of an ArrayList. Remember that gallery was an ArrayList of pictures. The get method can get a picture out of that collection. The argument of the get method is called an index and as it happens in Java the index values start with zero. So the first element is at position zero. The second element is at position one, the third at position two and so on. The get method returns the elements stored at the index position. In our case that's the initial element and we store that in this variable. What if we wanted to get at the last element? Then we need to know how many elements are stored in the ArrayList at this time. The size method tells us that. So gallery.size is the number of elements that's currently stored in this particular ArrayList. Since the first index is zero, the last index is one less than the size. Look at over here. This list here has length five and the last element has index four. Now once we have the last index, we can again use the get method passing at the last index to get the last element out of here. Here you've seen how to access elements individually. More often than not, we actually want to access all of the elements in a loop. So let's have a look at that. In order to work with every element in an ArrayList, you want to call the get method for every valid index. That means zero, one, two and so on up to the size minus one. So here's what we need to put into our four loop. I starts at zero. It get incremented at every step and we stay in the loop while i is less than the size of the ArrayList. So this is the classic loop to traverse all of the elements in an ArrayList. I takes every legal index value, for each i we get the element stored in the ArrayList and then we do something with that element. You will get to try that right now. Go ahead and write a loop that draws every picture in the gallery.

Drawing All the Elements

Okay, here is our Array List of pictures. A bunch of pictures have already been added and our job is to draw them all. Here is the loop that goes through all of the valid index values. We get the IF picture and we'll draw it. Let's see what happens. Oh yuck. It drew them all on top of each other. I guess it makes sense each picture has as its top left corner 00. So I'd like you to do a better job with this. Draw the IF picture so that its upper left corner is 100 times i for x, and leave y at 0.

Drawing All the Elements

Alright, let's do that. You remember that to move a picture one needs to call the translate method. Here we go. And let's see what this looks like. that's a little better. But still that first picture here, is very long. And the next one overlaps it. And let's see what we really want. What we really want to do is have the first picture appear at zero zero. And have the next picture appear a little bit after the last x coordinate of the first one. We could call get max x to get that last x coordinate. And then add a small value to it. This way they would be ten pixels apart.

Look at the Element Before this One

Specifically, I want you to do the following. Remove this call to translate. We'll re-arrange the pictures in a separate loop. In this loop we will look at a picture and the one to the left of it. The picture is at index i and the one to the left at index i minus 1. Call getMaxX on the picture to the left. And use that value to position pic, go ahead and give it a try.

Look at the Element Before this One

Lets tackle this together, here we have right most value of the picture to the left, we will add 10 and then we translate pic by that amount that's the statement, now we need to do that for all of the pictures so I need to add the loop header, I have done that often enough that my fingers can do it on auto pilot, here goes, pretty soon your fingers will be able to do that too. Let's go and compile and let's run the program. Mm-hm. That did not seem to work now, did it. Let's see. The program crashed and I'm told that there is an ArrayIndexOutOfBoundsException and index that was out of bounds was -1. Well minus one is not a valid array index. And why would I have gotten a negative one? Well, look at this. i is zero, so over here, this i is zero, and then the i minus one is, zero minus one, and that's bad. Now the problem is, that when I'm at the zeroth picture, that's the initial picture in the sequence, there is nothing to to the left. So, the remedy is, to start here, with i equals one. The zeroth picture to stay where it was. Picture at index one then gets moved to the right of the one at index zero. And that's all good. So in this case, my fingers shouldn't have been on auto pilot. But I should have thought through what values for i I actually want. It's very very common in actual programming to get these kinds of errors, and I wanted to show you how it looks like when you do. Now let's try this, and look at that! Our pictures are finally arranged in a neat sequence. So I want to show you one more thing, here we have two loops, this one arranges the pictures, the one over here, draws the pictures. Now the second loop is so simple and so common that there is a shorthand for it called the enhanced for loop. Instead of letting the index value i go from zero through all the valid values and then using the index to get the ith picture. You can do the following, you can simply write for then you make a variable for the picture, then you write a colon and then the array list that you want to traverse. This loop sets pic to the first element in the gallery, or I guess I should say the zeroth element. Then to the element with index one, then to the element with index two and so on. So pic assumes. In turn all of the values off the array list. Each time the loop is entered, and in this case, pic is draw. You could do other things as well, of course.

Enhanced For Loop

Could we have done the same thing with a loop over here? Not really because in this loop we didn't traverse all of the pictures, we skipped the zeroth one. You can only use the enhanced for loop when you look at all of the elements of an array list. And there's another reason when you use the enhanced for loop you don't actually know the index value. Of any of the elements. And, over here, we needed the index value because we had the i-th element, and then the i minus first element. But, I'll give you a challenge question, and that is, to rethink the logic of this loop, and rewrite it, as an enhanced for loop, like this. And to make that a little bit easier, you get to position the first image, at offset ten. So put ten pixels before the first image, before the second, before the third, and so on.

Enhanced For Loop

This problem is a little bit tricky, because you have to completely rethink the approach. Previously, we looked at a picture,and the one to the left. But when we use an enhance photo, we only get to look at one picture at a time, so we have to remember something from the past. The way I've done it is, I would remember the rightmost position of the previous picture. Let me show you. I have an enhanced for loop, and when I'm done positioning the picture, I remember its rightmostX value. So when I reenter the loop with the next picture, then I can position it 10 further than the rightmostX value. And they're always spaced apart nicely. What about he first picture? If I start the rightmostX at 0, then the first picture ends up at offset 10. So that's the answer. And now when you look at these two loops, you can see that we can actually merge them. So we do the positioning and drawing in a single loop. That's enough about pictures for right now. Sarah will show you another application of array lists. She'll revisit a class that you've seen in lesson three. The person class that collected friends, at that time we did it in lesson than perfect way by just having one long string of friend names. Now that you know how to collect objects, she'll collect the friends in an array list. Alright, over to you Sarah.

Friends Done Right

Now that you know a little bit about ArrayLists, it's time to revisit an old friend, the Person class. I removed some of the methods and added one new one. GetFriend gets the ith friend, but as you can see it's a pretty ugly method. This is bad code. I wasn't careful when I wrote it and it's messy. It would work alright if my friends are named Madonna, Sting, and Cher. But most people have spaces in their names. Maybe I could fix this by separating the names with commas or semicolons. I could change the separator here. But that won't really fix the underlying problem. The underlying problem is that reality has structure and we need to choose the right data types to model that structure. In our case we have multiple individual people. A string of names isn't the right way to save a bunch of individuals who all play a similar role. An ArrayList would be much better for this. Saving an ArrayList of Person objects, instead of just a string of friends would allow us to do a lot of cool things. For example, we could add a string nationality to each person. And then you can get a list of all the countries your friends are from. But let's work our way up to problems like that. First, let's store the friends in an ArrayList of strings without changing the observable behavior. In software engineering this would be called refactoring. Refactoring is when you reorganize code. The implementation changes. The observable behavior does not change. Often we do this to make it easier to add new features. Now I want you to refactor the person class. I'll give you some tests so you can make sure nothing breaks in the process. You'll need to update the instance variables. Save the friend's names in an ArrayList of strings. You'll need to update addFriend, getFriend and getFriends. We'll skip unfriend for the moment, but we will come back to it later. And I'm going to give you a hint. Do you remember the toString method from lesson two? ToString returns a representation of the object, and works pretty well for ArrayList of strings. Let me show you what it does. If I create an ArrayList, strs, and add a couple of strings to it, like this, and then I call the toString method. The toString method returns, a string, that has the values separated by commas and spaces and then surrounded by brackets. This is pretty close to what you want for the getFriends method. For the getFriends method, you just want the values separated by commas and spaces. And here's one last hint. If you get an error that Java doesn't know what an ArrayList is, you might need to import it.

Friends Done Right

To do this, I'll first add a new variable. I'll call it 'friends two for now. Now in the constructor I need to initialize friends two, and there's that error. And you need to import it. So far so good, now I'll fix add friend. I'll add the friend to both of the lists that I'm keeping track of right now. I tried to add the whole friend instead of just the name, much better. Let's see if the tests are still passing. Person tester, looks like things are matching, so I'll go to getFriends. Instead of using fiends, I want to use friends2. But friends2 is an array list, so I need to get a string representation of it. But toString returns brackets around what I want. So I'll need to remove the brackets using substring. I'll put it in a variable, and now I'll return substring, starting with the second character and stopping before the last character. Let's see if tests still pass. Looks like everything is still matching. Except that there's a trailing comma right here. But that's the getFriend method. So, I will come back to that. And now for the especially satisfying one, I'll get to delete all of this code, and replace it with one line. I'll get the element of the array list at friend index and then return its name. And now everything is matching what we wanted to, but I need to clean up my extra unused variables. I still have this private string friends and I am not using it anywhere, or atleast I shouldn't be. So I'll delete it there, and here, and here and I think that's all of it. But now friends2 has a sort of silly name, so I just want to change friends2 to be friends. So I will use Find, replace and replace all of the occurrences creating an extra variable might of look like extra work, and if you didn't do all of that that's fine. I did it to show you how you might approach a much larger refactoring. Sometimes when you're working on a very big refactoring, it's good to make sure that everything still works at each intermediate stage. You'll learn more about that if you take a job as a software engineer.

Get Num Friends

So what did all of that refactoring get us? Well, think about how you would implement this method now. Before, we had to create a local variable and remember to increment it when we added a friend and decrement it when we took away a friend. Implement getNumFriends, think about the ArrayList methods we talked about that might help you. You can do this by adding one line.

Get Num Friends

In the person class, we can now implement the getNumFriends method by returning the size of the friends ArrayList. Looks like it worked.

refractoring

Storing our friends in an ArrayList instead of a string made it easier for us to add some useful features. Now friends can have spaces in their names and I can have multiple friends with the same name. It's easy to answer questions like, how many friends does someone have or who is the fifth friend on my list? But you may have noticed that we haven't touched the un-friend method. For that we would need to modify the ArrayList, back to Kai to tell us how to do that.

Modifying an ArrayList

Now you've had a lot of practice, making, and traversing array lists, but what if you want to modify their contents? You know how to get an element, and if you want to change it, you use a very similar method, the set method. So, over here, we're calling set, with an index, and the new value. Whatever was there before at position two is now replaced with this new value. In the next exercise you will see a couple of lines of code involving get and set that try to swap two pictures in our gallery but when you run it you'll see it's not working. Your job is to fix it. Here's the bad code, let's see what's bad about it. When you run the program, then the gallery looks like this. Clearly it is not swapping. The pictures had position one and two. Instead, there's seems to be a gap here. Let's, first of all, understand that gap before we go and fix it. Here's the original gallery. Let me write the index values so it makes it easier to follow along what happens. Now, we're taking the element at position one, that's this fellow here. And now we're setting this one here to this picture. So now, over here, this element is also that same guy, pardon my drawing skills, obviously I'm not Gauguin. We get that's this fellow again and put him into slot one. So what we would expect is to see him twice maybe. Except remember that what we we're having in the array list are not objects, but object references. So here's what the array list really looks like. The zero slot, as a reference to this object. The one and two slot have a reference to the exact same object, and then the three and four point to these ones, and I won't draw those arrows. The point is that these ones are the exact same object, and so it's drawn twice, but you don't see that because it gets drawn on top of itself. The gap was just an artifact of the positioning. Never mind the gap, what's important is that if you first copy this one over here you wipe out the element that's in here and then when you copy back then you just get two identical values in the array. That's no good. So what we need to do is instead of wiping out the bridge here at position two, we need to save it. Let's do that. Here we're saving the old value. At slot two, then we can set slot two to what we want. And now here, instead of using the new value, we'll use the old one. I'll go ahead and run this and you'll see that the elements at one and two are swapped. Here you see them. Get and set are certainly the most basic operations on an array list. But there are a bunch of others that are also quite convenient. Let's have a look at those.

Modifying the Contents

The add and remove methods, let's you add elements or remove them at arbitrary index positions. So if we add a bunch of pictures and now we add one at position 0, the new one gets added here and what used to be position 0 is now position one. What used to be position one is now position two and so on. Now let's look at remove, here we remove the element at position two. And the other offsets of course, are now different. Note that you've seen a different version of the add method when we first learned about array lists. That method did not have a position, when you omit the position, then add simply adds it at the end of the array list. In the next exercise I'd like you to put add and remove to work. Here's what I want you to do. When you have an array list of pictures, I want you to slide the last one to the front so that all the others get shifted to the right. Go ahead and give it a try.

Modifying the Contents

The task at hand was simply to remove the last element off the list and insert it as the first one. Let's look at the code, the index of the last element is the size minus one. That's the one that we remove. Now as it happens the remove method returns the element that it was removed. Now you might say that's not fair, how was I suppose to know that? So let's say that you didn't. In that case, you could have done it in two steps. You could first get the element and then remove it. Either way will work. Let me get back to my original way because it's a bit shorter. Now that we've removed the last element we simply stick it at the very beginning, like this. And there you have it, what was previously the last element is now the initial one. Sara has a couple more exercise prepared for you where you practice working with set, add and remove. Have fun.

Books To Read

I'm keeping a list of books I want to read. Realistically, this would probably have 50 items in it, but right now I'll keep it short. I'll start reading again when you're writing your own programs from scratch in Java. Let's say there are six books in my list to read for now. I'll store them as strings in an array list, so they would be indexed like this. For now I'll store them as strings to make this exercise less typing, but if I were doing this for real, I would probably make a book class, so I could store authors and my friend who recommended the book to me. Now a friend just recommended that I read Why Zebras Don't Get Ulcers. I've decided that I want to read it after I read Night Watch but before I read Next. What would method should I use to insert Why Zebras Don't Get Ulcers after Night Watch and before Next without removing anything from the list?

Books To Read

Originally, I create the list by using add. And now I want to insert an element without wiping away anything. I can't just use the add method because that would add it on to the end of a list and I want to put it in the middle. So I'll specify the index where I want to add it. So the index I would want is two. Now I always forget whether the index or the element comes first, but that's okay, I can always check. All I have to do is search for ArrayList, Java I'll search, for add, and here I can see the index comes before the element. So the index I wanted was two. And I'm adding another book. And now when I run the demo it'll print The Eyre Affair, Night Watch, followed by zebras and then next, just like I asked.

Lost In A Good Book

So I actually read the Eyre Affair already, but it was really fantastic and I want to read the sequel. So instead of deleting the Eyre Affair, I want to put the sequel, Lost in a Good Book, on my list in place of the Eyre Affair. What method should I use to replace the Eyre Affair with Lost in a Good Book?

Lost In A Good Book

So back in the book list demo I have my list of books to read and here I want to replace the Eyre Affair with the sequel. When I want to replace an element I use the set method and the Eyre Affair is element zero. So now that reference at element zero will be a reference to Lost in a Good Book instead of the Eyre Affair and you can see this by running the method again. Now it starts with Lost in a Good Book.

Lost In A Good Book 2

Wait a minute, I've already read The Brain That Changes Itself. Who put that there? Please take that one off the list for me.

Lost In A Good Book 2

To take The Brain That Changes Itself off the list, I first have to figure out what its index is. Originally, it was three. Zero, one, two, three, but then I added another one, before it, so now it's four. So I'll remove the item at index four. I think you're more familiar with basic ArrayList modifications now. Let's go back to Kai to talk about, how to do computations that take the entire ArrayList into account.

Array Algorithms Sum Over All Elements

In this section, we'll be talking about some common algorithms. I'll explain to you the problem that we want to solve. I'll explain to you the general algorithm and then I'll leave it to you to implement it in Java and then we'll talk together about the implementation. Let's start with the algorithm to compute the sum of values in an ArrayList. Suppose we have a bunch of pictures that we want to arrange horizontally, the total width of all of them depends on the sum of the widths of all of the individual ones. To compute the sum, we'll of course need a variable to hold it. And I'll just write it in a pseudo-code here. Now for each element in the array, add to the sum to measure of that element. And I'm writing it in this generic form so that you can reuse the algorithm for other situations. In our case, the element is a picture in the ArrayList of pictures. And the measure is the width, and here we're summing up the various widths. But in other situations you may be, if wanting to compute some other things, maybe the prices of some articles. So that's the general algorithm, now your job will be to complete code for the specific case of summing the width of pictures. So here I've have set up the ArrayList of pictures for you. Here is a statement to print the result and your job will be to put in the Java code for the algorithm that I've just described. Have a go at it and then we'll compare notes.

Array Algorithms Sum Over All Elements

So here is the algorithm that we now need to translate into Java. Let's do it. I declare a variable to hold the sum. I declare a loop to visit all of the pictures in the gallery. The enhanced photo will do nicely here because I need to visit all of the pictures and I don't care in which order. For each picture, I compute it's width and I update the sum. At the end of the loop the sum will be the sum of all of the widths and here it is printed. That's all. Let's move on to our next algorithm.

Array Algorithms Max and Min

In our next algorithm, we want to find the largest element in an array list. Again, let's look at the example of our pictures. We might want to know the largest one, to know how much vertical space we need on the wall. Or maybe we want to center them all with respect to the largest one, then we need to know the largest one first. In this algorithm, we start assuming. That, the first element, or rather the element at index 0, is the largest one. Then we look at all other elements, and if an element is larger, by some measure, than the largest element, then we change our mind, and now say the largest element, is the one that we've just seen. So in this example, for example, we would start off by saying, oh, the first one that we've seen, that's the tallest picture. Then we move onto the next one, and say that one is taller so I'm changing my mind, and now this one is now the tallest. this one is even a bit taller, so that one must be the tallest. Now this one here is not as tall so we no longer change our mind. And the last one that was considered to be the tallest is in fact, the one. Just like we've done before, I now leave it to you to implement this code in Java, and this time I want you to actually draw the tallest picture. Go ahead.

Array Algorithms Max and Min

Alright, let's do it together. The algorithm started out by assuming that the tallest one is the one at position zero. Now, we want to visit all other elements. For that, we can't really use the enhanced for loop, that would visit all elements including the one at zero, which we no longer care about, so we'll use a regular for loop. Here's the loop. Notice that i starts at one, and not at zero, because we no longer want to look at the element at index zero. With this loop, we only look to the index values, and we still need to get the element at that value. Now we're ready to compare the current one against the tallest one. That comparison is here. In that case, we change our mind, and say the tallest one is no pic. When you run the code the tallest one will be displayed, and it's this one. Let's move on to another algorithm.

Array Algorithms Count Matches

In this algorithm we will count all of the elements that match a certain criteria. When you have a picture, we say that the picture is in landscape orientation if it is wider than it is tall. Most, but not all of these pictures, of course, contain a landscape. We say that the picture is in portrait orientation if it is taller, than it is wide. Now let's say we have a bunch of pictures and we want to count how many of them are in portrait orientation. That's an example of a counting problem, in general you keep a counter. You visit each element. If the element is a match for whatever it is you're looking for you increment the counter. What does it mean to be a match? Well that depends on the problem. If you have an array of bacteria, we might be looking for the ones that are beneficial. If you have an array of pictures, like we have in our example, we happen to want to know the ones that are portrait. Those are the ones for which the height is greater than the width. Now that's your job in the next quiz. Complete the program so that it counts, how many pictures are taller than their way.

Array Algorithms Count Matches

Our job here is to figure out how many of these pictures are in portrait orientation. It's a counting task. We start by declaring counter. Now, we want to look through all of the elements of the array list. And since we want to go through all of them, we can use the enhanced for loop. We consider the picture a match if it's taller than it is wide. And it seems a good idea in this case to make a comment to explain that. And when we do have a match, then we increment the counter, and that's all. When we run the program, we're told that there three matching pictures. It would be kind of nice to know which ones they are, and we'll get to that soon.

Array Algorithms Find the First Match

In the previous algorithm you've seen how many elements match a condition but we didn't get to see any of the elements that match. Let's start modestly and say we want to see the first one. That's a match. So here in our series of pictures we just want to find the first one that is a portrait which I guess here just happens to be this one. The difficulty with this algorithm is that we don't really want to look at all of the elements, we want to stop as soon as we have found one. Let's set a Boolean variable. We'll keep looking while we haven't found a match. If the ith element matches, then we set found to true, and otherwise, we increment i. We still need to be clear about what i is. i should start at zero, and of course i shouldn't get too large. It needs to be less than the size of the collection. Now when we terminated this loop there are two possibilities. Maybe there wasn't any match in there at all. You could imagine a picture gallery only with landscapes. But if there was at least one match, then i is the index of that match. Once again it's your turn. Draw the first portrait in the gallery.

Array Algorithms Find the First Match

As you see in the algorithm for finding the first match was a bit more involved, and it looks like our friendly [INAUDIBLE] 's have given us some more starter code. We have an integer index that starts at zero. We have a boolean variable to keep track of whether we already found a match. Now, we have to keep looking while what? First of all, while we haven't yet found a match, and while we'll still have a chance of finding one. Now I is the index. We need the actual picture at that index. Here it is. We need to check whether it's a match. It's a match if it's taller than it is wide. Now if it is a match, then we set found to true. Otherwise, we keep on looking at the next position. Finally, if we have found a match, then we need to draw it. Where do we find it? Well, at position I. So we get it from here. When you run the program, it shows the first match. It happens to be this one. It might be nice to know what all the matches are. And as it turns out, that's actually easier to do then finding the first one. Let's see how to do that.

Array Algorithms Find All Matches

You've seen how to find the first match now we want to find them all. In our picture example we just want to collect all of the portraits. This one, and this one. Now if we want to collect them we need to put them somewhere. And you just learned how to collect stuff, namely with an ArrayList. So we have two ArrayLists, the one that contains the elements that we inspect and the one in which we will collect our matches. Now for each element in the original ArrayList we check if it's a match and if so we add the matching element to the ArrayList matches. When this loop is complete matches contains all matches. Like I said this one is actually simpler because we don't need to keep track of whether we have found the first one we don't need to stop after we found the first one. Go ahead and implement it in Java.

Array Algorithms Find All Matches

Here's the starter code that we were given. We were already given the declaration, for this variable, but we still have to initialize it. And down here is, the loop, that we've had at the beginning of this lesson, that arranges, all of the pictures. This time, all of the pictures inside matches, so that they appear side by side. Our job is, to fill up, the ArrayList matches. We need to initialize the variable, and here is the expression. We called the new operator, because we want to have a new object and the type of the object is ArrayList off the picture. The parenthesis here, again, just means that we call the construct. Next, we loop through all of the pictures in the original array list. For each one we decide whether it's a match. And so we added to this ArrayList, that's all. As it happens with this set of pictures there are two matches. Those of them are displayed here. Now you've seen quite a few useful algorithms, but maybe your getting a bit tired of our galleries here. Go ahead and practice them with Sarah in a different context.

separators

Iterating over structures like ArrayLists is very important. So let's make sure you've got this down. Let's return to the getFriends method. It was pretty convenient that the two string method printed out almost exactly what we wanted before. But how would we have printed the names of friends without the two string method? Or what if we wanted to use a semicolon instead of a comma? Lets update the getFriends method so that it takes a string separator as a parameter. It should still return a string. You should use the tester I wrote to check your code. This method is a little bit like a sum over all the elements, but you're putting together a string instead of a sum of numbers and you'll need to be careful at the edges. You only want to print separators in between names, you don't want to print one after the last name.

separators

In the new space for the getFriends method I want to start by creating a string that I can use to collect all of the names. Now I'll want to add all of the friends. So I'll loop through all of the friends, one at a time, and I'll add the separator and the ith friend's name onto that variable I was using as the collector. But as this is right now it's going to print out a separator before the fist name. So I need to look for a special case. In the regular case, where we're not looking at the very first friend, we'll add the separator and the friend's name. But if we are looking at the very first friend, then we just add the friend's name. I'll just fix a couple syntax errors, and I'll remember to return that variable that I used to collect all the names and now when I run the tester, I can see that it works with whatever kind of separators I put in, whether it's a semicolon, a vertical bar, or a unicode heart.

Unfriend Revisited

While we're looking at the person class, we didn't implement the unfriend method when we refactored our code. But now you know how to remove items from an array list. So let me see, if I want to remove a person nonFriend, what if I try getting the name of nonFriend, going through the list to find its index. And then removing that index. Is there anything wrong with this? Refactoring to save an ArrayList of the friends names was a step in the right direction, but not enough. If I have two friends with the same name, I wouldn't know which one to remove. In fact, I can't even tell if I have the same friend in here twice right now. I shouldn't just be storing a list of the friends name, I should be storing a list of the person objects, associated, with each friend. So let's refactor again. I'll create a new variable, that's an array list of person, and I'll initialize it in the constructor, I'll make my array list of string, that I called friends before, into an array list of person. And I'll have to fix the way I initialize it in the constructor. And let's look at that implementation of the get friends method with the separator. Now I need to actually get the name out of the friend stored at this position. I'll show you what happens if I don't do that. Whenever I try to print out the result of get friends, instead of printing the person's name, it's printing the class, and this weird jumble of symbols. Right now, the array list two string method, doesn't know how to make a string representation of a person. So it just prints the reference. These symbols make sense to the computer but not to people. So to avoid that mess, in the getFriends method, I'll get the name from the front and add that. And I'll do it in both spots. Can you finish the rest of this refractoring?

Unfriend Revisited

So, I'll pick up where I left off. I wrote those tests to protect the functionality of the person class. So, I can run them again to find out which method's broke when I changed the friends variable. Looks like the first thing that's broken is that I'm trying to add a string into my array list of person. So, I no longer need to get the name out of the friend before adding it. If I run the test, it looks like the getFriends method is still broken. But the getFriends method that takes a separator is good. The get number of friends method seems to be working alright still. So I'll need to look at this original getFriends method. When we run the two string method on the friends array list, it doesn't have a good way of printing a simple representation for each friend. I can think of two convenient solutions to this problem. One possibility is to delete this, and just use the other getFriends method, that we already fixed. I'll just call getFriends, and pass in a comma and a space as a separator. And now if I run the test, the getFriends method prints what I would hope.

Another Way to Implement Get Friends

But there's another way I might have implemented this getFriends method. I could just add a toString method to the Person class. If the toString method returns the name, then I could implement getFriends the way I did before. So here's approximately what I had before, and if I run the tester again, I can see that the getFriends method is working. This is because when I called toString on the arraylist of Friends, it uses each friend's toString method, to get it's name. Well, actually just to get a representation of it, which in this case, is the name. This implementation will work, so long as I don't want the person to return something more than the name, in its toString method.

Implementing Unfriend

That last refactoring made our code much better, now when we remove a friend, we can be sure we are removing the right friend. Next you're going to implement the unfriend method but first I want to tell you a secret, classes can have secret methods, here is an example, this private helper method can't be seen outside of the person class, they are only used inside to help with other methods. This one searches for a friend and returns its index. If it doesn't find the friend, it returns minus 1. You should implement the unfriend method and you can use find in your implementation.

Implementing Unfriend

Now that the friends are in an array list. To remove a friend, I just needs to know its index, and then I can call friends.remove, and that one will be erased, and the indexes will be fixed. In BlueJ, that would look like this. I would find the index of the nonFriend, using the find method, and then remove the friend, at nonFriendIndex. But I need to be a little bit careful, nonFriendIndex could be minus one. I can't remove the person if they're not there to begin with. So if the nonFriendIndex is not minus one, then I remove the friend. Otherwise, I don't do anything.

Talk To

What if I want to rearrange my friends list, based on who I talked to last. I'll add a method, talkTo, which takes a friend, which, wherever they are on the list, will take them, and move them up to the front of the list. There's one odd situation we would need to think about. What should happen if the given person isn't a friend? To decide this, we would need to think about this situation we're modeling. Do you add every person you talk to, as a friend? That would be pretty cool. We'd all have a lot of friends, but I think that's not realistic. So in this case, let's say if you talked to somebody who isn't a friend at all yet, nothing changes. How would you implement the talkTo method?

Talk To

I'm going to use the Find method again. I need to find the index of the person I want to move. In this example it would be four. Then I need to remove them from that spot so that I won't have two copies of that person in the list. And then the indices would change accordingly. Then once I remove them, I need to add them back at the beginning. I will use add instead of set. Because I don't want to wipe away whoever is at the front right now. I just want to move everything down by one and have the element that use to be here right here. Then I want to add them at the front. I'm going to use add instead of set because I don't want to wipe away the zeroth one. I just want to move everybody down. So now this will be zero. This'll be 1, 2, 3, 4, 5. In BlueJ that would look like get the old index by finding the person and then if that person is already a friend, we remove them from their old position and insert them into the zeroth spot. If they're not already a friend, then we don't have to do anything.

Removing Mean Friends

Now for the last method we'll write for the friend's class, at least for this lesson. It's possible right now for John to have TJ as a friend and TJ not to have John back. Let's write a method, removeMeanFriends, that removes all of the friends that don't like John back. So for example, if John has friends, TJ, Maria, Jamesha and Joe. Let's say Jamesha and Joe both like John back, but TJ and Maria don't. So we want to remove TJ and Maria from John's friends list. So in this case we'll start with TJ at index zero. So we'll remove TJ from the list. Now the list gets re-indexed. To look at the next person in the list we need to look at the zeroth person again. So we can't just have a counter variable that we increment by one each time. We look at Maria and Maria also doesn't like John. So we'll remove Maria and the rest of the list will get re-indexed again. So yet again to look at the next person we have to look at the zeroth person. We look at Jamesha and Jamesha likes John, so she should stay in the list. We'll increment the counter and look at the next person. Joe likes John, so we'll keep Joe in the list. So we should increment the counter variable and look at the next person, which would be at index two. But two is no longer a valid index. Even though it was, originally. So we're done.

Is This Code Correct

What if I try to code the removeMeanFriends method this way. What's wrong with this code? Sometimes it will not remove enough friends, sometimes it will remove too many friends, or sometimes an Index Out of Bounds exception will occur. As a hint, this condition means, this person is not in person i's friends list. This question is diffuclt. You don't have to get it right on the first try.

Is This Code Correct

The answer is, sometimes it will not remove enough friends. Let's trace through an example and talk about why. For this John example, in the for loop we start with i is 0, i is less than the number of friends. The friend at position 0 doesn't like John, so we remove that friend. And now the indexes of the friends change. Whereas before this was 0, 1, 2, 3. Now, it's 0, 1, 2. So we'll check if the friend at position 1 likes John back. The person at position 1 is Jamesha, and Jamesha does like John back. So we skip over this, and come back up to the top of the loop. Now i is 2. So we check if friend 2 likes John back, friend 2 does like John back so we'll come back up to the top of the loop skipping the remove step and now i is 3 which is now less than the number of friends so we're done but Maria never got removed. After removing TJ, Maria's index went from 1 to 0, but the counter in the loop went from 0 to 1. So we never checked whether Maria should be removed or not. This code will sometimes skip friends and not check if they should be removed.

Implementing Removing Mean Friends

Now it's your turn to code the Remove Mean Friends method in BlueJ. I'll show you some working pseudocode, but feel free to try it yourself first, and then come back to look at the pseudocode. We'll create a variable i, which starts at the beginning of the friends list. Now, while i is a valid index of friends, we either remove the i-th friend or increment i. We remove the ith friend if the ith friend doesn't have this person as a friend. And otherwise we increment i. Kai would like you to pay close attention to the answer to this question, even if you get it right. This algorithm is going to be important again, later in the course.

Implementing Removing Mean Friends

To code this in BlueJ, we'll start by creating that int i which we're starting at zero. Now, while i is a valid index, so it's less than the size of friends, we either remove the i-th friend or increment i. So, if the condition holds, then we remove the i-th friend. Otherwise, we increment i. And the condition is the same one that we saw in that buggy version. We get the i-th friend and then try to find this person in the i-th friend's friend list, and if we don't find them, that means it isn't a mutual friendship. And we're removing that one. So we get the i'th friend, and then try to find, this person, in that person's friend list. And if the index of this person, is negative one, then we know that the friendship, isn't mutual, and we should remove that friend. Now let's test it. Looks like our expectations match.