パトリシア・ツリーを作ろうぜ☆(^~^)?

KITASHIRAKAWA_Chiyuri_80x100x8_01_Futu.gif
「 rust に BTreeMap ぐらい有るが、 パトリシア・ツリーを自作しようぜ☆?」

KIFUWARABE_80x100x8_01_Futu.gif
「 BTreeMap を使えばいいのに……☆」

OKAZAKI_Yumemi_80x80x8_02_Syaberu.gif
「 さっさと作り終えなさい」

20201104blog9a1.png

KITASHIRAKAWA_Chiyuri_80x100x8_01_Futu.gif
「 ↑ charstring は 普段から使ってるな関係だよな☆」

20201104blog10.png

KITASHIRAKAWA_Chiyuri_80x100x8_01_Futu.gif
「 ↑ 木の形をした文字列も 考え方は簡単だな☆
メモリの省略にならないから無駄なだけで……☆」

OKAZAKI_Yumemi_80x80x8_02_Syaberu.gif
「 じゃあ、 illustillustration を つないでみてよ」

20201104blog11.png

KITASHIRAKAWA_Chiyuri_80x100x8_01_Futu.gif
「 ↑ こうだな☆」

KIFUWARABE_80x100x8_01_Futu.gif
「 文字が切れるのは どういう仕組みだぜ☆?」

20201104blog12.png

KITASHIRAKAWA_Chiyuri_80x100x8_01_Futu.gif
「 ↑ 既に illust があるところに、あとから illustration を投げ込みたいなら……☆」

20201104blog12a1.png

KITASHIRAKAWA_Chiyuri_80x100x8_01_Futu.gif
「 ↑ 一致しなくなるまで、一致するところを読み進め……☆」

20201104blog12a2b1.png

KITASHIRAKAWA_Chiyuri_80x100x8_01_Futu.gif
「 ↑ 余りを、既存の部品のうしろに リンクで つなげだぜ☆」

KIFUWARABE_80x100x8_01_Futu.gif
「 あとから うしろ が伸びたら、 そんなの聞いてない! という 先頭のやつが いたりしないかだぜ☆?」

KITASHIRAKAWA_Chiyuri_80x100x8_01_Futu.gif
「 聞いてない先頭のやつがいたら困るぜ☆」

OKAZAKI_Yumemi_80x80x8_02_Syaberu.gif
「 こんな分岐のある 文字列、 イテレーション できなくない?」

while tree.branch_iter(&mut list, &mut select) {
    select = list[0].clone();
}

KITASHIRAKAWA_Chiyuri_80x100x8_01_Futu.gif
「 ↑ 自力実装イテレーションを考えてみるかだぜ☆?」

KIFUWARABE_80x100x8_01_Futu.gif
「 End は どうやって区別するんだぜ☆?」

KITASHIRAKAWA_Chiyuri_80x100x8_01_Futu.gif
「 Option 型でラッピングしておいて、 None が入ってたら End がある、ということでどうだぜ☆?」

OKAZAKI_Yumemi_80x80x8_02_Syaberu.gif
「 パトリシア・ツリーを作る前に、 tree-shaped string を作りましょう!」

pub struct CharacterRelation<T> {
    character: T,
}
pub struct StringRelation<T> {
    string: Vec<T>,
}
pub struct TreeShapedRelation<T> {
    root: Option<Box<StringRelation<T>>>,
}

KITASHIRAKAWA_Chiyuri_80x100x8_01_Futu.gif
「 ↑ 型を ジェネリック型の にしておけば、 文字以外にも この構造が使えるはずだぜ☆」

KIFUWARABE_80x100x8_01_Futu.gif
「 じゃあ、 illustration を追加してみてくれだぜ☆」

use crate::TreeShapedRelation;

impl<T> Default for TreeShapedRelation<T> {
    fn default() -> Self {
        TreeShapedRelation { root: None }
    }
}

impl<T> TreeShapedRelation<T> {
    pub fn insert_all(sequence: &Vec<T>) {}
}

KITASHIRAKAWA_Chiyuri_80x100x8_01_Futu.gif
「 ↑ うーん、大変そうだぜ☆
リンクトリスト を作るんだよな☆」

OKAZAKI_Yumemi_80x80x8_02_Syaberu.gif
「 StringRelation 型を先に作っておかなくちゃいけなくない? そして CharacterRelation 型の存在意義は何なの?」

KITASHIRAKAWA_Chiyuri_80x100x8_01_Futu.gif
「 CharacterRelation 型は要らないか……☆」

KIFUWARABE_80x100x8_01_Futu.gif
「 StringRelation という名前も 邪魔くさくないか☆ Sequence でいいのでは☆?」

KITASHIRAKAWA_Chiyuri_80x100x8_01_Futu.gif
「 じゃあ それで☆」

OKAZAKI_Yumemi_80x80x8_02_Syaberu.gif
「 TreeShapedRelation は単に Tree でよくない?」

KITASHIRAKAWA_Chiyuri_80x100x8_01_Futu.gif
「 まったくだぜ☆」

extern crate rattle_tree;

use rattle_tree::Tree;

fn main() {
    println!("Start.");
    let mut tree = Tree::default();
    tree.insert_sequence(&vec![
        'H', 'e', 'l', 'l', 'o', ',', ' ', 'W', 'o', 'r', 'l', 'd', '!', '!',
    ]);
    println!("tree={:?}", tree);
    println!("Finished.");
}

KITASHIRAKAWA_Chiyuri_80x100x8_01_Futu.gif
「 ↑ 使い方は こんな感じを想像しているぜ☆」

OKAZAKI_Yumemi_80x80x8_02_Syaberu.gif
「 Sequence 型で渡したくならない?」

KITASHIRAKAWA_Chiyuri_80x100x8_01_Futu.gif
「 言われてみれば☆」

extern crate rattle_tree;

use rattle_tree::{Sequence, Tree};

fn main() {
    println!("Start.");

    // Sequence.
    let mut seq = Sequence::default();
    seq.push(&vec![
        'H', 'e', 'l', 'l', 'o', ',', ' ', 'W', 'o', 'r', 'l', 'd', '!', '!',
    ]);

    // Tree.
    let mut tree = Tree::default();
    tree.insert(&seq);
    assert_eq!("Hello, World!!", format!("{:?}", tree));

    println!("Finished.");
}

KITASHIRAKAWA_Chiyuri_80x100x8_01_Futu.gif
「 ↑ いったん、これが動くことを目指してみるぜ☆」

#[derive(Clone)]
pub struct Sequence<T> {
    sequence: Vec<T>,
    cursor: usize,
}

KITASHIRAKAWA_Chiyuri_80x100x8_01_Futu.gif
「 ↑ シーケンスにイテレーター用の cursor を持たせておいて☆」

impl<T> Iterator for Sequence<T>
where
    T: std::clone::Clone,
{
    type Item = T;
    // The return type is `Option<T>`:
    //     * When the `Iterator` is finished, `None` is returned.
    //     * Otherwise, the next value is wrapped in `Some` and returned.
    fn next(&mut self) -> Option<T> {
        if self.cursor < self.sequence.len() {
            let item = Some(self.sequence[self.cursor].clone());
            self.cursor += 1;
            return item;
        }

        return None;
    }
}

KITASHIRAKAWA_Chiyuri_80x100x8_01_Futu.gif
「 ↑ イテレーターを実装したり☆」

impl<T> fmt::Debug for Sequence<T>
where
    T: std::fmt::Debug,
{
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        let mut buf = String::new();
        for chr in &self.sequence {
            buf.push_str(&format!("{:?}", chr));
        }
        write!(f, "{}", buf)
    }
}

KITASHIRAKAWA_Chiyuri_80x100x8_01_Futu.gif
「 ↑ デバッグ用文字列を出力できるようにしたり☆」

thread 'main' panicked at 'assertion failed: `(left == right)`
  left: `"\'H\'ello, World!!"`,
 right: `"\'H\'\'e\'\'l\'\'l\'\'o\'\',\'\' \'\'W\'\'o\'\'r\'\'l\'\'d\'\'!\'\'!\'"`', examples\example.rs:18:5
stack backtrace:
   0: std::panicking::begin_panic_handler

KITASHIRAKAWA_Chiyuri_80x100x8_01_Futu.gif
「 ↑ 失敗☆」

    // Hello, World!!
    assert_eq!(
        "'H''e''l''l''o'','' ''W''o''r''l''d''!''!'",
        format!("{:?}", tree)
    );

KITASHIRAKAWA_Chiyuri_80x100x8_01_Futu.gif
「 ↑ こうだったか☆」

KIFUWARABE_80x100x8_01_Futu.gif
「 お父ん、ルートは1つじゃないよな☆?」

KITASHIRAKAWA_Chiyuri_80x100x8_01_Futu.gif
「 まったくだぜ☆」

impl<T> fmt::Debug for Tree<T>
where
    T: std::fmt::Debug + std::clone::Clone,
{
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        let mut buf = String::new();
        // Multiple root.
        // TODO clone しまくってて重そうだが他に方法はないか?
        for root in self.roots.iter() {
            // println!("(trace.29) chr={:?}", root);
            for chr in root.clone().into_iter() {
                // println!("(trace.31) chr={:?}", chr);
                buf.push_str(&format!("{:?}", chr));
            }
        }
        write!(f, "{}", buf)
    }
}

KITASHIRAKAWA_Chiyuri_80x100x8_01_Futu.gif
「 ↑ イテレーターのクローンを作らずにイテレートする方法が分からん☆」

KIFUWARABE_80x100x8_01_Futu.gif
「 文字列を もう1個 挿入してみようぜ☆? illustration で☆」

    // Sequence.
    let mut seq1 = Sequence::default();
    seq1.push(&vec![
        'H', 'e', 'l', 'l', 'o', ',', ' ', 'W', 'o', 'r', 'l', 'd', '!', '!',
    ]);

OKAZAKI_Yumemi_80x80x8_02_Syaberu.gif
「 ↑ その前に Sequence が ミュータブルなのは気持ち悪くない?」

KITASHIRAKAWA_Chiyuri_80x100x8_01_Futu.gif
「 まったくだぜ☆」

pub struct SequenceBuilder<T> {
    sequence: Vec<T>,
}

#[derive(Clone)]
pub struct SequenceVal<T> {
    sequence: Vec<T>,
    cursor: usize,
}

KITASHIRAKAWA_Chiyuri_80x100x8_01_Futu.gif
「 ↑ Builder と Val に分けて……☆」

    pub fn push<'a>(&'a mut self, raw: &Vec<T>) -> &'a Self {
        self.sequence.extend(raw.clone());
        self
    }

KITASHIRAKAWA_Chiyuri_80x100x8_01_Futu.gif
「 ↑ 自分自身を返せる関数にすることで、ワン・ライナーで書けるようにしようぜ☆」

    pub fn build(&self) -> SequenceVal<T> {
        SequenceVal {
            sequence: self.sequence.clone(),
            cursor: 0,
        }
    }

KITASHIRAKAWA_Chiyuri_80x100x8_01_Futu.gif
「 ↑ ビルド・デザイン・パターンにしておくと 使い慣れてるだろ☆」

    // Sequence.
    let seq1 = SequenceBuilder::default()
        .push(&vec![
            'H', 'e', 'l', 'l', 'o', ',', ' ', 'W', 'o', 'r', 'l', 'd', '!', '!',
        ])
        .build();

KITASHIRAKAWA_Chiyuri_80x100x8_01_Futu.gif
「 ↑ こう書けるようになるぜ☆」

    assert_eq!(
        "'H''e''l''l''o'','' ''W''o''r''l''d''!''!'
'I''l''l''u''s''t''r''a''t''i''o''n'
",
        format!("{:?}", tree)
    );

KITASHIRAKAWA_Chiyuri_80x100x8_01_Futu.gif
「 ↑ アサーションはこんな感じで☆」

KIFUWARABE_80x100x8_01_Futu.gif
「 illust も挿入してみようぜ☆?」

    assert_eq!(
        "'H''e''l''l''o'','' ''W''o''r''l''d''!''!'
'I''l''l''u''s''t''r''a''t''i''o''n'
'I''l''l''u''s''t'
",
        format!("{:?}", tree)
    );

KITASHIRAKAWA_Chiyuri_80x100x8_01_Futu.gif
「 ↑ こうなってしまうと面白みがないよな☆
どういうふうに表示されると良さげ?」

Hell, World!!
Illust
      ration

OKAZAKI_Yumemi_80x80x8_02_Syaberu.gif
「 ↑ こうじゃないの?」

KIFUWARABE_80x100x8_01_Futu.gif
「 まず Sequence をリンクトリストにしろだぜ☆」

pub struct SequenceBuilder<T> {
    sequence: Vec<T>,
    head: Option<Box<SequenceVal<T>>>,
    tail: Option<Box<SequenceVal<T>>>,
}

#[derive(Clone)]
pub struct SequenceVal<T> {
    sequence: Vec<T>,
    cursor: usize,
    head: Option<Box<SequenceVal<T>>>,
    tail: Option<Box<SequenceVal<T>>>,
}

KITASHIRAKAWA_Chiyuri_80x100x8_01_Futu.gif
「 ↑ いきなりツリー状では つらいんで、まずは リングで……☆」

    let seq4 = SequenceBuilder::default()
        .push(&vec!['s', 't', 'a'])
        .build();
    let seq5 = SequenceBuilder::default()
        .push(&vec!['t', 'i', 'o', 'n'])
        .build();

    // Concatination.
    let seq4and5 = SequenceBuilder::concat(&seq4, &seq5);
    assert_eq!("'s''t''a''t''i''o''n'", format!("{:?}", seq4and5));

KITASHIRAKAWA_Chiyuri_80x100x8_01_Futu.gif
「 ↑ 大文字、小文字の違いでつまづいたが、 ignore case 考えるのめんどくさいんで、全部小文字で入力しようぜ☆?」

KIFUWARABE_80x100x8_01_Futu.gif
「 ↑ リンクトリストを作れ、と言ったのに お父ん、 コンカッチしたな☆!」

KITASHIRAKAWA_Chiyuri_80x100x8_01_Futu.gif
「 ↑ あっ、そうか……☆」

Rustでリンクトリスト

Rustでdoubly linked list

KITASHIRAKAWA_Chiyuri_80x100x8_01_Futu.gif
「 ↑ Rust言語で Linked List 作るの めっちゃ工夫が要る……☆」

20201104blog14.png

KITASHIRAKAWA_Chiyuri_80x100x8_01_Futu.gif
「 ↑ わたしは リンクトリストは こんなもんぐらいに思っているが、 エグザンプルはもうすこし凝っているようだぜ☆」

20201104blog15.png

KITASHIRAKAWA_Chiyuri_80x100x8_01_Futu.gif
「 ↑ まだ全部を飲み込めていないが、作りながら分かっていこうぜ☆」

use std::cell::RefCell;
use std::rc::Rc;

KITASHIRAKAWA_Chiyuri_80x100x8_01_Futu.gif
「 ↑ 新しく出てくるのは この2つで、普段はライブラリが中でコソコソやるようなことで、
相互参照するときぐらいにしか お目にかからないものらしい☆」

        Rc::new(RefCell::new(BananaVal {
            head: None,
            tail: None,
        }))

KITASHIRAKAWA_Chiyuri_80x100x8_01_Futu.gif
「 ↑ インスタンスは Rc<RefCell<Banana<T>>> のように、常に二重にラッピングされると考えろだぜ☆」

type SequenceRef<T> = Rc<RefCell<BananaVal<T>>>;

KITASHIRAKAWA_Chiyuri_80x100x8_01_Futu.gif
「 ↑ そこで型名を定義して楽するのが手筋☆」

KITASHIRAKAWA_Chiyuri_80x100x8_01_Futu.gif
「 次に、イテレーターも再実装しなくてはいけないようだぜ☆」

pub struct Iter<T> {
    current: Option<SequenceRef<T>>,
}

pub struct Banana<T> {
    /// イテレーターで使います。
    length: usize,
}

impl<T> Banana<T> {
    /// イテレーターで使います。
    pub fn len(&self) -> usize {
        self.length
    }

    pub fn iter(&self) -> Iter<T> {
        Iter {
            current: if self.len() == 0 {
                None
            } else {
                Some(Rc::clone(&self.head.as_ref().unwrap()))
            },
        }
    }
}

KITASHIRAKAWA_Chiyuri_80x100x8_01_Futu.gif
「 ↑ イテレーターを実装するだけのために、いくつか下準備が要るぜ☆」

<書きかけ>

何度でもクリック!→

むずでょ@きふわらべ第29回世界コンピューター将棋選手権一次予選36位

光速のアカウント凍結されちゃったんで……。ゲームプログラムを独習中なんだぜ☆電王戦IIに出た棋士もコンピューターもみんな好きだぜ☆▲(パソコン将棋)WCSC29一次予選36位、SDT5予選42位▲(パソコン囲碁)AI竜星戦予選16位

Crieitは個人で開発中です。 興味がある方は是非記事の投稿をお願いします! どんな軽い内容でも嬉しいです。
なぜCrieitを作ろうと思ったか

また、「こんな記事が読みたいけど見つからない!」という方は是非記事投稿リクエストボードへ!

こじんまりと作業ログやメモ、進捗を書き残しておきたい方はボード機能をご利用ください!

ボードとは?

むずでょ@きふわらべ第29回世界コンピューター将棋選手権一次予選36位 の最近の記事