package main

import (
	"slices"
)

const (
	// maxBuilds is the number of model builds that can run at once.
	maxBuilds = 8

	// leafWindow is the number of unbuilt leaves that can be before a leaf
	// whose build starts.
	leafWindow = 8
)

// queue holds the nodes that wait for a model build. A leaf joins it when its
// message is too long to be its own node. A merge joins it when both of its
// children are built and their texts do not fit in one node. So the core never
// scans the tree for work.
//
// A leaf can start when fewer than leafWindow leaves before it are unbuilt.
// Leaves start before merges, oldest first, because a turn waits for the leaves
// of all earlier messages. Merges start in the order in which they became
// ready. A failed build waits until the next message.
type queue struct {
	leaves  []int
	merges  []nodeKey
	queued  map[nodeKey]bool
	running map[nodeKey]bool
	failed  map[nodeKey]bool
}

func newQueue() *queue {
	return &queue{
		queued:  make(map[nodeKey]bool),
		running: make(map[nodeKey]bool),
		failed:  make(map[nodeKey]bool),
	}
}

// AddLeaf adds the leaf of message id. The IDs must come in increasing order.
func (q *queue) AddLeaf(id int) {
	q.leaves = append(q.leaves, id)
}

// AddMerge adds a merge whose children are built. A merge that is in the queue
// already stays as it is.
func (q *queue) AddMerge(key nodeKey) {
	if q.queued[key] {
		return
	}

	q.queued[key] = true
	q.merges = append(q.merges, key)
}

// Next returns the next node that can start, and marks it as running.
func (q *queue) Next() (nodeKey, bool) {
	if len(q.running) >= maxBuilds {
		return nodeKey{}, false
	}

	for _, id := range q.leaves[:min(len(q.leaves), leafWindow)] {
		key := nodeKey{0, id}
		if q.startable(key) {
			q.running[key] = true
			return key, true
		}
	}

	for _, key := range q.merges {
		if q.startable(key) {
			q.running[key] = true
			return key, true
		}
	}

	return nodeKey{}, false
}

func (q *queue) startable(key nodeKey) bool {
	return !q.running[key] && !q.failed[key]
}

// Done removes a built node from the queue.
func (q *queue) Done(key nodeKey) {
	delete(q.running, key)
	if key.level == 0 {
		q.leaves = slices.DeleteFunc(q.leaves, func(id int) bool {
			return id == key.index
		})

		return
	}

	delete(q.queued, key)
	q.merges = slices.DeleteFunc(q.merges, func(other nodeKey) bool {
		return other == key
	})
}

// Fail keeps a node in the queue, but it cannot start until Retry.
func (q *queue) Fail(key nodeKey) {
	delete(q.running, key)
	q.failed[key] = true
}

// Retry lets the failed nodes start again.
func (q *queue) Retry() {
	clear(q.failed)
}

// Running returns the number of builds that run.
func (q *queue) Running() int {
	return len(q.running)
}