package ether

import (
	"sort"

	"github.com/pingcap/wormhole/pkg/whpb"
)

// ScheduleAlgorithm would provide method to select best [job worker] pairs from workers and jobs set
type ScheduleAlgorithm interface {
	Select(jobs Resources, workers Resources) []Resources
}

type simpleFirstFit struct{}

// Select implements ScheduleAlgorithm interface
func (s *simpleFirstFit) Select(jobs Resources, workers Resources) []Resources {
	sort.Sort(jobs)
	sort.Sort(workers)

	for _, job := range jobs {
		for _, worker := range workers {
			jobContracts := worker.GetContracts()
			if haveContract(job.GetId(), jobContracts) {
				continue
			}
			if matchLabels(job.GetLabels(), worker.GetLabels()) {
				return []Resources{{job, worker}}
			}
		}
	}
	return nil
}

type simpleExpel struct{}

func (s *simpleExpel) Select(jobs Resources, workers Resources) []Resources {
	sort.Sort(workers)
	sort.Sort(jobs)
	workerCount := len(workers)
	if workerCount <= 1 {
		return nil
	}

	workerScores := make(map[uint64]int)
	workerContracts := make(map[uint64][]uint64)

	for _, worker := range workers {
		workerScores[worker.GetId()] = worker.GetStatusScore()
		workerContracts[worker.GetId()] = worker.GetContracts()
	}

	for i := 0; i < workerCount; i++ {
		tiredWorkerContracts := workerContracts[workers[i].GetId()]
		tiredWorkerScore := workerScores[workers[i].GetId()]
		for j := workerCount - 1; j > i; j-- {
			worker := workers[j]
			score := workerScores[worker.GetId()]
			contracts := workerContracts[worker.GetId()]
			if (score - tiredWorkerScore) >= 2 {
				intersection := intersect(contracts, tiredWorkerContracts)
				for _, id := range intersection {
					job := findResource(jobs, id)
					if job != nil {
						return []Resources{{job, workers[i]}}
					}
				}
			}
		}
	}

	return nil
}

type uint64s []uint64

func (u uint64s) Len() int           { return len(u) }
func (u uint64s) Swap(i, j int)      { u[i], u[j] = u[j], u[i] }
func (u uint64s) Less(i, j int) bool { return u[i] > u[j] }

func intersect(a uint64s, b uint64s) []uint64 {
	sort.Sort(a)
	sort.Sort(b)

	var (
		i, j         int
		intersection []uint64
	)
	for i < a.Len() && j < b.Len() {
		if a[i] == b[j] {
			intersection = append(intersection, a[i])
			i++
			j++
		} else if a[i] > b[j] {
			i++
		} else {
			j++
		}
	}

	return intersection
}

func findResource(resources Resources, id uint64) Resource {
	index := sort.Search(len(resources), func(i int) bool { return resources[i].GetId() >= id })
	if index < len(resources) && resources[index].GetId() == id {
		return resources[index]
	}

	return nil
}

func haveContract(a uint64, b uint64s) bool {
	sort.Sort(b)
	index := sort.Search(len(b), func(i int) bool { return b[i] >= a })
	if index < len(b) && b[index] == a {
		return true
	}

	return false
}

func matchLabels(s map[string]*whpb.Label, t map[string]*whpb.Label) bool {
	for key, val := range s {
		tVal := t[key]
		if tVal == nil {
			return false
		}

		if !contain(val, tVal) {
			return false
		}
	}
	return true
}

func contain(s *whpb.Label, t *whpb.Label) bool {
	sVals := s.GetVals()
	tVals := t.GetVals()

	index := 0
	for _, v := range tVals {
		for v != sVals[index] {
			index++
			if index == len(sVals) {
				return false
			}
		}
	}

	return true
}