package graphs

import (
	"datastructures/linear"
)

// DFS() -> Depth First traversal, returns ordered slice or nil if start point
// is invalid
func (graph *Graph[T]) DFS(start T) []T {
	// sanity check
	if _, ok := graph.adjList[start]; !ok {
		return nil
	}

	visited := make(map[T]bool, len(graph.adjList))
	ordered := make([]T, 0, graph.Order())

	stack := linear.Stack[T]{}

	stack.Push(start)
	visited[start] = true

	for stack.Size() > 0 {

		current, err := stack.Pop()
		if err != nil {
			break
		}

		ordered = append(ordered, current)

		for _, neighbor := range graph.adjList[current] {
			if !visited[neighbor] {
				visited[neighbor] = true
				stack.Push(neighbor)

			}
		}

	}

	return ordered
}

// BFS() -> Breadth First traversal start, returning the
// vertices in visit order. Returns nil if start is not in the graph.
func (graph *Graph[T]) BFS(start T) []T {
	// sanity check
	if _, ok := graph.adjList[start]; !ok {
		return nil
	}

	visited := make(map[T]bool, len(graph.adjList))
	ordered := make([]T, 0, graph.Order())

	queue := linear.Queue[T]{}

	queue.Push(start)
	visited[start] = true

	for queue.Size() > 0 {

		current, err := queue.Pop()
		if err != nil {
			break
		}

		ordered = append(ordered, current)

		for _, neighbor := range graph.adjList[current] {
			if !visited[neighbor] {
				visited[neighbor] = true
				queue.Push(neighbor)

			}
		}

	}

	return ordered
}