! pointer1.f90

! This is the first of a series of programs to demonstrate use
! of derived types and pointers.

! The final program in the series will be a module that dynamically
! and efficiently maintains sorted structures (balanced binary tree).

! You can customize the type "node" to hold data of your type, with only
! a few changes to the module.

program pointer1
  implicit none

  ! define the type "node" to be a node in a tree
  type node
    integer (kind=selected_int_kind(1)) :: bf    ! balance factor for later use
    type (node), pointer                :: left  ! left tree branch (smaller)
    type (node), pointer                :: right ! right tree branch (larger)
    character (len=2)                   :: name  ! sort key (can be any type)
    character (len=2)                   :: phone ! any amount of stuff
  end type node

  type (node), pointer :: root_ptr               ! the root of the tree

  print *, " pointer1, manually built tree"
  nullify(root_ptr)                              ! begin with empty tree

  ! manually build the tree to test the "make_node" and "output" procedures
  !
  !                 D 4
  !                /   \
  !              /       \
  !           B 2         F 6        first tier
  !          /   \       /   \
  !        A 1   C 3   E 5   G 7     second tier
  !

  root_ptr => make_node("D ", "4 ")               ! root node
  root_ptr%left  => make_node("B ", "2 ")         ! first tier
  root_ptr%right => make_node("F ", "6 ")
  root_ptr%left%left   => make_node("A ", "1 ")   ! second tier
  root_ptr%left%right  => make_node("C ", "3 ")
  root_ptr%right%left  => make_node("E ", "5 ")
  root_ptr%right%right => make_node("G ", "7 ")
  call output(root_ptr)
  print *, " pointer1 finished"
contains

  ! needed to simulate constructor  node(0, name, phone, null, null)
  function make_node(name, phone) result(new_node)
    character (len=2) :: name
    character (len=2) :: phone
    type (node), pointer :: new_node

    allocate(new_node)
    new_node%bf = 0                 ! initial balance factor zero
    nullify(new_node%left)          ! initial left pointer null
    nullify(new_node%right)         ! initial right pointer null
    new_node%name = name            ! fill in name
    new_node%phone = phone          ! fill in phone
  end function make_node            ! return pointer to constructed node

  ! simple subroutine to output a tree given a pointer to the root
  recursive subroutine output(t)
    type (node), pointer :: t

    if(associated(t)) then
      call output(t%left)
      print *, " ", t%name, t%phone
      call output(t%right)
    end if
  end subroutine output

end program pointer1

! result of running pointer1 is :
! pointer1, manually built tree
! A 1
! B 2
! C 3
! D 4
! E 5
! F 6
! G 7
! pointer1 finished