Set Operations and Algorithms

import scala.collection.mutable

@main def run(): Unit =
  val setA = Set(1, 2, 3, 4, 5)
  val setB = Set(4, 5, 6, 7, 8)

  // Basic operations
  println(s"Union: ${setA | setB}")         // or setA.union(setB)
  println(s"Intersect: ${setA & setB}")      // or setA.intersect(setB)
  println(s"Diff A-B: ${setA &~ setB}")      // or setA.diff(setB)
  println(s"Diff B-A: ${setB &~ setA}")
  println(s"Symmetric diff: ${(setA | setB) &~ (setA & setB)}")

  // Membership
  println(s"Contains 3: ${setA.contains(3)}")
  println(s"Contains 9: ${setA(9)}")  // apply = contains

  // Subset/superset
  println(s"Set(1,2) ⊂ setA: ${Set(1, 2).subsetOf(setA)}")

  // Add/remove (immutable)
  val extended = setA + 6 + 7
  val reduced = setA - 1 - 2
  println(s"Extended: $extended")
  println(s"Reduced: $reduced")

  // Practical: find duplicates
  val items = List("a", "b", "c", "a", "d", "b", "e", "a")
  val seen = mutable.Set.empty[String]
  val duplicates = items.filter(!seen.add(_))
  println(s"Duplicates: $duplicates")

  // Find unique elements
  println(s"Unique: ${items.toSet}")

  // Set of sets: power set (small sets only!)
  def powerSet[A](s: Set[A]): Set[Set[A]] =
    if s.isEmpty then Set(Set.empty)
    else
      val head = s.head
      val rest = powerSet(s.tail)
      rest ++ rest.map(_ + head)

  println(s"Power set of {{1,2,3}}: ${powerSet(Set(1, 2, 3))}")

  // Permissions example
  val userPerms = Set("read", "write", "delete")
  val requiredPerms = Set("read", "write")
  val hasAccess = requiredPerms.subsetOf(userPerms)
  val missingPerms = requiredPerms &~ userPerms
  println(s"Has access: $hasAccess")
  println(s"Missing: $missingPerms")

  // Tags intersection
  val post1Tags = Set("scala", "fp", "jvm")
  val post2Tags = Set("scala", "akka", "jvm", "actors")
  val commonTags = post1Tags & post2Tags
  println(s"Common tags: $commonTags")

  // SortedSet
  val sorted = scala.collection.immutable.SortedSet(5, 3, 1, 4, 2)
  println(s"Sorted: $sorted")
  println(s"Range: ${sorted.range(2, 5)}")