bin/arr.go

package bin

func DeleteArrElem(arr []byte, qty int, elemSize int, idx int) {
	dstIdx := elemSize * idx
	srcIdx := dstIdx + elemSize

	end := qty * elemSize

	for ; srcIdx < end; srcIdx++ {
		arr[dstIdx] = arr[srcIdx]
		dstIdx++
	}

	for i := elemSize * (qty - 1); i < end; i++ {
		arr[i] = 0
	}
}

func InsertArrElem(arr []byte, qty int, elem []byte, idx int) {
	elemSize := len(elem)

	srcIdx := qty*elemSize - 1 // last byte
	dstIdx := srcIdx + elemSize

	end := elemSize * idx

	for ; srcIdx >= end; srcIdx-- {
		arr[dstIdx] = arr[srcIdx]
		dstIdx--
	}

	// Вставляем элемент
	for _, b := range elem {
		arr[end] = b
		end++
	}
}

// Для массивов, которые начинаются с конца arr и движутся к началу
func DeleteReverseArrElem(arr []byte, qty int, elemSize int, idx int) {
	dstIdx := len(arr) - idx*elemSize - 1
	srcIdx := dstIdx - elemSize

	end := len(arr) - qty*elemSize

	for ; srcIdx >= end; srcIdx-- {
		arr[dstIdx] = arr[srcIdx]
		dstIdx--
	}

	for i := end; i < end+elemSize; i++ {
		arr[i] = 0
	}
}

// qty = 2
// 0 0 3 3 1 1
// 3 3 3 3 1 1
func InsertReverseArrElem(arr []byte, qty int, elem []byte, idx int) {
	elemSize := len(elem)

	srcIdx := len(arr) - qty*elemSize
	dstIdx := srcIdx - elemSize

	end := len(arr) - elemSize*idx

	for ; srcIdx < end; srcIdx++ {
		arr[dstIdx] = arr[srcIdx]
		dstIdx++
	}

	// Вставляем элемент
	i := end - elemSize
	for _, b := range elem {
		arr[i] = b
		i++
	}
}

// Предполагается что значения отсортированы ASC
func FindArrElem(arr []byte, qty int, elem []byte, byteOrder ByteOrder) (elemIdx int, isFound bool) {
	if qty == 0 {
		return
	}

	// Границы (индексы элементов массива)
	a := 0
	b := qty - 1

	for {
		elemIdx = (b-a)/2 + a

		code := compareToArrElem(arr, elem, elemIdx, byteOrder)

		if code == 1 {
			a = elemIdx + 1
			if a > b {
				return elemIdx + 1, false
			}
		} else if code == -1 {
			b = elemIdx - 1
			if b < a {
				return elemIdx, false
			}
		} else {
			return elemIdx, true
		}
	}
}

// -1, меньше
// 1, больше
// 0, равны
func compareToArrElem(arr []byte, elem []byte, elemIdx int, byteOrder ByteOrder) int {
	if byteOrder == HL {
		// индекс первого байта
		idx := elemIdx * len(elem)

		for _, b := range elem {
			if b > arr[idx] {
				return 1
			} else if b < arr[idx] {
				return -1
			}
			idx++
		}
	} else {
		// индекс последнего байта
		idx := (elemIdx+1)*len(elem) - 1

		for bIdx := len(elem) - 1; bIdx >= 0; bIdx-- {
			b := elem[bIdx]
			if b > arr[idx] {
				return 1
			} else if b < arr[idx] {
				return -1
			}
			idx--
		}
	}
	return 0
}

// func find(arr []int, num int) (int, bool) {
// 	var a, b, i int
// 	b = len(arr) - 1
// 	for {
// 		i = (b-a)/2 + a
// 		if num > arr[i] {
// 			a = i + 1
// 			if a > b {
// 				return i + 1, false
// 			}
// 		} else if num < arr[i] {
// 			b = i - 1
// 			if b < a {
// 				return i, false
// 			}
// 		} else {
// 			return i, true
// 		}
// 	}
// }

type KeyComparator interface {
	CompareTo(int) int
}

// Предполагается что значения отсортированы ASC
func BinarySearch(qty int, keyComparator KeyComparator) (elemIdx int, isFound bool) {
	if qty == 0 {
		return
	}

	// Границы (индексы элементов массива)
	a := 0
	b := qty - 1

	for {
		elemIdx = (b-a)/2 + a

		code := keyComparator.CompareTo(elemIdx)

		if code == 1 {
			a = elemIdx + 1
			if a > b {
				return elemIdx + 1, false
			}
		} else if code == -1 {
			b = elemIdx - 1
			if b < a {
				return elemIdx, false
			}
		} else {
			return elemIdx, true
		}
	}
}