intrex

Intrusive doubly-linked lists with items stored in an application-provided object pool and addressed by indices.

use intrex::list::{Head, Link};

struct Node {
    value: i32,
    siblings: Option<Link>,
}

let mut nodes: Vec<_> = (0..4)
    .map(|value| Node { value, siblings: None })
    .collect();
let mut head = Head::default();

// Add [2, 3, 1, 0] to the list
let mut accessor = head
    .accessor_mut(&mut nodes, |n: &mut Node| &mut n.siblings);
accessor.push_back(3);
accessor.push_back(0);
accessor.insert(1, Some(0));
accessor.push_front(2);

// Inspect the list
let accessor = head.accessor(&nodes, |n| &n.siblings);
assert_eq!(accessor.front().unwrap().value, 2);
assert_eq!(accessor.back().unwrap().value, 0);
assert_eq!(
    accessor.values().map(|n| n.value).collect::<Vec<_>>(),
    vec![2, 3, 1, 0],
);

// Sort the list
head.accessor_mut(&mut nodes, |n: &mut Node| &mut n.siblings)
    .sort_by_key(|nodes, i| nodes[i].value);

let accessor = head.accessor(&nodes, |n| &n.siblings);
assert_eq!(
    accessor.values().map(|n| n.value).collect::<Vec<_>>(),
    vec![0, 1, 2, 3],
);

This crate also provides a function to sort singly-linked lists.

License

MIT/Apache-2.0