RustでBinary treeの left, right のポインターに使うデータ型を考える

概要

Option<Rc<RefCell<_>>>を使うか、RefCell<Option<Rc<_>>> を使うか？

俺は雰囲気で Rust を書いている … 訳ではない人はこれの違いが分かるはずだ。……いや分からんし…という人のための整理記事です。

A: Option → Rc → RefCell?

pub struct TreeNode<K> {
    key: K,
    left: Option<Rc<RefCell<TreeNode<K>>>>,
    right: Option<Rc<RefCell<TreeNode<K>>>>,
}

B: RefCell → Option → Rc?

pub struct TreeNode<K> {
    key: K,
    left: RefCell<Option<Rc<TreeNode<K>>>>,
    right: RefCell<Option<Rc<TreeNode<K>>>>,
}

C: Rc → RefCell → Rc?

pub struct TreeNodes<K> {
    left: Option<Rc<TreeNode<K>>>,
    right: Option<Rc<TreeNode<K>>>,
}

pub struct TreeNode<K> {
    key: K,
    children: RefCell<TreeNodes<K>>,
}

ちょっと気になった記事

• 『みんなのデータ構造』を読んで Rust で実装した - Qiita

なお、後ほど木構造を実装していて思ったのですが、RefCell>>> のような型で実装したほうがもっとスッキリかけたのではないかと考えています。

スッキリとはスッキリしない書き方だ……。

ポイント解説

基本は、変更不要なものに RefCell をつける必要はないこと、変更が必要な操作対象には RefCell をつけること。

• 効果的なパターンと無意味なパターンがあるものの Rc と RefCell の関係は独立している
  • Rc ... ツリーを巡回のカーソル用途
    ツリーを巡回する際のカーソルは複製できる必要はあって、自然とループを Rc 主体に回すことになる。Rc がないと比較的いびつなアルゴリズムを再発明する必要性に迫られる。
  • RefCell ... 更新したいものに付与する。初期化した時点からの不変なものにはつける必要はない
• Option<Rc<_>> の関係は、自己参照型のデータ構造では参照カウントのカウント数の調整で重要な役割を果たす

A と B は基本的には等価(Rc起点で見ると分かる)だが、次の違いが実装に表れることもある。

• left/right のアクセスに borrow()/borrow_mut()が必要かどうか
• Noneのチェックに borrow()/borrow_mut()が必要かどうか

基本 borrow()による参照が一時的で、if let/while letなどブロック全体に借用チェックの影響が及ぶため。
RefMut を使う前提において、最終的にはパターンAのほうが実装が簡潔であった。
insert()の末尾のみ可変借用で良いという要件を実現しやすいのが可変借用と不変借用が混在できるパターンBでした。
(今回、実装に加えていない remove やらRed Black treeのノードの張替えを伴うものを対象とすると、また評価は変わるかもしれません。その場合はパターンCのような形態が扱いやすいかもしれませんね。)

パターンA: Option<Rc<RefCell<TreeNode<K>>>>

pub struct TreeNode<K> {
    key: K,
    left: Option<Rc<RefCell<TreeNode<K>>>>,
    right: Option<Rc<RefCell<TreeNode<K>>>>,
}

今回のツリーはキー自体は更新する必要がないから、 RefCell<TreeNode<K>> はさほど意味はない。
ただ、実装自体のコツがつかめれば、結果的にそれほど悪くもない。

Option<Rc<**RefCell**\>>> → Option\>> のように RefCell を取り除くと変更すると、
left/rightのノードに追加するときに (素朴な実装では) Rc 内のOption型に対して可変借用ができない問題が起きる(NG例1)。

そのため、正確に言うと キーを更新するための RefCell は不要 だが、Option型を更新するための RefCell は必要 ということになる。なお、これは必要性を説いているだけでスッキリ書けるかどうかは、また別の話。

上記の Option のみ可変が必要という要件を直接的に表現するとパターンB に落ち着く。

pub struct TreeNode<K> {
    key: K,
    left: RefCell<Option<Rc<TreeNode<K>>>>,
    right: RefCell<Option<Rc<TreeNode<K>>>>,
}

NG例1: Option<Rc<\>>

pub struct TreeNode<K> {
    key: K,
    left: Option<Rc<TreeNode<K>>>,
    right: Option<Rc<TreeNode<K>>>,
}

impl<K> TreeNode<K> {
    pub fn new(key: K) -> Self {
        TreeNode {
            key,
            left: None,
            right: None,
        }
    }
}

impl<K: Ord> BTree<K> {
    pub fn insert(&mut self, key: K) {
        if self.head.is_none() {
            self.head.replace(Rc::new(TreeNode::new(key)));
            return;
        }
        let cur_ref: &mut Rc<TreeNode<K>>;
        cur_ref = self.head.as_mut().unwrap();

        let mut cur: Rc<TreeNode<K>>;
        cur = Rc::clone(cur_ref);

        loop {
            let some_next_rc_ref: &Option<Rc<TreeNode<K>>>;
            if cur.key.cmp(&key) == Ordering::Greater {
                some_next_rc_ref = &cur.left;
            } else {
                some_next_rc_ref = &cur.right;
            }
            if let Some(next_rc_ref) = some_next_rc_ref {
                cur = Rc::clone(next_rc_ref);
                continue;
            }

            if cur.key.cmp(&key) == Ordering::Greater {
                Rc::get_mut(&mut cur).unwrap().left.replace(
                    Rc::new(TreeNode::new(key))
                ); // NG: Strong count が 2 あるため失敗
            } else {
                Rc::get_mut(&mut cur).unwrap().right.replace(
                    Rc::new(TreeNode::new(key))
                ); // NG: Strong count が 2 あるため失敗
            }
            return;
        }
    }
}

パターンB: RefCell<Option<Rc<TreeNode<K>>>>

pub struct TreeNode<K> {
    key: K,
    left: RefCell<Option<Rc<TreeNode<K>>>>,
    right: RefCell<Option<Rc<TreeNode<K>>>>,
}

パターンAの説明で触れたとおり、ツリーのアクセス要件に無駄なく合致したデータ構造です。

• RefCell<Option<_>> ... Option型に対して一時的に可変借用する
• Rc<TreeNode<K> ... ノード自体は初期化した時点から変更はしない構造
• Option<Rc<TreeNode<K>>> ... ノードを置き換えることは許可する (ノード追加時の replace 操作)

パターンC: RefCell<Option<Rc<TreeNode<K>>>>

パターンAの説明で触れたとおり、ツリーのアクセス要件に無駄なく合致したデータ構造です。
Rustのチュートリアルのツリーの例もこの形だったと思います(あちらは Vec を使っていた)。

pub struct TreeNode<K> {
    key: K,
    left: Rc<RefCell<Option<TreeNode<K>>>>,
    right: Rc<RefCell<Option<TreeNode<K>>>>,
}

付録1: 実装例

全体的に、構造が単純であることがコードを単純化に寄与するのではなく、操作に対して無駄なく必要な制約を課すことが単純化につながる。

パターンA: Option<Rc<RefCell<TreeNode<K>>>>

use std::fmt::{self};
use std::rc::Rc;
use std::cell::{RefCell, RefMut};
use std::cmp::Ordering;

pub struct TreeNode<K> {
    key: K,
    left: Option<Rc<RefCell<TreeNode<K>>>>,
    right: Option<Rc<RefCell<TreeNode<K>>>>,
}

impl<K> TreeNode<K> {
    pub fn new(key: K) -> Self {
        TreeNode {
            key,
            left: None,
            right: None,
        }
    }
}

impl<T: fmt::Debug> fmt::Debug for TreeNode<T> {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        match (self.left.as_ref(), self.right.as_ref()) {
            (None, None) => {
                write!(f, "TreeNode(Nil,{:?},Nil)", self.key)
            },
            (Some(left), Some(right)) => {
                write!(f,
                    "{:?}, TreeNode({:?},{:?},{:?}), {:?}",
                    left.borrow(), left.borrow().key, self.key, right.borrow().key, right.borrow()
                )
            },
            (None, Some(right)) => {
                write!(f,
                    "TreeNode(Nil,{:?},{:?}), {:?}",
                    self.key, right.borrow().key, right.borrow()
                )
            },
            (Some(left), None) => {
                write!(f,
                    "{:?}, TreeNode({:?},{:?},Nil)",
                    left.borrow(), left.borrow().key, self.key
                )
            },
        }
    }
}

# [derive(Default)]
pub struct BTree<K> {
    head: Option<Rc<RefCell<TreeNode<K>>>>,
}

impl<K> BTree<K> {
    pub fn new() -> Self {
        BTree {
            head: None,
        }
    }
}

impl<K: Ord> BTree<K> {
    /// # Examples
    ///
    /// ```
    /// use bt_opt_rc_refcell::BTree;
    /// let mut tree: BTree<&str> = Default::default();
    /// tree.insert("E");
    /// tree.insert("A");
    /// tree.insert("S");
    /// println!("{:?}", &tree);
    /// ```
    pub fn insert(&mut self, key: K) {
        if self.head.is_none() {
            self.head.replace(
                Rc::new(RefCell::new(TreeNode::new(key)))
            );
            return;
        }
        let cur_ref: &Rc<RefCell<TreeNode<K>>>;
        cur_ref = self.head.as_ref().unwrap();

        let mut cur: Rc<RefCell<TreeNode<K>>>;
        cur = Rc::clone(cur_ref);

        loop {
            let cur_ref_mut: RefMut<TreeNode<K>> = cur.borrow_mut();
            let mut some_rc_ref_mut: RefMut<Option<Rc<RefCell<TreeNode<K>>>>>;

            if cur_ref_mut.key.cmp(&key) == Ordering::Greater {
                some_rc_ref_mut = RefMut::map(cur_ref_mut, |n| &mut n.left);
            } else {
                some_rc_ref_mut = RefMut::map(cur_ref_mut, |n| &mut n.right);
            }

            if some_rc_ref_mut.is_none() {
                some_rc_ref_mut.replace(
                    Rc::new(RefCell::new(TreeNode::new(key)))
                );
                return;
            }

            let next_rc_ref = Rc::clone(some_rc_ref_mut.as_ref().unwrap());
            drop(some_rc_ref_mut);
            cur = next_rc_ref;
        }
    }
}

impl<K: Clone> BTree<K> {
    /// # Examples
    ///
    /// ```
    /// use bt_opt_rc_refcell::BTree;
    /// let mut tree: BTree<&str> = Default::default();
    /// tree.insert("E");
    /// tree.insert("A");
    /// tree.insert("S");
    /// assert_eq!(tree.to_vec_in_order(), vec!["A", "E", "S"]);
    /// ```
    pub fn to_vec_in_order(&self) -> Vec<K> {
        if self.head.is_none() {
            return Vec::new();
        }
        let cur_ref: &Option<Rc<RefCell<TreeNode<K>>>>;
        cur_ref = &self.head;

        let mut stack: Vec<Rc<RefCell<TreeNode<K>>>>;
        stack = Vec::new();
        let mut cur = Some(Rc::clone(cur_ref.as_ref().unwrap()));

        let mut results: Vec<K> = vec!();

        'outer: loop {
            // Traverse the subtree on the left while adding nodes to the stack.
            while cur.is_some() {
                stack.push(Rc::clone(cur.as_ref().unwrap()));
                if Rc::clone(cur.as_ref().unwrap()).borrow().left.is_none() {
                    cur = None;
                } else {
                    // cur = Rc::clone(cur.as_ref().unwrap()).borrow().left;
                    cur = Some(
                        Rc::clone(
                            Rc::clone(cur.as_ref().unwrap()).borrow().left.as_ref().unwrap()
                        )
                    )
                }
            }

            // It pops elements from the stack and continues to output,
            // returning to traversing the left side
            // if a node is found on the current right side.
            loop {
                let cur_right = match stack.pop() {
                    Some(cur_right) => cur_right,
                    None => break 'outer,
                };
                results.push(cur_right.borrow().key.clone());
                if cur_right.borrow().right.is_some() {
                    cur = Some(Rc::clone(cur_right.borrow().right.as_ref().unwrap()));
                    continue 'outer;
                }
            }
        }
        results
    }
}

impl<T: fmt::Debug> fmt::Debug for BTree<T> {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        match &self.head {
            None => write!(f, "BTree {{}}"),
            Some(head) => write!(f, "BTree={{{:?}}}", head.borrow()),
        }
    }
}

# [cfg(test)]
mod tests;

パターンAの亜種: Option<Rc<TreeNode<K>>>

Optionの可変借用をどう実現するかで悩むことになる構造。
基本的には、 初期化した時点のツリーから不変であることを意味する構造 である。

親ノードが子ノードに対して参照カウントを1個つ持ち、ノードの巡回のカーソルに1個持つので、一時的に可変借用をする Rc::get_mut は失敗するので、ある意味、宣言した構造通り、不変である。

追加対象のノードを先読みをすれば可変借用を得られるが、どちらかというとそれの操作はツリーの再構築に近い。
以下の例では、今回の操作では実際には安全なので unsafe で実現している。

use std::fmt::{self};
use std::rc::Rc;
use std::cmp::Ordering;

pub struct TreeNode<K> {
    key: K,
    left: Option<Rc<TreeNode<K>>>,
    right: Option<Rc<TreeNode<K>>>,
}

impl<K> TreeNode<K> {
    pub fn new(key: K) -> Self {
        TreeNode {
            key,
            left: None,
            right: None,
        }
    }
}

impl<T: fmt::Debug> fmt::Debug for TreeNode<T> {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        match (self.left.as_ref(), self.right.as_ref()) {
            (None, None) => {
                write!(f, "TreeNode(Nil,{:?},Nil)", self.key)
            },
            (Some(left), Some(right)) => {
                write!(f,
                    "{:?}, TreeNode({:?},{:?},{:?}), {:?}",
                    left, left.key, self.key, right.key, right
                )
            },
            (None, Some(right)) => {
                write!(f,
                    "TreeNode(Nil,{:?},{:?}), {:?}",
                    self.key, right.key, right
                )
            },
            (Some(left), None) => {
                write!(f,
                    "{:?}, TreeNode({:?},{:?},Nil)",
                    left, left.key, self.key
                )
            },
        }
    }
}

# [derive(Default)]
pub struct BTree<K> {
    head: Option<Rc<TreeNode<K>>>,
}

impl<K> BTree<K> {
    pub fn new() -> Self {
        BTree {
            head: None,
        }
    }
}

impl<K: Ord> BTree<K> {
    /// # Examples
    ///
    /// ```
    /// use bt_opt_rc::BTree;
    /// let mut tree: BTree<&str> = Default::default();
    /// tree.insert("E");
    /// tree.insert("A");
    /// tree.insert("S");
    /// println!("{:?}", &tree);
    /// ```
    pub fn insert(&mut self, key: K) {
        if self.head.is_none() {
            self.head.replace(Rc::new(TreeNode::new(key)));
            return;
        }
        let cur_ref: &mut Rc<TreeNode<K>>;
        cur_ref = self.head.as_mut().unwrap();

        let mut cur: Rc<TreeNode<K>>;
        cur = Rc::clone(cur_ref);

        loop {
            let some_next_rc_ref: &Option<Rc<TreeNode<K>>>;
            if cur.key.cmp(&key) == Ordering::Greater {
                some_next_rc_ref = &cur.left;
            } else {
                some_next_rc_ref = &cur.right;
            }
            if let Some(next_rc_ref) = some_next_rc_ref {
                cur = Rc::clone(next_rc_ref);
                continue;
            }

            assert_eq!(2, Rc::strong_count(&cur));
            unsafe {
                let ptr = Rc::into_raw(cur);
                Rc::decrement_strong_count(ptr);
                cur = Rc::from_raw(ptr);
            }
            assert_eq!(1, Rc::strong_count(&cur));
            if cur.key.cmp(&key) == Ordering::Greater {
                Rc::get_mut(&mut cur).unwrap().left.replace(
                    Rc::new(TreeNode::new(key))
                );
            } else {
                Rc::get_mut(&mut cur).unwrap().right.replace(
                    Rc::new(TreeNode::new(key))
                );
            }
            unsafe {
                let ptr = Rc::into_raw(cur);
                Rc::increment_strong_count(ptr);
                cur = Rc::from_raw(ptr);
            }
            assert_eq!(2, Rc::strong_count(&cur));
            return;
        }
    }
}

impl<K: Clone> BTree<K> {
    /// # Examples
    ///
    /// ```
    /// use bt_opt_rc::BTree;
    /// let mut tree: BTree<&str> = Default::default();
    /// tree.insert("E");
    /// tree.insert("A");
    /// tree.insert("S");
    /// assert_eq!(tree.to_vec_in_order(), vec!["A", "E", "S"]);
    /// ```
    pub fn to_vec_in_order(&self) -> Vec<K> {
        if self.head.is_none() {
            return Vec::new();
        }
        let cur_ref: &Option<Rc<TreeNode<K>>>;
        cur_ref = &self.head;

        let mut stack: Vec<Rc<TreeNode<K>>>;
        stack = Vec::new();
        let mut cur = Some(Rc::clone(cur_ref.as_ref().unwrap()));

        let mut results: Vec<K> = vec!();

        'outer: loop {
            // Traverse the subtree on the left while adding nodes to the stack.
            while cur.is_some() {
                stack.push(Rc::clone(cur.as_ref().unwrap()));
                if Rc::clone(cur.as_ref().unwrap()).left.is_none() {
                    cur = None;
                } else {
                    // cur = Rc::clone(cur.as_ref().unwrap()).left;
                    cur = Some(
                        Rc::clone(
                            Rc::clone(cur.as_ref().unwrap()).left.as_ref().unwrap()
                        )
                    )
                }
            }

            // It pops elements from the stack and continues to output,
            // returning to traversing the left side
            // if a node is found on the current right side.
            loop {
                let cur_right = match stack.pop() {
                    Some(cur_right) => cur_right,
                    None => break 'outer,
                };
                results.push(cur_right.key.clone());
                if cur_right.right.is_some() {
                    cur = Some(Rc::clone(cur_right.right.as_ref().unwrap()));
                    continue 'outer;
                }
            }
        }
        results
    }
}

impl<T: fmt::Debug> fmt::Debug for BTree<T> {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        match &self.head {
            None => write!(f, "BTree={{}}"),
            Some(head) => write!(f, "BTree={{{:?}}}", head),
        }
    }
}

# [cfg(test)]
mod tests;

パターンB: RefCell<Option<Rc<TreeNode<K>>>>

insert についてみて見ます。

パターンA と比較して特徴的な点

• ノード追加以外の箇所は可変借用をせずに済んでいる
  パターンAでは全体が RefMut の中にあった (DB的な見方をすれば SELECT for UPDATE みたいな感じ)

パターンA と比較して改善された点

• left, right のアクセスに RefCell が挟まれないことでポインターの取得箇所が簡潔になっている

use std::fmt::{self};
use std::rc::Rc;
use std::cell::RefCell;
use std::cmp::Ordering;

pub struct TreeNode<K> {
    key: K,
    left: RefCell<Option<Rc<TreeNode<K>>>>,
    right: RefCell<Option<Rc<TreeNode<K>>>>,
}

impl<K> TreeNode<K> {
    pub fn new(key: K) -> Self {
        TreeNode {
            key,
            left: RefCell::new(None),
            right: RefCell::new(None),
        }
    }
}

impl<T: fmt::Debug> fmt::Debug for TreeNode<T> {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        match (self.left.borrow().clone(), self.right.borrow().clone()) {
            (None, None) => {
                write!(f, "TreeNode(Nil,{:?},Nil)", self.key)
            },
            (Some(ref left), Some(ref right)) => {
                write!(f,
                    "{:?}, TreeNode({:?},{:?},{:?}), {:?}",
                    left, left.key, self.key, right.key, right
                )
            },
            (None, Some(ref right)) => {
                write!(f,
                    "TreeNode(Nil,{:?},{:?}), {:?}",
                    self.key, right.key, right
                )
            },
            (Some(ref left), None) => {
                write!(f,
                    "{:?}, TreeNode({:?},{:?},Nil)",
                    left, left.key, self.key
                )
            },
        }
    }
}

# [derive(Default)]
pub struct BTree<K> {
    head: RefCell<Option<Rc<TreeNode<K>>>>,
}

impl<K: Ord> BTree<K> {
    /// # Examples
    ///
    /// ```
    /// use bt_refcell_opt_rc::kc::BTree;
    /// let mut tree: BTree<&str> = Default::default();
    /// tree.insert("E");
    /// tree.insert("A");
    /// tree.insert("S");
    /// println!("{:?}", &tree);
    /// ```
    pub fn insert(&self, key: K) {
        if self.head.borrow().as_ref().is_none() {
            self.head.borrow_mut().replace(
                Rc::new(TreeNode::new(key))
            );
            return;
        }
        let cur_cell_ref = self.head.borrow();
        let cur_ref: &Rc<TreeNode<K>>;
        cur_ref = cur_cell_ref.as_ref().unwrap();

        let mut cur: Rc<TreeNode<K>> = Rc::clone(cur_ref);
        drop(cur_cell_ref);

        loop {
            let cur_cell_ref = match cur.key.cmp(&key) {
                Ordering::Greater => &cur.left,
                _ => &cur.right,
            };
            if cur_cell_ref.borrow().is_none() {
                cur_cell_ref.replace(
                    Some(Rc::new(TreeNode::new(key))
                ));
                return;
            }
            let work: Rc<TreeNode<K>> = Rc::clone(
                cur_cell_ref.borrow().as_ref().unwrap()
            );
            cur = work;
        }
    }
}

impl<K: Clone> BTree<K> {
    /// # Examples
    ///
    /// ```
    /// use bt_refcell_opt_rc::kc::BTree;
    /// let mut tree: BTree<&str> = Default::default();
    /// tree.insert("E");
    /// tree.insert("A");
    /// tree.insert("S");
    /// assert_eq!(tree.to_vec_in_order(), vec!["A", "E", "S"]);
    /// ```
    pub fn to_vec_in_order(&self) -> Vec<K> {
        if self.head.borrow().is_none() {
            return Vec::new();
        }
        let cur_ref: &RefCell<Option<Rc<TreeNode<K>>>>;
        cur_ref = &self.head;

        let mut stack: Vec<Rc<TreeNode<K>>>;
        stack = Vec::new();
        let mut cur = Some(Rc::clone(cur_ref.borrow().as_ref().unwrap()));

        let mut results: Vec<K> = vec!();

        'outer: loop {
            // Traverse the subtree on the left while adding nodes to the stack.
            while cur.is_some() {
                if let Some(cur_rc_ref) = &cur {
                    stack.push(Rc::clone(cur_rc_ref));
                    match Rc::clone(cur_rc_ref).left.borrow().as_ref() {
                        Some(left_rc_ref) => {
                            cur = Some(Rc::clone(left_rc_ref));
                        },
                        None => {
                            cur = None;
                        }
                    }
                }
            }

            // It pops elements from the stack and continues to output,
            // returning to traversing the left side
            // if a node is found on the current right side.
            loop {
                let cur_right = match stack.pop() {
                    Some(cur_right) => cur_right,
                    None => break 'outer,
                };

                results.push(cur_right.key.clone());
                if cur_right.right.borrow().is_some() {
                    cur = Some(
                        Rc::clone(cur_right.right.borrow().as_ref().unwrap())
                    );
                    continue 'outer;
                }
            }
        }
        results
    }
}

impl<T: fmt::Debug> fmt::Debug for BTree<T> {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        match self.head.borrow().as_ref() {
            None => write!(f, "BTree {{}}"),
            Some(head) => write!(f, "BTree={{{:?}}}", head),
        }
    }
}

# [cfg(test)]
mod tests;

パターンC: Rc<RefCell<Option<TreeNode<K>>>>

見かけはパターンAに近い実装になっている。

use std::fmt::{self, Debug};
use std::rc::Rc;
use std::cell::{RefMut, RefCell};
use std::cmp::Ordering;

pub struct TreeNodes<K> {
    left: Option<Rc<TreeNode<K>>>,
    right: Option<Rc<TreeNode<K>>>,
}

pub struct TreeNode<K> {
    key: K,
    children: RefCell<TreeNodes<K>>,
}

impl<K> TreeNode<K> {
    pub fn new(key: K) -> Self {
        TreeNode {
            key,
            children: RefCell::new(
                TreeNodes { left: None, right: None }
            ),
        }
    }
}

impl<K: Debug> fmt::Debug for TreeNode<K> {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        match (self.children.borrow().left.as_ref(), self.children.borrow().right.as_ref()) {
            (None, None) => {
                write!(f, "TreeNode(Nil,{:?},Nil)", self.key)
            },
            (Some(ref left), Some(ref right)) => {
                write!(f,
                    "{:?}, TreeNode({:?},{:?},{:?}), {:?}",
                    left, left.key, self.key, right.key, right
                )
            },
            (None, Some(ref right)) => {
                write!(f,
                    "TreeNode(Nil,{:?},{:?}), {:?}",
                    self.key, right.key, right
                )
            },
            (Some(ref left), None) => {
                write!(f,
                    "{:?}, TreeNode({:?},{:?},Nil)",
                    left, left.key, self.key
                )
            },
        }
    }
}

# [derive(Default)]
pub struct BTree<K> {
    head: Option<Rc<TreeNode<K>>>,
}

impl<K: Ord> BTree<K> {
    /// # Examples
    ///
    /// ```
    /// use bt_refcell_children_opt_rc::BTree;
    /// let mut tree: BTree<&str> = Default::default();
    /// tree.insert("E");
    /// tree.insert("A");
    /// tree.insert("S");
    /// println!("{:?}", &tree);
    /// ```
    pub fn insert(&mut self, key: K) {
        let mut cur: Rc<TreeNode<K>>  = match self.head.as_ref() {
            Some(head_rc_ref) => Rc::clone(head_rc_ref),
            None => {
                self.head.replace(
                    Rc::new(TreeNode::new(key))
                );
                return;
            },
        };

        loop {
            let mut some_node_ref = RefMut::map(
                cur.children.borrow_mut(),
                |children_ref| {
                    match cur.key.cmp(&key) {
                        Ordering::Greater => &mut children_ref.left,
                        _ => &mut children_ref.right,
                    }
                }
            );
            if some_node_ref.is_none() {
                some_node_ref.replace(Rc::new(TreeNode::new(key)));
                return;
            }
            let cur_work = Rc::clone(some_node_ref.as_ref().unwrap());
            drop(some_node_ref);
            cur = cur_work;
        }
    }
}

impl<K: Clone> BTree<K> {
    /// # Examples
    ///
    /// ```
    /// use bt_refcell_children_opt_rc::BTree;
    /// let mut tree: BTree<&str> = Default::default();
    /// tree.insert("E");
    /// tree.insert("A");
    /// tree.insert("S");
    /// assert_eq!(tree.to_vec_in_order(), vec!["A", "E", "S"]);
    /// ```
    pub fn to_vec_in_order(&self) -> Vec<K> {
        let head_rc: Rc<TreeNode<K>>  = match self.head.as_ref() {
            Some(head_rc_ref) => Rc::clone(head_rc_ref),
            None => {
                return Vec::new();
            },
        };

        let mut stack: Vec<Rc<TreeNode<K>>>;
        stack = Vec::new();

        let mut results: Vec<K> = vec!();

        let mut cur = Some(head_rc);
        'outer: loop {
            // Traverse the subtree on the left while adding nodes to the stack.
            while let Some(cur_rc) = cur {
                stack.push(Rc::clone(&cur_rc));
                match Rc::clone(&cur_rc).children.borrow().left.as_ref() {
                    Some(left_rc_ref) => {
                        cur = Some(Rc::clone(left_rc_ref));
                    },
                    None => {
                        cur = None;
                    }
                }
            }

            // It pops elements from the stack and continues to output,
            // returning to traversing the left side
            // if a node is found on the current right side.
            loop {
                let cur_right = match stack.pop() {
                    Some(cur_right) => cur_right,
                    None => break 'outer,
                };

                results.push(cur_right.key.clone());
                if let Some(right_rc_ref) = Rc::clone(
                    &cur_right
                ).children.borrow().right.as_ref() {
                    cur = Some(Rc::clone(right_rc_ref));
                    continue 'outer;
                }
            }
        }
        results
    }
}

impl<T: fmt::Debug> fmt::Debug for BTree<T> {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        match self.head.as_ref() {
            None => write!(f, "BTree {{}}"),
            Some(head) => write!(f, "BTree={{{:?}}}", head),
        }
    }
}

# [cfg(test)]
mod tests;