　考えてみる。

成果物

これまで考えたインタフェース

学習用

impl<T> OnewayList<T> {
    pub fn new() -> Self { Self { head: None } }

    pub fn push(&mut self, item: T) { self.push_tail(item); }
    pub fn push_head(&mut self, item: T) {}
    pub fn push_tail(&mut self, item: T) {}
    pub fn push_from_index(&mut self, item: T, index: u32) {}

    pub fn remove(&mut self) { self.remove_tail(); }
    pub fn remove_head(&mut self) {}
    pub fn remove_tail(&mut self) {}
    pub fn remove_from_index(&mut self, index: u32) {}
    pub fn remove_from_item(&mut self, item: T) {} // 指定要素に一致するノードを検索する必要がある
    fn search(&self, item: T) -> Result<&Option<Box<Node<T>>>, &'static str> { Err("Not found") }
    pub fn clear(&mut self) {}
}

　学習のために色々なメソッドを実装したい。

最適化

　単方向リストとして必要最小限なインタフェースのみにしたい。

impl<T> OnewayList<T> {
    pub fn new() -> Self { Self { head: None } }
    pub fn push(&mut self, item: T) { self.push_tail(item); }
}

　単方向リストは、次のノードがわかるリストである。追加や削除については特に決まりはないはず。

挿入、削除の位置: 末尾（_head, _tail, _from_index, _from_item系）
- 先頭や指定位置で行う必要はない
  - 「単方向」であるなら追加や削除もまた一方向のみでいい
    - 追加: ふつう最初に追加したものほど先頭に近い
    - 削除: 間違って追加したときに削除する想定。つまり追加の順序と同じが好ましい。

　push, removeした順序だけで対象ノードを選択する。単方向リストとはそういうもの、ということにしておく。追加と削除はいつも末尾に対して行う。先頭や任意位置には行えないようにする。

　こうなると使い方は限られる。予め決まった順序の要素をまとめるのに使うくらいか。たとえば工程。開発工程リストなら、企画、要件定義、設計、実装、テスト、納品など。

データ構造

　データ構造から考え直してみる。

グラフ
- 連結リスト
  - 線形リスト
    - 単方向リスト
    - 双方向リスト
  - 循環リスト
    - 単方向循環リスト
    - 双方向循環リスト
  - スタック
  - キュー
  - 3すくみ

　いずれ循環リストから3すくみ関係を表現したい。（じゃんけんゲームの改善）

インタフェース再考

　データ構造とその関係から、それぞれのインタフェースについて考えてみる。

LinkedList（連結リスト）
- LinearList（線形リスト）
  - SinglyLinkedList（片方向線形リスト）
  - DoublyLinkedList（双方向線形リスト）
- CircularlyLinkedList（循環リスト）
  - SinglyCircularlyLinkedList（片方向循環リスト）
  - DoublyCircularlyLinkedList（双方向循環リスト）
- Array（配列）
  - Stack（スタック）
  - Queue（キュー）

　分類は以下を参考にした。

共通

#[derive(Debug, PartialEq)]
struct Node<T> {
    item: T,
    next: Option<Box<Node<T>>>,
}
impl<T> Node<T> { fn new(item: T) -> Self { Self { item: item, next: None } } }

　もっとも、単方向か双方向かで持つべきポインタが増減する。この細かい点は以後省略してNodeと仮定する。

struct SinglyNode<T> {
    item: T,
    next: Option<Box<Node<T>>>,
}
struct DoublyNode<T> {
    item: T,
    next: Option<Box<Node<T>>>,
    prev: Option<Box<Node<T>>>,
}

　オブジェクト指向なら継承したくなるところ。たとえば以下みたいに。

class Node {
    T item;
    Node next;
}
class DoublyNode : Node {
    Node prev;
}

　でもRustにはクラスも継承もない……。structで別のstructフィールド定義を継承できたらいいのに。

　では、どうするか。各種リストを個別のクレートとし、それぞれ微妙に違うNodeを実装するしかない。Nodeは非公開だし。重複コードを書くのが嫌だが、今はそれで進めよう。

LinkedList（線形リスト）

#[derive(Debug, PartialEq)]
pub struct LinkedList<T> {
    head: Option<Box<Node<T>>>,
    tail: Option<Box<Node<T>>>,
}
impl<T> LinkedList<T> {
    pub fn new() -> Self { Self { head: None, tail: None } }

    pub fn push(&mut self, item: T) { self.push_tail(); }
    pub fn push_head(&mut self, item: T) {}
    pub fn push_tail(&mut self, item: T) {}
    pub fn push_from_index(&mut self, index: u32, item: T) {}

    pub fn remove(&mut self) { self.remove_tail(); }
    pub fn remove_head(&mut self) {}
    pub fn remove_tail(&mut self) {}
    pub fn remove_from_index(&mut self, index: u32) {}
    pub fn remove_from_item(&mut self, item: T) {} // 指定要素に一致するノードを検索する必要がある
    fn search(&self, item: T) -> Result<&Option<Box<Node<T>>>, &'static str> { Err("Not found") }
    pub fn clear(&mut self) {}

    pub fn get(&mut self, index: u32) -> &mut T {}
    pub fn next(&mut self) -> &mut T {}
}

　std::iter::Iteratorトレイトを実装してnextメソッドにて次の要素を取得するようにしたい。このとき、Node<T>の<T>にあたる値の可変参照を得たい。所有権はそのままNodeインスタンスに持たせておきたいから。

　nextでノードがもつ値への可変参照を得られたら、あとはそれに新しい値を代入することで別の値をセットすることもできる。また、参照外ししてitemフィールド値に値を代入すれば、値の更新もできる。

　ただ、nextはふつう、所有権をムーブするから位置が特定できるはず。所有権をムーブせず持たせた場合、何を基準にして「次」を決めればいいのか。内部にカウンタが必要か？

SinglyLinkedList（片方向線形リスト）

　これまでOnewayList（単方向リスト）と呼んでいたものと同じ。

#[derive(Debug, PartialEq)]
pub struct SinglyLinkedList<T> {
    head: Option<Box<Node<T>>>,
}
impl<T> SinglyLinkedList<T> {
    pub fn new() -> Self { Self { head: None } }

    pub fn push(&mut self, item: T) {} // 対象ノード: 末尾
    pub fn remove(&mut self) {} // 対象ノード: 末尾
    pub fn clear(&mut self) {}

    pub fn next(&mut self) -> &mut T {}
}

　ここでの単方向リストは、追加や削除も末尾のみという単方向性をもたせる。簡略化しつつ統一性をもたせて用途を限定するため。用途は工程など固定した順序をもつものに限る。並び替えは想定しない。順に追加したものを、順に削除したり取り出すことだけを想定する。

　唯一clearだけは例外。全ノードを消す。これは不要かもしれない。だが、ノードの早期dropや、リストを使いまわすときに使えそうなので一応入れておく。

DoublyLinkedList（双方向線形リスト）

#[derive(Debug, PartialEq)]
pub struct DoublyLinkedList<T> {
    head: Option<Box<Node<T>>>,
    tail: Option<Box<Node<T>>>,
}
impl<T> DoublyLinkedList<T> {
    pub fn new() -> Self { Self { head: None, tail: None } }

    pub fn push(&mut self, item: T) { self.push_tail(); }
    pub fn push_head(&mut self, item: T) {}
    pub fn push_tail(&mut self, item: T) {}

    pub fn remove(&mut self) { self.remove_tail(); }
    pub fn remove_head(&mut self) {}
    pub fn remove_tail(&mut self) {}
    pub fn clear(&mut self) {}

    pub fn get(&mut self, index: u32) -> &mut T {}
    pub fn next(&mut self) -> &mut T {}
}

　ほぼLinkedListと同じ。だが以下の一部メソッドを削っている。

*_from_index()系
*_from_item()系

　双方向ということで、追加と削除もまたheadとtailの双方向に対応させた。それ以外のメソッドである上記は削除することで前後関係のみに注目するリストとする。

Array（配列）

　これはStackとQueueのグループに過ぎない。

Stack（スタック）

#[derive(Debug, PartialEq)]
pub struct Stack<T> {
    tail: Option<Box<Node<T>>>,
}
impl<T> Stack<T> {
    pub fn new() -> Self { Self { head: None, tail: None } }
    pub fn push(&mut self, item: T) {} // 末尾へ追加
    pub fn pop(&mut self, item: T) -> T {} // 末尾を取得（所有権を放棄し削除後、戻り値として返す）
}

　関数の再帰呼出はまさにスタック構造。

挿入         取出
              C  B  A
| || || ||C| | || || || |
| || ||B||B| |B|| || || |
| ||A||A||A| |A||A|| || |
+-++-++-++-+ +-++-++-++-+
 1  2  3  4   5  6  7  8

Queue（キュー）

#[derive(Debug, PartialEq)]
pub struct Queue<T> {
    head: Option<Box<Node<T>>>,
    tail: Option<Box<Node<T>>>,
}
impl<T> Queue<T> {
    pub fn new() -> Self { Self { head: None, tail: None } }
    pub fn Enqueue(&mut self, item: T) {} // 末尾へ追加
    pub fn Dequeue(&mut self, item: T) -> T {} // 先頭を取得（所有権を放棄し削除後、戻り値として返す）
}

　店の行列はまさにキュー。

挿入          取出

| || || ||C| | || || || |
| || ||B||B| |C|| || || |
| ||A||A||A| |B||C|| || |
              A  B  C

 1  2  3  4   5  6  7  8

CircularlyLinkedList（循環リスト）

　先頭と末尾が互いに接続している。

#[derive(Debug, PartialEq)]
pub struct CircularlyLinkedList<T> {
    access_pointer: Option<Box<Node<T>>>, // 末尾ノード
}
impl<T> CircularlyLinkedList<T> {
    pub fn new() -> Self { Self { head: None, tail: None } }

    pub fn push(&mut self, item: T) {} // 末尾に追加
    pub fn push_for_next(&mut self, item: T, for: T) {} // forで指定した値をもつノードの`next`にitemで指定した値をもつノードを挿入する
    pub fn push_for_prev(&mut self, item: T, for: T) {} // forで指定した値をもつノードの`prev`にitemで指定した値をもつノードを挿入する

    pub fn remove(&mut self) {} // 末尾を削除
    pub fn remove_from_item(&mut self, item: T) {} // 指定要素に一致するノードを検索する必要がある
    fn search(&self, item: T) -> Result<&Option<Box<Node<T>>>, &'static str> { Err("Not found") }
    pub fn clear(&mut self) {}

    pub fn get_access_pointer(&mut self) -> &mut T {} // アクセスポインタが指すノードの値への可変参照を返す
    pub fn next_for(&mut self, for: T) -> &mut T {} // 指定した値をもつノードの`next`が指すノードの値への可変参照を返す
    pub fn prev_for(&mut self, for: T) -> &mut T {} // 指定した値をもつノードの`prev`が指すノードの値への可変参照を返す

    // 先頭・末尾系
    pub fn push_head(&mut self, item: T) {}
    pub fn push_tail(&mut self, item: T) {}
    pub fn remove_head(&mut self) {}
    pub fn remove_tail(&mut self) {}

    // インデックス系
    pub fn push_from_index(&mut self, index: u32, item: T) {}
    pub fn remove_from_index(&mut self, index: u32) {}
    pub fn get(&mut self, index: u32) -> &mut T {}
}

　循環するため「先頭」と「末尾」という順序が失われる。順序をなくせばインデックス指定も失われる。

　ただ、循環しつつも順序を保っていたい要件もあるはず。そこで、最も抽象的な「循環リスト」は全部のメソッドをもたせることにした。

　循環リストは順序が失われる場合があるため、先頭・末尾でなく「次・前」という相対位置による操作がメインとなる想定。

SinglyCircularlyLinkedList（片方向循環リスト）

　CircularlyLinkedListの機能限定版。以下メソッドを削除したもの。

先頭・末尾系
インデックス系
next, prev系（片方のみ）

DoublyCircularlyLinkedList（双方向循環リスト）

　CircularlyLinkedListの機能限定版。以下メソッドを削除したもの。

先頭・末尾系
インデックス系

Standoff（3すくみ関係リスト）

　循環リストの前後関係を互いの弱点関係とする。

struct Standoff<T> {
    item: T,
    weak: Option<Box<Standoff<T>>>,
    strong: Option<Box<Standoff<T>>>,
}
impl<T> Standoff<T> {
    pub fn new(item: T) -> Self { Self { item: item, weak: None, strong: None } }

    pub fn weak_for(&mut self, item: T) {} // 末尾は引数に弱い
    pub fn strong_for(&mut self, item: T) {} // 末尾は引数に強い

    pub fn remove(&mut self) {} // 末尾を削除

    pub fn weakable_for(&self, for: T) -> &T {} //指定した手に負ける弱い手を返す
    pub fn strongable_for(&self, for: T) -> &T {} //指定した手に勝てる強い手を返す
}

　かつて「じゃんけんゲーム」を作ったとき、「グー・チョキ・パー」の関係性をスマートに書けなかった。if文で全パターン網羅という不細工な実装をした屈辱、忘れはしない。それをこれでカッコよく書きたい。

和	英
グー	Rock
チョキ	Scissors
パー	Paper

let standoff = Standoff::new(Hand::Rock);
standoff.weak_for(Hand::Paper);
standoff.weak_for(Hand::Scissors);

assert_eq!(Hand::Scissors, standoff.weakable_for(Hand::Rock));
assert_eq!(Hand::Rock, standoff.weakable_for(Hand::Paper));
assert_eq!(Hand::Paper, standoff.weakable_for(Hand::Scissors));

assert_eq!(Hand::Paper, standoff.strongable_for(Hand::Rock));
assert_eq!(Hand::Scissors, standoff.strongable_for(Hand::Paper));
assert_eq!(Hand::Rock, standoff.strongable_for(Hand::Scissors));

　以下のようにstrong_forを使って挿入することもできる。

let standoff = Standoff::new(Hand::Rock);
standoff.strong_for(Hand::Scissors);
standoff.strong_for(Hand::Paper);

assert_eq!(Hand::Paper, standoff.strongable_for(Hand::Rock));
assert_eq!(Hand::Scissors, standoff.strongable_for(Hand::Paper));
assert_eq!(Hand::Rock, standoff.strongable_for(Hand::Scissors));

　よく考えたら一度関係を構築したあとで新たに挿入・削除することはないはず。なら、リスト生成時に全部渡せばいい。

impl<T> Standoff<T> {
    pub fn new(items_for_strong: Vec<T>) -> Self {
        let this = Self { item: Node { item: items_for_strong[0], next: None, prev: None }, weak: None, strong: None };
        for item in items_for_strong { this.strong_for(item); }
        this
    }
    fn weak_for(&mut self, item: T) {} // 末尾は引数に弱い
    fn strong_for(&mut self, item: T) {} // 末尾は引数に強い

    pub fn weakable_for(&self, for: T) -> &T {} //指定した手に負ける弱い手を返す
    pub fn strongable_for(&self, for: T) -> &T {} //指定した手に勝てる強い手を返す
    pub fn get_access_pointer(&mut self) -> &mut T {} // アクセスポインタが指すノードの値への可変参照を返す
}

　追加メソッドを非公開にした。削除メソッドは不要なため消した。

let standoff = Standoff::new(vec![Hand::Rock, Hand::Paper, Hand::Scissors]);
assert_eq!(Hand::Rock, standoff.get_access_pointer());

assert_eq!(Hand::Scissors, standoff.weakable_for(Hand::Rock));
assert_eq!(Hand::Rock, standoff.weakable_for(Hand::Paper));
assert_eq!(Hand::Paper, standoff.weakable_for(Hand::Scissors));

assert_eq!(Hand::Paper, standoff.strongable_for(Hand::Rock));
assert_eq!(Hand::Scissors, standoff.strongable_for(Hand::Paper));
assert_eq!(Hand::Rock, standoff.strongable_for(Hand::Scissors));

　もし、リストに何を入れたか忘れたら、get_access_pointerからすべて辿れる。

fn get_item(&standoff: Standoff<T>) {
    let first = standoff.get_access_pointer();
    let item = first;
    loop {
        item = standoff.strong_for(first);
        if first == item { break; }
    }
}

　もし「3すくみ」なら数は3つ固定のはず。

impl<T> Standoff<T> {
    pub fn new(first: T, second: T, third: T, ) -> Self {
        let this = Self { item: Node { item: first, next: None, prev: None }, weak: None, strong: None };
        this.strong_for(second);
        this.strong_for(third);
        this
    }
    pub fn weakable_for(&self, for: T) -> &T {} //指定した手に負ける弱い手を返す
    pub fn strongable_for(&self, for: T) -> &T {} //指定した手に勝てる強い手を返す
    pub fn get_access_pointer(&mut self) -> &mut T {} // アクセスポインタが指すノードの値への可変参照を返す
}

　以下、3すくみを一般化して考えてみる。

2つ以下

　手が2つ以下のときは関係性が絶対的になってしまう。グーとチョキしかないなら、必ずグーが勝利する。こんなルールなら皆がグーしか出さないためゲームにならない。完全な支配構造。上下関係。

　手が1つなら「あいこ」の無限ループとなり、ゲームにならない。完全な平等。

4つ以上

　もし4つ以上なら、1つ前か後以外の関係が不定。以下のパターンがありうる。

不定（勝敗がつけられない。かといって引き分けにすると、あまりに引き分けの場合が多すぎる）
先頭ほど強い（なら先頭の手しか選ばないに決まってる）
末尾ほど強い（なら末尾の手しか選ばないに決まってる）

　たとえば以下のような4つの要素を含んだ循環リストがあったとする。

1<--2<--3<--4<-+
|______________|

　1は4に勝つ。2は1に勝つ。3は2に勝つ。4は3に勝つ。では、2と4の関係は？　上記3パターンのいずれかになる。

　4要素のとき、2つ以上離れている値の組合せは以下。

1, 3
2, 4

　要素数が増えるほど多くなる。たとえば1〜5の5つの要素なら、1,3,1,4,1,5,2,4,2,5,3,5の6通り。

　2つ以上離れているときの手を引き分け（勝敗判定不能）にしてしまったら、手が増えると引き分けになる確率が高くなってしまう。

　かといって、もし勝敗をつけるなら、手の強さにばらつきが生じる。たとえば「末尾ほど強い」としたら、末尾が最強になる。1〜5なら、5は1にしか負けない。他の4,3,2,1にはすべて勝てる。同じ手である5はあいこになるため負けない。こんなルールならだれもが5の手を出すだろう。

　もっとも、勝率に応じて「勝点」という概念を追加すれば平等感もある。もしくは一発逆転の射幸心を煽ることもできる。だが、ゲーム性も変わる。なにより、ゲームが複雑になってしまう。今は学習用にコードを書くので単純なほうがいい。

　3つのときのみ、手の強さが同じになる。3すくみは最も単純に対等な勝負ができる構造。確率ゲーでなく運ゲー。

対象環境

2019-07-14
Raspbierry pi 3 Model B+
Raspbian stretch 9.0 2018-11-13
bash 4.4.12(1)-release
rustc 1.34.2 (6c2484dc3 2019-05-13)
cargo 1.34.0 (6789d8a0a 2019-04-01)

$ uname -a
Linux raspberrypi 4.19.42-v7+ #1219 SMP Tue May 14 21:20:58 BST 2019 armv7l GNU/Linux

やってみる

アウトプットすべく己を導くためのブログ。その試行錯誤すらたれ流す。

Rust自習（リストのインタフェースを考える）

成果物