package inner_sort

import (
	C "gitee.com/ljfirst/algo-go-sdk/common/constant"
	"reflect"
)

/**
 * @author ljfirst
 * @version V1.0
 * @date 2023/6/26 00:01
 * @author-Email ljfirst@mail.ustc.edu.cn
 * @blogURL https://blog.csdn.net/ljfirst
 * @description
 * */
type HeapSort2 struct {
	FromHighToLow bool // true表示从高到低排序,默认 false 表示从低到高排序
	IsSmallHeap   bool // Flag = true:表示开启小顶堆，默认大顶堆(false)
	gt            C.GT
	change        C.Change
}

func NewHeapSort2(options ...C.Options) *HeapSort2 {
	opt := C.NewOptions(options...)
	gt := opt.GT
	if gt == nil {
		gt = C.ArrayGT
	}
	change := opt.Change
	if change == nil {
		change = C.ArrayChange()
	}
	return &HeapSort2{
		IsSmallHeap: opt.IsSmallHeap,
		gt:          gt,
		change:      change,
	}
}

func (m *HeapSort2) SortMethod(array []int) {
	if len(array) < 2 {
		return
	}
	for i := len(array) - 1; i > 0; i-- {
		m.BuildHeapUp(array, i)
		array[0], array[i] = array[i], array[0]
	}
}

func (m *HeapSort2) BuildHeapUp(array interface{}, border int) {
	// tips : 通过反射判断 array 是否是数组, 以及应用数组的数量判断: value.Len()
	value := reflect.ValueOf(array)
	if value.Kind() != reflect.Array && value.Kind() != reflect.Slice {
		//fmt.Println("data is not an array or slice")
		return
	}

	if border <= 0 || border > value.Len()-1 {
		return
	}
	for i := (border - 1) / 2; i >= 0; i-- {
		child := i*2 + 1
		if child+1 <= border {
			if m.IsSmallHeap && m.gt(array, child, child+1) {
				child = child + 1
			}
			if !m.IsSmallHeap && !m.gt(array, child, child+1) {
				child = child + 1
			}
		}
		if (m.IsSmallHeap && m.gt(array, child, i)) || (!m.IsSmallHeap && !m.gt(array, child, i)) {
			continue
		}
		m.change(array, child, i)
	}
}

func (m *HeapSort2) GetAttribute() *C.Attribute {
	return &C.Attribute{
		Tags: []string{C.Sort},
		Desc: &C.Desc{
			Name:   "HeapSort2",
			NameCn: "内部排序:堆排序:自低向上",
			ParamsDesc: map[string]string{
				"fromHighToLow": "true表示从高到低排序, 默认 false 表示从低到高排序",
			},
			Example: map[int]string{
				1: "输入[1,3,2],跳用SortMethod方法进行排序后，输出[1,2,3]",
			},
		},
	}
}