Rust · Sorting and Sets

Sorting and Sets

use stringzilla::ArgsortOptions;use stringzilla::EscapeKind;use stringzilla::*; 6.0.0-rc.1 · 91a27bdd

§ Argsort

argsort writes the sorted permutation of a slice into a caller-provided order slice, while argsort_by sorts by a byte-slice key extracted from each element.

pub fn argsort<T: AsRef<[u8]>>(data: &[T], order: &mut [usize], options: ArgsortOptions) -> Result<(), Status>;
pub fn argsort_by<T, K>(data: &[T], key: K, order: &mut [usize], options: ArgsortOptions) -> Result<(), Status>
where K: Fn(&T) -> &[u8];

Both write the sorting permutation of data into a caller-supplied order buffer of length at least data.len(), or return Status::UnexpectedDimensions. argsort_by sorts by a byte-slice key of each element, ideal for sorting structs by a field. The binding indexes data itself, so the key only projects an element onto its bytes; it runs inside the C call, where a panic cannot unwind and aborts the process.

ArgsortOptions is a builder; the default is a full, ascending, byte-lexicographic, stable sort:

  • reversed() / field reverse: bool — descending order, still stable on ties.
  • uncased() / field uncased: bool — order under Unicode case folding instead of raw bytes.
  • top(k) / field top: Option<usize> — only fully order the leading k elements, a top-K or partial sort.
use stringzilla::{self as sz, ArgsortOptions};

let fruits = ["banana", "apple", "cherry"];
let mut order = [0; 3];
sz::argsort(&fruits, &mut order, Default::default()).unwrap();
assert_eq!(&order, &[1, 0, 2]); // apple, banana, cherry

// Descending + uncased
let labels = ["beta", "Alpha", "BETA"];
let mut order = [0; 3];
sz::argsort(&labels, &mut order, ArgsortOptions::default().reversed().uncased()).unwrap();

// Sort structs by a key
struct Person { name: &'static str }
let people = [Person { name: "Charlie" }, Person { name: "Alice" }, Person { name: "Bob" }];
let mut order = [0; 3];
sz::argsort_by(&people, |person| person.name.as_bytes(), &mut order, Default::default()).unwrap();
assert_eq!(&order, &[1, 2, 0]); // Alice, Bob, Charlie

§ Intersection, an Inner Join

intersection matches two collections directly, while intersection_by matches by a byte-slice key extracted from each element, both writing the matched positions of each side.

pub fn intersection<T: AsRef<[u8]>>(data1: &[T], data2: &[T], seed: u64,
    positions1: &mut [usize], positions2: &mut [usize]) -> Result<usize, Status>;
pub fn intersection_by<T, U, K, L>(data1: &[T], key1: K, data2: &[U], key2: L, seed: u64,
    positions1: &mut [usize], positions2: &mut [usize]) -> Result<usize, Status>
where K: Fn(&T) -> &[u8], L: Fn(&U) -> &[u8];

Both compute the intersection of two collections, which may differ in length and, for intersection_by, in element type. They write the matching positions into output buffers each sized at least min(data1.len(), data2.len()), or return Status::UnexpectedDimensions, and return the intersection size:

use stringzilla as sz;

let set1 = ["banana", "apple", "cherry"];
let set2 = ["cherry", "orange", "pineapple", "banana"];
let (mut p1, mut p2) = ([0; 3], [0; 3]);
let n = sz::intersection(&set1, &set2, 0, &mut p1, &mut p2).unwrap();
assert_eq!(n, 2); // "banana" and "cherry"

§ Random Fill

fill_random overwrites a buffer with deterministic pseudo-random bytes derived from a nonce.

pub fn fill_random<T: AsMut<[u8]>>(buffer: &mut T, nonce: u64);

fill_random overwrites a buffer with deterministic pseudo-random bytes for a given nonce — the same nonce always yields the same output — useful for generating test data:

use stringzilla as sz;

let mut a = vec![0u8; 10];
let mut b = vec![1u8; 10];
sz::fill_random(&mut a, 42);
sz::fill_random(&mut b, 42);
assert_eq!(a, b); // identical nonce → identical bytes

§ Splitting, Joining, Escaping, Mapping and Normalizing Collections

A column of strings comes in two types. A StringsView borrows one in any layout C reads: an Apache Arrow String or LargeString tape of bytes and offsets, or a slice of anything AsRef<[u8]>, read in place through an accessor. A Strings<A> owns one tape, its payload and its offsets both from the allocator A, Global unless named, and frees them on drop. Every conversion writes a new Strings, or a joined Vec<u8, A>, from the allocator it is given, on the device of the stream it is given, joining that stream before returning:

impl<A: Allocator> Strings<A> {
    pub fn copy_in(strings: StringsView<'_>, allocator: A, stream: &Stream) -> Result<Self, Status>;
    pub fn split_in(text: &[u8], delimiters: Byteset, kind: SplitKind, allocator: A, stream: &Stream) -> Result<Self, Status>;
    pub fn split_lines_in(text: &[u8], allocator: A, stream: &Stream) -> Result<Self, Status>;
    pub fn view(&self) -> StringsView<'_>;
}
impl<'a> StringsView<'a> {
    pub fn from_u32_tape(data: &'a [u8], offsets: &'a [u32]) -> Result<Self, Status>;
    pub fn from_u64_tape(data: &'a [u8], offsets: &'a [u64]) -> Result<Self, Status>;
    pub fn from_slices<T: AsRef<[u8]>>(texts: &'a [T]) -> Self;
    pub fn get(&self, index: usize) -> Option<&'a [u8]>;
    pub fn iter(&self) -> StringsIter<'a>;
    pub fn escape_in<A: Allocator>(&self, kind: EscapeKind, allocator: A, stream: &Stream) -> Result<Strings<A>, Status>;
    pub fn unescape_in<A: Allocator>(&self, kind: EscapeKind, allocator: A, stream: &Stream) -> Result<Strings<A>, StringsError>;
    pub fn lookup_in<A: Allocator>(&self, table: &[u8; 256], allocator: A, stream: &Stream) -> Result<Strings<A>, Status>;
    pub fn normalize_in<A: Allocator>(&self, form: NormalForm, allocator: A, stream: &Stream) -> Result<Strings<A>, Status>;
    pub fn join_in<A: Allocator>(&self, between: &[u8], allocator: A, stream: &Stream) -> Result<Vec<u8, A>, Status>;
    pub fn join_columns_in<A: Allocator>(columns: &[StringsView<'_>], frames: &[&[u8]], between: &[u8], allocator: A, stream: &Stream) -> Result<Vec<u8, A>, Status>;
    pub fn to_rows(&self, rows: &mut [u8], width: usize, stream: &Stream) -> Result<usize, Status>;
    pub fn find(&self, needle: &[u8], positions: &mut [usize], stream: &Stream) -> Result<(), Status>;
    pub fn hashes(&self, seed: u64, hashes: &mut [u64], stream: &Stream) -> Result<(), Status>;
    pub fn utf8_count(&self, runes: Option<&mut [usize]>, stream: &Stream) -> Result<(), StringsError>;
}

from_u32_tape and from_u64_tape refuse offsets that fall or run past the data with Status::UnexpectedDimensions, and accept a sliced Arrow array whose first offset is past zero. EscapeKind names the format: Json, JsonAscii, Csv, Html, Url, Hex or Console, the last one keeping logs safe from control bytes and bidirectional overrides. unescape_in stops at the first malformed string, like a CSV field with an unbalanced quote, and reports its position as StringsError::Malformed. find writes each string’s first match of one needle, usize::MAX where there is none, and hashes each string’s hash_with_seed, both into a slice of exactly len() entries. utf8_count validates every string as UTF-8, reporting the first ill-formed one as StringsError::Malformed, and writes each one’s rune count into such a slice unless given None. split_in cuts a text at the bytes of a Byteset, every delimiter ending a part with SplitKind::Each, like slice::split, or every run of them with SplitKind::Runs, like str::split_ascii_whitespace. split_lines_in cuts UTF-8 at the line breaks of Python’s str.splitlines(), CR LF counting as one, leaving no empty line after the last. join_columns_in writes row r as frames[0], columns[0][r], frames[1] and so on, with between between rows, serializing CSV lines or JSON records without a string per cell, and join_in joins one column like slice::join. to_rows writes NUL-padded fixed-width rows, truncating longer strings, and returns the longest length to retry with wider rows:

use std::alloc::Global;
use stringzilla::{Byteset, Capabilities, EscapeKind, NormalForm, SplitKind, Stream, Strings, StringsError, StringsView};

let cpu = Stream::default(Capabilities::cpu_enabled());
let names = StringsView::from_slices(&["Ada", "Grace \"Amazing\" Hopper", "Stra\u{df}e"]);

let fields = names.escape_in(EscapeKind::Csv, Global, &cpu)?;
assert_eq!(fields.view().get(1), Some(&br#""Grace ""Amazing"" Hopper""#[..]));
let restored = fields.view().unescape_in(EscapeKind::Csv, Global, &cpu).unwrap();
assert!(restored.view().iter().eq(names.iter()));

let years = StringsView::from_slices(&["1815", "1906", "1984"]);
let csv = StringsView::join_columns_in(&[fields.view(), years], &[b"", b",", b""], b"\r\n", Global, &cpu)?;
assert_eq!(csv, "Ada,1815\r\n\"Grace \"\"Amazing\"\" Hopper\",1906\r\nStra\u{df}e,1984".as_bytes());
let lines = Strings::split_lines_in(&csv, Global, &cpu)?;
let cells = Strings::split_in(lines.view().get(2).unwrap(), Byteset::from(","), SplitKind::Each, Global, &cpu)?;
assert!(cells.view().iter().eq(["Stra\u{df}e".as_bytes(), b"1984"]));

let mut runes = [0; 3];
names.utf8_count(Some(&mut runes), &cpu).unwrap();
assert_eq!(runes, [3, 22, 6]);

let keys = names.normalize_in(NormalForm::NfkcCasefold, Global, &cpu)?;
assert_eq!(keys.view().get(2), Some(&b"strasse"[..]));

let mut rows = [0u8; 3 * 8];
assert_eq!(names.to_rows(&mut rows, 8, &cpu)?, 22); // "Grace \"Amazing\" Hopper" is 22 bytes long

let broken = StringsView::from_slices(&["fine", "\"unbalanced"]);
assert_eq!(broken.unescape_in(EscapeKind::Csv, Global, &cpu).err(), Some(StringsError::Malformed(1)));

// An Arrow array sliced from its second string, copied into a tape of its own.
let arrow = StringsView::from_u32_tape(b"skipAdaGrace", &[4, 7, 12])?;
let copy = Strings::copy_in(arrow, Global, &cpu)?;
assert!(copy.view().iter().eq([&b"Ada"[..], b"Grace"]));

API

StructArgsortOptionsKnobs for argsort and argsort_by.3
sort.rs:22 ↗
pub struct ArgsortOptions

The default is a full, ascending, byte-lexicographic, stable sort (equal elements keep their input order). Tweak the public fields directly or chain the builder methods:

use stringzilla as sz;

let descending = sz::ArgsortOptions::default().reversed();
let top_10_folded = sz::ArgsortOptions { uncased: true, top: Some(10), ..Default::default() };

Fields

reverseboolSort in descending order; equal elements still keep their input order, as the sort is stable.
uncasedboolOrder under Unicode case-folding instead of raw bytes.
topOption<usize>Only fully order the leading Some(k) elements (top-K / partial sort); None sorts everything. The remaining entries of order stay a valid - but arbitrary - permutation of the leftover indices.

Implements

Clone, Copy, Debug, Default, StructuralPartialEq, PartialEq, Eq
reversedSort in descending order.
sort.rs:36 ↗
pub const fn reversed(self) -> Self
uncasedOrder under Unicode case-folding instead of raw bytes.
sort.rs:41 ↗
pub const fn uncased(self) -> Self
topOnly fully order the leading count elements (top-K / partial sort).
sort.rs:46 ↗
pub const fn top(self, count: usize) -> Self
EnumEscapeKindThe text formats StringsView::escape_in and StringsView::unescape_in convert strings to and from.
strings.rs:354 ↗
pub enum EscapeKind

Corresponds to sz_escape_kind_t in the C API.

Values

Json0RFC 8259 string bodies: \", \\, short forms like \n, and \u00XX for the other bytes below 0x20, every other byte kept as it is.
Hex1Two lowercase hexadecimal digits per byte, decoding either case.
Html2HTML and XML text and attribute values: &amp;, &lt;, &gt;, &quot; and &#39;.
Url3RFC 3986 percent-encoding of every byte outside A-Z a-z 0-9 - . _ ~.
Console4Terminal-safe logs: short forms like \n, \xHH for the other control bytes and ill-formed UTF-8, and \uXXXX for C1 controls and the bidirectional overrides that reorder what a reader sees.
Csv5RFC 4180 fields, quoted only when holding a comma, a quote, CR or LF, with inner quotes doubled.
JsonAscii6RFC 8259 string bodies in ASCII alone: every other codepoint becomes \uXXXX, a surrogate pair beyond the Basic Multilingual Plane, and every ill-formed byte the escaped U+FFFD.

Implements

Debug, Clone, Copy, StructuralPartialEq, PartialEq, Eq

Functions

intersectionIntersects two sequences, as an inner join, using their default byte-slice views.
intersect.rs:26 ↗
pub fn intersection<Element: AsRef<[u8]>>(
    data1: &[Element],
    data2: &[Element],
    seed: u64,
    positions1: &mut [usize],
    positions2: &mut [usize],
) -> Result<usize, Status>

Both sequences must have an output buffer provided, for the first and second positions, whose length is at least the minimum of the two input lengths.

Examples

use stringzilla as sz;

let set1 = ["banana", "apple", "cherry"];
let set2 = ["cherry", "orange", "pineapple", "banana"];
let mut positions1 = [0; 3]; // at least min(3, 4) == 3 elements.
let mut positions2 = [0; 3];
let n = sz::intersection(&set1, &set2, 0, &mut positions1, &mut positions2).expect("intersection failed");
assert!(n == 2); // "banana" and "cherry" are common.
intersection_byIntersects two sequences, as an inner join, on a byte-slice key of each element.
intersect.rs:76 ↗
pub fn intersection_by<Element1, Element2, Key1, Key2>(
    data1: &[Element1],
    key1: Key1,
    data2: &[Element2],
    key2: Key2,
    seed: u64,
    positions1: &mut [usize],
    positions2: &mut [usize],
) -> Result<usize, Status>
where
    Key1: Fn(&Element1) -> &[u8],
    Key2: Fn(&Element2) -> &[u8],

The sequences may differ in length and element type, and each output buffer must hold at least as many positions as the shorter sequence has elements, or Status::UnexpectedDimensions is returned. The keys run inside the C call, where a panic cannot unwind and aborts the process.

Examples

use stringzilla as sz;

struct Person { name: &'static str, age: u32 }

let people = [
    Person { name: "Charlie", age: 20 },
    Person { name: "Alice", age: 25 },
    Person { name: "Bob", age: 30 },
];
let invited = ["Alice", "Bob", "Dave", "Eve"];
let mut positions1 = [0; 3]; // min(people.len(), invited.len())
let mut positions2 = [0; 3];
let n = sz::intersection_by(
    &people,
    |person| person.name.as_bytes(),
    &invited,
    |name| name.as_bytes(),
    0,
    &mut positions1,
    &mut positions2,
).expect("intersection_by failed");
assert!(n == 2); // "Alice" and "Bob" are common.
argsortComputes the permutation that sorts data by its byte-slice representations.
sort.rs:74 ↗
pub fn argsort<Element: AsRef<[u8]>>(
    data: &[Element],
    order: &mut [usize],
    options: ArgsortOptions,
) -> Result<(), Status>

The caller supplies an output buffer order of length at least data.len(), or gets Status::UnexpectedDimensions; on success the sorted permutation indices are written into its first data.len() slots. See ArgsortOptions for descending, uncased, and top-K variants.

Examples

use stringzilla as sz;

let fruits = ["banana", "apple", "cherry"];
let mut order = [0; 3];
sz::argsort(&fruits, &mut order, Default::default()).expect("sort failed");
assert_eq!(&order, &[1, 0, 2]); // "apple", "banana", "cherry"

// Descending, uncased:
let labels = ["beta", "Alpha", "BETA"];
let mut order = [0; 3];
sz::argsort(&labels, &mut order, sz::ArgsortOptions::default().reversed().uncased()).unwrap();
assert_eq!(labels[order[0]], "beta"); // "beta"/"BETA" (fold-equal) before "Alpha", stable on ties
argsort_byComputes the permutation that sorts data by a byte-slice key of each element.
sort.rs:102 ↗
pub fn argsort_by<Element, Key>(
    data: &[Element],
    key: Key,
    order: &mut [usize],
    options: ArgsortOptions,
) -> Result<(), Status>
where
    Key: Fn(&Element) -> &[u8],

order must hold at least data.len() entries, as in argsort. key runs inside the C call, where a panic cannot unwind and aborts the process.

Examples

use stringzilla as sz;

struct Person { name: &'static str, age: u32 }
let people = [
    Person { name: "Charlie", age: 20 },
    Person { name: "Alice", age: 25 },
    Person { name: "Bob", age: 30 },
];
let mut order = [0; 3];
sz::argsort_by(&people, |person| person.name.as_bytes(), &mut order, Default::default()).expect("sort failed");
assert_eq!(&order, &[1, 2, 0]); // "Alice", "Bob", "Charlie"
fill_randomRandomizes the contents of a given byte slice text using characters from a specified alphabet.
strings.rs:171 ↗
pub fn fill_random<Buffer>(buffer: &mut Buffer, nonce: u64)
where
    Buffer: AsMut<[u8]> + ?Sized,

This function mutates text in place, replacing each byte with a random one from alphabet. It is designed for situations where you need to generate random strings or data sequences based on a specific set of characters, such as generating random DNA sequences or testing inputs.

Arguments

  • buffer: A mutable reference to the data to randomize. This data will be mutated in place.
  • nonce: A 64-bit "number used once", or nonce, value to seed the random number generator.

Examples

use stringzilla as sz;
let mut buffer = vec![0; 10];
sz::fill_random(&mut buffer, 42);

After than, buffer is filled with random byte values from 0 to 255.