Golang の sort パッケージ

## intro

sort パッケージは slice などをソートするデフォルト実装や、独自の比較ロジックを定めるインタフェースなどが提供されています。
Go のインタフェース、継承による拡張などの考え方的にも面白いので解説メモ。


## Sort function

sort パッケージには Sort 関数が定義されている。

そのシグネチャは以下。

```
func Sort(data Interface)
```

つまり、ここに sort.Interface インタフェースを満たしたものを渡すと、中で Quick Sort, Heap Sort, Insertion Sort を、条件に応じて使い分け、いい感じに並べ替えてくれる。


## Sort Interface

sort.Interface のインタフェースは以下。
(Go では、メソッドを持っていればインタフェースは満たされる)

```go
type Interface interface {
  // Len is the number of elements in the collection.
  Len() int
  // Less returns whether the element with index i should sort
  // before the element with index j.
  Less(i, j int) bool
  // Swap swaps the elements with indexes i and j.
  Swap(i, j int)
}
```

## 簡単なソート

自分で作った構造体のソートなんかは、上記メソッドを実装すれば終わる。

```go
package main

import (
	"log"
	"sort"
)

// 独自の構造体
type Person struct {
	Name string
	Age  uint8
}

// 構造体のスライス
type People []Person

// 以下インタフェースを満たす

func (p People) Len() int {
	return len(p)
}

func (p People) Swap(i, j int) {
	p[i], p[j] = p[j], p[i]
}

func (p People) Less(i, j int) bool {
	return p[i].Name < p[j].Name
}

func main() {
	var people People = []Person{
		{"John", 22},
		{"Tom", 20},
		{"Emily", 18},
	}

	// sort.Sort に渡すだけ
	sort.Sort(people) // return はされない点には注意
	log.Println(people) // [{Emily 18} {Tom 22} {John 20}]
}
```

## ソート条件が複数欲しい

名前と年齢でそれぞれソートできるようにする。
ソート条件のための型を用意し、もとの構造体を継承させる。
Swap, Len は継承したものを、 Less は子で実装すれば良い。

```go
package main

import (
	"log"
	"sort"
)

type Person struct {
	Name string
	Age  uint8
}

type People []Person

func (p People) Len() int {
	return len(p)
}

func (p People) Swap(i, j int) {
	p[i], p[j] = p[j], p[i]
}

// Name でソートするための型
type ByName struct {
	People // 継承にあたるもの
	// ちなみに
	// people People
	// などとすると継承にはならない
}

func (b ByName) Less(i, j int) bool {
	return b.People[i].Name < b.People[j].Name
}

// Age でソートするための型
type ByAge struct {
	People
}

func (b ByAge) Less(i, j int) bool {
	return b.People[i].Age < b.People[j].Age
}

func main() {
	var people People = []Person{
		{"John", 22},
		{"Tom", 20},
		{"Emily", 18},
	}

	// 条件に継承させてからソート
	sort.Sort(ByName{people})
	log.Println(people) // [{Emily 18} {John 22} {Tom 20}]

	sort.Sort(ByAge{people})
	log.Println(people) // [{Emily 18} {Tom 20} {John 22}]
}
```


## basic sort

int, string, float64 の slice のためには、デフォルトの実装が提供されている。
sort.Interface を満たすための型が提供され、それを継承してソートするラッパー関数も提供されている。

```go
package main

import (
	"log"
	"sort"
)

func main() {
	i := []int{5, 2, 6, 3, 1, 4}
	// sort.IntSlice に型変換している
	// sort.Interface が満たされる
	sort.Sort(sort.IntSlice(i))
	log.Println(i) // [1 2 3 4 5 6]

	s := []string{"cd", "bc", "ab", "aa"}
	// 継承と Sort を両方やってくれる
	sort.Strings(s)
	log.Println(s) // [aa ab bc cd]

	// 同様に sort.Float64s もある。
}
```


## Reverse

sort.Interface を満たしていれば、 Reverse() が使える。

```
sort.Sort(people)
log.Println(people) // [{Emily 18} {John 20} {Tom 22}]

sort.Sort(sort.Reverse(people)) // reverse
log.Println(people) // [{Tom 22} {John 20} {Emily 18}]
```

なぜなら、 Reverse の実装は Less を盗んでるだけだから。

```
package sort

type reverse struct {
	// This embedded Interface permits Reverse to use the methods of
	// another Interface implementation.
	Interface
}

// Less returns the opposite of the embedded implementation's Less method.
func (r reverse) Less(i, j int) bool {
	return r.Interface.Less(j, i)
}

// Reverse returns the reverse order for data.
func Reverse(data Interface) Interface {
	return &reverse{data}
}
```


## Less をユーザランドで決める

http://golang.org/pkg/sort/#example__sortKeys に紹介されているテク。
Less() にあたるものを型の定義から外しておけると便利、みたいなの。

動的に Less を定義することはできないので、内部にもう一つ Struct を作って、
その初期化時に渡した func を、 Less() で使うようなテクニック。

```go
package main

import (
	"log"
	"sort"
)

type Person struct {
	Name string
	Age  uint8
}

type People []Person

// Less() の型
type By func(p1, p2 Person) bool

func (by By) Sort(people People) {
  // ここで struct にメンバとして渡す
	ps := PeopleSorter{
		people: people,
		by:     by,
	}
	sort.Sort(ps)
}

type PeopleSorter struct {
	people People
	by     By
}

func (p PeopleSorter) Len() int {
	return len(p.people)
}

func (p PeopleSorter) Swap(i, j int) {
	p.people[i], p.people[j] = p.people[j], p.people[i]
}

func (p PeopleSorter) Less(i, j int) bool {
  // ここで渡された Less が使う
	return p.by(p.people[i], p.people[j])
}

func main() {
	var people People = []Person{
		{"John", 22},
		{"Tom", 20},
		{"Emily", 18},
	}

  // Less() を別途定義
	name := func(p1, p2 Person) bool {
		return p1.Name < p2.Name
	}

	age := func(p1, p2 Person) bool {
		return p1.Age < p2.Age
	}

  // ここで渡す
	By(name).Sort(people)
	log.Println(people)

	By(age).Sort(people)
	log.Println(people)
}
```


## Sort(people).By(name) だろ JK

できるかどうかやってみた。
Sort() では People の情報しか無いから、
By() の中でもう一つ struct が必要だと思う。実装は汚い。(もっと綺麗になるかも)


```go
package main

import (
	"log"
	"sort"
)

type Person struct {
	Name string
	Age  uint8
}

type People []Person

func Sort(people People) PeopleSorter {
	return PeopleSorter{
		people,
	}
}

type PeopleSorter struct {
	people People
}

func (p PeopleSorter) By(by By) {
	s := Sorter{
		p,
		by,
	}
	s.sort()
}

type Sorter struct {
	PeopleSorter
	By
}

func (s Sorter) Len() int {
	return len(s.people)
}

func (s Sorter) Swap(i, j int) {
	s.people[i], s.people[j] = s.people[j], s.people[i]
}

func (s Sorter) Less(i, j int) bool {
	return s.By(s.people[i], s.people[j])
}

func (s Sorter) sort() {
	sort.Sort(s)
}

type By func(p1, p2 Person) bool

func main() {
	var people People = []Person{
		{"John", 22},
		{"Tom", 20},
		{"Emily", 18},
	}

	name := func(p1, p2 Person) bool {
		return p1.Name < p2.Name
	}

	age := func(p1, p2 Person) bool {
		return p1.Age < p2.Age
	}

	Sort(people).By(name)
	log.Println(people)

	Sort(people).By(age)
	log.Println(people)
}
```

## 一応置いておく

いいかどうかは別として、Sort(people, name) で書いてみた。

```go
package main

import (
	"log"
	"sort"
)

type Person struct {
	Name string
	Age  uint8
}

type People []Person

type By func(p1, p2 Person) bool

func Sort(people People, by By) {
	p := PeopleSorter{
		people,
		by,
	}
	sort.Sort(p)
}

type PeopleSorter struct {
	People
	By
}

func (s PeopleSorter) Len() int {
	return len(s.People)
}

func (s PeopleSorter) Swap(i, j int) {
	s.People[i], s.People[j] = s.People[j], s.People[i]
}

func (s PeopleSorter) Less(i, j int) bool {
	return s.By(s.People[i], s.People[j])
}

func main() {
	var people People = []Person{
		{"John", 22},
		{"Tom", 20},
		{"Emily", 18},
	}

	name := func(p1, p2 Person) bool {
		return p1.Name < p2.Name
	}

	age := func(p1, p2 Person) bool {
		return p1.Age < p2.Age
	}

	Sort(people, name)
	log.Println(people)

	Sort(people, age)
	log.Println(people)
}
```

力尽きたので Search はまた今度。