秘密合同开发工具包 - 孵化器

⚠️ 此软件包是 secret-toolkit 软件包的子包。请参阅其crate页面以获取更多上下文。

此软件包包含尚未定稿的工具，可能发生变化或包含未知错误，并等待更多测试或审查。

最大堆存储

“最大堆存储”是一个实现二叉树最大堆数据结构的存储包装器。基于https://en.wikipedia.org/wiki/Min-max_heap 实现。基于https://algorithmtutor.com/Data-Structures/Tree/Binary-Heaps/

• 插入 O(log n)
• 删除最大值 O(log n)

用法

MaxHeapStoreMut 和 MaxHeapStore 的使用模式分别基于 AppendStoreMut 和 AppendStore。要向堆中添加项，请使用 insert，要从堆中取出顶部值请使用 remove，它还将返回被删除的项。要查看最大值而不删除，请使用 get_max 函数。可以添加重复项到堆中。

# use cosmwasm_std::{StdError, testing::MockStorage};
# use secret_toolkit_incubator::maxheap::MaxHeapStoreMut;
let mut storage = MockStorage::new();
let mut heap_store = MaxHeapStoreMut::attach_or_create(&mut storage)?;
heap_store.insert(&1234)?;
heap_store.insert(&2143)?;
heap_store.insert(&4321)?;
heap_store.insert(&3412)?;
heap_store.insert(&2143)?;

assert_eq!(heap_store.remove(), Ok(4321));
assert_eq!(heap_store.remove(), Ok(3412));
assert_eq!(heap_store.remove(), Ok(2143));
assert_eq!(heap_store.remove(), Ok(2143));
assert_eq!(heap_store.remove(), Ok(1234));
# Ok::<(), StdError>(())

为了使用与 MaxHeapStore 相关的自定义结构，您需要实现适当的Ordering traits。以下是一个使用自定义结构 Tx 的示例，它使用 amount 字段来确定堆中的顺序

# use cosmwasm_std::{StdError, testing::MockStorage, Addr};
# use secret_toolkit_incubator::maxheap::MaxHeapStoreMut;
# use serde::{Serialize, Deserialize};
# use std::cmp::Ordering;
#[derive(Serialize, Deserialize, Clone, Debug, Eq)]
pub struct Tx {
    address: Addr,
    amount: u128,
}

impl PartialOrd for Tx {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        Some(self.cmp(other))
    }
}
        
impl Ord for Tx {
    fn cmp(&self, other: &Self) -> Ordering {
        self.amount.cmp(&other.amount)
    }
}
        
impl PartialEq for Tx {
    fn eq(&self, other: &Self) -> bool {
        self.amount == other.amount
    }
}

let mut storage = MockStorage::new();
let mut heap_store = MaxHeapStoreMut::attach_or_create(&mut storage)?;

heap_store.insert(&Tx{
    address: Addr::unchecked("address1"),
    amount: 100,
})?;
heap_store.insert(&Tx{
    address: Addr::unchecked("address2"),
    amount: 200,
})?;
heap_store.insert(&Tx{
    address: Addr::unchecked("address5"),
    amount: 50,
})?;

assert_eq!(heap_store.remove(), Ok(Tx{
    address: Addr::unchecked("address3"),
    amount: 200,
}));
assert_eq!(heap_store.remove(), Ok(Tx{
    address: Addr::unchecked("address4"),
    amount: 100,
}));
assert_eq!(heap_store.remove(), Ok(Tx{
    address: Addr::unchecked("address1"),
    amount: 50,
}));
# Ok::<(), StdError>(())

MaxHeapStore 是基于 AppendStore 模型构建的，并以相同的方式存储堆的数组表示，例如使用 len 键来存储长度。因此，如果您需要以某种原因迭代所有值，可以将 AppendStore 附接到最大堆，而不是使用 MaxHeapStore。

代索引存储

也称为槽位图，代索引存储是一种可迭代的 数据结构，其中列表中的每个元素都由一个唯一键标识，该键是一个索引和一代的配对。每次从列表中删除项目时，存储的代数都会增加1。如果新项目放置在之前已删除项目的相同索引处，则旧引用不会指向新元素。这是因为虽然索引匹配，但代数不匹配。这确保了列表中每个元素的引用都是稳定和安全的。

从空集开始，如果我们插入 A，我们将有键：(索引：0，代：0)。插入 B 将有键：(索引：1，代：0)。当我们删除 A 时，代数将增加1，索引 0 将被释放。当我们插入 C 时，它将进入我们空闲槽位的列表头部，并被赋予键 (索引：0，代：1)。如果您尝试获取 A，结果将是 None，即使 A 和 C 都曾在列表的“0”位置。

与 AppendStore 不同，代索引存储的迭代顺序不是插入顺序。

用例

此类存储的主要用途是我们想要由其他结构或列表在合同中引用的元素集合，并且我们想要确保如果删除元素，我们的其他引用不会中断。例如，想象我们有一个合同，其中我们想要一组独立的 User 结构体，这些结构体不受秘密地址的影响（也许我们想要人们能够将他们的账户从一个地址移动到另一个地址）。我们还希望人们能够删除 User 账户，因此我们使用代索引存储。我们可以通过其代索引键（索引，代）来引用 User 账户。我们还可以通过在 User 结构体中添加指向代索引存储中另一个键的字段来引用用户之间的关系。如果我们删除一个 User，并在同一索引处放置一个新 User 但在不同的代，那么就不会有链接指向错误用户的危险。可以轻松地想象将其扩展到更多异构的相互关联元素，而不仅仅是用户。

实际上，这个例子是一个图结构，其中节点是元素，对唯一（索引，代）对的引用是边。任何这样的图都可以使用代索引存储实现。

用法

请参阅 generational_store.rs 中的测试，包括迭代示例。

# use cosmwasm_std::{StdError, testing::MockStorage};
# use secret_toolkit_incubator::generational_store::{GenerationalStoreMut, Index};
let mut storage = MockStorage::new();
let mut gen_store = GenerationalStoreMut::attach_or_create(&mut storage)?;
let alpha = gen_store.insert(String::from("Alpha"));
let beta = gen_store.insert(String::from("Beta"));
let gamma = gen_store.insert(String::from("Gamma"));

assert_eq!(gen_store.len(), 3_u32);
assert_eq!(gen_store.remove(beta.clone()), Ok(Some(String::from("Beta"))));
assert_eq!(gen_store.len(), 2_u32);
assert_eq!(gen_store.get(alpha), Some(String::from("Alpha")));
assert_eq!(gen_store.get(beta.clone()), None);
assert_eq!(gen_store.get(gamma), Some(String::from("Gamma")));

let delta = gen_store.insert(String::from("Delta"));
assert_eq!(gen_store.get(delta.clone()), Some(String::from("Delta")));
// check that the generation has updated
assert_ne!(delta.clone(), Index::from_raw_parts(1, 0));
// delta has filled the slot where beta was but generation is now 1
assert_eq!(delta, Index::from_raw_parts(1, 1));

// cannot remove twice
assert!(gen_store.remove(beta).is_err());
# Ok::<(), StdError>(())

待办事项

重命名为 SlotMap？(见：https://docs.rs/slotmap/1.0.5/slotmap/) 尽管名称简单，但可能不如实际执行的任务那样富有启发性。