}
impl<T> Copy for Rawlink<T> {}
-unsafe impl<T:Send> Send for Rawlink<T> {}
-unsafe impl<T:Sync> Sync for Rawlink<T> {}
+unsafe impl<T: Send> Send for Rawlink<T> {}
+unsafe impl<T: Sync> Sync for Rawlink<T> {}
struct Node<T> {
next: Link<T>,
/// An iterator over references to the items of a `LinkedList`.
#[stable(feature = "rust1", since = "1.0.0")]
-pub struct Iter<'a, T:'a> {
+pub struct Iter<'a, T: 'a> {
head: &'a Link<T>,
tail: Rawlink<Node<T>>,
nelem: usize,
/// An iterator over mutable references to the items of a `LinkedList`.
#[stable(feature = "rust1", since = "1.0.0")]
-pub struct IterMut<'a, T:'a> {
+pub struct IterMut<'a, T: 'a> {
list: &'a mut LinkedList<T>,
head: Rawlink<Node<T>>,
tail: Rawlink<Node<T>>,
#[derive(Clone)]
#[stable(feature = "rust1", since = "1.0.0")]
pub struct IntoIter<T> {
- list: LinkedList<T>
+ list: LinkedList<T>,
}
/// Rawlink is a type like Option<T> but for holding a raw pointer
impl<T> Rawlink<T> {
/// Like Option::None for Rawlink
fn none() -> Rawlink<T> {
- Rawlink{p: ptr::null_mut()}
+ Rawlink { p: ptr::null_mut() }
}
/// Like Option::Some for Rawlink
fn some(n: &mut T) -> Rawlink<T> {
- Rawlink{p: n}
+ Rawlink { p: n }
}
/// Convert the `Rawlink` into an Option value
impl<T> Clone for Rawlink<T> {
#[inline]
fn clone(&self) -> Rawlink<T> {
- Rawlink{p: self.p}
+ Rawlink { p: self.p }
}
}
impl<T> Node<T> {
fn new(v: T) -> Node<T> {
- Node{value: v, next: None, prev: Rawlink::none()}
+ Node {
+ value: v,
+ next: None,
+ prev: Rawlink::none(),
+ }
}
/// Update the `prev` link on `next`, then set self's next pointer.
self.length -= 1;
match front_node.next.take() {
Some(node) => self.list_head = link_no_prev(node),
- None => self.list_tail = Rawlink::none()
+ None => self.list_tail = Rawlink::none(),
}
front_node
})
self.list_tail = tail.prev;
match tail.prev.resolve_mut() {
None => self.list_head.take(),
- Some(tail_prev) => tail_prev.next.take()
+ Some(tail_prev) => tail_prev.next.take(),
}
})
}
#[stable(feature = "rust1", since = "1.0.0")]
impl<T> Default for LinkedList<T> {
#[inline]
- fn default() -> LinkedList<T> { LinkedList::new() }
+ fn default() -> LinkedList<T> {
+ LinkedList::new()
+ }
}
impl<T> LinkedList<T> {
#[inline]
#[stable(feature = "rust1", since = "1.0.0")]
pub fn new() -> LinkedList<T> {
- LinkedList{list_head: None, list_tail: Rawlink::none(), length: 0}
+ LinkedList {
+ list_head: None,
+ list_tail: Rawlink::none(),
+ length: 0,
+ }
}
/// Moves all elements from `other` to the end of the list.
self.length = other.length;
self.list_head = other.list_head.take();
self.list_tail = other.list_tail.take();
- },
+ }
Some(tail) => {
// Carefully empty `other`.
let o_tail = other.list_tail.take();
#[inline]
#[stable(feature = "rust1", since = "1.0.0")]
pub fn iter(&self) -> Iter<T> {
- Iter{nelem: self.len(), head: &self.list_head, tail: self.list_tail}
+ Iter {
+ nelem: self.len(),
+ head: &self.list_head,
+ tail: self.list_tail,
+ }
}
/// Provides a forward iterator with mutable references.
nelem: self.len(),
head: Rawlink::from(&mut self.list_head),
tail: self.list_tail,
- list: self
+ list: self,
}
}
#[inline]
#[stable(feature = "rust1", since = "1.0.0")]
pub fn back(&self) -> Option<&T> {
- unsafe {
- self.list_tail.resolve().map(|tail| &tail.value)
- }
+ unsafe { self.list_tail.resolve().map(|tail| &tail.value) }
}
/// Provides a mutable reference to the back element, or `None` if the list
#[inline]
#[stable(feature = "rust1", since = "1.0.0")]
pub fn back_mut(&mut self) -> Option<&mut T> {
- unsafe {
- self.list_tail.resolve_mut().map(|tail| &mut tail.value)
- }
+ unsafe { self.list_tail.resolve_mut().map(|tail| &mut tail.value) }
}
/// Adds an element first in the list.
///
#[stable(feature = "rust1", since = "1.0.0")]
pub fn pop_front(&mut self) -> Option<T> {
- self.pop_front_node().map(|box Node{value, ..}| value)
+ self.pop_front_node().map(|box Node { value, .. }| value)
}
/// Appends an element to the back of a list
/// ```
#[stable(feature = "rust1", since = "1.0.0")]
pub fn pop_back(&mut self) -> Option<T> {
- self.pop_back_node().map(|box Node{value, ..}| value)
+ self.pop_back_node().map(|box Node { value, .. }| value)
}
/// Splits the list into two at the given index. Returns everything after the given index,
iter.next();
}
iter.head
- } else {
+ } else {
// better off starting from the end
let mut iter = self.iter_mut();
for _ in 0..len - 1 - (at - 1) {
let second_part = LinkedList {
list_head: second_part_head,
list_tail: self.list_tail,
- length: len - at
+ length: len - at,
};
// Fix the tail ptr of the first part
//
// The inserted node will not appear in further iteration.
match unsafe { self.head.resolve_mut() } {
- None => { self.list.push_back_node(ins_node); }
+ None => {
+ self.list.push_back_node(ins_node);
+ }
Some(node) => {
let prev_node = match unsafe { node.prev.resolve_mut() } {
None => return self.list.push_front_node(ins_node),
issue = "27794")]
pub fn peek_next(&mut self) -> Option<&mut A> {
if self.nelem == 0 {
- return None
- }
- unsafe {
- self.head.resolve_mut().map(|head| &mut head.value)
+ return None;
}
+ unsafe { self.head.resolve_mut().map(|head| &mut head.value) }
}
}
type Item = A;
#[inline]
- fn next(&mut self) -> Option<A> { self.list.pop_front() }
+ fn next(&mut self) -> Option<A> {
+ self.list.pop_front()
+ }
#[inline]
fn size_hint(&self) -> (usize, Option<usize>) {
#[stable(feature = "rust1", since = "1.0.0")]
impl<A> DoubleEndedIterator for IntoIter<A> {
#[inline]
- fn next_back(&mut self) -> Option<A> { self.list.pop_back() }
+ fn next_back(&mut self) -> Option<A> {
+ self.list.pop_back()
+ }
}
#[stable(feature = "rust1", since = "1.0.0")]
#[stable(feature = "rust1", since = "1.0.0")]
impl<A> FromIterator<A> for LinkedList<A> {
- fn from_iter<T: IntoIterator<Item=A>>(iter: T) -> LinkedList<A> {
+ fn from_iter<T: IntoIterator<Item = A>>(iter: T) -> LinkedList<A> {
let mut ret = LinkedList::new();
ret.extend(iter);
ret
/// Consumes the list into an iterator yielding elements by value.
#[inline]
fn into_iter(self) -> IntoIter<T> {
- IntoIter{list: self}
+ IntoIter { list: self }
}
}
#[stable(feature = "rust1", since = "1.0.0")]
impl<A> Extend<A> for LinkedList<A> {
- fn extend<T: IntoIterator<Item=A>>(&mut self, iter: T) {
- for elt in iter { self.push_back(elt); }
+ fn extend<T: IntoIterator<Item = A>>(&mut self, iter: T) {
+ for elt in iter {
+ self.push_back(elt);
+ }
}
}
#[stable(feature = "extend_ref", since = "1.2.0")]
impl<'a, T: 'a + Copy> Extend<&'a T> for LinkedList<T> {
- fn extend<I: IntoIterator<Item=&'a T>>(&mut self, iter: I) {
+ fn extend<I: IntoIterator<Item = &'a T>>(&mut self, iter: I) {
self.extend(iter.into_iter().cloned());
}
}
#[stable(feature = "rust1", since = "1.0.0")]
impl<A: PartialEq> PartialEq for LinkedList<A> {
fn eq(&self, other: &LinkedList<A>) -> bool {
- self.len() == other.len() &&
- self.iter().eq(other.iter())
+ self.len() == other.len() && self.iter().eq(other.iter())
}
fn ne(&self, other: &LinkedList<A>) -> bool {
- self.len() != other.len() ||
- self.iter().ne(other.iter())
+ self.len() != other.len() || self.iter().ne(other.iter())
}
}
mod tests {
use std::clone::Clone;
use std::iter::{Iterator, IntoIterator, Extend};
- use std::option::Option::{Some, None, self};
+ use std::option::Option::{self, Some, None};
use std::__rand::{thread_rng, Rng};
use std::thread;
use std::vec::Vec;
let mut last_ptr: Option<&Node<T>> = None;
let mut node_ptr: &Node<T>;
match list.list_head {
- None => { assert_eq!(0, list.length); return }
+ None => {
+ assert_eq!(0, list.length);
+ return;
+ }
Some(ref node) => node_ptr = &**node,
}
loop {
match unsafe { (last_ptr, node_ptr.prev.resolve()) } {
- (None , None ) => {}
- (None , _ ) => panic!("prev link for list_head"),
+ (None, None) => {}
+ (None, _) => panic!("prev link for list_head"),
(Some(p), Some(pptr)) => {
assert_eq!(p as *const Node<T>, pptr as *const Node<T>);
}
}
// Non-empty to non-empty
- let v = vec![1,2,3,4,5];
- let u = vec![9,8,1,2,3,4,5];
+ let v = vec![1, 2, 3, 4, 5];
+ let u = vec![9, 8, 1, 2, 3, 4, 5];
let mut m = list_from(&v);
let mut n = list_from(&u);
m.append(&mut n);
#[test]
fn test_insert_prev() {
- let mut m = list_from(&[0,2,4,6,8]);
+ let mut m = list_from(&[0, 2, 4, 6, 8]);
let len = m.len();
{
let mut it = m.iter_mut();
}
check_links(&m);
assert_eq!(m.len(), 3 + len * 2);
- assert_eq!(m.into_iter().collect::<Vec<_>>(), [-2,0,1,2,3,4,5,6,7,8,9,0,1]);
+ assert_eq!(m.into_iter().collect::<Vec<_>>(),
+ [-2, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1]);
}
#[test]
fn test_send() {
- let n = list_from(&[1,2,3]);
+ let n = list_from(&[1, 2, 3]);
thread::spawn(move || {
check_links(&n);
- let a: &[_] = &[&1,&2,&3];
+ let a: &[_] = &[&1, &2, &3];
assert_eq!(a, &n.iter().collect::<Vec<_>>()[..]);
- }).join().ok().unwrap();
+ })
+ .join()
+ .ok()
+ .unwrap();
}
#[test]
v.remove(0);
}
}
- 2 | 4 => {
+ 2 | 4 => {
m.push_front(-i);
v.insert(0, -i);
}