discrete_range_map

此包已重命名为 nodit

大约在 2024-01-03 的版本 v0.7.0 中，此包从 discrete_range_map 重命名为 nodit，因为旧名称不准确。请切换到 nodit 包，因为此包将不再接收更新。

旧 Readme

此包提供了 DiscreteRangeMap 和 DiscreteRangeSet，基于 BTreeMap 的用于存储非重叠离散区间的数据结构。

no_std 支持，并且应与默认功能一起工作。

必须实现 Copy

由于与非 Copy 类型的实现复杂性，当前数据结构要求范围类型以及这些范围覆盖的点必须是 Copy。

使用包含-排除范围示例

use discrete_range_map::test_ranges::ie;
use discrete_range_map::DiscreteRangeMap;

let mut map = DiscreteRangeMap::new();

map.insert_strict(ie(0, 5), true);
map.insert_strict(ie(5, 10), false);

assert_eq!(map.overlaps(ie(-2, 12)), true);
assert_eq!(map.contains_point(20), false);
assert_eq!(map.contains_point(5), true);

使用自定义范围类型示例

use std::ops::{Bound, RangeBounds};

use discrete_range_map::test_ranges::ie;
use discrete_range_map::{
	DiscreteFinite, DiscreteRangeMap, InclusiveInterval,
	InclusiveRange,
};

#[derive(Debug, Copy, Clone)]
enum Reservation {
	// Start, End (Inclusive-Inclusive)
	Finite(i8, i8),
	// Start (Inclusive-Infinity)
	Infinite(i8),
}

// First, we need to implement InclusiveRange
impl InclusiveRange<i8> for Reservation {
	fn start(&self) -> i8 {
		match self {
			Reservation::Finite(start, _) => *start,
			Reservation::Infinite(start) => *start,
		}
	}
	fn end(&self) -> i8 {
		match self {
			Reservation::Finite(_, end) => *end,
			Reservation::Infinite(_) => i8::MAX,
		}
	}
}

// Second, we need to implement From<InclusiveInterval<i8>>
impl From<InclusiveInterval<i8>> for Reservation {
	fn from(value: InclusiveInterval<i8>) -> Self {
		if value.end == i8::MAX {
			Reservation::Infinite(value.start)
		} else {
			Reservation::Finite(
				value.start,
				value.end.up().unwrap(),
			)
		}
	}
}

// Next we can create a custom typed DiscreteRangeMap
let reservation_map = DiscreteRangeMap::from_slice_strict([
	(Reservation::Finite(10, 20), "Ferris".to_string()),
	(Reservation::Infinite(21), "Corro".to_string()),
])
.unwrap();

for (reservation, name) in reservation_map.overlapping(ie(16, 17))
{
	println!(
		"{name} has reserved {reservation:?} inside the range 16..17"
	);
}

for (reservation, name) in reservation_map.iter() {
	println!("{name} has reserved {reservation:?}");
}

assert_eq!(
	reservation_map.overlaps(Reservation::Infinite(0)),
	true
);

关键理解和哲学

离散性

此包旨在与 Discrete 类型一起工作，而不是与 Continuous 类型。例如，u8 是一个 Discrete 类型，但如果你尝试将其解析为十进制值，则 String 是一个 Continuous。

原因在于，常见的区间-数学运算取决于底层类型是离散还是连续。例如，5..=6触及了7..=8，因为整数是离散的，但5.0..=6.0并没有触及7.0..=8.0，因为存在值6.5。

有限性

该库还设计用于与有限类型一起工作，因为它更容易实现，并且对用户没有限制，因为您仍然可以使用实在无限的概念，以矛盾的方式在有限类型中表示无限数字。

例如，您可以为u8定义无限为u8::MAX，或者如果您仍然想将u8::MAX作为一个有限数字，您可以定义一个包装类型，为u8添加一个实在无限值到u8集合。

无效范围

在此库中，并非所有范围都被视为有效范围。在此库中使用范围的定义是，只有当范围包含底层域至少一个值时，该范围才是有效的。

例如，4..6被认为是有效的，因为它包含值4和5，然而，4..4被认为是无效的，因为它不包含任何值。另一个无效范围的例子是起始值大于结束值的情况，例如5..2或100..=40。