Struct fst::Set

source ·
pub struct Set(_);
Expand description

Set is a lexicographically ordered set of byte strings.

A Set is constructed with the SetBuilder type. Alternatively, a Set can be constructed in memory from a lexicographically ordered iterator of byte strings (Set::from_iter).

A key feature of Set is that it can be serialized to disk compactly. Its underlying representation is built such that the Set can be memory mapped (Set::from_path) and searched without necessarily loading the entire set into memory.

It supports most common operations associated with sets, such as membership, union, intersection, subset/superset, etc. It also supports range queries and automata based searches (e.g. a regular expression).

Sets are represented by a finite state transducer where output values are always zero. As such, sets have the following invariants:

  1. Once constructed, a Set can never be modified.
  2. Sets must be constructed with lexicographically ordered byte sequences.

Implementations

Opens a set stored at the given file path via a memory map.

The set must have been written with a compatible finite state transducer builder (SetBuilder qualifies). If the format is invalid or if there is a mismatch between the API version of this library and the set, then an error is returned.

This is unsafe because Rust programs cannot guarantee that memory backed by a memory mapped file won’t be mutably aliased. It is up to the caller to enforce that the memory map is not modified while it is opened.

Creates a set from its representation as a raw byte sequence.

Note that this operation is very cheap (no allocations and no copies).

The set must have been written with a compatible finite state transducer builder (SetBuilder qualifies). If the format is invalid or if there is a mismatch between the API version of this library and the set, then an error is returned.

Create a Set from an iterator of lexicographically ordered byte strings.

If the iterator does not yield values in lexicographic order, then an error is returned.

Note that this is a convenience function to build a set in memory. To build a set that streams to an arbitrary io::Write, use SetBuilder.

Tests the membership of a single key.

Example
use fst::Set;

let set = Set::from_iter(&["a", "b", "c"]).unwrap();

assert_eq!(set.contains("b"), true);
assert_eq!(set.contains("z"), false);

Return a lexicographically ordered stream of all keys in this set.

While this is a stream, it does require heap space proportional to the longest key in the set.

If the set is memory mapped, then no further heap space is needed. Note though that your operating system may fill your page cache (which will cause the resident memory usage of the process to go up correspondingly).

Example

Since streams are not iterators, the traditional for loop cannot be used. while let is useful instead:

use fst::{IntoStreamer, Streamer, Set};

let set = Set::from_iter(&["a", "b", "c"]).unwrap();
let mut stream = set.stream();

let mut keys = vec![];
while let Some(key) = stream.next() {
    keys.push(key.to_vec());
}
assert_eq!(keys, vec![b"a", b"b", b"c"]);

Return a builder for range queries.

A range query returns a subset of keys in this set in a range given in lexicographic order.

Memory requirements are the same as described on Set::stream. Notably, only the keys in the range are read; keys outside the range are not.

Example

Returns only the keys in the range given.

use fst::{IntoStreamer, Streamer, Set};

let set = Set::from_iter(&["a", "b", "c", "d", "e"]).unwrap();
let mut stream = set.range().ge("b").lt("e").into_stream();

let mut keys = vec![];
while let Some(key) = stream.next() {
    keys.push(key.to_vec());
}
assert_eq!(keys, vec![b"b", b"c", b"d"]);

Executes an automaton on the keys of this set.

Note that this returns a StreamBuilder, which can be used to add a range query to the search (see the range method).

Memory requirements are the same as described on Set::stream.

Example

An implementation of regular expressions for Automaton is available in the fst-regex crate, which can be used to search sets.

extern crate fst;
extern crate fst_regex;

use std::error::Error;

use fst::{IntoStreamer, Streamer, Set};
use fst_regex::Regex;

fn example() -> Result<(), Box<Error>> {
    let set = Set::from_iter(&[
        "foo", "foo1", "foo2", "foo3", "foobar",
    ]).unwrap();

    let re = Regex::new("f[a-z]+3?").unwrap();
    let mut stream = set.search(&re).into_stream();

    let mut keys = vec![];
    while let Some(key) = stream.next() {
        keys.push(key.to_vec());
    }
    assert_eq!(keys, vec![
        "foo".as_bytes(), "foo3".as_bytes(), "foobar".as_bytes(),
    ]);

    Ok(())
}

Returns the number of elements in this set.

Returns true if and only if this set is empty.

Creates a new set operation with this set added to it.

The OpBuilder type can be used to add additional set streams and perform set operations like union, intersection, difference and symmetric difference.

Example
use fst::{IntoStreamer, Streamer, Set};

let set1 = Set::from_iter(&["a", "b", "c"]).unwrap();
let set2 = Set::from_iter(&["a", "y", "z"]).unwrap();

let mut union = set1.op().add(&set2).union();

let mut keys = vec![];
while let Some(key) = union.next() {
    keys.push(key.to_vec());
}
assert_eq!(keys, vec![b"a", b"b", b"c", b"y", b"z"]);

Returns true if and only if the self set is disjoint with the set stream.

stream must be a lexicographically ordered sequence of byte strings.

Example
use fst::{IntoStreamer, Streamer, Set};

let set1 = Set::from_iter(&["a", "b", "c"]).unwrap();
let set2 = Set::from_iter(&["x", "y", "z"]).unwrap();

assert_eq!(set1.is_disjoint(&set2), true);

let set3 = Set::from_iter(&["a", "c"]).unwrap();

assert_eq!(set1.is_disjoint(&set3), false);

Returns true if and only if the self set is a subset of stream.

stream must be a lexicographically ordered sequence of byte strings.

Example
use fst::Set;

let set1 = Set::from_iter(&["a", "b", "c"]).unwrap();
let set2 = Set::from_iter(&["x", "y", "z"]).unwrap();

assert_eq!(set1.is_subset(&set2), false);

let set3 = Set::from_iter(&["a", "c"]).unwrap();

assert_eq!(set1.is_subset(&set3), false);
assert_eq!(set3.is_subset(&set1), true);

Returns true if and only if the self set is a superset of stream.

stream must be a lexicographically ordered sequence of byte strings.

Example
use fst::Set;

let set1 = Set::from_iter(&["a", "b", "c"]).unwrap();
let set2 = Set::from_iter(&["x", "y", "z"]).unwrap();

assert_eq!(set1.is_superset(&set2), false);

let set3 = Set::from_iter(&["a", "c"]).unwrap();

assert_eq!(set1.is_superset(&set3), true);
assert_eq!(set3.is_superset(&set1), false);

Returns a reference to the underlying raw finite state transducer.

Trait Implementations

Returns the underlying finite state transducer.

Converts this type into a shared reference of the (usually inferred) input type.
Formats the value using the given formatter. Read more
Returns the “default value” for a type. Read more
Converts to this type from the input type.
The type of the item emitted by the stream.
The type of the stream to be constructed.
Construct a stream from Self.

Auto Trait Implementations

Blanket Implementations

Gets the TypeId of self. Read more
Immutably borrows from an owned value. Read more
Mutably borrows from an owned value. Read more

Returns the argument unchanged.

Calls U::from(self).

That is, this conversion is whatever the implementation of From<T> for U chooses to do.

The type returned in the event of a conversion error.
Performs the conversion.
The type returned in the event of a conversion error.
Performs the conversion.