unique_pointer/lib.rs
1#![allow(unused)]
2#![feature(intra_doc_pointers)]
3#![doc(issue_tracker_base_url = "https://github.com/gabrielfalcao/unique-pointer/issues/")]
4//! [UniquePointer] is an experimental data structure that makes
5//! extensive use of unsafe rust to provide a shared pointer
6//! throughout the runtime of a rust program as transparently as
7//! possible.
8//!
9//!
10//! # Crate Features
11//!
12//! ### `allow-no-debug`
13//!
14//! > Permits using `UniquePointer<T>` where `T` does not implement `std::fmt::Debug`
15//!
16//!
17//! # Binary Tree Example
18//!
19//! ### Binary Tree Implementation
20//!
21//! ```
22//! use unique_pointer::{RefCounter, UniquePointer};
23//!
24//! use std::borrow::Cow;
25//! use std::convert::{AsMut, AsRef};
26//! use std::cmp::{Eq, Ord, Ordering, PartialEq, PartialOrd};
27//!
28//! # #[derive(Clone, PartialOrd, Ord, Default, PartialEq, Eq, Hash)]
29//! # pub enum Value<'c> {
30//! # #[default]
31//! # Nil,
32//! # String(Cow<'c, str>),
33//! # Byte(u8),
34//! # UInt(u64),
35//! # Int(i64),
36//! # }
37//! # impl<'c> Value<'_> {
38//! # pub fn nil() -> Value<'c> {
39//! # Value::Nil
40//! # }
41//! #
42//! # pub fn is_nil(&self) -> bool {
43//! # if *self == Value::Nil {
44//! # true
45//! # } else {
46//! # false
47//! # }
48//! # }
49//! # }
50//! #
51//! # impl<'c> Drop for Value<'c> {
52//! # fn drop(&mut self) {}
53//! # }
54//! #
55//! # impl std::fmt::Display for Value<'_> {
56//! # fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
57//! # write!(
58//! # f,
59//! # "{}",
60//! # match self {
61//! # Value::Nil => "nil".to_string(),
62//! # Value::String(h) => format!("{}", h),
63//! # Value::Byte(h) => format!("{}", h),
64//! # Value::UInt(h) => format!("{}", h),
65//! # Value::Int(h) => format!("{}", h),
66//! # }
67//! # )
68//! # }
69//! # }
70//! # impl std::fmt::Debug for Value<'_> {
71//! # fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
72//! # write!(
73//! # f,
74//! # "{}",
75//! # match self {
76//! # Value::Nil => "nil".to_string(),
77//! # Value::String(h) => format!("{:#?}", h),
78//! # Value::Byte(h) => format!("{}u8", h),
79//! # Value::UInt(h) => format!("{}u64", h),
80//! # Value::Int(h) => format!("{}i64", h),
81//! # }
82//! # )
83//! # }
84//! # }
85//! #
86//! # impl<'c> From<u8> for Value<'c> {
87//! # fn from(value: u8) -> Value<'c> {
88//! # Value::Byte(value)
89//! # }
90//! # }
91//! # impl<'c> From<u64> for Value<'c> {
92//! # fn from(value: u64) -> Value<'c> {
93//! # Value::UInt(value)
94//! # }
95//! # }
96//! # impl<'c> From<i64> for Value<'c> {
97//! # fn from(value: i64) -> Value<'c> {
98//! # Value::Int(value)
99//! # }
100//! # }
101//! # impl<'c> From<&'c str> for Value<'c> {
102//! # fn from(value: &'c str) -> Value<'c> {
103//! # Value::String(Cow::from(value))
104//! # }
105//! # }
106//! # impl<'c> From<Cow<'c, str>> for Value<'c> {
107//! # fn from(value: Cow<'c, str>) -> Value<'c> {
108//! # Value::from(value.into_owned())
109//! # }
110//! # }
111//! # impl<'c> From<&'c mut str> for Value<'c> {
112//! # fn from(value: &'c mut str) -> Value<'c> {
113//! # Value::String(Cow::<'c, str>::Borrowed(&*value))
114//! # }
115//! # }
116//! # impl<'c> From<String> for Value<'c> {
117//! # fn from(value: String) -> Value<'c> {
118//! # Value::String(Cow::from(value))
119//! # }
120//! # }
121//! # impl<'c> From<Option<String>> for Value<'c> {
122//! # fn from(value: Option<String>) -> Value<'c> {
123//! # match value {
124//! # None => Value::Nil,
125//! # Some(value) => Value::from(value),
126//! # }
127//! # }
128//! # }
129//! #
130//! # impl<'c> AsRef<Value<'c>> for Value<'c> {
131//! # fn as_ref(&self) -> &Value<'c> {
132//! # unsafe { &*self }
133//! # }
134//! # }
135//! # impl<'c> AsMut<Value<'c>> for Value<'c> {
136//! # fn as_mut(&mut self) -> &mut Value<'c> {
137//! # unsafe { &mut *self }
138//! # }
139//! # }
140//! #
141//! # impl<'c> PartialEq<&Value<'c>> for Value<'c> {
142//! # fn eq(&self, other: &&Value<'c>) -> bool {
143//! # let other = unsafe { &**other };
144//! # self == other
145//! # }
146//! # }
147//! #
148//! # impl<'c> PartialEq<&mut Value<'c>> for Value<'c> {
149//! # fn eq(&self, other: &&mut Value<'c>) -> bool {
150//! # let other = unsafe { &**other };
151//! # self == other
152//! # }
153//! # }
154//! #
155//! pub struct Node<'c> {
156//! pub parent: UniquePointer<Node<'c>>,
157//! pub left: UniquePointer<Node<'c>>,
158//! pub right: UniquePointer<Node<'c>>,
159//! pub item: UniquePointer<Value<'c>>,
160//! refs: RefCounter,
161//! }
162//!
163//! impl<'c> Node<'c> {
164//! pub fn nil() -> Node<'c> {
165//! Node {
166//! parent: UniquePointer::<Node<'c>>::null(),
167//! left: UniquePointer::<Node<'c>>::null(),
168//! right: UniquePointer::<Node<'c>>::null(),
169//! item: UniquePointer::<Value<'c>>::null(),
170//! refs: RefCounter::new(),
171//! }
172//! }
173//!
174//! pub fn is_nil(&self) -> bool {
175//! self.item.is_null()
176//! && self.left.is_null()
177//! && self.right.is_null()
178//! && self.parent.is_null()
179//! && self.refs <= 1
180//! }
181//!
182//! pub fn new(value: Value<'c>) -> Node<'c> {
183//! let mut node = Node::nil();
184//! unsafe {
185//! node.item.write(value);
186//! }
187//! node
188//! }
189//!
190//! pub fn parent(&self) -> Option<&'c Node<'c>> {
191//! self.parent.as_ref()
192//! }
193//!
194//! pub fn parent_mut(&mut self) -> Option<&'c mut Node<'c>> {
195//! self.parent.as_mut()
196//! }
197//!
198//! pub fn item(&self) -> Value<'c> {
199//! self.value().unwrap_or_default()
200//! }
201//!
202//! pub fn id(&self) -> String {
203//! format!(
204//! "{}{}",
205//! if self.item.is_null() {
206//! format!("Null Node {:p}", self)
207//! } else {
208//! format!("Node {}", self.item())
209//! },
210//! format!(" ({} referefences)", self.refs)
211//! )
212//! }
213//!
214//! pub fn value(&self) -> Option<Value<'c>> {
215//! if self.item.is_null() {
216//! None
217//! } else {
218//! unsafe {
219//! if let Some(value) = self.item.as_ref() {
220//! Some(value.clone())
221//! } else {
222//! None
223//! }
224//! }
225//! }
226//! }
227//!
228//! pub fn parent_value(&self) -> Option<Value<'c>> {
229//! if let Some(parent) = self.parent() {
230//! parent.value()
231//! } else {
232//! None
233//! }
234//! }
235//!
236//! pub fn set_left(&mut self, left: &mut Node<'c>) {
237//! self.incr_ref();
238//! left.parent = self.ptr();
239//! self.left = left.ptr();
240//! left.incr_ref();
241//! }
242//!
243//! pub fn set_right(&mut self, right: &mut Node<'c>) {
244//! self.incr_ref();
245//! right.parent = self.ptr();
246//! self.right = right.ptr();
247//! right.incr_ref();
248//! }
249//!
250//! pub fn delete_left(&mut self) {
251//! if self.left.is_null() {
252//! return;
253//! }
254//! let left = self.left.inner_mut();
255//! left.decr_ref();
256//! self.left.dealloc(true);
257//! self.left = UniquePointer::null();
258//! }
259//!
260//! pub fn left(&self) -> Option<&'c Node<'c>> {
261//! let left = self.left.as_ref();
262//! left
263//! }
264//!
265//! pub fn left_mut(&mut self) -> Option<&'c mut Node<'c>> {
266//! self.left.as_mut()
267//! }
268//!
269//! pub fn left_value(&self) -> Option<Value<'c>> {
270//! if let Some(left) = self.left() {
271//! left.value()
272//! } else {
273//! None
274//! }
275//! }
276//!
277//! pub fn delete_right(&mut self) {
278//! if self.right.is_null() {
279//! return;
280//! }
281//! let right = self.right.inner_mut();
282//! right.decr_ref();
283//! self.right.dealloc(true);
284//! self.right = UniquePointer::null();
285//! }
286//!
287//! pub fn right(&self) -> Option<&'c Node<'c>> {
288//! self.right.as_ref()
289//! }
290//!
291//! pub fn right_mut(&mut self) -> Option<&'c mut Node<'c>> {
292//! self.right.as_mut()
293//! }
294//!
295//! pub fn right_value(&self) -> Option<Value<'c>> {
296//! if let Some(right) = self.right() {
297//! right.value()
298//! } else {
299//! None
300//! }
301//! }
302//!
303//! pub fn height(&self) -> usize {
304//! let mut node = self;
305//! let mut vertices = 0;
306//!
307//! while !node.left.is_null() {
308//! node = node.left.inner_ref();
309//! vertices += 1;
310//! }
311//! vertices
312//! }
313//!
314//! pub fn depth(&self) -> usize {
315//! let mut node = self;
316//! if self.parent.is_null() {
317//! return 0;
318//! }
319//! let mut vertices = 0;
320//!
321//! while !node.parent.is_null() {
322//! node = node.parent.inner_ref();
323//! vertices += 1;
324//! }
325//! vertices
326//! }
327//!
328//! pub fn leaf(&self) -> bool {
329//! self.left.is_null() && self.right.is_null()
330//! }
331//!
332//! pub fn addr(&self) -> usize {
333//! (self as *const Node<'c>).addr()
334//! }
335//!
336//! pub fn left_addr(&self) -> usize {
337//! self.left.addr()
338//! }
339//!
340//! pub fn right_addr(&self) -> usize {
341//! self.right.addr()
342//! }
343//!
344//! pub fn parent_addr(&self) -> usize {
345//! self.parent.addr()
346//! }
347//!
348//! pub fn refs(&self) -> usize {
349//! *self.refs
350//! }
351//!
352//! pub fn subtree_first(&self) -> &'c Node<'c> {
353//! if self.left.is_null() {
354//! let node = self as *const Node<'c>;
355//! return unsafe { node.as_ref().unwrap() };
356//! }
357//!
358//! let mut subtree_first = self.left.cast_mut();
359//!
360//! loop {
361//! unsafe {
362//! let node = &*subtree_first;
363//! if node.left.is_null() {
364//! break;
365//! }
366//! subtree_first = node.left.cast_mut()
367//! }
368//! }
369//! unsafe { subtree_first.as_mut().unwrap() }
370//! }
371//!
372//! pub fn successor(&self) -> &'c Node<'c> {
373//! if !self.right.is_null() {
374//! return unsafe { self.right.as_ref().unwrap() }.subtree_first();
375//! }
376//!
377//! if let Some(parent) = self.parent() {
378//! if parent.parent.is_null() {
379//! return self.subtree_first();
380//! }
381//! }
382//! let mut successor = self as *const Node<'c>;
383//! let mut node = unsafe { &*successor };
384//! loop {
385//! if node.left() == Some(self) {
386//! break;
387//! }
388//! if !node.parent.is_null() {
389//! successor = node.parent.cast_const();
390//! node = unsafe { &*successor };
391//! } else {
392//! break;
393//! };
394//! }
395//! unsafe { &*successor }
396//! }
397//!
398//! pub fn subtree_first_mut(&mut self) -> &'c mut Node<'c> {
399//! if self.left.is_null() {
400//! let node = self as *mut Node<'c>;
401//! return {
402//! let node = unsafe {
403//! let node = &mut *node;
404//! node
405//! };
406//! unsafe { std::mem::transmute::<&mut Node<'c>, &'c mut Node<'c>>(node) }
407//! };
408//! }
409//!
410//! let mut subtree_first = &mut self.left;
411//!
412//! loop {
413//! unsafe {
414//! let node = subtree_first.inner_mut();
415//! if node.left.is_null() {
416//! break;
417//! }
418//! subtree_first = &mut node.left;
419//! }
420//! }
421//!
422//! subtree_first.inner_mut()
423//! }
424//!
425//! pub fn successor_mut(&mut self) -> &'c mut Node<'c> {
426//! if !self.right.is_null() {
427//! return self.right.inner_mut().subtree_first_mut();
428//! }
429//!
430//! if let Some(parent) = self.parent() {
431//! if parent.parent.is_null() {
432//! return self.subtree_first_mut();
433//! }
434//! }
435//! let mut successor = self as *mut Node<'c>;
436//! let mut node = {
437//! let node = unsafe {
438//! let node = &mut *successor;
439//! node
440//! };
441//! unsafe { std::mem::transmute::<&mut Node<'c>, &'c mut Node<'c>>(node) }
442//! };
443//!
444//! loop {
445//! if node.left() == Some(self) {
446//! break;
447//! }
448//! if !node.parent.is_null() {
449//! successor = node.parent.cast_mut();
450//! node = {
451//! let node = unsafe {
452//! let node = &mut *successor;
453//! node
454//! };
455//! unsafe { std::mem::transmute::<&mut Node<'c>, &'c mut Node<'c>>(node) }
456//! };
457//! } else {
458//! break;
459//! };
460//! }
461//! {
462//! let node = unsafe {
463//! let node = &mut *successor;
464//! node
465//! };
466//! unsafe { std::mem::transmute::<&mut Node<'c>, &'c mut Node<'c>>(node) }
467//! }
468//! }
469//!
470//! pub fn subtree_insert_after(&mut self, new: &mut Node<'c>) {
471//! if self.right.is_null() {
472//! self.set_right(new);
473//! } else {
474//! let successor = self.successor_mut();
475//! successor.set_left(new);
476//! }
477//! }
478//!
479//! pub fn predecessor(&self) -> &'c Node<'c> {
480//! let mut predecessor = self as *const Node<'c>;
481//! let mut node = {
482//! let node = unsafe {
483//! let node = &*predecessor;
484//! node
485//! };
486//! unsafe { std::mem::transmute::<&Node<'c>, &'c Node<'c>>(node) }
487//! };
488//!
489//! loop {
490//! if !node.left.is_null() {
491//! predecessor = node.left.cast_const();
492//! node = {
493//! let node = unsafe {
494//! let node = &*predecessor;
495//! node
496//! };
497//! unsafe { std::mem::transmute::<&Node<'c>, &'c Node<'c>>(node) }
498//! };
499//! if !node.right.is_null() {
500//! predecessor = node.right.cast_const();
501//! node = {
502//! let node = unsafe {
503//! let node = &*predecessor;
504//! node
505//! };
506//! unsafe { std::mem::transmute::<&Node<'c>, &'c Node<'c>>(node) }
507//! };
508//! }
509//! break;
510//! } else if !node.parent.is_null() {
511//! predecessor = node.parent.cast_const();
512//! node = {
513//! let node = unsafe {
514//! let node = &*predecessor;
515//! node
516//! };
517//! unsafe { std::mem::transmute::<&Node<'c>, &'c Node<'c>>(node) }
518//! };
519//! if let Some(right) = node.right() {
520//! if right == self {
521//! break;
522//! }
523//! }
524//! }
525//! }
526//! node = {
527//! let node = unsafe {
528//! let node = &*predecessor;
529//! node
530//! };
531//! unsafe { std::mem::transmute::<&Node<'c>, &'c Node<'c>>(node) }
532//! };
533//! node
534//! }
535//!
536//! pub fn predecessor_mut(&mut self) -> &'c mut Node<'c> {
537//! let mut predecessor = UniquePointer::<Node<'c>>::from_ref_mut(self);
538//! let mut node = predecessor.inner_mut();
539//!
540//! loop {
541//! if !node.left.is_null() {
542//! predecessor = node.left.clone();
543//! node = predecessor.inner_mut();
544//! if !node.right.is_null() {
545//! predecessor = node.right.clone();
546//! node = predecessor.inner_mut();
547//! }
548//! break;
549//! } else if !node.parent.is_null() {
550//! predecessor = node.parent.clone();
551//! node = predecessor.inner_mut();
552//!
553//! if let Some(right) = node.right() {
554//! if right == self {
555//! break;
556//! }
557//! }
558//! }
559//! }
560//! predecessor.inner_mut()
561//! }
562//!
563//! pub fn dealloc(&mut self) {
564//! if self.refs > 0 {
565//! self.decr_ref();
566//! } else {
567//! if !self.parent.is_null() {
568//! self.parent.drop_in_place();
569//! // self.parent = UniquePointer::null();
570//! }
571//! if !self.left.is_null() {
572//! self.left.drop_in_place();
573//! // self.left = UniquePointer::null();
574//! }
575//! if !self.right.is_null() {
576//! self.right.drop_in_place();
577//! // self.right = UniquePointer::null();
578//! }
579//! if !self.item.is_null() {
580//! self.item.drop_in_place();
581//! // self.item = UniquePointer::null();
582//! }
583//! }
584//! }
585//!
586//! pub fn swap_item(&mut self, other: &mut Self) {
587//! unsafe {
588//! self.item.swap(&mut other.item);
589//! };
590//! }
591//! }
592//!
593//! pub fn subtree_delete<'c>(node: &mut Node<'c>) {
594//! if node.leaf() {
595//! node.decr_ref();
596//! if node.parent.is_not_null() {
597//! unsafe {
598//! let parent = node.parent.inner_mut();
599//! let delete_left = if let Some(parents_left_child) = parent.left() {
600//! parents_left_child == node
601//! } else {
602//! false
603//! };
604//! if delete_left {
605//! parent.left.dealloc(true);
606//! parent.left = UniquePointer::null();
607//! } else {
608//! parent.right.dealloc(true);
609//! parent.right = UniquePointer::null();
610//! }
611//! }
612//! node.parent.dealloc(true);
613//! node.parent = UniquePointer::null();
614//! }
615//! node.refs.reset();
616//! node.parent = UniquePointer::<Node<'c>>::null();
617//! return;
618//! } else {
619//! let predecessor = node.predecessor_mut();
620//! predecessor.swap_item(node);
621//! subtree_delete(predecessor);
622//! }
623//! }
624//!
625//! // Node private methods
626//! impl<'c> Node<'c> {
627//! pub fn ptr(&self) -> UniquePointer<Node<'c>> {
628//! let ptr = UniquePointer::copy_from_ref(self, *self.refs);
629//! ptr
630//! }
631//!
632//! fn incr_ref(&mut self) {
633//! self.refs += 1;
634//! let mut node = self;
635//! while !node.parent.is_null() {
636//! unsafe {
637//! node = node.parent.inner_mut();
638//! node.refs += 1;
639//! }
640//! }
641//! }
642//!
643//! fn decr_ref(&mut self) {
644//! self.refs -= 1;
645//! let mut node = self;
646//! while !node.parent.is_null() {
647//! unsafe {
648//! node = node.parent.inner_mut();
649//! node.refs -= 1;
650//! }
651//! }
652//! }
653//!
654//! fn item_eq(&self, other: &Node<'c>) -> bool {
655//! if self.item.addr() == other.item.addr() {
656//! self.item.addr() == other.item.addr()
657//! } else {
658//! self.value() == other.value()
659//! }
660//! }
661//! }
662//!
663//! impl<'c> PartialEq<Node<'c>> for Node<'c> {
664//! fn eq(&self, other: &Node<'c>) -> bool {
665//! if self.item_eq(other) {
666//! let eq = self.value().unwrap_or_default() == other.value().unwrap_or_default();
667//! eq
668//! } else {
669//! false
670//! }
671//! }
672//! }
673//!
674//! impl<'c> PartialEq<&mut Node<'c>> for Node<'c> {
675//! fn eq(&self, other: &&mut Node<'c>) -> bool {
676//! let other = unsafe { &**other };
677//! if self.item_eq(other) {
678//! let eq = self.value().unwrap_or_default() == other.value().unwrap_or_default();
679//! eq
680//! } else {
681//! false
682//! }
683//! }
684//! }
685//!
686//! impl<'c> Drop for Node<'c> {
687//! fn drop(&mut self) {
688//! self.dealloc();
689//! }
690//! }
691//!
692//! impl<'c> Clone for Node<'c> {
693//! fn clone(&self) -> Node<'c> {
694//! let mut node = Node::nil();
695//! node.refs = self.refs.clone();
696//! if self.parent.is_not_null() {
697//! node.parent = self.parent.clone();
698//! }
699//! if self.left.is_not_null() {
700//! node.left = self.left.clone();
701//! }
702//! if self.right.is_not_null() {
703//! node.right = self.right.clone();
704//! }
705//! if !self.item.is_null() {
706//! node.item = self.item.clone();
707//! }
708//! node
709//! }
710//! }
711//!
712//! impl<'c> AsRef<Node<'c>> for Node<'c> {
713//! fn as_ref(&self) -> &'c Node<'c> {
714//! unsafe { std::mem::transmute::<&Node<'c>, &'c Node<'c>>(self) }
715//! }
716//! }
717//! impl<'c> AsMut<Node<'c>> for Node<'c> {
718//! fn as_mut(&mut self) -> &'c mut Node<'c> {
719//! self.incr_ref();
720//! let node = unsafe {
721//! let node = &mut *self as *mut Node<'c>;
722//! node
723//! };
724//! unsafe { std::mem::transmute::<&mut Node<'c>, &'c mut Node<'c>>(self) }
725//! }
726//! }
727//! impl<'c> std::fmt::Display for Node<'c> {
728//! fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
729//! write!(f, "{}", self.id())
730//! }
731//! }
732//! impl<'c> std::fmt::Debug for Node<'c> {
733//! fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
734//! write!(
735//! f,
736//! "{}",
737//! [
738//! format!("Node@"),
739//! format!("{:016x}", self.addr()),
740//! format!("[refs={}]", *self.refs),
741//! if self.item.is_null() {
742//! format!("null")
743//! } else {
744//! format!(
745//! "[item={}]",
746//! self.value()
747//! .map(|value| format!("{:#?}", value))
748//! .unwrap_or_else(|| format!("empty"))
749//! )
750//! },
751//! if self.parent.is_null() {
752//! String::new()
753//! } else {
754//! format!(
755//! "(parent:{})",
756//! if self.parent.is_null() {
757//! format!("null")
758//! } else {
759//! self.parent_value()
760//! .map(|parent_value| format!("{:#?}", parent_value))
761//! .unwrap_or_else(|| format!("empty"))
762//! }
763//! )
764//! },
765//! if self.left.is_null() && self.right.is_null() {
766//! String::new()
767//! } else {
768//! format!(
769//! "[left:{} | right:{}]",
770//! if self.left.is_null() {
771//! format!("null")
772//! } else {
773//! self.left_value()
774//! .map(|left_value| format!("{:#?}", left_value))
775//! .unwrap_or_else(|| format!("empty"))
776//! },
777//! if self.right.is_null() {
778//! format!("null")
779//! } else {
780//! self.right_value()
781//! .map(|right_value| format!("{:#?}", right_value))
782//! .unwrap_or_else(|| format!("empty"))
783//! }
784//! )
785//! }
786//! ]
787//! .join("")
788//! )
789//! }
790//! }
791//! ```
792//!
793//! ### Testing the Binary Tree
794//!
795//! ```
796//! # use std::borrow::Cow;
797//! # use std::convert::{AsMut, AsRef};
798//! # use std::cmp::{Eq, Ord, Ordering, PartialEq, PartialOrd};
799//! # use unique_pointer::{UniquePointer, RefCounter};
800//! # #[derive(Clone, PartialOrd, Ord, Default, PartialEq, Eq, Hash)]
801//! # pub enum Value<'c> {
802//! # #[default]
803//! # Nil,
804//! # String(Cow<'c, str>),
805//! # Byte(u8),
806//! # UInt(u64),
807//! # Int(i64),
808//! # }
809//! # impl<'c> Value<'_> {
810//! # pub fn nil() -> Value<'c> {
811//! # Value::Nil
812//! # }
813//! #
814//! # pub fn is_nil(&self) -> bool {
815//! # if *self == Value::Nil {
816//! # true
817//! # } else {
818//! # false
819//! # }
820//! # }
821//! # }
822//! #
823//! # impl<'c> Drop for Value<'c> {
824//! # fn drop(&mut self) {}
825//! # }
826//! #
827//! # impl std::fmt::Display for Value<'_> {
828//! # fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
829//! # write!(
830//! # f,
831//! # "{}",
832//! # match self {
833//! # Value::Nil => "nil".to_string(),
834//! # Value::String(h) => format!("{}", h),
835//! # Value::Byte(h) => format!("{}", h),
836//! # Value::UInt(h) => format!("{}", h),
837//! # Value::Int(h) => format!("{}", h),
838//! # }
839//! # )
840//! # }
841//! # }
842//! # impl std::fmt::Debug for Value<'_> {
843//! # fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
844//! # write!(
845//! # f,
846//! # "{}",
847//! # match self {
848//! # Value::Nil => "nil".to_string(),
849//! # Value::String(h) => format!("{:#?}", h),
850//! # Value::Byte(h) => format!("{}u8", h),
851//! # Value::UInt(h) => format!("{}u64", h),
852//! # Value::Int(h) => format!("{}i64", h),
853//! # }
854//! # )
855//! # }
856//! # }
857//! #
858//! # impl<'c> From<u8> for Value<'c> {
859//! # fn from(value: u8) -> Value<'c> {
860//! # Value::Byte(value)
861//! # }
862//! # }
863//! # impl<'c> From<u64> for Value<'c> {
864//! # fn from(value: u64) -> Value<'c> {
865//! # Value::UInt(value)
866//! # }
867//! # }
868//! # impl<'c> From<i64> for Value<'c> {
869//! # fn from(value: i64) -> Value<'c> {
870//! # Value::Int(value)
871//! # }
872//! # }
873//! # impl<'c> From<&'c str> for Value<'c> {
874//! # fn from(value: &'c str) -> Value<'c> {
875//! # Value::String(Cow::from(value))
876//! # }
877//! # }
878//! # impl<'c> From<Cow<'c, str>> for Value<'c> {
879//! # fn from(value: Cow<'c, str>) -> Value<'c> {
880//! # Value::from(value.into_owned())
881//! # }
882//! # }
883//! # impl<'c> From<&'c mut str> for Value<'c> {
884//! # fn from(value: &'c mut str) -> Value<'c> {
885//! # Value::String(Cow::<'c, str>::Borrowed(&*value))
886//! # }
887//! # }
888//! # impl<'c> From<String> for Value<'c> {
889//! # fn from(value: String) -> Value<'c> {
890//! # Value::String(Cow::from(value))
891//! # }
892//! # }
893//! # impl<'c> From<Option<String>> for Value<'c> {
894//! # fn from(value: Option<String>) -> Value<'c> {
895//! # match value {
896//! # None => Value::Nil,
897//! # Some(value) => Value::from(value),
898//! # }
899//! # }
900//! # }
901//! #
902//! # impl<'c> AsRef<Value<'c>> for Value<'c> {
903//! # fn as_ref(&self) -> &Value<'c> {
904//! # unsafe { &*self }
905//! # }
906//! # }
907//! # impl<'c> AsMut<Value<'c>> for Value<'c> {
908//! # fn as_mut(&mut self) -> &mut Value<'c> {
909//! # unsafe { &mut *self }
910//! # }
911//! # }
912//! #
913//! # impl<'c> PartialEq<&Value<'c>> for Value<'c> {
914//! # fn eq(&self, other: &&Value<'c>) -> bool {
915//! # let other = unsafe { &**other };
916//! # self == other
917//! # }
918//! # }
919//! #
920//! # impl<'c> PartialEq<&mut Value<'c>> for Value<'c> {
921//! # fn eq(&self, other: &&mut Value<'c>) -> bool {
922//! # let other = unsafe { &**other };
923//! # self == other
924//! # }
925//! # }
926//! #
927//! #
928//! # pub struct Node<'c> {
929//! # pub parent: UniquePointer<Node<'c>>,
930//! # pub left: UniquePointer<Node<'c>>,
931//! # pub right: UniquePointer<Node<'c>>,
932//! # pub item: UniquePointer<Value<'c>>,
933//! # refs: RefCounter,
934//! # }
935//! #
936//! # impl<'c> Node<'c> {
937//! # pub fn nil() -> Node<'c> {
938//! # Node {
939//! # parent: UniquePointer::<Node<'c>>::null(),
940//! # left: UniquePointer::<Node<'c>>::null(),
941//! # right: UniquePointer::<Node<'c>>::null(),
942//! # item: UniquePointer::<Value<'c>>::null(),
943//! # refs: RefCounter::new(),
944//! # }
945//! # }
946//! #
947//! # pub fn is_nil(&self) -> bool {
948//! # self.item.is_null()
949//! # && self.left.is_null()
950//! # && self.right.is_null()
951//! # && self.parent.is_null()
952//! # && self.refs <= 1
953//! # }
954//! #
955//! # pub fn new(value: Value<'c>) -> Node<'c> {
956//! # let mut node = Node::nil();
957//! # unsafe {
958//! # node.item.write(value);
959//! # }
960//! # node
961//! # }
962//! #
963//! # pub fn parent(&self) -> Option<&'c Node<'c>> {
964//! # self.parent.as_ref()
965//! # }
966//! #
967//! # pub fn parent_mut(&mut self) -> Option<&'c mut Node<'c>> {
968//! # self.parent.as_mut()
969//! # }
970//! #
971//! # pub fn item(&self) -> Value<'c> {
972//! # self.value().unwrap_or_default()
973//! # }
974//! #
975//! # pub fn id(&self) -> String {
976//! # format!(
977//! # "{}{}",
978//! # if self.item.is_null() {
979//! # format!("Null Node {:p}", self)
980//! # } else {
981//! # format!("Node {}", self.item())
982//! # },
983//! # format!(" ({} referefences)", self.refs)
984//! # )
985//! # }
986//! #
987//! # pub fn value(&self) -> Option<Value<'c>> {
988//! # if self.item.is_null() {
989//! # None
990//! # } else {
991//! # unsafe {
992//! # if let Some(value) = self.item.as_ref() {
993//! # Some(value.clone())
994//! # } else {
995//! # None
996//! # }
997//! # }
998//! # }
999//! # }
1000//! #
1001//! # pub fn parent_value(&self) -> Option<Value<'c>> {
1002//! # if let Some(parent) = self.parent() {
1003//! # parent.value()
1004//! # } else {
1005//! # None
1006//! # }
1007//! # }
1008//! #
1009//! # pub fn set_left(&mut self, left: &mut Node<'c>) {
1010//! # self.incr_ref();
1011//! # left.parent = self.ptr();
1012//! # self.left = left.ptr();
1013//! # left.incr_ref();
1014//! # }
1015//! #
1016//! # pub fn set_right(&mut self, right: &mut Node<'c>) {
1017//! # self.incr_ref();
1018//! # right.parent = self.ptr();
1019//! # self.right = right.ptr();
1020//! # right.incr_ref();
1021//! # }
1022//! #
1023//! # pub fn delete_left(&mut self) {
1024//! # if self.left.is_null() {
1025//! # return;
1026//! # }
1027//! # let left = self.left.inner_mut();
1028//! # left.decr_ref();
1029//! # self.left.dealloc(true);
1030//! # self.left = UniquePointer::null();
1031//! # }
1032//! #
1033//! # pub fn left(&self) -> Option<&'c Node<'c>> {
1034//! # let left = self.left.as_ref();
1035//! # left
1036//! # }
1037//! #
1038//! # pub fn left_mut(&mut self) -> Option<&'c mut Node<'c>> {
1039//! # self.left.as_mut()
1040//! # }
1041//! #
1042//! # pub fn left_value(&self) -> Option<Value<'c>> {
1043//! # if let Some(left) = self.left() {
1044//! # left.value()
1045//! # } else {
1046//! # None
1047//! # }
1048//! # }
1049//! #
1050//! # pub fn delete_right(&mut self) {
1051//! # if self.right.is_null() {
1052//! # return;
1053//! # }
1054//! # let right = self.right.inner_mut();
1055//! # right.decr_ref();
1056//! # self.right.dealloc(true);
1057//! # self.right = UniquePointer::null();
1058//! # }
1059//! #
1060//! # pub fn right(&self) -> Option<&'c Node<'c>> {
1061//! # self.right.as_ref()
1062//! # }
1063//! #
1064//! # pub fn right_mut(&mut self) -> Option<&'c mut Node<'c>> {
1065//! # self.right.as_mut()
1066//! # }
1067//! #
1068//! # pub fn right_value(&self) -> Option<Value<'c>> {
1069//! # if let Some(right) = self.right() {
1070//! # right.value()
1071//! # } else {
1072//! # None
1073//! # }
1074//! # }
1075//! #
1076//! # pub fn height(&self) -> usize {
1077//! # let mut node = self;
1078//! # let mut vertices = 0;
1079//! #
1080//! # while !node.left.is_null() {
1081//! # node = node.left.inner_ref();
1082//! # vertices += 1;
1083//! # }
1084//! # vertices
1085//! # }
1086//! #
1087//! # pub fn depth(&self) -> usize {
1088//! # let mut node = self;
1089//! # if self.parent.is_null() {
1090//! # return 0;
1091//! # }
1092//! # let mut vertices = 0;
1093//! #
1094//! # while !node.parent.is_null() {
1095//! # node = node.parent.inner_ref();
1096//! # vertices += 1;
1097//! # }
1098//! # vertices
1099//! # }
1100//! #
1101//! # pub fn leaf(&self) -> bool {
1102//! # self.left.is_null() && self.right.is_null()
1103//! # }
1104//! #
1105//! # pub fn addr(&self) -> usize {
1106//! # (self as *const Node<'c>).addr()
1107//! # }
1108//! #
1109//! # pub fn left_addr(&self) -> usize {
1110//! # self.left.addr()
1111//! # }
1112//! #
1113//! # pub fn right_addr(&self) -> usize {
1114//! # self.right.addr()
1115//! # }
1116//! #
1117//! # pub fn parent_addr(&self) -> usize {
1118//! # self.parent.addr()
1119//! # }
1120//! #
1121//! # pub fn refs(&self) -> usize {
1122//! # *self.refs
1123//! # }
1124//! #
1125//! # pub fn subtree_first(&self) -> &'c Node<'c> {
1126//! # if self.left.is_null() {
1127//! # let node = self as *const Node<'c>;
1128//! # return unsafe { node.as_ref().unwrap() };
1129//! # }
1130//! #
1131//! # let mut subtree_first = self.left.cast_mut();
1132//! #
1133//! # loop {
1134//! # unsafe {
1135//! # let node = &*subtree_first;
1136//! # if node.left.is_null() {
1137//! # break;
1138//! # }
1139//! # subtree_first = node.left.cast_mut()
1140//! # }
1141//! # }
1142//! # unsafe { subtree_first.as_mut().unwrap() }
1143//! # }
1144//! #
1145//! # pub fn successor(&self) -> &'c Node<'c> {
1146//! # if !self.right.is_null() {
1147//! # return unsafe { self.right.as_ref().unwrap() }.subtree_first();
1148//! # }
1149//! #
1150//! # if let Some(parent) = self.parent() {
1151//! # if parent.parent.is_null() {
1152//! # return self.subtree_first();
1153//! # }
1154//! # }
1155//! # let mut successor = self as *const Node<'c>;
1156//! # let mut node = unsafe { &*successor };
1157//! # loop {
1158//! # if node.left() == Some(self) {
1159//! # break;
1160//! # }
1161//! # if !node.parent.is_null() {
1162//! # successor = node.parent.cast_const();
1163//! # node = unsafe { &*successor };
1164//! # } else {
1165//! # break;
1166//! # };
1167//! # }
1168//! # unsafe { &*successor }
1169//! # }
1170//! #
1171//! # pub fn subtree_first_mut(&mut self) -> &'c mut Node<'c> {
1172//! # if self.left.is_null() {
1173//! # let node = self as *mut Node<'c>;
1174//! # return {
1175//! # let node = unsafe {
1176//! # let node = &mut *node;
1177//! # node
1178//! # };
1179//! # unsafe { std::mem::transmute::<&mut Node<'c>, &'c mut Node<'c>>(node) }
1180//! # };
1181//! # }
1182//! #
1183//! # let mut subtree_first = &mut self.left;
1184//! #
1185//! # loop {
1186//! # unsafe {
1187//! # let node = subtree_first.inner_mut();
1188//! # if node.left.is_null() {
1189//! # break;
1190//! # }
1191//! # subtree_first = &mut node.left;
1192//! # }
1193//! # }
1194//! #
1195//! # subtree_first.inner_mut()
1196//! # }
1197//! #
1198//! # pub fn successor_mut(&mut self) -> &'c mut Node<'c> {
1199//! # if !self.right.is_null() {
1200//! # return self.right.inner_mut().subtree_first_mut();
1201//! # }
1202//! #
1203//! # if let Some(parent) = self.parent() {
1204//! # if parent.parent.is_null() {
1205//! # return self.subtree_first_mut();
1206//! # }
1207//! # }
1208//! # let mut successor = self as *mut Node<'c>;
1209//! # let mut node = {
1210//! # let node = unsafe {
1211//! # let node = &mut *successor;
1212//! # node
1213//! # };
1214//! # unsafe { std::mem::transmute::<&mut Node<'c>, &'c mut Node<'c>>(node) }
1215//! # };
1216//! #
1217//! # loop {
1218//! # if node.left() == Some(self) {
1219//! # break;
1220//! # }
1221//! # if !node.parent.is_null() {
1222//! # successor = node.parent.cast_mut();
1223//! # node = {
1224//! # let node = unsafe {
1225//! # let node = &mut *successor;
1226//! # node
1227//! # };
1228//! # unsafe { std::mem::transmute::<&mut Node<'c>, &'c mut Node<'c>>(node) }
1229//! # };
1230//! # } else {
1231//! # break;
1232//! # };
1233//! # }
1234//! # {
1235//! # let node = unsafe {
1236//! # let node = &mut *successor;
1237//! # node
1238//! # };
1239//! # unsafe { std::mem::transmute::<&mut Node<'c>, &'c mut Node<'c>>(node) }
1240//! # }
1241//! # }
1242//! #
1243//! # pub fn subtree_insert_after(&mut self, new: &mut Node<'c>) {
1244//! # if self.right.is_null() {
1245//! # self.set_right(new);
1246//! # } else {
1247//! # let successor = self.successor_mut();
1248//! # successor.set_left(new);
1249//! # }
1250//! # }
1251//! #
1252//! # pub fn predecessor(&self) -> &'c Node<'c> {
1253//! # let mut predecessor = self as *const Node<'c>;
1254//! # let mut node = {
1255//! # let node = unsafe {
1256//! # let node = &*predecessor;
1257//! # node
1258//! # };
1259//! # unsafe { std::mem::transmute::<&Node<'c>, &'c Node<'c>>(node) }
1260//! # };
1261//! #
1262//! # loop {
1263//! # if !node.left.is_null() {
1264//! # predecessor = node.left.cast_const();
1265//! # node = {
1266//! # let node = unsafe {
1267//! # let node = &*predecessor;
1268//! # node
1269//! # };
1270//! # unsafe { std::mem::transmute::<&Node<'c>, &'c Node<'c>>(node) }
1271//! # };
1272//! # if !node.right.is_null() {
1273//! # predecessor = node.right.cast_const();
1274//! # node = {
1275//! # let node = unsafe {
1276//! # let node = &*predecessor;
1277//! # node
1278//! # };
1279//! # unsafe { std::mem::transmute::<&Node<'c>, &'c Node<'c>>(node) }
1280//! # };
1281//! # }
1282//! # break;
1283//! # } else if !node.parent.is_null() {
1284//! # predecessor = node.parent.cast_const();
1285//! # node = {
1286//! # let node = unsafe {
1287//! # let node = &*predecessor;
1288//! # node
1289//! # };
1290//! # unsafe { std::mem::transmute::<&Node<'c>, &'c Node<'c>>(node) }
1291//! # };
1292//! # if let Some(right) = node.right() {
1293//! # if right == self {
1294//! # break;
1295//! # }
1296//! # }
1297//! # }
1298//! # }
1299//! # node = {
1300//! # let node = unsafe {
1301//! # let node = &*predecessor;
1302//! # node
1303//! # };
1304//! # unsafe { std::mem::transmute::<&Node<'c>, &'c Node<'c>>(node) }
1305//! # };
1306//! # node
1307//! # }
1308//! #
1309//! # pub fn predecessor_mut(&mut self) -> &'c mut Node<'c> {
1310//! # let mut predecessor = UniquePointer::<Node<'c>>::from_ref_mut(self);
1311//! # let mut node = predecessor.inner_mut();
1312//! #
1313//! # loop {
1314//! # if !node.left.is_null() {
1315//! # predecessor = node.left.clone();
1316//! # node = predecessor.inner_mut();
1317//! # if !node.right.is_null() {
1318//! # predecessor = node.right.clone();
1319//! # node = predecessor.inner_mut();
1320//! # }
1321//! # break;
1322//! # } else if !node.parent.is_null() {
1323//! # predecessor = node.parent.clone();
1324//! # node = predecessor.inner_mut();
1325//! #
1326//! # if let Some(right) = node.right() {
1327//! # if right == self {
1328//! # break;
1329//! # }
1330//! # }
1331//! # }
1332//! # }
1333//! # predecessor.inner_mut()
1334//! # }
1335//! #
1336//! # pub fn dealloc(&mut self) {
1337//! # if self.refs > 0 {
1338//! # self.decr_ref();
1339//! # } else {
1340//! # if !self.parent.is_null() {
1341//! # self.parent.drop_in_place();
1342//! # // self.parent = UniquePointer::null();
1343//! # }
1344//! # if !self.left.is_null() {
1345//! # self.left.drop_in_place();
1346//! # // self.left = UniquePointer::null();
1347//! # }
1348//! # if !self.right.is_null() {
1349//! # self.right.drop_in_place();
1350//! # // self.right = UniquePointer::null();
1351//! # }
1352//! # if !self.item.is_null() {
1353//! # self.item.drop_in_place();
1354//! # // self.item = UniquePointer::null();
1355//! # }
1356//! # }
1357//! # }
1358//! #
1359//! # pub fn swap_item(&mut self, other: &mut Self) {
1360//! # unsafe {
1361//! # self.item.swap(&mut other.item);
1362//! # };
1363//! # }
1364//! #
1365//! # pub fn disconnect(&mut self) {
1366//! # if !self.left.is_null() {
1367//! # unsafe {
1368//! # let node = self.left.inner_mut();
1369//! # node.refs -= 1;
1370//! # }
1371//! # }
1372//! # if !self.right.is_null() {
1373//! # unsafe {
1374//! # let node = self.right.inner_mut();
1375//! # node.refs -= 1;
1376//! # }
1377//! # }
1378//! # if !self.parent.is_null() {
1379//! # unsafe {
1380//! # let parent = self.parent.inner_mut();
1381//! # let delete_left = if let Some(parents_left_child) = parent.left() {
1382//! # parents_left_child == self
1383//! # } else {
1384//! # false
1385//! # };
1386//! # if delete_left {
1387//! # parent.left.dealloc(true);
1388//! # parent.left = UniquePointer::null();
1389//! # } else {
1390//! # parent.right.dealloc(true);
1391//! # parent.right = UniquePointer::null();
1392//! # }
1393//! # parent.decr_ref();
1394//! # }
1395//! # self.parent.dealloc(true);
1396//! # self.parent = UniquePointer::null();
1397//! # }
1398//! # }
1399//! # }
1400//! #
1401//! # pub fn subtree_delete<'c>(node: &mut Node<'c>) {
1402//! # if node.leaf() {
1403//! # node.decr_ref();
1404//! # if node.parent.is_not_null() {
1405//! # unsafe {
1406//! # let parent = node.parent.inner_mut();
1407//! # let delete_left = if let Some(parents_left_child) = parent.left() {
1408//! # parents_left_child == node
1409//! # } else {
1410//! # false
1411//! # };
1412//! # if delete_left {
1413//! # parent.left.dealloc(true);
1414//! # parent.left = UniquePointer::null();
1415//! # } else {
1416//! # parent.right.dealloc(true);
1417//! # parent.right = UniquePointer::null();
1418//! # }
1419//! # }
1420//! # node.parent.dealloc(true);
1421//! # node.parent = UniquePointer::null();
1422//! # }
1423//! # node.refs.reset();
1424//! # node.parent = UniquePointer::<Node<'c>>::null();
1425//! # return;
1426//! # } else {
1427//! # let predecessor = node.predecessor_mut();
1428//! # predecessor.swap_item(node);
1429//! # subtree_delete(predecessor);
1430//! # }
1431//! # }
1432//! #
1433//! # // Node private methods
1434//! # impl<'c> Node<'c> {
1435//! # pub fn ptr(&self) -> UniquePointer<Node<'c>> {
1436//! # let ptr = UniquePointer::copy_from_ref(self, *self.refs);
1437//! # ptr
1438//! # }
1439//! #
1440//! # fn incr_ref(&mut self) {
1441//! # self.refs += 1;
1442//! # let mut node = self;
1443//! # while !node.parent.is_null() {
1444//! # unsafe {
1445//! # node = node.parent.inner_mut();
1446//! # node.refs += 1;
1447//! # }
1448//! # }
1449//! # }
1450//! #
1451//! # fn decr_ref(&mut self) {
1452//! # self.refs -= 1;
1453//! # let mut node = self;
1454//! # while !node.parent.is_null() {
1455//! # unsafe {
1456//! # node = node.parent.inner_mut();
1457//! # node.refs -= 1;
1458//! # }
1459//! # }
1460//! # }
1461//! #
1462//! # fn item_eq(&self, other: &Node<'c>) -> bool {
1463//! # if self.item.addr() == other.item.addr() {
1464//! # self.item.addr() == other.item.addr()
1465//! # } else {
1466//! # self.value() == other.value()
1467//! # }
1468//! # }
1469//! # }
1470//! #
1471//! # impl<'c> PartialEq<Node<'c>> for Node<'c> {
1472//! # fn eq(&self, other: &Node<'c>) -> bool {
1473//! # if self.item_eq(other) {
1474//! # let eq = self.value().unwrap_or_default() == other.value().unwrap_or_default();
1475//! # eq
1476//! # } else {
1477//! # false
1478//! # }
1479//! # }
1480//! # }
1481//! #
1482//! # impl<'c> PartialEq<&mut Node<'c>> for Node<'c> {
1483//! # fn eq(&self, other: &&mut Node<'c>) -> bool {
1484//! # let other = unsafe { &**other };
1485//! # if self.item_eq(other) {
1486//! # let eq = self.value().unwrap_or_default() == other.value().unwrap_or_default();
1487//! # eq
1488//! # } else {
1489//! # false
1490//! # }
1491//! # }
1492//! # }
1493//! #
1494//! # impl<'c> Drop for Node<'c> {
1495//! # fn drop(&mut self) {
1496//! # self.dealloc();
1497//! # }
1498//! # }
1499//! #
1500//! # impl<'c> Clone for Node<'c> {
1501//! # fn clone(&self) -> Node<'c> {
1502//! # let mut node = Node::nil();
1503//! # node.refs = self.refs.clone();
1504//! # if self.parent.is_not_null() {
1505//! # node.parent = self.parent.clone();
1506//! # }
1507//! # if self.left.is_not_null() {
1508//! # node.left = self.left.clone();
1509//! # }
1510//! # if self.right.is_not_null() {
1511//! # node.right = self.right.clone();
1512//! # }
1513//! # if !self.item.is_null() {
1514//! # node.item = self.item.clone();
1515//! # }
1516//! # node
1517//! # }
1518//! # }
1519//! #
1520//! # impl<'c> AsRef<Node<'c>> for Node<'c> {
1521//! # fn as_ref(&self) -> &'c Node<'c> {
1522//! # unsafe { std::mem::transmute::<&Node<'c>, &'c Node<'c>>(self) }
1523//! # }
1524//! # }
1525//! # impl<'c> AsMut<Node<'c>> for Node<'c> {
1526//! # fn as_mut(&mut self) -> &'c mut Node<'c> {
1527//! # self.incr_ref();
1528//! # let node = unsafe {
1529//! # let node = &mut *self as *mut Node<'c>;
1530//! # node
1531//! # };
1532//! # unsafe { std::mem::transmute::<&mut Node<'c>, &'c mut Node<'c>>(self) }
1533//! # }
1534//! # }
1535//! # impl<'c> std::fmt::Display for Node<'c> {
1536//! # fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
1537//! # write!(f, "{}", self.id())
1538//! # }
1539//! # }
1540//! # impl<'c> std::fmt::Debug for Node<'c> {
1541//! # fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
1542//! # write!(
1543//! # f,
1544//! # "{}",
1545//! # [
1546//! # format!("Node@"),
1547//! # format!("{:016x}", self.addr()),
1548//! # format!("[refs={}]", *self.refs),
1549//! # if self.item.is_null() {
1550//! # format!("null")
1551//! # } else {
1552//! # format!(
1553//! # "[item={}]",
1554//! # self.value()
1555//! # .map(|value| format!("{:#?}", value))
1556//! # .unwrap_or_else(|| format!("empty"))
1557//! # )
1558//! # },
1559//! # if self.parent.is_null() {
1560//! # String::new()
1561//! # } else {
1562//! # format!(
1563//! # "(parent:{})",
1564//! # if self.parent.is_null() {
1565//! # format!("null")
1566//! # } else {
1567//! # self.parent_value()
1568//! # .map(|parent_value| format!("{:#?}", parent_value))
1569//! # .unwrap_or_else(|| format!("empty"))
1570//! # }
1571//! # )
1572//! # },
1573//! # if self.left.is_null() && self.right.is_null() {
1574//! # String::new()
1575//! # } else {
1576//! # format!(
1577//! # "[left:{} | right:{}]",
1578//! # if self.left.is_null() {
1579//! # format!("null")
1580//! # } else {
1581//! # self.left_value()
1582//! # .map(|left_value| format!("{:#?}", left_value))
1583//! # .unwrap_or_else(|| format!("empty"))
1584//! # },
1585//! # if self.right.is_null() {
1586//! # format!("null")
1587//! # } else {
1588//! # self.right_value()
1589//! # .map(|right_value| format!("{:#?}", right_value))
1590//! # .unwrap_or_else(|| format!("empty"))
1591//! # }
1592//! # )
1593//! # }
1594//! # ]
1595//! # .join("")
1596//! # )
1597//! # }
1598//! # }
1599//! struct MitOpenCourseWare6006Tree<'t> {
1600//! pub node_a: Node<'t>,
1601//! pub node_b: Node<'t>,
1602//! pub node_c: Node<'t>,
1603//! pub node_d: Node<'t>,
1604//! pub node_e: Node<'t>,
1605//! pub node_f: Node<'t>,
1606//! }
1607//! impl<'t> MitOpenCourseWare6006Tree<'t> {
1608//! pub fn initial_state() -> MitOpenCourseWare6006Tree<'t> {
1609//! ///|||||||||||||||||||||||||||||||||||||||||||||\\\
1610//! /// \\\
1611//! /// INITIAL TREE STATE \\\
1612//! /// \\\
1613//! /// A \\\
1614//! /// / \ \\\
1615//! /// / \ \\\
1616//! /// B C \\\
1617//! /// / \ \\\
1618//! /// / \ \\\
1619//! /// D E \\\
1620//! /// / \\\
1621//! /// / \\\
1622//! /// F \\\
1623//! /// \\\
1624//! /// \\\
1625//! // Scenario: Create nodes and test the equality of its items
1626//! //
1627//! // Given that I create disconnected nodes with values A through F
1628//! let mut node_a = Node::new(Value::from("A"));
1629//! let mut node_b = Node::new(Value::from("B"));
1630//! let mut node_c = Node::new(Value::from("C"));
1631//! let mut node_d = Node::new(Value::from("D"));
1632//! let mut node_e = Node::new(Value::from("E"));
1633//! let mut node_f = Node::new(Value::from("F"));
1634//!
1635//! // Then each node has its corresponding value
1636//! assert_eq!(node_a.value(), Some(Value::from("A")));
1637//! assert_eq!(node_b.value(), Some(Value::from("B")));
1638//! assert_eq!(node_c.value(), Some(Value::from("C")));
1639//! assert_eq!(node_d.value(), Some(Value::from("D")));
1640//! assert_eq!(node_e.value(), Some(Value::from("E")));
1641//! assert_eq!(node_f.value(), Some(Value::from("F")));
1642//!
1643//! /// /////////////////////////////////////////////////////////////////// ///
1644//! /// Scenario: Connect nodes and check the equality of the items parents ///
1645//! /// ///
1646//! /// Given that I set D as in left of B ///
1647//! node_b.set_left(&mut node_d);
1648//! ///
1649//! /// ///
1650//! /// And that I set B as in left of A before setting E as right of B ///
1651//! /// so as to test that memory references are set correctly* ///
1652//! node_a.set_left(&mut node_b);
1653//! ///
1654//! /// ///
1655//! /// And that I set C as left of A ///
1656//! node_a.set_right(&mut node_c);
1657//! ///
1658//! /// ///
1659//! /// And that I set E in right of B* ///
1660//! node_b.set_right(&mut node_e);
1661//! ///
1662//! /// ///
1663//! /// And that I set F in left of D ///
1664//! node_d.set_left(&mut node_f);
1665//! ///
1666//! /// ///
1667//! /// Then the parent of node B parent has value "A" ///
1668//! assert_eq!(node_b.parent_value(), node_a.value());
1669//! ///
1670//! /// And the parent of node C parent has value "A" ///
1671//! assert_eq!(node_c.parent_value(), node_a.value());
1672//! ///
1673//! /// And the parent of node D parent has value "B" ///
1674//! assert_eq!(node_d.parent_value(), node_b.value());
1675//! ///
1676//! /// And the parent of node E parent has value "B" ///
1677//! assert_eq!(node_e.parent_value(), node_b.value());
1678//! ///
1679//! /// ///
1680//! /// And the parent of node F parent has value "D" ///
1681//! assert_eq!(node_f.parent_value(), node_d.value());
1682//! ///
1683//!
1684//! /// //////////////////////////////////////////////// ///
1685//! /// Scenario: Check the equality of parent nodes ///
1686//! /// (i.e.: `impl PartialEq for Node') ///
1687//! /// ///
1688//! /// Given that all nodes have been connected ///
1689//! /// ///
1690//! /// Then the parent of node B is node A ///
1691//! assert_eq!(node_b.parent(), Some(&node_a));
1692//! ///
1693//! /// ///
1694//! /// And the parent of node C is node A ///
1695//! assert_eq!(node_c.parent(), Some(&node_a));
1696//! ///
1697//! /// ///
1698//! /// ///
1699//! /// And the parent of node D is node B ///
1700//! assert_eq!(node_d.parent(), Some(&node_b));
1701//! ///
1702//! /// ///
1703//! /// And the parent of node E is node B ///
1704//! assert_eq!(node_e.parent(), Some(&node_b));
1705//! ///
1706//! /// ///
1707//! /// And the parent of node F is node D ///
1708//! assert_eq!(node_f.parent(), Some(&node_d));
1709//! ///
1710//! /// ///
1711//!
1712//! /// ////////////////////////////////////////////////////////////////////////////////////// ///
1713//! /// Scenario: Check the equality of left and right nodes ///
1714//! /// (i.e.: `impl PartialEq for Node') ///
1715//! /// ///
1716//! /// Given that all nodes have been connected ///
1717//! /// ///
1718//! /// Then the left of node A is node B ///
1719//! assert_eq!(node_a.left(), Some(&node_b));
1720//! ///
1721//! /// ///
1722//! /// And the right of node A is node C ///
1723//! assert_eq!(node_a.right(), Some(&node_c));
1724//! ///
1725//! /// ///
1726//! /// And node A is the root node (no parent) ///
1727//! assert_eq!(node_a.parent(), None);
1728//! ///
1729//! /// ///
1730//! /// ///
1731//! /// And the left of node B is node D ///
1732//! assert_eq!(node_b.left(), Some(&node_d));
1733//! ///
1734//! /// ///
1735//! /// And the right of node B is node E ///
1736//! assert_eq!(node_b.right(), Some(&node_e));
1737//! ///
1738//! /// ///
1739//! /// And the parent of node B is node A ///
1740//! assert_eq!(node_b.parent(), Some(&node_a));
1741//! ///
1742//! /// ///
1743//! /// And node B has no grand-parent ///
1744//! assert_eq!(node_b.parent().unwrap().parent(), None);
1745//! ///
1746//! /// ///
1747//! assert_eq!(node_c.left(), None);
1748//! ///
1749//! /// ///
1750//! assert_eq!(node_c.right(), None);
1751//! ///
1752//! /// ///
1753//! assert_eq!(node_c.parent(), Some(&node_a));
1754//! ///
1755//! /// ///
1756//! assert_eq!(node_c.parent().unwrap().parent(), None);
1757//! ///
1758//! /// ///
1759//! assert_eq!(node_d.left(), Some(&node_f));
1760//! ///
1761//! /// ///
1762//! assert_eq!(node_d.right(), None);
1763//! ///
1764//! /// ///
1765//! assert_eq!(node_d.parent(), Some(&node_b));
1766//! ///
1767//! /// ///
1768//! assert_eq!(node_d.parent().unwrap().parent(), Some(&node_a));
1769//! ///
1770//! /// ///
1771//! assert_eq!(node_d.parent().unwrap().parent().unwrap().parent(), None);
1772//! ///
1773//! /// ///
1774//! assert_eq!(node_f.left(), None);
1775//! ///
1776//! /// ///
1777//! assert_eq!(node_f.right(), None);
1778//! ///
1779//! /// ///
1780//! assert_eq!(node_f.parent(), Some(&node_d));
1781//! ///
1782//! /// ///
1783//! assert_eq!(node_f.parent().unwrap().parent(), Some(&node_b));
1784//! ///
1785//! /// ///
1786//! assert_eq!(node_f.parent().unwrap().parent().unwrap().parent(), Some(&node_a));
1787//! ///
1788//! /// ///
1789//! assert_eq!(node_f.parent().unwrap().parent().unwrap().parent().unwrap().parent(), None);
1790//! ///
1791//! /// ///
1792//! assert_eq!(node_a.refs(), 9);
1793//! ///
1794//! /// ///
1795//! assert_eq!(node_b.refs(), 8);
1796//! ///
1797//! /// ///
1798//! assert_eq!(node_c.refs(), 2);
1799//! ///
1800//! /// ///
1801//! assert_eq!(node_d.refs(), 4);
1802//! ///
1803//! /// ///
1804//! assert_eq!(node_e.refs(), 2);
1805//! ///
1806//! /// ///
1807//! assert_eq!(node_f.refs(), 2);
1808//! ///
1809//! /// ///
1810//! let mut tree = unsafe {
1811//! MitOpenCourseWare6006Tree {
1812//! node_a,
1813//! node_b,
1814//! node_c,
1815//! node_d,
1816//! node_e,
1817//! node_f,
1818//! }
1819//! };
1820//! assert_eq!(tree.node_a.refs(), 9);
1821//! assert_eq!(tree.node_b.refs(), 8);
1822//! assert_eq!(tree.node_c.refs(), 2);
1823//! assert_eq!(tree.node_d.refs(), 4);
1824//! assert_eq!(tree.node_e.refs(), 2);
1825//! assert_eq!(tree.node_f.refs(), 2);
1826//!
1827//! tree.node_a.dealloc();
1828//! tree.node_b.dealloc();
1829//! tree.node_c.dealloc();
1830//! tree.node_d.dealloc();
1831//! tree.node_e.dealloc();
1832//! tree.node_f.dealloc();
1833//!
1834//! unsafe { std::mem::transmute::<MitOpenCourseWare6006Tree, MitOpenCourseWare6006Tree<'t>>(tree) }
1835//! }
1836//! }
1837//! // test_tree_initial_state
1838//! MitOpenCourseWare6006Tree::initial_state();
1839//!
1840//! // test_tree_property_height
1841//! let tree = MitOpenCourseWare6006Tree::initial_state();
1842//!
1843//! assert_eq!(tree.node_c.height(), 0); // leaf
1844//! assert_eq!(tree.node_e.height(), 0); // leaf
1845//! assert_eq!(tree.node_f.height(), 0); // leaf
1846//!
1847//! assert_eq!(tree.node_a.height(), 3);
1848//!
1849//! assert_eq!(tree.node_b.height(), 2);
1850//!
1851//! assert_eq!(tree.node_d.height(), 1);
1852//!
1853//!
1854//! // test_tree_property_depth
1855//! let tree = MitOpenCourseWare6006Tree::initial_state();
1856//!
1857//! assert_eq!(tree.node_a.depth(), 0);
1858//!
1859//! assert_eq!(tree.node_b.depth(), 1);
1860//! assert_eq!(tree.node_c.depth(), 1);
1861//!
1862//! assert_eq!(tree.node_e.depth(), 2);
1863//! assert_eq!(tree.node_d.depth(), 2);
1864//!
1865//! assert_eq!(tree.node_f.depth(), 3);
1866//!
1867//!
1868//! // test_tree_property_leaf
1869//! let tree = MitOpenCourseWare6006Tree::initial_state();
1870//!
1871//! assert_eq!(tree.node_a.leaf(), false);
1872//!
1873//! assert_eq!(tree.node_b.leaf(), false);
1874//! assert_eq!(tree.node_c.leaf(), true);
1875//!
1876//! assert_eq!(tree.node_d.leaf(), false);
1877//! assert_eq!(tree.node_e.leaf(), true);
1878//!
1879//! assert_eq!(tree.node_f.leaf(), true);
1880//!
1881//!
1882//! // test_tree_operation_subtree_first
1883//! let tree = MitOpenCourseWare6006Tree::initial_state();
1884//!
1885//! assert_eq!(tree.node_a.subtree_first(), &tree.node_f);
1886//! assert_eq!(tree.node_b.subtree_first(), &tree.node_f);
1887//! assert_eq!(tree.node_d.subtree_first(), &tree.node_f);
1888//! assert_eq!(tree.node_f.subtree_first(), &tree.node_f);
1889//!
1890//! assert_eq!(tree.node_e.subtree_first(), &tree.node_e);
1891//! assert_eq!(tree.node_c.subtree_first(), &tree.node_c);
1892//!
1893//!
1894//! // test_tree_operation_successor
1895//! let tree = MitOpenCourseWare6006Tree::initial_state();
1896//!
1897//! assert_eq!(tree.node_e.successor(), &tree.node_a);
1898//! assert_eq!(tree.node_f.successor(), &tree.node_d);
1899//! assert_eq!(tree.node_b.successor(), &tree.node_e);
1900//! assert_eq!(tree.node_d.successor(), &tree.node_b);
1901//! assert_eq!(tree.node_a.successor(), &tree.node_c);
1902//! assert_eq!(tree.node_c.successor(), &tree.node_c);
1903//!
1904//!
1905//! // test_tree_operation_successor_of_c
1906//! let mut tree = MitOpenCourseWare6006Tree::initial_state();
1907//!
1908//! let mut node_g = Node::new(Value::from("G"));
1909//! tree.node_c.set_left(&mut node_g);
1910//!
1911//! assert_eq!(tree.node_c.successor(), &node_g);
1912//!
1913//!
1914//!
1915//! // test_tree_operation_subtree_first_mut
1916//! let mut tree = MitOpenCourseWare6006Tree::initial_state();
1917//!
1918//! assert_eq!(tree.node_a.subtree_first_mut(), &mut tree.node_f);
1919//! assert_eq!(tree.node_b.subtree_first_mut(), &mut tree.node_f);
1920//! assert_eq!(tree.node_d.subtree_first_mut(), &mut tree.node_f);
1921//! assert_eq!(tree.node_f.subtree_first_mut(), &mut tree.node_f);
1922//!
1923//! assert_eq!(tree.node_e.subtree_first_mut(), &mut tree.node_e);
1924//! assert_eq!(tree.node_c.subtree_first_mut(), &mut tree.node_c);
1925//!
1926//!
1927//! // test_tree_operation_successor_mut
1928//! let mut tree = MitOpenCourseWare6006Tree::initial_state();
1929//!
1930//! assert_eq!(tree.node_e.successor_mut(), &mut tree.node_a);
1931//! assert_eq!(tree.node_f.successor_mut(), &mut tree.node_d);
1932//! assert_eq!(tree.node_b.successor_mut(), &mut tree.node_e);
1933//! assert_eq!(tree.node_d.successor_mut(), &mut tree.node_b);
1934//! assert_eq!(tree.node_a.successor_mut(), &mut tree.node_c);
1935//! assert_eq!(tree.node_c.successor_mut(), &mut tree.node_c);
1936//!
1937//!
1938//! // test_tree_operation_successor_mut_of_c
1939//! let mut tree = MitOpenCourseWare6006Tree::initial_state();
1940//!
1941//! let mut node_g = Node::new(Value::from("G"));
1942//! tree.node_c.set_left(&mut node_g);
1943//!
1944//! assert_eq!(tree.node_c.successor_mut(), &mut node_g);
1945//!
1946//!
1947//! // test_tree_operation_subtree_insert_after_node_when_node_left_is_null
1948//! let mut tree = MitOpenCourseWare6006Tree::initial_state();
1949//!
1950//! let mut node_g = Node::new(Value::from("G"));
1951//! tree.node_c.subtree_insert_after(&mut node_g);
1952//!
1953//! assert_eq!(node_g.parent(), Some(&tree.node_c.clone()));
1954//!
1955//!
1956//! // test_tree_operation_subtree_insert_after_node_when_node_right_is_non_null
1957//! let mut tree = MitOpenCourseWare6006Tree::initial_state();
1958//!
1959//! let mut node_g = Node::new(Value::from("G"));
1960//! tree.node_a.subtree_insert_after(&mut node_g);
1961//!
1962//! assert_eq!(node_g.parent(), tree.node_a.right());
1963//! assert_eq!(node_g.parent(), Some(&tree.node_c));
1964//!
1965//!
1966//! // test_tree_operation_predecessor
1967//! let tree = MitOpenCourseWare6006Tree::initial_state();
1968//!
1969//! assert_eq!(tree.node_a.predecessor(), &tree.node_e);
1970//! assert_eq!(tree.node_d.predecessor(), &tree.node_f);
1971//! assert_eq!(tree.node_c.predecessor(), &tree.node_a);
1972//! assert_eq!(tree.node_e.predecessor(), &tree.node_b);
1973//! assert_eq!(tree.node_b.predecessor(), &tree.node_d);
1974//!
1975//!
1976//! // test_tree_operation_predecessor_of_g_as_right_of_e
1977//! let mut tree = MitOpenCourseWare6006Tree::initial_state();
1978//!
1979//! let mut node_g = Node::new(Value::from("G"));
1980//! tree.node_e.set_right(&mut node_g);
1981//!
1982//! assert_eq!(node_g.predecessor(), &tree.node_e);
1983//!
1984//!
1985//! // test_tree_operation_predecessor_mut
1986//! let mut tree = MitOpenCourseWare6006Tree::initial_state();
1987//!
1988//! assert_eq!(tree.node_a.predecessor_mut(), &mut tree.node_e);
1989//! assert_eq!(tree.node_d.predecessor_mut(), &mut tree.node_f);
1990//! assert_eq!(tree.node_c.predecessor_mut(), &mut tree.node_a);
1991//! assert_eq!(tree.node_e.predecessor_mut(), &mut tree.node_b);
1992//! assert_eq!(tree.node_b.predecessor_mut(), &mut tree.node_d);
1993//!
1994//!
1995//! // test_tree_operation_predecessor_mut_of_g_as_right_of_e
1996//! let mut tree = MitOpenCourseWare6006Tree::initial_state();
1997//!
1998//! let mut node_g = Node::new(Value::from("G"));
1999//! tree.node_e.set_right(&mut node_g);
2000//!
2001//! assert_eq!(node_g.predecessor_mut(), &mut tree.node_e);
2002//!
2003//!
2004//! // test_tree_operation_swap_item
2005//! // Given the test tree in its initial state
2006//! let mut tree = MitOpenCourseWare6006Tree::initial_state();
2007//!
2008//! // When I swap item of node A with item of node E
2009//! tree.node_a.swap_item(&mut tree.node_e);
2010//!
2011//! // Then node A has the value E
2012//! assert_eq!(tree.node_a.value(), Some(Value::from("E")));
2013//! // And node E has the value A
2014//! assert_eq!(tree.node_e.value(), Some(Value::from("A")));
2015//!
2016//! // And all other nodes remain with their values unmodified
2017//! assert_eq!(tree.node_b.value(), Some(Value::from("B")));
2018//! assert_eq!(tree.node_c.value(), Some(Value::from("C")));
2019//! assert_eq!(tree.node_d.value(), Some(Value::from("D")));
2020//! assert_eq!(tree.node_f.value(), Some(Value::from("F")));
2021//!
2022//!
2023//! // test_tree_operation_subtree_delete_leaf_nodes
2024//! // Given the test tree in its initial state
2025//! let mut tree = MitOpenCourseWare6006Tree::initial_state();
2026//!
2027//! // Then node D has 3 references
2028//! assert_eq!(tree.node_d.refs(), 2);
2029//! assert_eq!(tree.node_a.refs(), 3);
2030//! assert_eq!(tree.node_b.refs(), 4);
2031//! assert_eq!(tree.node_c.refs(), 1);
2032//! assert_eq!(tree.node_d.refs(), 2);
2033//! assert_eq!(tree.node_e.refs(), 1);
2034//!
2035//! // When I subtree_delete node F
2036//! subtree_delete(&mut tree.node_f);
2037//!
2038//! // Then node F has no more references
2039//! assert_eq!(tree.node_f.refs(), 1);
2040//!
2041//! // And node F is dangling in the left of node D
2042//! assert_eq!(tree.node_d.left(), Some(&tree.node_f));
2043//!
2044//! // And node D has 1 reference
2045//! assert_eq!(tree.node_d.refs(), 1);
2046//!
2047//! // And the references of all ancestors of D are decremented
2048//! assert_eq!(tree.node_a.refs(), 2);
2049//! assert_eq!(tree.node_b.refs(), 3);
2050//!
2051//! // And the references of the other leaf nodes remains unchanged
2052//! assert_eq!(tree.node_c.refs(), 1);
2053//! assert_eq!(tree.node_e.refs(), 1);
2054//!
2055//!
2056//! // test_tree_operation_subtree_delete_root_node
2057//! // Given the test tree in its initial state
2058//! let mut tree = MitOpenCourseWare6006Tree::initial_state();
2059//!
2060//! // Then node A has 8 references
2061//! assert_eq!(tree.node_a.refs(), 3);
2062//! // And node B is in the left of node A
2063//! assert_eq!(tree.node_a.left(), Some(tree.node_b.as_ref()));
2064//! // And node C is in the right of node A
2065//! assert_eq!(tree.node_a.right(), Some(tree.node_c.as_ref()));
2066//!
2067//! // When I subtree_delete node A
2068//! subtree_delete(&mut tree.node_a);
2069//!
2070//! // Then node E becomes node A
2071//! assert_eq!(tree.node_a.value(), Some(Value::from("E")));
2072//!
2073//! // And node E (which has become A) has 2 references
2074//! assert_eq!(tree.node_a.refs(), 2);
2075//!
2076//! // And node B is in the left of node E (which has become A)
2077//! assert_eq!(tree.node_a.left(), Some(tree.node_b.as_ref()));
2078//!
2079//! // And node C is in the right of node E (which has become A)
2080//! assert_eq!(tree.node_a.right(), Some(tree.node_c.as_ref()));
2081//!
2082//! // And node A becomes node E
2083//! assert_eq!(tree.node_e.value(), Some(Value::from("A")));
2084//!
2085//! // And node A (which has become E) has no more references
2086//! assert_eq!(tree.node_e.refs(), 1);
2087//!
2088//! ```
2089//!
2090//! ### Testing Node
2091//!
2092//! ```
2093//! # use std::borrow::Cow;
2094//! # use std::convert::{AsMut, AsRef};
2095//! # use std::cmp::{Eq, Ord, Ordering, PartialEq, PartialOrd};
2096//! # use unique_pointer::{UniquePointer, RefCounter};
2097//! # #[derive(Clone, PartialOrd, Ord, Default, PartialEq, Eq, Hash)]
2098//! # pub enum Value<'c> {
2099//! # #[default]
2100//! # Nil,
2101//! # String(Cow<'c, str>),
2102//! # Byte(u8),
2103//! # UInt(u64),
2104//! # Int(i64),
2105//! # }
2106//! # impl<'c> Value<'_> {
2107//! # pub fn nil() -> Value<'c> {
2108//! # Value::Nil
2109//! # }
2110//! #
2111//! # pub fn is_nil(&self) -> bool {
2112//! # if *self == Value::Nil {
2113//! # true
2114//! # } else {
2115//! # false
2116//! # }
2117//! # }
2118//! # }
2119//! #
2120//! # impl<'c> Drop for Value<'c> {
2121//! # fn drop(&mut self) {}
2122//! # }
2123//! #
2124//! # impl std::fmt::Display for Value<'_> {
2125//! # fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
2126//! # write!(
2127//! # f,
2128//! # "{}",
2129//! # match self {
2130//! # Value::Nil => "nil".to_string(),
2131//! # Value::String(h) => format!("{}", h),
2132//! # Value::Byte(h) => format!("{}", h),
2133//! # Value::UInt(h) => format!("{}", h),
2134//! # Value::Int(h) => format!("{}", h),
2135//! # }
2136//! # )
2137//! # }
2138//! # }
2139//! # impl std::fmt::Debug for Value<'_> {
2140//! # fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
2141//! # write!(
2142//! # f,
2143//! # "{}",
2144//! # match self {
2145//! # Value::Nil => "nil".to_string(),
2146//! # Value::String(h) => format!("{:#?}", h),
2147//! # Value::Byte(h) => format!("{}u8", h),
2148//! # Value::UInt(h) => format!("{}u64", h),
2149//! # Value::Int(h) => format!("{}i64", h),
2150//! # }
2151//! # )
2152//! # }
2153//! # }
2154//! #
2155//! # impl<'c> From<u8> for Value<'c> {
2156//! # fn from(value: u8) -> Value<'c> {
2157//! # Value::Byte(value)
2158//! # }
2159//! # }
2160//! # impl<'c> From<u64> for Value<'c> {
2161//! # fn from(value: u64) -> Value<'c> {
2162//! # Value::UInt(value)
2163//! # }
2164//! # }
2165//! # impl<'c> From<i64> for Value<'c> {
2166//! # fn from(value: i64) -> Value<'c> {
2167//! # Value::Int(value)
2168//! # }
2169//! # }
2170//! # impl<'c> From<&'c str> for Value<'c> {
2171//! # fn from(value: &'c str) -> Value<'c> {
2172//! # Value::String(Cow::from(value))
2173//! # }
2174//! # }
2175//! # impl<'c> From<Cow<'c, str>> for Value<'c> {
2176//! # fn from(value: Cow<'c, str>) -> Value<'c> {
2177//! # Value::from(value.into_owned())
2178//! # }
2179//! # }
2180//! # impl<'c> From<&'c mut str> for Value<'c> {
2181//! # fn from(value: &'c mut str) -> Value<'c> {
2182//! # Value::String(Cow::<'c, str>::Borrowed(&*value))
2183//! # }
2184//! # }
2185//! # impl<'c> From<String> for Value<'c> {
2186//! # fn from(value: String) -> Value<'c> {
2187//! # Value::String(Cow::from(value))
2188//! # }
2189//! # }
2190//! # impl<'c> From<Option<String>> for Value<'c> {
2191//! # fn from(value: Option<String>) -> Value<'c> {
2192//! # match value {
2193//! # None => Value::Nil,
2194//! # Some(value) => Value::from(value),
2195//! # }
2196//! # }
2197//! # }
2198//! #
2199//! # impl<'c> AsRef<Value<'c>> for Value<'c> {
2200//! # fn as_ref(&self) -> &Value<'c> {
2201//! # unsafe { &*self }
2202//! # }
2203//! # }
2204//! # impl<'c> AsMut<Value<'c>> for Value<'c> {
2205//! # fn as_mut(&mut self) -> &mut Value<'c> {
2206//! # unsafe { &mut *self }
2207//! # }
2208//! # }
2209//! #
2210//! # impl<'c> PartialEq<&Value<'c>> for Value<'c> {
2211//! # fn eq(&self, other: &&Value<'c>) -> bool {
2212//! # let other = unsafe { &**other };
2213//! # self == other
2214//! # }
2215//! # }
2216//! #
2217//! # impl<'c> PartialEq<&mut Value<'c>> for Value<'c> {
2218//! # fn eq(&self, other: &&mut Value<'c>) -> bool {
2219//! # let other = unsafe { &**other };
2220//! # self == other
2221//! # }
2222//! # }
2223//! #
2224//! #
2225//! # pub struct Node<'c> {
2226//! # pub parent: UniquePointer<Node<'c>>,
2227//! # pub left: UniquePointer<Node<'c>>,
2228//! # pub right: UniquePointer<Node<'c>>,
2229//! # pub item: UniquePointer<Value<'c>>,
2230//! # refs: RefCounter,
2231//! # }
2232//! #
2233//! # impl<'c> Node<'c> {
2234//! # pub fn nil() -> Node<'c> {
2235//! # Node {
2236//! # parent: UniquePointer::<Node<'c>>::null(),
2237//! # left: UniquePointer::<Node<'c>>::null(),
2238//! # right: UniquePointer::<Node<'c>>::null(),
2239//! # item: UniquePointer::<Value<'c>>::null(),
2240//! # refs: RefCounter::new(),
2241//! # }
2242//! # }
2243//! #
2244//! # pub fn is_nil(&self) -> bool {
2245//! # self.item.is_null()
2246//! # && self.left.is_null()
2247//! # && self.right.is_null()
2248//! # && self.parent.is_null()
2249//! # && self.refs <= 1
2250//! # }
2251//! #
2252//! # pub fn new(value: Value<'c>) -> Node<'c> {
2253//! # let mut node = Node::nil();
2254//! # unsafe {
2255//! # node.item.write(value);
2256//! # }
2257//! # node
2258//! # }
2259//! #
2260//! # pub fn parent(&self) -> Option<&'c Node<'c>> {
2261//! # self.parent.as_ref()
2262//! # }
2263//! #
2264//! # pub fn parent_mut(&mut self) -> Option<&'c mut Node<'c>> {
2265//! # self.parent.as_mut()
2266//! # }
2267//! #
2268//! # pub fn item(&self) -> Value<'c> {
2269//! # self.value().unwrap_or_default()
2270//! # }
2271//! #
2272//! # pub fn id(&self) -> String {
2273//! # format!(
2274//! # "{}{}",
2275//! # if self.item.is_null() {
2276//! # format!("Null Node {:p}", self)
2277//! # } else {
2278//! # format!("Node {}", self.item())
2279//! # },
2280//! # format!(" ({} referefences)", self.refs)
2281//! # )
2282//! # }
2283//! #
2284//! # pub fn value(&self) -> Option<Value<'c>> {
2285//! # if self.item.is_null() {
2286//! # None
2287//! # } else {
2288//! # unsafe {
2289//! # if let Some(value) = self.item.as_ref() {
2290//! # Some(value.clone())
2291//! # } else {
2292//! # None
2293//! # }
2294//! # }
2295//! # }
2296//! # }
2297//! #
2298//! # pub fn parent_value(&self) -> Option<Value<'c>> {
2299//! # if let Some(parent) = self.parent() {
2300//! # parent.value()
2301//! # } else {
2302//! # None
2303//! # }
2304//! # }
2305//! #
2306//! # pub fn set_left(&mut self, left: &mut Node<'c>) {
2307//! # self.incr_ref();
2308//! # left.parent = self.ptr();
2309//! # self.left = left.ptr();
2310//! # left.incr_ref();
2311//! # }
2312//! #
2313//! # pub fn set_right(&mut self, right: &mut Node<'c>) {
2314//! # self.incr_ref();
2315//! # right.parent = self.ptr();
2316//! # self.right = right.ptr();
2317//! # right.incr_ref();
2318//! # }
2319//! #
2320//! # pub fn delete_left(&mut self) {
2321//! # if self.left.is_null() {
2322//! # return;
2323//! # }
2324//! # let left = self.left.inner_mut();
2325//! # left.decr_ref();
2326//! # self.left.dealloc(true);
2327//! # self.left = UniquePointer::null();
2328//! # }
2329//! #
2330//! # pub fn left(&self) -> Option<&'c Node<'c>> {
2331//! # let left = self.left.as_ref();
2332//! # left
2333//! # }
2334//! #
2335//! # pub fn left_mut(&mut self) -> Option<&'c mut Node<'c>> {
2336//! # self.left.as_mut()
2337//! # }
2338//! #
2339//! # pub fn left_value(&self) -> Option<Value<'c>> {
2340//! # if let Some(left) = self.left() {
2341//! # left.value()
2342//! # } else {
2343//! # None
2344//! # }
2345//! # }
2346//! #
2347//! # pub fn delete_right(&mut self) {
2348//! # if self.right.is_null() {
2349//! # return;
2350//! # }
2351//! # let right = self.right.inner_mut();
2352//! # right.decr_ref();
2353//! # self.right.dealloc(true);
2354//! # self.right = UniquePointer::null();
2355//! # }
2356//! #
2357//! # pub fn right(&self) -> Option<&'c Node<'c>> {
2358//! # self.right.as_ref()
2359//! # }
2360//! #
2361//! # pub fn right_mut(&mut self) -> Option<&'c mut Node<'c>> {
2362//! # self.right.as_mut()
2363//! # }
2364//! #
2365//! # pub fn right_value(&self) -> Option<Value<'c>> {
2366//! # if let Some(right) = self.right() {
2367//! # right.value()
2368//! # } else {
2369//! # None
2370//! # }
2371//! # }
2372//! #
2373//! # pub fn height(&self) -> usize {
2374//! # let mut node = self;
2375//! # let mut vertices = 0;
2376//! #
2377//! # while !node.left.is_null() {
2378//! # node = node.left.inner_ref();
2379//! # vertices += 1;
2380//! # }
2381//! # vertices
2382//! # }
2383//! #
2384//! # pub fn depth(&self) -> usize {
2385//! # let mut node = self;
2386//! # if self.parent.is_null() {
2387//! # return 0;
2388//! # }
2389//! # let mut vertices = 0;
2390//! #
2391//! # while !node.parent.is_null() {
2392//! # node = node.parent.inner_ref();
2393//! # vertices += 1;
2394//! # }
2395//! # vertices
2396//! # }
2397//! #
2398//! # pub fn leaf(&self) -> bool {
2399//! # self.left.is_null() && self.right.is_null()
2400//! # }
2401//! #
2402//! # pub fn addr(&self) -> usize {
2403//! # (self as *const Node<'c>).addr()
2404//! # }
2405//! #
2406//! # pub fn left_addr(&self) -> usize {
2407//! # self.left.addr()
2408//! # }
2409//! #
2410//! # pub fn right_addr(&self) -> usize {
2411//! # self.right.addr()
2412//! # }
2413//! #
2414//! # pub fn parent_addr(&self) -> usize {
2415//! # self.parent.addr()
2416//! # }
2417//! #
2418//! # pub fn refs(&self) -> usize {
2419//! # *self.refs
2420//! # }
2421//! #
2422//! # pub fn subtree_first(&self) -> &'c Node<'c> {
2423//! # if self.left.is_null() {
2424//! # let node = self as *const Node<'c>;
2425//! # return unsafe { node.as_ref().unwrap() };
2426//! # }
2427//! #
2428//! # let mut subtree_first = self.left.cast_mut();
2429//! #
2430//! # loop {
2431//! # unsafe {
2432//! # let node = &*subtree_first;
2433//! # if node.left.is_null() {
2434//! # break;
2435//! # }
2436//! # subtree_first = node.left.cast_mut()
2437//! # }
2438//! # }
2439//! # unsafe { subtree_first.as_mut().unwrap() }
2440//! # }
2441//! #
2442//! # pub fn successor(&self) -> &'c Node<'c> {
2443//! # if !self.right.is_null() {
2444//! # return unsafe { self.right.as_ref().unwrap() }.subtree_first();
2445//! # }
2446//! #
2447//! # if let Some(parent) = self.parent() {
2448//! # // node.parent is root but node.right is null, so successor is node.subtree_first()
2449//! # if parent.parent.is_null() {
2450//! # return self.subtree_first();
2451//! # }
2452//! # }
2453//! # let mut successor = self as *const Node<'c>;
2454//! # let mut node = unsafe { &*successor };
2455//! # loop {
2456//! # if node.left() == Some(self) {
2457//! # break;
2458//! # }
2459//! # if !node.parent.is_null() {
2460//! # successor = node.parent.cast_const();
2461//! # node = unsafe { &*successor };
2462//! # } else {
2463//! # break;
2464//! # };
2465//! # }
2466//! # unsafe { &*successor }
2467//! # }
2468//! #
2469//! # pub fn subtree_first_mut(&mut self) -> &'c mut Node<'c> {
2470//! # if self.left.is_null() {
2471//! # let node = self as *mut Node<'c>;
2472//! # return {
2473//! # let node = unsafe {
2474//! # let node = &mut *node;
2475//! # node
2476//! # };
2477//! # unsafe { std::mem::transmute::<&mut Node<'c>, &'c mut Node<'c>>(node) }
2478//! # };
2479//! # }
2480//! #
2481//! # let mut subtree_first = &mut self.left;
2482//! #
2483//! # loop {
2484//! # unsafe {
2485//! # let node = subtree_first.inner_mut();
2486//! # if node.left.is_null() {
2487//! # break;
2488//! # }
2489//! # subtree_first = &mut node.left;
2490//! # }
2491//! # }
2492//! #
2493//! # subtree_first.inner_mut()
2494//! # }
2495//! #
2496//! # pub fn successor_mut(&mut self) -> &'c mut Node<'c> {
2497//! # if !self.right.is_null() {
2498//! # return self.right.inner_mut().subtree_first_mut();
2499//! # }
2500//! #
2501//! # if let Some(parent) = self.parent() {
2502//! # // node.parent is root but node.right is null, so successor is node.subtree_first_mut()
2503//! # if parent.parent.is_null() {
2504//! # return self.subtree_first_mut();
2505//! # }
2506//! # }
2507//! # let mut successor = self as *mut Node<'c>;
2508//! # let mut node = {
2509//! # let node = unsafe {
2510//! # let node = &mut *successor;
2511//! # node
2512//! # };
2513//! # unsafe { std::mem::transmute::<&mut Node<'c>, &'c mut Node<'c>>(node) }
2514//! # };
2515//! #
2516//! # loop {
2517//! # if node.left() == Some(self) {
2518//! # break;
2519//! # }
2520//! # if !node.parent.is_null() {
2521//! # successor = node.parent.cast_mut();
2522//! # node = {
2523//! # let node = unsafe {
2524//! # let node = &mut *successor;
2525//! # node
2526//! # };
2527//! # unsafe { std::mem::transmute::<&mut Node<'c>, &'c mut Node<'c>>(node) }
2528//! # };
2529//! # } else {
2530//! # break;
2531//! # };
2532//! # }
2533//! # {
2534//! # let node = unsafe {
2535//! # let node = &mut *successor;
2536//! # node
2537//! # };
2538//! # unsafe { std::mem::transmute::<&mut Node<'c>, &'c mut Node<'c>>(node) }
2539//! # }
2540//! # }
2541//! #
2542//! # pub fn subtree_insert_after(&mut self, new: &mut Node<'c>) {
2543//! # if self.right.is_null() {
2544//! # self.set_right(new);
2545//! # } else {
2546//! # let successor = self.successor_mut();
2547//! # successor.set_left(new);
2548//! # }
2549//! # }
2550//! #
2551//! # pub fn predecessor(&self) -> &'c Node<'c> {
2552//! # let mut predecessor = self as *const Node<'c>;
2553//! # let mut node = {
2554//! # let node = unsafe {
2555//! # let node = &*predecessor;
2556//! # node
2557//! # };
2558//! # unsafe { std::mem::transmute::<&Node<'c>, &'c Node<'c>>(node) }
2559//! # };
2560//! #
2561//! # loop {
2562//! # if !node.left.is_null() {
2563//! # predecessor = node.left.cast_const();
2564//! # node = {
2565//! # let node = unsafe {
2566//! # let node = &*predecessor;
2567//! # node
2568//! # };
2569//! # unsafe { std::mem::transmute::<&Node<'c>, &'c Node<'c>>(node) }
2570//! # };
2571//! # if !node.right.is_null() {
2572//! # predecessor = node.right.cast_const();
2573//! # node = {
2574//! # let node = unsafe {
2575//! # let node = &*predecessor;
2576//! # node
2577//! # };
2578//! # unsafe { std::mem::transmute::<&Node<'c>, &'c Node<'c>>(node) }
2579//! # };
2580//! # }
2581//! # break;
2582//! # } else if !node.parent.is_null() {
2583//! # predecessor = node.parent.cast_const();
2584//! # node = {
2585//! # let node = unsafe {
2586//! # let node = &*predecessor;
2587//! # node
2588//! # };
2589//! # unsafe { std::mem::transmute::<&Node<'c>, &'c Node<'c>>(node) }
2590//! # };
2591//! # if let Some(right) = node.right() {
2592//! # if right == self {
2593//! # break;
2594//! # }
2595//! # }
2596//! # }
2597//! # }
2598//! # node = {
2599//! # let node = unsafe {
2600//! # let node = &*predecessor;
2601//! # node
2602//! # };
2603//! # unsafe { std::mem::transmute::<&Node<'c>, &'c Node<'c>>(node) }
2604//! # };
2605//! # node
2606//! # }
2607//! #
2608//! # pub fn predecessor_mut(&mut self) -> &'c mut Node<'c> {
2609//! # let mut predecessor = UniquePointer::<Node<'c>>::from_ref_mut(self);
2610//! # let mut node = predecessor.inner_mut();
2611//! #
2612//! # loop {
2613//! # if !node.left.is_null() {
2614//! # predecessor = node.left.clone();
2615//! # node = predecessor.inner_mut();
2616//! # if !node.right.is_null() {
2617//! # predecessor = node.right.clone();
2618//! # node = predecessor.inner_mut();
2619//! # }
2620//! # break;
2621//! # } else if !node.parent.is_null() {
2622//! # predecessor = node.parent.clone();
2623//! # node = predecessor.inner_mut();
2624//! #
2625//! # if let Some(right) = node.right() {
2626//! # if right == self {
2627//! # break;
2628//! # }
2629//! # }
2630//! # }
2631//! # }
2632//! # predecessor.inner_mut()
2633//! # }
2634//! #
2635//! # pub fn dealloc(&mut self) {
2636//! # if self.refs > 0 {
2637//! # self.decr_ref();
2638//! # } else {
2639//! # if !self.parent.is_null() {
2640//! # self.parent.drop_in_place();
2641//! # // self.parent = UniquePointer::null();
2642//! # }
2643//! # if !self.left.is_null() {
2644//! # self.left.drop_in_place();
2645//! # // self.left = UniquePointer::null();
2646//! # }
2647//! # if !self.right.is_null() {
2648//! # self.right.drop_in_place();
2649//! # // self.right = UniquePointer::null();
2650//! # }
2651//! # if !self.item.is_null() {
2652//! # self.item.drop_in_place();
2653//! # // self.item = UniquePointer::null();
2654//! # }
2655//! # }
2656//! # }
2657//! #
2658//! # pub fn swap_item(&mut self, other: &mut Self) {
2659//! # unsafe {
2660//! # self.item.swap(&mut other.item);
2661//! # };
2662//! # }
2663//! #
2664//! # pub fn disconnect(&mut self) {
2665//! # if !self.left.is_null() {
2666//! # unsafe {
2667//! # let node = self.left.inner_mut();
2668//! # node.refs -= 1;
2669//! # }
2670//! # }
2671//! # if !self.right.is_null() {
2672//! # unsafe {
2673//! # let node = self.right.inner_mut();
2674//! # node.refs -= 1;
2675//! # }
2676//! # }
2677//! # if !self.parent.is_null() {
2678//! # unsafe {
2679//! # let parent = self.parent.inner_mut();
2680//! # let delete_left = if let Some(parents_left_child) = parent.left() {
2681//! # parents_left_child == self
2682//! # } else {
2683//! # false
2684//! # };
2685//! # if delete_left {
2686//! # parent.left.dealloc(true);
2687//! # parent.left = UniquePointer::null();
2688//! # } else {
2689//! # parent.right.dealloc(true);
2690//! # parent.right = UniquePointer::null();
2691//! # }
2692//! # parent.decr_ref();
2693//! # }
2694//! # self.parent.dealloc(true);
2695//! # self.parent = UniquePointer::null();
2696//! # }
2697//! # }
2698//! # }
2699//! #
2700//! # pub fn subtree_delete<'c>(node: &mut Node<'c>) {
2701//! # if node.leaf() {
2702//! # node.decr_ref();
2703//! # if node.parent.is_not_null() {
2704//! # unsafe {
2705//! # let parent = node.parent.inner_mut();
2706//! # let delete_left = if let Some(parents_left_child) = parent.left() {
2707//! # parents_left_child == node
2708//! # } else {
2709//! # false
2710//! # };
2711//! # if delete_left {
2712//! # parent.left.dealloc(true);
2713//! # parent.left = UniquePointer::null();
2714//! # } else {
2715//! # parent.right.dealloc(true);
2716//! # parent.right = UniquePointer::null();
2717//! # }
2718//! # }
2719//! # node.parent.dealloc(true);
2720//! # node.parent = UniquePointer::null();
2721//! # }
2722//! # node.refs.reset();
2723//! # node.parent = UniquePointer::<Node<'c>>::null();
2724//! # return;
2725//! # } else {
2726//! # let predecessor = node.predecessor_mut();
2727//! # predecessor.swap_item(node);
2728//! # subtree_delete(predecessor);
2729//! # }
2730//! # }
2731//! #
2732//! # // Node private methods
2733//! # impl<'c> Node<'c> {
2734//! # pub fn ptr(&self) -> UniquePointer<Node<'c>> {
2735//! # let ptr = UniquePointer::copy_from_ref(self, *self.refs);
2736//! # ptr
2737//! # }
2738//! #
2739//! # fn incr_ref(&mut self) {
2740//! # self.refs += 1;
2741//! # let mut node = self;
2742//! # while !node.parent.is_null() {
2743//! # unsafe {
2744//! # node = node.parent.inner_mut();
2745//! # node.refs += 1;
2746//! # }
2747//! # }
2748//! # }
2749//! #
2750//! # fn decr_ref(&mut self) {
2751//! # self.refs -= 1;
2752//! # let mut node = self;
2753//! # while !node.parent.is_null() {
2754//! # unsafe {
2755//! # node = node.parent.inner_mut();
2756//! # node.refs -= 1;
2757//! # }
2758//! # }
2759//! # }
2760//! #
2761//! # fn item_eq(&self, other: &Node<'c>) -> bool {
2762//! # if self.item.addr() == other.item.addr() {
2763//! # self.item.addr() == other.item.addr()
2764//! # } else {
2765//! # self.value() == other.value()
2766//! # }
2767//! # }
2768//! # }
2769//! #
2770//! # impl<'c> PartialEq<Node<'c>> for Node<'c> {
2771//! # fn eq(&self, other: &Node<'c>) -> bool {
2772//! # if self.item_eq(other) {
2773//! # let eq = self.value().unwrap_or_default() == other.value().unwrap_or_default();
2774//! # eq
2775//! # } else {
2776//! # false
2777//! # }
2778//! # }
2779//! # }
2780//! #
2781//! # impl<'c> PartialEq<&mut Node<'c>> for Node<'c> {
2782//! # fn eq(&self, other: &&mut Node<'c>) -> bool {
2783//! # let other = unsafe { &**other };
2784//! # if self.item_eq(other) {
2785//! # let eq = self.value().unwrap_or_default() == other.value().unwrap_or_default();
2786//! # eq
2787//! # } else {
2788//! # false
2789//! # }
2790//! # }
2791//! # }
2792//! #
2793//! # impl<'c> Drop for Node<'c> {
2794//! # fn drop(&mut self) {
2795//! # self.dealloc();
2796//! # }
2797//! # }
2798//! #
2799//! # impl<'c> Clone for Node<'c> {
2800//! # fn clone(&self) -> Node<'c> {
2801//! # let mut node = Node::nil();
2802//! # node.refs = self.refs.clone();
2803//! # if self.parent.is_not_null() {
2804//! # node.parent = self.parent.clone();
2805//! # }
2806//! # if self.left.is_not_null() {
2807//! # node.left = self.left.clone();
2808//! # }
2809//! # if self.right.is_not_null() {
2810//! # node.right = self.right.clone();
2811//! # }
2812//! # if !self.item.is_null() {
2813//! # node.item = self.item.clone();
2814//! # }
2815//! # node
2816//! # }
2817//! # }
2818//! #
2819//! # impl<'c> AsRef<Node<'c>> for Node<'c> {
2820//! # fn as_ref(&self) -> &'c Node<'c> {
2821//! # unsafe { std::mem::transmute::<&Node<'c>, &'c Node<'c>>(self) }
2822//! # }
2823//! # }
2824//! # impl<'c> AsMut<Node<'c>> for Node<'c> {
2825//! # fn as_mut(&mut self) -> &'c mut Node<'c> {
2826//! # self.incr_ref();
2827//! # let node = unsafe {
2828//! # let node = &mut *self as *mut Node<'c>;
2829//! # node
2830//! # };
2831//! # unsafe { std::mem::transmute::<&mut Node<'c>, &'c mut Node<'c>>(self) }
2832//! # }
2833//! # }
2834//! # impl<'c> std::fmt::Display for Node<'c> {
2835//! # fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
2836//! # write!(f, "{}", self.id())
2837//! # }
2838//! # }
2839//! # impl<'c> std::fmt::Debug for Node<'c> {
2840//! # fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
2841//! # write!(
2842//! # f,
2843//! # "{}",
2844//! # [
2845//! # format!("Node@"),
2846//! # format!("{:016x}", self.addr()),
2847//! # format!("[refs={}]", *self.refs),
2848//! # if self.item.is_null() {
2849//! # format!("null")
2850//! # } else {
2851//! # format!(
2852//! # "[item={}]",
2853//! # self.value()
2854//! # .map(|value| format!("{:#?}", value))
2855//! # .unwrap_or_else(|| format!("empty"))
2856//! # )
2857//! # },
2858//! # if self.parent.is_null() {
2859//! # String::new()
2860//! # } else {
2861//! # format!(
2862//! # "(parent:{})",
2863//! # if self.parent.is_null() {
2864//! # format!("null")
2865//! # } else {
2866//! # self.parent_value()
2867//! # .map(|parent_value| format!("{:#?}", parent_value))
2868//! # .unwrap_or_else(|| format!("empty"))
2869//! # }
2870//! # )
2871//! # },
2872//! # if self.left.is_null() && self.right.is_null() {
2873//! # String::new()
2874//! # } else {
2875//! # format!(
2876//! # "[left:{} | right:{}]",
2877//! # if self.left.is_null() {
2878//! # format!("null")
2879//! # } else {
2880//! # self.left_value()
2881//! # .map(|left_value| format!("{:#?}", left_value))
2882//! # .unwrap_or_else(|| format!("empty"))
2883//! # },
2884//! # if self.right.is_null() {
2885//! # format!("null")
2886//! # } else {
2887//! # self.right_value()
2888//! # .map(|right_value| format!("{:#?}", right_value))
2889//! # .unwrap_or_else(|| format!("empty"))
2890//! # }
2891//! # )
2892//! # }
2893//! # ]
2894//! # .join("")
2895//! # )
2896//! # }
2897//! # }
2898//! // test_node_nil
2899//! let node = Node::nil();
2900//!
2901//! assert_eq!(node.is_nil(), true);
2902//! assert_eq!(node.parent(), None);
2903//! assert_eq!(node.value(), None);
2904//! assert_eq!(node.left(), None);
2905//! assert_eq!(node.right(), None);
2906//! assert_eq!(node.left_value(), None);
2907//! assert_eq!(node.right_value(), None);
2908//!
2909//! let expected = {
2910//! let node = Node::nil();
2911//! node
2912//! };
2913//! assert_eq!(node, expected);
2914//! assert_eq!(node, Node::nil());
2915//!
2916//!
2917//! // test_node_new
2918//! let node = Node::new(Value::from("value"));
2919//! assert_eq!(node.is_nil(), false);
2920//! assert_eq!(node.parent(), None);
2921//! assert_eq!(node.left(), None);
2922//! assert_eq!(node.right(), None);
2923//! assert_eq!(node.left_value(), None);
2924//! assert_eq!(node.right_value(), None);
2925//!
2926//! assert_eq!(node.value(), Some(Value::from("value")));
2927//!
2928//! let expected = {
2929//! let node = Node::new(Value::from("value"));
2930//! node
2931//! };
2932//! assert_eq!(node, expected);
2933//! assert_eq!(node, Node::new(Value::from("value")));
2934//!
2935//!
2936//! // test_set_left
2937//! let mut node = Node::new(Value::from("value"));
2938//! let mut left = Node::new(Value::from("left"));
2939//!
2940//! node.set_left(&mut left);
2941//!
2942//! assert_eq!(left.parent(), Some(&node));
2943//!
2944//! assert_eq!(node.is_nil(), false);
2945//! assert_eq!(left.parent_value(), Some(Value::from("value")));
2946//! assert_eq!(left.parent(), Some(&node));
2947//! assert_eq!(node.value(), Some(Value::from("value")));
2948//! assert_eq!(node.parent(), None);
2949//! assert_eq!(node.left_value(), Some(Value::from("left")));
2950//! assert_eq!(node.refs(), 3);
2951//! assert_eq!(left.refs(), 2);
2952//! assert_eq!(node.left(), Some(&left));
2953//! assert_eq!(node.right_value(), None);
2954//! assert_eq!(node.right(), None);
2955//!
2956//! let expected = {
2957//! let mut node = Node::new(Value::from("value"));
2958//! let mut left = Node::new(Value::from("left"));
2959//! node.set_left(&mut left);
2960//! node
2961//! };
2962//! assert_eq!(node, expected);
2963//!
2964//! let expected = {
2965//! let mut node = Node::new(Value::from("value"));
2966//! let mut left = Node::new(Value::from("left"));
2967//! node.set_left(&mut left);
2968//! left
2969//! };
2970//! assert_eq!(left, expected);
2971//!
2972//! // test_set_right
2973//! let mut node = Node::new(Value::from("value"));
2974//! let mut right = Node::new(Value::from("right"));
2975//!
2976//! node.set_right(&mut right);
2977//!
2978//! assert_eq!(right.parent(), Some(&node));
2979//!
2980//! assert_eq!(node.is_nil(), false);
2981//! assert_eq!(right.parent_value(), Some(Value::from("value")));
2982//! assert_eq!(right.parent(), Some(&node));
2983//! assert_eq!(node.value(), Some(Value::from("value")));
2984//! assert_eq!(node.parent(), None);
2985//! assert_eq!(node.right_value(), Some(Value::from("right")));
2986//! assert_eq!(node.right(), Some(&right));
2987//! assert_eq!(node.left_value(), None);
2988//! assert_eq!(node.left(), None);
2989//!
2990//! let expected = {
2991//! let mut node = Node::new(Value::from("value"));
2992//! let mut left = Node::new(Value::from("right"));
2993//! node.set_right(&mut left);
2994//! node
2995//! };
2996//! assert_eq!(node, expected);
2997//!
2998//! let expected = {
2999//! let mut node = Node::new(Value::from("value"));
3000//! let mut left = Node::new(Value::from("right"));
3001//! node.set_right(&mut left);
3002//! left
3003//! };
3004//! assert_eq!(right, expected);
3005//!
3006//!
3007//! // test_clone_null
3008//! let node = Node::nil();
3009//! assert_eq!(node.clone(), Node::nil());
3010//!
3011//!
3012//! // test_clone_non_null
3013//! let mut node = Node::new(Value::from("value"));
3014//! let mut left = Node::new(Value::from("left"));
3015//! let mut right = Node::new(Value::from("right"));
3016//!
3017//! node.set_left(&mut left);
3018//! node.set_right(&mut right);
3019//!
3020//! assert_eq!(node.parent(), None);
3021//! assert_eq!(node.is_nil(), false);
3022//! assert_eq!(node.left(), Some(&left));
3023//! assert_eq!(node.right(), Some(&right));
3024//! assert_eq!(node.left_value(), Some(Value::from("left")));
3025//! assert_eq!(node.right_value(), Some(Value::from("right")));
3026//!
3027//! let expected = {
3028//! let mut node = Node::new(Value::from("value"));
3029//! let mut left = Node::new(Value::from("left"));
3030//! let mut right = Node::new(Value::from("right"));
3031//!
3032//! node.set_left(&mut left);
3033//! node.set_right(&mut right);
3034//! node
3035//! };
3036//! assert_eq!(node, expected);
3037//! let expected = {
3038//! let mut node = Node::new(Value::from("value"));
3039//! let mut left = Node::new(Value::from("left"));
3040//! node.set_left(&mut left);
3041//! left
3042//! };
3043//! assert_eq!(left, expected);
3044//! let expected = {
3045//! let mut node = Node::new(Value::from("value"));
3046//! let mut right = Node::new(Value::from("right"));
3047//! node.set_right(&mut right);
3048//! right
3049//! };
3050//! assert_eq!(right, expected);
3051//!
3052//! let tree = node.clone();
3053//! assert_eq!(node, tree);
3054//! ```
3055//!
3056//! ### Value Implementation
3057//!
3058//! ```
3059//! use std::borrow::Cow;
3060//! use std::convert::{AsMut, AsRef};
3061//! use std::cmp::{Eq, Ord, Ordering, PartialEq, PartialOrd};
3062//! #[derive(Clone, PartialOrd, Ord, Default, PartialEq, Eq, Hash)]
3063//! pub enum Value<'c> {
3064//! #[default]
3065//! Nil,
3066//! String(Cow<'c, str>),
3067//! Byte(u8),
3068//! UInt(u64),
3069//! Int(i64),
3070//! }
3071//! impl<'c> Value<'_> {
3072//! pub fn nil() -> Value<'c> {
3073//! Value::Nil
3074//! }
3075//!
3076//! pub fn is_nil(&self) -> bool {
3077//! if *self == Value::Nil {
3078//! true
3079//! } else {
3080//! false
3081//! }
3082//! }
3083//! }
3084//!
3085//! impl<'c> Drop for Value<'c> {
3086//! fn drop(&mut self) {}
3087//! }
3088//!
3089//! impl std::fmt::Display for Value<'_> {
3090//! fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
3091//! write!(
3092//! f,
3093//! "{}",
3094//! match self {
3095//! Value::Nil => "nil".to_string(),
3096//! Value::String(h) => format!("{}", h),
3097//! Value::Byte(h) => format!("{}", h),
3098//! Value::UInt(h) => format!("{}", h),
3099//! Value::Int(h) => format!("{}", h),
3100//! }
3101//! )
3102//! }
3103//! }
3104//! impl std::fmt::Debug for Value<'_> {
3105//! fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
3106//! write!(
3107//! f,
3108//! "{}",
3109//! match self {
3110//! Value::Nil => "nil".to_string(),
3111//! Value::String(h) => format!("{:#?}", h),
3112//! Value::Byte(h) => format!("{}u8", h),
3113//! Value::UInt(h) => format!("{}u64", h),
3114//! Value::Int(h) => format!("{}i64", h),
3115//! }
3116//! )
3117//! }
3118//! }
3119//!
3120//! impl<'c> From<u8> for Value<'c> {
3121//! fn from(value: u8) -> Value<'c> {
3122//! Value::Byte(value)
3123//! }
3124//! }
3125//! impl<'c> From<u64> for Value<'c> {
3126//! fn from(value: u64) -> Value<'c> {
3127//! Value::UInt(value)
3128//! }
3129//! }
3130//! impl<'c> From<i64> for Value<'c> {
3131//! fn from(value: i64) -> Value<'c> {
3132//! Value::Int(value)
3133//! }
3134//! }
3135//! impl<'c> From<&'c str> for Value<'c> {
3136//! fn from(value: &'c str) -> Value<'c> {
3137//! Value::String(Cow::from(value))
3138//! }
3139//! }
3140//! impl<'c> From<Cow<'c, str>> for Value<'c> {
3141//! fn from(value: Cow<'c, str>) -> Value<'c> {
3142//! Value::from(value.into_owned())
3143//! }
3144//! }
3145//! impl<'c> From<&'c mut str> for Value<'c> {
3146//! fn from(value: &'c mut str) -> Value<'c> {
3147//! Value::String(Cow::<'c, str>::Borrowed(&*value))
3148//! }
3149//! }
3150//! impl<'c> From<String> for Value<'c> {
3151//! fn from(value: String) -> Value<'c> {
3152//! Value::String(Cow::from(value))
3153//! }
3154//! }
3155//! impl<'c> From<Option<String>> for Value<'c> {
3156//! fn from(value: Option<String>) -> Value<'c> {
3157//! match value {
3158//! None => Value::Nil,
3159//! Some(value) => Value::from(value),
3160//! }
3161//! }
3162//! }
3163//!
3164//! impl<'c> AsRef<Value<'c>> for Value<'c> {
3165//! fn as_ref(&self) -> &Value<'c> {
3166//! unsafe { &*self }
3167//! }
3168//! }
3169//! impl<'c> AsMut<Value<'c>> for Value<'c> {
3170//! fn as_mut(&mut self) -> &mut Value<'c> {
3171//! unsafe { &mut *self }
3172//! }
3173//! }
3174//!
3175//! impl<'c> PartialEq<&Value<'c>> for Value<'c> {
3176//! fn eq(&self, other: &&Value<'c>) -> bool {
3177//! let other = unsafe { &**other };
3178//! self == other
3179//! }
3180//! }
3181//!
3182//! impl<'c> PartialEq<&mut Value<'c>> for Value<'c> {
3183//! fn eq(&self, other: &&mut Value<'c>) -> bool {
3184//! let other = unsafe { &**other };
3185//! self == other
3186//! }
3187//! }
3188//!
3189pub mod traits;
3190#[doc(inline)]
3191pub use traits::Pointee;
3192pub mod unique_pointer;
3193#[doc(inline)]
3194pub use unique_pointer::UniquePointer;
3195pub mod refcounter;
3196#[doc(inline)]
3197pub use refcounter::RefCounter;