// Copyright 2023 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

package trace

import (
	
	
	

	
	
)

type batchCursor struct {
	m       ThreadID
	lastTs  Time
	idx     int       // next index into []batch
	dataOff int       // next index into batch.data
	ev      baseEvent // last read event
}

func ( *batchCursor) ( []batch,  frequency) ( bool,  error) {
	// Batches should generally always have at least one event,
	// but let's be defensive about that and accept empty batches.
	for .idx < len() && len([.idx].data) == .dataOff {
		.idx++
		.dataOff = 0
		.lastTs = 0
	}
	// Have we reached the end of the batches?
	if .idx == len() {
		return false, nil
	}
	// Initialize lastTs if it hasn't been yet.
	if .lastTs == 0 {
		.lastTs = .mul([.idx].time)
	}
	// Read an event out.
	, ,  := readTimedBaseEvent([.idx].data[.dataOff:], &.ev)
	if  != nil {
		return false, 
	}
	// Complete the timestamp from the cursor's last timestamp.
	.ev.time = .mul() + .lastTs

	// Move the cursor's timestamp forward.
	.lastTs = .ev.time

	// Move the cursor forward.
	.dataOff += 
	return true, nil
}

func ( *batchCursor) ( *batchCursor) int {
	return cmp.Compare(.ev.time, .ev.time)
}

// readTimedBaseEvent reads out the raw event data from b
// into e. It does not try to interpret the arguments
// but it does validate that the event is a regular
// event with a timestamp (vs. a structural event).
//
// It requires that the event its reading be timed, which must
// be the case for every event in a plain EventBatch.
func readTimedBaseEvent( []byte,  *baseEvent) (int, timestamp, error) {
	// Get the event type.
	 := event.Type([0])
	 := go122.Specs()
	if int() >= len() {
		return 0, 0, fmt.Errorf("found invalid event type: %v", )
	}
	.typ = 

	// Get spec.
	 := &[]
	if len(.Args) == 0 || !.IsTimedEvent {
		return 0, 0, fmt.Errorf("found event without a timestamp: type=%v", )
	}
	 := 1

	// Read timestamp diff.
	,  := binary.Uvarint([:])
	if  <= 0 {
		return 0, 0, fmt.Errorf("found invalid uvarint for timestamp")
	}
	 += 

	// Read the rest of the arguments.
	for  := 0;  < len(.Args)-1; ++ {
		,  := binary.Uvarint([:])
		if  <= 0 {
			return 0, 0, fmt.Errorf("found invalid uvarint")
		}
		.args[] = 
		 += 
	}
	return , timestamp(), nil
}

func heapInsert( []*batchCursor,  *batchCursor) []*batchCursor {
	// Add the cursor to the end of the heap.
	 = append(, )

	// Sift the new entry up to the right place.
	heapSiftUp(, len()-1)
	return 
}

func heapUpdate( []*batchCursor,  int) {
	// Try to sift up.
	if heapSiftUp(, ) !=  {
		return
	}
	// Try to sift down, if sifting up failed.
	heapSiftDown(, )
}

func heapRemove( []*batchCursor,  int) []*batchCursor {
	// Sift index i up to the root, ignoring actual values.
	for  > 0 {
		[(-1)/2], [] = [], [(-1)/2]
		 = ( - 1) / 2
	}
	// Swap the root with the last element, then remove it.
	[0], [len()-1] = [len()-1], [0]
	 = [:len()-1]
	// Sift the root down.
	heapSiftDown(, 0)
	return 
}

func heapSiftUp( []*batchCursor,  int) int {
	for  > 0 && [(-1)/2].ev.time > [].ev.time {
		[(-1)/2], [] = [], [(-1)/2]
		 = ( - 1) / 2
	}
	return 
}

func heapSiftDown( []*batchCursor,  int) int {
	for {
		 := min3(, , 2*+1, 2*+2)
		if  ==  {
			// Heap invariant already applies.
			break
		}
		[], [] = [], []
		 = 
	}
	return 
}

func min3( []*batchCursor, , ,  int) int {
	 := 
	 := maxTime
	if  < len() {
		 = [].ev.time
	}
	if  < len() {
		if  := [].ev.time;  <  {
			 = 
			 = 
		}
	}
	if  < len() {
		if  := [].ev.time;  <  {
			 = 
			 = 
		}
	}
	return 
}