🥮 mooncakes.io

    moonbit-roaring

    Pure MoonBit 32-bit Roaring Bitmap indexes

    roaring
    bitmap
    index
    set
    Download zip
    Author
    Version
    0.1.0
    License
    Apache-2.0
    Repository
    Last updated
    2 hours ago
    Downloads
    1

    #MoonBit Roaring

    MoonBit Roaring is a pure-MoonBit compressed integer-set library. It partitions non-negative Int values by their high 16 bits and represents each partition as a sorted array, a fixed bitmap, or consecutive runs. It is an index data structure, not a database, search engine, or permission service.

    #Why

    Search filters, access-control sets, and analytical cohorts repeatedly need union, intersection, difference, rank, and select over integer identifiers. A plain Array[Int] wastes work for dense values; a flat bitset wastes memory for sparse values. Roaring-style containers choose a representation per block.

    #Use

    let left = @roaring.RoaringBitmap::from_array([1, 2, 3, 70_000]).unwrap()
    let right = @roaring.RoaringBitmap::from_array([2, 3, 80_000]).unwrap()
    assert_eq(left.intersection(right).to_array(), [2, 3])

    Run checks and the example:

    moon check --deny-warn
moon test --deny-warn
moon bench --release --deny-warn
moon run cmd/main

    #Implemented API boundaries

    • from_range, add_range, and remove_range use half-open ranges and reject negative and inverted endpoints. Constructing or adding a range longer than 1,000,000 values is rejected because it materializes new members; removing a range has no such cap because it only scans members already stored.
    • add_all and remove_all validate a whole batch before returning a new, immutable bitmap; invalid input returns an error rather than silently changing the batch.
    • from_ranges, add_ranges, and remove_ranges accept batches of half-open intervals and normalize overlap. to_ranges returns a canonical interval cover; it explicitly rejects the unrepresentable half-open endpoint after the maximum Int.
    • cursor().next() traverses values in ascending order without exposing the internal container representation, loading one container at a time rather than copying the complete bitmap at cursor creation.
    • union_all, intersection_all, and xor_all aggregate an array of bitmap operands with explicit empty-input identities, for multi-filter queries.
    • RoaringBuilder stages validated values, batches, and bounded inserted ranges, then performs one normalization at finish; this is the preferred ingestion path when values arrive incrementally.
    • encode_words and decode_words implement a deterministic, versioned word encoding: [1, cardinality, ..strictly_ascending_values]. The decoder rejects bad versions, incorrect lengths, negative values, duplicates, and non-canonical order. This is deliberately not CRoaring binary format.
    • encode_run_words and decode_run_words provide a second deterministic format for interval-heavy data: [3, cardinality, run_count, start, length,...]. Decoding is bounded to 1,000,000 materialized members and rejects overflow, overlap, and adjacent runs that would be non-canonical.
    • Union, intersection, difference, and xor merge high-16-bit blocks first and dispatch matching keys to container-local operations. When both containers are dense bitmaps, the operation runs word-wise and downshifts a sparse result back to Array/Run storage.
    • Point membership, extrema, rank, and select stay at block/container level. contains_range, next_at_or_after, and previous_at_or_before build range and navigation queries from those primitives without allocating a temporary range bitmap.
    • stats and block_stats expose cardinality and selected container kinds for diagnostics, without exposing mutable container storage.
    • diff_to produces an immutable RoaringPatch containing additions and removals. A patch can be applied, inverted, and inspected for the values it touches, which supports incremental index and cache updates.

    The test suite includes fixed boundary tests plus a deterministic 64-case property corpus covering commutativity, idempotence, cancellation, and encode/decode round trips. roaring_bench.mbt contains reproducible dense block workloads for moon bench; its numbers are measurements for the local toolchain and machine, not portable performance claims.

    #Scope and provenance

    This is an independent MoonBit implementation inspired by the Roaring Bitmap data-structure family and the public design of CRoaring. No CRoaring source, test corpus, binary format, SIMD routine, or API is copied here. CRoaring is Apache-2.0 licensed; see https://github.com/RoaringBitmap/CRoaring.

    The initial API accepts non-negative MoonBit Int values. It intentionally does not claim the complete unsigned-32-bit API until a public UInt API and cross-target boundary tests are implemented.

    #License

    Apache-2.0; the complete text is in LICENSE.

    BitmapBatchReport

    source
    pub(all) struct BitmapBatchReport {
      operand_count : Int
      total_cardinality : Int
      union_cardinality : Int
      intersection_cardinality : Int
      duplicate_occurrences : Int
      empty_operands : Int
    }

    Aggregate facts about a batch of bitmap operands.

    BitmapCatalog

    source
    pub struct BitmapCatalog {
      entries : Array[BitmapEntry]
    }

    Small immutable catalog for faceted search and rule evaluation.

    BitmapCatalog::evaluate

    source
    fn BitmapCatalog::evaluate(self : BitmapCatalog, query : CatalogQuery, universe : RoaringBitmap) -> RoaringBitmap

    BitmapCatalog::evaluate_traced

    source
    fn BitmapCatalog::evaluate_traced(self : BitmapCatalog, query : CatalogQuery, universe : RoaringBitmap) -> CatalogQueryResult

    Evaluate a query and report missing keys separately from an empty bitmap.

    BitmapCatalog::execute_with_trace

    source
    fn BitmapCatalog::execute_with_trace(self : BitmapCatalog, query : CatalogQuery, universe : RoaringBitmap) -> QueryExecutionTrace

    Evaluate a catalog query and record its observable planning facts.

    BitmapCatalog::get

    source
    fn BitmapCatalog::get(self : BitmapCatalog, key : Int) -> RoaringBitmap?

    BitmapCatalog::keys

    source
    fn BitmapCatalog::keys(self : BitmapCatalog) -> Array[Int]

    Keys in deterministic ascending order.

    BitmapCatalog::len

    source
    fn BitmapCatalog::len(self : BitmapCatalog) -> Int

    Number of indexed labels.

    BitmapCatalog::new

    source

    BitmapCatalog::remove

    source
    fn BitmapCatalog::remove(self : BitmapCatalog, key : Int) -> BitmapCatalog

    BitmapCatalog::upsert

    source
    fn BitmapCatalog::upsert(self : BitmapCatalog, key : Int, bitmap : RoaringBitmap) -> BitmapCatalog

    BitmapComparison

    source
    pub(all) struct BitmapComparison {
      relation : SetRelation
      left_cardinality : Int
      right_cardinality : Int
      common_cardinality : Int
      left_only_cardinality : Int
      right_only_cardinality : Int
      union_cardinality : Int
    }

    Exact comparison facts for two bitmaps, suitable for reporting decisions.

    BitmapEntry

    source
    pub(all) struct BitmapEntry {
      key : Int
      bitmap : RoaringBitmap
    }

    One numeric label and the bitmap indexed by that label.

    BitmapFrame

    source
    pub(all) struct BitmapFrame {
      format : CodecFormat
      payload : Array[Int]
      checksum : Int
    }

    A self-checking stable word frame around a supported codec payload.

    BitmapFrame::decode

    source
    fn BitmapFrame::decode(self : BitmapFrame) -> Result[RoaringBitmap, FrameError]

    Validate a frame checksum before decoding it.

    BitmapFrame::with_payload

    source
    fn BitmapFrame::with_payload(self : BitmapFrame, payload : Array[Int]) -> BitmapFrame

    Replace a frame payload for corruption-testing or transport adapters.

    BitmapOperation

    source
    pub(all) enum BitmapOperation {
      Add(Int)
      Remove(Int)
      AddRange(Int, Int)
      RemoveRange(Int, Int)
      AddAll(Array[Int])
      RemoveAll(Array[Int])
    }

    A replayable immutable bitmap operation.

    BitmapOperation::apply

    source

    Apply one operation to an immutable bitmap.

    BitmapPlan

    source
    pub(all) enum BitmapPlan {
      Source(RoaringBitmap)
      Union(BitmapPlan, BitmapPlan)
      Intersection(BitmapPlan, BitmapPlan)
      Difference(BitmapPlan, BitmapPlan)
      Xor(BitmapPlan, BitmapPlan)
      Take(BitmapPlan, Int)
      Drop(BitmapPlan, Int)
    }

    A composable immutable set-algebra execution plan.

    BitmapPlan::describe

    source
    fn BitmapPlan::describe(self : BitmapPlan) -> String

    Render a stable compact prefix description for diagnostics.

    BitmapPlan::estimated_cardinality

    source
    fn BitmapPlan::estimated_cardinality(self : BitmapPlan) -> Int

    BitmapPlan::evaluate

    source
    fn BitmapPlan::evaluate(self : BitmapPlan) -> RoaringBitmap

    BitmapPlan::stats

    source

    Count nodes, depth, and source leaves without materializing a bitmap.

    BitmapPlanStats

    source
    pub(all) struct BitmapPlanStats {
      nodes : Int
      depth : Int
      sources : Int
    }

    Static shape information for a plan before execution.

    BitmapProfile

    source
    pub(all) struct BitmapProfile {
      cardinality : Int
      minimum : Int?
      maximum : Int?
      span : Int
      block_count : Int
    }

    Compact summary of the numeric extent of a bitmap.

    CatalogQuery

    source
    pub(all) enum CatalogQuery {
      Key(Int)
      Any(Array[CatalogQuery])
      All(Array[CatalogQuery])
      Not(CatalogQuery)
      AtLeast(Int, Array[CatalogQuery])
    }

    Boolean expression evaluated against a catalog and an explicit universe.

    CatalogQuery::referenced_keys

    source
    fn CatalogQuery::referenced_keys(self : CatalogQuery) -> Array[Int]

    Collect keys in deterministic depth-first order, retaining repeats.

    CatalogQuery::result_upper_bound

    source
    fn CatalogQuery::result_upper_bound(self : CatalogQuery, catalog : BitmapCatalog, universe : RoaringBitmap) -> Int

    Return a conservative result upper bound before evaluating a query. The bound is the universe cardinality for any expression containing Not.

    CatalogQuery::stats

    source

    Inspect the structural shape of a catalog query.

    CatalogQueryResult

    source
    pub(all) struct CatalogQueryResult {
      bitmap : RoaringBitmap
      missing_keys : Array[Int]
    }

    Evaluation output paired with catalog keys that were absent at lookup time.

    CatalogQueryStats

    source
    pub(all) struct CatalogQueryStats {
      nodes : Int
      depth : Int
      key_references : Int
    }

    Static query metadata available without evaluating bitmap operands.

    CodecError

    source
    pub(all) enum CodecError {
      MissingHeader
      UnsupportedVersion(Int)
      InvalidCount(Int)
      InvalidPayloadLength(Int, Int)
      InvalidValue(Int)
      InvalidRunLength(Int)
      CardinalityMismatch(Int, Int)
      PayloadTooLarge(Int)
      NonCanonicalPayload
    }

    Errors for the versioned word encoding.

    CodecFormat

    source
    pub(all) enum CodecFormat {
      PlainWords
      RunWords
    }

    Stable word encodings supported by this module.

    ContainerKind

    source
    pub(all) enum ContainerKind {
      Array
      Bitmap
      Run
    }

    Public classification of the representation selected for one high block.

    FrameError

    source
    pub(all) enum FrameError {
      Codec(CodecError)
      ChecksumMismatch(Int, Int)
    }

    Errors for framed transport validation.

    IntRange

    source
    pub(all) struct IntRange {
      start : Int
      end : Int
    }

    A validated half-open interval used for batch range input and output.

    JournalCodecError

    source
    pub(all) enum JournalCodecError {
      MissingHeader
      UnsupportedVersion(Int)
      InvalidOperationCount(Int)
      InvalidTag(Int)
      TruncatedPayload(Int)
      InvalidBatchCount(Int)
    }

    Parse failures for the versioned operation-journal word format.

    JournalRangeError

    source
    pub(all) enum JournalRangeError {
      InvalidIndex(Int, Int)
    }

    Invalid operation-log position requests.

    QueryExecutionTrace

    source
    pub(all) struct QueryExecutionTrace {
      result : RoaringBitmap
      nodes : Int
      depth : Int
      requested_keys : Array[Int]
      resolved_keys : Array[Int]
      missing_keys : Array[Int]
      result_cardinality : Int
    }

    Read-only execution information for a catalog query.

    RoaringBitmap

    source
    pub struct RoaringBitmap {
      blocks : Array[RoaringBlock]
    }

    high 16 bits; each block chooses an array, bitmap, or run representation.

    RoaringBitmap::add

    source
    fn RoaringBitmap::add(self : RoaringBitmap, value : Int) -> Result[RoaringBitmap, RoaringError]

    Insert one value. Insertion is idempotent and returns a new bitmap.

    RoaringBitmap::add_all

    source
    fn RoaringBitmap::add_all(self : RoaringBitmap, values : Array[Int]) -> Result[RoaringBitmap, RoaringError]

    Add a batch atomically: invalid input leaves no partial result exposed.

    RoaringBitmap::add_range

    source
    fn RoaringBitmap::add_range(self : RoaringBitmap, start : Int, end : Int) -> Result[RoaringBitmap, RoaringError]

    Add every value in the half-open range [start, end).

    RoaringBitmap::add_ranges

    source
    fn RoaringBitmap::add_ranges(self : RoaringBitmap, ranges : Array[IntRange]) -> Result[RoaringBitmap, RoaringError]

    Add every value described by a validated batch of half-open ranges.

    RoaringBitmap::block_stats

    source

    Describe the selected representation of every block in ascending key order. This is intended for observability and test tooling, not mutation.

    RoaringBitmap::cardinality

    source
    fn RoaringBitmap::cardinality(self : RoaringBitmap) -> Int

    Number of distinct values stored in the bitmap.

    RoaringBitmap::containment_gaps

    source
    fn RoaringBitmap::containment_gaps(self : RoaringBitmap, other : RoaringBitmap) -> (Int, Int)

    Return exact containment gaps: (missing_from_self, missing_from_other).

    RoaringBitmap::contains

    source
    fn RoaringBitmap::contains(self : RoaringBitmap, value : Int) -> Bool

    True when value belongs to this bitmap.

    RoaringBitmap::contains_range

    source
    fn RoaringBitmap::contains_range(self : RoaringBitmap, start : Int, end : Int) -> Result[Bool, RoaringError]

    True only when every value in the half-open range belongs to this bitmap. Unlike construction, this query never materializes the range.

    RoaringBitmap::count_in_range

    source
    fn RoaringBitmap::count_in_range(self : RoaringBitmap, start : Int, end : Int) -> Result[Int, RoaringError]

    Count values in the half-open range without materializing a new bitmap.

    RoaringBitmap::cursor

    source

    Start a stable ascending cursor.

    RoaringBitmap::density_parts

    source
    fn RoaringBitmap::density_parts(self : RoaringBitmap) -> (Int, Int)

    Return occupied and total positions in the bitmap's inclusive numeric span.

    RoaringBitmap::diff_to

    source
    fn RoaringBitmap::diff_to(self : RoaringBitmap, target : RoaringBitmap) -> RoaringPatch

    Compute the exact additions and removals needed to reach target.

    RoaringBitmap::difference

    source
    fn RoaringBitmap::difference(self : RoaringBitmap, other : RoaringBitmap) -> RoaringBitmap

    Set difference self - other.

    RoaringBitmap::difference_cardinality

    source
    fn RoaringBitmap::difference_cardinality(self : RoaringBitmap, other : RoaringBitmap) -> Int

    Number of values in self not present in other.

    RoaringBitmap::drop

    source
    fn RoaringBitmap::drop(self : RoaringBitmap, count : Int) -> RoaringBitmap

    Discard the first count values in ascending order. Negative counts are a no-op.

    RoaringBitmap::encode

    source
    fn RoaringBitmap::encode(self : RoaringBitmap, format : CodecFormat) -> Result[Array[Int], CodecError]

    RoaringBitmap::encode_run_words

    source
    fn RoaringBitmap::encode_run_words(self : RoaringBitmap) -> Result[Array[Int], CodecError]

    Encode consecutive values as stable runs: [3, cardinality, run_count,start_0, length_0, ...].

    This format is compact for interval-heavy data. Its explicit size ceiling prevents a tiny hostile input from requesting an unbounded allocation.

    RoaringBitmap::encode_words

    source
    fn RoaringBitmap::encode_words(self : RoaringBitmap) -> Array[Int]

    It is intentionally simple and platform-neutral; it is not CRoaring format.

    RoaringBitmap::filter

    source
    fn RoaringBitmap::filter(self : RoaringBitmap, predicate : (Int) -> Bool) -> RoaringBitmap

    Keep values satisfying predicate and preserve normalized ordering.

    RoaringBitmap::frame

    source
    fn RoaringBitmap::frame(self : RoaringBitmap, format : CodecFormat) -> Result[BitmapFrame, CodecError]

    Encode a bitmap and record a deterministic checksum of the resulting words.

    RoaringBitmap::from_array

    source
    fn RoaringBitmap::from_array(values : Array[Int]) -> Result[RoaringBitmap, RoaringError]

    Build a normalized bitmap from non-negative integers.

    RoaringBitmap::from_range

    source
    fn RoaringBitmap::from_range(start : Int, end : Int) -> Result[RoaringBitmap, RoaringError]

    Construct every value in the validated half-open range.

    RoaringBitmap::from_ranges

    source
    fn RoaringBitmap::from_ranges(ranges : Array[IntRange]) -> Result[RoaringBitmap, RoaringError]

    Construct a bitmap from a batch of half-open ranges.

    The combined materialized length is capped by the same safety limit as a single range. Overlap is accepted and normalized.

    RoaringBitmap::intersection

    source
    fn RoaringBitmap::intersection(self : RoaringBitmap, other : RoaringBitmap) -> RoaringBitmap

    Intersection of two bitmaps.

    RoaringBitmap::intersection_cardinality

    source
    fn RoaringBitmap::intersection_cardinality(self : RoaringBitmap, other : RoaringBitmap) -> Int

    Number of values shared by both bitmaps.

    RoaringBitmap::intersects

    source
    fn RoaringBitmap::intersects(self : RoaringBitmap, other : RoaringBitmap) -> Bool

    RoaringBitmap::is_disjoint

    source
    fn RoaringBitmap::is_disjoint(self : RoaringBitmap, other : RoaringBitmap) -> Bool

    True when no member is shared by two bitmaps.

    RoaringBitmap::is_empty

    source
    fn RoaringBitmap::is_empty(self : RoaringBitmap) -> Bool

    RoaringBitmap::is_proper_subset_of

    source
    fn RoaringBitmap::is_proper_subset_of(self : RoaringBitmap, other : RoaringBitmap) -> Bool

    True when self is contained in but not equal to other.

    RoaringBitmap::is_proper_superset_of

    source
    fn RoaringBitmap::is_proper_superset_of(self : RoaringBitmap, other : RoaringBitmap) -> Bool

    True when self contains but is not equal to other.

    RoaringBitmap::is_subset_of

    source
    fn RoaringBitmap::is_subset_of(self : RoaringBitmap, other : RoaringBitmap) -> Bool

    RoaringBitmap::jaccard_parts

    source
    fn RoaringBitmap::jaccard_parts(self : RoaringBitmap, other : RoaringBitmap) -> (Int, Int)

    Return numerator and denominator for exact Jaccard similarity. Callers can choose their own floating-point representation if required.

    RoaringBitmap::map_values

    source
    fn RoaringBitmap::map_values(self : RoaringBitmap, mapper : (Int) -> Int) -> Result[RoaringBitmap, RoaringError]

    Map values and normalize the mapped result. A negative mapped value is rejected instead of silently dropping it.

    RoaringBitmap::maximum

    source
    fn RoaringBitmap::maximum(self : RoaringBitmap) -> Int?

    RoaringBitmap::minimum

    source
    fn RoaringBitmap::minimum(self : RoaringBitmap) -> Int?

    RoaringBitmap::new

    source

    Create an empty bitmap.

    RoaringBitmap::next_at_or_after

    source
    fn RoaringBitmap::next_at_or_after(self : RoaringBitmap, value : Int) -> Int?

    Return the first member greater than or equal to value.

    RoaringBitmap::overlap_coefficient_parts

    source
    fn RoaringBitmap::overlap_coefficient_parts(self : RoaringBitmap, other : RoaringBitmap) -> (Int, Int)

    Return the shared fraction as exact (shared, smaller_set_size) parts. An empty smaller set has denominator zero instead of an invented ratio.

    RoaringBitmap::overlap_parts

    source
    fn RoaringBitmap::overlap_parts(self : RoaringBitmap, other : RoaringBitmap) -> (Int, Int, Int, Int)

    Return exact intersection, left-only, right-only, and union cardinalities.

    RoaringBitmap::partition

    source
    fn RoaringBitmap::partition(self : RoaringBitmap, predicate : (Int) -> Bool) -> (RoaringBitmap, RoaringBitmap)

    Split values into matching and non-matching bitmaps.

    RoaringBitmap::previous_at_or_before

    source
    fn RoaringBitmap::previous_at_or_before(self : RoaringBitmap, value : Int) -> Int?

    Return the last member less than or equal to value.

    RoaringBitmap::profile

    source

    Inspect cardinality and extent without exposing container internals.

    RoaringBitmap::quantile

    source
    fn RoaringBitmap::quantile(self : RoaringBitmap, numerator : Int, denominator : Int) -> Result[Int?, RoaringError]

    Select the value at an exact rational quantile in [0, denominator].

    RoaringBitmap::rank

    source
    fn RoaringBitmap::rank(self : RoaringBitmap, value : Int) -> Int

    Number of values less than or equal to value.

    RoaringBitmap::relation_to

    source
    fn RoaringBitmap::relation_to(self : RoaringBitmap, other : RoaringBitmap) -> SetRelation

    Classify two sets using their set differences.

    RoaringBitmap::remove

    source
    fn RoaringBitmap::remove(self : RoaringBitmap, value : Int) -> RoaringBitmap

    Remove one value. Removing an absent value is a no-op.

    RoaringBitmap::remove_all

    source
    fn RoaringBitmap::remove_all(self : RoaringBitmap, values : Array[Int]) -> Result[RoaringBitmap, RoaringError]

    Remove every listed value; unknown values are ignored.

    RoaringBitmap::remove_range

    source
    fn RoaringBitmap::remove_range(self : RoaringBitmap, start : Int, end : Int) -> Result[RoaringBitmap, RoaringError]

    Remove every value in the half-open range [start, end).

    RoaringBitmap::remove_ranges

    source
    fn RoaringBitmap::remove_ranges(self : RoaringBitmap, ranges : Array[IntRange]) -> Result[RoaringBitmap, RoaringError]

    Remove every value described by a validated batch of half-open ranges.

    RoaringBitmap::sample_evenly

    source
    fn RoaringBitmap::sample_evenly(self : RoaringBitmap, count : Int) -> Array[Int]

    Return a stable, evenly distributed sample in ascending order.

    RoaringBitmap::sample_stride

    source
    fn RoaringBitmap::sample_stride(self : RoaringBitmap, stride : Int) -> Array[Int]

    Sample each strideth ordinal. Non-positive strides return an empty sample.

    RoaringBitmap::select

    source
    fn RoaringBitmap::select(self : RoaringBitmap, index : Int) -> Int?

    The zero-based indexth value, if present.

    RoaringBitmap::shift

    source
    fn RoaringBitmap::shift(self : RoaringBitmap, offset : Int) -> Result[RoaringBitmap, RoaringError]

    Shift every value by offset, rejecting shifts that leave the supported non-negative Int domain.

    RoaringBitmap::slice_positions

    source
    fn RoaringBitmap::slice_positions(self : RoaringBitmap, start : Int, end : Int) -> Result[RoaringBitmap, RoaringError]

    Select values whose zero-based positions belong to [start, end).

    RoaringBitmap::stats

    source

    RoaringBitmap::symmetric_difference_cardinality

    source
    fn RoaringBitmap::symmetric_difference_cardinality(self : RoaringBitmap, other : RoaringBitmap) -> Int

    Number of values present in exactly one of the two bitmaps.

    RoaringBitmap::take

    source
    fn RoaringBitmap::take(self : RoaringBitmap, count : Int) -> RoaringBitmap

    Keep the first count values in ascending order. Negative counts are empty.

    RoaringBitmap::to_array

    source
    fn RoaringBitmap::to_array(self : RoaringBitmap) -> Array[Int]

    Return the values in ascending order.

    RoaringBitmap::to_ranges

    source
    fn RoaringBitmap::to_ranges(self : RoaringBitmap) -> Result[Array[IntRange], RoaringError]

    Return a normalized interval cover of the values in this bitmap.

    A bitmap containing the maximum Int cannot be represented as a half-open interval because its end endpoint would overflow, and returns an error.

    RoaringBitmap::union

    source

    Union of two bitmaps.

    RoaringBitmap::union_cardinality

    source
    fn RoaringBitmap::union_cardinality(self : RoaringBitmap, other : RoaringBitmap) -> Int

    Number of distinct values present in either bitmap.

    RoaringBitmap::validate

    source
    fn RoaringBitmap::validate(self : RoaringBitmap) -> Result[Unit, ValidationError]

    Verify representation invariants without changing this bitmap. This is useful at trust boundaries and in differential tests.

    RoaringBitmap::xor

    source

    Symmetric difference of two bitmaps.

    RoaringBlock

    source
    type RoaringBlock

    One high-16-bit partition of a bitmap.

    RoaringBlockStats

    source
    pub(all) struct RoaringBlockStats {
      key : Int
      cardinality : Int
      kind : ContainerKind
    }

    Read-only diagnostics for one high-16-bit block.

    RoaringBuilder

    source
    pub struct RoaringBuilder {
      values : Array[Int]
    }

    A mutable staging area for bulk ingestion followed by one normalization.

    RoaringBuilder::finish

    source

    Normalize all staged values and return an immutable bitmap.

    RoaringBuilder::new

    source

    Create an empty builder.

    RoaringBuilder::push

    source
    fn RoaringBuilder::push(self : RoaringBuilder, value : Int) -> Result[Unit, RoaringError]

    Stage one non-negative value.

    RoaringBuilder::push_all

    source
    fn RoaringBuilder::push_all(self : RoaringBuilder, values : Array[Int]) -> Result[Unit, RoaringError]

    Stage a batch atomically: invalid input appends nothing.

    RoaringBuilder::push_range

    source
    fn RoaringBuilder::push_range(self : RoaringBuilder, start : Int, end : Int) -> Result[Unit, RoaringError]

    Stage a range subject to the normal insertion materialization limit.

    RoaringBuilder::staged_len

    source
    fn RoaringBuilder::staged_len(self : RoaringBuilder) -> Int

    Number of values staged, including duplicates that finish will normalize.

    RoaringCursor

    source
    pub struct RoaringCursor {
      bitmap : RoaringBitmap
      block_index : Int
      lows : Array[Int]
      low_index : Int
      yielded : Int
    }

    Cursor for ascending traversal without exposing container internals.

    RoaringCursor::next

    source
    fn RoaringCursor::next(self : RoaringCursor) -> (Int?, RoaringCursor)

    Return the next value and a successor cursor. The original cursor is unchanged.

    RoaringCursor::remaining

    source
    fn RoaringCursor::remaining(self : RoaringCursor) -> Int

    Number of values not yet returned by this cursor.

    RoaringError

    source
    pub(all) enum RoaringError {
      NegativeValue(Int)
      InvalidRange(Int, Int)
      RangeTooLarge(Int)
      RangeEndpointOverflow(Int)
    }

    Input validation failures at the non-negative integer boundary.

    RoaringOperationLog

    source
    pub struct RoaringOperationLog {
      checkpoint : RoaringBitmap
      operations : Array[BitmapOperation]
    }

    A checkpoint plus ordered operations that have not yet been compacted.

    RoaringOperationLog::append

    source

    Append one operation without changing the checkpoint.

    RoaringOperationLog::append_all

    source

    Append a batch while preserving its declared order.

    RoaringOperationLog::cardinality_history

    source
    fn RoaringOperationLog::cardinality_history(self : RoaringOperationLog) -> Array[Int]

    Return cumulative cardinalities after each replayed operation, including the checkpoint.

    RoaringOperationLog::checkpoint

    source

    Return the checkpoint without replaying pending operations.

    RoaringOperationLog::checkpoint_frame

    source
    fn RoaringOperationLog::checkpoint_frame(self : RoaringOperationLog, format : CodecFormat) -> Result[BitmapFrame, RoaringError]

    Encode the current replayed state as a checked snapshot frame.

    RoaringOperationLog::compact

    source

    Materialize a new checkpoint and clear the replay queue.

    RoaringOperationLog::discard_pending

    source

    Discard all pending operations and restore the original checkpoint state.

    RoaringOperationLog::encode_words

    source
    fn RoaringOperationLog::encode_words(self : RoaringOperationLog) -> Array[Int]

    Encode a replayable log as [1, operation_count, tag, payload...] words. Tags 1-6 represent Add, Remove, AddRange, RemoveRange, AddAll, RemoveAll.

    RoaringOperationLog::is_compacted

    source
    fn RoaringOperationLog::is_compacted(self : RoaringOperationLog) -> Bool

    True when this log is already represented solely by its checkpoint.

    RoaringOperationLog::len

    source

    Number of unapplied operations.

    RoaringOperationLog::new

    source

    Start an empty log from a known checkpoint.

    RoaringOperationLog::operation_at

    source
    fn RoaringOperationLog::operation_at(self : RoaringOperationLog, index : Int) -> Result[BitmapOperation, JournalRangeError]

    Return one operation by zero-based index.

    RoaringOperationLog::operations

    source

    Return the ordered operations as an isolated copy for audit sinks.

    RoaringOperationLog::pending_patch

    source

    Compute the checkpoint-to-current patch without changing this log.

    RoaringOperationLog::replay

    source

    Replay all operations in order. Failure returns no partial bitmap.

    RoaringOperationLog::replay_prefix

    source
    fn RoaringOperationLog::replay_prefix(self : RoaringOperationLog, count : Int) -> Result[RoaringBitmap, JournalRangeError]

    Replay exactly the first count operations from this log checkpoint.

    RoaringOperationLog::split_at

    source

    Split a log into its retained prefix and a suffix rebased on the prefix state.

    RoaringPatch

    source
    pub struct RoaringPatch {
      additions : RoaringBitmap
      removals : RoaringBitmap
    }

    An immutable delta that transforms one bitmap into another.

    RoaringPatch::added_cardinality

    source
    fn RoaringPatch::added_cardinality(self : RoaringPatch) -> Int

    Number of values added by this patch.

    RoaringPatch::apply

    source

    Apply this patch. Removals are performed before additions.

    RoaringPatch::invert

    source
    fn RoaringPatch::invert(self : RoaringPatch) -> RoaringPatch

    Return a patch that reverses this patch when applied to its target state.

    RoaringPatch::is_empty

    source
    fn RoaringPatch::is_empty(self : RoaringPatch) -> Bool

    True when the patch makes no change.

    RoaringPatch::removed_cardinality

    source
    fn RoaringPatch::removed_cardinality(self : RoaringPatch) -> Int

    Number of values removed by this patch.

    RoaringPatch::touched

    source
    fn RoaringPatch::touched(self : RoaringPatch) -> RoaringBitmap

    Values touched by this patch, regardless of direction.

    RoaringSnapshot

    source
    pub struct RoaringSnapshot {
      generation : Int
      bitmap : RoaringBitmap
    }

    An immutable bitmap state identified by a monotonically increasing generation.

    RoaringSnapshot::advance

    source

    Apply a patch and advance exactly one generation.

    RoaringSnapshot::apply_patch_envelope

    source
    fn RoaringSnapshot::apply_patch_envelope(self : RoaringSnapshot, envelope : SnapshotPatchEnvelope) -> Result[RoaringSnapshot, SnapshotError]

    Apply a checked patch only when its base generation matches this snapshot.

    RoaringSnapshot::at

    source
    fn RoaringSnapshot::at(generation : Int, bitmap : RoaringBitmap) -> Result[RoaringSnapshot, SnapshotError]

    Create a snapshot at an explicit non-negative generation.

    RoaringSnapshot::bitmap

    source

    Return the immutable bitmap held by this snapshot.

    RoaringSnapshot::diff_to

    source

    Produce the exact patch needed to reach another snapshot.

    RoaringSnapshot::envelope

    source
    fn RoaringSnapshot::envelope(self : RoaringSnapshot, format : CodecFormat) -> Result[SnapshotEnvelope, CodecError]

    Wrap this snapshot in an integrity-checked frame.

    RoaringSnapshot::generation

    source
    fn RoaringSnapshot::generation(self : RoaringSnapshot) -> Int

    Return the snapshot generation.

    RoaringSnapshot::new

    source

    Create generation zero from a bitmap.

    RoaringSnapshot::patch_envelope

    source
    fn RoaringSnapshot::patch_envelope(self : RoaringSnapshot, target : RoaringSnapshot, format : CodecFormat) -> Result[SnapshotPatchEnvelope, CodecError]

    Encode the exact delta from this snapshot to target.

    RoaringStats

    source
    pub(all) struct RoaringStats {
      block_count : Int
      array_blocks : Int
      bitmap_blocks : Int
      run_blocks : Int
      cardinality : Int
    }

    SetRelation

    source
    pub(all) enum SetRelation {
      Equal
      ProperSubset
      ProperSuperset
      Overlap
      Disjoint
    }

    The mutually exclusive relation between two integer sets.

    SnapshotEnvelope

    source
    pub(all) struct SnapshotEnvelope {
      generation : Int
      frame : BitmapFrame
    }

    A transportable snapshot envelope with its self-checking bitmap frame.

    SnapshotEnvelope::decode

    source

    Recover a snapshot after validating its transport frame.

    SnapshotEnvelope::generation

    source
    fn SnapshotEnvelope::generation(self : SnapshotEnvelope) -> Int

    Return envelope generation without decoding its payload.

    SnapshotError

    source
    pub(all) enum SnapshotError {
      InvalidGeneration(Int)
      GenerationOverflow(Int)
      StaleGeneration(Int, Int)
      Frame(FrameError)
    }

    Errors at snapshot generation and frame boundaries.

    SnapshotPatchEnvelope

    source
    pub(all) struct SnapshotPatchEnvelope {
      base_generation : Int
      target_generation : Int
      additions : BitmapFrame
      removals : BitmapFrame
    }

    A checked patch between two exact snapshot generations.

    SnapshotPatchEnvelope::base_generation

    source
    fn SnapshotPatchEnvelope::base_generation(self : SnapshotPatchEnvelope) -> Int

    SnapshotPatchEnvelope::target_generation

    source
    fn SnapshotPatchEnvelope::target_generation(self : SnapshotPatchEnvelope) -> Int

    ValidationError

    source
    pub(all) enum ValidationError {
      UnsortedBlockKey(Int, Int)
      EmptyBlock(Int)
      InvalidLowValue(Int, Int)
      UnsortedLowValue(Int, Int, Int)
      BitmapCardinalityMismatch(Int, Int)
      RunCardinalityMismatch(Int, Int)
      InvalidRun(Int, Int, Int)
    }

    Structural invariant failures reported by validate.

    analyze_batch

    source
    fn analyze_batch(bitmaps : Array[RoaringBitmap]) -> BitmapBatchReport

    Analyze a batch using exact set algebra. Empty input has empty union and intersection by the library's documented aggregate identity.

    compare_bitmaps

    source
    fn compare_bitmaps(left : RoaringBitmap, right : RoaringBitmap) -> BitmapComparison

    Compare two bitmaps once and retain all basic cardinality facts.

    decode

    source
    fn decode(format : CodecFormat, words : Array[Int]) -> Result[RoaringBitmap, CodecError]

    decode_auto

    source
    fn decode_auto(words : Array[Int]) -> Result[RoaringBitmap, CodecError]

    Decode a supported payload using its own version header.

    decode_operation_log

    source
    fn decode_operation_log(checkpoint : RoaringBitmap, words : Array[Int]) -> Result[RoaringOperationLog, JournalCodecError]

    Decode a stable journal payload with a caller-provided checkpoint.

    decode_run_words

    source
    fn decode_run_words(words : Array[Int]) -> Result[RoaringBitmap, CodecError]

    Decode canonical run words and reject overlaps, adjacency, overflow, and payloads exceeding the documented safety ceiling.

    decode_words

    source
    fn decode_words(words : Array[Int]) -> Result[RoaringBitmap, CodecError]

    Decode and reject malformed or non-canonical word payloads.

    detect_codec

    source
    fn detect_codec(words : Array[Int]) -> Result[CodecFormat, CodecError]

    Inspect a stable word header without decoding its payload.

    equal_within

    source
    fn equal_within(left : RoaringBitmap, right : RoaringBitmap, universe : RoaringBitmap) -> Bool

    True when equality holds after restricting both bitmaps to an allowed universe.

    f1_parts

    source
    fn f1_parts(actual : RoaringBitmap, expected : RoaringBitmap) -> (Int, Int)

    Return exact F1 components (two_times_common, actual_plus_expected).

    intersection_all

    source
    fn intersection_all(bitmaps : Array[RoaringBitmap]) -> RoaringBitmap

    Intersect every bitmap in bitmaps. The identity for an empty input is empty.

    overlap_with_others

    source
    fn overlap_with_others(bitmaps : Array[RoaringBitmap]) -> Array[Int]

    Return each operand's overlap count with the union of all other operands.

    precision_parts

    source
    fn precision_parts(actual : RoaringBitmap, expected : RoaringBitmap) -> (Int, Int)

    Return exact precision parts when actual is compared to expected.

    recall_parts

    source
    fn recall_parts(actual : RoaringBitmap, expected : RoaringBitmap) -> (Int, Int)

    Return exact recall parts when actual is compared to expected.

    transcode

    source
    fn transcode(words : Array[Int], from : CodecFormat, to : CodecFormat) -> Result[Array[Int], CodecError]

    Decode one supported format and re-encode it canonically as another.

    union_all

    source
    fn union_all(bitmaps : Array[RoaringBitmap]) -> RoaringBitmap

    Union every bitmap in bitmaps. The identity for an empty input is empty.

    values_at_least

    source
    fn values_at_least(bitmaps : Array[RoaringBitmap], threshold : Int) -> RoaringBitmap

    Return the values that appear in at least threshold operands. Threshold zero returns the union because no external universe is supplied.

    values_in_exactly_one

    source
    fn values_in_exactly_one(bitmaps : Array[RoaringBitmap]) -> RoaringBitmap

    Return values present in exactly one operand.

    xor_all

    source
    fn xor_all(bitmaps : Array[RoaringBitmap]) -> RoaringBitmap

    Symmetric-difference every bitmap in bitmaps. The empty identity is empty.

    Source Files

    Powered by MoonBit

    Site sourceReport issuePackagesBuild queueSkillsStatistics

    © 2026 mooncakes.io