1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
|
// Copyright 2019 The Hugo Authors. All rights reserved.
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
// http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
package page
import "sort"
// Used in page binary search, the most common in front.
var pageLessFunctions = []func(p1, p2 Page) bool{
DefaultPageSort,
lessPageDate,
lessPagePubDate,
lessPageTitle,
lessPageLinkTitle,
}
func searchPage(p Page, pages Pages) int {
if len(pages) < 1000 {
// For smaller data sets, doing a linear search is faster.
return searchPageLinear(p, pages, 0)
}
less := isPagesProbablySorted(pages, pageLessFunctions...)
if less == nil {
return searchPageLinear(p, pages, 0)
}
i := searchPageBinary(p, pages, less)
if i != -1 {
return i
}
return searchPageLinear(p, pages, 0)
}
func searchPageLinear(p Page, pages Pages, start int) int {
for i := start; i < len(pages); i++ {
c := pages[i]
if c.Eq(p) {
return i
}
}
return -1
}
func searchPageBinary(p Page, pages Pages, less func(p1, p2 Page) bool) int {
n := len(pages)
f := func(i int) bool {
c := pages[i]
isLess := less(c, p)
return !isLess || c.Eq(p)
}
i := sort.Search(n, f)
if i == n {
return -1
}
return searchPageLinear(p, pages, i)
}
// isPagesProbablySorted tests if the pages slice is probably sorted.
func isPagesProbablySorted(pages Pages, lessFuncs ...func(p1, p2 Page) bool) func(p1, p2 Page) bool {
n := len(pages)
step := 1
if n > 500 {
step = 50
}
is := func(less func(p1, p2 Page) bool) bool {
samples := 0
for i := n - 1; i > 0; i = i - step {
if less(pages[i], pages[i-1]) {
return false
}
samples++
if samples >= 15 {
return true
}
}
return samples > 0
}
isReverse := func(less func(p1, p2 Page) bool) bool {
samples := 0
for i := 0; i < n-1; i = i + step {
if less(pages[i], pages[i+1]) {
return false
}
samples++
if samples > 15 {
return true
}
}
return samples > 0
}
for _, less := range lessFuncs {
if is(less) {
return less
}
if isReverse(less) {
return func(p1, p2 Page) bool {
return less(p2, p1)
}
}
}
return nil
}
|
