Crate rust_lapper 

This module provides a simple data structure for fast interval searches.

Features

• Extremely fast overlap queries on both ordinary genomic datasets and datasets with long intervals that engulf many shorter intervals.
• Extremely fast in order queries through the cursor-based seek() method.
• Extremely fast intersection counts based on the BITS algorithm
• NEON acceleration on AArch64, runtime-detected AVX2 on x86-64, and an exact scalar fallback everywhere else.
• Parallel friendly. Queries are on an immutable structure, even for seek().
• Consumer / Adapter paradigm. Iterators are returned and serve as the main API for interacting with the Lapper.

Details:

         0  1  2  3  4  5  6  7  8  9  10 11
[0, 10)  X  X  X  X  X  X  X  X  X  X
[2, 5)         X  X  X
[3, 8)            X  X  X  X  X
[3, 8)            X  X  X  X  X
[3, 8)            X  X  X  X  X
[3, 8)            X  X  X  X  X
[5, 9)                  X  X  X  X
[8, 11)                          X  X  X

Query:  [8, 11)
Answer: [0, 10), [5, 9), [8, 11)

Most interaction with this crate will be through the Lapper struct. The main methods are Lapper::find, Lapper::seek, and Lapper::count. find() handles independent queries, seek() reuses a caller-owned cursor when query starts arrive in order, and count() is used when only the number of overlaps is needed.

Ranges are half-open: [start, stop). Two ranges overlap when interval.start < query.stop and interval.stop > query.start, so adjacent ranges such as [0, 10) and [10, 20) do not overlap. This matches the usual zero-based genomic coordinate system. Signed and unsigned primitive coordinates are supported.

Lapper does not use an interval tree. It keeps intervals sorted by start and builds a small index over fixed blocks of 32 intervals. A prefix maximum finds the first block that could overlap; each block’s minimum and maximum end positions then prove whether the block is a miss or a dense prefix, and a next-greater link skips runs of blocks that cannot overlap. Mixed blocks produce an exact 32-bit overlap mask with NEON, AVX2, or the scalar fallback. Mask bits are drained from low to high, so results remain borrowed and in ascending start order.

The same block algorithm handles ordinary data and the old worst case where one long interval engulfs many shorter intervals. There is no workload mode to configure. merge_overlaps() remains useful when callers want merged coverage, while count() remains the independent BITS implementation and is fast regardless of interval shape.

Examples

   use rust_lapper::{Interval, Lapper};
   use std::cmp;
   type Iv = Interval<usize, u32>;

   // create some fake data
   let data: Vec<Iv> = (0..20).step_by(5).map(|x| Iv{start: x, stop: x + 2, val: 0}).collect();
   println!("{:#?}", data);

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

   assert_eq!(laps.find(6, 11).next(), Some(&Iv{start: 5, stop: 7, val: 0}));

   // Demonstration of seek function. By passing in the &mut cursor, seek can have thread local
   // cursors going
   let mut sim: usize = 0;
   let mut cursor = 0;
   // Calculate the overlap between the query and the found intervals, sum total overlap
   for i in (0..10).step_by(3) {
       sim += laps
           .seek(i, i + 2, &mut cursor)
           .map(|iv| cmp::min(i + 2, iv.stop) - cmp::max(i, iv.start))
           .sum::<usize>();
   }
   assert_eq!(sim, 4);

Structs

Interval

Represent a range from [start, stop) Inclusive start, exclusive of stop

IterDepth

Depth Iterator

IterFind

Find Iterator

IterLapper

Lapper Iterator

Lapper

Primary interval collection and query index.