Repository: etcd-io/etcd
File: pkg/adt/interval_tree_test.go (Go)

Code before:
		{root: NewInt64Interval(410, 411), color: black, left: newInt64EmptyInterval(), right: newInt64EmptyInterval(), depth: 2},
		{root: NewInt64Interval(647, 648), color: black, left: newInt64EmptyInterval(), right: NewInt64Interval(815, 816), depth: 2},
		{root: NewInt64Interval(899, 900), color: red, left: NewInt64Interval(888, 889), right: NewInt64Interval(972, 973), depth: 2},

		{root: NewInt64Interval(82, 83), color: black, left: newInt64EmptyInterval(), right: NewInt64Interval(238, 239), depth: 3},
		{root: NewInt64Interval(292, 293), color: black, left: newInt64EmptyInterval(), right: newInt64EmptyInterval(), depth: 3},
		{root: NewInt64Interval(815, 816), color: red, left: newInt64EmptyInterval(), right: newInt64EmptyInterval(), depth: 3},
		{root: NewInt64Interval(888, 889), color: black, left: newInt64EmptyInterval(), right: newInt64EmptyInterval(), depth: 3},
		{root: NewInt64Interval(972, 973), color: black, left: NewInt64Interval(953, 954), right: newInt64EmptyInterval(), depth: 3},

		{root: NewInt64Interval(238, 239), color: red, left: newInt64EmptyInterval(), right: newInt64EmptyInterval(), depth: 4},
		{root: NewInt64Interval(953, 954), color: red, left: newInt64EmptyInterval(), right: newInt64EmptyInterval(), depth: 4},
	}
	visitsAfterDelete11 := tr.visitLevel()
	require.Truef(t, reflect.DeepEqual(expectedAfterDelete11, visitsAfterDelete11), "level order after deleting '11' expected %v, got %v", expectedAfterDelete11, visitsAfterDelete11)
}

func TestIntervalTreeFind(t *testing.T) {
	ivt := NewIntervalTree()
	ivl1 := NewInt64Interval(3, 6)
	assert.Nilf(t, ivt.Find(ivl1), "find expected nil on empty tree")
	ivt.Insert(ivl1, 123)
	assert.Equalf(t, ivl1, ivt.Find(ivl1).Ivl, "find expected to return exact-matched interval")
	ivl2 := NewInt64Interval(3, 7)
	assert.Nilf(t, ivt.Find(ivl2), "find expected nil on single-matched endpoint")
}

func TestIntervalTreeIntersects(t *testing.T) {
	ivt := NewIntervalTree()
	ivt.Insert(NewStringInterval("1", "3"), 123)

	assert.Falsef(t, ivt.Intersects(NewStringPoint("0")), "contains 0")
	assert.Truef(t, ivt.Intersects(NewStringPoint("1")), "missing 1")
	assert.Truef(t, ivt.Intersects(NewStringPoint("11")), "missing 11")
	assert.Truef(t, ivt.Intersects(NewStringPoint("2")), "missing 2")
	assert.Falsef(t, ivt.Intersects(NewStringPoint("3")), "contains 3")
}

func TestIntervalTreeStringAffine(t *testing.T) {
	ivt := NewIntervalTree()
	ivt.Insert(NewStringAffineInterval("8", ""), 123)
	assert.Truef(t, ivt.Intersects(NewStringAffinePoint("9")), "missing 9")
	assert.Falsef(t, ivt.Intersects(NewStringAffinePoint("7")), "contains 7")
}

func TestIntervalTreeStab(t *testing.T) {
	ivt := NewIntervalTree()
	ivt.Insert(NewStringInterval("0", "1"), 123)
	ivt.Insert(NewStringInterval("0", "2"), 456)
	ivt.Insert(NewStringInterval("5", "6"), 789)
	ivt.Insert(NewStringInterval("6", "8"), 999)

Review comment (suggestion):
Was looking for something more extensive. Quick prompt to ML gave me the following results:
```
func TestIntervalTreeFind(t *testing.T) {
	t.Run("Basic Find Operations", func(t *testing.T) {
		ivt := NewIntervalTree()
		ivl1 := NewInt64Interval(3, 6)
		val1 := 123

		// 1. Find on empty tree
		assert.Nil(t, ivt.Find(ivl1), "Find on empty tree should return nil")

		// 2. Insert and find exact match
		ivt.Insert(ivl1, val1)
		foundNode := ivt.Find(ivl1)
		assert.NotNil(t, foundNode, "Find should return the inserted interval")
		if foundNode != nil {
			assert.Equal(t, ivl1, foundNode.Ivl, "Found interval should match the inserted interval")
			assert.Equal(t, val1, foundNode.Val, "Found value should match the inserted value")
		}

		// 3. Find non-existent interval (overlapping start, different end)
		ivl2 := NewInt64Interval(3, 7)
		assert.Nil(t, ivt.Find(ivl2), "Find should return nil for an interval not exactly matching (different end)")

		// 4. Find non-existent interval (overlapping end, different start)
		ivl3 := NewInt64Interval(2, 6)
		assert.Nil(t, ivt.Find(ivl3), "Find should return nil for an interval not exactly matching (different start)")

		// 5. Find non-existent interval (completely different)
		ivl4 := NewInt64Interval(10, 20)
		assert.Nil(t, ivt.Find(ivl4), "Find should return nil for a completely different interval")

		// 6. Insert another interval and find both
		ivl5 := NewInt64Interval(10, 15)
		val5 := 456
		ivt.Insert(ivl5, val5)

		foundNode1 := ivt.Find(ivl1)
		assert.NotNil(t, foundNode1)
		if foundNode1 != nil {
			assert.Equal(t, ivl1, foundNode1.Ivl)
			assert.Equal(t, val1, foundNode1.Val)
		}

		foundNode5 := ivt.Find(ivl5)
		assert.NotNil(t, foundNode5)
		if foundNode5 != nil {
			assert.Equal(t, ivl5, foundNode5.Ivl)
			assert.Equal(t, val5, foundNode5.Val)
		}
	})

	t.Run("Find After Deletion", func(t *testing.T) {
		ivt := NewIntervalTree()
		ivlA := NewInt64Interval(1, 5)
		valA := "A"
		ivlB := NewInt64Interval(6, 10)
		valB := "B"

		ivt.Insert(ivlA, valA)
		ivt.Insert(ivlB, valB)

		assert.NotNil(t, ivt.Find(ivlA), "Should find ivlA before deletion")
		assert.NotNil(t, ivt.Find(ivlB), "Should find ivlB before deletion")

		deleted := ivt.Delete(ivlA)
		assert.True(t, deleted, "Delete should return true for an existing interval")
		assert.Nil(t, ivt.Find(ivlA), "Should not find ivlA after deletion")
		assert.NotNil(t, ivt.Find(ivlB), "Should still find ivlB after deleting ivlA")

		deleted = ivt.Delete(NewInt64Interval(100, 200)) // Non-existent
		assert.False(t, deleted, "Delete should return false for a non-existing interval")
	})

	t.Run("Find with StringComparable", func(t *testing.T) {
		ivt := NewIntervalTree()
		sivl1 := NewStringInterval("apple", "banana")
		sval1 := "fruit1"

		assert.Nil(t, ivt.Find(sivl1), "Find on empty string tree should return nil")

		ivt.Insert(sivl1, sval1)
		foundNode := ivt.Find(sivl1)
		assert.NotNil(t, foundNode, "Find should return the inserted string interval")
		if foundNode != nil {
			assert.Equal(t, sivl1, foundNode.Ivl)
			assert.Equal(t, sval1, foundNode.Val)
		}

		sivl2 := NewStringInterval("apple", "cherry") // Different end
		assert.Nil(t, ivt.Find(sivl2), "Find should return nil for a non-exact string interval")
	})

    t.Run("Find with overlapping but not identical intervals", func(t *testing.T) {
        ivt := NewIntervalTree()
        ivlBase := NewInt64Interval(5, 10)
        valBase := "base"
        ivt.Insert(ivlBase, valBase)

        // Test cases that overlap but are not identical
        testCases := []struct {
            name     string
            interval Interval
        }{
            {"Subset", NewInt64Interval(6, 9)},
            {"Superset", NewInt64Interval(4, 11)},
            {"OverlapLeft", NewInt64Interval(3, 7)},
            {"OverlapRight", NewInt64Interval(8, 12)},
            {"TouchesBegin", NewInt64Interval(3, 5)}, // Does not overlap [5,10)
            {"TouchesEnd", NewInt64Interval(10, 12)}, // Does not overlap [5,10)
        }

        for _, tc := range testCases {
            t.Run(tc.name, func(t *testing.T) {
                assert.Nil(t, ivt.Find(tc.interval), "Find(%v) should be nil as it's not an exact match for %v", tc.interval, ivlBase)
            })
        }
         // Ensure the base interval is still findable
        foundNode := ivt.Find(ivlBase)
        assert.NotNil(t, foundNode)
        if foundNode != nil {
            assert.Equal(t, ivlBase, foundNode.Ivl)
        }
    })
}
```

Code after:
		{root: NewInt64Interval(410, 411), color: black, left: newInt64EmptyInterval(), right: newInt64EmptyInterval(), depth: 2},
		{root: NewInt64Interval(647, 648), color: black, left: newInt64EmptyInterval(), right: NewInt64Interval(815, 816), depth: 2},
		{root: NewInt64Interval(899, 900), color: red, left: NewInt64Interval(888, 889), right: NewInt64Interval(972, 973), depth: 2},

		{root: NewInt64Interval(82, 83), color: black, left: newInt64EmptyInterval(), right: NewInt64Interval(238, 239), depth: 3},
		{root: NewInt64Interval(292, 293), color: black, left: newInt64EmptyInterval(), right: newInt64EmptyInterval(), depth: 3},
		{root: NewInt64Interval(815, 816), color: red, left: newInt64EmptyInterval(), right: newInt64EmptyInterval(), depth: 3},
		{root: NewInt64Interval(888, 889), color: black, left: newInt64EmptyInterval(), right: newInt64EmptyInterval(), depth: 3},
		{root: NewInt64Interval(972, 973), color: black, left: NewInt64Interval(953, 954), right: newInt64EmptyInterval(), depth: 3},

		{root: NewInt64Interval(238, 239), color: red, left: newInt64EmptyInterval(), right: newInt64EmptyInterval(), depth: 4},
		{root: NewInt64Interval(953, 954), color: red, left: newInt64EmptyInterval(), right: newInt64EmptyInterval(), depth: 4},
	}
	visitsAfterDelete11 := tr.visitLevel()
	require.Truef(t, reflect.DeepEqual(expectedAfterDelete11, visitsAfterDelete11), "level order after deleting '11' expected %v, got %v", expectedAfterDelete11, visitsAfterDelete11)
}

func TestIntervalTreeFind(t *testing.T) {
	ivt := NewIntervalTree()
	ivl1 := NewInt64Interval(3, 6)
	val := 123
	assert.Nilf(t, ivt.Find(ivl1), "find for %v expected nil on empty tree", ivl1)
	// insert interval [3, 6) into tree
	ivt.Insert(ivl1, val)
	// check cases of expected find matches and non-matches
	assert.NotNilf(t, ivt.Find(ivl1), "find expected not-nil on exact-matched interval %v", ivl1)
	assert.Equalf(t, ivl1, ivt.Find(ivl1).Ivl, "find expected to return exact-matched interval %v", ivl1)
	ivl2 := NewInt64Interval(3, 7)
	assert.Nilf(t, ivt.Find(ivl2), "find expected nil on matched start, different end %v", ivl2)
	ivl3 := NewInt64Interval(2, 6)
	assert.Nilf(t, ivt.Find(ivl3), "find expected nil on different start, matched end %v", ivl3)
	ivl4 := NewInt64Interval(10, 20)
	assert.Nilf(t, ivt.Find(ivl4), "find expected nil on different start, different end %v", ivl4)
	// insert the additional intervals into the tree, and check they can each be found.
	ivls := []Interval{ivl2, ivl3, ivl4}
	for _, ivl := range ivls {
		ivt.Insert(ivl, val)
		assert.NotNilf(t, ivt.Find(ivl), "find expected not-nil on exact-matched interval %v", ivl)
		assert.Equalf(t, ivl, ivt.Find(ivl).Ivl, "find expected to return exact-matched interval %v", ivl)
	}
	// check additional intervals no longer found after deletion
	for _, ivl := range ivls {
		assert.Truef(t, ivt.Delete(ivl), "expected successful delete on %v", ivl)
		assert.Nilf(t, ivt.Find(ivl), "find expected nil after deleted interval %v", ivl)
	}
}

func TestIntervalTreeIntersects(t *testing.T) {
	ivt := NewIntervalTree()
	ivt.Insert(NewStringInterval("1", "3"), 123)