The "Same Fringe" is a simple and known programming problem:
http://wiki.c2.com/?SameFringeProblem
The problem is:
"two binary trees have the same fringe if they have exactly the same leaves reading from left to right."
Solving that problem in Python is easy:
from itertools import zip_longest
class Leaf:
def __init__(self, v):
self.v = v
class Branch:
def __init__(self, t1, t2):
self.t1, self.t2 = t1, t2
def tree_values(t):
if isinstance(t, Leaf):
yield t.v
elif isinstance(t, Branch):
yield from tree_values(t.t1)
yield from tree_values(t.t2)
def same_fringe(t1, t2):
return all(v1 == v2 for v1, v2 in zip_longest(tree_values(t1), tree_values(t2)))
def main():
L, B = Leaf, Branch
t1 = B(B(L(1), L(2)), L(3))
t2 = B(L(1), B(L(2), L(3)))
print(same_fringe(t1, t2))
t3 = B(L(1), L(2))
print(same_fringe(t1, t3))
main()
I've tried to write a similar program in Rust Nightly with similar generators (but I think currently in Rust you can't do something like the Python yield from
):
#![feature(generator_trait, generators, box_syntax, box_patterns)]
use std::ops::{Generator, GeneratorState};
fn generator_to_iterator<G>(g: G) -> impl Iterator<Item = G::Yield>
where G: Generator<Return = ()> {
struct It<G>(G);
impl<G: Generator<Return = ()>> Iterator for It<G> {
type Item = G::Yield;
fn next(&mut self) -> Option<Self::Item> {
unsafe {
match self.0.resume() {
GeneratorState::Yielded(y) => Some(y),
GeneratorState::Complete(()) => None,
}
}
}
}
It(g)
}
enum Tree { Leaf(u32), Branch(Box<Tree>, Box<Tree>) }
fn tree_values<'a>(t: &'a Tree) -> impl Iterator<Item=u32> + 'a {
generator_to_iterator(move || {
match t {
Tree::Leaf(v) => { yield *v; },
Tree::Branch(ref t1, ref t2) => {
for v in tree_values(t1) { yield v; }
for v in tree_values(t2) { yield v; }
},
}
})
}
fn same_fringe(t1: &Tree, t2: &Tree) -> bool {
tree_values(t1).eq(tree_values(t2))
}
fn main() {
use Tree::{Leaf as L, Branch as B};
let t1 = B(box B(box L(1), box L(2)), box L(3));
let t2 = B(box L(1), box B(box L(2), box L(3)));
let t3 = B(box L(1), box L(2));
println!("{}", same_fringe(&t1, &t2)); // True
println!("{}", same_fringe(&t1, &t3)); // False
}
But it detects a type cycle error. So do I have to box?