package brotli

import 

/* Copyright 2013 Google Inc. All Rights Reserved.

   Distributed under MIT license.
   See file LICENSE for detail or copy at https://opensource.org/licenses/MIT
*/

/* Computes the bit cost reduction by combining out[idx1] and out[idx2] and if
   it is below a threshold, stores the pair (idx1, idx2) in the *pairs queue. */
func compareAndPushToQueueLiteral( []histogramLiteral,  []uint32,  uint32,  uint32,  uint,  []histogramPair,  *uint) {
	var  bool = false
	var  histogramPair
	.idx2 = 0
	.idx1 = .idx2
	.cost_combo = 0
	.cost_diff = .cost_combo
	if  ==  {
		return
	}

	if  <  {
		var  uint32 = 
		 = 
		 = 
	}

	.idx1 = 
	.idx2 = 
	.cost_diff = 0.5 * clusterCostDiff(uint([]), uint([]))
	.cost_diff -= [].bit_cost_
	.cost_diff -= [].bit_cost_

	if [].total_count_ == 0 {
		.cost_combo = [].bit_cost_
		 = true
	} else if [].total_count_ == 0 {
		.cost_combo = [].bit_cost_
		 = true
	} else {
		var  float64
		if * == 0 {
			 = 1e99
		} else {
			 = brotli_max_double(0.0, [0].cost_diff)
		}
		var  histogramLiteral = []
		var  float64
		histogramAddHistogramLiteral(&, &[])
		 = populationCostLiteral(&)
		if  < -.cost_diff {
			.cost_combo = 
			 = true
		}
	}

	if  {
		.cost_diff += .cost_combo
		if * > 0 && histogramPairIsLess(&[0], &) {
			/* Replace the top of the queue if needed. */
			if * <  {
				[*] = [0]
				(*)++
			}

			[0] = 
		} else if * <  {
			[*] = 
			(*)++
		}
	}
}

func histogramCombineLiteral( []histogramLiteral,  []uint32,  []uint32,  []uint32,  []histogramPair,  uint,  uint,  uint,  uint) uint {
	var  float64 = 0.0
	var  uint = 1
	var  uint = 0
	{
		/* We maintain a vector of histogram pairs, with the property that the pair
		   with the maximum bit cost reduction is the first. */
		var  uint
		for  = 0;  < ; ++ {
			var  uint
			for  =  + 1;  < ; ++ {
				compareAndPushToQueueLiteral(, , [], [], , [0:], &)
			}
		}
	}

	for  >  {
		var  uint32
		var  uint32
		var  uint
		if [0].cost_diff >=  {
			 = 1e99
			 = 
			continue
		}

		/* Take the best pair from the top of heap. */
		 = [0].idx1

		 = [0].idx2
		histogramAddHistogramLiteral(&[], &[])
		[].bit_cost_ = [0].cost_combo
		[] += []
		for  = 0;  < ; ++ {
			if [] ==  {
				[] = 
			}
		}

		for  = 0;  < ; ++ {
			if [] ==  {
				copy([:], [+1:][:--1])
				break
			}
		}

		--
		{
			/* Remove pairs intersecting the just combined best pair. */
			var  uint = 0
			for  = 0;  < ; ++ {
				var  *histogramPair = &[]
				if .idx1 ==  || .idx2 ==  || .idx1 ==  || .idx2 ==  {
					/* Remove invalid pair from the queue. */
					continue
				}

				if histogramPairIsLess(&[0], ) {
					/* Replace the top of the queue if needed. */
					var  histogramPair = [0]
					[0] = *
					[] = 
				} else {
					[] = *
				}

				++
			}

			 = 
		}

		/* Push new pairs formed with the combined histogram to the heap. */
		for  = 0;  < ; ++ {
			compareAndPushToQueueLiteral(, , , [], , [0:], &)
		}
	}

	return 
}

/* What is the bit cost of moving histogram from cur_symbol to candidate. */
func histogramBitCostDistanceLiteral( *histogramLiteral,  *histogramLiteral) float64 {
	if .total_count_ == 0 {
		return 0.0
	} else {
		var  histogramLiteral = *
		histogramAddHistogramLiteral(&, )
		return populationCostLiteral(&) - .bit_cost_
	}
}

/* Find the best 'out' histogram for each of the 'in' histograms.
   When called, clusters[0..num_clusters) contains the unique values from
   symbols[0..in_size), but this property is not preserved in this function.
   Note: we assume that out[]->bit_cost_ is already up-to-date. */
func histogramRemapLiteral( []histogramLiteral,  uint,  []uint32,  uint,  []histogramLiteral,  []uint32) {
	var  uint
	for  = 0;  < ; ++ {
		var  uint32
		if  == 0 {
			 = [0]
		} else {
			 = [-1]
		}
		var  float64 = histogramBitCostDistanceLiteral(&[], &[])
		var  uint
		for  = 0;  < ; ++ {
			var  float64 = histogramBitCostDistanceLiteral(&[], &[[]])
			if  <  {
				 = 
				 = []
			}
		}

		[] = 
	}

	/* Recompute each out based on raw and symbols. */
	for  = 0;  < ; ++ {
		histogramClearLiteral(&[[]])
	}

	for  = 0;  < ; ++ {
		histogramAddHistogramLiteral(&[[]], &[])
	}
}

/* Reorders elements of the out[0..length) array and changes values in
   symbols[0..length) array in the following way:
     * when called, symbols[] contains indexes into out[], and has N unique
       values (possibly N < length)
     * on return, symbols'[i] = f(symbols[i]) and
                  out'[symbols'[i]] = out[symbols[i]], for each 0 <= i < length,
       where f is a bijection between the range of symbols[] and [0..N), and
       the first occurrences of values in symbols'[i] come in consecutive
       increasing order.
   Returns N, the number of unique values in symbols[]. */

var histogramReindexLiteral_kInvalidIndex uint32 = math.MaxUint32

func histogramReindexLiteral( []histogramLiteral,  []uint32,  uint) uint {
	var  []uint32 = make([]uint32, )
	var  uint32
	var  []histogramLiteral
	var  uint
	for  = 0;  < ; ++ {
		[] = histogramReindexLiteral_kInvalidIndex
	}

	 = 0
	for  = 0;  < ; ++ {
		if [[]] == histogramReindexLiteral_kInvalidIndex {
			[[]] = 
			++
		}
	}

	/* TODO: by using idea of "cycle-sort" we can avoid allocation of
	   tmp and reduce the number of copying by the factor of 2. */
	 = make([]histogramLiteral, )

	 = 0
	for  = 0;  < ; ++ {
		if [[]] ==  {
			[] = [[]]
			++
		}

		[] = [[]]
	}

	 = nil
	for  = 0; uint32() < ; ++ {
		[] = []
	}

	 = nil
	return uint()
}

func clusterHistogramsLiteral( []histogramLiteral,  uint,  uint,  []histogramLiteral,  *uint,  []uint32) {
	var  []uint32 = make([]uint32, )
	var  []uint32 = make([]uint32, )
	var  uint = 0
	var  uint = 64
	var  uint =  *  / 2
	var  []histogramPair = make([]histogramPair, ( + 1))
	var  uint

	/* For the first pass of clustering, we allow all pairs. */
	for  = 0;  < ; ++ {
		[] = 1
	}

	for  = 0;  < ; ++ {
		[] = []
		[].bit_cost_ = populationCostLiteral(&[])
		[] = uint32()
	}

	for  = 0;  < ;  +=  {
		var  uint = brotli_min_size_t(-, )
		var  uint
		var  uint
		for  = 0;  < ; ++ {
			[+] = uint32( + )
		}

		 = histogramCombineLiteral(, , [:], [:], , , , , )
		 += 
	}
	{
		/* For the second pass, we limit the total number of histogram pairs.
		   After this limit is reached, we only keep searching for the best pair. */
		var  uint = brotli_min_size_t(64*, (/2)*)
		if  < ( + 1) {
			var  uint
			if  == 0 {
				 =  + 1
			} else {
				 = 
			}
			var  []histogramPair
			for  < ( + 1) {
				 *= 2
			}
			 = make([]histogramPair, )
			if  != 0 {
				copy(, [:])
			}

			 = 
			 = 
		}

		/* Collapse similar histograms. */
		 = histogramCombineLiteral(, , , , , , , , )
	}

	 = nil
	 = nil

	/* Find the optimal map from original histograms to the final ones. */
	histogramRemapLiteral(, , , , , )

	 = nil

	/* Convert the context map to a canonical form. */
	* = histogramReindexLiteral(, , )
}