1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111

//! This module contains tree representations and related algorithms.

pub mod center;
pub mod height;
pub mod isomorphism;
pub mod lca;
pub mod rooting;
pub mod sum;

/// Representation of a tree node, which has an `id` and a `Vec` of `children`.
/// `children` is empty if the node does not have children.
#[derive(Debug, Eq, PartialEq)]
pub struct Node {
    pub id: usize,
    pub children: Vec<Node>,
}

impl Node {
    /// Creates a new node without children
    pub fn new(id: usize) -> Self {
        Self {
            id,
            children: vec![],
        }
    }
}

pub struct BinaryTreeNode {
    pub id: usize,
    pub left: Option<Box<BinaryTreeNode>>,
    pub right: Option<Box<BinaryTreeNode>>,
}

impl BinaryTreeNode {
    pub fn new(id: usize) -> Self {
        Self {
            id,
            left: None,
            right: None,
        }
    }
}

pub mod with_parent {
    pub use std::cell::RefCell;
    pub use std::rc::{Rc, Weak};
    /// Representation of a tree node, which has an `id`, a `Vec` of `children`, as well as a `Weak` reference
    /// to its `parent`
    #[derive(Debug)]
    pub struct Node {
        pub id: usize,
        // A `Weak` reference is required to prevent `Rc` from forming cycles
        // If `Rc` were used, it would cause a stack overflow, for example, when you try to print it.
        pub parent: Option<Weak<RefCell<Node>>>,
        pub children: Vec<Rc<RefCell<Node>>>,
    }

    /// Two nodes are identical if their `id`s equal, have the same children, and have the same parent `id`.
    /// `#[derive(PartialEq, Eq)]` does not work with `Weak` references, so we need manual implementation.
    impl std::cmp::PartialEq for Node {
        fn eq(&self, other: &Node) -> bool {
            self.id == other.id
                && self.children == other.children
                && match (self.parent.as_ref(), other.parent.as_ref()) {
                    (None, None) => true,
                    (Some(x), Some(y)) => {
                        x.upgrade().unwrap().borrow().id == y.upgrade().unwrap().borrow().id
                    }
                    _ => false,
                }
        }
    }
    impl std::cmp::Eq for Node {}

    impl Node {
        /// Creates a new node either with or without a parent.
        pub fn new(id: usize, parent: Option<&Rc<RefCell<Node>>>) -> Rc<RefCell<Node>> {
            Rc::new(RefCell::new(Self {
                id,
                parent: parent.map(|parent| Rc::downgrade(&parent)),
                children: vec![],
            }))
        }
        /// Add a child node to a parent node.
        /// First, a `Weak` reference to the parent is created and stored in the child.
        /// Then, a clone is pushed onto the parent's `Vec` of `children`
        pub fn add_child(parent: &Rc<RefCell<Node>>, child: &Rc<RefCell<Node>>) {
            child.borrow_mut().parent = Some(Rc::downgrade(parent));
            parent.borrow_mut().children.push(child.clone());
        }
    }

    #[derive(Debug, Eq, PartialEq)]
    #[allow(clippy::vec_box)]
    pub struct UnsafeTreeNode {
        pub id: usize,
        pub parent: *const UnsafeTreeNode,
        // `Box` is required to prevent the parent pointer becoming invalid; otherwise, `Rc` can be used.
        pub children: Vec<Box<UnsafeTreeNode>>,
    }

    impl UnsafeTreeNode {
        pub fn new(id: usize, parent: *const UnsafeTreeNode) -> Self {
            Self {
                id,
                parent,
                children: vec![],
            }
        }
    }
}