[ Chapter Index | Main Index ]

Answers for Quiz on Chapter 10

This page contains sample answers to the quiz on Chapter 10 of Introduction to Programming Using Java. Note that generally, there are lots of correct answers to a given question.

Question 1:

What is meant by generic programming and what is the alternative?

Answer:

Generic programming means writing data structures and subroutines that can be used for many different types of data. The alternative would be to write a new data structure or subroutine for each different type of data, even when they would all be essentially identical except for the type name. For example, a single generic sort routine can be used for sorting lists that contain data of any type. The alternative is one routine for sorting lists of integers, one for sorting lists of strings, one for storing arrays of real numbers, and so on.

Question 2:

Why can't you make an object of type LinkedList<int>? What should you do instead?

Answer:

LinkedList<int> is an attempt to use a generic class with a type parameter of type int, which is a primitive type. Generic programming in Java works only for objects, and not for the primitive types, so a type parameter of primitive type is not allowed. However, it is possible to use the wrapper class Integer in place of int. An object of type LinkedList<Integer> can be used almost as if it were actually a list of ints.

Question 3:

What is an iterator and why are iterators necessary for generic programming?

Answer:

One of the principle features of Java's generic programming framework is Collections. There are several types of collection (including LinkedList, ArrayList, TreeSet, and HashSet). In order to deal with all the different types of collection in a generic way, we need a generic way to access all the elements in a collection. An iterator makes this possible. An iterator is an object associated with a collection that makes it possible to traverse the collection (that is, to visit each of the items in the collection in turn). Code written using iterators will work for any type of collection. (Note, however, that explicit use of an iterator can often be avoided by using a for-each loop.)

Question 4:

Suppose that integers is a variable of type Collection<Integer>. Write a code segment that uses an iterator to compute the sum of all the integer values in the collection. Write a second code segment that does the same thing using a for-each loop.

Answer:

Using an iterator:

int sum = 0;
Iterator<Integer>  iter = integers.iterator();
while ( iter.hasNext() ) {
   sum += iter.next();
}

The statement "sum += iter.next()" relies on the automatic conversion from type Integer to type int. It could also be written "sum += iter.next().intValue()".

Using a for-each loop:

int sum = 0;
for ( int number : integers ) {   // ( Could also use "Integer number : integers". )
   sum += number;
}

Note that either of these two solutions will fail if integers contains a null value.

Question 5:

Interfaces such as List, Set, and Map define abstract data types. Explain what this means.

Answer:

An abstract data type is defined by the operations that can be performed on it, not by the way the data is actually stored or by the way the operations are implemented. An interface such as List defines operations that can be performed, but says nothing about how they are to be implemented. In fact, there can be many different implementations. For example, both LinkedList and ArrayList implement the List interface. They are different "concrete" data types that implement the same abstract data type.

Question 6:

What is the fundamental property that distinguishes Sets from other types of Collections?

Answer:

A Set cannot contain duplicate elements. Adding an item to the set has no effect if that item is already in the set. (Note that exactly what it means to say that two items are the same depends on the type of set. For HashSet, two items are tested for equality using the equals() method. For a TreeSet, the test for equality uses the compareTo() method from the Comparable interface or the compare() method from a Comparator.)

Question 7:

What is the essential difference in functionality between a TreeMap and a HashMap?

Answer:

The key/value pairs in a TreeMap are sorted so that the keys are in ascending order. (For this reason, it must be possible to compare the keys in a TreeMap, using a compareTo() method or compare(). Either the keys must implement the Comparable interface or a Comparator must be provided to do the comparison.)

Question 8:

Explain what is meant by a hash code.

Answer:

The hash code of an object is an integer that tells where that object should be stored in a hash table. A hash table is an array of linked lists. When an object is stored in a hash table, it is added to one of these linked lists. The object's hash code is the index of the position in the array where the object is stored. All objects with the same hash code go into the same linked list. In Java, every object obj has a method obj.hashCode() that is used to compute hash codes for the object. If the object is to be stored in a hash table of size N, then the hash code that is used for the object is Math.abs(obj.hashCode()) % N.

Question 9:

Modify the following Date class so that it implements the interface Comparable<Date>. The ordering on objects of type Date should be the natural, chronological ordering.

class Date {
   int month;  // Month number in range 1 to 12.
   int day;    // Day number in range 1 to 31.
   int year;   // Year number.
   Date(int m, int d, int y) { 
      month = m;
      day = d;
      year = y;
   }
}

Also, rewrite the resulting Date class as a record class. (See Section 7.4.)

Answer:

The interface Comparable<Date> specifies the method "public int compareTo(Date d)", which will be used to compare two objects of type Date. The compareTo() method must be added to the class, and the class must be declared to implement the interface. To compare two dates, first try comparing the years. If the years are equal, try comparing the months. If the months are also equal, compare the days.

class Date implements Comparable<Date> {
   int month;  // Month number in range 1 to 12.
   int day;    // Day number in range 1 to 31.
   int year;   // Year number.
   Date(int m, int d, int y) {
      month = m;
      day = d;
      year = y;
   }
   public int compareTo( Date otherDate ) {
           // Returns 1, 0, or -1 if this date is greater than, equal to,
           // or less than otherDate, respectively.
      if (year < otherDate.year)
         return -1;
      else if (year > otherDate.year)
         return 1;
      else { // Years are equal; compare months.
         if (month < otherDate.month)
            return -1;
         else if (month > otherDate.month)
            return 1;
         else { // Years and months are equal; compare days.
            if (day < otherDate.day)
               return -1;
            else if (day > otherDate.day)
               return 1;
            else 
               return 0;
         }
      }
   }
}

When this class is rewritten as a record class, the class's instance variables are listed in parentheses after the class name, and a canonical constructor is automatically provided. However, the Comparable interface is added to the class in the same way. Record classes cannot extend other classes, but they can implement interfaces. Of course, this record class could use many other improvements...

record Date(int month, int day, int year)
                        implements Comparable<Date> {
   public int compareTo( Date otherDate ) {
           // Returns 1, 0, or -1 if this date is greater than, equal to,
           // or less than otherDate, respectively.
      if (year < otherDate.year)
         return -1;
      else if (year > otherDate.year)
         return 1;
      else { // Years are equal; compare months.
         if (month < otherDate.month)
            return -1;
         else if (month > otherDate.month)
            return 1;
         else { // Years and months are equal; compare days.
            if (day < otherDate.day)
               return -1;
            else if (day > otherDate.day)
               return 1;
            else 
               return 0;
         }
      }
   }
}

Question 10:

Suppose that syllabus is a variable of type TreeMap<Date,String>, where Date is the class from the preceding exercise. Write a code segment that will write out the value string for every key that is in the month of December, 2021.

Answer:

I will give two solutions. One of them simply looks up each date in December, 2021 in the map and prints the corresponding value, if there is one. The other iterates though a submap that contains all the entries for dates in that month.

A solution using the map's get() method:

      for (int day = 1; day <= 31; day++) {
           // Get the info for one day in December, 2021
         Date date = new Date(12,day,2021); // The key.
         String info = syllabus.get(date);  // Get the value for that key.
                                            // (Can be null if there is no
                                            // entry in the map for this date.)
         if (info != null)
            System.out.println("December " + day + ": " + info);
      }


A solution using a submap (harder, but more efficient):

      Date startDate = new Date(12,1,2021); // Starting date for submap.
      Date endDate = new Date(1,1,2022);    // Ending date for submap.
                                            // (Remember that the end date
                                            // is not included.)
      Map<Date,String> decemberData = syllabus.subMap(startDate, endDate);
      for ( Map.Entry<Date,String> entry : decemberData ) {
         Date date = entry.getKey();
         String info = entry.getValue();
         System.out.println("December " + date.day + ": " + info);
      }

Using var to declare local variables, this could also be written:

      Date startDate = new Date(12,1,2021); // Starting date for submap.
      Date endDate = new Date(1,1,2022);    // Ending date for submap.
                                            // (Remember that the end date
                                            // is not included.)
      var decemberData = syllabus.subMap(startDate, endDate);
      for (var entry : decemberData ) {
         Date date = entry.getKey();
         String info = entry.getValue();
         System.out.println("December " + date.day + ": " + info);
      }

Question 11:

Write a generic class Stack<T> that can be used to represent stacks of objects of type T. The class should include methods push(), pop(), and isEmpty(). Inside the class, use an ArrayList to hold the items on the stack.

Answer:

public class Stack<T> {
   ArrayList<T> stack = new ArrayList<T>();
   public void push( T newItem ) {
      stack.add(newItem);
   }  
   public T pop() {
      if ( isEmpty() ) {
          throw new IllegalStateException("Can't pop from an empty stack");
      }
      int top = stack.size() - 1;  // location of top item
      return stack.remove(top);    // remove and return top item
   }
   public boolean isEmpty() {
      return stack.size() == 0;
   }
}

Question 12:

Write a generic method, using a generic type parameter <T>, that replaces every occurrence in an ArrayList<T> of a specified item with a specified replacement item. The list and the two items are parameters to the method. Both items are of type T. Take into account the fact that the item that is being replaced might be null. For a non-null item, use equals() to do the comparison.

Answer:

Since the method operates on ArrayLists, it can use indexed access with the get(i) and set(i,item) methods. These operations are efficient for array lists. I also give a second version of the method that uses a list iterator and is efficient for any type of list.

public static <T> void replaceAll(ArrayList<T> list, T oldItem, T newItem) {
   if (oldItem == null) {
      for (int i = 0; i < list.size(); i++) {
         if ( null == list.get(i) )
            list.set( i, newItem );
      }
   }
   else {
      for (int i = 0; i < list.size(); i++) {
         if ( oldItem.equals(list.get(i)) )
            list.set( i, newItem );
      }
   }
}


public static <T> void replaceAll(List<T> list, T oldItem, T newItem) {
   ListIterator<T> iter = list.listIterator();
   while (iter.hasNext()) {
      T listItem = iter.next();
      if ( oldItem == null ) {
         if ( listItem == null )
            iter.set(newItem);
      }
      else {
         if ( oldItem.equals(listItem) )
            iter.set(newItem);
      }
   }
}

(Note, by the way, that a replaceAll method is already defined as a static method in class Collections.)

Question 13:

Suppose that words is an array of Strings. Explain what is done by the following code:

long n = Arrays.stream(words)
               .filter( w -> (w != null) )
               .map( w -> w.toLowerCase() )
               .distinct()
               .count();

Answer:

This code counts the number of different strings in the array, ignoring case. It starts with a stream containing all the strings from the array. The filter() operation only lets non-null values through. This makes sure that there won't be a NullPointerExcetion in the next step, when w.toLowerCase() is evaluated. The map() replaces each string in the stream with a lower case version, so that there will be no difference between upper and lower case versions of the same string. The distinct() eliminates duplicates from the stream. And count() returns the number of strings in the resulting. stream, which now contains just one lower-case copy of every string that occurs in the array.

Question 14:

Use the stream API to print all the even integers from 2 to 20. Start with IntStream.range and apply a filter operation.

Answer:

IntStream.range(2,20)
         .filter( n -> (n % 2 == 0) )
         .forEach( n -> System.out.println(n) );

(IntStream.range() can be used to create a stream containing all of the integers 2 to 20. The predicate "n -> (n%2 == 0)" is true just for even integers, so the stream that emerges from the filter operation contains the numbers 2, 4, ... 20. Finally, we can apply an operation to each of the numbers of the stream by using the forEach terminal operator. The operation forEachOrdered would also work, but since the stream is sequential, forEach will print out the numbers in order. If we were using a parallel stream, it is possible that forEach could print the numbers out of order.)

Question 15:

Write a generic method countIf(c,t) with type parameter <T>, where the first parameter, c, is of type Collection<T>, and the second parameter, p, is of type Predicate<T>. The method should return the number of items in the collection for which the predicate is true. Give two versions, one using a loop and the other using the stream API.

Answer:

The first version uses a for-each loop, and uses the fact that a Predicate contains a boolean-valued function named test() for testing whether the predicate is true:

public static <T> int countIf( Collection<T> items, Predicate<T> pred ) ) {
    int count = 0;
    for ( T x : items ) {
        if ( pred.test(x) )
            count++;
    }
    return count;
}

The second version uses the stream API, with a filter() operation that lets through only the items for which the predicate is true. Note that filter() takes a parameter that is a predicate. Usually, the parameter is given by a lambda expression, but in this case, the predicate is pred, so we need to pass pred as the paramter to filter().

public static <T> int countIf( Collection<T> items, Predicate<T> pred ) {
    long ct = items.parallelStream()
                   .filter(pred)
                   .count();
         // .count() returns a long, but I want countIf to return an int
    return (int)ct; 
}

[ Chapter Index | Main Index ]