avlsort/
node.rs

1//! The node of AVL tree.
2
3use std::sync::{Arc, Mutex};
4
5use crate::traits::*;
6
7/// When propagating tree height information, 
8/// the direction of the child from which the information cames is indicated.
9pub enum Direction {
10    Left,
11    Right,
12}
13
14/// Information on changing the height of tree.
15#[derive(Clone, Copy)]
16pub enum DeltaDiff {
17    Longer,
18    Zero,
19    Shorter,
20}
21
22/// The node of AVL tree.
23pub struct AvlNode<T> {
24    /// The value of element.
25    pub value: T,
26    /// The difference of heights of children.
27    /// 
28    /// If diff > 0, the height of the left child is larger than that of the right child.
29    pub diff: i32,
30    /// The number of elements smaller than the value of this node, 
31    /// and the number of duplicates of `value`.
32    /// 
33    /// `(number_of_less, number_of_duplicates)`
34    pub n_ledu: (usize, usize),
35    /// Pointer to the left child node.
36    pub left: Option<Arc<Mutex<Self>>>,
37    /// Pointer to the right child node.
38    pub right: Option<Arc<Mutex<Self>>>,
39}
40
41impl<T: TreeElem> AvlNode<T> {
42    /// Create a new node.
43    pub fn new(value: T) -> Self {
44        Self { value, diff: 0, n_ledu: (0, 0), left: None, right: None }
45    }
46
47    /// Push `value` and propagate `((number_of_less, number_of_duplicates), height_information)` to parent node.
48    pub fn push_child(&mut self, value: T) -> ((usize, usize), DeltaDiff) {
49        if value < self.value {
50            self.n_ledu.0 += 1;
51            match &self.left {
52                Some(node) => {
53                    let (n_ledu, d_diff) = node.lock().unwrap().push_child(value);
54                    
55                    (n_ledu, self.balance(d_diff, Direction::Left))
56                }
57                _ => {
58                    self.left = Some(Arc::new(Mutex::new(Self::new(value))));
59                    
60                    ((0, 0), self.balance(DeltaDiff::Longer, Direction::Left))
61                }
62            }
63        } else if value > self.value {
64            match &self.right {
65                Some(node) => {
66                    let (n_ledu, d_diff) = node.lock().unwrap().push_child(value);
67                    
68                    ((n_ledu.0 + self.n_ledu.0 + self.n_ledu.1 + 1, n_ledu.1), self.balance(d_diff, Direction::Right))
69                }
70                _ => {
71                    self.right = Some(Arc::new(Mutex::new(Self::new(value))));
72                    
73                    ((self.n_ledu.0 + self.n_ledu.1 + 1, 0), self.balance(DeltaDiff::Longer, Direction::Right))
74                }
75            }
76        } else {
77            self.n_ledu.1 += 1;
78            (self.n_ledu, DeltaDiff::Zero)
79        }
80    }
81
82    /// Search `value` and propagate `number_of_duplicates` to parent node.
83    pub fn search(&self, value: T) -> Option<usize> {
84        if value == self.value {
85            Some(self.n_ledu.1)
86        } else {
87            if value < self.value {
88                match &self.left {
89                    Some(node) => node.lock().unwrap().search(value),
90                    None => None,
91                }
92            } else {
93                match &self.right {
94                    Some(node) => node.lock().unwrap().search(value),
95                    None => None,
96                }
97            }
98        }
99    }
100
101    /// Remove the node of `value` and propagate `height_information` to parent node.
102    /// 
103    /// If `value` is a duplicate, return and remove only one.
104    pub fn remove_child(&mut self, value: T) -> Result<DeltaDiff, ()> {
105        if value == self.value {
106            return Err(());
107        }
108        if value < self.value {
109            let (new_child, fin, reconnect) = match &self.left {
110                Some(node) => {
111                    let mut n = node.lock().unwrap();
112                    if n.value == value {
113                        if n.n_ledu.1 > 0 {
114                            n.n_ledu.1 -= 1;
115                            (None, Ok(Some(DeltaDiff::Zero)), false)
116                        } else {
117                            n.remove_reconnect()
118                        }
119                    } else {
120                        (None, Err(()), false)
121                    }
122                }
123                None => (None, Ok(None), false),
124            };
125            if reconnect {
126                self.left = new_child;
127            }
128            match fin {
129                Ok(Some(d_diff)) => {
130                    Ok(self.balance(d_diff, Direction::Left))
131                }
132                Ok(None) => {
133                    Err(())
134                }
135                Err(()) => {
136                    match self.left.clone().unwrap().lock().unwrap().remove_child(value) {
137                        Ok(d_diff) => {
138                            Ok(self.balance(d_diff, Direction::Left))
139                        }
140                        Err(()) => Err(())
141                    }
142                }
143            }
144        } else {
145            let (new_child, fin, reconnect) = match &self.right {
146                Some(node) => {
147                    let mut n = node.lock().unwrap();
148                    if n.value == value {
149                        if n.n_ledu.1 > 0 {
150                            n.n_ledu.1 -= 1;
151                            (None, Ok(Some(DeltaDiff::Zero)), false)
152                        } else {
153                            n.remove_reconnect()
154                        }
155                    } else {
156                        (None, Err(()), false)
157                    }
158                }
159                None => (None, Ok(None), false),
160            };
161            if reconnect {
162                self.right = new_child;
163            }
164            match fin {
165                Ok(Some(d_diff)) => {
166                    Ok(self.balance(d_diff, Direction::Right))
167                }
168                Ok(None) => {
169                    Err(())
170                }
171                Err(()) => {
172                    match self.right.clone().unwrap().lock().unwrap().remove_child(value) {
173                        Ok(d_diff) => {
174                            Ok(self.balance(d_diff, Direction::Right))
175                        }
176                        Err(()) => Err(())
177                    }
178                }
179            }
180        }
181    }
182
183    /// Utility function for removing a node.
184    fn remove_reconnect(&mut self) -> (Option<Arc<Mutex<Self>>>, Result<Option<DeltaDiff>, ()>, bool) {
185        match (&self.left, &self.right) {
186            (Some(nl), Some(nr)) => {
187                let n_m = if self.diff >= 0 {
188                    nl.lock().unwrap().max_child()
189                } else {
190                    nr.lock().unwrap().min_child()
191                };
192                self.value = n_m;
193                self.n_ledu.1 = self.search(n_m).unwrap();
194                match self.remove_child(n_m) {
195                    Ok(d_diff) => (None, Ok(Some(d_diff)), false),
196                    Err(()) => panic!(),
197                }
198            }
199            (Some(nl), None) => {
200                (Some(nl.clone()), Ok(Some(self.balance(DeltaDiff::Shorter, Direction::Left))), true)
201            }
202            (None, Some(nr)) => {
203                (Some(nr.clone()), Ok(Some(self.balance(DeltaDiff::Shorter, Direction::Right))), true)
204            }
205            (None, None) => {
206                (None, Ok(Some(DeltaDiff::Shorter)), true)
207            }
208        }
209    }
210
211    /// Balance the tree at the bottom and propagate `height_information` to parent node.
212    pub fn balance(&mut self, d_diff: DeltaDiff, from_dir: Direction) -> DeltaDiff {
213        match d_diff {
214            DeltaDiff::Zero => DeltaDiff::Zero,
215            DeltaDiff::Longer => {
216                match from_dir {
217                    Direction::Left => {
218                        self.diff += 1;
219                        if self.rotate() {
220                            DeltaDiff::Zero
221                        } else {
222                            if self.diff > 0 {
223                                DeltaDiff::Longer
224                            } else {
225                                DeltaDiff::Zero
226                            }
227                        }
228                    }
229                    Direction::Right => {
230                        self.diff -= 1;
231                        if self.rotate() {
232                            DeltaDiff::Zero
233                        } else {
234                            if self.diff < 0 {
235                                DeltaDiff::Longer
236                            } else {
237                                DeltaDiff::Zero
238                            }
239                        }
240                    }
241                }
242            }
243            DeltaDiff::Shorter => {
244                match from_dir {
245                    Direction::Left => {
246                        self.diff -= 1;
247                        if self.diff == -2 {
248                            let d_diff_rotate = match &self.right {
249                                None => panic!(),
250                                Some(node) => {
251                                    if node.lock().unwrap().diff == 0 {
252                                        DeltaDiff::Zero
253                                    } else {
254                                        DeltaDiff::Shorter
255                                    }
256                                }
257                            };
258                            let _ = self.rotate();
259                            d_diff_rotate
260                        } else if self.diff <= 1 && self.diff >= -1 {
261                            if self.diff >= 0 {
262                                DeltaDiff::Shorter
263                            } else {
264                                DeltaDiff::Zero
265                            }
266                        } else {
267                            panic!()
268                        }
269                    }
270                    Direction::Right => {
271                        self.diff += 1;
272                        if self.diff == 2 {
273                            let d_diff_rotate = match &self.left {
274                                None => panic!(),
275                                Some(node) => {
276                                    if node.lock().unwrap().diff == 0 {
277                                        DeltaDiff::Zero
278                                    } else {
279                                        DeltaDiff::Shorter
280                                    }
281                                }
282                            };
283                            d_diff_rotate
284                        } else if self.diff <= 1 && self.diff >= -1 {
285                            if self.diff <= 0 {
286                                DeltaDiff::Shorter
287                            } else {
288                                DeltaDiff::Zero
289                            }
290                        } else {
291                            panic!()
292                        }
293                    }
294                }
295            }
296        }
297    }
298
299    /// Rotate the tree at the bottom to balance it.
300    pub fn rotate(&mut self) -> bool {
301        if self.diff <= 1 && self.diff >= -1 {
302            return false;
303        }
304        if self.diff == 2 {
305            let n_val = self.value;
306            let n_n_ledu1 = self.n_ledu.1;
307            let nr = self.right.clone();
308            let (nl_val, nl_n_ledu1, n_diff, nll_op) = match &mut self.left {
309                None => panic!(),
310                Some(nl_arc) => {
311                    let mut nl = nl_arc.lock().unwrap();
312                    let nl_val = nl.value;
313                    let nl_n_ledu1 = nl.n_ledu.1;
314                    let nll_op = nl.left.clone();
315                    if nl.diff == -1 {
316                        let (nlr_val, nlr_n_ledu1, nlrr_op, diff) = match &mut nl.right {
317                            None => panic!(),
318                            Some(nlr_arc) => {
319                                let mut nlr = nlr_arc.lock().unwrap();
320                                let nlr_diff = nlr.diff;
321                                let diff = if nlr_diff == -1 {
322                                    nlr.diff = 1;
323                                    1
324                                } else if nlr_diff == 0 {
325                                    nlr.diff = 0;
326                                    1
327                                } else if nlr_diff == 1 {
328                                    nlr.diff = 0;
329                                    2
330                                } else {
331                                    panic!()
332                                };
333                                let nlr_val = nlr.value;
334                                let nlr_n_ledu1 = nlr.n_ledu.1;
335                                nlr.value = nl_val;
336                                nlr.n_ledu.1 = nl_n_ledu1;
337                                let nlrl_op = nlr.left.clone();
338                                let nlrr_op = nlr.right.clone();
339                                nlr.left = nll_op;
340                                nlr.n_ledu.0 = match &nlr.left {
341                                    Some(node) => node.lock().unwrap().len_child_and_self(),
342                                    None => 0,
343                                };
344                                nlr.right = nlrl_op;
345                                (nlr_val, nlr_n_ledu1, nlrr_op, diff)
346                            }
347                        };
348                        nl.value = nlr_val;
349                        nl.n_ledu.1 = nlr_n_ledu1;
350                        let nlr_op = nl.right.clone();
351                        nl.right = nlrr_op;
352                        nl.left = nlr_op;
353                        nl.n_ledu.0 = match &nl.left {
354                            Some(node) => node.lock().unwrap().len_child_and_self(),
355                            None => 0,
356                        };
357                        nl.diff = diff;
358                    }
359                    let n_diff = if nl.diff == 2 {
360                        nl.diff = -1;
361                        0
362                    } else if nl.diff == 1 {
363                        nl.diff = 0;
364                        0
365                    } else if nl.diff == 0 {
366                        nl.diff = 1;
367                        -1
368                    } else {
369                        panic!()
370                    };
371                    let nll_op = nl.left.clone();
372                    nl.left = nl.right.clone();
373                    nl.right = nr;
374                    let nl_val = nl.value;
375                    let nl_n_ledu1 = nl.n_ledu.1;
376                    nl.value = n_val;
377                    nl.n_ledu.1 = n_n_ledu1;
378                    nl.n_ledu.0 = match &nl.left {
379                        Some(node) => node.lock().unwrap().len_child_and_self(),
380                        None => 0,
381                    };
382                    (nl_val, nl_n_ledu1, n_diff, nll_op)
383                }
384            };
385            self.value = nl_val;
386            self.n_ledu.1 = nl_n_ledu1;
387            self.diff = n_diff;
388            self.right = self.left.clone();
389            self.left = nll_op;
390            self.n_ledu.0 = match &self.left {
391                Some(node) => node.lock().unwrap().len_child_and_self(),
392                None => 0,
393            };
394
395            return true;
396        } else if self.diff == -2 {
397            let n_val = self.value;
398            let n_n_ledu1 = self.n_ledu.1;
399            let nl = self.left.clone();
400            let (nr_val, nr_n_ledu1, n_diff, nrr_op) = match &mut self.right {
401                None => {
402                    panic!()
403                }
404                Some(nr_arc) => {
405                    let mut nr = nr_arc.lock().unwrap();
406                    let nr_val = nr.value;
407                    let nr_n_ledu1 = nr.n_ledu.1;
408                    let nrr_op = nr.right.clone();
409                    if nr.diff == 1 {
410                        let (nrl_val, nrl_n_ledu1, nrll_op, diff) = match &mut nr.left {
411                            None => panic!(),
412                            Some(nrl_arc) => {
413                                let mut nrl = nrl_arc.lock().unwrap();
414                                let nrl_diff = nrl.diff;
415                                let diff = if nrl_diff == 1 {
416                                    nrl.diff = -1;
417                                    -1
418                                } else if nrl_diff == 0 {
419                                    nrl.diff = 0;
420                                    -1
421                                } else if nrl_diff == -1 {
422                                    nrl.diff = 0;
423                                    -2
424                                } else {
425                                    panic!()
426                                };
427                                let nrl_val = nrl.value;
428                                let nrl_n_ledu1 = nrl.n_ledu.1;
429                                nrl.value = nr_val;
430                                nrl.n_ledu.1 = nr_n_ledu1;
431                                let nrlr_op = nrl.right.clone();
432                                let nrll_op = nrl.left.clone();
433                                nrl.right = nrr_op;
434                                nrl.left = nrlr_op;
435                                nrl.n_ledu.0 = match &nrl.left {
436                                    Some(node) => node.lock().unwrap().len_child_and_self(),
437                                    None => 0,
438                                };
439                                (nrl_val, nrl_n_ledu1, nrll_op, diff)
440                            }
441                        };
442                        nr.value = nrl_val;
443                        nr.n_ledu.1 = nrl_n_ledu1;
444                        let nrl_op = nr.left.clone();
445                        nr.left = nrll_op;
446                        nr.n_ledu.0 = match &nr.left {
447                            Some(node) => node.lock().unwrap().len_child_and_self(),
448                            None => 0,
449                        };
450                        nr.right = nrl_op;
451                        nr.diff = diff;
452                    }
453                    let n_diff = if nr.diff == -2 {
454                        nr.diff = 1;
455                        0
456                    } else if nr.diff == -1 {
457                        nr.diff = 0;
458                        0
459                    } else if nr.diff == 0 {
460                        nr.diff = -1;
461                        1
462                    } else {
463                        panic!()
464                    };
465                    let nrr_op = nr.right.clone();
466                    nr.right = nr.left.clone();
467                    nr.left = nl;
468                    let nr_val = nr.value;
469                    let nr_n_ledu1 = nr.n_ledu.1;
470                    nr.value = n_val;
471                    nr.n_ledu.1 = n_n_ledu1;
472                    nr.n_ledu.0 = match &nr.left {
473                        Some(node) => node.lock().unwrap().len_child_and_self(),
474                        None => 0,
475                    };
476                    (nr_val, nr_n_ledu1, n_diff, nrr_op)
477                }
478            };
479            self.value = nr_val;
480            self.n_ledu.1 = nr_n_ledu1;
481            self.diff = n_diff;
482            self.left = self.right.clone();
483            self.right = nrr_op;
484            self.n_ledu.0 = match &self.left {
485                Some(node) => node.lock().unwrap().len_child_and_self(),
486                None => 0,
487            };
488
489            return true;
490        } else {
491            panic!()
492        }
493    }
494
495    /// Propagate the maximum value in the tree at the bottom to parent node.
496    pub fn max_child(&self) -> T {
497        match &self.right {
498            Some(node) => node.lock().unwrap().max_child(),
499            None => self.value,
500        }
501    }
502
503    /// Return and remove the maximum value, 
504    /// and propagate `(max_value, height_information)` to parent node.
505    /// 
506    /// If the maximum value is a duplicate, return and remove only one.
507    pub fn pop_max_child(&mut self) -> Result<(T, DeltaDiff), ()> {
508        let res = match &self.right {
509            Some(node) => {
510                let mut n = node.lock().unwrap();
511                match &n.right {
512                    Some(_) => {
513                        match &n.pop_max_child() {
514                            Ok((value, d_diff)) => Ok((*value, *d_diff, None)),
515                            Err(()) => Err(()),
516                        }
517                    }
518                    None => {
519                        let value = n.value;
520                        if n.n_ledu.1 > 0 {
521                            n.n_ledu.1 -= 1;
522                            Ok((value, DeltaDiff::Zero, None))
523                        } else {
524                            Ok((value, DeltaDiff::Shorter, Some(n.left.clone())))
525                        }
526                    }
527                }
528            }
529            None => Err(()),
530        };
531        match res {
532            Ok((value, d_diff, reconnect)) => {
533                match reconnect {
534                    Some(node_left) => { self.right = node_left; }
535                    None => {}
536                }
537                Ok((value, self.balance(d_diff, Direction::Right)))
538            }
539            Err(()) => Err(()),
540        }
541    }
542
543    /// Propagate `((max_value, number_of_duplicates), height_information)` to parent node, 
544    /// then remove its node.
545    pub fn pop_max_all_child(&mut self) -> Result<((T, usize), DeltaDiff), ()> {
546        let res = match &self.right {
547            Some(node) => {
548                let mut n = node.lock().unwrap();
549                match &n.right {
550                    Some(_) => {
551                        match &n.pop_max_all_child() {
552                            Ok((value, d_diff)) => Ok((*value, *d_diff, None)),
553                            Err(()) => Err(()),
554                        }
555                    }
556                    None => {
557                        let value = n.value;
558                        Ok(((value, n.n_ledu.1), DeltaDiff::Zero, Some(n.left.clone())))
559                    }
560                }
561            }
562            None => Err(()),
563        };
564        match res {
565            Ok((value, d_diff, reconnect)) => {
566                match reconnect {
567                    Some(node_left) => { self.right = node_left; }
568                    None => {}
569                }
570                Ok((value, self.balance(d_diff, Direction::Right)))
571            }
572            Err(()) => Err(()),
573        }
574    }
575
576    /// Propagate the maximum value in the tree at the bottom to parent node.
577    pub fn min_child(&self) -> T {
578        match &self.left {
579            Some(node) => node.lock().unwrap().max_child(),
580            None => self.value,
581        }
582    }
583
584    /// Return and remove the maximum value, 
585    /// and propagate `(max_value, height_information)` to parent node.
586    /// 
587    /// If the maximum value is a duplicate, return and remove only one.
588    pub fn pop_min_child(&mut self) -> Result<(T, DeltaDiff), ()> {
589        let res = match &self.left {
590            Some(node) => {
591                let mut n = node.lock().unwrap();
592                match &n.left {
593                    Some(_) => {
594                        match &n.pop_min_child() {
595                            Ok((value, d_diff)) => Ok((*value, *d_diff, None)),
596                            Err(()) => Err(()),
597                        }
598                    }
599                    None => {
600                        let value = n.value;
601                        if n.n_ledu.1 > 0 {
602                            n.n_ledu.1 -= 1;
603                            Ok((value, DeltaDiff::Zero, None))
604                        } else {
605                            Ok((value, DeltaDiff::Shorter, Some(n.right.clone())))
606                        }
607                    }
608                }
609            }
610            None => Err(()),
611        };
612        match res {
613            Ok((value, d_diff, reconnect)) => {
614                match reconnect {
615                    Some(node_right) => { self.left = node_right; }
616                    None => {}
617                }
618                Ok((value, self.balance(d_diff, Direction::Left)))
619            }
620            Err(()) => Err(()),
621        }
622    }
623
624    /// Propagate `((max_value, number_of_duplicates), height_information)` to parent node, 
625    /// then remove its node.
626    pub fn pop_min_all_child(&mut self) -> Result<((T, usize), DeltaDiff), ()> {
627        let res = match &self.left {
628            Some(node) => {
629                let mut n = node.lock().unwrap();
630                match &n.left {
631                    Some(_) => {
632                        match &n.pop_min_all_child() {
633                            Ok((value, d_diff)) => Ok((*value, *d_diff, None)),
634                            Err(()) => Err(()),
635                        }
636                    }
637                    None => {
638                        Ok(((n.value, n.n_ledu.1), DeltaDiff::Shorter, Some(n.right.clone())))
639                    }
640                }
641            }
642            None => Err(()),
643        };
644        match res {
645            Ok((value, d_diff, reconnect)) => {
646                match reconnect {
647                    Some(node_right) => { self.left = node_right; }
648                    None => {}
649                }
650
651                Ok((value, self.balance(d_diff, Direction::Left)))
652            }
653            Err(()) => Err(()),
654        }
655    }
656
657    /// Return the number of elements in the tree at the bottom including itself.
658    pub fn len_child_and_self(&self) -> usize {
659        match &self.right {
660            Some(node) => self.n_ledu.0 + self.n_ledu.1 + 1 + node.lock().unwrap().len_child_and_self(),
661            None => self.n_ledu.0 + self.n_ledu.1 + 1,
662        }
663    }
664
665    /// Return the height of the tree at the bottom.
666    pub fn height_child(&self) -> usize {
667        if self.diff >= 0 {
668            match &self.left {
669                Some(node) => 1 + node.lock().unwrap().height_child(),
670                None => 1,
671            }
672        } else {
673            match &self.right {
674                Some(node) => 1 + node.lock().unwrap().height_child(),
675                None => 1,
676            }
677        }
678    }
679
680    /// Utility function to test `diff`.
681    pub fn check_diff(&self) {
682        let hl = match &self.left {
683            Some(node) => node.lock().unwrap().height_child(),
684            None => 0,
685        } as i32;
686        let hr = match &self.right {
687            Some(node) => node.lock().unwrap().height_child(),
688            None => 0,
689        } as i32;
690        let diff = hl - hr;
691        if diff != self.diff {
692            panic!("Diff value is incorrect!: diff={}, left={}, right={}", self.diff, hl, hr);
693        }
694    }
695}
696
avlsort/node.rs

avlsort/
node.rs
