func diffListsOfScalars(original, modified []interface{}, diffOptions DiffOptions) ([]interface{}, []interface{}, error) {
	modifiedCopy := make([]interface{}, len(modified))
	copy(modifiedCopy, modified)
	originalScalars := sortScalars(original)
	modifiedScalars := sortScalars(modifiedCopy)
	originalIndex, modifiedIndex := 0, 0
	addList := []interface{}{}
	deletionList := []interface{}{}
	for {
		originalInBounds := originalIndex < len(originalScalars)
		modifiedInBounds := modifiedIndex < len(modifiedScalars)
		if !originalInBounds && !modifiedInBounds {
			break
		}
		var originalString, modifiedString string
		var originalValue, modifiedValue interface{}
		if originalInBounds {
			originalValue = originalScalars[originalIndex]
			originalString = fmt.Sprintf("%v", originalValue)
		}
		if modifiedInBounds {
			modifiedValue = modifiedScalars[modifiedIndex]
			modifiedString = fmt.Sprintf("%v", modifiedValue)
		}
		originalV, modifiedV := compareListValuesAtIndex(originalInBounds, modifiedInBounds, originalString, modifiedString)
		switch {
		case originalV == nil && modifiedV == nil:
			originalIndex++
			modifiedIndex++
		case originalV != nil && modifiedV == nil:
			if !diffOptions.IgnoreDeletions {
				deletionList = append(deletionList, originalValue)
			}
			originalIndex++
		case originalV == nil && modifiedV != nil:
			if !diffOptions.IgnoreChangesAndAdditions {
				addList = append(addList, modifiedValue)
			}
			modifiedIndex++
		default:
			return nil, nil, fmt.Errorf("Unexpected returned value from compareListValuesAtIndex: %v and %v", originalV, modifiedV)
		}
	}
	return addList, deduplicateScalars(deletionList), nil
}
diffListsOfScalars returns 2 lists, the first one is addList and the second one is deletionList.
Argument diffOptions.IgnoreChangesAndAdditions controls if calculate addList. true means not calculate.
Argument diffOptions.IgnoreDeletions controls if calculate deletionList. true means not calculate.
original may be changed, but modified is guaranteed to not be changed
package strategicpatch
import (
	"fmt"
	"reflect"
	"sort"
	"strings"
	"k8s.io/apimachinery/pkg/apis/meta/v1/unstructured"
	"k8s.io/apimachinery/pkg/util/json"
	"k8s.io/apimachinery/pkg/util/mergepatch"
)
const (
	directiveMarker  = "$patch"
	deleteDirective  = "delete"
	replaceDirective = "replace"
	mergeDirective   = "merge"
	retainKeysStrategy = "retainKeys"
	deleteFromPrimitiveListDirectivePrefix = "$deleteFromPrimitiveList"
	retainKeysDirective                    = "$" + retainKeysStrategy
	setElementOrderDirectivePrefix         = "$setElementOrder"
)
type JSONMap map[string]interface{}
type DiffOptions struct {
	SetElementOrder bool
	IgnoreChangesAndAdditions bool
	IgnoreDeletions bool
	BuildRetainKeysDirective bool
}
type MergeOptions struct {
	MergeParallelList bool
	IgnoreUnmatchedNulls bool
}
func CreateTwoWayMergePatch(original, modified []byte, dataStruct interface{}, fns ...mergepatch.PreconditionFunc) ([]byte, error) {
	schema, err := NewPatchMetaFromStruct(dataStruct)
	if err != nil {
		return nil, err
	}
	return CreateTwoWayMergePatchUsingLookupPatchMeta(original, modified, schema, fns...)
}
func CreateTwoWayMergePatchUsingLookupPatchMeta(
	original, modified []byte, schema LookupPatchMeta, fns ...mergepatch.PreconditionFunc) ([]byte, error) {
	originalMap := map[string]interface{}{}
	if len(original) > 0 {
		if err := json.Unmarshal(original, &originalMap); err != nil {
			return nil, mergepatch.ErrBadJSONDoc
		}
	}
	modifiedMap := map[string]interface{}{}
	if len(modified) > 0 {
		if err := json.Unmarshal(modified, &modifiedMap); err != nil {
			return nil, mergepatch.ErrBadJSONDoc
		}
	}
	patchMap, err := CreateTwoWayMergeMapPatchUsingLookupPatchMeta(originalMap, modifiedMap, schema, fns...)
	if err != nil {
		return nil, err
	}
	return json.Marshal(patchMap)
}
func CreateTwoWayMergeMapPatch(original, modified JSONMap, dataStruct interface{}, fns ...mergepatch.PreconditionFunc) (JSONMap, error) {
	schema, err := NewPatchMetaFromStruct(dataStruct)
	if err != nil {
		return nil, err
	}
	return CreateTwoWayMergeMapPatchUsingLookupPatchMeta(original, modified, schema, fns...)
}
func CreateTwoWayMergeMapPatchUsingLookupPatchMeta(original, modified JSONMap, schema LookupPatchMeta, fns ...mergepatch.PreconditionFunc) (JSONMap, error) {
	diffOptions := DiffOptions{
		SetElementOrder: true,
	}
	patchMap, err := diffMaps(original, modified, schema, diffOptions)
	if err != nil {
		return nil, err
	}
	for _, fn := range fns {
		if !fn(patchMap) {
			return nil, mergepatch.NewErrPreconditionFailed(patchMap)
		}
	}
	return patchMap, nil
}
func diffMaps(original, modified map[string]interface{}, schema LookupPatchMeta, diffOptions DiffOptions) (map[string]interface{}, error) {
	patch := map[string]interface{}{}
	retainKeysList := make([]interface{}, 0, len(modified))
	for key, modifiedValue := range modified {
		if diffOptions.BuildRetainKeysDirective && modifiedValue != nil {
			retainKeysList = append(retainKeysList, key)
		}
		originalValue, ok := original[key]
		if !ok {
			if !diffOptions.IgnoreChangesAndAdditions {
				patch[key] = modifiedValue
			}
			continue
		}
		foundDirectiveMarker, err := handleDirectiveMarker(key, originalValue, modifiedValue, patch)
		if err != nil {
			return nil, err
		}
		if foundDirectiveMarker {
			continue
		}
		if reflect.TypeOf(originalValue) != reflect.TypeOf(modifiedValue) {
			if !diffOptions.IgnoreChangesAndAdditions {
				patch[key] = modifiedValue
			}
			continue
		}
		switch originalValueTyped := originalValue.(type) {
		case map[string]interface{}:
			modifiedValueTyped := modifiedValue.(map[string]interface{})
			err = handleMapDiff(key, originalValueTyped, modifiedValueTyped, patch, schema, diffOptions)
		case []interface{}:
			modifiedValueTyped := modifiedValue.([]interface{})
			err = handleSliceDiff(key, originalValueTyped, modifiedValueTyped, patch, schema, diffOptions)
		default:
			replacePatchFieldIfNotEqual(key, originalValue, modifiedValue, patch, diffOptions)
		}
		if err != nil {
			return nil, err
		}
	}
	updatePatchIfMissing(original, modified, patch, diffOptions)
	if len(retainKeysList) > 0 &&
		(len(patch) > 0 || hasAdditionalNewField(original, modified)) {
		patch[retainKeysDirective] = sortScalars(retainKeysList)
	}
	return patch, nil
}
func handleDirectiveMarker(key string, originalValue, modifiedValue interface{}, patch map[string]interface{}) (bool, error) {
	if key == directiveMarker {
		originalString, ok := originalValue.(string)
		if !ok {
			return false, fmt.Errorf("invalid value for special key: %s", directiveMarker)
		}
		modifiedString, ok := modifiedValue.(string)
		if !ok {
			return false, fmt.Errorf("invalid value for special key: %s", directiveMarker)
		}
		if modifiedString != originalString {
			patch[directiveMarker] = modifiedValue
		}
		return true, nil
	}
	return false, nil
}
func handleMapDiff(key string, originalValue, modifiedValue, patch map[string]interface{},
	schema LookupPatchMeta, diffOptions DiffOptions) error {
	subschema, patchMeta, err := schema.LookupPatchMetadataForStruct(key)
	if err != nil {
		if reflect.DeepEqual(originalValue, modifiedValue) {
			return nil
		}
		return err
	}
	retainKeys, patchStrategy, err := extractRetainKeysPatchStrategy(patchMeta.GetPatchStrategies())
	if err != nil {
		return err
	}
	diffOptions.BuildRetainKeysDirective = retainKeys
	switch patchStrategy {
	case replaceDirective:
		if !diffOptions.IgnoreChangesAndAdditions {
			patch[key] = modifiedValue
		}
	default:
		patchValue, err := diffMaps(originalValue, modifiedValue, subschema, diffOptions)
		if err != nil {
			return err
		}
		if len(patchValue) > 0 {
			patch[key] = patchValue
		}
	}
	return nil
}
func handleSliceDiff(key string, originalValue, modifiedValue []interface{}, patch map[string]interface{},
	schema LookupPatchMeta, diffOptions DiffOptions) error {
	subschema, patchMeta, err := schema.LookupPatchMetadataForSlice(key)
	if err != nil {
		if reflect.DeepEqual(originalValue, modifiedValue) {
			return nil
		}
		return err
	}
	retainKeys, patchStrategy, err := extractRetainKeysPatchStrategy(patchMeta.GetPatchStrategies())
	if err != nil {
		return err
	}
	switch patchStrategy {
	case mergeDirective:
		diffOptions.BuildRetainKeysDirective = retainKeys
		addList, deletionList, setOrderList, err := diffLists(originalValue, modifiedValue, subschema, patchMeta.GetPatchMergeKey(), diffOptions)
		if err != nil {
			return err
		}
		if len(addList) > 0 {
			patch[key] = addList
		}
		if len(deletionList) > 0 {
			parallelDeletionListKey := fmt.Sprintf("%s/%s", deleteFromPrimitiveListDirectivePrefix, key)
			patch[parallelDeletionListKey] = deletionList
		}
		if len(setOrderList) > 0 {
			parallelSetOrderListKey := fmt.Sprintf("%s/%s", setElementOrderDirectivePrefix, key)
			patch[parallelSetOrderListKey] = setOrderList
		}
	default:
		replacePatchFieldIfNotEqual(key, originalValue, modifiedValue, patch, diffOptions)
	}
	return nil
}
func replacePatchFieldIfNotEqual(key string, original, modified interface{},
	patch map[string]interface{}, diffOptions DiffOptions) {
	if diffOptions.IgnoreChangesAndAdditions {
		return
	}
	if reflect.DeepEqual(original, modified) {
		return
	}
	patch[key] = modified
}
func updatePatchIfMissing(original, modified, patch map[string]interface{}, diffOptions DiffOptions) {
	if diffOptions.IgnoreDeletions {
		return
	}
	for key := range original {
		if _, found := modified[key]; !found {
			patch[key] = nil
		}
	}
}
func validateMergeKeyInLists(mergeKey string, lists ...[]interface{}) error {
	for _, list := range lists {
		for _, item := range list {
			m, ok := item.(map[string]interface{})
			if !ok {
				return mergepatch.ErrBadArgType(m, item)
			}
			if _, ok = m[mergeKey]; !ok {
				return mergepatch.ErrNoMergeKey(m, mergeKey)
			}
		}
	}
	return nil
}
func normalizeElementOrder(patch, serverOnly, patchOrder, serverOrder []interface{}, mergeKey string, kind reflect.Kind) ([]interface{}, error) {
	patch, err := normalizeSliceOrder(patch, patchOrder, mergeKey, kind)
	if err != nil {
		return nil, err
	}
	serverOnly, err = normalizeSliceOrder(serverOnly, serverOrder, mergeKey, kind)
	if err != nil {
		return nil, err
	}
	all := mergeSortedSlice(serverOnly, patch, serverOrder, mergeKey, kind)
	return all, nil
}
func mergeSortedSlice(left, right, serverOrder []interface{}, mergeKey string, kind reflect.Kind) []interface{} {
	less := func(l, r interface{}) (bool, bool) {
		li := index(serverOrder, l, mergeKey, kind)
		ri := index(serverOrder, r, mergeKey, kind)
		if li >= 0 && ri >= 0 {
			return li < ri, true
		} else {
			return false, false
		}
	}
	size := len(left) + len(right)
	i, j := 0, 0
	s := make([]interface{}, size, size)
	for k := 0; k < size; k++ {
		if i >= len(left) && j < len(right) {
			s[k] = right[j]
			j++
		} else if j >= len(right) && i < len(left) {
			s[k] = left[i]
			i++
		} else {
			less, foundBoth := less(left[i], right[j])
			if foundBoth && less {
				s[k] = left[i]
				i++
			} else {
				s[k] = right[j]
				j++
			}
		}
	}
	return s
}
func index(l []interface{}, valToLookUp interface{}, mergeKey string, kind reflect.Kind) int {
	var getValFn func(interface{}) interface{}
	switch kind {
	case reflect.Map:
		getValFn = func(item interface{}) interface{} {
			typedItem, ok := item.(map[string]interface{})
			if !ok {
				return nil
			}
			val := typedItem[mergeKey]
			return val
		}
	default:
		getValFn = func(item interface{}) interface{} {
			return item
		}
	}
	for i, v := range l {
		if getValFn(valToLookUp) == getValFn(v) {
			return i
		}
	}
	return -1
}
func extractToDeleteItems(l []interface{}) ([]interface{}, []interface{}, error) {
	var nonDelete, toDelete []interface{}
	for _, v := range l {
		m, ok := v.(map[string]interface{})
		if !ok {
			return nil, nil, mergepatch.ErrBadArgType(m, v)
		}
		directive, foundDirective := m[directiveMarker]
		if foundDirective && directive == deleteDirective {
			toDelete = append(toDelete, v)
		} else {
			nonDelete = append(nonDelete, v)
		}
	}
	return nonDelete, toDelete, nil
}
func normalizeSliceOrder(toSort, order []interface{}, mergeKey string, kind reflect.Kind) ([]interface{}, error) {
	var toDelete []interface{}
	if kind == reflect.Map {
		err := validateMergeKeyInLists(mergeKey, toSort, order)
		if err != nil {
			return nil, err
		}
		toSort, toDelete, err = extractToDeleteItems(toSort)
		if err != nil {
			return nil, err
		}
	}
	sort.SliceStable(toSort, func(i, j int) bool {
		if ii := index(order, toSort[i], mergeKey, kind); ii >= 0 {
			if ij := index(order, toSort[j], mergeKey, kind); ij >= 0 {
				return ii < ij
			}
		}
		return true
	})
	toSort = append(toSort, toDelete...)
	return toSort, nil
}
func diffLists(original, modified []interface{}, schema LookupPatchMeta, mergeKey string, diffOptions DiffOptions) ([]interface{}, []interface{}, []interface{}, error) {
	if len(original) == 0 {
		if len(modified) == 0 || diffOptions.IgnoreChangesAndAdditions {
			return nil, nil, nil, nil
		}
		return modified, nil, nil, nil
	}
	elementType, err := sliceElementType(original, modified)
	if err != nil {
		return nil, nil, nil, err
	}
	var patchList, deleteList, setOrderList []interface{}
	kind := elementType.Kind()
	switch kind {
	case reflect.Map:
		patchList, deleteList, err = diffListsOfMaps(original, modified, schema, mergeKey, diffOptions)
		if err != nil {
			return nil, nil, nil, err
		}
		patchList, err = normalizeSliceOrder(patchList, modified, mergeKey, kind)
		if err != nil {
			return nil, nil, nil, err
		}
		orderSame, err := isOrderSame(original, modified, mergeKey)
		if err != nil {
			return nil, nil, nil, err
		}
		patchList = append(patchList, deleteList...)
		deleteList = nil
		if diffOptions.SetElementOrder &&
			((!diffOptions.IgnoreChangesAndAdditions && (len(patchList) > 0 || !orderSame)) ||
				(!diffOptions.IgnoreDeletions && len(patchList) > 0)) {
			setOrderList = make([]interface{}, len(modified))
			for i, v := range modified {
				typedV := v.(map[string]interface{})
				setOrderList[i] = map[string]interface{}{
					mergeKey: typedV[mergeKey],
				}
			}
		}
	case reflect.Slice:
		return nil, nil, nil, mergepatch.ErrNoListOfLists
	default:
		patchList, deleteList, err = diffListsOfScalars(original, modified, diffOptions)
		if err != nil {
			return nil, nil, nil, err
		}
		patchList, err = normalizeSliceOrder(patchList, modified, mergeKey, kind)
		if diffOptions.SetElementOrder && ((!diffOptions.IgnoreDeletions && len(deleteList) > 0) ||
			(!diffOptions.IgnoreChangesAndAdditions && !reflect.DeepEqual(original, modified))) {
			setOrderList = modified
		}
	}
	return patchList, deleteList, setOrderList, err
}
func isOrderSame(original, modified []interface{}, mergeKey string) (bool, error) {
	if len(original) != len(modified) {
		return false, nil
	}
	for i, modifiedItem := range modified {
		equal, err := mergeKeyValueEqual(original[i], modifiedItem, mergeKey)
		if err != nil || !equal {
			return equal, err
		}
	}
	return true, nil
}