Андон обнови решението на 26.01.2016 04:54 (преди над 2 години)
+package main
+
+import (
+ "encoding/json"
+ "fmt"
+ "net/http"
+ "sort"
+ "strconv"
+ "sync"
+)
+
+//begining of Game of Life implementation
+type Cell [2]int64
+
+type KdTree struct {
+ Node Cell
+ left *KdTree
+ right *KdTree
+}
+
+type Zone struct {
+ StartPoint Cell
+ Width int64
+ Height int64
+ AliveCells *KdTree
+}
+
+type CellX []Cell
+type CellY []Cell
+
+func min(i, j int) int {
+ if i > j {
+ return j
+ } else {
+ return i
+ }
+}
+
+func max(i, j int) int {
+ if i < j {
+ return j
+ } else {
+ return i
+ }
+}
+
+func abs(i int) int {
+ if i < 0 {
+ return -i
+ }
+
+ return i
+}
+
+func (cells CellX) Len() int {
+ return len(cells)
+}
+
+func (cells CellX) Less(i, j int) bool {
+
+ return cells[i][0] < cells[j][0]
+}
+
+func (cells CellX) Swap(i, j int) {
+ cells[i], cells[j] = cells[j], cells[i]
+}
+
+func (cells CellY) Len() int {
+ return len(cells)
+}
+
+func (cells CellY) Less(i, j int) bool {
+ return cells[i][1] < cells[j][1]
+}
+
+func (cells CellY) Swap(i, j int) {
+ cells[i], cells[j] = cells[j], cells[i]
+}
+
+func (tr *KdTree) Height() int {
+ if tr == nil {
+ return 0
+ }
+
+ var leftHeight int = tr.left.Height()
+
+ var rightHeight int = tr.right.Height()
+
+ return 1 + max(leftHeight, rightHeight)
+}
+
+func (tr *KdTree) IsInTree(c Cell, depth int) bool {
+ if tr == nil {
+ return false
+ }
+
+ if tr.Node == c {
+ return true
+ }
+
+ var goLeft bool
+ if depth%2 == 0 {
+ goLeft = c[0] < tr.Node[0]
+ } else {
+ goLeft = c[1] < tr.Node[1]
+ }
+
+ if goLeft {
+ return tr.left.IsInTree(c, depth+1)
+ } else {
+ return tr.right.IsInTree(c, depth+1)
+ }
+
+}
+
+func (tr *KdTree) Search(c Cell) bool {
+ if tr == nil {
+ return false
+ }
+
+ return tr.IsInTree(c, 0)
+}
+
+func GetMedian(cells []Cell, axis int) int {
+ var median int = len(cells) / 2
+
+ for i := median; i > 0; i-- {
+ if axis%2 == 0 {
+ if cells[i][0] > cells[i-1][0] {
+ return i
+ }
+ } else {
+ if cells[i][1] > cells[i-1][1] {
+ return i
+ }
+ }
+ }
+
+ return 0
+}
+
+func (tr *KdTree) ToCells() []Cell {
+ if tr == nil {
+ return make([]Cell, 0)
+ }
+
+ cells := append(tr.left.ToCells(), tr.Node)
+ if tr.right != nil {
+ rightCells := tr.right.ToCells()
+ cells = append(cells, rightCells...)
+ }
+
+ return cells
+}
+
+func (tr *KdTree) rebalance() {
+ if tr == nil {
+ return
+ }
+
+ t := MakeTree(tr.ToCells())
+ tr.Node = t.Node
+ tr.left = t.left
+ tr.right = t.right
+}
+
+func (tr *KdTree) recursiveAdd(c Cell, d int) {
+ if tr == nil {
+ return
+ }
+
+ var goLeft bool
+ if d%2 == 0 {
+ goLeft = c[0] < tr.Node[0]
+ } else {
+ goLeft = c[1] < tr.Node[1]
+ }
+
+ if goLeft {
+ if tr.left == nil {
+ tr.left = &KdTree{Node: c}
+ } else {
+ tr.left.recursiveAdd(c, d+1)
+ }
+ } else {
+ if tr.right == nil {
+ tr.right = &KdTree{Node: c}
+ } else {
+ tr.right.recursiveAdd(c, d+1)
+ }
+ }
+
+}
+
+func (tr *KdTree) Add(c Cell) {
+
+ tr.recursiveAdd(c, 0)
+
+ if abs(tr.left.Height()-tr.right.Height()) > 2 {
+ tr.rebalance()
+ }
+}
+
+func recursiveMakeTree(cells []Cell, d int) (tr *KdTree) {
+ if len(cells) == 0 {
+ tr = nil
+ return
+ }
+
+ if len(cells) == 1 {
+ tr = &KdTree{Node: cells[0], left: nil, right: nil}
+ return
+ }
+
+ var leftChan chan *KdTree = make(chan *KdTree)
+ var rightChan chan *KdTree = make(chan *KdTree)
+
+ if d%2 == 0 {
+ sort.Sort(CellX(cells))
+ } else {
+ sort.Sort(CellY(cells))
+ }
+
+ median := GetMedian(cells, d)
+
+ tr = &KdTree{Node: cells[median]}
+
+ go func() {
+ leftChan <- recursiveMakeTree(cells[:median], d+1)
+ }()
+
+ go func() {
+ rightChan <- recursiveMakeTree(cells[median+1:], d+1)
+ }()
+
+ tr.left = <-leftChan
+ tr.right = <-rightChan
+
+ return
+}
+
+func MakeTree(cells []Cell) *KdTree {
+ return recursiveMakeTree(cells, 0)
+}
+
+func NumberOfAliveNeighbours(c Cell, tr *KdTree) int {
+ var n int = 0
+ neighbours := []Cell{Cell{c[0] - 1, c[1] + 1}, Cell{c[0], c[1] + 1}, Cell{c[0] + 1, c[1] + 1}, Cell{c[0] - 1, c[1]}, Cell{c[0] + 1, c[1]}, Cell{c[0] - 1, c[1] - 1}, Cell{c[0], c[1] - 1}, Cell{c[0] + 1, c[1] - 1}}
+
+ for _, c := range neighbours {
+ if tr.Search(c) {
+ n++
+ }
+ }
+
+ return n
+}
+
+func shouldLive(c Cell, tr *KdTree) bool {
+ var aliveNeighbours int = NumberOfAliveNeighbours(c, tr)
+
+ return aliveNeighbours == 3
+}
+
+func shouldSurvive(c Cell, tr *KdTree) bool {
+ var aliveNeighbours int = NumberOfAliveNeighbours(c, tr)
+
+ return aliveNeighbours == 2 || aliveNeighbours == 3
+}
+
+func iterateAliveCells(aliveCells *KdTree) []Cell {
+ survivedCells := make([]Cell, 0)
+
+ var recursiveFunc func(tr *KdTree)
+ recursiveFunc = func(tr *KdTree) {
+ if tr == nil {
+ return
+ }
+
+ recursiveFunc(tr.left)
+ if shouldSurvive(tr.Node, aliveCells) {
+ survivedCells = append(survivedCells, tr.Node)
+ }
+
+ recursiveFunc(tr.right)
+ }
+
+ recursiveFunc(aliveCells)
+ return survivedCells
+}
+
+func iterateDeadCells(aliveCells *KdTree) []Cell {
+
+ cells := make(map[Cell]bool)
+ var recursiveInorder func(*KdTree)
+ recursiveInorder = func(tr *KdTree) {
+ if tr == nil {
+ return
+ }
+
+ if tr.left != nil {
+ recursiveInorder(tr.left)
+ }
+
+ neighbours := []Cell{
+ {tr.Node[0] - 1, tr.Node[1] + 1},
+ {tr.Node[0], tr.Node[1] + 1},
+ {tr.Node[0] + 1, tr.Node[1] + 1},
+ {tr.Node[0] - 1, tr.Node[1]},
+ {tr.Node[0] + 1, tr.Node[1]},
+ {tr.Node[0] - 1, tr.Node[1] - 1},
+ {tr.Node[0], tr.Node[1] - 1},
+ {tr.Node[0] + 1, tr.Node[1] - 1},
+ }
+
+ for _, n := range neighbours {
+ if !aliveCells.Search(n) {
+ _, exists := cells[n]
+ if shouldLive(n, aliveCells) && !exists {
+ cells[n] = true
+ }
+ }
+ }
+
+ if tr.right != nil {
+ recursiveInorder(tr.right)
+ }
+ }
+
+ recursiveInorder(aliveCells)
+
+ c := make([]Cell, 0)
+
+ for k, _ := range cells {
+ c = append(c, k)
+ }
+
+ return c
+}
+
+//End of game of life implementation
+
+//Server code
+type GameOfLifeHandler struct {
+ Generation int
+ Cells []Cell
+ aliveCells *KdTree
+ mux *http.ServeMux
+ cellsMutex sync.RWMutex
+}
+
+func (g *GameOfLifeHandler) ServeHTTP(w http.ResponseWriter, r *http.Request) {
+ g.mux.ServeHTTP(w, r)
+}
+
+func (g *GameOfLifeHandler) StatusHandle(w http.ResponseWriter, r *http.Request) {
+ if r.URL.Path != "/cell/status/" {
+ http.NotFound(w, r)
+ } else if r.Method == "GET" {
+ vals := r.URL.Query()
+ var c Cell
+ if i, err := strconv.ParseInt(vals["x"][0], 10, 64); err == nil {
+ c[0] = i
+ }
+
+ if i, err := strconv.ParseInt(vals["y"][0], 10, 64); err == nil {
+ c[1] = i
+ }
+
+ g.cellsMutex.RLock()
+ isAlive := g.aliveCells.Search(c)
+ g.cellsMutex.RUnlock()
+
+ type Status struct {
+ Alive bool `json:"alive"`
+ }
+
+ w.Header().Set("Content-Type", "application/javascript")
+
+ w.WriteHeader(200)
+
+ s := Status{isAlive}
+ encoder := json.NewEncoder(w)
+ if err := encoder.Encode(s); err != nil {
+ fmt.Println(err.Error())
+ }
+
+ } else {
+ http.Error(w, "Wrong method!", 405)
+ }
+}
+
+func (g *GameOfLifeHandler) GenerationHandle(w http.ResponseWriter, r *http.Request) {
+ if r.URL.Path != "/generation/" {
+ http.NotFound(w, r)
+ } else if r.Method == "GET" {
+ g.cellsMutex.RLock()
+ type GenerationJson struct {
+ Generation int `json:"generation"`
+ Living []Cell `json:"living"`
+ }
+
+ gen := GenerationJson{g.Generation, g.Cells}
+ g.cellsMutex.RUnlock()
+
+ w.WriteHeader(200)
+ w.Header().Set("Content-Type", "application/javascript")
+ json.NewEncoder(w).Encode(gen)
+ } else {
+ http.Error(w, "Wrong method!", 405)
+ }
+}
+
+func (g *GameOfLifeHandler) CellsHandle(w http.ResponseWriter, r *http.Request) {
+ if r.URL.Path != "/cells/" {
+ http.NotFound(w, r)
+ } else if r.Method == "POST" {
+ type JsonCell struct {
+ X int64 `json:"x"`
+ Y int64 `json:"y"`
+ }
+
+ var postCells []JsonCell
+ decoder := json.NewDecoder(r.Body)
+
+ if err := decoder.Decode(&postCells); err != nil {
+ http.Error(w, "Wrong json format", 400)
+ } else {
+ g.cellsMutex.Lock()
+ if g.Generation > 0 {
+ g.Generation++
+ }
+
+ newCells := make([]Cell, 0)
+ for _, jc := range postCells {
+ var c Cell = Cell{jc.X, jc.Y}
+ if !g.aliveCells.Search(c) {
+
+ newCells = append(newCells, c)
+ if g.aliveCells != nil {
+ g.aliveCells.Add(c)
+ } else {
+ g.aliveCells = new(KdTree)
+ g.aliveCells.Node = c
+ }
+ }
+ }
+
+ g.Cells = append(g.Cells, newCells...)
+
+ g.cellsMutex.Unlock()
+ w.WriteHeader(201)
+ }
+
+ } else {
+ http.Error(w, "Wrong method!", 405)
+ }
+}
+
+func (g *GameOfLifeHandler) EvolveHandle(w http.ResponseWriter, r *http.Request) {
+ if r.URL.Path != "/generation/evolve/" {
+ fmt.Println("Not found")
+ http.NotFound(w, r)
+ } else if r.Method == "POST" {
+ g.cellsMutex.Lock()
+ defer g.cellsMutex.Unlock()
+
+ g.Generation++
+
+ newCells := make([]Cell, 0)
+ newCells = append(newCells, iterateAliveCells(g.aliveCells)...)
+ newCells = append(newCells, iterateDeadCells(g.aliveCells)...)
+
+ g.Cells = newCells
+ g.aliveCells = MakeTree(g.Cells)
+
+ w.WriteHeader(204)
+ } else {
+ http.Error(w, "Wrong method!", 405)
+ }
+}
+
+func (g *GameOfLifeHandler) ResetHandle(w http.ResponseWriter, r *http.Request) {
+ if r.URL.Path != "/reset/" {
+ http.NotFound(w, r)
+ } else if r.Method == "POST" {
+ g.Generation = 0
+ g.Cells = make([]Cell, 0)
+ g.aliveCells = nil
+ w.WriteHeader(204)
+ } else {
+ http.Error(w, "Wrong method", 405)
+ }
+}
+
+func NewGameOfLifeHandler(cells [][2]int64) http.Handler {
+ gofh := new(GameOfLifeHandler)
+ gofh.Generation = 0
+ gofh.Cells = make([]Cell, 0)
+ for _, v := range cells {
+ gofh.Cells = append(gofh.Cells, Cell(v))
+ }
+ gofh.aliveCells = MakeTree(gofh.Cells)
+ gofh.mux = http.NewServeMux()
+ gofh.mux.HandleFunc("/cell/status/", gofh.StatusHandle)
+ gofh.mux.HandleFunc("/generation/", gofh.GenerationHandle)
+ gofh.mux.HandleFunc("/generation/evolve/", gofh.EvolveHandle)
+ gofh.mux.HandleFunc("/cells/", gofh.CellsHandle)
+ gofh.mux.HandleFunc("/reset/", gofh.ResetHandle)
+ gofh.mux.HandleFunc("/", func(w http.ResponseWriter, r *http.Request) {
+ fmt.Println("Default handler")
+ http.NotFound(w, r)
+ })
+
+ return gofh
+}
+
+//end of server code
Слагам ти допълнителна точка заради готиното балансирано дърво :) За много голямо количество клетки твоето решение има шанс да се държи най - добре.
Благодаря