kpq

Documentation

Overview

Package kpq provides a generic keyed priority queue implementation.

A keyed priority queue is a data structure that allows you to associate keys with priority values and efficiently retrieve, update, and remove elements based on their priorities. This package offers concurrent-safe operations that leverages a binary heap to maintain the priority queue. Operations like Push, Pop, Update and Remove have O(log n) time complexity, where n is the size of the priority queue. The use of a map ensures fast lookups by key. Operations like Peek, Contains and ValueOf have O(1) time complexity.

Example

package main

import (
	"fmt"
	"log"

	"github.com/rdleal/go-priorityq/kpq"
)

func main() {
	// Create a new KeyedPriorityQueue with a custom comparison function
	cmp := func(a, b int) bool {
		return a < b
	}
	pq := kpq.NewKeyedPriorityQueue[string](cmp)

	// Insert elements onto the priority queue
	pq.Push("key1", 42)
	pq.Push("key2", 30)
	pq.Push("key3", 50)

	// Remove and retrieve the element with the highest priority
	key, value, ok := pq.Pop()
	if !ok {
		log.Fatal("priority queue is empty")
	}

	fmt.Printf("Key: %q, Value: %d\n", key, value)

	// Update the priority value of an element
	if err := pq.Update("key3", 20); err != nil {
		log.Fatalf("got unexpected error: %v\n", err)
	}

	// Remove an element from the priority queue
	pq.Remove("key1")

	// Check if a key exists in the priority queue
	exists := pq.Contains("key3")

	fmt.Println("Key 'key3' exists:", exists)
}

Output:

Key: "key2", Value: 30
Key 'key3' exists: true

Index

• type CmpFunc
• type KeyAlreadyExistsError
  • func (e KeyAlreadyExistsError) Error() string
  • func (e KeyAlreadyExistsError) Key() K
• type KeyNotFoundError
  • func (e KeyNotFoundError) Error() string
  • func (e KeyNotFoundError) Key() K
• type KeyedPriorityQueue
  • func NewKeyedPriorityQueue[K comparable, V any](cmp CmpFunc[V]) *KeyedPriorityQueue[K, V]
  • func (pq *KeyedPriorityQueue[K, V]) Contains(k K) bool
  • func (pq *KeyedPriorityQueue[K, V]) IsEmpty() bool
  • func (pq *KeyedPriorityQueue[K, V]) Len() int
  • func (pq *KeyedPriorityQueue[K, V]) Peek() (K, V, bool)
  • func (pq *KeyedPriorityQueue[K, V]) PeekKey() (K, bool)
  • func (pq *KeyedPriorityQueue[K, V]) PeekValue() (V, bool)
  • func (pq *KeyedPriorityQueue[K, V]) Pop() (K, V, bool)
  • func (pq *KeyedPriorityQueue[K, V]) Push(k K, v V) error
  • func (pq *KeyedPriorityQueue[K, V]) Remove(k K)
  • func (pq *KeyedPriorityQueue[K, V]) Set(k K, v V)
  • func (pq *KeyedPriorityQueue[K, V]) Update(k K, v V) error
  • func (pq *KeyedPriorityQueue[K, V]) ValueOf(k K) (V, bool)

Examples

• Package
• KeyAlreadyExistsError
• KeyedPriorityQueue.Set

Types

type CmpFunc

type CmpFunc[V any] func(x, y V) bool

CmpFunc is a generic function type used for ordering the priority queue.

type KeyAlreadyExistsError

type KeyAlreadyExistsError[K comparable] struct {
	// contains filtered or unexported fields
}

KeyAlreadyExistsError represents an error from calling a Push method with a key that already exists in the priority queue.

Example

package main

import (
	"errors"
	"fmt"

	"github.com/rdleal/go-priorityq/kpq"
)

func main() {
	pq := kpq.NewKeyedPriorityQueue[string](func(a, b int) bool {
		return a > b // max priority queue
	})

	key := "key1"
	pq.Push(key, 10)
	err := pq.Push(key, 20) // pushing the same key should return an error
	if err != nil {
		var keyErr kpq.KeyAlreadyExistsError[string]
		if errors.As(err, &keyErr) {
			fmt.Println(keyErr.Key() == key)
		}
	}
}

Output:

true

func (KeyAlreadyExistsError) Error

func (e KeyAlreadyExistsError) Error() string

Error returns the textual description of an error.

func (KeyAlreadyExistsError) Key

func (e KeyAlreadyExistsError) Key() K

Key returns the key that caused the error.

type KeyNotFoundError

type KeyNotFoundError[K comparable] struct {
	// contains filtered or unexported fields
}

KeyNotFoundError represents an error from calling Update method with a key that doesn't exist in the priority queue.

func (KeyNotFoundError) Error

func (e KeyNotFoundError) Error() string

Error returns the textual description of an error.

func (KeyNotFoundError) Key

func (e KeyNotFoundError) Key() K

Key returns the key that caused the error.

type KeyedPriorityQueue

type KeyedPriorityQueue[K comparable, V any] struct {
	// contains filtered or unexported fields
}

KeyedPriorityQueue represents a generic keyed priority queue, where K is the key type and V is the priority value type.

KeyedPriorityQueue must not be copied after first use.

func NewKeyedPriorityQueue

func NewKeyedPriorityQueue[K comparable, V any](cmp CmpFunc[V]) *KeyedPriorityQueue[K, V]

NewKeyedPriorityQueue returns a new keyed priority queue that uses the given cmp function for ordering the priority queue.

NewKeyedPriorityQueue will panic if cmp is nil.

func (*KeyedPriorityQueue[K, V]) Contains

func (pq *KeyedPriorityQueue[K, V]) Contains(k K) bool

Contains returns true if the given key k exists in the priority queue; otherwise, false.

func (*KeyedPriorityQueue[K, V]) IsEmpty

func (pq *KeyedPriorityQueue[K, V]) IsEmpty() bool

IsEmpty returns true if the priority queue is empty; otherwise, false.

func (*KeyedPriorityQueue[K, V]) Len

func (pq *KeyedPriorityQueue[K, V]) Len() int

Len returns the size of the priority queue.

func (*KeyedPriorityQueue[K, V]) Peek

func (pq *KeyedPriorityQueue[K, V]) Peek() (K, V, bool)

Peek returns the highest priority key and value from the priority queue. It returns false as its last return value if the priority queue is empty; otherwise, true.

func (*KeyedPriorityQueue[K, V]) PeekKey

func (pq *KeyedPriorityQueue[K, V]) PeekKey() (K, bool)

PeekKey returns the highest priority key from the priority queue. It returns false as its last return value if the priority queue is empty; otherwise, true.

func (*KeyedPriorityQueue[K, V]) PeekValue

func (pq *KeyedPriorityQueue[K, V]) PeekValue() (V, bool)

PeekValue returns the highest priority value from the priority queue. It returns false as its last return value if the priority queue is empty; otherwise, true.

func (*KeyedPriorityQueue[K, V]) Pop

func (pq *KeyedPriorityQueue[K, V]) Pop() (K, V, bool)

Pop removes and returns the highest priority key and value from the priority queue. It returns false as its last return value if the priority queue is empty; otherwise, true.

func (*KeyedPriorityQueue[K, V]) Push

func (pq *KeyedPriorityQueue[K, V]) Push(k K, v V) error

Push inserts the given priority value v onto the priority queue associated with the given key k. If the key already exists in the priority queue, it returns a KeyAlreadyExistsError error.

func (*KeyedPriorityQueue[K, V]) Remove

func (pq *KeyedPriorityQueue[K, V]) Remove(k K)

Remove removes the priority value associated with the given key k from the priority queue. It's a no-op if there's no such key k in the priority queue.

func (*KeyedPriorityQueue[K, V]) Set

func (pq *KeyedPriorityQueue[K, V]) Set(k K, v V)

Set inserts a new entry in the priority queue with the given key and value, if the key is not present in it; otherwise, it updates the priority value associated with the given key.

Example

package main

import (
	"fmt"
	"math"
	"os"
	"text/tabwriter"

	"github.com/rdleal/go-priorityq/kpq"
)

func main() {
	// This code implements Dijkstra's algorithm to find the shortest path in a
	// weighted graph from a source vertex to all other vertices.
	//
	// This example shows how to change the priority in `KeyedPriorityQueue`
	// when needed.
	graph := struct {
		len   int
		edges []int
	}{
		len: 8,
		// edges represents the adjacency matrix of a directed weighted Graph.
		edges: []int{
			0, 5, 0, 0, 9, 0, 0, 8,
			0, 0, 12, 15, 0, 0, 0, 4,
			0, 0, 0, 3, 0, 0, 11, 0,
			0, 0, 0, 0, 0, 0, 9, 0,
			0, 0, 0, 0, 0, 4, 20, 5,
			0, 0, 1, 0, 0, 0, 13, 0,
			0, 0, 0, 0, 0, 0, 0, 0,
			0, 0, 7, 0, 0, 6, 0, 0,
		},
	}

	edge := func(u, v int) (weight int) {
		return graph.edges[graph.len*u+v]
	}

	adj := func(v int) []int {
		vertices := make([]int, 0)

		for i := 0; i < graph.len; i++ {
			if weight := edge(v, i); weight > 0 {
				vertices = append(vertices, i)
			}
		}

		return vertices
	}

	src := 0

	distTo := make([]int, graph.len)
	for i := 0; i < graph.len; i++ {
		distTo[i] = math.MaxInt
	}
	distTo[src] = 0

	// cmpFunc maintains the variant of a min priority queue,
	// needed for relaxing all the edges from the source.
	cmpFunc := func(a, b int) bool {
		return a < b
	}
	pq := kpq.NewKeyedPriorityQueue[int](cmpFunc)
	pq.Push(src, 0) // starts with source vertex.

	for !pq.IsEmpty() {
		u, dist, _ := pq.Pop()
		// Iterate over vertices adjacent to vertex u, and relax each edge
		// between them.
		// Given a vertex u and v and a weighted edge e from u to v,
		// the relaxation algorithm updates the value in the priority queue
		// if the edge e provides a shorter path from u to v than previously known.
		for _, v := range adj(u) {
			weight := edge(u, v)
			if distTo[v] > dist+weight {
				distTo[v] = dist + weight
				pq.Set(v, distTo[v])
			}
		}
	}

	w := tabwriter.NewWriter(os.Stdout, 0, 0, 4, ' ', 0)
	fmt.Fprintln(w, "Vertex\tDistance From Source")
	for i := 0; i < graph.len; i++ {
		fmt.Fprintf(w, "%3d\t%10d\n", i, distTo[i])
	}
	w.Flush()
}

Output:

Vertex    Distance From Source
  0                0
  1                5
  2               14
  3               17
  4                9
  5               13
  6               25
  7                8

func (*KeyedPriorityQueue[K, V]) Update

func (pq *KeyedPriorityQueue[K, V]) Update(k K, v V) error

Update changes the priority value associated with the given key k to the given value v. If there's no key k in the priority queue, it returns a KeyNotFoundError error.

func (*KeyedPriorityQueue[K, V]) ValueOf

func (pq *KeyedPriorityQueue[K, V]) ValueOf(k K) (V, bool)

ValueOf returns the priority value associated with the given key k. It returns false as its last return value if there's no such key k in the priority queue; otherwise, true.