Fortranの集合演算

# Fortranでも集合の概念を扱いたい
重複を排除したデータを作りたいこと、ありませんか？
例えば、`[1,2,2,4,4,6]`配列から `[1,2,4,6]`を作りたい、とか、`["alpha", "alpha", "beta"]`を`["alpha", "beta"]`にしたい、、という具合です。

近年活発に開発されている[`stdlib`](https://stdlib.fortran-lang.org/index.html)の `hashmap`を応用して、ある程度簡単に実現することができます。

## 整数の集合または文字列の集合を使う事例
整数[1,3,5]の集合（プログラム中では`map`という変数名）に対して
1. 整数1~5が集合に含まれているかテスト
1. 集合から要素を取り出す
1. [5,6,7]を既存の集合に追加することを試みる
1. 要素[1]を集合から削除
1. 最後まで残った要素を表示

という処理をした結果のコンソール出力を下記に記します。


```text
!=== hashmapを集合のように使う事例(intバージョン)
add values :[1,3,5,]
!-- 値が集合に含まれているかどうかのテスト
[1] is included.
[2] is not included.
[3] is included.
[4] is not included.
[5] is included.
 !-- 追加した要素を取り出してループ処理
key=[1]
key=[3]
key=[5]
 !-- 重複した値が無ければ集合に登録（重複があれば登録しない）
[5] は既に登録されています.
[6] を登録しました.
[7] を登録しました.
!---
[1]を削除するので、3,5,6,7が残るはずです
削除後の要素:   3,  5,  6,  7,
```

この出力は、下記ソースの`test_as_set_int`というsubroutineを呼び出した結果です。
(test_as_set_stringというsubroutineは文字列の集合を扱うテストです。)

```fortran
module sample_container
  use iso_fortran_env
  use stdlib_hashmaps
  use stdlib_hashmap_wrappers
  implicit none
  private

  public :: test_as_set_int,test_as_set_string
contains
  subroutine test_as_set_int
    type(chaining_hashmap_type) :: map 
    type(key_type), allocatable :: keys(:)
    integer, allocatable :: int_key(:)
    integer :: i
    logical :: tf
    call map%init(fnv_1_hasher)
    print *, "!=== hashmapを集合のように使う事例(intバージョン)"

    write(output_unit,fmt='(a)',advance="no") "add values :["
    do i = 1, 5, 2
      call map%map_entry([i])
      write(output_unit,fmt="(i0,',')", advance="no") i
    end do
    write(output_unit,fmt='(a)',advance="yes") "]"

    !--
    write(output_unit,fmt='(a)',advance="yes") "!-- 値が集合に含まれているかどうかのテスト"
    do i = 1, 5
      call map%key_test([i], tf)
      if (tf) then
        write(output_unit,'("[",i0,"] is included.")') i
      else
        write(output_unit,'("[",i0,"] is not included.")') i
      end if
    end do
    !-- getting all the key in the map
    write(output_unit,*) "!-- 追加した要素を取り出してループ処理"
    call map%get_all_keys(keys)
    do i = 1, size(keys)
      call get(keys(i), int_key)
      write(output_unit,'("key=[",i0,"]")') int_key
    end do

    write(output_unit,*) "!-- 重複した値が無ければ集合に登録（重複があれば登録しない）"
    do i = 5, 7
      call map%map_entry([i], conflict=tf)
      if (tf) then
        write(output_unit,'("[",i0,"] は既に登録されています.")') i
      else
        write(output_unit,'("[",i0,"] を登録しました.")') i
      end if
    end do

    write(output_unit,fmt='("!---")',advance='yes')
    write(output_unit,fmt='("[1]を削除するので、3,5,6,7が残るはずです")',advance='yes')
    call map%remove([1])
    call map%get_all_keys(keys)
    block
      integer:: n
      integer,allocatable :: int_keys(:)
      n=size(keys)
      write(output_unit,fmt='("削除後の要素: ")',advance='no')
      do i=1,n
        call get(keys(i), int_keys)
        write(output_unit,'(i3,",")',advance='no') int_keys
      end do
      write(output_unit,fmt="(a)",advance='yes')
    end block
  end subroutine 

  subroutine test_as_set_string
    type(chaining_hashmap_type) :: map 
    type(key_type), allocatable :: keys(:)
    character(len=:),allocatable :: string
    integer :: i
    call map%init(fnv_1_hasher)
    print *, "!=== hashmapを集合のように使う事例(文字列バージョン)"
    call map%map_entry("alpha")
    call map%map_entry("beta")
    call map%map_entry("gamma")
    call map%get_all_keys(keys)
    do i = 1, size(keys)
      call get(keys(i), string)
      write(output_unit,'("key=[",A,"]")') string
    end do
    call check_char(map, "alpha")
    call check_char(map, "beta")
    call check_char(map, "gamma")
    call check_char(map, "kappa")
    call check_char(map, "epsilon")
  end subroutine 

  subroutine check_char(map, txt)
    type(chaining_hashmap_type) :: map 
    character(*) :: txt
    logical :: tf
    call map%key_test(txt, tf)
    if (tf) then
      write(output_unit,'(a,"はmapに含まれています")') txt
    else
      write(output_unit,'(a,"はmapに含まれていません")') txt
    end if
  end subroutine
end module sample_container
```

Fortranコード例のうち、文字列を扱う`test_as_set_string`の実行結果は次の通りです。
```text
!=== hashmapを集合のように使う事例(文字列バージョン)
key=[alpha]
key=[beta]
key=[gamma]
alphaはmapに含まれています
betaはmapに含まれています
gammaはmapに含まれています
kappaはmapに含まれていません
epsilonはmapに含まれていません
```

## 重要な箇所だけ抜き出すと
コンソール出力のための文でやや見にくくなっていますが、
```Fortran
use stdlib_hashmaps
use stdlib_hashmap_wrappers
```
として、以下の関数などを使うのが基本となります。
```fortran
 call map%init(fnv_1_hasher)    !初期化のおまじない。引数を変えると、内部処理の方法が変わる（らしい）
 call map%map_entry(key_object) !key_objectはtype(key_type),character, int8配列,int32配列のどれか
 call map%get_all_keys(keys)    !keysはtype(key_type),allocatable,dimension(:)
 call map%key_test(key_object, tf) ! tfが.true.なら、key_objectがすでに存在
 call map%remove(key_object)    ! key_objectがmapから削除される
```

# ユーザ定義構造体の場合
構造体のビット表現をint8の配列に`mytype_to_int8array`で変換して利用する事例を紹介します。

厳密には、構造体の要素のバイト表現上の大きさ次第ではパディングが生じてうまくいかない場合が多いと思ってください。ここでは32bit実数と16bit整数が要素となっているからか、私の実行環境ではパディングが生じなかったようでうまくいきました。

本気で構造体を集合の成分として識別したければ、変数の要素をサーチしてハッシュ値を算出する関数などを作成すべきだと思います。（C++の標準ライブラリでも、自作クラスでsetを定義するときはハッシュ計算のメソッドと求められたような。。）

```fortran
module user_defined_type
  use iso_fortran_env
  use stdlib_hashmaps
  use stdlib_hashmap_wrappers
  implicit none
  public

  type :: mytype_t
    real(real32) :: x
    real(real32) :: y
    integer(int16) :: i
  end type
contains

  subroutine test_set_mytype
    type(chaining_hashmap_type) :: map 
    type(key_type) :: key
    type(key_type), allocatable :: keys(:)
    integer(int8), allocatable :: int_key(:)
    type(mytype_t) :: mytype
    logical :: conflict

    call map%init(fnv_1_hasher)
    print *, "!=== hashmapを集合のように使う事例(ユーザ定義構造体バージョン)"
    call map%map_entry(mytype_to_int8array(mytype_t(1d0,2d0,0)), conflict=conflict)
    call map%map_entry(mytype_to_int8array(mytype_t(3d0,4d0,1)), conflict=conflict)
    call map%map_entry(mytype_to_int8array(mytype_t(5d0,6d0,2)), conflict=conflict)
    call show_keytest_result(map, mytype_t(1d0,2d0,1))
    call show_keytest_result(map, mytype_t(3d0,4d0,1))
    call map%get_all_keys(keys)
    call show_keys(keys)
  end subroutine

  function mytype_to_int8array(mytype) result(int_key)
    ! keyとして受け付けられるのはint配列またはcharacterなので、構造体のバイト表現をint配列に変換する
    type(mytype_t), intent(in) :: mytype
    integer(int8), allocatable :: int_key(:)
    integer(int8) :: int_8
    integer :: size_mytype
    size_mytype=storage_size(mytype)/8
    int_key = transfer(source=mytype,mold=int_8,size=size_mytype)
  end function

  subroutine show_keytest_result(map,mytype)
    type(chaining_hashmap_type) :: map 
    type(mytype_t) :: mytype
    integer(int8), allocatable :: int_key(:)
    logical :: tf
    call map%key_test(mytype_to_int8array(mytype), tf)
    if (tf) then
        write(output_unit,*) mytype,"はmapに含まれています"
    else
        write(output_unit,*) mytype,"はmapに含まれていません"
    end if
  end subroutine

  subroutine show_keys(keys)
    type(key_type), intent(in) :: keys(:)
    integer(int8), allocatable :: int_key(:)
    type(mytype_t) :: mytype
    integer :: n,i
    n = size(keys)
    do i = 1,n
      call get(keys(i),int_key)
      mytype = transfer(int_key, mytype)
      print *, mytype,mytype_to_int8array(mytype)
    end do
  end subroutine
end module
```

このコードの`test_set_mytype`を実行した結果は下記の通りです。

```text
 !=== hashmapを集合のように使う事例(ユーザ定義構造体バージョン)
   1.00000000       2.00000000          1 はmapに含まれていません
   3.00000000       4.00000000          1 はmapに含まれています
   1.00000000       2.00000000          0    0    0 -128   63    0    0    0   64    0    0    0    0
   3.00000000       4.00000000          1    0    0   64   64    0    0 -128   64    1    0    0    0
   5.00000000       6.00000000          2    0    0  -96   64    0    0  -64   64    2    0    0    0
```

同じ構造体が要素に含まれているかどうかを正しく判別できました。

簡易的にtransferを使いましたが、パディングの問題や、要素がポインタ or allocatableな時の動作は怪しくなると思います。

# おわりに
stdlibのhashmapを活用して、integerやcharacter型の集合、さらに構造体の集合を作ることができました。本来、hashmapはkeyとペアになる任意のデータ型を保持できるので、「辞書」を生成できます。余力があれば辞書についても書こうかと思います。