sorter.go

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
	}
}