caps-sa 0.7.0

Cache-friendly, parallel, sample-sort-based suffix array construction (Rust port of CaPS-SA)
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94

//! Cache-friendly, parallel, sample-sort-based suffix array construction.
//!
//! This crate is a Rust port of [CaPS-SA] (Khan et al., WABI 2023), a parallel
//! and cache-friendly suffix-array constructor based on sample sort with
//! LCP-enhanced comparison.
//!
//! The crate is generic over the symbol type (`u8`, `u16`, …; any `Ord + Copy`)
//! and the index type (`u32`, `u64`; via the [`Index`] trait). It produces a
//! standard lexicographic suffix array. Callers who need a *generalized* suffix
//! array can supply a [`LimitProvider`] (for example [`SegmentedText`]) to stop
//! comparisons at string boundaries and define their boundary ordering. This
//! avoids enlarging the symbol alphabet with one distinct sentinel per input
//! string.
//!
//! Phase 1 of the port provides the **in-memory** algorithm; the external-memory
//! variant (disk-spilling buckets) is layered on top in a later phase.
//!
//! [CaPS-SA]: https://github.com/jamshed/CaPS-SA

mod ext_bucket;
mod ext_mem;
mod lcp;
mod lcp_memo;
mod limits;
mod sample_sort;

pub use ext_mem::{
    BuildError, ExtMemOpts, build_ext_mem, build_ext_mem_for_filter, build_ext_mem_for_filter_with,
    build_ext_mem_for_positions, build_ext_mem_for_positions_with, build_ext_mem_with,
    build_in_memory_sample_sort, build_in_memory_sample_sort_for_positions,
    build_in_memory_sample_sort_for_positions_with, build_in_memory_sample_sort_with,
    try_build_ext_mem, try_build_ext_mem_for_filter, try_build_ext_mem_for_filter_with,
    try_build_ext_mem_for_positions, try_build_ext_mem_for_positions_with, try_build_ext_mem_with,
    try_build_in_memory_sample_sort, try_build_in_memory_sample_sort_for_positions,
    try_build_in_memory_sample_sort_for_positions_with, try_build_in_memory_sample_sort_with,
};
pub use lcp::{LcpDispatch, Symbol, lcp, lcp_scalar, lcp_u8, suffix_cmp};
pub use lcp_memo::{GeometricMemoizationConfig, LcpMemoizationPolicy};
pub use limits::{LimitProvider, PlainText, SegmentedText};
pub use sample_sort::{
    Opts, build_in_memory, build_in_memory_for_positions, build_in_memory_for_positions_with,
    build_in_memory_for_positions_with_opts, build_in_memory_with, build_in_memory_with_opts,
};

/// Trait implemented by integer types usable as suffix array indices.
///
/// Provided for `u32`, `u64`, and `usize`. Callers pick the narrowest type
/// large enough to address their text.
pub trait Index:
    Copy
    + Eq
    + Ord
    + Send
    + Sync
    + std::fmt::Debug
    + std::ops::Add<Output = Self>
    + std::ops::Sub<Output = Self>
{
    /// Convert from `usize`.
    ///
    /// Current primitive implementations use Rust's `as` casts and
    /// therefore truncate if the value does not fit. Public constructors
    /// dispatch to an index width large enough for their generated
    /// positions; callers that invoke generic internals directly must
    /// choose an `I` that can represent every position they pass.
    fn from_usize(v: usize) -> Self;
    /// Convert to `usize`. Lossless for `u32`/`u64`/`usize` on 64-bit targets.
    fn to_usize(self) -> usize;
    /// The zero value.
    fn zero() -> Self;
}

macro_rules! impl_index {
    ($t:ty) => {
        impl Index for $t {
            #[inline]
            fn from_usize(v: usize) -> Self {
                v as $t
            }
            #[inline]
            fn to_usize(self) -> usize {
                self as usize
            }
            #[inline]
            fn zero() -> Self {
                0
            }
        }
    };
}

impl_index!(u32);
impl_index!(u64);
impl_index!(usize);