// Copyright (c) 2010, 2020 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 orthogonal

import (
	
	

	
)

// DetectCycles ports HyperEdgeCycleDetector.detectCycles. When criticalOnly
// is false, critical arcs are still protected from reversal.
func ( []*HyperEdgeSegment,  bool,  *javacompat.Random) []*HyperEdgeSegmentDependency {
	if  == nil {
		 = javacompat.NewRandom(1)
	}
	,  := initializeCycleDetector(, )
	computeLinearOrderingMarks(, , , , )

	 := make([]*HyperEdgeSegmentDependency, 0)
	for ,  := range  {
		for ,  := range .OutgoingDependencies {
			if (! || .Type == CriticalDependency) && .Mark > .Target.Mark {
				 = append(, )
			}
		}
	}
	return 
}

func initializeCycleDetector( []*HyperEdgeSegment,  bool) (,  []*HyperEdgeSegment) {
	 := -1
	for ,  := range  {
		.Mark = 
		--
		,  := 0, 0
		for ,  := range .IncomingDependencies {
			if .Type == CriticalDependency {
				 += .Weight
			}
		}
		for ,  := range .OutgoingDependencies {
			if .Type == CriticalDependency {
				 += .Weight
			}
		}
		.CriticalInWeight, .CriticalOutWeight = , 
		.InWeight, .OutWeight = , 
		if ! {
			.InWeight, .OutWeight = 0, 0
			for ,  := range .IncomingDependencies {
				.InWeight += .Weight
			}
			for ,  := range .OutgoingDependencies {
				.OutWeight += .Weight
			}
		}
		if .OutWeight == 0 {
			 = append(, )
		} else if .InWeight == 0 {
			 = append(, )
		}
	}
	return , 
}

func computeLinearOrderingMarks(
	, ,  []*HyperEdgeSegment,
	 bool,
	 *javacompat.Random,
) {
	// TreeSet orders the initial negative marks, so its stable iteration order
	// is the reverse of the input list. Mutating marks does not rebalance Java's
	// tree; we likewise retain this frozen order.
	 := append([]*HyperEdgeSegment(nil), ...)
	sort.SliceStable(, func(,  int) bool { return [].Mark < [].Mark })
	 := make(map[*HyperEdgeSegment]bool, len())
	for ,  := range  {
		[] = true
	}
	 := len()
	,  := -1, +1

	for len() > 0 {
		for len() > 0 {
			 := [0]
			 = [1:]
			if ![] {
				continue
			}
			delete(, )
			.Mark = 
			--
			,  = updateNeighbors(, , , )
		}
		for len() > 0 {
			 := [0]
			 = [1:]
			if ![] {
				continue
			}
			delete(, )
			.Mark = 
			++
			,  = updateNeighbors(, , , )
		}

		 := math.MinInt
		 := make([]*HyperEdgeSegment, 0)
		for ,  := range  {
			if ![] {
				continue
			}
			if ! && .CriticalOutWeight > 0 && .CriticalInWeight <= 0 {
				 = append([:0], )
				break
			}
			 := .OutWeight - .InWeight
			if  >=  {
				if  >  {
					 = [:0]
					 = 
				}
				 = append(, )
			}
		}
		if len() > 0 {
			 := [.NextIntN(int32(len()))]
			delete(, )
			.Mark = 
			++
			,  = updateNeighbors(, , , )
		}
	}

	 := len() + 1
	for ,  := range  {
		if .Mark <  {
			.Mark += 
		}
	}
}

func updateNeighbors(
	 *HyperEdgeSegment,
	,  []*HyperEdgeSegment,
	 bool,
) ([]*HyperEdgeSegment, []*HyperEdgeSegment) {
	for ,  := range .OutgoingDependencies {
		if  && .Type != CriticalDependency {
			continue
		}
		 := .Target
		if .Mark < 0 && .Weight > 0 {
			.InWeight -= .Weight
			if .Type == CriticalDependency {
				.CriticalInWeight -= .Weight
			}
			if .InWeight <= 0 && .OutWeight > 0 {
				 = append(, )
			}
		}
	}
	for ,  := range .IncomingDependencies {
		if  && .Type != CriticalDependency {
			continue
		}
		 := .Source
		if .Mark < 0 && .Weight > 0 {
			.OutWeight -= .Weight
			if .Type == CriticalDependency {
				.CriticalOutWeight -= .Weight
			}
			if .OutWeight <= 0 && .InWeight > 0 {
				 = append(, )
			}
		}
	}
	return , 
}

// BreakNonCriticalCycles removes zero-weight two-cycle arcs and reverses all
// other feedback arcs selected by ELK's cycle detector.
func ( []*HyperEdgeSegment,  *javacompat.Random) {
	for ,  := range DetectCycles(, false, ) {
		if .Weight == 0 {
			.Remove()
		} else {
			.Reverse()
		}
	}
}