func sortedSolutionKeys(conflictSolution map[string]MergeSolution) []string {
	orderedKeys := make([]struct {
		number int64
		key    string
	}, len(conflictSolution))
	i := 0
	for key := range conflictSolution {
		match := extractKeyNumber.FindStringSubmatch(key)
		number, _ := strconv.ParseInt(match[0], 0, 64)
		orderedKeys[i] = struct {
			number int64
			key    string
		}{
			number: number,
			key:    key,
		}
		i++
	}
	sort.Slice(orderedKeys, func(i int, j int) bool {
		return orderedKeys[i].number < orderedKeys[j].number
	})
	result := make([]string, len(orderedKeys))
	for i, ordered := range orderedKeys {
		result[i] = ordered.key
	}
	return result
}
sortedSolutionKeys returns a list of keys from the conflictSolution map,
where the keys are sorted by the first number-part of a key (i.e.
12345_uniqueKey would be sorted according to 12345).
package merger
import (
	"fmt"
	"reflect"
	"regexp"
	"sort"
	"strconv"
	"strings"
	"time"
	"github.com/AndreasSko/go-jwlm/model"
)
type brFrom struct {
	side MergeSide
	br   *model.BlockRange
}
type umbrFrom struct {
	side MergeSide
	umbr []*model.UserMarkBlockRange
}
func MergeUserMarkAndBlockRange(leftUM []*model.UserMark, leftBR []*model.BlockRange,
	rightUM []*model.UserMark, rightBR []*model.BlockRange,
	conflictSolution map[string]MergeSolution) ([]*model.UserMark, []*model.BlockRange, IDChanges, error) {
	if conflictSolution == nil {
		conflictSolution = map[string]MergeSolution{}
	}
	left := joinToUserMarkBlockRange(leftUM, leftBR)
	right := joinToUserMarkBlockRange(rightUM, rightBR)
	var merged []*model.UserMarkBlockRange
	var changes IDChanges
	var err error
	for {
		merged, changes, err = mergeUMBR(left, right, conflictSolution)
		if err == nil {
			um, br := splitUserMarkBlockRange(merged)
			return um, br, changes, nil
		}
		switch err := err.(type) {
		case MergeConflictError:
			autoConflictSolution, sErr := solveEqualityMergeConflict(err.Conflicts)
			for key, autoSol := range autoConflictSolution {
				conflictSolution[key] = autoSol
			}
			if sErr == nil {
				continue
			}
			if reflect.DeepEqual(err.Conflicts, sErr.(MergeConflictError).Conflicts) {
				return nil, nil, IDChanges{}, sErr
			}
		default:
			return nil, nil, IDChanges{}, err
		}
	}
}
func mergeUMBR(left []*model.UserMarkBlockRange, right []*model.UserMarkBlockRange,
	conflictSolution map[string]MergeSolution) ([]*model.UserMarkBlockRange, IDChanges, error) {
	changes, invertedChanges := replaceUMBRConflictsWithSolution(&left, &right, conflictSolution)
	conflicts := map[string]MergeConflict{}
	blRanges := ingestUMBR(left, right)
	for _, locationBlock := range blRanges {
		for _, identifierBlock := range locationBlock {
			identifierBlock, moreConflicts := detectAndFilterDuplicateBRs(identifierBlock, left, right)
			for key, value := range moreConflicts {
				conflicts[key] = value
			}
			for i := 0; i < len(identifierBlock); i++ {
				br := identifierBlock[i]
			Loop:
				for j := i + 1; j < len(identifierBlock) && br.br.EndToken.Int32 >= identifierBlock[j].br.StartToken.Int32; j++ {
					if br.side == identifierBlock[j].side {
						continue
					}
					var first, second *model.UserMarkBlockRange
					if br.side == LeftSide {
						first = left[br.br.UserMarkID]
						second = right[identifierBlock[j].br.UserMarkID]
					} else {
						first = left[identifierBlock[j].br.UserMarkID]
						second = right[br.br.UserMarkID]
					}
					var conflictKey strings.Builder
					conflictKey.Grow(160)
					conflictKey.WriteString(fmt.Sprint(time.Now().UnixNano()))
					conflictKey.WriteString("_")
					conflictKey.WriteString(first.UniqueKey())
					conflictKey.WriteString("_")
					conflictKey.WriteString(second.UniqueKey())
					conflicts[conflictKey.String()] = MergeConflict{first, second}
					for ; i < len(identifierBlock); i++ {
						if identifierBlock[i].br.StartToken.Int32 > identifierBlock[j].br.EndToken.Int32 {
							break Loop
						}
					}
				}
			}
		}
	}
	if len(conflicts) > 0 {
		return []*model.UserMarkBlockRange{}, IDChanges{}, MergeConflictError{Conflicts: conflicts}
	}
	result := make([]*model.UserMarkBlockRange, len(left)+len(right)+2)
	i := 1
	for _, mergeSide := range []MergeSide{LeftSide, RightSide} {
		var side []*model.UserMarkBlockRange
		if mergeSide == LeftSide {
			side = left
		} else {
			side = right
		}
		for _, entry := range side {
			if entry == nil {
				continue
			}
			entry = model.MakeModelCopy(entry).(*model.UserMarkBlockRange)
			if entry.ID() != i {
				if mergeSide == LeftSide {
					if val, ok := invertedChanges.Right[entry.ID()]; ok {
						changes.Right[val] = i
					}
					changes.Left[entry.ID()] = i
				} else {
					if val, ok := invertedChanges.Left[entry.ID()]; ok {
						changes.Left[val] = i
					}
					changes.Right[entry.ID()] = i
				}
			}
			result[i] = entry
			result[i].SetID(i)
			i++
		}
	}
	return result[:i], changes, nil
}
func detectAndFilterDuplicateBRs(idBlock []brFrom, left []*model.UserMarkBlockRange,
	right []*model.UserMarkBlockRange) ([]brFrom, map[string]MergeConflict) {
	conflicts := map[string]MergeConflict{}
	idBlock = sortBRFroms(idBlock)
	for i := 0; i < len(idBlock); i++ {
		if idBlock[i] == (brFrom{}) {
			continue
		}
		for j := i + 1; j < len(idBlock); j++ {
			if idBlock[j] == (brFrom{}) {
				continue
			}
			if idBlock[j].br.StartToken.Int32 > idBlock[i].br.EndToken.Int32 {
				break
			}
			if idBlock[i].br.BlockType == idBlock[j].br.BlockType &&
				idBlock[i].br.Identifier == idBlock[j].br.Identifier &&
				idBlock[i].br.StartToken.Int32 == idBlock[j].br.StartToken.Int32 &&
				idBlock[i].br.EndToken.Int32 == idBlock[j].br.EndToken.Int32 {
				if idBlock[i].side == idBlock[j].side {
					continue
				}
				var first, second *model.UserMarkBlockRange
				if idBlock[i].side == LeftSide {
					first = left[idBlock[i].br.UserMarkID]
					second = right[idBlock[j].br.UserMarkID]
				} else {
					first = left[idBlock[j].br.UserMarkID]
					second = right[idBlock[i].br.UserMarkID]
				}
				if !first.UserMark.Equals(second.UserMark) {
					continue
				}
				var conflictKey strings.Builder
				conflictKey.WriteString(fmt.Sprint(time.Now().UnixNano()))
				conflictKey.WriteString("_")
				conflictKey.WriteString(first.UniqueKey())
				conflictKey.WriteString("_")
				conflictKey.WriteString(second.UniqueKey())
				conflicts[conflictKey.String()] = MergeConflict{first, second}
				idBlock[j] = brFrom{}
			}
		}
	}
	idBlock = sortBRFroms(idBlock)
	return idBlock, conflicts
}
func sortBRFroms(entries []brFrom) []brFrom {
	sort.SliceStable(entries, func(i, j int) bool {
		if entries[i] == (brFrom{}) {
			return false
		}
		if entries[j] == (brFrom{}) {
			return true
		}
		return entries[i].br.StartToken.Int32 < entries[j].br.StartToken.Int32
	})
	emptyEntries := 0
	for i := len(entries) - 1; i >= 0; i-- {
		if entries[i] != (brFrom{}) {
			break
		}
		emptyEntries++
	}
	return entries[:len(entries)-emptyEntries]
}
func replaceUMBRConflictsWithSolution(left *[]*model.UserMarkBlockRange, right *[]*model.UserMarkBlockRange, conflictSolution map[string]MergeSolution) (IDChanges, IDChanges) {
	changes := IDChanges{
		Left:  map[int]int{},
		Right: map[int]int{},
	}
	invertedChanges := IDChanges{
		Left:  map[int]int{},
		Right: map[int]int{},
	}
	sortedKeys := sortedSolutionKeys(conflictSolution)
	for _, key := range sortedKeys {
		sol := conflictSolution[key]
		var side, other *[]*model.UserMarkBlockRange
		if _, ok := sol.Solution.(*model.UserMarkBlockRange); !ok {
			continue
		}
		if _, ok := sol.Discarded.(*model.UserMarkBlockRange); !ok {
			continue
		}
		if sol.Side == LeftSide {
			side = left
			other = right
			changes.Right[sol.Discarded.ID()] = sol.Solution.ID()
			invertedChanges.Right[sol.Solution.ID()] = sol.Discarded.ID()
		} else {
			side = right
			other = left
			changes.Left[sol.Discarded.ID()] = sol.Solution.ID()
			invertedChanges.Left[sol.Solution.ID()] = sol.Discarded.ID()
		}
		(*side)[sol.Solution.ID()] = (sol.Solution).(*model.UserMarkBlockRange)
		(*other)[sol.Discarded.ID()] = nil
	}
	return changes, invertedChanges
}
var extractKeyNumber = regexp.MustCompile(`^(\d*)`)