mean.go

/*	Copyright (c) 2019-present, Serhat Şevki Dinçer.
	This Source Code Form is subject to the terms of the Mozilla Public
	License, v. 2.0. If a copy of the MPL was not distributed with this
	file, You can obtain one at http://mozilla.org/MPL/2.0/.
*/

package sixb

import "cmp"

// MeanS returns lexicographic average of s1 and s2. It treats ascii specially. The result is
// (len(s1)+len(s2)+1)/2 bytes and may contain unprintable characters or may not be valid utf8.
//
//go:nosplit
func MeanS[T ~string](s1, s2 T) T {
	if len(s2) < len(s1) {
		s1, s2 = s2, s1
	} else if len(s2) <= 0 {
		return ""
	}
	i := Mean(len(s1)+1, len(s2))
	avg := make([]byte, i)

	i--
	sum := uint32(s2[i])
	mask := sum | 127
	if i < len(s1) {
		c := uint32(s1[i])
		sum += c
		mask |= c // if ascii inputs, consider 7 bits
	}
	for i > 0 {
		prMask := mask
		prSum := sum & mask
		shift := 7 + mask>>7
		sum >>= shift // carry

		i--
		c := uint32(s2[i])
		sum += c
		mask = c | 127
		if i < len(s1) {
			c = uint32(s1[i])
			sum += c
			mask |= c
		}
		avg[i+1] = byte((sum<<(shift-1) ^ prSum>>1) & prMask)
	}
	avg[0] = byte(sum >> 1)

	return T(String(avg))
}

// Signed is the set of signed integer types.
type Signed interface {
	~int | ~int8 | ~int16 | ~int32 | ~int64
}

// Unsigned is the set of unsigned integer types.
type Unsigned interface {
	~uint | ~uint8 | ~uint16 | ~uint32 | ~uint64 | ~uintptr
}

// Integer is the set of integer types.
type Integer interface {
	Signed | Unsigned
}

type Float interface {
	~float32 | ~float64
}

// Mean returns average of integers x and y, mathematically equivalent to floor((x+y)/2).
// This function works on the whole domain of (x,y) pairs, unlike (x+y)/2.
func Mean[T Integer](x, y T) T {
	return x&y + (x^y)>>1
}

// Median3 returns median of three values
func Median3[T cmp.Ordered](a, b, c T) T {
	// almost insertion sort to have a ≤ b ≤ c
	if b < a {
		a, b = b, a
	}
	if c < b {
		b = c
		if b < a {
			b = a
		}
	}
	return b
}

// Median4 returns median of four integers
func Median4[T Integer](a, b, c, d T) T {
	if d < b {
		d, b = b, d
	}
	if c < a {
		c, a = a, c
	}
	if d < c {
		c = d
	}
	if b < a {
		b = a
	}
	return Mean(b, c)
}