// Week 6 – Java's built-in sets: HashSet and TreeSet
// Run: java BuiltinSets.java
import java.util.HashSet;
import java.util.Set;
import java.util.TreeSet;

public class BuiltinSets {
    public static void main(String[] args) {
        // HashSet: based on a hash table (week 11) – O(1) operations on average, no order
        Set<String> a = new HashSet<>(Set.of("Wuhan", "Beijing", "Eger", "Shanghai"));
        Set<String> b = new HashSet<>(Set.of("Eger", "Budapest", "Wuhan"));

        Set<String> union = new HashSet<>(a);
        union.addAll(b);
        Set<String> inter = new HashSet<>(a);
        inter.retainAll(b);
        Set<String> diff = new HashSet<>(a);
        diff.removeAll(b);
        System.out.println("A ∪ B = " + union);
        System.out.println("A ∩ B = " + inter);
        System.out.println("A \\ B = " + diff);
        System.out.println("contains(\"Eger\") = " + a.contains("Eger") + ", add(\"Eger\") = " + a.add("Eger") + " (it was already in)");

        // TreeSet: based on a balanced search tree (week 15) – O(log n), SORTED order
        TreeSet<Integer> t = new TreeSet<>(Set.of(42, 7, 19, 3, 25));
        System.out.println("\nTreeSet: " + t + ", first = " + t.first() + ", last = " + t.last());
        System.out.println("smallest greater than 19: " + t.higher(19) + ", below 20: " + t.headSet(20));

        // A common application: filtering out duplicates
        int[] nums = { 3, 1, 3, 2, 1, 3 };
        Set<Integer> distinct = new TreeSet<>();
        for (int x : nums) distinct.add(x);
        System.out.println("distinct elements: " + distinct);
    }
}