rust-lapper

Documentation Crates.io

rust-lapper 2 is currently in beta. To try it, use 2.0.0-beta.1 explicitly; Cargo will not select it from a version = "2" requirement.

This was originally a Rust port of Brent Pedersen's nim-lapper. find() and seek() return lazy borrowed iterators in ascending start order, so normal iterator adaptors work without collecting results first.

All stored intervals and query ranges use half-open [start, stop) semantics. Lapper keeps its intervals sorted by start and builds a fixed 32-interval block index that can skip regions proven not to overlap. Mixed blocks use NEON on AArch64, runtime-detected AVX2 on x86-64, and an exact scalar fallback elsewhere. The same algorithm handles both ordinary and pathological datasets with long intervals that engulf many shorter intervals.

The count() method uses the BITS algorithm to count overlaps with two binary searches.

API and algorithm compatibility

The block index and SIMD backends are private implementation details: there is no mode flag, alternate query method, or architecture-specific API. Existing call patterns for find(), seek(), count(), cov(), set_cov(), merge_overlaps(), depth(), union_and_intersect(), union(), and intersect() retain their range semantics and return types. count() remains the independent BITS implementation; methods that use find() or seek() internally automatically share the exact indexed query path.

NEON and AVX2 cover u8, i8, u16, i16, u32, i32, u64, i64, usize, and isize. The same block algorithm uses exact scalar masks for u128, i128, custom PrimInt types, and partial vector tails.

Minimum Supported Rust Version

rust-lapper 2 supports Rust 1.59 and newer. Rust 1.59 is the first stable release that provides the AArch64 intrinsics used by the NEON query backend.

Query coordinates must be 'static so private dispatch code can use TypeId before reinterpreting primitive integer slices for SIMD. This includes every primitive integer and ordinary owned custom numeric type; it does not require a Lapper value to live for the entire program. Non-primitive PrimInt types use the scalar mask implementation. The bound is the API-breaking change that makes this a major release.

Mutation

Use insert() and merge_overlaps() for coordinate or structural changes so the private query index is rebuilt. Directly changing Lapper::intervals coordinates or length leaves derived metadata stale; changing payload values is safe.

Serde Support

rust-lapper supports serialization with serde for Lapper and Interval objects:

[dependencies]
rust-lapper = { version = "2.0.0-beta.1", features = ["with_serde"] }

See examples/serde.rs for a brief example.

Benchmarks

The retained v2 release measurements, raw samples, compiler flags, and pinned competitor revisions live in lapper_bakeoff. On an AMD Ryzen 9 3950X with AVX2, the new implementation improved total time over rust-lapper 1.3.0 by 37.30%, 98.89%, and 34.64% on the three retained article cases. All implementations returned identical overlap counts.

Benchmark results are workload- and hardware-specific; use the linked harness and raw data when making comparisons.

Example

use rust_lapper::{Interval, Lapper};

type Iv = Interval<usize, u32>;
fn main() {
    // create some fake data
    let data: Vec<Iv> = vec![
        Iv {
            start: 70,
            stop: 120,
            val: 0,
        }, // a long interval
        Iv {
            start: 10,
            stop: 15,
            val: 0,
        },
        Iv {
            start: 10,
            stop: 15,
            val: 0,
        }, // exact overlap
        Iv {
            start: 12,
            stop: 15,
            val: 0,
        }, // inner overlap
        Iv {
            start: 14,
            stop: 16,
            val: 0,
        }, // overlap end
        Iv {
            start: 40,
            stop: 45,
            val: 0,
        },
        Iv {
            start: 50,
            stop: 55,
            val: 0,
        },
        Iv {
            start: 60,
            stop: 65,
            val: 0,
        },
        Iv {
            start: 68,
            stop: 71,
            val: 0,
        }, // overlap start
        Iv {
            start: 70,
            stop: 75,
            val: 0,
        },
    ];

    // make lapper structure
    let mut lapper = Lapper::new(data);

    // Find every interval that overlaps [11, 15).
    // For queries in nondecreasing start order, seek() can reuse a caller-owned cursor.
    assert_eq!(
        lapper.find(11, 15).collect::<Vec<&Iv>>(),
        vec![
            &Iv {
                start: 10,
                stop: 15,
                val: 0
            },
            &Iv {
                start: 10,
                stop: 15,
                val: 0
            }, // exact overlap
            &Iv {
                start: 12,
                stop: 15,
                val: 0
            }, // inner overlap
            &Iv {
                start: 14,
                stop: 16,
                val: 0
            }, // overlap end
        ]
    );
    assert_eq!(lapper.count(11, 15), 4);

    // Merge overlapping regions to simplify queries that only depend on whether
    // any interval overlaps.
    lapper.merge_overlaps();
    assert_eq!(
        lapper.find(11, 15).collect::<Vec<&Iv>>(),
        vec![&Iv {
            start: 10,
            stop: 16,
            val: 0
        },]
    );

    // Get the number of positions covered by the interval collection.
    assert_eq!(lapper.cov(), 73);

    // Get the union and intersection lengths of two interval collections.
    let data = vec![
        Iv {
            start: 5,
            stop: 15,
            val: 0,
        },
        Iv {
            start: 48,
            stop: 80,
            val: 0,
        },
    ];
    let (union, intersect) = lapper.union_and_intersect(&Lapper::new(data));
    assert_eq!(union, 88);
    assert_eq!(intersect, 27);

    // Get the depth at each position covered by the lapper
    for interval in lapper.depth().filter(|x| x.val > 2) {
        println!(
            "Depth at {} - {}: {}",
            interval.start, interval.stop, interval.val
        );
    }

}

Release Notes

• 2.0.0-beta.1: Begin the rust-lapper 2 beta with a portable SIMD block index, signed coordinates, Rust 1.59 as the MSRV, and the I: 'static coordinate bound.
• 1.3.0: Add the sort_unstable feature flag for allocation-sensitive sorting thanks to @jameslkingsley.
• 1.1.0: Added insert functionality thanks to @zaporter
• 1.0.0: Add serde support via the with_serde feature flag
• 0.5.0: Make Interval start/stop generic
• 0.4.3: Remove leftover print statement
• 0.4.2: Bugfix in to update starts/stops vectors when overlaps merged
• 0.4.0: Addition of the BITS count algorithm.