tipos - Tipo de datos de intervalo para C#.NET?

niveles de medicion ejemplos

Question

Estoy buscando un tipo de datos de interval para .NET 4.0. Por ejemplo, el intervalo (a, b], todos señalan x de tal manera que a <x <= b.

Lo que me gustaría poder hacer es crear intervalos con las siguientes propiedades:

• Extremos cerrados y abiertos.
• Intervalos ilimitados, totalmente ilimitados, y derecha / izquierda ilimitados.

Con estos me gustaría hacer una cosa como:

• Compruebe si un punto está en un intervalo.
• Compruebe si dos intervalos se superponen.
• Combine dos intervalos superpuestos en un solo intervalo.
• Compruebe si una colección de intervalos cubre un solo intervalo.
• Etc :)

Estaría bien si pudiera trabajar tanto con el tipo de datos numérico como con los tiempos de datos.

Sé que la lógica es bastante sencilla, pero no veo ninguna razón por la que yo sea la primera en necesitar algo así tampoco.

Answer 1

En general, usaría las clases estándar de .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''s Union to avoid mutating.
// Also IntersectWith, IsSubsetOf, etc. (plus all the LINQ extensions).

EDITAR: Si desea imponer que se trata de un intervalo en lugar de un conjunto (y / o imponer la inmutabilidad), podría ajustarlo en una clase personalizada.

Answer 2

Implementé esto hace mucho tiempo para el marco .NET e incluso incluí soporte para DateTime y TimeSpan , ya que este fue uno de mis principales casos de uso (implementación de una línea de tiempo en WPF ). Mi implementación soporta todo lo que solicite, excepto intervalos ilimitados. Esto me permitió hacer cosas geniales como:

// Mockup of a GUI element and mouse position.
var timeBar = new { X = 100, Width = 200 };
int mouseX = 180;

// Find out which date on the time bar the mouse is positioned on,
// assuming it represents whole of 2014.
var timeRepresentation = new Interval<int>( timeBar.X, timeBar.X + timeBar.Width );
DateTime start = new DateTime( 2014, 1, 1 );
DateTime end = new DateTime( 2014, 12, 31 );
var thisYear = new Interval<DateTime, TimeSpan>( start, end );
DateTime hoverOver = timeRepresentation.Map( mouseX, thisYear );

// If the user clicks, zoom in to this position.
double zoomLevel = 0.5;
double zoomInAt = thisYear.GetPercentageFor( hoverOver );
Interval<DateTime, TimeSpan> zoomed = thisYear.Scale( zoomLevel, zoomInAt );

// Iterate over the interval, e.g. draw labels.
zoomed.EveryStepOf( TimeSpan.FromDays( 1 ), d => DrawLabel( d ) );

Más recientemente, porté un AbstractInterval<T> a una versión anterior del estándar .NET que simplifica la implementación de tipos concretos. Por ejemplo, IntInterval que se incluye en la biblioteca . Debido a las restricciones (al menos en el momento) del estándar .NET, tuve que apuntar a .NET Core para una implementación genérica completa. Una implementación totalmente genérica de Interval<T> basa en las clases base de .NET Standard.

El mayor inconveniente de esto es que hay bastantes dependencias en todo el lugar (por lo tanto, copiar parte de este proyecto será difícil). La razón de esto es que la implementación de esto no es en absoluto trivial (a diferencia de otros que han comentado sobre esto). En caso de que todavía no haya ninguna buena biblioteca de ''intervalo'' para .NET, realmente debería hacer de este un paquete separado. La biblioteca estándar de .NET está disponible en Nuget .

Answer 3

Lo siguiente permite rangos abiertos de cualquier tipo que implemente IComparable . Una extensión obvia sería permitirle pasar su propio comparador (de la misma forma que lo hace Hashset<T> .

El rango en este caso es un <= x

Incluye superposición y fusión. Otras funciones deberían ser razonablemente fáciles de agregar.

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

Para empezar:

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 5

Tal cosa es trivial de implementar. Tenga en cuenta que debido a que la mayoría de los tipos de datos primitivos y también DateTime implementan IComparable , puede crear un tipo invaluable genérico que pueda funcionar con todos estos tipos.

Answer 6

Incluye un punto de partida a continuación.

Aunque esto sería un buen desafío para la mente, así que lo intenté. Esto está lejos de ser completo y podrían realizarse muchas más operaciones, pero es un comienzo.

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 7

Como han dicho otros, no hay un tipo de intervalo integrado. Dependiendo de las necesidades de su proyecto, una simple Tuple<T1, T2> o una llamada a Enumerable.Range con unas pocas líneas adicionales de código puede ser suficiente. El HashSet<T> contiene métodos de operación establecidos, como UnionWith, IntersectWith y más, pero aún almacena todos los elementos, no solo los puntos finales.

Muchas implementaciones se pueden encontrar en línea. Existe la parte básica genérica de la clase Range del proyecto Microsoft Research Dynamic Data Display y otra de Kevin Gadd . El proyecto AForge contiene una implementación IntInterval / DoubleInterval no genérica. Otras preguntas ( 1 , 2 ) SO también pueden ser de interés. Andy Clymer tiene una interesante implementación compilada dinámicamente en su blog . Se pueden encontrar soluciones más completas en CodeProject , en el libro de Jon Skeet y Desde Rusia con amor . Parece que también hay algunas ( 1 , 2 ) soluciones comerciales. He visto otros antes que no puedo encontrar en este momento.

Hagas lo que hagas, ten cuidado cuando uses un tipo de intervalo genérico. En realidad, es difícil escribir una clase de intervalo genérico monolítica correcta porque los intervalos de punto flotante y entero tienen diferentes propiedades matemáticas. Por ejemplo, todos los intervalos de enteros se pueden representar con puntos finales cerrados y el par [1,2] [3,6] se puede considerar como contiguo, equivalente a [1,6] . Nada de esto es cierto con intervalos de puntos flotantes. Ver Wikipedia para más detalles. Un grupo de clases podría ser mejor, con una clase base genérica abstracta y clases derivadas tipeadas IntInterval o DoubleInterval para implementar los diferentes comportamientos.

Aparte de las matemáticas, hay algunas dificultades de implementación más con los tipos de intervalo genéricos. No es posible hacer aritmética con genéricos en C #, y hay errores de redondeo de NaN y de redondeo que hay que cuidar. Consulte la documentación de la biblioteca Boost para el Interval<T> para obtener más información sobre esto. (Mucho de esto se traduce a C # y .NET.) Afortunadamente, muchas operaciones se pueden hacer con solo IComparable<T> .

Como mencioné anteriormente, la elección de lo que es apropiado en términos de funcionalidad y corrección depende de los requisitos de sus proyectos.