Go中的字母数字排序

Question

I am reading rows from the GAE Datastore and I want to sort them alphanumerically.

Suppose I have something like this:

key      name      description    sequence  
===========================================  
ASD..    maths1    it is maths    chap21.1  
ASD..    maths2    it is maths    chap21.10  
ASD..    maths3    it is maths    chap21.2  

I want the result sorted alphanumerically on the sequence field, like this:

key      name      description    sequence  
===========================================  
ASD..    maths1    it is maths    chap21.1  
ASD..    maths3    it is maths    chap21.2 
ASD..    maths2    it is maths    chap21.10   

Answer 1

Use ISO/IEC 14651:2011 to construct the sequence sort key. For example,

package main

import (
    "fmt"
    "sort"
)

const maxByte = 1<<8 - 1

func isDigit(d byte) bool {
    return '0' <= d && d <= '9'
}

func SequenceKey(key string) string {
    sKey := make([]byte, 0, len(key)+8)
    j := -1
    for i := 0; i < len(key); i++ {
        b := key[i]
        if !isDigit(b) {
            sKey = append(sKey, b)
            j = -1
            continue
        }
        if j == -1 {
            sKey = append(sKey, 0x00)
            j = len(sKey) - 1
        }
        if sKey[j] == 1 && sKey[j+1] == '0' {
            sKey[j+1] = b
            continue
        }
        if sKey[j]+1 > maxByte {
            panic("SequenceKey: invalid key")
        }
        sKey = append(sKey, b)
        sKey[j]++
    }
    return string(sKey)
}

type Chapter struct {
    Key         string
    Name        string
    Description string
    Sequence    string
    SequenceKey string `datastore:"-"`
}

type Chapters []*Chapter

var chapters = Chapters{
    {Key: "ASD..", Name: "maths1", Description: "it is maths", Sequence: "chap21.1"},
    {Key: "ASD..", Name: "maths2", Description: "it is maths", Sequence: "chap21.10"},
    {Key: "ASD..", Name: "maths3", Description: "it is maths", Sequence: "chap21.2"},
}

func (s Chapters) Len() int {
    return len(s)
}

func (s Chapters) Swap(i, j int) {
    s[i], s[j] = s[j], s[i]
}

type BySequenceKey struct{ Chapters }

func (s BySequenceKey) Less(i, j int) bool {
    return s.Chapters[i].SequenceKey < s.Chapters[j].SequenceKey
}

func main() {
    for _, chapter := range chapters {
        chapter.SequenceKey = SequenceKey(chapter.Sequence)
    }
    fmt.Println("Unsorted:")
    for _, chapter := range chapters {
        fmt.Printf("  sequence: %#v
", chapter.Sequence)
        fmt.Printf("    sort key: %#v
", chapter.SequenceKey)
        fmt.Printf("      name: %#v
", chapter.Name)
    }
    fmt.Println("Sorted:")
    sort.Sort(BySequenceKey{chapters})
    for _, chapter := range chapters {
        fmt.Printf("  sequence: %#v
", chapter.Sequence)
        fmt.Printf("    sort key: %#v
", chapter.SequenceKey)
        fmt.Printf("      name: %#v
", chapter.Name)
    }
}

Output:

Unsorted:
  sequence: "chap21.1"
    sort key: "chap\x0221.\x011"
      name: "maths1"
  sequence: "chap21.10"
    sort key: "chap\x0221.\x0210"
      name: "maths2"
  sequence: "chap21.2"
    sort key: "chap\x0221.\x012"
      name: "maths3"
Sorted:
  sequence: "chap21.1"
    sort key: "chap\x0221.\x011"
      name: "maths1"
  sequence: "chap21.2"
    sort key: "chap\x0221.\x012"
      name: "maths3"
  sequence: "chap21.10"
    sort key: "chap\x0221.\x0210"
      name: "maths2"