pages_sort_search_test.go (3579B)
1 // Copyright 2019 The Hugo Authors. All rights reserved.
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 // http://www.apache.org/licenses/LICENSE-2.0
7 //
8 // Unless required by applicable law or agreed to in writing, software
9 // distributed under the License is distributed on an "AS IS" BASIS,
10 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
11 // See the License for the specific language governing permissions and
12 // limitations under the License.
13
14 package page
15
16 import (
17 "fmt"
18 "math/rand"
19 "testing"
20 "time"
21
22 qt "github.com/frankban/quicktest"
23 )
24
25 func TestSearchPage(t *testing.T) {
26 t.Parallel()
27 c := qt.New(t)
28 pages := createSortTestPages(10)
29 for i, p := range pages {
30 p.(*testPage).title = fmt.Sprintf("Title %d", i%2)
31 }
32
33 for _, pages := range []Pages{pages.ByTitle(), pages.ByTitle().Reverse()} {
34 less := isPagesProbablySorted(pages, lessPageTitle)
35 c.Assert(less, qt.Not(qt.IsNil))
36 for i, p := range pages {
37 idx := searchPageBinary(p, pages, less)
38 c.Assert(idx, qt.Equals, i)
39 }
40 }
41 }
42
43 func BenchmarkSearchPage(b *testing.B) {
44 type Variant struct {
45 name string
46 preparePages func(pages Pages) Pages
47 search func(p Page, pages Pages) int
48 }
49
50 shufflePages := func(pages Pages) Pages {
51 rand.Shuffle(len(pages), func(i, j int) { pages[i], pages[j] = pages[j], pages[i] })
52 return pages
53 }
54
55 linearSearch := func(p Page, pages Pages) int {
56 return searchPageLinear(p, pages, 0)
57 }
58
59 createPages := func(num int) Pages {
60 pages := createSortTestPages(num)
61 for _, p := range pages {
62 tp := p.(*testPage)
63 tp.weight = rand.Intn(len(pages))
64 tp.title = fmt.Sprintf("Title %d", rand.Intn(len(pages)))
65
66 tp.pubDate = time.Now().Add(time.Duration(rand.Intn(len(pages)/5)) * time.Hour)
67 tp.date = time.Now().Add(time.Duration(rand.Intn(len(pages)/5)) * time.Hour)
68 }
69
70 return pages
71 }
72
73 for _, variant := range []Variant{
74 {"Shuffled", shufflePages, searchPage},
75 {"ByWeight", func(pages Pages) Pages {
76 return pages.ByWeight()
77 }, searchPage},
78 {"ByWeight.Reverse", func(pages Pages) Pages {
79 return pages.ByWeight().Reverse()
80 }, searchPage},
81 {"ByDate", func(pages Pages) Pages {
82 return pages.ByDate()
83 }, searchPage},
84 {"ByPublishDate", func(pages Pages) Pages {
85 return pages.ByPublishDate()
86 }, searchPage},
87 {"ByTitle", func(pages Pages) Pages {
88 return pages.ByTitle()
89 }, searchPage},
90 {"ByTitle Linear", func(pages Pages) Pages {
91 return pages.ByTitle()
92 }, linearSearch},
93 } {
94 for _, numPages := range []int{100, 500, 1000, 5000} {
95 b.Run(fmt.Sprintf("%s-%d", variant.name, numPages), func(b *testing.B) {
96 b.StopTimer()
97 pages := createPages(numPages)
98 if variant.preparePages != nil {
99 pages = variant.preparePages(pages)
100 }
101 b.StartTimer()
102 for i := 0; i < b.N; i++ {
103 j := rand.Intn(numPages)
104 k := variant.search(pages[j], pages)
105 if k != j {
106 b.Fatalf("%d != %d", k, j)
107 }
108 }
109 })
110 }
111 }
112 }
113
114 func TestIsPagesProbablySorted(t *testing.T) {
115 t.Parallel()
116 c := qt.New(t)
117
118 c.Assert(isPagesProbablySorted(createSortTestPages(6).ByWeight(), DefaultPageSort), qt.Not(qt.IsNil))
119 c.Assert(isPagesProbablySorted(createSortTestPages(300).ByWeight(), DefaultPageSort), qt.Not(qt.IsNil))
120 c.Assert(isPagesProbablySorted(createSortTestPages(6), DefaultPageSort), qt.IsNil)
121 c.Assert(isPagesProbablySorted(createSortTestPages(300).ByTitle(), pageLessFunctions...), qt.Not(qt.IsNil))
122 }