初めに

　Fortranに実装されているデータ構造は非常に少なく、大体自力で実装する羽目になる｡dequeもその例に漏れない。一方、stackやqueueなどの他のデータ構造はue1221さんなどを始めとして主にfortran2008を用いた実装が行われている。しかし筆者はFortranのOOPに慣れていない。そこで今回はOOPなしでのdequeの実装を行った。

dequeとは

　deque（デック）とは両端キューとも呼ばれるデータ構造である。dequeは右端にも左端にもデータを積むことができ、また取り出しも両端から行える。
　挿入、取り出しを同片方向から行えば最後に入れた要素が最初に出てくる　=> LIFO(Last In First Out)
　挿入、取り出しを異片方向から行えば最初に入れた要素が最初に出てくる　=> FIFO(First In First Out)
　などのように、dequeはstackとしてもqueueとしても使うことができる。

環境

Ubuntu 18.04.4 LTS
ifort (IFORT) 19.0.4.243 20190416
GNU Fortran (Ubuntu 7.5.0-3ubuntu1~18.04) 7.5.0

実装

.f95

module deque_mod
    implicit none
    type deque
        integer(4),pointer:: v(:)
        integer(4):: l,r
        integer(4):: lmax, rmax
    end type
    private
    public:: deque
    public:: init
    public:: append, appendleft
    public:: pop, popleft
    public:: right, left
    public:: remaining_elements
    public:: remain

contains
    subroutine init(dq)
        ! 初期化
        type(deque):: dq
        dq%r=0; dq%rmax=1
        dq%l=1; dq%lmax=-1
        allocate(dq%v(dq%lmax:dq%rmax))
    end subroutine


    subroutine append(dq,num)
        ! 右端に挿入
        type(deque):: dq
        integer(4):: num
        if (dq%r+1 > dq%rmax) call add_(dq)
        dq%r=dq%r+1
        dq%v(dq%r) = num
    end subroutine

    subroutine appendleft(dq,num)
        ! 左端に挿入
        type(deque):: dq
        integer(4):: num
        if (dq%l-1 < dq%lmax) call add_(dq)
        dq%l=dq%l-1
        dq%v(dq%l) = num
    end subroutine

    subroutine add_(dq)
        ! arrayの延長　隠蔽して行われる
        type(deque):: dq
        integer(4):: l
        integer(4),pointer:: tmp(:)
        l = size(dq%v)
        allocate(tmp(l))
        tmp(:) = dq%v(:)
        deallocate(dq%v)
        allocate(dq%v(2*dq%lmax:2*dq%rmax))
        dq%v(dq%lmax:dq%rmax) = tmp(:)
        dq%lmax = 2*dq%lmax
        dq%rmax = 2*dq%rmax
    end subroutine


    function pop(dq) result(ret)
        ! 右端から取り出し
        type(deque):: dq
        integer(4):: ret
        ret = dq%v(dq%r)
        dq%r=dq%r-1
    end function

    function popleft(dq) result(ret)
        ! 左端から取り出し
        type(deque):: dq
        integer(4):: ret
        ret = dq%v(dq%l)
        dq%l=dq%l+1
    end function


    function right(dq) result(ret)
        ! 右端要素を確認
        type(deque):: dq
        integer(4):: ret
        ret = dq%v(dq%r)
    end function

    function left(dq) result(ret)
        ! 左端要素を確認
        type(deque):: dq
        integer(4):: ret
        ret = dq%v(dq%l)
    end function

    function remaining_elements(dq) result(ret)
        ! 残りの要素数
        type(deque):: dq
        integer(4):: ret 
        ret = dq%r - dq%l + 1
    end function

    function remain(dq) result(ret)
        ! 要素が残っているかどうか
        type(deque):: dq
        logical:: ret
        ret = remaining_elements(dq) > 0
    end function
end module

　実装としては

init(初期化)
append(右に追加)
add_(private)
appendleft(左に追加)
pop(右から取り出し)
popleft(左から取り出し)
right(右端を見るだけ)
left(左端を見るだけ)
remaining_elements(残りの要素数を返す)
remain(dequeに要素が残っているか)

の８つである。
　命名については基本的にpythonのdequeに従った。pythonにないものはCでの命名を感覚でまねた｡

使用例

こんなプログラムを作成した。
　①1から20までの値を、4で割り切れる→右から挿入、4で割り切れない→左から挿入
　②dequeが空になるまで右から取り出し、出力

a.f95

program test
    use deque_mod
    implicit none
    type(deque):: dq
    integer(4):: i

    call init(dq)

    do i=1,20
        if (mod(i,4) == 0) then
            call append(dq,i)
        else
            call appendleft(dq,i)
        end if
    end do

    do while(remain(dq))
        print'(i0)', pop(dq)
    end do
end program test

出力結果

　おそらく大丈夫なはず。使用回数が少ないが､今のところ使っていて気になる点はない。

その他

　可変長配列様の動き(サブルーチンadd_)はue1221さんの記事を改悪した｡
　確保している配列のどちらかの端が埋まった状態でその方向に値を挿入しようとするとadd_ subroutineに入り、配列長が二倍になる。ただし、右端と左端が同時に伸びるのでメモリの効率は元の倍悪い(下図)。あと要素が少なくなったとしても配列は縮んでくれたりはしない。競技プログラミングで使う目的では気にならないので妥協した形。

まとめ

　modern fortranの機能にあまりついていけてない人間がdequeを書いてみたよ｡

使う際の注意点

メモリ効率は気になる人は気になるかもしれない
初期化をしてから使用しよう
(remain subroutineなどを用いて)要素が残っていることを確認してから取り出してね

　作ってすぐこの記事を書いたのでバグがあるかも知れない
　気になる点をコメントしてくれたら追記していくつもり(つもり)