// Copyright 2020 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

package graph

import (
	"fmt"
	"testing"

	"slices"
)

type direction int

const (
	north direction = iota
	ne
	east
	se
	south
	sw
	west
	nw
	up
	down
)

func (dir direction) String() string {
	strs := map[direction]string{
		north: "north",
		ne:    "ne",
		east:  "east",
		se:    "se",
		south: "south",
		sw:    "sw",
		west:  "west",
		nw:    "nw",
		up:    "up",
		down:  "down",
	}
	if str, ok := strs[dir]; ok {
		return str
	}
	return fmt.Sprintf("direction %d", dir)
}

type mazeRoom struct {
	index int
	exits [10]int
}

type mazeEdge struct {
	from, to int
	dir      direction
}

// Edges returns the exits from the room.
func (m mazeRoom) Edges() []mazeEdge {
	var r []mazeEdge
	for i, exit := range m.exits {
		if exit != 0 {
			r = append(r, mazeEdge{
				from: m.index,
				to:   exit,
				dir:  direction(i),
			})
		}
	}
	return r
}

// Nodes returns the rooms connected by an edge.
func (e mazeEdge) Nodes() (mazeRoom, mazeRoom) {
	m1, ok := zork[e.from]
	if !ok {
		panic("bad edge")
	}
	m2, ok := zork[e.to]
	if !ok {
		panic("bad edge")
	}
	return m1, m2
}

// The first maze in Zork. Room indexes based on original Fortran data file.
// You are in a maze of twisty little passages, all alike.
var zork = map[int]mazeRoom{
	11: {exits: [10]int{north: 11, south: 12, east: 14}}, // west to Troll Room
	12: {exits: [10]int{south: 11, north: 14, east: 13}},
	13: {exits: [10]int{west: 12, north: 14, up: 16}},
	14: {exits: [10]int{west: 13, north: 11, east: 15}},
	15: {exits: [10]int{south: 14}},                   // Dead End
	16: {exits: [10]int{east: 17, north: 13, sw: 18}}, // skeleton, etc.
	17: {exits: [10]int{west: 16}},                    // Dead End
	18: {exits: [10]int{down: 16, east: 19, west: 18, up: 22}},
	19: {exits: [10]int{up: 29, west: 18, ne: 15, east: 20, south: 30}},
	20: {exits: [10]int{ne: 19, west: 20, se: 21}},
	21: {exits: [10]int{north: 20}}, // Dead End
	22: {exits: [10]int{north: 18, east: 24, down: 23, south: 28, west: 26, nw: 22}},
	23: {exits: [10]int{east: 22, west: 28, up: 24}},
	24: {exits: [10]int{ne: 25, down: 23, nw: 28, sw: 26}},
	25: {exits: [10]int{sw: 24}}, // Grating room (up to Clearing)
	26: {exits: [10]int{west: 16, sw: 24, east: 28, up: 22, north: 27}},
	27: {exits: [10]int{south: 26}}, // Dead End
	28: {exits: [10]int{east: 22, down: 26, south: 23, west: 24}},
	29: {exits: [10]int{west: 30, nw: 29, ne: 19, south: 19}},
	30: {exits: [10]int{west: 29, south: 19}}, // ne to Cyclops Room
}

func TestShortestPath(t *testing.T) {
	// The Zork maze is not a proper undirected simple graph,
	// as there are some one way paths (e.g., 19 -> 15),
	// but for this test that doesn't matter.

	// Set the index field in the map. Simpler than doing it in the
	// composite literal.
	for k := range zork {
		r := zork[k]
		r.index = k
		zork[k] = r
	}

	var nodes []mazeRoom
	for idx, room := range zork {
		mridx := room
		mridx.index = idx
		nodes = append(nodes, mridx)
	}
	g := New[mazeRoom, mazeEdge](nodes)
	path, err := g.ShortestPath(zork[11], zork[30])
	if err != nil {
		t.Fatal(err)
	}
	var steps []direction
	for _, edge := range path {
		steps = append(steps, edge.dir)
	}
	want := []direction{east, west, up, sw, east, south}
	if !slices.Equal(steps, want) {
		t.Errorf("ShortestPath returned %v, want %v", steps, want)
	}
}