2015-04-02_sets.md

Objectives

To learn about Set:

• What is a Set, i.e. how it differs from say List.
• How to add and remove values.
• How to use keySet.

IntelliJ settings

• Presentation
• settings.jar

Sets

Definition: A set is a collection that contains no duplicate elements.

What's an example of a set? An alphabet is a set:

a b c d e f g ...

Or here is some Hiragana:

あ い う え お

Set vs List

How is a set different from a list?

	List	Set
Unique	No	Yes
Ordered	Yes	Depends
Indexable	Yes	No

Java's Set

There are a few ways to make a set in Java. Today, we'll be using HashSet (documentation). With HashSet, order is not guaranteed.

You import it like this:

import java.util.HashSet;

Today, let's start with an empty HashSet. Call it odd.

HashSet<Integer> odd = new HashSet<Integer>();

add

You add objects to a set using add:

odd.add(1);
odd.add(3);
odd.add(57);

Exercise: Your odd set is empty. Add some odd numbers!

for each

You can iterate over a set using a for each loop:

for (Integer num : odds) {
}

Exercise: Create a new HashSet called even with only even numbers. Use a for each loop to add all the numbers in odd to even.

remove

You remove an object by calling remove:

odd.remove(3);

Exercise: Undo what you just did: remove all the odd numbers from even.

addAll, removeAll

These are two useful methods. They add every element from one set into another, retaining uniqueness. Here's addAll:

// odd = [1,3,5]
// even = [2,4,6]
odd.addAll(even); // [1,2,3,4,6,7]

Here's removeAll:

// nums1 = [1,3,5]
// nums2 = [1,2,4]
nums1.removeAll(nums2); // [2,4]

Exercise: Redo the previous exercises, this time using addAll and removeAll.

contains, size, isEmpty

Sets also have our standard methods: contains, size, and isEmpty.

odd.contains(1); // true

Cloning a set

An easy way to clone a set is to just pass the set you want to copy into the constructor:

HashSet<Integer> odd2 = new HashSet<Integer>(odd);
HashSet<Integer> odd3 = new HashSet<Integer>(odd);
System.out.println(odd2 == odd2);
System.out.println(odd2 == odd3);
System.out.println(odd2.equals(odd3));

keySet

We've actually already used a set before, when iterating over the values in a HashMap. Let's look at that again:

import java.util.HashMap;
fruitCount.put("bananas", 3);
fruitCount.put("apples", 99);
for (String fruit : fruitCount.keySet()) {
    System.out.println(fruit);
}

In the above code, keySet() is return a set of String objects. We are looping over that set.

In-class exercises: analyze our social network

Please work through these exercises using this stencil file. Complete as many as you can in class.

1. Implement allFriends: A union of two sets is the set of all things that are members of either. Here is a visual:

allFriends friends should return a new set that contains all the friends in yours and all the friends in mine.

1. Implement mutualFriends: An intersection is the set of all things that are members of both sets.

   

mutualFriends friends should return a new set that contains just the friends that are in both yours and mine.

1. Implement justYourFriends: A complement is the set of all elements that are members of one set but not another.

justYourFriends friends should return a new set that contains just the friends that are in both yours. If any friends in mine are also in yours, do not add them to the set returned.

1. Implement justMyFriends: This is just like justYourFriends but returns only the friends in mine rather than yours. Can you think of an easy way to do this?

2. Implement exclusiveFriends: The symmetric difference is the set of things which are in either of two sets but not in their intersection.

1. Implement yourFriendsAreMine: A set is a subset of another if every thing in the first set is also in the second. Here, A is a subset of B:

yourFriendsAreMine should return true only if all the friends in yours are also in mine. mine can have friends that are not in yours.

1. (Bonus) Implement matchmaker: Calculate all possible matches between your friends and return a HashSet of HashSet of String objects.