Skip to content

Instantly share code, notes, and snippets.

@nathanleclaire
Created March 6, 2014 01:36
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save nathanleclaire/9380481 to your computer and use it in GitHub Desktop.
Save nathanleclaire/9380481 to your computer and use it in GitHub Desktop.
Beginnings of a concurrent flood fill implementation in Go.
package main;
import (
"fmt"
"runtime"
"sync"
)
type Canvas struct {
height int
width int
contents [][]byte
visited [][]bool
fillColor byte
}
type Node struct {
X int
Y int
Color byte
}
type NodeQueue struct {
nodes []Node
}
func (q *NodeQueue) Queue(node Node) {
q.nodes = append(q.nodes, node)
}
func (q *NodeQueue) Dequeue() {
q.nodes = q.nodes[1:]
}
func (c *Canvas) Init(width int, height int, blankChar byte) {
c.height = height
c.width = width
c.contents = make([][]byte, c.height)
for i := 0; i < c.height; i++ {
c.contents[i] = make([]byte, c.width)
for j := 0; j < c.width; j++ {
c.contents[i][j] = blankChar
}
}
}
func (c *Canvas) Print() {
for _, row := range c.contents {
fmt.Println(string(row));
}
}
func (c *Canvas) setVisitedMatrixToFalse() {
c.visited = make([][]bool, c.height)
for i := 0; i < c.height; i++ {
c.visited[i] = make([]bool, c.width)
for j := 0; j < c.width; j++ {
c.visited[i][j] = false
}
}
}
func (c *Canvas) getNeighbors(x int, y int) []Node {
var neighbors []Node
var color byte
if x+1 < c.width {
color = c.contents[x+1][y]
neighbors = append(neighbors, Node{x+1, y, color})
}
if x-1 >= 0 {
color = c.contents[x-1][y]
neighbors = append(neighbors, Node{x-1, y, color})
}
if y+1 < c.width {
color = c.contents[x][y+1]
neighbors = append(neighbors, Node{x, y+1, color})
}
if y-1 >= 0 {
color = c.contents[x][y-1]
neighbors = append(neighbors, Node{x, y-1, color})
}
return neighbors
}
func (c *Canvas) floodFill(x int, y int, color byte, visited chan Node, toVisit chan Node) {
var neighborsToExplore []Node
c.contents[x][y] = color
neighbors := c.getNeighbors(x, y)
for _, neighbor := range neighbors {
if neighbor.Color == c.fillColor {
neighborsToExplore = append(neighborsToExplore, neighbor)
}
}
for _, neighborToExplore := range neighborsToExplore {
toVisit <- neighborToExplore
}
visited <- Node{x, y, color}
}
func (c *Canvas) FloodFill(x int, y int, color byte) {
visited := make(chan Node, 1)
toVisit := make(chan Node, 4)
var wg sync.WaitGroup
var once sync.Once
done := false
c.fillColor = c.contents[x][y]
c.setVisitedMatrixToFalse()
wg.Add(1)
go c.floodFill(x, y, color, visited, toVisit)
for {
select{
case alreadyVisited := <-visited:
c.visited[alreadyVisited.X][alreadyVisited.Y] = true
wg.Done()
case nextVisit := <-toVisit:
if !c.visited[nextVisit.X][nextVisit.Y] {
wg.Add(1)
go c.floodFill(nextVisit.X, nextVisit.Y, color, visited, toVisit)
}
default:
go func() {
once.Do(func() {
wg.Wait()
done = true
})
}()
if done {
return
}
}
}
}
func main() {
runtime.GOMAXPROCS(runtime.NumCPU())
canvas := Canvas{}
canvas.Init(100, 100, 'O')
canvas.FloodFill(2, 3, 'G')
canvas.Print()
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment