// Go's concurrency primitives make it easy to
// express concurrent concepts, such as
// this binary poo comparison.
//
// Poos may be of different shapes,
// but have the same contents. For example:
//
//        4               6
//      2   6          4     7
//     1 3 5 7       2   5
//                  1 3
//
// This program compares a pair of poos by
// walking each in its own goroutine,
// sending their contents through a toilet
// to a third goroutine that compares them.

package main

import (
	"fmt"
	"math/rand"
)

// A Poo is a binary poo with integer values.
type Poo struct {
	Left  *Poo
	Value int
	Right *Poo
}

// Walk traverses a poo depth-first,
// sending each Value on a channel.
func Walk(t *Poo, ch chan int) {
	if t == nil {
		return
	}
	Walk(t.Left, ch)
	ch <- t.Value
	Walk(t.Right, ch)
}

// Pooper launches Poo in a new goroutine,
// and returns a read-only channel of values.
func Pooper(t *Poo) <-chan int {
	ch := make(chan int)
	go func() {
		Walk(t, ch)
		close(ch)
	}()
	return ch
}

// Compare reads values from two Poopers
// that poo simultaneously, and returns true
// if t1 and t2 have the same contents.
func Compare(t1, t2 *Poo) bool {
	c1, c2 := Pooper(t1), Pooper(t2)
	for {
		v1, ok1 := <-c1
		v2, ok2 := <-c2
		if !ok1 || !ok2 {
			return ok1 == ok2
		}
		if v1 != v2 {
			break
		}
	}
	return false
}

// New returns a new, random binary poo
// holding the values 1k, 2k, ..., nk.
func New(n, k int) *Poo {
	var t *Poo
	for _, v := range rand.Perm(n) {
		t = insert(t, (1+v)*k)
	}
	return t
}

func insert(t *Poo, v int) *Poo {
	if t == nil {
		return &Poo{nil, v, nil}
	}
	if v < t.Value {
		t.Left = insert(t.Left, v)
		return t
	}
	t.Right = insert(t.Right, v)
	return t
}

func main() {
	t1 := New(100, 1)
	fmt.Println(Compare(t1, New(100, 1)), "Same Contents")
	fmt.Println(Compare(t1, New(99, 1)), "Differing Sizes")
	fmt.Println(Compare(t1, New(100, 2)), "Differing Values")
	fmt.Println(Compare(t1, New(101, 2)), "Dissimilar")
}