lib/waveletmatrix/waveletmatrix_test.go

• View this file on GitHub
• Last update: 2023-08-09 15:23:16+09:00

Depends on

• lib/template/main.go
• lib/waveletmatrix/examples/range_kth_smallest.test.go
• lib/waveletmatrix/examples/static_range_frequency.test.go
• lib/waveletmatrix/waveletmatrix.go

Required by

• lib/template/main.go
• lib/waveletmatrix/waveletmatrix.go

Verified with

• lib/waveletmatrix/examples/range_kth_smallest.test.go
• lib/waveletmatrix/examples/static_range_frequency.test.go

Code

package main

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

func TestNewWaveletMatrix(t *testing.T) {
	testCases := [][]int{
		{},
		{1, 1, 1, 1},
		{1, 2, 3, 4, 5},
		{5, 4, 3, 2, 1},
	}

	for _, testCase := range testCases {
		_ = NewWaveletMatrix(testCase)
	}
}

func TestAccess(t *testing.T) {
	data := []int{1, 2, 3, 4, 5}
	wm := NewWaveletMatrix(data)

	for i, v := range data {
		if wm.Access(i) != v {
			t.Errorf("Access(%d) returned %d, expected %d", i, wm.Access(i), v)
		}
	}
}

func TestSelect(t *testing.T) {
	data := []int{1, 2, 2, 3, 3, 3}
	wm := NewWaveletMatrix(data)

	for i := 1; i <= 3; i++ {
		for j := 1; j <= i; j++ {
			pos, ok := wm.Select(i, j)
			if !ok || data[pos] != i {
				t.Errorf("Select(%d, %d) returned %d, expected %d", i, j, pos, (i-1)*i+j-1)
			}
		}
	}

	_, ok := wm.Select(4, 1)
	if ok {
		t.Error("Select(4, 1) should return false")
	}
}

func TestRank(t *testing.T) {
	data := []int{1, 2, 1, 2, 1, 2}
	wm := NewWaveletMatrix(data)

	type query struct {
		n, idx, want int
	}

	queries := []query{
		{1, 0, 1},
		{1, 1, 1},
		{1, 2, 2},
		{1, 3, 2},
		{2, 0, 0},
		{2, 1, 1},
		{2, 2, 1},
		{2, 3, 2},
		{2, 4, 2},
		{2, 5, 3},
	}

	for _, q := range queries {
		got := wm.Rank(q.n, q.idx)
		if got != q.want {
			t.Errorf("Rank(%d, %d) returned %d, expected %d", q.n, q.idx, got, q.want)
		}
	}
}

func TestWaveletMatrix_KthSmall(t *testing.T) {
	data := []int{1, 2, 2, 3, 3, 3}
	wm := NewWaveletMatrix(data)

	quantiles := []int{1, 2, 2, 3, 3, 3}
	for i, q := range quantiles {
		if wm.KthSmall(0, 5, i+1) != q {
			t.Errorf("Quantile(0, 5, %d) returned %d, expected %d", i+1, wm.KthSmall(0, 5, i+1), q)
		}
	}
}
func TestWaveletMatrix_KthLarge(t *testing.T) {
	data := []int{1, 2, 2, 3, 3, 3}
	wm := NewWaveletMatrix(data)

	quantiles2 := []int{3, 3, 3, 2, 2, 1}
	for i, q := range quantiles2 {
		if wm.KthLarge(0, 5, i+1) != q {
			t.Errorf("Quantile2(0, 5, %d) returned %d, expected %d", i+1, wm.KthLarge(0, 5, i+1), q)
		}
	}
}

func TestWaveletMatrixRandomData(t *testing.T) {
	data := make([]int, 1000)
	for i := range data {
		data[i] = rand.Intn(1000)
	}

	wm := NewWaveletMatrix(data)
	sortedData := make([]int, 1000)
	copy(sortedData, data)
	sort.Ints(sortedData)

	for i := 0; i < 1000; i++ {
		q := wm.KthSmall(0, 999, i+1)
		if q != sortedData[i] {
			t.Errorf("Quantile(0, 999, %d) returned %d, expected %d", i+1, q, sortedData[i])
		}

		q2 := wm.KthLarge(0, 999, i+1)
		if q2 != sortedData[999-i] {
			t.Errorf("Quantile2(0, 999, %d) returned %d, expected %d", i+1, q2, sortedData[999-i])
		}
	}
}
func TestFreq(t *testing.T) {
	data := []int{0, 1, 2, 3, 2, 2, 1}
	wm := NewWaveletMatrix(data)

	tests := []struct {
		l, r, x int
		want    int
	}{
		{l: 0, r: 6, x: 2, want: 3},
		{l: 1, r: 6, x: 2, want: 3},
		{l: 2, r: 6, x: 2, want: 3},
		{l: 3, r: 6, x: 2, want: 2},
		{l: 0, r: 6, x: 0, want: 1},
		{l: 0, r: 6, x: 1, want: 2},
		{l: 0, r: 6, x: 3, want: 1},
		{l: 4, r: 4, x: 5, want: 0},
	}

	for _, test := range tests {
		result := wm.Freq(test.l, test.r, test.x)
		if result != test.want {
			t.Errorf("Freq(%d, %d, %d) = %d; want %d", test.l, test.r, test.x, result, test.want)
		}
	}
}
func TestRangeFreq(t *testing.T) {
	data := []int{0, 1, 2, 3, 2, 2, 1}
	wm := NewWaveletMatrix(data)

	tests := []struct {
		l, r, low, high int
		want            int
	}{
		{l: 0, r: 6, low: 2, high: 2, want: 3},
		{l: 1, r: 6, low: 2, high: 2, want: 3},
		{l: 2, r: 6, low: 2, high: 2, want: 3},
		{l: 3, r: 6, low: 2, high: 2, want: 2},
		{l: 0, r: 6, low: 0, high: 0, want: 1},
		{l: 0, r: 6, low: 1, high: 1, want: 2},
		{l: 0, r: 6, low: 3, high: 3, want: 1},
		{l: 4, r: 4, low: 5, high: 5, want: 0},
	}

	for _, test := range tests {
		result := wm.RangeFreq(test.l, test.r, test.low, test.high)
		if result != test.want {
			t.Errorf("RangeFreq(%d, %d, %d, %d) = %d; want %d", test.l, test.r, test.low, test.high, result, test.want)
		}
	}
}

Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.11.4/x64/lib/python3.11/site-packages/onlinejudge_verify/documentation/build.py", line 71, in _render_source_code_stat
    bundled_code = language.bundle(stat.path, basedir=basedir, options={'include_paths': [basedir]}).decode()
                   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.11.4/x64/lib/python3.11/site-packages/onlinejudge_verify/languages/user_defined.py", line 68, in bundle
    raise RuntimeError('bundler is not specified: {}'.format(str(path)))
RuntimeError: bundler is not specified: lib/waveletmatrix/waveletmatrix_test.go

Back to top page