import Foundation

/*
43. Multiply Strings
Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2.
Note:

The length of both num1 and num2 is < 110.
Both num1 and num2 contains only digits 0-9.
Both num1 and num2 does not contain any leading zero.
You must not use any built-in BigInteger library or convert the inputs to integer directly.
*/

/*
Thinking:
需要模擬單個位上的乘法，主要要儲存進位和余數(shù)
例如  18 * 8
-------
18
 8
64 --> 個位 (6, 4)  //進6， 余4 a(個位)*b(個位)
8  ->  十位 8+6 (1,4) //進1，余4，a(十位) * b(個位） a(個位) * b(十位)

我們從個位開始計算，每次計算的結(jié)果丟入到一個棧結(jié)構(gòu)中，
例如 18 * 12
例如首先計算18* 2， 先是8*2，產(chǎn)生了1的進位，6的余數(shù)，6進入棧，1記錄
然后1*2， 2+之前的進位，產(chǎn)生3， 0的進位，3的余數(shù)，3進入棧，一次循環(huán)結(jié)束。
第二次循環(huán)，從棧的index = 1 開始，注意這里計算位置要反向計算
18*1 ， 先是8*1，產(chǎn)生0的進位，8的余數(shù)，8丟進棧的1位置，1有值，則為3+8 = 11，
1 放入棧，產(chǎn)生了1 的進位，放到當前存儲進位的位置
然后1*1， 產(chǎn)生了0的進位，1的余數(shù)，加上進位，就變成2， 放入到棧中。

單個過程就是：
計算->存儲進位->pushStack->返回進位->合并存儲進位
下一次

//Error: 如果要頻繁的遍歷字符，也許轉(zhuǎn)換為C字符串更高效。
*/


func multiply(_ num1: String, _ num2: String) -> String {
    let length1 = num1.lengthOfBytes(using: .ascii)
    let length2 = num2.lengthOfBytes(using: .ascii)
    guard length1 > 0, length2 > 0 else {
        return ""
    }

    var calcResultStack: [Int] = [Int]()  //存儲結(jié)構(gòu)
    var bit: Int = 0  //存儲進位

    //計算是從個位開始，所以是反向計算
    print("0000+ \(CFAbsoluteTimeGetCurrent())")
    let num1Scalar = num1.cString(using: .ascii)
    let num2Scalar = num2.cString(using: .ascii)
    print("1111+ \(CFAbsoluteTimeGetCurrent())")
    //把計算結(jié)果push到 stack 結(jié)構(gòu)中去，然后返回結(jié)果產(chǎn)生的進位
    func push(_ left: Int, _ index: Int) -> Int {
        var appendValue = left //應該合并進的數(shù)
        var bitValue = 0     //產(chǎn)生的進位
        if calcResultStack.count > index {
            appendValue += calcResultStack[index]
            calcResultStack[index] = appendValue % 10
            bitValue = appendValue / 10
        } else {
            //Error: 不能直接存進去，因為也可能超過10
            calcResultStack.append(appendValue % 10)
            bitValue = appendValue / 10
        }

        return bitValue
    }

    //根據(jù)輸入值，計算出進位，返回(應該入棧的結(jié)果，進位)
    let zeroValue = ("0" as UnicodeScalar).value  //獲取0的 unicode值
    func calc(_ left: Int, _ right: Int) -> (Int, Int) {
        let l = left - Int(zeroValue)
        let r = right - Int(zeroValue)
        let value = l * r
        return (Int(value % 10), Int(value / 10))
    }

    print("2222+ \(CFAbsoluteTimeGetCurrent())")
    for i in stride(from: length1 - 1, through: 0, by: -1) {
        let v = Int(num1Scalar![i])
        for i2 in stride(from: length2 - 1, through: 0, by: -1) {
            let v2 = Int(num2Scalar![i2])
            var (result, add) = calc(v, v2)  //add 是下一次計算需要的進位
            result += bit //先加上之前的進位
            let pushAdd = push(result, length1 - 1 - i + length2 - 1 - i2)  //計算出入棧產(chǎn)生的下一次進位
            bit = add + pushAdd
        }
        if (bit != 0) {
            //一次內(nèi)循環(huán)結(jié)束，如果還有進位，則需要進位
            calcResultStack.append(bit)
            bit = 0
        }
    }
    print("3333+ \(CFAbsoluteTimeGetCurrent())")

    let reversedStack = calcResultStack.map {
        String($0)
    }.reversed()
    var retString: String = ""
    var start = false
    for value in reversedStack {
        if value != "0", !start {
            start = true
        }
        if start {
            retString.append(value)
        }
    }

    if retString.isEmpty {
        retString = "0"
    }

    return retString
}

print(multiply("7", "871"))