3
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 5 years have passed since last update.

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

Last updated at Posted at 2018-08-24

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

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

#Version

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

#1章 イントロダクション

#2章 配列を使ったリスト
##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
編集中
#さいごに
ちまちま書いていこうかなと思いま

3
1
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
3
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?