summaryrefslogtreecommitdiff
path: root/indexing/zhmakeindex/sorter.go
diff options
context:
space:
mode:
authorNorbert Preining <norbert@preining.info>2019-09-02 13:46:59 +0900
committerNorbert Preining <norbert@preining.info>2019-09-02 13:46:59 +0900
commite0c6872cf40896c7be36b11dcc744620f10adf1d (patch)
tree60335e10d2f4354b0674ec22d7b53f0f8abee672 /indexing/zhmakeindex/sorter.go
Initial commit
Diffstat (limited to 'indexing/zhmakeindex/sorter.go')
-rw-r--r--indexing/zhmakeindex/sorter.go445
1 files changed, 445 insertions, 0 deletions
diff --git a/indexing/zhmakeindex/sorter.go b/indexing/zhmakeindex/sorter.go
new file mode 100644
index 0000000000..3109186a61
--- /dev/null
+++ b/indexing/zhmakeindex/sorter.go
@@ -0,0 +1,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
+ }
+}