EECS2030: Advanced Object-Oriented Programming - CombinePDF (1)

EECS2030: ADVANCED OBJECT-ORIENTED PROGRAMMING By: Dr. Marzieh Ahmadzadeh Announcement ▪ This week’s office hour is the last office hour. ▪ If there is any regrade request, you MUST attend this office hour. Outline ▪ Last Week ▪ ADT ▪ Examples of ADT ▪ Collection...

EECS2030: ADVANCED OBJECT-ORIENTED PROGRAMMING By: Dr. Marzieh Ahmadzadeh Announcement ▪ This week’s office hour is the last office hour. ▪ If there is any regrade request, you MUST attend this office hour. Outline ▪ Last Week ▪ ADT ▪ Examples of ADT ▪ Collection and its family ▪ Searching ▪ Sorting ▪ This Week ▪ Time Complexity ▪ Big-O ▪ Recursion Correctness Algorithm Analysis (AKA algorithm performance) ▪ Is the approach by which two different algorithms that solves the same problem can be compared. ▪ The required resources for an algorithm to complete its task should be compared. ▪ How much of computer resources does an algorithm use? ▪ Memory Space ▪ We are not interested in this for now. ▪ CPU time ▪ Mostly is dependent to the input size ▪ How to measure the running time? ▪ Experimental method ▪ Theoretical analysis 4 Experimental Methods ▪ Implement the algorithm using a programming language. ▪ Start the timer 4500 ▪ Execute the algorithm 4000 ▪ Stop the timer 3500 3000 ▪ Plot the results to compare. 2500 2000 1500 1000 500 0 1 2 3 4 5 6 7 8 9 10 11 12 N 5 Experimental Methods: Drawback ▪ The algorithm should be implemented. ▪ The results are only indicative of the algorithm running time on the experimental data. ▪ Example: Sort the following lists with selection sort and compare the running time. 1 2 3 4 5 6 7 8 9 10 4 9 5 8 1 7 2 6 3 10 ▪ Dependent on the programming language. ▪ Dependent on the hardware. 6 Theoretical Analysis ▪ Uses a pseudo-code instead of the code ▪ Independent on the programming language ▪ Independent of the hardware ▪ You can decide on which scenario to consider ▪ Best case: does not represent reality. ▪ Average case: difficult to determine ▪ Worst case: give a proper basis for comparison (all the operations of the algorithm is executed) ▪ Describe the execution time as a function of input size. ▪ Assumes that every primitive operation takes one unit of time in a certain machine model. ▪ expression evaluation, assignment, indexing into an array, function call, returning from a function, comparison, follow an object reference ▪ Analogy: put $1 in a piggybank for every operation mentioned above. 7 Example ▪ In worst case scenario, what is the running Code # of Operations ($) time of this algorithm? (How much money max  aList do you spend to run the algorithm?) i  1 ▪ aList is a list containing n comparable numeric data While ( i max Function findMax(aList, n) max  a_list[i] max  a_list i  i + 1 for i  1 to n do return max if a_list[i] > max max  aList[i] return max ▪ It is dependent on the # of inputs: ▪ Did we consider the worst-case scenario ▪ n = 100 then $798 when analyzing the running time of this ▪ n = 10 then $78 algorithm? 8 Time Complexity (AKA running time) ▪ Is the time taken to run an algorithm when maximum amount of time is spent. ▪ i.e. worst case ▪ Since complexity varies with different input size, it is shown by a function: ▪ T(n) = r, where n: input size, r: running time ▪ n ϵ N, r ϵ R+ ▪ For previous example: T(n) = 8n – 2 ▪ How to say which algorithm is better? ▪ T(n) = 106 n + 3 ▪ T(n) = 100n + 1025 ▪ We don’t need to know the exact value of T(n), instead an upper bound (i.e. dominant term) is used as an estimate. ▪ upper bound (i.e. dominant term) is the term that grows faster than other terms in the equation. 9 The order of magnitude ▪ We define the order of magnitude as the upper bound [aka dominant term] of T(n) that increases faster (than other terms) as the value of n increases. ▪ Suppose T(n) = 8n-2, then the order of magnitude [upper bound] is n. ▪ To find the upper bound 𝑓 𝑛 : ▪ ∋ 𝑐, ∀𝑛 ∈ 𝑁: 𝑇 𝑛 ≤ 𝑐. 𝑓 𝑛 ▪ 𝑇 𝑛 = 8𝑛 − 2 , 𝑓 𝑛 = 𝑛, 𝑐 = 8 ▪ The order of magnitude is shown by Big-O notation. O(𝑓 𝑛 ) ▪ If T(n) = 8n – 2, then the order of magnitude is O(n) ▪ T has order n ▪ T is big- oh of n ▪ Therefore, the following two algorithms are the same in terms of the order of magnitude ( and therefore, time complexity/ running time). ▪ T(n) = 106 n + 3 ▪ T(n) = 100n + 1025 10 Example ▪ Prove that the order of magnitude of the following is the same: ▪ T(n) = 106 n + 3 ▪ T(n) = 100n + 1025 11 Example ▪ The time complexity of an algorithm is 3𝑛2 + 5𝑛 − 7. Prove that the order of magnitude is 𝑛2 ▪ You should find c such that 3𝑛2 + 5𝑛 − 7 ≤ c𝑛2 12 Side Note: ▪ The order of magnitude of an algorithm is only important when N is large. ▪ For small N, sometimes an algorithm with larger running time may be better, as it does not add any overhead to the running time. ▪ e.g. ▪ Selection Sort running time : O(𝑛2 ) ▪ Merge sort running time: O(n log 2 𝑛) ▪ Recursion overhead – pushing and popping into/from stack ▪ Therefore, the study of algorithms running time, is only useful when N is large. 13 The Upper Bound ▪ Suppose T(n) = a*n + b, then a*n [and therefore, n] should only be dominant if n is large enough. ▪ So we define asymptotic upper-bound: ▪ Let 𝑓: 𝑁 → 𝑅+ , T: 𝑁 → 𝑅+ be functions then: 𝑂(𝑓(𝑛)) = {𝑇(𝑛)| ∋ 𝑐, ∋ 𝑏, ∀𝑛 ≥ 𝑏: 𝑇(𝑛) ≤ 𝑐. 𝑓(𝑛)} ▪ T(n) ∈ O(f(n)) for any function 𝑇(𝑛), if there exist constants 𝑐 and 𝑏 such that for all values of 𝑛 ≥ 𝑏, the function 𝑇(𝑛) is less than or equal to 𝑐 times 𝑓(𝑛). ▪ 𝑇 𝑛 = 2𝑛 + 10 , 𝑓 𝑛 = 𝑛 , 𝑐 = 3, 𝑛 ≥ 10 14 Example ▪ If the running time of an algorithm is estimated to be 𝑇 𝑛 = 3𝑛2 + 5𝑛 + 7 then what is the order of magnitude of this algorithm? ▪ The dominant term is 𝑛2 if ∋ 𝑐, ∋ 𝑏, ∀𝑛 ≥ 𝑏: 3𝑛2 + 5𝑛 + 7 ≤ 𝑐. 𝑛2 ▪ Find c and b such that 3𝑛2 + 5𝑛 + 7 ≤ c𝑛2 ▪ c=4 b=7 ▪ So 3𝑛2 + 5𝑛 + 7 ∈ O(𝑛2), the order of magnitude is 𝑛2 15  Important Functions ▪ Constant : O(1) ▪ Logarithmic: O(log n) ▪ Linear: O(n) ▪ Linearithmic: O(n log n) ▪ Quadratic: O(n2) ▪ Cubic : O(n3) ▪ Exponential: O(2n) 16 O(1): Example ▪ Describes an algorithm whose running time is independent of the input size. ▪ Adding an element into a hashSet ▪ Accessing an element from a list ▪ Push(), Pop into/from a Stack 10 5 7 2 4 3 9 11 3 8 17 O(log 2 𝑛): Example ▪ Describes an algorithm whose running time grows in proportion to the logarithm of the input size. ▪ Binary search 1 2 3 4 5 6 7 8 9 10 6 7 8 9 10 9 10 10 Worst case scenario, how many times the list should be split to two sub-lists? 18 O(n): Example ▪ Describes an algorithm whose running time grows in proportion to the input size. ▪ Linear Search 8 5 7 2 4 3 9 1 3 10 20 O(n log 2 𝑛): Example ▪ Describes an algorithm whose running time is proportional to the product of n by the logarithm of the input size. ▪ Merge Sort : 𝑖 ∗ 𝑐 ∗ 𝑛 ≈ 𝑛 log 2 𝑛 1. Merging 𝑐 ∗ 𝑛 2. Splitting i = log 2 𝑛 21 O(𝑛2 ): Example ▪ Describes an algorithm whose running time is proportional to the input size squared. ▪ A nested-for loop containing two loops, each runs n times. ▪ Selection Sort 22 O(𝑛3 ): Example ▪ Describes an algorithm whose running time is proportional to the input size cubed. ▪ A nested-for loop containing three loops, each runs n times. ▪ n by n matrix multiplication 23 O(2𝑛 ): Example ▪ Describes an algorithm whose running time grows exponentially. ▪ Extremely inefficient ▪ Example: (binary recursion) Fibonacci public static int fibonacchi (int n) { if (n == 1 || n == 2 ) return 1; else return fibonacchi(n -1) + fibonacchi (n - 2); } 24 Activity 25 RECURSION CORRECTNESS 27 Induction ▪ Suppose you want to prove that a statement f(n) is true for every positive integer n. ▪ In mathematics, induction technique is used to prove facts about natural numbers. ▪ By induction: ▪ Base Case: Prove the statement is true for the smallest possible n. ▪ Induction Case: assume that f(n) is true for all positive n, then prove that it is true for n+1. ▪ Recursion is directly related to induction. ▪ We can use induction to prove that the recursion is correct. 28 Example: Induction ▪ Prove that 2𝑛 < 𝑛! for all 𝑛 > = 4 29 Example: Recursion Correctness ▪ Prove that the factorial function is correct. ▪ Base case: if 𝑛 = 0 then 𝑓𝑎𝑐𝑡 = 1 ▪ Recursive case: assume that 𝑓𝑎𝑐𝑡 𝑛 is correct, then 𝑓𝑎𝑐𝑡 𝑛 + 1 = 𝑛 + 1 ∗ 𝑓𝑎𝑐𝑡(𝑛), which is also correct. 30 Example: Recursion Correctness ▪ Prove that the power function is correct. ▪ Base case: if 𝑛 = 0 then 𝑏𝑎𝑠𝑒 0 = 1 ▪ Recursive case: assume that power 𝑛, 𝑏𝑎𝑠𝑒 is correct, prove 𝑝𝑜𝑤𝑒𝑟 𝑛 + 1, 𝑏𝑎𝑠𝑒 is correct. 𝑝𝑜𝑤𝑒𝑟 𝑛 + 1, 𝑏𝑎𝑠𝑒 = 𝑏𝑎𝑠𝑒 ∗ 𝑝𝑜𝑤𝑒𝑟 𝑛, 𝑏𝑎𝑠𝑒 = 𝑏𝑎𝑠𝑒 ∗ 𝑏𝑎𝑠𝑒 𝑛 = 𝑏𝑎𝑠𝑒 𝑛+1 31 Recursion Termination ▪ The next step on proving the correctness of a recursion is to prove that the recursion terminates. ▪ i.e. it reaches a base case. ▪ 𝑝𝑜𝑤𝑒𝑟 𝑛, 𝑏𝑎𝑠𝑒 = 𝑏𝑎𝑠𝑒 ∗ 𝑝𝑜𝑤𝑒𝑟 𝑛 − 1, 𝑏𝑎𝑠𝑒 = 𝑏𝑎𝑠𝑒 ∗ 𝑏𝑎𝑠𝑒 ∗ 𝑝𝑜𝑤𝑒𝑟 𝑛 − 2, 𝑏𝑎𝑠𝑒 = ….. ▪ = 𝑏𝑎𝑠𝑒 ∗ 𝑏𝑎𝑠𝑒 ∗ 𝑏𝑎𝑠𝑒 ∗ …. 𝑝𝑜𝑤𝑒𝑟 0, 𝑏𝑎𝑠𝑒 = 𝑏𝑎𝑠𝑒 𝑛 ∗ 1 = 𝑏𝑎𝑠𝑒 𝑛 ▪ Proving the termination of a recursion is not always as straight forward. ▪ More on EECS3101 32 Expectations ▪ You should have a good understanding of what time complexity of an algorithm means. ▪ You should be able to estimate the running time of the given algorithm. ▪ based on the 9 functions that were discussed. ▪ You should be able to prove the correctness of simple recursion algorithms using induction. ▪ You should be able to informally show if a simple recursive algorithm terminates. ▪ One Minute Paper 33  EECS2030: ADVANCED OBJECT-ORIENTED PROGRAMMING By: Dr. Marzieh Ahmadzadeh Outline ▪ Last Week ▪ Generics ▪ This week ▪ Abstract Data Type ▪ Examples of ADT ▪ Collection ▪ List ▪ Sets ▪ Searching ▪ Sorting ABSTRACT DATA TYPE 3 The Story of Software Engineering ▪ Requirement Engineering ▪ Software Architecture Design ▪ Implementation ▪ Testing ▪ Maintenance ▪ The cost of change will dramatically increase in the later stages. ▪ You should have such an [almost] perfect design that if at the implementation level, you needed to change something, this change has minimum effect on the rest of the code. ▪ Modularity and therefore creating ADTs is the solution. 4 Abstract Data Type ▪ An ADT, is a type in which the organization of data and the Examples of data and their operations on data is specified. operations: ▪ Type: class ▪ Organization of data: proper definition of instance variables / a data structure ▪ Operations: methods ▪ Exceptions ▪ By ADT: ▪ we focus on the operations rather than the implementation ▪ To hide away implementation details ▪ One of the important applications of abstract classes and interfaces is to create an Abstract Data Type. 5 Example: Stack ▪ A stack is an ADTthat follows FILO rule for insertion and removal. ▪ Organisation of data (i.e. data structure) ▪ Array, arrayList, … ▪ Operations: ▪ Two main operations: ▪ push(object) ▪ pop() ▪ Auxiliary methods: ▪ size() ▪ top() ▪ Exception ▪ pop(), when there is no item in the Stack ▪ top() , when there is no item in the stack ▪ push(), stack overflow 6 Stack: Implementation Attention: This code is not complete as the exceptions are not handled. 7 ADT by Abstract Classes or Interfaces 8 ADT & Abstract Classes & Interfaces ▪ Do not confuse ADT and abstract classes. ▪ One way to implement ADT is to use abstract classes or interfaces. ▪ With abstract classes and interfaces, creating an ADT is guaranteed. ▪ As the focus will be on the operations not their implementations 9 EXAMPLES OF ADT IN JAVA (COLLECTIONS, LISTS & SETS) 10 An Example of ADT in java ▪ Collection’s requirement: 1. A container to hold one or more objects. 2. It should allow duplicate data for some applications, and should not for others [e.g. ArrayList vs Set] 3. It should allow sequential access for some applications and should not for others. [e.g. List vs Set] 4. It should provide all the operations that one needs to access data. [e.g. insertion, removal, processing, searching & sorting]. 5. It should have the capability to be used for polymorphism purpose. ▪ Collection in java: ▪ is a framework that satisfies the above requirements. ▪ Is an interface that has a number of interfaces and their implementations (i.e. classes) as its subtypes [see next slide] ▪ Calls the stored objects as elements. ▪ Provides a couple of algorithms for sorting and searching 11 Collections Inheritance Hierarchy 12 Note: Collections can only store object references  Collection Operations * ** * Optional methods * * * 13 Optional Methods ▪ A concrete class that implements an interface MUST implement all the methods, including the ones that marked optional. ▪ Why is it called optional? ▪ Because some of the methods are useful for some types of collections, and some are not. ▪ At least the method signature is there, which creates a consistency among all the implementation of the same method. ▪ It is a very bad practice to leave a method body empty, just because you don’t have any definition for it. ▪ Some of them return something, so at least you must return something. ▪ In case an optional method seems unnecessary then UnsupportedOperationException should be thrown. ▪ UnsupportedOperationException is a RuntimeException, so it can be thrown in two ways, as you’ve learnt before. 14 LIST ADT 15 The List ADT ▪ Is an ordered collection ▪ data is added sequentially ▪ Data can be accessed by the position (index) of the element. ▪ Duplicate element is allowed. ▪ Like arrays, they are zero based. ▪ Extends Collection, which extends Iterable. ▪ If an object IS-A(n) Iterable, then it can be used in for-each loop. ▪ e.g. for (String obj: str) where str is a List 16  The List interface operations ** * * //searching //sorting //searching //searching * Optional methods The static factory methods [i.e. of] were removed from this list. 17 The List’s Operations: Recall ▪ Declaration: ▪ D.T. is List, A.T. can be any concrete subclass of List. ▪ It is a generic type. Therefore, all the types can be replaced. ▪ The generic can be even another List, however it is not recommended as equal() and hashCode() may not work as expected. ▪ Insertion: ▪ Is added to the end of the list, unless you specify the index in which the object should be inserted. ▪ Deletion: ▪ Can delete by the object value or the index. ▪ Access: ▪ Can be accessed in both by the index and the object. ▪ Search 18 [Optional]: The ListIterator ▪ List interface provides two useful methods that create and return a special type of iterator called ListIterator. 19 SET ADT 20 The Set ADT ▪ It models the mathematical sets. ▪ Is NOT an ordered collection ▪ Data can NOT be accessed by their position. ▪ data is hashed. ▪ Duplicate element is NOT allowed. ▪ Main operations are set intersection, union and difference. 21  The Set interface operations * * * * * //searching * //searching * Optional methods The overloaded static factory methods [i.e. of] were removed from this list. 22  HashSet is normally used to create a set. HashSet is created using a hash table (i.e. uses an instance of HashMap) Therefore, it is not an ordered collection. Question: Why does HashSet requires to implement Set, while AbstractSet, has already done that? 23 The Set’s Operations ▪ Declaration: ▪ D.T. is Set, A.T. can be any concrete subclass of set. ▪ can be any type of object reference. ▪ Insertion: ▪ Is added to the set using a hash function ▪ Union ▪ Deletion: ▪ Can delete the object by passing it to the method. 24 The Set’s Operations ▪ Access: ▪ No sequential access is available. ▪ An iterator on the objects should be created. ▪ Search ▪ Intersection ▪ Difference 25 Homework ▪ Since no duplicate data is allowed in the set, a set can be used for many applications: ▪ Remove all the duplicates from a list. ▪ Hint: a set cannot have a duplicate data. ▪ Find all the duplicate data in a list. ▪ Hint: The Set’s add() method returns false, if the object is not added. ▪ Find all the people, who have taken courses EECS2030 and EECS2031 this semester, assuming that each course has it’s own list. ▪ Hint: Set’s intersection ▪ Find all the people who have taken at least one course with a certain prof. assuming that each prof has its own list. ▪ Hint: set’s union ▪ Find all the people who didn’t pass the prerequisite of a course assuming that each course has its own list of students. ▪ Hint: set difference 26 Activity 27 SEARCHING 29 Searching ▪ Is an important operation for many data structure and a popular operation in software development as seen in ADT examples. ▪ Types of Searching: ▪ Linear ▪ Binary Search ▪ List-based binary search ▪ BSTs -> More in Data Structure Course ▪ Hashing Technique -> More in Data Structure Course 30 Linear Search ▪ Scan the list sequentially to either find the requested element or reach to the end of the list. ▪ Find Peter John Jane Alice Bob Rose Peter Marge jack 31 List-based Binary Search ▪ A searching algorithm that is applicable to a sorted list. ▪ Two pointers are needed. One to point to beginning and one to the end of the list. ▪ Iteratively(recursively): ▪ Find the middle of the list ▪ If what you are looking for is greater than the item in the middle, search the right sub-list ▪ Otherwise search the left sub-list ▪ Stop either when you find the data or when the lower_boundary_index > higher_boundary_index 32 List-Based Binary Search ▪ Find Peter Alice Bob Jack Jane John Marge Peter Rose ▪ Find Jade 33 List-Based Binary Search Alice Bob Jack Jane John Marge Peter Rose ▪ Find Peter 34 List-Based Binary Search ▪ Find Peter Alice Bob Jack Jane John Marge Peter Rose 35 SORTING 36 Sorting ▪ Is an important operation for many data structure and a popular operation in software development as seen in ADT examples. ▪ Many algorithms are available. ▪ Such as: ▪ They are different in terms of the time that it takes to sort a list. ▪ Selection Sort ▪ N = 1024 ➔ time required = 1,048,576 units ▪ O(n2) : for n data, n2 unit of CPU time is required. Stay tuned for this…. ▪ Merge-Sort ▪ N=1024 → time required= 1024 * 10 = 10,240 ▪ O(n log2 n): for n data, (n log2 n ) unit of CPU time is required. Stay tuned for this… ▪ Does this mean that we should always use the faster algorithm? 37 Selection Sort 11 35 44 74 88 46 37 38 70 11 35 37 38 44 46 70 74 88 11 35 44 74 70 46 37 38 88 11 35 37 38 44 46 70 74 88 11 35 44 38 70 46 37 74 88 11 35 37 38 44 46 70 74 88 11 35 44 38 37 46 70 74 88 11 35 44 38 37 46 70 74 88 11 35 37 38 44 46 70 74 88 38 Selection Sort Algorithm 39 Merge Sort ▪ Merge operation: ▪ Given two sorted list A & B ▪ Create a merged list C by removing the lower item from the top of either A or B. 1 31 57 28 36 47 58 80 ▪ The question is how to sort list A & B? 40  Merge Sort 11 35 44 74 88 46 37 38 70 11 35 44 74 88 46 37 38 70 11 35 44 74 11 35 41  Merge Sort 11 35 44 74 88 46 37 38 70 11 35 44 74 88 46 37 38 70 11 35 44 74 44 74 42  Merge Sort 11 35 44 74 88 46 37 38 70 11 35 44 74 88 46 37 38 70 11 35 44 74 43 Merge Sort 11 35 44 74 88 46 37 38 70 11 35 44 74 88 46 37 38 70 88 46 37 38 70 88 46 44 Merge Sort 11 35 44 74 88 46 37 38 70 11 35 44 74 88 46 37 38 70 46 88 37 38 70 37 38 70 38 70 45 Merge Sort 11 35 44 74 88 46 37 38 70 11 35 44 74 88 46 37 38 70 46 88 37 38 70 37 38 70 46 Merge Sort 11 35 44 74 88 46 37 38 70 11 35 44 74 88 46 37 38 70 46 88 37 38 70 47 Merge Sort 11 35 44 74 88 46 37 38 70 11 35 44 74 37 38 46 70 88 48 Merge Sort 11 35 37 38 44 46 70 74 88 49 Homework ▪ See java.util.Arrays.sort() for sorting methods on arrays. ▪ See java.util.Arrays.parallelSort() ▪ [Optional]: The base algorithm for both the above methods is quick-sort with two pivots. ▪ To sort a list you can use Collections.sort() ▪ Note: it is Collections not Collection. ▪ Collections is a class and sort is its static method ▪ Collection is an interface. ▪ They both are in java.util 50 Expectations ▪ You should be able to explain what is the purpose of defining an abstract data type. ▪ You should be able to navigate the API and understand the relationships between the different components of Collection. ▪ You should be able to use the collections in your code. ▪ You should be able to explain how a linear and binary search works and consequently be able to implement the related algorithms. ▪ You should be able to explain how selection and merge sort work and consequently be able to implement the related code. ▪ One Minute Paper 51  EECS2030: ADVANCED OBJECT-ORIENTED PROGRAMMING By: Dr. Marzieh Ahmadzadeh Outline ▪ Last Week: ▪ Abstract Classes ▪ Interfaces ▪ This Week: ▪ Generics ▪ Generic classes ▪ Generic methods ▪ Generic & inheritance Recall from the last activity ▪ Stack data structure: ▪ Main methods ▪ push(e) ▪ pop() ▪ Auxiliary methods ▪ isEmpty() ▪ top() ▪ Application of Stack ▪ Program stack ▪ Undo operation (editors) ▪ Parenthesis matching in an expression (compilers) ▪ Tag matching in files (XML or HTML) ▪ etc. etc. etc. ▪ It is a very popular data structure that is used to store a variety of objects/data types. 3 A Stack of integers 4 A Stack of Strings compared to a stack of Integer What if we need a ProgramStack, HTMLtagStack, ParenthesisStack, ….? 5 Generic Types ▪ A mechanism by which the problem of duplicate code is solved. ▪ With this mechanism, an interface, class and method can have a parameter as their type. ▪ At runtime, the actual type is replaced. ▪ A class (interface, or method) with type parameter is called parameterized class (interface or method), generic class (interface, or method) or simply generics. IntegerStack StringStack ProgramStack Stack HTMLtagStack ParenthesisStack 6 Generics: Implementer Side ▪ Use to represent a type in class definition. ▪ Whenever the type is required, use the letter instead. 7 Generics: Client Side ▪ When you use the class to create a type, insert the desired type in the angle bracket. ▪ Note: only non-primitive data type can replace a generic type. 8 Questions: ▪ Where have you seen the generics type before? ▪ Isn’t it a better idea that we create a Stack of Object, knowing that with polymorphism any object type can be replaced? ▪ Casting was removed. ▪ Type match can be done at compile time. 9 GENERICS & INHERITANCE (1) Generics & Inheritance ▪ Is the following code valid? ▪ Is this a valid code? ▪ Is List a subtype of List? NO ▪ The same rule applies to the Generics: If T1 IS-A T2, then SomeClass IS-NOT SomeClass 11 Examples ▪ String IS-A(n) object but…… ▪ Student IS-A(n) UniversityMember but….. ▪ Triangle IS-A Shape but…. ▪ MP4Player is an ElectronicDevice but…. 12 ARRAY OF GENERICS 13 Cannot create a generic array ! ▪ Why? ▪ Solution? 14 GENERICS & INHERITANCE (2) Generics & Inheritance ▪ Is the following code valid? Why? ▪ How about this code? ▪ Arrays are said to be covariant, which means an array of type T[ ], can contain objects of S, where S is a subtype of T. 16 Example: Arrays are covariant 17 MULTIPLE PARAMETERS 18 Generics < K, V, …> ▪ If required, a class (interface or method) can be parameterized with more than one parameter. ▪ Java Example: ▪ Map interface and HashMap class 19 Type Parameter Naming Conventions E − Element K − Key [ Map ADT] V − Value [Map ADT] N − Number T − Type, for first generic type parameter. S − Type, for second generic type parameter. U − Type, for third generic type parameter. V − Type, for fourth generic type parameter. 20 GENERIC METHODS Generics Methods ▪ Methods can be defined as generics. ▪ Independent or dependent to their classes. ▪ The generic type is placed before the return type in the method heading. ▪ The scope of the type parameter is limited to the method. 22 Generic Methods: How to call. Implementer Side Client Side ▪ Note: the type that is passed to the method is an object reference. ▪ So why is Integer[] arr1 = { 1 , 2, 3}; allowed? ▪ Autoboxing: Automatic conversion from primitive data type to the corresponding object. ▪ This is done using the objects wrapper class. 23 Wrapper Class Primitive type Wrapper class boolean Boolean.valueOf() byte Byte.valueOf() char Character.valueOf() float Float.valueOf() int Integer.valueOf() long Long.valueOf() short Short.valueOf() Wrapper classes are actually a static factory double Double.valueOf() method. 24 Different approach to implement a generic method ▪ Please note that the type of the parameter of a method does not need to be the same as the type of the class parameter. Note the difference between these two codes. Independent vs dependent ▪ K & V’s scope: The whole class ▪ S & T’s scope: The method 25 GENERIC & INHERITANCE (3) 27 Bounded Type Parameters ▪ Using inheritance relationship, you can restrict the allowable type that replaces the generic type. ▪ Why the following code generates an error? ▪ What is the solution? ▪ Use compareTo() ▪ What if the object that replaces T is not comparable? 28 Bounded Type Parameters ▪ With this solution, the type that replaces T IS-A Comparable, so compareTo() can be used. ▪ The type parameter T is bounded to be a Comparable. 29 UPPER BOUND WILDCARD 30 Problem Statement ▪ Can we use this method as is, and call it with List, List etc.? ▪ How can we rewrite the method, so that it can be used for Number and its children? ▪ Use Upper Bound Wildcard 31 Upper Bound Wildcard ▪ When there is an inheritance relationship, ▪ and the restriction on the type parameter is to be relaxed ▪ then Upper Bound Wildcard is used. ▪ ? is the wildcard. Only a list of A list of Number can be Number passed and all its subclasses can be passed. 32 Example 33 BOUNDED WILDCARD & GENERICS 34 Upper Bound Wildcard in Generics This method alone may not seem useful as is. The usefulness will be clearer if the class in which this method is defined, is parameterized too. 35 Lower Bound Wildcards in Generics ▪ A lower bound wildcard restricts the generic type to be a specific type or a supertype of that. ▪ It is defined by ▪ Applications: ▪ When the used methods are independent of the type replaces the ‘?’. ▪ e.g, When only Object’s methods are used. 38 When to use Wildcards? A guideline ▪ Definition ▪ IN-variable: A variable, whose value is used in the code. ▪ AKA producer ▪ OUT-Variable: A variable, which gets a value in the code. ▪ AKA consumer ▪ IN/OUT-variable: A variable that not only produces a value but also consume it. ▪ Guideline: ▪ IN-Variable: use upper bound wildcards 39 Guideline’s Justification ▪ IN-Variable: use upper bound wildcards