package pijul
import (
	"fmt"
	"io"
)
// topologicalSort returns a slice of b and its children, sorted
// topologically.
// It uses the algorithm from
// https://en.wikipedia.org/wiki/Topological_sorting#Depth-first_search,
// except that cycles are treated like the end of a branch of the
// graph instead of causing the search to abort.
func topologicalSort(b *Block) []*Block {
	var list []*Block
	visited := make(map[*Block]bool)
	var visit func(*Block)
	visit = func(n *Block) {
		if visited[n] {
			return
		}
		visited[n] = true
		for _, e := range n.Edges {
			visit(e.To)
		}
		list = append(list, n)
	}
	visit(b)
	// Reverse the list.
	for i, j := 0, len(list)-1; i < j; i, j = i+1, j-1 {
		list[i], list[j] = list[j], list[i]
	}
	return list
}
func OutputFile(dest io.Writer, inode *Block) error {
	blocks := topologicalSort(inode)
	index := make(map[*Block]int, len(blocks))
	deleted := make([]bool, len(blocks))
	for i, b := range blocks {
		index[b] = i
		if b.ReverseEdges[0].Flag&EdgeFlagsDeleted != 0 {
			deleted[i] = true
		}
	}
	// These maps tell us how many conflicts begin (etc.) directly before the
	// specified index of blocks.
	conflictStart := make(map[int]int)
	conflictCenter := make(map[int]int)
	conflictEnd := make(map[int]int)
	for i, b := range blocks {
		if i == 0 {
			continue
		}
		hasEdge := false
		for _, e := range blocks[i-1].Edges {
			if e.To == b {
				hasEdge = true
				break
			}
		}
		if !hasEdge {
			// If this block is not a child of the previous block, the order between
			// them is undetermined, and therefore we have a conflict.
			// The conflict begins just after the closest parent of b.
			closestParent := -1
			for _, e := range b.ReverseEdges {
				parent := index[e.From]
				if parent > closestParent {
					closestParent = parent
				}
			}
			// The conflict ends just before the closest child of the previous block.
			closestChild := len(blocks)
			for _, e := range blocks[i-1].Edges {
				child := index[e.To]
				if child < closestChild {
					closestChild = child
				}
			}
			// If either side of the conflict consists entirely of deleted vertices,
			// it's not really a conflict.
			aliveBefore := false
			for j := closestParent + 1; j < i; j++ {
				if !deleted[j] {
					aliveBefore = true
					break
				}
			}
			aliveAfter := false
			for j := i; j < closestChild; j++ {
				if !deleted[j] {
					aliveAfter = true
					break
				}
			}
			if aliveBefore && aliveAfter {
				conflictStart[closestParent+1]++
				conflictCenter[i]++
				conflictEnd[closestChild]++
			}
		}
	}
	for i, b := range blocks {
		for j := 0; j < conflictEnd[i]; j++ {
			fmt.Fprintf(dest, ">>>>>>>\n")
		}
		for j := 0; j < conflictCenter[i]; j++ {
			fmt.Fprintf(dest, "======= %v\n", b.Change)
		}
		for j := 0; j < conflictStart[i]; j++ {
			fmt.Fprintf(dest, "<<<<<<< %v\n", b.Change)
		}
		if deleted[i] {
			continue
		}
		_, err := dest.Write(b.Content)
		if err != nil {
			return err
		}
	}
	return nil
}