id_collections: Rust 中的索引导向编程

下载: crates.io/crates/id_collections

文档: docs.rs/id_collections

在 Rust 中，定义围绕整数类型的自定义包装类型（有时称为 "newtypes"）是很常见的，以便更好地传达这些类型的意图，并捕捉到由于将具有不同意义的整数值混合在一起而产生的错误。例如，可以定义两种不同的类型来表示 "用户 ID" 和 "组 ID"。

struct UserId(u32);
struct GroupId(u32);

id_collections crate 提供了与这些强类型整数类型包装一起工作的数据结构

• IdVec<I, T> 类型是一个向量，它使用自定义索引类型 I 而不是 usize。
• IdMap<I, T> 类型是一个由向量支持的映射。它与 IdVec<I, T> 类似，除了其键集不必占用连续范围，因此可以无序填充其条目。
• Count<I> 类型提供了一种类型安全的方式来表示自定义 ID 范围的大小。

要使用此库中的结构体与您应用程序的 ID 类型一起使用，您的 ID 类型需要实现 Id 特性。实现 Id 特性最简单的方法是使用 #[id_type] 属性宏

use id_collections::id_type;

#[id_type]
struct UserId(u32);

#[id_type]
struct GroupId(u32);

在实现 Id 之后，您可以使用自定义的 id 类型作为 IdVec 的索引类型

use id_collections::IdVec;

let mut users: IdVec<UserId, &str> = IdVec::new();
let alice_id: UserId = users.push("Alice");
let bob_id: UserId = users.push("Bob");

assert_eq!(users[alice_id], "Alice");
assert_eq!(users[bob_id], "Bob");

使用 IdVec 可以防止您意外地混淆不同的 id 类型

let group = GroupId(1);
let name = users[group]; // error: expected 'UserId', found 'GroupId'!

如果您需要一个支持非连续键的集合，您可以使用 IdMap

use id_collections::IdMap;

let mut users: IdMap<UserId, &str> = IdMap::new();
users.insert(UserId(5), "Alice");
users.insert(UserId(10), "Bob");
assert_eq!(users[UserId(5)], "Alice");
assert_eq!(users[UserId(10)], "Bob");

示例：计算目录大小

id_collections crate 的一项主要用途是实现图算法。以下示例展示了如何将 IdVec、IdMap 和 Count 结合使用，以实现一个简单的深度优先图遍历，该遍历计算文件系统的内存表示中每个目录的大小

use id_collections::{id_type, IdMap, IdVec};

#[id_type]
struct FileId(usize);

#[id_type]
struct DirectoryId(usize);

struct DirectoryContents {
    files: Vec<FileId>,
    subdirectories: Vec<DirectoryId>,
}

/// Calculate the size of each directory in `directories`.
///
/// `directories` may contain file and directory "hard links" (i.e., a file or directory may
/// be pointed to by multiple parent directories), but for simplicity we assume that the
/// filesystem may not contain cycles (i.e., a directory is not allowed to directly or
/// indirectly contain itself).
fn calculate_sizes(
    file_sizes: &IdVec<FileId, u64>,
    directories: &IdVec<DirectoryId, DirectoryContents>,
) -> IdVec<DirectoryId, u64> {
    fn calculate_size_rec(
        file_sizes: &IdVec<FileId, u64>,
        directories: &IdVec<DirectoryId, DirectoryContents>,
        directory_sizes: &mut IdMap<DirectoryId, u64>,
        directory: DirectoryId,
    ) -> u64 {
        if let Some(&cached_size) = directory_sizes.get(directory) {
            return cached_size;
        }

        let mut size = 0;
        for file in &directories[directory].files {
            size += file_sizes[file];
        }
        for &subdirectory in &directories[directory].subdirectories {
            size +=
                calculate_size_rec(file_sizes, directories, directory_sizes, subdirectory);
        }
        directory_sizes.insert_vacant(directory, size);
        size
    }

    let mut directory_sizes = IdMap::with_capacity(directories.len());
    for directory in directories.count() {
        calculate_size_rec(file_sizes, directories, &mut directory_sizes, directory);
    }

    directory_sizes.to_id_vec(directories.count())
}