123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123 |
- package simple
- import "k8s.io/kubernetes/third_party/forked/gonum/graph"
- // edgeHolder represents a set of edges, with no more than one edge to or from a particular neighbor node
- type edgeHolder interface {
- // Visit invokes visitor with each edge and the id of the neighbor node in the edge
- Visit(visitor func(neighbor int, edge graph.Edge))
- // Delete removes edges to or from the specified neighbor
- Delete(neighbor int) edgeHolder
- // Set stores the edge to or from the specified neighbor
- Set(neighbor int, edge graph.Edge) edgeHolder
- // Get returns the edge to or from the specified neighbor
- Get(neighbor int) (graph.Edge, bool)
- // Len returns the number of edges
- Len() int
- }
- // sliceEdgeHolder holds a list of edges to or from self
- type sliceEdgeHolder struct {
- self int
- edges []graph.Edge
- }
- func (e *sliceEdgeHolder) Visit(visitor func(neighbor int, edge graph.Edge)) {
- for _, edge := range e.edges {
- if edge.From().ID() == e.self {
- visitor(edge.To().ID(), edge)
- } else {
- visitor(edge.From().ID(), edge)
- }
- }
- }
- func (e *sliceEdgeHolder) Delete(neighbor int) edgeHolder {
- edges := e.edges[:0]
- for i, edge := range e.edges {
- if edge.From().ID() == e.self {
- if edge.To().ID() == neighbor {
- continue
- }
- } else {
- if edge.From().ID() == neighbor {
- continue
- }
- }
- edges = append(edges, e.edges[i])
- }
- e.edges = edges
- return e
- }
- func (e *sliceEdgeHolder) Set(neighbor int, newEdge graph.Edge) edgeHolder {
- for i, edge := range e.edges {
- if edge.From().ID() == e.self {
- if edge.To().ID() == neighbor {
- e.edges[i] = newEdge
- return e
- }
- } else {
- if edge.From().ID() == neighbor {
- e.edges[i] = newEdge
- return e
- }
- }
- }
- if len(e.edges) < 4 {
- e.edges = append(e.edges, newEdge)
- return e
- }
- h := mapEdgeHolder(make(map[int]graph.Edge, len(e.edges)+1))
- for i, edge := range e.edges {
- if edge.From().ID() == e.self {
- h[edge.To().ID()] = e.edges[i]
- } else {
- h[edge.From().ID()] = e.edges[i]
- }
- }
- h[neighbor] = newEdge
- return h
- }
- func (e *sliceEdgeHolder) Get(neighbor int) (graph.Edge, bool) {
- for _, edge := range e.edges {
- if edge.From().ID() == e.self {
- if edge.To().ID() == neighbor {
- return edge, true
- }
- } else {
- if edge.From().ID() == neighbor {
- return edge, true
- }
- }
- }
- return nil, false
- }
- func (e *sliceEdgeHolder) Len() int {
- return len(e.edges)
- }
- // mapEdgeHolder holds a map of neighbors to edges
- type mapEdgeHolder map[int]graph.Edge
- func (e mapEdgeHolder) Visit(visitor func(neighbor int, edge graph.Edge)) {
- for neighbor, edge := range e {
- visitor(neighbor, edge)
- }
- }
- func (e mapEdgeHolder) Delete(neighbor int) edgeHolder {
- delete(e, neighbor)
- return e
- }
- func (e mapEdgeHolder) Set(neighbor int, edge graph.Edge) edgeHolder {
- e[neighbor] = edge
- return e
- }
- func (e mapEdgeHolder) Get(neighbor int) (graph.Edge, bool) {
- edge, ok := e[neighbor]
- return edge, ok
- }
- func (e mapEdgeHolder) Len() int {
- return len(e)
- }
|