C#.NET的区间数据类型？

Question

我正在寻找.NET 4.0 的间隔数据类型.例如,间隔(a,b),所有点x使得a <x <= b.

我希望能够做的是创建具有以下特性的间隔:

• 封闭和开放的
• 无限的间隔,完全无界,右/左无界.

有了这些,我想做的事情如下:

• 检查点是否在某个区间内.
• 检查两个间隔是否重叠.
• 将两个重叠间隔合并为一个间隔.
• 检查间隔集合是否包含单个间隔.
• 等等:)

如果我能同时处理数值数据类型和日期时间会很好.

我知道逻辑非常简单,但我认为没有理由认为我是第一个需要这样做的人.

Answer 1

正如其他人所说,没有集成区间类型.根据项目的需要,简单System.Range或Tuple<T1, T2>使用一些额外的代码行调用就足够了.该Enumerable.Range包含一套操作方法,如UnionWith,IntersectWith多,但仍保存所有项目,而不仅仅是端点.

许多实现都可以在网上找到.Microsoft Research动态数据显示项目有一个基本的通用Range类部分,另一个来自Kevin Gadd.AForge项目包含非泛型IntInterval/DoubleInterval实现.其他(1,2),这样的问题也可能会感兴趣.Andy Clymer在他的博客上有一个有趣的动态编译实现.更完整的解决方案可能被发现在CodeProject上,在乔恩斯基特的书和来自俄罗斯的爱情.似乎有几个(1,2)商业解决方案也是如此.我之前见过别人,此刻我找不到.

无论您做什么,请注意何时使用通用间隔类型.实际上很难编写正确的单片通用间隔类,因为整数和浮点间隔具有不同的数学属性.例如,所有整数区间都可以用封闭端点表示,并且该对HashSet<T>可以被认为是连续的,相当于[1,2] [3,6].浮点间隔都不是这样.有关详细信息,请参阅Wikipedia 一组类可能更好,具有抽象通用基类和类型派生类IntInterval或DoubleInterval来实现不同的行为.

除了数学之外,通用区间类型还有一些实现困难.在C#中使用泛型无法轻松进行算术运算,并且存在浮点NaN和舍入误差.有关详细信息,请参阅Boost库文档[1,6].(其中很多都转换为C#和.NET.)幸运的是,很多操作都可以完成Interval<T>.

正如我之前提到的,在功能和正确性方面选择合适的内容都取决于项目的要求.

Answer 2

为了帮助您入门:

public class Interval<T> where T : struct, IComparable
{
    public T? Start { get; set; }
    public T? End { get; set; }

    public Interval(T? start, T? end)
    {
        Start = start;
        End = end;
    }

    public bool InRange(T value)
    {
        return ((!Start.HasValue || value.CompareTo(Start.Value) > 0) &&
                (!End.HasValue || End.Value.CompareTo(value) > 0));
    }
}

Answer 3

以下允许实现的任何类型的开放式范围IComparable.一个显而易见的扩展是允许你传递自己的比较器(就像Hashset<T>那样.

在这种情况下,范围是<= x

它包括重叠和合并.其他功能应该相当容易添加.

public class Interval<T> where T : IComparable
{
    public T Start { get; private set; }
    public T End { get; private set; }

    public bool HasStart { get; private set; }
    public bool HasEnd { get; private set; }

    private Interval()
    {
    }

    public bool Overlaps(Interval<T> other)
    {
        if (this.HasStart && other.IsInRange(this.Start))
            return true;
        if (this.HasEnd && other.IsInRange(this.End))
            return true;
        return false;
    }

    public static Interval<T> Merge(Interval<T> int1, Interval<T> int2)
    {
        if (!int1.Overlaps(int2))
        {
            throw new ArgumentException("Interval ranges do not overlap.");
        }
        bool hasStart = false;
        bool hasEnd = false;
        T start = default(T);
        T end = default(T);

        if (int1.HasStart && int2.HasStart)
        {
            hasStart = true;
            start = (int1.Start.CompareTo(int2.Start) < 0) ? int1.Start : int2.Start;
        }
        if (int1.HasEnd && int2.HasEnd)
        {
            hasEnd = true;
            end = (int1.End.CompareTo(int2.End) > 0) ? int1.Start : int2.Start;
        }
        return CreateInternal(start, hasStart, end, hasEnd);
    }

    private static Interval<T> CreateInternal(T start, bool hasStart, T end, bool hasEnd)
    {
        var i = new Interval<T>();
        i.Start = start;
        i.End = end;
        i.HasEnd = hasEnd;
        i.HasStart = hasStart;
        return i;
    }

    public static Interval<T> Create(T start, T end)
    {
        return CreateInternal(start, true, end, true);
    }

    public static Interval<T> CreateLowerBound(T start)
    {
        return CreateInternal(start, true, default(T), false);
    }

    public static Interval<T> CreateUpperBound(T end)
    {
        return CreateInternal(default(T), false, end, true);
    }

    public bool IsInRange(T item)
    {
        if (HasStart && item.CompareTo(Start) < 0)
        {
            return false;
        }
        if (HasEnd && item.CompareTo(End) >= 0)
        {
            return false;
        }
        return true;
    }
}

Answer 4

包括下面的起点.

虽然这将是一个很好的脑筋急转弯,所以试试看.这远非完整,可以召唤出更多的操作,但这是一个开始.

class Program
{
    public static void Main(string[] args)
    {
        var boundedOpenInterval = Interval<int>.Bounded(0, Edge.Open, 10, Edge.Open);
        var boundedClosedInterval = Interval<int>.Bounded(0, Edge.Closed, 10, Edge.Closed);
        var smallerInterval = Interval<int>.Bounded(3, Edge.Closed, 7, Edge.Closed);
        var leftBoundedOpenInterval = Interval<int>.LeftBounded(10, Edge.Open);
        var leftBoundedClosedInterval = Interval<int>.LeftBounded(10, Edge.Closed);
        var rightBoundedOpenInterval = Interval<int>.RightBounded(0, Edge.Open);
        var rightBoundedClosedInterval = Interval<int>.RightBounded(0, Edge.Closed);

        Assert.That(
            boundedOpenInterval.Includes(smallerInterval)
        );
        Assert.That(
            boundedOpenInterval.Includes(5)
        );
        Assert.That(
            leftBoundedClosedInterval.Includes(100)
        );
        Assert.That(
            !leftBoundedClosedInterval.Includes(5)
        );
        Assert.That(
            rightBoundedClosedInterval.Includes(-100)
        );
        Assert.That(
            !rightBoundedClosedInterval.Includes(5)
        );
    }
}

public class Interval<T> where T : struct, IComparable<T>
{
    private T? _left;
    private T? _right;
    private int _edges;

    private Interval(T? left, Edge leftEdge, T? right, Edge rightEdge)
    {
        if (left.HasValue && right.HasValue && left.Value.CompareTo(right.Value) > 0)
            throw new ArgumentException("Left edge must be lower than right edge");

        _left = left;
        _right = right;
        _edges = (leftEdge == Edge.Closed ? 0x1 : 0) | (rightEdge == Edge.Closed ? 0x2 : 0);
    }

    public T? Left
    {
        get { return _left; }
    }

    public Edge LeftEdge
    {
        get { return _left.HasValue ? ((_edges & 0x1) != 0 ? Edge.Closed : Edge.Open) : Edge.Unbounded; }
    }

    public T? Right
    {
        get { return _right; }
    }

    public Edge RightEdge
    {
        get { return _right.HasValue ? ((_edges & 0x2) != 0 ? Edge.Closed : Edge.Open) : Edge.Unbounded; }
    }

    public bool Includes(T value)
    {
        var leftCompare = CompareLeft(value);
        var rightCompare = CompareRight(value);

        return
            (leftCompare == CompareResult.Equals || leftCompare == CompareResult.Inside) &&
            (rightCompare == CompareResult.Equals || rightCompare == CompareResult.Inside);
    }

    public bool Includes(Interval<T> interval)
    {
        var leftEdge = LeftEdge;

        if (leftEdge != Edge.Unbounded)
        {
            if (
                leftEdge == Edge.Open &&
                interval.LeftEdge == Edge.Closed &&
                interval._left.Equals(_left)
            )
                return false;

            if (interval.CompareLeft(_left.Value) == CompareResult.Inside)
                return false;
        }

        var rightEdge = RightEdge;

        if (rightEdge != Edge.Unbounded)
        {
            if (
                rightEdge == Edge.Open &&
                interval.RightEdge == Edge.Closed &&
                interval._right.Equals(_right)
            )
                return false;

            if (interval.CompareRight(_right.Value) == CompareResult.Inside)
                return false;
        }

        return true;
    }

    private CompareResult CompareLeft(T value)
    {
        var leftEdge = LeftEdge;

        if (leftEdge == Edge.Unbounded)
            return CompareResult.Equals;

        if (leftEdge == Edge.Closed && _left.Value.Equals(value))
            return CompareResult.Inside;

        return _left.Value.CompareTo(value) < 0
            ? CompareResult.Inside
            : CompareResult.Outside;
    }

    private CompareResult CompareRight(T value)
    {
        var rightEdge = RightEdge;

        if (rightEdge == Edge.Unbounded)
            return CompareResult.Equals;

        if (rightEdge == Edge.Closed && _right.Value.Equals(value))
            return CompareResult.Inside;

        return _right.Value.CompareTo(value) > 0
            ? CompareResult.Inside
            : CompareResult.Outside;
    }

    public static Interval<T> LeftBounded(T left, Edge leftEdge)
    {
        return new Interval<T>(left, leftEdge, null, Edge.Unbounded);
    }

    public static Interval<T> RightBounded(T right, Edge rightEdge)
    {
        return new Interval<T>(null, Edge.Unbounded, right, rightEdge);
    }

    public static Interval<T> Bounded(T left, Edge leftEdge, T right, Edge rightEdge)
    {
        return new Interval<T>(left, leftEdge, right, rightEdge);
    }

    public static Interval<T> Unbounded()
    {
        return new Interval<T>(null, Edge.Unbounded, null, Edge.Unbounded);
    }

    public override bool Equals(object obj)
    {
        if (ReferenceEquals(this, obj))
            return true;

        var other = obj as Interval<T>;

        if (other == null)
            return false;

        return
            ((!_left.HasValue && !other._left.HasValue) || _left.Equals(other._left)) &&
            ((!_right.HasValue && !other._right.HasValue) || _right.Equals(other._right)) &&
            _edges == other._edges;
    }

    public override int GetHashCode()
    {
        return
            (_left.HasValue ? _left.GetHashCode() : 0) ^
            (_right.HasValue ? _right.GetHashCode() : 0) ^
            _edges.GetHashCode();
    }

    public static bool operator ==(Interval<T> a, Interval<T> b)
    {
        return ReferenceEquals(a, b) || a.Equals(b);
    }

    public static bool operator !=(Interval<T> a, Interval<T> b)
    {
        return !(a == b);
    }

    public override string ToString()
    {
        var leftEdge = LeftEdge;
        var rightEdge = RightEdge;

        var sb = new StringBuilder();

        if (leftEdge == Edge.Unbounded)
        {
            sb.Append("(-?");
        }
        else
        {
            if (leftEdge == Edge.Open)
                sb.Append('(');
            else
                sb.Append('[');

            sb.Append(_left.Value);
        }

        sb.Append(',');

        if (rightEdge == Edge.Unbounded)
        {
            sb.Append("?)");
        }
        else
        {
            sb.Append(_right.Value);

            if (rightEdge == Edge.Open)
                sb.Append(')');
            else
                sb.Append(']');
        }

        return sb.ToString();
    }

    private enum CompareResult
    {
        Inside,
        Outside,
        Equals
    }
}

public enum Edge
{
    Open,
    Closed,
    Unbounded
}

Answer 5

这样的事情实施起来很简单。请注意，因为大多数原始数据类型和 DateTime 都实现IComparable，所以您可以创建一个可以与所有这些类型一起使用的通用 inval 类型。