5 releases
0.1.5 | May 24, 2022 |
---|---|
0.1.4 | May 19, 2022 |
0.1.3 | Dec 3, 2021 |
0.1.2 | Nov 29, 2021 |
0.1.1 | Nov 27, 2021 |
#1251 in Data structures
23 downloads per month
51KB
750 lines
generational_token_list
A doubly-linked list backed by generational-arena. Inspired by indexlist.
Instead of returning pointers or numerical indices to items this data structure returns opaque ItemToken
s.
fn main() {
let mut list = GenerationalTokenList::<i32>::new();
let item1 = list.push_back(10);
let item2 = list.push_back(20);
let item3 = list.push_back(30);
let data = list.into_iter().collect::<Vec<_>>();
assert_eq!(data, vec![10, 20, 30]);
}
Tokens remain valid regardless of other items being inserted or removed. Removing an item invalidates its token. Clearing the list invalidates all tokens.
More details and examples are available in the documentation for the methods.
Useful features
There are a couple features that I think make this crate stand out compared to other similar crates. Some crates implement a few of these features but I haven't found one that implements all of them (or at the very least, both 1 and 2).
- Insertion of items relative to other items
fn main() {
let mut list = GenerationalTokenList::<i32>::new();
let item1 = list.push_back(10);
list.push_back(20);
list.insert_after(item1, 300);
// list: [10, 300, 20]
}
- All push/insert methods have a variant that takes a
FnOnce
allowing creation of items that know their own token
fn main() {
struct Meta {
data: u8,
my_token: ItemToken,
}
let mut list = GenerationalTokenList::new();
let item1 = list.push_back_with(|token| Meta { data: 1, my_token: token });
let item2 = list.push_back_with(|token| Meta { data: 2, my_token: token });
let item1_data = list.head().unwrap();
assert_eq!(item1, item1_data.my_token);
}
- Passthrough of
get2_mut
method from generational-arena. - Implements
Iter
andIterMut
1 traits.
1 requires enabling iter-mut
feature
Cargo features
iter-mut
: enables theiter_mut
method. See "Safety" section for more details.
Safety
By default, this crate is forbid(unsafe_code)
.
If you need GenerationalTokenList::iter_mut
and/or GenerationalTokenList::iter_with_tokens_mut
then you must enable the iter-mut
feature. Doing so makes the crate deny(unsafe_code)
, and the unsafe
block inside iter_mut
is excluded via allow(unsafe_code)
.
Similar crates
TODO
Pull requests are welcome :)
- Implement
Drain
- Implement
try_push_*
andtry_insert_*
methods - Implement flavors of
push_*_with
andinsert_*_with
that allow fallible insertion of items? E.g.:
pub fn push_back_fallible(&mut self, create: impl FnOnce(ItemToken) -> Result<T>) -> Result<ItemToken> {
//...
}
- Add
no-std
support?' - Consider adding
#[inline]
to some methods?
Disclaimer
This is not an official Agilent product. No support is implied.
Dependencies
~56KB