rs_bush/
bush.rs

1use std::{ptr::null_mut, collections::VecDeque};
2
3
4pub type IterItems<T, It> = std::iter::Map<It, fn(&BushNode<T>) -> &T>;
5pub type IterItemsMut<T, It> = std::iter::Map<It, fn(&mut BushNode<T>) -> &mut T>;
6
7pub struct BushSlice<T>(pub Box<BushNode<T>>, pub Box<BushNode<T>>);
8
9
10pub struct NodeHandle<T> (*const BushNode<T>);
11
12impl<T> NodeHandle<T> {
13
14    #[inline(always)]
15    pub const fn as_ptr(&self) -> *const BushNode<T> {
16        self.0
17    }
18
19
20    #[inline(always)]
21    pub const fn as_ref(&self) -> &BushNode<T> {
22        unsafe { &*self.0 }
23    }
24
25
26    #[inline(always)]
27    pub const fn clone(&self) -> NodeHandle<T> {
28        NodeHandle(self.0)
29    }
30
31
32    #[inline(always)]
33    pub fn as_mut(self) -> &'static mut BushNode<T> {
34        unsafe { &mut *(self.0 as *mut BushNode<T>) }
35    }
36
37}
38
39
40impl<T> PartialEq for NodeHandle<T> {
41    fn eq(&self, other: &Self) -> bool {
42        self.0 == other.0
43    }
44}
45
46
47pub struct BushNodeItemIterRight<'a, T> {
48
49    node: Option<&'a BushNode<T>>
50
51}
52
53
54pub struct BushNodeItemIterRightMut<'a, T> {
55
56    node: Option<&'a mut BushNode<T>>
57
58}
59
60
61pub struct BushNodeItemIterLeft<'a, T> {
62
63    node: Option<&'a BushNode<T>>
64
65}
66
67
68pub struct BushNodeItemIterLeftMut<'a, T> {
69
70    node: Option<&'a mut BushNode<T>>
71
72}
73
74
75impl<'a, T> Iterator for BushNodeItemIterRight<'a, T> {
76    type Item = &'a T;
77
78    fn next(&mut self) -> Option<Self::Item> {
79        if let Some(node) = self.node {
80            self.node = if node.right.is_null() {
81                None
82            } else {
83                unsafe {
84                    Some(&(*node.right))
85                }
86            };
87            Some(&node.item)
88        } else {
89            None
90        }
91    }
92}
93
94
95impl<'a, T> Iterator for BushNodeItemIterRightMut<'a, T> {
96    type Item = &'a mut T;
97
98    fn next(&mut self) -> Option<Self::Item> {
99        if let Some(node) = self.node.take() {
100            if !node.right.is_null() {
101                unsafe {
102                    self.node = Some(&mut (*node.right))
103                }
104            };
105            Some(&mut node.item)
106        } else {
107            None
108        }
109    }
110}
111
112
113impl<'a, T> Iterator for BushNodeItemIterLeft<'a, T> {
114    type Item = &'a T;
115
116    fn next(&mut self) -> Option<Self::Item> {
117        if let Some(node) = self.node {
118            self.node = if node.left.is_null() {
119                None
120            } else {
121                unsafe {
122                    Some(&(*node.left))
123                }
124            };
125            Some(&node.item)
126        } else {
127            None
128        }
129    }
130}
131
132
133impl<'a, T> Iterator for BushNodeItemIterLeftMut<'a, T> {
134    type Item = &'a mut T;
135
136    fn next(&mut self) -> Option<Self::Item> {
137        if let Some(node) = self.node.take() {
138            if !node.left.is_null() {
139                unsafe {
140                    self.node = Some(&mut (*node.left))
141                }
142            };
143            Some(&mut node.item)
144        } else {
145            None
146        }
147    }
148}
149
150
151pub struct BushNodeIterLeft<'a, T> {
152
153    node: Option<&'a BushNode<T>>
154
155}
156
157
158pub struct BushNodeIterLeftMut<'a, T> {
159
160    node: Option<&'a mut BushNode<T>>
161
162}
163
164
165impl<'a, T> Iterator for BushNodeIterLeft<'a, T> {
166    type Item = &'a BushNode<T>;
167
168    fn next(&mut self) -> Option<Self::Item> {
169        if let Some(node) = self.node {
170            self.node = if node.left.is_null() {
171                None
172            } else {
173                unsafe {
174                    Some(&(*node.left))
175                }
176            };
177            Some(node)
178        } else {
179            None
180        }
181    }
182}
183
184
185impl<'a, T> Iterator for BushNodeIterLeftMut<'a, T> {
186    type Item = &'a mut BushNode<T>;
187
188    fn next(&mut self) -> Option<Self::Item> {
189        if let Some(node) = self.node.take() {
190            if !node.left.is_null() {
191                unsafe {
192                    self.node = Some(&mut (*node.left))
193                }
194            };
195            Some(node)
196        } else {
197            None
198        }
199    }
200}
201
202
203pub struct BushNodeIterRight<'a, T> {
204
205    node: Option<&'a BushNode<T>>
206
207}
208
209
210pub struct BushNodeIterRightMut<'a, T> {
211
212    node: Option<&'a mut BushNode<T>>
213
214}
215
216
217impl<'a, T> Iterator for BushNodeIterRight<'a, T> {
218    type Item = &'a BushNode<T>;
219
220    fn next(&mut self) -> Option<Self::Item> {
221        if let Some(node) = self.node {
222            self.node = if node.right.is_null() {
223                None
224            } else {
225                unsafe {
226                    Some(&(*node.right))
227                }
228            };
229            Some(node)
230        } else {
231            None
232        }
233    }
234}
235
236
237impl<'a, T> Iterator for BushNodeIterRightMut<'a, T> {
238    type Item = &'a mut BushNode<T>;
239
240    fn next(&mut self) -> Option<Self::Item> {
241        if let Some(node) = self.node.take() {
242            if !node.right.is_null() {
243                unsafe {
244                    self.node = Some(&mut (*node.right))
245                }
246            };
247            Some(node)
248        } else {
249            None
250        }
251    }
252}
253
254
255pub struct BushNode<T> {
256
257    left: *mut BushNode<T>,
258    right: *mut BushNode<T>,
259
260    pub children: Option<Bush<T>>,
261
262    pub item: T
263
264}
265
266
267impl<T> BushNode<T> {
268
269    /// Create a new bush node
270    pub fn new(item: T, left: *mut BushNode<T>) -> BushNode<T> {
271        Self {
272            left,
273            right: null_mut(),
274            children: None,
275            item
276        }
277    }
278
279
280    pub fn into_handle(&self) -> NodeHandle<T> {
281        NodeHandle(self as *const BushNode<T>)
282    }
283
284
285    /// Insert the given slice to the left while preserving the links
286    pub fn insert_slice_left(&mut self, slice: BushSlice<T>) {
287        let start_node = Box::leak(slice.0);
288        let end_node = Box::leak(slice.1);
289        
290        if !self.left.is_null() {
291            unsafe {
292                (*self.left).right = start_node;
293            }
294        }
295
296        start_node.left = self.left;
297        end_node.right = self;
298
299        self.left = end_node;
300    }
301
302
303    /// Insert the given slice to the right while preserving the links
304    pub fn insert_slice_right(&mut self, slice: BushSlice<T>) {
305
306        let start_node = Box::leak(slice.0);
307        let end_node = Box::leak(slice.1);
308
309        if !self.right.is_null() {
310            unsafe {
311                (*self.right).left = end_node;
312            }
313        }
314
315        end_node.right = self.right;
316        start_node.left = self;
317
318        self.right = start_node;
319    }
320
321
322    /// Insert the given node to the left while preserving the links
323    pub fn insert_left_node(&mut self, node: Box<BushNode<T>>) {
324        let node = Box::leak(node);
325
326        node.right = self;
327
328        if !self.left.is_null() {
329            unsafe {
330                (*self.left).right = node;
331            }
332        } 
333
334        node.left = self.left;
335
336        self.left = node;
337    }
338
339
340    /// Insert the given node to the right while preserving the links
341    pub fn insert_right_node(&mut self, node: Box<BushNode<T>>) {
342        let node = Box::leak(node);
343
344        node.left = self;
345
346        if !self.right.is_null() {
347            unsafe {
348                (*self.right).left = node;
349            }
350        }
351
352        node.right = self.right;
353
354        self.right = node;
355    }
356
357
358    /// Get the node to the left, if any
359    pub fn left_node(&self) -> Option<&BushNode<T>> {
360        if self.left.is_null() {
361            None
362        } else {
363            unsafe {
364                Some(&*self.left)
365            }
366        }
367    }
368
369
370    /// Get the node to the right, if any
371    pub fn right_node(&self) -> Option<&BushNode<T>> {
372        if self.right.is_null() {
373            None
374        } else {
375            unsafe {
376                Some(&*self.right)
377            }
378        }
379    }
380
381
382    /// Get the node to the left, if any
383    pub fn left_node_mut(&self) -> Option<&mut BushNode<T>> {
384        if self.left.is_null() {
385            None
386        } else {
387            unsafe {
388                Some(&mut *self.left)
389            }
390        }
391    }
392
393
394    /// Get the node to the right, if any
395    pub fn right_node_mut(&self) -> Option<&mut BushNode<T>> {
396        if self.right.is_null() {
397            None
398        } else {
399            unsafe {
400                Some(&mut *self.right)
401            }
402        }
403    }
404
405
406    /// Get the item to the left, if any
407    pub fn left_item(&self) -> Option<&T> {
408        self.left_node().map(|node| &node.item)
409    }
410
411
412    /// Get the item to the right, if any
413    pub fn right_item(&self) -> Option<&T> {
414        self.right_node().map(|node| &node.item)
415    }
416
417
418    /// Get an iterator over the items to the left
419    pub fn iter_items_left(&self) -> IterItems<T, BushNodeIterLeft<T>> {
420        self.iter_nodes_left().map(|node| &node.item)
421    }
422
423
424    /// Get an iterator over the items to the right
425    pub fn iter_items_right(&self) -> IterItems<T, BushNodeIterRight<T>> {
426        self.iter_nodes_right().map(|node| &node.item)
427    }
428
429
430    /// Get an iterator over the nodes to the left
431    pub fn iter_nodes_left(&self) -> BushNodeIterLeft<'_, T> {
432        BushNodeIterLeft { 
433            node: Some(self)
434        }
435    }
436
437
438    /// Get an iterator over the nodes to the right
439    pub fn iter_nodes_right(&self) -> BushNodeIterRight<'_, T> {
440        BushNodeIterRight { 
441            node: Some(self)
442        }
443    }
444
445
446    pub fn bfs_nodes(&self) -> BFSIter<T> {
447        BFSIter {
448            nodes: self.children.as_ref().map(
449                |children|
450            {
451                let mut nodes = VecDeque::new();
452                if let Some(first_node) = children.first_node() {
453                    nodes.push_back(first_node);
454                }
455                nodes
456            }).unwrap_or_default()
457        }
458    }
459
460
461    pub fn dfs_nodes(&self) -> DFSIter<T> {
462        DFSIter {
463            nodes: self.children.as_ref().map(
464                |children|
465            {
466                let mut nodes = VecDeque::new();
467                if let Some(first_node) = children.first_node() {
468                    nodes.push_back(first_node);
469                }
470                nodes
471            }).unwrap_or_default()
472        }
473    }
474
475
476    pub fn bfs_items(&self) -> IterItems<T, BFSIter<T>> {
477        self.bfs_nodes().map(|node| &node.item)
478    }
479
480
481    pub fn dfs_items(&self) -> IterItems<T, DFSIter<T>> {
482        self.dfs_nodes().map(|node| &node.item)
483    }
484
485}
486
487
488pub struct Bush<T> {
489
490    first: *mut BushNode<T>,
491    last: *mut BushNode<T>,
492
493}
494
495
496impl<T> Bush<T> {
497
498    /// Create a new empty bush
499    pub fn new() -> Bush<T> {
500        Self::default()
501    }
502
503
504    pub fn from_slice(slice: BushSlice<T>) -> Bush<T> {
505        Bush {
506            first: Box::leak(slice.0),
507            last: Box::leak(slice.1),
508        }
509    }
510
511
512    pub fn is_empty(&self) -> bool {
513        self.first.is_null()
514    }
515
516
517    /// Return the number of nodes in the bush's top layer
518    pub fn top_layer_length(&self) -> usize {
519        self.iter_nodes().count()
520    }
521
522
523    /// Return the total number of nodes in the bush
524    pub fn total_node_count(&self) -> usize {
525        self.iter_nodes().map(
526            |node| {
527                let mut count = 1;
528
529                if let Some(children) = &node.children {
530                    count += children.total_node_count();
531                }
532
533                count
534            }
535        ).sum()
536    }
537
538
539    /// Get the last item of the bush's top layer
540    pub fn last_item(&self) -> Option<&T> {
541        self.last_node().map(|node| &node.item)
542    }
543
544
545    /// Get the last item of the bush's top layer
546    pub fn last_item_mut(&self) -> Option<&mut T> {
547        self.last_node_mut().map(|node| &mut node.item)
548    }
549
550
551    /// Get the last node if the bush's top layer
552    pub fn last_node(&self) -> Option<&BushNode<T>> {
553        if self.last.is_null() {
554            None
555        } else {
556            unsafe {
557                Some(&*self.last)
558            }
559        }
560    }
561
562
563    /// Get the last node if the bush's top layer
564    pub fn last_node_mut(&self) -> Option<&mut BushNode<T>> {
565        if self.last.is_null() {
566            None
567        } else {
568            unsafe {
569                Some(&mut *self.last)
570            }
571        }
572    }
573
574
575    /// Get the first item of the bush's top layer
576    pub fn first_item(&self) -> Option<&T> {
577        self.first_node().map(|node| &node.item)
578    }
579
580
581    /// Get the first item of the bush's top layer
582    pub fn first_item_mut(&self) -> Option<&mut T> {
583        self.first_node_mut().map(|node| &mut node.item)
584    }
585
586
587    pub fn first_node_handle(&self) -> Option<NodeHandle<T>> {
588        if self.first.is_null() {
589            None
590        } else {
591            Some(NodeHandle(self.first))
592        }
593    }
594
595
596    pub fn last_node_handle(&self) -> Option<NodeHandle<T>> {
597        if self.last.is_null() {
598            None
599        } else {
600            Some(NodeHandle(self.last))
601        }
602    }
603
604
605    /// Get the first node of the bush's top layer
606    pub fn first_node(&self) -> Option<&BushNode<T>> {
607        if self.first.is_null() {
608            None
609        } else {
610            unsafe {
611                Some(&*self.first)
612            }
613        }
614    }
615
616
617    /// Get the first node of the bush's top layer
618    pub fn first_node_mut(&self) -> Option<&mut BushNode<T>> {
619        if self.first.is_null() {
620            None
621        } else {
622            unsafe {
623                Some(&mut *self.first)
624            }
625        }
626    }
627
628
629    /// Get the nth node of the bush's top layer
630    pub fn nth_node(&self, i: usize) -> Option<&BushNode<T>> {
631        self.iter_nodes().nth(i)
632    }
633
634
635    /// Get the nth item of the bush's top layer
636    pub fn nth_item(&self, i: usize) -> Option<&T> {
637        self.nth_node(i).map(|node| &node.item)
638    }
639
640
641    /// Append a new node to the bush's top layer
642    pub fn append(&mut self, item: T) {
643
644        let node = Box::leak(Box::new(BushNode::new(item, self.last)));
645
646        if self.last.is_null() {
647            // Bush is empty
648            self.first = node;
649            self.last = node;
650        } else {
651            // Bush is not empty
652            unsafe {
653                (*self.last).right = node;
654            }
655            self.last = node;
656        }
657    }
658
659
660    /// Prepend a new node to the bush's top layer
661    pub fn prepend(&mut self, item: T) {
662
663        let node = Box::leak(Box::new(BushNode::new(item, null_mut())));
664
665        if self.first.is_null() {
666            // Bush is empty
667            self.first = node;
668            self.last = node;
669        } else {
670            // Bush is not empty
671            unsafe {
672                (*self.first).left = node;
673            }
674            node.right = self.first;
675            self.first = node;
676        }
677    }
678
679
680    /// Get an iterator over the items of the bush's top layer
681    pub fn iter_items(&self) -> IterItems<T, BushNodeIterRight<T>> {
682        self.iter_nodes().map(|node| &node.item)
683    }
684
685
686    /// Get an iterator over the items of the bush's top layer
687    pub fn iter_items_mut(&mut self) -> IterItemsMut<T, BushNodeIterRightMut<T>> {
688        self.iter_nodes_mut().map(|node| &mut node.item)
689    }
690
691
692    /// Get an iterator over the nodes of the bush's top layer
693    pub fn iter_nodes(&self) -> BushNodeIterRight<'_, T> {
694        BushNodeIterRight {
695            node: if self.first.is_null() {
696                None
697            } else {
698                Some(unsafe { &*self.first })
699            }
700        }
701    }
702
703
704    /// Get an iterator over the nodes of the bush's top layer
705    pub fn iter_nodes_mut(&self) -> BushNodeIterRightMut<'_, T> {
706        BushNodeIterRightMut {
707            node: if self.first.is_null() {
708                None
709            } else {
710                Some(unsafe { &mut *self.first })
711            }
712        }
713    }
714
715
716    /// Extrat the given node and its branches, assuming that the node is in the bush's top layer
717    /// Assumes the node pointer is not null
718    pub fn extract_node(&mut self, node: NodeHandle<T>) -> Box<BushNode<T>> {
719        let node_ptr = node.as_ptr() as *mut BushNode<T>;
720        let node = node.as_ref();
721
722        if node_ptr != self.first {
723            let left_node = node.left;
724            // Assume the left node is not null since the current node is not the first
725            unsafe {
726                (*left_node).right = node.right
727            }
728        } else {
729            self.first = node.right;
730        }
731
732        if node_ptr != self.last {
733            let right_node = node.right;
734            // Assume the right node is not null since the current node is not the last
735            unsafe {
736                (*right_node).left = node.left;
737            }
738        } else {
739            self.last = node.left;
740        }
741
742        unsafe { Box::from_raw(node_ptr) }
743    }
744
745
746    /// Extract a slice of the bush and the relative branches into a new bush, assumimg the nodes are n the bush's top layer
747    pub fn extract_slice(&mut self, start_node: NodeHandle<T>, end_node: NodeHandle<T>) -> BushSlice<T> {
748        let start_ptr = start_node.as_ptr() as *mut BushNode<T>;
749        let end_ptr = end_node.as_ptr() as *mut BushNode<T>;
750        let start_node = start_node.as_ref();
751        let end_node = end_node.as_ref();
752
753        if start_ptr != self.first {
754            let left_node = start_node.left;
755            // Assume the left node is not null
756            unsafe {
757                (*left_node).right = end_node.right;
758            }
759        } else {
760            self.first = end_node.right;
761        }
762
763        if end_ptr != self.last {
764            let right_node = end_node.right;
765            // Assume the right node is nt null
766            unsafe {
767                (*right_node).left = start_node.left;
768            }
769        } else {
770            self.last = start_node.left;
771        }
772
773        unsafe {
774            BushSlice(Box::from_raw(start_ptr), Box::from_raw(end_ptr))
775        }
776    }
777
778
779    /// Recursively flatten the bush into the top layer
780    pub fn flatten(&mut self) {
781
782        for node in self.iter_nodes_mut() {
783            if let Some(mut children) = node.children.take() {
784                children.flatten();
785                if let Some(children) = children.as_slice() {
786                    node.insert_slice_right(children);
787                }
788            }
789        }
790
791    }
792
793
794    /// Return the first and last node of the bush's top layer, consuming the bush
795    pub fn as_slice(mut self) -> Option<BushSlice<T>> {
796        if self.first.is_null() {
797            None
798        } else {
799            // Set the first and last nodes to null to avoid dropping them when the bush is dropped
800            let first = self.first;
801            let last = self.last;
802            self.first = null_mut();
803            self.last = null_mut();
804            unsafe {
805                Some(BushSlice(Box::from_raw(first), Box::from_raw(last)))
806            }
807        }
808    }
809
810
811    /// Get a breadth first search iterator over the bush
812    pub fn bfs_nodes(&self) -> BFSIter<T> {
813        BFSIter {
814            nodes: if let Some(first) = self.first_node() {
815                VecDeque::from(vec![first])
816            } else {
817                VecDeque::new()
818            }
819        }
820    }
821
822
823    /// Get a depth first search iterator over the bush
824    pub fn dfs_nodes(&self) -> DFSIter<T> {
825        DFSIter {
826            nodes: if let Some(first) = self.first_node() {
827                VecDeque::from(vec![first])
828            } else {
829                VecDeque::new()
830            }
831        }
832    }
833
834
835    /// Get a breadth first search iterator over the bush
836    pub fn bfs_items(&self) -> IterItems<T, BFSIter<T>> {
837        self.bfs_nodes().map(|node| &node.item)
838    }
839
840
841    /// Get a depth first search iterator over the bush
842    pub fn dfs_items(&self) -> IterItems<T, DFSIter<T>> {
843        self.dfs_nodes().map(|node| &node.item)
844    }
845
846}
847
848
849impl<T> Default for Bush<T> {
850    fn default() -> Self {
851        Self {
852            first: null_mut(),
853            last: null_mut(),
854        }
855    }
856}
857
858
859pub struct BFSIter<'a, T> {
860
861    nodes: VecDeque<&'a BushNode<T>>,
862
863}
864
865
866impl<'a, T> Iterator for BFSIter<'a, T> {
867    type Item = &'a BushNode<T>;
868
869    fn next(&mut self) -> Option<Self::Item> {
870        
871        self.nodes.pop_front().map(
872            |node|
873        {
874            // Push the same-layer node on the front to give it priority
875            if let Some(node) = node.right_node() {
876                self.nodes.push_front(node);
877            }
878
879            // Push lower-layer nodes on the back for lower priority
880            if let Some(children) = &node.children {
881                if let Some(first_node) = children.first_node() {
882                    self.nodes.push_back(first_node);
883                }
884            }
885
886            node
887        })
888    }
889}
890
891
892pub struct DFSIter<'a, T> {
893
894    nodes: VecDeque<&'a BushNode<T>>,
895
896}
897
898
899impl<'a, T> Iterator for DFSIter<'a, T> {
900    type Item = &'a BushNode<T>;
901
902    fn next(&mut self) -> Option<Self::Item> {
903
904        self.nodes.pop_front().map(
905            |node|
906        {
907            // Push the same-layer nodes before children nodes to give children priority
908            if let Some(right) = node.right_node() {
909                self.nodes.push_front(right);
910            }
911
912            if let Some(children) = &node.children {
913                if let Some(first_node) = children.first_node() {
914                    self.nodes.push_front(first_node);
915                }
916            }
917
918            node
919        })
920    }
921}
922
923
924impl<T> Drop for Bush<T> {
925    fn drop(&mut self) {
926        let mut node = self.first;
927
928        while !node.is_null() {
929            let owned_node = unsafe { Box::from_raw(node) };
930            node = owned_node.right;
931        }        
932    }
933}
934
935
936#[cfg(test)]
937mod tests {
938    use super::*;
939
940    #[test]
941    fn create_empty_bush() {
942        let bush: Bush<i32> = Bush::new();
943        assert_eq!(bush.top_layer_length(), 0);
944        assert_eq!(bush.total_node_count(), 0);
945    }
946
947
948    #[test]
949    fn append_to_bush() {
950        let mut bush = Bush::new();
951        for i in 0..10 {
952            bush.append(i);
953        }
954        assert_eq!(bush.top_layer_length(), 10);
955        assert_eq!(bush.total_node_count(), 10);
956    }
957
958
959    #[test]
960    fn prepend_to_bush() {
961        let mut bush = Bush::new();
962        for i in 0..10 {
963            bush.prepend(i);
964        }
965        assert_eq!(bush.top_layer_length(), 10);
966        assert_eq!(bush.total_node_count(), 10);
967
968        for i in 0..10 {
969            assert_eq!(bush.nth_item(i), Some(&(9 - i)));
970        }
971    }
972
973
974    #[test]
975    fn iter_items() {
976        let mut bush = Bush::new();
977        for i in 0..10 {
978            bush.append(i);
979        }
980        for (i, item) in bush.iter_items().enumerate() {
981            assert_eq!(i, *item as usize);
982        }
983    }
984
985
986    #[test]
987    fn iter_bush_nodes() {
988        let mut bush = Bush::new();
989        bush.append(1);
990        bush.append(2);
991        bush.append(3);
992        let mut iter = bush.iter_nodes();
993        assert_eq!(iter.next().map(|n| n.item), Some(1));
994        assert_eq!(iter.next().map(|n| n.item), Some(2));
995        assert_eq!(iter.next().map(|n| n.item), Some(3));
996        assert_eq!(iter.next().map(|n| n.item), None);
997    }
998
999
1000    #[test]
1001    fn iter_bush_nodes_mut() {
1002        let mut bush = Bush::new();
1003        bush.append(1);
1004        bush.append(2);
1005        bush.append(3);
1006        let mut iter = bush.iter_nodes_mut();
1007        assert_eq!(iter.next().map(|n| n.item), Some(1));
1008        assert_eq!(iter.next().map(|n| n.item), Some(2));
1009        assert_eq!(iter.next().map(|n| n.item), Some(3));
1010        assert_eq!(iter.next().map(|n| n.item), None);
1011    }
1012
1013
1014    #[test]
1015    fn extract_node() {
1016        let mut bush = Bush::new();
1017        bush.append(1);
1018        bush.append(2);
1019        bush.append(3);
1020        let node = bush.extract_node(bush.first_node_handle().unwrap());
1021        assert_eq!(node.item, 1);
1022        assert_eq!(bush.top_layer_length(), 2);
1023        assert_eq!(bush.total_node_count(), 2);
1024    }
1025
1026    
1027    #[test]
1028    fn extract_slice() {
1029        let mut bush = Bush::new();
1030        bush.append(1);
1031        bush.append(2);
1032        bush.append(3);
1033        let slice = Bush::from_slice(bush.extract_slice(bush.first_node_handle().unwrap(), bush.last_node_handle().unwrap()));
1034        assert_eq!(slice.top_layer_length(), 3);
1035        assert_eq!(bush.top_layer_length(), 0);
1036        assert_eq!(slice.total_node_count(), 3);
1037        assert_eq!(bush.total_node_count(), 0);
1038    }
1039
1040
1041    #[test]
1042    fn build_up() {
1043        let mut bush: Bush<usize> = Bush::new();
1044        
1045        let mut counter = 0;
1046
1047        for _ in 0..10 {
1048            bush.append(counter);
1049            counter += 1;
1050
1051            let mut children = Bush::new();
1052            for _ in 0..10 {
1053                children.append(counter);
1054                counter += 1;
1055            }
1056            
1057            bush.last_node_mut().unwrap().children = Some(children);
1058        }
1059
1060        assert_eq!(bush.total_node_count(), counter);
1061    }
1062
1063
1064    #[test]
1065    fn flatten() {
1066        let mut bush: Bush<usize> = Bush::new();
1067        
1068        let mut counter = 0;
1069
1070        for _ in 0..10 {
1071            bush.append(counter);
1072            counter += 1;
1073
1074            let mut children = Bush::new();
1075            for _ in 0..10 {
1076                children.append(counter);
1077                counter += 1;
1078            }
1079            
1080            bush.last_node_mut().unwrap().children = Some(children);
1081        }
1082
1083        assert_eq!(bush.total_node_count(), counter);
1084
1085        bush.flatten();
1086
1087        assert_eq!(bush.total_node_count(), counter);
1088
1089        bush.iter_nodes().enumerate().for_each(|(i, item)| {
1090            assert_eq!(i, item.item);
1091        });
1092    }
1093
1094
1095    #[test]
1096    fn extract_bush() {
1097        let mut bush: Bush<usize> = Bush::new();
1098
1099        let mut counter = 0;
1100        for _ in 0..10 {
1101            bush.append(counter);
1102            counter += 1;
1103
1104            let mut children = Bush::new();
1105            for _ in 0..10 {
1106                children.append(counter);
1107                counter += 1;
1108            }
1109
1110            bush.last_node_mut().unwrap().children = Some(children);
1111        }
1112
1113        let _extracted = bush.as_slice().unwrap();
1114
1115    }
1116
1117    
1118
1119}
1120
rs_bush/bush.rs

rs_bush/
bush.rs
