// Copyright (c) 2016 Kiel University and others.
// Copyright (c) 2016, 2017 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 networksimplex implements ELK's deterministic network-simplex
// layering primitive. The implementation is a direct port of ELK v0.8.1's
// org.eclipse.elk.alg.common.networksimplex package.
package networksimplex

import 

// NodeID and EdgeID are stable arena handles. Arena order is Java object
// creation order; Nodes separately preserves NGraph's mutable list order.
type NodeID uint32
type EdgeID uint32

// Node is the Go counterpart of NNode.
type Node struct {
	ID     int
	Origin any
	Layer  int

	IncomingEdges []EdgeID
	OutgoingEdges []EdgeID

	internalID       int
	treeNode         bool
	unknownCutvalues []EdgeID
}

// ConnectedEdges returns incoming edges followed by outgoing edges, matching
// NNode.getConnectedEdges' iteration order.
func ( *Node) () []EdgeID {
	 := make([]EdgeID, 0, len(.IncomingEdges)+len(.OutgoingEdges))
	 = append(, .IncomingEdges...)
	 = append(, .OutgoingEdges...)
	return 
}

// Edge is the Go counterpart of NEdge.
type Edge struct {
	ID     int
	Origin any
	Source NodeID
	Target NodeID
	Weight float64
	Delta  int

	internalID int
	treeEdge   bool
}

// Other returns the opposite endpoint of edge.
func ( *Edge) ( NodeID) NodeID {
	switch  {
	case .Source:
		return .Target
	case .Target:
		return .Source
	default:
		panic(fmt.Sprintf("node %d is not part of edge %d", , .ID))
	}
}

// Graph stores network-simplex nodes and edges in deterministic arenas.
type Graph struct {
	// Nodes is the mutable list ELK removes from and appends to while pruning
	// subtrees. It intentionally differs from the immutable node arena.
	Nodes []NodeID
	nodes []Node
	edges []Edge
}

func () *Graph { return &Graph{} }

func ( *Graph) ( NodeID) *Node { return &.nodes[int()] }
func ( *Graph) ( EdgeID) *Edge { return &.edges[int()] }
func ( *Graph) () int       { return len(.edges) }

// AddNode creates and appends an NNode.
func ( *Graph) () NodeID {
	 := NodeID(len(.nodes))
	.nodes = append(.nodes, Node{})
	.Nodes = append(.Nodes, )
	return 
}

// AddEdge creates an NEdge and registers it with both endpoints.
func ( *Graph) (,  NodeID,  float64,  int) EdgeID {
	if  ==  {
		panic(fmt.Sprintf("network simplex does not support self-loops on node %d", ))
	}
	 := EdgeID(len(.edges))
	.edges = append(.edges, Edge{
		Source: ,
		Target: ,
		Weight: ,
		Delta:  ,
	})
	.Node().OutgoingEdges = append(.Node().OutgoingEdges, )
	.Node().IncomingEdges = append(.Node().IncomingEdges, )
	return 
}

// ReverseEdge reverses edge and updates endpoint incidence lists in the same
// order as NGraph.reverseEdge.
func ( *Graph) ( EdgeID) {
	 := .Edge()
	.Source, .Target = .Target, .Source
	,  := .Source, .Target
	.Node().OutgoingEdges = removeFirst(.Node().OutgoingEdges, )
	.Node().IncomingEdges = append(.Node().IncomingEdges, )
	.Node().IncomingEdges = removeFirst(.Node().IncomingEdges, )
	.Node().OutgoingEdges = append(.Node().OutgoingEdges, )
}

// MakeConnected adds one artificial root for a disconnected graph and joins
// each connected component to it with zero-weight, zero-delta edges. The
// second return value reports whether a root was created.
func ( *Graph) () (NodeID, bool) {
	for ,  := range append([]NodeID(nil), .Nodes...) {
		.Node().internalID = 
	}
	 := .connectedComponentRepresentatives()
	if len() <= 1 {
		return 0, false
	}
	 := .AddNode()
	for ,  := range  {
		.AddEdge(, , 0, 0)
	}
	return , true
}

func ( *Graph) () []NodeID {
	 := make([]NodeID, 0)
	 := make([]bool, len(.Nodes))
	for ,  := range .Nodes {
		if ![.Node().internalID] {
			 = append(, )
			.markComponent(, )
		}
	}
	return 
}

func ( *Graph) ( NodeID,  []bool) {
	 := .Node().internalID
	if [] {
		return
	}
	[] = true
	for ,  := range .Node().ConnectedEdges() {
		.(.Edge().Other(), )
	}
}

// IsAcyclic creates the same topological numbering as NGraph.isAcyclic and
// reports whether every edge points forward in it.
func ( *Graph) () bool {
	for ,  := range append([]NodeID(nil), .Nodes...) {
		.Node().internalID = 
	}
	 := make([]int, len(.Nodes))
	 := make([]int, len(.Nodes))
	for ,  := range .Nodes {
		[.Node().internalID] += len(.Node().IncomingEdges)
	}
	 := make([]NodeID, 0)
	for ,  := range .Nodes {
		if len(.Node().IncomingEdges) == 0 {
			 = append(, )
		}
	}
	if len() == 0 && len(.Nodes) != 0 {
		return false
	}
	for len() > 0 {
		 := [0]
		 = [1:]
		for ,  := range .Node().OutgoingEdges {
			 := .Edge().Target
			 := .Node().internalID
			 := .Node().internalID
			[] = max([], []+1)
			[]--
			if [] == 0 {
				 = append(, )
			}
		}
	}
	for ,  := range .Nodes {
		for ,  := range .Node().OutgoingEdges {
			 := .Edge()
			if [.Node(.Target).internalID] <= [.Node(.Source).internalID] {
				return false
			}
		}
	}
	return true
}

func removeFirst[ comparable]( [],  ) [] {
	for ,  := range  {
		if  ==  {
			copy([:], [+1:])
			var  
			[len()-1] = 
			return [:len()-1]
		}
	}
	return 
}