std.set

func int_set() -> &IntSet {
  return new IntSet { entries: int_map() };
}

func int_set_with_capacity(capacity: i32) -> &IntSet {
  return new IntSet { entries: int_map_with_capacity(capacity) };
}

func int_set_from(values: &I32Values) -> &IntSet {
  let out: &IntSet = int_set_with_capacity(#values);
  for i in 0..#values {
    out.add(values[i]);
  }
  return out;
}

func bit_set(capacity: i32) -> &BitSet {
  let n: i32 = capacity < 0 ? 0 : capacity;
  // Round up to whole 32-bit words.
  return new BitSet { words: new I32Values[(n + 31) / 32]{}, capacity: n };
}

func IntSet.len(self: &IntSet) -> i32 {
  return self->entries.len();
}

func IntSet.is_empty(self: &IntSet) -> i32 {
  return self->entries.len() == 0;
}

func IntSet.add(self: &IntSet, value: i32) -> i32 {
  if (self->entries.contains(value)) { return 0; }
  self->entries.put(value, 1);
  return 1;
}

func IntSet.contains(self: &IntSet, value: i32) -> i32 {
  return self->entries.contains(value);
}

func IntSet.remove(self: &IntSet, value: i32) -> i32 {
  return self->entries.remove(value);
}

func IntSet.clear(self: &IntSet) {
  self->entries.clear();
}

func IntSet.to_list(self: &IntSet) -> &IntList {
  return self->entries.keys();
}

func IntSet.union(self: &IntSet, other: &IntSet) -> &IntSet {
  let out: &IntSet = int_set_with_capacity(self.len() + other.len());
  let mine: &IntList = self.to_list();
  for i in 0..mine.len() {
    out.add(mine.at(i));
  }
  let theirs: &IntList = other.to_list();
  for i in 0..theirs.len() {
    out.add(theirs.at(i));
  }
  return out;
}

func IntSet.intersect(self: &IntSet, other: &IntSet) -> &IntSet {
  let out: &IntSet = int_set();
  let smaller: &IntSet = self.len() <= other.len() ? self : other;
  let larger: &IntSet = self.len() <= other.len() ? other : self;
  let members: &IntList = smaller.to_list();
  for i in 0..members.len() {
    let value: i32 = members.at(i);
    if (larger.contains(value)) { out.add(value); }
  }
  return out;
}

func IntSet.difference(self: &IntSet, other: &IntSet) -> &IntSet {
  let out: &IntSet = int_set();
  let members: &IntList = self.to_list();
  for i in 0..members.len() {
    let value: i32 = members.at(i);
    if (other.contains(value) == 0) { out.add(value); }
  }
  return out;
}

func IntSet.is_subset(self: &IntSet, other: &IntSet) -> i32 {
  let members: &IntList = self.to_list();
  for i in 0..members.len() {
    if (other.contains(members.at(i)) == 0) { return 0; }
  }
  return 1;
}

func BitSet.capacity(self: &BitSet) -> i32 {
  return self->capacity;
}

func BitSet.add(self: &BitSet, value: i32) -> i32 {
  if (value < 0 || value >= self->capacity) { return 0; }
  let word: i32 = value >>> 5;
  let bit: i32 = 1 << (value & 31);
  if ((self->words[word] & bit) != 0) { return 0; }
  self->words[word] = self->words[word] | bit;
  return 1;
}

func BitSet.contains(self: &BitSet, value: i32) -> i32 {
  if (value < 0 || value >= self->capacity) { return 0; }
  return (self->words[value >>> 5] >>> (value & 31)) & 1;
}

func BitSet.remove(self: &BitSet, value: i32) -> i32 {
  if (value < 0 || value >= self->capacity) { return 0; }
  let word: i32 = value >>> 5;
  let bit: i32 = 1 << (value & 31);
  if ((self->words[word] & bit) == 0) { return 0; }
  self->words[word] = self->words[word] & ~bit;
  return 1;
}

func BitSet.toggle(self: &BitSet, value: i32) -> i32 {
  if (value < 0 || value >= self->capacity) { return 0; }
  let word: i32 = value >>> 5;
  let bit: i32 = 1 << (value & 31);
  self->words[word] = self->words[word] ^ bit;
  return (self->words[word] & bit) != 0;
}

func BitSet.len(self: &BitSet) -> i32 {
  var total: i32 = 0;
  for i in 0..#self->words {
    total = total + self->words[i].popcnt();
  }
  return total;
}

func BitSet.is_empty(self: &BitSet) -> i32 {
  for i in 0..#self->words {
    if (self->words[i] != 0) { return 0; }
  }
  return 1;
}

func BitSet.clear(self: &BitSet) {
  self->words.fill(0, 0, #self->words);
}

func BitSet.fill_all(self: &BitSet) {
  self->words.fill(0, -1, #self->words);
  let extra: i32 = #self->words * 32 - self->capacity;
  if (extra > 0) {
    self->words[#self->words - 1] = self->words[#self->words - 1] & (-1 >>> extra);
  }
}

func BitSet.next(self: &BitSet, from: i32) -> i32 {
  var at: i32 = from < 0 ? 0 : from;
  if (at >= self->capacity) { return -1; }
  var word: i32 = at >>> 5;
  // Mask off the bits below `at` in the first word, so the scan starts exactly at `from`.
  var bits: i32 = self->words[word] & (-1 << (at & 31));
  loop scan() {
    if (bits != 0) {
      let found: i32 = word * 32 + bits.ctz();
      return found < self->capacity ? found : -1;
    }
    word = word + 1;
    if (word >= #self->words) { break scan(); }
    bits = self->words[word];
    continue scan();
  }
  return -1;
}

func BitSet.to_array(self: &BitSet) -> &I32Values {
  let out: &I32Values = new I32Values[self.len()]{};
  var index: i32 = 0;
  var value: i32 = self.next(0);
  loop collect() {
    if (value < 0) { break collect(); }
    out[index] = value;
    index = index + 1;
    value = self.next(value + 1);
    continue collect();
  }
  return out;
}

func BitSet.union_with(self: &BitSet, other: &BitSet) {
  let n: i32 = #self->words < #other->words ? #self->words : #other->words;
  for i in 0..n {
    self->words[i] = self->words[i] | other->words[i];
  }
  self.trim();
}

func BitSet.intersect_with(self: &BitSet, other: &BitSet) {
  for i in 0..#self->words {
    let mask: i32 = i < #other->words ? other->words[i] : 0;
    self->words[i] = self->words[i] & mask;
  }
}

func BitSet.subtract(self: &BitSet, other: &BitSet) {
  let n: i32 = #self->words < #other->words ? #self->words : #other->words;
  for i in 0..n {
    self->words[i] = self->words[i] & ~other->words[i];
  }
}

func BitSet.trim(self: &BitSet) {
  if (#self->words == 0) { return; }
  let extra: i32 = #self->words * 32 - self->capacity;
  if (extra > 0) {
    self->words[#self->words - 1] = self->words[#self->words - 1] & (-1 >>> extra);
  }
}

struct IntSet {
  entries: mut &IntMap,
}

struct BitSet {
  words: mut &I32Values,
  /// The exclusive upper bound on membership. Kept separately because the word array
  /// rounds up to a multiple of 32 and the padding bits must never be reported as members.
  capacity: mut i32,
}