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