!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
! Module: bitarray_module
!
! Purpose: This module provides a two-dimensional bit array and a set of
!   routines to manipulate and examine the bits of the array.
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
module bitarray_module

   use module_debug

   type bitarray
      integer, pointer, dimension(:,:) :: iarray ! Storage array
      integer :: nx, ny                 ! Number of bits in the x and y directions
      integer :: x_int_dim, y_int_dim   ! Number of integers in the x and y directions
      integer :: integer_size           ! Number of bits in an integer
   end type bitarray

   contains

   !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
   ! Name: bitarray_create
   !
   ! Purpose: Allocate and initialize a bit array so that all bits are FALSE
   !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
   subroutine bitarray_create(b, i, j)

      implicit none

      ! Arguments
      integer, intent(in) :: i, j
      type (bitarray), intent(out) :: b

      b%integer_size = bit_size(b%integer_size)

      b%nx = i
      b%ny = j

      b%x_int_dim = ceiling(real(b%nx)/real(b%integer_size))
      b%y_int_dim = b%ny

      nullify(b%iarray)
      allocate(b%iarray(b%x_int_dim, b%y_int_dim))
      b%iarray = 0

   end subroutine bitarray_create

   !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
   ! Name: bitarray_copy
   !
   ! Purpose: Duplicate a bitarray.
   !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
   subroutine bitarray_copy(src, dst)

      implicit none

      ! Arguments
      type (bitarray), intent(in) :: src
      type (bitarray), intent(out) :: dst

      dst%integer_size = src%integer_size

      dst%nx = src%nx
      dst%ny = src%ny

      dst%x_int_dim = src%x_int_dim
      dst%y_int_dim = src%y_int_dim

      allocate(dst%iarray(dst%x_int_dim, dst%y_int_dim))
      dst%iarray = src%iarray

   end subroutine bitarray_copy

   !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
   ! Name: bitarray_set
   !
   ! Purpose: Set the bit located at (i,j) to TRUE
   !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
   subroutine bitarray_set(b, i, j)

      implicit none

      ! Arguments
      integer, intent(in) :: i, j
      type (bitarray), intent(inout) :: b

      ! Local variables
      integer :: n_integer, n_bit

      n_integer = ((i-1) / b%integer_size) + 1
      n_bit = mod((i-1), b%integer_size)

      b%iarray(n_integer, j) = ibset(b%iarray(n_integer, j), n_bit)

   end subroutine bitarray_set

   !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
   ! Name: bitarray_clear
   !
   ! Purpose: Set the bit located at (i,j) to FALSE
   !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
   subroutine bitarray_clear(b, i, j)

      implicit none

      ! Arguments
      integer, intent(in) :: i, j
      type (bitarray), intent(inout) :: b

      ! Local variables
      integer :: n_integer, n_bit

      n_integer = ((i-1) / b%integer_size) + 1
      n_bit = mod((i-1), b%integer_size)

      b%iarray(n_integer, j) = ibclr(b%iarray(n_integer, j), n_bit)

   end subroutine bitarray_clear

   !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
   ! Name: bitarray_test
   !
   ! Purpose: To return the value of the bit located at (i,j)
   !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
   function bitarray_test(b, i, j)

      implicit none

      ! Arguments
      integer, intent(in) :: i, j
      type (bitarray), intent(in) :: b

      ! Local variables
      logical :: bitarray_test
      integer :: n_integer, n_bit

      n_integer = ((i-1) / b%integer_size) + 1
      n_bit = mod((i-1), b%integer_size)

      bitarray_test = btest(b%iarray(n_integer,j), n_bit)

   end function bitarray_test

   !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
   ! Name: bitarray_merge
   !
   ! Purpose: The first bitarray argument, b1, is set to the union of the .TRUE.
   !   bits in b1 and b2. That is, after returning, a bit x in b1 is set if
   !   either x was set in b1 or x was set in b2. Thus, b1 AND b2 MUST BE BIT
   !   ARRAYS OF THE SAME DIMENSIONS.
   !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
   subroutine bitarray_merge(b1, b2)

      implicit none

      ! Arguments
      type (bitarray), intent(inout) :: b1, b2

      ! Local variables
      integer :: i, j

      if (b1%x_int_dim /= b2%x_int_dim .or. b1%y_int_dim /= b2%y_int_dim) then
         call mprintf(.true.,ERROR,'In bitarray_merge(), b1 and b2 have different dimensions.')
      end if

      do i=1,b1%x_int_dim
         do j=1,b1%y_int_dim
            b1%iarray(i,j) = ior(b1%iarray(i,j), b2%iarray(i,j))
         end do
      end do

   end subroutine bitarray_merge

   !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
   ! Name: bitarray_destroy
   !
   ! Purpose: To deallocate all allocated memory associated with the bit array
   !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
   subroutine bitarray_destroy(b)

      implicit none

      ! Arguments
      type (bitarray), intent(inout) :: b

      if (associated(b%iarray)) then
         deallocate(b%iarray)
      else
         call mprintf(.true.,WARN,'In bitarray_destroy(), b is not allocated.')
      end if

   end subroutine bitarray_destroy

end module bitarray_module