diff options
Diffstat (limited to 'doc/play/tree.go')
-rw-r--r-- | doc/play/tree.go | 100 |
1 files changed, 0 insertions, 100 deletions
diff --git a/doc/play/tree.go b/doc/play/tree.go deleted file mode 100644 index 3790e6cda5..0000000000 --- a/doc/play/tree.go +++ /dev/null @@ -1,100 +0,0 @@ -// 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") -} |