! This module implements a linked list with the following operations to
! manipulate it:
!
! - subroutine addFirst(list, element)
! Insert the given element at the beginning of the specified list.
!
! - subroutine addLast(list, element)
! Append the specified element to the end of the list.
!
! - subroutine add(list, element)
! Add (according to the type of the list) the specified element to the list.
!
! - function createList()
! Create and return an empty list.
!
! - function empty(list)
! Return true if the specified list contains no elements.
!
! - function removeFirst(list)
! Remove and return the first element from the specified list.
!
! - function removeLast(list)
! Remove and return the last element from the specified list.
!
! - function remove(list)
! Remove (according to the type of the list) and return the element 
! from the specified list.

module LinkedList

  use Container

! Different types of a list.
  integer, parameter :: QUEUE    = 0
  integer, parameter :: STACK    = 1
  integer, parameter :: PRIORITY = 2
  integer, parameter :: UNSPEC   = 3

! ************************************************************************
! ************************************************************************

  type list

     private

!    Datatype to represent a list.

!    Pointer to the first element of the list.
     type(node), pointer :: first

!    Pointer to the last element of the list.
     type(node), pointer :: last

!    The type of this list. If this variable is set, the subroutine add()
!    and the function remove() will execute a specific action, according
!    to the type of the list.
     integer :: type

!    Size of the list.
     integer :: size

  end type list

! ************************************************************************
! ************************************************************************

  type, private :: node

!    Datatype to represent a node in the list. It stores a data
!    and a pointer to the next element of the list.

!    The data stored in this node.
     type(data) :: data

!    Pointer to the next node.
     type(node), pointer :: next

!    Pointer to the previous node.
     type(node), pointer :: previous

  end type node

! ************************************************************************
! ************************************************************************

contains

  function createList(type) result(list_)

    implicit none

!   Create and return an empty list.

!   OPTIONAL ARGUMENT
    integer, optional, intent(in) :: type

!   RETURN VARIABLE
    type(list) :: list_

    if(present(type)) then

       list_%type = type

    else

       list_%type = UNSPEC

    end if

    list_%size = 0
    nullify(list_%first)
    nullify(list_%last)

  end function createList

! ************************************************************************
! ************************************************************************

  subroutine changeListType(list_,type)

    implicit none

!   Change the type of the list.

!   ARGUMENTS
    integer,    intent(in)     :: type
    type(list), intent(in out) :: list_

    list_%type = type

  end subroutine changeListType

! ************************************************************************
! ************************************************************************

  integer function getListType(list_)

    implicit none

!   Return the type of the list.

!   ARGUMENT
    type(list), intent(in) :: list_

    getListType = list_%type

  end function getListType

! ************************************************************************
! ************************************************************************

  subroutine addFirst(list_, element)

    implicit none

!   Insert the given element at the beginning of the specified list.
!
!   Parameters of the function:
!   ===========================
!
!   LIST_ list: List where the element will be inserted.
!   ----------
!
!   ELEMENT data: Element to be inserted at the beginning of the list.
!   ------------

!   ARGUMENTS
    type(list), intent(in out) :: list_
    type(data), intent(in)     :: element

!   LOCAL VARIABLES
    type(node), pointer :: current

!   Create a new node.
    allocate(current)
    current%data = element

    if(empty(list_)) then

       nullify(current%next)
       nullify(current%previous)

!      Update the first element of the list.
       list_%first => current

!      Update the pointer to the last element of the list.
       list_%last => current

    else

       nullify(current%previous)

!      Point to next node.
       current%next => list_%first

!      First node points to the new node.
       list_%first%previous => current

!      Update the first element of the list.
       list_%first => current

    endif

    list_%size = list_%size + 1

  end subroutine addFirst

! ************************************************************************
! ************************************************************************

  subroutine addLast(list_, element)

    implicit none

!   Append the specified element to the end of the list.
!
!   Parameters of the function:
!   ===========================
!
!   LIST_ list: List where the element will be appended.
!   ----------
!
!   ELEMENT data: Element to be appended to the list.
!   ------------

!   ARGUMENTS
    type(list), intent(in out) :: list_
    type(data), intent(in)     :: element

!   LOCAL VARIABLES
    type(node), pointer :: current

!   Create a new node.
    allocate(current)
    current%data = element

    if(empty(list_)) then

       nullify(current%next)
       nullify(current%previous)

!      Update the first element of the list.
       list_%first => current

!      Update the pointer to the last element of the list.
       list_%last => current

    else

       nullify(current%next)

!      Point to previous node.
       current%previous => list_%last

!      Last node points to the new node.
       list_%last%next => current

!      Update the pointer to the last element of the list.
       list_%last => current

    endif

    list_%size = list_%size + 1

  end subroutine addLast

! ************************************************************************
! ************************************************************************

  function removeFirst(list_) result(element)

    implicit none

!   Remove and returns the first element from the specified list.
!
!   Parameters of the function:
!   ===========================
!
!   LIST_ list: List where the first element will be removed.
!   ----------

!   ARGUMENTS
    type(list), intent(in out) :: list_

!   RETURN VARIABLE
    type(data) :: element

!   LOCAL VARIABLES
    type(node), pointer :: old

    if(.not. empty(list_)) then

       element = list_%first%data
       old => list_%first
       list_%first => list_%first%next

       if(.not. empty(list_)) then
          nullify(list_%first%previous)
       end if

       deallocate(old)

       list_%size = list_%size - 1

    end if

  end function removeFirst

! ************************************************************************
! ************************************************************************

  function removeLast(list_) result(element)

    implicit none

!   Remove and return the last element from the specified list.
!
!   Parameters of the function:
!   ===========================
!
!   LIST_ list: List where the last element will be removed.
!   ----------

!   ARGUMENTS
    type(list), intent(in out) :: list_

!   RETURN VARIABLE
    type(data) :: element

!   LOCAL VARIABLES
    type(node), pointer :: old

    if(.not. empty(list_)) then

       element = list_%last%data
       old => list_%last
       list_%last => list_%last%previous

       if(.not. empty(list_)) then
          nullify(list_%last%next)
       end if

       deallocate(old)

       list_%size = list_%size - 1

    end if
    
  end function removeLast

! ************************************************************************
! ************************************************************************

  function removeBestBound(list_) result(element)

    implicit none

!   Remove and return the first element from the specified list.
!
!   Parameters of the function:
!   ===========================
!
!   LIST_ list: List where the first element will be removed.
!   ----------

!   ARGUMENTS
    type(list), intent(in out) :: list_

!   RETURN VARIABLE
    type(data) :: element

!   LOCAL VARIABLES
    real(kind=8) :: lowerBound, bestLowerBound
    type(node), pointer :: current, bestNode

    if(.not. empty(list_)) then

       current  => list_%first
       bestNode => current
       bestLowerBound = current%data%problem%lowerBound

       do while(associated(current))

          lowerBound = current%data%problem%lowerBound

          if(lowerBound .lt. bestLowerBound) then

             bestLowerBound = lowerBound
             bestNode => current

          end if

          current => current%next

       end do

       element = bestNode%data

       if(associated(bestNode%previous) .and. associated(bestNode%next)) then

          ! *----------*        *-----------*        *------*
          ! | Previous |  <-->  | Best node |  <-->  | Next |
          ! *----------*        *-----------*        *------*

          bestNode%previous%next => bestNode%next          
          bestNode%next%previous => bestNode%previous

       else if(associated(bestNode%previous)) then

          ! *----------*        *-----------*
          ! | Previous |  <-->  | Best node |  <-->  NULL
          ! *----------*        *-----------*

          nullify(bestNode%previous%next)
          list_%last => bestNode%previous

       else if(associated(bestNode%next)) then

          !                     *-----------*        *------*
          !         NULL  <-->  | Best node |  <-->  | Next |
          !                     *-----------*        *------*

          nullify(bestNode%next%previous)
          list_%first => bestNode%next

       else

          !                     *-----------*
          !         NULL  <-->  | Best node |  <-->  NULL
          !                     *-----------*

          nullify(list_%first)
          nullify(list_%last)

       end if

       deallocate(bestNode)

       list_%size = list_%size - 1

    end if

  end function removeBestBound

! ************************************************************************
! ************************************************************************

  logical function empty(list_)

    implicit none

!   Return true if the specified list contains no elements.

!   ARGUMENTS
    type(list), intent(in) :: list_

    if(.not. associated (list_%first) .or. .not. associated (list_%last)) then
       empty = .true.
    else
       empty = .false.
    end if

  end function empty

! ************************************************************************
! ************************************************************************

  function remove(list_) result(element)

    implicit none

!   Remove and return an element from the specified list, according
!   to its type.
!
!   Parameters of the function:
!   ===========================
!
!   LIST_ list: List where the element will be removed.
!   ----------

!   ARGUMENTS
    type(list), intent(in out) :: list_

!   RETURN VARIABLE
    type(data) :: element

    if(list_%type == PRIORITY) then

       element = removeBestBound(list_)

    else 
   
       element = removeFirst(list_)

    end if

  end function remove

! ************************************************************************
! ************************************************************************

  subroutine add(list_, element)

    implicit none

!   Add the specified element to the list, according to its type.
!
!   Parameters of the function:
!   ===========================
!
!   LIST_ list: List where the element will be added.
!   ----------
!
!   ELEMENT data: Element to be added to the list.
!   ------------

!   ARGUMENTS
    type(list), intent(in out) :: list_
    type(data), intent(in)     :: element

    if(list_%type == QUEUE) then

       call addLast(list_, element)

    else
       ! Stack.
       call addFirst(list_, element)

    end if

  end subroutine add

! ************************************************************************
! ************************************************************************

  subroutine printList(list_)

    implicit none

!   Print the specified list.

    type(list), intent(in) :: list_
    type(node), pointer    :: current

    current => list_%first

    do while(associated(current))
       print *, current%data%problem%initialPoint(1)
       current => current%next
    end do

  end subroutine printList

! ************************************************************************
! ************************************************************************

  function getSize(list_) result(size)

    type(list), intent(in) :: list_

    integer :: size

    size = list_%size

  end function getSize

! ************************************************************************
! ************************************************************************

  subroutine destroyList(list_)

    use Problems
    use Container

    implicit none

    type(list), intent(in out) :: list_

    type(data) :: d

    do while(.not. empty(list_))
       d = removeLast(list_)
       call deallocateProblem(d%problem)
    end do

  end subroutine destroyList

! ************************************************************************
! ************************************************************************

end module LinkedList