package main
import "algo/metrics"
// This file is YOURS to fill in. The algorithm is in step 2; wgraph_test.go
// decides whether you got it right.
//
// The counter counts FRONTIER WORK — every comparison the queue makes while
// deciding what comes next. Not edges, not nodes. That is the quantity step 5
// compares between the two frontiers, and it is the one `transit` reports too.
// WEdge is lesson 14's edge with one field added: what it costs to use.
//
// Here the cost is DAYS BETWEEN BORROWS — how long a reader waited before
// picking up the next book. Lesson 14 treated every edge as one hop; now they
// are not interchangeable.
type WEdge struct {
To int32
Cost int32
}
// WGraph is lesson 14's Graph with weights. Everything else — the adjacency
// list, the trails, the shape — is unchanged.
type WGraph struct {
adj [][]WEdge
edges int
}
func NewWGraph(n int) *WGraph { panic("not implemented") }
func (g *WGraph) Nodes() int { panic("not implemented") }
func (g *WGraph) Edges() int { panic("not implemented") }
// AddEdge links a and b in both directions at the given cost, rejecting
// self-loops and duplicates as in lesson 14.
func (g *WGraph) AddEdge(a, b, cost int32) { panic("not implemented") }
func (g *WGraph) Neighbors(v int32) []WEdge { panic("not implemented") }
// NodeHeap is lesson 13's MinHeap with a different payload: it orders NODES by
// their tentative distance instead of items by Rating.
//
// The array-tree, the sift-up, the sift-down and the index arithmetic are the
// SAME CODE. Only what sits in the array changed — which is the point. Copy your
// heap across and change the payload; do not invent a second one.
//
// Two parallel slices rather than a slice of structs, so a swap touches two
// small arrays instead of copying a struct. Either works; this one is closer to
// what `transit` does.
type NodeHeap struct {
node []int32
dist []int32
}
func NewNodeHeap(capacity int) *NodeHeap { panic("not implemented") }
func (h *NodeHeap) Len() int { panic("not implemented") }
func (h *NodeHeap) Push(v, d int32, c *metrics.Counter) { panic("not implemented") }
// Pop returns the node with the smallest tentative distance.
func (h *NodeHeap) Pop(c *metrics.Counter) (node, dist int32, ok bool) {
panic("not implemented")
}
// DijkstraHeap finds the CHEAPEST path, using the heap as the frontier.
//
// USE LAZY DELETION: when a cheaper route to a node appears, push it again
// rather than trying to update the entry already in the heap. Skip an entry
// whose node is already done. Step 2 explains why, and a test checks that you
// did it this way — a version with no stale entries is doing decrease-key, which
// is a different structure.
//
// Returns the path, its cost, and how many nodes were settled.
func DijkstraHeap(g *WGraph, from, to int32, c *metrics.Counter) ([]int32, int32, int, bool) {
panic("not implemented")
}
// DijkstraScan is the same algorithm with no priority queue at all: to find the
// nearest unsettled node it looks at every node.
//
// It is CORRECT — the same path, the same cost. Do not "fix" it; step 5 is about
// what it costs, and a test requires both to agree.
func DijkstraScan(g *WGraph, from, to int32, c *metrics.Counter) ([]int32, int32, int, bool) {
panic("not implemented")
}
// PathCost adds up the weights along a path, so a hop-count answer and a cost
// answer can be compared on the same footing.
func (g *WGraph) PathCost(path []int32) int32 { panic("not implemented") }
// BFSW is lesson 14's BFS on the weighted graph. It still counts HOPS and still
// ignores the weights entirely — copy it across unchanged. Step 1 is what that
// costs.
func BFSW(g *WGraph, from, to int32, c *metrics.Counter) ([]int32, bool) {
panic("not implemented")
}
