Skip to main content

LimitProvider

caps_sa

Trait LimitProvider 

Source 
pub trait LimitProvider: Sync {
    // Required method
    fn lim_at(&self, p: usize) -> usize;

    // Provided method
    fn boundary_order(
        &self,
        p_a: usize,
        lim_a: usize,
        p_b: usize,
        lim_b: usize,
    ) -> Ordering { ... }
}
Expand description

Per-suffix length provider. The merge and cascade-merge code use lp.lim_at(p) instead of text.len() - p; the LCP function itself is unchanged (the merge passes the appropriately-capped max_ctx to the existing SIMD path).

Implementations must be Sync so the rayon-parallel sort can share one provider across worker threads.

Required Methods§

Source

fn lim_at(&self, p: usize) -> usize

Logical length of the suffix starting at position p in symbols — i.e. the number of comparable symbols before the next segment boundary or end-of-text. Must be at most text.len() - p.

Provided Methods§

Source

fn boundary_order( &self, p_a: usize, lim_a: usize, p_b: usize, lim_b: usize, ) -> Ordering

Order to resolve when one or both suffixes hit their boundary before any byte of their shared prefix differs. The default is lim_a.cmp(&lim_b) — “shorter-suffix-is-smaller”, the standard generalised-SA / multi-string-SA convention, what a Vec<&str> sort with &str ordering produces.

Custom impls can override for different boundary conventions. The motivating example is STAR’s spacer-as-largest ordering: the suffix that hits a spacer first is larger, equivalently the longer-lim one is smaller, with an ascending-position tie-break when both lims coincide:

ⓘ
fn boundary_order(&self, p_a: usize, lim_a: usize,
                  p_b: usize, lim_b: usize) -> Ordering {
    lim_b.cmp(&lim_a).then(p_a.cmp(&p_b))
}

p_a / p_b are the suffix start positions in the same coordinate space the merge sees (the spacer-free text’s coordinates when invoked through *_with entries on a rustar-aligner-style spacer-free text). The default impl ignores them; impls that want a position tie-break use them.

Dyn Compatibility§

This trait is dyn compatible.

In older versions of Rust, dyn compatibility was called "object safety".

Implementors§