vendor/golang.org/x/text/collate/build/order_test.go

   1 // Copyright 2012 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 build
   6
   7 import (
   8         "strconv"
   9         "testing"
  10
  11         "golang.org/x/text/internal/colltab"
  12 )
  13
  14 type entryTest struct {
  15         f   func(in []int) (uint32, error)
  16         arg []int
  17         val uint32
  18 }
  19
  20 // makeList returns a list of entries of length n+2, with n normal
  21 // entries plus a leading and trailing anchor.
  22 func makeList(n int) []*entry {
  23         es := make([]*entry, n+2)
  24         weights := []rawCE{{w: []int{100, 20, 5, 0}}}
  25         for i := range es {
  26                 runes := []rune{rune(i)}
  27                 es[i] = &entry{
  28                         runes: runes,
  29                         elems: weights,
  30                 }
  31                 weights = nextWeight(colltab.Primary, weights)
  32         }
  33         for i := 1; i < len(es); i++ {
  34                 es[i-1].next = es[i]
  35                 es[i].prev = es[i-1]
  36                 _, es[i-1].level = compareWeights(es[i-1].elems, es[i].elems)
  37         }
  38         es[0].exclude = true
  39         es[0].logical = firstAnchor
  40         es[len(es)-1].exclude = true
  41         es[len(es)-1].logical = lastAnchor
  42         return es
  43 }
  44
  45 func TestNextIndexed(t *testing.T) {
  46         const n = 5
  47         es := makeList(n)
  48         for i := int64(0); i < 1<<n; i++ {
  49                 mask := strconv.FormatInt(i+(1<<n), 2)
  50                 for i, c := range mask {
  51                         es[i].exclude = c == '1'
  52                 }
  53                 e := es[0]
  54                 for i, c := range mask {
  55                         if c == '0' {
  56                                 e, _ = e.nextIndexed()
  57                                 if e != es[i] {
  58                                         t.Errorf("%d: expected entry %d; found %d", i, es[i].elems, e.elems)
  59                                 }
  60                         }
  61                 }
  62                 if e, _ = e.nextIndexed(); e != nil {
  63                         t.Errorf("%d: expected nil entry; found %d", i, e.elems)
  64                 }
  65         }
  66 }
  67
  68 func TestRemove(t *testing.T) {
  69         const n = 5
  70         for i := int64(0); i < 1<<n; i++ {
  71                 es := makeList(n)
  72                 mask := strconv.FormatInt(i+(1<<n), 2)
  73                 for i, c := range mask {
  74                         if c == '0' {
  75                                 es[i].remove()
  76                         }
  77                 }
  78                 e := es[0]
  79                 for i, c := range mask {
  80                         if c == '1' {
  81                                 if e != es[i] {
  82                                         t.Errorf("%d: expected entry %d; found %d", i, es[i].elems, e.elems)
  83                                 }
  84                                 e, _ = e.nextIndexed()
  85                         }
  86                 }
  87                 if e != nil {
  88                         t.Errorf("%d: expected nil entry; found %d", i, e.elems)
  89                 }
  90         }
  91 }
  92
  93 // nextPerm generates the next permutation of the array.  The starting
  94 // permutation is assumed to be a list of integers sorted in increasing order.
  95 // It returns false if there are no more permuations left.
  96 func nextPerm(a []int) bool {
  97         i := len(a) - 2
  98         for ; i >= 0; i-- {
  99                 if a[i] < a[i+1] {
 100                         break
 101                 }
 102         }
 103         if i < 0 {
 104                 return false
 105         }
 106         for j := len(a) - 1; j >= i; j-- {
 107                 if a[j] > a[i] {
 108                         a[i], a[j] = a[j], a[i]
 109                         break
 110                 }
 111         }
 112         for j := i + 1; j < (len(a)+i+1)/2; j++ {
 113                 a[j], a[len(a)+i-j] = a[len(a)+i-j], a[j]
 114         }
 115         return true
 116 }
 117
 118 func TestInsertAfter(t *testing.T) {
 119         const n = 5
 120         orig := makeList(n)
 121         perm := make([]int, n)
 122         for i := range perm {
 123                 perm[i] = i + 1
 124         }
 125         for ok := true; ok; ok = nextPerm(perm) {
 126                 es := makeList(n)
 127                 last := es[0]
 128                 for _, i := range perm {
 129                         last.insertAfter(es[i])
 130                         last = es[i]
 131                 }
 132                 for _, e := range es {
 133                         e.elems = es[0].elems
 134                 }
 135                 e := es[0]
 136                 for _, i := range perm {
 137                         e, _ = e.nextIndexed()
 138                         if e.runes[0] != orig[i].runes[0] {
 139                                 t.Errorf("%d:%d: expected entry %X; found %X", perm, i, orig[i].runes, e.runes)
 140                                 break
 141                         }
 142                 }
 143         }
 144 }
 145
 146 func TestInsertBefore(t *testing.T) {
 147         const n = 5
 148         orig := makeList(n)
 149         perm := make([]int, n)
 150         for i := range perm {
 151                 perm[i] = i + 1
 152         }
 153         for ok := true; ok; ok = nextPerm(perm) {
 154                 es := makeList(n)
 155                 last := es[len(es)-1]
 156                 for _, i := range perm {
 157                         last.insertBefore(es[i])
 158                         last = es[i]
 159                 }
 160                 for _, e := range es {
 161                         e.elems = es[0].elems
 162                 }
 163                 e := es[0]
 164                 for i := n - 1; i >= 0; i-- {
 165                         e, _ = e.nextIndexed()
 166                         if e.runes[0] != rune(perm[i]) {
 167                                 t.Errorf("%d:%d: expected entry %X; found %X", perm, i, orig[i].runes, e.runes)
 168                                 break
 169                         }
 170                 }
 171         }
 172 }
 173
 174 type entryLessTest struct {
 175         a, b *entry
 176         res  bool
 177 }
 178
 179 var (
 180         w1 = []rawCE{{w: []int{100, 20, 5, 5}}}
 181         w2 = []rawCE{{w: []int{101, 20, 5, 5}}}
 182 )
 183
 184 var entryLessTests = []entryLessTest{
 185         {&entry{str: "a", elems: w1},
 186                 &entry{str: "a", elems: w1},
 187                 false,
 188         },
 189         {&entry{str: "a", elems: w1},
 190                 &entry{str: "a", elems: w2},
 191                 true,
 192         },
 193         {&entry{str: "a", elems: w1},
 194                 &entry{str: "b", elems: w1},
 195                 true,
 196         },
 197         {&entry{str: "a", elems: w2},
 198                 &entry{str: "a", elems: w1},
 199                 false,
 200         },
 201         {&entry{str: "c", elems: w1},
 202                 &entry{str: "b", elems: w1},
 203                 false,
 204         },
 205         {&entry{str: "a", elems: w1, logical: firstAnchor},
 206                 &entry{str: "a", elems: w1},
 207                 true,
 208         },
 209         {&entry{str: "a", elems: w1},
 210                 &entry{str: "b", elems: w1, logical: firstAnchor},
 211                 false,
 212         },
 213         {&entry{str: "b", elems: w1},
 214                 &entry{str: "a", elems: w1, logical: lastAnchor},
 215                 true,
 216         },
 217         {&entry{str: "a", elems: w1, logical: lastAnchor},
 218                 &entry{str: "c", elems: w1},
 219                 false,
 220         },
 221 }
 222
 223 func TestEntryLess(t *testing.T) {
 224         for i, tt := range entryLessTests {
 225                 if res := entryLess(tt.a, tt.b); res != tt.res {
 226                         t.Errorf("%d: was %v; want %v", i, res, tt.res)
 227                 }
 228         }
 229 }