This module provides a simple data-structure for fast interval searches. It does not use an interval tree, instead, it operates on the assumption that most intervals are of similar length; or, more exactly, that the longest interval in the set is not long compared to the average distance between intervals. On any dataset where that is not the case, this method will not perform well. For cases where this holds true (as it often does with genomic data), we can sort by start and use binary search on the starts, accounting for the length of the longest interval. The advantage of this approach is simplicity of implementation and speed. In realistic tests queries returning the overlapping intervals are 1000 times faster than brute force and queries that merely check for the overlaps are > 5000 times faster.

The main methods are find and seek where the latter uses a cursor and is very fast for cases when the queries are sorted. This is another innovation in this library that allows an addition ~50% speed improvement when consecutive queries are known to be in sort order.

For both find and seek, if the given intervals parameter is nil, the function will return a boolean indicating if any intervals in the set overlap the query. This is much faster than modifying the intervals.

The example below shows off most of the API of Lapper.

import lapper
type myinterval = ref object
   start: int
   stop: int
   val: int
 
 proc start(m: myinterval): int {.inline.} = return m.start
 proc stop(m: myinterval): int {.inline.} = return m.stop
 proc `$`(m:myinterval): string = return "(start:$#, stop:$#, val:$#)" % [$m.start, $m.stop, $m.val]

create some fake data

var ivs = new_seq[myinterval]()
for i in countup(0, 100, 10):
  ivs.add(myinterval(start:i, stop:i + 15, val:0))

make the Lapper "data-structure"

l = lapify(ivs)
empty:seq[myinterval]

l.find(10, 20, empty)
notfound = not l.find(200, 300, empty)
assert notfound

res = new_seq[myinterval]()

find is the more general case, l.seek gives a speed benefit when consecutive queries are in order.

echo l.find(50, 70, res)
echo res
# @[(start: 40, stop: 55, val:0), (start: 50, stop: 65, val: 0), (start: 60, stop: 75, val: 0), (start: 70, stop: 85, val: 0)]
for r in res:
   r.val += 1

or we can do a function on each overlapping interval

l.each_seek(50, 60, proc(a:myinterval) = inc(a.val))

or

l.each_find(50, 60, proc(a:myinterval) = a.val += 10)

discard l.seek(50, 70, res)
echo res
# @[(start:40, stop:55, val:12), (start:50, stop:65, val:12), (start:60, stop:75, val:1)]