package sortedseq_intersect

  1. Overview
  2. Docs

Module Sortedseq_intersect.Sorted_seq_intersectSource

Sourceval intersect_merge : 'a array -> 'a array -> 'a list

Intersection of sorted sequences, using a linear merge algorithm, with complexity O(m+n).

Sourceval intersect_merge_range : ?acc:'a list -> 'a array -> int -> int -> 'a array -> int -> int -> 'a list

Like intersect_merge, but restricted to ranges alo..hi, bb_lo..b_hi

Sourceval intersect_bisect : 'a array -> 'a array -> 'a list

Intersection of sorted sequences, using the Baeza-Yates-Salinger algorithm, with complexity O(m log(n/m)). If m is o(n/log n), this algorithm is better than linear merging, which is O(m+n) If m << n, it's better to do m binary searches in b

Sourceval intersect_bisect_range : 'a list -> 'a array -> int -> int -> 'a array -> int -> int -> 'a list

Like intersect_bisect_merge, but restricted to ranges alo..hi, bb_lo..b_hi

Sourceval intersect_bisect_adaptive : 'a array -> 'a array -> 'a list

Intersection of sorted sequences, using the adaptive Baeza-Yates-Salinger algorithm, which switches to a merge algorithm when n/m < 32. If m is o(n/log n), this algorithm is better than linear merging, which is O(m+n) If m << n, it's better to do m binary searches in b

Sourceval intersect_adaptive_range : 'a list -> 'a array -> int -> int -> 'a array -> int -> int -> 'a list

Like intersect_bisect_adaptive, but restricted to ranges alo..hi, bb_lo..b_hi