1. This site uses cookies. By continuing to use this site, you are agreeing to our use of cookies. Learn More.

Exercice Collection

abdelouafiSep 27, 2016

    1. abdelouafi

      abdelouafi Administrator Staff Member

      Messages:
      267
      Likes Received:
      8
      Trophy Points:
      18
      Joined
      Sep 13, 2016
      TD
      Chapter 12. The Collection Interface
      The interface CollectionFigure 12.1) defines the core functionality that we expect of any collection other than a map. It provides methods in four groups.

      Figure 12-1. Collection
      [​IMG]


      Adding Elements

      boolean add(E e) // add the element e
      boolean addAll(Collection<? extends E> c) // add the contents of c

      The boolean result returned by these methods indicates whether the collection was changed by the call. It can be false for collections, such as sets, which will be unchanged if they are asked to add an element that is already present. But the method contracts specify that the elements being added must be present after execution so, if the collection refuses an element for any other reason (for example, some collections don't permit null elements), these methods must throw an exception.

      The signatures of these methods show that, as you might expect, you can add elements or element collections only of the parametric type.

      Removing Elements

      boolean remove(Object o) // remove the element o
      void clear() // remove all elements
      boolean removeAll(Collection<?> c) // remove the elements in c
      boolean retainAll(Collection<?> c) // remove the elements *not* in c

      If the element o is null, remove removes a null from the collection if one is present. Otherwise, if an element e is present for which o.equals(e), it removes it. If not, it leaves the collection unchanged. Where a method in this group returns a boolean, the value is true if the collection changed as a result of applying the operation.

      In contrast to the methods for adding elements, these methodsand those of the next groupwill accept elements or element collections of any type. We will explain this in a moment, when we look at examples of the use of these methods.

      Querying the Contents of a Collection

      boolean contains(Object o) // true if o is present
      boolean containsAll(Collection<?> c) // true if all elements of c
      // are present in the collection
      boolean isEmpty() // true if no elements are present
      int size() // return the element count (or
      // Integer.MAX_VALUE if that is less)
      The decision to make size return Integer.MAX_VALUE for extremely large collections was probably taken on the assumption that such collectionswith more than two billion elementswill rarely arise. Even so, an alternative design which raises an exception instead of returning an arbitrary value would have the merit of ensuring that the contract for size could clearly state that if it does succeed in returning a value, that value will be correct.

      Making a Collection's Contents Available for Further Processing

      Iterator<E> iterator() // return an Iterator over the elements
      Object[] toArray() // copy contents to an Object[]
      <T> T[] toArray(T[] t) // copy contents to a T[] (for any T)

      The last two methods in this group convert collections into arrays. The first method will create a new array of Object, and the second takes an array of T and returns an array of the same type containing the elements of the collection.

      These methods are important because, although arrays should now be regarded as a legacy data typeSection 6.9), many APIs, especially older ones that predate the Java Collections Framework, have methods that accept or return arrays.

      As discussed in Section 6.4, the argument of the second method is required in order to provide at run time the reifiable type of the array, though it can have another purpose as well: if there is room, the elements of the collection are placed in itotherwise, a new array of that type is created. The first case can be useful if you want to allow the toArray method to reuse an array that you supply; this can be more efficient, particularly if the method is being called repeatedly. The second case is more convenienta common and straightforward idiom is to supply an array of zero length:

      Collection<String> cs = ...
      String[] sa = cs.toArray(new String[0]);

      A more efficient alternative, if a class uses this idiom more than once, is to declare a single empty array of the required type, that can then be used as many times as required:

      private static final String[] EMPTY_STRING_ARRAY = new String[0];
      Collection<String> cs = ...
      String[] sa = cs.toArray(EMPTY_STRING_ARRAY);

      Why is any type allowed for T in the declaration of toArray? One reason is to give the flexibility to allocate a more specific array type if the collection happens to contain elements of that type:

      List<Object> l = Array.asList("zero","one");
      String[] a = l.toArray(new String[0]);

      Here, a list of objects happens to contain only strings, so it can be converted into a string array, in an operation analogous to the promote method described in Section 6.2.

      If the list contains an object that is not a string, the error is caught at run time rather than compile time:

      List<Object> l = Array.asList("zero","one",2);
      String[] a = l.toArray(new String[0]); // run-time error

      Here, the call raises ArrayStoreException, the exception that occurs if you try to assign to an array with an incompatible reified type.

      In general, one may want to copy a collection of a given type into an array of a more specific type (for instance, copying a list of objects into an array of strings, as we showed earlier), or of a more general type (for instance, copying a list of strings into an array of objects). One would never want to copy a collection of a given type into an array of a completely unrelated type (for instance, copying a list of integers into an array of strings is always wrong). However, there is no way to specify this constraint in Java, so such errors are caught at run time rather than compile time.

      One drawback of this design is that it does not work with arrays of primitive type:

      List<Integer> l = Array.asList(0,1,2);
      int[] a = l.toArray(new int[0]); // compile-time error

      This is illegal because the type parameter T in the method call must, as always, be a reference type. The call would work if we replaced both occurrences of int with Integer, but often this will not do because, for performance or compatibility reasons, we require an array of primitive type. In such cases, there is nothing for it but to copy the array explicitly:

      List<Integer> l = Array.asList(0,1,2);
      int[] a = new int[l.size()];
      for (int i=0; i<l.size(); i++) a = l.get(i);

      The Collections Framework does not include convenience methods to convert collections to arrays of primitive type. Fortunately, this requires only a few lines of code.

      12.1. Using the Methods of Collection
      To illustrate the use of the collection classes, let's construct a tiny example. Your authors are forever trying to get organized; let's imagine that our latest effort involves writing our own to-do manager. We begin by defining a class to represent tasks, and subclasses to represent different kinds of tasks, such as writing some code or making a phone call.

      Here is the definition of tasks that we shall use:

      public abstract class Task implements Comparable<Task> {
      protected Task() {}
      public boolean equals(Object o) {
      if (o instanceof Task) {
      return toString().equals(o.toString());
      } else return false;
      }
      public int compareTo(Task t) {
      return toString().compareTo(t.toString());
      }
      public int hashCode() {
      return toString().hashCode();
      }
      public abstract String toString();
      }

      We only require four operations on tasks: equals, compareTo, hashCode and toString. Equality will be used to test whether a collection contains a given task, comparison will be used to by ordered collections (such as OrderedSet and OrderedMap) and the hash code will be used by collections based on hash tables (such as HashSet and HashMap), and the string representation of a task will be used whenever we show the contents of a collection. The first three methods are defined in terms of the toString method, which is declared abstract, so it must be defined in each subclass of Task. We consider two tasks equal if they are represented by the same string, and the natural ordering on tasks is the same as the ordering on their strings. This guarantees that the natural ordering on tasks is consistent with equality, as discussed in Section 3.1that is, compareTo returns 0 exactly when equals returns TRue.

      We define subclasses for two kinds of tasks, writing some code and making a phone call:

      public final class CodingTask extends Task {
      private final String spec;
      public CodingTask(String spec) {
      this.spec = spec;
      }
      public String getSpec() { return spec; }
      public String toString() { return "code " + spec; }
      }


      public final class PhoneTask extends Task {
      private final String name;
      private final String number;
      public PhoneTask(String name, String number) {
      this.name = name;
      this.number = number;
      }
      public String getName() { return name; }
      public String getNumber() { return number; }
      public String toString() { return "phone " + name; }
      }

      A coding task is specified by a string, and a phone task is specified by the name and number of the person to be called. In each case we provide a constructor for the class, methods to access its fields, and a way to convert it to a string. In accordance with good practice, we have made both kinds of task immutable by declaring the fields to be final, and we have declared both subclasses to be final so that no one can later define mutable subclasses (see "Item 13: Favor immutability", in Effective Java by Joshua Bloch, Addison-Wesley).

      The toString method prefaces every coding task with the string "code" and every phone task with the string "phone". Since the first precedes the second in alphabetic order, and since tasks are ordered according to the results returned by toString, it follows that coding tasks come before phone tasks in the natural ordering on tasks. This suits our needswe are geeks, after all!

      For compactness, the toString method on phone tasks only returns the name of the person to call and not the phone number. We assume we never create two phone tasks with the same name and different numbers; if we did, it would be wrong to test equality using the result returned by toString.

      We also define an empty task:

      public class EmptyTask extends Task {
      public EmptyTask() {}
      public String toString() { return ""; }
      }

      Since the empty string precedes all others in the natural ordering on strings, the empty task comes before all others in the natural ordering on tasks. This task will be useful when we construct range views of sorted sets (see Section 13.2).

      Example 12.1 shows how we can define a series of tasks to be carried out (even if, in a real system, they would be more likely to be retrieved from a database). We've chosen ArrayList as the implementation of Collection to use in this example, but we're not going to take advantage of any of the special properties of lists; we're treating ArrayList as an implementation of Collection and nothing more. As part of the retrieval process, we have organized the tasks into various categories represented by lists, using the methodCollections.addAll introduced in Section 1.4.

      Example 12-1. Example tasks and task collections for the task manager
      PhoneTask mikePhone = new PhoneTask("Mike", "987 6543");
      PhoneTask paulPhone = new PhoneTask("Paul", "123 4567");
      CodingTask databaseCode = new CodingTask("db");
      CodingTask interfaceCode = new CodingTask("gui");
      CodingTask logicCode = new CodingTask("logic");

      Collection<PhoneTask> phoneTasks = new ArrayList<PhoneTask>();
      Collection<CodingTask> codingTasks = new ArrayList<CodingTask>();
      Collection<Task> mondayTasks = new ArrayList<Task>();
      Collection<Task> tuesdayTasks = new ArrayList<Task>();

      Collections.addAll(phoneTasks, mikePhone, paulPhone);
      Collections.addAll(codingTasks, databaseCode, interfaceCode, logicCode);
      Collections.addAll(mondayTasks, logicCode, mikePhone);
      Collections.addAll(tuesdayTasks, databaseCode, interfaceCode, paulPhone);

      assert phoneTasks.toString().equals("[phone Mike, phone Paul]");
      assert codingTasks.toString().equals("[code db, code gui, code logic]");
      assert mondayTasks.toString().equals("[code logic, phone Mike]");
      assert tuesdayTasks.toString().equals("[code db, code gui, phone Paul]");

      Now we can use the methods of Collection to work with these categories. The examples we present here use the methods in the order in which they were presented earlier.

      Adding Elements We can add new tasks to the schedule:

      mondayTasks.add(new PhoneTask("Ruth", "567 1234"));
      assert mondayTasks.toString().equals(
      "[code logic, phone Mike, phone Ruth]");

      or we can combine schedules together:

      Collection<Task> allTasks = new ArrayList<Task>(mondayTasks);
      allTasks.addAll(tuesdayTasks);
      assert allTasks.toString().equals(
      "[code logic, phone Mike, phone Ruth, code db, code gui, phone Paul]");

      Removing Elements When a task is completed, we can remove it from a schedule:

      boolean wasPresent = mondayTasks.remove(mikePhone);
      assert wasPresent;
      assert mondayTasks.toString().equals("[code logic, phone Ruth]");

      and we can clear a schedule out altogether because all of its tasks have been done (yeah, right):

      mondayTasks.clear();
      assert mondayTasks.toString().equals("[]");

      The removal methods also allow us to combine entire collections in various ways. For example, to see which tasks other than phone calls are scheduled for Tuesday, we can write:

      Collection<Task> tuesdayNonphoneTasks = new ArrayList<Task>(tuesdayTasks);
      tuesdayNonphoneTasks.removeAll(phoneTasks);
      assert tuesdayNonphoneTasks.toString().equals("[code db, code gui]");

      or to see which phone calls are scheduled for that day:

      Collection<Task> phoneTuesdayTasks = new ArrayList<Task>(tuesdayTasks);
      phoneTuesdayTasks.retainAll(phoneTasks);
      assert phoneTuesdayTasks.toString().equals("[phone Paul]");

      This last example can be approached differently to achieve the same result:

      Collection<PhoneTask> tuesdayPhoneTasks =
      new ArrayList<PhoneTask>(phoneTasks);
      tuesdayPhoneTasks.retainAll(tuesdayTasks);
      assert tuesdayPhoneTasks.toString().equals("[phone Paul]");

      Note that phoneTuesdayTasks has the type List<Task>, while tuesdayPhoneTasks has the more precise type List<PhoneTask>.

      This example provides an explanation of the signatures of methods in this group and the next. We have already discussed (Section 2.6) why they take arguments of type Object or Collection<?> when the methods for adding to the collection restrict their arguments to its parametric type. Taking the example of retainAll, its contract requires the removal of those elements of this collection which do not occur in the argument collection. That gives no justification for restricting what the argument collection may contain; in the preceding example it can contain instances of any kind of Task, not just PhoneTask. And it is too narrow even to restrict the argument to collections of supertypes of the parametric type; we want the least restrictive type possible, which is Collection<?>. Similar reasoning applies to remove, removeAll, contains, and containsAll.

      Querying the Contents of a Collection These methods allow us to check, for example, that the operations above have worked correctly. We are going to use assert here to make the system check our belief that we have programmed the previous operations correctly. For example the first statement will throw an AssertionError if tuesdayPhoneTasks does not contain paulPhone:

      assert tuesdayPhoneTasks.contains(paulPhone);
      assert tuesdayTasks.containsAll(tuesdayPhoneTasks);
      assert mondayTasks.isEmpty();
      assert mondayTasks.size() == 0;

      Making the Collection Contents Available for Further Processing The methods in this group provide an iterator over the collection or convert it to an array.

      Section 11.1 showed how the simplestand most commonexplicit use of iterators has been replaced in Java 5 by the foreach statement, which uses them implicitly. But there are uses of iteration with which foreach can't help; you must use an explicit iterator if you want to change the structure of a collection without encountering ConcurrentModificationException, or if you want to process two lists in parallel. For example, suppose that we decide that we don't have time for phone tasks on Tuesday. It may perhaps be tempting to use foreach to filter them from our task list, but that won't work for the reasons described in Section 11.1:

      // throws ConcurrentModificationException
      for (Task t : tuesdayTasks) {
      if (t instanceof PhoneTask) {
      tuesdayTasks.remove(t);
      }
      }

      Using an iterator explicitly is no improvement if you still use the Collection methods that modify the structure:

      // throws ConcurrentModificationException
      for (Iterator<Task> it = tuesdayTasks.iterator() ; it.hasNext() ; ) {
      Task t = it.next();
      if (t instanceof PhoneTask) {
      tuesdayTasks.remove(t);
      }
      }

      But using the iterator's structure-changing methods gives the result we want:

      for (Iterator<Task> it = tuesdayTasks.iterator() ; it.hasNext() ; ) {
      Task t = it.next();
      if (t instanceof PhoneTask) {
      it.remove();
      }
      }

      For another example, suppose we are fastidious people that like to keep all our lists of tasks in ascending order, and we want to merge two lists of tasks into a single list, while maintaining the order. Example 12.2 shows how we can merge two collections into a third, provided that the iterators of each return their elements ascending in natural order. This method relies on the fact that the collections to be merged contain no null elements; if one is encountered, the method throws a NullPointerException.Example 12.1 are both in ascending order, and we can merge them as follows:

      Example 12-2. Merging collections using natural ordering
      public class MergeCollections {
      static <T extends Comparable<? super T>>
      List<T> merge(Collection<? extends T> c1, Collection<? extends T> c2)
      {
      List<T> mergedList = new ArrayList<T>();
      Iterator<? extends T> itr1 = c1.iterator();
      Iterator<? extends T> itr2 = c2.iterator();
      T c1Element = getNextElement(itr1);
      T c2Element = getNextElement(itr2);
      // each iteration will take a task from one of the iterators;
      // continue until neither iterator has any further tasks
      while (c1Element != null || c2Element != null) {
      // use the current c1 element if either the current c2
      // element is null, or both are non-null and the c1 element
      // precedes the c2 element in the natural order
      boolean useC1Element = c2Element == null ||
      c1Element != null && c1Element.compareTo(c2Element) < 0;
      if (useC1Element) {
      mergedList.add(c1Element);
      c1Element = getNextElement(itr1);
      } else {
      mergedList.add(c2Element);
      c2Element = getNextElement(itr2);
      }
      }
      return mergedList;
      }
      static <E> E getNextElement(Iterator<E> itr) {
      if (itr.hasNext()){
      E nextElement = itr.next();
      if (nextElement == null) throw new NullPointerException();
      return nextElement;
      } else {
      return null;
      }
      }
      }

      Collection<Task> mergedTasks =
      MergeCollections.merge(mondayTasks, tuesdayTasks);
      assert mergedTasks.toString().equals(
      "[code db, code gui, code logic, phone Mike, phone Paul]");
      Implementing Collection
      There are no concrete implementations of Collection. The class AbstractCollection, which partially implements it, is one of a series of skeletal implementationsincluding AbstractSet, AbstractList, and so onwhich provide functionality common to the different concrete implementations of each interface. These skeletal implementations are available to help the designer of new implementations of the Framework interfaces. For example, Collection could serve as the interface for bags (unordered lists), and a programmer implementing bags could extend AbstractCollection and find most of the implementation work already done.


      Manivelle
       

      Attached Files:

      Loading...

Share This Page

Share