summaryrefslogtreecommitdiff
path: root/indexing/zhmakeindex/sorter.go
blob: 3109186a61fb627eb46d7b1066287d3d823d0583 (plain)
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
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
package main

import (
	"log"
	"sort"
	"strconv"
	"unicode"
	"unicode/utf8"
)

// 对应不同的分类排序方式
type IndexCollator interface {
	// 初始化分组
	InitGroups(style *OutputStyle) []IndexGroup
	// 给索引项分组
	Group(entry *IndexEntry) int
	// 单个字符比较
	RuneCmp(a, b rune) int
	// 判断是否字母或汉字
	IsLetter(r rune) bool
}

// 排序器
type IndexSorter struct {
	IndexCollator
}

func NewIndexSorter(method string) *IndexSorter {
	switch method {
	case "bihua", "stroke":
		return &IndexSorter{
			IndexCollator: StrokeIndexCollator{},
		}
	case "pinyin", "reading":
		return &IndexSorter{
			IndexCollator: ReadingIndexCollator{},
		}
	case "bushou", "radical":
		return &IndexSorter{
			IndexCollator: RadicalIndexCollator{},
		}
	default:
		log.Fatalln("未知排序方式")
	}
	return nil
}

func (sorter *IndexSorter) SortIndex(input *InputIndex, style *OutputStyle, option *OutputOptions) *OutputIndex {
	out := new(OutputIndex)
	// 分组
	out.groups = sorter.InitGroups(style)

	// 先整体排序
	sort.Sort(IndexEntrySlice{
		entries:  *input,
		colattor: sorter.IndexCollator,
	})

	// 再依次对页码排序,并分组添加
	pagesorter := NewPageSorter(style, option)
	for _, entry := range *input {
		pageranges := pagesorter.Sort(entry)
		pageranges = pagesorter.Merge(pageranges)
		item := IndexItem{
			level: len(entry.level) - 1,
			text:  entry.level[len(entry.level)-1].text,
			page:  pageranges,
		}
		group := sorter.Group(&entry)
		out.groups[group].items = append(out.groups[group].items, item)
	}

	return out
}

type IndexEntrySlice struct {
	entries  []IndexEntry
	colattor IndexCollator
}

func (s IndexEntrySlice) Len() int {
	return len(s.entries)
}

func (s IndexEntrySlice) Swap(i, j int) {
	s.entries[i], s.entries[j] = s.entries[j], s.entries[i]
}

// 比较两个串的大小
func (s IndexEntrySlice) Strcmp(a, b string) int {
	atype, btype := getStringType(s.colattor, a), getStringType(s.colattor, b)
	if atype < btype {
		return -1
	} else if atype > btype {
		return 1
	}
	// 特例:尝试按纯数字比较
	if cmp := DecimalStrcmp(a, b); cmp != 0 {
		return cmp
	}
	// 忽略大小写,按字典序比较
	a_rune, b_rune := []rune(a), []rune(b)
	for i := range a_rune {
		if i >= len(b_rune) {
			return 1
		}
		cmp := s.colattor.RuneCmp(a_rune[i], b_rune[i])
		if cmp != 0 {
			return cmp
		}
	}
	if len(a_rune) < len(b_rune) {
		return -1
	}
	// 不忽略大小写重新比较串,此时不必使用 colattor 特有的比较
	if a < b {
		return -1
	} else if a > b {
		return 1
	} else {
		return 0
	}
}

// 串类型
type stringType int

// 用于比较的串类型,有前后次序
const (
	EMPTY_STR      stringType = iota // 空串
	SYMBOL_STR                       // 符号开头
	NUM_SYMBOL_STR                   // 数字开头
	NUM_STR                          // 纯数字
	LETTER_STR                       // 字母或汉字
)

// 取得串类型
func getStringType(collator IndexCollator, s string) stringType {
	if len(s) == 0 {
		return EMPTY_STR
	}
	r, _ := utf8.DecodeRuneInString(s)
	switch {
	case IsNumRune(r):
		if IsNumString(s) {
			return NUM_STR
		} else {
			return NUM_SYMBOL_STR
		}
	case collator.IsLetter(r):
		return LETTER_STR
	default:
		return SYMBOL_STR
	}
}

func (s IndexEntrySlice) Less(i, j int) bool {
	a, b := s.entries[i], s.entries[j]
	for i := range a.level {
		if i >= len(b.level) {
			return false
		}
		keycmp := s.Strcmp(a.level[i].key, b.level[i].key)
		if keycmp < 0 {
			return true
		} else if keycmp > 0 {
			return false
		}
		textcmp := s.Strcmp(a.level[i].text, b.level[i].text)
		if textcmp < 0 {
			return true
		} else if textcmp > 0 {
			return false
		}
	}
	if len(a.level) < len(b.level) {
		return true
	}
	return false
}

// 页码排序器
type PageSorter struct {
	precedence    map[NumFormat]int
	strict        bool
	disable_range bool
}

func NewPageSorter(style *OutputStyle, option *OutputOptions) *PageSorter {
	var sorter PageSorter
	sorter.precedence = make(map[NumFormat]int)
	for i, r := range style.page_precedence {
		switch r {
		case 'r':
			sorter.precedence[NUM_ROMAN_LOWER] = i
		case 'n':
			sorter.precedence[NUM_ARABIC] = i
		case 'a':
			sorter.precedence[NUM_ALPH_LOWER] = i
		case 'R':
			sorter.precedence[NUM_ROMAN_UPPER] = i
		case 'A':
			sorter.precedence[NUM_ALPH_UPPER] = i
		default:
			log.Println("page_precedence 语法错误,采用默认值")
			sorter.precedence = map[NumFormat]int{
				NUM_ROMAN_LOWER: 0,
				NUM_ARABIC:      1,
				NUM_ALPH_LOWER:  2,
				NUM_ROMAN_UPPER: 3,
				NUM_ALPH_UPPER:  4,
			}
		}
	}
	sorter.strict = option.strict
	sorter.disable_range = option.disable_range
	return &sorter
}

// 处理输入的页码,生成页码区间组
func (sorter *PageSorter) Sort(entry IndexEntry) []PageRange {
	pages := entry.pagelist
	//debug.Println(entry.input, pages)
	var out []PageRange
	// 合并前排序。传统 Makeindex 按原始输入的次序,在处理多个文件时可能不大好
	if sorter.strict {
		sort.Sort(PageSliceStrict{
			PageSlice{pages: pages, sorter: sorter}})
	} else {
		sort.Sort(PageSliceLoose{
			PageSlice{pages: pages, sorter: sorter}})
	}
	//debug.Println(pages)
	// 使用一个栈来合并页码区间
	// 这里的合并只将 1( 2 3 3) 合并为 1--3,不处理相邻区间,后者需要再做 Merge 操作
	var stack []*Page
	for i := 0; i < len(pages); i++ {
		p := pages[i]
		//debug.Printf("处理页码 %s{%s} %s\n", p.encap, p.NumString(), p.rangetype)
		if len(stack) == 0 {
			switch p.rangetype {
			case PAGE_NORMAL:
				// 输出独立页
				out = append(out, PageRange{begin: p, end: p})
			case PAGE_OPEN:
				// 压栈
				stack = append(stack, p)
			case PAGE_CLOSE:
				log.Printf("条目 %s 的页码区间有误,区间末尾 %s{%s} 没有匹配的区间头。\n", entry.input, p.encap, p)
				// 输出从空白到当前页的伪区间
				out = append(out, PageRange{begin: p.Empty(), end: p})
			}
		} else {
			front := stack[0]
			top := stack[len(stack)-1]
			if p.encap != front.encap {
				if sorter.strict {
					log.Printf("条目 %s 的页码区间可能有误,区间头 %s 没有对应的区间尾\n", entry.input, front)
					// 输出从区间头到空白的伪区间,并清空栈
					out = append(out, PageRange{begin: front, end: front.Empty()})
					stack = nil
					// 退回重新处理此项
					i--
					continue
				} else {
					// 只输出独立页面,与 Makeindex 行为类似
					if p.rangetype == PAGE_NORMAL {
						out = append(out, PageRange{begin: p, end: p})
					} else {
						log.Printf("条目 %s 的页码区间 %s{%s--} 内 %s%s{%s} 命令格式不同,可能丢失信息",
							entry.input, front.encap, front, p.rangetype, p.encap, p)
					}
				}
			} else if !p.Compatible(top) {
				// 标准 Makeindex 会尝试把区间断开,这里只给出警告
				log.Printf("条目 %s 的页码区间 %s{%s -- %s} 跨过不同的数字格式\n", entry.input, top.encap, top, p)
			}
			switch p.rangetype {
			case PAGE_NORMAL:
				// 什么也不做
			case PAGE_OPEN:
				// 压栈
				stack = append(stack, p)
			case PAGE_CLOSE:
				// 栈中只有一个元素时输出正常区间,弹栈
				if len(stack) == 1 {
					out = append(out, PageRange{begin: front, end: p})
				}
				stack = stack[:len(stack)-1]
			}
		}
	}
	if len(stack) > 0 {
		log.Printf("条目 %s 的页码区间有误,未找到与 %s{%s} 匹配的区间尾。\n", entry.input, stack[0].encap, stack[0])
		// 输出从当前页到空白的伪区间
		out = append(out, PageRange{begin: stack[0], end: stack[0].Empty()})
	}
	//	debug.Println(out)
	return out
}

// 合并相邻的页码区间
// 输入是 1 2--3 4--6 7,输出 1--7
func (sorter *PageSorter) Merge(pages []PageRange) []PageRange {
	var out []PageRange
	for i, r := range pages {
		// 跳过首项;按设置跳过单页页码
		if i == 0 {
			out = append(out, r)
			continue
		}
		// 合并重复页和区间
		prev := out[len(out)-1]
		if sorter.disable_range &&
			(r.begin.rangetype == PAGE_NORMAL || prev.begin.rangetype == PAGE_NORMAL) {
			// 合并(跳过)重复页
			if prev.begin == r.begin {
				continue
			} else {
				out = append(out, r)
			}
		} else if prev.begin.encap == r.begin.encap &&
			r.begin.Compatible(prev.begin) &&
			r.begin.Diff(prev.end) <= 1 {
			// 合并区间,只用后一区间尾替换前一区间尾
			out[len(out)-1].end = r.end
		} else {
			out = append(out, r)
		}
	}
	// 修正区间类型(似乎无用)
	for i := range out {
		if out[i].begin.encap == out[i].end.encap {
			if out[i].begin.Diff(out[i].end) == 0 {
				out[i].begin.rangetype = PAGE_NORMAL
				out[i].end.rangetype = PAGE_NORMAL
			}
			// 保留首尾区间类型,可以输出时判断是否是合并得到的区间
		}
		// encap 不同是不匹配区间或不完全区间,不修正
	}
	return out
}

type PageSlice struct {
	pages  []*Page
	sorter *PageSorter
}

func (p PageSlice) Len() int {
	return len(p.pages)
}

func (p PageSlice) Swap(i, j int) {
	p.pages[i], p.pages[j] = p.pages[j], p.pages[i]
}

type PageSliceStrict struct {
	PageSlice
}

// 先按 encap 类型比较,然后按页码本身比较,然后是 rangetype,方便以后合并
// 不同 encap 严格分离
func (p PageSliceStrict) Less(i, j int) bool {
	a, b := p.pages[i], p.pages[j]
	if a.encap < b.encap {
		return true
	} else if a.encap > b.encap {
		return false
	}
	if cmp := a.Cmp(b, p.sorter.precedence); cmp != 0 {
		return cmp < 0
	}
	if a.rangetype < b.rangetype {
		return true
	} else {
		return false
	}
}

type PageSliceLoose struct {
	PageSlice
}

// 先按页码类型比较,然后按页码数值,然后 rangetype,最后是 encap 类型,方便以后合并
// 允许不同 encap 合并,接近传统的 Makeindex 行为
func (p PageSliceLoose) Less(i, j int) bool {
	a, b := p.pages[i], p.pages[j]
	if cmp := a.Cmp(b, p.sorter.precedence); cmp != 0 {
		return cmp < 0
	}
	if a.rangetype < b.rangetype {
		return true
	} else if a.rangetype > b.rangetype {
		return false
	}
	if a.encap < b.encap {
		return true
	} else {
		return false
	}
}

// 忽略大小写,按内码比较两个字符
// 此过程被其他 collator 的 RuneCmp 调用
func RuneCmpIgnoreCases(a, b rune) int {
	la, lb := unicode.ToLower(a), unicode.ToLower(b)
	return int(la - lb)
}

// 测试是否是数字,但把“〇”单独算做汉字
func IsNumRune(r rune) bool {
	return unicode.IsNumber(r) && r != '〇'
}

// 测试是否为数字串
// 此过程被其他 collator 的 RuneCmp 调用
func IsNumString(s string) bool {
	for _, r := range s {
		if !IsNumRune(r) {
			return false
		}
	}
	return true
}

// 按数字大小比较自然数串,如果不是自然数串视为相等
func DecimalStrcmp(a, b string) int {
	aint, err := strconv.ParseUint(a, 10, 64)
	if err != nil {
		return 0
	}
	bint, err := strconv.ParseUint(b, 10, 64)
	if err != nil {
		return 0
	}
	switch {
	case aint < bint:
		return -1
	case aint > bint:
		return 1
	default:
		return 0
	}
}