archive-edu.com » EDU » H » HWS.EDU

Total: 727

Choose link from "Titles, links and description words view":

Or switch to "Titles and links view".
  • Javanotes 7.0, Section 8.5 -- Analysis of Algorithms
    the running time The exact running time would then be a b n c where the constants a b and c depend on factors such as how the code is compiled and what computer it is run on Using the fact that c is less than or equal to c n for any positive integer n we can say that the run time is less than or equal to a b c n That is the run time is less than or equal to a constant times n By definition this means that the run time for this algorithm is O n If this explanation is too mathematical for you we can just note that for large values of n the c in the formula a b n c is insignificant compared to the other term a b n We say that c is a lower order term When doing asymptotic analysis lower order terms can be discarded A rough but correct asymptotic analysis of the algorithm would go something like this Each iteration of the for loop takes a certain constant amount of time There are n iterations of the loop so the total run time is a constant times n plus lower order terms to account for the initialization Disregarding lower order terms we see that the run time is O n Note that to say that an algorithm has run time O f n is to say that its run time is no bigger than some constant times f n for large values of n O f n puts an upper limit on the run time However the run time could be smaller even much smaller For example if the run time is O n it would also be correct to say that the run time is O n 2 or even O n 10 If the run time is less than a constant times n then it is certainly less than the same constant times n 2 or n 10 Of course sometimes it s useful to have a lower limit on the run time That is we want to be able to say that the run time is greater than or equal to some constant times f n for large values of n The notation for this is Ω f n read Omega of f of n Omega is the name of a letter in the Greek alphabet and Ω is the upper case version of that letter To be technical saying that the run time of an algorithm is Ω f n means that there is a positive number C and a positive integer M such that whenever n is greater than M the run time is greater than or equal to C f n O f n tells you something about the maximum amount of time that you might have to wait for an algorithm to finish Ω f n tells you something about the minimum time The algorithm for adding up the numbers in an array has a run time that is Ω n as well as O n When an algorithm has a run time that is both Ω f n and O f n its run time is said to be Θ f n read Theta of f of n Theta is another letter from the Greek alphabet To say that the run time of an algorithm is Θ f n means that for large values of n the run time is between a f n and b f n where a and b are constants with b greater than a and both greater than 0 Let s look at another example Consider the algorithm that can be expressed in Java in the following method Sorts the n array elements A 0 A 1 A n 1 into increasing order public static simpleBubbleSort int A int n for int i 0 i n i Do n passes through the array for int j 0 j n 1 j if A j A j 1 A j and A j 1 are out of order so swap them int temp A j A j A j 1 A j 1 temp Here the parameter n represents the problem size The outer for loop in the method is executed n times Each time the outer for loop is executed the inner for loop is executed n 1 times so the if statement is executed n n 1 times This is n 2 n but since lower order terms are not significant in an asymptotic analysis it s good enough to say that the if statement is executed about n 2 times In particular the test A j A j 1 is executed about n 2 times and this fact by itself is enough to say that the run time of the algorithm is Ω n 2 that is the run time is at least some constant times n 2 Furthermore if we look at other operations the assignment statements incrementing i and j etc none of them are executed more than n 2 times so the run time is also O n 2 that is the run time is no more than some constant times n 2 Since it is both Ω n 2 and O n 2 the run time of the simpleBubbleSort algorithm is Θ n 2 You should be aware that some people use the notation O f n as if it meant Θ f n That is when they say that the run time of an algorithm is O f n they mean to say that the run time is about equal to a constant times f n For that they should use Θ f n Properly speaking O f n means that the run time is less than a constant times f n possibly much less So far my analysis has ignored an important detail We have looked at how run time depends on the problem size

    Original URL path: http://math.hws.edu/javanotes/c8/s5.html (2016-02-07)
    Open archived version from archive


  • Javanotes 7.0, Exercises for Chapter 8
    1 sequence Count the number of terms in the sequence and print the count at the end of the sequence Exit the program when the user inputs an empty line See the Solution Exercise 8 3 A Roman numeral represents an integer using letters Examples are XVII to represent 17 MCMLIII for 1953 and MMMCCCIII for 3303 By contrast ordinary numbers such as 17 or 1953 are called Arabic numerals The following table shows the Arabic equivalent of all the single letter Roman numerals M 1000 X 10 D 500 V 5 C 100 I 1 L 50 When letters are strung together the values of the letters are just added up with the following exception When a letter of smaller value is followed by a letter of larger value the smaller value is subtracted from the larger value For example IV represents 5 1 or 4 And MCMXCV is interpreted as M CM XC V or 1000 1000 100 100 10 5 which is 1995 In standard Roman numerals no more than three consecutive copies of the same letter are used Following these rules every number between 1 and 3999 can be represented as a Roman numeral made up of the following one and two letter combinations M 1000 X 10 CM 900 IX 9 D 500 V 5 CD 400 IV 4 C 100 I 1 XC 90 L 50 XL 40 Write a class to represent Roman numerals The class should have two constructors One constructs a Roman numeral from a string such as XVII or MCMXCV It should throw a NumberFormatException if the string is not a legal Roman numeral The other constructor constructs a Roman numeral from an int It should throw a NumberFormatException if the int is outside the range 1 to 3999 In addition the class should have two instance methods The method toString returns the string that represents the Roman numeral The method toInt returns the value of the Roman numeral as an int At some point in your class you will have to convert an int into the string that represents the corresponding Roman numeral One way to approach this is to gradually move value from the Arabic numeral to the Roman numeral Here is the beginning of a routine that will do this where number is the int that is to be converted String roman int N number while N 1000 Move 1000 from N to roman roman M N 1000 while N 900 Move 900 from N to roman roman CM N 900 Continue with other values from the above table You can save yourself a lot of typing in this routine if you use arrays in a clever way to represent the data in the above table Once you ve written your class use it in a main program that will read both Arabic numerals and Roman numerals entered by the user If the user enters an Arabic numeral print the corresponding Roman numeral If the user enters

    Original URL path: http://math.hws.edu/javanotes/c8/exercises.html (2016-02-07)
    Open archived version from archive

  • Javanotes 7.0, Quiz on Chapter 8
    Write a method that prints out a 3N 1 sequence starting from a given integer N The starting value should be a parameter to the method If the parameter is less than or equal to zero throw an IllegalArgumentException If the number in the sequence becomes too large to be represented as a value of type int throw an ArithmeticException Question 7 Rewrite the method from the previous question using assert statements instead of exceptions to check for errors What is the difference between the two versions of the method when the program is run Question 8 Some classes of exceptions are checked exceptions that require mandatory exception handling Explain what this means Question 9 Consider a subroutine processData that has the header static void processData throws IOException Write a try catch statement that calls this subroutine and prints an error message if an IOException occurs Question 10 Why should a subroutine throw an exception when it encounters an error Why not just terminate the program Question 11 Suppose that you have a choice of two algorithms that perform the same task One has average case run time that is Θ n 2 while the run time of the second

    Original URL path: http://math.hws.edu/javanotes/c8/quiz.html (2016-02-07)
    Open archived version from archive

  • Javanotes 7.0, Exercises for Chapter 9
    to test whether that is true The depth of a node in a binary tree is the length of the path from the root of the tree to that node That is the root has depth 0 its children have depth 1 its grandchildren have depth 2 and so on In a balanced tree all the leaves in the tree are about the same depth For example in a perfectly balanced tree with 1023 nodes all the leaves are at depth 9 In an approximately balanced tree with 1023 nodes the average depth of all the leaves should be not too much bigger than 9 On the other hand even if the tree is approximately balanced there might be a few leaves that have much larger depth than the average so we might also want to look at the maximum depth among all the leaves in a tree For this exercise you should create a random binary sort tree with 1023 nodes The items in the tree can be real numbers and you can create the tree by generating 1023 random real numbers and inserting them into the tree using the usual treeInsert method for binary sort trees Once you have the tree you should compute and output the average depth of all the leaves in the tree and the maximum depth of all the leaves To do this you will need three recursive subroutines one to count the leaves one to find the sum of the depths of all the leaves and one to find the maximum depth The latter two subroutines should have an int valued parameter depth that tells how deep in the tree you ve gone When you call this routine from the main program the depth parameter is 0 when you call the routine recursively the parameter increases by 1 See the Solution Exercise 9 6 The parsing programs in Section 9 5 work with expressions made up of numbers and operators We can make things a little more interesting by allowing the variable x to occur This would allow expression such as 3 x 1 x 1 for example Make a new version of the sample program SimpleParser3 java that can work with such expressions In your program the main routine can t simply print the value of the expression since the value of the expression now depends on the value of x Instead it should print the value of the expression for x 0 x 1 x 2 and x 3 The original program will have to be modified in several other ways Currently the program uses classes ConstNode BinOpNode and UnaryMinusNode to represent nodes in an expression tree Since expressions can now include x you will need a new class VariableNode to represent an occurrence of x in the expression In the original program each of the node classes has an instance method double value which returns the value of the node But in your program the value can depend on x

    Original URL path: http://math.hws.edu/javanotes/c9/exercises.html (2016-02-07)
    Open archived version from archive

  • Javanotes 7.0, Quiz on Chapter 9
    be produced by the subroutine calls printStuff 0 printStuff 1 printStuff 2 and printStuff 3 Question 3 Suppose that a linked list is formed from objects that belong to the class class ListNode int item An item in the list ListNode next Pointer to next item in the list Write a subroutine that will count the number of zeros that occur in a given linked list of ints The subroutine should have a parameter of type ListNode and should return a value of type int Question 4 What are the three operations on a stack Question 5 What is the basic difference between a stack and a queue Question 6 What is an activation record What role does a stack of activation records play in a computer Question 7 Suppose that a binary tree of integers is formed from objects belonging to the class class TreeNode int item One item in the tree TreeNode left Pointer to the left subtree TreeNode right Pointer to the right subtree Write a recursive subroutine that will find the sum of all the nodes in the tree Your subroutine should have a parameter of type TreeNode and it should return a value of type

    Original URL path: http://math.hws.edu/javanotes/c9/quiz.html (2016-02-07)
    Open archived version from archive

  • Javanotes 7.0, Section 10.1 -- Generic Programming
    of object This means that if list was an ArrayList then list get i would return a value of type Object If the programmer was actually using the list to store Strings the value returned by list get i would have to be type cast to treat it as a string String item String list get i This is still a kind of generic programming since one class can work for any kind of object but it was closer in spirit to Smalltalk than it was to C since there is no way to do type checks at compile time Unfortunately as in Smalltalk the result is a category of errors that show up only at run time rather than at compile time If a programmer assumes that all the items in a data structure are strings and tries to process those items as strings a run time error will occur if other types of data have inadvertently been added to the data structure In Java the error will most likely occur when the program retrieves an Object from the data structure and tries to type cast it to type String If the object is not actually of type String the illegal type cast will throw an error of type ClassCastException Java 5 0 introduced parameterized types which made it possible to create generic data structures that can be type checked at compile time rather than at run time For example if list is of type ArrayList String then the compiler will only allow objects of type String to be added to list Furthermore the return type of list get i is String so type casting is not necessary Java s parameterized classes are similar to template classes in C although the implementation is very different and their introduction moves Java s generic programming model closer to C and farther from Smalltalk In this chapter I will use the parameterized types exclusively but you should remember that their use is not mandatory It is still legal to use a parameterized class as a non parameterized type such as a plain ArrayList In that case any type of object can be stored in the data structure Note that there is a significant difference between parameterized classes in Java and template classes in C A template class in C is not really a class at all it s a kind of factory for generating classes Every time the template is used with a new type a new compiled class is created With a Java parameterized class there is only one compiled class file For example there is only one compiled class file ArrayList class for the parameterized class ArrayList The parameterized types ArrayList String and ArrayList Integer both use the same compiled class file as does the plain ArrayList type The type parameter String or Integer just tells the compiler to limit the type of object that can be stored in the data structure The type parameter has no effect at run time and is not even known at run time The type information is said to be erased at run time This type erasure introduces a certain amount of weirdness For example you can t test if list instanceof ArrayList String because the instanceof operator is evaluated at run time and at run time only the plain ArrayList exists Similarly you can t type cast to the type ArrayList String Even worse you can t create an array that has base type ArrayList String by using the new operator as in new ArrayList String N This is because the new operator is evaluated at run time and at run time there is no such thing as ArrayList String only the non parameterized type ArrayList exists at run time However although you can t have an array of ArrayList String you can have an ArrayList of ArrayList String with the type written as ArrayList ArrayList String which is just as good or better Fortunately most programmers don t have to deal with such problems since they turn up only in fairly advanced programming Most people who use parameterized types will not encounter the problems and they will get the benefits of type safe generic programming with little difficulty 10 1 4 The Java Collection Framework As I ve said Java comes with a number of parameterized classes that implement common data structures This collection of data structure classes is referred to as the Java Collection Framework or JFC We will spend the next few sections learning about the JFC The generic data structures in the Java Collection Framework can be divided into two categories collections and maps A collection is more or less what it sounds like a collection of objects A map associates objects in one set with objects in another set in the way that a dictionary associates definitions with words or a phone book associates phone numbers with names A map is similar to what I called an association list in Subsection 7 4 2 In Java collections and maps are represented by the parameterized interfaces Collection T and Map T S Here T and S stand for any type except for the primitive types Map T S is an example of a parameterized type that ahs two type parameters T and S we will not deal further with this possibility until we look at maps more closely in Section 10 3 In this section and the next we look at collections only There are two types of collections lists and sets A list is a collection in which the objects are arranged in a linear sequence A list has a first item a second item and so on For any item in the list except the last there is an item that directly follows it For collections that are sets the defining property is that no object can occur more than once in a set the elements of a set are not necessarily thought of as being in any particular order The ideas of lists and sets are represented as parameterized interfaces List T and Set T These are sub interfaces of Collection T That is any object that implements the interface List T or Set T automatically implements Collection T as well The interface Collection T specifies general operations that can be applied to any collection at all List T and Set T add additional operations that are appropriate for lists and sets respectively Of course any actual object that is a collection list or set must belong to a concrete class that implements the corresponding interface For example the class ArrayList T implements the interface List T and therefore also implements Collection T This means that all the methods that are defined in the list and collection interfaces can be used with an ArrayList We will look at various classes that implement the list and set interfaces in the next section But before we do that we ll look briefly at some of the general operations that are available for all collections The interface Collection T specifies methods for performing some basic operations on any collection of objects Since collection is a very general concept operations that can be applied to all collections are also very general They are generic operations in the sense that they can be applied to various types of collections containing various types of objects Suppose that coll is an object that implements the interface Collection T for some specific non primitive type T Then the following operations which are specified in the interface Collection T are defined for coll coll size returns an int that gives the number of objects in the collection coll isEmpty returns a boolean value which is true if the size of the collection is 0 coll clear removes all objects from the collection coll add tobject adds tobject to the collection The parameter must be of type T if not a syntax error occurs at compile time Remember that if T is a class this includes objects belonging to a subclass of T and if T is an interface it includes any object that implements T The add method returns a boolean value which tells you whether the operation actually modified the collection For example adding an object to a Set has no effect if that object was already in the set coll contains object returns a boolean value that is true if object is in the collection Note that object is not required to be of type T since it makes sense to check whether object is in the collection no matter what type object has For testing equality null is considered to be equal to itself The criterion for testing non null objects for equality can differ from one kind of collection to another see Subsection 10 1 6 below coll remove object removes object from the collection if it occurs in the collection and returns a boolean value that tells you whether the object was found Again object is not required to be of type T The test for equality is the same test that is used by contains coll containsAll coll2 returns a boolean value that is true if every object in coll2 is also in coll The parameter can be any collection coll addAll coll2 adds all the objects in coll2 to coll The parameter coll2 can be any collection of type Collection T However it can also be more general For example if T is a class and S is a sub class of T then coll2 can be of type Collection S This makes sense because any object of type S is automatically of type T and so can legally be added to coll coll removeAll coll2 removes every object from coll that also occurs in the collection coll2 coll2 can be any collection coll retainAll coll2 removes every object from coll that does not occur in the collection coll2 It retains only the objects that do occur in coll2 coll2 can be any collection coll toArray returns an array of type Object that contains all the items in the collection Note that the return type is Object not T However there is another version of this method that takes an array of type T as a parameter the method coll toArray tarray returns an array of type T containing all the items in the collection If the array parameter tarray is large enough to hold the entire collection then the items are stored in tarray and tarray is also the return value of the collection If tarray is not large enough then a new array is created to hold the items in that case tarray serves only to specify the type of the array For example coll toArray new String 0 can be used if coll is a collection of Strings and will return a new array of type String Since these methods are part of the Collection T interface they must be defined for every object that implements that interface There is a problem with this however For example the size of some collections cannot be changed after they are created Methods that add or remove objects don t make sense for these collections While it is still legal to call the methods an exception will be thrown when the call is evaluated at run time The type of the exception is UnsupportedOperationException Furthermore since Collection T is only an interface not a concrete class the actual implementation of the method is left to the classes that implement the interface This means that the semantics of the methods as described above are not guaranteed to be valid for all collection objects they are valid however for classes in the Java Collection Framework There is also the question of efficiency Even when an operation is defined for several types of collections it might not be equally efficient in all cases Even a method as simple as size can vary greatly in efficiency For some collections computing the size might involve counting the items in the collection The number of steps in this process is equal to the number of items Other collections might have instance variables to keep track of the size so evaluating size just means returning the value of a variable In this case the computation takes only one step no matter how many items there are When working with collections it s good to have some idea of how efficient operations are and to choose a collection for which the operations that you need can be implemented most efficiently We ll see specific examples of this in the next two sections 10 1 5 Iterators and for each Loops The interface Collection T defines a few basic generic algorithms but suppose you want to write your own generic algorithms Suppose for example you want to do something as simple as printing out every item in a collection To do this in a generic way you need some way of going through an arbitrary collection accessing each item in turn We have seen how to do this for specific data structures For an array you can use a for loop to iterate through all the array indices For a linked list you can use a while loop in which you advance a pointer along the list For a binary tree you can use a recursive subroutine to do an inorder traversal Collections can be represented in any of these forms and many others besides With such a variety of traversal mechanisms how can we even hope to come up with a single generic method that will work for collections that are stored in wildly different forms This problem is solved by iterators An iterator is an object that can be used to traverse a collection Different types of collections have iterators that are implemented in different ways but all iterators are used in the same way An algorithm that uses an iterator to traverse a collection is generic because the same technique can be applied to any type of collection Iterators can seem rather strange to someone who is encountering generic programming for the first time but you should understand that they solve a difficult problem in an elegant way The interface Collection T defines a method that can be used to obtain an iterator for any collection If coll is a collection then coll iterator returns an iterator that can be used to traverse the collection You should think of the iterator as a kind of generalized pointer that starts at the beginning of the collection and can move along the collection from one item to the next Iterators are defined by a parameterized interface named Iterator T If coll implements the interface Collection T for some specific type T then coll iterator returns an iterator of type Iterator T with the same type T as its type parameter The interface Iterator T defines just three methods If iter refers to an object that implements Iterator T then we have iter next returns the next item and advances the iterator The return value is of type T This method lets you look at one of the items in the collection Note that there is no way to look at an item without advancing the iterator past that item If this method is called when no items remain it will throw a NoSuchElementException iter hasNext returns a boolean value telling you whether there are more items to be processed In general you should test this before calling iter next iter remove if you call this after calling iter next it will remove the item that you just saw from the collection Note that this method has no parameter It removes the item that was most recently returned by iter next This might produce an UnsupportedOperationException if the collection does not support removal of items Using iterators we can write code for printing all the items in any collection Suppose for example that coll is of type Collection String In that case the value returned by coll iterator is of type Iterator String and we can say Iterator String iter Declare the iterator variable iter coll iterator Get an iterator for the collection while iter hasNext String item iter next Get the next item System out println item The same general form will work for other types of processing For example the following code will remove all null values from any collection of type Collection JButton as long as that collection supports removal of values Iterator JButton iter coll iterator while iter hasNext JButton item iter next if item null iter remove Note by the way that when Collection T Iterator T or any other parameterized type is used in actual code they are always used with actual types such as String or JButton in place of the formal type parameter T An iterator of type Iterator String is used to iterate through a collection of Strings an iterator of type Iterator JButton is used to iterate through a collection of JButtons and so on An iterator is often used to apply the same operation to all the elements in a collection In many cases it s possible to avoid the use of iterators for this purpose by using a for each loop The for each loop was discussed in Subsection 7 1 1 for use with arrays and in Subsection 7 3 3 for use with ArrayLists But in fact a for each loop can be used to iterate through any collection For a collection coll of type Collection T a for each loop takes the form for T x coll for each object x of type T in coll process x Here x is the loop control variable Each object in coll will be assigned to x in turn and the body of the loop will be executed for each object Since objects in coll

    Original URL path: http://math.hws.edu/javanotes/c10/s1.html (2016-02-07)
    Open archived version from archive

  • Javanotes 7.0, Section 10.3 -- Maps
    an iterator for the key set of a map to traverse the map For example if map is of type Map String Double we could write Set String keys map keySet The set of keys in the map Iterator String keyIter keys iterator System out println The map contains the following associations while keyIter hasNext String key keyIter next Get the next key Double value map get key Get the value for that key System out println key value Or we could do the same thing more easily avoiding the explicit use of an iterator with a for each loop System out println The map contains the following associations for String key map keySet for each key in the map s key set Double value map get key System out println key value If the map is a TreeMap then the key set of the map is a sorted set and the iterator will visit the keys in ascending order For a HashMap the keys are visited in an arbitrary unpredictable order The Map interface defines two other views If map is a variable of type Map K V then the method map values returns an object of type Collection V that contains all the values from the associations that are stored in the map The return value is a Collection rather than a Set because it can contain duplicate elements since a map can associate the same value to any number of keys The method map entrySet returns a set that contains all the associations from the map The elements in the set are objects of type Map Entry K V Map Entry K V is defined as a static nested interface inside the interface Map K V so its full name contains a period However the name can be used in the same way as any other type name The return type of the method map entrySet is written as Set Map Entry K V The type parameter in this case is itself a parameterized type Although this might look confusing it s just Java s way of saying that the elements of the set are of type Map Entry K V The information in the set returned by map entrySet is actually no different from the information in the map itself but the set provides a different view of this information with different operations Each Map Entry object contains one key value pair and defines methods getKey and getValue for retrieving the key and the value There is also a method setValue value for setting the value calling this method for a Map Entry object will modify the map itself just as if the map s put method were called As an example we can use the entry set of a map to print all the key value pairs in the map This is more efficient than using the key set to print the same information as I did in the above example since we don t have to use the get method to look up the value associated with each key Suppose again that map is of type Map String Double Then we can write Set Map Entry String Double entries map entrySet Iterator Map Entry String Double entryIter entries iterator System out println The map contains the following associations while entryIter hasNext Map Entry String Double entry entryIter next String key entry getKey Get the key from the entry Double value entry getValue Get the value System out println key value or using a for each loop System out println The map contains the following associations for Map Entry String Double entry map entrySet System out println entry getKey entry getValue Maps are not the only place in Java s generic programming framework where views are used For example the interface List T defines a sublist as a view of a part of a list If list implements the interface List T then the method list subList fromIndex toIndex where fromIndex and toIndex are integers returns a view of the part of the list consisting of the list elements in positions between fromIndex and toIndex including fromIndex but excluding toIndex This view lets you operate on the sublist using any of the operations defined for lists but the sublist is not an independent list Changes made to the sublist are actually made to the original list Similarly it is possible to obtain views that represent certain subsets of a sorted set If set is of type TreeSet T then set subSet fromElement toElement returns a Set T that contains all the elements of set that are between fromElement and toElement including fromElement and excluding toElement The parameters fromElement and toElement must be objects of type T For example if words is a set of type TreeSet String in which all the elements are strings of lower case letters then words subSet m n contains all the elements of words that begin with the letter m This subset is a view of part of the original set That is creating the subset does not involve copying elements And changes made to the subset such as adding or removing elements are actually made to the original set The view set headSet toElement consists of all elements from the set which are strictly less than toElement and set tailSet fromElement is a view that contains all elements from the set that are greater than or equal to fromElement The class TreeMap K V defines three submap views A submap is similar to a subset A submap is a Map that contains a subset of the keys from the original Map along with their associated values If map is a variable of type TreeMap K V and if fromKey and toKey are of type T then map subMap fromKey toKey returns a view that contains all key value pairs from map whose keys are between fromKey and toKey including fromKey and excluding toKey There are also views map headMap

    Original URL path: http://math.hws.edu/javanotes/c10/s3.html (2016-02-07)
    Open archived version from archive

  • Javanotes 7.0, Section 10.5 -- Writing Generic Classes and Methods
    a method public void draw and suppose that Shape has subclasses such as Rect and Oval Suppose that we want a method that can draw all the shapes in a collection of Shapes We might try public static void drawAll Collection Shape shapes for Shape s shapes s draw This method works fine if we apply it to a variable of type Collection Shape or ArrayList Shape or any other collection class with type parameter Shape Suppose however that you have a list of Rects stored in a variable named rectangles of type Collection Rect Since Rects are Shapes you might expect to be able to call drawAll rectangles Unfortunately this will not work a collection of Rects is not considered to be a collection of Shapes The variable rectangles cannot be assigned to the formal parameter shapes The solution is to replace the type parameter Shape in the declaration of shapes with the wildcard type extends Shape public static void drawAll Collection extends Shape shapes for Shape s shapes s draw The wildcard type extends Shape means roughly any type that is either equal to Shape or that is a subclass of Shape When the parameter shapes is declared to be of type Collection extends Shape it becomes possible to call the drawAll method with an actual parameter of type Collection Rect since Rect is a subclass of Shape and therefore matches the wildcard We could also pass actual parameters to drawAll of type ArrayList Rect or Set Oval or List Oval And we can still pass variables of type Collection Shape or ArrayList Shape since the class Shape itself matches extends Shape We have greatly increased the usefulness of the method by using the wildcard type Although it is not essential you might be interested in knowing why Java does not allow a collection of Rects to be used as a collection of Shapes even though every Rect is considered to be a Shape Consider the rather silly but legal method that adds an oval to a list of shapes static void addOval List Shape shapes Oval oval shapes add oval Suppose that rectangles is of type List Rect It s illegal to call addOval rectangles oval because of the rule that a list of Rects is not a list of Shapes If we dropped that rule then addOval rectangles oval would be legal and it would add an Oval to a list of Rects This would be bad Since Oval is not a subclass of Rect an Oval is not a Rect and a list of Rects should never be able to contain an Oval The method call addOval rectangles oval does not make sense and should be illegal so the rule that a collection of Rects is not a collection of Shapes is a good rule As another example consider the method addAll from the interface Collection T In my description of this method in Subsection 10 1 4 I say that for a collection coll of type Collection T coll addAll coll2 adds all the objects in coll2 to coll The parameter coll2 can be any collection of type Collection T However it can also be more general For example if T is a class and S is a sub class of T then coll2 can be of type Collection S This makes sense because any object of type S is automatically of type T and so can legally be added to coll If you think for a moment you ll see that what I m describing here a little awkwardly is a use of wildcard types We don t want to require coll2 to be a collection of objects of type T we want to allow collections of any subclass of T To be more specific let s look at how a similar addAll method could be added to the generic Queue class that was defined earlier in this section class Queue T private LinkedList T items new LinkedList T public void enqueue T item items addLast item public T dequeue return items removeFirst public boolean isEmpty return items size 0 public void addAll Collection extends T collection Add all the items from the collection to the end of the queue for T item collection enqueue item Here T is a type parameter in the generic class definition We are combining wildcard types with generic classes Inside the generic class definition T is used as if it is a specific though unknown type The wildcard type extends T means some type that is equal to or extends that specific type When we create a queue of type Queue Shape T refers to Shape and the wildcard type extends T in the class definition means extends Shape meaning that the addAll method of the queue can be applied to collections of Rects and Ovals as well as to collections of Shapes The for each loop in the definition of addAll iterates through the collection using a variable item of type T Now collection can be of type Collection S where S is a subclass of T Since item is of type T not S do we have a problem here No no problem As long as S is a subclass of T a value of type S can be assigned to a variable of type T The restriction on the wildcard type makes everything work nicely The addAll method adds all the items from a collection to the queue Suppose that we wanted to do the opposite Add all the items that are currently on the queue to a given collection An instance method defined as public void addAllTo Collection T collection would only work for collections whose base type is exactly the same as T This is too restrictive We need some sort of wildcard However extends T won t work Suppose we try it public void addAllTo Collection extends T collection Remove all items currently on the queue and add them to collection

    Original URL path: http://math.hws.edu/javanotes/c10/s5.html (2016-02-07)
    Open archived version from archive