diff options
Diffstat (limited to 'vendor/github.com/mattermost/rsc/rosetta')
4 files changed, 339 insertions, 0 deletions
diff --git a/vendor/github.com/mattermost/rsc/rosetta/graph/Makefile b/vendor/github.com/mattermost/rsc/rosetta/graph/Makefile new file mode 100644 index 000000000..1cb49f788 --- /dev/null +++ b/vendor/github.com/mattermost/rsc/rosetta/graph/Makefile @@ -0,0 +1,7 @@ +include $(GOROOT)/src/Make.inc + +TARG=rsc.googlecode.com/hg/rosetta/graph +GOFILES=\ + graph.go\ + +include $(GOROOT)/src/Make.pkg diff --git a/vendor/github.com/mattermost/rsc/rosetta/graph/graph.go b/vendor/github.com/mattermost/rsc/rosetta/graph/graph.go new file mode 100644 index 000000000..359617d41 --- /dev/null +++ b/vendor/github.com/mattermost/rsc/rosetta/graph/graph.go @@ -0,0 +1,133 @@ +// Copyright 2011 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. + +// Simple demonstration of a graph interface and +// Dijkstra's algorithm built on top of that interface, +// without using inheritance. + +package graph + +import "container/heap" + +// A Graph is the interface implemented by graphs that +// this package can run algorithms on. +type Graph interface { + // NumVertex returns the number of vertices in the graph. + NumVertex() int + + // VertexID returns a vertex ID, 0 <= ID < NumVertex(), for v. + VertexID(v Vertex) int + + // Neighbors returns a slice of vertices that are adjacent + // to v in the graph. + Neighbors(v Vertex) []Vertex +} + +type Vertex interface { + String() string +} + +// ShortestPath uses Dijkstra's algorithm to find the shortest +// path from start to end in g. It returns the path as a slice of +// vertices, with start first and end last. If there is no path, +// ShortestPath returns nil. +func ShortestPath(g Graph, start, end Vertex) []Vertex { + d := newDijkstra(g) + + d.visit(start, 1, nil) + for !d.empty() { + p := d.next() + if g.VertexID(p.v) == g.VertexID(end) { + break + } + for _, v := range g.Neighbors(p.v) { + d.visit(v, p.depth+1, p) + } + } + + p := d.pos(end) + if p.depth == 0 { + // unvisited - no path + return nil + } + path := make([]Vertex, p.depth) + for ; p != nil; p = p.parent { + path[p.depth-1] = p.v + } + return path +} + +// A dpos is a position in the Dijkstra traversal. +type dpos struct { + depth int + heapIndex int + v Vertex + parent *dpos +} + +// A dijkstra is the Dijkstra traversal's work state. +// It contains the heap queue and per-vertex information. +type dijkstra struct { + g Graph + q []*dpos + byID []dpos +} + +func newDijkstra(g Graph) *dijkstra { + d := &dijkstra{g: g} + d.byID = make([]dpos, g.NumVertex()) + return d +} + +func (d *dijkstra) pos(v Vertex) *dpos { + p := &d.byID[d.g.VertexID(v)] + p.v = v // in case this is the first time we've seen it + return p +} + +func (d *dijkstra) visit(v Vertex, depth int, parent *dpos) { + p := d.pos(v) + if p.depth == 0 { + p.parent = parent + p.depth = depth + heap.Push(d, p) + } +} + +func (d *dijkstra) empty() bool { + return len(d.q) == 0 +} + +func (d *dijkstra) next() *dpos { + return heap.Pop(d).(*dpos) +} + +// Implementation of heap.Interface +func (d *dijkstra) Len() int { + return len(d.q) +} + +func (d *dijkstra) Less(i, j int) bool { + return d.q[i].depth < d.q[j].depth +} + +func (d *dijkstra) Swap(i, j int) { + d.q[i], d.q[j] = d.q[j], d.q[i] + d.q[i].heapIndex = i + d.q[j].heapIndex = j +} + +func (d *dijkstra) Push(x interface{}) { + p := x.(*dpos) + p.heapIndex = len(d.q) + d.q = append(d.q, p) +} + +func (d *dijkstra) Pop() interface{} { + n := len(d.q) + x := d.q[n-1] + d.q = d.q[:n-1] + x.heapIndex = -1 + return x +} diff --git a/vendor/github.com/mattermost/rsc/rosetta/maze/Makefile b/vendor/github.com/mattermost/rsc/rosetta/maze/Makefile new file mode 100644 index 000000000..8a83abd05 --- /dev/null +++ b/vendor/github.com/mattermost/rsc/rosetta/maze/Makefile @@ -0,0 +1,8 @@ +include $(GOROOT)/src/Make.inc + +TARG=maze +GOFILES=\ + maze.go\ + +include $(GOROOT)/src/Make.cmd + diff --git a/vendor/github.com/mattermost/rsc/rosetta/maze/maze.go b/vendor/github.com/mattermost/rsc/rosetta/maze/maze.go new file mode 100644 index 000000000..3cd15d04f --- /dev/null +++ b/vendor/github.com/mattermost/rsc/rosetta/maze/maze.go @@ -0,0 +1,191 @@ +// Copyright 2011 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. + +// Rosetta Code-inspired maze generator and solver. +// Demonstrates use of interfaces to separate algorithm +// implementations (graph.ShortestPath, heap.*) from data. +// (In contrast, multiple inheritance approaches require +// you to store their data in your data structures as part +// of the inheritance.) + +package main + +import ( + "bytes" + "fmt" + "math/rand" + "time" + + "github.com/mattermost/rsc/rosetta/graph" +) + +type Maze struct { + w, h int + grid [][]walls +} + +type Dir uint + +const ( + North Dir = iota + East + West + South +) + +type walls uint8 + +const allWalls walls = 1<<North | 1<<East | 1<<South | 1<<West + +var dirs = []struct { + δx, δy int +}{ + {0, -1}, + {1, 0}, + {-1, 0}, + {0, 1}, +} + +// move returns the cell in the direction dir from position r, c. +// It returns ok==false if there is no cell in that direction. +func (m *Maze) move(x, y int, dir Dir) (nx, ny int, ok bool) { + nx = x + dirs[dir].δx + ny = y + dirs[dir].δy + ok = 0 <= nx && nx < m.w && 0 <= ny && ny < m.h + return +} + +// Move returns the cell in the direction dir from position x, y +// It returns ok==false if there is no cell in that direction +// or if a wall blocks movement in that direction. +func (m *Maze) Move(x, y int, dir Dir) (nx, ny int, ok bool) { + nx, ny, ok = m.move(x, y, dir) + ok = ok && m.grid[y][x]&(1<<dir) == 0 + return +} + +// NewMaze returns a new, randomly generated maze +// of width w and height h. +func NewMaze(w, h int) *Maze { + // Allocate one slice for the whole 2-d cell grid and break up into rows. + all := make([]walls, w*h) + for i := range all { + all[i] = allWalls + } + m := &Maze{w: w, h: h, grid: make([][]walls, h)} + for i := range m.grid { + m.grid[i], all = all[:w], all[w:] + } + + // All cells start with all walls. + m.generate(rand.Intn(w), rand.Intn(h)) + + return m +} + +func (m *Maze) generate(x, y int) { + i := rand.Intn(4) + for j := 0; j < 4; j++ { + dir := Dir(i+j) % 4 + if nx, ny, ok := m.move(x, y, dir); ok && m.grid[ny][nx] == allWalls { + // break down wall + m.grid[y][x] &^= 1 << dir + m.grid[ny][nx] &^= 1 << (3 - dir) + m.generate(nx, ny) + } + } +} + +// String returns a multi-line string representation of the maze. +func (m *Maze) String() string { + return m.PathString(nil) +} + +// PathString returns the multi-line string representation of the +// maze with the path marked on it. +func (m *Maze) PathString(path []graph.Vertex) string { + var b bytes.Buffer + wall := func(w, m walls, ch byte) { + if w&m != 0 { + b.WriteByte(ch) + } else { + b.WriteByte(' ') + } + } + for _, row := range m.grid { + b.WriteByte('+') + for _, cell := range row { + wall(cell, 1<<North, '-') + b.WriteByte('+') + } + b.WriteString("\n") + for _, cell := range row { + wall(cell, 1<<West, '|') + b.WriteByte(' ') + } + b.WriteString("|\n") + } + for i := 0; i < m.w; i++ { + b.WriteString("++") + } + b.WriteString("+") + grid := b.Bytes() + + // Overlay path. + last := -1 + for _, v := range path { + p := v.(pos) + i := (2*m.w+2)*(2*p.y+1) + 2*p.x + 1 + grid[i] = '#' + if last != -1 { + grid[(i+last)/2] = '#' + } + last = i + } + + return string(grid) +} + +// Implement graph.Graph. + +type pos struct { + x, y int +} + +func (p pos) String() string { + return fmt.Sprintf("%d,%d", p.x, p.y) +} + +func (m *Maze) Neighbors(v graph.Vertex) []graph.Vertex { + p := v.(pos) + var neighbors []graph.Vertex + for dir := North; dir <= South; dir++ { + if nx, ny, ok := m.Move(p.x, p.y, dir); ok { + neighbors = append(neighbors, pos{nx, ny}) + } + } + return neighbors +} + +func (m *Maze) NumVertex() int { + return m.w * m.h +} + +func (m *Maze) VertexID(v graph.Vertex) int { + p := v.(pos) + return p.y*m.w + p.x +} + +func (m *Maze) Vertex(x, y int) graph.Vertex { + return pos{x, y} +} + +func main() { + const w, h = 30, 10 + rand.Seed(time.Now().UnixNano()) + + m := NewMaze(w, h) + path := graph.ShortestPath(m, m.Vertex(0, 0), m.Vertex(w-1, h-1)) + fmt.Println(m.PathString(path)) +} |