+
−// This file is part of ICU4X. For terms of use, please see the file
+
−// called LICENSE at the top level of the ICU4X source tree
+
−// (online at: https://github.com/unicode-org/icu4x/blob/main/LICENSE ).
+
−
+
−use litemap::LiteMap;
+
−use zerotrie::ZeroTriePerfectHash;
+
−use zerotrie::ZeroTrieSimpleAscii;
+
−
+
−mod testdata {
+
−    include!("data/data.rs");
+
−}
+
−
+
−use testdata::strings_to_litemap;
+
−
+
−const NON_EXISTENT_STRINGS: &[&str] = &[
+
−    "a9PS", "ahsY", "ahBO", "a8IN", "xk8o", "xv1l", "xI2S", "618y", "d6My", "uszy",
+
−];
+
−
+
−macro_rules! assert_bytes_eq {
+
−    ($len:literal, $a:expr, $b:expr) => {
+
−        assert_eq!($len, $a.len());
+
−        assert_eq!($a, $b);
+
−    };
+
−}
+
−
+
−fn check_simple_ascii_trie<S>(items: &LiteMap<&[u8], usize>, trie: &ZeroTrieSimpleAscii<S>)
+
−where
+
−    S: AsRef<[u8]> + ?Sized,
+
−{
+
−    // Check that each item is in the trie
+
−    for (k, v) in items.iter() {
+
−        assert_eq!(trie.get(k), Some(*v));
+
−    }
+
−    // Check that some items are not in the trie
+
−    for s in NON_EXISTENT_STRINGS.iter() {
+
−        assert_eq!(trie.get(s.as_bytes()), None);
+
−    }
+
−    // Check that the iterator returns items in the same order as the LiteMap
+
−    assert!(items
+
−        .iter()
+
−        .map(|(s, v)| (String::from_utf8(s.to_vec()).unwrap(), *v))
+
−        .eq(trie.iter()));
+
−    // Check that the const builder works
+
−    let const_trie = ZeroTrieSimpleAscii::try_from_litemap_with_const_builder(items).unwrap();
+
−    assert_eq!(trie.as_bytes(), const_trie.as_bytes());
+
−}
+
−
+
−fn check_phf_ascii_trie<S>(items: &LiteMap<&[u8], usize>, trie: &ZeroTriePerfectHash<S>)
+
−where
+
−    S: AsRef<[u8]> + ?Sized,
+
−{
+
−    // Check that each item is in the trie
+
−    for (k, v) in items.iter() {
+
−        assert_eq!(trie.get(k), Some(*v));
+
−    }
+
−    // Check that some items are not in the trie
+
−    for s in NON_EXISTENT_STRINGS.iter() {
+
−        assert_eq!(trie.get(s.as_bytes()), None);
+
−    }
+
−    // Check that the iterator returns the contents of the LiteMap
+
−    // Note: Since the items might not be in order, we collect them into a new LiteMap
+
−    let recovered_items: LiteMap<_, _> = trie.iter().collect();
+
−    assert_eq!(
+
−        items.to_borrowed_keys_values::<[u8], usize, Vec<_>>(),
+
−        recovered_items.to_borrowed_keys_values()
+
−    );
+
−}
+
−
+
−fn check_phf_bytes_trie<S>(items: &LiteMap<&[u8], usize>, trie: &ZeroTriePerfectHash<S>)
+
−where
+
−    S: AsRef<[u8]> + ?Sized,
+
−{
+
−    // Check that each item is in the trie
+
−    for (k, v) in items.iter() {
+
−        assert_eq!(trie.get(k), Some(*v), "{k:?}");
+
−    }
+
−    // Check that some items are not in the trie
+
−    for s in NON_EXISTENT_STRINGS.iter() {
+
−        assert_eq!(trie.get(s.as_bytes()), None, "{s:?}");
+
−    }
+
−    // Check that the iterator returns the contents of the LiteMap
+
−    // Note: Since the items might not be in order, we collect them into a new LiteMap
+
−    let recovered_items: LiteMap<_, _> = trie.iter().collect();
+
−    assert_eq!(
+
−        items.to_borrowed_keys_values::<[u8], usize, Vec<_>>(),
+
−        recovered_items.to_borrowed_keys_values()
+
−    );
+
−}
+
−
+
−#[test]
+
−fn test_basic() {
+
−    let lm1a: LiteMap<&[u8], usize> = testdata::basic::DATA_ASCII.iter().copied().collect();
+
−    let lm1b: LiteMap<&[u8], usize> = lm1a.to_borrowed_keys();
+
−    let lm2: LiteMap<&[u8], usize> = testdata::basic::DATA_UNICODE.iter().copied().collect();
+
−    let lm3: LiteMap<&[u8], usize> = testdata::basic::DATA_BINARY.iter().copied().collect();
+
−
+
−    let expected_bytes = testdata::basic::TRIE_ASCII;
+
−    let trie = ZeroTrieSimpleAscii::try_from(&lm1a).unwrap();
+
−    assert_bytes_eq!(26, trie.as_bytes(), expected_bytes);
+
−    check_simple_ascii_trie(&lm1a, &trie);
+
−
+
−    let trie = ZeroTriePerfectHash::try_from(&lm1b).unwrap();
+
−    assert_bytes_eq!(26, trie.as_bytes(), expected_bytes);
+
−    check_phf_ascii_trie(&lm1a, &trie);
+
−
+
−    let expected_bytes = testdata::basic::TRIE_UNICODE;
+
−    let trie = ZeroTriePerfectHash::try_from(&lm2).unwrap();
+
−    assert_bytes_eq!(39, trie.as_bytes(), expected_bytes);
+
−    check_phf_bytes_trie(&lm2, &trie);
+
−
+
−    let expected_bytes = testdata::basic::TRIE_BINARY;
+
−    let trie = ZeroTriePerfectHash::try_from(&lm3).unwrap();
+
−    assert_bytes_eq!(26, trie.as_bytes(), expected_bytes);
+
−    check_phf_bytes_trie(&lm3, &trie);
+
−}
+
−
+
−#[test]
+
−fn test_empty() {
+
−    let trie = ZeroTrieSimpleAscii::try_from(&LiteMap::<&[u8], usize>::new_vec()).unwrap();
+
−    assert_eq!(trie.byte_len(), 0);
+
−    assert!(trie.is_empty());
+
−    assert_eq!(trie.get(b""), None);
+
−    assert_eq!(trie.as_bytes(), &[]);
+
−}
+
−
+
−#[test]
+
−fn test_single_empty_value() {
+
−    let litemap: LiteMap<&[u8], usize> = [
+
−        (&b""[..], 10), //
+
−    ]
+
−    .into_iter()
+
−    .collect();
+
−    let trie = ZeroTrieSimpleAscii::try_from(&litemap.as_sliced()).unwrap();
+
−    assert_eq!(trie.get(b""), Some(10));
+
−    assert_eq!(trie.get(b"x"), None);
+
−    let expected_bytes = &[0b10001010];
+
−    assert_eq!(trie.as_bytes(), expected_bytes);
+
−
+
−    let litemap_bytes = litemap.to_borrowed_keys::<[u8], Vec<_>>();
+
−    let trie_phf = ZeroTriePerfectHash::try_from(&litemap_bytes).unwrap();
+
−    assert_bytes_eq!(1, trie_phf.as_bytes(), expected_bytes);
+
−    check_phf_ascii_trie(&litemap, &trie_phf);
+
−}
+
−
+
−#[test]
+
−fn test_single_byte_string() {
+
−    let litemap: LiteMap<&[u8], usize> = [
+
−        (&b"x"[..], 10), //
+
−    ]
+
−    .into_iter()
+
−    .collect();
+
−    let trie = ZeroTrieSimpleAscii::try_from(&litemap.as_sliced()).unwrap();
+
−    assert_eq!(trie.get(b""), None);
+
−    assert_eq!(trie.get(b"xy"), None);
+
−    check_simple_ascii_trie(&litemap, &trie);
+
−    let expected_bytes = &[b'x', 0b10001010];
+
−    assert_bytes_eq!(2, trie.as_bytes(), expected_bytes);
+
−
+
−    let litemap_bytes = litemap.to_borrowed_keys::<[u8], Vec<_>>();
+
−    let trie_phf = ZeroTriePerfectHash::try_from(&litemap_bytes).unwrap();
+
−    assert_bytes_eq!(2, trie_phf.as_bytes(), expected_bytes);
+
−    check_phf_ascii_trie(&litemap, &trie_phf);
+
−}
+
−
+
−#[test]
+
−fn test_single_string() {
+
−    let litemap: LiteMap<&[u8], usize> = [
+
−        (&b"xyz"[..], 10), //
+
−    ]
+
−    .into_iter()
+
−    .collect();
+
−    let trie = ZeroTrieSimpleAscii::try_from(&litemap.as_sliced()).unwrap();
+
−    assert_eq!(trie.get(b""), None);
+
−    assert_eq!(trie.get(b"x"), None);
+
−    assert_eq!(trie.get(b"xy"), None);
+
−    assert_eq!(trie.get(b"xyzz"), None);
+
−    check_simple_ascii_trie(&litemap, &trie);
+
−    let expected_bytes = &[b'x', b'y', b'z', 0b10001010];
+
−    assert_bytes_eq!(4, trie.as_bytes(), expected_bytes);
+
−
+
−    let litemap_bytes = litemap.to_borrowed_keys::<[u8], Vec<_>>();
+
−    let trie_phf = ZeroTriePerfectHash::try_from(&litemap_bytes).unwrap();
+
−    assert_bytes_eq!(4, trie_phf.as_bytes(), expected_bytes);
+
−    check_phf_ascii_trie(&litemap, &trie_phf);
+
−}
+
−
+
−#[test]
+
−fn test_prefix_strings() {
+
−    let litemap: LiteMap<&[u8], usize> = [(&b"x"[..], 0), (b"xy", 1)].into_iter().collect();
+
−    let trie = ZeroTrieSimpleAscii::try_from(&litemap.as_sliced()).unwrap();
+
−    assert_eq!(trie.get(b""), None);
+
−    assert_eq!(trie.get(b"xyz"), None);
+
−    check_simple_ascii_trie(&litemap, &trie);
+
−    let expected_bytes = &[b'x', 0b10000000, b'y', 0b10000001];
+
−    assert_bytes_eq!(4, trie.as_bytes(), expected_bytes);
+
−
+
−    let litemap_bytes = litemap.to_borrowed_keys::<[u8], Vec<_>>();
+
−    let trie_phf = ZeroTriePerfectHash::try_from(&litemap_bytes).unwrap();
+
−    assert_bytes_eq!(4, trie_phf.as_bytes(), expected_bytes);
+
−    check_phf_ascii_trie(&litemap, &trie_phf);
+
−}
+
−
+
−#[test]
+
−fn test_single_byte_branch() {
+
−    let litemap: LiteMap<&[u8], usize> = [(&b"x"[..], 0), (b"y", 1)].into_iter().collect();
+
−    let trie = ZeroTrieSimpleAscii::try_from(&litemap.as_sliced()).unwrap();
+
−    assert_eq!(trie.get(b""), None);
+
−    assert_eq!(trie.get(b"xy"), None);
+
−    check_simple_ascii_trie(&litemap, &trie);
+
−    let expected_bytes = &[0b11000010, b'x', b'y', 1, 0b10000000, 0b10000001];
+
−    assert_bytes_eq!(6, trie.as_bytes(), expected_bytes);
+
−
+
−    let litemap_bytes = litemap.to_borrowed_keys::<[u8], Vec<_>>();
+
−    let trie_phf = ZeroTriePerfectHash::try_from(&litemap_bytes).unwrap();
+
−    assert_bytes_eq!(6, trie_phf.as_bytes(), expected_bytes);
+
−    check_phf_ascii_trie(&litemap, &trie_phf);
+
−}
+
−
+
−#[test]
+
−fn test_multi_byte_branch() {
+
−    let litemap: LiteMap<&[u8], usize> = [(&b"axb"[..], 0), (b"ayc", 1)].into_iter().collect();
+
−    let trie = ZeroTrieSimpleAscii::try_from(&litemap.as_sliced()).unwrap();
+
−    assert_eq!(trie.get(b""), None);
+
−    assert_eq!(trie.get(b"a"), None);
+
−    assert_eq!(trie.get(b"ax"), None);
+
−    assert_eq!(trie.get(b"ay"), None);
+
−    check_simple_ascii_trie(&litemap, &trie);
+
−    let expected_bytes = &[
+
−        b'a', 0b11000010, b'x', b'y', 2, b'b', 0b10000000, b'c', 0b10000001,
+
−    ];
+
−    assert_bytes_eq!(9, trie.as_bytes(), expected_bytes);
+
−
+
−    let litemap_bytes = litemap.to_borrowed_keys::<[u8], Vec<_>>();
+
−    let trie_phf = ZeroTriePerfectHash::try_from(&litemap_bytes).unwrap();
+
−    assert_bytes_eq!(9, trie_phf.as_bytes(), expected_bytes);
+
−    check_phf_ascii_trie(&litemap, &trie_phf);
+
−}
+
−
+
−#[test]
+
−fn test_linear_varint_values() {
+
−    let litemap: LiteMap<&[u8], usize> = [(&b""[..], 100), (b"x", 500), (b"xyz", 5000)]
+
−        .into_iter()
+
−        .collect();
+
−    let trie = ZeroTrieSimpleAscii::try_from(&litemap.as_sliced()).unwrap();
+
−    assert_eq!(trie.get(b"xy"), None);
+
−    assert_eq!(trie.get(b"xz"), None);
+
−    assert_eq!(trie.get(b"xyzz"), None);
+
−    check_simple_ascii_trie(&litemap, &trie);
+
−    let expected_bytes = &[0x90, 0x54, b'x', 0x93, 0x64, b'y', b'z', 0x90, 0x96, 0x78];
+
−    assert_bytes_eq!(10, trie.as_bytes(), expected_bytes);
+
−
+
−    let litemap_bytes = litemap.to_borrowed_keys::<[u8], Vec<_>>();
+
−    let trie_phf = ZeroTriePerfectHash::try_from(&litemap_bytes).unwrap();
+
−    assert_bytes_eq!(10, trie_phf.as_bytes(), expected_bytes);
+
−    check_phf_ascii_trie(&litemap, &trie_phf);
+
−}
+
−
+
−#[test]
+
−fn test_bug() {
+
−    let litemap: LiteMap<&[u8], usize> = [(&b"abc"[..], 100), (b"abcd", 500), (b"abcde", 5000)]
+
−        .into_iter()
+
−        .collect();
+
−    let trie = ZeroTrieSimpleAscii::try_from(&litemap.as_sliced()).unwrap();
+
−    assert_eq!(trie.get(b"ab"), None);
+
−    assert_eq!(trie.get(b"abd"), None);
+
−    assert_eq!(trie.get(b"abCD"), None);
+
−    check_simple_ascii_trie(&litemap, &trie);
+
−
+
−    let litemap_bytes = litemap.to_borrowed_keys::<[u8], Vec<_>>();
+
−    let trie_phf = ZeroTriePerfectHash::try_from(&litemap_bytes).unwrap();
+
−    check_phf_ascii_trie(&litemap, &trie_phf);
+
−}
+
−
+
−#[test]
+
−fn test_varint_branch() {
+
−    let chars = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
+
−    let litemap: LiteMap<&[u8], usize> = (0..chars.len())
+
−        .map(|i| (chars.get(i..i + 1).unwrap().as_bytes(), i))
+
−        .collect();
+
−    let trie = ZeroTrieSimpleAscii::try_from(&litemap.as_sliced()).unwrap();
+
−    assert_eq!(trie.get(b""), None);
+
−    assert_eq!(trie.get(b"ax"), None);
+
−    assert_eq!(trie.get(b"ay"), None);
+
−    check_simple_ascii_trie(&litemap, &trie);
+
−    #[rustfmt::skip]
+
−    let expected_bytes = &[
+
−        0b11100000, // branch varint lead
+
−        0x14,       // branch varint trail
+
−        // search array:
+
−        b'A', b'B', b'C', b'D', b'E', b'F', b'G', b'H', b'I', b'J',
+
−        b'K', b'L', b'M', b'N', b'O', b'P', b'Q', b'R', b'S', b'T',
+
−        b'U', b'V', b'W', b'X', b'Y', b'Z',
+
−        b'a', b'b', b'c', b'd', b'e', b'f', b'g', b'h', b'i', b'j',
+
−        b'k', b'l', b'm', b'n', b'o', b'p', b'q', b'r', b's', b't',
+
−        b'u', b'v', b'w', b'x', b'y', b'z',
+
−        // offset array:
+
−        1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 18, 20,
+
−        22, 24, 26, 28, 30, 32, 34, 36, 38, 40, 42, 44, 46, 48, 50, 52,
+
−        54, 56, 58, 60, 62, 64, 66, 68, 70, 72, 74, 76, 78, 80, 82, 84,
+
−        86,
+
−        // single-byte values:
+
−        0x80, (0x80 | 1), (0x80 | 2), (0x80 | 3), (0x80 | 4),
+
−        (0x80 | 5), (0x80 | 6), (0x80 | 7), (0x80 | 8), (0x80 | 9),
+
−        (0x80 | 10), (0x80 | 11), (0x80 | 12), (0x80 | 13), (0x80 | 14),
+
−        (0x80 | 15),
+
−        // multi-byte values:
+
−        0x90, 0, 0x90, 1, 0x90, 2, 0x90, 3, 0x90, 4, 0x90, 5,
+
−        0x90, 6, 0x90, 7, 0x90, 8, 0x90, 9, 0x90, 10, 0x90, 11,
+
−        0x90, 12, 0x90, 13, 0x90, 14, 0x90, 15, 0x90, 16, 0x90, 17,
+
−        0x90, 18, 0x90, 19, 0x90, 20, 0x90, 21, 0x90, 22, 0x90, 23,
+
−        0x90, 24, 0x90, 25, 0x90, 26, 0x90, 27, 0x90, 28, 0x90, 29,
+
−        0x90, 30, 0x90, 31, 0x90, 32, 0x90, 33, 0x90, 34, 0x90, 35,
+
−    ];
+
−    assert_bytes_eq!(193, trie.as_bytes(), expected_bytes);
+
−
+
−    #[rustfmt::skip]
+
−    let expected_bytes = &[
+
−        0b11100000, // branch varint lead
+
−        0x14,       // branch varint trail
+
−        // PHF metadata:
+
−        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 6, 10, 12, 16, 4, 4, 4, 4, 4, 4, 8,
+
−        4, 4, 4, 16, 16, 16, 16, 16, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+
−        0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 0, 7,
+
−        // search array:
+
−        b'h', b'i', b'j', b'k', b'l', b'm', b'n', b'o',
+
−        b'p', b'u', b'v', b'w', b'D', b'E', b'F', b'q',
+
−        b'r', b'A', b'B', b'C', b'x', b'y', b'z', b's',
+
−        b'H', b'I', b'J', b'G', b'P', b'Q', b'R', b'S',
+
−        b'T', b'U', b'V', b'W', b'X', b'Y', b'Z', b'K',
+
−        b'L', b'M', b'N', b'O', b'g', b'a', b'b', b'c',
+
−        b't', b'd', b'f', b'e',
+
−        // offset array:
+
−        2, 4, 6, 8, 10, 12, 14,
+
−        16, 18, 20, 22, 24, 25, 26, 27,
+
−        29, 31, 32, 33, 34, 36, 38, 40,
+
−        42, 43, 44, 45, 46, 47, 49, 51,
+
−        53, 55, 57, 59, 61, 63, 65, 67,
+
−        68, 69, 70, 71, 72, 74, 76, 78,
+
−        80, 82, 84, 86,
+
−        // values:
+
−        0x90, 17, 0x90, 18, 0x90, 19, 0x90, 20, 0x90, 21, 0x90, 22, 0x90, 23,
+
−        0x90, 24, 0x90, 25, 0x90, 30, 0x90, 31, 0x90, 32, 0x80 | 3, 0x80 | 4,
+
−        0x80 | 5, 0x90, 26, 0x90, 27, 0x80, 0x80 | 1, 0x80 | 2, 0x90, 33,
+
−        0x90, 34, 0x90, 35, 0x90, 28, 0x80 | 7, 0x80 | 8, 0x80 | 9, 0x80 | 6,
+
−        0x80 | 15, 0x90, 0, 0x90, 1, 0x90, 2, 0x90, 3, 0x90, 4, 0x90, 5,
+
−        0x90, 6, 0x90, 7, 0x90, 8, 0x90, 9, 0x80 | 10, 0x80 | 11, 0x80 | 12,
+
−        0x80 | 13, 0x80 | 14, 0x90, 16, 0x90, 10, 0x90, 11, 0x90, 12, 0x90, 29,
+
−        0x90, 13, 0x90, 15, 0x90, 14,
+
−    ];
+
−    let litemap_bytes = litemap.to_borrowed_keys::<[u8], Vec<_>>();
+
−    let trie_phf = ZeroTriePerfectHash::try_from(&litemap_bytes).unwrap();
+
−    assert_bytes_eq!(246, trie_phf.as_bytes(), expected_bytes);
+
−    check_phf_ascii_trie(&litemap, &trie_phf);
+
−}
+
−
+
−#[test]
+
−fn test_below_wide() {
+
−    let litemap: LiteMap<&[u8], usize> = [
+
−        (&b"abcdefghijklmnopqrstuvwxyz"[..], 1),
+
−        (b"bcdefghijklmnopqrstuvwxyza", 2),
+
−        (b"cdefghijklmnopqrstuvwxyzab", 3),
+
−        (b"defghijklmnopqrstuvwxyzabc", 4),
+
−        (b"efghijklmnopqrstuvwxyzabcd", 5),
+
−        (b"fghijklmnopqrstuvwxyzabcde", 6),
+
−        (b"ghijklmnopqrstuvwxyzabcdef", 7),
+
−        (b"hijklmnopqrstuvwxyzabcdefg", 8),
+
−        (b"ijklmnopqrstuvwxyzabcdefgh", 9),
+
−        (b"jklmnopqrstuvwxyzabcd", 10),
+
−    ]
+
−    .into_iter()
+
−    .collect();
+
−    let trie = ZeroTrieSimpleAscii::try_from(&litemap.as_sliced()).unwrap();
+
−    assert_eq!(trie.get(b""), None);
+
−    assert_eq!(trie.get(b"abc"), None);
+
−    check_simple_ascii_trie(&litemap, &trie);
+
−    #[rustfmt::skip]
+
−    let expected_bytes = &[
+
−        0b11001010, // branch
+
−        // search array:
+
−        b'a', b'b', b'c', b'd', b'e', b'f', b'g', b'h', b'i', b'j',
+
−        // offset array:
+
−        26, 52, 78, 104, 130, 156, 182, 208, 234,
+
−        // offset data:
+
−        b'b', b'c', b'd', b'e', b'f', b'g', b'h', b'i', b'j', b'k', b'l', b'm', b'n',
+
−        b'o', b'p', b'q', b'r', b's', b't', b'u', b'v', b'w', b'x', b'y', b'z',
+
−        0x81,
+
−        b'c', b'd', b'e', b'f', b'g', b'h', b'i', b'j', b'k', b'l', b'm', b'n', b'o',
+
−        b'p', b'q', b'r', b's', b't', b'u', b'v', b'w', b'x', b'y', b'z', b'a',
+
−        0x82,
+
−        b'd', b'e', b'f', b'g', b'h', b'i', b'j', b'k', b'l', b'm', b'n', b'o', b'p',
+
−        b'q', b'r', b's', b't', b'u', b'v', b'w', b'x', b'y', b'z', b'a', b'b',
+
−        0x83,
+
−        b'e', b'f', b'g', b'h', b'i', b'j', b'k', b'l', b'm', b'n', b'o', b'p', b'q',
+
−        b'r', b's', b't', b'u', b'v', b'w', b'x', b'y', b'z', b'a', b'b', b'c',
+
−        0x84,
+
−        b'f', b'g', b'h', b'i', b'j', b'k', b'l', b'm', b'n', b'o', b'p', b'q', b'r',
+
−        b's', b't', b'u', b'v', b'w', b'x', b'y', b'z', b'a', b'b', b'c', b'd',
+
−        0x85,
+
−        b'g', b'h', b'i', b'j', b'k', b'l', b'm', b'n', b'o', b'p', b'q', b'r', b's',
+
−        b't', b'u', b'v', b'w', b'x', b'y', b'z', b'a', b'b', b'c', b'd', b'e',
+
−        0x86,
+
−        b'h', b'i', b'j', b'k', b'l', b'm', b'n', b'o', b'p', b'q', b'r', b's', b't',
+
−        b'u', b'v', b'w', b'x', b'y', b'z', b'a', b'b', b'c', b'd', b'e', b'f',
+
−        0x87,
+
−        b'i', b'j', b'k', b'l', b'm', b'n', b'o', b'p', b'q', b'r', b's', b't', b'u',
+
−        b'v', b'w', b'x', b'y', b'z', b'a', b'b', b'c', b'd', b'e', b'f', b'g',
+
−        0x88,
+
−        b'j', b'k', b'l', b'm', b'n', b'o', b'p', b'q', b'r', b's', b't', b'u', b'v',
+
−        b'w', b'x', b'y', b'z', b'a', b'b', b'c', b'd', b'e', b'f', b'g', b'h',
+
−        0x89,
+
−        b'k', b'l', b'm', b'n', b'o', b'p', b'q', b'r', b's', b't', b'u', b'v', b'w',
+
−        b'x', b'y', b'z', b'a', b'b', b'c', b'd',
+
−        0x8A,
+
−    ];
+
−    assert_bytes_eq!(275, trie.as_bytes(), expected_bytes);
+
−}
+
−
+
−#[test]
+
−fn test_at_wide() {
+
−    let litemap: LiteMap<&[u8], usize> = [
+
−        (&b"abcdefghijklmnopqrstuvwxyz"[..], 1),
+
−        (b"bcdefghijklmnopqrstuvwxyza", 2),
+
−        (b"cdefghijklmnopqrstuvwxyzab", 3),
+
−        (b"defghijklmnopqrstuvwxyzabc", 4),
+
−        (b"efghijklmnopqrstuvwxyzabcd", 5),
+
−        (b"fghijklmnopqrstuvwxyzabcde", 6),
+
−        (b"ghijklmnopqrstuvwxyzabcdef", 7),
+
−        (b"hijklmnopqrstuvwxyzabcdefg", 8),
+
−        (b"ijklmnopqrstuvwxyzabcdefgh", 9),
+
−        (b"jklmnopqrstuvwxyzabcde", 10),
+
−    ]
+
−    .into_iter()
+
−    .collect();
+
−    let trie = ZeroTrieSimpleAscii::try_from(&litemap.as_sliced()).unwrap();
+
−    assert_eq!(trie.get(b""), None);
+
−    assert_eq!(trie.get(b"abc"), None);
+
−    check_simple_ascii_trie(&litemap, &trie);
+
−    #[rustfmt::skip]
+
−    let expected_bytes = &[
+
−        0b11100001, // branch lead
+
−        0x6A, // branch trail
+
−        // search array:
+
−        b'a', b'b', b'c', b'd', b'e', b'f', b'g', b'h', b'i', b'j',
+
−        // offset array (wide):
+
−        0, 0, 0, 0, 0, 0, 0, 0, 0,
+
−        26, 52, 78, 104, 130, 156, 182, 208, 234,
+
−        // offset data:
+
−        b'b', b'c', b'd', b'e', b'f', b'g', b'h', b'i', b'j', b'k', b'l', b'm', b'n',
+
−        b'o', b'p', b'q', b'r', b's', b't', b'u', b'v', b'w', b'x', b'y', b'z',
+
−        0x81,
+
−        b'c', b'd', b'e', b'f', b'g', b'h', b'i', b'j', b'k', b'l', b'm', b'n', b'o',
+
−        b'p', b'q', b'r', b's', b't', b'u', b'v', b'w', b'x', b'y', b'z', b'a',
+
−        0x82,
+
−        b'd', b'e', b'f', b'g', b'h', b'i', b'j', b'k', b'l', b'm', b'n', b'o', b'p',
+
−        b'q', b'r', b's', b't', b'u', b'v', b'w', b'x', b'y', b'z', b'a', b'b',
+
−        0x83,
+
−        b'e', b'f', b'g', b'h', b'i', b'j', b'k', b'l', b'm', b'n', b'o', b'p', b'q',
+
−        b'r', b's', b't', b'u', b'v', b'w', b'x', b'y', b'z', b'a', b'b', b'c',
+
−        0x84,
+
−        b'f', b'g', b'h', b'i', b'j', b'k', b'l', b'm', b'n', b'o', b'p', b'q', b'r',
+
−        b's', b't', b'u', b'v', b'w', b'x', b'y', b'z', b'a', b'b', b'c', b'd',
+
−        0x85,
+
−        b'g', b'h', b'i', b'j', b'k', b'l', b'm', b'n', b'o', b'p', b'q', b'r', b's',
+
−        b't', b'u', b'v', b'w', b'x', b'y', b'z', b'a', b'b', b'c', b'd', b'e',
+
−        0x86,
+
−        b'h', b'i', b'j', b'k', b'l', b'm', b'n', b'o', b'p', b'q', b'r', b's', b't',
+
−        b'u', b'v', b'w', b'x', b'y', b'z', b'a', b'b', b'c', b'd', b'e', b'f',
+
−        0x87,
+
−        b'i', b'j', b'k', b'l', b'm', b'n', b'o', b'p', b'q', b'r', b's', b't', b'u',
+
−        b'v', b'w', b'x', b'y', b'z', b'a', b'b', b'c', b'd', b'e', b'f', b'g',
+
−        0x88,
+
−        b'j', b'k', b'l', b'm', b'n', b'o', b'p', b'q', b'r', b's', b't', b'u', b'v',
+
−        b'w', b'x', b'y', b'z', b'a', b'b', b'c', b'd', b'e', b'f', b'g', b'h',
+
−        0x89,
+
−        b'k', b'l', b'm', b'n', b'o', b'p', b'q', b'r', b's', b't', b'u', b'v', b'w',
+
−        b'x', b'y', b'z', b'a', b'b', b'c', b'd', b'e',
+
−        0x8A,
+
−    ];
+
−    assert_bytes_eq!(286, trie.as_bytes(), expected_bytes);
+
−}
+
−
+
−#[test]
+
−fn test_at_wide_plus() {
+
−    let litemap: LiteMap<&[u8], usize> = [
+
−        (&b"abcdefghijklmnopqrstuvwxyz"[..], 1),
+
−        (b"bcdefghijklmnopqrstuvwxyza", 2),
+
−        (b"cdefghijklmnopqrstuvwxyzab", 3),
+
−        (b"defghijklmnopqrstuvwxyzabc", 4),
+
−        (b"efghijklmnopqrstuvwxyzabcd", 5),
+
−        (b"fghijklmnopqrstuvwxyzabcde", 6),
+
−        (b"ghijklmnopqrstuvwxyzabcdef", 7),
+
−        (b"hijklmnopqrstuvwxyzabcdefg", 8),
+
−        (b"ijklmnopqrstuvwxyzabcdefgh", 9),
+
−        (b"jklmnopqrstuvwxyzabcdef", 10),
+
−    ]
+
−    .into_iter()
+
−    .collect();
+
−    let trie = ZeroTrieSimpleAscii::try_from(&litemap.as_sliced()).unwrap();
+
−    assert_eq!(trie.get(b""), None);
+
−    assert_eq!(trie.get(b"abc"), None);
+
−    check_simple_ascii_trie(&litemap, &trie);
+
−    #[rustfmt::skip]
+
−    let expected_bytes = &[
+
−        0b11100001, // branch lead
+
−        0x6A, // branch trail
+
−        // search array:
+
−        b'a', b'b', b'c', b'd', b'e', b'f', b'g', b'h', b'i', b'j',
+
−        // offset array (wide):
+
−        0, 0, 0, 0, 0, 0, 0, 0, 0,
+
−        26, 52, 78, 104, 130, 156, 182, 208, 234,
+
−        // offset data:
+
−        b'b', b'c', b'd', b'e', b'f', b'g', b'h', b'i', b'j', b'k', b'l', b'm', b'n',
+
−        b'o', b'p', b'q', b'r', b's', b't', b'u', b'v', b'w', b'x', b'y', b'z',
+
−        0x81,
+
−        b'c', b'd', b'e', b'f', b'g', b'h', b'i', b'j', b'k', b'l', b'm', b'n', b'o',
+
−        b'p', b'q', b'r', b's', b't', b'u', b'v', b'w', b'x', b'y', b'z', b'a',
+
−        0x82,
+
−        b'd', b'e', b'f', b'g', b'h', b'i', b'j', b'k', b'l', b'm', b'n', b'o', b'p',
+
−        b'q', b'r', b's', b't', b'u', b'v', b'w', b'x', b'y', b'z', b'a', b'b',
+
−        0x83,
+
−        b'e', b'f', b'g', b'h', b'i', b'j', b'k', b'l', b'm', b'n', b'o', b'p', b'q',
+
−        b'r', b's', b't', b'u', b'v', b'w', b'x', b'y', b'z', b'a', b'b', b'c',
+
−        0x84,
+
−        b'f', b'g', b'h', b'i', b'j', b'k', b'l', b'm', b'n', b'o', b'p', b'q', b'r',
+
−        b's', b't', b'u', b'v', b'w', b'x', b'y', b'z', b'a', b'b', b'c', b'd',
+
−        0x85,
+
−        b'g', b'h', b'i', b'j', b'k', b'l', b'm', b'n', b'o', b'p', b'q', b'r', b's',
+
−        b't', b'u', b'v', b'w', b'x', b'y', b'z', b'a', b'b', b'c', b'd', b'e',
+
−        0x86,
+
−        b'h', b'i', b'j', b'k', b'l', b'm', b'n', b'o', b'p', b'q', b'r', b's', b't',
+
−        b'u', b'v', b'w', b'x', b'y', b'z', b'a', b'b', b'c', b'd', b'e', b'f',
+
−        0x87,
+
−        b'i', b'j', b'k', b'l', b'm', b'n', b'o', b'p', b'q', b'r', b's', b't', b'u',
+
−        b'v', b'w', b'x', b'y', b'z', b'a', b'b', b'c', b'd', b'e', b'f', b'g',
+
−        0x88,
+
−        b'j', b'k', b'l', b'm', b'n', b'o', b'p', b'q', b'r', b's', b't', b'u', b'v',
+
−        b'w', b'x', b'y', b'z', b'a', b'b', b'c', b'd', b'e', b'f', b'g', b'h',
+
−        0x89,
+
−        b'k', b'l', b'm', b'n', b'o', b'p', b'q', b'r', b's', b't', b'u', b'v', b'w',
+
−        b'x', b'y', b'z', b'a', b'b', b'c', b'd', b'e', b'f',
+
−        0x8A,
+
−    ];
+
−    assert_bytes_eq!(287, trie.as_bytes(), expected_bytes);
+
−}
+
−
+
−#[test]
+
−fn test_everything() {
+
−    let litemap: LiteMap<&[u8], usize> = [
+
−        (&b""[..], 0),
+
−        (b"axb", 100),
+
−        (b"ayc", 2),
+
−        (b"azd", 3),
+
−        (b"bxe", 4),
+
−        (b"bxefg", 500),
+
−        (b"bxefh", 6),
+
−        (b"bxei", 7),
+
−        (b"bxeikl", 8),
+
−    ]
+
−    .into_iter()
+
−    .collect();
+
−    let trie = ZeroTrieSimpleAscii::try_from(&litemap.as_sliced()).unwrap();
+
−    assert_eq!(trie.get(b""), Some(0));
+
−    assert_eq!(trie.get(b"a"), None);
+
−    assert_eq!(trie.get(b"ax"), None);
+
−    assert_eq!(trie.get(b"ay"), None);
+
−    check_simple_ascii_trie(&litemap, &trie);
+
−    let expected_bytes = &[
+
−        0b10000000, // value 0
+
−        0b11000010, // branch of 2
+
−        b'a',       //
+
−        b'b',       //
+
−        13,         //
+
−        0b11000011, // branch of 3
+
−        b'x',       //
+
−        b'y',       //
+
−        b'z',       //
+
−        3,          //
+
−        5,          //
+
−        b'b',       //
+
−        0b10010000, // value 100 (lead)
+
−        0x54,       // value 100 (trail)
+
−        b'c',       //
+
−        0b10000010, // value 2
+
−        b'd',       //
+
−        0b10000011, // value 3
+
−        b'x',       //
+
−        b'e',       //
+
−        0b10000100, // value 4
+
−        0b11000010, // branch of 2
+
−        b'f',       //
+
−        b'i',       //
+
−        7,          //
+
−        0b11000010, // branch of 2
+
−        b'g',       //
+
−        b'h',       //
+
−        2,          //
+
−        0b10010011, // value 500 (lead)
+
−        0x64,       // value 500 (trail)
+
−        0b10000110, // value 6
+
−        0b10000111, // value 7
+
−        b'k',       //
+
−        b'l',       //
+
−        0b10001000, // value 8
+
−    ];
+
−    assert_bytes_eq!(36, trie.as_bytes(), expected_bytes);
+
−
+
−    #[rustfmt::skip]
+
−    let expected_bytes = &[
+
−        0b10000000, // value 0
+
−        0b11000010, // branch of 2
+
−        b'a',       //
+
−        b'b',       //
+
−        13,         //
+
−        0b11000011, // start of 'a' subtree: branch of 3
+
−        b'x',       //
+
−        b'y',       //
+
−        b'z',       //
+
−        3,          //
+
−        5,          //
+
−        b'b',       //
+
−        0b10010000, // value 100 (lead)
+
−        0x54,       // value 100 (trail)
+
−        b'c',       //
+
−        0b10000010, // value 2
+
−        b'd',       //
+
−        0b10000011, // value 3
+
−        b'x',       // start of 'b' subtree
+
−        b'e',       //
+
−        0b10000100, // value 4
+
−        0b11000010, // branch of 2
+
−        b'f',       //
+
−        b'i',       //
+
−        7,          //
+
−        0b11000010, // branch of 2
+
−        b'g',       //
+
−        b'h',       //
+
−        2,          //
+
−        0b10010011, // value 500 (lead)
+
−        0x64,       // value 500 (trail)
+
−        0b10000110, // value 6
+
−        0b10000111, // value 7
+
−        b'k',       //
+
−        b'l',       //
+
−        0b10001000, // value 8
+
−    ];
+
−    let litemap_bytes = litemap.to_borrowed_keys::<[u8], Vec<_>>();
+
−    let trie_phf = ZeroTriePerfectHash::try_from(&litemap_bytes).unwrap();
+
−    assert_bytes_eq!(36, trie_phf.as_bytes(), expected_bytes);
+
−    check_phf_ascii_trie(&litemap, &trie_phf);
+
−
+
−    let zhm: zerovec::ZeroMap<[u8], u32> = litemap.iter().map(|(a, b)| (*a, *b as u32)).collect();
+
−    let zhm_buf = postcard::to_allocvec(&zhm).unwrap();
+
−    assert_eq!(zhm_buf.len(), 88);
+
−
+
−    let zhm: zerovec::ZeroMap<[u8], u8> = litemap.iter().map(|(a, b)| (*a, *b as u8)).collect();
+
−    let zhm_buf = postcard::to_allocvec(&zhm).unwrap();
+
−    assert_eq!(zhm_buf.len(), 61);
+
−
+
−    let zhm: zerovec::ZeroHashMap<[u8], u32> =
+
−        litemap.iter().map(|(a, b)| (*a, *b as u32)).collect();
+
−    let zhm_buf = postcard::to_allocvec(&zhm).unwrap();
+
−    assert_eq!(zhm_buf.len(), 161);
+
−
+
−    let zhm: zerovec::ZeroHashMap<[u8], u8> = litemap.iter().map(|(a, b)| (*a, *b as u8)).collect();
+
−    let zhm_buf = postcard::to_allocvec(&zhm).unwrap();
+
−    assert_eq!(zhm_buf.len(), 134);
+
−}
+
−
+
−macro_rules! utf8_byte {
+
−    ($ch:expr, $i:literal) => {{
+
−        let mut utf8_encoder_buf = [0u8; 4];
+
−        $ch.encode_utf8(&mut utf8_encoder_buf);
+
−        utf8_encoder_buf[$i]
+
−    }};
+
−}
+
−
+
−#[test]
+
−fn test_non_ascii() {
+
−    let litemap: LiteMap<&[u8], usize> = [
+
−        ("".as_bytes(), 0),
+
−        ("axb".as_bytes(), 100),
+
−        ("ayc".as_bytes(), 2),
+
−        ("azd".as_bytes(), 3),
+
−        ("bxe".as_bytes(), 4),
+
−        ("bxefg".as_bytes(), 500),
+
−        ("bxefh".as_bytes(), 6),
+
−        ("bxei".as_bytes(), 7),
+
−        ("bxeikl".as_bytes(), 8),
+
−        ("bxeiklmΚαλημέρααα".as_bytes(), 9),
+
−        ("bxeiklmαnλo".as_bytes(), 10),
+
−        ("bxeiklmη".as_bytes(), 11),
+
−    ]
+
−    .into_iter()
+
−    .collect();
+
−
+
−    #[rustfmt::skip]
+
−    let expected_bytes = &[
+
−        0b10000000, // value 0
+
−        0b11000010, // branch of 2
+
−        b'a',       //
+
−        b'b',       //
+
−        13,         //
+
−        0b11000011, // start of 'a' subtree: branch of 3
+
−        b'x',       //
+
−        b'y',       //
+
−        b'z',       //
+
−        3,          //
+
−        5,          //
+
−        b'b',       //
+
−        0b10010000, // value 100 (lead)
+
−        0x54,       // value 100 (trail)
+
−        b'c',       //
+
−        0b10000010, // value 2
+
−        b'd',       //
+
−        0b10000011, // value 3
+
−        b'x',       // start of 'b' subtree
+
−        b'e',       //
+
−        0b10000100, // value 4
+
−        0b11000010, // branch of 2
+
−        b'f',       //
+
−        b'i',       //
+
−        7,          //
+
−        0b11000010, // branch of 2
+
−        b'g',       //
+
−        b'h',       //
+
−        2,          //
+
−        0b10010011, // value 500 (lead)
+
−        0x64,       // value 500 (trail)
+
−        0b10000110, // value 6
+
−        0b10000111, // value 7
+
−        b'k',       //
+
−        b'l',       //
+
−        0b10001000, // value 8
+
−        b'm',       //
+
−        0b10100001, // span of length 1
+
−        utf8_byte!('Κ', 0), // NOTE: all three letters have the same lead byte
+
−        0b11000011, // branch of 3
+
−        utf8_byte!('Κ', 1),
+
−        utf8_byte!('α', 1),
+
−        utf8_byte!('η', 1),
+
−        21,
+
−        27,
+
−        0b10110000, // span of length 18 (lead)
+
−        0b00000010, // span of length 18 (trail)
+
−        utf8_byte!('α', 0),
+
−        utf8_byte!('α', 1),
+
−        utf8_byte!('λ', 0),
+
−        utf8_byte!('λ', 1),
+
−        utf8_byte!('η', 0),
+
−        utf8_byte!('η', 1),
+
−        utf8_byte!('μ', 0),
+
−        utf8_byte!('μ', 1),
+
−        utf8_byte!('έ', 0),
+
−        utf8_byte!('έ', 1),
+
−        utf8_byte!('ρ', 0),
+
−        utf8_byte!('ρ', 1),
+
−        utf8_byte!('α', 0),
+
−        utf8_byte!('α', 1),
+
−        utf8_byte!('α', 0),
+
−        utf8_byte!('α', 1),
+
−        utf8_byte!('α', 0),
+
−        utf8_byte!('α', 1),
+
−        0b10001001, // value 9
+
−        b'n',
+
−        0b10100010, // span of length 2
+
−        utf8_byte!('λ', 0),
+
−        utf8_byte!('λ', 1),
+
−        b'o',
+
−        0b10001010, // value 10
+
−        0b10001011, // value 11
+
−    ];
+
−    let trie_phf = ZeroTriePerfectHash::try_from(&litemap).unwrap();
+
−    assert_bytes_eq!(73, trie_phf.as_bytes(), expected_bytes);
+
−    check_phf_bytes_trie(&litemap, &trie_phf);
+
−}
+
−
+
−#[test]
+
−fn test_max_branch() {
+
−    // Evaluate a branch with all 256 possible children
+
−    let mut litemap: LiteMap<&[u8], usize> = LiteMap::new_vec();
+
−    let all_bytes: Vec<u8> = (u8::MIN..=u8::MAX).collect();
+
−    assert_eq!(all_bytes.len(), 256);
+
−    let all_bytes_prefixed: Vec<[u8; 2]> = (u8::MIN..=u8::MAX).map(|x| [b'\0', x]).collect();
+
−    for b in all_bytes.iter() {
+
−        litemap.insert(core::slice::from_ref(b), *b as usize);
+
−    }
+
−    for s in all_bytes_prefixed.iter() {
+
−        litemap.insert(s, s[1] as usize);
+
−    }
+
−    let trie_phf = ZeroTriePerfectHash::try_from(&litemap).unwrap();
+
−    assert_eq!(trie_phf.byte_len(), 3042);
+
−    check_phf_bytes_trie(&litemap, &trie_phf);
+
−}
+
−
+
−#[test]
+
−fn test_short_subtags_10pct() {
+
−    let litemap = strings_to_litemap(testdata::short_subtags_10pct::STRINGS);
+
−
+
−    let trie = ZeroTrieSimpleAscii::try_from(&litemap).unwrap();
+
−    assert_eq!(trie.byte_len(), 1050);
+
−    check_simple_ascii_trie(&litemap, &trie);
+
−
+
−    let litemap_bytes = litemap.to_borrowed_keys::<[u8], Vec<_>>();
+
−    let trie_phf = ZeroTriePerfectHash::try_from(&litemap_bytes).unwrap();
+
−    assert_eq!(trie_phf.byte_len(), 1100);
+
−    check_phf_ascii_trie(&litemap, &trie_phf);
+
−
+
−    let zhm: zerovec::ZeroMap<[u8], u32> = litemap.iter().map(|(a, b)| (*a, *b as u32)).collect();
+
−    let zhm_buf = postcard::to_allocvec(&zhm).unwrap();
+
−    assert_eq!(zhm_buf.len(), 1890);
+
−
+
−    let zhm: zerovec::ZeroMap<[u8], u8> = litemap.iter().map(|(a, b)| (*a, *b as u8)).collect();
+
−    let zhm_buf = postcard::to_allocvec(&zhm).unwrap();
+
−    assert_eq!(zhm_buf.len(), 1326);
+
−
+
−    let zhm: zerovec::ZeroHashMap<[u8], u32> =
+
−        litemap.iter().map(|(a, b)| (*a, *b as u32)).collect();
+
−    let zhm_buf = postcard::to_allocvec(&zhm).unwrap();
+
−    assert_eq!(zhm_buf.len(), 3396);
+
−
+
−    let zhm: zerovec::ZeroHashMap<[u8], u8> = litemap.iter().map(|(a, b)| (*a, *b as u8)).collect();
+
−    let zhm_buf = postcard::to_allocvec(&zhm).unwrap();
+
−    assert_eq!(zhm_buf.len(), 2832);
+
−}
+
−
+
−#[test]
+
−fn test_short_subtags() {
+
−    let litemap = strings_to_litemap(testdata::short_subtags::STRINGS);
+
−
+
−    let trie = ZeroTrieSimpleAscii::try_from(&litemap).unwrap();
+
−    assert_eq!(trie.byte_len(), 8793);
+
−    check_simple_ascii_trie(&litemap, &trie);
+
−
+
−    let litemap_bytes = litemap.to_borrowed_keys::<[u8], Vec<_>>();
+
−    let trie_phf = ZeroTriePerfectHash::try_from(&litemap_bytes).unwrap();
+
−    assert_eq!(trie_phf.byte_len(), 9400);
+
−    check_phf_ascii_trie(&litemap, &trie_phf);
+
−
+
−    let zm: zerovec::ZeroMap<[u8], u32> = litemap.iter().map(|(a, b)| (*a, *b as u32)).collect();
+
−    let zhm_buf = postcard::to_allocvec(&zm).unwrap();
+
−    assert_eq!(zhm_buf.len(), 18931);
+
−
+
−    let zm: zerovec::ZeroMap<[u8], u8> = litemap.iter().map(|(a, b)| (*a, *b as u8)).collect();
+
−    let zhm_buf = postcard::to_allocvec(&zm).unwrap();
+
−    assert_eq!(zhm_buf.len(), 13300);
+
−
+
−    let zhm: zerovec::ZeroHashMap<[u8], u32> =
+
−        litemap.iter().map(|(a, b)| (*a, *b as u32)).collect();
+
−    let zhm_buf = postcard::to_allocvec(&zhm).unwrap();
+
−    assert_eq!(zhm_buf.len(), 33949);
+
−
+
−    let zhm: zerovec::ZeroHashMap<[u8], u8> = litemap.iter().map(|(a, b)| (*a, *b as u8)).collect();
+
−    let zhm_buf = postcard::to_allocvec(&zhm).unwrap();
+
−    assert_eq!(zhm_buf.len(), 28318);
+
−}