In Python this is easy using a stack and recursive functions since Python uses object references so saying 'append to the last item on the stack' and 'push the current item (i.e., an object reference to the current item)' onto the stack are easy.
It's perfectly fine and possible to create recursive functions and data structures in Rust. Do you have some concrete code that you tried and didn't work?
I know Rust supports recursion, but the problem I have is maintaining a stack of Values which I want to be in effect references to the actual values so that given a root List and a stack with that root as its first item, I want to say add a new item to the List referred to by the last item on the stack. And also to put that last item itself on the stack. I've tried & and Rc but to no avail.
I still don't understand what you mean. Please share actual code. You don't generally need either references (at least not shared references) or Rc for building a collection if it's a tree (i.e. there are no cycles or multiple parents for a given child).
Here's an example of recursively building up a data structure, but I really don't know what exactly you are looking for.
It is true that a type (e.g. List) cannot have fields or alternativies that of that same type or of types that contains that same type, since that would lead to infinite recursion giving an infinitely large type. But they can contain owernship of a separately allocated List, e.g. a Box<List> or a Vec<List>. It is also possible to contain a borrowed reference (e.g. &List), but then your type is a referencing type and you need to keep track of lifetimes (and something else has to own the things you borrow).
What I do in Python and which I can't figure out how to do in Rust is essentially this:
stack = [] # a stack is just a list
stack.append(stack) # now its first element is itself
# stack == [stack]
if len(stack) == 0:
parent = stack
else:
parent = stack[-1] # last one
lst = []
parent.append(lst)
# stack == [stack[lst]]
stack.append(lst)
# stack == [stack[lst], lst]
And at the end I have a stack with one item which contains all the others.
You need interior mutability (e.g. RefCell) and reference counting (e.g. Rc) for creating such a self-referential, multiple ownership structure. But it doesn't look like you need all of this for simply creating a tree. Is there a reason you are creating an explicit stack and push it onto itself? There are far simpler approaches (both recursive and iterative) for building up a tree of objects.
E.g., here is a literal translation of your code, but as it's predictable, it's very non-idiomatic:
#[derive(Clone)]
enum Value {
Leaf,
List(Rc<RefCell<Vec<Value>>>),
}
impl Value {
fn new_leaf() -> Value {
Value::Leaf
}
fn new_list() -> Value {
Value::List(Rc::new(RefCell::new(Vec::new())))
}
fn push(&self, child: Value) {
if let Value::List(list) = self {
list.borrow_mut().push(child);
}
}
fn last(&self) -> Option<Value> {
if let Value::List(list) = self {
list.borrow().last().cloned()
} else {
None
}
}
}
fn main() {
let stack = Value::new_list();
stack.push(stack.clone());
let parent = stack.last().unwrap_or_else(|| stack.clone());
let lst = Value::new_list();
parent.push(lst.clone());
stack.push(lst);
}
I finally solved it by getting rid of the stack entirely, and passing the list down recursively.
This did lead to one problem. When I did: parent_lst.push(track) in a loop, I built this structure track by track: [], [(T 1)], [(T 1) (T 2)], [(T 1) (T 2) (T 3)], etc. I solved it by adding a push_or_combine() method to the underlying collection's API. So now the calls are parent_lst.push_or_combine(track) and this builds: [], [(T 1)], [(T 1 2)], [(T 1 2 3)], etc.
Here's the relevant code:
fn save_uxf(&mut self) -> Result<()> {
let (group_tclass, track_tclass, history_tclass) = make_tclasses();
let mut uxo = uxf::Uxf::new("TLM 2", "");
uxo.add_tclass(group_tclass.clone());
uxo.add_tclass(track_tclass.clone());
uxo.add_tclass(history_tclass.clone());
let parent_lst = uxo.value_mut();
if let Some(item) = self.track_tree.first() {
self.write_tree_uxf(parent_lst, &item, &group_tclass, &track_tclass);
}
// elided lines saving history
uxo.write_format(&self.filename.to_string_lossy(), &uxf::Format::new(2, 240, Some(3)))
}
fn write_tree_uxf(&mut self, parent_lst: &mut uxf::Value, item: &fltk::tree::TreeItem, group_tclass: &uxf::TClass, track_tclass: &uxf::TClass) {
for i in 0..item.children() {
if let Some(child) = item.child(i) {
let tid = unsafe { child.user_data::<TrackID>() };
if let Some(tid) = tid { // Track
if let Some(track_item) = self.track_for_tid.get(&tid) {
let filename: uxf::Value = track_item .filename .to_string_lossy() .to_string().into();
let secs: uxf::Value = track_item.secs.into();
let mut track = uxf::Value::new_table(track_tclass.clone());
track.push(filename).unwrap();
track.push(secs).unwrap();
parent_lst.push_or_combine(track).unwrap();
}
} else { // Group
let label = child.label().unwrap();
let mut group = uxf::Value::new_table(group_tclass.clone());
group.push(label.into()).unwrap();
let mut child_lst = uxf::Value::new_list();
self.write_tree_uxf(&mut child_lst, &child, group_tclass, track_tclass);
group.push(child_lst).unwrap();
parent_lst.push(group).unwrap();
}
}
}
}