package graphs

import "slices"

// DAG -> Directed Acyclic Graph. Any edge that would introduce a cycle is
// rejected, so the acyclic invariant always holds.
type DAG[T comparable] struct {
	adjList map[T][]T
}

// NewDAG() -> Creates a Directed Acyclic Graph
func NewDAG[T comparable]() *DAG[T] {
	gp := &DAG[T]{
		adjList: make(map[T][]T),
	}

	return gp
}

// AddIsolatedVertex() -> Creates an isolated Vertex returns True if ok ,
// false if vertex already exist
func (gp *DAG[T]) AddIsolatedVertex(newVertex T) bool {
	_, ok := gp.adjList[newVertex]
	if !ok {
		gp.adjList[newVertex] = make([]T, 0)
		return true
	}
	return false
}

// AddVertex() -> adds a directed edge from -> to, creating either vertex if it
// is missing. Returns false (and adds nothing) when the edge is a self loop,
// already exists, or would create a cycle.
func (gp *DAG[T]) AddVertex(from T, to T) bool {
	// self loops are cycles of length 1
	if from == to {
		return false
	}

	gp.AddIsolatedVertex(from)
	gp.AddIsolatedVertex(to)

	if slices.Contains(gp.adjList[from], to) {
		return false
	}

	// from -> to closes a cycle iff "to" can already reach "from".
	if gp.hasPath(to, from) {
		return false
	}

	gp.adjList[from] = append(gp.adjList[from], to)
	return true
}

// hasPath() -> reports whether a directed path exists from src to dst.
func (gp *DAG[T]) hasPath(src T, dst T) bool {
	visited := make(map[T]bool)
	return gp.dfs(src, dst, visited)
}

func (gp *DAG[T]) dfs(current T, dst T, visited map[T]bool) bool {
	if current == dst {
		return true
	}

	visited[current] = true

	for _, next := range gp.adjList[current] {
		if !visited[next] && gp.dfs(next, dst, visited) {
			return true
		}
	}

	return false
}

// Order() -> returns the amount of Vertices
func (gp *DAG[T]) Order() int {
	return len(gp.adjList)
}

// Size() -> returns the amount of Edges
func (gp *DAG[T]) Size() int {
	var size int

	// directed: each edge is stored once, so no halving.
	for _, val := range gp.adjList {
		size += len(val)
	}
	return size
}

// Display() -> returns adjList[map]T []T
func (gp *DAG[T]) Display() map[T][]T {
	return gp.adjList
}