From b3ce67680f630c31bf715447c604019682c9c9ce Mon Sep 17 00:00:00 2001
From: Rose Hogenson <rosehogenson@posteo.net>
Date: Sat, 12 Apr 2025 17:43:42 -0700
Subject: Rebrand to github.com/rhogenson/container

I also added a heap package
---
 heap/example_test.go | 178 +++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 178 insertions(+)
 create mode 100644 heap/example_test.go

(limited to 'heap/example_test.go')

diff --git a/heap/example_test.go b/heap/example_test.go
new file mode 100644
index 0000000..f8ea7d8
--- /dev/null
+++ b/heap/example_test.go
@@ -0,0 +1,178 @@
+package heap_test
+
+import (
+	"cmp"
+	"fmt"
+
+	"github.com/rhogenson/container/heap"
+)
+
+func Example_dijkstra() {
+	const (
+		maze = `
+---------------------
+    |   |           |
+| --- | | --- ----- |
+|   | |   |   |     |
+|-- |-----| ----- --|
+|   |     |     | | |
+| --- --- | --- | | |
+| |   | |     | | | |
+| | --- | | --- | | |
+| | |   | | |   |   |
+| | --- | |-- --|-- |
+| |   | | |   | |   |
+| |-- | | | --- | --|
+| |   | |   |     | |
+| | --| ----- ----- |
+| |   |       |     |
+| | | | --------- | |
+| | | |     |   | | |
+| --- |---- | | | | |
+|     |       |      
+---------------------
+`
+		width  = 21
+		height = 21
+	)
+
+	type point struct{ x, y int }
+	start := point{0, 1}
+	goal := point{20, 19}
+	neighbors := func(p point) []point {
+		return []point{
+			{p.x - 1, p.y},
+			{p.x + 1, p.y},
+			{p.x, p.y - 1},
+			{p.x, p.y + 1},
+		}
+	}
+	walkable := func(p point) bool {
+		return 0 <= p.y && p.y < height &&
+			0 <= p.x && p.x < width &&
+			maze[p.y*(width+1)+p.x+1] == ' '
+	}
+
+	visited := map[point]int{start: 1}
+	q := heap.New(func(x, y point) int { return cmp.Compare(visited[x], visited[y]) })
+	q.Push(start)
+Dijkstra:
+	for {
+		p, ok := q.Pop()
+		if !ok {
+			fmt.Println("Giving up!")
+			return
+		}
+		for _, neighbor := range neighbors(p) {
+			if !walkable(neighbor) || visited[neighbor] > 0 {
+				continue
+			}
+			visited[neighbor] = visited[p] + 1
+			if neighbor == goal {
+				break Dijkstra
+			}
+			q.Push(neighbor)
+		}
+	}
+
+	completedMaze := []byte(maze)
+	fillIn := func(p point) {
+		completedMaze[p.y*(width+1)+p.x+1] = '*'
+	}
+	for p := goal; p != start; {
+		fillIn(p)
+		closestPoint := p
+		for _, neighbor := range neighbors(p) {
+			if walkable(neighbor) && visited[neighbor] > 0 && visited[neighbor] < visited[closestPoint] {
+				closestPoint = neighbor
+			}
+		}
+		p = closestPoint
+	}
+	fillIn(start)
+
+	fmt.Printf("%s\n", completedMaze)
+
+	// Output:
+	// ---------------------
+	// **  |   |    *******|
+	// |*--- | | ---*-----*|
+	// |***| |   |***|  ***|
+	// |--*|-----|*-----*--|
+	// |***|*****|*    |*| |
+	// |*---*---*|*--- |*| |
+	// |*|***| |***  | |*| |
+	// |*|*--- | | --- |*| |
+	// |*|*|   | | |   |***|
+	// |*|*--- | |-- --|--*|
+	// |*|***| | |   | |***|
+	// |*|--*| | | --- |*--|
+	// |*|***| |   |*****| |
+	// |*|*--| -----*----- |
+	// |*|***|*******|     |
+	// |*| |*|*--------- | |
+	// |*| |*|*****|***| | |
+	// |*---*|----*|*|*| | |
+	// |*****|    ***|******
+	// ---------------------
+}
+
+func ExampleNew() {
+	priority := map[string]int{
+		"job1": 10,
+		"job2": 30,
+		"job3": 100,
+		"job4": 20,
+	}
+	h := heap.New(func(j1, j2 string) int { return cmp.Compare(priority[j1], priority[j2]) })
+	h.Push("job1")
+	h.Push("job2")
+	h.Push("job3")
+	h.Push("job4")
+	if highestPriorityJob, ok := h.Pop(); ok {
+		fmt.Println(highestPriorityJob)
+	}
+
+	// Output:
+	// job1
+}
+
+func ExampleHeap_Len() {
+	h := heap.New(cmp.Compare[int])
+	h.Push(1)
+	h.Push(2)
+	h.Push(3)
+	fmt.Println(h.Len())
+
+	// Output:
+	// 3
+}
+
+func ExampleHeap_Grow() {
+	h := heap.New(cmp.Compare[int])
+	h.Grow(3)
+	// Push without allocating:
+	h.Push(1)
+	h.Push(2)
+	h.Push(3)
+}
+
+func ExampleHeap_Push() {
+	h := heap.New(cmp.Compare[int])
+	h.Push(1)
+	h.Push(2)
+	h.Push(3)
+}
+
+func ExampleHeap_Pop() {
+	h := heap.New(cmp.Compare[int])
+	h.Push(1)
+	h.Push(2)
+	h.Push(3)
+	if n, ok := h.Pop(); ok {
+		fmt.Println(n)
+	}
+
+	// Output:
+	// 1
+}
-- 
cgit v1.3.1