Перестановки двух элементов поодиночке-связанный список


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

Любая обратная связь с благодарностью! (Руст площадка ссылке здесь.)

#![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() {}


139
3
задан 16 марта 2018 в 04:03 Источник Поделиться
Комментарии
1 ответ


  1. Запустить Rustfmt. Он также автоматически сказать вам такие вещи, как:


    • Идиоматические ржавчины использует 4-пространства отступа.

    • Матч оружием без фигурных скобок трейлинг запятые

    • Вам не нужно префикс пути в use с ::; это значение по умолчанию.


  2. Вам не нужно #![allow(dead_code)] и лучше не отключить предупреждения о том, что в целом.

  3. Это обычно, чтобы импортировать только модуль, а не свободная функция, а затем пространство имен функции. Например, mem::replace.

  4. mem::replace(&mut /* ... */, None) эквивалентно Option::take

  5. Вы можете также заменить некоторые обычаи mem::swap С Option::take и прямое назначение. Это означает, что вам не нужно использовать функции из mem на всех.

#[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() {}

Для чего это стоит, я предпочитаю bubble2 в качестве реализации лучше учитывать и вспомогательные функции.

Я не большой поклонник слова "синглтон", так как он чувствует, как неправильное использование термина. У меня нет прекрасной альтернативой другим именем {push,pop}_boxed хотя.

2
ответ дан 17 марта 2018 в 04:03 Источник Поделиться