Switches Lm and Rm, as defined on page 20 of the paper.

def switch_sides(d_u, dfs_data):
    """Switches Lm and Rm, as defined on page 20 of the paper."""
    # global fn_x

    m = dfs_data['FG']['m']
    u_m = u(m, dfs_data)
    # x_m = fn_x(m, dfs_data)

    if d_u <= u_m:
        l_w = lw(dfs_data)
        u_m1 = u(m-1, dfs_data)
        while u_m1 > l_w:
            merge_Fm(dfs_data)
            m = dfs_data['FG']['m']
            u_m1 = u(m-1, dfs_data)

        # l_w = r_w is handled dynamically by the switching of fronds below

        # l = r
        dfs_data['FG']['l'] = dfs_data['FG']['r']

        # adjust r so that gr is first frond preceding xm in RF
        x_m = fn_x(m, dfs_data)
        r = len(dfs_data['RF']) - 1
        g_r = dfs_data['RF'][r][0]
        while g_r >= x_m:
            r -= 1
            if r < 0:
                r = 0
                break
            g_r = dfs_data['RF'][r][0]
        dfs_data['FG']['r'] = r

        # changing r_w is also handled dynamically by the frond switching
    else:
        r_w = rw(dfs_data)
        x_m1 = fn_x(m-1, dfs_data)
        while x_m1 > r_w:
            merge_Fm(dfs_data)
            m = dfs_data['FG']['m']
            x_m1 = fn_x(m-1, dfs_data)

        # r_w = l_w is handled dynamically by the switching of fronds below

        # r = l
        dfs_data['FG']['r'] = dfs_data['FG']['l']

        # adjust l so that fl is first frond preceding um in LF
        u_m = u(m, dfs_data)
        l = len(dfs_data['LF']) - 1
        f_l = dfs_data['LF'][l][0]
        while f_l >= u_m:
            l -= 1
            f_l = dfs_data['LF'][l][0]
        dfs_data['FG']['l'] = l

        # changing l_w is also handled dynamically by the frond switching

    m = dfs_data['FG']['m']

    # Exchange the portion of the linked list LF between um and vm with the portion of RF between xm and ym
    LF = dfs_data['LF']
    RF = dfs_data['RF']

    u_m = u(m, dfs_data)
    v_m = v(m, dfs_data)
    x_m = fn_x(m, dfs_data)
    y_m = y(m, dfs_data)

    # --These are the baseline indexes, they should be narrowed appropriately
    first_left_index = 1
    last_left_index = len(LF) - 1
    first_right_index = 1
    last_right_index = len(RF) - 1

    # --Narrow the left indexes
    while first_left_index < last_left_index:
        frond = LF[first_left_index]
        if u_m >= frond[0]:
            first_left_index -= 1
            break
        else:
            first_left_index += 1

    while first_left_index < last_left_index:
        frond = LF[last_left_index]
        if v_m < frond[1]:
            last_left_index -= 1
        else:
            last_left_index += 1
            break

    # --Narrow the right indexes
    while first_right_index < last_right_index:
        frond = RF[first_right_index]
        if x_m >= frond[0]:
            first_right_index -= 1
            break
        else:
            first_right_index += 1

    while first_right_index < last_right_index:
        frond = RF[last_right_index]
        if y_m < frond[1]:
            last_right_index -= 1
        else:
            last_right_index += 1
            break


    # --Grab the appropriate list slices from each list
    LF_slice = LF[first_left_index:last_left_index+1]
    RF_slice = RF[first_right_index:last_right_index+1]

    # --Remove the slices from each list
    del LF[first_left_index:last_left_index+1]
    del RF[first_right_index:last_right_index+1]

    # --Add the slice from the right list to the left list
    i = first_left_index
    for x in RF_slice:
        LF.insert(i, x)
        i += 1

    # --Add the slice from the left list to the right list
    i = first_right_index
    for x in LF_slice:
        RF.insert(i, x)
        i += 1

    # Descriptive Note: We can just switch the slices directly because we know that if there were any conflicts from
    # the switch, those fronds would also have been included in the switch.

    # Exchange um and xm , vm and ym , Lm and Rm
    # --Only Lm and Rm need to be exchanged, since um, xm, vm, and ym are all dynamically calculated
    old_rm = dfs_data['FG'][m][1]
    old_lm = dfs_data['FG'][m][0]

    # --We have to convert the Lm and Rm dicts to use the correct keys
    converted_rm = __convert_RF_dict_to_LF(old_rm)
    converted_lm = __convert_LF_dict_to_RF(old_lm)

    dfs_data['FG'][m][1] = converted_lm
    dfs_data['FG'][m][0] = converted_rm

    merge_Fm(dfs_data)