package matchfinder

import (
	
	
	
	
)

// Pathfinder is a MatchFinder that uses hash chains to find matches, and a
// shortest-path optimizer to choose which matches to use.
type Pathfinder struct {
	// MaxDistance is the maximum distance (in bytes) to look back for
	// a match. The default is 65535.
	MaxDistance int

	// MinLength is the length of the shortest match to return.
	// The default is 4.
	MinLength int

	// HashLen is the number of bytes to use to calculate the hashes.
	// The maximum is 8 and the default is 6.
	HashLen int

	// TableBits is the number of bits in the hash table indexes.
	// The default is 17 (128K entries).
	TableBits int

	// ChainLength is how many entries to search on the "match chain" of older
	// locations with the same hash as the current location.
	ChainLength int

	table []uint32
	chain []uint32

	history []byte

	// holding onto buffers to reduce allocations:

	arrivals     []arrival
	foundMatches []absoluteMatch
	matches      []Match
}

func ( *Pathfinder) () {
	for  := range .table {
		.table[] = 0
	}
	.history = .history[:0]
	.chain = .chain[:0]
}

// An arrival represents how we got to a certain byte position.
// The cost is the total cost to get there from the beginning of the block.
// If distance > 0, the arrival is with a match.
// If distance == 0, the arrival is with a run of literals.
type arrival struct {
	length   uint32
	distance uint32
	cost     float32
}

const (
	baseMatchCost float32 = 4
)

func ( *Pathfinder) ( []Match,  []byte) []Match {
	if .MaxDistance == 0 {
		.MaxDistance = 65535
	}
	if .MinLength == 0 {
		.MinLength = 4
	}
	if .HashLen == 0 {
		.HashLen = 6
	}
	if .TableBits == 0 {
		.TableBits = 17
	}
	if len(.table) < 1<<.TableBits {
		.table = make([]uint32, 1<<.TableBits)
	}

	var  [256]uint32
	for ,  := range  {
		[]++
	}
	var  [256]float32
	for ,  := range  {
		 := max(math.Log2(float64(len())/float64()), 1)
		[] = float32()
	}

	// Each element in arrivals corresponds to the position just after
	// the corresponding byte in src.
	 := .arrivals
	if len() < len() {
		 = make([]arrival, len())
		.arrivals = 
	} else {
		 = [:len()]
		for  := range  {
			[] = arrival{}
		}
	}

	if len(.history) > .MaxDistance*2 {
		// Trim down the history buffer.
		 := len(.history) - .MaxDistance
		copy(.history, .history[:])
		.history = .history[:.MaxDistance]
		.chain = .chain[:.MaxDistance]

		for ,  := range .table {
			 := max(int()-, 0)
			.table[] = uint32()
		}
	}

	// Append src to the history buffer.
	 := len(.history)
	.history = append(.history, ...)
	.chain = append(.chain, make([]uint32, len())...)
	 = .history

	// Calculate hashes and build the chain.
	for  := ;  < len()-7; ++ {
		 := ((binary.LittleEndian.Uint64([:]) & (1<<(8*.HashLen) - 1)) * hashMul64) >> (64 - .TableBits)
		 := int(.table[])
		.table[] = uint32()
		if  != 0 {
			 :=  - 
			.chain[] = uint32()
		}
	}

	// Look for matches, and collect them in foundMatches. Later we'll figure out
	// which ones to actually use.
	 := .foundMatches[:0]
	var  absoluteMatch
	 := 
	for  < len()-7 {
		 := .chain[]
		if  == 0 {
			++
			continue
		}
		 :=  - int()
		if  <= 0 || - > .MaxDistance {
			++
			continue
		}

		var  absoluteMatch

		if  >= .End &&  != (absoluteMatch{}) {
			// Look for a repeat match at i+1.
			 := .Start - .Match
			if binary.LittleEndian.Uint32([+1:]) == binary.LittleEndian.Uint32([+1-:]) {
				 := extendMatch2(, +1, +1-, +1)
				if .End-.Start > .MinLength {
					 = 
					 = append(, )
				}
			}
		}

		if binary.LittleEndian.Uint32([:]) == binary.LittleEndian.Uint32([:]) {
			 := extendMatch2(, , , max(, .Start))
			if .End-.Start > .MinLength {
				 = 
				 = append(, )
			}
		}

		for range .ChainLength {
			 := .chain[]
			if  == 0 {
				break
			}
			 -= int()
			if  <= 0 || - > .MaxDistance {
				break
			}
			if binary.LittleEndian.Uint32([:]) == binary.LittleEndian.Uint32([:]) {
				 := extendMatch2(, , , max(, .Start))
				if .End-.Start > .MinLength && .End-.Start > .End-.Start {
					 = 
					 = append(, )
				}
			}
		}

		if  < .End && .End-.Start <= .End-.Start {
			// We were looking for an overlapping match, but we didn't find one longer
			// than the previous match. So we'll go back to sequential search,
			// starting right after the previous match.
			 = .End
			continue
		}

		if  == (absoluteMatch{}) {
			// No match found. Continue with sequential search.
			++
			continue
		}

		// We've found a match; now look for matches overlapping the end of it.
		 = 
		 = .End + 2 - .HashLen
	}

	.foundMatches = 

	slices.SortFunc(, func(,  absoluteMatch) int { return .Start - .Start })
	 := 0
	var  absoluteMatch

	for  := ;  < len(); ++ {
		var  arrival
		if  >  {
			 = [--1]
		}

		 := 0
		if .distance == 0 {
			 = int(.length)
		}
		 := 0
		if - >  {
			 = int([--1-].distance)
		}

		 := [[]]
		 := &[-]
		if .cost == 0 || .cost+ < .cost {
			* = arrival{
				cost:   .cost + ,
				length: uint32( + 1),
			}
		}

		for  < len() && [].Start ==  {
			 := []
			++
			if .End > .End {
				 = 
			}
			 := baseMatchCost + float32(bits.Len(uint()))
			if .Start-.Match !=  {
				 += float32(bits.Len(uint(.Start - .Match)))
			}
			for  := .Start + .MinLength;  <= .End; ++ {
				 := 
				if -.Start < 6 {
					// Matches shorter than 6 are comparatively rare, and therefore
					// have longer codes.
					 += float32(6-(-.Start)) * 2
				}
				 := &[--1]
				if .cost == 0 || .cost+ < .cost {
					* = arrival{
						length:   uint32( - .Start),
						distance: uint32(.Start - .Match),
						cost:     .cost + ,
					}
				}
			}
		}

		// If a match from an earlier position extends far enough past the current
		// position, try using the tail of it, starting from here.
		if  == 0 && .Start !=  && .End >= +.MinLength &&
			!(.length != 0 && .distance == uint32(.Start-.Match)) {
			 := baseMatchCost + float32(bits.Len(uint(.Start-.Match)))
			for  :=  + .MinLength;  <= .End; ++ {
				 := 
				if - < 6 {
					// Matches shorter than 6 are comparatively rare, and therefore
					// have longer codes.
					 += float32(6-(-)) * 2
				}
				 := &[--1]
				if .cost == 0 || .cost+ < .cost {
					* = arrival{
						length:   uint32( - ),
						distance: uint32(.Start - .Match),
						cost:     .cost + ,
					}
				}
			}
		}

		 := .chain[]
		if  == 0 {
			continue
		}
		 :=  - int()
		if  <= 0 || - > .MaxDistance {
			continue
		}
	}

	// We've found the shortest path; now walk it backward and store the matches.
	 := .matches[:0]
	 = len() - 1
	for  >= 0 {
		 := []
		if .distance > 0 {
			 = append(, Match{
				Length:   int(.length),
				Distance: int(.distance),
			})
			 -= int(.length)
		} else {
			if len() == 0 {
				 = append(, Match{})
			}
			[len()-1].Unmatched = int(.length)
			 -= int(.length)
		}
	}
	.matches = 

	slices.Reverse()

	return append(, ...)
}