package main

import "sort"

const (
	StateReady   = "R"
	StateExecute = "E"
	StateWait    = "W"
	StateFinish  = "F"
)

type PCB struct {
	Name          string `json:"name"`
	Priority      int    `json:"priority"`
	InitPriority  int    `json:"initPriority"`
	ArrivalTime   int    `json:"arrivalTime"`
	NeedTime      int    `json:"needTime"`
	UsedTime      int    `json:"usedTime"`
	State         string `json:"state"`
	StartTime     int    `json:"startTime"`
	FinishTime    int    `json:"finishTime"`
	QueueLevel    int    `json:"queueLevel"`
	WaitUntil     int    `json:"waitUntil"`
	SliceUsedTime int    `json:"sliceUsedTime"`
}

func (p *PCB) Clone() PCB {
	return *p
}

func (p *PCB) Remaining() int {
	return p.NeedTime - p.UsedTime
}

type Snapshot struct {
	Time      int        `json:"time"`
	Processes []PCB      `json:"processes"`
	Running   string     `json:"running"`
	Queues    [][]string `json:"queues"`
	Event     string     `json:"event"`
}

type SimResult struct {
	Snapshots     []Snapshot `json:"snapshots"`
	Algorithm     string     `json:"algorithm"`
	AvgTurnaround float64    `json:"avgTurnaround"`
	Deadlock      bool       `json:"deadlock"`
}

func NewPCB(name string, priority, arrivalTime, needTime int) *PCB {
	return &PCB{
		Name:          name,
		Priority:      priority,
		InitPriority:  priority,
		ArrivalTime:   arrivalTime,
		NeedTime:      needTime,
		UsedTime:      0,
		State:         StateReady,
		StartTime:     -1,
		FinishTime:    -1,
		QueueLevel:    0,
		WaitUntil:     -1,
		SliceUsedTime: 0,
	}
}

func allFinished(procs []*PCB) bool {
	for _, p := range procs {
		if p.State != StateFinish {
			return false
		}
	}
	return true
}

func allWaitingOrFinished(procs []*PCB) bool {
	for _, p := range procs {
		if p.State != StateWait && p.State != StateFinish {
			return false
		}
	}
	return true
}

func anyWillWake(procs []*PCB, time int) bool {
	for _, p := range procs {
		if p.State == StateWait && p.WaitUntil > time {
			return true
		}
	}
	return false
}

func collectReady(procs []*PCB, time int) []*PCB {
	var ready []*PCB
	for _, p := range procs {
		if p.State == StateReady && p.ArrivalTime <= time {
			ready = append(ready, p)
		}
	}
	return ready
}

func findRunning(procs []*PCB) *PCB {
	for _, p := range procs {
		if p.State == StateExecute {
			return p
		}
	}
	return nil
}

func calcAvgTurnaround(procs []*PCB) float64 {
	total := 0
	count := 0
	for _, p := range procs {
		if p.State == StateFinish && p.FinishTime > 0 {
			total += p.FinishTime - p.ArrivalTime
			count++
		}
	}
	if count == 0 {
		return 0
	}
	return float64(total) / float64(count)
}

func makeSnap(time int, procs []*PCB, running string, queues [][]string, event string) Snapshot {
	var copies []PCB
	for _, p := range procs {
		copies = append(copies, p.Clone())
	}
	return Snapshot{
		Time:      time,
		Processes: copies,
		Running:   running,
		Queues:    queues,
		Event:     event,
	}
}

func SimulatePriorityRR(processes []*PCB, timeSlice int) SimResult {
	procs := make([]*PCB, len(processes))
	for i, p := range processes {
		c := *p
		procs[i] = &c
	}

	var snapshots []Snapshot
	var readyQueue []*PCB
	time := 0
	maxTime := 0
	for _, p := range procs {
		end := p.ArrivalTime + p.NeedTime*2 + 10
		if end > maxTime {
			maxTime = end
		}
	}

	for time <= maxTime {
		for _, p := range procs {
			if p.State == StateWait && p.WaitUntil <= time {
				p.State = StateReady
				p.WaitUntil = -1
				readyQueue = append(readyQueue, p)
			}
			if p.ArrivalTime == time && p.State == StateReady {
				found := false
				for _, q := range readyQueue {
					if q == p {
						found = true
						break
					}
				}
				if !found {
					readyQueue = append(readyQueue, p)
				}
			}
		}

		running := findRunning(procs)

		if running != nil {
			for _, p := range readyQueue {
				if p.Priority < running.Priority {
					running.State = StateReady
					running.SliceUsedTime = 0
					readyQueue = append(readyQueue, running)
					running = nil
					break
				}
			}
		}

		if running == nil {
			if len(readyQueue) == 0 {
				if allFinished(procs) {
					snapshots = append(snapshots, makeSnap(time, procs, "", nil, "✓ 所有进程执行完毕"))
					break
				}
				if allWaitingOrFinished(procs) {
					if !anyWillWake(procs, time) {
						snapshots = append(snapshots, makeSnap(time, procs, "", nil, "✗ 死锁：所有未完成进程都在等待"))
						return SimResult{Snapshots: snapshots, Algorithm: "基于优先级的时间片轮转", AvgTurnaround: calcAvgTurnaround(procs), Deadlock: true}
					}
					snapshots = append(snapshots, makeSnap(time, procs, "", nil, "无就绪进程，等待唤醒..."))
					time++
					continue
				}
				snapshots = append(snapshots, makeSnap(time, procs, "", nil, "无就绪进程"))
				time++
				continue
			}

			sort.Slice(readyQueue, func(i, j int) bool {
				if readyQueue[i].Priority != readyQueue[j].Priority {
					return readyQueue[i].Priority < readyQueue[j].Priority
				}
				return readyQueue[i].ArrivalTime < readyQueue[j].ArrivalTime
			})

			selected := readyQueue[0]
			readyQueue = readyQueue[1:]
			selected.State = StateExecute
			selected.SliceUsedTime = 0
			if selected.StartTime == -1 {
				selected.StartTime = time
			}
			running = selected
		}

		queueNames := buildQueueNames(readyQueue)
		event := running.Name + " 执行 (优先级=" + itoa(running.Priority) + ", 剩余=" + itoa(running.Remaining()) + ")"
		snapshots = append(snapshots, makeSnap(time, procs, running.Name, queueNames, event))

		running.UsedTime++
		running.SliceUsedTime++

		if running.UsedTime >= running.NeedTime {
			running.State = StateFinish
			running.FinishTime = time + 1
			snapshots = append(snapshots, makeSnap(time+1, procs, "", nil, running.Name+" 执行完毕 ✓"))
		} else if running.SliceUsedTime >= timeSlice {
			running.Priority += 3
			if running.UsedTime%3 == 0 && running.UsedTime < running.NeedTime {
				running.State = StateWait
				running.WaitUntil = time + 2
				running.SliceUsedTime = 0
				snapshots = append(snapshots, makeSnap(time+1, procs, "", nil,
					running.Name+" 等待I/O (优先级→"+itoa(running.Priority)+", 唤醒于t="+itoa(running.WaitUntil)+")"))
			} else {
				running.State = StateReady
				running.SliceUsedTime = 0
				readyQueue = append(readyQueue, running)
				snapshots = append(snapshots, makeSnap(time+1, procs, "", buildQueueNames(readyQueue),
					running.Name+" 时间片用完 (优先级→"+itoa(running.Priority)+")"))
			}
		} else {
			queueNames2 := buildQueueNames(readyQueue)
			snapshots = append(snapshots, makeSnap(time+1, procs, running.Name, queueNames2, running.Name+" 继续执行"))
		}

		time++
	}

	return SimResult{
		Snapshots:     snapshots,
		Algorithm:     "基于优先级的时间片轮转",
		AvgTurnaround: calcAvgTurnaround(procs),
		Deadlock:      false,
	}
}

func SimulateMLFQ(processes []*PCB, queueTimeSlices [3]int) SimResult {
	procs := make([]*PCB, len(processes))
	for i, p := range processes {
		c := *p
		c.QueueLevel = 0
		c.SliceUsedTime = 0
		procs[i] = &c
	}

	var snapshots []Snapshot
	queues := [3][]*PCB{}
	time := 0
	maxTime := 0
	for _, p := range procs {
		end := p.ArrivalTime + p.NeedTime*3 + 20
		if end > maxTime {
			maxTime = end
		}
	}

	for time <= maxTime {
		for _, p := range procs {
			if p.State == StateWait && p.WaitUntil <= time {
				p.State = StateReady
				p.WaitUntil = -1
				queues[p.QueueLevel] = append(queues[p.QueueLevel], p)
			}
			if p.ArrivalTime == time && p.State == StateReady {
				p.QueueLevel = 0
				p.SliceUsedTime = 0
				found := false
				for _, q := range queues[0] {
					if q == p {
						found = true
						break
					}
				}
				if !found {
					queues[0] = append(queues[0], p)
				}
			}
		}

		running := findRunning(procs)

		if running != nil {
			preempted := false
			for q := 0; q < 3; q++ {
				sort.Slice(queues[q], func(i, j int) bool {
					return queues[q][i].Priority < queues[q][j].Priority
				})
				if len(queues[q]) > 0 && (q < running.QueueLevel || (q == running.QueueLevel && queues[q][0].Priority < running.Priority)) {
					running.State = StateReady
					queues[running.QueueLevel] = insertSortedByPriority(queues[running.QueueLevel], running)
					running = nil
					preempted = true
					break
				}
			}
			_ = preempted
		}

		if running == nil {
			selected := selectFromMLFQ(queues)
			if selected == nil {
				if allFinished(procs) {
					snapshots = append(snapshots, makeMLFQSnap(time, procs, "", queues, "✓ 所有进程执行完毕"))
					break
				}
				if allWaitingOrFinished(procs) {
					if !anyWillWake(procs, time) {
						snapshots = append(snapshots, makeMLFQSnap(time, procs, "", queues, "✗ 死锁：所有未完成进程都在等待"))
						return SimResult{Snapshots: snapshots, Algorithm: "多级反馈队列轮转", AvgTurnaround: calcAvgTurnaround(procs), Deadlock: true}
					}
					snapshots = append(snapshots, makeMLFQSnap(time, procs, "", queues, "无就绪进程，等待唤醒..."))
					time++
					continue
				}
				snapshots = append(snapshots, makeMLFQSnap(time, procs, "", queues, "无就绪进程"))
				time++
				continue
			}

			removeFromQueue(&queues, selected)
			selected.State = StateExecute
			if selected.StartTime == -1 {
				selected.StartTime = time
			}
			running = selected
		}

		event := running.Name + " 从Q" + itoa(running.QueueLevel) + "执行 (片内已用=" + itoa(running.SliceUsedTime) + "/" + itoa(queueTimeSlices[running.QueueLevel]) + ")"
		snapshots = append(snapshots, makeMLFQSnap(time, procs, running.Name, queues, event))

		running.UsedTime++
		running.SliceUsedTime++
		qLevel := running.QueueLevel
		ts := queueTimeSlices[qLevel]

		if running.UsedTime >= running.NeedTime {
			running.State = StateFinish
			running.FinishTime = time + 1
			snapshots = append(snapshots, makeMLFQSnap(time+1, procs, "", queues, running.Name+" 执行完毕 ✓"))
		} else if running.SliceUsedTime >= ts {
			shouldWait := running.UsedTime%3 == 0 && running.UsedTime < running.NeedTime
			if shouldWait {
				running.State = StateWait
				running.WaitUntil = time + 2
				running.SliceUsedTime = 0
				snapshots = append(snapshots, makeMLFQSnap(time+1, procs, "", queues,
					running.Name+" 等待I/O (唤醒于t="+itoa(running.WaitUntil)+")"))
			} else if qLevel < 2 {
				running.QueueLevel = qLevel + 1
				running.State = StateReady
				running.SliceUsedTime = 0
				queues[qLevel+1] = append(queues[qLevel+1], running)
				snapshots = append(snapshots, makeMLFQSnap(time+1, procs, "", queues,
					running.Name+" 降级→Q"+itoa(qLevel+1)))
			} else {
				running.State = StateReady
				running.SliceUsedTime = 0
				queues[2] = append(queues[2], running)
				snapshots = append(snapshots, makeMLFQSnap(time+1, procs, "", queues,
					running.Name+" 重新加入Q2"))
			}
		} else {
			snapshots = append(snapshots, makeMLFQSnap(time+1, procs, running.Name, queues, running.Name+" 继续执行"))
		}

		time++
	}

	return SimResult{
		Snapshots:     snapshots,
		Algorithm:     "多级反馈队列轮转",
		AvgTurnaround: calcAvgTurnaround(procs),
		Deadlock:      false,
	}
}

func selectFromMLFQ(queues [3][]*PCB) *PCB {
	for q := 0; q < 3; q++ {
		sort.Slice(queues[q], func(i, j int) bool {
			if queues[q][i].Priority != queues[q][j].Priority {
				return queues[q][i].Priority < queues[q][j].Priority
			}
			return queues[q][i].ArrivalTime < queues[q][j].ArrivalTime
		})
		if len(queues[q]) > 0 {
			return queues[q][0]
		}
	}
	return nil
}

func removeFromQueue(queues *[3][]*PCB, target *PCB) {
	for q := 0; q < 3; q++ {
		for i, p := range queues[q] {
			if p == target {
				queues[q] = append(queues[q][:i], queues[q][i+1:]...)
				return
			}
		}
	}
}

func insertSortedByPriority(queue []*PCB, p *PCB) []*PCB {
	queue = append(queue, p)
	sort.Slice(queue, func(i, j int) bool {
		if queue[i].Priority != queue[j].Priority {
			return queue[i].Priority < queue[j].Priority
		}
		return queue[i].ArrivalTime < queue[j].ArrivalTime
	})
	return queue
}

func buildQueueNames(queue []*PCB) [][]string {
	var names []string
	for _, p := range queue {
		names = append(names, p.Name)
	}
	if names == nil {
		names = []string{}
	}
	return [][]string{names}
}

func buildMLFQQueueNames(queues [3][]*PCB) [][]string {
	var qs [][]string
	for q := 0; q < 3; q++ {
		var names []string
		for _, p := range queues[q] {
			names = append(names, p.Name)
		}
		if names == nil {
			names = []string{}
		}
		qs = append(qs, names)
	}
	return qs
}

func makeMLFQSnap(time int, procs []*PCB, running string, queues [3][]*PCB, event string) Snapshot {
	return makeSnap(time, procs, running, buildMLFQQueueNames(queues), event)
}

func itoa(n int) string {
	if n == 0 {
		return "0"
	}
	neg := false
	if n < 0 {
		neg = true
		n = -n
	}
	s := ""
	for n > 0 {
		s = string(rune('0'+n%10)) + s
		n /= 10
	}
	if neg {
		s = "-" + s
	}
	return s
}

func minInt(a, b int) int {
	if a < b {
		return a
	}
	return b
}