1//! An element in a [Tree](super::Tree)
2///
3/// Contains a niche, and as such, [`Option<TreeRef<T>>`] is free :D
4use std::{marker::PhantomData, num::NonZeroUsize};
56/// An element of in a [Tree](super::Tree).
7//? The index of the node is stored as a [NonZeroUsize] for space savings
8//? Making Refs T-specific helps the user keep track of which Refs belong to which trees.
9//? This isn't bulletproof, of course, but it'll keep Ref<Foo> from being used on Tree<Bar>
10pub struct Ref<T: ?Sized>(NonZeroUsize, PhantomData<T>);
1112impl<T: ?Sized> Ref<T> {
13/// Constructs a new [Ref] with the given index
14pub fn new_unchecked(index: usize) -> Self {
15// Safety: index cannot be zero because we use saturating addition on unsigned type.
16Self(
17unsafe { NonZeroUsize::new_unchecked(index.saturating_add(1)) },
18 PhantomData,
19 )
20 }
21}
2223impl<T: ?Sized> From<Ref<T>> for usize {
24fn from(value: Ref<T>) -> Self {
25 usize::from(value.0) - 1
26}
27}
2829/* --- implementations of derivable traits, because we don't need bounds here --- */
3031impl<T: ?Sized> std::fmt::Debug for Ref<T> {
32fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
33 f.debug_tuple("TreeRef").field(&self.0).finish()
34 }
35}
3637impl<T: ?Sized> std::hash::Hash for Ref<T> {
38fn hash<H: std::hash::Hasher>(&self, state: &mut H) {
39self.0.hash(state);
40self.1.hash(state);
41 }
42}
4344impl<T: ?Sized> PartialEq for Ref<T> {
45fn eq(&self, other: &Self) -> bool {
46self.0 == other.0 && self.1 == other.1
47}
48}
4950impl<T: ?Sized> Eq for Ref<T> {}
5152impl<T: ?Sized> PartialOrd for Ref<T> {
53fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
54Some(self.cmp(other))
55 }
56}
5758impl<T: ?Sized> Ord for Ref<T> {
59fn cmp(&self, other: &Self) -> std::cmp::Ordering {
60self.0.cmp(&other.0)
61 }
62}
6364impl<T: ?Sized> Clone for Ref<T> {
65fn clone(&self) -> Self {
66*self
67}
68}
6970impl<T: ?Sized> Copy for Ref<T> {}