HAXY

▄▀▀▀ ▄ ▄▀▀▀▀▀▀▄ ▀▀▀▀▀▄ ▀▀▀▀▀▀▀▀▀▀ ▄▀▀▀▀▀▀▀ ▀▀▀▀▀▀▀▀▀▀▄ ▀▀▀▀▀▀ ▀▀▀▀▀▀▀▀▀▀▀ ▄▀▀▀▀▀▀▀ ▀▀▀▀▀▀▀▀▀▀▀▀ ▀▀▀▀▀▄▀▀▀ ▀▀▀▀▀▄▀▀▀▀ ▀ ▀▀▀▀▀▀▄▀▀ ▀▀▀▀▀▀▀▀▀▀▀▀ ▀▀▀▀▀▀▀▀▀▀ ▀▀▀▀▀▀▀▀▀▀▀ ▀▀▀▀▀▀▀▀▀▀▄ ▀▀▀▀▀▀▀▀ ▀▀▀▀▀▀▀▀▀▀ ▀▀▀▀ ▀▀▀▀▀▀▀▀▀▀▀▀▄ ▀▀▀▀ ▀▀▀▀▀▀▀▀▀▀▀▀▀▀▄ ▀▀▀ ▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▄ ▀▀▀ ▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀ ▀▄ ▀▀▀▀▀▀▀▀▀▀▀▄▀▀▀▀▀▀ ▀▀ ▄▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀ ▀▀ ▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▄ ▀ ▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀ ▀▀▀▀▄▄▄▄▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀ ▀▀▀ ▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀ ▀▀▄ ▀▀▀▀▄▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀ ▄▀▀ ▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀ ▀▀ ▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▄▀▀▀▀▀▀▀▀▀▀▀ ▀ ▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▄▀▀▀▀▀▀▀▀▀▀ ▀▄▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▄▀▀▀▀ ▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▄▀▀ ▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▄▀▀▀▀▀▀▀▀▀▀▀▀▀ ▀▀▀▀▀▀▀▀ ▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀ ▀ ▀▀▀▀ ▀▀▀▀▀▀▀▀▀ ▀▀▀▀▄▀▀▀▀▀▀ ▀ ▀▀ ▀▀▀▀▀▀▀▀▀ ▀▀▀▄▀▀▀▀▀▀▀ ▀ ▀▀ ▀▀▀▀▀▀ ▀▀▀▀▀▀▀▀▀▀ ▀▄ ▀▀ ▀▀▀▀▀▀ ▀▀▀▀▀▀▀ ▀▀ ▀▀▀ ▀▀▀▀▀▀ ▀▀▀▀▀▀▄ ▀▀ ▀▀ ▀▀▀▀▀▀▀▀ ▀▀▀▀▀▀▀ ▀ ▀▀▀ ▀▀▀▀▀▀▄▀ ▀▀▀▀▀▀▀ ▀ ▀▀▀ ▄▀▀▀▀▀▄▄ ▀▀▀▀▄▄▀▀ ▀ ▀▀▀ ▀▀▀▀▀▀▀▀▄ ▀▀▀▄▀▀▀ ▀▀ ▀▀▀ ▀▀▀▀▀▀▀▀▀ ▀▀▀▀▀▀▀▀ ▀▀ ▀▀▀▀▀▀▀▀▀▀▀▄▀ ▀▀▀▀▀▀▀▀▄ ▀ ▀▀▀▀▀▀▀▀▀▀▀▀▀ ▀▀▀▀▀▀▀▀▀ ▀ ▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▄▄▀▀▀▀▀ ▀ ▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▄▀▀▀ ▀▄ ▄▀▀▀▀▀▀▀ ▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▄ ▀▀▄▀▀▀▄▀▀▀▀ ▀▀▀▀▄ ▀▀▀▀▀▀▀▀▀ ▀▀▀▀▀▀ ▀▀ ▀▀▀▀▀ ▀▀▀

╭ bit_set.zig ──────────────────────────────────────────────────╮ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ ╰───────────────────────────────────────────────────────────────╯

╭ find file ─ ─ ─ ─ ─ ─ ─ ─ ─ ─╮ ╭────╮ ╭ clone ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ╮ │ │ │http│ ssh │ │ ╰ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─╯ ╰────╯ ╰ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ╯

1 //! This file defines several variants of bit sets. A bit set 2 //! is a densely stored set of integers with a known maximum, 3 //! in which each integer gets a single bit. Bit sets have very 4 //! fast presence checks, update operations, and union and intersection 5 //! operations. However, if the number of possible items is very 6 //! large and the number of actual items in a given set is usually 7 //! small, they may be less memory efficient than an array set. 8 //! 9 //! There are five variants defined here: 10 //! 11 //! Integer: 12 //! A bit set with static size, which is backed by a single integer. 13 //! This set is good for sets with a small size, but may generate 14 //! inefficient code for larger sets, especially in debug mode. 15 //! 16 //! Array: 17 //! A bit set with static size, which is backed by an array of usize. 18 //! This set is good for sets with a larger size, but may use 19 //! more bytes than necessary if your set is small. 20 //! 21 //! Static: 22 //! Picks either Integer or Array depending on the requested 23 //! size. The interfaces of these two types match exactly, except for fields. 24 //! 25 //! Dynamic: 26 //! A bit set with runtime-known size, backed by an allocated slice 27 //! of usize. 28 //! 29 //! DynamicManaged: 30 //! A variant of Dynamic which stores an allocator, using it when needed. 31 32 const std = @import("std.zig"); 33 const assert = std.debug.assert; 34 const Allocator = std.mem.Allocator; 35 const builtin = @import("builtin"); 36 37 /// Deprecated: use `Static`. 38 pub const StaticBitSet = Static; 39 40 /// Returns the optimal static bit set type for the specified number 41 /// of elements: either `IntegerBitSet` or `ArrayBitSet`, 42 /// both of which fulfill the same interface. 43 /// The returned type will perform no allocations, 44 /// can be copied by value, and does not require deinitialization. 45 pub fn Static(comptime size: usize) type { 46 if (size <= @bitSizeOf(usize)) { 47 return Integer(size); 48 } else { 49 return Array(usize, size); 50 } 51 } 52 53 /// Deprecated: use `Integer`. 54 pub const IntegerBitSet = Integer; 55 56 /// A bit set with static size, which is backed by a single integer. 57 /// This set is good for sets with a small size, but may generate 58 /// inefficient code for larger sets, especially in debug mode. 59 pub fn Integer(comptime size: u16) type { 60 return packed struct(MaskInt) { 61 const Self = @This(); 62 63 // TODO: Make this a comptime field once those are fixed 64 /// The number of items in this bit set 65 pub const bit_length: usize = size; 66 67 /// The integer type used to represent a mask in this bit set 68 pub const MaskInt = @Int(.unsigned, size); 69 70 /// The integer type used to shift a mask in this bit set 71 pub const ShiftInt = std.math.Log2Int(MaskInt); 72 73 /// The bit mask, as a single integer 74 mask: MaskInt, 75 76 /// A bit set with no elements present. 77 pub const empty: Self = .{ .mask = 0 }; 78 79 /// A bit set with all elements present. 80 pub const full: Self = .{ .mask = ~@as(MaskInt, 0) }; 81 82 /// Returns the number of bits in this bit set 83 pub inline fn capacity(self: Self) usize { 84 _ = self; 85 return bit_length; 86 } 87 88 /// Returns true if the bit at the specified index 89 /// is present in the set, false otherwise. 90 pub fn isSet(self: Self, index: usize) bool { 91 assert(index < bit_length); 92 return (self.mask & maskBit(index)) != 0; 93 } 94 95 /// Returns the total number of set bits in this bit set. 96 pub fn count(self: Self) usize { 97 return @popCount(self.mask); 98 } 99 100 /// Changes the value of the specified bit of the bit 101 /// set to match the passed boolean. 102 pub fn setValue(self: *Self, index: usize, value: bool) void { 103 assert(index < bit_length); 104 if (MaskInt == u0) return; 105 const bit = maskBit(index); 106 const new_bit = bit & std.math.boolMask(MaskInt, value); 107 self.mask = (self.mask & ~bit) | new_bit; 108 } 109 110 /// Adds a specific bit to the bit set 111 pub fn set(self: *Self, index: usize) void { 112 assert(index < bit_length); 113 self.mask |= maskBit(index); 114 } 115 116 /// Changes the value of all bits in the specified range to 117 /// match the passed boolean. 118 pub fn setRangeValue(self: *Self, range: Range, value: bool) void { 119 assert(range.end <= bit_length); 120 assert(range.start <= range.end); 121 if (range.start == range.end) return; 122 if (MaskInt == u0) return; 123 124 const start_bit = @as(ShiftInt, @intCast(range.start)); 125 126 var mask = std.math.boolMask(MaskInt, true) << start_bit; 127 if (range.end != bit_length) { 128 const end_bit = @as(ShiftInt, @intCast(range.end)); 129 mask &= std.math.boolMask(MaskInt, true) >> @as(ShiftInt, @truncate(@as(usize, @bitSizeOf(MaskInt)) - @as(usize, end_bit))); 130 } 131 self.mask &= ~mask; 132 133 mask = std.math.boolMask(MaskInt, value) << start_bit; 134 if (range.end != bit_length) { 135 const end_bit = @as(ShiftInt, @intCast(range.end)); 136 mask &= std.math.boolMask(MaskInt, value) >> @as(ShiftInt, @truncate(@as(usize, @bitSizeOf(MaskInt)) - @as(usize, end_bit))); 137 } 138 self.mask |= mask; 139 } 140 141 /// Removes a specific bit from the bit set 142 pub fn unset(self: *Self, index: usize) void { 143 assert(index < bit_length); 144 // Workaround for #7953 145 if (MaskInt == u0) return; 146 self.mask &= ~maskBit(index); 147 } 148 149 /// Flips a specific bit in the bit set 150 pub fn toggle(self: *Self, index: usize) void { 151 assert(index < bit_length); 152 self.mask ^= maskBit(index); 153 } 154 155 /// Flips all bits in this bit set which are present 156 /// in the toggles bit set. 157 pub fn toggleSet(self: *Self, toggles: Self) void { 158 self.mask ^= toggles.mask; 159 } 160 161 /// Flips every bit in the bit set. 162 pub fn toggleAll(self: *Self) void { 163 self.mask = ~self.mask; 164 } 165 166 /// Performs a union of two bit sets, and stores the 167 /// result in the first one. Bits in the result are 168 /// set if the corresponding bits were set in either input. 169 pub fn setUnion(self: *Self, other: Self) void { 170 self.mask |= other.mask; 171 } 172 173 /// Performs an intersection of two bit sets, and stores 174 /// the result in the first one. Bits in the result are 175 /// set if the corresponding bits were set in both inputs. 176 pub fn setIntersection(self: *Self, other: Self) void { 177 self.mask &= other.mask; 178 } 179 180 /// Finds the index of the first set bit. 181 /// If no bits are set, returns null. 182 pub fn findFirstSet(self: Self) ?usize { 183 const mask = self.mask; 184 if (mask == 0) return null; 185 return @ctz(mask); 186 } 187 188 /// Finds the index of the last set bit. 189 /// If no bits are set, returns null. 190 pub fn findLastSet(self: Self) ?usize { 191 const mask = self.mask; 192 if (mask == 0) return null; 193 return bit_length - @clz(mask) - 1; 194 } 195 196 /// Finds the index of the first set bit, and unsets it. 197 /// If no bits are set, returns null. 198 pub fn toggleFirstSet(self: *Self) ?usize { 199 const mask = self.mask; 200 if (mask == 0) return null; 201 const index = @ctz(mask); 202 self.mask = mask & (mask - 1); 203 return index; 204 } 205 206 /// Returns true iff every corresponding bit in both 207 /// bit sets are the same. 208 pub fn eql(self: Self, other: Self) bool { 209 return bit_length == 0 or self.mask == other.mask; 210 } 211 212 /// Returns true iff the first bit set is the subset 213 /// of the second one. 214 pub fn subsetOf(self: Self, other: Self) bool { 215 return self.intersectWith(other).eql(self); 216 } 217 218 /// Returns true iff the first bit set is the superset 219 /// of the second one. 220 pub fn supersetOf(self: Self, other: Self) bool { 221 return other.subsetOf(self); 222 } 223 224 /// Returns the complement bit sets. Bits in the result 225 /// are set if the corresponding bits were not set. 226 pub fn complement(self: Self) Self { 227 var result = self; 228 result.toggleAll(); 229 return result; 230 } 231 232 /// Returns the union of two bit sets. Bits in the 233 /// result are set if the corresponding bits were set 234 /// in either input. 235 pub fn unionWith(self: Self, other: Self) Self { 236 var result = self; 237 result.setUnion(other); 238 return result; 239 } 240 241 /// Returns the intersection of two bit sets. Bits in 242 /// the result are set if the corresponding bits were 243 /// set in both inputs. 244 pub fn intersectWith(self: Self, other: Self) Self { 245 var result = self; 246 result.setIntersection(other); 247 return result; 248 } 249 250 /// Returns the xor of two bit sets. Bits in the 251 /// result are set if the corresponding bits were 252 /// not the same in both inputs. 253 pub fn xorWith(self: Self, other: Self) Self { 254 var result = self; 255 result.toggleSet(other); 256 return result; 257 } 258 259 /// Returns the difference of two bit sets. Bits in 260 /// the result are set if set in the first but not 261 /// set in the second set. 262 pub fn differenceWith(self: Self, other: Self) Self { 263 var result = self; 264 result.setIntersection(other.complement()); 265 return result; 266 } 267 268 /// Iterates through the items in the set, according to the options. 269 /// The default options (.{}) will iterate indices of set bits in 270 /// ascending order. Modifications to the underlying bit set may 271 /// or may not be observed by the iterator. 272 pub fn iterator(self: *const Self, comptime options: IteratorOptions) Iterator(options) { 273 return .{ 274 .bits_remain = switch (options.kind) { 275 .set => self.mask, 276 .unset => ~self.mask, 277 }, 278 }; 279 } 280 281 pub fn Iterator(comptime options: IteratorOptions) type { 282 return SingleWordIterator(options.direction); 283 } 284 285 fn SingleWordIterator(comptime direction: IteratorOptions.Direction) type { 286 return struct { 287 const IterSelf = @This(); 288 // all bits which have not yet been iterated over 289 bits_remain: MaskInt, 290 291 /// Returns the index of the next unvisited set bit 292 /// in the bit set, in ascending order. 293 pub fn next(self: *IterSelf) ?usize { 294 if (self.bits_remain == 0) return null; 295 296 switch (direction) { 297 .forward => { 298 const next_index = @ctz(self.bits_remain); 299 self.bits_remain &= self.bits_remain - 1; 300 return next_index; 301 }, 302 .reverse => { 303 const leading_zeroes = @clz(self.bits_remain); 304 const top_bit = (@bitSizeOf(MaskInt) - 1) - leading_zeroes; 305 self.bits_remain &= (@as(MaskInt, 1) << @as(ShiftInt, @intCast(top_bit))) - 1; 306 return top_bit; 307 }, 308 } 309 } 310 }; 311 } 312 313 fn maskBit(index: usize) MaskInt { 314 if (MaskInt == u0) return 0; 315 return @as(MaskInt, 1) << @as(ShiftInt, @intCast(index)); 316 } 317 fn boolMaskBit(index: usize, value: bool) MaskInt { 318 if (MaskInt == u0) return 0; 319 return @as(MaskInt, @intFromBool(value)) << @as(ShiftInt, @intCast(index)); 320 } 321 }; 322 } 323 324 /// Deprecated: use `Array`. 325 pub const ArrayBitSet = Array; 326 327 /// A bit set with static size, which is backed by an array of usize. 328 /// This set is good for sets with a larger size, but may use 329 /// more bytes than necessary if your set is small. 330 pub fn Array(comptime MaskIntType: type, comptime size: usize) type { 331 const mask_info: std.builtin.Type = @typeInfo(MaskIntType); 332 333 // Make sure the mask int is indeed an int 334 if (mask_info != .int) @compileError("Array can only operate on integer masks, but was passed " ++ @typeName(MaskIntType)); 335 336 // It must also be unsigned. 337 if (mask_info.int.signedness != .unsigned) @compileError("Array requires an unsigned integer mask type, but was passed " ++ @typeName(MaskIntType)); 338 339 // And it must not be empty. 340 if (MaskIntType == u0) 341 @compileError("Array requires a sized integer for its mask int. u0 does not work."); 342 343 const byte_size = std.mem.byte_size_in_bits; 344 345 // We use shift and truncate to decompose indices into mask indices and bit indices. 346 // This operation requires that the mask has an exact power of two number of bits. 347 if (!std.math.isPowerOfTwo(@bitSizeOf(MaskIntType))) { 348 var desired_bits = std.math.ceilPowerOfTwoAssert(usize, @bitSizeOf(MaskIntType)); 349 if (desired_bits < byte_size) desired_bits = byte_size; 350 const FixedMaskType = @Int(.unsigned, desired_bits); 351 @compileError("Array was passed integer type " ++ @typeName(MaskIntType) ++ 352 ", which is not a power of two. Please round this up to a power of two integer size (i.e. " ++ @typeName(FixedMaskType) ++ ")."); 353 } 354 355 // Make sure the integer has no padding bits. 356 // Those would be wasteful here and are probably a mistake by the user. 357 // This case may be hit with small powers of two, like u4. 358 if (@bitSizeOf(MaskIntType) != @sizeOf(MaskIntType) * byte_size) { 359 var desired_bits = @sizeOf(MaskIntType) * byte_size; 360 desired_bits = std.math.ceilPowerOfTwoAssert(usize, desired_bits); 361 const FixedMaskType = @Int(.unsigned, desired_bits); 362 @compileError("Array was passed integer type " ++ @typeName(MaskIntType) ++ 363 ", which contains padding bits. Please round this up to an unpadded integer size (i.e. " ++ @typeName(FixedMaskType) ++ ")."); 364 } 365 366 return extern struct { 367 const Self = @This(); 368 369 // TODO: Make this a comptime field once those are fixed 370 /// The number of items in this bit set 371 pub const bit_length: usize = size; 372 373 /// The integer type used to represent a mask in this bit set 374 pub const MaskInt = MaskIntType; 375 376 /// The integer type used to shift a mask in this bit set 377 pub const ShiftInt = std.math.Log2Int(MaskInt); 378 379 // bits in one mask 380 const mask_len = @bitSizeOf(MaskInt); 381 // total number of masks 382 const num_masks = (size + mask_len - 1) / mask_len; 383 // padding bits in the last mask (may be 0) 384 const last_pad_bits = mask_len * num_masks - size; 385 // Mask of valid bits in the last mask. 386 // All functions will ensure that the invalid 387 // bits in the last mask are zero. 388 pub const last_item_mask = ~@as(MaskInt, 0) >> last_pad_bits; 389 390 /// The bit masks, ordered with lower indices first. 391 /// Padding bits at the end are undefined. 392 masks: [num_masks]MaskInt, 393 394 /// A bit set with no elements present. 395 pub const empty: Self = .{ .masks = @splat(0) }; 396 397 /// A bit set with all elements present. 398 pub const full: Self = full: { 399 var masks: [num_masks]MaskInt = @splat(~@as(MaskInt, 0)); 400 if (num_masks > 0) masks[num_masks - 1] = last_item_mask; 401 break :full .{ .masks = masks }; 402 }; 403 404 /// Returns the number of bits in this bit set 405 pub inline fn capacity(self: Self) usize { 406 _ = self; 407 return bit_length; 408 } 409 410 /// Returns true if the bit at the specified index 411 /// is present in the set, false otherwise. 412 pub fn isSet(self: Self, index: usize) bool { 413 assert(index < bit_length); 414 if (num_masks == 0) return false; // doesn't compile in this case 415 return (self.masks[maskIndex(index)] & maskBit(index)) != 0; 416 } 417 418 /// Returns the total number of set bits in this bit set. 419 pub fn count(self: Self) usize { 420 var total: usize = 0; 421 for (self.masks) |mask| { 422 total += @popCount(mask); 423 } 424 return total; 425 } 426 427 /// Changes the value of the specified bit of the bit 428 /// set to match the passed boolean. 429 pub fn setValue(self: *Self, index: usize, value: bool) void { 430 assert(index < bit_length); 431 if (num_masks == 0) return; // doesn't compile in this case 432 const bit = maskBit(index); 433 const mask_index = maskIndex(index); 434 const new_bit = bit & std.math.boolMask(MaskInt, value); 435 self.masks[mask_index] = (self.masks[mask_index] & ~bit) | new_bit; 436 } 437 438 /// Adds a specific bit to the bit set 439 pub fn set(self: *Self, index: usize) void { 440 assert(index < bit_length); 441 if (num_masks == 0) return; // doesn't compile in this case 442 self.masks[maskIndex(index)] |= maskBit(index); 443 } 444 445 /// Changes the value of all bits in the specified range to 446 /// match the passed boolean. 447 pub fn setRangeValue(self: *Self, range: Range, value: bool) void { 448 assert(range.end <= bit_length); 449 assert(range.start <= range.end); 450 if (range.start == range.end) return; 451 if (num_masks == 0) return; 452 453 const start_mask_index = maskIndex(range.start); 454 const start_bit = @as(ShiftInt, @truncate(range.start)); 455 456 const end_mask_index = maskIndex(range.end); 457 const end_bit = @as(ShiftInt, @truncate(range.end)); 458 459 if (start_mask_index == end_mask_index) { 460 var mask1 = std.math.boolMask(MaskInt, true) << start_bit; 461 var mask2 = std.math.boolMask(MaskInt, true) >> (mask_len - 1) - (end_bit - 1); 462 self.masks[start_mask_index] &= ~(mask1 & mask2); 463 464 mask1 = std.math.boolMask(MaskInt, value) << start_bit; 465 mask2 = std.math.boolMask(MaskInt, value) >> (mask_len - 1) - (end_bit - 1); 466 self.masks[start_mask_index] |= mask1 & mask2; 467 } else { 468 var bulk_mask_index: usize = undefined; 469 if (start_bit > 0) { 470 self.masks[start_mask_index] = 471 (self.masks[start_mask_index] & ~(std.math.boolMask(MaskInt, true) << start_bit)) | 472 (std.math.boolMask(MaskInt, value) << start_bit); 473 bulk_mask_index = start_mask_index + 1; 474 } else { 475 bulk_mask_index = start_mask_index; 476 } 477 478 while (bulk_mask_index < end_mask_index) : (bulk_mask_index += 1) { 479 self.masks[bulk_mask_index] = std.math.boolMask(MaskInt, value); 480 } 481 482 if (end_bit > 0) { 483 self.masks[end_mask_index] = 484 (self.masks[end_mask_index] & (std.math.boolMask(MaskInt, true) << end_bit)) | 485 (std.math.boolMask(MaskInt, value) >> ((@bitSizeOf(MaskInt) - 1) - (end_bit - 1))); 486 } 487 } 488 } 489 490 /// Removes a specific bit from the bit set 491 pub fn unset(self: *Self, index: usize) void { 492 assert(index < bit_length); 493 if (num_masks == 0) return; // doesn't compile in this case 494 self.masks[maskIndex(index)] &= ~maskBit(index); 495 } 496 497 /// Flips a specific bit in the bit set 498 pub fn toggle(self: *Self, index: usize) void { 499 assert(index < bit_length); 500 if (num_masks == 0) return; // doesn't compile in this case 501 self.masks[maskIndex(index)] ^= maskBit(index); 502 } 503 504 /// Flips all bits in this bit set which are present 505 /// in the toggles bit set. 506 pub fn toggleSet(self: *Self, toggles: Self) void { 507 for (&self.masks, 0..) |*mask, i| { 508 mask.* ^= toggles.masks[i]; 509 } 510 } 511 512 /// Flips every bit in the bit set. 513 pub fn toggleAll(self: *Self) void { 514 for (&self.masks) |*mask| { 515 mask.* = ~mask.*; 516 } 517 518 // Zero the padding bits 519 if (num_masks > 0) { 520 self.masks[num_masks - 1] &= last_item_mask; 521 } 522 } 523 524 /// Performs a union of two bit sets, and stores the 525 /// result in the first one. Bits in the result are 526 /// set if the corresponding bits were set in either input. 527 pub fn setUnion(self: *Self, other: Self) void { 528 for (&self.masks, 0..) |*mask, i| { 529 mask.* |= other.masks[i]; 530 } 531 } 532 533 /// Performs an intersection of two bit sets, and stores 534 /// the result in the first one. Bits in the result are 535 /// set if the corresponding bits were set in both inputs. 536 pub fn setIntersection(self: *Self, other: Self) void { 537 for (&self.masks, 0..) |*mask, i| { 538 mask.* &= other.masks[i]; 539 } 540 } 541 542 /// Finds the index of the first set bit. 543 /// If no bits are set, returns null. 544 pub fn findFirstSet(self: Self) ?usize { 545 var offset: usize = 0; 546 const mask = for (self.masks) |mask| { 547 if (mask != 0) break mask; 548 offset += @bitSizeOf(MaskInt); 549 } else return null; 550 return offset + @ctz(mask); 551 } 552 553 /// Finds the index of the last set bit. 554 /// If no bits are set, returns null. 555 pub fn findLastSet(self: Self) ?usize { 556 if (bit_length == 0) return null; 557 const bs = @bitSizeOf(MaskInt); 558 var len = bit_length / bs; 559 if (bit_length % bs != 0) len += 1; 560 var offset: usize = len * bs; 561 var idx: usize = len - 1; 562 while (self.masks[idx] == 0) : (idx -= 1) { 563 offset -= bs; 564 if (idx == 0) return null; 565 } 566 offset -= @clz(self.masks[idx]); 567 offset -= 1; 568 return offset; 569 } 570 571 /// Finds the index of the first set bit, and unsets it. 572 /// If no bits are set, returns null. 573 pub fn toggleFirstSet(self: *Self) ?usize { 574 var offset: usize = 0; 575 const mask = for (&self.masks) |*mask| { 576 if (mask.* != 0) break mask; 577 offset += @bitSizeOf(MaskInt); 578 } else return null; 579 const index = @ctz(mask.*); 580 mask.* &= (mask.* - 1); 581 return offset + index; 582 } 583 584 /// Returns true iff every corresponding bit in both 585 /// bit sets are the same. 586 pub fn eql(self: Self, other: Self) bool { 587 var i: usize = 0; 588 return while (i < num_masks) : (i += 1) { 589 if (self.masks[i] != other.masks[i]) { 590 break false; 591 } 592 } else true; 593 } 594 595 /// Returns true iff the first bit set is the subset 596 /// of the second one. 597 pub fn subsetOf(self: Self, other: Self) bool { 598 return self.intersectWith(other).eql(self); 599 } 600 601 /// Returns true iff the first bit set is the superset 602 /// of the second one. 603 pub fn supersetOf(self: Self, other: Self) bool { 604 return other.subsetOf(self); 605 } 606 607 /// Returns the complement bit sets. Bits in the result 608 /// are set if the corresponding bits were not set. 609 pub fn complement(self: Self) Self { 610 var result = self; 611 result.toggleAll(); 612 return result; 613 } 614 615 /// Returns the union of two bit sets. Bits in the 616 /// result are set if the corresponding bits were set 617 /// in either input. 618 pub fn unionWith(self: Self, other: Self) Self { 619 var result = self; 620 result.setUnion(other); 621 return result; 622 } 623 624 /// Returns the intersection of two bit sets. Bits in 625 /// the result are set if the corresponding bits were 626 /// set in both inputs. 627 pub fn intersectWith(self: Self, other: Self) Self { 628 var result = self; 629 result.setIntersection(other); 630 return result; 631 } 632 633 /// Returns the xor of two bit sets. Bits in the 634 /// result are set if the corresponding bits were 635 /// not the same in both inputs. 636 pub fn xorWith(self: Self, other: Self) Self { 637 var result = self; 638 result.toggleSet(other); 639 return result; 640 } 641 642 /// Returns the difference of two bit sets. Bits in 643 /// the result are set if set in the first but not 644 /// set in the second set. 645 pub fn differenceWith(self: Self, other: Self) Self { 646 var result = self; 647 result.setIntersection(other.complement()); 648 return result; 649 } 650 651 /// Iterates through the items in the set, according to the options. 652 /// The default options (.{}) will iterate indices of set bits in 653 /// ascending order. Modifications to the underlying bit set may 654 /// or may not be observed by the iterator. 655 pub fn iterator(self: *const Self, comptime options: IteratorOptions) Iterator(options) { 656 return Iterator(options).init(&self.masks, last_item_mask); 657 } 658 659 pub fn Iterator(comptime options: IteratorOptions) type { 660 return GenericIterator(MaskInt, options); 661 } 662 663 fn maskBit(index: usize) MaskInt { 664 return @as(MaskInt, 1) << @as(ShiftInt, @truncate(index)); 665 } 666 fn maskIndex(index: usize) usize { 667 return index >> @bitSizeOf(ShiftInt); 668 } 669 fn boolMaskBit(index: usize, value: bool) MaskInt { 670 return @as(MaskInt, @intFromBool(value)) << @as(ShiftInt, @intCast(index)); 671 } 672 }; 673 } 674 675 /// Deprecated: use `Dynamic`. 676 pub const DynamicBitSetUnmanaged = Dynamic; 677 678 /// A bit set with runtime-known size, backed by an allocated slice 679 /// of usize. The allocator must be tracked externally by the user. 680 pub const Dynamic = struct { 681 const Self = @This(); 682 683 /// The integer type used to represent a mask in this bit set 684 pub const MaskInt = usize; 685 686 /// The integer type used to shift a mask in this bit set 687 pub const ShiftInt = std.math.Log2Int(MaskInt); 688 689 /// The number of valid items in this bit set 690 bit_length: usize = 0, 691 692 /// The bit masks, ordered with lower indices first. 693 /// Padding bits at the end must be zeroed. 694 masks: [*]MaskInt = empty_masks_ptr, 695 // This pointer is one usize after the actual allocation. 696 // That slot holds the size of the true allocation, which 697 // is needed by Zig's allocator interface in case a shrink 698 // fails. 699 700 // Don't modify this value. Ideally it would go in const data so 701 // modifications would cause a bus error, but the only way 702 // to discard a const qualifier is through intFromPtr, which 703 // cannot currently round trip at comptime. 704 var empty_masks_data = [_]MaskInt{ 0, undefined }; 705 const empty_masks_ptr = empty_masks_data[1..2]; 706 707 /// Creates a bit set with no elements present. 708 /// If bit_length is not zero, deinit must eventually be called. 709 pub fn initEmpty(allocator: Allocator, bit_length: usize) !Self { 710 var self = Self{}; 711 try self.resize(allocator, bit_length, false); 712 return self; 713 } 714 715 /// Creates a bit set with all elements present. 716 /// If bit_length is not zero, deinit must eventually be called. 717 pub fn initFull(allocator: Allocator, bit_length: usize) !Self { 718 var self = Self{}; 719 try self.resize(allocator, bit_length, true); 720 return self; 721 } 722 723 /// Resizes to a new bit_length. If the new length is larger 724 /// than the old length, fills any added bits with `fill`. 725 /// If new_len is not zero, deinit must eventually be called. 726 pub fn resize(self: *@This(), allocator: Allocator, new_len: usize, fill: bool) !void { 727 const old_len = self.bit_length; 728 729 const old_masks = numMasks(old_len); 730 const new_masks = numMasks(new_len); 731 732 const old_allocation = (self.masks - 1)[0..(self.masks - 1)[0]]; 733 734 if (new_masks == 0) { 735 assert(new_len == 0); 736 allocator.free(old_allocation); 737 self.masks = empty_masks_ptr; 738 self.bit_length = 0; 739 return; 740 } 741 742 if (old_allocation.len != new_masks + 1) realloc: { 743 // If realloc fails, it may mean one of two things. 744 // If we are growing, it means we are out of memory. 745 // If we are shrinking, it means the allocator doesn't 746 // want to move the allocation. This means we need to 747 // hold on to the extra 8 bytes required to be able to free 748 // this allocation properly. 749 const new_allocation = allocator.realloc(old_allocation, new_masks + 1) catch |err| { 750 if (new_masks + 1 > old_allocation.len) return err; 751 break :realloc; 752 }; 753 754 new_allocation[0] = new_allocation.len; 755 self.masks = new_allocation.ptr + 1; 756 } 757 758 // If we increased in size, we need to set any new bits 759 // to the fill value. 760 if (new_len > old_len) { 761 // set the padding bits in the old last item to 1 762 if (fill and old_masks > 0) { 763 const old_padding_bits = old_masks * @bitSizeOf(MaskInt) - old_len; 764 const old_mask = (~@as(MaskInt, 0)) >> @as(ShiftInt, @intCast(old_padding_bits)); 765 self.masks[old_masks - 1] |= ~old_mask; 766 } 767 768 // fill in any new masks 769 if (new_masks > old_masks) { 770 const fill_value = std.math.boolMask(MaskInt, fill); 771 @memset(self.masks[old_masks..new_masks], fill_value); 772 } 773 } 774 775 // Zero out the padding bits 776 if (new_len > 0) { 777 const padding_bits = new_masks * @bitSizeOf(MaskInt) - new_len; 778 const last_item_mask = (~@as(MaskInt, 0)) >> @as(ShiftInt, @intCast(padding_bits)); 779 self.masks[new_masks - 1] &= last_item_mask; 780 } 781 782 // And finally, save the new length. 783 self.bit_length = new_len; 784 } 785 786 /// Deinitializes the array and releases its memory. 787 /// The passed allocator must be the same one used for 788 /// init* or resize in the past. 789 pub fn deinit(self: *Self, allocator: Allocator) void { 790 self.resize(allocator, 0, false) catch unreachable; 791 } 792 793 /// Creates a duplicate of this bit set, using the new allocator. 794 pub fn clone(self: *const Self, new_allocator: Allocator) !Self { 795 const num_masks = numMasks(self.bit_length); 796 var copy = Self{}; 797 try copy.resize(new_allocator, self.bit_length, false); 798 @memcpy(copy.masks[0..num_masks], self.masks[0..num_masks]); 799 return copy; 800 } 801 802 /// Returns the number of bits in this bit set 803 pub inline fn capacity(self: Self) usize { 804 return self.bit_length; 805 } 806 807 /// Returns true if the bit at the specified index 808 /// is present in the set, false otherwise. 809 pub fn isSet(self: Self, index: usize) bool { 810 assert(index < self.bit_length); 811 return (self.masks[maskIndex(index)] & maskBit(index)) != 0; 812 } 813 814 /// Returns the total number of set bits in this bit set. 815 pub fn count(self: Self) usize { 816 const num_masks = (self.bit_length + (@bitSizeOf(MaskInt) - 1)) / @bitSizeOf(MaskInt); 817 var total: usize = 0; 818 for (self.masks[0..num_masks]) |mask| { 819 // Note: This is where we depend on padding bits being zero 820 total += @popCount(mask); 821 } 822 return total; 823 } 824 825 /// Changes the value of the specified bit of the bit 826 /// set to match the passed boolean. 827 pub fn setValue(self: *Self, index: usize, value: bool) void { 828 assert(index < self.bit_length); 829 const bit = maskBit(index); 830 const mask_index = maskIndex(index); 831 const new_bit = bit & std.math.boolMask(MaskInt, value); 832 self.masks[mask_index] = (self.masks[mask_index] & ~bit) | new_bit; 833 } 834 835 /// Adds a specific bit to the bit set 836 pub fn set(self: *Self, index: usize) void { 837 assert(index < self.bit_length); 838 self.masks[maskIndex(index)] |= maskBit(index); 839 } 840 841 /// Changes the value of all bits in the specified range to 842 /// match the passed boolean. 843 pub fn setRangeValue(self: *Self, range: Range, value: bool) void { 844 assert(range.end <= self.bit_length); 845 assert(range.start <= range.end); 846 if (range.start == range.end) return; 847 848 const start_mask_index = maskIndex(range.start); 849 const start_bit = @as(ShiftInt, @truncate(range.start)); 850 851 const end_mask_index = maskIndex(range.end); 852 const end_bit = @as(ShiftInt, @truncate(range.end)); 853 854 if (start_mask_index == end_mask_index) { 855 var mask1 = std.math.boolMask(MaskInt, true) << start_bit; 856 var mask2 = std.math.boolMask(MaskInt, true) >> (@bitSizeOf(MaskInt) - 1) - (end_bit - 1); 857 self.masks[start_mask_index] &= ~(mask1 & mask2); 858 859 mask1 = std.math.boolMask(MaskInt, value) << start_bit; 860 mask2 = std.math.boolMask(MaskInt, value) >> (@bitSizeOf(MaskInt) - 1) - (end_bit - 1); 861 self.masks[start_mask_index] |= mask1 & mask2; 862 } else { 863 var bulk_mask_index: usize = undefined; 864 if (start_bit > 0) { 865 self.masks[start_mask_index] = 866 (self.masks[start_mask_index] & ~(std.math.boolMask(MaskInt, true) << start_bit)) | 867 (std.math.boolMask(MaskInt, value) << start_bit); 868 bulk_mask_index = start_mask_index + 1; 869 } else { 870 bulk_mask_index = start_mask_index; 871 } 872 873 while (bulk_mask_index < end_mask_index) : (bulk_mask_index += 1) { 874 self.masks[bulk_mask_index] = std.math.boolMask(MaskInt, value); 875 } 876 877 if (end_bit > 0) { 878 self.masks[end_mask_index] = 879 (self.masks[end_mask_index] & (std.math.boolMask(MaskInt, true) << end_bit)) | 880 (std.math.boolMask(MaskInt, value) >> ((@bitSizeOf(MaskInt) - 1) - (end_bit - 1))); 881 } 882 } 883 } 884 885 /// Removes a specific bit from the bit set 886 pub fn unset(self: *Self, index: usize) void { 887 assert(index < self.bit_length); 888 self.masks[maskIndex(index)] &= ~maskBit(index); 889 } 890 891 /// Set all bits to 0. 892 pub fn unsetAll(self: *Self) void { 893 const masks_len = numMasks(self.bit_length); 894 @memset(self.masks[0..masks_len], 0); 895 } 896 897 /// Set all bits to 1. 898 pub fn setAll(self: *Self) void { 899 const masks_len = numMasks(self.bit_length); 900 @memset(self.masks[0..masks_len], std.math.maxInt(MaskInt)); 901 } 902 903 /// Flips a specific bit in the bit set 904 pub fn toggle(self: *Self, index: usize) void { 905 assert(index < self.bit_length); 906 self.masks[maskIndex(index)] ^= maskBit(index); 907 } 908 909 /// Flips all bits in this bit set which are present 910 /// in the toggles bit set. Both sets must have the 911 /// same bit_length. 912 pub fn toggleSet(self: *Self, toggles: Self) void { 913 assert(toggles.bit_length == self.bit_length); 914 const num_masks = numMasks(self.bit_length); 915 for (self.masks[0..num_masks], 0..) |*mask, i| { 916 mask.* ^= toggles.masks[i]; 917 } 918 } 919 920 /// Flips every bit in the bit set. 921 pub fn toggleAll(self: *Self) void { 922 const bit_length = self.bit_length; 923 // avoid underflow if bit_length is zero 924 if (bit_length == 0) return; 925 926 const num_masks = numMasks(self.bit_length); 927 for (self.masks[0..num_masks]) |*mask| { 928 mask.* = ~mask.*; 929 } 930 931 const padding_bits = num_masks * @bitSizeOf(MaskInt) - bit_length; 932 const last_item_mask = (~@as(MaskInt, 0)) >> @as(ShiftInt, @intCast(padding_bits)); 933 self.masks[num_masks - 1] &= last_item_mask; 934 } 935 936 /// Performs a union of two bit sets, and stores the 937 /// result in the first one. Bits in the result are 938 /// set if the corresponding bits were set in either input. 939 /// The two sets must both be the same bit_length. 940 pub fn setUnion(self: *Self, other: Self) void { 941 assert(other.bit_length == self.bit_length); 942 const num_masks = numMasks(self.bit_length); 943 for (self.masks[0..num_masks], 0..) |*mask, i| { 944 mask.* |= other.masks[i]; 945 } 946 } 947 948 /// Performs an intersection of two bit sets, and stores 949 /// the result in the first one. Bits in the result are 950 /// set if the corresponding bits were set in both inputs. 951 /// The two sets must both be the same bit_length. 952 pub fn setIntersection(self: *Self, other: Self) void { 953 assert(other.bit_length == self.bit_length); 954 const num_masks = numMasks(self.bit_length); 955 for (self.masks[0..num_masks], 0..) |*mask, i| { 956 mask.* &= other.masks[i]; 957 } 958 } 959 960 /// Finds the index of the first set bit. 961 /// If no bits are set, returns null. 962 pub fn findFirstSet(self: Self) ?usize { 963 var offset: usize = 0; 964 var mask = self.masks; 965 while (offset < self.bit_length) { 966 if (mask[0] != 0) break; 967 mask += 1; 968 offset += @bitSizeOf(MaskInt); 969 } else return null; 970 return offset + @ctz(mask[0]); 971 } 972 973 /// Finds the index of the last set bit. 974 /// If no bits are set, returns null. 975 pub fn findLastSet(self: Self) ?usize { 976 if (self.bit_length == 0) return null; 977 const bs = @bitSizeOf(MaskInt); 978 var len = self.bit_length / bs; 979 if (self.bit_length % bs != 0) len += 1; 980 var offset: usize = len * bs; 981 var idx: usize = len - 1; 982 while (self.masks[idx] == 0) : (idx -= 1) { 983 offset -= bs; 984 if (idx == 0) return null; 985 } 986 offset -= @clz(self.masks[idx]); 987 offset -= 1; 988 return offset; 989 } 990 991 /// Finds the index of the first set bit, and unsets it. 992 /// If no bits are set, returns null. 993 pub fn toggleFirstSet(self: *Self) ?usize { 994 var offset: usize = 0; 995 var mask = self.masks; 996 while (offset < self.bit_length) { 997 if (mask[0] != 0) break; 998 mask += 1; 999 offset += @bitSizeOf(MaskInt); 1000 } else return null; 1001 const index = @ctz(mask[0]); 1002 mask[0] &= (mask[0] - 1); 1003 return offset + index; 1004 } 1005 1006 /// Returns true iff every corresponding bit in both 1007 /// bit sets are the same. 1008 pub fn eql(self: Self, other: Self) bool { 1009 if (self.bit_length != other.bit_length) { 1010 return false; 1011 } 1012 const num_masks = numMasks(self.bit_length); 1013 var i: usize = 0; 1014 return while (i < num_masks) : (i += 1) { 1015 if (self.masks[i] != other.masks[i]) { 1016 break false; 1017 } 1018 } else true; 1019 } 1020 1021 /// Returns true iff the first bit set is the subset 1022 /// of the second one. 1023 pub fn subsetOf(self: Self, other: Self) bool { 1024 if (self.bit_length != other.bit_length) { 1025 return false; 1026 } 1027 const num_masks = numMasks(self.bit_length); 1028 var i: usize = 0; 1029 return while (i < num_masks) : (i += 1) { 1030 if (self.masks[i] & other.masks[i] != self.masks[i]) { 1031 break false; 1032 } 1033 } else true; 1034 } 1035 1036 /// Returns true iff the first bit set is the superset 1037 /// of the second one. 1038 pub fn supersetOf(self: Self, other: Self) bool { 1039 if (self.bit_length != other.bit_length) { 1040 return false; 1041 } 1042 const num_masks = numMasks(self.bit_length); 1043 var i: usize = 0; 1044 return while (i < num_masks) : (i += 1) { 1045 if (self.masks[i] & other.masks[i] != other.masks[i]) { 1046 break false; 1047 } 1048 } else true; 1049 } 1050 1051 /// Iterates through the items in the set, according to the options. 1052 /// The default options (.{}) will iterate indices of set bits in 1053 /// ascending order. Modifications to the underlying bit set may 1054 /// or may not be observed by the iterator. Resizing the underlying 1055 /// bit set invalidates the iterator. 1056 pub fn iterator(self: *const Self, comptime options: IteratorOptions) Iterator(options) { 1057 const num_masks = numMasks(self.bit_length); 1058 const padding_bits = num_masks * @bitSizeOf(MaskInt) - self.bit_length; 1059 const last_item_mask = (~@as(MaskInt, 0)) >> @as(ShiftInt, @intCast(padding_bits)); 1060 return Iterator(options).init(self.masks[0..num_masks], last_item_mask); 1061 } 1062 1063 pub fn Iterator(comptime options: IteratorOptions) type { 1064 return GenericIterator(MaskInt, options); 1065 } 1066 1067 fn maskBit(index: usize) MaskInt { 1068 return @as(MaskInt, 1) << @as(ShiftInt, @truncate(index)); 1069 } 1070 fn maskIndex(index: usize) usize { 1071 return index >> @bitSizeOf(ShiftInt); 1072 } 1073 fn boolMaskBit(index: usize, value: bool) MaskInt { 1074 return @as(MaskInt, @intFromBool(value)) << @as(ShiftInt, @intCast(index)); 1075 } 1076 fn numMasks(bit_length: usize) usize { 1077 return (bit_length + (@bitSizeOf(MaskInt) - 1)) / @bitSizeOf(MaskInt); 1078 } 1079 }; 1080 1081 /// Deprecated: use `DynamicManaged` or `Dynamic` (will need to update callsites). 1082 pub const DynamicBitSet = DynamicManaged; 1083 1084 /// A bit set with runtime-known size, backed by an allocated slice 1085 /// of usize. Thin wrapper around Dynamic which keeps 1086 /// track of the allocator instance. 1087 /// 1088 /// Deprecated in favor of `Dynamic` which accepts an `Allocator` 1089 /// as a parameter when needed instead of storing it. 1090 pub const DynamicManaged = struct { 1091 const Self = @This(); 1092 1093 /// The integer type used to represent a mask in this bit set 1094 pub const MaskInt = usize; 1095 1096 /// The integer type used to shift a mask in this bit set 1097 pub const ShiftInt = std.math.Log2Int(MaskInt); 1098 1099 allocator: Allocator, 1100 unmanaged: Dynamic = .{}, 1101 1102 /// Creates a bit set with no elements present. 1103 pub fn initEmpty(allocator: Allocator, bit_length: usize) !Self { 1104 return Self{ 1105 .unmanaged = try .initEmpty(allocator, bit_length), 1106 .allocator = allocator, 1107 }; 1108 } 1109 1110 /// Creates a bit set with all elements present. 1111 pub fn initFull(allocator: Allocator, bit_length: usize) !Self { 1112 return Self{ 1113 .unmanaged = try .initFull(allocator, bit_length), 1114 .allocator = allocator, 1115 }; 1116 } 1117 1118 /// Resizes to a new length. If the new length is larger 1119 /// than the old length, fills any added bits with `fill`. 1120 pub fn resize(self: *@This(), new_len: usize, fill: bool) !void { 1121 try self.unmanaged.resize(self.allocator, new_len, fill); 1122 } 1123 1124 /// Deinitializes the array and releases its memory. 1125 /// The passed allocator must be the same one used for 1126 /// init* or resize in the past. 1127 pub fn deinit(self: *Self) void { 1128 self.unmanaged.deinit(self.allocator); 1129 } 1130 1131 /// Creates a duplicate of this bit set, using the new allocator. 1132 pub fn clone(self: *const Self, new_allocator: Allocator) !Self { 1133 return Self{ 1134 .unmanaged = try self.unmanaged.clone(new_allocator), 1135 .allocator = new_allocator, 1136 }; 1137 } 1138 1139 /// Returns the number of bits in this bit set 1140 pub inline fn capacity(self: Self) usize { 1141 return self.unmanaged.capacity(); 1142 } 1143 1144 /// Returns true if the bit at the specified index 1145 /// is present in the set, false otherwise. 1146 pub fn isSet(self: Self, index: usize) bool { 1147 return self.unmanaged.isSet(index); 1148 } 1149 1150 /// Returns the total number of set bits in this bit set. 1151 pub fn count(self: Self) usize { 1152 return self.unmanaged.count(); 1153 } 1154 1155 /// Changes the value of the specified bit of the bit 1156 /// set to match the passed boolean. 1157 pub fn setValue(self: *Self, index: usize, value: bool) void { 1158 self.unmanaged.setValue(index, value); 1159 } 1160 1161 /// Adds a specific bit to the bit set 1162 pub fn set(self: *Self, index: usize) void { 1163 self.unmanaged.set(index); 1164 } 1165 1166 /// Changes the value of all bits in the specified range to 1167 /// match the passed boolean. 1168 pub fn setRangeValue(self: *Self, range: Range, value: bool) void { 1169 self.unmanaged.setRangeValue(range, value); 1170 } 1171 1172 /// Removes a specific bit from the bit set 1173 pub fn unset(self: *Self, index: usize) void { 1174 self.unmanaged.unset(index); 1175 } 1176 1177 /// Flips a specific bit in the bit set 1178 pub fn toggle(self: *Self, index: usize) void { 1179 self.unmanaged.toggle(index); 1180 } 1181 1182 /// Flips all bits in this bit set which are present 1183 /// in the toggles bit set. Both sets must have the 1184 /// same bit_length. 1185 pub fn toggleSet(self: *Self, toggles: Self) void { 1186 self.unmanaged.toggleSet(toggles.unmanaged); 1187 } 1188 1189 /// Flips every bit in the bit set. 1190 pub fn toggleAll(self: *Self) void { 1191 self.unmanaged.toggleAll(); 1192 } 1193 1194 /// Performs a union of two bit sets, and stores the 1195 /// result in the first one. Bits in the result are 1196 /// set if the corresponding bits were set in either input. 1197 /// The two sets must both be the same bit_length. 1198 pub fn setUnion(self: *Self, other: Self) void { 1199 self.unmanaged.setUnion(other.unmanaged); 1200 } 1201 1202 /// Performs an intersection of two bit sets, and stores 1203 /// the result in the first one. Bits in the result are 1204 /// set if the corresponding bits were set in both inputs. 1205 /// The two sets must both be the same bit_length. 1206 pub fn setIntersection(self: *Self, other: Self) void { 1207 self.unmanaged.setIntersection(other.unmanaged); 1208 } 1209 1210 /// Finds the index of the first set bit. 1211 /// If no bits are set, returns null. 1212 pub fn findFirstSet(self: Self) ?usize { 1213 return self.unmanaged.findFirstSet(); 1214 } 1215 1216 /// Finds the index of the last set bit. 1217 /// If no bits are set, returns null. 1218 pub fn findLastSet(self: Self) ?usize { 1219 return self.unmanaged.findLastSet(); 1220 } 1221 1222 /// Finds the index of the first set bit, and unsets it. 1223 /// If no bits are set, returns null. 1224 pub fn toggleFirstSet(self: *Self) ?usize { 1225 return self.unmanaged.toggleFirstSet(); 1226 } 1227 1228 /// Returns true iff every corresponding bit in both 1229 /// bit sets are the same. 1230 pub fn eql(self: Self, other: Self) bool { 1231 return self.unmanaged.eql(other.unmanaged); 1232 } 1233 1234 /// Iterates through the items in the set, according to the options. 1235 /// The default options (.{}) will iterate indices of set bits in 1236 /// ascending order. Modifications to the underlying bit set may 1237 /// or may not be observed by the iterator. Resizing the underlying 1238 /// bit set invalidates the iterator. 1239 pub fn iterator(self: *const Self, comptime options: IteratorOptions) Iterator(options) { 1240 return self.unmanaged.iterator(options); 1241 } 1242 1243 pub const Iterator = Dynamic.Iterator; 1244 }; 1245 1246 /// Options for configuring an iterator over a bit set 1247 pub const IteratorOptions = struct { 1248 /// determines which bits should be visited 1249 kind: Type = .set, 1250 /// determines the order in which bit indices should be visited 1251 direction: Direction = .forward, 1252 1253 pub const Type = enum { 1254 /// visit indexes of set bits 1255 set, 1256 /// visit indexes of unset bits 1257 unset, 1258 }; 1259 1260 pub const Direction = enum { 1261 /// visit indices in ascending order 1262 forward, 1263 /// visit indices in descending order. 1264 /// Note that this may be slightly more expensive than forward iteration. 1265 reverse, 1266 }; 1267 }; 1268 1269 // The iterator is reusable between several bit set types 1270 fn GenericIterator(comptime MaskInt: type, comptime options: IteratorOptions) type { 1271 const ShiftInt = std.math.Log2Int(MaskInt); 1272 const kind = options.kind; 1273 const direction = options.direction; 1274 return struct { 1275 const Self = @This(); 1276 1277 // all bits which have not yet been iterated over 1278 bits_remain: MaskInt, 1279 // all words which have not yet been iterated over 1280 words_remain: []const MaskInt, 1281 // the offset of the current word 1282 bit_offset: usize, 1283 // the mask of the last word 1284 last_word_mask: MaskInt, 1285 1286 fn init(masks: []const MaskInt, last_word_mask: MaskInt) Self { 1287 if (masks.len == 0) { 1288 return Self{ 1289 .bits_remain = 0, 1290 .words_remain = &[_]MaskInt{}, 1291 .last_word_mask = last_word_mask, 1292 .bit_offset = 0, 1293 }; 1294 } else { 1295 var result = Self{ 1296 .bits_remain = 0, 1297 .words_remain = masks, 1298 .last_word_mask = last_word_mask, 1299 .bit_offset = if (direction == .forward) 0 else (masks.len - 1) * @bitSizeOf(MaskInt), 1300 }; 1301 result.nextWord(true); 1302 return result; 1303 } 1304 } 1305 1306 /// Returns the index of the next unvisited set bit 1307 /// in the bit set, in ascending order. 1308 pub fn next(self: *Self) ?usize { 1309 while (self.bits_remain == 0) { 1310 if (self.words_remain.len == 0) return null; 1311 self.nextWord(false); 1312 switch (direction) { 1313 .forward => self.bit_offset += @bitSizeOf(MaskInt), 1314 .reverse => self.bit_offset -= @bitSizeOf(MaskInt), 1315 } 1316 } 1317 1318 switch (direction) { 1319 .forward => { 1320 const next_index = @ctz(self.bits_remain) + self.bit_offset; 1321 self.bits_remain &= self.bits_remain - 1; 1322 return next_index; 1323 }, 1324 .reverse => { 1325 const leading_zeroes = @clz(self.bits_remain); 1326 const top_bit = (@bitSizeOf(MaskInt) - 1) - leading_zeroes; 1327 const no_top_bit_mask = (@as(MaskInt, 1) << @as(ShiftInt, @intCast(top_bit))) - 1; 1328 self.bits_remain &= no_top_bit_mask; 1329 return top_bit + self.bit_offset; 1330 }, 1331 } 1332 } 1333 1334 // Load the next word. Don't call this if there 1335 // isn't a next word. If the next word is the 1336 // last word, mask off the padding bits so we 1337 // don't visit them. 1338 inline fn nextWord(self: *Self, comptime is_first_word: bool) void { 1339 var word = switch (direction) { 1340 .forward => self.words_remain[0], 1341 .reverse => self.words_remain[self.words_remain.len - 1], 1342 }; 1343 switch (kind) { 1344 .set => {}, 1345 .unset => { 1346 word = ~word; 1347 if ((direction == .reverse and is_first_word) or 1348 (direction == .forward and self.words_remain.len == 1)) 1349 { 1350 word &= self.last_word_mask; 1351 } 1352 }, 1353 } 1354 switch (direction) { 1355 .forward => self.words_remain = self.words_remain[1..], 1356 .reverse => self.words_remain.len -= 1, 1357 } 1358 self.bits_remain = word; 1359 } 1360 }; 1361 } 1362 1363 /// A range of indices within a bitset. 1364 pub const Range = struct { 1365 /// The index of the first bit of interest. 1366 start: usize, 1367 /// The index immediately after the last bit of interest. 1368 end: usize, 1369 }; 1370 1371 // ---------------- Tests ----------------- 1372 1373 const testing = std.testing; 1374 1375 fn testEql(empty: anytype, full: anytype, len: usize) !void { 1376 try testing.expect(empty.eql(empty)); 1377 try testing.expect(full.eql(full)); 1378 switch (len) { 1379 0 => { 1380 try testing.expect(empty.eql(full)); 1381 try testing.expect(full.eql(empty)); 1382 }, 1383 else => { 1384 try testing.expect(!empty.eql(full)); 1385 try testing.expect(!full.eql(empty)); 1386 }, 1387 } 1388 } 1389 1390 fn testSubsetOf(empty: anytype, full: anytype, even: anytype, odd: anytype, len: usize) !void { 1391 try testing.expect(empty.subsetOf(empty)); 1392 try testing.expect(empty.subsetOf(full)); 1393 try testing.expect(full.subsetOf(full)); 1394 switch (len) { 1395 0 => { 1396 try testing.expect(even.subsetOf(odd)); 1397 try testing.expect(odd.subsetOf(even)); 1398 }, 1399 1 => { 1400 try testing.expect(!even.subsetOf(odd)); 1401 try testing.expect(odd.subsetOf(even)); 1402 }, 1403 else => { 1404 try testing.expect(!even.subsetOf(odd)); 1405 try testing.expect(!odd.subsetOf(even)); 1406 }, 1407 } 1408 } 1409 1410 fn testSupersetOf(empty: anytype, full: anytype, even: anytype, odd: anytype, len: usize) !void { 1411 try testing.expect(full.supersetOf(full)); 1412 try testing.expect(full.supersetOf(empty)); 1413 try testing.expect(empty.supersetOf(empty)); 1414 switch (len) { 1415 0 => { 1416 try testing.expect(even.supersetOf(odd)); 1417 try testing.expect(odd.supersetOf(even)); 1418 }, 1419 1 => { 1420 try testing.expect(even.supersetOf(odd)); 1421 try testing.expect(!odd.supersetOf(even)); 1422 }, 1423 else => { 1424 try testing.expect(!even.supersetOf(odd)); 1425 try testing.expect(!odd.supersetOf(even)); 1426 }, 1427 } 1428 } 1429 1430 fn testBitSet(a: anytype, b: anytype, len: usize) !void { 1431 try testing.expectEqual(len, a.capacity()); 1432 try testing.expectEqual(len, b.capacity()); 1433 1434 { 1435 var i: usize = 0; 1436 while (i < len) : (i += 1) { 1437 a.setValue(i, i & 1 == 0); 1438 b.setValue(i, i & 2 == 0); 1439 } 1440 } 1441 1442 try testing.expectEqual((len + 1) / 2, a.count()); 1443 try testing.expectEqual((len + 3) / 4 + (len + 2) / 4, b.count()); 1444 1445 { 1446 var iter = a.iterator(.{}); 1447 var i: usize = 0; 1448 while (i < len) : (i += 2) { 1449 try testing.expectEqual(@as(?usize, i), iter.next()); 1450 } 1451 try testing.expectEqual(@as(?usize, null), iter.next()); 1452 try testing.expectEqual(@as(?usize, null), iter.next()); 1453 try testing.expectEqual(@as(?usize, null), iter.next()); 1454 } 1455 a.toggleAll(); 1456 { 1457 var iter = a.iterator(.{}); 1458 var i: usize = 1; 1459 while (i < len) : (i += 2) { 1460 try testing.expectEqual(@as(?usize, i), iter.next()); 1461 } 1462 try testing.expectEqual(@as(?usize, null), iter.next()); 1463 try testing.expectEqual(@as(?usize, null), iter.next()); 1464 try testing.expectEqual(@as(?usize, null), iter.next()); 1465 } 1466 1467 { 1468 var iter = b.iterator(.{ .kind = .unset }); 1469 var i: usize = 2; 1470 while (i < len) : (i += 4) { 1471 try testing.expectEqual(@as(?usize, i), iter.next()); 1472 if (i + 1 < len) { 1473 try testing.expectEqual(@as(?usize, i + 1), iter.next()); 1474 } 1475 } 1476 try testing.expectEqual(@as(?usize, null), iter.next()); 1477 try testing.expectEqual(@as(?usize, null), iter.next()); 1478 try testing.expectEqual(@as(?usize, null), iter.next()); 1479 } 1480 1481 { 1482 var i: usize = 0; 1483 while (i < len) : (i += 1) { 1484 try testing.expectEqual(i & 1 != 0, a.isSet(i)); 1485 try testing.expectEqual(i & 2 == 0, b.isSet(i)); 1486 } 1487 } 1488 1489 a.setUnion(b.*); 1490 { 1491 var i: usize = 0; 1492 while (i < len) : (i += 1) { 1493 try testing.expectEqual(i & 1 != 0 or i & 2 == 0, a.isSet(i)); 1494 try testing.expectEqual(i & 2 == 0, b.isSet(i)); 1495 } 1496 1497 i = len; 1498 var set = a.iterator(.{ .direction = .reverse }); 1499 var unset = a.iterator(.{ .kind = .unset, .direction = .reverse }); 1500 while (i > 0) { 1501 i -= 1; 1502 if (i & 1 != 0 or i & 2 == 0) { 1503 try testing.expectEqual(@as(?usize, i), set.next()); 1504 } else { 1505 try testing.expectEqual(@as(?usize, i), unset.next()); 1506 } 1507 } 1508 try testing.expectEqual(@as(?usize, null), set.next()); 1509 try testing.expectEqual(@as(?usize, null), set.next()); 1510 try testing.expectEqual(@as(?usize, null), set.next()); 1511 try testing.expectEqual(@as(?usize, null), unset.next()); 1512 try testing.expectEqual(@as(?usize, null), unset.next()); 1513 try testing.expectEqual(@as(?usize, null), unset.next()); 1514 } 1515 1516 a.toggleSet(b.*); 1517 { 1518 try testing.expectEqual(len / 4, a.count()); 1519 1520 var i: usize = 0; 1521 while (i < len) : (i += 1) { 1522 try testing.expectEqual(i & 1 != 0 and i & 2 != 0, a.isSet(i)); 1523 try testing.expectEqual(i & 2 == 0, b.isSet(i)); 1524 if (i & 1 == 0) { 1525 a.set(i); 1526 } else { 1527 a.unset(i); 1528 } 1529 } 1530 } 1531 1532 a.setIntersection(b.*); 1533 { 1534 try testing.expectEqual((len + 3) / 4, a.count()); 1535 1536 var i: usize = 0; 1537 while (i < len) : (i += 1) { 1538 try testing.expectEqual(i & 1 == 0 and i & 2 == 0, a.isSet(i)); 1539 try testing.expectEqual(i & 2 == 0, b.isSet(i)); 1540 } 1541 } 1542 1543 a.toggleSet(a.*); 1544 { 1545 var iter = a.iterator(.{}); 1546 try testing.expectEqual(@as(?usize, null), iter.next()); 1547 try testing.expectEqual(@as(?usize, null), iter.next()); 1548 try testing.expectEqual(@as(?usize, null), iter.next()); 1549 try testing.expectEqual(@as(usize, 0), a.count()); 1550 } 1551 { 1552 var iter = a.iterator(.{ .direction = .reverse }); 1553 try testing.expectEqual(@as(?usize, null), iter.next()); 1554 try testing.expectEqual(@as(?usize, null), iter.next()); 1555 try testing.expectEqual(@as(?usize, null), iter.next()); 1556 try testing.expectEqual(@as(usize, 0), a.count()); 1557 } 1558 1559 const test_bits = [_]usize{ 1560 0, 1, 2, 3, 4, 5, 6, 7, 9, 10, 11, 22, 31, 32, 63, 64, 1561 66, 95, 127, 160, 192, 1000, 1562 }; 1563 for (test_bits) |i| { 1564 if (i < a.capacity()) { 1565 a.set(i); 1566 } 1567 } 1568 1569 for (test_bits) |i| { 1570 if (i < a.capacity()) { 1571 try testing.expectEqual(@as(?usize, i), a.findFirstSet()); 1572 try testing.expectEqual(@as(?usize, i), a.toggleFirstSet()); 1573 } 1574 } 1575 try testing.expectEqual(@as(?usize, null), a.findFirstSet()); 1576 try testing.expectEqual(@as(?usize, null), a.findLastSet()); 1577 try testing.expectEqual(@as(?usize, null), a.toggleFirstSet()); 1578 try testing.expectEqual(@as(?usize, null), a.findFirstSet()); 1579 try testing.expectEqual(@as(?usize, null), a.findLastSet()); 1580 try testing.expectEqual(@as(?usize, null), a.toggleFirstSet()); 1581 try testing.expectEqual(@as(usize, 0), a.count()); 1582 1583 a.setRangeValue(.{ .start = 0, .end = len }, false); 1584 try testing.expectEqual(@as(usize, 0), a.count()); 1585 1586 a.setRangeValue(.{ .start = 0, .end = len }, true); 1587 try testing.expectEqual(len, a.count()); 1588 1589 a.setRangeValue(.{ .start = 0, .end = len }, false); 1590 a.setRangeValue(.{ .start = 0, .end = 0 }, true); 1591 try testing.expectEqual(@as(usize, 0), a.count()); 1592 1593 a.setRangeValue(.{ .start = len, .end = len }, true); 1594 try testing.expectEqual(@as(usize, 0), a.count()); 1595 1596 if (len >= 1) { 1597 a.setRangeValue(.{ .start = 0, .end = len }, false); 1598 a.setRangeValue(.{ .start = 0, .end = 1 }, true); 1599 try testing.expectEqual(@as(usize, 1), a.count()); 1600 try testing.expect(a.isSet(0)); 1601 1602 a.setRangeValue(.{ .start = 0, .end = len }, false); 1603 a.setRangeValue(.{ .start = 0, .end = len - 1 }, true); 1604 try testing.expectEqual(len - 1, a.count()); 1605 try testing.expect(!a.isSet(len - 1)); 1606 1607 a.setRangeValue(.{ .start = 0, .end = len }, false); 1608 a.setRangeValue(.{ .start = 1, .end = len }, true); 1609 try testing.expectEqual(@as(usize, len - 1), a.count()); 1610 try testing.expect(!a.isSet(0)); 1611 1612 a.setRangeValue(.{ .start = 0, .end = len }, false); 1613 a.setRangeValue(.{ .start = len - 1, .end = len }, true); 1614 try testing.expectEqual(@as(usize, 1), a.count()); 1615 try testing.expect(a.isSet(len - 1)); 1616 1617 if (len >= 4) { 1618 a.setRangeValue(.{ .start = 0, .end = len }, false); 1619 a.setRangeValue(.{ .start = 1, .end = len - 2 }, true); 1620 try testing.expectEqual(@as(usize, len - 3), a.count()); 1621 try testing.expect(!a.isSet(0)); 1622 try testing.expect(a.isSet(1)); 1623 try testing.expect(a.isSet(len - 3)); 1624 try testing.expect(!a.isSet(len - 2)); 1625 try testing.expect(!a.isSet(len - 1)); 1626 } 1627 } 1628 } 1629 1630 fn fillEven(set: anytype, len: usize) void { 1631 var i: usize = 0; 1632 while (i < len) : (i += 1) { 1633 set.setValue(i, i & 1 == 0); 1634 } 1635 } 1636 1637 fn fillOdd(set: anytype, len: usize) void { 1638 var i: usize = 0; 1639 while (i < len) : (i += 1) { 1640 set.setValue(i, i & 1 == 1); 1641 } 1642 } 1643 1644 fn testPureBitSet(comptime Set: type) !void { 1645 const empty = Set.empty; 1646 const full = Set.full; 1647 1648 const even = even: { 1649 var bit_set = Set.empty; 1650 fillEven(&bit_set, Set.bit_length); 1651 break :even bit_set; 1652 }; 1653 1654 const odd = odd: { 1655 var bit_set = Set.empty; 1656 fillOdd(&bit_set, Set.bit_length); 1657 break :odd bit_set; 1658 }; 1659 1660 try testSubsetOf(empty, full, even, odd, Set.bit_length); 1661 try testSupersetOf(empty, full, even, odd, Set.bit_length); 1662 1663 try testing.expect(empty.complement().eql(full)); 1664 try testing.expect(full.complement().eql(empty)); 1665 try testing.expect(even.complement().eql(odd)); 1666 try testing.expect(odd.complement().eql(even)); 1667 1668 try testing.expect(empty.unionWith(empty).eql(empty)); 1669 try testing.expect(empty.unionWith(full).eql(full)); 1670 try testing.expect(full.unionWith(full).eql(full)); 1671 try testing.expect(full.unionWith(empty).eql(full)); 1672 try testing.expect(even.unionWith(odd).eql(full)); 1673 try testing.expect(odd.unionWith(even).eql(full)); 1674 1675 try testing.expect(empty.intersectWith(empty).eql(empty)); 1676 try testing.expect(empty.intersectWith(full).eql(empty)); 1677 try testing.expect(full.intersectWith(full).eql(full)); 1678 try testing.expect(full.intersectWith(empty).eql(empty)); 1679 try testing.expect(even.intersectWith(odd).eql(empty)); 1680 try testing.expect(odd.intersectWith(even).eql(empty)); 1681 1682 try testing.expect(empty.xorWith(empty).eql(empty)); 1683 try testing.expect(empty.xorWith(full).eql(full)); 1684 try testing.expect(full.xorWith(full).eql(empty)); 1685 try testing.expect(full.xorWith(empty).eql(full)); 1686 try testing.expect(even.xorWith(odd).eql(full)); 1687 try testing.expect(odd.xorWith(even).eql(full)); 1688 1689 try testing.expect(empty.differenceWith(empty).eql(empty)); 1690 try testing.expect(empty.differenceWith(full).eql(empty)); 1691 try testing.expect(full.differenceWith(full).eql(empty)); 1692 try testing.expect(full.differenceWith(empty).eql(full)); 1693 try testing.expect(full.differenceWith(odd).eql(even)); 1694 try testing.expect(full.differenceWith(even).eql(odd)); 1695 } 1696 1697 fn testStaticBitSet(comptime Set: type) !void { 1698 var a = Set.empty; 1699 var b = Set.full; 1700 try testing.expectEqual(@as(usize, 0), a.count()); 1701 try testing.expectEqual(@as(usize, Set.bit_length), b.count()); 1702 1703 try testEql(a, b, Set.bit_length); 1704 try testBitSet(&a, &b, Set.bit_length); 1705 1706 try testPureBitSet(Set); 1707 } 1708 1709 test Integer { 1710 try testStaticBitSet(Integer(0)); 1711 try testStaticBitSet(Integer(1)); 1712 try testStaticBitSet(Integer(2)); 1713 try testStaticBitSet(Integer(5)); 1714 try testStaticBitSet(Integer(8)); 1715 try testStaticBitSet(Integer(32)); 1716 try testStaticBitSet(Integer(64)); 1717 try testStaticBitSet(Integer(127)); 1718 } 1719 1720 test Array { 1721 inline for (.{ 0, 1, 2, 31, 32, 33, 63, 64, 65, 254, 500, 3000 }) |size| { 1722 try testStaticBitSet(Array(u8, size)); 1723 try testStaticBitSet(Array(u16, size)); 1724 try testStaticBitSet(Array(u32, size)); 1725 try testStaticBitSet(Array(u64, size)); 1726 try testStaticBitSet(Array(u128, size)); 1727 } 1728 } 1729 1730 test Dynamic { 1731 const allocator = std.testing.allocator; 1732 var a: Dynamic = try .initEmpty(allocator, 300); 1733 try testing.expectEqual(@as(usize, 0), a.count()); 1734 a.deinit(allocator); 1735 1736 a = try .initEmpty(allocator, 0); 1737 defer a.deinit(allocator); 1738 for ([_]usize{ 1, 2, 31, 32, 33, 0, 65, 64, 63, 500, 254, 3000 }) |size| { 1739 const old_len = a.capacity(); 1740 1741 var empty = try a.clone(allocator); 1742 defer empty.deinit(allocator); 1743 try testing.expectEqual(old_len, empty.capacity()); 1744 var i: usize = 0; 1745 while (i < old_len) : (i += 1) { 1746 try testing.expectEqual(a.isSet(i), empty.isSet(i)); 1747 } 1748 1749 a.toggleSet(a); // zero a 1750 empty.toggleSet(empty); 1751 1752 try a.resize(allocator, size, true); 1753 try empty.resize(allocator, size, false); 1754 1755 if (size > old_len) { 1756 try testing.expectEqual(size - old_len, a.count()); 1757 } else { 1758 try testing.expectEqual(@as(usize, 0), a.count()); 1759 } 1760 try testing.expectEqual(@as(usize, 0), empty.count()); 1761 1762 var full: Dynamic = try .initFull(allocator, size); 1763 defer full.deinit(allocator); 1764 try testing.expectEqual(@as(usize, size), full.count()); 1765 1766 try testEql(empty, full, size); 1767 { 1768 var even: Dynamic = try .initEmpty(allocator, size); 1769 defer even.deinit(allocator); 1770 fillEven(&even, size); 1771 1772 var odd: Dynamic = try .initEmpty(allocator, size); 1773 defer odd.deinit(allocator); 1774 fillOdd(&odd, size); 1775 1776 try testSubsetOf(empty, full, even, odd, size); 1777 try testSupersetOf(empty, full, even, odd, size); 1778 } 1779 try testBitSet(&a, &full, size); 1780 } 1781 } 1782 1783 test DynamicManaged { 1784 const allocator = std.testing.allocator; 1785 var a: DynamicManaged = try .initEmpty(allocator, 300); 1786 try testing.expectEqual(@as(usize, 0), a.count()); 1787 a.deinit(); 1788 1789 a = try .initEmpty(allocator, 0); 1790 defer a.deinit(); 1791 for ([_]usize{ 1, 2, 31, 32, 33, 0, 65, 64, 63, 500, 254, 3000 }) |size| { 1792 const old_len = a.capacity(); 1793 1794 var tmp = try a.clone(allocator); 1795 defer tmp.deinit(); 1796 try testing.expectEqual(old_len, tmp.capacity()); 1797 var i: usize = 0; 1798 while (i < old_len) : (i += 1) { 1799 try testing.expectEqual(a.isSet(i), tmp.isSet(i)); 1800 } 1801 1802 a.toggleSet(a); // zero a 1803 tmp.toggleSet(tmp); // zero tmp 1804 1805 try a.resize(size, true); 1806 try tmp.resize(size, false); 1807 1808 if (size > old_len) { 1809 try testing.expectEqual(size - old_len, a.count()); 1810 } else { 1811 try testing.expectEqual(@as(usize, 0), a.count()); 1812 } 1813 try testing.expectEqual(@as(usize, 0), tmp.count()); 1814 1815 var b: DynamicManaged = try .initFull(allocator, size); 1816 defer b.deinit(); 1817 try testing.expectEqual(@as(usize, size), b.count()); 1818 1819 try testEql(tmp, b, size); 1820 try testBitSet(&a, &b, size); 1821 } 1822 } 1823 1824 test Static { 1825 try testing.expectEqual(Integer(0), Static(0)); 1826 try testing.expectEqual(Integer(5), Static(5)); 1827 try testing.expectEqual(Integer(@bitSizeOf(usize)), Static(@bitSizeOf(usize))); 1828 try testing.expectEqual(Array(usize, @bitSizeOf(usize) + 1), Static(@bitSizeOf(usize) + 1)); 1829 try testing.expectEqual(Array(usize, 500), Static(500)); 1830 } 1831