Set #

The abstract data type set simulates a (usually finite) mathematical set.

A set may expose the following methods:

add: adds an element to the set if it was not present already (and returns true iff this was the case),
contains: checks whether an element belongs to the set,
size: returns the cardinality of the set,
etc.

Warning. A set provides no guarantee on the order of its elements!

in Java #

Java provides an interface Set with 8 native implementations (i.e. different classes that implement this interface). The most commonly used are HashSet and TreeSet.

The interface Set extends the interface Collection.

Syntax #

Here are code snippets for a few simple operations specified in the interface Set.

Create a Set and populate it:

City milan = new City("Milan", 20100);
City florence = new City("Florence", 50100);

// Creates an empty set of cities
Set<City> mySet = new HashSet<>();

// Adds Milan to the set
mySet.add(milan);
// Adds Florence to the set
mySet.add(florence);
// Tries to add Milan again; this has no effect.
mySet.add(milan);

// Creates a set identical to the previous one,
// but which cannot be modified
Set<City> myOtherSet = Set.of(milan, florence);

Remove an element from a set:

mySet.remove(milan);

Check whether a set contains an certain element:

// Outputs false
System.out.println(mySet.contains(milan));

// Outputs true
System.out.println(mySet.contains(florence));

Retrieve the cardinality of a set:

// Outputs 1
System.out.println(mySet.size());

Compute the intersection of two sets:

mySet.add(new City("Bologna", 40100));
mySet.retainAll(myOtherSet);

// Outputs 1
System.out.println(mySet.size());

Add a collection to a set:

mySet.addAll(myOtherSet);

// Outputs 2
System.out.println(mySet.size());

For more operations, consult the Javadoc of the interface Set.

Duplicates #

By definition, a set cannot contain identical elements. But what does “identical” mean for two objects?

In Java, the method equals is (implicitly) used to determine whether two elements added to a Set should be considered identical.

Warning. Recall that the method equals should be overridden together with the method hashCode (more on this later). This is essential for a HashSet to behave as expected (more on this later).

For instance, consider a naive implementation of the class City, which does not override equals (or hashCode):

public class City {

    String name;
    int zipcode;

    public City(String name, int zipCode){
        this.name = name;
        this.zipCode =zipCode;
    }
}

Recall that every class inherits a default implementation of equals (and hashCode), from the class Object. According to this default implementation, equals behaves like ==.

City trento = new City("Trento", 38100);
City trentoAgain = new City("Trento", 38100);

Set<City> cities = Set.of(trento, trentoAgain);

// Outputs 2
System.out.println(cities.size());

Now consider a class SmartCity identical to City, but that overrides equals (andhashCode) in the standard way:

public class SmartCity {
  String name;
  int zipCode;

  public SmartCity(String name, int zipCode) {
    this.name = name;
    this.zipCode = zipCode;
  }

  @Override
  public boolean equals(Object o) {
    if (this == o) return true;
    if (o == null || getClass() != o.getClass()) return false;
    SmartCity smartCity = (SmartCity) o;
    return zipCode == smartCity.zipCode && name.equals(smartCity.name);
  }

  @Override
  public int hashCode() {
    return Objects.hash(name, zipCode);
  }
}

A Java Set cannot contain two instances of SmartCity that have the same name and zip code:

SmartCity smartTrento = new SmartCity("Trento", 38100);
SmartCity smartTrentoAgain = new SmartCity("Trento", 38100);

Set<SmartCity> smartCities = new HashSet<>();
smartCities.add(smartTrento);
smartCities.add(smartTrentoAgain);

// Outputs 1
System.out.println(smartCities.size());

// Outputs false
System.out.println(smartCities.add(smartTrentoAgain));

Note. Recall that many native Java classes already override equals (and hashCode). Among others: String, boxed types (like Integer), but also most implementations of the Collection interface (including HashSet).

Note. Some implementations of List also provide methods that perform “set-like” comparisons. E.g. containsAll, removeAll, retainAll, etc. Again, we refer to the Javadoc for an exhaustive documentation.

Usage #

Implementations of the ADT set can be useful in a variety of contexts. For instance, remove duplicates from an array (assuming that the order of elements in the array is irrelevant):

Integer[] myArray = new Integer[]{1,2,3,1,2};
List<Integer> tuple = List.of(myArray);
Set<Integer> set = new HashSet<>(tuple);

// Outputs 3
System.out.println(set.size());

Or check whether two lists contain the same (distinct) elements:

SmartCity mantova = new SmartCity("Mantua", 46100);
SmartCity bergamo = new SmartCity("Bergamo", 24100);
List<SmartCity> list1 = List.of(mantova, bergamo);
List<SmartCity> list2 = List.of(bergamo, mantova);

Set<SmartCity> set1 = new HashSet<>(list1);
Set<SmartCity> set2 = new HashSet<>(list2);

// Outputs true
System.out.println(set1.equals(set2));

Exercise

In our game, a same unit may sit on two (or more) adjacent tiles.

Consider an implementation where:

a board consists of a two-dimensional array with type Unit[][], and
if a same unit sits on several tiles, then these tiles contain (a reference to) the same (instance of) Unit, and
Unit does not override equals (neither do its sub or superclasses).

Write a Java method int countUnits(Unit[][] board) that takes such an array as input, and returns the number of different units on the board.

For instance, with the board below as input, the method should return 5.

Possible solution

int countUnits(Unit[][] board) {

    Set<Unit> units = new HashSet<>();

    for (Unit[] row : board) {
        for (Unit unit : row) {
            if (unit != null) {
                  units.add(unit);
            }
        }
    }
    return units.size();
}

Exercise

What does the following program print?

Set<Integer> aSet = new HashSet<>();
Set<Integer> anotherSet = new HashSet<>();
aSet.add(1);
aSet.add(2);
anotherSet.add(1);

Set<Set<Integer>> aFamily = new HashSet<>();
aFamily.add(aSet);
aFamily.add(anotherSet);

System.out.println(aFamily.size());

anotherSet.add(2);
System.out.println(aFamily.size());

Solution

2 and 2.