Интервальный тип данных для С#.NET?

Ответ 1

Как утверждали другие, интегрального типа интервала нет. В зависимости от потребностей вашего проекта, просто Tuple<T1, T2> или позвоните Enumerable.Range с несколькими дополнительными строками кода может быть достаточно. HashSet<T> содержит заданные методы работы, такие как UnionWith, IntersectWith и более, но все же сохраняет все элементы, а не только конечные точки.

Многие реализации можно найти в Интернете. Существует базовый общий класс Range в Microsoft Research Dynamic Data Показать проект, а другой - Кевин Гадд. Проект AForge содержит неосновную реализацию IntInterval/DoubleInterval. Другое (1, 2). Вопросы также могут представлять интерес. Энди Клаймер имеет интересную динамически скомпилированную реализацию на в своем блоге. Более полные решения можно найти на CodeProject, в Jon Skeet книга и Из России с любовью. Кажется, что несколько (1, 2). Я видел других, прежде чем я не могу найти в данный момент.

Независимо от того, что вы делаете, будьте внимательны при использовании типа универсального интервала. На самом деле трудно написать правильный монолитный общий интервал, потому что целые числа и интервалы с плавающей запятой имеют разные математические свойства. Например, все целые интервалы могут быть представлены с закрытыми конечными точками, а пара [1,2] [3,6] может рассматриваться как смежная, эквивалентная [1,6]. Ничего из этого не верно для интервалов с плавающей запятой. Подробнее см. Wikipedia. Группа классов может быть лучше, с абстрактным общим базовым классом и типизированными производными классами IntInterval или DoubleInterval для реализации различных типов поведения.

Помимо математики, существует еще несколько проблем с реализацией общих типов интервалов. Невозможно легко выполнить арифметику с дженериками в С#, и есть проблемы с плавающей запятой NaN и ошибки округления. Подробнее об этом см. Документация по расширению библиотеки Interval<T>. (Многие из них переводится на С# и .NET.) К счастью, многие операции могут выполняться только с помощью IComparable<T>.

Как я упоминал ранее, выбор того, что подходит с точки зрения функциональности и правильности, зависит от требований ваших проектов.

Ответ 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));
    }
}

Ответ 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;
    }
}

Ответ 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
}

Ответ 5

Такую вещь тривиально реализовать. Обратите внимание: поскольку большинство примитивных типов данных, а также DateTime реализуют IComparable, вы можете создать общий тип inval, который может работать со всеми этими типами.

Ответ 6

Обычно я использовал стандартные классы .NET Framework.

int a = 2;
int b = 10;

// a < x <= b
var interval1 = new HashSet<int>(Enumerable.Range(a + 1, b - a));

// Dump is a LINQPad extension method.
interval1.Dump();
// 3..10

// Check if point in interval
interval1.Contains(a).Dump();
// False
interval1.Contains(b).Dump();
// True

var overlappingInterval = new HashSet<int>(Enumerable.Range(9, 3));
overlappingInterval.Dump();
// 9, 10, 11

var nonOverlappingInterval = new HashSet<int>(Enumerable.Range(11, 2));
nonOverlappingInterval.Dump();
// 11, 12

interval1.Overlaps(overlappingInterval).Dump();
// True

interval1.Overlaps(nonOverlappingInterval).Dump();
// False

interval1.UnionWith(overlappingInterval);
interval1.Dump();
// 3..11
// Alternately use LINQ Union to avoid mutating.
// Also IntersectWith, IsSubsetOf, etc. (plus all the LINQ extensions).

РЕДАКТИРОВАТЬ: Если вы хотите принудительно установить, что это интервал, а не набор (и/или обеспечить неизменность), вы можете обернуть это в пользовательский класс.