// Copyright (c) 2016 Kiel University and others.
//
// 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 intermediate

import (
	

	basegraph 
	
)

// ProcessHighDegreeNodes is the arena-backed port of ELK 0.8.1's
// HighDegreeNodeLayeringProcessor. It isolates bounded-height trees adjacent
// to high-degree nodes in newly introduced layers.
func ( *layered.LGraphArena,  layered.LGraphID) {
	 := highDegreeNodeProcessor{
		arena:               ,
		graphID:             ,
		degreeThreshold:     basegraph.Get(&.Graph().Properties, layered.HighDegreeNodeThreshold),
		treeHeightThreshold: basegraph.Get(&.Graph().Properties, layered.HighDegreeNodeTreeHeight),
	}
	if .treeHeightThreshold == 0 {
		.treeHeightThreshold = math.MaxInt
	}
	.process()
}

type highDegreeNodeProcessor struct {
	arena               *layered.LGraphArena
	graphID             layered.LGraphID
	degreeThreshold     int
	treeHeightThreshold int
}

type highDegreeNodeInformation struct {
	incomingMaxHeight int
	incomingRoots     []layered.LNodeID
	outgoingMaxHeight int
	outgoingRoots     []layered.LNodeID
}

type treeDirection uint8

const (
	treeIncoming treeDirection = iota
	treeOutgoing
)

func ( *highDegreeNodeProcessor) () {
	// Java's ListIterator skips the layers it introduces. Retaining the
	// original layer identities gives the same traversal while slice inserts
	// move their indices underneath us.
	 := append([]layered.LayerID(nil), .arena.Graph(.graphID).Layers...)
	for ,  := range  {
		 := .arena.Graph(.graphID)
		 := indexOfLayer(.Layers, )
		if  < 0 {
			continue
		}

		type  struct {
			 layered.LNodeID
			 highDegreeNodeInformation
		}
		 := make([], 0)
		,  := -1, -1
		for ,  := range append([]layered.LNodeID(nil), .arena.Layer().Nodes...) {
			if !.isHighDegreeNode() {
				continue
			}
			 := .calculateInformation()
			 = max(, .incomingMaxHeight)
			 = max(, .outgoingMaxHeight)
			 = append(, {: , : })
		}

		 := make([]layered.LayerID, 0, max(0, ))
		for range  {
			 := .insertLayer()
			// Each repeated prepend is nearer to the current layer than the
			// previous one; Java consequently adds it at index zero.
			 = append([]layered.LayerID{}, ...)
			++
		}
		for ,  := range  {
			for ,  := range ..incomingRoots {
				.moveTree(, treeIncoming, )
			}
		}

		 := make([]layered.LayerID, 0, max(0, ))
		for range  {
			 := .insertLayer( + 1 + len())
			 = append(, )
		}
		for ,  := range  {
			for ,  := range ..outgoingRoots {
				.moveTree(, treeOutgoing, )
			}
		}
	}

	 := .arena.Graph(.graphID)
	 := .Layers[:0]
	for ,  := range .Layers {
		if len(.arena.Layer().Nodes) != 0 {
			 = append(, )
		}
	}
	.Layers = 
}

func ( *highDegreeNodeProcessor) ( int) layered.LayerID {
	 := .arena.Graph(.graphID)
	 := .arena.AddLayer(.graphID)
	 = .arena.Graph(.graphID) // AddLayer may grow the arena.
	.Layers = append(.Layers, 0)
	copy(.Layers[+1:], .Layers[:])
	.Layers[] = 
	return 
}

func ( *highDegreeNodeProcessor) ( layered.LNodeID) bool {
	return len(.arena.NodeConnectedEdges()) >= .degreeThreshold
}

func ( *highDegreeNodeProcessor) ( layered.LNodeID) highDegreeNodeInformation {
	 := highDegreeNodeInformation{incomingMaxHeight: -1, outgoingMaxHeight: -1}
	for ,  := range .arena.NodeIncomingEdges() {
		if .arena.EdgeIsSelfLoop() {
			continue
		}
		 := .arena.EdgeSourceNode()
		if !.hasSingleConnection(, treeOutgoing) {
			continue
		}
		 := .treeHeight(, treeOutgoing, treeIncoming)
		if  < 0 {
			continue
		}
		.incomingMaxHeight = max(.incomingMaxHeight, )
		.incomingRoots = append(.incomingRoots, )
	}
	for ,  := range .arena.NodeOutgoingEdges() {
		if .arena.EdgeIsSelfLoop() {
			continue
		}
		 := .arena.EdgeTargetNode()
		if !.hasSingleConnection(, treeIncoming) {
			continue
		}
		 := .treeHeight(, treeIncoming, treeOutgoing)
		if  < 0 {
			continue
		}
		.outgoingMaxHeight = max(.outgoingMaxHeight, )
		.outgoingRoots = append(.outgoingRoots, )
	}
	return 
}

func ( *highDegreeNodeProcessor) ( layered.LNodeID,  treeDirection) []layered.LEdgeID {
	if  == treeIncoming {
		return .arena.NodeIncomingEdges()
	}
	return .arena.NodeOutgoingEdges()
}

func ( *highDegreeNodeProcessor) (
	 layered.LNodeID,
	 treeDirection,
) bool {
	var  *layered.LNodeID
	for ,  := range .edges(, ) {
		 := .arena.EdgeOtherNode(, )
		if  == nil {
			 := 
			 = &
		} else if * !=  {
			return false
		}
	}
	return true
}

func ( *highDegreeNodeProcessor) (
	 layered.LNodeID,
	 treeDirection,
	 treeDirection,
) int {
	if .isHighDegreeNode() || !.hasSingleConnection(, ) {
		return -1
	}
	 := .edges(, )
	if len() == 0 {
		return 1
	}
	 := 0
	for ,  := range  {
		 := .arena.EdgeOtherNode(, )
		 := .(, , )
		if  < 0 {
			return -1
		}
		 = max(, )
		if  > .treeHeightThreshold-1 {
			return -1
		}
	}
	return  + 1
}

func ( *highDegreeNodeProcessor) (
	 layered.LNodeID,
	 treeDirection,
	 []layered.LayerID,
) {
	if len() == 0 {
		panic("layered: high-degree tree exceeds its calculated height")
	}
	.arena.SetNodeLayer(, &[0])
	for ,  := range .edges(, ) {
		.(.arena.EdgeOtherNode(, ), , [1:])
	}
}

func indexOfLayer( []layered.LayerID,  layered.LayerID) int {
	for ,  := range  {
		if  ==  {
			return 
		}
	}
	return -1
}