如何创建 BTreeSet<(String, String, String)> 的子范围？如何将边界元组转换为元组边界？

Question

我正在尝试使用 aBTreeSet<(String, String, String)>作为创建一个简单的内存中“三重存储”的方法。

准确地说：

type Entity = String;
type Attribute = String;
type Value = String;
type EAV = (Entity, Attribute, Value);
type EAVSet = BTreeSet<EAV>;


pub fn example_db() -> EAVSet {
    let mut example: EAVSet = BTreeSet::new();
    insert_strtup(&mut example, ("1", "type", "user"));
    insert_strtup(&mut example, ("1", "user/name", "Arthur Dent"));
    insert_strtup(&mut example, ("1", "user/age", "33"));

    insert_strtup(&mut example, ("2", "type", "user"));
    insert_strtup(&mut example, ("2", "user/name", "Ford Prefect"));
    insert_strtup(&mut example, ("2", "user/age", "42"));

    return example;
}


fn insert_strtup(db: &mut EAVSet, val: (&str, &str, &str)) -> () {
    db.insert((val.0.to_string(), val.1.to_string(), val.2.to_string()));
}

pub fn example()  {
    let db = example_db();

    // How to customize this?
    let range: (Bound<EAV>, Bound<EAV>) = (Bound::Unbounded, Bound::Unbounded);

    for elem in eavt.range(range) {
        println!("{:?}", elem);
    }
}

我面临的问题是，我希望人们能够迭代集合中的值的子范围。然而，简单的使用std::ops::Bound是不可能的，因为我们存储具有多个字段的元组。

我希望能够为以下所有内容构建范围查询：

• 所有实体；
• ID 在范围内的所有实体x..y；
• 实体的所有字段1；
• 1实体字段的当前值"user/age"）。

到目前为止，想到的唯一想法是使用字符串键，我们知道该字符串键的事实比较较低。高于我们在“占位符”字段中寻找的值。但这感觉非常黑客/容易出错，就像重新发明轮子一样。

有没有办法把a变成(Bound<String>, Bound<String>, Bound<String>)也许Bound<(String, String, String)>？或者这里可以采取另一种方法吗？

编辑：在 Rust 中过滤/查询多键 btree 索引显示了一种通过将所有值包装在有序 Enum ( Min, Exact(String), Max) 中的解决方案，但此解决方案需要更改 BTreeSet 中存储的值类型。这也感觉像是增加了内存开销，因为我们实际上从不存储除Exact(some_string)内部之外的任何内容。是否有另一种方法不需要更改存储在 中的值的类型BTreeSet？

Answer 1

由于Borrow总是返回一个引用（grrrrrrrr），并且Borrowed不一定Copy，您也许可以依赖哨兵内存地址？

请注意，由于static不允许关联项目，因此您可能需要为要使用的每种类型提供此代码的副本。

use std::borrow::Borrow;
use std::cmp::Ordering;

#[repr(transparent)]
pub struct StringWithMinMaxSentinel(String);

// must be static, not const, to ensure a constant memory address
pub static STRING_MIN_SENTINEL: StringWithMinMaxSentinel = StringWithMinMaxSentinel(String::new());
pub static STRING_MAX_SENTINEL: StringWithMinMaxSentinel = StringWithMinMaxSentinel(String::new());

impl Borrow<StringWithMinMaxSentinel> for String {
    fn borrow(self: &String) -> &StringWithMinMaxSentinel {
        unsafe { &*(self as *const String as *const StringWithMinMaxSentinel) }
    }
}

impl PartialEq for StringWithMinMaxSentinel {
    fn eq(&self, other: &Self) -> bool {
        std::ptr::eq(self, other) || (!std::ptr::eq(self, &STRING_MIN_SENTINEL) && !std::ptr::eq(other, &STRING_MAX_SENTINEL) && !std::ptr::eq(other, &STRING_MIN_SENTINEL) && !std::ptr::eq(self, &STRING_MAX_SENTINEL) && self.0.eq(&other.0))
    }
}

impl Eq for StringWithMinMaxSentinel {}

impl PartialOrd for StringWithMinMaxSentinel {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        Some(self.cmp(other))
    }
}

impl Ord for StringWithMinMaxSentinel {
    fn cmp(&self, other: &Self) -> Ordering {
        if std::ptr::eq(self, other) {
            Ordering::Equal
        } else if std::ptr::eq(self, &STRING_MIN_SENTINEL) || std::ptr::eq(other, &STRING_MAX_SENTINEL) {
            Ordering::Less
        } else if std::ptr::eq(self, &STRING_MAX_SENTINEL) || std::ptr::eq(other, &STRING_MIN_SENTINEL) {
            Ordering::Greater
        } else {
            self.0.cmp(&other.0)
        }
    }
}