aboutsummaryrefslogtreecommitdiff
path: root/doc/play/tree.go
diff options
context:
space:
mode:
Diffstat (limited to 'doc/play/tree.go')
-rw-r--r--doc/play/tree.go100
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")
-}