// Licensed to the Apache Software Foundation (ASF) under one
// or more contributor license agreements.  See the NOTICE file
// distributed with this work for additional information
// regarding copyright ownership.  The ASF licenses this file
// to you under the Apache License, Version 2.0 (the
// "License"); you may not use this file except in compliance
// with the License.  You may obtain a copy of the License at
//
// http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

package array

import (
	
	

	
)

// Edit represents one entry in the edit script to compare two arrays.
type Edit struct {
	Insert    bool
	RunLength int64
}

// Edits is a slice of Edit structs that represents an edit script to compare two arrays.
// When applied to the base array, it produces the target array.
// Each element of "insert" determines whether an element was inserted into (true)
// or deleted from (false) base. Each insertion or deletion is followed by a run of
// elements which are unchanged from base to target; the length of this run is stored
// in RunLength. (Note that the edit script begins and ends with a run of shared
// elements but both fields of the struct must have the same length. To accommodate this
// the first element of "insert" should be ignored.)
//
// For example for base "hlloo" and target "hello", the edit script would be
// [
//
//	{"insert": false, "run_length": 1}, // leading run of length 1 ("h")
//	{"insert": true, "run_length": 3}, // insert("e") then a run of length 3 ("llo")
//	{"insert": false, "run_length": 0} // delete("o") then an empty run
//
// ]
type Edits []Edit

// String returns a simple string representation of the edit script.
func ( Edits) () string {
	return fmt.Sprintf("%v", []Edit())
}

// UnifiedDiff returns a string representation of the diff of base and target in Unified Diff format.
func ( Edits) (,  arrow.Array) string {
	var  strings.Builder
	 := int64(0)
	 := int64(0)
	 := false
	for  := 0;  < len(); ++ {
		if  > 0 {
			if ! {
				.WriteString(fmt.Sprintf("@@ -%d, +%d @@\n", , ))
				 = true
			}
			if [].Insert {
				.WriteString(fmt.Sprintf("+%v\n", stringAt(, )))
				++
			} else {
				.WriteString(fmt.Sprintf("-%v\n", stringAt(, )))
				++
			}
		}
		for  := int64(0);  < [].RunLength; ++ {
			++
			++
			 = false
		}
	}
	return .String()
}

func stringAt( arrow.Array,  int64) string {
	if .IsNull(int()) {
		return "null"
	}
	 := .DataType()
	switch {
	case arrow.TypeEqual(, arrow.PrimitiveTypes.Float32):
		return fmt.Sprintf("%f", .(*Float32).Value(int()))
	case arrow.TypeEqual(, arrow.PrimitiveTypes.Float64):
		return fmt.Sprintf("%f", .(*Float64).Value(int()))
	case arrow.TypeEqual(, arrow.PrimitiveTypes.Date32):
		return .(*Date32).Value(int()).FormattedString()
	case arrow.TypeEqual(, arrow.PrimitiveTypes.Date64):
		return .(*Date64).Value(int()).FormattedString()
	case arrow.TypeEqual(, arrow.FixedWidthTypes.Timestamp_s):
		return .(*Timestamp).Value(int()).ToTime(arrow.Second).String()
	case arrow.TypeEqual(, arrow.FixedWidthTypes.Timestamp_ms):
		return .(*Timestamp).Value(int()).ToTime(arrow.Millisecond).String()
	case arrow.TypeEqual(, arrow.FixedWidthTypes.Timestamp_us):
		return .(*Timestamp).Value(int()).ToTime(arrow.Microsecond).String()
	case arrow.TypeEqual(, arrow.FixedWidthTypes.Timestamp_ns):
		return .(*Timestamp).Value(int()).ToTime(arrow.Nanosecond).String()
	}
	 := NewSlice(, , +1)
	defer .Release()
	,  := .MarshalJSON()
	return strings.Trim(string([1:len()-1]), "\n")
}

// Diff compares two arrays, returning an edit script which expresses the difference
// between them. The edit script can be applied to the base array to produce the target.
// 'base' is a baseline for comparison.
// 'target' is an array of identical type to base whose elements differ from base's.
func (,  arrow.Array) ( Edits,  error) {
	if !arrow.TypeEqual(.DataType(), .DataType()) {
		return nil, fmt.Errorf("%w: only taking the diff of like-typed arrays is supported", arrow.ErrNotImplemented)
	}
	switch .DataType().ID() {
	case arrow.EXTENSION:
		return (.(ExtensionArray).Storage(), .(ExtensionArray).Storage())
	case arrow.DICTIONARY:
		return nil, fmt.Errorf("%w: diffing arrays of type %s is not implemented", arrow.ErrNotImplemented, .DataType())
	case arrow.RUN_END_ENCODED:
		return nil, fmt.Errorf("%w: diffing arrays of type %s is not implemented", arrow.ErrNotImplemented, .DataType())
	}
	 := newQuadraticSpaceMyersDiff(, )
	return .Diff()
}

// editPoint represents an intermediate state in the comparison of two arrays
type editPoint struct {
	base   int
	target int
}

type quadraticSpaceMyersDiff struct {
	base         arrow.Array
	target       arrow.Array
	finishIndex  int
	editCount    int
	endpointBase []int
	insert       []bool
	baseBegin    int
	targetBegin  int
	baseEnd      int
	targetEnd    int
}

func newQuadraticSpaceMyersDiff(,  arrow.Array) *quadraticSpaceMyersDiff {
	 := &quadraticSpaceMyersDiff{
		base:         ,
		target:       ,
		finishIndex:  -1,
		editCount:    0,
		endpointBase: []int{},
		insert:       []bool{},
		baseBegin:    0,
		targetBegin:  0,
		baseEnd:      .Len(),
		targetEnd:    .Len(),
	}
	.endpointBase = []int{.extendFrom(editPoint{.baseBegin, .targetBegin}).base}
	if .baseEnd-.baseBegin == .targetEnd-.targetBegin && .endpointBase[0] == .baseEnd {
		// trivial case: base == target
		.finishIndex = 0
	}
	return 
}

func ( *quadraticSpaceMyersDiff) (,  int) bool {
	 := .base.IsNull()
	 := .target.IsNull()
	if  ||  {
		return  && 
	}
	return SliceEqual(.base, int64(), int64(+1), .target, int64(), int64(+1))
}

// increment the position within base and target (the elements skipped in this way were
// present in both sequences)
func ( *quadraticSpaceMyersDiff) ( editPoint) editPoint {
	for .base != .baseEnd && .target != .targetEnd {
		if !.valuesEqual(.base, .target) {
			break
		}
		.base++
		.target++
	}
	return 
}

// increment the position within base (the element pointed to was deleted)
// then extend maximally
func ( *quadraticSpaceMyersDiff) ( editPoint) editPoint {
	if .base != .baseEnd {
		.base++
	}
	return .extendFrom()
}

// increment the position within target (the element pointed to was inserted)
// then extend maximally
func ( *quadraticSpaceMyersDiff) ( editPoint) editPoint {
	if .target != .targetEnd {
		.target++
	}
	return .extendFrom()
}

// beginning of a range for storing per-edit state in endpointBase and insert
func storageOffset( int) int {
	return  * ( + 1) / 2
}

// given edit_count and index, augment endpointBase[index] with the corresponding
// position in target (which is only implicitly represented in editCount, index)
func ( *quadraticSpaceMyersDiff) (,  int) editPoint {
	 := 2*(-storageOffset()) - 
	 := .endpointBase[]
	 := min(.targetBegin+((-.baseBegin)+), .targetEnd)
	return editPoint{, }
}

func ( *quadraticSpaceMyersDiff) () {
	.editCount++
	if len(.endpointBase) < storageOffset(.editCount+1) {
		.endpointBase = append(.endpointBase, make([]int, storageOffset(.editCount+1)-len(.endpointBase))...)
	}
	if len(.insert) < storageOffset(.editCount+1) {
		.insert = append(.insert, make([]bool, storageOffset(.editCount+1)-len(.insert))...)
	}
	 := storageOffset(.editCount - 1)
	 := storageOffset(.editCount)

	// try deleting from base first
	for ,  := 0, 0;  < .editCount; ,  = +1, +1 {
		 := .getEditPoint(.editCount-1, +)
		.endpointBase[+] = .deleteOne().base
	}

	// check if inserting from target could do better
	for ,  := 0, 1;  < .editCount; ,  = +1, +1 {
		// retrieve the previously computed best endpoint for (editCount, iOut)
		// for comparison with the best endpoint achievable with an insertion
		 := .getEditPoint(.editCount, +)

		 := .getEditPoint(.editCount-1, +)
		 := .insertOne()

		if .base-.base >= 0 {
			// insertion was more efficient; keep it and mark the insertion in insert
			.insert[+] = true
			.endpointBase[+] = .base
		}
	}

	 := editPoint{.baseEnd, .targetEnd}
	for  := 0;  < .editCount+1; ++ {
		if .getEditPoint(.editCount, +) ==  {
			.finishIndex =  + 
			return
		}
	}
}

func ( *quadraticSpaceMyersDiff) () bool {
	return .finishIndex != -1
}

func ( *quadraticSpaceMyersDiff) () (Edits, error) {
	if !.Done() {
		panic("GetEdits called but Done() = false")
	}

	 := .editCount + 1
	 := make(Edits, )
	 := .finishIndex
	 := .getEditPoint(.editCount, .finishIndex)

	for  := .editCount;  > 0; -- {
		 := .insert[]
		[].Insert = 
		 := (.base - .baseBegin) - (.target - .targetBegin)
		if  {
			++
		} else {
			--
		}
		 = (-1-)/2 + storageOffset(-1)

		// endpoint of previous edit
		 := .getEditPoint(-1, )
		 := 0
		if  {
			 = 1
		}
		[].RunLength = int64(.base - .base - (1 - ))
		 = 
	}
	[0].Insert = false
	[0].RunLength = int64(.base - .baseBegin)

	return , nil
}

func ( *quadraticSpaceMyersDiff) () ( Edits,  error) {
	for !.Done() {
		.Next()
	}
	return .GetEdits()
}