Fortranで可変長配列を実装する

# 誰向け?

-   Fortran でユーザ定義型を作りたい人向け.
-   Fortran で競技プログラミングに挑む人向け.
    -   Graph の問題で隣接リストでグラフを表現することができる.
    -   Stack が必要な問題で末尾に要素を加えたり, 取り除ける.


<a id="orgaa883c3"></a>

## 適しない人

-   数値計算
    -   配列を可変にする必要はないだろう.


<a id="org7c0ff53"></a>

# 配列のサイズをてきとーに変更する

-   標準の関数 でサイズを変更できるが&#x2026;
    -   自分で配列のサイズを気にして, 手動でサイズ変更するのは面倒くさい!!!
-   他の言語みたいな機能(push とか)付けて楽したい!!!!!!

```fortran
program expand_array
  use, intrinsic :: iso_fortran_env
  implicit none
  integer, allocatable :: arr(:)
  integer(int32) :: i
  allocate(arr(4), source = [(i, i = 1, 4)])
  write(output_unit, '(*(i0, 1x))') arr(:)
  call resize(arr, 2 * size(arr))
  arr(5:) = 88
  write(output_unit, '(*(i0, 1x))') arr(:)
contains
  subroutine resize(arr, new_size)
    integer(int32), allocatable, intent(inout) :: arr(:)
    integer(int32), intent(in) :: new_size
    integer(int32), allocatable :: tmp(:)
    integer(int32) :: n
    allocate(tmp(new_size))
    n = size(arr)
    tmp(1:n) = arr(1:n)
    call move_alloc(from = tmp, to = arr)
  end subroutine resize
end program expand_array
```


<a id="org6f165ee"></a>

# 他の言語の可変長配列の機能は?

-   C++ や Rust の可変長配列は末尾に値を代入するメソッドや取り除くメソッドがある.
-   こういうことを Fortran で再現したい.

```rust
fn main() {
    let mut v: Vec<i32> = Vec::new();
    println!("{:?}", v);
    v.push(2);
    v.push(100);
    println!("{:?}", v);
    v.pop().unwrap();
    println!("{:?}", v);
}
```

    []
    [2, 100]
    [2]

    []
    [2, 100]
    [2]


<a id="org02c4305"></a>

# ユーザ定義型を使う

-   ユーザ定義型[^1]と型に紐付いた関数[^2]を使う.-
    -   利点は変数に対する操作を制限することができる.
    -   つまり, 自分で配列の長さを変更するのではなく, 型(を作った人)にやってもらうのである.

[^1]: User-defined-type 
[^2]: type-bound-procedure 型束縛手続き?


<a id="org4fd8c02"></a>

## 型を作ろう

-   とりあえず, 型を定義してみる.
-   名前は? \`myvector\` にしよう.
-   必要なものは?
    
    -   動的に確保できる配列.
    -   配列に詰め込まれている要素の数.
    -   配列の実際の長さ.
    
    で良いだろう.
-   外に見せるふるまいは?
    
    -   \`myvector\` に値を後ろに詰め込むことができる.
    -   \`myvector\` の \`n\` 番目の値を見る.
    
    で, とりあえず良いだろうか?
-   \`module\` で実際に型を定義する.
    
    ```fortran
    module myvector_m
      use, intrinsic :: iso_fortran_env
      implicit none
      private
      public :: myvector
      type :: myvector
         private
         integer(int32), allocatable :: arr_(:) ! 動的に確保できる配列.
         integer(int32) :: size_ ! 配列の要素数.
         integer(int32) :: capa_ ! 配列の実際の長さ.
       contains
         procedure, pass, private :: resize => resize_myvector ! 初期化用
         procedure, pass :: push_back => push_back_myvector ! 値を配列の後ろに詰め込む.
         procedure, pass :: at => at_myvector ! 配列の `n` 番目を見る.
      end type myvector
    contains
      pure subroutine push_back_myvector(this, val)
        class(myvector), intent(inout) :: this
        integer(int32), intent(in) :: val
        if (.not. allocated(this%arr_)) &
             call this%resize(1)
        if (this%size_ == this%capa_) &
             call this%resize(this%capa_ * 2)
        this%size_ = this%size_ + 1
        this%arr_(this%size_) = val
      end subroutine push_back_myvector
      impure integer(int32) function at_myvector(this, idx) result(res)
        class(myvector), intent(in) :: this
        integer(int32), intent(in) :: idx
        if (idx < 1 .or. idx > this%size_) &
             error stop "Index is out of bounds in `at_myvector`."
        res = this%arr_(idx)
      end function at_myvector
      pure subroutine resize_myvector(this, n)
        class(myvector), intent(inout) :: this
        integer(int32), intent(in) :: n
        integer(int32), allocatable :: tmp(:)
        if (allocated(this%arr_)) then
           allocate(tmp(n))
           tmp(1:min(n, this%size_)) = this%arr_(1:min(n, this%size_))
           call move_alloc(from = tmp, to = this%arr_)
           this%capa_ = n
           this%size_ = min(n, this%size_)
        else
           allocate(this%arr_(n))
           this%size_ = 0
           this%capa_ = n
        end if
      end subroutine resize_myvector
    end module myvector_m
    
    program test_myvector
      use, intrinsic :: iso_fortran_env
      use myvector_m
      implicit none
      integer(int32), parameter :: n = 10
      type(myvector) :: v
      integer(int32) :: i
      do i = 1, n
         call v%push_back(i * i)
      end do
      do i = 1, n
         write(output_unit, '(i0, 1x, i0)') i, v%at(i)
      end do
    end program test_myvector
    ```
    
    ```
    1 1
    2 4
    3 9
    4 16
    5 25
    6 36
    7 49
    8 64
    9 81
    10 100
    ```


<a id="org417d1c1"></a>

# 結論

-   型に紐付いた関数(type-bound-procedure)を使うことによって, 型に対する操作を制限することができる.
-   つまり, \`v%push_back\` をする人は変数 \`v\` が十分なサイズを持っているかを気にする必要がない.
-   また, この \`v%at\` 関数はサイズの外にある領域へのアクセスを許さない.
    -   つまり, プログラムが正常終了したなら配列のアクセスに異常はないことが保証される.


<a id="org0dd6a62"></a>

# 更なる発展

-   size を返す関数 \`size\` を実装する.
    -   これと \`at\` と \`push_back\` があれば \`type(myvector), alloctable :: g(:)\` でグラフの問題に対処できる.
-   \`push_back\` 操作の対の \`pop_back\` を実装する.
-   一番後ろの要素を返す関数 \`back\` を実装する.
    -   これで stack の機能を表現できる.
-   \`arr_(:)\` を public にして, 配列の整合性を犠牲に利便性を確保する.


<a id="org3b69b03"></a>

# 参考

-   型結合手続き

https://www.nag-j.co.jp/fortran/fortran2003/Fortran2003_2_4.html#AUTOTOC_2_4

-   move<sub>alloc</sub>

https://www.nag-j.co.jp/fortran/fortran2003/Fortran2003_3_5.html#AUTOTOC_3_5

-   マイライブラリvector

https://github.com/osada-yum/Fortran_competitive_library/blob/master/src/data_structures/unwrapped_vector_m.F90