Есть ли способ использовать рекурсию с брендированными индексами индексного ящика для создания дерева? - PullRequest
Новая
       22

Есть ли способ использовать рекурсию с брендированными индексами индексного ящика для создания дерева?

0 голосов
/ 02 апреля 2019

Я пытаюсь построить дерево, используя индексную корзину : 

use indexing::{Container, Index, scope, container::OnlyIndex};

struct Tree<'id>(Option<(Index<'id>, Index<'id>)>);

fn tree<'a>(c: &mut Container<'a, &mut Vec<Tree<'a>>, OnlyIndex>, depth: usize) -> Index<'a> {
    if depth == 0 {
        c.push(Tree(None))
    } else {
        let left = tree(c, depth - 1);
        let right = tree(c, depth - 1);
        c.push(Tree(Some((left, right))))
    }
}

fn main() {
    let mut v = vec![];
    scope(&mut v, |v| {
        let mut v = v.only_index();
        tree(&mut v, 3);
        assert_eq!(v.len(), 1 + 2 + 4 + 8);
    });
}

Это приводит к пожизненной ошибке: 

error: borrowed data cannot be stored outside of its closure
  --> src/main.rs:18:23
   |
16 |     let mut v = vec![];
   |         ----- borrowed data cannot be stored into here...
17 |     scope(&mut v, |v| {
   |                   --- ...because it cannot outlive this closure
18 |         let mut v = v.only_index();
   |                       ^^^^^^^^^^ cannot be stored outside of its closure

Есть ли способ правильно определить tree для работы в индексированной области?

1 Ответ

0 голосов
/ 15 апреля 2019

Как отмечалось в комментариях, это действительно невозможно с корзиной индексации.Однако это не значит, что хранить фирменные индексы вообще невозможно.Фактически, избавление от замыкания будет работать нормально, как в следующем коде: 

use std::marker::PhantomData;
use std::ops::Index;

#[derive(Copy, Clone)]
struct InvariantLifetime<'a>(PhantomData<fn(&'a ()) -> &'a ()>);
pub struct Arena<'b, T>(Vec<T>, InvariantLifetime<'b>);
pub struct Idx<'b>(usize, InvariantLifetime<'b>);

impl<'b, T> Arena<'b, T> {
    pub unsafe fn new(_: &'b mut ()) -> Self {
        Arena(vec![], InvariantLifetime(PhantomData))
    }

    pub fn add(&mut self, t: T) -> Idx<'b> {
        let i = self.0.len();
        self.0.push(t);
        Idx(i, self.1)
    }
}

impl<'b, T> Index<Idx<'b>> for Arena<'b, T> {
    type Output = T;

    fn index(&self, i: Idx<'b>) -> &T {
        unsafe { &self.0.get_unchecked(i.0) }
    }
}

macro_rules! mk_arena {
    ($arena:ident) => {
        let mut tag = ();
        let mut $arena = unsafe { Arena::new(&mut tag) };
    };
}

struct Tree<'b>(Option<(Idx<'b>, Idx<'b>)>);
fn tree<'b>(a: &mut Arena<'b, Tree<'b>>, d: usize) -> Idx<'b> {
    if d > 0 {
        a.add(Tree(Some((tree(a, d - 1), tree(a, d - 1)))))
    } else {
        a.add(Tree(None))
    }
}

pub fn main() {
    mk_arena!(arena);
    let _ = tree(&mut arena, 3);
}

Ящик compact_arena имеет то же решение с лучшими документами.

...