Struct yada::DoubleArray
source · pub struct DoubleArray<T>(pub T)
where
T: Deref<Target = [u8]>;
Expand description
A double array trie.
Tuple Fields§
§0: T
Implementations§
source§impl<T> DoubleArray<T>
impl<T> DoubleArray<T>
sourcepub fn new(bytes: T) -> Self
pub fn new(bytes: T) -> Self
Creates a new DoubleArray
with a byte slice.
Examples found in repository?
examples/load_from_file.rs (line 26)
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
fn main() -> Result<(), Box<dyn std::error::Error>> {
// filename to save and load
let filename = "load_from_file_example.da";
// make a keyset which have key-value pairs
let keyset = &[
("a".as_bytes(), 0),
("aa".as_bytes(), 1),
("aaa".as_bytes(), 2),
("b".as_bytes(), 3),
("bcd".as_bytes(), 4),
];
// build a double-array trie binary
let da_bytes = DoubleArrayBuilder::build(keyset);
assert!(da_bytes.is_some());
// create a double-array trie instance
let da = DoubleArray::new(da_bytes.unwrap());
// save to file
let mut file = File::create(filename)?;
file.write_all(da.0.as_slice())?;
file.flush()?;
// load from file
let mut file = File::open(filename)?;
let mut buf = Vec::new();
let _ = file.read_to_end(&mut buf)?;
let da = DoubleArray::new(buf);
// test search
for (key, value) in keyset.iter() {
let v = da.exact_match_search(key).unwrap();
assert_eq!(v, *value);
}
assert_eq!(
da.common_prefix_search(&"aaaa").collect::<Vec<_>>(),
vec![(0, 1), (1, 2), (2, 3)]
);
assert_eq!(
da.common_prefix_search(&"bcde").collect::<Vec<_>>(),
vec![(3, 1), (4, 3)]
);
Ok(())
}
More examples
examples/build_and_search.rs (line 22)
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
fn main() {
// make a keyset which have key-value pairs
let keyset = &[
("a".as_bytes(), 0),
("ab".as_bytes(), 1),
("abc".as_bytes(), 2),
("b".as_bytes(), 3),
("bc".as_bytes(), 4),
("c".as_bytes(), 5),
];
// build a double-array trie binary
let da_bytes = DoubleArrayBuilder::build(keyset);
assert!(da_bytes.is_some());
// create a double-array trie instance
let da = DoubleArray::new(da_bytes.unwrap());
// exact match search
for (key, value) in keyset {
assert_eq!(da.exact_match_search(key), Some(*value as u32));
}
assert_eq!(da.exact_match_search("aa".as_bytes()), None);
assert_eq!(da.exact_match_search("aba".as_bytes()), None);
assert_eq!(da.exact_match_search("abb".as_bytes()), None);
assert_eq!(da.exact_match_search("abcd".as_bytes()), None);
assert_eq!(da.exact_match_search("ba".as_bytes()), None);
assert_eq!(da.exact_match_search("bb".as_bytes()), None);
assert_eq!(da.exact_match_search("bcd".as_bytes()), None);
assert_eq!(da.exact_match_search("ca".as_bytes()), None);
// common prefix search
assert_eq!(
da.common_prefix_search("a".as_bytes()).collect::<Vec<_>>(),
vec![(0, 1)] // match "a"
);
assert_eq!(
da.common_prefix_search("abc".as_bytes())
.collect::<Vec<_>>(),
vec![(0, 1), (1, 2), (2, 3)] // match "a", "ab", "abc"
);
assert_eq!(
da.common_prefix_search("abcd".as_bytes())
.collect::<Vec<_>>(),
vec![(0, 1), (1, 2), (2, 3)] // match "a", "ab", "abc"
);
assert_eq!(
da.common_prefix_search("bcd".as_bytes())
.collect::<Vec<_>>(),
vec![(3, 1), (4, 2)] // match "b", "bc"
);
assert_eq!(
da.common_prefix_search("d".as_bytes()).collect::<Vec<_>>(),
vec![] // don't match
);
}
sourcepub fn exact_match_search<K>(&self, key: K) -> Option<u32>
pub fn exact_match_search<K>(&self, key: K) -> Option<u32>
Finds a value associated with a key
.
Examples found in repository?
examples/load_from_file.rs (line 41)
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
fn main() -> Result<(), Box<dyn std::error::Error>> {
// filename to save and load
let filename = "load_from_file_example.da";
// make a keyset which have key-value pairs
let keyset = &[
("a".as_bytes(), 0),
("aa".as_bytes(), 1),
("aaa".as_bytes(), 2),
("b".as_bytes(), 3),
("bcd".as_bytes(), 4),
];
// build a double-array trie binary
let da_bytes = DoubleArrayBuilder::build(keyset);
assert!(da_bytes.is_some());
// create a double-array trie instance
let da = DoubleArray::new(da_bytes.unwrap());
// save to file
let mut file = File::create(filename)?;
file.write_all(da.0.as_slice())?;
file.flush()?;
// load from file
let mut file = File::open(filename)?;
let mut buf = Vec::new();
let _ = file.read_to_end(&mut buf)?;
let da = DoubleArray::new(buf);
// test search
for (key, value) in keyset.iter() {
let v = da.exact_match_search(key).unwrap();
assert_eq!(v, *value);
}
assert_eq!(
da.common_prefix_search(&"aaaa").collect::<Vec<_>>(),
vec![(0, 1), (1, 2), (2, 3)]
);
assert_eq!(
da.common_prefix_search(&"bcde").collect::<Vec<_>>(),
vec![(3, 1), (4, 3)]
);
Ok(())
}
More examples
examples/build_and_search.rs (line 26)
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
fn main() {
// make a keyset which have key-value pairs
let keyset = &[
("a".as_bytes(), 0),
("ab".as_bytes(), 1),
("abc".as_bytes(), 2),
("b".as_bytes(), 3),
("bc".as_bytes(), 4),
("c".as_bytes(), 5),
];
// build a double-array trie binary
let da_bytes = DoubleArrayBuilder::build(keyset);
assert!(da_bytes.is_some());
// create a double-array trie instance
let da = DoubleArray::new(da_bytes.unwrap());
// exact match search
for (key, value) in keyset {
assert_eq!(da.exact_match_search(key), Some(*value as u32));
}
assert_eq!(da.exact_match_search("aa".as_bytes()), None);
assert_eq!(da.exact_match_search("aba".as_bytes()), None);
assert_eq!(da.exact_match_search("abb".as_bytes()), None);
assert_eq!(da.exact_match_search("abcd".as_bytes()), None);
assert_eq!(da.exact_match_search("ba".as_bytes()), None);
assert_eq!(da.exact_match_search("bb".as_bytes()), None);
assert_eq!(da.exact_match_search("bcd".as_bytes()), None);
assert_eq!(da.exact_match_search("ca".as_bytes()), None);
// common prefix search
assert_eq!(
da.common_prefix_search("a".as_bytes()).collect::<Vec<_>>(),
vec![(0, 1)] // match "a"
);
assert_eq!(
da.common_prefix_search("abc".as_bytes())
.collect::<Vec<_>>(),
vec![(0, 1), (1, 2), (2, 3)] // match "a", "ab", "abc"
);
assert_eq!(
da.common_prefix_search("abcd".as_bytes())
.collect::<Vec<_>>(),
vec![(0, 1), (1, 2), (2, 3)] // match "a", "ab", "abc"
);
assert_eq!(
da.common_prefix_search("bcd".as_bytes())
.collect::<Vec<_>>(),
vec![(3, 1), (4, 2)] // match "b", "bc"
);
assert_eq!(
da.common_prefix_search("d".as_bytes()).collect::<Vec<_>>(),
vec![] // don't match
);
}
sourcepub fn common_prefix_search<'b, K>(
&'b self,
key: &'b K
) -> impl Iterator<Item = (u32, usize)> + 'b
pub fn common_prefix_search<'b, K>( &'b self, key: &'b K ) -> impl Iterator<Item = (u32, usize)> + 'b
Finds all values and it’s key length which have a common prefix with a key
.
Examples found in repository?
examples/load_from_file.rs (line 45)
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
fn main() -> Result<(), Box<dyn std::error::Error>> {
// filename to save and load
let filename = "load_from_file_example.da";
// make a keyset which have key-value pairs
let keyset = &[
("a".as_bytes(), 0),
("aa".as_bytes(), 1),
("aaa".as_bytes(), 2),
("b".as_bytes(), 3),
("bcd".as_bytes(), 4),
];
// build a double-array trie binary
let da_bytes = DoubleArrayBuilder::build(keyset);
assert!(da_bytes.is_some());
// create a double-array trie instance
let da = DoubleArray::new(da_bytes.unwrap());
// save to file
let mut file = File::create(filename)?;
file.write_all(da.0.as_slice())?;
file.flush()?;
// load from file
let mut file = File::open(filename)?;
let mut buf = Vec::new();
let _ = file.read_to_end(&mut buf)?;
let da = DoubleArray::new(buf);
// test search
for (key, value) in keyset.iter() {
let v = da.exact_match_search(key).unwrap();
assert_eq!(v, *value);
}
assert_eq!(
da.common_prefix_search(&"aaaa").collect::<Vec<_>>(),
vec![(0, 1), (1, 2), (2, 3)]
);
assert_eq!(
da.common_prefix_search(&"bcde").collect::<Vec<_>>(),
vec![(3, 1), (4, 3)]
);
Ok(())
}
More examples
examples/build_and_search.rs (line 39)
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
fn main() {
// make a keyset which have key-value pairs
let keyset = &[
("a".as_bytes(), 0),
("ab".as_bytes(), 1),
("abc".as_bytes(), 2),
("b".as_bytes(), 3),
("bc".as_bytes(), 4),
("c".as_bytes(), 5),
];
// build a double-array trie binary
let da_bytes = DoubleArrayBuilder::build(keyset);
assert!(da_bytes.is_some());
// create a double-array trie instance
let da = DoubleArray::new(da_bytes.unwrap());
// exact match search
for (key, value) in keyset {
assert_eq!(da.exact_match_search(key), Some(*value as u32));
}
assert_eq!(da.exact_match_search("aa".as_bytes()), None);
assert_eq!(da.exact_match_search("aba".as_bytes()), None);
assert_eq!(da.exact_match_search("abb".as_bytes()), None);
assert_eq!(da.exact_match_search("abcd".as_bytes()), None);
assert_eq!(da.exact_match_search("ba".as_bytes()), None);
assert_eq!(da.exact_match_search("bb".as_bytes()), None);
assert_eq!(da.exact_match_search("bcd".as_bytes()), None);
assert_eq!(da.exact_match_search("ca".as_bytes()), None);
// common prefix search
assert_eq!(
da.common_prefix_search("a".as_bytes()).collect::<Vec<_>>(),
vec![(0, 1)] // match "a"
);
assert_eq!(
da.common_prefix_search("abc".as_bytes())
.collect::<Vec<_>>(),
vec![(0, 1), (1, 2), (2, 3)] // match "a", "ab", "abc"
);
assert_eq!(
da.common_prefix_search("abcd".as_bytes())
.collect::<Vec<_>>(),
vec![(0, 1), (1, 2), (2, 3)] // match "a", "ab", "abc"
);
assert_eq!(
da.common_prefix_search("bcd".as_bytes())
.collect::<Vec<_>>(),
vec![(3, 1), (4, 2)] // match "b", "bc"
);
assert_eq!(
da.common_prefix_search("d".as_bytes()).collect::<Vec<_>>(),
vec![] // don't match
);
}
Trait Implementations§
Auto Trait Implementations§
impl<T> RefUnwindSafe for DoubleArray<T>where
T: RefUnwindSafe,
impl<T> Send for DoubleArray<T>where
T: Send,
impl<T> Sync for DoubleArray<T>where
T: Sync,
impl<T> Unpin for DoubleArray<T>where
T: Unpin,
impl<T> UnwindSafe for DoubleArray<T>where
T: UnwindSafe,
Blanket Implementations§
source§impl<T> BorrowMut<T> for Twhere
T: ?Sized,
impl<T> BorrowMut<T> for Twhere
T: ?Sized,
source§fn borrow_mut(&mut self) -> &mut T
fn borrow_mut(&mut self) -> &mut T
Mutably borrows from an owned value. Read more