diff options
Diffstat (limited to 'vendor/github.com/mattermost/rsc/rosetta')
4 files changed, 0 insertions, 339 deletions
diff --git a/vendor/github.com/mattermost/rsc/rosetta/graph/Makefile b/vendor/github.com/mattermost/rsc/rosetta/graph/Makefile deleted file mode 100644 index 1cb49f788..000000000 --- a/vendor/github.com/mattermost/rsc/rosetta/graph/Makefile +++ /dev/null @@ -1,7 +0,0 @@ -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 deleted file mode 100644 index 359617d41..000000000 --- a/vendor/github.com/mattermost/rsc/rosetta/graph/graph.go +++ /dev/null @@ -1,133 +0,0 @@ -// 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 deleted file mode 100644 index 8a83abd05..000000000 --- a/vendor/github.com/mattermost/rsc/rosetta/maze/Makefile +++ /dev/null @@ -1,8 +0,0 @@ -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 deleted file mode 100644 index 3cd15d04f..000000000 --- a/vendor/github.com/mattermost/rsc/rosetta/maze/maze.go +++ /dev/null @@ -1,191 +0,0 @@ -// 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)) -} |