|
// Licensed to the .NET Foundation under one or more agreements.
// The .NET Foundation licenses this file to you under the MIT license.
// See the LICENSE file in the project root for more information.
#nullable disable
using System;
using System.Collections.Generic;
using System.Linq;
using Microsoft.CodeAnalysis.Shared.Collections;
using Microsoft.CodeAnalysis.Text;
using Microsoft.VisualStudio.Text;
using Roslyn.Test.Utilities;
using Xunit;
namespace Microsoft.CodeAnalysis.Editor.UnitTests.Collections
{
public class IntervalTreeTests
{
private readonly struct TupleIntrospector<T> : IIntervalIntrospector<Tuple<int, int, T>>
{
public int GetStart(Tuple<int, int, T> value)
=> value.Item1;
public int GetLength(Tuple<int, int, T> value)
=> value.Item2;
}
private static IEnumerable<SimpleIntervalTree<Tuple<int, int, string>, TupleIntrospector<string>>> CreateTrees(params Tuple<int, int, string>[] values)
=> CreateTrees((IEnumerable<Tuple<int, int, string>>)values);
private static IEnumerable<SimpleIntervalTree<Tuple<int, int, string>, TupleIntrospector<string>>> CreateTrees(IEnumerable<Tuple<int, int, string>> values)
{
yield return SimpleIntervalTree.Create(new TupleIntrospector<string>(), values);
}
[Fact]
public void TestEmpty()
{
foreach (var tree in CreateTrees())
{
var spans = tree.GetIntervalsThatOverlapWith(0, 1);
Assert.Empty(spans);
}
}
[Fact]
public void TestBeforeSpan()
{
foreach (var tree in CreateTrees(Tuple.Create(5, 5, "A")))
{
var spans = tree.GetIntervalsThatOverlapWith(0, 1);
Assert.Empty(spans);
}
}
[Fact]
public void TestAbuttingBeforeSpan()
{
foreach (var tree in CreateTrees(Tuple.Create(5, 5, "A")))
{
var spans = tree.GetIntervalsThatOverlapWith(0, 5);
Assert.Empty(spans);
}
}
[Fact]
public void TestAfterSpan()
{
foreach (var tree in CreateTrees(Tuple.Create(5, 5, "A")))
{
var spans = tree.GetIntervalsThatOverlapWith(15, 5);
Assert.Empty(spans);
}
}
[Fact]
public void TestAbuttingAfterSpan()
{
foreach (var tree in CreateTrees(Tuple.Create(5, 5, "A")))
{
var spans = tree.GetIntervalsThatOverlapWith(10, 5);
Assert.Empty(spans);
}
}
[Fact]
public void TestMatchingSpan()
{
foreach (var tree in CreateTrees(Tuple.Create(5, 5, "A")))
{
var spans = tree.GetIntervalsThatOverlapWith(5, 5).Select(t => t.Item3);
Assert.True(Set("A").SetEquals(spans));
}
}
[Fact]
public void TestContainedAbuttingStart()
{
foreach (var tree in CreateTrees(Tuple.Create(5, 5, "A")))
{
var spans = tree.GetIntervalsThatOverlapWith(5, 2).Select(i => i.Item3);
Assert.True(Set("A").SetEquals(spans));
}
}
[Fact]
public void TestContainedAbuttingEnd()
{
foreach (var tree in CreateTrees(Tuple.Create(5, 5, "A")))
{
var spans = tree.GetIntervalsThatOverlapWith(8, 2).Select(i => i.Item3);
Assert.True(Set("A").SetEquals(spans));
}
}
[Fact]
public void TestCompletedContained()
{
foreach (var tree in CreateTrees(Tuple.Create(5, 5, "A")))
{
var spans = tree.GetIntervalsThatOverlapWith(7, 2).Select(i => i.Item3);
Assert.True(Set("A").SetEquals(spans));
}
}
[Fact]
public void TestOverlappingStart()
{
foreach (var tree in CreateTrees(Tuple.Create(5, 5, "A")))
{
var spans = tree.GetIntervalsThatOverlapWith(4, 2).Select(i => i.Item3);
Assert.True(Set("A").SetEquals(spans));
}
}
[Fact]
public void TestOverlappingEnd()
{
foreach (var tree in CreateTrees(Tuple.Create(5, 5, "A")))
{
var spans = tree.GetIntervalsThatOverlapWith(9, 2).Select(i => i.Item3);
Assert.True(Set("A").SetEquals(spans));
}
}
[Fact]
public void TestOverlappingAll()
{
foreach (var tree in CreateTrees(Tuple.Create(5, 5, "A")))
{
var spans = tree.GetIntervalsThatOverlapWith(4, 7).Select(i => i.Item3);
Assert.True(Set("A").SetEquals(spans));
}
}
[Fact]
public void TestNonOverlappingSpans()
{
foreach (var tree in CreateTrees(Tuple.Create(5, 5, "A"), Tuple.Create(15, 5, "B")))
{
// Test between the spans
Assert.Empty(tree.GetIntervalsThatOverlapWith(2, 2));
Assert.Empty(tree.GetIntervalsThatOverlapWith(11, 2));
Assert.Empty(tree.GetIntervalsThatOverlapWith(22, 2));
// Test in the spans
Assert.True(Set("A").SetEquals(tree.GetIntervalsThatOverlapWith(6, 2).Select(i => i.Item3)));
Assert.True(Set("B").SetEquals(tree.GetIntervalsThatOverlapWith(16, 2).Select(i => i.Item3)));
// Test covering both spans
Assert.True(Set("A", "B").SetEquals(tree.GetIntervalsThatOverlapWith(2, 20).Select(i => i.Item3)));
Assert.True(Set("A", "B").SetEquals(tree.GetIntervalsThatOverlapWith(2, 14).Select(i => i.Item3)));
Assert.True(Set("A", "B").SetEquals(tree.GetIntervalsThatOverlapWith(6, 10).Select(i => i.Item3)));
Assert.True(Set("A", "B").SetEquals(tree.GetIntervalsThatOverlapWith(6, 20).Select(i => i.Item3)));
}
}
[Fact]
public void TestSubsumedSpans()
{
var spans = List(
Tuple.Create(5, 5, "a"),
Tuple.Create(6, 3, "b"),
Tuple.Create(7, 1, "c"));
TestOverlapsAndIntersects(spans);
}
[Fact]
public void TestOverlappingSpans()
{
var spans = List(
Tuple.Create(5, 5, "a"),
Tuple.Create(7, 5, "b"),
Tuple.Create(9, 5, "c"));
TestOverlapsAndIntersects(spans);
}
[Fact]
public void TestIntersectsWith()
{
var spans = List(
Tuple.Create(0, 2, "a"));
foreach (var tree in CreateTrees(spans))
{
Assert.False(tree.HasIntervalThatIntersectsWith(-1));
Assert.True(tree.HasIntervalThatIntersectsWith(0));
Assert.True(tree.HasIntervalThatIntersectsWith(1));
Assert.True(tree.HasIntervalThatIntersectsWith(2));
Assert.False(tree.HasIntervalThatIntersectsWith(3));
}
}
[Fact]
public void LargeTest()
{
var spans = List(
Tuple.Create(0, 3, "a"),
Tuple.Create(5, 3, "b"),
Tuple.Create(6, 4, "c"),
Tuple.Create(8, 1, "d"),
Tuple.Create(15, 8, "e"),
Tuple.Create(16, 5, "f"),
Tuple.Create(17, 2, "g"),
Tuple.Create(19, 1, "h"),
Tuple.Create(25, 5, "i"));
TestOverlapsAndIntersects(spans);
}
[Fact]
public void TestCrash1()
{
foreach (var _ in CreateTrees(Tuple.Create(8, 1, "A"), Tuple.Create(59, 1, "B"), Tuple.Create(52, 1, "C")))
{
}
}
[Fact]
public void TestEmptySpanAtStart()
{
// Make sure creating empty spans works (there was a bug here)
var tree = CreateTrees(Tuple.Create(0, 0, "A")).Last();
Assert.Equal(1, tree.Count());
}
private readonly struct Int32Introspector : IIntervalIntrospector<int>
{
public int GetLength(int value)
=> 0;
public int GetStart(int value)
=> value;
}
private static IntervalTree<int> CreateIntTree(params int[] values)
=> IntervalTree<int>.Create(new Int32Introspector(), values);
[Fact]
public void TestSortedEnumerable1()
{
Assert.Equal(CreateIntTree(0, 0, 0), new[] { 0, 0, 0 });
Assert.Equal(CreateIntTree(0, 0, 1), new[] { 0, 0, 1 });
Assert.Equal(CreateIntTree(0, 0, 2), new[] { 0, 0, 2 });
Assert.Equal(CreateIntTree(0, 1, 0), new[] { 0, 0, 1 });
Assert.Equal(CreateIntTree(0, 1, 1), new[] { 0, 1, 1 });
Assert.Equal(CreateIntTree(0, 1, 2), new[] { 0, 1, 2 });
Assert.Equal(CreateIntTree(0, 2, 0), new[] { 0, 0, 2 });
Assert.Equal(CreateIntTree(0, 2, 1), new[] { 0, 1, 2 });
Assert.Equal(CreateIntTree(0, 2, 2), new[] { 0, 2, 2 });
Assert.Equal(CreateIntTree(1, 0, 0), new[] { 0, 0, 1 });
Assert.Equal(CreateIntTree(1, 0, 1), new[] { 0, 1, 1 });
Assert.Equal(CreateIntTree(1, 0, 2), new[] { 0, 1, 2 });
Assert.Equal(CreateIntTree(1, 1, 0), new[] { 0, 1, 1 });
Assert.Equal(CreateIntTree(1, 1, 1), new[] { 1, 1, 1 });
Assert.Equal(CreateIntTree(1, 1, 2), new[] { 1, 1, 2 });
Assert.Equal(CreateIntTree(1, 2, 0), new[] { 0, 1, 2 });
Assert.Equal(CreateIntTree(1, 2, 1), new[] { 1, 1, 2 });
Assert.Equal(CreateIntTree(1, 2, 2), new[] { 1, 2, 2 });
Assert.Equal(CreateIntTree(2, 0, 0), new[] { 0, 0, 2 });
Assert.Equal(CreateIntTree(2, 0, 1), new[] { 0, 1, 2 });
Assert.Equal(CreateIntTree(2, 0, 2), new[] { 0, 2, 2 });
Assert.Equal(CreateIntTree(2, 1, 0), new[] { 0, 1, 2 });
Assert.Equal(CreateIntTree(2, 1, 1), new[] { 1, 1, 2 });
Assert.Equal(CreateIntTree(2, 1, 2), new[] { 1, 2, 2 });
Assert.Equal(CreateIntTree(2, 2, 0), new[] { 0, 2, 2 });
Assert.Equal(CreateIntTree(2, 2, 1), new[] { 1, 2, 2 });
Assert.Equal(CreateIntTree(2, 2, 2), new[] { 2, 2, 2 });
}
[Fact]
public void TestSortedEnumerable2()
{
var tree = IntervalTree<int>.Create(new Int32Introspector(), new[] { 1, 0 });
Assert.Equal(tree, new[] { 0, 1 });
}
private static void TestOverlapsAndIntersects(IList<Tuple<int, int, string>> spans)
{
foreach (var tree in CreateTrees(spans))
{
var max = spans.Max(t => t.Item1 + t.Item2);
for (var start = 0; start <= max; start++)
{
for (var length = 1; length <= max; length++)
{
var span = new Span(start, length);
var set1 = new HashSet<string>(tree.GetIntervalsThatOverlapWith(start, length).Select(i => i.Item3));
var set2 = new HashSet<string>(spans.Where(t =>
{
return span.OverlapsWith(new Span(t.Item1, t.Item2));
}).Select(t => t.Item3));
Assert.True(set1.SetEquals(set2));
var set3 = new HashSet<string>(tree.GetIntervalsThatIntersectWith(start, length).Select(i => i.Item3));
var set4 = new HashSet<string>(spans.Where(t =>
{
return span.IntersectsWith(new Span(t.Item1, t.Item2));
}).Select(t => t.Item3));
Assert.True(set3.SetEquals(set4));
}
}
Assert.Equal(spans.Count, tree.Count());
Assert.True(new HashSet<string>(spans.Select(t => t.Item3)).SetEquals(tree.Select(i => i.Item3)));
}
}
private static ISet<T> Set<T>(params T[] values)
=> new HashSet<T>(values);
private static IList<T> List<T>(params T[] values)
=> new List<T>(values);
}
}
|