LESSON 11 Generic Collections Part 1 CSC 300

LESSON 11 Generic Collections Part 1 CSC 300

LESSON 11 Generic Collections Part 1 CSC 300 Fall 2019 Howard Rosenthal Course References Materials for this course have utilized materials in the following documents. Additional materials taken from web sites will be referenced when utilized. 1. http://www.programmedlessons.org/Java9/index.html 2. Anderson, Julie and Franceschi Herve, Java Illuminated 5 TH Edition,, Jones and Bartlett, 2019 3. Bravaco, Ralph and Simonson, Shai, Java programming From The Ground Up, McGraw Hill, 2010 4. Deitel, Paul and Deitel, Harvey, Java, How To Program, Early Objects, Eleventh Edition, Pearson Publishing, 2017 5. Gaddis, Tony, Starting Out With Objects From Control Structures Through Objects, Pearson Publishing, Version 7, 2019

6. Horstmann, Cay, Core Java For The Impatient, Addison Wesley- Pearson Education, 2015 7. Schmuller, Joseph, Teach Yourself UML In 24 Hours Second Edition, SAMS Publishing, 2002 8. Urma, Raoul-Gabriel, Fusco, Mario and Mycroft, Alan, Java 8 in Action: Lambdas, Streams, and Functional-Style Programming, Manning Publishing, 2014 9. Wirfs-Brock, Rebecca, Wilkerson, Brian and Wiener, Laura, Designing ObjectOriented Software, Prentice Hall, 1990 2 Lesson Goals Learn what Collections are Use class Arrays for array manipulation Briefly review wrapper classes, boxing and unboxing Learn to use pre-built generic data structures Learn about iterators Understand the List Interface and related classes Use algorithms of the Collections class to process collections

Understand the Queue interface and PriorityQueue class Understand the Set and SortedSet interface and HashSet, LinkedHashSet and TreeSet classes Understand the Map interface and HashMap, TreeMap and LinkedHashMap classes 3 Overview 4 The Collections Framework The Collections Framework is a unified architecture for representing and manipulating collections, enabling them to be manipulated independently of the details of their representation. It contains prebuilt generic data structures It reduces programming effort while increasing performance. It enables interoperability among unrelated APIs, reduces effort in

designing and learning new APIs, and fosters software reuse. It allows interoperability between APIs The framework is based on more than a dozen collection interfaces. It includes implementations of these interfaces and algorithms to manipulate them. The interface Collection contains bulk operations for adding, clearing and comparing objects in a collection. This includes adding a list of elements, or even a whole Collection, to a Collection Dont confuse the Collection interface with the Collections class Helpful reference For reading Oracle Java documentation https://docs.oracle.com/javase/tutorial/java/generics/types.html 5 Describing The Collections Class And Collections Objects

This Collections class consists exclusively of static methods that operate on or return collections. It contains polymorphic algorithms that operate on collections, "wrappers", which return a new collection backed by a specified collection, and a few other odds and ends. The methods of this class all throw a NullPointerException if the collections or class objects provided to them are null. The "destructive" algorithms contained in this class, that is, the algorithms that modify the collection on which they operate, are specified to throw UnsupportedOperationException if the collection does not support the appropriate mutation primitive(s), such as the set method. A collection is a data structure actually an object that can hold references to other objects Usually collections contain references to objects of any type that has an is-a relationship

In other words it takes advantage of polymorphism i.e an ArrayList of a certain type can have as member any subclass of that type Collections cannot manipulate variables of primitive data This is why we use wrapper classes for the primitive variables, taking advantage of autoboxing and unboxing, when needing to use a Collection class (i.e. ArrayList) with objects See IntegersInArrayList.java and CharacterArrayListExample.java See https://docs.oracle.com/javase/8/docs/api/java/util/Collections.html 6 The Java Collection Framework Hierarchy For The Collection interface 7 Polymorphism Example With ArrayList In the example below assume we create the ArrayList: ArrayList autotList = new ArrayList();

Then not only Auto objects, but Ford, Honda, Volvo, Civic, Accord and Pilot objects, etc. can be added to the ArrayList autoList Remember that if you retrieve an object from autoList you may need to cast downward to exact type in order to access its data and methods Auto Ford Civic Honda Volvo Accord Pilot 8

Some Collections Framework Interfaces collections framework classes and interfaces are all found in the java.util packa 9 Using The Iterator And iterator() Method An Introduction Often you wish to access the elements of an ArrayList one by one, in order You could write a counting loop You can use an Iterator object. The Interface Collection provides a method that returns an Iterator object, which allows a program to walk through the collection and remove elements from the collection during the iteration. To get an Iterator object, use the iterator method of ArrayList: Iterator iterator() // Returns an iterator i.e.

Iterator iter = names.iterator(); //creates an Iterator object ArrayList implements the Iterable interface (to be discussed later). iterator() is the only method in this interface An iterator object is used to visit the elements of a list one by one It visits only the cells that have data (so you don't need to worry about going past the end of data) This is more convenient than writing a loop 10 Iterator Methods An iterator implements the Iterator interface, which has the following methods: boolean hasNext() // Returns true if not all elements have been visited E next() // Returns the next element of the list, a reference to type E void remove() // Remove from the list the element just returned by next() You need to import the Iterator class: import java.util.Iterator;

Note: If a collection is modified by one of its methods after an iterator is created for that collection, the iterator becomes invalid Any operation performed with the iterator fails immediately and throws an exception. This is called fast-fail Fast-fail iterators help ensure that a modifiable collection is not manipulated by two or more threads at the same time. See ArrayListExampleIterator.java 11 Using The Enhanced For Loop With The ArrayList Class The enhanced for loop (sometimes called a "for each" loop) can be used with any class that implement the Iterable interface, such as ArrayList

for (ClassName currentObject: ArrayListName) { Process currentObject } The program does the same thing as we showed with the Iterator The enhanced for loop accesses the String references in names and assigns them oneby-one to currentObject With an enhanced for loop there is no danger an index will go out of bounds The enhanced for loop only visits those cells that are not empty, beginning with cell zero Since an ArrayList never has gaps between cells, all occupied cells are visited See ArrayListExampleIterator.java 12 The List interface and Related classes

13 Understanding Lists (1) A List (sometimes called a sequence) is an ordered Collection that can contain duplicate elements. List indices are zero based. In addition to the methods inherited from Collection, List provides methods for: Manipulating elements via their indices Manipulating a specified range of elements Searching for elements and obtaining a ListIterator to access the elements. Interface List is implemented by several classes, including ArrayList, LinkedList and Vector. (We discuss LinkedList later)

Autoboxing occurs when you add primitive-type values to objects of these classes, because they store only references to objects. See https://docs.oracle.com/javase/8/docs/api/java/util/List.html 14 Understanding Lists (2) Class ArrayList and Vector are resizable-array implementations of List. Inserting an element between existing elements of an ArrayList or Vector is an inefficient operation. A LinkedList enables efficient insertion (or removal) of elements in the middle of a collection, but is much less efficient than an ArrayList for jumping to a specific element in the collection. We discuss the architecture of linked lists later. The primary difference between ArrayList and Vector is

that operations on Vectors are synchronized by default, whereas those on ArrayLists are not. Unsynchronized collections provide better performance than synchronized ones. For this reason, ArrayList is typically preferred over Vector in programs that do not share a collection among threads. 15 ArrayList and Iterator List method add adds an item to the end of a list. List method size returns the number of elements. List method get retrieves an individual elements value from the specified index. Collection method iterator gets an Iterator for a Collection. Iterator- method hasNext determines whether there are more elements to iterate through. Returns true if another element exists and false otherwise.

Iterator method next obtains a reference to the next element. Collection method contains determine whether a Collection contains a specified element. Iterator method remove removes the current element from a Collection. Note: We refer to each ArrayList in this example. This would for instance allow us to substiture LinkedList for ArrayList if we needed to. Same with the way we implement removeColors method See CollectionTest.java 16 Type Inference With The <> Notation You can use type inferencing with <>, known as diamond notation, in statements that declare and create generic type variations

and objects. Example: List list= new ArrayList(); and List list = new ArrayList<>(); are equivalent list is actually an ArrayList 17 The LinkedList An Overview Linked Lists are linear data structures where the elements are not stored in contiguous locations and every element is a separate object with a data part and address part. The elements are linked using references to addresses. Each element is known as a node. Due to the dynamicity and ease of insertions and deletions, they are preferred over the arrays.

With an ArrayList, insertions and deletions require rewriting all elements after the insertion It also has few disadvantages like the nodes cannot be accessed directly instead we need to start from the head and follow through the link to reach to a node we wish to access. To store the elements in a linked list we use a doubly linked list which provides a linear data structure and also used to inherit an abstract class and implement list and deque interfaces. In Java, LinkedList class implements the list interface. The LinkedList class also consists of various constructors and methods like other java collections. We demonstrate some of these in LinkedListTest.java

See https://docs.oracle.com/javase/8/docs/api/java/util/LinkedList.html 18 Inserting A Node In a Doubly Linked List The dotted lines shows what happens when you insert Leah between Joshua and Miriam 19 Array vs. Linked List The LinkedList class in java is doubly linked This means it has a reference to the predecessor as well as the successor 20 Collections class Methods

21 Collections class Implements A Number Of Useful Static Methods Method Description sort Sorts the elements of a Collection in an input list See CollectionSorting.java or CollectionSorting1.java or (Time.java, TimeComparator.java and SortingTime.java) reverse Reverses all the elements in a Collection See CollectionSorting1.java shuffle

Random shuffling of the elements of a Collection (very good in card simulations) See ShuffleExample.java or (Card.java, DeckOfCards.java and CardShuffleTester.java fill Sets every element in the Collection to refer to the given argument (see AlgorithmsForCollections.java) copy Copies the references from one Collection into another List. The destination List must be at least as long as the source List; otherwise, an IndexOutOfBoundsException occurs. (see AlgorithmsForCollections.java) min Returns the smallest element in a Collection, based on the elements comparator (i.e must implement the Comparable interface)

max Returns the largest element in a Collection, based on the elements comparator (see AlgorithmsForCollections.java) binarySearch Locate an item in a sorted Collection using binary search See BinarySearchTest.java addAll Appends all the elements in an array to a Collection. See AlgorithmsForMoreCollectionMethods.java frequency Calculates how many Collection elements are equal to the specified element. See AlgorithmsForMoreCollectionMethods.java disjoint

Returns true if two Collections have no elements in common otherwise false. See AlgorithmsForMoreCollectionMethods.java 22 Type Parameter Naming Conventions The following discussion is useful for reading Oracle documentation on Generic Types By convention, type parameter names are single, uppercase letters. This stands in sharp contrast to the variable naming conventions that you already know about, and with good reason: Without this convention, it would be difficult to tell the difference between a type variable and an ordinary class or interface name. The most commonly used type parameter names are: E - Element (used extensively by the Java Collections Framework)

K - Key N - Number T - Type V - Value S,U,V etc. - 2nd, 3rd, 4th types 23 The asList Method For Arrays The asList() method of java.util.Arrays class is used to return a fixed-size list backed by the specified array. This method acts as bridge between array-based and collection- based APIs, in combination with Collection.toArray(). The returned list is serializable and implements RandomAccess. Changes to the returned list "write through" to the array. toArray is a method of the Collection interface that converts the elements of any lCollection into a fixed sized array.

This method also provides a convenient way to create a fixedsize list initialized to contain several elements: List stooges = Arrays.asList("Larry", "Moe", "Curly"); See AsListDemo1.java 24 The sort Method Method sort sorts the elements of a List The elements must implement the Comparable interface. The order is determined by the natural order of the elements type as implemented by a compareTo method. Method compareTo is declared in interface Comparable and is sometimes called the natural comparison method. The sort call may specify as a second argument a Comparator object that determines an alternative ordering of the elements. Note: in several of the programs we use the Arrays method

asList, which allows you to view an array as a List Collection. This List view allows you to manipulate the array as if it were a List. Useful for adding elements in the array to a List, and for sorting. 25 Using Comparator in Sorting The custom Comparator class, named TimeComparator, that implements interface Comparator to compare two Time objects. Class Time represents times with hours, minutes and seconds. Class TimeComparator implements interface Comparator, a generic type that takes one type argument.

A class that implements Comparator must declare a compare method that receives two arguments and returns a negative integer if the first argument is less than the second, 0 if the arguments are equal or a positive integer if the first argument is greater than the second. See Time.java, TimeComparator.java and SortingTime.java 26 Using the binarySearch Method static Collections method binarySearch locates an object in a List. If the object is found, its index is returned. If the object is not found, binarySearch returns a negative value.

Method binarySearch determines this negative value by first calculating the insertion point and making its sign negative. Then, binarySearch subtracts 1 from the insertion point to obtain the return value, which guarantees that method binarySearch returns positive numbers (>= 0) if and only if the object is found. Binary search can only be used after sorting the list 27

Recently Viewed Presentations

  • Origin of Oxygen Species in Titan&#x27;s Atmosphere

    Origin of Oxygen Species in Titan's Atmosphere

    Origin of Oxygen Species in Titan's Atmosphere Sarah M. Hörst, Véronqiue Vuitton, Roger V. Yelle ... (volcanic outgassing, ocean source) (Lara et al. 1996, Baines et al. 2006) ... Origin of Oxygen Species in Titan's Atmosphere Sarah M. Hörst, Véronqiue...
  • Introduction to Language: Animals and Human Language ...

    Introduction to Language: Animals and Human Language ...

    Necessity Hypotheses "yo-he-ho" Hypothesis: Language developed on the basis of human cooperation. The earliest language was . chanting. to stimulate collective effort, like moving a great stone to block off a cave entrance from roving carnivores, or repeatinga war phrase...
  • Teen sexuality &amp; abstinence vs sexual activity

    Teen sexuality & abstinence vs sexual activity

    Teen sexuality&abstinence vs sexual activity. 1.02 Understanding teen sexuality, teen pregnancy, and responsible decisions about abstinence versus sexual activity. What is sexuality . Refers to a person's view of himself or herself as a male or female. Sexuality includes how...
  • Justice, Democracy and Constitutionalism: Indonesia&#x27;S Experiences

    Justice, Democracy and Constitutionalism: Indonesia'S Experiences

    JUSTICE, DEMOCRACY AND CONSTITUTIONALISM: INDONESIA'S EXPERIENCES. ... the government of Indonesia is still reluctant to acknowledge the facts and the crimes that were committed. International People Tribunal 1965, The Hague, 10-13 Nov 2015 ... Hotel Indonesia traffic circle, Central Jakarta...
  • &quot;DC-3 NextGen&quot;

    "DC-3 NextGen"

    Isometric Views Carpet Plot Design Details W/S = 100 T/W = 0.3 AR=8 L = 75,000 lb Wing t/c = 0.1 (CL)max = 5 C-5A Airfoil Cross-sections (CL)max = 3.8 Triple Slotted Krueger Internally Blown Flaps Slats Cruise CL =...
  • Agriculture Labor Program

    Agriculture Labor Program

    Next, determine whether the worker meets the criteria of being employed in farm work through either working in farm work for 50% of their time in the past year, or through earning 50% of their income in the past year....
  •  Fire Chief Gregory Fish  Deputy Fire Chief A

    Fire Chief Gregory Fish Deputy Fire Chief A

    Event 4: ROOF WALK Description: Candidate ascends and descends a 12-foot distance walking/crawling on the rungs of a 12-foot roof ladder while carrying a simulated 20-pound chain saw. The candidate must hit every rung while ascending the ladder. Candidate will...
  • Sparse LU Factorization - UCSB

    Sparse LU Factorization - UCSB

    Positive matrix elements - diagonally dominant SPSD and matroid analysis ... The Laplacian matrix of G is symmetric, singular, and positive semidefinite. The multiplicity of 0 as an eigenvalue is equal to the number of connected components of G. A...