class Lapper::Lapper(T)

Overview

Lapper is the primary data structure that contains the sorted Array of Interval(T)

data = (0..100).step(by: 20).map { |x| Interval(Int32).new(x, x + 10, 0) }.to_a
lapper = Lapper(Int32).new(data)

Defined in:

lapper.cr

Constructors

Instance Method Summary

Constructor Detail

def self.new(intervals : Array(Lapper::Interval(T)), cursor : Int32 = 0, max_len : Int32 = 0) #

[View source]

Instance Method Detail

def find(start : Int32, stop : Int32, ivs : Array(Lapper::Interval(T))) #

Find all intervals that overlap start .. stop. Reuses an passed in array.

data = (0..100).step(by: 5).map { |x| Interval(Int32).new(x, x + 2, 0) }.to_a
lapper = Lapper(Int32).new(data)
lapper.find(5, 11, [] of Interval(Int32)).size == 2

[View source]
def find(start : Int32, stop : Int32) #

Find all intervals that overlap start .. stop. Returns a new array for each query.

data = (0..100).step(by: 5).map { |x| Interval(Int32).new(x, x + 2, 0) }.to_a
lapper = Lapper(Int32).new(data)
lapper.find(5, 11).size == 2

[View source]
def find(start : Int32, stop : Int32, &) #

Find all intervals that overlap start .. stop. Takes a block that accepts an interval.

data = (0..100).step(by: 5).map { |x| Interval(Int32).new(x, x + 2, 0) }.to_a
lapper = Lapper(Int32).new(data)
total = 0
lapper.find(5, 11) { |iv| total += 1 }
total # => 2

[View source]
def intervals : Array(Lapper::Interval(T)) #

[View source]
def seek(start : Int32, stop : Int32, ivs : Array(Lapper::Interval(T))) #

Find all intervals that overlap start .. stop when queries are in sorted (by start) order. This variant adds to an array ref that is passed in.

data = (0..100).step(by: 5).map { |x| Interval(Int32).new(x, x + 2, 0) }.to_a
lapper = Lapper(Int32).new(data)
cursor = 0
ivs = [] of Interval(Int32)
lapper.intervals.each do |i|
  lapper.seek(i.start, i.stop, ivs)
  ivs.size == 1
end

[View source]
def seek(start : Int32, stop : Int32) #

Find all intervals that overlap start .. stop when queries are in sorted (by start) order. It uses a linear search from the last query instead of a binary search. A reference to a cursor must be passed in. This reference will be modified and should be reused in the next query. This allows seek to not need to make mutate the lapper itself and be useable across threads.

data = (0..100).step(by: 5).map { |x| Interval(Int32).new(x, x + 2, 0) }.to_a
lapper = Lapper(Int32).new(data)
cursor = 0
lapper.intervals.each do |i|
  lapper.seek(i.start, i.stop).size == 1
end

[View source]
def seek(start : Int32, stop : Int32, &) #

Find all intervals that overlap start .. stop when queries are in sorted (by start) order. This variant takes a block that will be called for each found interval.

data = (0..100).step(by: 5).map { |x| Interval(Int32).new(x, x + 2, 0) }.to_a
lapper = Lapper(Int32).new(data)
cursor = 0
lapper.intervals.each do |i|
  size = 0
  lapper.seek(i.start, i.stop) { |iv| size += 1 }
  size == 1
end

[View source]