This leads to a dual understanding of something like the IntList class:
IntList
/ \
/ \
as client as implementor
We often just want to be a client of the class and not worry about how it does
something, but we also want to know that we could look into its implementation
details and understand them if necessary. Knuth describes this as solving a
problem at many levels of abstraction all at once.I pointed out that a few weeks from now when we get through with this IntList example and another example we're going to develop with linked lists, we'll be able to understand some very important concepts that are related to what are known as the Java Collections classes. We'll see an important application for interfaces and inheritance and we'll have a better understanding of a set of standard classes that people use all the time from the Java collections (in particular, ArrayList, LinkedList and various iterator classes).
I then discussed the new version of IntList (handout #5) that I passed out on Friday. I reminded people of the concept of preconditions. Some methods can work only if certain conditions hold. For example, the "get" method requires a legal index value. Whenever you find a method that has this kind of dependence, you should document it as a precondition of the method. It is also a common practice in Java to "throw" an exception if a precondition is not met. This is a clean way to stop the execution of the program and force the client of the code to fix their call on the method.
I mentioned that in some cases it is not practical to check the precondition of a method. For example, the binary search technique we are using relies on the list being in sorted order. But our very fast binary search technique would grind to a halt if each time we called it we checked to make sure the list is in sorted order. So we don't always check preconditions, but when it's easy to do so, we should. Someone asked whether there is a general "bad argument" exception and I said that Java has something called IllegalArgumentException that can be thrown when someone passes an illegal value to a method.
In the case of the get method in IntList it calls a private method called checkIndex that checks the bounds of the index and throws an IndexOutOfBoundsException if the value is not legal. Two other methods (set and remove) also call this same method. You are asked to include similar code for your solution to assignment #2.
I spent some time discussing the idea that there are three kinds of methods: constructors, accessors and mutators. I pointed out that in the documentation for the IntList class I list them in this order with a blank line between each group of methods. Constructors are special methods that can be called only in conjunction with "new". Accessors are "read only" methods that examine the state of an object but don't change it. Sometimes people refer to these as "getters". Someone pointed out that all of the accessors have return values, which makes sense given that their purpose is to examine some aspect of the object's current state. Mutators are methods that potentially change the state of an object (in other words, they are read/write operations). They are sometimes referred to as "setters".
This new version of IntList has several new methods in it and I discussed a few of them individually. First I talked about the clear method. The idea is to set the list back to being empty. I pointed out that this is done simply by setting the size back to 0. This doesn't seem quite right, because it means that the array has non-zero values in it. It seems like maybe we should blast the array with zeros to wash away the "dirty" values. But it turns out that we don't need to do that. We won't access those values until new values are added to the list, and those new values will overwrite these old values. In fact, a client would never be able to find out that these non-zero values are there. If someone tried to do a "get" on one of these positions, our code would throw an exception.
Someone asked if there isn't a memory issue. In general, the answer is "no". We have allocated an array that has a certain capacity and that memory is in use whether it's filled with 0's or whether it's filled with these old values. The one exception I mentioned is that for the ArrayList class where this is an array of references to objects, it is actually worth blasting the array with "null" values. That's because if the ArrayList holds on to a reference to an object, it might prevent the garbage collector from noticing that the object is no longer in use. But for these simple ints, there is no memory issue.
Then we looked at the isEmpty method and I used it as a way to talk about the "zen of type boolean" that novices don't quite appreciate. The isEmpty method is supposed to return true if the list is empty and false otherwise. Many novices would write it this way:
if (this.size == 0)
return true;
else
return false;
But why write it that way? We are saying, "If this test evaluates to true,
then return true and if this test evaluates to false return false." That would
be like having an integer variable x and saying something like:
if (x == 1)
return 1;
else if (x == 2)
return 2;
else if (x == 3)
return 3;
else if (x == 4)
return 4;
...
If in every case you're going to return the value that "x" has, why not just
say:
return x;
Similarly in our case we can simply return the value of the test rather than
including it in an if/else:
return this.size == 0;
I pointed out that I had seen this kind of mistake also with code people wrote
for assignment #1 where they said things like this:
if (unique == true)
But why test whether unique is true? It's of type boolean, so it already is
either true or false. Otherwise you might find yourself saying, "Okay, I have
tested whether unique is true and I want to know if that's true, so let's
say:"
if ((unique == true) == true)
But now that I've tested whether unique being true is true, I want to know if
that's true, so I'd say:
if (((unique == true) == true) == true)
I tried to make this a bit absurd on purpose to point out that these extra
tests just aren't necessary. You can simply say:
if (unique)
Having the extra test is dangerous because if you accidentally use assignment
instead of a test on equals:
if (unique = true)
this is the one case where the Java compiler won't warn you that you're doing
something strange (that you probably want "==" instead of "="). The other
version of this is that people have been saying:
if (unique == false)
This makes more sense because the test is actually doing something useful.
It's seeing whether unique is NOT true. But you can do this using the negation
operator:
if (!unique)
and that's considered better style.Then we briefly looked at the code for the contains method. I pointed out that the contains method calls the indexOf method. I use the "this" notation calling "this.indexOf(value)". As always, the "this" keyword is not required. If you just say "indexOf(value)", Java will figure out that you must have meant "this.indexOf(value)".
Then we looked at the addAll method. The idea here is that the IntList is given a reference to another IntList and that it adds all the values from the other list to the current list. I asked people if they noticed anything odd about the code and someone pointed out that the method is accessing the private data fields of the other IntList with references like "other.size" (versus other.size()) and other.elementData[i] (versus other.get(i)). This points out an important point about the "private" keyword. Private means private to the class, not private to the instance. Because we're inside the IntList class, we can access the private data fields of any other IntList object.
Someone asked whether it wouldn't be a good idea to go through the public methods anyway. There certainly is some value in doing so, but in some cases you'll find that you can't perform the operation or you can't do so efficiently without directly accessing the private data fields.
I spent the rest of the class time talking about the idea behind the next programming assignment. I said that given a String like "Alabama", we might want to count how many of each kind of letter appears in the String. This particular String has 4 a's, one b, one l and one m. The LetterInventory objects you are going to write are going to do this kind of counting. In examining a String, it will ignore the case of letters (uppercase and lowercase letters are lumped together) and it completely ignores non-letters. The class has get and set methods that allow a client to find out the count for an individual letter or to change the count for an individual letter. And it has a toString method that returns a String representation of the inventory (e.g., "[aaaablm]" for "Alabama").
Two of the more challenging methods to write will be the add and subtract methods. I pointed out that they are supposed to return new objects of type LetterInventory. For example, I will ask one LetterInventory object to add another LetterInventory to its counts and to return the result as a new LetterInventory object. The add operation will always succeed, but the subtract might not. In subtracting one objects counts from another, you might end up with a negative count. If that happens, the subtract method is supposed to return the value "null" instead of returning a new LetterInventory object. The value "null" is a special value for objects that indicates "no object".
In talking about the assignment, I noticed a minor typographical error in the hardcopy version of the assignment. In the description of toString method I had talked about 3 a's when I should have said 4 a's. I counted the number of a's in Alabama incorrectly when I made up the handout. The String that is shown obviously has 4 a's, not 3.
I briefly mentioned that the LetterInventory class will have some useful applications even though it seems a bit odd. For example, newspapers often have "word jumble" problems where the letters of a word have been rearranged. The LetterInventory class can be used to figure out whether two words have the same letters in them but in a different order (what we call "anagrams"). For example, the words "pears" and "spear" will both produce inventories of "[aeprs]".
We didn't have time to go over the iterator code that will become handout #6, so we're saving that for another day.