/// Roaring-style compressed bitmaps over non-negative `Int`s: the posting /// lists of the trigram index (`search`). A set is split into containers of /// 65,536 values each (the low 16 bits), keyed by the high bits; a container /// is a sorted list while it holds at most 4,096 values and a 65,536-bit /// bitmap (a big `Int`) past that, so intersections stay cheap for both /// sparse and dense postings. Intersecting two bitmap containers is one /// `int.and`; the result drops back to a list when it gets sparse again. /// /// (After "Roaring Bitmaps" by Chambi, Lemire et al., arXiv:1402.6407, with /// a persistent list for the array container.) import std/dict.{type Dict} import std/int import std/list /// A set of non-negative `Int`s. `add` and `remove` return a new set and /// leave the old one as it was. pub opaque type Bitmap { Bitmap(containers: Dict, size: Int) } /// The values of one 16-bit container: a sorted list (at most /// `container_max()` values) or a bitmap of `container_bits()` bits with its /// population count. type Container { Arr(List), Bits(bits: Int, card: Int) } /// The most values an `Arr` holds before it becomes a `Bits`: the point /// where both take 65,536 bits. fn container_max :: -> Int { 4096 } /// The values a container covers: its key shifted left by 16. fn container_bits :: -> Int { 65536 } /// The empty set. pub fn empty :: -> Bitmap { Bitmap(dict.empty (), 0) } /// The number of values. pub fn size :: b: Bitmap -> Int { b.size } pub fn is_empty :: b: Bitmap -> Bool { b.size == 0 } /// `(array containers, bitmap containers)`: which containers the set uses, /// for tests and tuning. pub fn stats :: b: Bitmap -> (Int, Int) { dict.fold b.containers (0, 0) fn acc _ c { let (arrays, bitmaps) = acc match c { Arr(_) -> (arrays + 1, bitmaps), Bits(_, _) -> (arrays, bitmaps + 1) } } } /// `b` with `id` added (no change if it is present). Panics on a negative /// `id`. pub fn add :: b: Bitmap id: Int -> Bitmap { if id < 0 { panic "search/bitmap.add: negative id {id}" } else { let high = id / container_bits () let low = id % container_bits () let ( containers , added ) = match dict.get b.containers high { None -> (dict.insert b.containers high (Arr([low])), True) , Some(c) -> { let (c2, added) = add_to c low (dict.insert b.containers high c2, added) } } Bitmap(containers, if added { b.size + 1 } else { b.size }) } } /// `b` without `id` (no change if it is absent). pub fn remove :: b: Bitmap id: Int -> Bitmap { if id < 0 { b } else { let high = id / container_bits () let low = id % container_bits () match dict.get b.containers high { None -> b , Some(c) -> { let (c2, removed) = remove_from c low if !removed { b } else if card c2 == 0 { Bitmap(dict.remove b.containers high, b.size - 1) } else { Bitmap(dict.insert b.containers high c2, b.size - 1) } } } } } pub fn contains :: b: Bitmap id: Int -> Bool { if id < 0 { False } else { match dict.get b.containers (id / container_bits ()) { None -> False, Some(c) -> member c (id % container_bits ()) } } } /// The values in both, container by container. pub fn intersect :: a: Bitmap b: Bitmap -> Bitmap { walk (dict.to_list a.containers) (dict.to_list b.containers) [] 0 } fn walk :: xs: List<(Int, Container)> ys: List<(Int, Container)> acc: List<(Int, Container)> size: Int -> Bitmap { match (xs, ys) { ( [(ka, ca), ..xs1] , [(kb, cb), ..ys1] ) -> if ka == kb { let c = intersect_container ca cb if card c == 0 { walk xs1 ys1 acc size } else { walk xs1 ys1 [(ka, c), ..acc] (size + card c) } } else if ka < kb { walk xs1 ys acc size } else { walk xs ys1 acc size } , _ -> Bitmap(dict.from_list (list.reverse acc), size) } } /// The values, ascending. pub fn to_list :: b: Bitmap -> List { use (high, c) <- list.flat_map (dict.to_list b.containers) list.map (values c) fn low { high * container_bits () + low } } /// A set of `ids` (duplicates are ignored). Panics on a negative id. pub fn from_list :: ids: List -> Bitmap { if list.any ids fn id { id < 0 } { panic "search/bitmap.from_list: negative id" } else { from_sorted_list (list.sort ids) } } /// A set of `ids`, which must be ascending (duplicates are dropped): /// [`from_list`] without the sort. Panics on a negative id or one below /// its predecessor. pub fn from_sorted_list :: ids: List -> Bitmap { group (dedupe_checked ids (0 - 1)) [] 0 } /// `xs` without duplicates; panics unless `xs` is ascending, every id /// above `prev`. fn dedupe_checked :: xs: List prev: Int -> List { match xs { [] -> [] , [ x , ..rest ] -> if x < 0 { panic "search/bitmap.from_sorted_list: negative id" } else if x < prev { panic "search/bitmap.from_sorted_list: ids not ascending" } else if x == prev { dedupe_checked rest prev } else { [x, ..dedupe_checked rest x] } } } /// Containers of the sorted distinct `ids`, grouped by their high bits. fn group :: ids: List acc: List<(Int, Container)> size: Int -> Bitmap { match ids { [] -> Bitmap(dict.from_list (list.reverse acc), size) , [id, ..] -> { let high = id / container_bits () let (run, rest) = span_run ids high [] let c = container_of run group rest [(high, c), ..acc] (size + card c) } } } /// The longest prefix of `ids` (sorted) with high bits `high`, and the rest. fn span_run :: ids: List high: Int acc: List -> (List, List) { match ids { [id, ..rest] if id / container_bits () == high -> span_run rest high [id % container_bits (), ..acc] , _ -> (list.reverse acc, ids) } } /// A container of the sorted distinct low bits `run`. fn container_of :: run: List -> Container { if list.length run > container_max () { bits_of_list run } else { Arr(run) } } // ---- containers ---------------------------------------------------------- fn card :: c: Container -> Int { match c { Arr(xs) -> list.length xs, Bits(_, n) -> n } } fn member :: c: Container v: Int -> Bool { match c { Arr(xs) -> sorted_member xs v, Bits(bits, _) -> int.bit bits v } } fn sorted_member :: xs: List v: Int -> Bool { match xs { [] -> False , [ x , ..rest ] -> if x == v { True } else if x > v { False } else { sorted_member rest v } } } /// The container's values, ascending. fn values :: c: Container -> List { match c { Arr(xs) -> xs, Bits(bits, _) -> bits_to_list bits } } /// `c` with `v`, and whether that changed it. fn add_to :: c: Container v: Int -> (Container, Bool) { match c { Arr(xs) -> { let (ys, added) = insert_sorted xs v if added && list.length ys > container_max () { (bits_of_list ys, True) } else { (Arr(ys), added) } } , Bits(bits, n) -> if int.bit bits v { (c, False) } else { (Bits(int.or bits (int.shift_left 1 v), n + 1), True) } } } /// `c` without `v`, and whether that changed it. fn remove_from :: c: Container v: Int -> (Container, Bool) { match c { Arr(xs) -> { let (ys, removed) = remove_sorted xs v (Arr(ys), removed) } , Bits ( bits , n ) -> if int.bit bits v { let bits2 = int.and bits (int.not (int.shift_left 1 v)) if n - 1 <= container_max () { (Arr(bits_to_list bits2), True) } else { (Bits(bits2, n - 1), True) } } else { (c, False) } } } fn intersect_container :: a: Container b: Container -> Container { match (a, b) { (Arr(xs), Arr(ys)) -> Arr(intersect_lists xs ys) , (Arr(xs), Bits(bits, _)) -> Arr(list.filter xs fn v { int.bit bits v }) , (Bits(bits, _), Arr(ys)) -> Arr(list.filter ys fn v { int.bit bits v }) , (Bits(b1, _), Bits(b2, _)) -> { let bits = int.and b1 b2 let n = popcount bits if n <= container_max () { Arr(bits_to_list bits) } else { Bits(bits, n) } } } } /// The values in both sorted lists, ascending. fn intersect_lists :: xs: List ys: List -> List { merge xs ys [] } fn merge :: xs: List ys: List acc: List -> List { match (xs, ys) { ([x, ..xs1], [y, ..ys1]) -> if x == y { merge xs1 ys1 [x, ..acc] } else if x < y { merge xs1 ys acc } else { merge xs ys1 acc } , _ -> list.reverse acc } } /// `xs` (sorted) with `v`, and whether that inserted it. fn insert_sorted :: xs: List v: Int -> (List, Bool) { match xs { [] -> ([v], True) , [x, ..rest] -> if v < x { ([v, ..xs], True) } else if v == x { (xs, False) } else { let (ys, inserted) = insert_sorted rest v ([x, ..ys], inserted) } } } /// `xs` (sorted) without `v`, and whether that removed it. fn remove_sorted :: xs: List v: Int -> (List, Bool) { match xs { [] -> ([], False) , [x, ..rest] -> if v == x { (rest, True) } else if v < x { (xs, False) } else { let (ys, removed) = remove_sorted rest v ([x, ..ys], removed) } } } // ---- bitmaps as big Ints --------------------------------------------------- /// The bits set in `n`. fn popcount :: n: Int -> Int { popcount_acc n 0 } fn popcount_acc :: n: Int acc: Int -> Int { if n == 0 { acc } else { // Clear the lowest set bit. popcount_acc (int.and n (n - 1)) (acc + 1) } } /// The positions of the set bits of `n`, ascending. fn bits_to_list :: bits: Int -> List { bits_up bits [] } fn bits_up :: bits: Int acc: List -> List { if bits == 0 { list.reverse acc } else { // The lowest set bit of `bits` alone (two's complement). let low = int.and bits (0 - bits) bits_up (int.xor bits low) [int.bit_length low - 1, ..acc] } } /// A bitmap container of the sorted `xs` (more than `container_max()`). fn bits_of_list :: xs: List -> Container { Bits(list.fold xs 0 fn b v { int.or b (int.shift_left 1 v) }, list.length xs) }