// Copyright (c) 2016, 2020 Kiel University and others.
// Copyright (c) 2026 The elk-go Authors.
//
// This program and the accompanying materials are made available under the
// terms of the Eclipse Public License 2.0 which is available at
// https://www.eclipse.org/legal/epl-2.0.
//
// SPDX-License-Identifier: EPL-2.0

package p2layers

import (
	basegraph 
	
	
)

// CoffmanGrahamLayerer bounds the number of nodes per layer after computing
// the exact ELK 0.12.0 transitive reduction and priority topological order.
type CoffmanGrahamLayerer struct {
	nodeMark           []bool
	edgeMark           []bool
	inDegree           []int
	outDegree          []int
	topologicalOrder   []int
	inTopologicalOrder map[layered.LNodeID][]int
}

func (*CoffmanGrahamLayerer) (
	 *layered.LGraphArena,
	 layered.LGraphID,
) layered.ProcessorConfiguration {
	return layered.NetworkSimplexLayeringConfiguration()
}

func ( *CoffmanGrahamLayerer) ( *layered.LGraphArena,  layered.LGraphID) error {
	 := .Graph()
	if len(.LayerlessNodes) == 0 {
		return nil
	}
	 := basegraph.Get(&.Properties, layered.CoffmanGrahamLayerBound)
	 := 0
	for ,  := range .LayerlessNodes {
		.Node().ID = 
		for ,  := range .NodeOutgoingEdges() {
			.Edge().ID = 
			++
		}
	}
	.nodeMark = make([]bool, len(.LayerlessNodes))
	.edgeMark = make([]bool, )
	.inDegree = make([]int, len(.LayerlessNodes))
	.outDegree = make([]int, len(.LayerlessNodes))
	.topologicalOrder = make([]int, len(.LayerlessNodes))
	.inTopologicalOrder = make(map[layered.LNodeID][]int)
	.transitiveReduction(, )

	 := javacompat.NewGWTPriorityQueue(func(,  layered.LNodeID) int {
		return .compareNodesInTopologicalOrder(, , )
	})
	for ,  := range .LayerlessNodes {
		for ,  := range .NodeIncomingEdges() {
			if !.edgeMark[.Edge().ID] {
				.inDegree[.Node().ID]++
			}
		}
		if .inDegree[.Node().ID] == 0 {
			.Add()
		}
	}
	 := 0
	for !.IsEmpty() {
		,  := .Poll()
		.topologicalOrder[.Node().ID] = 
		++
		for ,  := range .NodeOutgoingEdges() {
			if .edgeMark[.Edge().ID] {
				continue
			}
			 := .EdgeTargetNode()
			 := .Node().ID
			.inDegree[]--
			.inTopologicalOrder[] = append(
				.inTopologicalOrder[], .topologicalOrder[.Node().ID],
			)
			if .inDegree[] == 0 {
				.Add()
			}
		}
	}

	 := javacompat.NewGWTPriorityQueue(func(,  layered.LNodeID) int {
		 := .topologicalOrder[.Node().ID]
		 := .topologicalOrder[.Node().ID]
		if  >  {
			return -1
		}
		if  <  {
			return 1
		}
		return 0
	})
	for ,  := range .LayerlessNodes {
		for ,  := range .NodeOutgoingEdges() {
			if !.edgeMark[.Edge().ID] {
				.outDegree[.Node().ID]++
			}
		}
		if .outDegree[.Node().ID] == 0 {
			.Add()
		}
	}

	 := []layered.LayerID{.AddLayer()}
	 := [0]
	for !.IsEmpty() {
		,  := .Poll()
		if len(.Layer().Nodes) >=  || !.canAdd(, , ) {
			 = .AddLayer()
			 = append(, )
		}
		.SetNodeLayer(, &)
		for ,  := range .NodeIncomingEdges() {
			if .edgeMark[.Edge().ID] {
				continue
			}
			 := .EdgeSourceNode()
			 := .Node().ID
			.outDegree[]--
			if .outDegree[] == 0 {
				.Add()
			}
		}
	}
	for  := len() - 1;  >= 0; -- {
		.Layers = append(.Layers, [])
	}
	.LayerlessNodes = .LayerlessNodes[:0]
	return nil
}

func ( *CoffmanGrahamLayerer) (
	 *layered.LGraphArena,
	,  layered.LNodeID,
) int {
	 := .inTopologicalOrder[]
	 := .inTopologicalOrder[]
	,  := len(), len()
	for  > 0 &&  > 0 {
		--
		--
		if [] < [] {
			return -1
		}
		if [] > [] {
			return 1
		}
	}
	// ELK tests hasNext() after traversing each ListIterator backwards.
	// Thus a non-empty iterator reports true after at least one previous() call,
	// even when it is exhausted in the backwards direction. Preserve that
	// seemingly unusual source (and elkjs) behavior exactly. ELK 0.12.0 adds
	// node ID as the deterministic final criterion when both lists are empty.
	 :=  < len()
	 :=  < len()
	if ! && ! {
		,  := .Node().ID, .Node().ID
		if  <  {
			return -1
		}
		if  >  {
			return 1
		}
		return 0
	}
	if  {
		return 1
	}
	return -1
}

func ( *CoffmanGrahamLayerer) (
	 *layered.LGraphArena,
	 layered.LGraphID,
) {
	for ,  := range .Graph().LayerlessNodes {
		clear(.nodeMark)
		for ,  := range .NodeOutgoingEdges() {
			.transitiveDFS(, , .EdgeTargetNode())
		}
	}
}

func ( *CoffmanGrahamLayerer) (
	 *layered.LGraphArena,
	,  layered.LNodeID,
) {
	 := .Node().ID
	if .nodeMark[] {
		return
	}
	for ,  := range .NodeOutgoingEdges() {
		 := .EdgeTargetNode()
		for ,  := range .NodeIncomingEdges() {
			if .EdgeSourceNode() ==  {
				.edgeMark[.Edge().ID] = true
			}
		}
		.(, , )
	}
	.nodeMark[] = true
}

func ( *CoffmanGrahamLayerer) (
	 *layered.LGraphArena,
	 layered.LNodeID,
	 layered.LayerID,
) bool {
	for ,  := range .NodeOutgoingEdges() {
		 := .Node(.EdgeTargetNode()).Layer
		if  != nil && * ==  {
			return false
		}
	}
	return true
}