collate/build/order_test.go

// Copyright 2012 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

package build

import (
	"strconv"
	"testing"

	"golang.org/x/text/collate/colltab"
)

type entryTest struct {
	f   func(in []int) (uint32, error)
	arg []int
	val uint32
}

// makeList returns a list of entries of length n+2, with n normal
// entries plus a leading and trailing anchor.
func makeList(n int) []*entry {
	es := make([]*entry, n+2)
	weights := []rawCE{{w: []int{100, 20, 5, 0}}}
	for i := range es {
		runes := []rune{rune(i)}
		es[i] = &entry{
			runes: runes,
			elems: weights,
		}
		weights = nextWeight(colltab.Primary, weights)
	}
	for i := 1; i < len(es); i++ {
		es[i-1].next = es[i]
		es[i].prev = es[i-1]
		_, es[i-1].level = compareWeights(es[i-1].elems, es[i].elems)
	}
	es[0].exclude = true
	es[0].logical = firstAnchor
	es[len(es)-1].exclude = true
	es[len(es)-1].logical = lastAnchor
	return es
}

func TestNextIndexed(t *testing.T) {
	const n = 5
	es := makeList(n)
	for i := int64(0); i < 1<<n; i++ {
		mask := strconv.FormatInt(i+(1<<n), 2)
		for i, c := range mask {
			es[i].exclude = c == '1'
		}
		e := es[0]
		for i, c := range mask {
			if c == '0' {
				e, _ = e.nextIndexed()
				if e != es[i] {
					t.Errorf("%d: expected entry %d; found %d", i, es[i].elems, e.elems)
				}
			}
		}
		if e, _ = e.nextIndexed(); e != nil {
			t.Errorf("%d: expected nil entry; found %d", i, e.elems)
		}
	}
}

func TestRemove(t *testing.T) {
	const n = 5
	for i := int64(0); i < 1<<n; i++ {
		es := makeList(n)
		mask := strconv.FormatInt(i+(1<<n), 2)
		for i, c := range mask {
			if c == '0' {
				es[i].remove()
			}
		}
		e := es[0]
		for i, c := range mask {
			if c == '1' {
				if e != es[i] {
					t.Errorf("%d: expected entry %d; found %d", i, es[i].elems, e.elems)
				}
				e, _ = e.nextIndexed()
			}
		}
		if e != nil {
			t.Errorf("%d: expected nil entry; found %d", i, e.elems)
		}
	}
}

// nextPerm generates the next permutation of the array.  The starting
// permutation is assumed to be a list of integers sorted in increasing order.
// It returns false if there are no more permuations left.
func nextPerm(a []int) bool {
	i := len(a) - 2
	for ; i >= 0; i-- {
		if a[i] < a[i+1] {
			break
		}
	}
	if i < 0 {
		return false
	}
	for j := len(a) - 1; j >= i; j-- {
		if a[j] > a[i] {
			a[i], a[j] = a[j], a[i]
			break
		}
	}
	for j := i + 1; j < (len(a)+i+1)/2; j++ {
		a[j], a[len(a)+i-j] = a[len(a)+i-j], a[j]
	}
	return true
}

func TestInsertAfter(t *testing.T) {
	const n = 5
	orig := makeList(n)
	perm := make([]int, n)
	for i := range perm {
		perm[i] = i + 1
	}
	for ok := true; ok; ok = nextPerm(perm) {
		es := makeList(n)
		last := es[0]
		for _, i := range perm {
			last.insertAfter(es[i])
			last = es[i]
		}
		for _, e := range es {
			e.elems = es[0].elems
		}
		e := es[0]
		for _, i := range perm {
			e, _ = e.nextIndexed()
			if e.runes[0] != orig[i].runes[0] {
				t.Errorf("%d:%d: expected entry %X; found %X", perm, i, orig[i].runes, e.runes)
				break
			}
		}
	}
}

func TestInsertBefore(t *testing.T) {
	const n = 5
	orig := makeList(n)
	perm := make([]int, n)
	for i := range perm {
		perm[i] = i + 1
	}
	for ok := true; ok; ok = nextPerm(perm) {
		es := makeList(n)
		last := es[len(es)-1]
		for _, i := range perm {
			last.insertBefore(es[i])
			last = es[i]
		}
		for _, e := range es {
			e.elems = es[0].elems
		}
		e := es[0]
		for i := n - 1; i >= 0; i-- {
			e, _ = e.nextIndexed()
			if e.runes[0] != rune(perm[i]) {
				t.Errorf("%d:%d: expected entry %X; found %X", perm, i, orig[i].runes, e.runes)
				break
			}
		}
	}
}

type entryLessTest struct {
	a, b *entry
	res  bool
}

var (
	w1 = []rawCE{{w: []int{100, 20, 5, 5}}}
	w2 = []rawCE{{w: []int{101, 20, 5, 5}}}
)

var entryLessTests = []entryLessTest{
	{&entry{str: "a", elems: w1},
		&entry{str: "a", elems: w1},
		false,
	},
	{&entry{str: "a", elems: w1},
		&entry{str: "a", elems: w2},
		true,
	},
	{&entry{str: "a", elems: w1},
		&entry{str: "b", elems: w1},
		true,
	},
	{&entry{str: "a", elems: w2},
		&entry{str: "a", elems: w1},
		false,
	},
	{&entry{str: "c", elems: w1},
		&entry{str: "b", elems: w1},
		false,
	},
	{&entry{str: "a", elems: w1, logical: firstAnchor},
		&entry{str: "a", elems: w1},
		true,
	},
	{&entry{str: "a", elems: w1},
		&entry{str: "b", elems: w1, logical: firstAnchor},
		false,
	},
	{&entry{str: "b", elems: w1},
		&entry{str: "a", elems: w1, logical: lastAnchor},
		true,
	},
	{&entry{str: "a", elems: w1, logical: lastAnchor},
		&entry{str: "c", elems: w1},
		false,
	},
}

func TestEntryLess(t *testing.T) {
	for i, tt := range entryLessTests {
		if res := entryLess(tt.a, tt.b); res != tt.res {
			t.Errorf("%d: was %v; want %v", i, res, tt.res)
		}
	}
}