edgeholder.go 2.9 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123
  1. package simple
  2. import "k8s.io/kubernetes/third_party/forked/gonum/graph"
  3. // edgeHolder represents a set of edges, with no more than one edge to or from a particular neighbor node
  4. type edgeHolder interface {
  5. // Visit invokes visitor with each edge and the id of the neighbor node in the edge
  6. Visit(visitor func(neighbor int, edge graph.Edge))
  7. // Delete removes edges to or from the specified neighbor
  8. Delete(neighbor int) edgeHolder
  9. // Set stores the edge to or from the specified neighbor
  10. Set(neighbor int, edge graph.Edge) edgeHolder
  11. // Get returns the edge to or from the specified neighbor
  12. Get(neighbor int) (graph.Edge, bool)
  13. // Len returns the number of edges
  14. Len() int
  15. }
  16. // sliceEdgeHolder holds a list of edges to or from self
  17. type sliceEdgeHolder struct {
  18. self int
  19. edges []graph.Edge
  20. }
  21. func (e *sliceEdgeHolder) Visit(visitor func(neighbor int, edge graph.Edge)) {
  22. for _, edge := range e.edges {
  23. if edge.From().ID() == e.self {
  24. visitor(edge.To().ID(), edge)
  25. } else {
  26. visitor(edge.From().ID(), edge)
  27. }
  28. }
  29. }
  30. func (e *sliceEdgeHolder) Delete(neighbor int) edgeHolder {
  31. edges := e.edges[:0]
  32. for i, edge := range e.edges {
  33. if edge.From().ID() == e.self {
  34. if edge.To().ID() == neighbor {
  35. continue
  36. }
  37. } else {
  38. if edge.From().ID() == neighbor {
  39. continue
  40. }
  41. }
  42. edges = append(edges, e.edges[i])
  43. }
  44. e.edges = edges
  45. return e
  46. }
  47. func (e *sliceEdgeHolder) Set(neighbor int, newEdge graph.Edge) edgeHolder {
  48. for i, edge := range e.edges {
  49. if edge.From().ID() == e.self {
  50. if edge.To().ID() == neighbor {
  51. e.edges[i] = newEdge
  52. return e
  53. }
  54. } else {
  55. if edge.From().ID() == neighbor {
  56. e.edges[i] = newEdge
  57. return e
  58. }
  59. }
  60. }
  61. if len(e.edges) < 4 {
  62. e.edges = append(e.edges, newEdge)
  63. return e
  64. }
  65. h := mapEdgeHolder(make(map[int]graph.Edge, len(e.edges)+1))
  66. for i, edge := range e.edges {
  67. if edge.From().ID() == e.self {
  68. h[edge.To().ID()] = e.edges[i]
  69. } else {
  70. h[edge.From().ID()] = e.edges[i]
  71. }
  72. }
  73. h[neighbor] = newEdge
  74. return h
  75. }
  76. func (e *sliceEdgeHolder) Get(neighbor int) (graph.Edge, bool) {
  77. for _, edge := range e.edges {
  78. if edge.From().ID() == e.self {
  79. if edge.To().ID() == neighbor {
  80. return edge, true
  81. }
  82. } else {
  83. if edge.From().ID() == neighbor {
  84. return edge, true
  85. }
  86. }
  87. }
  88. return nil, false
  89. }
  90. func (e *sliceEdgeHolder) Len() int {
  91. return len(e.edges)
  92. }
  93. // mapEdgeHolder holds a map of neighbors to edges
  94. type mapEdgeHolder map[int]graph.Edge
  95. func (e mapEdgeHolder) Visit(visitor func(neighbor int, edge graph.Edge)) {
  96. for neighbor, edge := range e {
  97. visitor(neighbor, edge)
  98. }
  99. }
  100. func (e mapEdgeHolder) Delete(neighbor int) edgeHolder {
  101. delete(e, neighbor)
  102. return e
  103. }
  104. func (e mapEdgeHolder) Set(neighbor int, edge graph.Edge) edgeHolder {
  105. e[neighbor] = edge
  106. return e
  107. }
  108. func (e mapEdgeHolder) Get(neighbor int) (graph.Edge, bool) {
  109. edge, ok := e[neighbor]
  110. return edge, ok
  111. }
  112. func (e mapEdgeHolder) Len() int {
  113. return len(e)
  114. }