edgeholder.go

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)
}