パトリシア・ツリーを作ろうぜ☆（＾～＾）？

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

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

「　さっさと作り終えなさい」

「　↑ char と string は 普段から使ってるな関係だよな☆」

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

「　じゃあ、 illust と illustration を　つないでみてよ」

「　↑ こうだな☆」

「　文字が切れるのは　どういう仕組みだぜ☆？」

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

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

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

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

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

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

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

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

「　End は どうやって区別するんだぜ☆？」

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

「　パトリシア・ツリーを作る前に、 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>>>,
}

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

「　じゃあ、 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>) {}
}

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

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

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

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

「　じゃあ それで☆」

「　TreeShapedRelation は単に Tree でよくない？」

「　まったくだぜ☆」

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.");
}

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

「　Sequence 型で渡したくならない？」

「　言われてみれば☆」

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.");
}

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

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

「　↑　シーケンスにイテレーター用の 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;
    }
}

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

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)
    }
}

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

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

「　↑　失敗☆」

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

「　↑　こうだったか☆」

「　お父ん、ルートは１つじゃないよな☆？」

「　まったくだぜ☆」

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)
    }
}

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

「　文字列を　もう１個　挿入してみようぜ☆？ illustration で☆」

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

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

「　まったくだぜ☆」

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

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

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

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

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

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

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

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

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

    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)
    );

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

「　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)
    );

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

Hell, World!!
Illust
      ration

「　↑ こうじゃないの？」

「　まず 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>>>,
}

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

    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));

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

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

「　↑ あっ、そうか……☆」

Rustでリンクトリスト

Rustでdoubly linked list

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

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

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

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

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

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

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

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

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

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

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()))
            },
        }
    }
}

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

＜書きかけ＞