C#实现获取值范围和这些范围的并集

Question

我有一个情况，这个问题解释的很清楚:

范围交集/并集

我需要一个C#实现（可能是一个集合），它接受一个范围（int类型）列表并对它们进行联合。 然后我需要遍历此集合中的所有int（也包括范围之间的数字） 是否有任何库/实现，以便我不必自己重写一切？

- Francesco Belladonna

Answer 1

你可以看一下这个实现，看它是否符合你的需求。

使用Range.Coalesce来组合范围：

var range1 = Range.Create(0, 5, "Range 1");
var range2 = Range.Create(11, 41, "Range 2");
var range3 = Range.Create(34, 50, "Range 3");
var ranges = new List<Range> { range1, range2, range3 };
var unioned = Range.Coalesce(ranges);

使用.Iterate迭代范围：

foreach (var range in unioned)
{
    foreach (int i in range.Iterate(x => x + 1))
    {
        Debug.WriteLine(i);
    }
}

- mellamokb

---

更具体地说，我认为那里最有用的函数应该是Coalesce()。 - svick

也许你的回答是最完整的，我非常喜欢它。 - Francesco Belladonna

Answer 2

我脑海中想到的最简单的方法是使用 Enumerable.Range，然后使用标准的 linq 运算符处理不同的 IEnumerable。类似这样：

var list = Enumerable.Range(1, 5)
.Concat(Enumerable.Range(7, 11))
.Concat(Enumerable.Range(13, 22))

foreach(var number in list)
  // Do something

显然，您也可以使用Union和Intersect... 当然，您还可以将范围放入List<IEnumerable<int>>或类似的东西中，然后迭代元素以生成一个元素的单个列表：

var ranges = new List<IEnumerable<int>> 
{ 
    Enumerable.Range(1, 5), 
    Enumerable.Range(7, 11), 
    Enumerable.Range(10, 22) 
};
var unionOfRanges = Enumerable.Empty<int>();

foreach(var range in ranges)
    unionOfRanges = unionOfRanges.Union(range);

foreach(var item in unionOfRanges)
    // Do something

- LazyOfT

---

我不确定我更喜欢你的答案还是另一个！ - Francesco Belladonna

我最终更喜欢这个答案，因为写起来更快。 - Francesco Belladonna

Answer 3

以下是基本的Linq实现：

var r1 = Enumerable.Range(1,10);
var r2 = Enumerable.Range(20,5);
var r3 = Enumerable.Range(-5,10);

var union = r1.Union(r2).Union(r3).Distinct();

foreach(var n in union.OrderBy(n=>n))
    Console.WriteLine(n);

- hemme

---

而且对于大范围来说非常低效。 - mellamokb

Answer 4

System.Collections.Generic.HashSet有你需要的功能：

• UnionWith( IEnumerable<T> other )。修改当前HashSet对象，使其包含存在于自身、指定集合或两者中的所有元素。
• IntersectWith( IEnumerable<T> other )。修改当前HashSet对象，仅包含存在于该对象和指定集合中的元素。

- Nicholas Carey

Answer 5

你需要的数据结构叫做“区间树”。

在网络上可以找到不同的实现方式。

例如，这里有一个：http://www.emilstefanov.net/Projects/RangeSearchTree.aspx。

- Pop Catalin