Go語言縮排排序

本節將通過範例為大家演示如何將字串按照等級（縮排級別）進行排序，完整程式碼如下所示。

package main

import (
    "fmt"
    "sort"
    "strings"
)

var original = []string{
    "Nonmetals",
    "    Hydrogen",
    "    Carbon",
    "    Nitrogen",
    "    Oxygen",
    "Inner Transitionals",
    "    Lanthanides",
    "        Europium",
    "        Cerium",
    "    Actinides",
    "        Uranium",
    "        Plutonium",
    "        Curium",
    "Alkali Metals",
    "    Lithium",
    "    Sodium",
    "    Potassium",
}

func main() {
    fmt.Println("|     Original      |       Sorted      |")
    fmt.Println("|-------------------|-------------------|")
    sorted := SortedIndentedStrings(original) // 最初是 []string
    for i := range original {                 // 在全域性變數中設定
        fmt.Printf("|%-19s|%-19s|n", original[i], sorted[i])
    }
}

func SortedIndentedStrings(slice []string) []string {
    entries := populateEntries(slice)
    return sortedEntries(entries)
}

func populateEntries(slice []string) Entries {
    indent, indentSize := computeIndent(slice)
    entries := make(Entries, 0)
    for _, item := range slice {
        i, level := 0, 0
        for strings.HasPrefix(item[i:], indent) {
            i += indentSize
            level++
        }
        key := strings.ToLower(strings.TrimSpace(item))
        addEntry(level, key, item, &entries)
    }
    return entries
}

func computeIndent(slice []string) (string, int) {
    for _, item := range slice {
        if len(item) > 0 && (item[0] == ' ' || item[0] == 't') {
            whitespace := rune(item[0])
            for i, char := range item[1:] {
                if char != whitespace {
                    i++
                    return strings.Repeat(string(whitespace), i), i
                }
            }
        }
    }
    return "", 0
}

func addEntry(level int, key, value string, entries *Entries) {
    if level == 0 {
        *entries = append(*entries, Entry{key, value, make(Entries, 0)})
    } else {
        addEntry(level-1, key, value,
            &((*entries)[entries.Len()-1].children))
    }
}

func sortedEntries(entries Entries) []string {
    var indentedSlice []string
    sort.Sort(entries)
    for _, entry := range entries {
        populateIndentedStrings(entry, &indentedSlice)
    }
    return indentedSlice
}

func populateIndentedStrings(entry Entry, indentedSlice *[]string) {
    *indentedSlice = append(*indentedSlice, entry.value)
    sort.Sort(entry.children)
    for _, child := range entry.children {
        populateIndentedStrings(child, indentedSlice)
    }
}

type Entry struct {
    key      string
    value    string
    children Entries
}
type Entries []Entry

func (entries Entries) Len() int { return len(entries) }

func (entries Entries) Less(i, j int) bool {
    return entries[i].key < entries[j].key
}
func (entries Entries) Swap(i, j int) {
    entries[i], entries[j] = entries[j], entries[i]
}

注意 SortedIndentedStrings() 函數有一個很重要的前提就是，字串的縮排是通過讀到的空格或縮排的個數來決定的，下面來看一下輸出結果，為了方便對比，這裡將排序前的結果放在左邊，排序後的結果放在右邊。

|     Original      |       Sorted      |
|-------------------|-------------------|
|Nonmetals          |Alkali Metals      |
|    Hydrogen       |    Lithium        |
|    Carbon         |    Potassium      |
|    Nitrogen       |    Sodium         |
|    Oxygen         |Inner Transitionals|
|Inner Transitionals|    Actinides      |
|    Lanthanides    |        Curium     |
|        Europium   |        Plutonium  |
|        Cerium     |        Uranium    |
|    Actinides      |    Lanthanides    |
|        Uranium    |        Cerium     |
|        Plutonium  |        Europium   |
|        Curium     |Nonmetals          |
|Alkali Metals      |    Carbon         |
|    Lithium        |    Hydrogen       |
|    Sodium         |    Nitrogen       |
|    Potassium      |    Oxygen         |

其中，SortedIndentedStrings() 函數和它的輔助函數使用到了遞回、函數參照以及指向切片的指標等。

type Entry struct {
    key      string
    value    string
    children Entries
}
type Entries []Entry

func (entries Entries) Len() int { return len(entries) }

func (entries Entries) Less(i, j int) bool {
    return entries[i].key < entries[j].key
}
func (entries Entries) Swap(i, j int) {
    entries[i], entries[j] = entries[j], entries[i]
}

sort.Interface 介面定義了 3 個方法 Len()、Less() 和 Swap()，它們的函數簽名和 Entries 中的同名方法是一樣的，這就意味著我們可以使用標準庫裡的 sort.Sort() 函數來對一個 Entries 進行排序。

func SortedIndentedStrings(slice []string) []string {
    entries := populateEntries(slice)
    return sortedEntries(entries)
}

匯出的函數 SortedIndentedStrings() 就做了這個工作，雖然我們已經對它進行了重構，讓它把所有東西都傳遞給輔助函數，函數 populateEntries() 傳入一個 []string 並返回一個對應的 Entries（[]Entry 型別）。

而函數 sortedEntries() 需要傳入一個 Entries，然後返回一個排過序的 []string（根據縮排的級別進行排序）。

func populateEntries(slice []string) Entries {
    indent, indentSize := computeIndent(slice)
    entries := make(Entries, 0)
    for _, item := range slice {
        i, level := 0, 0
        for strings.HasPrefix(item[i:], indent) {
            i += indentSize
            level++
        }
        key := strings.ToLower(strings.TrimSpace(item))
        addEntry(level, key, item, &entries)
    }
    return entries
}

populateEntries() 函數首先以字串的形式得到給定切片裡的一級縮排（如有 4 個空格的字串）和它佔用的位元組數，然後建立一個空的 Entries，並遍歷切片裡的每一個字串，判斷該字串的縮排級別，再建立一個用於排序的鍵。

下一步，呼叫自定義函數 addEntry()，將當前字串的級別、鍵、字串本身，以及指向 entries 的地址作為引數，這樣 addEntry() 就能建立一個新的 Entry 並能夠正確地將它追加到 entries 裡去，最後返回 entries。

func computeIndent(slice []string) (string, int) {
    for _, item := range slice {
        if len(item) > 0 && (item[0] == ' ' || item[0] == 't') {
            whitespace := rune(item[0])
            for i, char := range item[1:] {
                if char != whitespace {
                    i++
                    return strings.Repeat(string(whitespace), i), i
                }
            }
        }
    }
    return "", 0
}

computeIndent() 函數主要是用來判斷縮排使用的是什麼字元，例如空格或者縮排符等，以及一個縮排級別佔用多少個這樣的字元。

因為第一級的字串可能沒有縮排，所以函數必須疊代所有的字串，一旦它發現某個字串的行首是空格或者縮排，函數馬上返回表示縮排的字元以及一個縮排所佔用的字元數。

func addEntry(level int, key, value string, entries *Entries) {
    if level == 0 {
        *entries = append(*entries, Entry{key, value, make(Entries, 0)})
    } else {
        addEntry(level-1, key, value,
            &((*entries)[entries.Len()-1].children))
    }
}

addEntry() 是一個遞回函數，它建立一個新的 Entry，如果這個 Entry 的 level 是 0，那就直接增加到 entries 裡去，否則，就將它作為另一個 Entry 的子集。

我們必須確定這個函數傳入的是一個 *Entries 而不是傳遞一個 entries 參照（切片的預設行為），因為我們是要將資料追加到 entries 裡，追加到一個參照會導致無用的本地副本且原來的資料實際上並沒有被修改。

如果 level 是 0，表明這個字串是頂級項，因此必須將它直接追加到 *entries，實際上情況要更複雜一些，因為 level 是相對傳入的 *entries 而言的，第一次呼叫 addEntry() 時，*entries 是一個第一級的 Entries，但函數進入遞回後，*entries 就可能是某個 Entry 的子集。

我們使用內建的 append() 函數來追加新的 Entry，並使用 * 操作符獲得 entries 指標指向的值，這就保證了任何改變對呼叫者來說都是可見的，新增的 Entry 包含給定的 key 和 value，以及一個空的子 Entries，這是遞迴的結束條件。

如果 level 大於 0，則我們必須將它追加到上一級 Entry 的 children 欄位裡去，這裡我們只是簡單地遞回呼叫 addEntry() 函數，最後一個引數可能是我們目前為止見到的最複雜的表示式了。

子表示式 entries.Len() - 1 產生一個 int 型整數，表示 *entries 指向的 Entries 值的最後一個條目的索引位置（注意 Entries.Len() 傳入的是一個 Entries 值而不是 *Entries 指標，不過Go語言也可以自動對 entries 指標進行解除參照並呼叫相應的方法）。

完整的表示式（&(...) 除外）存取了 Entries 最後一個 Entry 的 children 欄位（這也是一個 Entries 型別），所以如果把這個表示式作為一個整體，實際上我們是將 Entries 裡最後一個 Entry 的 children 欄位的記憶體地址作為遞回呼叫的引數，因為 addEntry() 最後一個引數是 *Entries 型別的。

為了幫助大家弄清楚到底發生了什麼，下面的程式碼和上述程式碼中 else 程式碼塊中的那個呼叫是一樣的。

theEntries := *entries
lastEntry := &theEntries[theEntries.Len()-1]
addEntry(level-1, key, value, &lastEntry.children)

首先，我們建立 theEntries 變數用來儲存 *entries 指標指向的值，這裡沒有什麼開銷因為不會產生複製，實際上 theEntries 相當於一個指向 Entries 值的別名。

然後我們取得最後一項的記憶體地址（即一個指標），如果不取地址的話就會取到最後一項的副本，最後遞回呼叫 addEntry() 函數，並將最後一項的 children 欄位的地址作為引數傳遞給它。

func sortedEntries(entries Entries) []string {
    var indentedSlice []string
    sort.Sort(entries)
    for _, entry := range entries {
        populateIndentedStrings(entry, &indentedSlice)
    }
    return indentedSlice
}

當呼叫 sortedEntries() 函數的時候，Entries 顯示的結構和原先程式輸出的字串是一樣的，每一個縮排的字串都是上一級縮排的子級，而且還可能有下一級的縮排，依次類推。

建立了 Entries 之後，SortedIndentedStrings() 函數呼叫上面這個函數去生成一個排好序的字串切片 []string，這個函數首先建立一個空的 []string 用來儲存最後的結果，然後對 entries 進行排序。

Entries 實現了 sort.Interface 介面，因此我們可以直接使用 sort.Sort() 函數根據 Entry 的 key 欄位來對 Entries 進行排序（這是 Entries.Less() 的實現方式），這個排序只是作用於第一級的 Entry，對其他未排序的子集是沒有任何影響的。

為了能夠對 children 欄位以及 children 的 children 等進行遞回排序，函數遍歷第一級的每一個項並呼叫 populateIndentedStrings() 函數，傳入這個 Entry 型別的項和一個指向 []string 切片的指標。

切片可以傳遞給函數並由函數更新內容（如替換切片裡的某些項），但是這裡需要往切片裡新增一些資料，所以這裡將一個指向切片的指標（也就是指標的指標）作為引數傳進去，並將指標指向的內容設定為 append() 函數的返回結果，可能是一個新的切片，也可能是原先的切片。

另一種辦法就是傳入切片的值，然後返回 append() 之後的切片，但是必須將返回的結果賦值給原來的切片變數（例如 slice = function(slice)），不過這麼做的話，很難正確地使用遞回函數。

func populateIndentedStrings(entry Entry, indentedSlice *[]string) {
    *indentedSlice = append(*indentedSlice, entry.value)
    sort.Sort(entry.children)
    for _, child := range entry.children {
        populateIndentedStrings(child, indentedSlice)
    }
}

populateIndentedStrings() 函數將頂級項追加到建立的切片，然後對頂級項的子項進行排序，並遞回呼叫自身對每一個子項做同樣的處理，這就相當於對每一項的子項以及子項的子項等都做了排序，所以整個字串切片就是已經排好序的了。