<commit_before>// Copyright (c) 2017 <NAME>
// Licensed under MIT License
//
// See LICENSE for license information

import Foundation

// BZip2 specific function for generation of HuffmanLength array from stats.
extension BZip2 {

    /**
     Based on "procedure for generating the lists which specify a Huffman code table" (annexes C and K)
     from Recommendation T.81 of ITU (aka JPEG specfications).
     */
    static func lengths(from stats: [Int]) -> [HuffmanLength] {
        if stats.count == 0 {
            return []
        } else if stats.count == 1 {
            return [HuffmanLength(symbol: 0, codeLength: 1)]
        }

        /// Mutable copy of input `stats`.
        var stats = stats

        var codeSizes = Array(repeating: 0, count: 259)
        var others = Array(repeating: -1, count: 259)

        while true {
            var c1 = -1
            var minFreq = Int.max
            for i in 0..<stats.count {
                if stats[i] > 0 && stats[i] <= minFreq {
                    minFreq = stats[i]
                    c1 = i
                }
            }

            var c2 = -1
            minFreq = Int.max
            for i in 0..<stats.count {
                if stats[i] > 0 && stats[i] <= minFreq && i != c1 {
                    minFreq = stats[i]
                    c2 = i
                }
            }

            guard c2 >= 0
                else { break }

            stats[c1] += stats[c2]
            stats[c2] = 0

            codeSizes[c1] += 1
            while others[c1] >= 0 {
                c1 = others[c1]
                codeSizes[c1] += 1

            }
            others[c1] = c2

            codeSizes[c2] += 1
            while others[c2] >= 0 {
                c2 = others[c2]
                codeSizes[c2] += 1
            }
        }

        // Now we count code lengths.
        // In worst case scenario the maximum code length is 258.
        var bits = Array(repeating: 0, count: 259)
        for i in 0..<bits.count {
            // We don't check for zero code length because we have unused element in `bits` array for them.
            bits[codeSizes[i]] += 1
        }

        // Adjust_bits
        for i in stride(from: 258, to: 20, by: -1) {
            while bits[i] > 0 {
                var j = i - 2
                while bits[j] == 0 {
                    j -= 1
                }
                bits[i] -= 2
                bits[i - 1] += 1
                bits[j + 1] += 2
                bits[j] -= 1
            }
        }

        // Generate_size_table
        var symbol = 0
        var lengths = [HuffmanLength]()
        for i in 1...20 {
            var j = 1
            while j <= bits[i] {
                lengths.append(HuffmanLength(symbol: symbol, codeLength: i))
                symbol += 1
                j += 1
            }
        }

        return lengths
    }

}<commit_msg>Make bzip2 lengths creation algorithm slightly more space efficient<commit_after>// Copyright (c) 2017 <NAME>
// Licensed under MIT License
//
// See LICENSE for license information

import Foundation

// BZip2 specific function for generation of HuffmanLength array from stats.
extension BZip2 {

    /**
     Based on "procedure for generating the lists which specify a Huffman code table" (annexes C and K)
     from Recommendation T.81 of ITU (aka JPEG specfications).
     */
    static func lengths(from stats: [Int]) -> [HuffmanLength] {
        if stats.count == 0 {
            return []
        } else if stats.count == 1 {
            return [HuffmanLength(symbol: 0, codeLength: 1)]
        }

        let symbolsCount = stats.count

        /// Mutable copy of input `stats`.
        var stats = stats

        var codeSizes = Array(repeating: 0, count: symbolsCount)
        var others = Array(repeating: -1, count: symbolsCount)

        while true {
            var c1 = -1
            var minFreq = Int.max
            for i in 0..<stats.count {
                if stats[i] > 0 && stats[i] <= minFreq {
                    minFreq = stats[i]
                    c1 = i
                }
            }

            var c2 = -1
            minFreq = Int.max
            for i in 0..<stats.count {
                if stats[i] > 0 && stats[i] <= minFreq && i != c1 {
                    minFreq = stats[i]
                    c2 = i
                }
            }

            guard c2 >= 0
                else { break }

            stats[c1] += stats[c2]
            stats[c2] = 0

            codeSizes[c1] += 1
            while others[c1] >= 0 {
                c1 = others[c1]
                codeSizes[c1] += 1

            }
            others[c1] = c2

            codeSizes[c2] += 1
            while others[c2] >= 0 {
                c2 = others[c2]
                codeSizes[c2] += 1
            }
        }

        // Now we count code lengths.
        var bits = Array(repeating: 0, count: symbolsCount)
        for i in 0..<bits.count {
            // We don't check for zero code length because we have unused element in `bits` array for them.
            bits[codeSizes[i]] += 1
        }

        // Adjust_bits
        for i in stride(from: symbolsCount - 1, to: 20, by: -1) {
            while bits[i] > 0 {
                var j = i - 2
                while bits[j] == 0 {
                    j -= 1
                }
                bits[i] -= 2
                bits[i - 1] += 1
                bits[j + 1] += 2
                bits[j] -= 1
            }
        }

        // Generate_size_table
        var symbol = 0
        var lengths = [HuffmanLength]()
        for i in 1...min(20, bits.count - 1) {
            var j = 1
            while j <= bits[i] {
                lengths.append(HuffmanLength(symbol: symbol, codeLength: i))
                symbol += 1
                j += 1
            }
        }

        return lengths
    }

}
{'fraction_non_alphanumeric': 0.10151334807005612, 'fraction_numerical': 0.027546335657201156, 'mean_word_length': 1.1226993865030674, 'pattern_counts': {'":': 0, '<': 17, '<?xml version=': 0, '>': 19, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '7527982', 'n_tokens_mistral': 1835, 'n_tokens_neox': 1649, 'n_words': 534}