// RemoveEdge removes the edge between nodes identified by e.From and e.To and
// its adjacent faces from g.
func (g *Graph) RemoveEdge(e graph.Edge) {
	h := g.Halfedge(e.From(), e.To())
	if h == nil {
		// Nothing to do.
		return
	}

	// Remove any adjacent faces.
	if h.Face() != nil {
		g.RemoveFace(h.Face())
	}
	if h.Twin().Face() != nil {
		g.RemoveFace(h.Twin().Face())
	}

	// Detach both halfedges from their From nodes and update affected
	// halfedges.
	detach(h)
	detach(h.Twin())

	id := h.Edge().ID()
	delete(g.edges, id)
	if g.nextEdgeID != 0 && id == g.nextEdgeID {
		g.nextEdgeID--
	}
	g.freeEdges[id] = struct{}{}
}

func (g *TileGraph) Cost(e graph.Edge) float64 {
	if edge := g.EdgeBetween(e.Head(), e.Tail()); edge != nil {
		return 1
	}

	return inf
}

func (g *TileGraph) Weight(e graph.Edge) float64 {
	if edge := g.EdgeBetween(e.From(), e.To()); edge != nil {
		return 1
	}

	return inf
}

func (g *Graph) Cost(e graph.Edge) float64 {
	if n, ok := g.neighbors[e.Head().ID()]; ok {
		if we, ok := n[e.Tail().ID()]; ok {
			return we.Cost
		}
	}
	return inf
}

func (g *DirectedDenseGraph) SetEdgeWeight(e graph.Edge, weight float64) {
	fid := e.From().ID()
	tid := e.To().ID()
	if fid == tid {
		panic("concrete: set edge cost of illegal edge")
	}
	g.mat.Set(fid, tid, weight)
}

func (g *DirectedGraph) Weight(e graph.Edge) float64 {
	if s, ok := g.successors[e.From().ID()]; ok {
		if we, ok := s[e.To().ID()]; ok {
			return we.Cost
		}
	}
	return inf
}

func (g *DirectedGraph) Cost(e graph.Edge) float64 {
	if s, ok := g.successors[e.Head().ID()]; ok {
		if we, ok := s[e.Tail().ID()]; ok {
			return we.Cost
		}
	}
	return inf
}

func (g *Graph) Weight(e graph.Edge) float64 {
	if n, ok := g.neighbors[e.From().ID()]; ok {
		if we, ok := n[e.To().ID()]; ok {
			return we.Cost
		}
	}
	return inf
}

func (g *Graph) RemoveUndirectedEdge(e graph.Edge) {
	head, tail := e.Head(), e.Tail()
	if _, ok := g.nodeMap[head.ID()]; !ok {
		return
	} else if _, ok := g.nodeMap[tail.ID()]; !ok {
		return
	}

	delete(g.neighbors[head.ID()], tail.ID())
	delete(g.neighbors[tail.ID()], head.ID())
}

func (g *UndirectedGraph) RemoveEdge(e graph.Edge) {
	from, to := e.From(), e.To()
	if _, ok := g.nodeMap[from.ID()]; !ok {
		return
	} else if _, ok := g.nodeMap[to.ID()]; !ok {
		return
	}

	delete(g.neighbors[from.ID()], to.ID())
	delete(g.neighbors[to.ID()], from.ID())
}

// RemoveEdge removes e from the graph, leaving the terminal nodes. If the edge does not exist
// it is a no-op.
func (g *DirectedMatrix) RemoveEdge(e graph.Edge) {
	fid := e.From().ID()
	if !g.has(fid) {
		return
	}
	tid := e.To().ID()
	if !g.has(tid) {
		return
	}
	g.mat.Set(fid, tid, g.absent)
}

func (g *DirectedGraph) RemoveDirectedEdge(e graph.Edge) {
	head, tail := e.Head(), e.Tail()
	if _, ok := g.nodeMap[head.ID()]; !ok {
		return
	} else if _, ok := g.nodeMap[tail.ID()]; !ok {
		return
	}

	delete(g.successors[head.ID()], tail.ID())
	delete(g.predecessors[tail.ID()], head.ID())
}

// RemoveEdge removes e from the graph, leaving the terminal nodes. If the edge does not exist
// it is a no-op.
func (g *DirectedGraph) RemoveEdge(e graph.Edge) {
	from, to := e.From(), e.To()
	if _, ok := g.nodes[from.ID()]; !ok {
		return
	}
	if _, ok := g.nodes[to.ID()]; !ok {
		return
	}

	delete(g.from[from.ID()], to.ID())
	delete(g.to[to.ID()], from.ID())
}

func (g *Graph) AddUndirectedEdge(e graph.Edge, cost float64) {
	head, tail := e.Head(), e.Tail()
	if !g.NodeExists(head) {
		g.AddNode(head)
	}

	if !g.NodeExists(tail) {
		g.AddNode(tail)
	}

	g.neighbors[head.ID()][tail.ID()] = WeightedEdge{Edge: e, Cost: cost}
	g.neighbors[tail.ID()][head.ID()] = WeightedEdge{Edge: e, Cost: cost}
}

func (g *gnDirected) SetEdge(e graph.Edge) {
	switch {
	case e.From().ID() == e.To().ID():
		g.addSelfLoop = true
		return
	case g.DirectedBuilder.HasEdgeFromTo(e.From(), e.To()):
		g.addMultipleEdge = true
	}

	g.DirectedBuilder.SetEdge(e)
}

// Weight returns the weight of the given edge.
func (g *Grid) Weight(e graph.Edge) float64 {
	if e := g.EdgeBetween(e.From(), e.To()); e != nil {
		if !g.AllowDiagonal {
			return 1
		}
		ux, uy := g.XY(e.From())
		vx, vy := g.XY(e.To())
		return math.Hypot(ux-vx, uy-vy)

	}
	return math.Inf(1)
}

// SetEdge adds e, an edge from one node to another. If the nodes do not exist, they are added.
// It will panic if the IDs of the e.From and e.To are equal.
func (g *UndirectedGraph) SetEdge(e graph.Edge) {
	var (
		from = e.From()
		fid  = from.ID()
		to   = e.To()
		tid  = to.ID()
	)

	if fid == tid {
		panic("simple: adding self edge")
	}

	if !g.Has(from) {
		g.AddNode(from)
	}
	if !g.Has(to) {
		g.AddNode(to)
	}

	g.edges[fid][tid] = e
	g.edges[tid][fid] = e
}

func (g *UndirectedDenseGraph) SetEdgeWeight(e graph.Edge) {
	fid := e.From().ID()
	tid := e.To().ID()
	if fid == tid {
		panic("concrete: set edge cost of illegal edge")
	}
	g.mat.SetSym(fid, tid, e.Weight())
}

// SetEdge sets e, an edge from one node to another. If the ends of the edge are not in g
// or the edge is a self loop, SetEdge panics.
func (g *DirectedMatrix) SetEdge(e graph.Edge) {
	fid := e.From().ID()
	tid := e.To().ID()
	if fid == tid {
		panic("simple: set illegal edge")
	}
	g.mat.Set(fid, tid, e.Weight())
}

func (g *DirectedGraph) SetEdge(e graph.Edge, cost float64) {
	var (
		from = e.From()
		fid  = from.ID()
		to   = e.To()
		tid  = to.ID()
	)

	if fid == tid {
		panic("concrete: adding self edge")
	}

	if !g.Has(from) {
		g.AddNode(from)
	}

	if !g.Has(to) {
		g.AddNode(to)
	}

	g.successors[fid][tid] = WeightedEdge{Edge: e, Cost: cost}
	g.predecessors[tid][fid] = WeightedEdge{Edge: e, Cost: cost}
}