Двоичное дерево со статически ограниченной максимальной глубиной вложенности

main.rs

use std::cmp::Ordering;
use std::convert::Infallible as Never;
use std::fmt::{self, Debug};

struct Z;
struct S<T>(T);

#[derive(Clone)]
struct Node<T, Next> {
    value: T,
    left: Next,
    right: Next,
}

trait Find<T> {
    fn find<F>(&self, cmp: F) -> Option<&T>
    where
        F: FnMut(&T) -> Ordering;
    
    fn find_mut<F>(&mut self, cmp: F) -> Option<&mut T>
    where
        F: FnMut(&T) -> Ordering;
}

impl<T> Find<T> for Node<T, Never> {
    fn find<F>(&self, mut cmp: F) -> Option<&T>
    where
        F: FnMut(&T) -> Ordering,
    {
        if cmp(&self.value).is_eq() {
            Some(&self.value)
        } else {
            None
        }
    }

    fn find_mut<F>(&mut self, mut cmp: F) -> Option<&mut T>
    where
        F: FnMut(&T) -> Ordering,
    {
        if cmp(&self.value).is_eq() {
            Some(&mut self.value)
        } else {
            None
        }
    }
}

impl<T, Next> Find<T> for Node<T, Option<Next>>
where
    Next: Find<T>,
{
    fn find<F>(&self, mut cmp: F) -> Option<&T>
    where
        F: FnMut(&T) -> Ordering,
    {
        use Ordering::*;

        match cmp(&self.value) {
            Less => self.left.as_ref()?.find(cmp),
            Equal => Some(&self.value),
            Greater => self.right.as_ref()?.find(cmp),
        }
    }

    fn find_mut<F>(&mut self, mut cmp: F) -> Option<&mut T>
    where
        F: FnMut(&T) -> Ordering,
    {
        use Ordering::*;

        match cmp(&self.value) {
            Less => self.left.as_mut()?.find_mut(cmp),
            Equal => Some(&mut self.value),
            Greater => self.right.as_mut()?.find_mut(cmp),
        }
    }
}

impl<T, Next> Node<T, Option<Next>> {
    fn some_leaf(value: T) -> Option<Self> {
        Some(Self::leaf(value))
    }

    fn leaf(value: T) -> Self {
        Self {
            value,
            left: None,
            right: None,
        }
    }
}

impl<T: Debug> Debug for Node<T, Option<Node<T, Never>>> {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        f.debug_tuple("Node::leaf").field(&self.value).finish()
    }
}

impl<T, Next> Debug for Node<T, Option<Node<T, Next>>>
where
    T: Debug,
    Node<T, Next>: Debug,
{
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        f
            .debug_struct("Node")
            .field("value", &self.value)
            .field("left", &self.left)
            .field("right", &self.right)
            .finish()
    }
}

trait Project<T> {
    type Projected;
}

impl<T> Project<T> for Z {
    type Projected = Node<T, Never>;
}

impl<T, N> Project<T> for S<N>
where
    N: Project<T>,
{
    type Projected = Node<T, Option<N::Projected>>;
}

struct Tree<T, Height: Project<T>> {
    repr: Height::Projected,
}

impl<T, Height: Project<T>> Tree<T, Height> {
    fn find<F>(&self, cmp: F) -> Option<&T>
    where
        Height::Projected: Find<T>,
        F: FnMut(&T) -> Ordering,
    {
        Find::find(&self.repr, cmp)
    }

    fn find_mut<F>(&mut self, cmp: F) -> Option<&mut T>
    where
        Height::Projected: Find<T>,
        F: FnMut(&T) -> Ordering,
    {
        Find::find_mut(&mut self.repr, cmp)
    }
}

// нет, мы не можем написать `impl From<Height::Projected> for Tree<T, Height>`,
// поскольку компилятор не может доказать, что `Height::Projected` и `Tree<T, Height>`
// безусловно являются разными типами и потому эта реализация не кофликтует
// с `impl From<T> for T`
impl<T, Height> From<Node<T, Option<Height::Projected>>> for Tree<T, S<Height>>
where
    Height: Project<T>,
{
    fn from(repr: Node<T, Option<Height::Projected>>) -> Self {
        Self { repr }
    }
}

impl<T> From<Node<T, Never>> for Tree<T, Z>
{
    fn from(repr: Node<T, Never>) -> Self {
        Self { repr }
    }
}

fn main() {
    let tree: Tree<i32, S<S<Z>>> = Node {
        value: 42,
        left: None,
        right: Node::some_leaf(43),
    }.into();

    println!("{:#?}", tree.repr);
    println!("{:?}", tree.find(|x| 43.cmp(x)));

    // let _: Tree<i32, S<Z>> = Node {
    //     value: 42,
    //     left: None,
    //     right: Node::leaf(43),
    // }.into_tree();
}