...

Source file src/cmd/compile/internal/abt/avlint32_test.go

Documentation: cmd/compile/internal/abt

     1  // Copyright 2022 The Go Authors. All rights reserved.
     2  // Use of this source code is governed by a BSD-style
     3  // license that can be found in the LICENSE file.
     4  
     5  package abt
     6  
     7  import (
     8  	"fmt"
     9  	"strconv"
    10  	"testing"
    11  )
    12  
    13  func makeTree(te *testing.T, x []int32, check bool) (t *T, k int, min, max int32) {
    14  	t = &T{}
    15  	k = 0
    16  	min = int32(0x7fffffff)
    17  	max = int32(-0x80000000)
    18  	history := []*T{}
    19  
    20  	for _, d := range x {
    21  		d = d + d // double everything for Glb/Lub testing.
    22  
    23  		if check {
    24  			history = append(history, t.Copy())
    25  		}
    26  
    27  		t.Insert(d, stringer(fmt.Sprintf("%v", d)))
    28  
    29  		k++
    30  		if d < min {
    31  			min = d
    32  		}
    33  		if d > max {
    34  			max = d
    35  		}
    36  
    37  		if !check {
    38  			continue
    39  		}
    40  
    41  		for j, old := range history {
    42  			s, i := old.wellFormed()
    43  			if s != "" {
    44  				te.Errorf("Old tree consistency problem %v at k=%d, j=%d, old=\n%v, t=\n%v", s, k, j, old.DebugString(), t.DebugString())
    45  				return
    46  			}
    47  			if i != j {
    48  				te.Errorf("Wrong tree size %v, expected %v for old %v", i, j, old.DebugString())
    49  			}
    50  		}
    51  		s, i := t.wellFormed()
    52  		if s != "" {
    53  			te.Errorf("Tree consistency problem at %v", s)
    54  			return
    55  		}
    56  		if i != k {
    57  			te.Errorf("Wrong tree size %v, expected %v for %v", i, k, t.DebugString())
    58  			return
    59  		}
    60  		if t.Size() != k {
    61  			te.Errorf("Wrong t.Size() %v, expected %v for %v", t.Size(), k, t.DebugString())
    62  			return
    63  		}
    64  	}
    65  	return
    66  }
    67  
    68  func applicInsert(te *testing.T, x []int32) {
    69  	makeTree(te, x, true)
    70  }
    71  
    72  func applicFind(te *testing.T, x []int32) {
    73  	t, _, _, _ := makeTree(te, x, false)
    74  
    75  	for _, d := range x {
    76  		d = d + d // double everything for Glb/Lub testing.
    77  		s := fmt.Sprintf("%v", d)
    78  		f := t.Find(d)
    79  
    80  		// data
    81  		if s != fmt.Sprint(f) {
    82  			te.Errorf("s(%v) != f(%v)", s, f)
    83  		}
    84  	}
    85  }
    86  
    87  func applicBounds(te *testing.T, x []int32) {
    88  	t, _, min, max := makeTree(te, x, false)
    89  	for _, d := range x {
    90  		d = d + d // double everything for Glb/Lub testing.
    91  		s := fmt.Sprintf("%v", d)
    92  
    93  		kg, g := t.Glb(d + 1)
    94  		kge, ge := t.GlbEq(d)
    95  		kl, l := t.Lub(d - 1)
    96  		kle, le := t.LubEq(d)
    97  
    98  		// keys
    99  		if d != kg {
   100  			te.Errorf("d(%v) != kg(%v)", d, kg)
   101  		}
   102  		if d != kl {
   103  			te.Errorf("d(%v) != kl(%v)", d, kl)
   104  		}
   105  		if d != kge {
   106  			te.Errorf("d(%v) != kge(%v)", d, kge)
   107  		}
   108  		if d != kle {
   109  			te.Errorf("d(%v) != kle(%v)", d, kle)
   110  		}
   111  		// data
   112  		if s != fmt.Sprint(g) {
   113  			te.Errorf("s(%v) != g(%v)", s, g)
   114  		}
   115  		if s != fmt.Sprint(l) {
   116  			te.Errorf("s(%v) != l(%v)", s, l)
   117  		}
   118  		if s != fmt.Sprint(ge) {
   119  			te.Errorf("s(%v) != ge(%v)", s, ge)
   120  		}
   121  		if s != fmt.Sprint(le) {
   122  			te.Errorf("s(%v) != le(%v)", s, le)
   123  		}
   124  	}
   125  
   126  	for _, d := range x {
   127  		d = d + d // double everything for Glb/Lub testing.
   128  		s := fmt.Sprintf("%v", d)
   129  		kge, ge := t.GlbEq(d + 1)
   130  		kle, le := t.LubEq(d - 1)
   131  		if d != kge {
   132  			te.Errorf("d(%v) != kge(%v)", d, kge)
   133  		}
   134  		if d != kle {
   135  			te.Errorf("d(%v) != kle(%v)", d, kle)
   136  		}
   137  		if s != fmt.Sprint(ge) {
   138  			te.Errorf("s(%v) != ge(%v)", s, ge)
   139  		}
   140  		if s != fmt.Sprint(le) {
   141  			te.Errorf("s(%v) != le(%v)", s, le)
   142  		}
   143  	}
   144  
   145  	kg, g := t.Glb(min)
   146  	kge, ge := t.GlbEq(min - 1)
   147  	kl, l := t.Lub(max)
   148  	kle, le := t.LubEq(max + 1)
   149  	fmin := t.Find(min - 1)
   150  	fmax := t.Find(max + 1)
   151  
   152  	if kg != NOT_KEY32 || kge != NOT_KEY32 || kl != NOT_KEY32 || kle != NOT_KEY32 {
   153  		te.Errorf("Got non-error-key for missing query")
   154  	}
   155  
   156  	if g != nil || ge != nil || l != nil || le != nil || fmin != nil || fmax != nil {
   157  		te.Errorf("Got non-error-data for missing query")
   158  	}
   159  }
   160  
   161  func applicDeleteMin(te *testing.T, x []int32) {
   162  	t, _, _, _ := makeTree(te, x, false)
   163  	_, size := t.wellFormed()
   164  	history := []*T{}
   165  	for !t.IsEmpty() {
   166  		k, _ := t.Min()
   167  		history = append(history, t.Copy())
   168  		kd, _ := t.DeleteMin()
   169  		if kd != k {
   170  			te.Errorf("Deleted minimum key %v not equal to minimum %v", kd, k)
   171  		}
   172  		for j, old := range history {
   173  			s, i := old.wellFormed()
   174  			if s != "" {
   175  				te.Errorf("Tree consistency problem %s at old after DeleteMin, old=\n%stree=\n%v", s, old.DebugString(), t.DebugString())
   176  				return
   177  			}
   178  			if i != len(x)-j {
   179  				te.Errorf("Wrong old tree size %v, expected %v after DeleteMin, old=\n%vtree\n%v", i, len(x)-j, old.DebugString(), t.DebugString())
   180  				return
   181  			}
   182  		}
   183  		size--
   184  		s, i := t.wellFormed()
   185  		if s != "" {
   186  			te.Errorf("Tree consistency problem at %v after DeleteMin, tree=\n%v", s, t.DebugString())
   187  			return
   188  		}
   189  		if i != size {
   190  			te.Errorf("Wrong tree size %v, expected %v after DeleteMin", i, size)
   191  			return
   192  		}
   193  		if t.Size() != size {
   194  			te.Errorf("Wrong t.Size() %v, expected %v for %v", t.Size(), i, t.DebugString())
   195  			return
   196  		}
   197  	}
   198  }
   199  
   200  func applicDeleteMax(te *testing.T, x []int32) {
   201  	t, _, _, _ := makeTree(te, x, false)
   202  	_, size := t.wellFormed()
   203  	history := []*T{}
   204  
   205  	for !t.IsEmpty() {
   206  		k, _ := t.Max()
   207  		history = append(history, t.Copy())
   208  		kd, _ := t.DeleteMax()
   209  		if kd != k {
   210  			te.Errorf("Deleted maximum key %v not equal to maximum %v", kd, k)
   211  		}
   212  
   213  		for j, old := range history {
   214  			s, i := old.wellFormed()
   215  			if s != "" {
   216  				te.Errorf("Tree consistency problem %s at old after DeleteMin, old=\n%stree=\n%v", s, old.DebugString(), t.DebugString())
   217  				return
   218  			}
   219  			if i != len(x)-j {
   220  				te.Errorf("Wrong old tree size %v, expected %v after DeleteMin, old=\n%vtree\n%v", i, len(x)-j, old.DebugString(), t.DebugString())
   221  				return
   222  			}
   223  		}
   224  
   225  		size--
   226  		s, i := t.wellFormed()
   227  		if s != "" {
   228  			te.Errorf("Tree consistency problem at %v after DeleteMax, tree=\n%v", s, t.DebugString())
   229  			return
   230  		}
   231  		if i != size {
   232  			te.Errorf("Wrong tree size %v, expected %v after DeleteMax", i, size)
   233  			return
   234  		}
   235  		if t.Size() != size {
   236  			te.Errorf("Wrong t.Size() %v, expected %v for %v", t.Size(), i, t.DebugString())
   237  			return
   238  		}
   239  	}
   240  }
   241  
   242  func applicDelete(te *testing.T, x []int32) {
   243  	t, _, _, _ := makeTree(te, x, false)
   244  	_, size := t.wellFormed()
   245  	history := []*T{}
   246  
   247  	missing := t.Delete(11)
   248  	if missing != nil {
   249  		te.Errorf("Returned a value when there should have been none, %v", missing)
   250  		return
   251  	}
   252  
   253  	s, i := t.wellFormed()
   254  	if s != "" {
   255  		te.Errorf("Tree consistency problem at %v after delete of missing value, tree=\n%v", s, t.DebugString())
   256  		return
   257  	}
   258  	if size != i {
   259  		te.Errorf("Delete of missing data should not change tree size, expected %d, got %d", size, i)
   260  		return
   261  	}
   262  
   263  	for _, d := range x {
   264  		d += d // double
   265  		vWant := fmt.Sprintf("%v", d)
   266  		history = append(history, t.Copy())
   267  		v := t.Delete(d)
   268  
   269  		for j, old := range history {
   270  			s, i := old.wellFormed()
   271  			if s != "" {
   272  				te.Errorf("Tree consistency problem %s at old after DeleteMin, old=\n%stree=\n%v", s, old.DebugString(), t.DebugString())
   273  				return
   274  			}
   275  			if i != len(x)-j {
   276  				te.Errorf("Wrong old tree size %v, expected %v after DeleteMin, old=\n%vtree\n%v", i, len(x)-j, old.DebugString(), t.DebugString())
   277  				return
   278  			}
   279  		}
   280  
   281  		if v.(*sstring).s != vWant {
   282  			te.Errorf("Deleted %v expected %v but got %v", d, vWant, v)
   283  			return
   284  		}
   285  		size--
   286  		s, i := t.wellFormed()
   287  		if s != "" {
   288  			te.Errorf("Tree consistency problem at %v after Delete %d, tree=\n%v", s, d, t.DebugString())
   289  			return
   290  		}
   291  		if i != size {
   292  			te.Errorf("Wrong tree size %v, expected %v after Delete", i, size)
   293  			return
   294  		}
   295  		if t.Size() != size {
   296  			te.Errorf("Wrong t.Size() %v, expected %v for %v", t.Size(), i, t.DebugString())
   297  			return
   298  		}
   299  	}
   300  
   301  }
   302  
   303  func applicIterator(te *testing.T, x []int32) {
   304  	t, _, _, _ := makeTree(te, x, false)
   305  	it := t.Iterator()
   306  	for !it.Done() {
   307  		k0, d0 := it.Next()
   308  		k1, d1 := t.DeleteMin()
   309  		if k0 != k1 || d0 != d1 {
   310  			te.Errorf("Iterator and deleteMin mismatch, k0, k1, d0, d1 = %v, %v, %v, %v", k0, k1, d0, d1)
   311  			return
   312  		}
   313  	}
   314  	if t.Size() != 0 {
   315  		te.Errorf("Iterator ended early, remaining tree = \n%s", t.DebugString())
   316  		return
   317  	}
   318  }
   319  
   320  func equiv(a, b interface{}) bool {
   321  	sa, sb := a.(*sstring), b.(*sstring)
   322  	return *sa == *sb
   323  }
   324  
   325  func applicEquals(te *testing.T, x, y []int32) {
   326  	t, _, _, _ := makeTree(te, x, false)
   327  	u, _, _, _ := makeTree(te, y, false)
   328  	if !t.Equiv(t, equiv) {
   329  		te.Errorf("Equiv failure, t == t, =\n%v", t.DebugString())
   330  		return
   331  	}
   332  	if !t.Equiv(t.Copy(), equiv) {
   333  		te.Errorf("Equiv failure, t == t.Copy(), =\n%v", t.DebugString())
   334  		return
   335  	}
   336  	if !t.Equiv(u, equiv) {
   337  		te.Errorf("Equiv failure, t == u, =\n%v", t.DebugString())
   338  		return
   339  	}
   340  	v := t.Copy()
   341  
   342  	v.DeleteMax()
   343  	if t.Equiv(v, equiv) {
   344  		te.Errorf("!Equiv failure, t != v, =\n%v\nand%v\n", t.DebugString(), v.DebugString())
   345  		return
   346  	}
   347  
   348  	if v.Equiv(u, equiv) {
   349  		te.Errorf("!Equiv failure, v != u, =\n%v\nand%v\n", v.DebugString(), u.DebugString())
   350  		return
   351  	}
   352  
   353  }
   354  
   355  func tree(x []int32) *T {
   356  	t := &T{}
   357  	for _, d := range x {
   358  		t.Insert(d, stringer(fmt.Sprintf("%v", d)))
   359  	}
   360  	return t
   361  }
   362  
   363  func treePlus1(x []int32) *T {
   364  	t := &T{}
   365  	for _, d := range x {
   366  		t.Insert(d, stringer(fmt.Sprintf("%v", d+1)))
   367  	}
   368  	return t
   369  }
   370  func TestApplicInsert(t *testing.T) {
   371  	applicInsert(t, []int32{24, 22, 20, 18, 16, 14, 12, 10, 8, 6, 4, 2, 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25})
   372  	applicInsert(t, []int32{1, 2, 3, 4})
   373  	applicInsert(t, []int32{1, 2, 3, 4, 5, 6, 7, 8, 9})
   374  	applicInsert(t, []int32{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25})
   375  	applicInsert(t, []int32{25, 24, 23, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1})
   376  	applicInsert(t, []int32{25, 24, 23, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1})
   377  	applicInsert(t, []int32{1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24})
   378  	applicInsert(t, []int32{1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 24, 22, 20, 18, 16, 14, 12, 10, 8, 6, 4, 2})
   379  }
   380  
   381  func TestApplicFind(t *testing.T) {
   382  	applicFind(t, []int32{24, 22, 20, 18, 16, 14, 12, 10, 8, 6, 4, 2, 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25})
   383  	applicFind(t, []int32{1, 2, 3, 4})
   384  	applicFind(t, []int32{1, 2, 3, 4, 5, 6, 7, 8, 9})
   385  	applicFind(t, []int32{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25})
   386  	applicFind(t, []int32{25, 24, 23, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1})
   387  	applicFind(t, []int32{25, 24, 23, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1})
   388  	applicFind(t, []int32{1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24})
   389  	applicFind(t, []int32{1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 24, 22, 20, 18, 16, 14, 12, 10, 8, 6, 4, 2})
   390  }
   391  
   392  func TestBounds(t *testing.T) {
   393  	applicBounds(t, []int32{24, 22, 20, 18, 16, 14, 12, 10, 8, 6, 4, 2, 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25})
   394  	applicBounds(t, []int32{1, 2, 3, 4})
   395  	applicBounds(t, []int32{1, 2, 3, 4, 5, 6, 7, 8, 9})
   396  	applicBounds(t, []int32{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25})
   397  	applicBounds(t, []int32{25, 24, 23, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1})
   398  	applicBounds(t, []int32{25, 24, 23, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1})
   399  	applicBounds(t, []int32{1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24})
   400  	applicBounds(t, []int32{1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 24, 22, 20, 18, 16, 14, 12, 10, 8, 6, 4, 2})
   401  }
   402  func TestDeleteMin(t *testing.T) {
   403  	applicDeleteMin(t, []int32{1, 2, 3, 4})
   404  	applicDeleteMin(t, []int32{24, 22, 20, 18, 16, 14, 12, 10, 8, 6, 4, 2, 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25})
   405  	applicDeleteMin(t, []int32{1, 2, 3, 4, 5, 6, 7, 8, 9})
   406  	applicDeleteMin(t, []int32{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25})
   407  	applicDeleteMin(t, []int32{25, 24, 23, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1})
   408  	applicDeleteMin(t, []int32{25, 24, 23, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1})
   409  	applicDeleteMin(t, []int32{1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24})
   410  	applicDeleteMin(t, []int32{1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 24, 22, 20, 18, 16, 14, 12, 10, 8, 6, 4, 2})
   411  }
   412  func TestDeleteMax(t *testing.T) {
   413  	applicDeleteMax(t, []int32{24, 22, 20, 18, 16, 14, 12, 10, 8, 6, 4, 2, 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25})
   414  	applicDeleteMax(t, []int32{1, 2, 3, 4})
   415  	applicDeleteMax(t, []int32{1, 2, 3, 4, 5, 6, 7, 8, 9})
   416  	applicDeleteMax(t, []int32{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25})
   417  	applicDeleteMax(t, []int32{25, 24, 23, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1})
   418  	applicDeleteMax(t, []int32{25, 24, 23, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1})
   419  	applicDeleteMax(t, []int32{1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24})
   420  	applicDeleteMax(t, []int32{1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 24, 22, 20, 18, 16, 14, 12, 10, 8, 6, 4, 2})
   421  }
   422  func TestDelete(t *testing.T) {
   423  	applicDelete(t, []int32{24, 22, 20, 18, 16, 14, 12, 10, 8, 6, 4, 2, 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25})
   424  	applicDelete(t, []int32{1, 2, 3, 4})
   425  	applicDelete(t, []int32{1, 2, 3, 4, 5, 6, 7, 8, 9})
   426  	applicDelete(t, []int32{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25})
   427  	applicDelete(t, []int32{25, 24, 23, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1})
   428  	applicDelete(t, []int32{25, 24, 23, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1})
   429  	applicDelete(t, []int32{1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24})
   430  	applicDelete(t, []int32{1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 24, 22, 20, 18, 16, 14, 12, 10, 8, 6, 4, 2})
   431  }
   432  func TestIterator(t *testing.T) {
   433  	applicIterator(t, []int32{1, 2, 3, 4})
   434  	applicIterator(t, []int32{1, 2, 3, 4, 5, 6, 7, 8, 9})
   435  	applicIterator(t, []int32{24, 22, 20, 18, 16, 14, 12, 10, 8, 6, 4, 2, 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25})
   436  	applicIterator(t, []int32{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25})
   437  	applicIterator(t, []int32{25, 24, 23, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1})
   438  	applicIterator(t, []int32{25, 24, 23, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1})
   439  	applicIterator(t, []int32{1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24})
   440  	applicIterator(t, []int32{1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 24, 22, 20, 18, 16, 14, 12, 10, 8, 6, 4, 2})
   441  }
   442  func TestEquals(t *testing.T) {
   443  	applicEquals(t, []int32{1, 2, 3, 4}, []int32{4, 3, 2, 1})
   444  
   445  	applicEquals(t, []int32{24, 22, 20, 18, 16, 14, 12, 10, 8, 6, 4, 2, 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25},
   446  		[]int32{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25})
   447  	applicEquals(t, []int32{25, 24, 23, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1},
   448  		[]int32{25, 24, 23, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1})
   449  	applicEquals(t, []int32{1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24},
   450  		[]int32{1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 24, 22, 20, 18, 16, 14, 12, 10, 8, 6, 4, 2})
   451  }
   452  
   453  func first(x, y interface{}) interface{} {
   454  	return x
   455  }
   456  func second(x, y interface{}) interface{} {
   457  	return y
   458  }
   459  func alwaysNil(x, y interface{}) interface{} {
   460  	return nil
   461  }
   462  func smaller(x, y interface{}) interface{} {
   463  	xi, _ := strconv.Atoi(fmt.Sprint(x))
   464  	yi, _ := strconv.Atoi(fmt.Sprint(y))
   465  	if xi < yi {
   466  		return x
   467  	}
   468  	return y
   469  }
   470  func assert(t *testing.T, expected, got *T, what string) {
   471  	s, _ := got.wellFormed()
   472  	if s != "" {
   473  		t.Errorf("Tree consistency problem %v for 'got' in assert for %s, tree=\n%v", s, what, got.DebugString())
   474  		return
   475  	}
   476  
   477  	if !expected.Equiv(got, equiv) {
   478  		t.Errorf("%s fail, expected\n%vgot\n%v\n", what, expected.DebugString(), got.DebugString())
   479  	}
   480  }
   481  
   482  func TestSetOps(t *testing.T) {
   483  	A := tree([]int32{1, 2, 3, 4})
   484  	B := tree([]int32{3, 4, 5, 6, 7})
   485  
   486  	AIB := tree([]int32{3, 4})
   487  	ADB := tree([]int32{1, 2})
   488  	BDA := tree([]int32{5, 6, 7})
   489  	AUB := tree([]int32{1, 2, 3, 4, 5, 6, 7})
   490  	AXB := tree([]int32{1, 2, 5, 6, 7})
   491  
   492  	aib1 := A.Intersection(B, first)
   493  	assert(t, AIB, aib1, "aib1")
   494  	if A.Find(3) != aib1.Find(3) {
   495  		t.Errorf("Failed aliasing/reuse check, A/aib1")
   496  	}
   497  	aib2 := A.Intersection(B, second)
   498  	assert(t, AIB, aib2, "aib2")
   499  	if B.Find(3) != aib2.Find(3) {
   500  		t.Errorf("Failed aliasing/reuse check, B/aib2")
   501  	}
   502  	aib3 := B.Intersection(A, first)
   503  	assert(t, AIB, aib3, "aib3")
   504  	if A.Find(3) != aib3.Find(3) {
   505  		// A is smaller, intersection favors reuse from smaller when function is "first"
   506  		t.Errorf("Failed aliasing/reuse check, A/aib3")
   507  	}
   508  	aib4 := B.Intersection(A, second)
   509  	assert(t, AIB, aib4, "aib4")
   510  	if A.Find(3) != aib4.Find(3) {
   511  		t.Errorf("Failed aliasing/reuse check, A/aib4")
   512  	}
   513  
   514  	aub1 := A.Union(B, first)
   515  	assert(t, AUB, aub1, "aub1")
   516  	if B.Find(3) != aub1.Find(3) {
   517  		// B is larger, union favors reuse from larger when function is "first"
   518  		t.Errorf("Failed aliasing/reuse check, A/aub1")
   519  	}
   520  	aub2 := A.Union(B, second)
   521  	assert(t, AUB, aub2, "aub2")
   522  	if B.Find(3) != aub2.Find(3) {
   523  		t.Errorf("Failed aliasing/reuse check, B/aub2")
   524  	}
   525  	aub3 := B.Union(A, first)
   526  	assert(t, AUB, aub3, "aub3")
   527  	if B.Find(3) != aub3.Find(3) {
   528  		t.Errorf("Failed aliasing/reuse check, B/aub3")
   529  	}
   530  	aub4 := B.Union(A, second)
   531  	assert(t, AUB, aub4, "aub4")
   532  	if A.Find(3) != aub4.Find(3) {
   533  		t.Errorf("Failed aliasing/reuse check, A/aub4")
   534  	}
   535  
   536  	axb1 := A.Union(B, alwaysNil)
   537  	assert(t, AXB, axb1, "axb1")
   538  	axb2 := B.Union(A, alwaysNil)
   539  	assert(t, AXB, axb2, "axb2")
   540  
   541  	adb := A.Difference(B, alwaysNil)
   542  	assert(t, ADB, adb, "adb")
   543  	bda := B.Difference(A, nil)
   544  	assert(t, BDA, bda, "bda")
   545  
   546  	Ap1 := treePlus1([]int32{1, 2, 3, 4})
   547  
   548  	ada1_1 := A.Difference(Ap1, smaller)
   549  	assert(t, A, ada1_1, "ada1_1")
   550  	ada1_2 := Ap1.Difference(A, smaller)
   551  	assert(t, A, ada1_2, "ada1_2")
   552  
   553  }
   554  
   555  type sstring struct {
   556  	s string
   557  }
   558  
   559  func (s *sstring) String() string {
   560  	return s.s
   561  }
   562  
   563  func stringer(s string) interface{} {
   564  	return &sstring{s}
   565  }
   566  
   567  // wellFormed ensures that a red-black tree meets
   568  // all of its invariants and returns a string identifying
   569  // the first problem encountered. If there is no problem
   570  // then the returned string is empty. The size is also
   571  // returned to allow comparison of calculated tree size
   572  // with expected.
   573  func (t *T) wellFormed() (s string, i int) {
   574  	if t.root == nil {
   575  		s = ""
   576  		i = 0
   577  		return
   578  	}
   579  	return t.root.wellFormedSubtree(nil, -0x80000000, 0x7fffffff)
   580  }
   581  
   582  // wellFormedSubtree ensures that a red-black subtree meets
   583  // all of its invariants and returns a string identifying
   584  // the first problem encountered. If there is no problem
   585  // then the returned string is empty. The size is also
   586  // returned to allow comparison of calculated tree size
   587  // with expected.
   588  func (t *node32) wellFormedSubtree(parent *node32, keyMin, keyMax int32) (s string, i int) {
   589  	i = -1 // initialize to a failing value
   590  	s = "" // s is the reason for failure; empty means okay.
   591  
   592  	if keyMin >= t.key {
   593  		s = " min >= t.key"
   594  		return
   595  	}
   596  
   597  	if keyMax <= t.key {
   598  		s = " max <= t.key"
   599  		return
   600  	}
   601  
   602  	l := t.left
   603  	r := t.right
   604  
   605  	lh := l.height()
   606  	rh := r.height()
   607  	mh := max(lh, rh)
   608  	th := t.height()
   609  	dh := lh - rh
   610  	if dh < 0 {
   611  		dh = -dh
   612  	}
   613  	if dh > 1 {
   614  		s = fmt.Sprintf(" dh > 1, t=%d", t.key)
   615  		return
   616  	}
   617  
   618  	if l == nil && r == nil {
   619  		if th != LEAF_HEIGHT {
   620  			s = " leaf height wrong"
   621  			return
   622  		}
   623  	}
   624  
   625  	if th != mh+1 {
   626  		s = " th != mh + 1"
   627  		return
   628  	}
   629  
   630  	if l != nil {
   631  		if th <= lh {
   632  			s = " t.height <= l.height"
   633  		} else if th > 2+lh {
   634  			s = " t.height > 2+l.height"
   635  		} else if t.key <= l.key {
   636  			s = " t.key <= l.key"
   637  		}
   638  		if s != "" {
   639  			return
   640  		}
   641  
   642  	}
   643  
   644  	if r != nil {
   645  		if th <= rh {
   646  			s = " t.height <= r.height"
   647  		} else if th > 2+rh {
   648  			s = " t.height > 2+r.height"
   649  		} else if t.key >= r.key {
   650  			s = " t.key >= r.key"
   651  		}
   652  		if s != "" {
   653  			return
   654  		}
   655  	}
   656  
   657  	ii := 1
   658  	if l != nil {
   659  		res, il := l.wellFormedSubtree(t, keyMin, t.key)
   660  		if res != "" {
   661  			s = ".L" + res
   662  			return
   663  		}
   664  		ii += il
   665  	}
   666  	if r != nil {
   667  		res, ir := r.wellFormedSubtree(t, t.key, keyMax)
   668  		if res != "" {
   669  			s = ".R" + res
   670  			return
   671  		}
   672  		ii += ir
   673  	}
   674  	i = ii
   675  	return
   676  }
   677  
   678  func (t *T) DebugString() string {
   679  	if t.root == nil {
   680  		return ""
   681  	}
   682  	return t.root.DebugString(0)
   683  }
   684  
   685  // DebugString prints the tree with nested information
   686  // to allow an eyeball check on the tree balance.
   687  func (t *node32) DebugString(indent int) string {
   688  	s := ""
   689  	if t.left != nil {
   690  		s = s + t.left.DebugString(indent+1)
   691  	}
   692  	for i := 0; i < indent; i++ {
   693  		s = s + "    "
   694  	}
   695  	s = s + fmt.Sprintf("%v=%v:%d\n", t.key, t.data, t.height_)
   696  	if t.right != nil {
   697  		s = s + t.right.DebugString(indent+1)
   698  	}
   699  	return s
   700  }
   701  

View as plain text