43. Multiply Strings

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:
需要模拟单个位上的乘法，主要要储存进位和余数
例如  18 * 8
-------
18
 8
64 --> 个位 (6, 4)  //进6， 余4 a(个位)*b(个位)
8  ->  十位 8+6 (1,4) //进1，余4，a(十位) * b(个位） a(个位) * b(十位)

我们从个位开始计算，每次计算的结果丢入到一个栈结构中，
例如 18 * 12
例如首先计算18* 2， 先是8*2，产生了1的进位，6的余数，6进入栈，1记录
然后1*2， 2+之前的进位，产生3， 0的进位，3的余数，3进入栈，一次循环结束。
第二次循环，从栈的index = 1 开始，注意这里计算位置要反向计算
18*1 ， 先是8*1，产生0的进位，8的余数，8丢进栈的1位置，1有值，则为3+8 = 11，
1 放入栈，产生了1 的进位，放到当前存储进位的位置
然后1*1， 产生了0的进位，1的余数，加上进位，就变成2， 放入到栈中。

单个过程就是：
计算->存储进位->pushStack->返回进位->合并存储进位
下一次

//Error: 如果要频繁的遍历字符，也许转换为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]()  //存储结构
    var bit: Int = 0  //存储进位

    //计算是从个位开始，所以是反向计算
    print("0000+ \(CFAbsoluteTimeGetCurrent())")
    let num1Scalar = num1.cString(using: .ascii)
    let num2Scalar = num2.cString(using: .ascii)
    print("1111+ \(CFAbsoluteTimeGetCurrent())")
    //把计算结果push到 stack 结构中去，然后返回结果产生的进位
    func push(_ left: Int, _ index: Int) -> Int {
        var appendValue = left //应该合并进的数
        var bitValue = 0     //产生的进位
        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
    }

    //根据输入值，计算出进位，返回(应该入栈的结果，进位)
    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)  //计算出入栈产生的下一次进位
            bit = add + pushAdd
        }
        if (bit != 0) {
            //一次内循环结束，如果还有进位，则需要进位
            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"))