Реализовать IntoIterator для двоичного дерева

Question

Я пытаюсь построить двоичное дерево и написать итератор для обхода значений в дереве. При реализации черты IntoIterator для узлов дерева я столкнулся с проблемой времени жизни

src\main.rs:43:6: 43:8 error: the lifetime parameter `'a` is not constrained by the impl trait, self type, or predicates [E0207]
src\main.rs:43 impl<'a, T: 'a> IntoIterator for Node<T> {

Я понимаю, что мне нужно указать, что NodeIterator будет жить так же долго, как и Node, но я не уверен, как это выразить

use std::cmp::PartialOrd;
use std::boxed::Box;

struct Node<T: PartialOrd> {
    value: T,
    left: Option<Box<Node<T>>>,
    right: Option<Box<Node<T>>>,
}

struct NodeIterator<'a, T: 'a + PartialOrd> {
    current: &'a Node<T>,
    parent: Option<&'a Node<T>>,
}

impl<T: PartialOrd> Node<T> {
    pub fn insert(&mut self, value: T) {
        ...
    }
}

impl<'a, T: 'a> IntoIterator for Node<T> { // line 43
     type Item = T;
     type IntoIter = NodeIterator<'a, T>;

     fn into_iter(&self) -> Self::IntoIter {
         NodeIterator::<'a> {
             current: Some(&self),
             parent: None
         }
     }
 }

Answer 1

Конкретная ошибка, которую вы получаете, заключается в том, что 'a должно появиться справа от for, Иначе как компилятор может узнать, что a является?

При реализации IntoIterator Вы должны решить, будет ли итератор использовать контейнер, или он просто создаст ссылки на него. На данный момент ваши настройки противоречивы, и сообщение об ошибке указывает на это.

В случае бинарного дерева вы также должны подумать о том, в каком порядке вы хотите получить значения: традиционные порядки - это сначала глубина (с сортированной последовательностью) и ширина - сначала (открывая "слои" дерева). Сначала я приму глубину, так как она самая распространенная.

---

Давайте сначала рассмотрим случай использования итератора. Это проще в том смысле, что нам не нужно беспокоиться о жизни.

#![feature(box_patterns)]

struct Node<T: PartialOrd> {
    value: T,
    left: Option<Box<Node<T>>>,
    right: Option<Box<Node<T>>>,
}

struct NodeIterator<T: PartialOrd> {
    stack: Vec<Node<T>>,
    next: Option<T>,
}

impl<T: PartialOrd> IntoIterator for Node<T> {
    type Item = T;
    type IntoIter = NodeIterator<T>;

    fn into_iter(self) -> Self::IntoIter {
        let mut stack = Vec::new();

        let smallest = pop_smallest(self, &mut stack);

        NodeIterator { stack: stack, next: Some(smallest) }
    }
}

impl<T: PartialOrd> Iterator for NodeIterator<T> {
    type Item = T;

    fn next(&mut self) -> Option<T> {
        if let Some(next) = self.next.take() {
            return Some(next);
        }

        if let Some(Node { value, right, .. }) = self.stack.pop() {
            if let Some(right) = right {
                let box right = right;
                self.stack.push(right);
            }
            return Some(value);
        }

        None
    }
}

fn pop_smallest<T: PartialOrd>(node: Node<T>, stack: &mut Vec<Node<T>>) -> T {
    let Node { value, left, right } = node;

    if let Some(left) = left {
        stack.push(Node { value: value, left: None, right: right });
        let box left = left;
        return pop_smallest(left, stack);
    }

    if let Some(right) = right {
        let box right = right;
        stack.push(right);
    }

    value
}

fn main() {
    let root = Node {
        value: 3,
        left: Some(Box::new(Node { value: 2, left: None, right: None })),
        right: Some(Box::new(Node { value: 4, left: None, right: None }))
    };

    for t in root {
        println!("{}", t);
    }
}

---

Теперь мы можем "легко" адаптировать его к непотребляющему случаю, добавив соответствующие ссылки:

struct RefNodeIterator<'a, T: PartialOrd + 'a> {
    stack: Vec<&'a Node<T>>,
    next: Option<&'a T>,
}

impl<'a, T: PartialOrd + 'a> IntoIterator for &'a Node<T> {
    type Item = &'a T;
    type IntoIter = RefNodeIterator<'a, T>;

    fn into_iter(self) -> Self::IntoIter {
        let mut stack = Vec::new();

        let smallest = pop_smallest_ref(self, &mut stack);

        RefNodeIterator { stack: stack, next: Some(smallest) }
    }
}

impl<'a, T: PartialOrd + 'a> Iterator for RefNodeIterator<'a, T> {
    type Item = &'a T;

    fn next(&mut self) -> Option<&'a T> {
        if let Some(next) = self.next.take() {
            return Some(next);
        }

        if let Some(node) = self.stack.pop() {
            if let Some(ref right) = node.right {
                self.stack.push(right);
            }
            return Some(&node.value);
        }

        None
    }
}

fn pop_smallest_ref<'a, T>(node: &'a Node<T>, stack: &mut Vec<&'a Node<T>>) -> &'a T
    where
        T: PartialOrd + 'a
{
    if let Some(ref left) = node.left {
        stack.push(node);
        return pop_smallest_ref(left, stack);
    }

    if let Some(ref right) = node.right {
        stack.push(right);
    }

    &node.value
}

Там много чего можно распаковать; так что не торопитесь, чтобы переварить это. В частности:

• использование ref в Some(ref right) = node.right потому что я не хочу потреблять node.right только для получения ссылки внутри Option; компилятор будет жаловаться, что я не могу выйти из заемного объекта без него (поэтому я просто следую жалобам),
• в stack.push(right), right: &'a Box<Node<T>> и все еще stack: Vec<&'a Node<T>>; это магия Deref: Box<T> инвентарь Deref<T> поэтому компилятор автоматически преобразует ссылку в зависимости от ситуации.

Примечание: я не писал этот код как есть; вместо этого я просто помещаю первые несколько ссылок, где я ожидаю, что они будут (например, тип возврата Iterator ) и пусть компилятор ведет меня.