swiftのNumeric構造体を作りInt型の時だけmod計算する【競技プログラミング】

# はじめに
- タイトルを見ても、何を言いたいのか伝わりづらくてゴメンナサイ。なろう系小説も長いタイトルのわりに雰囲気しか伝わらないよね？同じようなものだと思って欲しい。
- [先日、正方行列の構造体を作った](https://qiita.com/kei_tnk/items/eb4d2829e85a59ae8522)けど、正方行列の要素がInt型の時だけmodして要素の中身を軽量化しようとしたら頭がこんがらがったから、そこだけ切り出したのが今回の投稿です。
- swiftは型定義をしっかりやらないといけないので、慣れるまでは大変だね。まぁ。慣れたら慣れたで、pythonみたいな型が適当な言語が気持ち悪くて馴染めなくなるんだけど。

# 加算代入演算「+=」のみを実装したNumeric構造体
- まず、mod導入前の、シンプルなNumeric構造体を作る。ちなみに[Numeric](https://developer.apple.com/documentation/swift/numeric)は「加減算と乗算が出来る」という制約を持つプロトコルです。
```swift
struct Num<T:Numeric> {
    private var data:T

    init(_ data:T){
        self.data = data
    }
    
    static func +=(left:inout Self,right:Self){
        left.data += right.data
    }
}

var (dbl1,dbl2) = (Num(11.1),Num(22.2))
var (int1,int2) = (Num(11),Num(22))

dbl1 += dbl2
print(dbl1) // Num<Double>(data: 33.3)

int1 += int2
print(int1) // Num<Int>(data: 33)
```

# 要素の型がIntの時だけmを法とした要素とする構造体
- 競技プログラミングでは、解答の数値が大きくなるとき、modにより数を小さくすることが多いため、Int型の時にmod計算するように機能を追加する。
```swift
struct Num<T:Numeric> {
    private var data:T
    let m : Int? // 追加①

    init(_ data:T){
        self.m = nil // 追加②
        self.data = data
    }
    init(_ data:T,m:Int? = nil) where T==Int{ // 追加③
        self.m = m
        if let mod = m {
            self.data = data % mod
        } else {
            self.data = data            
        }
    }
    
    static func +=(left:inout Self,right:Self){
        left.data += right.data
    }
    static func +=(left:inout Self,right:Self) where T==Int { // 追加④
        left.data += right.data
        if let mod = left.m { left.data %= mod }
    }
}

var (dbl1,dbl2) = (Num(11.1),Num(22.2))
var (int1,int2) = (Num(11,m:13),Num(22)) // 追加⑤int1でm=13

dbl1 += dbl2
print(dbl1) // Num<Double>(data: 33.3, m: nil)

int1 += int2
print(int1) // Num<Int>(data: 7, m: Optional(13))
```
- 上記のように、型ジェネリックTについて、通常はNumericプロトコルに属すところ、更に細分化して、Int型に属すときは、mの中身がnilでなければ、イニシャライザinitと演算子+=で、mod計算を行わせている。
- 上記の計算例では、m=13としたため、mod計算前は33となっていた値が、7となっている。

# 累乗計算の関数powもNumeric用とInt用を別に用意する
- まず、「\*=」関数を「+=」と同様に作成する。当然、Intではmod対応版を用意している。
- mod対応は「\*=」関数の中で行うので、関数powの中ではmod計算の為のコードは書かない。よって、Numeric用もInt用も中身のコードが全く同じとなるが、「\*=」がNumeric版とInt版の二種類有るので、powもInt版の「\*=」を使いたければ、要素がInt版である制約を宣言しないと駄目。
- ちなみに、累乗計算を高速に行うために、[繰り返し二乗法](https://qiita.com/kei_tnk/items/a622eec4e7a9d0c47aca)を採用してます。
```swift
    static func *=(left:inout Self,right:Self){
        left.data *= right.data
    }
    static func *=(left:inout Self,right:Self) where T==Int { // 追加④
        left.data *= right.data
        if let mod = left.m { left.data %= mod }
    }    
    
    func pow(_ n:Int)->Self {
        var ans = self
        var x = self
        var i = n - 1
        while i > 0 {
            if i % 2 == 1 {ans *= x}
            x *= x
            i >>= 1
        }
        return ans
    }
    // Int制約版のpow関数
    func pow(_ n:Int)->Self where Self == Num<Int> {
        var ans = self
        var x = self
        var i = n - 1
        while i > 0 {
            if i % 2 == 1 {ans *= x}
            x *= x
            i >>= 1
        }
        return ans
    }
```
```swift
var (dbl1,dbl2) = (Num(11.0),Num(22.0))
var (int1,int2) = (Num(11,m:13),Num(22)) // 追加⑤int1でm=13

dbl1 *= dbl2
print(dbl1) // Num<Double>(data: 242.0, m: nil)
dbl1 = dbl1.pow(2)
print(dbl1) // Num<Double>(data: 58564.0, m: nil)

int1 *= int2
print(int1) // Num<Int>(data: 8, m: Optional(13))
int1 = int1.pow(2)
print(int1) // Num<Int>(data: 12, m: Optional(13))
// Int制約版のpow関数をコメントアウトしたときの結果
print(int1) // Num<Int>(data: 64, m: Optional(13))
```
- 上記で、Int制約版のpow関数は、制約無しのpow関数と「where Self == Num<Int>」以外は違いがない。しかし、このInt制約版のpow関数を用意しないと、mod13が反映されず、8の二乗の64がそのまま出力される。


# おわりに
- 今回初めて、関数を「where T == Int」でオーバーロードしたけど、引数が全く同じ型名Selfでも、オーバーロードできるんだね。
- 最初の考えでは、追加①②は元の構造体定義で書けるけど、追加③④は、以下のようにextensionで追加定義するしかないと思っていたよ。
```swift
extension Num where T==Int{
    init(_ data:T,m:Int? = nil){
        self.mod = m
        if let mod = m {
            self.data = data % mod
        } else {
            self.data = data            
        }
    }
    
    static func +=(left:inout Self,right:Self){
        left.data += right.data
        if let mod = left.m { left.data %= mod }
    }
}
```
- 今回は勉強になりました。つか、この辺のジェネリックを用いたswiftのテクニックをまとめたテキストないかなぁ。でも、swiftは不人気言語だから無さそうだね。