PriorityQueue.go

// SPDX-License-Identifier: MIT
// Copyright (c) 2026 MaIII Themd

package dijkstra

import "fmt"

// StPriorityQueueData is one entry in the priority queue used by the
// Dijkstra relaxation pass: an edge (fromVertex -> toVertex) together
// with the cumulative cost to reach toVertex via that edge.
type StPriorityQueueData struct {
	fromVertex string
	toVertex   string
	weight     float64
	seq        uint64 // insertion order, for stable tie-breaking
}

// StPriorityQueue is an ascending-by-weight priority queue of
// StPriorityQueueData implemented as a binary min-heap, so EnQueue and
// DeQueue are O(log n). Entries with equal weight are dequeued in
// insertion order (FIFO within an equivalence class).
type StPriorityQueue struct {
	q   []StPriorityQueueData
	seq uint64
}

// less reports whether entry i should be dequeued before entry j: lower
// weight first, ties broken by insertion order.
func (pq *StPriorityQueue) less(i, j int) bool {
	if pq.q[i].weight != pq.q[j].weight {
		return pq.q[i].weight < pq.q[j].weight
	}
	return pq.q[i].seq < pq.q[j].seq
}

// Print writes the queue's contents to stdout in heap-array order.
func (pq *StPriorityQueue) Print() {
	fmt.Printf("Priority Queue : ")
	for _, pqd := range pq.q {
		fmt.Printf("(%s,%s,%1.2f), ", pqd.fromVertex, pqd.toVertex, pqd.weight)
	}
	fmt.Printf("\r\n")
}

// EnQueue inserts a new entry in O(log n).
func (pq *StPriorityQueue) EnQueue(fromVertex string, toVertex string, weight float64) {
	pq.q = append(pq.q, StPriorityQueueData{
		fromVertex: fromVertex,
		toVertex:   toVertex,
		weight:     weight,
		seq:        pq.seq,
	})
	pq.seq++
	pq.up(len(pq.q) - 1)
}

// DeQueue removes and returns the lowest-weight entry in O(log n).
// Returns (false, zero-value) if the queue is empty.
func (pq *StPriorityQueue) DeQueue() (bool, StPriorityQueueData) {
	n := len(pq.q)
	if n == 0 {
		return false, StPriorityQueueData{}
	}
	top := pq.q[0]
	last := n - 1
	pq.q[0] = pq.q[last]
	pq.q[last] = StPriorityQueueData{} // drop the moved-out copy so GC can reclaim its strings
	pq.q = pq.q[:last]
	if last > 0 {
		pq.down(0)
	}
	return true, top
}

// Head returns the lowest-weight entry without removing it.
// Returns (false, zero-value) if the queue is empty.
func (pq *StPriorityQueue) Head() (bool, StPriorityQueueData) {
	if len(pq.q) == 0 {
		return false, StPriorityQueueData{}
	}
	return true, pq.q[0]
}

// Len returns the number of entries currently in the queue.
func (pq *StPriorityQueue) Len() int { return len(pq.q) }

// Clear empties the queue.
func (pq *StPriorityQueue) Clear() {
	pq.q = nil
	pq.seq = 0
}

// NotEmpty is the negation of empty; convenient as a loop predicate.
func (pq *StPriorityQueue) NotEmpty() bool { return len(pq.q) > 0 }

// up restores the heap invariant by sifting element i towards the root.
func (pq *StPriorityQueue) up(i int) {
	for i > 0 {
		parent := (i - 1) / 2
		if !pq.less(i, parent) {
			break
		}
		pq.q[i], pq.q[parent] = pq.q[parent], pq.q[i]
		i = parent
	}
}

// down restores the heap invariant by sifting element i towards the leaves.
func (pq *StPriorityQueue) down(i int) {
	n := len(pq.q)
	for {
		left := 2*i + 1
		if left >= n {
			break
		}
		smallest := left
		if right := left + 1; right < n && pq.less(right, left) {
			smallest = right
		}
		if !pq.less(smallest, i) {
			break
		}
		pq.q[i], pq.q[smallest] = pq.q[smallest], pq.q[i]
		i = smallest
	}
}