Home > Software engineering >  Appending an element to recursive type in Rust
Appending an element to recursive type in Rust

Time:07-11

The code I have:

#[derive(Debug, Clone, Eq, PartialEq)]
struct BugColony {
    pub first: Link,
}

type Link = Option<Box<Bug>>;

#[derive(Debug, Clone, Eq, PartialEq)]
struct Bug {
    bug_type: String,
    next_bug: Link,
}

Now I'd like to create a function that appends a new Bug to the end of the recursive bug 'list'. What is the rust way of doing that.

ex:

fn main() {
    let mut list = BugColony{Link::None};
    list.add_bug(String::from("Bee"));
    list.add_bug(String::from("Bedbug"));

    println!("{:?}", list);
}

impl BugColony {
    fn add_bug(&mut self, type: String) {
         ...
    }
}

So the result would be:

WorkEnvironment { 
    first: Some(
        Bug {
            bug_type: "Bee",
            next_bug: Some(
                Bug {
                    bug_type: "Bee",
                    next_bug: None
                    })
            })
}

CodePudding user response:

This just sounds like appending to a Linked List to me; I don't think there's anything particularly Rusty about it. If what you're asking is how one would recommend performing the whole "loop to the end of a Linked List" thing in Rust, I'd use while let to unwrap your Option enums.

Below is an example. I also took the liberty to rename type (since it's a keyword), and to swap String for impl Into<String> so that you could pass in a &'static str and the like. Here's a link to the playground.


type Link<T> = Option<Box<T>>;

#[derive(Debug, Clone, Eq, PartialEq)]
struct BugColony {
    pub first: Link<Bug>,
}

#[derive(Debug, Clone, Eq, PartialEq)]
struct Bug {
    bug_type: String,
    next_bug: Link<Bug>,
}

impl BugColony {
    fn add_bug(&mut self, bug_type: impl Into<String>) {
        let mut cur = &mut self.first;

        // As long as the current bug has one after it, advance down the list.  
        // Once the loop is done running, `cur` will be a reference to the `None`  
        // at the end of the list.
        while let Some(bug) = cur {
            cur = &mut bug.next_bug;
        }

        let new = Bug { bug_type: bug_type.into(), next_bug: None };
        *cur = Some(Box::new(new));
    }
}

fn main() {
    let mut col = BugColony { first: None };

    col.add_bug("Grasshopper");
    col.add_bug("Ladybug");
    col.add_bug("Fire Ant");

    println!("{col:#?}");
}

Output:

BugColony {
    first: Some(
        Bug {
            bug_type: "Grasshopper",
            next_bug: Some(
                Bug {
                    bug_type: "Ladybug",
                    next_bug: Some(
                        Bug {
                            bug_type: "Fire Ant",
                            next_bug: None,
                        },
                    ),
                },
            ),
        },
    ),
}

CodePudding user response:

If you really want a linked list, there is nothing specific to Rust here.

In your example, the add_bug() operation was expected as appending to the end of the list. Just follow the Links and append a new Bug when you find None (see append_bug() below).

It would be much simpler to prepend: you just have to change the first Link (see prepend_bug() below).

I cannot think about a real situation where a linked list is better than a vector; it's much more complicated and much less efficient (that would be long to explain in details here -- cache-line usage, prefetching...). I suggest you simply use a vector; see VBugColony and VBug below.

#[derive(Debug, Clone, Eq, PartialEq)]
struct BugColony {
    first: Link,
}

type Link = Option<Box<Bug>>;

#[derive(Debug, Clone, Eq, PartialEq)]
struct Bug {
    bug_type: String,
    next_bug: Link,
}

impl BugColony {
    fn append_bug(
        &mut self,
        bug_type: String,
    ) {
        let mut lnk = &mut self.first;
        loop {
            if let Some(bug) = lnk {
                lnk = &mut bug.next_bug;
            } else {
                *lnk = Some(Box::new(Bug {
                    bug_type,
                    next_bug: None,
                }));
                break;
            }
        }
    }

    fn prepend_bug(
        &mut self,
        bug_type: String,
    ) {
        self.first = Some(Box::new(Bug {
            bug_type,
            next_bug: self.first.take(),
        }));
    }
}

#[derive(Debug, Clone, Eq, PartialEq)]
struct VBugColony {
    bugs: Vec<VBug>,
}

#[derive(Debug, Clone, Eq, PartialEq)]
struct VBug {
    bug_type: String,
}

impl VBugColony {
    fn add_bug(
        &mut self,
        bug_type: String,
    ) {
        self.bugs.push(VBug { bug_type });
    }
}

fn main() {
    let mut list = BugColony { first: None };
    list.append_bug(String::from("Bee"));
    list.append_bug(String::from("Bedbug"));
    println!("{:#?}", list);
    //
    let mut list = BugColony { first: None };
    list.prepend_bug(String::from("Bedbug"));
    list.prepend_bug(String::from("Bee"));
    println!("{:#?}", list);
    //
    let mut list = VBugColony {
        bugs: Default::default(),
    };
    list.add_bug(String::from("Bedbug"));
    list.add_bug(String::from("Bee"));
    println!("{:#?}", list);
}
/*
BugColony {
    first: Some(
        Bug {
            bug_type: "Bee",
            next_bug: Some(
                Bug {
                    bug_type: "Bedbug",
                    next_bug: None,
                },
            ),
        },
    ),
}
BugColony {
    first: Some(
        Bug {
            bug_type: "Bee",
            next_bug: Some(
                Bug {
                    bug_type: "Bedbug",
                    next_bug: None,
                },
            ),
        },
    ),
}
VBugColony {
    bugs: [
        VBug {
            bug_type: "Bedbug",
        },
        VBug {
            bug_type: "Bee",
        },
    ],
}
*/
  • Related