Rust初心者によるデータ構造

はじめに

Rust初心者によるものなので間違いや効率の悪いことをしていると思います．そこらへんは指摘してくださると助かります．指摘以外の意見などもお願いします．ぶっちゃけデータ構造の理解というよりもRustの理解です．

モチベーション

• これを読むのに疲れた(文字列ぐらいまで読んだ)．
• プログラミングRustを読むのに疲れた(11章の途中まで読んだ)．
• 手を動かしながらできていい感じの教材見つけた．これの擬似コード版を見ながらやる．

Version

% rustc --version
rustc 1.28.0 (9634041f0 2018-07-30)

１章　イントロダクション

略

２章　配列を使ったリスト

ArrayStack

勉強のためにtraitを使います．Haskellで言う型クラスだと認識しています．

main.rs

pub trait ArrayStack<T:Clone> {
    fn get_item(&self, index: usize) -> Result<T, String>; 
    fn set_item(&mut self, index: usize, item: T) -> Result<T, String>;
    fn add_item(&mut self, index: usize, item: T) -> Result<(), String>;
    fn remove_item(&mut self, index: usize) -> Result<T, String>;
}

実装です．データ構造はVecを使います．memが便利だと気づきました．範囲外の場合にはErrを返すようにしました．既存のメソッドを使っていて(insertとか)，ずるい気がしましたが良しとします．

main.rs

use std::mem;

impl<T: Clone> ArrayStack<T> for Vec<T> {
    fn get_item(&self, index: usize) -> Result<T, String> {
        if self.len() <= index { return Err("out of bounds".to_string()); }
        Ok(self[index].clone())
    }
    fn set_item(&mut self, index: usize, item: T) -> Result<T, String> {
        if self.len() <= index { return Err("out of bounds".to_string()); }
        let old_item = mem::replace(&mut self[index], item);
        Ok(old_item)
    }
    fn add_item(&mut self, index: usize, item: T) -> Result<(), String> {
        if self.len() < index { return Err("out of bounds".to_string()); }
        self.insert(index, item);
        Ok(())
    } 
    fn remove_item(&mut self, index: usize) -> Result<T, String> {
        if self.len() <= index { return Err("out of bounds".to_string()); }
        Ok(self.remove(index)) 
    }
}

さらに勉強のためにテストコードも書きます．

main.rs

#[cfg(test)]
mod array_stack_tests {
    use super::*;
    #[test]
    fn get_item_test() {
        let list = vec![0, 1, 2, 2, 4, 5];
        assert_eq!(list.get_item(4), Ok(4));
        assert_eq!(list.get_item(10), Err("out of bounds".to_string()));
        assert_eq!(list, [0, 1, 2, 2, 4, 5]);
    }
    #[test]
    fn set_item_test() {
        let mut list = vec![0, 1, 2, 2, 4, 5];
        assert_eq!(list.set_item(3, 3), Ok(2));
        assert_eq!(list.set_item(10, 10), Err("out of bounds".to_string()));
        assert_eq!(list, [0, 1, 2, 3, 4, 5]);
    }
    #[test]
    fn add_item_test() {
        let mut list = vec![0, 1, 2, 3, 5];
        assert_eq!(list.add_item(4, 4), Ok(()));
        assert_eq!(list.add_item(10, 10), Err("out of bounds".to_string()));
        assert_eq!(list, vec![0, 1, 2, 3, 4, 5]);
    }
    #[test]
    fn remove_item_test() {
        let mut list = vec![0, 1, 2, 2, 3, 4];
        assert_eq!(list.remove_item(2), Ok(2));
        assert_eq!(list.remove_item(10), Err("out of bounds".to_string()));
        assert_eq!(list, vec![0, 1, 2, 3, 4]);
    }
}

ArrayQueue

VecDequeが便利そうです．pop_back()やpush_front()などもあります．

main.rs

use std::collections::VecDeque;
pub trait ArrayQueue<T: Clone> {
    fn add_item(&mut self, item: T);
    fn remove_item(&mut self) -> Result<T, String>;
}
impl<T: Clone> ArrayQueue<T> for VecDeque<T> {
    fn add_item(&mut self, item: T) {
        self.push_back(item);
    }
    fn remove_item(&mut self) -> Result<T, String> {
        match self.pop_front() {
            Some(x) => Ok(x),
            None => Err("No item".to_string()),
        }
    }
}

テストコード

main.rs

#[cfg(test)]
mod array_queue_tests {
    use super::*;
    #[test]
    fn add_item_test() {
        let mut vec_q = VecDeque::from(vec![0, 1, 2, 3, 4]);
        vec_q.add_item(5);
        assert_eq!(vec_q, vec![0, 1, 2, 3, 4, 5]);
    }
    #[test]
    fn remove_item_test() {
        let mut vec_q = VecDeque::from(vec![0, 1, 2, 3, 4]);
        let mut vec_q_short = VecDeque::from(vec![0]);
        assert_eq!(vec_q.remove_item(), Ok(0));
        assert_eq!(vec_q_short.remove_item(), Ok(0));
        assert_eq!(vec_q_short.remove_item(), Err("No item".to_string()));
        assert_eq!(vec_q, VecDeque::from(vec![1, 2, 3, 4]));
    }
}

DualArrayDeque

編集中

さいごに

ちまちま書いていこうかなと思いま