package hierarchy

import (
	
	

	

	
)

const crossingComparisonPrecision = 0.0001

type crossingScratch struct {
	segments []layoutgraph.CrossingSegment
}

// The routines below are part of the implementation of the `ordering` procedure
// described in section `3. Vertex Ordering Within Ranks` of
// "A Technique for Drawing Directed Graphs" by Gansner et al.
// This is an iterative algorithm that tries to find the best node permutation (order) for each level
// for each iteration:
//     for each level
//         sort the nodes based on the `rank` of its connections
//         try swapping the nodes with their neighbors if crossings or length improve
//         recurse to children (sorting, swapping)
// main differences from the algorithm described in the paper:
// - they don't handle containers
// - they don't consider the edge lengths in case crossings stay the same
// - they consider only one direction when computing crossings

func initializeRanks( map[int][]*placementNode) {
	for  := 0;  < len(); ++ {
		computeLevelRanks([])
	}
}

// minimizes crossings iteratively. After minimization, recomputes the nodes ranks
func minimizeHierarchyCrossings( map[int][]*placementNode) {
	 := 0
	for ,  := range  {
		 = max(, len())
	}
	var  crossingScratch
	 := 
	for  := 0;  < ; ++ {
		for  := 0;  < len(); ++ {
			minimizeCrossings([], ,  > 0, &)
		}
	}
}

/*
This is the main routine to find the optimal node rank compared to its siblings.
Ranks are optimized considering edges above the given level.
|	Except for the first (top level), in which the optimization considers the edges below
Crossings take precedence to be optimized, then if they don't change, it tries to get the best length.
To find the best rank it first sorts the nodes so that it is "pulled" towards its connected neighbors in the direction under optimization.
Then, it tries to swap each node with its neighbors.
Once the nodes were ranked properly, if any of these nodes are containers, apply the same routine recursively to it's descendants.
The premise for containers is that they contain the same edges as their descendants so they are first placed at a proper rank.
Then, their descendants only need to be optimized against themselves without considering the container siblings.
*/
func minimizeCrossings( []*placementNode,  map[int][]*placementNode,  bool,  *crossingScratch) {
	sortLevelNodesByAdacencyPosition(, )
	computeLevelRanks([[0].level])
	 := .crossLevelSegments(, true, true)
	 := countCrossings()
	 := addLengths()
	for  := 0;  < len(); ++ {
		, ,  := bestIndexBySwappingNeighbors(, , , )
		if  <  {
			 = 
			 = 
			[], [] = [], []
		} else if  ==  && geo.PrecisionCompare(, , crossingComparisonPrecision) == -1 {
			 = 
			 = 
			[], [] = [], []
		}
		computeLevelRanks([[0].level])
	}
	for ,  := range  {
		if len(.children) > 0 && .optimizeChildrenCrossings {
			(.children, , , )
		}
	}
}

/*
Swap a given node with it's 3 neighbors to the right and returns the best crossing and index of this swap
This function returns the level nodes as they were, it does not change their position.
For the last nodes, it tries to swap them with the first ones in a sort of "circular" approach.
*/
func bestIndexBySwappingNeighbors( []*placementNode,  int,  map[int][]*placementNode,  *crossingScratch) (int64, float64, int) {
	 := int64(math.MaxInt64)
	 := math.Inf(1)
	 := 0
	for  :=  + 1;  < +4; ++ {
		// swap to count new crossings
		 :=  % len()
		[], [] = [], []
		computeLevelRanks([[].level])
		 := .crossLevelSegments(, true, true)
		 := countCrossings()
		 := addLengths()
		if  <  {
			 = 
			 = 
			 = 
		} else if  ==  && geo.PrecisionCompare(, , crossingComparisonPrecision) == -1 {
			 = 
			 = 
			 = 
		}
		// swap back, so that node[j] swaps with the next one
		[], [] = [], []
	}
	return , , 
}

// adjacentLevelNodes can be either the nodes above or below, depending on the optimization direction
func ( *crossingScratch) ( []*placementNode, ,  bool) []layoutgraph.CrossingSegment {
	 := 0
	iterAllDescendants(, func( *placementNode) {
		if  {
			 += len(.aboves)
		}
		if  {
			 += len(.belows)
		}
	})
	if cap(.segments) <  {
		.segments = make([]layoutgraph.CrossingSegment, 0, )
	} else {
		.segments = .segments[:0]
	}
	iterAllDescendants(, func( *placementNode) {
		if  {
			for  := range .aboves {
				.segments = append(.segments, layoutgraph.CrossingSegment{
					Start: geo.Point{X: float64(.rank), Y: float64(.level)},
					End:   geo.Point{X: float64(.rank), Y: float64(.level)},
				})
			}
		}
		if  {
			for  := range .belows {
				.segments = append(.segments, layoutgraph.CrossingSegment{
					Start: geo.Point{X: float64(.rank), Y: float64(.level)},
					End:   geo.Point{X: float64(.rank), Y: float64(.level)},
				})
			}
		}
	})
	slices.SortStableFunc(.segments, func(,  layoutgraph.CrossingSegment) int {
		if .Start.X == .Start.X {
			switch {
			case .End.X < .End.X:
				return -1
			case .End.X < .End.X:
				return 1
			default:
				return 0
			}
		}
		switch {
		case .Start.X < .Start.X:
			return -1
		case .Start.X < .Start.X:
			return 1
		default:
			return 0
		}
	})

	return .segments
}

func iterAllDescendants( []*placementNode,  func(*placementNode)) {
	for ,  := range  {
		()
	}
	for ,  := range  {
		(.children, )
	}
}

func allDescendants( []*placementNode,  bool) []*placementNode {
	 := make([]*placementNode, len())
	copy(, )
	for ,  := range  {
		if ! || .optimizeChildrenCrossings {
			 = append(, (.children, )...)
		}
	}
	return 
}

func addLengths( []layoutgraph.CrossingSegment) float64 {
	 := 0.0
	for ,  := range  {
		 += geo.EuclideanDistance(.Start.X, .Start.Y, .End.X, .End.Y)
	}
	return 
}

func countCrossings( []layoutgraph.CrossingSegment) int64 {
	return layoutgraph.CountSegmentCrossings()
}

func sortLevelNodesByAdacencyPosition( []*placementNode,  bool) {
	 := func( *placementNode) float64 {
		 := .aboves
		if ! {
			 = .belows
		}
		if len() == 0 {
			return 0
		}

		 := 0
		for  := range  {
			 += .rank
		}
		return float64() / float64(len())
	}

	slices.SortStableFunc(, func(,  *placementNode) int {
		 := ()
		 := ()
		switch {
		case  < :
			return -1
		case  < :
			return 1
		default:
			return 0
		}
	})
}

/*
Computes the nodes rank (index) from left to right as if they were sorted by TopLeft.X.
Ranking is performed by Depth First Search (DFS) adding nodes in reverse order.
By adding the nodes on the right first, they get stacked first and popped only after the nodes more on the left, yielding the desired
effect of processing the nodes on the left before the ones on the right
*/
func computeLevelRanks( []*placementNode) {
	 := make([]*placementNode, len())
	for  := 0;  < len(); ++ {
		[] = [len()--1]
	}
	for  := 0; len() > 0; ++ {
		 := [len()-1]
		 = [:len()-1]
		.rank = 
		for  := len(.children) - 1;  > -1; -- {
			 = append(, .children[])
		}
	}
}