etcd-io__etcd/pkg/adt/interval_tree_test.go

// Copyright 2016 The etcd Authors
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//     http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

package adt

import (
	"math/rand"
	"testing"
	"time"
)

func TestIntervalTreeContains(t *testing.T) {
	ivt := &IntervalTree{}
	ivt.Insert(NewStringInterval("1", "3"), 123)

	if ivt.Contains(NewStringPoint("0")) {
		t.Errorf("contains 0")
	}
	if !ivt.Contains(NewStringPoint("1")) {
		t.Errorf("missing 1")
	}
	if !ivt.Contains(NewStringPoint("11")) {
		t.Errorf("missing 11")
	}
	if !ivt.Contains(NewStringPoint("2")) {
		t.Errorf("missing 2")
	}
	if ivt.Contains(NewStringPoint("3")) {
		t.Errorf("contains 3")
	}
}

func TestIntervalTreeStringAffine(t *testing.T) {
	ivt := &IntervalTree{}
	ivt.Insert(NewStringAffineInterval("8", ""), 123)
	if !ivt.Contains(NewStringAffinePoint("9")) {
		t.Errorf("missing 9")
	}
	if ivt.Contains(NewStringAffinePoint("7")) {
		t.Errorf("contains 7")
	}
}

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

	if ivt.root.max.Compare(StringComparable("8")) != 0 {
		t.Fatalf("wrong root max got %v, expected 8", ivt.root.max)
	}
	if x := len(ivt.Stab(NewStringPoint("0"))); x != 3 {
		t.Errorf("got %d, expected 3", x)
	}
	if x := len(ivt.Stab(NewStringPoint("1"))); x != 2 {
		t.Errorf("got %d, expected 2", x)
	}
	if x := len(ivt.Stab(NewStringPoint("2"))); x != 1 {
		t.Errorf("got %d, expected 1", x)
	}
	if x := len(ivt.Stab(NewStringPoint("3"))); x != 0 {
		t.Errorf("got %d, expected 0", x)
	}
	if x := len(ivt.Stab(NewStringPoint("5"))); x != 1 {
		t.Errorf("got %d, expected 1", x)
	}
	if x := len(ivt.Stab(NewStringPoint("55"))); x != 1 {
		t.Errorf("got %d, expected 1", x)
	}
	if x := len(ivt.Stab(NewStringPoint("6"))); x != 1 {
		t.Errorf("got %d, expected 1", x)
	}
}

type xy struct {
	x int64
	y int64
}

func TestIntervalTreeRandom(t *testing.T) {
	// generate unique intervals
	ivs := make(map[xy]struct{})
	ivt := &IntervalTree{}
	maxv := 128
	rand.Seed(time.Now().UnixNano())

	for i := rand.Intn(maxv) + 1; i != 0; i-- {
		x, y := int64(rand.Intn(maxv)), int64(rand.Intn(maxv))
		if x > y {
			t := x
			x = y
			y = t
		} else if x == y {
			y++
		}
		iv := xy{x, y}
		if _, ok := ivs[iv]; ok {
			// don't double insert
			continue
		}
		ivt.Insert(NewInt64Interval(x, y), 123)
		ivs[iv] = struct{}{}
	}

	for ab := range ivs {
		for xy := range ivs {
			v := xy.x + int64(rand.Intn(int(xy.y-xy.x)))
			if slen := len(ivt.Stab(NewInt64Point(v))); slen == 0 {
				t.Fatalf("expected %v stab non-zero for [%+v)", v, xy)
			}
			if !ivt.Contains(NewInt64Point(v)) {
				t.Fatalf("did not get %d as expected for [%+v)", v, xy)
			}
		}
		if !ivt.Delete(NewInt64Interval(ab.x, ab.y)) {
			t.Errorf("did not delete %v as expected", ab)
		}
		delete(ivs, ab)
	}

	if ivt.Len() != 0 {
		t.Errorf("got ivt.Len() = %v, expected 0", ivt.Len())
	}
}

// TestIntervalTreeSortedVisit tests that intervals are visited in sorted order.
func TestIntervalTreeSortedVisit(t *testing.T) {
	tests := []struct {
		ivls       []Interval
		visitRange Interval
	}{
		{
			ivls:       []Interval{NewInt64Interval(1, 10), NewInt64Interval(2, 5), NewInt64Interval(3, 6)},
			visitRange: NewInt64Interval(0, 100),
		},
		{
			ivls:       []Interval{NewInt64Interval(1, 10), NewInt64Interval(10, 12), NewInt64Interval(3, 6)},
			visitRange: NewInt64Interval(0, 100),
		},
		{
			ivls:       []Interval{NewInt64Interval(2, 3), NewInt64Interval(3, 4), NewInt64Interval(6, 7), NewInt64Interval(5, 6)},
			visitRange: NewInt64Interval(0, 100),
		},
		{
			ivls: []Interval{
				NewInt64Interval(2, 3),
				NewInt64Interval(2, 4),
				NewInt64Interval(3, 7),
				NewInt64Interval(2, 5),
				NewInt64Interval(3, 8),
				NewInt64Interval(3, 5),
			},
			visitRange: NewInt64Interval(0, 100),
		},
	}
	for i, tt := range tests {
		ivt := &IntervalTree{}
		for _, ivl := range tt.ivls {
			ivt.Insert(ivl, struct{}{})
		}
		last := tt.ivls[0].Begin
		count := 0
		chk := func(iv *IntervalValue) bool {
			if last.Compare(iv.Ivl.Begin) > 0 {
				t.Errorf("#%d: expected less than %d, got interval %+v", i, last, iv.Ivl)
			}
			last = iv.Ivl.Begin
			count++
			return true
		}
		ivt.Visit(tt.visitRange, chk)
		if count != len(tt.ivls) {
			t.Errorf("#%d: did not cover all intervals. expected %d, got %d", i, len(tt.ivls), count)
		}
	}
}

// TestIntervalTreeVisitExit tests that visiting can be stopped.
func TestIntervalTreeVisitExit(t *testing.T) {
	ivls := []Interval{NewInt64Interval(1, 10), NewInt64Interval(2, 5), NewInt64Interval(3, 6), NewInt64Interval(4, 8)}
	ivlRange := NewInt64Interval(0, 100)
	tests := []struct {
		f IntervalVisitor

		wcount int
	}{
		{
			f:      func(n *IntervalValue) bool { return false },
			wcount: 1,
		},
		{
			f:      func(n *IntervalValue) bool { return n.Ivl.Begin.Compare(ivls[0].Begin) <= 0 },
			wcount: 2,
		},
		{
			f:      func(n *IntervalValue) bool { return n.Ivl.Begin.Compare(ivls[2].Begin) < 0 },
			wcount: 3,
		},
		{
			f:      func(n *IntervalValue) bool { return true },
			wcount: 4,
		},
	}

	for i, tt := range tests {
		ivt := &IntervalTree{}
		for _, ivl := range ivls {
			ivt.Insert(ivl, struct{}{})
		}
		count := 0
		ivt.Visit(ivlRange, func(n *IntervalValue) bool {
			count++
			return tt.f(n)
		})
		if count != tt.wcount {
			t.Errorf("#%d: expected count %d, got %d", i, tt.wcount, count)
		}
	}
}