SHARE
TWEET

Untitled

a guest Oct 17th, 2019 79 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. package main
  2.  
  3. import (
  4.     "container/heap"
  5.     "fmt"
  6.     "math"
  7.     "strconv"
  8.  
  9.     //"math"
  10.     "sync"
  11.     //"github.com/cheekybits/genny/generic"
  12. )
  13.  
  14. // Node a single node that composes the tree
  15. type Node struct {
  16.     Value Coordinate
  17. }
  18.  
  19. func CreateNode(coords Coordinate) Node {
  20.     var hash = strconv.FormatFloat(coords[0], 'f', -1, 64)
  21.     hash += strconv.FormatFloat(coords[1], 'f', -1, 64)
  22.     return Node{coords}
  23. }
  24.  
  25. func (n *Node) String() string {
  26.     return fmt.Sprintf("%v", n.Value)
  27. }
  28.  
  29. type Graph struct {
  30.     nodes []*Node
  31.     edges map[Node][]*Node
  32.     lock  sync.RWMutex
  33. }
  34.  
  35. // AddNode adds a node to the graph
  36. func (g *Graph) AddNode(n *Node) {
  37.     g.lock.Lock()
  38.     g.nodes = append(g.nodes, n)
  39.     g.lock.Unlock()
  40. }
  41.  
  42. // AddEdge adds an edge to the graph
  43. func (g *Graph) AddEdge(n1, n2 *Node) {
  44.     g.lock.Lock()
  45.     if g.edges == nil {
  46.         g.edges = make(map[Node][]*Node)
  47.     }
  48.     g.edges[*n1] = append(g.edges[*n1], n2)
  49.     g.edges[*n2] = append(g.edges[*n2], n1)
  50.     g.lock.Unlock()
  51. }
  52.  
  53. // Print graph
  54. func (g *Graph) String() {
  55.     g.lock.RLock()
  56.     s := ""
  57.     for i := 0; i < len(g.nodes); i++ {
  58.         s += g.nodes[i].String() + " -> "
  59.         near := g.edges[*g.nodes[i]]
  60.         for j := 0; j < len(near); j++ {
  61.             s += near[j].String() + " "
  62.         }
  63.         s += "\n"
  64.     }
  65.     fmt.Println(s)
  66.     g.lock.RUnlock()
  67. }
  68.  
  69. type QueueItem struct {
  70.     Node Node
  71.     Path []Node
  72. }
  73.  
  74. type NodeQueue struct {
  75.     items []QueueItem
  76.     lock  sync.RWMutex
  77. }
  78.  
  79. // New creates a new NodeQueue
  80. func (s *NodeQueue) New() *NodeQueue {
  81.     s.lock.Lock()
  82.     s.items = []QueueItem{}
  83.     s.lock.Unlock()
  84.     return s
  85. }
  86.  
  87. // Enqueue adds an Node to the end of the queue
  88. func (s *NodeQueue) Enqueue(t QueueItem) {
  89.     s.lock.Lock()
  90.     s.items = append(s.items, t)
  91.     s.lock.Unlock()
  92. }
  93.  
  94. // Dequeue removes an Node from the start of the queue
  95. func (s *NodeQueue) Dequeue() *QueueItem {
  96.     s.lock.Lock()
  97.     item := s.items[0]
  98.     s.items = s.items[1:len(s.items)]
  99.     s.lock.Unlock()
  100.     return &item
  101. }
  102.  
  103. // Front returns the item next in the queue, without removing it
  104. func (s *NodeQueue) Front() *QueueItem {
  105.     s.lock.RLock()
  106.     item := s.items[0]
  107.     s.lock.RUnlock()
  108.     return &item
  109. }
  110.  
  111. // IsEmpty returns true if the queue is empty
  112. func (s *NodeQueue) IsEmpty() bool {
  113.     s.lock.RLock()
  114.     defer s.lock.RUnlock()
  115.     return len(s.items) == 0
  116. }
  117.  
  118. // Size returns the number of Nodes in the queue
  119. func (s *NodeQueue) Size() int {
  120.     s.lock.RLock()
  121.     defer s.lock.RUnlock()
  122.     return len(s.items)
  123. }
  124.  
  125. func (g *Graph) FindNode(coords Coordinate) int {
  126.     nodes := g.nodes
  127.     //min distance
  128.     var foundNodeIndex int
  129.     var minDistance float64
  130.     //index of node
  131.     // Probably there is a better algo for this, just doing the brute force sorry :(
  132.     for i := 0; i < len(nodes); i++ {
  133.         //calc distance
  134.         value := nodes[i].Value
  135.         dx := coords[0] - value[0]
  136.         dy := coords[1] - value[1]
  137.         distance := math.Sqrt(dx*dx + dy*dy)
  138.         if i == 0 || distance < minDistance {
  139.             foundNodeIndex = i
  140.             minDistance = distance
  141.         }
  142.     }
  143.     return foundNodeIndex
  144. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top