// 第 6 周 – Java 内置的集合：HashSet 和 TreeSet
// 运行：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：基于哈希表（第 11 周）– 操作平均 O(1)，没有顺序
        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：基于平衡二叉搜索树（第 15 周）– O(log n)，有序
        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));

        // 常见应用：过滤重复元素
        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);
    }
}