use crate::cmp;
use crate::mem::{self, MaybeUninit, SizedTypeProperties};
use crate::ptr;

/// 旋转范围 `[mid-left, mid+right)`，以使 `mid` 处的元素成为第一个元素。等效地，将范围 `left` 元素向左旋转或将 `right` 元素向右旋转。
///
/// # Safety
///
/// 指定的范围必须对读写有效。
///
/// # Algorithm
///
/// 算法 1 用于较小的 `left + right` 或较大的 `T`。
/// 元素从 `mid - left` 开始一次移动到它们的最终位置，并以 `left + right` 为模以 `right` 步长前进，因此只需要一个临时位置。
/// 最终，我们回到 `mid - left`。
/// 但是，如果 `gcd(left + right, right)` 不为 1，则上述步骤将跳过元素。
/// 例如：
///
/// ```text
/// left = 10, right = 6
/// the `^` indicates an element in its final place
/// 6 7 8 9 10 11 12 13 14 15 . 0 1 2 3 4 5
/// after using one step of the above algorithm (The X will be overwritten at the end of the round,
/// and 12 is stored in a temporary):
/// X 7 8 9 10 11 6 13 14 15 . 0 1 2 3 4 5
///               ^
/// after using another step (now 2 is in the temporary):
/// X 7 8 9 10 11 6 13 14 15 . 0 1 12 3 4 5
///               ^                 ^
/// after the third step (the steps wrap around, and 8 is in the temporary):
/// X 7 2 9 10 11 6 13 14 15 . 0 1 12 3 4 5
///     ^         ^                 ^
/// after 7 more steps, the round ends with the temporary 0 getting put in the X:
/// 0 7 2 9 4 11 6 13 8 15 . 10 1 12 3 14 5
/// ^   ^   ^    ^    ^       ^    ^    ^
/// ```
///
/// 幸运的是，最终元素之间被跳过的元素的数量始终相等，因此我们可以偏移起始位置并进行更多的回合 (总回合数为 `gcd(left + right, right)` 值)。
///
/// 最终结果是所有元素只能一次完成。
///
/// 如果 `left + right` 大但 `min(left, right)` 小到足以适合栈缓冲区，则使用算法 2。
/// 将 `min(left, right)` 元素复制到缓冲区，将 `memmove` 应用于其他元素，然后将缓冲区中的元素移回它们起源的另一侧的 hole 中。
///
/// 一旦 `left + right` 变得足够大，可以向量化的算法就会胜过上面的算法。
/// 可以通过分块并一次执行多个回合来对算法 1 进行矢量化，但是在 `left + right` 变得巨大之前，平均回合数量太少，而且单回合的最坏情况始终存在。
/// 相反，算法 3 利用 `min(left, right)` 元素的重复交换，直到剩下较小的旋转问题为止。
///
/// ```text
/// left = 11, right = 4
/// [4 5 6 7 8 9 10 11 12 13 14 . 0 1 2 3]
///                  ^  ^  ^  ^   ^ ^ ^ ^ swapping the right most elements with elements to the left
/// [4 5 6 7 8 9 10 . 0 1 2 3] 11 12 13 14
///        ^ ^ ^  ^   ^ ^ ^ ^ swapping these
/// [4 5 6 . 0 1 2 3] 7 8 9 10 11 12 13 14
/// we cannot swap any more, but a smaller rotation problem is left to solve
/// ```
/// `left < right` 时，交换发生在左侧。
///
///
///
///
///
pub unsafe fn ptr_rotate<T>(mut left: usize, mut mid: *mut T, mut right: usize) {
    type BufType = [usize; 32];
    if T::IS_ZST {
        return;
    }
    loop {
        // 注意，如果不检查这些情况，以下算法可能会失败
        if (right == 0) || (left == 0) {
            return;
        }
        if (left + right < 24) || (mem::size_of::<T>() > mem::size_of::<[usize; 4]>()) {
            // 算法 1 的微基准测试表明，直到 `left + right == 32` 左右，随机移位的平均性能一直都比较好，但是最坏的情况甚至会达到 16。
            // 24 被选为中间立场。
            // 如果 `T` 的大小大于 4 个 `usize`，则该算法也将优于其他算法。
            // SAFETY: 调用者必须确保 `mid - left` 对读写有效。
            //
            //
            let x = unsafe { mid.sub(left) };
            // 第一轮开始
            // SAFETY: 参见上一个注释。
            let mut tmp: T = unsafe { x.read() };
            let mut i = right;
            // `gcd` 可以通过计算 `gcd(left + right, right)` 预先找到，但执行一个循环会更快，将 gcd 作为副作用计算，然后执行块的其余部分
            //
            //
            let mut gcd = right;
            // 基准测试表明，与一遍交换临时文件相比，一次读取一个临时文件，向后复制，然后在最后写入该临时文件要快得多。
            // 这可能是由于以下事实：交换或替换临时节点在循环中仅使用一个内存地址，而不需要管理两个。
            //
            //
            loop {
                // [long-safety-expl]
                // SAFETY: 调用者必须确保 `[left, left+mid+right)` 对读取和写入都是有效的。
                //
                // - `i` 以 `right` 开头所以 `mid-left <= x+i = x+right = mid-left+right < mid+right`
                // - `i <= left+right-1` 始终为 true
                //   - 如果 `i < left`，`right` 被添加，所以 `i < left+right` 和在下一次迭代中 `left` 从 `i` 中删除，所以它不会更进一步
                //
                //   - 如果 `i >= left`，`left` 立即被删除，所以它不会更进一步。
                // - `i` 不会发生溢出，因为函数的安全保证要求 `mid+right-1 = x+left+right` 对写入有效
                // - 不能发生下溢，因为 `i` 必须大于或等于 `left`，才能发生 `left` 的减法。
                //
                // 因此，如果调用者遵守契约，则 `x+i` 对读和写是有效的
                //
                //
                //
                tmp = unsafe { x.add(i).replace(tmp) };
                // 而不是递增 `i`，然后检查它是否在范围之内，我们检查 `i` 是否在下一次递增时越界。
                // 这样可以防止指针或 `usize` 的任何换行。
                //
                if i >= left {
                    i -= left;
                    if i == 0 {
                        // 第一轮结束
                        // SAFETY: tmp 已从有效来源读取，并且 x 可根据调用者的情况进行写入。
                        //
                        unsafe { x.write(tmp) };
                        break;
                    }
                    // 如果 `left + right >= 15`，则此条件必须在此处
                    if i < gcd {
                        gcd = i;
                    }
                } else {
                    i += right;
                }
            }
            // 用更多的回合完成大块
            for start in 1..gcd {
                // SAFETY: `gcd` 至多等于 `right`，因此 `1..gcd` 中的所有值都可以根据函数的安全保证进行读写，参见上面的 [long-safety-expl]
                //
                //
                tmp = unsafe { x.add(start).read() };
                // [safety-expl-addition]
                //
                // 这里 `start < gcd` so `start < right` so `i < right+right`: `right` 是 `(left+right, right)` 的最大公约数意味着 `left = right` so `i < left+right` so `x+i = mid-left+i` 根据函数的安全保证对于读写总是有效的。
                //
                //
                //
                i = start + right;
                loop {
                    // SAFETY: 请参见 [long-safety-expl] 和 [safety-expl-addition]
                    tmp = unsafe { x.add(i).replace(tmp) };
                    if i >= left {
                        i -= left;
                        if i == start {
                            // SAFETY: 请参见 [long-safety-expl] 和 [safety-expl-addition]
                            unsafe { x.add(start).write(tmp) };
                            break;
                        }
                    } else {
                        i += right;
                    }
                }
            }
            return;
        // `T` 不是零大小类型，所以除以它的大小是可以的。
        } else if cmp::min(left, right) <= mem::size_of::<BufType>() / mem::size_of::<T>() {
            // 算法 2 这里的 `[T; 0]` 是为了确保它与 T 正确对齐
            //
            let mut rawarray = MaybeUninit::<(BufType, [T; 0])>::uninit();
            let buf = rawarray.as_mut_ptr() as *mut T;
            // SAFETY: `mid-left <= mid-left+right < mid+right`
            let dim = unsafe { mid.sub(left).add(right) };
            if left <= right {
                // SAFETY:
                //
                // 1) 关于大小的 `else if` 条件确保 `[mid-left; left]` 将适合 `buf` 而不会溢出，而 `buf` 是在上面创建的，因此不能与 `[mid-left; left]` 的任何值重叠
                //
                // 2) [mid-left, mid+right) 都适用于读取和写入，我们不关心这里的重叠。
                // 3) 关于 `left <= right` 的 `if` 条件确保将 `left` 元素写入 `dim = mid-left+right` 是有效的，因为：
                //    - `buf` 有效，`left` 元素写入其中 1)
                //    - `dim+left = mid-left+right+left = mid+right` 我们写 `[dim, dim+left)`
                //
                //
                //
                unsafe {
                    // 1)
                    ptr::copy_nonoverlapping(mid.sub(left), buf, left);
                    // 2)
                    ptr::copy(mid, mid.sub(left), right);
                    // 3)
                    ptr::copy_nonoverlapping(buf, dim, left);
                }
            } else {
                // SAFETY: 与上述相同的推理，但 `left` 和 `right` 颠倒了
                unsafe {
                    ptr::copy_nonoverlapping(mid, buf, right);
                    ptr::copy(mid.sub(left), dim, left);
                    ptr::copy_nonoverlapping(buf, mid.sub(left), right);
                }
            }
            return;
        } else if left >= right {
            // 算法 3 有另一种交换方式，该方式涉及找到该算法的最后交换位置，然后使用该最后一个块进行交换，而不是像该算法那样交换相邻的块，但是这种方式仍然更快。
            //
            //
            //
            loop {
                // SAFETY:
                // `left >= right` 所以 `[mid-right, mid+right)` 对读写有效从 `mid` 中减去 `right` 每圈被加法抵消并在它之后检查。
                //
                //
                unsafe {
                    ptr::swap_nonoverlapping(mid.sub(right), mid, right);
                    mid = mid.sub(right);
                }
                left -= right;
                if left < right {
                    break;
                }
            }
        } else {
            // 算法 3，`left < right`
            loop {
                // SAFETY: `[mid-left, mid+left)` 对读写有效，因为 `left < right` 所以 `mid+left < mid+right`。
                //
                // 将 `left` 添加到 `mid` 每一圈都会被减法及其后的检查抵消。
                //
                unsafe {
                    ptr::swap_nonoverlapping(mid.sub(left), mid, left);
                    mid = mid.add(left);
                }
                right -= left;
                if right < left {
                    break;
                }
            }
        }
    }
}