// 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 p3order

import (
	

	
)

type hyperedge struct {
	id                                           int
	edges                                        []layered.LEdgeID
	ports                                        []layered.LPortID
	upperLeft, lowerLeft, upperRight, lowerRight int
}

type cornerType uint8

const (
	upperCorner cornerType = iota
	lowerCorner
)

type hyperedgeCorner struct {
	hyperedge        int
	position         int
	oppositePosition int
	typeOf           cornerType
}

// countHyperedgeCrossings implements the ELK 0.8.1 DIAGRAMS 2014 estimate.
// Java's final identity-hash tiebreak is represented by hyperedge creation
// order, which is also the stable identity order produced by GWT's runtime.
func countHyperedgeCrossings(
	 *layered.LGraphArena,
	 []int,
	,  []layered.LNodeID,
) int {
	if len() == 0 || len() == 0 {
		return 0
	}
	 := 0
	for ,  := range  {
		for ,  := range .Node().Ports {
			 := 0
			for ,  := range .Port().OutgoingEdges {
				if !sameLayer(.Node().Layer, .Node(.EdgeTargetNode()).Layer) {
					++
				}
			}
			if  > 0 {
				[.Port().ID] = 
				++
			}
		}
	}

	 := 0
	for ,  := range  {
		 := 0
		for ,  := range .Node().Ports {
			if .Port().Side != layered.NorthSide {
				break
			}
			for ,  := range .Port().IncomingEdges {
				if !sameLayer(.Node().Layer, .Node(.EdgeSourceNode()).Layer) {
					++
					break
				}
			}
		}
		 := 0
		 := .Node().Ports
		for  := len() - 1;  >= 0; -- {
			 := []
			 := 0
			for ,  := range .Port().IncomingEdges {
				if !sameLayer(.Node().Layer, .Node(.EdgeSourceNode()).Layer) {
					++
				}
			}
			if  == 0 {
				continue
			}
			if .Port().Side == layered.NorthSide {
				[.Port().ID] = 
				++
			} else {
				[.Port().ID] =  +  + 
				++
			}
		}
		 += 
	}

	 := make([]hyperedge, 0)
	 := make(map[layered.LPortID]int)
	 := make([]int, 0)
	for ,  := range  {
		for ,  := range .Node().Ports {
			for ,  := range .Port().OutgoingEdges {
				 := *.Edge().Target
				 := *.Port().Node
				if sameLayer(.Node().Layer, .Node().Layer) {
					continue
				}
				,  := []
				,  := []
				switch {
				case ! && !:
					 := len()
					 = append(, hyperedge{
						id: , edges: []layered.LEdgeID{},
						ports: []layered.LPortID{, },
					})
					 = append(, )
					[], [] = , 
				case !:
					[].edges = append([].edges, )
					[].ports = append([].ports, )
					[] = 
				case !:
					[].edges = append([].edges, )
					[].ports = append([].ports, )
					[] = 
				case  == :
					[].edges = append([].edges, )
				default:
					[].edges = append([].edges, )
					for ,  := range [].ports {
						[] = 
					}
					[].edges = append([].edges, [].edges...)
					[].ports = append([].ports, [].ports...)
					 = removeHyperedge(, )
				}
			}
		}
	}

	,  := .Node([0]).Layer, .Node([0]).Layer
	for ,  := range  {
		[].upperLeft = 
		[].upperRight = 
		for ,  := range [].ports {
			 := [.Port().ID]
			 := .Node(*.Port().Node).Layer
			if sameLayer(, ) {
				if  < [].upperLeft {
					[].upperLeft = 
				}
				if  > [].lowerLeft {
					[].lowerLeft = 
				}
			} else if sameLayer(, ) {
				if  < [].upperRight {
					[].upperRight = 
				}
				if  > [].lowerRight {
					[].lowerRight = 
				}
			}
		}
	}

	 := append([]int(nil), ...)
	sort.SliceStable(, func(,  int) bool {
		,  := [[]], [[]]
		if .upperLeft != .upperLeft {
			return .upperLeft < .upperLeft
		}
		if .upperRight != .upperRight {
			return .upperRight < .upperRight
		}
		return .id < .id
	})

	 := make([]int, len())
	 := make([]int, +1)
	for ,  := range  {
		[] = [].upperRight
		[[]] = 1
	}
	 := 0
	for  := range  {
		if [] == 1 {
			[] = 
		} else {
			--
		}
	}
	 := 0
	for  := range  {
		 := []
		[] += []
		 = maxInt(, []+1)
	}

	 := 1
	for  <  {
		 *= 2
	}
	 := make([]int, 2*-1)
	--
	 := 0
	for ,  := range  {
		 :=  + 
		[]++
		for  > 0 {
			if %2 > 0 {
				 += [+1]
			}
			 = ( - 1) / 2
			[]++
		}
	}

	 := make([]hyperedgeCorner, 0, len()*2)
	 := make([]hyperedgeCorner, 0, len()*2)
	for ,  := range  {
		 := []
		 = append(,
			hyperedgeCorner{.id, .upperLeft, .lowerLeft, upperCorner},
			hyperedgeCorner{.id, .lowerLeft, .upperLeft, lowerCorner},
		)
		 = append(,
			hyperedgeCorner{.id, .upperRight, .lowerRight, upperCorner},
			hyperedgeCorner{.id, .lowerRight, .upperRight, lowerCorner},
		)
	}
	 += countCornerOverlaps()
	 += countCornerOverlaps()
	return 
}

func countCornerOverlaps( []hyperedgeCorner) int {
	sort.SliceStable(, func(,  int) bool {
		,  := [], []
		if .position != .position {
			return .position < .position
		}
		if .oppositePosition != .oppositePosition {
			return .oppositePosition < .oppositePosition
		}
		if .hyperedge != .hyperedge {
			return .hyperedge < .hyperedge
		}
		return .typeOf < .typeOf
	})
	,  := 0, 0
	for ,  := range  {
		if .typeOf == upperCorner {
			++
		} else {
			--
			 += 
		}
	}
	return 
}

func removeHyperedge( []int,  int) []int {
	for ,  := range  {
		if  ==  {
			return append([:], [+1:]...)
		}
	}
	return 
}

func sameLayer(,  *layered.LayerID) bool {
	if  == nil ||  == nil {
		return  == nil &&  == nil
	}
	return * == *
}

func maxInt(,  int) int {
	if  >  {
		return 
	}
	return 
}