package graph

import (
	
	
)

type undirected[ comparable,  any] struct {
	hash   Hash[, ]
	traits *Traits
	store  Store[, ]
}

func newUndirected[ comparable,  any]( Hash[, ],  *Traits,  Store[, ]) *undirected[, ] {
	return &undirected[, ]{
		hash:   ,
		traits: ,
		store:  ,
	}
}

func ( *undirected[, ]) () *Traits {
	return .traits
}

func ( *undirected[, ]) ( ,  ...func(*VertexProperties)) error {
	 := .hash()

	 := VertexProperties{
		Weight:     0,
		Attributes: make(map[string]string),
	}

	for ,  := range  {
		(&)
	}

	return .store.AddVertex(, , )
}

func ( *undirected[, ]) ( ) (, error) {
	, ,  := .store.Vertex()
	return , 
}

func ( *undirected[, ]) ( ) (, VertexProperties, error) {
	, ,  := .store.Vertex()
	if  != nil {
		return , VertexProperties{}, 
	}

	return , , nil
}

func ( *undirected[, ]) ( ) error {
	return .store.RemoveVertex()
}

func ( *undirected[, ]) (,  ,  ...func(*EdgeProperties)) error {
	if , ,  := .store.Vertex();  != nil {
		return fmt.Errorf("could not find source vertex with hash %v: %w", , )
	}

	if , ,  := .store.Vertex();  != nil {
		return fmt.Errorf("could not find target vertex with hash %v: %w", , )
	}

	//nolint:govet // False positive.
	if ,  := .Edge(, ); !errors.Is(, ErrEdgeNotFound) {
		return ErrEdgeAlreadyExists
	}

	// If the user opted in to preventing cycles, run a cycle check.
	if .traits.PreventCycles {
		,  := CreatesCycle[, ](, , )
		if  != nil {
			return fmt.Errorf("check for cycles: %w", )
		}
		if  {
			return ErrEdgeCreatesCycle
		}
	}

	 := Edge[]{
		Source: ,
		Target: ,
		Properties: EdgeProperties{
			Attributes: make(map[string]string),
		},
	}

	for ,  := range  {
		(&.Properties)
	}

	if  := .addEdge(, , );  != nil {
		return fmt.Errorf("failed to add edge: %w", )
	}

	return nil
}

func ( *undirected[, ]) ( Graph[, ]) error {
	,  := .Edges()
	if  != nil {
		return fmt.Errorf("failed to get edges: %w", )
	}

	for ,  := range  {
		if  := .AddEdge(copyEdge());  != nil {
			return fmt.Errorf("failed to add (%v, %v): %w", .Source, .Target, )
		}
	}

	return nil
}

func ( *undirected[, ]) ( Graph[, ]) error {
	,  := .AdjacencyMap()
	if  != nil {
		return fmt.Errorf("failed to get adjacency map: %w", )
	}

	for  := range  {
		, ,  := .VertexWithProperties()
		if  != nil {
			return fmt.Errorf("failed to get vertex %v: %w", , )
		}

		if  = .AddVertex(, copyVertexProperties());  != nil {
			return fmt.Errorf("failed to add vertex %v: %w", , )
		}
	}

	return nil
}

func ( *undirected[, ]) (,  ) (Edge[], error) {
	// In an undirected graph, since multigraphs aren't supported, the edge AB
	// is the same as BA. Therefore, if source[target] cannot be found, this
	// function also looks for target[source].
	,  := .store.Edge(, )
	if errors.Is(, ErrEdgeNotFound) {
		,  = .store.Edge(, )
	}

	if  != nil {
		return Edge[]{}, 
	}

	, ,  := .store.Vertex()
	if  != nil {
		return Edge[]{}, 
	}

	, ,  := .store.Vertex()
	if  != nil {
		return Edge[]{}, 
	}

	return Edge[]{
		Source: ,
		Target: ,
		Properties: EdgeProperties{
			Weight:     .Properties.Weight,
			Attributes: .Properties.Attributes,
			Data:       .Properties.Data,
		},
	}, nil
}

type tuple[ comparable] struct {
	source, target 
}

func ( *undirected[, ]) () ([]Edge[], error) {
	,  := .store.ListEdges()
	if  != nil {
		return nil, fmt.Errorf("failed to get edges: %w", )
	}

	// An undirected graph creates each edge twice internally: The edge (A,B) is
	// stored both as (A,B) and (B,A). The Edges method is supposed to return
	// one of these two edges, because from an outside perspective, it only is
	// a single edge.
	//
	// To achieve this, Edges keeps track of already-added edges. For each edge,
	// it also checks if the reversed edge has already been added - e.g., for
	// an edge (A,B), Edges checks if the edge has been added as (B,A).
	//
	// These reversed edges are built as a custom tuple type, which is then used
	// as a map key for access in O(1) time. It looks scarier than it is.
	 := make([]Edge[], 0, len()/2)

	 := make(map[tuple[]]struct{})

	for ,  := range  {
		 := tuple[]{
			source: .Target,
			target: .Source,
		}
		if ,  := [];  {
			continue
		}

		 = append(, )

		 := tuple[]{
			source: .Source,
			target: .Target,
		}

		[] = struct{}{}
	}

	return , nil
}

func ( *undirected[, ]) (,  ,  ...func( *EdgeProperties)) error {
	,  := .store.Edge(, )
	if  != nil {
		return 
	}

	for ,  := range  {
		(&.Properties)
	}

	if  := .store.UpdateEdge(, , );  != nil {
		return 
	}

	 := 
	.Source = .Target
	.Target = .Source

	return .store.UpdateEdge(, , )
}

func ( *undirected[, ]) (,  ) error {
	if ,  := .Edge(, );  != nil {
		return 
	}

	if  := .store.RemoveEdge(, );  != nil {
		return fmt.Errorf("failed to remove edge from %v to %v: %w", , , )
	}

	if  := .store.RemoveEdge(, );  != nil {
		return fmt.Errorf("failed to remove edge from %v to %v: %w", , , )
	}

	return nil
}

func ( *undirected[, ]) () (map[]map[]Edge[], error) {
	,  := .store.ListVertices()
	if  != nil {
		return nil, fmt.Errorf("failed to list vertices: %w", )
	}

	,  := .store.ListEdges()
	if  != nil {
		return nil, fmt.Errorf("failed to list edges: %w", )
	}

	 := make(map[]map[]Edge[], len())

	for ,  := range  {
		[] = make(map[]Edge[])
	}

	for ,  := range  {
		[.Source][.Target] = 
	}

	return , nil
}

func ( *undirected[, ]) () (map[]map[]Edge[], error) {
	return .AdjacencyMap()
}

func ( *undirected[, ]) () (Graph[, ], error) {
	 := &Traits{
		IsDirected: .traits.IsDirected,
		IsAcyclic:  .traits.IsAcyclic,
		IsWeighted: .traits.IsWeighted,
		IsRooted:   .traits.IsRooted,
	}

	 := &undirected[, ]{
		hash:   .hash,
		traits: ,
		store:  newMemoryStore[, ](),
	}

	if  := .AddVerticesFrom();  != nil {
		return nil, fmt.Errorf("failed to add vertices: %w", )
	}

	if  := .AddEdgesFrom();  != nil {
		return nil, fmt.Errorf("failed to add edges: %w", )
	}

	return , nil
}

func ( *undirected[, ]) () (int, error) {
	return .store.VertexCount()
}

func ( *undirected[, ]) () (int, error) {
	 := 0

	,  := .AdjacencyMap()
	if  != nil {
		return 0, fmt.Errorf("failed to get adjacency map: %w", )
	}

	for ,  := range  {
		 += len()
	}

	// Divide by 2 since every add edge operation on undirected graph is counted
	// twice.
	return  / 2, nil
}

func ( *undirected[, ]) (,  Edge[]) bool {
	 := .hash(.Source)
	 := .hash(.Target)
	 := .hash(.Source)
	 := .hash(.Target)

	if  ==  &&  ==  {
		return true
	}

	if !.traits.IsDirected {
		return  ==  &&  == 
	}

	return false
}

func ( *undirected[, ]) (,  ,  Edge[]) error {
	 := .store.AddEdge(, , )
	if  != nil {
		return 
	}

	 := Edge[]{
		Source: .Target,
		Target: .Source,
		Properties: EdgeProperties{
			Weight:     .Properties.Weight,
			Attributes: .Properties.Attributes,
			Data:       .Properties.Data,
		},
	}

	 = .store.AddEdge(, , )
	if  != nil {
		return 
	}

	return nil
}