// Copyright (c) 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 

type segmentSplitter struct{ generator *Generator }

type freeArea struct {
	start float64
	end   float64
	size  float64
}

type areaRating struct {
	dependencies int
	crossings    int
}

func ( *segmentSplitter) (
	 []*HyperEdgeSegmentDependency,
	 *[]*HyperEdgeSegment,
	 float64,
) {
	if len() == 0 {
		return
	}
	 := findFreeAreas(*, )
	 := decideWhichSegmentsToSplit()
	// Stream.sorted is stable, preserving LinkedHashSet insertion order on ties.
	sort.SliceStable(, func(,  int) bool { return [].Length() < [].Length() })
	for ,  := range  {
		.split(, , &, )
	}
}

func findFreeAreas( []*HyperEdgeSegment,  float64) []freeArea {
	 := make([]float64, 0)
	for ,  := range  {
		 = append(, .IncomingCoordinates...)
		 = append(, .OutgoingCoordinates...)
	}
	sort.Float64s()
	 := make([]freeArea, 0)
	for  := 1;  < len(); ++ {
		if []-[-1] >= 2* {
			 := [-1] + 
			 := [] - 
			 = append(, freeArea{start: , end: , size:  - })
		}
	}
	return 
}

func decideWhichSegmentsToSplit( []*HyperEdgeSegmentDependency) []*HyperEdgeSegment {
	 := make([]*HyperEdgeSegment, 0)
	 := make(map[*HyperEdgeSegment]bool)
	for ,  := range  {
		,  := .Source, .Target
		if [] || [] {
			continue
		}
		,  := , 
		if .RepresentsHyperedge() && !.RepresentsHyperedge() {
			,  = , 
		}
		 = append(, )
		[] = true
		.SplitBy = 
	}
	return 
}

func ( *segmentSplitter) (
	 *HyperEdgeSegment,
	 *[]*HyperEdgeSegment,
	 *[]freeArea,
	 float64,
) {
	 := .computePositionToSplitAndUpdateFreeAreas(, , )
	* = append(*, .splitAt())
	.updateDependencies(, *)
}

func ( *segmentSplitter) ( *HyperEdgeSegment,  []*HyperEdgeSegment) {
	,  := .SplitBy, .SplitPartner
	AddCriticalDependency(, )
	AddCriticalDependency(, )
	for ,  := range  {
		if  !=  &&  !=  &&  !=  {
			.generator.CreateDependencyIfNecessary(, )
			.generator.CreateDependencyIfNecessary(, )
		}
	}
}

func ( *segmentSplitter) (
	 *HyperEdgeSegment,
	 *[]freeArea,
	 float64,
) float64 {
	,  := -1, -1
	for ,  := range * {
		if .start > .End {
			break
		}
		if .end >= .Start {
			if  < 0 {
				 = 
			}
			 = 
		}
	}
	 := center(.Start, .End)
	if  >= 0 {
		 := .chooseBestAreaIndex(, *, , )
		 = center((*)[].start, (*)[].end)
		useArea(, , )
	}
	return 
}

func ( *segmentSplitter) (
	 *HyperEdgeSegment,
	 []freeArea,
	,  int,
) int {
	 := 
	if  <  {
		,  := .simulateSplit()
		 := []
		 := .rateArea(, , , )
		for  :=  + 1;  <= ; ++ {
			 := []
			 := .rateArea(, , , )
			if isBetterArea(, , , ) {
				,  = , 
				// ELK 0.8.1 does not update bestIndex here. This source bug is
				// observable and therefore intentionally retained for parity.
			}
		}
	}
	return 
}

func ( *segmentSplitter) (
	, ,  *HyperEdgeSegment,
	 freeArea,
) areaRating {
	 := center(.start, .end)
	.OutgoingCoordinates = append(.OutgoingCoordinates[:0], )
	.IncomingCoordinates = append(.IncomingCoordinates[:0], )
	 := areaRating{}
	for ,  := range .IncomingDependencies {
		.updateConsideringBothOrderings(&, , .Source)
		.updateConsideringBothOrderings(&, , .Source)
	}
	for ,  := range .OutgoingDependencies {
		.updateConsideringBothOrderings(&, , .Target)
		.updateConsideringBothOrderings(&, , .Target)
	}
	.dependencies += 2
	.crossings += countCrossingsForSingleOrdering(, .SplitBy)
	.crossings += countCrossingsForSingleOrdering(.SplitBy, )
	return 
}

func (*segmentSplitter) (
	 *areaRating,
	,  *HyperEdgeSegment,
) {
	 := countCrossingsForSingleOrdering(, )
	 := countCrossingsForSingleOrdering(, )
	if  ==  {
		if  > 0 {
			.dependencies += 2
			.crossings += 
		}
	} else {
		.dependencies++
		.crossings += minInt(, )
	}
}

func countCrossingsForSingleOrdering(,  *HyperEdgeSegment) int {
	return CountCrossings(.OutgoingCoordinates, .Start, .End) +
		CountCrossings(.IncomingCoordinates, .Start, .End)
}

func isBetterArea( freeArea,  areaRating,  freeArea,  areaRating) bool {
	if .crossings < .crossings {
		return true
	}
	if .crossings == .crossings {
		if .dependencies < .dependencies {
			return true
		}
		return .dependencies == .dependencies && .size > .size
	}
	return false
}

func useArea( *[]freeArea,  int,  float64) {
	 := (*)[]
	copy((*)[:], (*)[+1:])
	* = (*)[:len(*)-1]
	if .size/2 <  {
		return
	}
	 := center(.start, .end)
	 := make([]freeArea, 0, 2)
	 :=  - 
	if .start <=  {
		 = append(, freeArea{start: .start, end: , size:  - .start})
	}
	 :=  + 
	if  <= .end {
		 = append(, freeArea{start: , end: .end, size: .end - })
	}
	if len() > 0 {
		* = append(*, make([]freeArea, len())...)
		copy((*)[+len():], (*)[:len(*)-len()])
		copy((*)[:], )
	}
}

func center(,  float64) float64 { return ( + ) / 2 }