func (m *Manager) getPackLeftNodeGroups(nag *assignmentsv1alpha1.NodeAssignmentGroup) map[string][]*corev1.Node {
	rtn := make(map[string][]*corev1.Node)
	targetedNodes := m.getTargetedNodes(nag)
	for _, node := range targetedNodes {
		if assignmentName, ok := nag.GetAssignment(node); ok {
			if assignment, ok := m.getAssignmentByName(assignmentName, nag); ok &&
				assignment.SchedulingMode == assignmentsv1alpha1.NodeAssignmentSchedulingModePackLeft {
				rtn[assignmentName] = append(rtn[assignmentName], node)
			}
		}
	}
	return rtn
}
get a map that contains an assignment name mapped to a list of nodes with that assignment
only returns nodes/assignments that are pack left
package packleft
import (
	"encoding/json"
	"fmt"
	"sort"
	assignmentsv1alpha1 "github.com/domoinc/kube-valet/pkg/apis/assignments/v1alpha1"
	valet "github.com/domoinc/kube-valet/pkg/client/clientset/versioned"
	"github.com/domoinc/kube-valet/pkg/utils"
	logging "github.com/op/go-logging"
	"github.com/prometheus/client_golang/prometheus"
	corev1 "k8s.io/api/core/v1"
	metav1 "k8s.io/apimachinery/pkg/apis/meta/v1"
	"k8s.io/apimachinery/pkg/types"
	"k8s.io/apimachinery/pkg/util/strategicpatch"
	"k8s.io/client-go/kubernetes"
	"k8s.io/client-go/tools/cache"
	"k8s.io/client-go/util/retry"
)
const (
	PackLeftFinalizer string = "packleft.nag.finalizer.kube-valet.io"
)
type Manager struct {
	nagIndex    cache.Indexer
	nodeIndex   cache.Indexer
	podIndex    cache.Indexer
	valetClient valet.Interface
	kubeClient  kubernetes.Interface
	log         *logging.Logger
}
func NewManager(nagIndex cache.Indexer, nodeIndex cache.Indexer, podIndex cache.Indexer, kubeClient kubernetes.Interface, valetClient valet.Interface) *Manager {
	return &Manager{
		nagIndex:    nagIndex,
		nodeIndex:   nodeIndex,
		podIndex:    podIndex,
		kubeClient:  kubeClient,
		valetClient: valetClient,
		log:         logging.MustGetLogger("PackLeftSchedulingManager"),
	}
}
func (m *Manager) RebalanceNag(nag *assignmentsv1alpha1.NodeAssignmentGroup, metric *prometheus.GaugeVec) {
	m.ensureFinalizer(nag)
	packLeftNodeGroups := m.getPackLeftNodeGroups(nag)
	m.log.Debugf("found %d node groups for nag %s with", len(packLeftNodeGroups), nag.Name)
	for assignmentName, nodes := range packLeftNodeGroups {
		if len(nodes) != 0 {
			m.log.Infof("rebalancing  %d nodes in assignment %s.%s", len(nodes), nag.Name, assignmentName)
			labelKey := getLabelKey(nag.Name)
			if assignment, ok := m.getAssignmentByName(assignmentName, nag); ok {
				m.balanceNodes(nodes, labelKey, nag, assignment, metric)
			} else {
				m.log.Warningf("Assignment %s doesn't exist in the NodeAssignmentGroup", assignmentName)
			}
		} else {
			m.log.Warningf("No nodes found for assignment %s on nag %s", assignmentName, nag.Name)
		}
	}
}
func (m *Manager) CleanAllNodes(nag *assignmentsv1alpha1.NodeAssignmentGroup) error {
	labelKey := getLabelKey(nag.Name)
	for _, obj := range m.nodeIndex.List() {
		node := obj.(*corev1.Node)
		if (!m.NodeHasPackLeftAssignment(node, nag) && m.NodeHasPackLeftAttributes(node, nag)) || !NodeCanBeBalanced(node) {
			newNode := m.unassignNode(node, labelKey)
			if err := m.patchNodeState(node, newNode); err != nil {
				return err
			}
		}
	}
	return nil
}
func (m *Manager) CleanUnassignedNodes(nag *assignmentsv1alpha1.NodeAssignmentGroup) {
	m.log.Infof("Cleaning nag %s", nag.Name)
	labelKey := getLabelKey(nag.Name)
	for _, obj := range m.nodeIndex.List() {
		node := obj.(*corev1.Node)
		if !m.NodeHasPackLeftAssignment(node, nag) && m.NodeHasPackLeftAttributes(node, nag) {
			m.log.Debugf("Node '%s' has packleft attributes for nag '%s' but is not assigned to it anymore. Clearing attributes", node.Name, nag.Name)
			newNode := m.unassignNode(node, labelKey)
			m.patchNodeState(node, newNode)
		}
	}
}
func (m *Manager) NodeHasPackLeftAttributes(node *corev1.Node, nag *assignmentsv1alpha1.NodeAssignmentGroup) bool {
	lk := getLabelKey(nag.Name)
	for k := range node.GetLabels() {
		if k == lk {
			return true
		}
	}
	for _, t := range node.Spec.Taints {
		if t.Key == lk {
			return true
		}
	}
	return false
}
func (m *Manager) NodeHasPackLeftAssignment(node *corev1.Node, nag *assignmentsv1alpha1.NodeAssignmentGroup) bool {
	assignments := getAllAssignments(nag)
	if na, ok := nag.GetAssignment(node); ok {
		for _, a := range assignments {
			if na == a.Name && a.SchedulingMode == assignmentsv1alpha1.NodeAssignmentSchedulingModePackLeft {
				return true
			}
		}
	}
	return false
}
type assignmentContext struct {
	percentFull float64
	node        *corev1.Node
	assignment  *assignmentsv1alpha1.NodeAssignment
}
func newAssignmentContext(percent float64, node *corev1.Node, assignment *assignmentsv1alpha1.NodeAssignment) *assignmentContext {
	return &assignmentContext{
		percentFull: percent,
		node:        node,
		assignment:  assignment,
	}
}
func (m *Manager) balanceNodes(nodes []*corev1.Node, labelKey string, nag *assignmentsv1alpha1.NodeAssignmentGroup, assignment *assignmentsv1alpha1.NodeAssignment, metric *prometheus.GaugeVec) {
	var nodesWithPercent []*assignmentContext
	podsOnNodes := m.getPodsOnNodes()
	for _, node := range nodes {
		if !NodeCanBeBalanced(node) {
			continue  
		}
		var percentFull float64
		memFull := m.getNodePercentFullMemory(node, podsOnNodes)
		cpuFull := m.getNodePercentFullCPU(node, podsOnNodes)
		if memFull > cpuFull {
			percentFull = memFull
		} else {
			percentFull = cpuFull
		}
		nodesWithPercent = append(nodesWithPercent, newAssignmentContext(percentFull, node, assignment))
	}
	if len(nodesWithPercent) < 1 {
		m.log.Warningf("No schedulable nodes found. Unable to balance nodes")
		return
	}
	sort.Slice(nodesWithPercent, func(i, j int) bool {
		if nodesWithPercent[i].percentFull == nodesWithPercent[j].percentFull {
			return nodesWithPercent[i].node.Name > nodesWithPercent[j].node.Name
		}
		return nodesWithPercent[i].percentFull > nodesWithPercent[j].percentFull
	})
	avoidBufferSize := 0
	if assignment.PackLeft != nil {
		if assignment.PackLeft.PercentAvoid != nil {
			avoidBufferSize = int(float32(len(nodes)) * float32(*assignment.PackLeft.PercentAvoid) / 100.0)
		}
		if assignment.PackLeft.NumAvoid > avoidBufferSize {
			avoidBufferSize = assignment.PackLeft.NumAvoid
		}
	}
	if avoidBufferSize < 1 {
		avoidBufferSize = 1
	}
	m.log.Debugf("attempting to leave %d nodes as 'Avoid' nodes", avoidBufferSize)
	fullPercent := .8  
	if assignment.PackLeft != nil && assignment.PackLeft.FullPercent != nil {
		fullPercent = float64(*assignment.PackLeft.FullPercent) / float64(100)
	}
	m.log.Debugf("nodes will be considered full at %%%v", fullPercent*100)
	denyCount := 0
	avoidCount := 0
	firstCtx := nodesWithPercent[0]
	m.log.Debugf("assigning node %s to be first full node", firstCtx.node.Name)
	firstNode := m.assignNode(firstCtx, nodeUse, labelKey, metric)
	m.patchNodeState(firstCtx.node, firstNode)
	for _, ctx := range nodesWithPercent[1:] {
		var newNode *corev1.Node
		if ctx.percentFull > fullPercent {
			m.log.Debugf("assigned node %s to be Use", ctx.node.Name)
			newNode = m.assignNode(ctx, nodeUse, labelKey, metric)
		} else if avoidCount < avoidBufferSize {
			m.log.Debugf("assigned node %s to be Avoid", ctx.node.Name)
			newNode = m.assignNode(ctx, nodeAvoid, labelKey, metric)
			avoidCount++
		} else {
			m.log.Debugf("assigned node %s to be Deny", ctx.node.Name)
			newNode = m.assignNode(ctx, nodeDeny, labelKey, metric)
			denyCount++
		}
		m.patchNodeState(ctx.node, newNode)
	}
	if avoidBufferSize != avoidCount {
		m.log.Warningf("avoid buffer size on %s.%s is lower than specified", nag.GetName(), assignment.Name)
	}
}
type nodePackLeftState string
const (
	nodeUse      nodePackLeftState = "Use"
	nodeAvoid    nodePackLeftState = "Avoid"
	nodeDeny     nodePackLeftState = "Deny"
	nodeLabelKey                   = "nag.packleft.scheduling.kube-valet.io/%s"
)
func getLabelKey(nag string) string {
	return fmt.Sprintf(nodeLabelKey, nag)
}
func (m *Manager) patchNodeState(oldNode *corev1.Node, newNode *corev1.Node) error {
	oldData, err := json.Marshal(oldNode)
	if err != nil {
		return err
	}
	newData, err := json.Marshal(newNode)
	if err != nil {
		return err
	}
	patchBytes, err := strategicpatch.CreateTwoWayMergePatch(oldData, newData, corev1.Node{})
	if err != nil {
		return err
	}
	if !utils.IsEmptyPatch(patchBytes) {
		_, err = m.kubeClient.CoreV1().Nodes().Patch(oldNode.Name, types.StrategicMergePatchType, patchBytes)
		if err != nil {
			return err
		}
	}
	return nil
}
func (m *Manager) unassignNode(node *corev1.Node, labelKey string) *corev1.Node {
	newNode := node.DeepCopy()
	delete(newNode.GetLabels(), labelKey)
	m.removeTaint(newNode, labelKey)
	return newNode
}
func (m *Manager) assignNode(ctx *assignmentContext, state nodePackLeftState, labelKey string, metric *prometheus.GaugeVec) *corev1.Node {
	metric.With(prometheus.Labels{"node_assignment": ctx.assignment.Name, "node_name": ctx.node.Name, "pack_left_state": string(state)}).Set(ctx.percentFull)
	newNode := ctx.node.DeepCopy()
	newNode.ObjectMeta.Labels[labelKey] = string(state)
	m.removeTaint(newNode, labelKey)
	if state != nodeUse {
		effect := corev1.TaintEffectPreferNoSchedule
		if state == nodeDeny {
			effect = corev1.TaintEffectNoSchedule
		}
		newNode.Spec.Taints = append(newNode.Spec.Taints, corev1.Taint{
			Key:    labelKey,
			Value:  string(state),
			Effect: effect,
		})
	}
	return newNode
}
func (m *Manager) removeTaint(node *corev1.Node, labelKey string) {
	var index int
	found := false
	for i, taint := range node.Spec.Taints {
		if taint.Key == labelKey {
			index = i
			found = true
			break
		}
	}
	if found {
		node.Spec.Taints = append(node.Spec.Taints[:index], node.Spec.Taints[index+1:]...)
	}
}