Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

カーソルの実装

さて、不変版は実際には面白くないので、std の CursorMut だけを扱うことにします。元の設計と同じように、リストの先頭/末尾を示す None を含む「ゴースト」要素があり、それを「通り越す」ことでリストの反対側に回り込めます。これを実装するには、次のものが必要です。

  • 現在のノードへのポインタ
  • リストへのポインタ
  • 現在のインデックス

「ゴースト」を指しているとき、インデックスはどうなるのでしょうか？

眉をひそめる … std を確認する … std の答えが気に入らない

さて、かなり妥当なことに、Cursor の index は Option<usize> を返します。std の実装は、それを Option として保持するのを避けるためにいろいろと余計なことをしていますが……こちらは連結リストなので、問題ありません。また std には cursor_front/cursor_back というものがあり、カーソルを先頭/末尾要素から開始します。これは直感的に感じますが、その結果、リストが空のときに奇妙なことをしなければならなくなります。

必要ならそのあたりを実装してもかまいませんが、私は反復的なごちゃごちゃした処理やコーナーケースを減らして、ゴーストから開始する素の cursor_mut メソッドだけを作ることにします。利用者は move_next/move_prev を使って欲しい位置へ移動できます（本当に必要なら、それを cursor_front として包むこともできます）。

始めましょう。

pub struct CursorMut<'a, T> {
    cur: Link<T>,
    list: &'a mut LinkedList<T>,
    index: Option<usize>,
}

かなり分かりやすいですね。箇条書きの各項目に対応するフィールドが 1 つずつあります！では cursor_mut メソッドです。

impl<T> LinkedList<T> {
    pub fn cursor_mut(&mut self) -> CursorMut<T> {
        CursorMut { 
            list: self, 
            cur: None, 
            index: None,
        }
    }
}

ゴーストから開始するので、すべて None で始めればよく、簡潔です！次は移動です。

impl<'a, T> CursorMut<'a, T> {
    pub fn index(&self) -> Option<usize> {
        self.index
    }

    pub fn move_next(&mut self) {
        if let Some(cur) = self.cur {
            unsafe {
                // 実際の要素上にいるので、その次（back）へ進む
                self.cur = (*cur.as_ptr()).back;
                if self.cur.is_some() {
                    *self.index.as_mut().unwrap() += 1;
                } else {
                    // ゴーストへ到達したので、もうインデックスはない
                    self.index = None;
                }
            }
        } else if !self.list.is_empty() {
            // ゴーストにいて、実際の front があるので、そこへ移動する！
            self.cur = self.list.front;
            self.index = Some(0)
        } else {
            // ゴーストにいるが、それが唯一の要素……何もしない。
        }
    }
}

つまり、興味深いケースは 4 つあります。

  • 通常ケース
  • 通常ケースだが、ゴーストに到達する場合
  • ゴーストケースで、リストの先頭へ移動する場合
  • ゴーストケースだが、リストが空なので何もしない場合

move_prev はまったく同じロジックですが、front/back が逆になり、インデックスの変更も逆になります。

pub fn move_prev(&mut self) {
    if let Some(cur) = self.cur {
        unsafe {
            // 実際の要素上にいるので、その前（front）へ進む
            self.cur = (*cur.as_ptr()).front;
            if self.cur.is_some() {
                *self.index.as_mut().unwrap() -= 1;
            } else {
                // ゴーストへ到達したので、もうインデックスはない
                self.index = None;
            }
        }
    } else if !self.list.is_empty() {
        // ゴーストにいて、実際の back があるので、そこへ移動する！
        self.cur = self.list.back;
        self.index = Some(self.list.len - 1)
    } else {
        // ゴーストにいるが、それが唯一の要素……何もしない。
    }
}

次に、カーソルの周囲の要素を見るためのメソッド、current、peek_next、peek_prev を追加しましょう。非常に重要な注意: これらのメソッドは、カーソルを &mut self で借用しなければならず、結果はその借用に結び付いていなければなりません。ユーザーに可変参照のコピーを複数取得させることはできませんし、そのような参照を保持している間に insert/remove/split/splice API を使わせることもできません！

ありがたいことに、ライフタイム省略を使ったときに Rust がデフォルトで仮定するのはこれなので、デフォルトで正しいことをするだけです！

pub fn current(&mut self) -> Option<&mut T> {
    unsafe {
        self.cur.map(|node| &mut (*node.as_ptr()).elem)
    }
}

pub fn peek_next(&mut self) -> Option<&mut T> {
    unsafe {
        self.cur
            .and_then(|node| (*node.as_ptr()).back)
            .map(|node| &mut (*node.as_ptr()).elem)
    }
}

pub fn peek_prev(&mut self) -> Option<&mut T> {
    unsafe {
        self.cur
            .and_then(|node| (*node.as_ptr()).front)
            .map(|node| &mut (*node.as_ptr()).elem)
    }
}

頭を空にして、Option メソッドと（省略された）コンパイラエラーがすべて考えてくれるようになりました。Option<NonNull> のあれこれには懐疑的でしたが、くそっ、本当にこのコードを自動操縦で書けるようにしてくれます。Option をまったく使えない配列ベースのコレクションを書きすぎていました。いやあ、これは素晴らしいですね！（(*node.as_ptr()) は相変わらずひどいですが、それは Rust の生ポインタというものです……）

次に選択肢があります。これらの API の要点である split と splice にそのまま進むか、単一要素の insert/remove で小さな一歩を踏むかです。insert/remove は結局 split と splice の観点で実装したくなる気がするので……先にそちらをやって、どう転ぶか見てみましょう（これを書いている時点では本当に分かっていません）。

Split

まずは split_before と split_after です。これらは現在の要素の前/後ろにあるすべてを LinkedList として返します（ゴースト要素で停止します。ただし、ゴースト上にいる場合はリスト全体を返し、カーソルは空のリストを指すようになります）。

目を細める うーん、これは実際にはそれなりに自明でないロジックなので、1 ステップずつ話していく必要があります。

split_before について、興味深そうなケースは 4 つあると思います。

  • 通常ケース
  • 通常ケースだが、prev がゴーストの場合
  • ゴーストケースで、リスト全体を返し、自分は空になる場合
  • ゴーストケースだが、リストが空なので、何もせず空のリストを返す場合

まずコーナーケースから始めましょう。3 番目のケースは、単にこれだと思います。

#![allow(unused)]
fn main() {
mem::replace(self.list, LinkedList::new())
}

ですよね？こちらは空になり、リスト全体を返し、フィールドはすでに None なので更新するものはありません。いいですね。おっと、これは 4 番目のケースでも正しいことをしてくれます！

では通常ケースです……よし、これには ASCII 図が必要です。最も一般的なケースでは、次のようなものがあります。

list.front -> A <-> B <-> C <-> D <- list.back
                          ^
                         cur

そして、こうしたいわけです。

list.front -> C <-> D <- list.back
              ^
             cur

return.front -> A <-> B <- return.back

なので、cur と prev の間のリンクを切る必要があります。そして……ああ、ものすごく多くの変更が必要です。よし、自分で筋が通っていると納得できるように、これを手順に分解する必要があります。少し過剰に冗長になりますが、少なくとも自分には理解できます。

pub fn split_before(&mut self) -> LinkedList<T> {
    if let Some(cur) = self.cur {
        // 実在する要素を指しているので、リストは空ではない。
        unsafe {
            // 現在の状態
            let old_len = self.list.len;
            let old_idx = self.index.unwrap();
            let prev = (*cur.as_ptr()).front;
            
            // self がどうなるか
            let new_len = old_len - old_idx;
            let new_front = self.cur;
            let new_back = self.list.back;
            let new_idx = Some(0);

            // 出力がどうなるか
            let output_len = old_len - new_len;
            let output_front = self.list.front;
            let output_back = prev;

            // cur と prev の間のリンクを切る
            if let Some(prev) = prev {
                (*cur.as_ptr()).front = None;
                (*prev.as_ptr()).back = None;
            }

            // 結果を生成する:
            self.list.len = new_len;
            self.list.front = new_front;
            self.list.back = new_back;
            self.index = new_idx;

            LinkedList {
                front: output_front,
                back: output_back,
                len: output_len,
                _boo: PhantomData,
            }
        }
    } else {
        // ゴースト位置にいるので、自分たちのリストを空のものと置き換えるだけ。
        // 他の状態を変更する必要はない。
        std::mem::replace(self.list, LinkedList::new())
    }
}

この if-let は、「通常のケースだが、prev がゴーストである」状況を扱っていることに注意してください。

if let Some(prev) = prev {
    (*cur.as_ptr()).front = None;
    (*prev.as_ptr()).back = None;
}

あなたが望むなら、これらを全部まとめて、次のような最適化を適用できます。

  • (*cur.as_ptr()).front への 2 回のアクセスを、単に (*cur.as_ptr()).front.take() として畳み込む
  • new_back は noop であることに注目して、両方とも削除する

私にわかる限り、それ以外はすべて、別の理由でたまたま正しいことをしています。テストを書くときにわかるでしょう！（copy-paste して split_after を作る）

私はもうミスをするのにうんざりしたので、できるだけ間違えようのないコードを書こうとするだけにします。これが、私が実際にコレクションを書く方法です。つまり、物事を些細な手順とケースに分解して、自分の頭に収まり、間違えようがないと思えるまで続けます。それから、自分がそれでもなお失敗していないと納得できるまで、大量のテストを書きます。

私がやってきたコレクション関連の作業の大半は極めて unsafe なので、コンパイラがミスを捕まえてくれることに頼ることは普通できませんし、昔は miri も存在していませんでした！ だから、頭が痛くなるまで問題を凝視して、絶対に絶対に絶対にミスをしないように全力を尽くす必要があります。

Unsafe Rust Code を書いてはいけません！ Safe Rust のほうがずっと良いです!!!!

Splice

あともう 1 体だけボスが残っています。splice_before と splice_after です。これが全部の中でいちばんコーナーケースが簡単なものになると予想しています。この 2 つの関数は LinkedList を受け取り、その内容をこちらのリストに接ぎ木します。こちらのリストが空かもしれないし、相手のリストが空かもしれないし、ゴーストも扱わなければなりません……はあ、splice_before で一歩ずつ進めましょう。

  • 相手のリストが空なら、何もする必要はありません。
  • こちらのリストが空なら、こちらのリストは単に相手のリストになります。
  • ゴーストを指しているなら、これは末尾に追加します（list.back を変更）
  • 最初の要素 (0) を指しているなら、これは先頭に追加します（list.front を変更）
  • 一般的なケースでは、非常に多くのポインタのクソ面倒な操作を行います。

一般的なケースはこれです。

input.front -> 1 <-> 2 <- input.back

 list.front -> A <-> B <-> C <- list.back
                     ^
                    cur

これがこうなります。

list.front -> A <-> 1 <-> 2 <-> B <-> C <- list.back

いいですか？ よし。これを書き出してみましょう……大きく息を吸い込み、飛び込む:

    pub fn splice_before(&mut self, mut input: LinkedList<T>) {
        unsafe {
            if input.is_empty() {
                // 入力が空なら、何もしない。
            } else if let Some(cur) = self.cur {
                if let Some(0) = self.index {
                    // 先頭に追加している。末尾への追加を参照
                    (*cur.as_ptr()).front = input.back.take();
                    (*input.back.unwrap().as_ptr()).back = Some(cur);
                    self.list.front = input.front.take();

                    // index は入力の長さだけ前に進む
                    *self.index.as_mut().unwrap() += input.len;
                    self.list.len += input.len;
                    input.len = 0;
                } else {
                    // 一般的なケース。境界はなく、内部の修正だけ
                    let prev = (*cur.as_ptr()).front.unwrap();
                    let in_front = input.front.take().unwrap();
                    let in_back = input.back.take().unwrap();

                    (*prev.as_ptr()).back = Some(in_front);
                    (*in_front.as_ptr()).front = Some(prev);
                    (*cur.as_ptr()).front = Some(in_back);
                    (*in_back.as_ptr()).back = Some(cur);

                    // index は入力の長さだけ前に進む
                    *self.index.as_mut().unwrap() += input.len;
                    self.list.len += input.len;
                    input.len = 0;
                }
            } else if let Some(back) = self.list.back {
                // ゴースト上にいるが空ではないので、末尾に追加する
                // 入力のポインタを `take` することも、`mem::forget` することもできる
                // カスタムアロケータか、クリーンアップが必要な何かを使う場合に備えて、
                // take を使うほうがより責任あるやり方！
                (*back.as_ptr()).back = input.front.take();
                (*input.front.unwrap().as_ptr()).front = Some(back);
                self.list.back = input.back.take();
                self.list.len += input.len;
                // 必要ではないが、やっておくと礼儀正しい
                input.len = 0;
            } else {
                // 空なので、入力になり、ゴースト上にとどまる
                *self.list = input;
            }
        }
    }

よし、これは本当にひどいもので、今やまさに Option<NonNull> のつらさを感じています。しかし、できるクリーンアップはたくさんあります。まず、このコードは最後まで引き出せます。常にそれを行いたいからです。私はこれを気に入っているわけではありません（もっとも、noop になることもありますし、input.len を設定するのは、今後のコード拡張に対するパラノイアのようなものです）。

self.list.len += input.len;
input.len = 0;

move された値の使用: input

ああ、そうでした。「こちらが空」のケースではリストを move しています。これを swap に置き換えましょう。

// 空なので、入力になり、ゴースト上にとどまる
std::mem::swap(self.list, &mut input);

この場合、書き込みは無意味になりますが、それでも動作します（おそらく、この分岐で早期リターンしてコンパイラをなだめることもできるでしょう）。

この unwrap は、私がケースを逆向きに考えていた結果にすぎず、if-let に正しい質問をさせることで修正できます。

if let Some(0) = self.index {

} else {
    let prev = (*cur.as_ptr()).front.unwrap();
}

インデックスの調整は分岐内で重複しているので、外に引き上げることもできます。

#![allow(unused)]
fn main() {
*self.index.as_mut().unwrap() += input.len;
}

よし、これらをすべてまとめるとこうなります。

#![allow(unused)]
fn main() {
if input.is_empty() {
    // 入力は空なので、何もしない。
} else if let Some(cur) = self.cur {
    // 両方のリストが空ではない
    if let Some(prev) = (*cur.as_ptr()).front {
        // 一般ケース、境界はなく、内部の修正だけ
        let in_front = input.front.take().unwrap();
        let in_back = input.back.take().unwrap();

        (*prev.as_ptr()).back = Some(in_front);
        (*in_front.as_ptr()).front = Some(prev);
        (*cur.as_ptr()).front = Some(in_back);
        (*in_back.as_ptr()).back = Some(cur);
    } else {
        // 前方に追加している。下の後方への追加を参照
        (*cur.as_ptr()).front = input.back.take();
        (*input.back.unwrap().as_ptr()).back = Some(cur);
        self.list.front = input.front.take();
    }
    // インデックスは入力の長さだけ前方に移動する
    *self.index.as_mut().unwrap() += input.len;
} else if let Some(back) = self.list.back {
    // ゴースト上にいるが空ではないので、後方に追加する
    // 入力のポインタを `take` することも、`mem::forget` することも
    // できる。カスタムアロケータなど、クリーンアップが必要なものも
    // 扱う場合に備えると、take を使う方が責任あるやり方だ！
    (*back.as_ptr()).back = input.front.take();
    (*input.front.unwrap().as_ptr()).front = Some(back);
    self.list.back = input.back.take();

} else {
    // 空なので、入力そのものになり、ゴースト上にとどまる
    std::mem::swap(self.list, &mut input);
}

self.list.len += input.len;
// 必須ではないが、やっておくのが礼儀
input.len = 0;

// 入力はここで drop される
}

よし、これはまだひどいですが、主な理由は――いや待って、バグを見つけました。

#![allow(unused)]
fn main() {
    (*back.as_ptr()).back = input.front.take();
    (*input.front.unwrap().as_ptr()).front = Some(back);
}

input.front を take してから、次の行でそれを unwrap しています！ ため息 しかも、対応するミラーケースでも同じことをしています。テストではこれを即座に捕まえられたでしょうが、今は完璧であろうとしていて、私はこれをほとんどライブでやっており、まさにこの瞬間にそれに気づいたのです。普段のように面倒くさいくらい段階を踏んでやらなかった報いですね。もっと明示的に！

#![allow(unused)]
fn main() {
// 入力のポインタを `take` することも、`mem::forget` することも
// できる。将来カスタムアロケータなど、クリーンアップも必要なものを
// 扱う場合に備えると、`take` を使う方が責任あるやり方だ！
if input.is_empty() {
    // 入力は空なので、何もしない。
} else if let Some(cur) = self.cur {
    // 両方のリストが空ではない
    let in_front = input.front.take().unwrap();
    let in_back = input.back.take().unwrap();

    if let Some(prev) = (*cur.as_ptr()).front {
        // 一般ケース、境界はなく、内部の修正だけ
        (*prev.as_ptr()).back = Some(in_front);
        (*in_front.as_ptr()).front = Some(prev);
        (*cur.as_ptr()).front = Some(in_back);
        (*in_back.as_ptr()).back = Some(cur);
    } else {
        // prev がないので、前方に追加している
        (*cur.as_ptr()).front = Some(in_back);
        (*in_back.as_ptr()).back = Some(cur);
        self.list.front = Some(in_front);
    }
    // インデックスは入力の長さだけ前方に移動する
    *self.index.as_mut().unwrap() += input.len;
} else if let Some(back) = self.list.back {
    // ゴースト上にいるが空ではないので、後方に追加する
    let in_front = input.front.take().unwrap();
    let in_back = input.back.take().unwrap();

    (*back.as_ptr()).back = Some(in_front);
    (*in_front.as_ptr()).front = Some(back);
    self.list.back = Some(in_back);
} else {
    // 空なので、入力そのものになり、ゴースト上にとどまる
    std::mem::swap(self.list, &mut input);
}

self.list.len += input.len;
// 必須ではないが、やっておくのが礼儀
input.len = 0;

// 入力はここで drop される
}

よし、今度のこれは、許容できます。唯一の不満は、in_front/in_back の重複を排除していないことです（おそらく条件を組み替えればできるでしょうが、まあいいでしょう）。実際これは、Option<NonNull> の厄介なもののせいで面倒になっているだけで、基本的には C で書くものと同じです。これなら受け入れられます。いや、やはりこの手のものについては raw pointer をもっと使いやすくするべきですね。ただし、それはこの本の範囲外です。

ともあれ、その後で完全に疲れ果てたので、insert や remove やその他すべての API は読者への練習問題として残しておけます。

以下は、組み合わせ論をコピペしようと試みた Cursor の最終コードです。正しくできているでしょうか？ 次の章を書いてこの怪物をテストするときに初めて分かります！

pub struct CursorMut<'a, T> {
    list: &'a mut LinkedList<T>,
    cur: Link<T>,
    index: Option<usize>,
}

impl<T> LinkedList<T> {
    pub fn cursor_mut(&mut self) -> CursorMut<T> {
        CursorMut { 
            list: self, 
            cur: None, 
            index: None,
        }
    }
}

impl<'a, T> CursorMut<'a, T> {
    pub fn index(&self) -> Option<usize> {
        self.index
    }

    pub fn move_next(&mut self) {
        if let Some(cur) = self.cur {
            unsafe {
                // 実要素上にいるので、その次（back）へ進む
                self.cur = (*cur.as_ptr()).back;
                if self.cur.is_some() {
                    *self.index.as_mut().unwrap() += 1;
                } else {
                    // ゴーストへ進んだところなので、もう index はない
                    self.index = None;
                }
            }
        } else if !self.list.is_empty() {
            // ゴーストにいて、実際の front があるので、そこへ移動する！
            self.cur = self.list.front;
            self.index = Some(0)
        } else {
            // ゴーストにいるが、それが唯一の要素である... 何もしない。
        }
    }

    pub fn move_prev(&mut self) {
        if let Some(cur) = self.cur {
            unsafe {
                // 実要素上にいるので、その前（front）へ進む
                self.cur = (*cur.as_ptr()).front;
                if self.cur.is_some() {
                    *self.index.as_mut().unwrap() -= 1;
                } else {
                    // ゴーストへ進んだところなので、もう index はない
                    self.index = None;
                }
            }
        } else if !self.list.is_empty() {
            // ゴーストにいて、実際の back があるので、そこへ移動する！
            self.cur = self.list.back;
            self.index = Some(self.list.len - 1)
        } else {
            // ゴーストにいるが、それが唯一の要素である... 何もしない。
        }
    }

    pub fn current(&mut self) -> Option<&mut T> {
        unsafe {
            self.cur.map(|node| &mut (*node.as_ptr()).elem)
        }
    }

    pub fn peek_next(&mut self) -> Option<&mut T> {
        unsafe {
            self.cur
                .and_then(|node| (*node.as_ptr()).back)
                .map(|node| &mut (*node.as_ptr()).elem)
        }
    }

    pub fn peek_prev(&mut self) -> Option<&mut T> {
        unsafe {
            self.cur
                .and_then(|node| (*node.as_ptr()).front)
                .map(|node| &mut (*node.as_ptr()).elem)
        }
    }

    pub fn split_before(&mut self) -> LinkedList<T> {
        // これは次の状態:
        //
        //     list.front -> A <-> B <-> C <-> D <- list.back
        //                               ^
        //                              cur
        // 
        //
        // そしてこれを生成したい:
        // 
        //     list.front -> C <-> D <- list.back
        //                   ^
        //                  cur
        //
        // 
        //    return.front -> A <-> B <- return.back
        //
        if let Some(cur) = self.cur {
            // 実要素を指しているので、リストは空ではない。
            unsafe {
                // 現在の状態
                let old_len = self.list.len;
                let old_idx = self.index.unwrap();
                let prev = (*cur.as_ptr()).front;
                
                // self がどうなるか
                let new_len = old_len - old_idx;
                let new_front = self.cur;
                let new_back = self.list.back;
                let new_idx = Some(0);

                // 出力がどうなるか
                let output_len = old_len - new_len;
                let output_front = self.list.front;
                let output_back = prev;

                // cur と prev の間のリンクを切る
                if let Some(prev) = prev {
                    (*cur.as_ptr()).front = None;
                    (*prev.as_ptr()).back = None;
                }

                // 結果を生成する:
                self.list.len = new_len;
                self.list.front = new_front;
                self.list.back = new_back;
                self.index = new_idx;

                LinkedList {
                    front: output_front,
                    back: output_back,
                    len: output_len,
                    _boo: PhantomData,
                }
            }
        } else {
            // ゴーストにいるので、自分のリストを空のものに置き換えるだけ。
            // 他の状態を変更する必要はない。
            std::mem::replace(self.list, LinkedList::new())
        }
    }

    pub fn split_after(&mut self) -> LinkedList<T> {
        // これは次の状態:
        //
        //     list.front -> A <-> B <-> C <-> D <- list.back
        //                         ^
        //                        cur
        // 
        //
        // そしてこれを生成したい:
        // 
        //     list.front -> A <-> B <- list.back
        //                         ^
        //                        cur
        //
        // 
        //    return.front -> C <-> D <- return.back
        //
        if let Some(cur) = self.cur {
            // 実要素を指しているので、リストは空ではない。
            unsafe {
                // 現在の状態
                let old_len = self.list.len;
                let old_idx = self.index.unwrap();
                let next = (*cur.as_ptr()).back;
                
                // self がどうなるか
                let new_len = old_idx + 1;
                let new_back = self.cur;
                let new_front = self.list.front;
                let new_idx = Some(old_idx);

                // 出力がどうなるか
                let output_len = old_len - new_len;
                let output_front = next;
                let output_back = self.list.back;

                // cur と next の間のリンクを切る
                if let Some(next) = next {
                    (*cur.as_ptr()).back = None;
                    (*next.as_ptr()).front = None;
                }

                // 結果を生成する:
                self.list.len = new_len;
                self.list.front = new_front;
                self.list.back = new_back;
                self.index = new_idx;

                LinkedList {
                    front: output_front,
                    back: output_back,
                    len: output_len,
                    _boo: PhantomData,
                }
            }
        } else {
            // ゴーストにいるので、自分のリストを空のものに置き換えるだけ。
            // 他の状態を変更する必要はない。
            std::mem::replace(self.list, LinkedList::new())
        }
    }

    pub fn splice_before(&mut self, mut input: LinkedList<T>) {
        // これは次の状態:
        //
        // input.front -> 1 <-> 2 <- input.back
        //
        // list.front -> A <-> B <-> C <- list.back
        //                     ^
        //                    cur
        //
        //
        // これになる:
        //
        // list.front -> A <-> 1 <-> 2 <-> B <-> C <- list.back
        //                                 ^
        //                                cur
        //
        unsafe {
            // input のポインタを `take` するか、`mem::forget`
            // するかのどちらかができる。将来、カスタムアロケータなど、
            // クリーンアップが必要なものを使う場合に備えて、`take` を使う方が責任ある対応だ！
            if input.is_empty() {
                // input は空なので、何もしない。
            } else if let Some(cur) = self.cur {
                // 両方のリストが空ではない
                let in_front = input.front.take().unwrap();
                let in_back = input.back.take().unwrap();

                if let Some(prev) = (*cur.as_ptr()).front {
                    // 一般的なケース。境界はなく、内部の修正だけを行う
                    (*prev.as_ptr()).back = Some(in_front);
                    (*in_front.as_ptr()).front = Some(prev);
                    (*cur.as_ptr()).front = Some(in_back);
                    (*in_back.as_ptr()).back = Some(cur);
                } else {
                    // prev がないので、front に追加している
                    (*cur.as_ptr()).front = Some(in_back);
                    (*in_back.as_ptr()).back = Some(cur);
                    self.list.front = Some(in_front);
                }
                // index は input の長さだけ前方へ移動する
                *self.index.as_mut().unwrap() += input.len;
            } else if let Some(back) = self.list.back {
                // ゴースト上にいるが空ではないので、back に追加する
                let in_front = input.front.take().unwrap();
                let in_back = input.back.take().unwrap();

                (*back.as_ptr()).back = Some(in_front);
                (*in_front.as_ptr()).front = Some(back);
                self.list.back = Some(in_back);
            } else {
                // 空なので、input になり、ゴースト上に留まる
                std::mem::swap(self.list, &mut input);
            }

            self.list.len += input.len;
            // 必須ではないが、やっておくのが礼儀
            input.len = 0;
            
            // ここで input がドロップされる
        }        
    }

    pub fn splice_after(&mut self, mut input: LinkedList<T>) {
        // これは次の状態:
        //
        // input.front -> 1 <-> 2 <- input.back
        //
        // list.front -> A <-> B <-> C <- list.back
        //                     ^
        //                    cur
        //
        //
        // これになる:
        //
        // list.front -> A <-> B <-> 1 <-> 2 <-> C <- list.back
        //                     ^
        //                    cur
        //
        unsafe {
            // input のポインタを `take` するか、`mem::forget`
            // するかのどちらかができる。将来、カスタムアロケータなど、
            // クリーンアップが必要なものを使う場合に備えて、`take` を使う方が責任ある対応だ！
            if input.is_empty() {
                // input は空なので、何もしない。
            } else if let Some(cur) = self.cur {
                // 両方のリストが空ではない
                let in_front = input.front.take().unwrap();
                let in_back = input.back.take().unwrap();

                if let Some(next) = (*cur.as_ptr()).back {
                    // 一般的なケース。境界はなく、内部の修正だけを行う
                    (*next.as_ptr()).front = Some(in_back);
                    (*in_back.as_ptr()).back = Some(next);
                    (*cur.as_ptr()).back = Some(in_front);
                    (*in_front.as_ptr()).front = Some(cur);
                } else {
                    // next がないので、back に追加している
                    (*cur.as_ptr()).back = Some(in_front);
                    (*in_front.as_ptr()).front = Some(cur);
                    self.list.back = Some(in_back);
                }
                // index は変化しない
            } else if let Some(front) = self.list.front {
                // ゴースト上にいるが空ではないので、front に追加する
                let in_front = input.front.take().unwrap();
                let in_back = input.back.take().unwrap();

                (*front.as_ptr()).front = Some(in_back);
                (*in_back.as_ptr()).back = Some(front);
                self.list.front = Some(in_front);
            } else {
                // 空なので、input になり、ゴースト上に留まる
                std::mem::swap(self.list, &mut input);
            }

            self.list.len += input.len;
            // 必須ではないが、やっておくのが礼儀
            input.len = 0;
            
            // ここで input がドロップされる
        }        
    }
}