用于检查HashSet的间隙的算法或修改检查值以适合间隙的方法

Question

我有一个年份范围的HashSet（HashSet >），在这里我想检查特定的Tuple是否已经存在。或者，如果可以在一个（或两个方向）上“碰撞”特定的元组以适合间隙。

我编写了一个单元测试，阐明了它应该如何工作。

测试将设置HashSet，然后调用NotImplemented方法并检查结果。

我想不出一种实现测试的最后调用/检查的绝妙方法。前4个调用/检查非常简单；我可以处理。

如何实现？

    [Fact]
    public void Handled2Test()
    {
        //setup data
        var alreadyHandled = new HashSet<Tuple<int, int>>();
        alreadyHandled.Add(new Tuple<int, int>(1993, 1993));
        alreadyHandled.Add(new Tuple<int, int>(1999, 2004));

        // check a simple range that has no overlap
        var notHandle = this.GetIfNotHandled(alreadyHandled, new Tuple<int, int>(1994, 1998));
        notHandle.Should().Be(new Tuple<int, int>(1994, 1998));

        // check a range that has been handled specifically
        var handled = this.GetIfNotHandled(alreadyHandled, new Tuple<int, int>(1999, 2004));
        handled.Should().BeNull();

        // check a range that has been handled by a larger range that extends around the queried range
        handled = this.GetIfNotHandled(alreadyHandled, new Tuple<int, int>(2001, 2002));
        handled.Should().BeNull();

        // THIS IS THE ONE I NEED HELP WITH
        // check a range that has a one year overlap on the min side
        notHandle = this.GetIfNotHandled(alreadyHandled, new Tuple<int, int>(1993, 1998));
        // returns a Tuple where 1993 has been "bumped" to 1994
        notHandle.Should().Be(new Tuple<int, int>(1994, 1998));

    }

    private Tuple<int, int> GetIfNotHandled(HashSet<Tuple<int, int>> alreadyHandled, Tuple<int, int> tuple)
    {
        throw new NotImplementedException();
    }

Answer 1

这是我想出的：

[TestClass]
public class YearCollectionTests
{
    [TestMethod]
    public void Test_GeneralBehaviour()
    {
        var years = new YearCollection(1993);

        years.AddYearRange(1993, 1993);
        years.AddYearRange(1999, 2004);

        var missingYears = years.GetMissingYears(1994, 2001)
                                .ToList();
        var expectedMissingYears = new List<int>
        {
            1994,
            1995,
            1996,
            1997,
            1998
        };

        CollectionAssert.AreEqual(expectedMissingYears, missingYears);

        missingYears = years.GetMissingYears(1999, 2004)
                            .ToList();

        Assert.AreEqual(0, missingYears.Count);
    }

}

public sealed class YearCollection
{
    private readonly int _baseYear;

    public YearCollection(int baseYear)
    {
        _baseYear = baseYear;
    }

    public int GeometricSum { get; private set; }

    public void AddYearRange(int first, int last)
    {
        var years = GetYears(first, last);

        foreach (var year in years)
        {
            var byteValue = GetGeometricValue(year);

            GeometricSum |= byteValue;
        }
    }

    public IEnumerable<int> GetMissingYears(int first, int last)
    {
        var years = GetYears(first, last);

        foreach (var year in years)
        {
            var byteValue = GetGeometricValue(year);

            if ((GeometricSum & byteValue) != byteValue)
                yield return year;
        }
    }

    private static IEnumerable<int> GetYears(int first, int last)
    {
        var years = Enumerable.Range(first, last - (first - 1));
        return years;
    }

    private int GetGeometricValue(int year)
    {
        var yearOffset = year - _baseYear;
        return 1 << yearOffset;
    }
}

Answer 2

我相信以下实现可能会接近您的需求。我不确定我是否完全理解您的要求（也不确定您是否充分指定了所有极端情况）。但是，如果我将此方法插入到您的单元测试中，它似乎会成功。

private Tuple<int, int> GetIfNotHandled(HashSet<Tuple<int, int>> existingItems, Tuple<int, int> range)
{
        //first check if we find a full overlap with an existing item
        var fullOverlap = existingItems.FirstOrDefault(t => (t.Item1 <= range.Item1)
                                                         && (t.Item2 >= range.Item2));
        if (fullOverlap != null)
        {
            return null;
        }

        //look for a partial overlap, or the closest item below our range
        var lowerItem = existingItems.FirstOrDefault(t => (t.Item1 <= range.Item1) 
                                                       && (t.Item2 >= range.Item1) 
                                                       && (t.Item2 < range.Item2));
        if (lowerItem == null)
        {
            lowerItem = existingItems.Where(t => t.Item2 < range.Item1)?.OrderBy(t => t.Item2).Last();
        }

        //look for a partial overlap, or the closest item above our range
        var upperItem = existingItems.FirstOrDefault(t => (t.Item1 <= range.Item2) 
                                                       && (t.Item2 >= range.Item2) 
                                                       && (t.Item1 > range.Item1));
        if (upperItem == null)
        {
            upperItem = existingItems.Where(t => t.Item1 > range.Item2)?.OrderBy(t => t.Item1).First();
        }
        return new Tuple<int, int>(lowerItem.Item2 + 1, upperItem.Item1 - 1);
}

请注意，如果您的清单很大，此实现在性能上可能不是最佳的。如果您的元组可能不一致（例如，Item1大于Item2），则它缺乏错误处理能力，并且可能不够鲁棒。但这可能会让您开始全面实施。