pages_sort_search.go (2586B)
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 "sort"
17
18 // Used in page binary search, the most common in front.
19 var pageLessFunctions = []func(p1, p2 Page) bool{
20 DefaultPageSort,
21 lessPageDate,
22 lessPagePubDate,
23 lessPageTitle,
24 lessPageLinkTitle,
25 }
26
27 func searchPage(p Page, pages Pages) int {
28 if len(pages) < 1000 {
29 // For smaller data sets, doing a linear search is faster.
30 return searchPageLinear(p, pages, 0)
31 }
32
33 less := isPagesProbablySorted(pages, pageLessFunctions...)
34 if less == nil {
35 return searchPageLinear(p, pages, 0)
36 }
37
38 i := searchPageBinary(p, pages, less)
39 if i != -1 {
40 return i
41 }
42
43 return searchPageLinear(p, pages, 0)
44 }
45
46 func searchPageLinear(p Page, pages Pages, start int) int {
47 for i := start; i < len(pages); i++ {
48 c := pages[i]
49 if c.Eq(p) {
50 return i
51 }
52 }
53 return -1
54 }
55
56 func searchPageBinary(p Page, pages Pages, less func(p1, p2 Page) bool) int {
57 n := len(pages)
58
59 f := func(i int) bool {
60 c := pages[i]
61 isLess := less(c, p)
62 return !isLess || c.Eq(p)
63 }
64
65 i := sort.Search(n, f)
66
67 if i == n {
68 return -1
69 }
70
71 return searchPageLinear(p, pages, i)
72 }
73
74 // isProbablySorted tests if the pages slice is probably sorted.
75 func isPagesProbablySorted(pages Pages, lessFuncs ...func(p1, p2 Page) bool) func(p1, p2 Page) bool {
76 n := len(pages)
77 step := 1
78 if n > 500 {
79 step = 50
80 }
81
82 is := func(less func(p1, p2 Page) bool) bool {
83 samples := 0
84
85 for i := n - 1; i > 0; i = i - step {
86 if less(pages[i], pages[i-1]) {
87 return false
88 }
89 samples++
90 if samples >= 15 {
91 return true
92 }
93 }
94 return samples > 0
95 }
96
97 isReverse := func(less func(p1, p2 Page) bool) bool {
98 samples := 0
99
100 for i := 0; i < n-1; i = i + step {
101 if less(pages[i], pages[i+1]) {
102 return false
103 }
104 samples++
105
106 if samples > 15 {
107 return true
108 }
109 }
110 return samples > 0
111 }
112
113 for _, less := range lessFuncs {
114 if is(less) {
115 return less
116 }
117 if isReverse(less) {
118 return func(p1, p2 Page) bool {
119 return less(p2, p1)
120 }
121 }
122 }
123
124 return nil
125 }