实现自定义Int+Range列表解决方案
我想知道是否有人能想出一种方法，以一种更有效的内存方式来实现一个数字数组，从而自动地将自己组织成一个范围。榜样；
List testList = new List{1,2,3,4,5,6,7...};vs
List<Range> testList = new List<Range>{1-3000,3002,4000-5000...};在此之前，我曾问过一个问题，以证实这是否会是一个更有效的记忆选择。然而，这个问题与实际应用有关，如何实现这个范围列表解决方案。
我认为这可能需要一个自定义列表解决方案，它将是ints和范围的混合。我想象的是能够将.Add( int )添加到列表中，此时它将确定该值是否会导致范围被添加或简单地将int值添加到列表中。
示例
RangeList rangeList = new RangeList{1, 4, 7-9};
rangeList.Add(2);
//rangeList -> 1-2, 4, 7-9
rangeList.Add(3);
//rangeList -> 1-3, 4, 7-9的详细信息特定于我的实现
在我的特殊情况下，我分析的是一个非常大的文档，逐行。需要确定符合特定条件的行，然后需要向用户显示行索引的总体列表。
明显地，显示“行33-32019识别”比“线33,34,35...etc”更好。在这种情况下，数字总是正数。
回答 1
Stack Overflow用户
发布于 2018-04-24 09:37:43
我要做的第一件事是做一个代表你的范围的类。您可以提供一些方便，比如格式化为字符串，以及从int进行隐式强制转换(这有助于稍后实现范围列表)。
public class Range
{
public int Start{get; private set;}
public int End{get; private set;}
public Range(int startEnd) : this(startEnd,startEnd)
{
}
public Range(int start, int end)
{
this.Start = start;
this.End = end;
}
public static implicit operator Range(int i)
{
return new Range(i);
}
public override string ToString()
{
if(Start == End)
return Start.ToString();
return String.Format("{0}-{1}",Start,End);
}
}然后，您可以开始RangeList的简单实现。通过提供Add方法，您可以使用类似于List<T>的列表初始化器。
public class RangeList : IEnumerable<Range>
{
private List<Range> ranges = new List<Range>();
public void Add(Range range)
{
this.ranges.Add(range);
}
public IEnumerator<Range> GetEnumerator()
{
return this.ranges.GetEnumerator();
}
IEnumerator IEnumerable.GetEnumerator(){
return this.GetEnumerator();
}
}此时，您可以编写一些测试代码：
var rangeList = new RangeList(){
new Range(1,10),
15
};
foreach(var range in rangeList)
Console.WriteLine(range);
// Outputs:
// 1-10
// 15这里是一个活生生的例子：http://rextester.com/NCZSA71850
接下来要做的是提供Add的重载，它需要一个int并找到正确的范围，或者添加一个新的范围。简单的执行可能如下所示(假设在范围上添加了Update方法)
public void Add(int i)
{
// is it within or contiguous to an existing range
foreach(var range in ranges)
{
if(i>=range.Start && i<=range.End)
return; // already in a range
if(i == range.Start-1)
{
range.Update(i,range.End);
return;
}
if(i == range.End + 1)
{
range.Update(range.Start,i);
return;
}
}
// not in any ranges
ranges.Add(i);
}这里是一个活生生的例子：http://rextester.com/CHX64125
然而，这也存在一些不足。
- 不合并范围(假设您已经有1-10和12-20以及您的
Add(11)) - 不重新订购，因此，如果您有1-5和20-25和
Add(7)，这将是在最后，而不是在中间。
您可以通过在每次添加后应用排序来解决这两个问题，还可以使用一些逻辑来确定是否应该合并范围。
private void SortAndMerge()
{
ranges.Sort((a,b) => a.Start - b.Start);
var i = ranges.Count-1;
do
{
var start = ranges[i].Start;
var end = ranges[i-1].End;
if(end == start-1)
{
// merge and remove
ranges[i-1].Update(ranges[i-1].Start,ranges[i].End);
ranges.RemoveAt(i);
}
} while(i-- >1);
}这需要在每次更改列表之后调用。
public void Add(Range range)
{
this.ranges.Add(range);
SortAndMerge();
}
public void Add(int value)
{
// is it within or contiguous to an existing range
foreach(var range in ranges)
{
if(value>=range.Start && value<=range.End)
return; // already in a range
if(value == range.Start-1)
{
range.Update(value,range.End);
SortAndMerge();
return;
}
if(value == range.End + 1)
{
range.Update(range.Start,value);
SortAndMerge();
return;
}
}
// not in any ranges
ranges.Add(value);
SortAndMerge();
}这里的实例：http://rextester.com/SYLARF47057
这里还有一些可能的边缘情况，我敦促你们继续努力。
更新
下文将使这一工作如预期的那样。这将像您所期望的那样合并任何添加的范围/ints，并返回它们的正确排序。我只更改了Add(Range)方法，我认为这是一种相当干净的方法。
public void Add(Range rangeToAdd)
{
var mergableRange = new List<Range>();
foreach (var range in ranges)
{
if (rangeToAdd.Start == range.Start && rangeToAdd.End == range.End)
return; // already exists
if (mergableRange.Any())
{
if (rangeToAdd.End >= range.Start - 1)
{
mergableRange.Add(range);
continue;
}
}
else
{
if (rangeToAdd.Start >= range.Start - 1
&& rangeToAdd.Start <= range.End + 1)
{
mergableRange.Add(range);
continue;
}
if (range.Start >= rangeToAdd.Start
&& range.End <= rangeToAdd.End)
{
mergableRange.Add(range);
continue;
}
}
}
if (!mergableRange.Any()) //Standalone range
{
ranges.Add(rangeToAdd);
}
else //merge overlapping ranges
{
mergableRange.Add(rangeToAdd);
var min = mergableRange.Min(x => x.Start);
var max = mergableRange.Max(x => x.End);
foreach (var range in mergableRange) ranges.Remove(range);
ranges.Add(new Range(min, max));
}
SortAndMerge();
}最后，在添加第一个范围时，我们需要在if (ranges.Count > 1)方法中使用SortAndMerge()来防止索引错误。
因此，我认为这完全满足了我的问题。
https://stackoverflow.com/questions/49997913
复制相似问题
腾讯云开发者
