package quic

import (
	
	

	
	list 
	
)

// byteInterval is an interval from one ByteCount to the other
type byteInterval struct {
	Start protocol.ByteCount
	End   protocol.ByteCount
}

var byteIntervalElementPool sync.Pool

func init() {
	byteIntervalElementPool = *list.NewPool[byteInterval]()
}

type frameSorterEntry struct {
	Data  []byte
	Frame *wire.StreamFrame
}

type frameSorter struct {
	queue   map[protocol.ByteCount]frameSorterEntry
	readPos protocol.ByteCount
	gaps    *list.List[byteInterval]
}

var errDuplicateStreamData = errors.New("duplicate stream data")

func newFrameSorter() *frameSorter {
	 := frameSorter{
		gaps:  list.NewWithPool[byteInterval](&byteIntervalElementPool),
		queue: make(map[protocol.ByteCount]frameSorterEntry),
	}
	.gaps.PushFront(byteInterval{Start: 0, End: protocol.MaxByteCount})
	return &
}

func ( *frameSorter) ( []byte,  protocol.ByteCount,  *wire.StreamFrame) error {
	 := .push(, , )
	if  == errDuplicateStreamData {
		if  != nil {
			.PutBack()
		}
		return nil
	}
	return 
}

func ( *frameSorter) ( []byte,  protocol.ByteCount,  *wire.StreamFrame) error {
	if len() == 0 {
		return errDuplicateStreamData
	}

	 := 
	 :=  + protocol.ByteCount(len())

	// In-order fast path: the frame starts at the read position and lies
	// entirely within the first gap. Data extending past the first gap's end
	// overlaps queued entries and may reach into later gaps, so it must go
	// through the general overlap handling below — truncating it here would
	// silently discard bytes the sender will never retransmit, permanently
	// stalling the stream.
	if  == .readPos {
		if ,  := .queue[]; ! {
			if  := .gaps.Front();  != nil && .Value.Start ==  &&  <= .Value.End {
				if  == .Value.End {
					.gaps.Remove()
				} else {
					.Value.Start = 
				}
				.queue[] = frameSorterEntry{Data: , Frame: }
				return nil
			}
		}
	}

	if  <= .gaps.Front().Value.Start {
		return errDuplicateStreamData
	}

	,  := .findStartGap()
	,  := .findEndGap(, )

	 :=  == 

	if ( &&  <= .Value.Start) ||
		(! && .Value.End >= .Value.Start &&  <= .Value.Start) {
		return errDuplicateStreamData
	}

	 := .Next()
	 := .Value.End // save it, in case startGap is modified
	 := .Value.Start // save it, in case endGap is modified
	 := .Value.End     // save it, in case endGap is modified
	var  bool
	var  bool

	 := 
	var  bool
	for {
		,  := .queue[]
		if ! {
			break
		}
		 := protocol.ByteCount(len(.Data))
		if - >  || ( && - == ) {
			// The existing frame is shorter than the new frame. Replace it.
			delete(.queue, )
			 += 
			 = true
			if .Frame != nil {
				.Frame.PutBack()
			}
		} else {
			if ! {
				return errDuplicateStreamData
			}
			// The existing frame is longer than the new frame.
			// Cut the new frame such that the end aligns with the start of the existing frame.
			 = [:-]
			 = 
			 = true
			break
		}
	}

	if ! && ! {
		// cut the frame, such that it starts at the start of the gap
		 = [.Value.Start-:]
		 = .Value.Start
		 = true
	}
	if  <= .Value.Start {
		if  >= .Value.End {
			// The frame covers the whole startGap. Delete the gap.
			.gaps.Remove()
		} else {
			.Value.Start = 
		}
	} else if ! {
		.Value.End = 
		 = true
	}

	if ! {
		.deleteConsecutive()
		var  *list.Element[byteInterval]
		for  := ; .Value.End < ;  =  {
			 = .Next()
			.deleteConsecutive(.Value.End)
			.gaps.Remove()
		}
	}

	if ! &&  !=  &&  >  {
		// cut the frame, such that it ends at the end of the gap
		 = [:-]
		 = 
		 = true
	}
	if  ==  {
		if ! {
			// The frame covers the whole endGap. Delete the gap.
			.gaps.Remove()
		}
	} else {
		if  &&  {
			// The frame split the existing gap into two.
			.gaps.InsertAfter(byteInterval{Start: , End: }, )
		} else if ! {
			.Value.Start = 
		}
	}

	if  && len() < protocol.MinStreamFrameBufferSize {
		 := make([]byte, len())
		copy(, )
		 = 
		if  != nil {
			.PutBack()
			 = nil
		}
	}

	if .gaps.Len() > protocol.MaxStreamFrameSorterGaps {
		return errors.New("too many gaps in received data")
	}

	.queue[] = frameSorterEntry{Data: , Frame: }
	return nil
}

func ( *frameSorter) ( protocol.ByteCount) (*list.Element[byteInterval], bool) {
	for  := .gaps.Front();  != nil;  = .Next() {
		if  >= .Value.Start &&  <= .Value.End {
			return , true
		}
		if  < .Value.Start {
			return , false
		}
	}
	panic("no gap found")
}

func ( *frameSorter) ( *list.Element[byteInterval],  protocol.ByteCount) (*list.Element[byteInterval], bool) {
	for  := ;  != nil;  = .Next() {
		if  >= .Value.Start &&  < .Value.End {
			return , true
		}
		if  < .Value.Start {
			return .Prev(), false
		}
	}
	panic("no gap found")
}

// deleteConsecutive deletes consecutive frames from the queue, starting at pos
func ( *frameSorter) ( protocol.ByteCount) {
	for {
		,  := .queue[]
		if ! {
			break
		}
		 := protocol.ByteCount(len(.Data))
		delete(.queue, )
		if .Frame != nil {
			.Frame.PutBack()
		}
		 += 
	}
}

func ( *frameSorter) () (protocol.ByteCount, []byte, *wire.StreamFrame) {
	,  := .queue[.readPos]
	if ! {
		return .readPos, nil, nil
	}
	delete(.queue, .readPos)
	 := .readPos
	.readPos += protocol.ByteCount(len(.Data))
	if .gaps.Front().Value.End <= .readPos {
		panic("frame sorter BUG: read position higher than a gap")
	}
	return , .Data, .Frame
}

// HasMoreData says if there is any more data queued at *any* offset.
func ( *frameSorter) () bool {
	return len(.queue) > 0
}

var errTooLittleData = errors.New("too little data")

// Peek copies len(p) consecutive bytes starting at offset into p, without removing them.
// It is only possible to peek from an offset where a frame starts.
//
// If there isn't enough consecutive data available, errTooLittleData is returned.
func ( *frameSorter) ( protocol.ByteCount,  []byte) error {
	if len() == 0 {
		return nil
	}

	// first, check if we have enough consecutive data available
	 := 
	 := len()
	for  > 0 {
		,  := .queue[]
		if ! {
			return errTooLittleData
		}
		 := len(.Data)
		if  <=  {
			break // enough data available
		}
		 -= 
		 += protocol.ByteCount()
	}

	 = 
	var  int
	for  < len() {
		 := .queue[] // the entry is guaranteed to exist from the check above
		 += copy([:], .Data)
		 += protocol.ByteCount(len(.Data))
	}
	return nil
}