caps_sa/
lib.rs

1//! Cache-friendly, parallel, sample-sort-based suffix array construction.
2//!
3//! This crate is a Rust port of [CaPS-SA] (Khan et al., WABI 2023), a parallel
4//! and cache-friendly suffix-array constructor based on sample sort with
5//! LCP-enhanced comparison.
6//!
7//! The crate is generic over the symbol type (`u8`, `u16`, …; any `Ord + Copy`)
8//! and the index type (`u32`, `u64`; via the [`Index`] trait). It produces a
9//! standard lexicographic suffix array. Callers who need a *generalized* suffix
10//! array can supply a [`LimitProvider`] (for example [`SegmentedText`]) to stop
11//! comparisons at string boundaries and define their boundary ordering. This
12//! avoids enlarging the symbol alphabet with one distinct sentinel per input
13//! string.
14//!
15//! Phase 1 of the port provides the **in-memory** algorithm; the external-memory
16//! variant (disk-spilling buckets) is layered on top in a later phase.
17//!
18//! [CaPS-SA]: https://github.com/jamshed/CaPS-SA
19
20mod ext_bucket;
21mod ext_mem;
22mod lcp;
23mod lcp_memo;
24mod limits;
25mod sample_sort;
26
27pub use ext_mem::{
28    BuildError, ExtMemOpts, build_ext_mem, build_ext_mem_for_filter, build_ext_mem_for_filter_with,
29    build_ext_mem_for_positions, build_ext_mem_for_positions_with, build_ext_mem_with,
30    build_in_memory_sample_sort, build_in_memory_sample_sort_for_positions,
31    build_in_memory_sample_sort_for_positions_with, build_in_memory_sample_sort_with,
32    try_build_ext_mem, try_build_ext_mem_for_filter, try_build_ext_mem_for_filter_with,
33    try_build_ext_mem_for_positions, try_build_ext_mem_for_positions_with, try_build_ext_mem_with,
34    try_build_in_memory_sample_sort, try_build_in_memory_sample_sort_for_positions,
35    try_build_in_memory_sample_sort_for_positions_with, try_build_in_memory_sample_sort_with,
36};
37pub use lcp::{LcpDispatch, Symbol, lcp, lcp_scalar, lcp_u8, suffix_cmp};
38pub use lcp_memo::{GeometricMemoizationConfig, LcpMemoizationPolicy};
39pub use limits::{LimitProvider, PlainText, SegmentedText};
40pub use sample_sort::{
41    Opts, build_in_memory, build_in_memory_for_positions, build_in_memory_for_positions_with,
42    build_in_memory_for_positions_with_opts, build_in_memory_with, build_in_memory_with_opts,
43};
44
45/// Trait implemented by integer types usable as suffix array indices.
46///
47/// Provided for `u32`, `u64`, and `usize`. Callers pick the narrowest type
48/// large enough to address their text.
49pub trait Index:
50    Copy
51    + Eq
52    + Ord
53    + Send
54    + Sync
55    + std::fmt::Debug
56    + std::ops::Add<Output = Self>
57    + std::ops::Sub<Output = Self>
58{
59    /// Convert from `usize`.
60    ///
61    /// Current primitive implementations use Rust's `as` casts and
62    /// therefore truncate if the value does not fit. Public constructors
63    /// dispatch to an index width large enough for their generated
64    /// positions; callers that invoke generic internals directly must
65    /// choose an `I` that can represent every position they pass.
66    fn from_usize(v: usize) -> Self;
67    /// Convert to `usize`. Lossless for `u32`/`u64`/`usize` on 64-bit targets.
68    fn to_usize(self) -> usize;
69    /// The zero value.
70    fn zero() -> Self;
71}
72
73macro_rules! impl_index {
74    ($t:ty) => {
75        impl Index for $t {
76            #[inline]
77            fn from_usize(v: usize) -> Self {
78                v as $t
79            }
80            #[inline]
81            fn to_usize(self) -> usize {
82                self as usize
83            }
84            #[inline]
85            fn zero() -> Self {
86                0
87            }
88        }
89    };
90}
91
92impl_index!(u32);
93impl_index!(u64);
94impl_index!(usize);
caps_sa/lib.rs

caps_sa/
lib.rs
