I am a beginner in Golang
I was reading about concurrency in Go from here.
Things were going fine until I was presented with the question on the 8th slide.
The question is: Find out whether two given Binary trees are equivalent or not.
My Approach: Do an Inorder traversal, save the values from both the trees in a slice and compare them.
Here is my solution: [incomplete]
package main
import (
"fmt"
"golang.org/x/tour/tree"
)
// Walk walks the tree t sending all values
// from the tree to the channel ch.
func Walk(t *tree.Tree, ch chan int) {
if t != nil {
Walk(t.Left, ch)
ch <- t.Value
Walk(t.Right, ch)
}
}
// Same determines whether the trees
// t1 and t2 contain the same values.
func Same(t1, t2 *tree.Tree) bool {
ch1 := make(chan int)
ch2 := make(chan int)
go func() {
fmt.Println("executing first go routing")
Walk(t1, ch1)
fmt.Println("closing channel [ch1]")
close(ch1)
}()
go func() {
fmt.Println("executing second go routing")
Walk( t2, ch2 )
fmt.Println("closing channel [ch2]")
close(ch2)
}()
shouldContinue := true
var continue1, continue2 bool
for shouldContinue {
select {
case r1, ok1 := <-ch1:
fmt.Println("[ch1] [rcvd]", r1)
continue1 = ok1
case r2, ok2 := <-ch2:
fmt.Println("[ch2] [rcvd]", r2)
continue2 = ok2
}
shouldContinue = continue1 || continue2
}
return true
}
func main() {
Same(tree.New(1), tree.New(1))
}
I know that goroutines are cooperatively scheduled and one and completely block another one if it is looping or doing computation continuously. So I expected that for the output, It would first receive the values from either of channels, close it and then it would receive values from another channel and then close. Once both are closed, the for loop will break.
To my surprise, the first go routine never gets scheduled. Here is the output I am receiving:
executing second go routing
[ch2] [rcvd] 1
[ch2] [rcvd] 2
[ch2] [rcvd] 3
[ch2] [rcvd] 4
[ch2] [rcvd] 5
[ch2] [rcvd] 6
[ch2] [rcvd] 7
[ch2] [rcvd] 8
[ch2] [rcvd] 9
[ch2] [rcvd] 10
closing channel [ch2]
[ch2] [rcvd] 0
Can anyone explain what is going on here? Once channel2 is closed and second go routine finishes, why doesn't the first one gets executed?
Any help would be appreciated. Thank you.
UPDATE:
I googled about breaking out of the channels and I found a SO question here.
According to which, I updated my solution as follows:
package main
import (
"fmt"
"golang.org/x/tour/tree"
// "time"
)
// Walk walks the tree t sending all values
// from the tree to the channel ch.
func Walk(t *tree.Tree, ch chan int) {
// time.Sleep(time.Millisecond)
if t != nil {
Walk(t.Left, ch)
ch <- t.Value
Walk(t.Right, ch)
}
}
// Same determines whether the trees
// t1 and t2 contain the same values.
func Same(t1, t2 *tree.Tree) bool {
ch1 := make(chan int)
ch2 := make(chan int)
go func() {
fmt.Println("executing first go routing")
Walk(t1, ch1)
fmt.Println("closing channel [ch1]")
close(ch1)
}()
go func() {
fmt.Println("executing second go routing")
Walk( t2, ch2 )
fmt.Println("closing channel [ch2]")
close(ch2)
}()
for {
select {
case r1, ok1 := <-ch1:
fmt.Println("[ch1] [rcvd]", r1)
if !ok1 {
ch1 = nil
}
case r2, ok2 := <-ch2:
fmt.Println("[ch2] [rcvd]", r2)
if !ok2 {
ch2 = nil
}
}
if ch1 == nil && ch2 == nil {
break
}
}
return true
}
func main() {
Same(tree.New(1), tree.New(1))
}
Which gives the exact output which I thought the first snippet would:
executing second go routing
[ch2] [rcvd] 1
[ch2] [rcvd] 2
[ch2] [rcvd] 3
[ch2] [rcvd] 4
[ch2] [rcvd] 5
[ch2] [rcvd] 6
[ch2] [rcvd] 7
[ch2] [rcvd] 8
[ch2] [rcvd] 9
[ch2] [rcvd] 10
closing channel [ch2]
[ch2] [rcvd] 0
executing first go routing
[ch1] [rcvd] 1
[ch1] [rcvd] 2
[ch1] [rcvd] 3
[ch1] [rcvd] 4
[ch1] [rcvd] 5
[ch1] [rcvd] 6
[ch1] [rcvd] 7
[ch1] [rcvd] 8
[ch1] [rcvd] 9
[ch1] [rcvd] 10
closing channel [ch1]
[ch1] [rcvd] 0
I am now even more confused about what is going on.