btree_left_insertion_i8_zp2d Subroutine

      SUBROUTINE btree_left_insertion_i8_zp2d (tree, node, new_node, key, value, before, split_pos, subtree)
         TYPE(btree_i8_zp2d), INTENT(IN) :: tree
         TYPE(btree_node_i8_zp2d), INTENT(INOUT) :: node, new_node
         INTEGER(KIND=keyt), INTENT(IN) :: key
         TYPE(btree_data_zp2d), INTENT(IN) :: value
         INTEGER, INTENT(IN) :: before, split_pos
         TYPE(btree_node_i8_zp2d), POINTER, OPTIONAL :: subtree
         !
         new_node%filled = (tree%b%max_fill) - (split_pos - 1)
         new_node%keys(1:new_node%filled) = &
            node%keys(split_pos:tree%b%max_fill)
         new_node%values(1:new_node%filled) = &
            node%values(split_pos:tree%b%max_fill)
         !IF (ASSOCIATED (node%subtrees(1)%node)) THEN
         IF (PRESENT(subtree)) THEN
            IF (before .EQ. split_pos) THEN
               new_node%subtrees(2:new_node%filled + 1) = &
                  node%subtrees(split_pos + 1:tree%b%max_fill + 1)
               new_node%subtrees(1)%node => subtree
            ELSE
               new_node%subtrees(1:new_node%filled + 1) = &
                  node%subtrees(split_pos:tree%b%max_fill + 1)
            END IF
         END IF
         ! Fill node%{keys,values}(1:node%filled), where node%filled
         ! is split_pos-1, but do insert the new value at ge_pos. The
         ! key/value at split_pos is to be inserted into the
         ! parent.
         ! The new tree is added to the right of the new insertion.
         node%keys(before + 1:node%filled) = node%keys(before:node%filled - 1)
         node%keys(before) = key
         node%values(before + 1:node%filled) = node%values(before:node%filled - 1)
         node%values(before) = value
         IF (PRESENT(subtree)) THEN
            node%subtrees(before + 2:node%filled + 1) = &
               node%subtrees(before + 1:node%filled)
            node%subtrees(before + 1)%node => subtree
         ELSE
            NULLIFY (node%subtrees(before + 1)%node)
         END IF
      END SUBROUTINE btree_left_insertion_i8_zp2d