Rust 親子関係を持つレコードを木構造に変換する

以下のような親子(id -> parent)関係のあるレコードを、

[
  { id: "1", parent: "", name: "/", path: "/", child_count: 0, depth: 1 }, 
  { id: "2", parent: "1", name: "home", path: "/home/", child_count: 0, depth: 2 },
  { id: "3", parent: "2", name: "user1", path: "/home/user1/", child_count: 0, depth: 3 },
  { id: "4", parent: "2", name: "user2", path: "/home/user2/", child_count: 0, depth: 3 },
  { id: "6", parent: "4", name: "workspace", path: "/home/user2/workspace/", child_count: 0, depth: 4 },
  { id: "5", parent: "2", name: "user3", path: "/home/user3/", child_count: 0, depth: 3 },
  { id: "8", parent: "1", name: "opt", path: "/opt/", child_count: 0, depth: 2 },
  { id: "10", parent: "8", name: "oracle", path: "/opt/oracle/", child_count: 0, depth: 3 },
  { id: "7", parent: "1", name: "var", path: "/var/", child_count: 0, depth: 2 },
  { id: "9", parent: "7", name: "logs", path: "/var/logs/", child_count: 0, depth: 3 },
  { id: "12", parent: "9", name: "app", path: "/var/logs/app/", child_count: 0, depth: 4 },
  { id: "11", parent: "9", name: "httpd", path: "/var/logs/httpd/", child_count: 0, depth: 4 }]

このようなオブジェクトの入れ子関係に変換する。

Directory { id: "1", name: "/", parent: "", path: "", depth: 1, children: [
  Directory { id: "2", name: "home", parent: "1", path: "1", depth: 2, children: [
    Directory { id: "3", name: "user1", parent: "2", path: "2", depth: 3, children: [] }, 
    Directory { id: "4", name: "user2", parent: "2", path: "2", depth: 3, children: [
      Directory { id: "6", name: "workspace", parent: "4", path: "4", depth: 4, children: [] }] }, 
    Directory { id: "5", name: "user3", parent: "2", path: "2", depth: 3, children: [] }] },
  Directory { id: "8", name: "opt", parent: "1", path: "1", depth: 2, children: [
    Directory { id: "10", name: "oracle", parent: "8", path: "8", depth: 3, children: [] }] }, 
  Directory { id: "7", name: "var", parent: "1", path: "1", depth: 2, children: [
    Directory { id: "9", name: "logs", parent: "7", path: "7", depth: 3, children: [
      Directory { id: "12", name: "app", parent: "9", path: "9", depth: 4, children: [] }, 
      Directory { id: "11", name: "httpd", parent: "9", path: "9", depth: 4, children: [] }] }] }] }

実装例

入れ子構造とする構造体の定義。childrenフィールドを可変としなければならない。

#[derive(Debug, Clone)]
pub struct Directory {
    id: String,
    name: String,
    parent: String,
    path: String,
    depth: i32,
    children: Vec<Directory>
}
impl Directory {
    fn add_node(&mut self, node: Directory) {
        if self.id == node.parent {
            self.children.push(node);
        }
        else {
            for child in self.children.iter_mut() {
                child.add_node(node.clone());
            }
        }
    }
}

childrenはVecでサイズが決定可能なので、Boxに包む必要はないようです。

構造体のフィールドを可変に扱う

引数に&mut selfととることで、フィールドを可変に扱うことが出来ました。

iteratorで可変参照として要素を取得する

今回、一番ハマったのがここで、iter()で返された要素はイミュータブルなので、どうやって探索&該当ノードにaddするか、午前2時から2時間くらい彷徨った(^_^;)

iterで取り出した要素をmutableにするにはiter_mut()を使う。

for child in self.children.iter_mut() {
  child.add_node(node.clone());
}

一連の要素をイテレータで処理する - The Rust Programming Language 日本語版

add_node()メソッドにレコードを渡す

あとはrecordをDirectoryに仕上げてloopでadd_nodeしていけばよい。

// iteratorも可変参照を必要とする
let mut record_iter = record.iter();
let record = record_iter.next().unwrap();
let mut root_directory = Directory {
    id: record.id.clone(),
    name: record.name.clone(),
    parent: record.parent.clone(),
    path: record.parent.clone(),
    depth: record.depth,
    children: Vec::new(),
};
for (i, record) in record_iter.iter().enumerate() {
    let node = Directory {
        id: record.id.clone(),
        name: record.name.clone(),
        parent: record.parent.clone(),
        path: record.parent.clone(),
        depth: record.depth,
        children: Vec::new(),
    };
    root_directory.add_node(node);
}

なんか2度、Directory{}初期化する文が出てきちゃった(^_^;) 上手なやり方ないかな...

所有権と可変参照難しい(^_^;) Rust書いてて楽しいけど、今日はさすがに疲れた。