SUBROUTINE btree_simple_insertion_i8_sp2d (node, key, value, before, subtree)
TYPE(btree_node_i8_sp2d), INTENT(INOUT) :: node
INTEGER(KIND=keyt), INTENT(IN) :: key
TYPE(btree_data_sp2d), INTENT(IN) :: value
INTEGER, INTENT(IN) :: before
TYPE(btree_node_i8_sp2d), POINTER, OPTIONAL :: subtree
!
! Shift keys
node%keys(before + 1:node%filled + 1) = node%keys(before:node%filled)
node%keys(before) = key
! Shift values
node%values(before + 1:node%filled + 1) = node%values(before:node%filled)
node%values(before) = value
! Shift subtree pointers, but only if node is not a leaf ; assume
! leaf <=> present(subtree)
IF (PRESENT(subtree)) THEN
node%subtrees(before + 2:node%filled + 2) = &
node%subtrees(before + 1:node%filled + 1)
node%subtrees(before + 1)%node => subtree
END IF
node%filled = node%filled + 1
END SUBROUTINE btree_simple_insertion_i8_sp2d