source: code/trunk/vendor/github.com/andybalholm/brotli/cluster_command.go@ 145

package brotli

/* 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 compareAndPushToQueueCommand(out []histogramCommand, cluster_size []uint32, idx1 uint32, idx2 uint32, max_num_pairs uint, pairs []histogramPair, num_pairs *uint) {
        var is_good_pair bool = false
        var p histogramPair
        p.idx2 = 0
        p.idx1 = p.idx2
        p.cost_combo = 0
        p.cost_diff = p.cost_combo
        if idx1 == idx2 {
                return
        }

        if idx2 < idx1 {
                var t uint32 = idx2
                idx2 = idx1
                idx1 = t
        }

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

        if out[idx1].total_count_ == 0 {
                p.cost_combo = out[idx2].bit_cost_
                is_good_pair = true
        } else if out[idx2].total_count_ == 0 {
                p.cost_combo = out[idx1].bit_cost_
                is_good_pair = true
        } else {
                var threshold float64
                if *num_pairs == 0 {
                        threshold = 1e99
                } else {
                        threshold = brotli_max_double(0.0, pairs[0].cost_diff)
                }
                var combo histogramCommand = out[idx1]
                var cost_combo float64
                histogramAddHistogramCommand(&combo, &out[idx2])
                cost_combo = populationCostCommand(&combo)
                if cost_combo < threshold-p.cost_diff {
                        p.cost_combo = cost_combo
                        is_good_pair = true
                }
        }

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

                        pairs[0] = p
                } else if *num_pairs < max_num_pairs {
                        pairs[*num_pairs] = p
                        (*num_pairs)++
                }
        }
}

func histogramCombineCommand(out []histogramCommand, cluster_size []uint32, symbols []uint32, clusters []uint32, pairs []histogramPair, num_clusters uint, symbols_size uint, max_clusters uint, max_num_pairs uint) uint {
        var cost_diff_threshold float64 = 0.0
        var min_cluster_size uint = 1
        var num_pairs 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 idx1 uint
                for idx1 = 0; idx1 < num_clusters; idx1++ {
                        var idx2 uint
                        for idx2 = idx1 + 1; idx2 < num_clusters; idx2++ {
                                compareAndPushToQueueCommand(out, cluster_size, clusters[idx1], clusters[idx2], max_num_pairs, pairs[0:], &num_pairs)
                        }
                }
        }

        for num_clusters > min_cluster_size {
                var best_idx1 uint32
                var best_idx2 uint32
                var i uint
                if pairs[0].cost_diff >= cost_diff_threshold {
                        cost_diff_threshold = 1e99
                        min_cluster_size = max_clusters
                        continue
                }

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

                best_idx2 = pairs[0].idx2
                histogramAddHistogramCommand(&out[best_idx1], &out[best_idx2])
                out[best_idx1].bit_cost_ = pairs[0].cost_combo
                cluster_size[best_idx1] += cluster_size[best_idx2]
                for i = 0; i < symbols_size; i++ {
                        if symbols[i] == best_idx2 {
                                symbols[i] = best_idx1
                        }
                }

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

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

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

                                copy_to_idx++
                        }

                        num_pairs = copy_to_idx
                }

                /* Push new pairs formed with the combined histogram to the heap. */
                for i = 0; i < num_clusters; i++ {
                        compareAndPushToQueueCommand(out, cluster_size, best_idx1, clusters[i], max_num_pairs, pairs[0:], &num_pairs)
                }
        }

        return num_clusters
}

/* What is the bit cost of moving histogram from cur_symbol to candidate. */
func histogramBitCostDistanceCommand(histogram *histogramCommand, candidate *histogramCommand) float64 {
        if histogram.total_count_ == 0 {
                return 0.0
        } else {
                var tmp histogramCommand = *histogram
                histogramAddHistogramCommand(&tmp, candidate)
                return populationCostCommand(&tmp) - candidate.bit_cost_
        }
}