// Copyright 2009 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 flate

import (
	
	
	
)

// hcode is a huffman code with a bit code and bit length.
type hcode struct {
	code, len uint16
}

type huffmanEncoder struct {
	codes     []hcode
	freqcache []literalNode
	bitCount  [17]int32
	lns       byLiteral // stored to avoid repeated allocation in generate
	lfs       byFreq    // stored to avoid repeated allocation in generate
}

type literalNode struct {
	literal uint16
	freq    int32
}

// A levelInfo describes the state of the constructed tree for a given depth.
type levelInfo struct {
	// Our level.  for better printing
	level int32

	// The frequency of the last node at this level
	lastFreq int32

	// The frequency of the next character to add to this level
	nextCharFreq int32

	// The frequency of the next pair (from level below) to add to this level.
	// Only valid if the "needed" value of the next lower level is 0.
	nextPairFreq int32

	// The number of chains remaining to generate for this level before moving
	// up to the next level
	needed int32
}

// set sets the code and length of an hcode.
func ( *hcode) ( uint16,  uint16) {
	.len = 
	.code = 
}

func maxNode() literalNode { return literalNode{math.MaxUint16, math.MaxInt32} }

func newHuffmanEncoder( int) *huffmanEncoder {
	return &huffmanEncoder{codes: make([]hcode, )}
}

// Generates a HuffmanCode corresponding to the fixed literal table
func generateFixedLiteralEncoding() *huffmanEncoder {
	 := newHuffmanEncoder(maxNumLit)
	 := .codes
	var  uint16
	for  = 0;  < maxNumLit; ++ {
		var  uint16
		var  uint16
		switch {
		case  < 144:
			// size 8, 000110000  .. 10111111
			 =  + 48
			 = 8
			break
		case  < 256:
			// size 9, 110010000 .. 111111111
			 =  + 400 - 144
			 = 9
			break
		case  < 280:
			// size 7, 0000000 .. 0010111
			 =  - 256
			 = 7
			break
		default:
			// size 8, 11000000 .. 11000111
			 =  + 192 - 280
			 = 8
		}
		[] = hcode{code: reverseBits(, byte()), len: }
	}
	return 
}

func generateFixedOffsetEncoding() *huffmanEncoder {
	 := newHuffmanEncoder(30)
	 := .codes
	for  := range  {
		[] = hcode{code: reverseBits(uint16(), 5), len: 5}
	}
	return 
}

var fixedLiteralEncoding *huffmanEncoder = generateFixedLiteralEncoding()
var fixedOffsetEncoding *huffmanEncoder = generateFixedOffsetEncoding()

func ( *huffmanEncoder) ( []int32) int {
	var  int
	for ,  := range  {
		if  != 0 {
			 += int() * int(.codes[].len)
		}
	}
	return 
}

const maxBitsLimit = 16

// Return the number of literals assigned to each bit size in the Huffman encoding
//
// This method is only called when list.length >= 3
// The cases of 0, 1, and 2 literals are handled by special case code.
//
// list  An array of the literals with non-zero frequencies
//             and their associated frequencies. The array is in order of increasing
//             frequency, and has as its last element a special element with frequency
//             MaxInt32
// maxBits     The maximum number of bits that should be used to encode any literal.
//             Must be less than 16.
// return      An integer array in which array[i] indicates the number of literals
//             that should be encoded in i bits.
func ( *huffmanEncoder) ( []literalNode,  int32) []int32 {
	if  >= maxBitsLimit {
		panic("flate: maxBits too large")
	}
	 := int32(len())
	 = [0 : +1]
	[] = maxNode()

	// The tree can't have greater depth than n - 1, no matter what. This
	// saves a little bit of work in some small cases
	if  > -1 {
		 =  - 1
	}

	// Create information about each of the levels.
	// A bogus "Level 0" whose sole purpose is so that
	// level1.prev.needed==0.  This makes level1.nextPairFreq
	// be a legitimate value that never gets chosen.
	var  [maxBitsLimit]levelInfo
	// leafCounts[i] counts the number of literals at the left
	// of ancestors of the rightmost node at level i.
	// leafCounts[i][j] is the number of literals at the left
	// of the level j ancestor.
	var  [maxBitsLimit][maxBitsLimit]int32

	for  := int32(1);  <= ; ++ {
		// For every level, the first two items are the first two characters.
		// We initialize the levels as if we had already figured this out.
		[] = levelInfo{
			level:        ,
			lastFreq:     [1].freq,
			nextCharFreq: [2].freq,
			nextPairFreq: [0].freq + [1].freq,
		}
		[][] = 2
		if  == 1 {
			[].nextPairFreq = math.MaxInt32
		}
	}

	// We need a total of 2*n - 2 items at top level and have already generated 2.
	[].needed = 2* - 4

	 := 
	for {
		 := &[]
		if .nextPairFreq == math.MaxInt32 && .nextCharFreq == math.MaxInt32 {
			// We've run out of both leafs and pairs.
			// End all calculations for this level.
			// To make sure we never come back to this level or any lower level,
			// set nextPairFreq impossibly large.
			.needed = 0
			[+1].nextPairFreq = math.MaxInt32
			++
			continue
		}

		 := .lastFreq
		if .nextCharFreq < .nextPairFreq {
			// The next item on this row is a leaf node.
			 := [][] + 1
			.lastFreq = .nextCharFreq
			// Lower leafCounts are the same of the previous node.
			[][] = 
			.nextCharFreq = [].freq
		} else {
			// The next item on this row is a pair from the previous row.
			// nextPairFreq isn't valid until we generate two
			// more values in the level below
			.lastFreq = .nextPairFreq
			// Take leaf counts from the lower level, except counts[level] remains the same.
			copy([][:], [-1][:])
			[.level-1].needed = 2
		}

		if .needed--; .needed == 0 {
			// We've done everything we need to do for this level.
			// Continue calculating one level up. Fill in nextPairFreq
			// of that level with the sum of the two nodes we've just calculated on
			// this level.
			if .level ==  {
				// All done!
				break
			}
			[.level+1].nextPairFreq =  + .lastFreq
			++
		} else {
			// If we stole from below, move down temporarily to replenish it.
			for [-1].needed > 0 {
				--
			}
		}
	}

	// Somethings is wrong if at the end, the top level is null or hasn't used
	// all of the leaves.
	if [][] !=  {
		panic("leafCounts[maxBits][maxBits] != n")
	}

	 := .bitCount[:+1]
	 := 1
	 := &[]
	for  := ;  > 0; -- {
		// chain.leafCount gives the number of literals requiring at least "bits"
		// bits to encode.
		[] = [] - [-1]
		++
	}
	return 
}

// Look at the leaves and assign them a bit count and an encoding as specified
// in RFC 1951 3.2.2
func ( *huffmanEncoder) ( []int32,  []literalNode) {
	 := uint16(0)
	for ,  := range  {
		 <<= 1
		if  == 0 ||  == 0 {
			continue
		}
		// The literals list[len(list)-bits] .. list[len(list)-bits]
		// are encoded using "bits" bits, and get the values
		// code, code + 1, ....  The code values are
		// assigned in literal order (not frequency order).
		 := [len()-int():]

		.lns.sort()
		for ,  := range  {
			.codes[.literal] = hcode{code: reverseBits(, uint8()), len: uint16()}
			++
		}
		 = [0 : len()-int()]
	}
}

// Update this Huffman Code object to be the minimum code for the specified frequency count.
//
// freq  An array of frequencies, in which frequency[i] gives the frequency of literal i.
// maxBits  The maximum number of bits to use for any literal.
func ( *huffmanEncoder) ( []int32,  int32) {
	if .freqcache == nil {
		// Allocate a reusable buffer with the longest possible frequency table.
		// Possible lengths are codegenCodeCount, offsetCodeCount and maxNumLit.
		// The largest of these is maxNumLit, so we allocate for that case.
		.freqcache = make([]literalNode, maxNumLit+1)
	}
	 := .freqcache[:len()+1]
	// Number of non-zero literals
	 := 0
	// Set list to be the set of all non-zero literals and their frequencies
	for ,  := range  {
		if  != 0 {
			[] = literalNode{uint16(), }
			++
		} else {
			[] = literalNode{}
			.codes[].len = 0
		}
	}
	[len()] = literalNode{}

	 = [:]
	if  <= 2 {
		// Handle the small cases here, because they are awkward for the general case code. With
		// two or fewer literals, everything has bit length 1.
		for ,  := range  {
			// "list" is in order of increasing literal value.
			.codes[.literal].set(uint16(), 1)
		}
		return
	}
	.lfs.sort()

	// Get the number of literals for each bit count
	 := .bitCounts(, )
	// And do the assignment
	.assignEncodingAndSize(, )
}

type byLiteral []literalNode

func ( *byLiteral) ( []literalNode) {
	* = byLiteral()
	sort.Sort()
}

func ( byLiteral) () int { return len() }

func ( byLiteral) (,  int) bool {
	return [].literal < [].literal
}

func ( byLiteral) (,  int) { [], [] = [], [] }

type byFreq []literalNode

func ( *byFreq) ( []literalNode) {
	* = byFreq()
	sort.Sort()
}

func ( byFreq) () int { return len() }

func ( byFreq) (,  int) bool {
	if [].freq == [].freq {
		return [].literal < [].literal
	}
	return [].freq < [].freq
}

func ( byFreq) (,  int) { [], [] = [], [] }

func reverseBits( uint16,  byte) uint16 {
	return bits.Reverse16( << (16 - ))
}