1 of 51

Prof. Christopher Rasmussen

​

Spring, 2019

CISC 181

Generics & Collections

2 of 51

Generic methods

  • Nearly identical methods, differing only in types of inputs/outputs, may be combined into generic version

3 of 51

Generic methods

  • Nearly identical methods, differing only in types of inputs/outputs, may be combined into generic version

4 of 51

Generic methods

  • Generic version of method declares special type parameter that is a kind of wildcard

​

public static <T>

T tripleMinValue(T item1, T item2, T item3) {

// . . .

}

​

​

5 of 51

Generic methods

  • Generic version of method declares special type parameter that is a kind of wildcard

​

public static <T>

T tripleMinValue(T item1, T item2, T item3) {

// . . .

}

​

  • The generic type T must be a reference type

6 of 51

Generic methods

  • More than one generic type may be declared:

​

public static <T1, T2>

T1 foo(T1 item1, T2 item2) {

// . . .

}

​

7 of 51

Generic methods

  • A generic type T may also have a type bound, or specification of what class types are valid for T

​

​

8 of 51

Generic methods

  • A generic type T may also have a type bound, or specification of what class types are valid for T
    • Must do this to get compareTo()

​

public static <T extends Comparable<T>>

T tripleMinValue(T item1, T item2, T item3) {

if (item1.compareTo(item2) <= 0) {

...

}

}

​

​

9 of 51

Generic classes: Motivation

  • Consider multiple classes (or interfaces) that differ only in the types of the data they contain:

class TwoIntegers {

Integer I1, I2;

TwoIntegers(Integer I1, Integer I2)

{ this.I1 = I1; this.I2 = I2; }

}

class TwoStrings {

String S1, S2;

TwoStrings(String S1, String S2)

{ this.S1 = S1; this.S2 = S2; }

}

10 of 51

Generic classes: Motivation

  • Like generic methods, we can combine such classes into one generic class

​

11 of 51

Generic classes: Motivation

  • Like generic methods, we can combine such classes into one generic class
  • This is how we want it to look:

​

​

class TwoVars {

AnyType V1, V2;

TwoVars(AnyType V1, AnyType V2)

{ this.V1 = V1; this.V2 = V2; }

}

12 of 51

Generic classes: Defining

  • But first we have to declare that AnyType is a generic type in this class definition:

​

​

class TwoVars <AnyType> {

AnyType V1, V2;

TwoVars(AnyType V1, AnyType V2)

{ this.V1 = V1; this.V2 = V2; }

}

13 of 51

Generic classes: Defining

  • Remember, you can use any name for the type that you want, but...

​

​

class TwoVars <Var> {

Var V1, V2;

TwoVars(Var V1, Var V2)

{ this.V1 = V1; this.V2 = V2; }

}

14 of 51

Generic classes: Defining

  • Remember, you can use any name for the type that you want, but...capitalized single letters are the convention

​

​

class TwoVars <T> {

T V1, V2;

TwoVars(T V1, T V2)

{ this.V1 = V1; this.V2 = V2; }

}

15 of 51

Generic classes: Defining

  • As with generic methods, multiple type parameters and type bounds are also ok:

​

​

class KeyValue <K, V> {

K key;

V value;

KeyValue(K key, V value) {

this.key = key;

this.value = value;

}

}

16 of 51

Generic classes: Defining

  • As with generic methods, multiple type parameters and type bounds are also ok:

​

​

class TwoComps <T extends JComponent> {

T C1, C2;

TwoComps(T C1, T C2)

{ this.C1 = C1; this.C2 = C2; }

}

17 of 51

Using generic classes

  • In order to instantiate an object of the generic class type, you have to pick a specific type
  • This is done when declaring and instantiating

​

18 of 51

Using generic classes

  • In order to instantiate an object of the generic class type, you have to pick a specific type
  • This is done when declaring and instantiating
  • For example:

TwoVars<Integer> pairOfIntegers;

// this is the old way

pairOfIntegers = new TwoVars<Integer>(3, 5);

19 of 51

Using generic classes

  • In order to instantiate an object of the generic class type, you have to pick a specific type
  • This is done when declaring and instantiating
  • For example:

TwoVars<Integer> pairOfIntegers;

// but this is also ok now

pairOfIntegers = new TwoVars<>(3, 5);

20 of 51

Using generic classes

  • In order to instantiate an object of the generic class type, you have to pick a specific type
  • This is done when declaring and instantiating
  • For example:

TwoVars<Integer> pairOfIntegers;

// but this is also ok now

pairOfIntegers = new TwoVars<>(3, 5);

  • Instantiate a KeyValue object

21 of 51

Examples of generic classes/interfaces

  • Comparable<T>, Comparator<T>
  • ArrayList<T>

​

22 of 51

Examples of generic classes/interfaces

  • Comparable<T>, Comparator<T>
  • ArrayList<T>
  • and the rest of the Collection classes / interfaces, plus the Map hierarchy...

23 of 51

Java Collections vs. Collection

  • Collections: Class containing static methods/algorithms (like sort()) for manipulating Collection objects

​

24 of 51

Java Collections vs. Collection

  • Collections: Class containing static methods/algorithms (like sort()) for manipulating Collection objects
  • Collection: Root interface in hierarchy of data structures like ArrayList
    • Properties like ordered or unordered, duplicate elements allowed or not, types of access

​

25 of 51

Java Collections vs. Collection

  • Collections: Class containing static methods/algorithms (like sort()) for manipulating Collection objects
  • Collection: Root interface in hierarchy of data structures like ArrayList
    • Properties like ordered or unordered, duplicate elements allowed or not, types of access

Queue/Deque

26 of 51

Collection examples

  • List: Ordered collection, duplicates allowed, can insert and remove at arbitrary locations
    • ArrayList is one implementation (LinkedList is other)

​

27 of 51

Collection examples

  • List: Ordered collection, duplicates allowed, can insert and remove at arbitrary locations
    • ArrayList is one implementation (LinkedList is other)
  • Queue/Deque: Like a list, but typically insertion/deletion constrained to "ends" of sequence

28 of 51

Collection examples

  • List: Ordered collection, duplicates allowed, can insert and remove at arbitrary locations
    • ArrayList is one implementation (LinkedList is other)
  • Queue/Deque: Like a list, but typically insertion/deletion constrained to "ends" of sequence
  • Set: No duplicate elements, may or may not be ordered

​

29 of 51

Useful Collections methods, part I

​

  • sort(List<T> L)
    • Also comes in sort(L, Comparator<T>)

30 of 51

Useful Collections methods, part I

​

  • sort(List<T> L)
    • Also comes in sort(L, Comparator<T>)
  • T min(L), T max(L): Extreme value elements

​

31 of 51

Useful Collections methods, part I

​

  • sort(List<T> L)
    • Also comes in sort(L, Comparator<T>)
  • T min(L), T max(L): Extreme value elements
  • int frequency(Collection<T> C, T e): Number of occurrences of element e

​

32 of 51

Useful Collections methods, part I

​

  • sort(List<T> L)
    • Also comes in sort(L, Comparator<T>)
  • T min(L), T max(L): Extreme value elements
  • int frequency(Collection<T> C, T e): Number of occurrences of element e
  • swap(L, int i, int j)
    • Switch locations of elements at indices i and j

33 of 51

Useful Collections methods, part II

​

  • reverse(L): Make first element last and last first, etc.

​

34 of 51

Useful Collections methods, part II

​

  • reverse(L): Make first element last and last first, etc.
  • shuffle(L): Randomize list order
    • Card deck example

​

35 of 51

Useful Collections methods, part II

​

  • reverse(L): Make first element last and last first, etc.
  • shuffle(L): Randomize list order
    • Card deck example
  • rotate(L, int distance)
    • Move element at index i → i + distance, mod list size (to "wrap")
    • i can be negative to change "direction"

36 of 51

Set (Collection interface)

  • Set is actually an interface that extends the Collection interface
    • Collection specifies methods such as:
      • add(E e), clear()
      • boolean isEmpty(), int size()
      • toArray()

​

37 of 51

Set (Collection interface)

  • Set is actually an interface that extends the Collection interface
    • Collection specifies methods such as:
      • add(E e), clear()
      • boolean isEmpty(), int size()
      • toArray()
    • You may recognize these because ArrayList had to define them in order to implement the interface!

​

38 of 51

Set (Collection interface)

  • Set is actually an interface that extends the Collection interface
    • Collection specifies methods such as:
      • add(E e), clear()
      • boolean isEmpty(), int size()
      • toArray()
    • You may recognize these because ArrayList had to define them in order to implement the interface!
  • Set doesn't actually add any methods...it just requires that the collection contains NO DUPLICATE ELEMENTS

39 of 51

Iterators

  • An important Collection method is called iterator()
    • It returns an object which implements the interface Iterator

​

40 of 51

Iterators

  • An important Collection method is called iterator()
    • It returns an object which implements the interface Iterator
  • The Iterator interface allows you to iterate through, or "visit" one by one, the elements of the collection

41 of 51

Iterators

  • An important Collection method is called iterator()
    • It returns an object which implements the interface Iterator
  • The Iterator interface allows you to iterate through, or "visit" one by one, the elements of the collection
  • Required methods:
    • boolean hasNext(): True if there are more elements to be visited
    • E next(): Returns next element to be visited

​

42 of 51

Iterators

  • An important Collection method is called iterator()
    • It returns an object which implements the interface Iterator
  • The Iterator interface allows you to iterate through, or "visit" one by one, the elements of the collection
  • Required methods:
    • boolean hasNext(): True if there are more elements to be visited
    • E next(): Returns next element to be visited

​

look familiar? that's because the Scanner class implements Iterator!!

43 of 51

Iterators

  • This gives us another way to "loop" over a Collection:

​

// myArrList elements are of type E

Iterator<E> iter = myArrList.iterator();

while (iter.hasNext()) {

E curElem = iter.next();

// do something with curElem

}

44 of 51

Set (Collection interface)

  • Requiring "no duplicates" means that in practice, calling add(E e) does nothing if element e is already in the set

​

45 of 51

Set (Collection interface)

  • Requiring "no duplicates" means that in practice, calling add(E e) does nothing if element e is already in the set
  • The Set inferface is implemented by two classes:
    • HashSet: No guarantee about iteration order; add() and remove() are always FAST
    • TreeSet: Elements ordered; add() and remove() get SLOWER as size grows

46 of 51

Set (Collection interface)

  • Requiring "no duplicates" means that in practice, calling add(E e) does nothing if element e is already in the set
  • The Set inferface is implemented by two classes:
    • HashSet: No guarantee about iteration order; add() and remove() are always FAST
    • TreeSet: Elements ordered; add() and remove() get SLOWER as size grows

Can call constructor with Comparator object to specify custom sorting criterion

47 of 51

Set operations

  • Member e ∊ S1?
    • S1.contains(e)
  • Subset S2 ⊂ S1?
    • S1.containsAll(S2)
  • Union S1 ∪ S2
    • S1.addAll(S2)
  • Intersection S1 ∩ S2
    • S1.retainAll(S2)
  • Difference S1 - S2
    • S1.removeAll(S2)

48 of 51

Set operations

  • Member e ∊ S1?
    • S1.contains(e)
  • Subset S2 ⊂ S1?
    • S1.containsAll(S2)
  • Union S1 ∪ S2
    • S1.addAll(S2)
  • Intersection S1 ∩ S2
    • S1.retainAll(S2)
  • Difference S1 - S2
    • S1.removeAll(S2)

49 of 51

Exercise (codestepbystep.com)

  • With this week's partner!
  • collections/Set
    • numUniqueValues
    • maxLength

​

50 of 51

Exercise (codestepbystep.com)

  • With this week's partner!
  • collections/Set
    • numUniqueValues
    • maxLength
  • For lab #4:
    • How could we use Set to write isFourOfAKind() method in Hand class?

​

​

51 of 51

Exercise (codestepbystep.com)

  • With this week's partner!
  • collections/Set
    • numUniqueValues
    • maxLength
  • For lab #4:
    • How could we use Set to write isFourOfAKind() method in Hand class?
    • How could we use Set to write isFlush()?

​