func createBinarySearch(sortedSeq Seq, target Object, cb Comparator, length int) int {
	resIndex := -1
	lo := 0
	hi := length
	for lo < hi {
		mid := (lo + hi) >> 1
		if cb(sortedSeq[mid], target) == 0 {
			resIndex = mid
			break
		}
		if cb(sortedSeq[mid], target) < 0 {
			lo = mid + 1
		} else {
			hi = mid
		}
	}
	return resIndex
}
createBinarySearch returns the index of the value we want to find,
it uses the Binary Search algorithm to reduce iteration count
this assumes that we operating with sorted Sequence
package ugo
import (
	sorter "github.com/alxrm/ugo/timsort"
	"math"
	"math/rand"
	"reflect"
	"time"
)
type Object interface{}
type Seq []interface{}
type Collector func(memo, current, currentKey, src Object) Object
type Callback func(current, currentKey, src Object) Object
type Comparator func(left, right Object) int
type Predicate func(current, currentKey, src Object) bool
type Action func(current, currentKey, src Object)
const (
	toMin int = -1  
	toMax int = 1   
)
const (
	less   = -1
	equal  = 0
	larger = 1
)
func Chain(target Seq) *ChainWrapper {
	if IsEmpty(target) {
		target = Seq{}
	}
	return &ChainWrapper{Mid: target, Res: target}
}
func NewSeq(size int) Seq {
	return make(Seq, size)
}
func Each(seq Seq, cb Action) {
	if cb == nil {
		return
	}
	for index, val := range seq {
		cb(val, index, seq)
	}
}
func ForEach(seq Seq, cb Action) {
	Each(seq, cb)
}
func Map(seq Seq, cb Callback) Seq {
	if seq == nil {
		return Seq{}
	}
	if cb == nil {
		return seq
	}
	length := len(seq)
	result := NewSeq(length)
	for index, val := range seq {
		result[index] = cb(val, index, seq)
	}
	return result
}
func Collect(seq Seq, cb Callback) Seq {
	return Map(seq, cb)
}
func Filter(seq Seq, cb Predicate) Seq {
	if seq == nil {
		return Seq{}
	}
	if cb == nil {
		return seq
	}
	result := NewSeq(0)
	for index, val := range seq {
		if cb(val, index, seq) {
			result = append(result, val)
		}
	}
	return result
}
func Select(seq Seq, cb Predicate) Seq {
	return Filter(seq, cb)
}
func Reject(seq Seq, cb Predicate) Seq {
	if seq == nil {
		return Seq{}
	}
	if cb == nil {
		return seq
	}
	return Filter(seq, negate(cb))
}
func Reduce(seq Seq, cb Collector, initial Object) Object {
	var memo Object
	if IsEmpty(seq) || cb == nil {
		return nil
	}
	length := len(seq) - 1
	if initial == nil {
		memo = seq[0]
		return createReduce(seq, cb, memo, 1, toMax, length-1)
	}
	memo = initial
	return createReduce(seq, cb, memo, 0, toMax, length)
}
func Inject(seq Seq, cb Collector, initial Object) Object {
	return Reduce(seq, cb, initial)
}
func FoldL(seq Seq, cb Collector, initial Object) Object {
	return Reduce(seq, cb, initial)
}
func ReduceRight(seq Seq, cb Collector, initial Object) Object {
	var memo Object
	if IsEmpty(seq) || cb == nil {
		return nil
	}
	length := len(seq) - 1
	if initial == nil {
		memo = seq[length]
		return createReduce(seq, cb, memo, length-1, toMin, length-1)
	}
	memo = initial
	return createReduce(seq, cb, memo, length, toMin, length)
}
func FoldR(seq Seq, cb Collector, initial Object) Object {
	return ReduceRight(seq, cb, initial)
}
func Min(seq Seq, cb Comparator) Object {
	return createComparingIterator(seq, cb, toMin, len(seq))
}
func Max(seq Seq, cb Comparator) Object {
	return createComparingIterator(seq, cb, toMax, len(seq))
}
func Find(seq Seq, cb Predicate) Object {
	length := len(seq) - 1
	res, _ := createPredicateSearch(seq, cb, 0, toMax, length)
	return res
}
func Detect(seq Seq, cb Predicate) Object {
	return Find(seq, cb)
}
func FindLast(seq Seq, cb Predicate) Object {
	length := len(seq) - 1
	res, _ := createPredicateSearch(seq, cb, length, toMin, length)
	return res
}
func FindIndex(seq Seq, cb Predicate) int {
	length := len(seq) - 1
	_, index := createPredicateSearch(seq, cb, 0, toMax, length)
	return index
}
func FindLastIndex(seq Seq, cb Predicate) int {
	length := len(seq) - 1
	_, index := createPredicateSearch(seq, cb, length, toMin, length)
	return index
}
func Some(seq Seq, cb Predicate) bool {
	return FindIndex(seq, cb) != -1
}
func Any(seq Seq, cb Predicate) bool {
	return Some(seq, cb)
}
func IndexOf(seq Seq, target Object, isSorted bool, cb Comparator) int {
	if cb == nil {
		return -1
	}
	if isSorted {
		return createBinarySearch(seq, target, cb, len(seq))
	}
	equalityPredicate := func(cur, _, _ Object) bool { return cb(cur, target) == 0 }
	return FindIndex(seq, equalityPredicate)
}
func LastIndexOf(seq Seq, target Object, cb Comparator) int {
	if cb == nil {
		return -1
	}
	var equalityPredicate Predicate = func(cur, _, _ Object) bool { return cb(cur, target) == 0 }
	return FindLastIndex(seq, equalityPredicate)
}
func Contains(seq Seq, target Object, isSorted bool, cb Comparator) bool {
	if cb == nil {
		return false
	}
	return IndexOf(seq, target, isSorted, cb) != -1
}
func Includes(seq Seq, target Object, isSorted bool, cb Comparator) bool {
	return Contains(seq, target, isSorted, cb)
}
func Every(seq Seq, cb Predicate) bool {
	if IsEmpty(seq) || cb == nil {
		return false
	}
	for index, val := range seq {
		if !cb(val, index, seq) {
			return false
		}
	}
	return true
}
func All(seq Seq, cb Predicate) bool {
	return Every(seq, cb)
}
func Uniq(seq Seq, cb Comparator) Seq {
	if seq == nil {
		return Seq{}
	}
	if cb == nil {
		return seq
	}
	result := NewSeq(0)
	for _, value := range seq {
		if !Contains(result, value, false, cb) {
			result = append(result, value)
		}
	}
	return result
}
func Unique(seq Seq, cb Comparator) Seq {
	return Uniq(seq, cb)
}
func Difference(seq, other Seq, cb Comparator) Seq {
	if seq == nil {
		return Seq{}
	}
	if cb == nil || other == nil {
		return Seq{}
	}
	result := NewSeq(0)
	for _, value := range seq {
		if !Contains(other, value, false, cb) {
			result = append(result, value)
		}
	}
	return result
}
func Without(seq Seq, nonGrata Object, cb Comparator) Seq {
	if seq == nil || cb == nil {
		return Seq{}
	}
	if nonGrata == nil {
		return seq
	}
	result := NewSeq(0)
	for _, value := range seq {
		if cb(value, nonGrata) != 0 {
			result = append(result, value)
		}
	}
	return result
}
func Intersection(seq, other Seq, cb Comparator) Seq {
	if seq == nil {
		return Seq{}
	}
	if cb == nil || other == nil {
		return Seq{}
	}
	result := NewSeq(0)
	for _, value := range seq {
		if Contains(other, value, false, cb) {
			result = append(result, value)
		}
	}
	return Uniq(result, cb)
}
func Union(seq, other Seq, cb Comparator) Seq {
	if seq == nil {
		return Seq{}
	}
	if cb == nil {
		return Seq{}
	}
	result := Concat(seq, other)
	return Uniq(result, cb)
}
func SortBy(seq Seq, cb Comparator) Seq {
	if seq == nil {
		return Seq{}
	}
	if cb == nil {
		return seq
	}
	sorter.Sort(seq, lessThan(cb))
	return seq
}
func CountBy(seq Seq, cb Callback) (result map[string]int) {
	result = make(map[string]int, 0)
	key := ""
	if seq == nil || cb == nil {
		return result
	}
	for index, val := range seq {
		key = cb(val, index, seq).(string)
		if result[key] == 0 {
			result[key] = 1
		} else {
			result[key] = result[key] + 1
		}
	}
	return result
}
func GroupBy(seq Seq, cb Callback) map[Object]Seq {
	var key Object
	var length int
	result := make(map[Object]Seq, 0)
	if seq == nil || cb == nil {
		return result
	}
	for index, val := range seq {
		key = cb(val, index, seq)
		length = len(result[key])
		if length == 0 {
			result[key] = Seq{val}
		} else {
			result[key] = Insert(result[key], val, length)
		}
	}
	return result
}
func Remove(seq Seq, position int) Seq {
	if IsEmpty(seq) {
		return Seq{}
	}
	position = fixPosition(position, len(seq)-1)
	bef := NewSeq(len(seq[:position]))
	aft := NewSeq(len(seq[position+1:]))
	copy(bef, seq[:position])
	copy(aft, seq[position+1:])
	return Concat(bef, aft)
}
func Insert(seq Seq, target Object, position int) Seq {
	if seq == nil {
		return Seq{}
	}
	position = fixPosition(position, len(seq))
	seq = append(seq, 0)
	copy(seq[position+1:], seq[position:])
	seq[position] = target
	return seq
}
func Concat(seq, next Seq) Seq {
	if seq == nil {
		return Seq{}
	}
	if next == nil {
		return seq
	}
	return append(seq, next...)
}
func Shuffle(seq Seq) Seq {
	if seq == nil {
		return Seq{}
	}
	return createShuffle(seq)
}
func ShuffledCopy(seq Seq) Seq {
	if seq == nil {
		return Seq{}
	}
	length := len(seq)
	copied := NewSeq(length)
	copy(copied, seq)
	return createShuffle(copied)
}
func Reverse(seq Seq) Seq {
	if seq == nil {
		return Seq{}
	}
	length := len(seq)
	return createReverse(seq, length)
}
func ReversedCopy(seq Seq) Seq {
	if seq == nil {
		return Seq{}
	}
	length := len(seq)
	copied := NewSeq(length)
	copy(copied, seq)
	return createReverse(copied, length)
}
func EqualsStrict(seqLeft, seqRight Seq, cb Comparator) bool {
	if len(seqLeft) != len(seqRight) || cb == nil {
		return false
	}
	for index, value := range seqLeft {
		if cb(seqRight[index], value) != 0 {
			return false
		}
	}
	return true
}
func EqualsNotStrict(seqLeft, seqRight Seq, cb Comparator) bool {
	lengthLeft := len(seqLeft)
	lengthRight := len(seqRight)
	target := NewSeq(lengthLeft)
	foundIndex := -1
	if lengthLeft != lengthRight || cb == nil {
		return false
	}
	copy(target, seqRight)
	for _, value := range seqLeft {
		if foundIndex = IndexOf(target, value, false, cb); foundIndex != -1 {
			target = Remove(target, foundIndex)
		} else {
			return false
		}
	}
	return true
}
func Random(min, max float64) int {
	if min == max {
		return 0
	}
	rand.Seed(time.Now().UnixNano())
	min = fixNumber(min)
	max = fixNumber(max)
	if min > max {
		min, max = max, min
	}
	res := min + math.Floor(rand.Float64()*(max-min+1))
	if math.IsNaN(res) {
		return 0
	}
	return int(res)
}
func IsEmpty(seq Seq) bool {
	return seq == nil || len(seq) == 0
}
func IsSlice(target Object) bool {
	return reflect.ValueOf(target).Kind() == reflect.Slice
}
func From(target Object, size int) Seq {
	if !IsSlice(target) || size < 0 {
		return Seq{}
	}
	s := reflect.ValueOf(target)
	res := make(Seq, size)
	for i := 0; i < size; i++ {
		res[i] = s.Index(i).Interface()
	}
	return res
}
func createComparingIterator(seq Seq, cb Comparator, dir, length int) Object {
	var lastComputed Object
	var innerComputed Object
	if IsEmpty(seq) || cb == nil {
		return -1
	}
	if length == 1 {
		return seq[0]
	}
	lastComputed = seq[0]
	for left, right := 0, length-1; left <= right; left, right = left+1, right-1 {
		if sgn(cb(seq[left], seq[right])) == dir {
			innerComputed = seq[left]
		} else {
			innerComputed = seq[right]
		}
		if sgn(cb(innerComputed, lastComputed)) == dir {
			lastComputed = innerComputed
		}
	}
	return lastComputed
}
func createReduce(seq Seq, cb Collector, memo Object, startPoint, direction, length int) Object {
	result := memo
	index := startPoint
	for i := 0; i <= length; i++ {
		result = cb(result, seq[index], index, seq)
		index += direction
	}
	return result
}
func createShuffle(seq Seq) Seq {
	for i := range seq {
		j := Random(0, float64(i))
		seq[i], seq[j] = seq[j], seq[i]
	}
	return seq
}
func createReverse(seq Seq, length int) Seq {
	for left, right := 0, length-1; left < right; left, right = left+1, right-1 {
		seq[left], seq[right] = seq[right], seq[left]
	}
	return seq
}
func createPredicateSearch(seq Seq, cb Predicate, startPoint, direction, length int) (res Object, resIndex int) {
	res = nil
	resIndex = -1
	if seq == nil || cb == nil {
		return
	}
	index := startPoint
	for i := 0; i <= length; i++ {
		if cb(seq[index], index, seq) {
			res = seq[index]
			resIndex = index
			break
		}
		index += direction
	}
	return
}