// Copyright (c) 2012, 2015 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 p4nodes

import (
	
	

	basegraph 
	
)

// BrandesKoepfPlacer adapts the default node placer to the layered pipeline.
type BrandesKoepfPlacer struct{}

func (BrandesKoepfPlacer) ( *layered.LGraphArena,  layered.LGraphID) error {
	PlaceBrandesKoepf(, )
	return nil
}

func (BrandesKoepfPlacer) (
	 *layered.LGraphArena,
	 layered.LGraphID,
) layered.ProcessorConfiguration {
	var  layered.ProcessorConfiguration
	 := basegraph.Get(&.Graph().Properties, layered.GraphProperties)
	if &layered.GraphPropertyExternalPorts != 0 {
		.AddBefore(layered.PhaseEdgeRouting, layered.HierarchicalPortPositionProcessor)
	}
	return 
}

// PlaceBrandesKoepf runs ELK 0.8.1's extended Brandes-Koepf node placement.
func ( *layered.LGraphArena,  layered.LGraphID) {
	 := BuildNeighborhoodInformation(, )
	 := basegraph.Get(&.Graph().Properties, layered.BKFixedAlignment)
	 := basegraph.Get(&.Graph().Properties, layered.FavorStraightEdges)
	 :=  == layered.FixedAlignmentNone && ! ||
		 == layered.FixedAlignmentBalanced
	 := make(map[layered.LEdgeID]bool)
	markConflicts(, , , )
	 := createDirectionalLayouts(, .NodeCount, )
	 := NewBKAligner(, , )
	for ,  := range  {
		.VerticalAlignment(, )
		.InsideBlockShift()
	}
	 := NewBKCompactor(, )
	for ,  := range  {
		.HorizontalCompaction(, , , )
	}
	var  *BKAlignedLayout
	if  {
		 := createBalancedLayout(, , , .NodeCount)
		if checkOrderConstraint(, , ) {
			 = 
		}
	}
	if  == nil {
		for ,  := range  {
			if !checkOrderConstraint(, , ) {
				continue
			}
			if  == nil || .LayoutSize() > .LayoutSize() {
				 = 
			}
		}
	}
	if  == nil {
		 = [0]
	}
	for ,  := range .Graph().Layers {
		for ,  := range .Layer().Nodes {
			 := .Node().ID
			.Node().Position.Y = requireFloat(.Y[], "y") +
				requireFloat(.InnerShift[], "inner shift")
		}
	}
	.Cleanup()
}

func createDirectionalLayouts(
	 layered.LGraphID,
	 int,
	 layered.FixedAlignment,
) []*BKAlignedLayout {
	 := func( VerticalDirection,  HorizontalDirection) *BKAlignedLayout {
		return NewBKAlignedLayout(, , , )
	}
	switch  {
	case layered.FixedAlignmentLeftDown:
		return []*BKAlignedLayout{(VerticalDown, HorizontalLeft)}
	case layered.FixedAlignmentLeftUp:
		return []*BKAlignedLayout{(VerticalUp, HorizontalLeft)}
	case layered.FixedAlignmentRightDown:
		return []*BKAlignedLayout{(VerticalDown, HorizontalRight)}
	case layered.FixedAlignmentRightUp:
		return []*BKAlignedLayout{(VerticalUp, HorizontalRight)}
	default:
		return []*BKAlignedLayout{
			(VerticalDown, HorizontalRight),
			(VerticalUp, HorizontalRight),
			(VerticalDown, HorizontalLeft),
			(VerticalUp, HorizontalLeft),
		}
	}
}

const minimumLayersForConflicts = 3

func markConflicts(
	 *layered.LGraphArena,
	 layered.LGraphID,
	 *NeighborhoodInformation,
	 map[layered.LEdgeID]bool,
) {
	 := .Graph().Layers
	if len() < minimumLayersForConflicts {
		return
	}
	 := make([]int, len())
	for ,  := range  {
		[] = len(.Layer().Nodes)
	}
	for  := 1;  < len()-1; ++ {
		 := .Layer([+1]).Nodes
		,  := 0, 0
		for  := 0;  < [+1]; ++ {
			 := []
			 := incidentToInnerSegment(, , , +1, )
			if  != [+1]-1 && ! {
				continue
			}
			 := [] - 1
			if  {
				 := .LeftNeighbors[.Node().ID]
				 = .NodeIndex[.Node([0].Node).ID]
			}
			for  <=  {
				 := []
				if !incidentToInnerSegment(, , , +1, ) {
					for ,  := range .LeftNeighbors[.Node().ID] {
						 := .NodeIndex[.Node(.Node).ID]
						if  <  ||  >  {
							[.Edge] = true
						}
					}
				}
				++
			}
			 = 
		}
	}
}

func incidentToInnerSegment(
	 *layered.LGraphArena,
	 *NeighborhoodInformation,
	 layered.LNodeID,
	,  int,
) bool {
	if .Node().Type != layered.LongEdgeNode {
		return false
	}
	for ,  := range .NodeIncomingEdges() {
		 := .EdgeSourceNode()
		if .Node().Type == layered.LongEdgeNode &&
			.LayerIndex[.Layer(*.Node().Layer).ID] ==  &&
			.LayerIndex[.Layer(*.Node().Layer).ID] ==  {
			return true
		}
	}
	return false
}

func createBalancedLayout(
	 *layered.LGraphArena,
	 layered.LGraphID,
	 []*BKAlignedLayout,
	 int,
) *BKAlignedLayout {
	 := NewBKAlignedLayout(, , VerticalBalanced, HorizontalBalanced)
	 := make([]float64, len())
	 := make([]float64, len())
	 := make([]float64, len())
	for  := range  {
		[] = float64(math.MaxInt32) // Java initializes min to Integer.MAX_VALUE.
		[] = float64(math.MinInt32)
	}
	 := 0
	for ,  := range  {
		[] = .LayoutSize()
		if [] > [] {
			 = 
		}
		for ,  := range .Graph().Layers {
			for ,  := range .Layer().Nodes {
				 := .Node().ID
				 := requireFloat(.Y[], "y") + requireFloat(.InnerShift[], "inner shift")
				[] = math.Min([], )
				[] = math.Max([], +.Node().Size.Y)
			}
		}
	}
	 := make([]float64, len())
	for ,  := range  {
		if .VDirection == VerticalDown {
			[] = [] - []
		} else {
			[] = [] - []
		}
	}
	 := make([]float64, len())
	for ,  := range .Graph().Layers {
		for ,  := range .Layer().Nodes {
			 := .Node().ID
			for ,  := range  {
				[] = requireFloat(.Y[], "y") +
					requireFloat(.InnerShift[], "inner shift") + []
			}
			sort.Float64s()
			.Y[] = floatPointer(([1] + [2]) / 2)
			.InnerShift[] = floatPointer(0)
		}
	}
	return 
}

func checkOrderConstraint(
	 *layered.LGraphArena,
	 layered.LGraphID,
	 *BKAlignedLayout,
) bool {
	for ,  := range .Graph().Layers {
		 := math.Inf(-1)
		for ,  := range .Layer().Nodes {
			 := .Node().ID
			 := requireFloat(.Y[], "y") + requireFloat(.InnerShift[], "inner shift") - .Node().Margin.Top
			 := requireFloat(.Y[], "y") + requireFloat(.InnerShift[], "inner shift") +
				.Node().Size.Y + .Node().Margin.Bottom
			if  <=  ||  <=  {
				return false
			}
			 = 
		}
	}
	return true
}