Struct NodeId

pub struct NodeId { /* private fields */ }

An identifier used to differentiate between Nodes within a Tree.

NodeIds are not something that the calling context will ever have to worry about generating. Trees generate NodeIds as Nodes are inserted into them.

In addition, each NodeId is specific to the Tree that generated it. This means that if there are two Trees - A and B - there’s no worry of trying to access a Node in A with an identifier that came from B. Doing so will return a Result::Err value instead of returning the wrong Node.

Potential NodeId Issues

Because Trees pass out NodeIds as Nodes are inserted, several issues can occur:

1. If a Node is removed, the NodeId that previously identified it now points to nothing (technically a None value in this case).
2. If a Node is removed and then another is inserted later, the “new” NodeId that is returned can (and will) be the same NodeId that was used to identify a different Node previously.

The above issues may seem like deal-breakers, but our situation isn’t as bad as it seems:

The first issue can be easily detected by the library itself. In this situation, a Result::Err will be returned with the appropriate NodeIdError. The second issue, however, is not something that the library can detect. To mitigate this problem, this library ensures the following:

1. All Node methods that provide NodeIds will return &NodeIds instead of NodeIds.
2. All Tree methods that read or insert data accept &NodeIds instead of taking NodeIds.
3. All Tree methods that remove data take NodeIds instead of accepting &NodeIds.
4. All Nodes that have been removed from a Tree will have their parent and child references cleared (to avoid leaking extra NodeId copies).
5. NodeIds themselves are Clone, but not Copy.

This means that no methods will ever take ownership of a NodeId except for methods that remove a Node from a Tree. The resulting behavior is that unless the caller explicitly Clones a NodeId they should never be in a situation where they accidentally hold onto a NodeId too long. This means that we have “almost safe references” that the caller can clone if they choose to. Doing so, however, will open up the possibility of confusing which NodeIds refer to which Nodes in the calling context.

This does transfer some of the burden to the caller, but any errors should be fairly easy to sort out because an explicit Clone is required for such an error to occur.

Trait Implementations

impl Clone for NodeId

fn clone(&self) -> NodeId

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Debug for NodeId

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl Hash for NodeId

fn hash<__H: Hasher>(&self, state: &mut __H)

Feeds this value into the given Hasher.

fn hash_slice<H>(data: &[Self], state: &mut H)

where H: Hasher, Self: Sized,

Feeds a slice of this type into the given Hasher.

impl Ord for NodeId

fn cmp(&self, other: &NodeId) -> Ordering

This method returns an Ordering between self and other.

fn max(self, other: Self) -> Self

where Self: Sized,

Compares and returns the maximum of two values.

fn min(self, other: Self) -> Self

where Self: Sized,

Compares and returns the minimum of two values.

fn clamp(self, min: Self, max: Self) -> Self

where Self: Sized,

Restrict a value to a certain interval.

impl PartialEq for NodeId

fn eq(&self, other: &NodeId) -> bool

Tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl PartialOrd for NodeId

fn partial_cmp(&self, other: &NodeId) -> Option<Ordering>

This method returns an ordering between self and other values if one exists.

fn lt(&self, other: &Rhs) -> bool

Tests less than (for self and other) and is used by the < operator.

fn le(&self, other: &Rhs) -> bool

Tests less than or equal to (for self and other) and is used by the <= operator.

fn gt(&self, other: &Rhs) -> bool

Tests greater than (for self and other) and is used by the > operator.

fn ge(&self, other: &Rhs) -> bool

Tests greater than or equal to (for self and other) and is used by the >= operator.

impl Eq for NodeId

impl StructuralPartialEq for NodeId