c# - 实现自定义 Int+Range 列表解决方案

Question

我想知道是否有人能想出一种方法，以更有效的内存方式实现数字数组，并自动将其自身组织到范围中。示例；

List testList = new List{1,2,3,4,5,6,7...};

对比

List<Range> testList = new List<Range>{1-3000,3002,4000-5000...};

之前，我问过一个问题只是为了确认这实际上是否是一个更有效的内存替代方案。然而这个问题涉及到实际应用，如何实现这个范围列表解决方案。

Index Array Storage Memory

我想这可能需要一个自定义列表解决方案，它是整数和范围的混合。我想象能够将 .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...等行”。对于这种情况，数字将始终为正。

Answer 1

我要做的第一件事是创建一个代表你的范围的类。您可以提供一些便利，例如格式化为字符串，以及从 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. 不合并范围(假设您已经有 1-10 和 12-20 并且您 Add(11) )
2. 如果您有 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

仍然存在一些可能的边缘情况，我敦促您解决这些问题。

更新

下面的内容将使其按预期工作。这将按照您的预期合并任何添加的范围/整数，并返回正确排序的它们。我只更改了 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()添加第一个范围时防止索引错误的方法。

因此，我认为这完全满足了我的问题。