interval_tree_test.go

Documentation: go.etcd.io/etcd/pkg/v3/adt

     1  // Copyright 2016 The etcd Authors
     2  //
     3  // Licensed under the Apache License, Version 2.0 (the "License");
     4  // you may not use this file except in compliance with the License.
     5  // You may obtain a copy of the License at
     6  //
     7  //     http://www.apache.org/licenses/LICENSE-2.0
     8  //
     9  // Unless required by applicable law or agreed to in writing, software
    10  // distributed under the License is distributed on an "AS IS" BASIS,
    11  // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    12  // See the License for the specific language governing permissions and
    13  // limitations under the License.
    14  
    15  package adt
    16  
    17  import (
    18  	"math/rand"
    19  	"reflect"
    20  	"testing"
    21  	"time"
    22  )
    23  
    24  // TestIntervalTreeInsert tests interval tree insertion.
    25  func TestIntervalTreeInsert(t *testing.T) {
    26  	// "Introduction to Algorithms" (Cormen et al, 3rd ed.) chapter 14, Figure 14.4
    27  	ivt := NewIntervalTree()
    28  	ivt.Insert(NewInt64Interval(16, 21), 30)
    29  	ivt.Insert(NewInt64Interval(8, 9), 23)
    30  	ivt.Insert(NewInt64Interval(0, 3), 3)
    31  	ivt.Insert(NewInt64Interval(5, 8), 10)
    32  	ivt.Insert(NewInt64Interval(6, 10), 10)
    33  	ivt.Insert(NewInt64Interval(15, 23), 23)
    34  	ivt.Insert(NewInt64Interval(17, 19), 20)
    35  	ivt.Insert(NewInt64Interval(25, 30), 30)
    36  	ivt.Insert(NewInt64Interval(26, 26), 26)
    37  	ivt.Insert(NewInt64Interval(19, 20), 20)
    38  
    39  	expected := []visitedInterval{
    40  		{root: NewInt64Interval(16, 21), color: black, left: NewInt64Interval(8, 9), right: NewInt64Interval(25, 30), depth: 0},
    41  
    42  		{root: NewInt64Interval(8, 9), color: red, left: NewInt64Interval(5, 8), right: NewInt64Interval(15, 23), depth: 1},
    43  		{root: NewInt64Interval(25, 30), color: red, left: NewInt64Interval(17, 19), right: NewInt64Interval(26, 26), depth: 1},
    44  
    45  		{root: NewInt64Interval(5, 8), color: black, left: NewInt64Interval(0, 3), right: NewInt64Interval(6, 10), depth: 2},
    46  		{root: NewInt64Interval(15, 23), color: black, left: newInt64EmptyInterval(), right: newInt64EmptyInterval(), depth: 2},
    47  		{root: NewInt64Interval(17, 19), color: black, left: newInt64EmptyInterval(), right: NewInt64Interval(19, 20), depth: 2},
    48  		{root: NewInt64Interval(26, 26), color: black, left: newInt64EmptyInterval(), right: newInt64EmptyInterval(), depth: 2},
    49  
    50  		{root: NewInt64Interval(0, 3), color: red, left: newInt64EmptyInterval(), right: newInt64EmptyInterval(), depth: 3},
    51  		{root: NewInt64Interval(6, 10), color: red, left: newInt64EmptyInterval(), right: newInt64EmptyInterval(), depth: 3},
    52  		{root: NewInt64Interval(19, 20), color: red, left: newInt64EmptyInterval(), right: newInt64EmptyInterval(), depth: 3},
    53  	}
    54  
    55  	tr := ivt.(*intervalTree)
    56  	visits := tr.visitLevel()
    57  	if !reflect.DeepEqual(expected, visits) {
    58  		t.Fatalf("level order expected %v, got %v", expected, visits)
    59  	}
    60  }
    61  
    62  // TestIntervalTreeSelfBalanced ensures range tree is self-balanced after inserting ranges to the tree.
    63  // Use https://www.cs.usfca.edu/~galles/visualization/RedBlack.html for test case creation.
    64  //
    65  // Regular Binary Search Tree
    66  //
    67  //	[0,1]
    68  //	    \
    69  //	    [1,2]
    70  //	       \
    71  //	      [3,4]
    72  //	         \
    73  //	        [5,6]
    74  //	            \
    75  //	           [7,8]
    76  //	              \
    77  //	             [8,9]
    78  //
    79  // Self-Balancing Binary Search Tree
    80  //
    81  //	       [1,2]
    82  //	     /       \
    83  //	[0,1]        [5,6]
    84  //	              /   \
    85  //	         [3,4]    [7,8]
    86  //	                      \
    87  //	                      [8,9]
    88  func TestIntervalTreeSelfBalanced(t *testing.T) {
    89  	ivt := NewIntervalTree()
    90  	ivt.Insert(NewInt64Interval(0, 1), 0)
    91  	ivt.Insert(NewInt64Interval(1, 2), 0)
    92  	ivt.Insert(NewInt64Interval(3, 4), 0)
    93  	ivt.Insert(NewInt64Interval(5, 6), 0)
    94  	ivt.Insert(NewInt64Interval(7, 8), 0)
    95  	ivt.Insert(NewInt64Interval(8, 9), 0)
    96  
    97  	expected := []visitedInterval{
    98  		{root: NewInt64Interval(1, 2), color: black, left: NewInt64Interval(0, 1), right: NewInt64Interval(5, 6), depth: 0},
    99  
   100  		{root: NewInt64Interval(0, 1), color: black, left: newInt64EmptyInterval(), right: newInt64EmptyInterval(), depth: 1},
   101  		{root: NewInt64Interval(5, 6), color: red, left: NewInt64Interval(3, 4), right: NewInt64Interval(7, 8), depth: 1},
   102  
   103  		{root: NewInt64Interval(3, 4), color: black, left: newInt64EmptyInterval(), right: newInt64EmptyInterval(), depth: 2},
   104  		{root: NewInt64Interval(7, 8), color: black, left: newInt64EmptyInterval(), right: NewInt64Interval(8, 9), depth: 2},
   105  
   106  		{root: NewInt64Interval(8, 9), color: red, left: newInt64EmptyInterval(), right: newInt64EmptyInterval(), depth: 3},
   107  	}
   108  
   109  	tr := ivt.(*intervalTree)
   110  	visits := tr.visitLevel()
   111  	if !reflect.DeepEqual(expected, visits) {
   112  		t.Fatalf("level order expected %v, got %v", expected, visits)
   113  	}
   114  
   115  	if visits[len(visits)-1].depth != 3 {
   116  		t.Fatalf("expected self-balanced tree with last level 3, but last level got %d", visits[len(visits)-1].depth)
   117  	}
   118  }
   119  
   120  // TestIntervalTreeDelete ensures delete operation maintains red-black tree properties.
   121  // Use https://www.cs.usfca.edu/~galles/visualization/RedBlack.html for test case creation.
   122  // See https://github.com/etcd-io/etcd/issues/10877 for more detail.
   123  //
   124  // After insertion:
   125  //
   126  //	                       [510,511]
   127  //	                        /      \
   128  //	              ----------        -----------------------
   129  //	             /                                          \
   130  //	         [82,83]                                      [830,831]
   131  //	         /    \                                    /            \
   132  //	        /      \                                  /               \
   133  //	  [11,12]    [383,384](red)               [647,648]              [899,900](red)
   134  //	               /   \                      /      \                      /    \
   135  //	              /     \                    /        \                    /      \
   136  //	        [261,262]  [410,411]  [514,515](red)  [815,816](red)  [888,889]      [972,973]
   137  //	        /       \                                                           /
   138  //	       /         \                                                         /
   139  //	[238,239](red)  [292,293](red)                                    [953,954](red)
   140  //
   141  // After deleting 514 (no rebalance):
   142  //
   143  //	                       [510,511]
   144  //	                        /      \
   145  //	              ----------        -----------------------
   146  //	             /                                          \
   147  //	         [82,83]                                      [830,831]
   148  //	         /    \                                    /            \
   149  //	        /      \                                  /               \
   150  //	  [11,12]    [383,384](red)               [647,648]              [899,900](red)
   151  //	               /   \                            \                      /    \
   152  //	              /     \                            \                    /      \
   153  //	        [261,262]  [410,411]                  [815,816](red)  [888,889]      [972,973]
   154  //	        /       \                                                           /
   155  //	       /         \                                                         /
   156  //	[238,239](red)  [292,293](red)                                    [953,954](red)
   157  //
   158  // After deleting 11 (requires rebalancing):
   159  //
   160  //	                      [510,511]
   161  //	                       /      \
   162  //	             ----------        --------------------------
   163  //	            /                                            \
   164  //	        [383,384]                                       [830,831]
   165  //	        /       \                                      /          \
   166  //	       /         \                                    /            \
   167  //	[261,262](red)  [410,411]                     [647,648]           [899,900](red)
   168  //	    /               \                              \                      /    \
   169  //	   /                 \                              \                    /      \
   170  //	[82,83]           [292,293]                      [815,816](red)   [888,889]    [972,973]
   171  //	      \                                                           /
   172  //	       \                                                         /
   173  //	    [238,239](red)                                       [953,954](red)
   174  func TestIntervalTreeDelete(t *testing.T) {
   175  	ivt := NewIntervalTree()
   176  	ivt.Insert(NewInt64Interval(510, 511), 0)
   177  	ivt.Insert(NewInt64Interval(82, 83), 0)
   178  	ivt.Insert(NewInt64Interval(830, 831), 0)
   179  	ivt.Insert(NewInt64Interval(11, 12), 0)
   180  	ivt.Insert(NewInt64Interval(383, 384), 0)
   181  	ivt.Insert(NewInt64Interval(647, 648), 0)
   182  	ivt.Insert(NewInt64Interval(899, 900), 0)
   183  	ivt.Insert(NewInt64Interval(261, 262), 0)
   184  	ivt.Insert(NewInt64Interval(410, 411), 0)
   185  	ivt.Insert(NewInt64Interval(514, 515), 0)
   186  	ivt.Insert(NewInt64Interval(815, 816), 0)
   187  	ivt.Insert(NewInt64Interval(888, 889), 0)
   188  	ivt.Insert(NewInt64Interval(972, 973), 0)
   189  	ivt.Insert(NewInt64Interval(238, 239), 0)
   190  	ivt.Insert(NewInt64Interval(292, 293), 0)
   191  	ivt.Insert(NewInt64Interval(953, 954), 0)
   192  
   193  	tr := ivt.(*intervalTree)
   194  
   195  	expectedBeforeDelete := []visitedInterval{
   196  		{root: NewInt64Interval(510, 511), color: black, left: NewInt64Interval(82, 83), right: NewInt64Interval(830, 831), depth: 0},
   197  
   198  		{root: NewInt64Interval(82, 83), color: black, left: NewInt64Interval(11, 12), right: NewInt64Interval(383, 384), depth: 1},
   199  		{root: NewInt64Interval(830, 831), color: black, left: NewInt64Interval(647, 648), right: NewInt64Interval(899, 900), depth: 1},
   200  
   201  		{root: NewInt64Interval(11, 12), color: black, left: newInt64EmptyInterval(), right: newInt64EmptyInterval(), depth: 2},
   202  		{root: NewInt64Interval(383, 384), color: red, left: NewInt64Interval(261, 262), right: NewInt64Interval(410, 411), depth: 2},
   203  		{root: NewInt64Interval(647, 648), color: black, left: NewInt64Interval(514, 515), right: NewInt64Interval(815, 816), depth: 2},
   204  		{root: NewInt64Interval(899, 900), color: red, left: NewInt64Interval(888, 889), right: NewInt64Interval(972, 973), depth: 2},
   205  
   206  		{root: NewInt64Interval(261, 262), color: black, left: NewInt64Interval(238, 239), right: NewInt64Interval(292, 293), depth: 3},
   207  		{root: NewInt64Interval(410, 411), color: black, left: newInt64EmptyInterval(), right: newInt64EmptyInterval(), depth: 3},
   208  		{root: NewInt64Interval(514, 515), color: red, left: newInt64EmptyInterval(), right: newInt64EmptyInterval(), depth: 3},
   209  		{root: NewInt64Interval(815, 816), color: red, left: newInt64EmptyInterval(), right: newInt64EmptyInterval(), depth: 3},
   210  		{root: NewInt64Interval(888, 889), color: black, left: newInt64EmptyInterval(), right: newInt64EmptyInterval(), depth: 3},
   211  		{root: NewInt64Interval(972, 973), color: black, left: NewInt64Interval(953, 954), right: newInt64EmptyInterval(), depth: 3},
   212  
   213  		{root: NewInt64Interval(238, 239), color: red, left: newInt64EmptyInterval(), right: newInt64EmptyInterval(), depth: 4},
   214  		{root: NewInt64Interval(292, 293), color: red, left: newInt64EmptyInterval(), right: newInt64EmptyInterval(), depth: 4},
   215  		{root: NewInt64Interval(953, 954), color: red, left: newInt64EmptyInterval(), right: newInt64EmptyInterval(), depth: 4},
   216  	}
   217  	visitsBeforeDelete := tr.visitLevel()
   218  	if !reflect.DeepEqual(expectedBeforeDelete, visitsBeforeDelete) {
   219  		t.Fatalf("level order after insertion expected %v, got %v", expectedBeforeDelete, visitsBeforeDelete)
   220  	}
   221  
   222  	// delete the node "514"
   223  	range514 := NewInt64Interval(514, 515)
   224  	if deleted := tr.Delete(NewInt64Interval(514, 515)); !deleted {
   225  		t.Fatalf("range %v not deleted", range514)
   226  	}
   227  
   228  	expectedAfterDelete514 := []visitedInterval{
   229  		{root: NewInt64Interval(510, 511), color: black, left: NewInt64Interval(82, 83), right: NewInt64Interval(830, 831), depth: 0},
   230  
   231  		{root: NewInt64Interval(82, 83), color: black, left: NewInt64Interval(11, 12), right: NewInt64Interval(383, 384), depth: 1},
   232  		{root: NewInt64Interval(830, 831), color: black, left: NewInt64Interval(647, 648), right: NewInt64Interval(899, 900), depth: 1},
   233  
   234  		{root: NewInt64Interval(11, 12), color: black, left: newInt64EmptyInterval(), right: newInt64EmptyInterval(), depth: 2},
   235  		{root: NewInt64Interval(383, 384), color: red, left: NewInt64Interval(261, 262), right: NewInt64Interval(410, 411), depth: 2},
   236  		{root: NewInt64Interval(647, 648), color: black, left: newInt64EmptyInterval(), right: NewInt64Interval(815, 816), depth: 2},
   237  		{root: NewInt64Interval(899, 900), color: red, left: NewInt64Interval(888, 889), right: NewInt64Interval(972, 973), depth: 2},
   238  
   239  		{root: NewInt64Interval(261, 262), color: black, left: NewInt64Interval(238, 239), right: NewInt64Interval(292, 293), depth: 3},
   240  		{root: NewInt64Interval(410, 411), color: black, left: newInt64EmptyInterval(), right: newInt64EmptyInterval(), depth: 3},
   241  		{root: NewInt64Interval(815, 816), color: red, left: newInt64EmptyInterval(), right: newInt64EmptyInterval(), depth: 3},
   242  		{root: NewInt64Interval(888, 889), color: black, left: newInt64EmptyInterval(), right: newInt64EmptyInterval(), depth: 3},
   243  		{root: NewInt64Interval(972, 973), color: black, left: NewInt64Interval(953, 954), right: newInt64EmptyInterval(), depth: 3},
   244  
   245  		{root: NewInt64Interval(238, 239), color: red, left: newInt64EmptyInterval(), right: newInt64EmptyInterval(), depth: 4},
   246  		{root: NewInt64Interval(292, 293), color: red, left: newInt64EmptyInterval(), right: newInt64EmptyInterval(), depth: 4},
   247  		{root: NewInt64Interval(953, 954), color: red, left: newInt64EmptyInterval(), right: newInt64EmptyInterval(), depth: 4},
   248  	}
   249  	visitsAfterDelete514 := tr.visitLevel()
   250  	if !reflect.DeepEqual(expectedAfterDelete514, visitsAfterDelete514) {
   251  		t.Fatalf("level order after deleting '514' expected %v, got %v", expectedAfterDelete514, visitsAfterDelete514)
   252  	}
   253  
   254  	// delete the node "11"
   255  	range11 := NewInt64Interval(11, 12)
   256  	if deleted := tr.Delete(NewInt64Interval(11, 12)); !deleted {
   257  		t.Fatalf("range %v not deleted", range11)
   258  	}
   259  
   260  	expectedAfterDelete11 := []visitedInterval{
   261  		{root: NewInt64Interval(510, 511), color: black, left: NewInt64Interval(383, 384), right: NewInt64Interval(830, 831), depth: 0},
   262  
   263  		{root: NewInt64Interval(383, 384), color: black, left: NewInt64Interval(261, 262), right: NewInt64Interval(410, 411), depth: 1},
   264  		{root: NewInt64Interval(830, 831), color: black, left: NewInt64Interval(647, 648), right: NewInt64Interval(899, 900), depth: 1},
   265  
   266  		{root: NewInt64Interval(261, 262), color: red, left: NewInt64Interval(82, 83), right: NewInt64Interval(292, 293), depth: 2},
   267  		{root: NewInt64Interval(410, 411), color: black, left: newInt64EmptyInterval(), right: newInt64EmptyInterval(), depth: 2},
   268  		{root: NewInt64Interval(647, 648), color: black, left: newInt64EmptyInterval(), right: NewInt64Interval(815, 816), depth: 2},
   269  		{root: NewInt64Interval(899, 900), color: red, left: NewInt64Interval(888, 889), right: NewInt64Interval(972, 973), depth: 2},
   270  
   271  		{root: NewInt64Interval(82, 83), color: black, left: newInt64EmptyInterval(), right: NewInt64Interval(238, 239), depth: 3},
   272  		{root: NewInt64Interval(292, 293), color: black, left: newInt64EmptyInterval(), right: newInt64EmptyInterval(), depth: 3},
   273  		{root: NewInt64Interval(815, 816), color: red, left: newInt64EmptyInterval(), right: newInt64EmptyInterval(), depth: 3},
   274  		{root: NewInt64Interval(888, 889), color: black, left: newInt64EmptyInterval(), right: newInt64EmptyInterval(), depth: 3},
   275  		{root: NewInt64Interval(972, 973), color: black, left: NewInt64Interval(953, 954), right: newInt64EmptyInterval(), depth: 3},
   276  
   277  		{root: NewInt64Interval(238, 239), color: red, left: newInt64EmptyInterval(), right: newInt64EmptyInterval(), depth: 4},
   278  		{root: NewInt64Interval(953, 954), color: red, left: newInt64EmptyInterval(), right: newInt64EmptyInterval(), depth: 4},
   279  	}
   280  	visitsAfterDelete11 := tr.visitLevel()
   281  	if !reflect.DeepEqual(expectedAfterDelete11, visitsAfterDelete11) {
   282  		t.Fatalf("level order after deleting '11' expected %v, got %v", expectedAfterDelete11, visitsAfterDelete11)
   283  	}
   284  }
   285  
   286  func TestIntervalTreeIntersects(t *testing.T) {
   287  	ivt := NewIntervalTree()
   288  	ivt.Insert(NewStringInterval("1", "3"), 123)
   289  
   290  	if ivt.Intersects(NewStringPoint("0")) {
   291  		t.Errorf("contains 0")
   292  	}
   293  	if !ivt.Intersects(NewStringPoint("1")) {
   294  		t.Errorf("missing 1")
   295  	}
   296  	if !ivt.Intersects(NewStringPoint("11")) {
   297  		t.Errorf("missing 11")
   298  	}
   299  	if !ivt.Intersects(NewStringPoint("2")) {
   300  		t.Errorf("missing 2")
   301  	}
   302  	if ivt.Intersects(NewStringPoint("3")) {
   303  		t.Errorf("contains 3")
   304  	}
   305  }
   306  
   307  func TestIntervalTreeStringAffine(t *testing.T) {
   308  	ivt := NewIntervalTree()
   309  	ivt.Insert(NewStringAffineInterval("8", ""), 123)
   310  	if !ivt.Intersects(NewStringAffinePoint("9")) {
   311  		t.Errorf("missing 9")
   312  	}
   313  	if ivt.Intersects(NewStringAffinePoint("7")) {
   314  		t.Errorf("contains 7")
   315  	}
   316  }
   317  
   318  func TestIntervalTreeStab(t *testing.T) {
   319  	ivt := NewIntervalTree()
   320  	ivt.Insert(NewStringInterval("0", "1"), 123)
   321  	ivt.Insert(NewStringInterval("0", "2"), 456)
   322  	ivt.Insert(NewStringInterval("5", "6"), 789)
   323  	ivt.Insert(NewStringInterval("6", "8"), 999)
   324  	ivt.Insert(NewStringInterval("0", "3"), 0)
   325  
   326  	tr := ivt.(*intervalTree)
   327  	if tr.root.max.Compare(StringComparable("8")) != 0 {
   328  		t.Fatalf("wrong root max got %v, expected 8", tr.root.max)
   329  	}
   330  	if x := len(ivt.Stab(NewStringPoint("0"))); x != 3 {
   331  		t.Errorf("got %d, expected 3", x)
   332  	}
   333  	if x := len(ivt.Stab(NewStringPoint("1"))); x != 2 {
   334  		t.Errorf("got %d, expected 2", x)
   335  	}
   336  	if x := len(ivt.Stab(NewStringPoint("2"))); x != 1 {
   337  		t.Errorf("got %d, expected 1", x)
   338  	}
   339  	if x := len(ivt.Stab(NewStringPoint("3"))); x != 0 {
   340  		t.Errorf("got %d, expected 0", x)
   341  	}
   342  	if x := len(ivt.Stab(NewStringPoint("5"))); x != 1 {
   343  		t.Errorf("got %d, expected 1", x)
   344  	}
   345  	if x := len(ivt.Stab(NewStringPoint("55"))); x != 1 {
   346  		t.Errorf("got %d, expected 1", x)
   347  	}
   348  	if x := len(ivt.Stab(NewStringPoint("6"))); x != 1 {
   349  		t.Errorf("got %d, expected 1", x)
   350  	}
   351  }
   352  
   353  type xy struct {
   354  	x int64
   355  	y int64
   356  }
   357  
   358  func TestIntervalTreeRandom(t *testing.T) {
   359  	// generate unique intervals
   360  	ivs := make(map[xy]struct{})
   361  	ivt := NewIntervalTree()
   362  	maxv := 128
   363  	rand.Seed(time.Now().UnixNano())
   364  
   365  	for i := rand.Intn(maxv) + 1; i != 0; i-- {
   366  		x, y := int64(rand.Intn(maxv)), int64(rand.Intn(maxv))
   367  		if x > y {
   368  			t := x
   369  			x = y
   370  			y = t
   371  		} else if x == y {
   372  			y++
   373  		}
   374  		iv := xy{x, y}
   375  		if _, ok := ivs[iv]; ok {
   376  			// don't double insert
   377  			continue
   378  		}
   379  		ivt.Insert(NewInt64Interval(x, y), 123)
   380  		ivs[iv] = struct{}{}
   381  	}
   382  
   383  	for ab := range ivs {
   384  		for xy := range ivs {
   385  			v := xy.x + int64(rand.Intn(int(xy.y-xy.x)))
   386  			if slen := len(ivt.Stab(NewInt64Point(v))); slen == 0 {
   387  				t.Fatalf("expected %v stab non-zero for [%+v)", v, xy)
   388  			}
   389  			if !ivt.Intersects(NewInt64Point(v)) {
   390  				t.Fatalf("did not get %d as expected for [%+v)", v, xy)
   391  			}
   392  		}
   393  		if !ivt.Delete(NewInt64Interval(ab.x, ab.y)) {
   394  			t.Errorf("did not delete %v as expected", ab)
   395  		}
   396  		delete(ivs, ab)
   397  	}
   398  
   399  	if ivt.Len() != 0 {
   400  		t.Errorf("got ivt.Len() = %v, expected 0", ivt.Len())
   401  	}
   402  }
   403  
   404  // TestIntervalTreeSortedVisit tests that intervals are visited in sorted order.
   405  func TestIntervalTreeSortedVisit(t *testing.T) {
   406  	tests := []struct {
   407  		ivls       []Interval
   408  		visitRange Interval
   409  	}{
   410  		{
   411  			ivls:       []Interval{NewInt64Interval(1, 10), NewInt64Interval(2, 5), NewInt64Interval(3, 6)},
   412  			visitRange: NewInt64Interval(0, 100),
   413  		},
   414  		{
   415  			ivls:       []Interval{NewInt64Interval(1, 10), NewInt64Interval(10, 12), NewInt64Interval(3, 6)},
   416  			visitRange: NewInt64Interval(0, 100),
   417  		},
   418  		{
   419  			ivls:       []Interval{NewInt64Interval(2, 3), NewInt64Interval(3, 4), NewInt64Interval(6, 7), NewInt64Interval(5, 6)},
   420  			visitRange: NewInt64Interval(0, 100),
   421  		},
   422  		{
   423  			ivls: []Interval{
   424  				NewInt64Interval(2, 3),
   425  				NewInt64Interval(2, 4),
   426  				NewInt64Interval(3, 7),
   427  				NewInt64Interval(2, 5),
   428  				NewInt64Interval(3, 8),
   429  				NewInt64Interval(3, 5),
   430  			},
   431  			visitRange: NewInt64Interval(0, 100),
   432  		},
   433  	}
   434  	for i, tt := range tests {
   435  		ivt := NewIntervalTree()
   436  		for _, ivl := range tt.ivls {
   437  			ivt.Insert(ivl, struct{}{})
   438  		}
   439  		last := tt.ivls[0].Begin
   440  		count := 0
   441  		chk := func(iv *IntervalValue) bool {
   442  			if last.Compare(iv.Ivl.Begin) > 0 {
   443  				t.Errorf("#%d: expected less than %d, got interval %+v", i, last, iv.Ivl)
   444  			}
   445  			last = iv.Ivl.Begin
   446  			count++
   447  			return true
   448  		}
   449  		ivt.Visit(tt.visitRange, chk)
   450  		if count != len(tt.ivls) {
   451  			t.Errorf("#%d: did not cover all intervals. expected %d, got %d", i, len(tt.ivls), count)
   452  		}
   453  	}
   454  }
   455  
   456  // TestIntervalTreeVisitExit tests that visiting can be stopped.
   457  func TestIntervalTreeVisitExit(t *testing.T) {
   458  	ivls := []Interval{NewInt64Interval(1, 10), NewInt64Interval(2, 5), NewInt64Interval(3, 6), NewInt64Interval(4, 8)}
   459  	ivlRange := NewInt64Interval(0, 100)
   460  	tests := []struct {
   461  		f IntervalVisitor
   462  
   463  		wcount int
   464  	}{
   465  		{
   466  			f:      func(n *IntervalValue) bool { return false },
   467  			wcount: 1,
   468  		},
   469  		{
   470  			f:      func(n *IntervalValue) bool { return n.Ivl.Begin.Compare(ivls[0].Begin) <= 0 },
   471  			wcount: 2,
   472  		},
   473  		{
   474  			f:      func(n *IntervalValue) bool { return n.Ivl.Begin.Compare(ivls[2].Begin) < 0 },
   475  			wcount: 3,
   476  		},
   477  		{
   478  			f:      func(n *IntervalValue) bool { return true },
   479  			wcount: 4,
   480  		},
   481  	}
   482  
   483  	for i, tt := range tests {
   484  		ivt := NewIntervalTree()
   485  		for _, ivl := range ivls {
   486  			ivt.Insert(ivl, struct{}{})
   487  		}
   488  		count := 0
   489  		ivt.Visit(ivlRange, func(n *IntervalValue) bool {
   490  			count++
   491  			return tt.f(n)
   492  		})
   493  		if count != tt.wcount {
   494  			t.Errorf("#%d: expected count %d, got %d", i, tt.wcount, count)
   495  		}
   496  	}
   497  }
   498  
   499  // TestIntervalTreeContains tests that contains returns true iff the ivt maps the entire interval.
   500  func TestIntervalTreeContains(t *testing.T) {
   501  	tests := []struct {
   502  		ivls   []Interval
   503  		chkIvl Interval
   504  
   505  		wContains bool
   506  	}{
   507  		{
   508  			ivls:   []Interval{NewInt64Interval(1, 10)},
   509  			chkIvl: NewInt64Interval(0, 100),
   510  
   511  			wContains: false,
   512  		},
   513  		{
   514  			ivls:   []Interval{NewInt64Interval(1, 10)},
   515  			chkIvl: NewInt64Interval(1, 10),
   516  
   517  			wContains: true,
   518  		},
   519  		{
   520  			ivls:   []Interval{NewInt64Interval(1, 10)},
   521  			chkIvl: NewInt64Interval(2, 8),
   522  
   523  			wContains: true,
   524  		},
   525  		{
   526  			ivls:   []Interval{NewInt64Interval(1, 5), NewInt64Interval(6, 10)},
   527  			chkIvl: NewInt64Interval(1, 10),
   528  
   529  			wContains: false,
   530  		},
   531  		{
   532  			ivls:   []Interval{NewInt64Interval(1, 5), NewInt64Interval(3, 10)},
   533  			chkIvl: NewInt64Interval(1, 10),
   534  
   535  			wContains: true,
   536  		},
   537  		{
   538  			ivls:   []Interval{NewInt64Interval(1, 4), NewInt64Interval(4, 7), NewInt64Interval(3, 10)},
   539  			chkIvl: NewInt64Interval(1, 10),
   540  
   541  			wContains: true,
   542  		},
   543  		{
   544  			ivls:   []Interval{},
   545  			chkIvl: NewInt64Interval(1, 10),
   546  
   547  			wContains: false,
   548  		},
   549  	}
   550  	for i, tt := range tests {
   551  		ivt := NewIntervalTree()
   552  		for _, ivl := range tt.ivls {
   553  			ivt.Insert(ivl, struct{}{})
   554  		}
   555  		if v := ivt.Contains(tt.chkIvl); v != tt.wContains {
   556  			t.Errorf("#%d: ivt.Contains got %v, expected %v", i, v, tt.wContains)
   557  		}
   558  	}
   559  }
   560
View as plain text