// Rust compiler CRASHES

// From the discussion in TG
// https://scastie.scala-lang.org/Odomontois/RmcXO65LQrqR87YcDIwl5w/1
// https://play.rust-lang.org/?version=nightly&mode=release&edition=2018&gist=1956b17e0da475a61dc30396921a3a9a

/*
trait Monoid[A]:
    def empty: A
    def (a: A) |+| (b: A): A

object Monoid:
    def empty[A](using m: Monoid[A]): A  = m.empty

    given Monoid[Int]:
        def empty = 0
        def (x: Int) |+| (y: Int) = x + y

trait Measured[A, R]:
    def (a: A) measure: R

object Measured:
    def of [A, R](a: A)(using Measured[A, R]): R = a.measure

    given [A] as Measured[A, A]:
        def (a: A) measure: A = a

    given [A, R](using Measured[A, R], Monoid[R]) as Measured[(A, A), R]:
        def (a: (A, A)) measure: R = a._1.measure |+| a._2.measure

    given [A, R](using Measured[A, R], Monoid[R]) as Measured[Option[A], R]:
        def (a: Option[A]) measure: R = a.fold(Monoid.empty)(_.measure)

enum CherryTree[A]:
    case Empty()
    case One(a: A)
    case Branch(left: Option[A], mid: CherryTree[(A, A)], right: Option[A])

    def :+(a: A): CherryTree[A] = this match
        case Empty()               => One(a)
        case One(b)                => Branch(None, One((b, a)), None)
        case Branch(l, m, None)    => Branch(l, m, Some(a))
        case Branch(l, m, Some(b)) => Branch(l, m :+ (b, a), None)

    def +:(a: A): CherryTree[A] = this match
        case Empty()               => One(a)
        case One(b)                => Branch(None, One((a, b)), None)
        case Branch(None, m, r)    => Branch(Some(a), m, r)
        case Branch(Some(b), m, r) => Branch(None, (b, a) +: m, r)

object CherryTree:
    def apply[A](a: A*): CherryTree[A] = a.foldLeft(CherryTree.Empty())(_ :+ _)

    given measured[A, R](using Measured[A, R], Monoid[R]) as Measured[CherryTree[A], R]:
        def (tree: CherryTree[A]) measure = tree match
            case CherryTree.Empty()          => Monoid.empty
            case CherryTree.One(a)           => a.measure
            case CherryTree.Branch(l, m, r)  =>
                Measured.of[R = R](l) |+| Measured.of[R = R](m) |+| Measured.of[R = R](r)

@main def cherryTreeMain() =
    val tree = CherryTree(1, 2, 3, 4, 5, 6, 7)
    println(tree)
    println(tree.measure)
*/


trait Monoid {
    fn empty() -> Self;
    fn plus(self, b: Self) -> Self;
}

impl Monoid for i32 {
    fn empty() -> Self { 0 }
    fn plus(self, b: i32) -> Self { self + b }
}

trait Measured<R> {
    fn measure(self) -> R;
}

impl<A> Measured<A> for A {
    fn measure(self) -> A { self }
}

impl<A: Measured<R>, R: Monoid> Measured<R> for (A, A) {
    fn measure(self) -> R {
        self.0.measure().plus(self.1.measure())
    }
}

impl<A: Measured<R>, R: Monoid> Measured<R> for Option<A> {
    fn measure(self) -> R {
        self.map(|x| x.measure()).unwrap_or(Monoid::empty())
    }
}

#[derive(Debug)]
enum CherryTree<A> {
    Empty(),
    One(A),
    Branch { left: Option<A>, mid: Box<CherryTree<(A, A)>>, right: Option<A> }
}

impl<A> CherryTree<A> {
    fn right(self, a: A) -> Self {
        match self {
            CherryTree::Empty() =>
                CherryTree::One(a),
            CherryTree::One(b) =>
                CherryTree::Branch {left: None, mid: Box::new(CherryTree::One((b, a))), right: None},
            CherryTree::Branch { left, mid, right: None } =>
                CherryTree::Branch {left, mid, right: Some(a)},
            CherryTree::Branch { left, mid, right: Some(b) } =>
                CherryTree::Branch { left, mid: Box::new(mid.right((b, a))), right: None }
        }
    }

    fn left(self, a: A) -> Self {
        match self {
            CherryTree::Empty() =>
                CherryTree::One(a),
            CherryTree::One(b) =>
                CherryTree::Branch {left: None, mid: Box::new(CherryTree::One((a, b))), right: None},
            CherryTree::Branch { left: None, mid, right } =>
                CherryTree::Branch {left: Some(a), mid, right},
            CherryTree::Branch { left: Some(b), mid, right } =>
                CherryTree::Branch { left: None, mid: Box::new(mid.left((b, a))), right }
        }
    }
}

impl<'a, A: Measured<R>, R: Monoid> Measured<R> for &'a CherryTree<A> {
    fn measure(self) -> R {
        match self {
            CherryTree::Empty() => Monoid::empty(),
            CherryTree::One(a) => a.measure(),
            CherryTree::Branch { left, mid, right } =>
                left.measure().plus(mid.as_ref().measure()).plus(right.measure()),
        }
    }
}


fn main() {
    let tree = CherryTree::Empty()
        .right(1)
        .right(2)
        .right(3)
        .right(4)
        .right(5)
        .right(6)
        .right(7);

    println!("{:?}", tree);
    println!("{:?}", tree.measure());
}