123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100 |
- // Go's concurrency primitives make it easy to
- // express concurrent concepts, such as
- // this binary tree comparison.
- //
- // Trees 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 trees by
- // walking each in its own goroutine,
- // sending their contents through a channel
- // to a third goroutine that compares them.
- package main
- import (
- "fmt"
- "math/rand"
- )
- // A Tree is a binary tree with integer values.
- type Tree struct {
- Left *Tree
- Value int
- Right *Tree
- }
- // Walk traverses a tree depth-first,
- // sending each Value on a channel.
- func Walk(t *Tree, ch chan int) {
- if t == nil {
- return
- }
- Walk(t.Left, ch)
- ch <- t.Value
- Walk(t.Right, ch)
- }
- // Walker launches Walk in a new goroutine,
- // and returns a read-only channel of values.
- func Walker(t *Tree) <-chan int {
- ch := make(chan int)
- go func() {
- Walk(t, ch)
- close(ch)
- }()
- return ch
- }
- // Compare reads values from two Walkers
- // that run simultaneously, and returns true
- // if t1 and t2 have the same contents.
- func Compare(t1, t2 *Tree) bool {
- c1, c2 := Walker(t1), Walker(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 tree
- // holding the values 1k, 2k, ..., nk.
- func New(n, k int) *Tree {
- var t *Tree
- for _, v := range rand.Perm(n) {
- t = insert(t, (1+v)*k)
- }
- return t
- }
- func insert(t *Tree, v int) *Tree {
- if t == nil {
- return &Tree{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")
- }
|