aboutsummaryrefslogtreecommitdiffstats
path: root/heap/example_test.go
diff options
context:
space:
mode:
Diffstat (limited to 'heap/example_test.go')
-rw-r--r--heap/example_test.go178
1 files changed, 0 insertions, 178 deletions
diff --git a/heap/example_test.go b/heap/example_test.go
deleted file mode 100644
index f8ea7d8..0000000
--- a/heap/example_test.go
+++ /dev/null
@@ -1,178 +0,0 @@
-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
-}