Fortran で array list を作ってみた

動機

前回は Fortran で linked list を実装しましたが、私が Java で普段よく使うのは ArrayList の方なので、今回は array list を実装します (前回記事 Fortran で linked list を作ってみた) 。配列が優秀な Fortran では array list の方が実装しやすいと思います。

array list とは

array list は要素を配列としてもつリストのことです。長さが固定されている配列とは異なり、長さを自由に変えることができるのが特徴です。 linked list と比較すると、要素の追加や削除は遅い $O(N)$ ですが、要素の検索は高速 $O(1)$ です。

環境

macOS Sierra (10.12.6)
GNU Fortran (GCC) 6.3.0

プログラム

実際に実装したのが以下のものです。

array_list.f08

module mod_array_list
  implicit none

  type t_array_list
    integer :: num = 0
    integer, pointer :: arr(:) => null()
  end type t_array_list

contains

  subroutine add(list,item)
    implicit none
    type(t_array_list), intent(inout) :: list
    integer, intent(in) :: item
    integer, allocatable :: tmp(:)

    if (.not.associated(list%arr)) allocate(list%arr(1))
    if (list%num == size(list%arr)) then
      allocate(tmp(list%num))
      tmp = list%arr
      deallocate(list%arr)
      allocate(list%arr(2*list%num))
      list%arr(1:list%num) = tmp
      deallocate(tmp)
    end if

    list%num = list%num+1
    list%arr(list%num) = item
    return
  end subroutine add

  subroutine clear(list)
    implicit none
    type(t_array_list), intent(inout) :: list

    if (associated(list%arr)) deallocate(list%arr)
    list%num = 0
    return
  end subroutine clear

  function get(list,i) result(item)
    implicit none
    type(t_array_list), intent(inout) :: list
    integer, intent(in) :: i
    integer :: item

    item = list%arr(i)
    return
  end function get

  function remove(list,i) result(item)
    implicit none
    type(t_array_list), intent(inout) :: list
    integer, intent(in) :: i
    integer :: item

    item = list%arr(i)
    list%arr(i:) = list%arr(i+1:)
    list%num = list%num-1
    return
  end function remove

  subroutine replace(list,i,item)
    implicit none
    type(t_array_list), intent(inout) :: list
    integer, intent(in) :: i
    integer :: item

    list%arr(i) = item
    return
  end subroutine replace

  function first_index_of(list,item) result(idx)
    implicit none
    type(t_array_list), intent(inout) :: list
    integer, intent(in) :: item
    integer :: idx, i

    idx = -1
    do i = 1, list%num
      if (list%arr(i) == item) then
        idx = i
        return
      end if
    end do
    return
  end function first_index_of

  function last_index_of(list,item) result(idx)
    implicit none
    type(t_array_list), intent(inout) :: list
    integer, intent(in) :: item
    integer :: idx, i

    idx = -1
    do i = list%num, 1, -1
      if (list%arr(i) == item) then
        idx = i
        return
      end if
    end do
    return
  end function last_index_of

  subroutine show_all(list)
    implicit none
    type(t_array_list), intent(inout) :: list
    integer :: i

    if (.not.associated(list%arr)) return
    write(*,'(i0)',advance='no') list%arr(1)
    do i = 2, list%num
      write(*,'(x,i0)',advance='no') list%arr(i)
    end do
    write(*,*)
    return
  end subroutine show_all

end module mod_array_list

また、実装できているか確認するために以下のプログラムも書きました。

test_array_list.f08

program test_array_list
  use mod_array_list
  implicit none
  type(t_array_list) :: list
  integer :: i, n = 3

  do i = 1, n
    call add(list,i)
    write(*,'("add: ",i0," size: ",i0)') i, list%num
  end do
  do i = 1, n
    call add(list,i)
    write(*,'("add: ",i0," size: ",i0)') i, list%num
  end do

  call show_all(list)

  write(*,'("first_index_of 2: ",i0," size: ",i0)') first_index_of(list,2), list%num

  write(*,'("last_index_of 2: ",i0," size: ",i0)') last_index_of(list,2), list%num

  write(*,'("remove at 3: ",i0," size: ",i0)') remove(list,3), list%num

  call show_all(list)

  call replace(list,3,9)
  write(*,'("replace at 3, size: ",i0)') list%num

  call show_all(list)

  write(*,'("get at 3: ",i0," size: ",i0)') get(list,3), list%num

  call show_all(list)

  call clear(list)
  write(*,'("clear, size: ",i0)') list%num

  call show_all(list)

  call add(list,10)
  write(*,'("add: ",i0," size: ",i0)') 10, list%num

  call show_all(list)

  stop
end program test_array_list

実行結果は以下のとおりです。

add: 1 size: 1
add: 2 size: 2
add: 3 size: 3
add: 1 size: 4
add: 2 size: 5
add: 3 size: 6
1 2 3 1 2 3
first_index_of 2: 2 size: 6
last_index_of 2: 5 size: 6
remove at 3: 3 size: 5
1 2 1 2 3
replace at 3, size: 5
1 2 9 2 3
get at 3: 9 size: 5
1 2 9 2 3
clear, size: 0
add: 10 size: 1
10

linked list よりも簡潔に実装できました。

追記 2019/08/11

不必要な部分を削り、よりオブジェクト指向な書き方に変更しました (ソースコード) 。