pub enum Ordering {
    Less,
    Equal,
    Greater,
}


// TODO: la structure AVLNode est extrait comme un inductif à un cas
// au lieu d'être extrait comme une structure
struct AVLNode {
    val: u32,
    left: AVLTree,
    right: AVLTree,
}

type AVLTree = Option<Box<AVLNode>>;

struct AVLTreeSet {
    root: AVLTree,
}

impl AVLTreeSet {
    pub fn new() -> Self {
        Self { root: None }
    }

    pub fn find(&mut self, value: u32) -> bool {
        let mut current_tree = &mut self.root;

        while let Some(current_node) = current_tree {
            match cmp(&current_node.val, &value) {
                Ordering::Less => current_tree = &mut current_node.right,
                Ordering::Equal => return true,
                Ordering::Greater => current_tree = &mut current_node.left,
            }
        }

        false
    }
    pub fn insert(&mut self, value: u32) -> bool {
        let mut current_tree = &mut self.root;

        while let Some(current_node) = current_tree {
            match cmp(&current_node.val, &value) {
                Ordering::Less => current_tree = &mut current_node.right,
                Ordering::Equal => return false,
                Ordering::Greater => current_tree = &mut current_node.left,
            }
        }

        *current_tree = Some(Box::new(AVLNode {
            val: value,
            left: None,
            right: None,
        }));

        true
    }
}

fn cmp(a: &u32, other: &u32) -> Ordering {
        if *a < *other {
            Ordering::Less
        } else if *a == *other {
            Ordering::Equal
        } else {
            Ordering::Greater
        }
    }