Struct fst::Map
[−]
[src]
pub struct Map(_);
Map is a lexicographically ordered map from byte strings to integers.
A Map
is constructed with the MapBuilder
type. Alternatively, a Map
can be constructed in memory from a lexicographically ordered iterator
of key-value pairs (Map::from_iter
).
A key feature of Map
is that it can be serialized to disk compactly. Its
underlying representation is built such that the Map
can be memory mapped
(Map::from_path
) and searched without necessarily loading the entire
map into memory.
It supports most common operations associated with maps, such as key lookup and search. It also supports set operations on its keys along with the ability to specify how conflicting values are merged together. Maps also support range queries and automata based searches (e.g. a regular expression).
Maps are represented by a finite state transducer where inputs are the keys and outputs are the values. As such, maps have the following invariants:
- Once constructed, a
Map
can never be modified. - Maps must be constructed with lexicographically ordered byte sequences. There is no restricting on the ordering of values.
Differences with sets
Maps and sets are represented by the same underlying data structure: the
finite state transducer. The principal difference between them is that
sets always have their output values set to 0
. This has an impact on the
representation size and is reflected in the type system for convenience.
A secondary but subtle difference is that duplicate values can be added
to a set, but it is an error to do so with maps. That is, a set can have
the same key added sequentially, but a map can't.
The future
It is regrettable that the output value is fixed to u64
. Indeed, it is
not necessary, but it was a major simplification in the implementation.
In the future, the value type may become generic to an extent (outputs must
satisfy a basic algebra).
Keys will always be byte strings; however, we may grow more conveniences around dealing with them (such as a serialization/deserialization step, although it isn't clear where exactly this should live).
Methods
impl Map
[src]
fn from_path<P: AsRef<Path>>(path: P) -> Result<Self>
Opens a map stored at the given file path via a memory map.
The map must have been written with a compatible finite state
transducer builder (MapBuilder
qualifies). If the format is invalid
or if there is a mismatch between the API version of this library
and the map, then an error is returned.
fn from_bytes(bytes: Vec<u8>) -> Result<Self>
Creates a map from its representation as a raw byte sequence.
Note that this operation is very cheap (no allocations and no copies).
The map must have been written with a compatible finite state
transducer builder (MapBuilder
qualifies). If the format is invalid
or if there is a mismatch between the API version of this library
and the map, then an error is returned.
fn from_iter<K, I>(iter: I) -> Result<Self> where K: AsRef<[u8]>, I: IntoIterator<Item=(K, u64)>
Create a Map
from an iterator of lexicographically ordered byte
strings and associated values.
If the iterator does not yield unique keys in lexicographic order, then an error is returned.
Note that this is a convenience function to build a map in memory.
To build a map that streams to an arbitrary io::Write
, use
MapBuilder
.
fn contains_key<K: AsRef<[u8]>>(&self, key: K) -> bool
Tests the membership of a single key.
Example
use fst::Map; let map = Map::from_iter(vec![("a", 1), ("b", 2), ("c", 3)]).unwrap(); assert_eq!(map.contains_key("b"), true); assert_eq!(map.contains_key("z"), false);
fn get<K: AsRef<[u8]>>(&self, key: K) -> Option<u64>
Retrieves the value associated with a key.
If the key does not exist, then None
is returned.
Example
use fst::Map; let map = Map::from_iter(vec![("a", 1), ("b", 2), ("c", 3)]).unwrap(); assert_eq!(map.get("b"), Some(2)); assert_eq!(map.get("z"), None);
fn stream(&self) -> Stream
Return a lexicographically ordered stream of all key-value pairs in this map.
While this is a stream, it does require heap space proportional to the longest key in the map.
If the map 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, Map}; let map = Map::from_iter(vec![("a", 1), ("b", 2), ("c", 3)]).unwrap(); let mut stream = map.stream(); let mut kvs = vec![]; while let Some((k, v)) = stream.next() { kvs.push((k.to_vec(), v)); } assert_eq!(kvs, vec![ (b"a".to_vec(), 1), (b"b".to_vec(), 2), (b"c".to_vec(), 3), ]);
fn keys(&self) -> Keys
Return a lexicographically ordered stream of all keys in this map.
Memory requirements are the same as described on Map::stream
.
Example
use fst::{IntoStreamer, Streamer, Map}; let map = Map::from_iter(vec![("a", 1), ("b", 2), ("c", 3)]).unwrap(); let mut stream = map.keys(); let mut keys = vec![]; while let Some(k) = stream.next() { keys.push(k.to_vec()); } assert_eq!(keys, vec![b"a", b"b", b"c"]);
fn values(&self) -> Values
Return a stream of all values in this map ordered lexicographically by each value's corresponding key.
Memory requirements are the same as described on Map::stream
.
Example
use fst::{IntoStreamer, Streamer, Map}; let map = Map::from_iter(vec![("a", 1), ("b", 2), ("c", 3)]).unwrap(); let mut stream = map.values(); let mut values = vec![]; while let Some(v) = stream.next() { values.push(v); } assert_eq!(values, vec![1, 2, 3]);
fn range(&self) -> StreamBuilder
Return a builder for range queries.
A range query returns a subset of key-value pairs in this map in a range given in lexicographic order.
Memory requirements are the same as described on Map::stream
.
Notably, only the keys in the range are read; keys outside the range
are not.
Example
Returns only the key-value pairs in the range given.
use fst::{IntoStreamer, Streamer, Map}; let map = Map::from_iter(vec![ ("a", 1), ("b", 2), ("c", 3), ("d", 4), ("e", 5), ]).unwrap(); let mut stream = map.range().ge("b").lt("e").into_stream(); let mut kvs = vec![]; while let Some((k, v)) = stream.next() { kvs.push((k.to_vec(), v)); } assert_eq!(kvs, vec![ (b"b".to_vec(), 2), (b"c".to_vec(), 3), (b"d".to_vec(), 4), ]);
fn search<A: Automaton>(&self, aut: A) -> StreamBuilder<A>
Executes an automaton on the keys of this map.
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 Map::stream
.
Example
This crate provides an implementation of regular expressions
for Automaton
. Make sure to see the documentation for fst::Regex
for more details such as what kind of regular expressions are allowed.
use fst::{IntoStreamer, Streamer, Regex, Map}; let map = Map::from_iter(vec![ ("foo", 1), ("foo1", 2), ("foo2", 3), ("foo3", 4), ("foobar", 5), ]).unwrap(); let re = Regex::new("f[a-z]+3?").unwrap(); let mut stream = map.search(&re).into_stream(); let mut kvs = vec![]; while let Some((k, v)) = stream.next() { kvs.push((k.to_vec(), v)); } assert_eq!(kvs, vec![ (b"foo".to_vec(), 1), (b"foo3".to_vec(), 4), (b"foobar".to_vec(), 5), ]);
fn len(&self) -> usize
Returns the number of elements in this map.
fn is_empty(&self) -> bool
Returns true if and only if this map is empty.
fn op(&self) -> OpBuilder
Creates a new map operation with this map added to it.
The OpBuilder
type can be used to add additional map streams
and perform set operations like union, intersection, difference and
symmetric difference on the keys of the map. These set operations also
allow one to specify how conflicting values are merged in the stream.
Example
This example demonstrates a union on multiple map streams. Notice that the stream returned from the union is not a sequence of key-value pairs, but rather a sequence of keys associated with one or more values. Namely, a key is associated with each value associated with that same key in the all of the streams.
use fst::{Streamer, Map}; use fst::map::IndexedValue; let map1 = Map::from_iter(vec![ ("a", 1), ("b", 2), ("c", 3), ]).unwrap(); let map2 = Map::from_iter(vec![ ("a", 10), ("y", 11), ("z", 12), ]).unwrap(); let mut union = map1.op().add(&map2).union(); let mut kvs = vec![]; while let Some((k, vs)) = union.next() { kvs.push((k.to_vec(), vs.to_vec())); } assert_eq!(kvs, vec![ (b"a".to_vec(), vec![ IndexedValue { index: 0, value: 1 }, IndexedValue { index: 1, value: 10 }, ]), (b"b".to_vec(), vec![IndexedValue { index: 0, value: 2 }]), (b"c".to_vec(), vec![IndexedValue { index: 0, value: 3 }]), (b"y".to_vec(), vec![IndexedValue { index: 1, value: 11 }]), (b"z".to_vec(), vec![IndexedValue { index: 1, value: 12 }]), ]);
fn as_fst(&self) -> &Fst
Returns a reference to the underlying raw finite state transducer.
Trait Implementations
impl Debug for Map
[src]
impl AsRef<Fst> for Map
[src]
Returns the underlying finite state transducer.