3
\$\begingroup\$

Similarly to Learning Rust With Entirely Too Many Linked Lists, I'm trying to learn Rust by working with linked lists. Currently I'm trying to implement a function bubble(...) that takes 2 elements of a singly-linked list and swaps them.

Any feedback is greatly appreciated! (Rust playground link here.)

#![allow(dead_code)]

use ::std::mem::replace;
use ::std::mem::swap;

#[derive(Debug)]
pub struct List<T> {
    list: Node<T>,
}

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

#[derive(Debug)]
struct Link<T> {
  head: T,
  tail: Node<T>,
}

impl<T> List<T> {
  pub fn push(&mut self, elem: T) {
    self.list = Some(Box::new(
      Link{ head: elem, tail: replace(&mut self.list, None) }));
  }

  pub fn pop(&mut self) -> Option<T> {
    match replace(&mut self.list, None) {
      Some(next_box) => {
        let next = *next_box;
        self.list = next.tail;
        Some(next.head)
      }
      _ => None
    }
  }

  // First attempt: Use push+pop. Not perfect, as we move the values
  // in and out, and if they're larger, we waste resources.
  pub fn bubble(&mut self) -> bool {
    if let Some(first) = self.pop() {
      if let Some(second) = self.pop() {
        self.push(first);
        self.push(second);
        return true;
      } else {
        self.push(first);
      }
    }
    false
  }

  // Learning from the above attempt, I created another push+pop
  // functions that don't move values, just Boxes instead.

  // Any tail of 'singleton' is silently discarded.
  fn push_singleton(&mut self, mut singleton: Box<Link<T>>) {
    swap(&mut self.list, &mut singleton.tail);
    self.list = Some(singleton);
  }

  fn pop_singleton(&mut self) -> Node<T> {
    match replace(&mut self.list, None) {
      Some(mut next_box) => {
        swap(&mut self.list, &mut next_box.tail);
        Some(next_box)
      }
      _ => None
    }
  }

  // Otherwise the implementation is very similar to 'bubble' above.
  pub fn bubble2(&mut self) -> bool {
    if let Some(first_box) = self.pop_singleton() {
      if let Some(second_box) = self.pop_singleton() {
        self.push_singleton(first_box);
        self.push_singleton(second_box);
        return true;
      } else {
        self.push_singleton(first_box);
      }
    }
    false
  }


  // Third attempt: Directly unpack the first two nodes and combine them
  // back together.
  pub fn bubble3(&mut self) -> bool {
    if let Some(mut first_box) = replace(&mut self.list, None) {
      if let Some(mut second_box) = replace(&mut first_box.tail, None) {
        first_box.tail = replace(&mut second_box.tail, None);
        second_box.tail = Some(first_box);
        *self = List{ list: Some(second_box) };
        return true;
      } else {
        *self = List{ list: Some(first_box) };
      }
    }
    false
  }
}

fn main() {}
\$\endgroup\$
2
  • \$\begingroup\$ *Checks name, double checks language*. Huh, another familiar face learning Rust :D. \$\endgroup\$
    – Zeta
    Mar 16 '18 at 16:46
  • \$\begingroup\$ @Zeta Sorry about that, fixed. Now it should compile and without errors/warnings. \$\endgroup\$
    – Petr
    Mar 17 '18 at 9:18
1
\$\begingroup\$
  1. Run Rustfmt. It well automatically tell you such things as:

    • Idiomatic Rust uses 4-space indents.
    • Match arms without curly braces have trailing commas
    • You don't need to prefix paths in use with ::; that's the default.
  2. You don't need #![allow(dead_code)] and it's better to not disable warnings that broadly.

  3. It's usual to import only the module, not the free function, and then namespace the function. For example, mem::replace.

  4. mem::replace(&mut /* ... */, None) is equivalent to Option::take

  5. You can also replace some usages of mem::swap with Option::take and direct assignment. This means you don't need to use functions from mem at all.

#[derive(Debug)]
pub struct List<T> {
    list: Node<T>,
}

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

#[derive(Debug)]
struct Link<T> {
    head: T,
    tail: Node<T>,
}

impl<T> List<T> {
    pub fn push(&mut self, elem: T) {
        self.list = Some(Box::new(Link {
            head: elem,
            tail: self.list.take(),
        }));
    }

    pub fn pop(&mut self) -> Option<T> {
        match self.list.take() {
            Some(next_box) => {
                let next = *next_box;
                self.list = next.tail;
                Some(next.head)
            }
            _ => None,
        }
    }

    // First attempt: Use push+pop. Not perfect, as we move the values
    // in and out, and if they're larger, we waste resources.
    pub fn bubble(&mut self) -> bool {
        if let Some(first) = self.pop() {
            if let Some(second) = self.pop() {
                self.push(first);
                self.push(second);
                return true;
            } else {
                self.push(first);
            }
        }
        false
    }

    // Learning from the above attempt, I created another push+pop
    // functions that don't move values, just Boxes instead.

    // Any tail of 'singleton' is silently discarded.
    fn push_singleton(&mut self, mut singleton: Box<Link<T>>) {
        singleton.tail = self.list.take();
        self.list = Some(singleton);
    }

    fn pop_singleton(&mut self) -> Node<T> {
        match self.list.take() {
            Some(mut next_box) => {
                self.list = next_box.tail.take();
                Some(next_box)
            }
            _ => None,
        }
    }

    // Otherwise the implementation is very similar to 'bubble' above.
    pub fn bubble2(&mut self) -> bool {
        if let Some(first_box) = self.pop_singleton() {
            if let Some(second_box) = self.pop_singleton() {
                self.push_singleton(first_box);
                self.push_singleton(second_box);
                return true;
            } else {
                self.push_singleton(first_box);
            }
        }
        false
    }

    // Third attempt: Directly unpack the first two nodes and combine them
    // back together.
    pub fn bubble3(&mut self) -> bool {
        if let Some(mut first_box) = self.list.take() {
            if let Some(mut second_box) = first_box.tail.take() {
                first_box.tail = second_box.tail.take();
                second_box.tail = Some(first_box);
                *self = List {
                    list: Some(second_box),
                };
                return true;
            } else {
                *self = List {
                    list: Some(first_box),
                };
            }
        }
        false
    }
}

fn main() {}

For what it's worth, I prefer bubble2 as the implementation is better factored and has helper functions.

I'm not a big fan of the word "singleton" here, as that feels like a misuse of the term. I don't have a great alternative name other than {push,pop}_boxed though.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.