1//! The [`HandleSet`] type and associated definitions.
23use crate::arena::{Arena, Handle, UniqueArena};
45/// A set of `Handle<T>` values.
6#[derive(Debug)]
7pub struct HandleSet<T> {
8/// Bound on indexes of handles stored in this set.
9len: usize,
1011/// `members[i]` is true if the handle with index `i` is a member.
12members: bit_set::BitSet,
1314/// This type is indexed by values of type `T`.
15as_keys: core::marker::PhantomData<T>,
16}
1718impl<T> HandleSet<T> {
19/// Return a new, empty `HandleSet`.
20pub fn new() -> Self {
21Self {
22 len: 0,
23 members: bit_set::BitSet::new(),
24 as_keys: core::marker::PhantomData,
25 }
26 }
2728pub fn is_empty(&self) -> bool {
29self.members.is_empty()
30 }
3132/// Return a new, empty `HandleSet`, sized to hold handles from `arena`.
33pub fn for_arena(arena: &impl ArenaType<T>) -> Self {
34let len = arena.len();
35Self {
36 len,
37 members: bit_set::BitSet::with_capacity(len),
38 as_keys: core::marker::PhantomData,
39 }
40 }
4142/// Remove all members from `self`.
43pub fn clear(&mut self) {
44self.members.clear();
45 }
4647/// Remove all members from `self`, and reserve space to hold handles from `arena`.
48pub fn clear_for_arena(&mut self, arena: &impl ArenaType<T>) {
49self.members.clear();
50self.members.reserve_len(arena.len());
51 }
5253/// Return an iterator over all handles that could be made members
54 /// of this set.
55pub fn all_possible(&self) -> impl Iterator<Item = Handle<T>> {
56super::Range::full_range_from_size(self.len)
57 }
5859/// Add `handle` to the set.
60 ///
61 /// Return `true` if `handle` was not already present in the set.
62pub fn insert(&mut self, handle: Handle<T>) -> bool {
63self.members.insert(handle.index())
64 }
6566/// Remove `handle` from the set.
67 ///
68 /// Returns `true` if `handle` was present in the set.
69pub fn remove(&mut self, handle: Handle<T>) -> bool {
70self.members.remove(handle.index())
71 }
7273/// Add handles from `iter` to the set.
74pub fn insert_iter(&mut self, iter: impl IntoIterator<Item = Handle<T>>) {
75for handle in iter {
76self.insert(handle);
77 }
78 }
7980/// Add all of the handles that can be included in this set.
81pub fn add_all(&mut self) {
82self.members.get_mut().set_all();
83 }
8485pub fn contains(&self, handle: Handle<T>) -> bool {
86self.members.contains(handle.index())
87 }
8889/// Return an iterator over all handles in `self`.
90pub fn iter(&self) -> impl '_ + Iterator<Item = Handle<T>> {
91self.members.iter().map(Handle::from_usize)
92 }
9394/// Removes and returns the numerically largest handle in the set, or `None`
95 /// if the set is empty.
96pub fn pop(&mut self) -> Option<Handle<T>> {
97let members = core::mem::take(&mut self.members);
98let mut vec = members.into_bit_vec();
99let result = vec.iter_mut().enumerate().rev().find_map(|(i, mut bit)| {
100if *bit {
101*bit = false;
102Some(i)
103 } else {
104None
105}
106 });
107self.members = bit_set::BitSet::from_bit_vec(vec);
108 result.map(Handle::from_usize)
109 }
110}
111112impl<T> Default for HandleSet<T> {
113fn default() -> Self {
114Self::new()
115 }
116}
117118pub trait ArenaType<T> {
119fn len(&self) -> usize;
120}
121122impl<T> ArenaType<T> for Arena<T> {
123fn len(&self) -> usize {
124self.len()
125 }
126}
127128impl<T: core::hash::Hash + Eq> ArenaType<T> for UniqueArena<T> {
129fn len(&self) -> usize {
130self.len()
131 }
132}