Binary search tree iterator ii

use std::cell::{Cell, RefCell};
use std::rc::Rc;

struct BSTIterator {
  index: Cell<usize>,
  stack: RefCell<Vec<Rc<RefCell<TreeNode>>>>,
  values: RefCell<Vec<i32>>,
}


/** 
 * `&self` means the method takes an immutable reference.
 * If you need a mutable reference, change it to `&mut self` instead.
 */
impl BSTIterator {

  fn new(root: Option<Rc<RefCell<TreeNode>>>) -> Self {
    let iterator = Self {
      index: Cell::new(0),
      stack: RefCell::new(Vec::new()),
      values: RefCell::new(Vec::new()),
    };

    iterator.push_left_path(root);
    iterator
  }

  fn push_left_path(&self, mut node: Option<Rc<RefCell<TreeNode>>>) {
    let mut stack = self.stack.borrow_mut();

    while let Some(current) = node {
      let left = current.borrow().left.clone();
      stack.push(current);
      node = left;
    }
  }
  
  fn has_next(&self) -> bool {
    let index = self.index.get();
    index < self.values.borrow().len() || !self.stack.borrow().is_empty()
  }
  
  fn next(&self) -> i32 {
    let index = self.index.get();

    if index == self.values.borrow().len() {
      let node = self.stack.borrow_mut().pop().unwrap();
      let (value, right) = {
        let node_ref = node.borrow();
        (node_ref.val, node_ref.right.clone())
      };

      self.push_left_path(right);
      self.values.borrow_mut().push(value);
    }

    self.index.set(index + 1);
    self.values.borrow()[index]
  }
  
  fn has_prev(&self) -> bool {
    self.index.get() > 1
  }
  
  fn prev(&self) -> i32 {
    let new_index = self.index.get() - 1;
    self.index.set(new_index);
    self.values.borrow()[new_index - 1]
  }
}