btree_add_into_i8_sp2d Subroutine

      RECURSIVE SUBROUTINE btree_add_into_i8_sp2d (tree, node, key, value, before, subtree)
         TYPE(btree_i8_sp2d), INTENT(INOUT) :: tree
         TYPE(btree_node_i8_sp2d), POINTER :: node
         INTEGER(KIND=keyt), INTENT(IN) :: key
         TYPE(btree_data_sp2d), INTENT(IN) :: value
         INTEGER, INTENT(IN), OPTIONAL :: before
         TYPE(btree_node_i8_sp2d), POINTER, OPTIONAL :: subtree
         !
         TYPE(btree_node_i8_sp2d), POINTER :: new_node
         INTEGER(KIND=keyt) :: upgrade_key
         INTEGER :: ge_pos, split_pos
         TYPE(btree_data_sp2d) :: upgrade_value
         LOGICAL :: leaf
         !
         ! Root is special
         IF (.NOT. ASSOCIATED(node)) THEN
            CALL btree_new_root_i8_sp2d (tree, key, value)
            IF (PRESENT(subtree)) THEN
               tree%b%root%subtrees(2)%node => subtree
               subtree%parent => tree%b%root
            END IF
            RETURN
         END IF
         ! Where the insertion takes place.
         IF (PRESENT(before)) THEN
            ge_pos = before
         ELSE
            CALL btree_node_find_gt_pos_i8_sp2d (node%keys, key, ge_pos, node%filled)
         END IF
         ! Addition is easy if the node has enough space.
         leaf = .NOT. ASSOCIATED(node%subtrees(1)%node)
         IF (node%filled .LT. tree%b%max_fill) THEN
            IF (PRESENT(subtree)) THEN
               CALL btree_simple_insertion_i8_sp2d (node, key, value, ge_pos, subtree)
            ELSE
               CALL btree_simple_insertion_i8_sp2d (node, key, value, ge_pos)
            END IF
            RETURN
         ELSE
            split_pos = ISHFT(tree%b%max_fill + 1, -1)
            ! I assert that split_pos <= SIZE(node%keys)
            CALL btree_new_node_i8_sp2d (tree, new_node)
            ! The key to be added falls in the left node
            node%filled = split_pos - 1
            IF (ge_pos .LE. split_pos) THEN
               IF (ge_pos .EQ. split_pos) THEN
                  upgrade_key = key
                  upgrade_value = value
               ELSE
                  upgrade_key = node%keys(split_pos - 1)
                  upgrade_value = node%values(split_pos - 1)
               END IF
               IF (PRESENT(subtree)) THEN
                  CALL btree_left_insertion_i8_sp2d (tree, node, new_node, key, value, &
                                                          ge_pos, split_pos, subtree)
                  !CALL btree_adopt_subtrees_i8_sp2d (new_node)
               ELSE
                  CALL btree_left_insertion_i8_sp2d (tree, node, new_node, key, value, &
                                                          ge_pos, split_pos)
               END IF
               !
            ELSE
               upgrade_key = node%keys(split_pos)
               upgrade_value = node%values(split_pos)
               IF (PRESENT(subtree)) THEN
                  CALL btree_right_insertion_i8_sp2d (tree, node, new_node, key, value, &
                                                           ge_pos, split_pos, subtree)
                  !CALL btree_adopt_subtrees_i8_sp2d (new_node)
               ELSE
                  CALL btree_right_insertion_i8_sp2d (tree, node, new_node, key, value, &
                                                           ge_pos, split_pos)
               END IF
               !
            END IF
            !
            new_node%parent => node%parent
            !
            IF (.NOT. leaf) THEN
               CALL btree_adopt_subtrees_i8_sp2d (new_node)
            END IF
            !
            CALL btree_add_into_i8_sp2d (tree, node%parent, upgrade_key, upgrade_value, &
                                              subtree=new_node)
            !
         END IF
      END SUBROUTINE btree_add_into_i8_sp2d