// SPDX-License-Identifier: MIT
pragma solidity ^0.8.4;
/// @notice Optimized sorts and operations for sorted arrays.
/// @author Solady (https://github.com/vectorized/solady/blob/main/src/utils/Sort.sol)
library LibSort {
/*´:°•.°+.*•´.*:˚.°*.˚•´.°:°•.°•.*•´.*:˚.°*.˚•´.°:°•.°+.*•´.*:*/
/* INSERTION SORT */
/*.•°:°.´+˚.*°.˚:*.´•*.+°.•°:´*.´•*.•°.•°:°.´:•˚°.*°.˚:*.´+°.•*/
// - Faster on small arrays (32 or lesser elements).
// - Faster on almost sorted arrays.
// - Smaller bytecode.
// - May be suitable for view functions intended for off-chain querying.
/// @dev Sorts the array in-place with insertion sort.
function insertionSort(uint256[] memory a) internal pure {
/// @solidity memory-safe-assembly
assembly {
let n := mload(a) // Length of `a`.
mstore(a, 0) // For insertion sort's inner loop to terminate.
let h := add(a, shl(5, n)) // High slot.
let s := 0x20
let w := not(0x1f)
for { let i := add(a, s) } 1 {} {
i := add(i, s)
if gt(i, h) { break }
let k := mload(i) // Key.
let j := add(i, w) // The slot before the current slot.
let v := mload(j) // The value of `j`.
if iszero(gt(v, k)) { continue }
for {} 1 {} {
mstore(add(j, s), v)
j := add(j, w) // `sub(j, 0x20)`.
v := mload(j)
if iszero(gt(v, k)) { break }
}
mstore(add(j, s), k)
}
mstore(a, n) // Restore the length of `a`.
}
}
/// @dev Sorts the array in-place with insertion sort.
function insertionSort(int256[] memory a) internal pure {
_flipSign(a);
insertionSort(_toUints(a));
_flipSign(a);
}
/// @dev Sorts the array in-place with insertion sort.
function insertionSort(address[] memory a) internal pure {
insertionSort(_toUints(a));
}
/*´:°•.°+.*•´.*:˚.°*.˚•´.°:°•.°•.*•´.*:˚.°*.˚•´.°:°•.°+.*•´.*:*/
/* INTRO-QUICKSORT */
/*.•°:°.´+˚.*°.˚:*.´•*.+°.•°:´*.´•*.•°.•°:°.´:•˚°.*°.˚:*.´+°.•*/
// - Faster on larger arrays (more than 32 elements).
// - Robust performance.
// - Larger bytecode.
/// @dev Sorts the array in-place with intro-quicksort.
function sort(uint256[] memory a) internal pure {
/// @solidity memory-safe-assembly
assembly {
let w := not(0x1f)
let s := 0x20
let n := mload(a) // Length of `a`.
mstore(a, 0) // For insertion sort's inner loop to terminate.
// Let the stack be the start of the free memory.
let stack := mload(0x40)
for {} iszero(lt(n, 2)) {} {
// Push `l` and `h` to the stack.
// The `shl` by 5 is equivalent to multiplying by `0x20`.
let l := add(a, s)
let h := add(a, shl(5, n))
let j := l
// forgefmt: disable-next-item
for {} iszero(or(eq(j, h), gt(mload(j), mload(add(j, s))))) {} {
j := add(j, s)
}
// If the array is already sorted.
if eq(j, h) { break }
j := h
// forgefmt: disable-next-item
for {} iszero(gt(mload(j), mload(add(j, w)))) {} {
j := add(j, w) // `sub(j, 0x20)`.
}
// If the array is reversed sorted.
if eq(j, l) {
for {} 1 {} {
let t := mload(l)
mstore(l, mload(h))
mstore(h, t)
h := add(h, w) // `sub(h, 0x20)`.
l := add(l, s)
if iszero(lt(l, h)) { break }
}
break
}
// Push `l` and `h` onto the stack.
mstore(stack, l)
mstore(add(stack, s), h)
stack := add(stack, 0x40)
break
}
for { let stackBottom := mload(0x40) } iszero(eq(stack, stackBottom)) {} {
// Pop `l` and `h` from the stack.
stack := sub(stack, 0x40)
let l := mload(stack)
let h := mload(add(stack, s))
// Do insertion sort if `h - l <= 0x20 * 12`.
// Threshold is fine-tuned via trial and error.
if iszero(gt(sub(h, l), 0x180)) {
// Hardcode sort the first 2 elements.
let i := add(l, s)
if iszero(lt(mload(l), mload(i))) {
let t := mload(i)
mstore(i, mload(l))
mstore(l, t)
}
for {} 1 {} {
i := add(i, s)
if gt(i, h) { break }
let k := mload(i) // Key.
let j := add(i, w) // The slot before the current slot.
let v := mload(j) // The value of `j`.
if iszero(gt(v, k)) { continue }
for {} 1 {} {
mstore(add(j, s), v)
j := add(j, w)
v := mload(j)
if iszero(gt(v, k)) { break }
}
mstore(add(j, s), k)
}
continue
}
// Pivot slot is the average of `l` and `h`.
let p := add(shl(5, shr(6, add(l, h))), and(31, l))
// Median of 3 with sorting.
{
function swap(a_, b_) -> _b, _a {
_b := a_
_a := b_
}
let e0 := mload(l)
let e1 := mload(h)
if iszero(lt(e0, e1)) { e1, e0 := swap(e0, e1) }
let e2 := mload(p)
if iszero(lt(e2, e1)) { e2, e1 := swap(e1, e2) }
if iszero(lt(e0, e2)) { e2, e0 := swap(e0, e2) }
mstore(p, e2)
mstore(h, e1)
mstore(l, e0)
}
// Hoare's partition.
{
// The value of the pivot slot.
let x := mload(p)
p := h
for { let i := l } 1 {} {
for {} 1 {} {
i := add(i, s)
if iszero(gt(x, mload(i))) { break }
}
let j := p
for {} 1 {} {
j := add(j, w)
if iszero(lt(x, mload(j))) { break }
}
p := j
if iszero(lt(i, p)) { break }
// Swap slots `i` and `p`.
let t := mload(i)
mstore(i, mload(p))
mstore(p, t)
}
}
// If slice on right of pivot is non-empty, push onto stack.
{
mstore(stack, add(p, s))
// Skip `mstore(add(stack, 0x20), h)`, as it is already on the stack.
stack := add(stack, shl(6, lt(add(p, s), h)))
}
// If slice on left of pivot is non-empty, push onto stack.
{
mstore(stack, l)
mstore(add(stack, s), p)
stack := add(stack, shl(6, gt(p, l)))
}
}
mstore(a, n) // Restore the length of `a`.
}
}
/// @dev Sorts the array in-place with intro-quicksort.
function sort(int256[] memory a) internal pure {
_flipSign(a);
sort(_toUints(a));
_flipSign(a);
}
/// @dev Sorts the array in-place with intro-quicksort.
function sort(address[] memory a) internal pure {
sort(_toUints(a));
}
/*´:°•.°+.*•´.*:˚.°*.˚•´.°:°•.°•.*•´.*:˚.°*.˚•´.°:°•.°+.*•´.*:*/
/* OTHER USEFUL OPERATIONS */
/*.•°:°.´+˚.*°.˚:*.´•*.+°.•°:´*.´•*.•°.•°:°.´:•˚°.*°.˚:*.´+°.•*/
// For performance, the `uniquifySorted` methods will not revert if the
// array is not sorted -- it will simply remove consecutive duplicate elements.
/// @dev Removes duplicate elements from a ascendingly sorted memory array.
function uniquifySorted(uint256[] memory a) internal pure {
/// @solidity memory-safe-assembly
assembly {
// If the length of `a` is greater than 1.
if iszero(lt(mload(a), 2)) {
let x := add(a, 0x20)
let y := add(a, 0x40)
let end := add(a, shl(5, add(mload(a), 1)))
for {} 1 {} {
if iszero(eq(mload(x), mload(y))) {
x := add(x, 0x20)
mstore(x, mload(y))
}
y := add(y, 0x20)
if eq(y, end) { break }
}
mstore(a, shr(5, sub(x, a)))
}
}
}
/// @dev Removes duplicate elements from a ascendingly sorted memory array.
function uniquifySorted(int256[] memory a) internal pure {
uniquifySorted(_toUints(a));
}
/// @dev Removes duplicate elements from a ascendingly sorted memory array.
function uniquifySorted(address[] memory a) internal pure {
uniquifySorted(_toUints(a));
}
/// @dev Returns whether `a` contains `needle`, and the index of `needle`.
/// `index` precedence: equal to > nearest before > nearest after.
function searchSorted(uint256[] memory a, uint256 needle)
internal
pure
returns (bool found, uint256 index)
{
(found, index) = _searchSorted(a, needle, 0);
}
/// @dev Returns whether `a` contains `needle`, and the index of `needle`.
/// `index` precedence: equal to > nearest before > nearest after.
function searchSorted(int256[] memory a, int256 needle)
internal
pure
returns (bool found, uint256 index)
{
(found, index) = _searchSorted(_toUints(a), uint256(needle), 1 << 255);
}
/// @dev Returns whether `a` contains `needle`, and the index of `needle`.
/// `index` precedence: equal to > nearest before > nearest after.
function searchSorted(address[] memory a, address needle)
internal
pure
returns (bool found, uint256 index)
{
(found, index) = _searchSorted(_toUints(a), uint256(uint160(needle)), 0);
}
/// @dev Reverses the array in-place.
function reverse(uint256[] memory a) internal pure {
/// @solidity memory-safe-assembly
assembly {
if iszero(lt(mload(a), 2)) {
let s := 0x20
let w := not(0x1f)
let h := add(a, shl(5, mload(a)))
for { a := add(a, s) } 1 {} {
let t := mload(a)
mstore(a, mload(h))
mstore(h, t)
h := add(h, w)
a := add(a, s)
if iszero(lt(a, h)) { break }
}
}
}
}
/// @dev Reverses the array in-place.
function reverse(int256[] memory a) internal pure {
reverse(_toUints(a));
}
/// @dev Reverses the array in-place.
function reverse(address[] memory a) internal pure {
reverse(_toUints(a));
}
/// @dev Returns whether the array is sorted in ascending order.
function isSorted(uint256[] memory a) internal pure returns (bool result) {
/// @solidity memory-safe-assembly
assembly {
result := 1
if iszero(lt(mload(a), 2)) {
let end := add(a, shl(5, mload(a)))
for { a := add(a, 0x20) } 1 {} {
let p := mload(a)
a := add(a, 0x20)
result := iszero(gt(p, mload(a)))
if iszero(mul(result, xor(a, end))) { break }
}
}
}
}
/// @dev Returns whether the array is sorted in ascending order.
function isSorted(int256[] memory a) internal pure returns (bool result) {
/// @solidity memory-safe-assembly
assembly {
result := 1
if iszero(lt(mload(a), 2)) {
let end := add(a, shl(5, mload(a)))
for { a := add(a, 0x20) } 1 {} {
let p := mload(a)
a := add(a, 0x20)
result := iszero(sgt(p, mload(a)))
if iszero(mul(result, xor(a, end))) { break }
}
}
}
}
/// @dev Returns whether the array is sorted in ascending order.
function isSorted(address[] memory a) internal pure returns (bool result) {
result = isSorted(_toUints(a));
}
/// @dev Returns whether the array is strictly ascending (sorted and uniquified).
function isSortedAndUniquified(uint256[] memory a) internal pure returns (bool result) {
/// @solidity memory-safe-assembly
assembly {
result := 1
if iszero(lt(mload(a), 2)) {
let end := add(a, shl(5, mload(a)))
for { a := add(a, 0x20) } 1 {} {
let p := mload(a)
a := add(a, 0x20)
result := lt(p, mload(a))
if iszero(mul(result, xor(a, end))) { break }
}
}
}
}
/// @dev Returns whether the array is strictly ascending (sorted and uniquified).
function isSortedAndUniquified(int256[] memory a) internal pure returns (bool result) {
/// @solidity memory-safe-assembly
assembly {
result := 1
if iszero(lt(mload(a), 2)) {
let end := add(a, shl(5, mload(a)))
for { a := add(a, 0x20) } 1 {} {
let p := mload(a)
a := add(a, 0x20)
result := slt(p, mload(a))
if iszero(mul(result, xor(a, end))) { break }
}
}
}
}
/// @dev Returns whether the array is strictly ascending (sorted and uniquified).
function isSortedAndUniquified(address[] memory a) internal pure returns (bool result) {
result = isSortedAndUniquified(_toUints(a));
}
/// @dev Returns the sorted set difference of `a` and `b`.
/// Note: Behaviour is undefined if inputs are not sorted and uniquified.
function difference(uint256[] memory a, uint256[] memory b)
internal
pure
returns (uint256[] memory c)
{
c = _difference(a, b, 0);
}
/// @dev Returns the sorted set difference between `a` and `b`.
/// Note: Behaviour is undefined if inputs are not sorted and uniquified.
function difference(int256[] memory a, int256[] memory b)
internal
pure
returns (int256[] memory c)
{
c = _toInts(_difference(_toUints(a), _toUints(b), 1 << 255));
}
/// @dev Returns the sorted set difference between `a` and `b`.
/// Note: Behaviour is undefined if inputs are not sorted and uniquified.
function difference(address[] memory a, address[] memory b)
internal
pure
returns (address[] memory c)
{
c = _toAddresses(_difference(_toUints(a), _toUints(b), 0));
}
/// @dev Returns the sorted set intersection between `a` and `b`.
/// Note: Behaviour is undefined if inputs are not sorted and uniquified.
function intersection(uint256[] memory a, uint256[] memory b)
internal
pure
returns (uint256[] memory c)
{
c = _intersection(a, b, 0);
}
/// @dev Returns the sorted set intersection between `a` and `b`.
/// Note: Behaviour is undefined if inputs are not sorted and uniquified.
function intersection(int256[] memory a, int256[] memory b)
internal
pure
returns (int256[] memory c)
{
c = _toInts(_intersection(_toUints(a), _toUints(b), 1 << 255));
}
/// @dev Returns the sorted set intersection between `a` and `b`.
/// Note: Behaviour is undefined if inputs are not sorted and uniquified.
function intersection(address[] memory a, address[] memory b)
internal
pure
returns (address[] memory c)
{
c = _toAddresses(_intersection(_toUints(a), _toUints(b), 0));
}
/// @dev Returns the sorted set union of `a` and `b`.
/// Note: Behaviour is undefined if inputs are not sorted and uniquified.
function union(uint256[] memory a, uint256[] memory b)
internal
pure
returns (uint256[] memory c)
{
c = _union(a, b, 0);
}
/// @dev Returns the sorted set union of `a` and `b`.
/// Note: Behaviour is undefined if inputs are not sorted and uniquified.
function union(int256[] memory a, int256[] memory b)
internal
pure
returns (int256[] memory c)
{
c = _toInts(_union(_toUints(a), _toUints(b), 1 << 255));
}
/// @dev Returns the sorted set union between `a` and `b`.
/// Note: Behaviour is undefined if inputs are not sorted and uniquified.
function union(address[] memory a, address[] memory b)
internal
pure
returns (address[] memory c)
{
c = _toAddresses(_union(_toUints(a), _toUints(b), 0));
}
/*´:°•.°+.*•´.*:˚.°*.˚•´.°:°•.°•.*•´.*:˚.°*.˚•´.°:°•.°+.*•´.*:*/
/* PRIVATE HELPERS */
/*.•°:°.´+˚.*°.˚:*.´•*.+°.•°:´*.´•*.•°.•°:°.´:•˚°.*°.˚:*.´+°.•*/
/// @dev Reinterpret cast to an uint256 array.
function _toUints(int256[] memory a) private pure returns (uint256[] memory casted) {
/// @solidity memory-safe-assembly
assembly {
casted := a
}
}
/// @dev Reinterpret cast to an uint256 array.
function _toUints(address[] memory a) private pure returns (uint256[] memory casted) {
/// @solidity memory-safe-assembly
assembly {
// As any address written to memory will have the upper 96 bits
// of the word zeroized (as per Solidity spec), we can directly
// compare these addresses as if they are whole uint256 words.
casted := a
}
}
/// @dev Reinterpret cast to an int array.
function _toInts(uint256[] memory a) private pure returns (int256[] memory casted) {
/// @solidity memory-safe-assembly
assembly {
casted := a
}
}
/// @dev Reinterpret cast to an address array.
function _toAddresses(uint256[] memory a) private pure returns (address[] memory casted) {
/// @solidity memory-safe-assembly
assembly {
casted := a
}
}
/// @dev Converts an array of signed integers to unsigned
/// integers suitable for sorting or vice versa.
function _flipSign(int256[] memory a) private pure {
/// @solidity memory-safe-assembly
assembly {
let w := shl(255, 1)
for { let end := add(a, shl(5, mload(a))) } iszero(eq(a, end)) {} {
a := add(a, 0x20)
mstore(a, add(mload(a), w))
}
}
}
/// @dev Returns whether `a` contains `needle`, and the index of `needle`.
/// `index` precedence: equal to > nearest before > nearest after.
function _searchSorted(uint256[] memory a, uint256 needle, uint256 signed)
private
pure
returns (bool found, uint256 index)
{
/// @solidity memory-safe-assembly
assembly {
let w := not(0)
let l := 1
let h := mload(a)
let t := 0
for { needle := add(signed, needle) } 1 {} {
index := shr(1, add(l, h))
t := add(signed, mload(add(a, shl(5, index))))
if or(gt(l, h), eq(t, needle)) { break }
// Decide whether to search the left or right half.
if iszero(gt(needle, t)) {
h := add(index, w)
continue
}
l := add(index, 1)
}
// `index` will be zero in the case of an empty array,
// or when the value is less than the smallest value in the array.
found := eq(t, needle)
t := iszero(iszero(index))
index := mul(add(index, w), t)
found := and(found, t)
}
}
/// @dev Returns the sorted set difference of `a` and `b`.
/// Note: Behaviour is undefined if inputs are not sorted and uniquified.
function _difference(uint256[] memory a, uint256[] memory b, uint256 signed)
private
pure
returns (uint256[] memory c)
{
/// @solidity memory-safe-assembly
assembly {
let s := 0x20
let aEnd := add(a, shl(5, mload(a)))
let bEnd := add(b, shl(5, mload(b)))
c := mload(0x40) // Set `c` to the free memory pointer.
a := add(a, s)
b := add(b, s)
let k := c
for {} iszero(or(gt(a, aEnd), gt(b, bEnd))) {} {
let u := mload(a)
let v := mload(b)
if iszero(xor(u, v)) {
a := add(a, s)
b := add(b, s)
continue
}
if iszero(lt(add(u, signed), add(v, signed))) {
b := add(b, s)
continue
}
k := add(k, s)
mstore(k, u)
a := add(a, s)
}
for {} iszero(gt(a, aEnd)) {} {
k := add(k, s)
mstore(k, mload(a))
a := add(a, s)
}
mstore(c, shr(5, sub(k, c))) // Store the length of `c`.
mstore(0x40, add(k, s)) // Allocate the memory for `c`.
}
}
/// @dev Returns the sorted set intersection between `a` and `b`.
/// Note: Behaviour is undefined if inputs are not sorted and uniquified.
function _intersection(uint256[] memory a, uint256[] memory b, uint256 signed)
private
pure
returns (uint256[] memory c)
{
/// @solidity memory-safe-assembly
assembly {
let s := 0x20
let aEnd := add(a, shl(5, mload(a)))
let bEnd := add(b, shl(5, mload(b)))
c := mload(0x40) // Set `c` to the free memory pointer.
a := add(a, s)
b := add(b, s)
let k := c
for {} iszero(or(gt(a, aEnd), gt(b, bEnd))) {} {
let u := mload(a)
let v := mload(b)
if iszero(xor(u, v)) {
k := add(k, s)
mstore(k, u)
a := add(a, s)
b := add(b, s)
continue
}
if iszero(lt(add(u, signed), add(v, signed))) {
b := add(b, s)
continue
}
a := add(a, s)
}
mstore(c, shr(5, sub(k, c))) // Store the length of `c`.
mstore(0x40, add(k, s)) // Allocate the memory for `c`.
}
}
/// @dev Returns the sorted set union of `a` and `b`.
/// Note: Behaviour is undefined if inputs are not sorted and uniquified.
function _union(uint256[] memory a, uint256[] memory b, uint256 signed)
private
pure
returns (uint256[] memory c)
{
/// @solidity memory-safe-assembly
assembly {
let s := 0x20
let aEnd := add(a, shl(5, mload(a)))
let bEnd := add(b, shl(5, mload(b)))
c := mload(0x40) // Set `c` to the free memory pointer.
a := add(a, s)
b := add(b, s)
let k := c
for {} iszero(or(gt(a, aEnd), gt(b, bEnd))) {} {
let u := mload(a)
let v := mload(b)
if iszero(xor(u, v)) {
k := add(k, s)
mstore(k, u)
a := add(a, s)
b := add(b, s)
continue
}
if iszero(lt(add(u, signed), add(v, signed))) {
k := add(k, s)
mstore(k, v)
b := add(b, s)
continue
}
k := add(k, s)
mstore(k, u)
a := add(a, s)
}
for {} iszero(gt(a, aEnd)) {} {
k := add(k, s)
mstore(k, mload(a))
a := add(a, s)
}
for {} iszero(gt(b, bEnd)) {} {
k := add(k, s)
mstore(k, mload(b))
b := add(b, s)
}
mstore(c, shr(5, sub(k, c))) // Store the length of `c`.
mstore(0x40, add(k, s)) // Allocate the memory for `c`.
}
}
}