[インデックス 16957] ファイルの概要

このコミットは、Go言語の標準ライブラリ container/list パッケージに、リスト内の要素を特定の位置に移動させるための新しいメソッド MoveBefore と MoveAfter を追加するものです。これにより、既存の要素を基準にして他の要素の順序を変更する操作がより容易かつ効率的に行えるようになります。

コミット

commit fbcc24bb9d20caa7a73cfd12ed0ba9332f274368
Author: Pieter Droogendijk <pieter@binky.org.uk>
Date:   Wed Jul 31 14:11:25 2013 -0700

    container/list: added MoveBefore and MoveAfter
    
    Fixes #4940.
    
    R=golang-dev, bradfitz, gri
    CC=golang-dev
    https://golang.org/cl/12021044

GitHub上でのコミットページへのリンク

https://github.com/golang/go/commit/fbcc24bb9d20caa7a73cfd12ed0ba9332f274368

元コミット内容

container/list: added MoveBefore and MoveAfter

Fixes #4940.

R=golang-dev, bradfitz, gri
CC=golang-dev
https://golang.org/cl/12021044

変更の背景

この変更は、Go言語のIssue #4940 に対応するものです。Issue #4940 は、「container/list に MoveBefore と MoveAfter メソッドを追加してほしい」という要望でした。

container/list パッケージは、Go言語で双方向連結リスト（doubly linked list）を実装するための標準パッケージです。既存のメソッドには、要素の追加（PushFront, PushBack, InsertBefore, InsertAfter）、削除（Remove）、移動（MoveToFront, MoveToBack）などがありましたが、特定の要素の「前」や「後」に別の既存要素を移動させる直接的なメソッドは存在しませんでした。

このような操作が必要な場合、開発者は既存の Remove と InsertBefore/InsertAfter を組み合わせて実装する必要がありました。これは冗長であり、また、リストの内部構造を理解していないと誤った操作をしてしまう可能性がありました。

MoveBefore と MoveAfter の追加は、このような一般的な操作を標準ライブラリのAPIとして提供することで、コードの可読性と保守性を向上させ、開発者の利便性を高めることを目的としています。これにより、リスト内の要素の順序を動的に変更するアプリケーションにおいて、より簡潔で安全なコードを記述できるようになります。

前提知識の解説

双方向連結リスト (Doubly Linked List)

双方向連結リストは、データ構造の一種で、各ノード（Go言語の container/list パッケージでは Element と呼ばれる）が、そのノードが保持するデータだけでなく、**次のノードへのポインタ（next）と前のノードへのポインタ（prev）**を持つ点が特徴です。

• ノード (Element): リスト内の個々の要素。データと、前後のノードへの参照を持つ。
• ヘッド (Head): リストの最初のノード。
• テール (Tail): リストの最後のノード。

双方向連結リストの主な利点は以下の通りです。

• 効率的な挿入と削除: リストの任意の位置に要素を挿入したり、削除したりする操作がO(1)の時間計算量で行えます。これは、挿入/削除対象のノードとその前後のノードのポインタを更新するだけで済むためです。配列のように要素をシフトする必要がありません。
• 双方向の走査: 前後のポインタを持つため、リストを先頭から末尾へ、または末尾から先頭へ、どちらの方向にも効率的に走査できます。

Go言語の container/list パッケージでは、リスト自体は List 構造体で表現され、その内部にダミーの root 要素を持つことで、リストが空の場合や、先頭・末尾への操作を簡潔に扱えるように設計されています。

container/list パッケージの基本的な操作

container/list パッケージは、以下のような基本的な操作を提供します。

• New(): 新しい空のリストを作成します。
• PushFront(v interface{}) *Element: リストの先頭に要素を追加します。
• PushBack(v interface{}) *Element: リストの末尾に要素を追加します。
• InsertBefore(v interface{}, mark *Element) *Element: mark 要素の前に新しい要素を挿入します。
• InsertAfter(v interface{}, mark *Element) *Element: mark 要素の後に新しい要素を挿入します。
• Remove(e *Element) interface{}: 指定された要素をリストから削除します。
• MoveToFront(e *Element): 指定された要素をリストの先頭に移動します。
• MoveToBack(e *Element): 指定された要素をリストの末尾に移動します。

これらの操作は、双方向連結リストの特性を活かして効率的に実装されています。

技術的詳細

このコミットで追加された MoveBefore と MoveAfter メソッドは、既存の Remove および insert (内部メソッド) を組み合わせて実装されています。

List 構造体には、リストの要素数を管理する len フィールドと、リストの先頭と末尾を指すダミーの root 要素があります。root 要素は、リストが空の場合でも常に存在し、root.next がリストの最初の要素を、root.prev がリストの最後の要素を指すように設計されています。これにより、リストの境界条件（空のリスト、先頭への追加、末尾への追加など）を統一的に処理できます。

remove(e *Element) *Element (内部メソッド)

この内部メソッドは、指定された要素 e をリストから削除し、その要素を返します。削除の際には、e の前後の要素のポインタを適切に更新し、e 自体のポインタをnilに設定して、リストから切り離します。また、リストの要素数 l.len をデクリメントします。

func (l *List) remove(e *Element) *Element {
	e.prev.next = e.next
	e.next.prev = e.prev
	e.next = nil // avoid memory leaks
	e.prev = nil // avoid memory leaks
	e.list = nil
	l.len--
	return e
}

insert(e, at *Element) (内部メソッド)

この内部メソッドは、指定された要素 e を、at 要素の「後」に挿入します。挿入の際には、e と at、そして at の次の要素のポインタを適切に更新します。また、リストの要素数 l.len をインクリメントします。

func (l *List) insert(e, at *Element) *Element {
	e.prev = at
	e.next = at.next
	e.prev.next = e
	e.next.prev = e
	e.list = l
	l.len++
	return e
}

MoveBefore と MoveAfter は、これらのプリミティブな操作を組み合わせて、要素の移動を実現します。

MoveBefore(e, mark *Element) のロジック

1. 前条件チェック:
   • e.list != l: 移動対象の要素 e が、操作対象のリスト l に属していない場合、何もしません。これは、異なるリスト間の要素移動を防ぐための安全策です。
   • e == mark: 移動対象の要素 e と基準となる要素 mark が同じ場合、移動は意味をなさないため、何もしません。
2. 要素の削除: l.remove(e) を呼び出して、リストから e を一時的に切り離します。この操作により、e はリストから論理的に削除されますが、その内容は保持されます。
3. 要素の挿入: l.insert(l.remove(e), mark.prev) を呼び出します。これは、削除した e を、mark の「前」に挿入することを意味します。mark.prev は mark の直前の要素を指すため、その要素の「後」に e を挿入することで、結果的に mark の「前」に e が配置されます。

MoveAfter(e, mark *Element) のロジック

1. 前条件チェック:
   • e.list != l: 移動対象の要素 e が、操作対象のリスト l に属していない場合、何もしません。
   • e == mark: 移動対象の要素 e と基準となる要素 mark が同じ場合、何もしません。
2. 要素の削除: l.remove(e) を呼び出して、リストから e を一時的に切り離します。
3. 要素の挿入: l.insert(l.remove(e), mark) を呼び出します。これは、削除した e を、mark の「後」に挿入することを意味します。

これらの実装は、双方向連結リストの特性を最大限に活用し、ポインタの付け替えのみで要素の移動を実現しているため、非常に効率的です（O(1)の時間計算量）。

コアとなるコードの変更箇所

src/pkg/container/list/list.go

--- a/src/pkg/container/list/list.go
+++ b/src/pkg/container/list/list.go
@@ -179,6 +179,24 @@ func (l *List) MoveToBack(e *Element) {
 	l.insert(l.remove(e), l.root.prev)
 }
 
+// MoveBefore moves element e to its new position before mark.
+// If e is not an element of l, or e == mark, the list is not modified.
+func (l *List) MoveBefore(e, mark *Element) {
+	if e.list != l || e == mark {
+		return
+	}
+	l.insert(l.remove(e), mark.prev)
+}
+
+// MoveAfter moves element e to its new position after mark.
+// If e is not an element of l, or e == mark, the list is not modified.
+func (l *List) MoveAfter(e, mark *Element) {
+	if e.list != l || e == mark {
+		return
+	}
+	l.insert(l.remove(e), mark)
+}
+
 // PushBackList inserts a copy of an other list at the back of list l.
 // The lists l and other may be the same.
 func (l *List) PushBackList(other *List) {

src/pkg/container/list/list_test.go

--- a/src/pkg/container/list/list_test.go
+++ b/src/pkg/container/list/list_test.go
@@ -233,3 +233,37 @@ func TestIssue4103(t *testing.T) {
 		t.Errorf("l1.Len() = %d, want 3", n)
 	}
 }
+
+func TestMove(t *testing.T) {
+	l := New()
+	e1 := l.PushBack(1)
+	e2 := l.PushBack(2)
+	e3 := l.PushBack(3)
+	e4 := l.PushBack(4)
+
+	l.MoveAfter(e3, e3)
+	checkListPointers(t, l, []*Element{e1, e2, e3, e4})
+	l.MoveBefore(e2, e2)
+	checkListPointers(t, l, []*Element{e1, e2, e3, e4})
+
+	l.MoveAfter(e3, e2)
+	checkListPointers(t, l, []*Element{e1, e2, e3, e4})
+	l.MoveBefore(e2, e3)
+	checkListPointers(t, l, []*Element{e1, e2, e3, e4})
+
+	l.MoveBefore(e2, e4)
+	checkListPointers(t, l, []*Element{e1, e3, e2, e4})
+	e1, e2, e3, e4 = e1, e3, e2, e4
+
+	l.MoveBefore(e4, e1)
+	checkListPointers(t, l, []*Element{e4, e1, e2, e3})
+	e1, e2, e3, e4 = e4, e1, e2, e3
+
+	l.MoveAfter(e4, e1)
+	checkListPointers(t, l, []*Element{e1, e4, e2, e3})
+	e1, e2, e3, e4 = e1, e4, e2, e3
+
+	l.MoveAfter(e2, e3)
+	checkListPointers(t, l, []*Element{e1, e3, e2, e4})
+	e1, e2, e3, e4 = e1, e3, e2, e4
+}

コアとなるコードの解説

list.go の変更点

list.go には、MoveBefore と MoveAfter の2つの新しい公開メソッドが追加されています。

1. func (l *List) MoveBefore(e, mark *Element)

   • 目的: 要素 e を、要素 mark の直前に移動させます。
   • 引数:
     • e *Element: 移動させたい要素。
     • mark *Element: e をその前に移動させたい基準となる要素。
   • 挙動:
     • e.list != l または e == mark の場合、リストは変更されずに処理を終了します。これは、e が現在のリストに属していない場合や、e と mark が同じ要素である場合に、無意味な操作やエラーを防ぐためのガード句です。
     • それ以外の場合、l.remove(e) を呼び出して e をリストから一時的に削除します。
     • 次に、l.insert(..., mark.prev) を呼び出して、削除した e を mark の直前の要素 (mark.prev) の「後」に挿入します。これにより、結果的に e は mark の直前に配置されます。

2. func (l *List) MoveAfter(e, mark *Element)

   • 目的: 要素 e を、要素 mark の直後に移動させます。
   • 引数:
     • e *Element: 移動させたい要素。
     • mark *Element: e をその後に移動させたい基準となる要素。
   • 挙動:
     • e.list != l または e == mark の場合、リストは変更されずに処理を終了します。
     • それ以外の場合、l.remove(e) を呼び出して e をリストから一時的に削除します。
     • 次に、l.insert(..., mark) を呼び出して、削除した e を mark の「後」に挿入します。

これらのメソッドは、既存の内部ヘルパー関数 remove と insert を再利用しており、コードの重複を避け、簡潔に実装されています。

list_test.go の変更点

list_test.go には、新しく追加された MoveBefore と MoveAfter メソッドの動作を検証するための TestMove 関数が追加されています。

TestMove 関数は、以下のようなシナリオをテストしています。

1. 初期状態のリスト作成: l := New() で新しいリストを作成し、e1, e2, e3, e4 の4つの要素を PushBack で追加します。
2. 無効な移動操作のテスト:
   • l.MoveAfter(e3, e3): 移動対象と基準が同じ要素の場合。
   • l.MoveBefore(e2, e2): 移動対象と基準が同じ要素の場合。
   • これらの操作の後もリストの順序が変わらないことを checkListPointers で確認します。
3. 隣接要素間の移動テスト:
   • l.MoveAfter(e3, e2): e3 を e2 の後に移動（元々 e2, e3 なので変化なし）。
   • l.MoveBefore(e2, e3): e2 を e3 の前に移動（元々 e2, e3 なので変化なし）。
   • これらの操作の後もリストの順序が変わらないことを確認します。
4. 非隣接要素間の移動テスト:
   • l.MoveBefore(e2, e4): e2 を e4 の前に移動。リストは e1, e3, e2, e4 となるべきです。テスト後、要素の参照を新しい順序に合わせて更新しています。
   • l.MoveBefore(e4, e1): e4 を e1 の前に移動。リストは e4, e1, e2, e3 となるべきです。テスト後、要素の参照を更新しています。
   • l.MoveAfter(e4, e1): e4 を e1 の後に移動。リストは e1, e4, e2, e3 となるべきです。テスト後、要素の参照を更新しています。
   • l.MoveAfter(e2, e3): e2 を e3 の後に移動。リストは e1, e3, e2, e4 となるべきです。テスト後、要素の参照を更新しています。

checkListPointers ヘルパー関数は、リストの要素の順序と、各要素の next および prev ポインタが正しく設定されているかを検証するために使用されます。これにより、単に要素の順序だけでなく、リストの内部的な整合性も確認しています。

このテストコードは、様々なケース（特にエッジケースや、移動によってリストの構造が複雑に変化するケース）を網羅しており、新しく追加されたメソッドが期待通りに動作することを保証しています。

関連リンク

• Go Issue #4940: container/list: add MoveBefore and MoveAfter
• Go CL 12021044: container/list: added MoveBefore and MoveAfter

参考にした情報源リンク

• Go言語の container/list パッケージのドキュメント: https://pkg.go.dev/container/list
• 双方向連結リストに関する一般的な情報源 (例: Wikipedia, 各種データ構造の教科書)
• Go言語のIssueトラッカー: https://github.com/golang/go/issues
• Go言語のコードレビューシステム (Gerrit): https://go-review.googlesource.com/