go-tour: improve existing solution for binarytrees.go and add non leaky solution
LGTM=adg
R=adg
CC=golang-codereviews
https://golang.org/cl/196890043
diff --git a/solutions/binarytrees.go b/solutions/binarytrees.go
index f4ca07f..83e94d3 100644
--- a/solutions/binarytrees.go
+++ b/solutions/binarytrees.go
@@ -13,13 +13,12 @@
)
func walkImpl(t *tree.Tree, ch chan int) {
- if t.Left != nil {
- walkImpl(t.Left, ch)
+ if t == nil {
+ return
}
+ walkImpl(t.Left, ch)
ch <- t.Value
- if t.Right != nil {
- walkImpl(t.Right, ch)
- }
+ walkImpl(t.Right, ch)
}
// Walk walks the tree t sending all values
@@ -32,6 +31,8 @@
// Same determines whether the trees
// t1 and t2 contain the same values.
+// NOTE: The implementation leaks goroutines when trees are different.
+// See binarytrees_quit.go for a better solution.
func Same(t1, t2 *tree.Tree) bool {
w1, w2 := make(chan int), make(chan int)
@@ -41,14 +42,13 @@
for {
v1, ok1 := <-w1
v2, ok2 := <-w2
- if v1 != v2 || ok1 != ok2 {
+ if !ok1 || !ok2 {
+ return ok1 == ok2
+ }
+ if v1 != v2 {
return false
}
- if !ok1 {
- break
- }
}
- return true
}
func main() {
diff --git a/solutions/binarytrees_quit.go b/solutions/binarytrees_quit.go
new file mode 100644
index 0000000..f73e09e
--- /dev/null
+++ b/solutions/binarytrees_quit.go
@@ -0,0 +1,72 @@
+// Copyright 2015 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+// +build ignore
+
+package main
+
+import (
+ "fmt"
+
+ "code.google.com/p/go-tour/tree"
+)
+
+func walkImpl(t *tree.Tree, ch, quit chan int) {
+ if t == nil {
+ return
+ }
+ walkImpl(t.Left, ch, quit)
+ select {
+ case ch <- t.Value:
+ // Value successfully sent.
+ case <-quit:
+ return
+ }
+ walkImpl(t.Right, ch, quit)
+}
+
+// Walk walks the tree t sending all values
+// from the tree to the channel ch.
+func Walk(t *tree.Tree, ch, quit chan int) {
+ walkImpl(t, ch, quit)
+ close(ch)
+}
+
+// Same determines whether the trees
+// t1 and t2 contain the same values.
+func Same(t1, t2 *tree.Tree) bool {
+ w1, w2 := make(chan int), make(chan int)
+ quit := make(chan int)
+ defer close(quit)
+
+ go Walk(t1, w1, quit)
+ go Walk(t2, w2, quit)
+
+ for {
+ v1, ok1 := <-w1
+ v2, ok2 := <-w2
+ if !ok1 || !ok2 {
+ return ok1 == ok2
+ }
+ if v1 != v2 {
+ return false
+ }
+ }
+}
+
+func main() {
+ fmt.Print("tree.New(1) == tree.New(1): ")
+ if Same(tree.New(1), tree.New(1)) {
+ fmt.Println("PASSED")
+ } else {
+ fmt.Println("FAILED")
+ }
+
+ fmt.Print("tree.New(1) != tree.New(2): ")
+ if !Same(tree.New(1), tree.New(2)) {
+ fmt.Println("PASSED")
+ } else {
+ fmt.Println("FAILED")
+ }
+}
