Skip to main content
added comments
Source Link
Dmitry
  • 4.6k
  • 1
  • 20
  • 32
private static IEnumerable<Meeting<T>> FindIntersections<T>(IEnumerable<Meeting<T>> listX,
    IEnumerable<Meeting<T>> listY)
    where T : IComparable<T>
{
    var iteratorX = listX.GetEnumerator();
    var iteratorY = listY.GetEnumerator();
    Meeting<T> lastX = null;
    Meeting<T> lastY = null;
    iteratorX.MoveNext();
    iteratorY.MoveNext();
    while (iteratorX.Current != null && iteratorY.Current != null)
    {
        Meeting<T> x = iteratorX.Current;
        Meeting<T> y = iteratorY.Current; 

        // Move iterators if needed:
        if (x.End.CompareTo(y.Start) < 0)
        {
            iteratorX.MoveNext();
            continue;
        }
        if (y.End.CompareTo(x.Start) < 0)
        {
            iteratorY.MoveNext();
            continue;
        }

        // Add items to the resulting set, if the items aren't already there:
        if (lastX != x)
        {
            yield return x;
            lastX = x;
        }
        if (lastY != y)
        {
            yield return y;
            lastY = y;
        } 

        // Determine which iterator should be moved first:
        if (y.End.CompareTo(x.End) >= 0)
        {
            iteratorX.MoveNext();
        }
        else
        {
            iteratorY.MoveNext();
        }
    }
}
private static IEnumerable<Meeting<T>> FindIntersections<T>(IEnumerable<Meeting<T>> listX,
    IEnumerable<Meeting<T>> listY)
    where T : IComparable<T>
{
    var iteratorX = listX.GetEnumerator();
    var iteratorY = listY.GetEnumerator();
    Meeting<T> lastX = null;
    Meeting<T> lastY = null;
    iteratorX.MoveNext();
    iteratorY.MoveNext();
    while (iteratorX.Current != null && iteratorY.Current != null)
    {
        Meeting<T> x = iteratorX.Current;
        Meeting<T> y = iteratorY.Current;
        if (x.End.CompareTo(y.Start) < 0)
        {
            iteratorX.MoveNext();
            continue;
        }
        if (y.End.CompareTo(x.Start) < 0)
        {
            iteratorY.MoveNext();
            continue;
        }

        if (lastX != x)
        {
            yield return x;
            lastX = x;
        }
        if (lastY != y)
        {
            yield return y;
            lastY = y;
        }
        if (y.End.CompareTo(x.End) >= 0)
            iteratorX.MoveNext();
        else
            iteratorY.MoveNext();
    }
}
private static IEnumerable<Meeting<T>> FindIntersections<T>(IEnumerable<Meeting<T>> listX,
    IEnumerable<Meeting<T>> listY)
    where T : IComparable<T>
{
    var iteratorX = listX.GetEnumerator();
    var iteratorY = listY.GetEnumerator();
    Meeting<T> lastX = null;
    Meeting<T> lastY = null;
    iteratorX.MoveNext();
    iteratorY.MoveNext();
    while (iteratorX.Current != null && iteratorY.Current != null)
    {
        Meeting<T> x = iteratorX.Current;
        Meeting<T> y = iteratorY.Current; 

        // Move iterators if needed:
        if (x.End.CompareTo(y.Start) < 0)
        {
            iteratorX.MoveNext();
            continue;
        }
        if (y.End.CompareTo(x.Start) < 0)
        {
            iteratorY.MoveNext();
            continue;
        }

        // Add items to the resulting set, if the items aren't already there:
        if (lastX != x)
        {
            yield return x;
            lastX = x;
        }
        if (lastY != y)
        {
            yield return y;
            lastY = y;
        } 

        // Determine which iterator should be moved first:
        if (y.End.CompareTo(x.End) >= 0)
        {
            iteratorX.MoveNext();
        }
        else
        {
            iteratorY.MoveNext();
        }
    }
}
added 79 characters in body
Source Link
Dmitry
  • 4.6k
  • 1
  • 20
  • 32

The method above returns a set of the unique Meeting<T>s:

  • Returns a set of the unique Meeting<T>s.
  • Supports case if one range overlaps several ranges in another set.

The method above returns a set of the unique Meeting<T>s

The method above:

  • Returns a set of the unique Meeting<T>s.
  • Supports case if one range overlaps several ranges in another set.
added method for sorted sets
Source Link
Dmitry
  • 4.6k
  • 1
  • 20
  • 32

EDIT
Try this code to find intersections of the sorted sets. It has complexity \$O(N+M)\$:

private static IEnumerable<Meeting<T>> FindIntersections<T>(IEnumerable<Meeting<T>> listX,
    IEnumerable<Meeting<T>> listY)
    where T : IComparable<T>
{
    var iteratorX = listX.GetEnumerator();
    var iteratorY = listY.GetEnumerator();
    Meeting<T> lastX = null;
    Meeting<T> lastY = null;
    iteratorX.MoveNext();
    iteratorY.MoveNext();
    while (iteratorX.Current != null && iteratorY.Current != null)
    {
        Meeting<T> x = iteratorX.Current;
        Meeting<T> y = iteratorY.Current;
        if (x.End.CompareTo(y.Start) < 0)
        {
            iteratorX.MoveNext();
            continue;
        }
        if (y.End.CompareTo(x.Start) < 0)
        {
            iteratorY.MoveNext();
            continue;
        }

        if (lastX != x)
        {
            yield return x;
            lastX = x;
        }
        if (lastY != y)
        {
            yield return y;
            lastY = y;
        }
        if (y.End.CompareTo(x.End) >= 0)
            iteratorX.MoveNext();
        else
            iteratorY.MoveNext();
    }
}

The method above returns a set of the unique Meeting<T>s

EDIT
Try this code to find intersections of the sorted sets. It has complexity \$O(N+M)\$:

private static IEnumerable<Meeting<T>> FindIntersections<T>(IEnumerable<Meeting<T>> listX,
    IEnumerable<Meeting<T>> listY)
    where T : IComparable<T>
{
    var iteratorX = listX.GetEnumerator();
    var iteratorY = listY.GetEnumerator();
    Meeting<T> lastX = null;
    Meeting<T> lastY = null;
    iteratorX.MoveNext();
    iteratorY.MoveNext();
    while (iteratorX.Current != null && iteratorY.Current != null)
    {
        Meeting<T> x = iteratorX.Current;
        Meeting<T> y = iteratorY.Current;
        if (x.End.CompareTo(y.Start) < 0)
        {
            iteratorX.MoveNext();
            continue;
        }
        if (y.End.CompareTo(x.Start) < 0)
        {
            iteratorY.MoveNext();
            continue;
        }

        if (lastX != x)
        {
            yield return x;
            lastX = x;
        }
        if (lastY != y)
        {
            yield return y;
            lastY = y;
        }
        if (y.End.CompareTo(x.End) >= 0)
            iteratorX.MoveNext();
        else
            iteratorY.MoveNext();
    }
}

The method above returns a set of the unique Meeting<T>s

added 250 characters in body
Source Link
Dmitry
  • 4.6k
  • 1
  • 20
  • 32
Loading
Source Link
Dmitry
  • 4.6k
  • 1
  • 20
  • 32
Loading