mem.mdtlbl

const Memory = cell1; # Read/Write默认实现的读写目标

const Read = (__:
    #**
    使用read读取Memory中的Index处, 读取到RES中, 这里假定传入RES不为`$`
    *#
    take Index = _0;
    take RES = _1;
    setres RES;

    read $ Memory Index;
);
const Write = (__:
    #**
    使用write向Memory中的Index写入Data
    获取Data时会传入Index
    *#
    take Index = _0;
    take[Index] Data = _1; # 会传入下标, 满足一部分需求
    write Data Memory Index;
);
const SwapMem = (
    #**
    交换两个内存中两个位置的值
    返回句柄为交换前Index1的值
    *#
    take Cell1 = _0;
    take Cell2 = _1;
    take Index1 = _2;
    take Index2 = _3;

    take Tmp1 = $; # 用于交换的中间变量
    take Tmp2 = ();

    read Tmp1 Cell1 Index1;
    read Tmp2 Cell2 Index2;

    write Tmp2 Cell1 Index1;
    write Tmp1 Cell2 Index2;
);
const Swap = (
    #**
    交换两个位置的值, 使用Read/Write
    返回句柄为交换前Index1位置的值
    *#
    take Index1 = _0;
    take Index2 = _1;

    take Res = $;
    take[Index1 Res] Num1 = Read;
    take[Index2 ()] Num2 = Read;

    take[Index1 Num2] Write;
    take[Index2 Num1] Write;
);
const Reverse = (__:
    #**
    对[Left,Right]区间的值反转, 使用Read/Write
    *#
    take Left = _0;
    take Right = _1;

    take I = ();
    take J = ();

    I J = Left, Right;

    while I < J {
        take[I J] Swap;
        op I I + 1;
        op J J - 1;
    }
);
const Fill = (__:
    #**
    使用Read/Write从Start到End(不包括)的区域使用Value进行填充
    这不会预先使用take对Value进行求值, 也就是说你可以使用DExp进行填充
        如果你使用DExp来进行填充, 你将会在`_0`接受到当前下标
    *#
    const Value = _0;
    take Start = _1;
    take End = _2;

    take I = ();

    I = Start;

    while I < End {
        take[I Value] Write;
        op I I + 1;
    }
);
const Swaps = (__:
    #**
    使用手摇算法将[LL,LR]与[RL,RR]两个区间的元素进行交换
    反转元素使用Reverse
    *#
    take LL = _0;
    take LR = _1;
    take RL = _2;
    take RR = _3;
    take[LL LR] Reverse;
    take[RL RR] Reverse;
    take[(op $ LR + 1;) (op $ RL - 1;)] Reverse;
    take[LL RR] Reverse;
);
const RWhile = (__:
    # 使用Read/Write将[a, b]区间进行一次距离为一的向右循环
    # 并且在空出的空位写入num
    take A = _0;
    take B = _1;
    take Num = _2;

    take I = ();
    take J = ();

    I = B;

    while I > A {
        op J I - 1;
        take[J ()] Num_1 = Read;
        take[I Num_1] Write;
        I = J;
    }
    take[A Num] Write;
);
const Middle = (
    #**
    获取A与B之间的中间值, 0 <= A <= B
    公式为 A + ((B - A) >> 1)
    但是由于`Mindustry`中数字都是`double`, 所以不用担心啥中间溢出
    并且单条运算效率都相等
    故而将其改为 `(A + B) // 2`, 还少了一条`op`
    *#
    take A = _0;
    take B = _1;
    #op $ A + (op $ B - A; op $ $ >> 1;);
    $ = (A + B) // 2;
);
const BinarySearchInsertIndex = (
    #**
    对`Start..Stop`也就是包含Start不包含Stop的区间进行二分查找
    查找出需要插入的位置, 如果没找到返回值应为Stop
    如果是`[0, 2, 3]`查找1, 则返回`1`也就是`2`的位置
    如果是`[0, 2, 3]`查找2, 则返回`2`也就是`3`的位置, 因为需要在3的位置插入2
    这需要被查找区间内元素有序
    Key是用来取用于比较的key的, 如果你并不想处理那直接传入`(_0:)`即可
    Num是已经使用Key求值之后的数据

    注: 使用Read进行读取
    *#
    take Num = _0;
    const Key = _1;
    take Start = _2;
    take Stop = _3;

    take I = $;
    take J = ();

    I J = Start, Stop;

    while I < J {
        take[I J] Mid = Middle;
        take[Mid ()] Tmp = Read;
        take[Tmp] KeyedTmp = Key;

        if KeyedTmp > Num {
            J = Mid;
        } else {
            op I Mid + 1;
        }
    }

    # result `I`
);
const BinaryInsertSort = (__:
    #**
    二分插入排序算法, 在Cell中对Start..Stop范围中进行二分插入排序
    Key是用来取用于比较的key的, 如果你并不想处理那直接传入`(_0:)`即可

    注: 使用Read/Write进行读写
    *#
    const Key = _0;
    take Start = _1;
    take Stop = _2;

    take I = ();

    op I Start + 1;

    while I < Stop {
        take[I ()] Num = Read;
        take[Num] KeyedNum = Key;
        take[KeyedNum Key Start I Cell] InsertPoint = BinarySearchInsertIndex;
        take[InsertPoint I Num Cell] RWhile;
        op I I + 1;
    }
);
const InsertSort = (__:
    #**
    插入排序算法, 在Cell中对Start..Stop范围中进行二分插入排序
    Key是用来取用于比较的key的, 如果你并不想处理那直接传入`(_0:)`即可

    注: 使用Read/Write进行读写
    *#
    const Key = _0;
    take Start = _1;
    take Stop = _2;

    take I = ();
    take J = ();
    take Tmp = ();
    take KeyedPeekNum = ();

    op I Start + 1;

    while I < Stop {
        take[I ()] Num = Read;
        take[Num] KeyedNum = Key;
        J = I;
        while (Tmp: $ = J; op J J - 1;) > Start {
            take[J ()] PeekNum = Read;
            take[PeekNum] KeyedPeekNum = Key;
            break ! KeyedPeekNum > KeyedNum;

            take[Tmp PeekNum] Write;
        }
        take[Tmp Num] Write;
        op I I + 1;
    }
);
const QUICK_SORT_USE_INSERT_SORT_LEN = 10;
const QuickSort = (__:
    #**
    * 简易快速排序, LL版本.
    * 当区间长度短于阈值时, 会采用插入排序.
    * # params
    * * Left: 排序区间的起始
    * * Right: 排序区间的终止(包含在内)
    * * Stack: 辅助栈内存
    * * StackFloor: 辅助栈内存的最低地址
    * * Key: 用于排序的键
    *#
    take Left = _0;
    take Right = _1;
    take Stack = _2;
    take StackFloor = _3;
    const Key = _4;

    take StackTop = ($ = StackFloor;);

    take FuncSize = 2;

    const PushParam = (__:
        take Left = _0;
        take Right = _1;

        write Left Stack StackTop;
        write Right Stack ($ = StackTop + 1;);
        op StackTop StackTop + FuncSize;
    );
    const PopParam = (__:
        take Left = _0;
        take Right = _1;

        read Left Stack ($ = StackTop - 2;);
        read Right Stack ($ = StackTop - 1;);
        op StackTop StackTop - FuncSize;
    );

    take PushParam[Left Right];
    while StackTop > StackFloor {
        take Left = ();
        take Right = ();
        take PopParam[Left Right];
        if ($ = Right - Left;) < QUICK_SORT_USE_INSERT_SORT_LEN {
            take InsertSort[Key Left ($ = Right + 1;)];
        } else while Left < Right {
            take PivotI = ($ = Left + rand(Right - Left););
            take Pivot = Swap[PivotI Right];
            take PivotK = Key[Pivot];
            take I = ($ = Left;);
            take J = ($ = Left;);
            while I < Right {
                take Num = Read[I ()];
                if Key[Num] < PivotK {
                    take Write[I Read[J ()]];
                    take Write[J Num];
                    op J J + 1;
                }
                op I I + 1;
            }
            take Write[Right Read[J ()]];
            take Write[J Pivot];

            take PushParam[($ = J + 1;) Right];
            Right = J - 1; # 左递归
        }
    }
);