Exercises

Exercices

1. Create an array of double and fill( ) it using RandDoubleGenerator. Print the results.
2. Create a new class called Gerbil with an int gerbilNumber that’s initialized in the constructor (similar to the Mouse example in this chapter). Give it a method called hop( ) that prints out which gerbil number this is, and that it’s hopping. Create an ArrayList and add a bunch of Gerbil objects to the List. Now use the get( ) method to move through the List and call hop( ) for each Gerbil.
3. Modify Exercise 2 so you use an Iterator to move through the List while calling hop( ).
4. Take the Gerbil class in Exercise 2 and put it into a Map instead, associating the name of the Gerbil as a String (the key) for each Gerbil (the value) you put in the table. Get an Iterator for the keySet( ) and use it to move through the Map, looking up the Gerbil for each key and printing out the key and telling the gerbil to hop( ).
5. Create a List (try both ArrayList and LinkedList) and fill it using Collections2.countries. Sort the list and print it, then apply Collections.shuffle( ) to the list repeatedly, printing it each time so that you can see how the shuffle( ) method randomizes the list differently each time.
6. Demonstrate that you can’t add anything but a Mouse to a MouseList.
7. Modify MouseList.java so that it inherits from ArrayList instead of using composition. Demonstrate the problem with this approach.
8. Repair CatsAndDogs.java by creating a Cats container (utilizing ArrayList) that will only accept and retrieve Cat objects.
9. Create a container that encapsulates an array of String, and that only adds Strings and gets Strings, so that there are no casting issues during use. If the internal array isn’t big enough for the next add, your container should automatically resize it. In main( ), compare the performance of your container with an ArrayList holding Strings.
10. Repeat Exercise 9 for a container of int, and compare the performance to an ArrayList holding Integer objects. In your performance comparison, include the process of incrementing each object in the container.
11. Using the utilities in com.bruceeckel.util, create an array of each primitive type and of String, then fill each array using an appropriate generator, and print each array using the appropriate print( ) method.
12. Create a generator that produces character names from your favorite movies (you can use Snow White or Star Wars as a fallback), and loops around to the beginning when it runs out of names. Use the utilities in com.bruceeckel.util to fill an array, an ArrayList, a LinkedList and both types of Set, then print each container.
13. Create a class containing two String objects, and make it Comparable so that the comparison only cares about the first String. Fill an array and an ArrayList with objects of your class, using the geography generator. Demonstrate that sorting works properly. Now make a Comparator that only cares about the second String and demonstrate that sorting works properly; also perform a binary search using your Comparator.
14. Modify Exercise 13 so that an alphabetic sort is used.
15. Use Arrays2.RandStringGenerator to fill a TreeSet but using alphabetic ordering. Print the TreeSet to verify the sort order.
16. Create both an ArrayList and a LinkedList, and fill each using the Collections2.capitals generator. Print each list using an ordinary Iterator, then insert one list into the other using a ListIterator, inserting at every other location. Now perform the insertion starting at the end of the first list and moving backward.
17. Write a method that uses an Iterator to step through a Collection and print the hashCode( ) of each object in the container. Fill all the different types of Collections with objects and apply your method to each container.
18. Repair the problem in InfiniteRecursion.java.
19. Create a class, then make an initialized array of objects of your class. Fill a List from your array. Create a subset of your List using subList( ), and then remove this subset from your List using removeAll( ).
20. Change Exercise 6 in Chapter 7 to use an ArrayList to hold the Rodents and an Iterator to move through the sequence of Rodents. Remember that an ArrayList holds only Objects so you must use a cast when accessing individual Rodents.
21. Following the Queue.java example, create a Deque class and test it.
22. Use a TreeMap in Statistics.java. Now add code that tests the performance difference between HashMap and TreeMap in that program.
23. Produce a Map and a Set containing all the countries that begin with ‘A.’
24. Using Collections2.countries, fill a Set multiple times with the same data and verify that the Set ends up with only one of each instance. Try this with both kinds of Set.
25. Starting with Statistics.java, create a program that runs the test repeatedly and looks to see if any one number tends to appear more than the others in the results.
26. Rewrite Statistics.java using a HashSet of Counter objects (you’ll have to modify Counter so that it will work in the HashSet). Which approach seems better?
27. Modify the class in Exercise 13 so that it will work with HashSets and as a key in HashMaps.
28. Using SlowMap.java for inspiration, create a SlowSet.
29. Apply the tests in Map1.java to SlowMap to verify that it works. Fix anything in SlowMap that doesn’t work correctly.
30. Implement the rest of the Map interface for SlowMap.
31. Modify MapPerformance.java to include tests of SlowMap.
32. Modify SlowMap so that instead of two ArrayLists, it holds a single ArrayList of MPair objects. Verify that the modified version works correctly. Using MapPerformance.java, test the speed of your new Map. Now change the put( ) method so that it performs a sort( ) after each pair is entered, and modify get( ) to use Collections.binarySearch( ) to look up the key. Compare the performance of the new version with the old ones.
33. Add a char field to CountedString that is also initialized in the constructor, and modify the hashCode( ) and equals( ) methods to include the value of this char.
34. Modify SimpleHashMap so that it reports collisions, and test this by adding the same data set twice so that you see collisions.
35. Modify SimpleHashMap so that it reports the number of “probes” necessary when collisions occur. That is, how many calls to next( ) must be made on the Iterators that walk the LinkedLists looking for matches?
36. Implement the clear( ) and remove( ) methods for SimpleHashMap.
37. Implement the rest of the Map interface for SimpleHashMap.
38. Add a private rehash( ) method to SimpleHashMap that is invoked when the load factor exceeds 0.75. During rehashing, double the number of buckets, then search for the first prime number greater than that to determine the new number of buckets.
39. Following the example in SimpleHashMap.java, create and test a SimpleHashSet.
40. Modify SimpleHashMap to use ArrayLists instead of LinkedLists. Modify MapPerformance.java to compare the performance of the two implementations.
41. Using the HTML documentation for the JDK (downloadable from java.sun.com), look up the HashMap class. Create a HashMap, fill it with elements, and determine the load factor. Test the lookup speed with this map, then attempt to increase the speed by making a new HashMap with a larger initial capacity and copying the old map into the new one, running your lookup speed test again on the new map.
42. In Chapter 8, locate the GreenhouseControls.java example, which consists of three files. In Controller.java, the class EventSet is just a container. Change the code to use a LinkedList instead of an EventSet. This will require more than just replacing EventSet with LinkedList; you’ll also need to use an Iterator to cycle through the set of events.
43. (Challenging). Write your own hashed map class, customized for a particular key type: String for this example. Do not inherit it from Map. Instead, duplicate the methods so that the put( ) and get( ) methods specifically take String objects, not Objects, as keys. Everything that involves keys should not use generic types, but instead work with Strings, to avoid the cost of upcasting and downcasting. Your goal is to make the fastest possible custom implementation. Modify MapPerformance.java to test your implementation vs. a HashMap.
44. (Challenging). Find the source code for List in the Java source code library that comes with all Java distributions. Copy this code and make a special version called intList that holds only ints. Consider what it would take to make a special version of List for all the primitive types. Now consider what happens if you want to make a linked list class that works with all the primitive types. If parameterized types are ever implemented in Java, they will provide a way to do this work for you automatically (as well as many other benefits).

1. Créez un tableau de doubles et remplissez-le avec fill() en utilisant RandDoubleGenerator. Affichez les résultats.
2. Créez une nouvelle classe Gerbil possédant un int gerbilNumber initialisé dans le constructeur (similaire à l'exemple Mouse de ce chapitre). Donnez-lui une méthode hop() qui affiche son numéro de gerboise et un message indiquant qu'elle est en train de sauter. Créez une ArrayList et ajoutez-y un ensemble d'objets Gerbil. Maintenant utilisez la méthode get() pour parcourir la List et appelez hop() pour chaque Gerbil.
3. Modifiez l'exercice 2 afin d'utiliser un Iterator lors du parcours de la List pour appeler hop().
4. Prenez la classe Gerbil de l'exercice 2 et placez-la dans une Map à la place, en associant le nom (une String) de la Gerbil à chaque Gerbil (la valeur) stockée dans la table. Récupérer un Iterator sur l'ensemble des clefs (obtenu via keySet()) et utilisez-le pour parcourir la Map, récupérez la Gerbil pour chaque clef, imprimez son nom et dites-lui de sauter avec la méthode hop().
5. Créez une List (essayez avec une ArrayList et une LinkedList) et remplissez-la en utilisant Collections2.countries. Triez cette liste et affichez-la, puis appliquez-lui Collections.shuffle() plusieurs fois, en l'imprimant à chaque fois pour voir les effets de cette méthode.
6. Montrez que vous ne pouvez ajouter que des objets Mouse dans une MouseList.
7. Modifiez MouseList.java de manière à ce qu'elle hérite de ArrayList au lieu d'utiliser la composition. Illustrez le problème de cette approche.
8. Réparez CatsAndDogs.java en créant un conteneur Cats (en utilisant ArrayList) qui n'accepte que des objets Cats.
9. Créez un conteneur qui encapsule un tableau de Strings, qui ne stocke et ne renvoie que des Strings, afin de ne pas avoir de transtypage à faire lorsqu'on l'utilise. Si le tableau interne n'est pas assez grand pour l'insertion suivante, le conteneur devra se redimensionner automatiquement. Dans main(), comparez les performances de votre conteneur avec une ArrayList contenant des Strings.
10. Répétez l'exercice 9 pour un conteneur d'ints, et comparez les performances avec une ArrayList contenant des objets Integer. Dans le test de performances, incluez en plus le fait d'incrémenter chaque objet du conteneur.
11. Créez un tableau pour chaque type primitif et un tableau de Strings, remplissez chaque tableau en utilisant un générateur fourni parmi les utilitaires de com.bruceeckel.util, et afficher chaque tableau en utilisant la méthode print() appropriée.
12. Créez un générateur qui produise des noms de personnages de vos films préférés (que pensez-vous de Snow White ou Star Wars), et revienne au début quand il n'a plus de noms à proposer. Utilisez les utilitaires de com.bruceeckel.util pour remplir un tableau, une ArrayList, une LinkedList et les deux types de Set disponibles, puis imprimez chaque conteneur.
13. Créez une classe contenant deux objets String, et rendez-la Comparable afin que la comparaison ne porte que sur la première String. Remplissez un tableau et une ArrayList avec des objets de cette classe, en utilisant le générateur geography. Montrez que le tri fonctionne correctement. Créez maintenant un Comparator qui porte sur la deuxième String, et montrez que le tri fonctionne aussi ; effectuez une recherche en utilisant votre Comparator.
14. Modifiez l'exercice 13 afin d'utiliser un tri alphabétique.
15. Utilisez Arrays2.RandStringGenerator pour remplir un TreeSet utilisant un tri alphabétique. Imprimez le TreeSet pour vérifier l'ordre.
16. Créez une ArrayList et une LinkedList, et remplissez-les en utilisant le générateur Collections2.capitals. Imprimez chaque liste en utilisant un Iterator ordinaire, puis insérer une liste dans l'autre en utilisant un ListIterator, en insérant un élément de la deuxième liste entre chaque élément de la première liste. Réalisez maintenant cette insertion en partant de la fin de la première liste et en la parcourant à l'envers.
17. Ecrivez une méthode qui utilise un Iterator pour parcourir une Collection et imprime le code de hachage de chaque objet du conteneur. Remplissez tous les types de Collections existants avec des objets et utilisez votre méthode avec chaque conteneur.
18. Réparez le problème d'InfiniteRecursion.java.
19. Créez une classe, puis créez un tableau d'objets de votre classe. Remplissez une List à partir du tableau. Créez un sous-ensemble de la List en utilisant subList(), puis supprimez cet ensemble de la List avec removeAll().
20. Modifiez l'exercice 6 du Chapitre 7 afin de stocker les Rodents dans une ArrayList et utilisez un Iterator pour parcourir la séquence des Rodents. Rappelez-vous qu'une ArrayList ne stocke que des Objects et qu'on doit donc les transtyper pour retrouver le comportement d'un Rodent.
21. En vous basant sur Queue.java, créez une classe DoubleFile et testez-la.
22. Utilisez un TreeMap dans Statistics.java. Ajoutez maintenant du code afin de tester les différences de performances entre HashMap et TreeMap dans ce programme.
23. Créez une Map et un Set contenant tous les pays dont le nom commence par un 'A'.
24. Remplissez un Set à l'aide de Collections2.countries, utilisez plusieurs fois les mêmes données et vérifiez que le Set ne stocke qu'une seule instance de chaque donnée. Testez ceci avec les deux types de Set.
25. A partir de Statistics.java, créez un programme qui lance le test plusieurs fois et vérifie si un nombre a tendance à apparaître plus souvent que les autres dans les résultats.
26. Réécrivez Statistics.java en utilisant un HashSet d'objets Counter (vous devrez modifiez la classe Counter afin qu'elle fonctionne avec un HashSet). Quelle approche semble la meilleure ?
27. Modifiez la classe de l'exercice 13 afin qu'elle puisse être stockée dans un HashSet et comme clef dans un HashMap.
28. Créez un SlowSet en vous inspirant de SlowMap.java.
29. Appliquez les tests de Map1.java à SlowMap pour vérifier que cette classe fonctionne. Corrigez dans SlowMap tout ce qui ne marche pas correctement.
30. Implémentez le reste de l'interface Map pour SlowMap.
31. Modifiez MapPerformance.java afin d'inclure les tests pour SlowMap.
32. Modifiez SlowMap afin qu'elle utilise une seule ArrayList d'objets MPair au lieu de deux ArrayLists. Vérifiez que la version modifiée fonctionne correctement. Utilisez MapPerformance.java pour tester cette nouvelle Map. Modifiez maintenant la méthode put() afin qu'elle effectue un sort() après chaque insertion, et modifiez get() afin d'utiliser Collections.binarySearch() pour récupérer la clef. Comparez les performances de la nouvelle version avec les anciennes.
33. Ajoutez un champ char à CountedString qui soit aussi initialisé dans le constructeur, et modifiez les méthodes hashCode() et equals() afin d'inclure la valeur de ce char.
34. Modifiez SimpleHashMap afin de signaler les collisions, et testez ce comportement en ajoutant les mêmes données plusieurs fois afin de voir les collisions.
35. Modifiez SimpleHashMap afin de signaler le nombre d'objets testés lorsqu'une collision survient. Autrement dit, combien d'appels à next() doivent être effectués sur l'Iterator parcourant la LinkedList pour trouver l'occurence recherchée ?
36. Implémentez les  méthodes clear() et remove() pour SimpleHashMap.
37. Implémentez le reste de l'interface Map pour SimpleHashMap.
38. Ajoutez une méthode private rehash() à SimpleHashMap qui soit invoquée lorsque le facteur de charge dépasse 0,75. Au cours du rehachage, doublez le nombre de seaux et recherchez le premier nombre premier qui soit supérieur à cette valeur pour déterminer le nouveau nombre de seaux.
39. Créez et testez un SimpleHashSet en vous inspirant de SimpleHashMap.java.
40. Modifiez SimpleHashMap afin d'utiliser des ArrayLists au lieu de LinkedLists. Modifiez MapPerformance.java afin de comparer les performances des deux implémentations.
41. Consultez la documentation HTML du JDK (téléchargeable sur java.sun.com) de la classe HashMap. Créez un HashMap, remplissez-le avec des éléments et déterminez son facteur de charge. Testez la vitesse d'accès aux éléments de ce dictionnaire ; essayez d'augmenter cette vitesse en créant un nouveau HashMap d'une capacité initiale supérieure et en copiant l'ancien dictionnaire dans le nouveau.
42. Dans le Chapitre 8, localisez l'exemple GreenHouse.java comportant 3 fichiers. Dans Controller.java, la classe EventSet n'est qu'un conteneur. Changez le code afin d'utiliser une LinkedList au lieu d'un EventSet. Remplacer EventSet par LinkedList ne suffira pas, il vous faudra aussi utiliser un Iterator pour parcourir l'ensemble d'événements.
43. (Difficile). Créez votre propre classe de dictionnaire haché, particularisée pour un type particulier de clefs : String par exemple. Ne la faites pas dériver de Map. A la place, dupliquez les méthodes afin que les méthodes put() et get() n'acceptent que des objets String comme clef, et non des Objects. Tout ce qui touche les clefs ne doit pas impliquer de types génériques, mais uniquement des Strings afin d'éviter les surcoûts liés au transtypage. Votre but est de réaliser l'implémentation la plus rapide possible. Modifiez MapPerformance.java afin de tester votre implémentation contre un HashMap.
44. (Difficile). Trouvez le code source de List dans la bibliothèque de code source Java fournie dans toutes les distributions Java. Copiez ce code et créez une version spéciale appelée intList qui ne stocke que des ints. Réfléchissez à ce qu'il faudrait pour créer une version spéciale de List pour chacun des types scalaires. Réfléchissez maintenant à ce qu'il faudrait si on veut créer une classe de liste chaînée qui fonctionne avec tous les types scalaires. Si les types paramétrés sont implémentés un jour dans Java, ils fourniront un moyen de réaliser ce travail automatiquement (entre autres).