构建一个通用的 Range 类

• 下载源代码文件 - 22.7 KB

引言

Range 类通常很有用，因为它可以在不实际拥有所有值的情况下表达大量值的概念。它可以用于各种应用，如调度程序或缓存算法。

背景

我将展示我编写的 Range 类，但也会深入探讨我的一些决策以及做出这些决策的原因。首先，我想感谢 Jay Bazuzi 和他的读者，感谢他们 的文章及其 后续文章，他们在其中创建了一个简单的 Range 类。

使用代码

代码被封装在一个名为 Sanity 的简单 C# Orcas 项目中。你可以直接解压 Range.cs 文件，或者仅引用该项目，然后在代码顶部使用一个简单的

using Sanity;

语句。请注意，如果你选择解压 Range.cs 文件，它会依赖项目中的其他文件进行验证，因此你需要相应地编辑它，或者同时包含 Assert.cs 文件。Range<T>、Range<TKey, TValue> 和 RangeArray<T> 类都用作标准的泛型类。

• Range<T> - 存储从 LowerBound 到 UpperBound 的范围。
• Range<TKey, TValue> - 存储从 LowerBound 到 UpperBound 的范围，以及一个 Value。
• RangeArray<TKey> - 存储从 LowerBound 到 UpperBound 的整数范围，以及一个名为 Values 的数组。

这些类都支持以下操作：

• Contains\IsContainedBy - 确定一个范围或一个值是否落在该范围内。
• Overlaps - 确定一个范围是否与另一个范围重叠/接触。
• IsContiguousWith - 确定两个范围是否相互接触。
• CompareTo - 允许你比较两个范围，或你的范围与一个值。
• Intersect - 返回两个范围的交集，即它们重叠的范围。
• Union - 返回一个代表两个范围合并的范围。
• Complement - 返回一个代表从该范围中移除另一个范围的范围。
• Split - 返回两个范围（也可能是一个），你的范围在某一点被分割。
• Iterate - 允许你从范围的 LowerBound 迭代到 UpperBound。
• ReverseIterate - 允许你从范围的 UpperBound 迭代到 LowerBound。
• ==, !=, >, >=, <, <= - 标准比较运算符。
• ^, |, & - 分别代表 Complement（补集）、Union（并集）、Intersect（交集）。

这些类的创建是通过静态 Range 类上的工厂方法 Create 来实现的。该类还包含操作 IEnumerable 对象的 Range... 类的那些方法。每种方法都有支持协变（如下所述）的重载。

Range 静态类上的方法是：

• Create - 创建一个范围。有 4 个重载，它们创建适用的 Range 类型。
• Contains - 指示一个点或范围是否包含在范围列表中。
• Sort - 对范围列表进行排序。
• Coalesce - 接受一个范围列表，并返回一个新列表，其中连续的范围被连接在一起。
• Overlapped - 接受一个范围列表，并返回与给定范围重叠的范围。
• Find - 接受一个范围列表，并应用谓词来查找你想要的范围。
• FindFirst - 接受一个范围列表，并应用谓词来查找你想要的范围。

请注意，其中大多数方法都实现为 IEnumerable<Range...> 对象的扩展方法。此外，所有返回 IEnumerable 的方法都实现为迭代器，因此它们只会执行获取你所需项所需的最小工作量。

关注点

泛型还是非泛型？

好吧，这个问题在某种程度上很容易回答；使 Range 类成为泛型是有意义的。然而，这其中存在一个暗示。显然，任何类型的范围都需要能够比较其项，但我们应该支持哪种 IComparable？IComparable<T> 的优点是类型更安全，但 IComparable 可能更广泛地受支持。我花了一段时间才决定，但我最终选择了 IComparable<T>，主要是因为强类型安全是一件好事。无论如何，主要的 Framework 类都支持它，而且对于自定义类，添加它并不困难。

类还是结构？

这是一个花了我很长时间才决定下来的问题。我最初选择了 struct，但后来当我决定想从某些方法返回 null 时，改用了 class。然后我又改变了主意，而是返回了 Nullable<Range<T>>。最后，我基于两个设计因素做出了决定：

1. 我想要子类继承自 Range<T>。
2. 我希望确保 Range<T> 仅由一组工厂方法创建。

由于不能继承 struct，并且任何人都可以使用其默认构造函数创建 struct，因此我（默认）选择了一个 class。

可变还是不可变？

这是另一个艰难的决定。通过使 Range<T> 可变，我肯定会简化我的生活，但也有一些反对意见。首先，我当时正在考虑一个 RangeList<T>，它会维护一组排序的范围，并试图保持连续范围的聚集。如果我们能够更改集合下方的范围值，那么保持一致的状态将变得非常困难。但最终拍板定论的是我创建的两个子类。让我们看看这些类：

在这个图表中，你可以看到我选择了一个 Range<T> 基类，它将包含 UpperBound 和 LowerBound 属性，并处理所有必需的比较和修改。有时我们想将一个范围与除了范围本身之外的其他东西关联起来，即一些额外的数据。为了满足这种可能性，我创建了 Range<TKey, TValue> 类，它继承自基类 Range<T>，但增加了一个 Value 属性。最后，我还处理了一个特殊情况，一个代表数组的范围，类似于 Range<TKey, TValue>，但在两个方面有所不同。首先，它专门继承自 Range<int>，其次，值是一个数组，只是为了更方便地访问元素。老实说，我仍然不确定这一点。

无论如何，这些子类为我决定了可变性问题。谈论拆分 Range<T> 是很不错的，但拆分 Range<TKey, TValue> 究竟意味着什么？我该如何处理这个值？如果我不知道它是什么，我如何有意义地处理包含这些值的范围的连接或拆分？我做不到，所以我决定使范围不可变。Range<T> 上你在图表中看到的“修改”方法都返回全新的范围。更具体地说，对 Range<TKey, TValue> 类的 Union 的调用将返回一个 Range<TKey>，“不带关联的值”。这里所有主要的方法都返回简单的范围，不带额外的关联数据。它们在某种意义上是用来告诉开发人员该做什么的。

var start = Range.Create(0, 5, "Hello ");
var end = Range.Create(6, 10, "World");
var join = start.Union(end);   // 0->10

在上面的示例中，最后一个 Range 告诉我们 start 和 end 的并集是从 0 到 10 的范围；它不知道如何连接这两个字符串。这需要程序员来决定，也许是这样的：

var final = Range.Create(join.LowerBound, join.UpperBound, 
                    start.Value + end.Value);

所以，就像 class 与 struct 的决定一样，在某种程度上，是之前的决定迫使我做出这个选择。我认为这是一个重要的教训。很多时候，在过程早期做出的决定会在后期限制你的选择。从某种意义上说，这就是重构的目的，是为了重新打开你可用的选项。

接口和重载

要实现的唯一接口很明显，就是 IComparable<Range<T>>。这是一个毫无疑问的选择。我还认为提供与 T 的比较很重要，所以这就是为什么有 IComparable<T>。这引出了一个非常有趣的插曲。给定一个范围 {0->10}，它比 5 大还是小？比较让我夜不能寐。我创建了各种混乱的代码，由于一个注定要失败的决定，即试图支持无穷大以及极限值（“几乎”等于给定值的值），代码变得更加庞大。所以我们可能有一个范围 {[5]->10}，这意味着范围从 5 之后一直延伸到包括 10。现在，问问你自己；忘记我前面给你的简单比较，即“现在”哪个更大：{[5]->10} 还是 {1->[5]}，或者 {∞->[5]} vs. {5->[7]}？我发现自己身处一个噩梦般的世界，在这个世界里，比较的含义会根据比较的双方和范围的哪一侧而改变。

我忘记了软件开发的基本规则：保持简单，愚蠢（Keep it Simple Stupid）。我真是的，如果我需要无穷大和极限值，我完全可以实现另一个类来处理它们，然后将其作为类型参数传递给 Range！试图实现一个包罗万象的范围是一种徒劳的尝试。更重要的是，如果使用我类的开发人员不想要无穷大，或者不想费力去弄清楚晦涩的比较规则呢？

无论如何，在花费了大量时间进行可怕的比较代码和单元测试后，我得出了一个简单的解决方案：比较将基于 LowerBound。所以 {5->10} < 6。为了好玩，我还决定支持 IComparable，其中我只测试传入对象的类型，然后将其传递给相关的 CompareTo 方法。

我还重载了 Equals。现在，我决定 Equals 永远只返回 true 给两个范围。我对此还没有完全决定。这意味着我遇到了一个不寻常的情况：{5->10}.CompareTo(5) == 0，但 {5->10}.Equals(5) == false。然而，在我看来，Equals 是一个比 CompareTo 更严格的比较。如果你有不同意见，请告诉我。

为了让事情稍微简单一些，我还提供了一个简单的 ToString 重载，它在调试器中显示我漂亮的 {x->y} 格式。

运算符

这很有趣。我通常不进行运算符重载，因为很少有这种需求。说实话，添加两个 Customer 对象究竟意味着什么？我实现了常见的比较运算符，还实现了三个修改运算符：

• ^ - 我将其解释为 Complement（补集），从一个范围中移除另一个范围。
• | - 我将其解释为 Union（并集），将两个范围合并为一个跨越两者的新范围。
• & - 我将其解释为 Intersect（交集），提供一个表示两个范围重叠区域的范围。

同样，我不完全确定提供修改运算符是否是正确的做法，但我认为我只是玩得太嗨了。

迭代器

这很有意思。我想能够迭代一个范围。换句话说（对于整数），给定 {0->5}，迭代 0, 1, 2, 3, 4, 5。然而，由于我处理的是泛型，我实际上不知道 T 是什么，尤其不知道从一个 T 迭代到另一个 T 的含义。即使对于我了解的类型，我该如何迭代它们？我的意思是，如果是 DateTime，我会迭代秒、分钟、年吗？所以我的做法是在 Iterate 方法中接受一个名为 incrementor 的委托。它是一个 Func<TArg0, TResult>>，因此可以与 lambda 表达式一起使用。所以你可以这样，例如：

Range<int> range = Range.Create(0, 5);
foreach (int i in range.Iterate(x => x + 1))
{
    Debug.WriteLine(i);
}

我认为这是一个不错的细节。为了完整起见，我提供了一个 ReverseIterate，它接受一个 decrementor。因此，范围的含义取决于提供 incrementor 的人，并且一个范围在不同时间可以有不同的含义。太棒了！

工厂类

Jay 的原始文章中的一个亮点是有一个静态 Range 类，它包含了操作多个范围的方法。我决定不完全走那条路，但所有操作范围列表的内容，以及工厂方法，我都放在了这个类中。

协变/逆变

C# 不支持泛型的协变。这意味着，如果我有一个这样的方法：

IEnumerable<Range<T>> Find<T>(this IEnumerable<Range<T>> ranges, 
                    Func<Range<T>, bool> predicate);

我不能将 List<RangeArray<object>> 传递给 ranges 参数。即使列表实现了 IEnumerable<T>，并且在这种情况下 T 是从 Range<T> 继承的，它也不会认为这两种类型是兼容的。据称有充分的理由，但我不知道是什么。

所以，为了解决这个问题，我最初决定创建 RangeList<T>、RangeList<TKey, TValue> 和 RangeArrayList<T>，它们都实现了 IEnumerable<Range<T>>，因此静态类中的方法将接受它们，并且整个领域将欢庆。好吧，我做到了，而且运行良好，但它让我耿耿于怀。我意识到那些集合类存在的唯一原因是为了绕过协变问题，但它们也限制了解决方案。如果有人想要一个 Dictionary<Range<T>, string>，并且想将 Keys 的枚举器传递给我的一个方法怎么办？好吧，他们将无法做到，这完全是因为该死的协变。所以，如果你向上看上面的类图，你会看到我的解决方案。

首先，我将我类的所有构造函数设为 internal，确保没有人可以继承它们，为了安全起见，我将 Range<TKey, TValue> 和 RangeArray<T> 标记为 sealed。然后，我在 Range 上创建了两个重载的 private 方法，称为 MakeCovariant。一个接受 IEnumerable<Range<TKey, TValue>>，另一个接受 IEnumerable<RangeArray<T>>，它们都返回 IEnumerable<Range<T>>。然后，我为调用 MakeCovariant 来处理其参数并将其传递给“主”方法的每个 static 方法创建了类似的重载。这样做的结果是，缺乏协变不再是我的 static Range 类的问题。只要我的三个类是唯一的，并且没有人创建新的子类（我已经确保了），这种情况就会一直存在。

我想，如果我当初决定将 Range 类保留为 struct，这就不需要了，但我喜欢有这三个 Range 选项，而且现在我也不必有三个额外的集合类来支持它们了。

无论如何，这一切的一个副作用是 Find 方法有点意思。看看这三个 Find 签名：

... Find<T>           (this IEnumerable<Range<T>> ranges,            
                Func<Range<T>, bool> predicate)    ...
... Find<TKey, TValue>(this IEnumerable<Range<TKey, TValue>> ranges, 
                Func<Range<TKey>, bool> predicate) ...
... Find<T>           (this IEnumerable<RangeArray<T>> ranges,       
                Func<Range<int>, bool> predicate)

请注意，在这三种情况下，谓词都接受基类 Range<T>。这意味着，如果你尝试这样做：

IEnumerable<RangeArray<T>> ranges = /* Create Range */
Range.Find(ranges, x => (x.Values.Count == 0)); 

你会发现 lambda 表达式无法编译。简单来说，尽管集合包含 RangeArray 类，但我只为接受 Range<T> 编写了谓词。我想我或许可以更改它，但这将意味着复制 Find 功能，而我很懒。

所以，尽情享受这个类吧，你可以在 这里 找到它。请注意，这是一个 Orcas 项目。将其移植到 Whidbey 并不需要太多努力。如果你遇到任何问题、改进或其他任何事情，请告诉我。它没有经过严格测试，但我包含了到目前为止我做的单元测试。