// File: contracts/safex/orderbooks/OrderbookFactory.sol



// SPDX-License-Identifier: BUSL-1.1
pragma solidity ^0.8.17;

import {AccessControl} from "@openzeppelin/contracts/access/AccessControl.sol";
import {Orderbook, IOrderbook} from "./Orderbook.sol";
import {CloneFactory} from "../libraries/CloneFactory.sol";
import {IOrderbookFactory} from "../interfaces/IOrderbookFactory.sol";
import {Initializable} from "@openzeppelin/contracts-upgradeable/proxy/utils/Initializable.sol";

interface IERC20 {
    function symbol() external view returns (string memory);
}

contract OrderbookFactory is IOrderbookFactory, Initializable {
    // Orderbooks
    address[] public allPairs;
    /// Address of manager
    address public override engine;
    /// version number of impl
    uint32 public version;
    /// address of order impl
    address public impl;

    error InvalidAccess(address sender, address allowed);
    error PairAlreadyExists(address base, address quote, address pair);
    error SameBaseQuote(address base, address quote);

    constructor() {
    }

    function createBook(
        address base_,
        address quote_
    ) external override returns (address orderbook) {
        if (msg.sender != engine) {
            revert InvalidAccess(msg.sender, engine);
        }

        if (base_ == quote_) {
            revert SameBaseQuote(base_, quote_);
        }

        address pair = _predictAddress(base_, quote_);

        // Check if the address has code
        uint32 size;
        assembly {
            size := extcodesize(pair)
        }

        // If the address has code and it's a clone of impl, revert.
        if (size > 0 || CloneFactory._isClone(impl, pair)) {
            revert PairAlreadyExists(base_, quote_, pair);
        }

        address proxy = CloneFactory._createCloneWithSalt(
            impl,
            _getSalt(base_, quote_)
        );
        IOrderbook(proxy).initialize(
            allPairsLength(),
            base_,
            quote_,
            engine
        );
        allPairs.push(proxy);
        return (proxy);
    }

    function isClone(address vault) external view returns (bool cloned) {
        cloned = CloneFactory._isClone(impl, vault);
    }

    function getBook(uint256 bookId_) external view override returns (address) {
        return allPairs[bookId_];
    }

    function getBookByPair(
        address base,
        address quote
    ) external view override returns (address book) {
        book = _predictAddress(base, quote);
        return address(book).code.length > 0 ? book : address(0);
    }

    function getPairs(
        uint256 start,
        uint256 end
    ) public view override returns (IOrderbookFactory.Pair[] memory) {
        uint256 last = end > allPairs.length ? allPairs.length : end;
        IOrderbookFactory.Pair[] memory pairs = new IOrderbookFactory.Pair[](
            last - start
        );
        for (uint256 i = start; i < last; i++) {
            (address base, address quote) = IOrderbook(allPairs[i])
                .getBaseQuote();
            pairs[i] = Pair(base, quote);
        }
        return pairs;
    }

    function getPairsWithIds(
        uint256[] memory ids
    ) public view override returns (IOrderbookFactory.Pair[] memory pairs) {
        pairs = new IOrderbookFactory.Pair[](ids.length);
        for (uint256 i = 0; i < ids.length; i++) {
            (address base, address quote) = IOrderbook(allPairs[i])
                .getBaseQuote();
            pairs[i] = Pair(base, quote);
        }
        return pairs;
    }

    function getPairNames(
        uint256 start,
        uint256 end
    ) external view override returns (string[] memory names) {
        IOrderbookFactory.Pair[] memory pairs = getPairs(start, end);
        names = new string[](pairs.length);
        for (uint256 i = 0; i < pairs.length; i++) {
            string memory baseName = IERC20(pairs[i].base).symbol();
            string memory quoteName = IERC20(pairs[i].quote).symbol();
            names[i] = string(abi.encodePacked(baseName, "/", quoteName));
        }
        return names;
    }

    function getPairNamesWithIds(
        uint256[] memory ids
    ) external view override returns (string[] memory names) {
        names = new string[](ids.length);
        for (uint256 i = 0; i < ids.length; i++) {
            (address base, address quote) = IOrderbook(allPairs[i])
                .getBaseQuote();
            string memory baseName = IERC20(base).symbol();
            string memory quoteName = IERC20(quote).symbol();
            names[i] = string(abi.encodePacked(baseName, "/", quoteName));
        }
        return names;
    }

    function getBaseQuote(
        address orderbook
    ) external view override returns (address base, address quote) {
        return IOrderbook(orderbook).getBaseQuote();
    }

    /**
     * @dev Initialize orderbook factory contract with engine address, reinitialize if engine is reset.
     * @param engine_ The address of the engine contract
     */
    function initialize(address engine_) public initializer {
        engine = engine_;
        _createImpl();
    }

    function allPairsLength() public view returns (uint256) {
        return allPairs.length;
    }

    // Set immutable, consistant, one rule for orderbook implementation
    function _createImpl() internal {
        address addr;
        bytes memory bytecode = type(Orderbook).creationCode;
        bytes32 salt = keccak256(abi.encodePacked("orderbook", version));
        assembly {
            addr := create2(0, add(bytecode, 0x20), mload(bytecode), salt)
            if iszero(extcodesize(addr)) {
                revert(0, 0)
            }
        }
        impl = addr;
    }

    function _predictAddress(
        address base_,
        address quote_
    ) internal view returns (address) {
        bytes32 salt = _getSalt(base_, quote_);
        return CloneFactory.predictAddressWithSalt(address(this), impl, salt);
    }

    function _getSalt(
        address base_,
        address quote_
    ) internal pure returns (bytes32) {
        return keccak256(abi.encodePacked(base_, quote_));
    }
}

// File: node_modules/@openzeppelin/contracts/access/AccessControl.sol



// SPDX-License-Identifier: MIT
// OpenZeppelin Contracts (last updated v4.9.0) (access/AccessControl.sol)

pragma solidity ^0.8.0;

import "./IAccessControl.sol";
import "../utils/Context.sol";
import "../utils/Strings.sol";
import "../utils/introspection/ERC165.sol";

/**
 * @dev Contract module that allows children to implement role-based access
 * control mechanisms. This is a lightweight version that doesn't allow enumerating role
 * members except through off-chain means by accessing the contract event logs. Some
 * applications may benefit from on-chain enumerability, for those cases see
 * {AccessControlEnumerable}.
 *
 * Roles are referred to by their `bytes32` identifier. These should be exposed
 * in the external API and be unique. The best way to achieve this is by
 * using `public constant` hash digests:
 *
 * ```solidity
 * bytes32 public constant MY_ROLE = keccak256("MY_ROLE");
 * ```
 *
 * Roles can be used to represent a set of permissions. To restrict access to a
 * function call, use {hasRole}:
 *
 * ```solidity
 * function foo() public {
 *     require(hasRole(MY_ROLE, msg.sender));
 *     ...
 * }
 * ```
 *
 * Roles can be granted and revoked dynamically via the {grantRole} and
 * {revokeRole} functions. Each role has an associated admin role, and only
 * accounts that have a role's admin role can call {grantRole} and {revokeRole}.
 *
 * By default, the admin role for all roles is `DEFAULT_ADMIN_ROLE`, which means
 * that only accounts with this role will be able to grant or revoke other
 * roles. More complex role relationships can be created by using
 * {_setRoleAdmin}.
 *
 * WARNING: The `DEFAULT_ADMIN_ROLE` is also its own admin: it has permission to
 * grant and revoke this role. Extra precautions should be taken to secure
 * accounts that have been granted it. We recommend using {AccessControlDefaultAdminRules}
 * to enforce additional security measures for this role.
 */
abstract contract AccessControl is Context, IAccessControl, ERC165 {
    struct RoleData {
        mapping(address => bool) members;
        bytes32 adminRole;
    }

    mapping(bytes32 => RoleData) private _roles;

    bytes32 public constant DEFAULT_ADMIN_ROLE = 0x00;

    /**
     * @dev Modifier that checks that an account has a specific role. Reverts
     * with a standardized message including the required role.
     *
     * The format of the revert reason is given by the following regular expression:
     *
     *  /^AccessControl: account (0x[0-9a-f]{40}) is missing role (0x[0-9a-f]{64})$/
     *
     * _Available since v4.1._
     */
    modifier onlyRole(bytes32 role) {
        _checkRole(role);
        _;
    }

    /**
     * @dev See {IERC165-supportsInterface}.
     */
    function supportsInterface(bytes4 interfaceId) public view virtual override returns (bool) {
        return interfaceId == type(IAccessControl).interfaceId || super.supportsInterface(interfaceId);
    }

    /**
     * @dev Returns `true` if `account` has been granted `role`.
     */
    function hasRole(bytes32 role, address account) public view virtual override returns (bool) {
        return _roles[role].members[account];
    }

    /**
     * @dev Revert with a standard message if `_msgSender()` is missing `role`.
     * Overriding this function changes the behavior of the {onlyRole} modifier.
     *
     * Format of the revert message is described in {_checkRole}.
     *
     * _Available since v4.6._
     */
    function _checkRole(bytes32 role) internal view virtual {
        _checkRole(role, _msgSender());
    }

    /**
     * @dev Revert with a standard message if `account` is missing `role`.
     *
     * The format of the revert reason is given by the following regular expression:
     *
     *  /^AccessControl: account (0x[0-9a-f]{40}) is missing role (0x[0-9a-f]{64})$/
     */
    function _checkRole(bytes32 role, address account) internal view virtual {
        if (!hasRole(role, account)) {
            revert(
                string(
                    abi.encodePacked(
                        "AccessControl: account ",
                        Strings.toHexString(account),
                        " is missing role ",
                        Strings.toHexString(uint256(role), 32)
                    )
                )
            );
        }
    }

    /**
     * @dev Returns the admin role that controls `role`. See {grantRole} and
     * {revokeRole}.
     *
     * To change a role's admin, use {_setRoleAdmin}.
     */
    function getRoleAdmin(bytes32 role) public view virtual override returns (bytes32) {
        return _roles[role].adminRole;
    }

    /**
     * @dev Grants `role` to `account`.
     *
     * If `account` had not been already granted `role`, emits a {RoleGranted}
     * event.
     *
     * Requirements:
     *
     * - the caller must have ``role``'s admin role.
     *
     * May emit a {RoleGranted} event.
     */
    function grantRole(bytes32 role, address account) public virtual override onlyRole(getRoleAdmin(role)) {
        _grantRole(role, account);
    }

    /**
     * @dev Revokes `role` from `account`.
     *
     * If `account` had been granted `role`, emits a {RoleRevoked} event.
     *
     * Requirements:
     *
     * - the caller must have ``role``'s admin role.
     *
     * May emit a {RoleRevoked} event.
     */
    function revokeRole(bytes32 role, address account) public virtual override onlyRole(getRoleAdmin(role)) {
        _revokeRole(role, account);
    }

    /**
     * @dev Revokes `role` from the calling account.
     *
     * Roles are often managed via {grantRole} and {revokeRole}: this function's
     * purpose is to provide a mechanism for accounts to lose their privileges
     * if they are compromised (such as when a trusted device is misplaced).
     *
     * If the calling account had been revoked `role`, emits a {RoleRevoked}
     * event.
     *
     * Requirements:
     *
     * - the caller must be `account`.
     *
     * May emit a {RoleRevoked} event.
     */
    function renounceRole(bytes32 role, address account) public virtual override {
        require(account == _msgSender(), "AccessControl: can only renounce roles for self");

        _revokeRole(role, account);
    }

    /**
     * @dev Grants `role` to `account`.
     *
     * If `account` had not been already granted `role`, emits a {RoleGranted}
     * event. Note that unlike {grantRole}, this function doesn't perform any
     * checks on the calling account.
     *
     * May emit a {RoleGranted} event.
     *
     * [WARNING]
     * ====
     * This function should only be called from the constructor when setting
     * up the initial roles for the system.
     *
     * Using this function in any other way is effectively circumventing the admin
     * system imposed by {AccessControl}.
     * ====
     *
     * NOTE: This function is deprecated in favor of {_grantRole}.
     */
    function _setupRole(bytes32 role, address account) internal virtual {
        _grantRole(role, account);
    }

    /**
     * @dev Sets `adminRole` as ``role``'s admin role.
     *
     * Emits a {RoleAdminChanged} event.
     */
    function _setRoleAdmin(bytes32 role, bytes32 adminRole) internal virtual {
        bytes32 previousAdminRole = getRoleAdmin(role);
        _roles[role].adminRole = adminRole;
        emit RoleAdminChanged(role, previousAdminRole, adminRole);
    }

    /**
     * @dev Grants `role` to `account`.
     *
     * Internal function without access restriction.
     *
     * May emit a {RoleGranted} event.
     */
    function _grantRole(bytes32 role, address account) internal virtual {
        if (!hasRole(role, account)) {
            _roles[role].members[account] = true;
            emit RoleGranted(role, account, _msgSender());
        }
    }

    /**
     * @dev Revokes `role` from `account`.
     *
     * Internal function without access restriction.
     *
     * May emit a {RoleRevoked} event.
     */
    function _revokeRole(bytes32 role, address account) internal virtual {
        if (hasRole(role, account)) {
            _roles[role].members[account] = false;
            emit RoleRevoked(role, account, _msgSender());
        }
    }
}

// File: contracts/safex/orderbooks/Orderbook.sol



// SPDX-License-Identifier: BUSL-1.1

pragma solidity ^0.8.17;

import {IOrderbook} from "../interfaces/IOrderbook.sol";
import {Initializable} from "../../security/Initializable.sol";
import {TransferHelper} from "../libraries/TransferHelper.sol";
import {ExchangeLinkedList} from "../libraries/ExchangeLinkedList.sol";
import {ExchangeOrderbook} from "../libraries/ExchangeOrderbook.sol";

interface IWETHMinimal {
    function WETH() external view returns (address);

    function transfer(address to, uint256 value) external returns (bool);

    function withdraw(uint256) external;
}

contract Orderbook is IOrderbook, Initializable {
    using ExchangeLinkedList for ExchangeLinkedList.PriceLinkedList;
    using ExchangeOrderbook for ExchangeOrderbook.OrderStorage;

    // Pair Struct
    struct Pair {
        uint256 id;
        address base;
        address quote;
        address engine;
    }

    Pair private pair;

    uint64 private decDiff;
    bool private baseBquote;

    ExchangeLinkedList.PriceLinkedList private priceLists;
    ExchangeOrderbook.OrderStorage private _askOrders;
    ExchangeOrderbook.OrderStorage private _bidOrders;

    error InvalidDecimals(uint8 base, uint8 quote);
    error InvalidAccess(address sender, address allowed);
    error OrderSizeTooSmall(uint256 amount, uint256 minRequired);

    function initialize(
        uint256 id_,
        address base_,
        address quote_,
        address engine_
    ) external initializer {
        uint8 baseD = TransferHelper.decimals(base_);
        uint8 quoteD = TransferHelper.decimals(quote_);
        if (baseD > 18 || quoteD > 18) {
            revert InvalidDecimals(baseD, quoteD);
        }
        (uint8 diff, bool baseBquote_) = _absdiff(baseD, quoteD);
        decDiff = uint64(10 ** diff);
        baseBquote = baseBquote_;
        pair = Pair(id_, base_, quote_, engine_);
    }

    modifier onlyEngine() {
        if (msg.sender != pair.engine) {
            revert InvalidAccess(msg.sender, pair.engine);
        }
        _;
    }

    function setLmp(uint256 price) external onlyEngine {
        priceLists._setLmp(price);
    }

    function placeAsk(
        address owner,
        uint256 price,
        uint256 amount
    ) external onlyEngine returns (uint32 id) {
        id = _askOrders._createOrder(owner, amount);
        // check if the price is new in the list. if not, insert id to the list
        if (_askOrders._isEmpty(price)) {
            priceLists._insert(false, price);
        }
        _askOrders._insertId(price, id, amount);
        return id;
    }

    function placeBid(
        address owner,
        uint256 price,
        uint256 amount
    ) external onlyEngine returns (uint32 id) {
        id = _bidOrders._createOrder(owner, amount);
        // check if the price is new in the list. if not, insert id to the list
        if (_bidOrders._isEmpty(price)) {
            priceLists._insert(true, price);
        }
        _bidOrders._insertId(price, id, amount);
        return id;
    }

    function cancelOrder(
        bool isBid,
        uint256 price,
        uint32 orderId,
        address owner
    ) external onlyEngine returns (uint256 remaining) {
        // check order owner
        ExchangeOrderbook.Order memory order = isBid
            ? _bidOrders._getOrder(orderId)
            : _askOrders._getOrder(orderId);
        if (order.owner != owner) {
            revert InvalidAccess(owner, order.owner);
        }

        if (priceLists._checkPriceExists(isBid, price)) {
            isBid
                ? _bidOrders._deleteOrder(price, orderId)
                : _askOrders._deleteOrder(price, orderId);
            isBid
                ? _sendFunds(pair.quote, owner, order.depositAmount)
                : _sendFunds(pair.base, owner, order.depositAmount);

            // check if the canceled order was the last order in the list
            if (isEmpty(isBid, price)) {
                priceLists._delete(isBid, price);
            }
        }

        return (order.depositAmount);
    }

    function execute(
        uint32 orderId,
        bool isBid,
        uint256 price,
        address sender,
        uint256 amount
    ) external onlyEngine returns (address owner) {
        ExchangeOrderbook.Order memory order = isBid
            ? _bidOrders._getOrder(orderId)
            : _askOrders._getOrder(orderId);
        uint256 converted = convert(price, amount, isBid);
        uint256 dust = convert(price, 1, isBid);
        // if isBid == true, sender is matching ask order with bid order(i.e. selling base to receive quote), otherwise sender is matching bid order with ask order(i.e. buying base with quote)
        if (isBid) {
            // decrease remaining amount of order
            uint256 withDust = _bidOrders._decreaseOrder(price, orderId, converted, dust);
            // sender is matching ask order for base asset with quote asset
            _sendFunds(pair.base, order.owner, amount);
            // send converted amount of quote asset from owner to sender
            _sendFunds(pair.quote, sender, withDust);
        }
        // if the order is bid order on the base/quote pair
        else {
            // decrease remaining amount of order
            uint256 withDust = _askOrders._decreaseOrder(price, orderId, converted, dust);
            // sender is matching bid order for quote asset with base asset
            // send deposited amount of quote asset from sender to owner
            _sendFunds(pair.quote, order.owner, amount);
            // send converted amount of base asset from owner to sender
            _sendFunds(pair.base, sender, withDust);
        }
        return order.owner;
    }

    function fpop(
        bool isBid,
        uint256 price,
        uint256 remaining
    ) external onlyEngine returns (uint32 orderId, uint256 required) {
        orderId = isBid ? _bidOrders._head(price) : _askOrders._head(price);
        ExchangeOrderbook.Order memory order = isBid
            ? _bidOrders._getOrder(orderId)
            : _askOrders._getOrder(orderId);
        required = convert(price, order.depositAmount, !isBid);
        if (required <= remaining) {
            isBid ? _bidOrders._fpop(price) : _askOrders._fpop(price);
            if (isEmpty(isBid, price)) {
                isBid
                    ? priceLists.bidHead = priceLists._next(isBid, price)
                    : priceLists.askHead = priceLists._next(isBid, price);
            }
        }
        return (orderId, required);
    }

    function _sendFunds(
        address token,
        address to,
        uint256 amount
    ) internal returns (bool) {
        address weth = IWETHMinimal(pair.engine).WETH();
        if (token == weth) {
            IWETHMinimal(weth).withdraw(amount);
            return payable(to).send(amount);
        } else {
            TransferHelper.safeTransfer(token, to, amount);
            return true;
        }
    }

    function _absdiff(uint8 a, uint8 b) internal pure returns (uint8, bool) {
        return (a > b ? a - b : b - a, a > b);
    }

    // get required amount for executing the order
    function getRequired(
        bool isBid,
        uint256 price,
        uint32 orderId
    ) external view returns (uint256 required) {
        ExchangeOrderbook.Order memory order = isBid
            ? _bidOrders._getOrder(orderId)
            : _askOrders._getOrder(orderId);
        if (order.depositAmount == 0) {
            return 0;
        }
        /* if ask, required base amount is quoteAmount / price,
         * converting the number converting decimal from quote to base,
         * otherwise quote amount is baseAmount * price, converting decimal from base to quote
         */
        return convert(price, order.depositAmount, isBid);
    }

    /////////////////////////////////
    /// Price linked list methods ///
    /////////////////////////////////

    function heads() external view returns (uint256, uint256) {
        return priceLists._heads();
    }

    function askHead() external view returns (uint256) {
        return priceLists._askHead();
    }

    function bidHead() external view returns (uint256) {
        return priceLists._bidHead();
    }

    function mktPrice() external view returns (uint256) {
        return priceLists._mktPrice();
    }

    function getPrices(
        bool isBid,
        uint32 n
    ) external view returns (uint256[] memory) {
        return priceLists._getPrices(isBid, n);
    }

    function getOrderIds(
        bool isBid,
        uint256 price,
        uint32 n
    ) external view returns (uint32[] memory) {
        return
            isBid
                ? _bidOrders._getOrderIds(price, n)
                : _askOrders._getOrderIds(price, n);
    }

    function getOrders(
        bool isBid,
        uint256 price,
        uint32 n
    ) external view returns (ExchangeOrderbook.Order[] memory) {
        return
            isBid
                ? _bidOrders._getOrders(price, n)
                : _askOrders._getOrders(price, n);
    }

    function getOrder(
        bool isBid,
        uint32 orderId
    ) external view returns (ExchangeOrderbook.Order memory) {
        return
            isBid
                ? _bidOrders._getOrder(orderId)
                : _askOrders._getOrder(orderId);
    }

    function getBaseQuote()
        external
        view
        returns (address base, address quote)
    {
        return (pair.base, pair.quote);
    }

    /**
     * @dev get asset value in quote asset if isBid is true, otherwise get asset value in base asset
     * @param amount amount of asset in base asset if isBid is true, otherwise in quote asset
     * @param isBid if true, get asset value in quote asset, otherwise get asset value in base asset
     * @return converted asset value in quote asset if isBid is true, otherwise asset value in base asset
     */
    function assetValue(
        uint256 amount,
        bool isBid
    ) external view returns (uint256 converted) {
        return convert(priceLists._mktPrice(), amount, isBid);
    }

    function isEmpty(bool isBid, uint256 price) public view returns (bool) {
        return isBid ? _bidOrders._isEmpty(price) : _askOrders._isEmpty(price);
    }

    function convert(
        uint256 price,
        uint256 amount,
        bool isBid
    ) public view returns (uint256 converted) {
        if (isBid) {
            // convert quote to base
            return
                baseBquote
                    ? ((amount * price) / 1e8) / decDiff
                    : ((amount * price) / 1e8) * decDiff;
        } else {
            // convert base to quote
            return
                baseBquote
                    ? ((amount * 1e8) / price) * decDiff
                    : ((amount * 1e8) / price) / decDiff;
        }
    }

    receive() external payable {
        assert(msg.sender == IWETHMinimal(pair.engine).WETH());
    }
}

// File: contracts/safex/libraries/CloneFactory.sol



// SPDX-License-Identifier: BUSL-1.1

pragma solidity ^0.8.17;

library CloneFactory {
    function _createClone(address target) internal returns (address result) {
        // convert address to 20 bytes
        bytes20 targetBytes = bytes20(target);

        // actual code //
        // 3d602d80600a3d3981f3363d3d373d3d3d363d73bebebebebebebebebebebebebebebebebebebebe5af43d82803e903d91602b57fd5bf3

        // creation code //
        // copy runtime code into memory and return it
        // 3d602d80600a3d3981f3

        // runtime code //
        // code to delegatecall to address
        // 363d3d373d3d3d363d73 address 5af43d82803e903d91602b57fd5bf3

        assembly {
            /*
            reads the 32 bytes of memory starting at pointer stored in 0x40

            In solidity, the 0x40 slot in memory is special: it contains the "free memory pointer"
            which points to the end of the currently allocated memory.
            */
            let clone := mload(0x40)
            // store 32 bytes to memory starting at "clone"
            mstore(
                clone,
                0x3d602d80600a3d3981f3363d3d373d3d3d363d73000000000000000000000000
            )

            /*
              |              20 bytes                |
            0x3d602d80600a3d3981f3363d3d373d3d3d363d73000000000000000000000000
                                                      ^
                                                      pointer
            */
            // store 32 bytes to memory starting at "clone" + 20 bytes
            // 0x14 = 20
            mstore(add(clone, 0x14), targetBytes)

            /*
              |               20 bytes               |                 20 bytes              |
            0x3d602d80600a3d3981f3363d3d373d3d3d363d73bebebebebebebebebebebebebebebebebebebebe
                                                                                              ^
                                                                                              pointer
            */
            // store 32 bytes to memory starting at "clone" + 40 bytes
            // 0x28 = 40
            mstore(
                add(clone, 0x28),
                0x5af43d82803e903d91602b57fd5bf30000000000000000000000000000000000
            )

            /*
              |               20 bytes               |                 20 bytes              |           15 bytes          |
            0x3d602d80600a3d3981f3363d3d373d3d3d363d73bebebebebebebebebebebebebebebebebebebebe5af43d82803e903d91602b57fd5bf3
            */
            // create new contract
            // send 0 Ether
            // code starts at pointer stored in "clone"
            // code size 0x37 (55 bytes)
            result := create(0, clone, 0x37)
        }
    }

    function _isClone(
        address target,
        address query
    ) internal view returns (bool result) {
        bytes20 targetBytes = bytes20(target);
        assembly {
            let clone := mload(0x40)
            mstore(
                clone,
                0x363d3d373d3d3d363d7300000000000000000000000000000000000000000000
            )
            mstore(add(clone, 0xa), targetBytes)
            mstore(
                add(clone, 0x1e),
                0x5af43d82803e903d91602b57fd5bf30000000000000000000000000000000000
            )

            let other := add(clone, 0x40)
            extcodecopy(query, other, 0, 0x2d)
            result := and(
                eq(mload(clone), mload(other)),
                eq(mload(add(clone, 0xd)), mload(add(other, 0xd)))
            )
        }
    }

    function _createCloneWithSalt(
        address target,
        bytes32 salt
    ) internal returns (address result) {
        bytes20 targetBytes = bytes20(target);
        assembly {
            let clone := mload(0x40)
            mstore(
                clone,
                0x3d602d80600a3d3981f3363d3d373d3d3d363d73000000000000000000000000
            )
            mstore(add(clone, 0x14), targetBytes)
            mstore(
                add(clone, 0x28),
                0x5af43d82803e903d91602b57fd5bf30000000000000000000000000000000000
            )

            // Use create2 with the provided salt
            result := create2(0, clone, 0x37, salt)
            if iszero(extcodesize(result)) {
                revert(0, 0)
            }
        }
    }

    function predictAddressWithSalt(address deployer, address target, bytes32 salt) internal pure returns (address) {
    // Create the expected bytecode of the minimal proxy
    bytes memory bytecode = abi.encodePacked(
        hex"3d602d80600a3d3981f3363d3d373d3d3d363d73",
        target,
        hex"5af43d82803e903d91602b57fd5bf3"
    );
    
    bytes32 bytecodeHash = keccak256(bytecode);

    bytes32 _data = keccak256(
        abi.encodePacked(
            bytes1(0xff),
            deployer,
            salt,
            bytecodeHash
        )
    );
    return address(uint160(uint256(_data)));
}

}

// File: contracts/safex/interfaces/IOrderbookFactory.sol



// SPDX-License-Identifier: BUSL-1.1

pragma solidity ^0.8.17;

interface IOrderbookFactory {
    struct Pair {
        address base;
        address quote;
    }

    function createBook(address bid_, address ask_) external returns (address orderbook);

    function getBook(uint256 bookId_) external view returns (address orderbook);

    function getBookByPair(address base, address quote) external view returns (address book);

    function getBaseQuote(address orderbook) external view returns (address base, address quote);

    function allPairsLength() external view returns (uint256);

    /// Address of a manager
    function engine() external view returns (address);

    function getPairs(uint256 start, uint256 end) external view returns (Pair[] memory);

    function getPairsWithIds(uint256[] memory ids) external view returns (Pair[] memory);

    function getPairNames(uint256 start, uint256 end) external view returns (string[] memory names);

    function getPairNamesWithIds(uint256[] memory ids) external view returns (string[] memory names);
}

// File: node_modules/@openzeppelin/contracts-upgradeable/proxy/utils/Initializable.sol



// SPDX-License-Identifier: MIT
// OpenZeppelin Contracts (last updated v4.9.0) (proxy/utils/Initializable.sol)

pragma solidity ^0.8.2;

import "../../utils/AddressUpgradeable.sol";

/**
 * @dev This is a base contract to aid in writing upgradeable contracts, or any kind of contract that will be deployed
 * behind a proxy. Since proxied contracts do not make use of a constructor, it's common to move constructor logic to an
 * external initializer function, usually called `initialize`. It then becomes necessary to protect this initializer
 * function so it can only be called once. The {initializer} modifier provided by this contract will have this effect.
 *
 * The initialization functions use a version number. Once a version number is used, it is consumed and cannot be
 * reused. This mechanism prevents re-execution of each "step" but allows the creation of new initialization steps in
 * case an upgrade adds a module that needs to be initialized.
 *
 * For example:
 *
 * [.hljs-theme-light.nopadding]
 * ```solidity
 * contract MyToken is ERC20Upgradeable {
 *     function initialize() initializer public {
 *         __ERC20_init("MyToken", "MTK");
 *     }
 * }
 *
 * contract MyTokenV2 is MyToken, ERC20PermitUpgradeable {
 *     function initializeV2() reinitializer(2) public {
 *         __ERC20Permit_init("MyToken");
 *     }
 * }
 * ```
 *
 * TIP: To avoid leaving the proxy in an uninitialized state, the initializer function should be called as early as
 * possible by providing the encoded function call as the `_data` argument to {ERC1967Proxy-constructor}.
 *
 * CAUTION: When used with inheritance, manual care must be taken to not invoke a parent initializer twice, or to ensure
 * that all initializers are idempotent. This is not verified automatically as constructors are by Solidity.
 *
 * [CAUTION]
 * ====
 * Avoid leaving a contract uninitialized.
 *
 * An uninitialized contract can be taken over by an attacker. This applies to both a proxy and its implementation
 * contract, which may impact the proxy. To prevent the implementation contract from being used, you should invoke
 * the {_disableInitializers} function in the constructor to automatically lock it when it is deployed:
 *
 * [.hljs-theme-light.nopadding]
 * ```
 * /// @custom:oz-upgrades-unsafe-allow constructor
 * constructor() {
 *     _disableInitializers();
 * }
 * ```
 * ====
 */
abstract contract Initializable {
    /**
     * @dev Indicates that the contract has been initialized.
     * @custom:oz-retyped-from bool
     */
    uint8 private _initialized;

    /**
     * @dev Indicates that the contract is in the process of being initialized.
     */
    bool private _initializing;

    /**
     * @dev Triggered when the contract has been initialized or reinitialized.
     */
    event Initialized(uint8 version);

    /**
     * @dev A modifier that defines a protected initializer function that can be invoked at most once. In its scope,
     * `onlyInitializing` functions can be used to initialize parent contracts.
     *
     * Similar to `reinitializer(1)`, except that functions marked with `initializer` can be nested in the context of a
     * constructor.
     *
     * Emits an {Initialized} event.
     */
    modifier initializer() {
        bool isTopLevelCall = !_initializing;
        require(
            (isTopLevelCall && _initialized < 1) || (!AddressUpgradeable.isContract(address(this)) && _initialized == 1),
            "Initializable: contract is already initialized"
        );
        _initialized = 1;
        if (isTopLevelCall) {
            _initializing = true;
        }
        _;
        if (isTopLevelCall) {
            _initializing = false;
            emit Initialized(1);
        }
    }

    /**
     * @dev A modifier that defines a protected reinitializer function that can be invoked at most once, and only if the
     * contract hasn't been initialized to a greater version before. In its scope, `onlyInitializing` functions can be
     * used to initialize parent contracts.
     *
     * A reinitializer may be used after the original initialization step. This is essential to configure modules that
     * are added through upgrades and that require initialization.
     *
     * When `version` is 1, this modifier is similar to `initializer`, except that functions marked with `reinitializer`
     * cannot be nested. If one is invoked in the context of another, execution will revert.
     *
     * Note that versions can jump in increments greater than 1; this implies that if multiple reinitializers coexist in
     * a contract, executing them in the right order is up to the developer or operator.
     *
     * WARNING: setting the version to 255 will prevent any future reinitialization.
     *
     * Emits an {Initialized} event.
     */
    modifier reinitializer(uint8 version) {
        require(!_initializing && _initialized < version, "Initializable: contract is already initialized");
        _initialized = version;
        _initializing = true;
        _;
        _initializing = false;
        emit Initialized(version);
    }

    /**
     * @dev Modifier to protect an initialization function so that it can only be invoked by functions with the
     * {initializer} and {reinitializer} modifiers, directly or indirectly.
     */
    modifier onlyInitializing() {
        require(_initializing, "Initializable: contract is not initializing");
        _;
    }

    /**
     * @dev Locks the contract, preventing any future reinitialization. This cannot be part of an initializer call.
     * Calling this in the constructor of a contract will prevent that contract from being initialized or reinitialized
     * to any version. It is recommended to use this to lock implementation contracts that are designed to be called
     * through proxies.
     *
     * Emits an {Initialized} event the first time it is successfully executed.
     */
    function _disableInitializers() internal virtual {
        require(!_initializing, "Initializable: contract is initializing");
        if (_initialized != type(uint8).max) {
            _initialized = type(uint8).max;
            emit Initialized(type(uint8).max);
        }
    }

    /**
     * @dev Returns the highest version that has been initialized. See {reinitializer}.
     */
    function _getInitializedVersion() internal view returns (uint8) {
        return _initialized;
    }

    /**
     * @dev Returns `true` if the contract is currently initializing. See {onlyInitializing}.
     */
    function _isInitializing() internal view returns (bool) {
        return _initializing;
    }
}

// File: node_modules/@openzeppelin/contracts/access/IAccessControl.sol



// SPDX-License-Identifier: MIT
// OpenZeppelin Contracts v4.4.1 (access/IAccessControl.sol)

pragma solidity ^0.8.0;

/**
 * @dev External interface of AccessControl declared to support ERC165 detection.
 */
interface IAccessControl {
    /**
     * @dev Emitted when `newAdminRole` is set as ``role``'s admin role, replacing `previousAdminRole`
     *
     * `DEFAULT_ADMIN_ROLE` is the starting admin for all roles, despite
     * {RoleAdminChanged} not being emitted signaling this.
     *
     * _Available since v3.1._
     */
    event RoleAdminChanged(bytes32 indexed role, bytes32 indexed previousAdminRole, bytes32 indexed newAdminRole);

    /**
     * @dev Emitted when `account` is granted `role`.
     *
     * `sender` is the account that originated the contract call, an admin role
     * bearer except when using {AccessControl-_setupRole}.
     */
    event RoleGranted(bytes32 indexed role, address indexed account, address indexed sender);

    /**
     * @dev Emitted when `account` is revoked `role`.
     *
     * `sender` is the account that originated the contract call:
     *   - if using `revokeRole`, it is the admin role bearer
     *   - if using `renounceRole`, it is the role bearer (i.e. `account`)
     */
    event RoleRevoked(bytes32 indexed role, address indexed account, address indexed sender);

    /**
     * @dev Returns `true` if `account` has been granted `role`.
     */
    function hasRole(bytes32 role, address account) external view returns (bool);

    /**
     * @dev Returns the admin role that controls `role`. See {grantRole} and
     * {revokeRole}.
     *
     * To change a role's admin, use {AccessControl-_setRoleAdmin}.
     */
    function getRoleAdmin(bytes32 role) external view returns (bytes32);

    /**
     * @dev Grants `role` to `account`.
     *
     * If `account` had not been already granted `role`, emits a {RoleGranted}
     * event.
     *
     * Requirements:
     *
     * - the caller must have ``role``'s admin role.
     */
    function grantRole(bytes32 role, address account) external;

    /**
     * @dev Revokes `role` from `account`.
     *
     * If `account` had been granted `role`, emits a {RoleRevoked} event.
     *
     * Requirements:
     *
     * - the caller must have ``role``'s admin role.
     */
    function revokeRole(bytes32 role, address account) external;

    /**
     * @dev Revokes `role` from the calling account.
     *
     * Roles are often managed via {grantRole} and {revokeRole}: this function's
     * purpose is to provide a mechanism for accounts to lose their privileges
     * if they are compromised (such as when a trusted device is misplaced).
     *
     * If the calling account had been granted `role`, emits a {RoleRevoked}
     * event.
     *
     * Requirements:
     *
     * - the caller must be `account`.
     */
    function renounceRole(bytes32 role, address account) external;
}

// File: node_modules/@openzeppelin/contracts/utils/Context.sol



// SPDX-License-Identifier: MIT
// OpenZeppelin Contracts v4.4.1 (utils/Context.sol)

pragma solidity ^0.8.0;

/**
 * @dev Provides information about the current execution context, including the
 * sender of the transaction and its data. While these are generally available
 * via msg.sender and msg.data, they should not be accessed in such a direct
 * manner, since when dealing with meta-transactions the account sending and
 * paying for execution may not be the actual sender (as far as an application
 * is concerned).
 *
 * This contract is only required for intermediate, library-like contracts.
 */
abstract contract Context {
    function _msgSender() internal view virtual returns (address) {
        return msg.sender;
    }

    function _msgData() internal view virtual returns (bytes calldata) {
        return msg.data;
    }
}

// File: node_modules/@openzeppelin/contracts/utils/Strings.sol



// SPDX-License-Identifier: MIT
// OpenZeppelin Contracts (last updated v4.9.0) (utils/Strings.sol)

pragma solidity ^0.8.0;

import "./math/Math.sol";
import "./math/SignedMath.sol";

/**
 * @dev String operations.
 */
library Strings {
    bytes16 private constant _SYMBOLS = "0123456789abcdef";
    uint8 private constant _ADDRESS_LENGTH = 20;

    /**
     * @dev Converts a `uint256` to its ASCII `string` decimal representation.
     */
    function toString(uint256 value) internal pure returns (string memory) {
        unchecked {
            uint256 length = Math.log10(value) + 1;
            string memory buffer = new string(length);
            uint256 ptr;
            /// @solidity memory-safe-assembly
            assembly {
                ptr := add(buffer, add(32, length))
            }
            while (true) {
                ptr--;
                /// @solidity memory-safe-assembly
                assembly {
                    mstore8(ptr, byte(mod(value, 10), _SYMBOLS))
                }
                value /= 10;
                if (value == 0) break;
            }
            return buffer;
        }
    }

    /**
     * @dev Converts a `int256` to its ASCII `string` decimal representation.
     */
    function toString(int256 value) internal pure returns (string memory) {
        return string(abi.encodePacked(value < 0 ? "-" : "", toString(SignedMath.abs(value))));
    }

    /**
     * @dev Converts a `uint256` to its ASCII `string` hexadecimal representation.
     */
    function toHexString(uint256 value) internal pure returns (string memory) {
        unchecked {
            return toHexString(value, Math.log256(value) + 1);
        }
    }

    /**
     * @dev Converts a `uint256` to its ASCII `string` hexadecimal representation with fixed length.
     */
    function toHexString(uint256 value, uint256 length) internal pure returns (string memory) {
        bytes memory buffer = new bytes(2 * length + 2);
        buffer[0] = "0";
        buffer[1] = "x";
        for (uint256 i = 2 * length + 1; i > 1; --i) {
            buffer[i] = _SYMBOLS[value & 0xf];
            value >>= 4;
        }
        require(value == 0, "Strings: hex length insufficient");
        return string(buffer);
    }

    /**
     * @dev Converts an `address` with fixed length of 20 bytes to its not checksummed ASCII `string` hexadecimal representation.
     */
    function toHexString(address addr) internal pure returns (string memory) {
        return toHexString(uint256(uint160(addr)), _ADDRESS_LENGTH);
    }

    /**
     * @dev Returns true if the two strings are equal.
     */
    function equal(string memory a, string memory b) internal pure returns (bool) {
        return keccak256(bytes(a)) == keccak256(bytes(b));
    }
}

// File: node_modules/@openzeppelin/contracts/utils/introspection/ERC165.sol



// SPDX-License-Identifier: MIT
// OpenZeppelin Contracts v4.4.1 (utils/introspection/ERC165.sol)

pragma solidity ^0.8.0;

import "./IERC165.sol";

/**
 * @dev Implementation of the {IERC165} interface.
 *
 * Contracts that want to implement ERC165 should inherit from this contract and override {supportsInterface} to check
 * for the additional interface id that will be supported. For example:
 *
 * ```solidity
 * function supportsInterface(bytes4 interfaceId) public view virtual override returns (bool) {
 *     return interfaceId == type(MyInterface).interfaceId || super.supportsInterface(interfaceId);
 * }
 * ```
 *
 * Alternatively, {ERC165Storage} provides an easier to use but more expensive implementation.
 */
abstract contract ERC165 is IERC165 {
    /**
     * @dev See {IERC165-supportsInterface}.
     */
    function supportsInterface(bytes4 interfaceId) public view virtual override returns (bool) {
        return interfaceId == type(IERC165).interfaceId;
    }
}

// File: contracts/safex/interfaces/IOrderbook.sol



// SPDX-License-Identifier: BUSL-1.1

pragma solidity ^0.8.17;

import "../libraries/ExchangeOrderbook.sol";

interface IOrderbook {
    function initialize(uint256 id, address base_, address quote_, address engine_) external;

    function fpop(bool isBid, uint256 price, uint256 remaining) external returns (uint32 orderId, uint256 required);

    function setLmp(uint256 lmp) external;

    function mktPrice() external view returns (uint256);

    function assetValue(uint256 amount, bool isBid) external view returns (uint256 converted);

    function isEmpty(bool isBid, uint256 price) external view returns (bool);

    function getRequired(bool isBid, uint256 price, uint32 orderId) external view returns (uint256 required);

    function convert(uint256 price, uint256 amount, bool isBid) external view returns (uint256 converted);

    function placeAsk(address owner, uint256 price, uint256 amount) external returns (uint32 orderId);

    function placeBid(address owner, uint256 price, uint256 amount) external returns (uint32 orderId);

    function cancelOrder(bool isBid, uint256 price, uint32 orderId, address owner)
        external
        returns (uint256 remaining);

    function execute(uint32 orderId, bool isBid, uint256 price, address sender, uint256 amount)
        external
        returns (address owner);

    function heads() external view returns (uint256 bidHead, uint256 askHead);

    function askHead() external view returns (uint256);

    function bidHead() external view returns (uint256);

    function getPrices(bool isBid, uint32 n) external view returns (uint256[] memory);

    function getOrders(bool isBid, uint256 price, uint32 n) external view returns (ExchangeOrderbook.Order[] memory);

    function getOrder(bool isBid, uint32 orderId) external view returns (ExchangeOrderbook.Order memory);

    function getOrderIds(bool isBid, uint256 price, uint32 n) external view returns (uint32[] memory);

    function getBaseQuote() external view returns(address base, address quote);
}

// File: contracts/security/Initializable.sol



// SPDX-License-Identifier: BUSL-1.1

pragma solidity ^0.8.17;

contract Initializable {
    bool private _initialized = false;

    modifier initializer() {
        // solhint-disable-next-line reason-string
        require(!_initialized);
        _;
        _initialized = true;
    }

    function initialized() external view returns (bool) {
        return _initialized;
    }
}

// File: contracts/safex/libraries/TransferHelper.sol



// SPDX-License-Identifier: BUSL-1.1

pragma solidity ^0.8.17;

// helper methods for interacting with ERC20 tokens and sending ETH that do not consistently return true/false
library TransferHelper {
    function safeApprove(address token, address to, uint256 value) internal {
        // bytes4(keccak256(bytes("approve(address,uint256)")));
        (bool success, bytes memory data) = token.call(abi.encodeWithSelector(0x095ea7b3, to, value));
        require(success && (data.length == 0 || abi.decode(data, (bool))), "AF");
    }

    function safeTransfer(address token, address to, uint256 value) internal {
        // bytes4(keccak256(bytes("transfer(address,uint256)")));
        (bool success, bytes memory data) = token.call(abi.encodeWithSelector(0xa9059cbb, to, value));
        require(success && (data.length == 0 || abi.decode(data, (bool))), "TF");
    }

    function safeTransferFrom(address token, address from, address to, uint256 value) internal {
        // bytes4(keccak256(bytes("transferFrom(address,address,uint256)")));
        (bool success, bytes memory data) = token.call(abi.encodeWithSelector(0x23b872dd, from, to, value));
        require(success && (data.length == 0 || abi.decode(data, (bool))), "TFF");
    }

    function safeTransferETH(address to, uint256 value) internal {
        (bool success,) = to.call{value: value}(new bytes(0));
        require(success, "ETF");
    }

    function decimals(address token) internal view returns (uint8) {
        // bytes4(keccak256(bytes("decimals()")));
        (bool success, bytes memory data) = token.staticcall(abi.encodeWithSelector(0x313ce567));
        require(success, "DF");
        return abi.decode(data, (uint8));
    }
}

// File: contracts/safex/libraries/ExchangeLinkedList.sol



// SPDX-License-Identifier: BUSL-1.1

pragma solidity ^0.8.17;

library ExchangeLinkedList {
    error NoMatchPrice(uint256 askHead, uint256 bidHead, uint256 lmp);

    struct PriceLinkedList {
        /// Hashmap-style linked list of prices to route orders
        // key: price, value: next_price (next_price > price)
        mapping(uint256 => uint256) askPrices;
        // key: price, value: next_price (next_price < price)
        mapping(uint256 => uint256) bidPrices;
        // Head of the bid price linked list(i.e. highest bid price)
        uint256 askHead;
        // Head of the ask price linked list(i.e. lowest ask price)
        uint256 bidHead;
        // Last matched price
        uint256 lmp;
    }

    error ZeroPrice(uint256 price);
    error NoHeadBelow(bool isBid, uint256 head);
    error PriceOutOfRange(uint256 price, uint256 np);
    error PriceNoneInRange(uint256 price, uint256 np);

    function _setLmp(PriceLinkedList storage self, uint256 lmp_) internal {
        self.lmp = lmp_;
    }

    function _heads(
        PriceLinkedList storage self
    ) internal view returns (uint256, uint256) {
        return (self.bidHead, self.askHead);
    }

    function _askHead(
        PriceLinkedList storage self
    ) internal view returns (uint256) {
        return self.askHead;
    }

    function _bidHead(
        PriceLinkedList storage self
    ) internal view returns (uint256) {
        return self.bidHead;
    }

    function _mktPrice(
        PriceLinkedList storage self
    ) internal view returns (uint256) {
        if (self.lmp == 0) {
            if (self.bidHead == 0 && self.askHead == 0) {
                revert NoMatchPrice(self.bidHead, self.askHead, self.lmp);
            } else if (self.bidHead != 0 && self.askHead != 0) {
                return (self.bidHead + self.askHead) / 2;
            } else {
                return self.askHead == 0 ? self.bidHead : self.askHead;
            }
        } else {
            if (self.lmp < self.bidHead) {
                return self.bidHead;
            } else if (self.lmp > self.askHead && self.askHead != 0) {
                return self.askHead;
            } else {
                return self.lmp;
            }
        }
    }

    function _next(
        PriceLinkedList storage self,
        bool isBid,
        uint256 price
    ) internal view returns (uint256) {
        if (isBid) {
            return self.bidPrices[price];
        } else {
            return self.askPrices[price];
        }
    }

    // for bidPrices, lower ones are next, for askPrices, higher ones are next
    function _insert(
        PriceLinkedList storage self,
        bool isBid,
        uint256 price
    ) internal {
        if (isBid) {
            uint256 last = 0;
            uint256 head = self.bidHead;
            // insert bid price to the linked list
            // if the list is empty
            if (head == 0 || price > head) {
                self.bidHead = price;
                self.bidPrices[price] = head;
                return;
            }
            while (head != 0) {
                uint256 next = self.bidPrices[head];
                if (price < next) {
                    // Keep traversing
                    head = self.bidPrices[head];
                    last = next;
                } else if (price > next) {
                    if (next == 0) {
                        // Insert price at the end of the list
                        self.bidPrices[head] = price;
                        self.bidPrices[price] = 0;
                        return;
                    }
                    // Insert price in the middle of the list
                    self.bidPrices[head] = price;
                    self.bidPrices[price] = next;
                    return;
                } else {
                    // price is already included in the queue as it is equal to next
                    // End traversal as there is no need to traverse further
                    return;
                }
            }
        }
        // insert ask price to the linked list
        else {
            uint256 last = 0;
            uint256 head = self.askHead;
            // insert order to the linked list
            // if the list is empty and price is the lowest ask
            if (head == 0 || price < head) {
                self.askHead = price;
                self.askPrices[price] = head;
                return;
            }
            // traverse the list
            while (head != 0) {
                uint256 next = self.askPrices[head];
                // Keep traversing
                if (price > next) {
                    if (next == 0) {
                        // Insert price in the middle of the list
                        self.askPrices[head] = price;
                        self.askPrices[price] = 0;
                        return;
                    }
                    head = self.askPrices[head];
                    last = next;
                } else if (price < next) {
                    // Insert price in the middle of the list
                    self.askPrices[head] = price;
                    self.askPrices[price] = next;
                    return;
                } else {
                    // price is already included in the queue as it is equal to next
                    // End traversal as there is no need to traverse further
                    return;
                }
            }
        }
    }

    function _delete(
        PriceLinkedList storage self,
        bool isBid,
        uint256 price
    ) internal returns (bool) {
        // traverse the list
        if (price == 0) {
            revert ZeroPrice(price);
            //return false;
        }

        if (isBid) {
            uint256 last = 0;
            uint256 head = self.bidHead;
            // insert bid price to the linked list
            // if the list is empty
            if (head == 0 || price > head) {
                revert NoHeadBelow(isBid, head);
            }
            while (head != 0 && price > head) {
                uint256 next = self.bidPrices[head];
                if (price < next) {
                    // Keep traversing
                    head = self.bidPrices[head];
                    last = next;
                } else if (price > next) {
                    if (next == 0) {
                        // if there is only one price left, check if it is the price we are looking for
                        if(head == price) {
                            // remove price at the end
                            self.bidPrices[last] = 0;
                            delete self.bidPrices[head];
                            return true;
                        }
                        // Price does not exist in price list
                        revert PriceOutOfRange(head, price);
                    }
                    // Price does not exist within range of prices
                    revert PriceNoneInRange(head, price);
                } else {
                    // price is already included in the queue as it is equal to next. price exists in the orderbook
                    // End traversal as there is no need to traverse further
                    // remove price in next, connect next next to the head
                    self.bidPrices[head] = self.bidPrices[next];
                    delete self.bidPrices[next];
                    return true;
                }
            }
        }
        // insert ask price to the linked list
        else {
            uint256 last = 0;
            uint256 head = self.askHead;
            // insert order to the linked list
            // if the list is empty and price is the lowest ask
            if (head == 0 || price < head) {
                revert NoHeadBelow(isBid, head);
            }
            // traverse the list
            while (head != 0) {
                uint256 next = self.askPrices[head];
                // Keep traversing
                if (price > next) {
                    if (next == 0) {
                        // if there is only one price left, check if it is the price we are looking for
                        if(head == price) {
                             self.askPrices[last] = 0;
                            delete self.askPrices[head];
                            return true;
                        }
                        // Price does not exist in price list                       
                        revert PriceOutOfRange(head, price);
                    }
                    head = self.askPrices[head];
                    last = next;
                } else if (price < next) {
                    // Price does not exist within range of prices
                    revert PriceNoneInRange(head, price);
                } else {
                    // price is already included in the queue as it is equal to next
                    // End traversal as there is no need to traverse further
                    self.askPrices[head] = self.askPrices[next];
                    delete self.askPrices[next];
                    return true;
                }
            }
        }

        return true;
    }

    // show n prices shown in the orderbook
    function _getPrices(
        PriceLinkedList storage self,
        bool isBid,
        uint256 n
    ) internal view returns (uint256[] memory) {
        uint256 i = 0;
        uint256[] memory prices = new uint256[](n);
        for (
            uint256 price = isBid ? self.bidHead : self.askHead;
            price != 0 && i < n;
            price = isBid ? self.bidPrices[price] : self.askPrices[price]
        ) {
            prices[i] = price;
            i++;
        }
        return prices;
    }

    function _checkPriceExists(
        PriceLinkedList storage self,
        bool isBid,
        uint256 price
    ) internal view returns (bool) {
        // traverse the list
        if (price == 0) {
            revert ZeroPrice(price);
            //return false;
        }

        if (isBid) {
            uint256 last = 0;
            uint256 head = self.bidHead;
            // insert bid price to the linked list
            // if the list is empty
            if (head == 0 || price > head) {
                revert NoHeadBelow(isBid, head);
            }
            while (head != 0 && price > head) {
                uint256 next = self.bidPrices[head];
                if (price < next) {
                    // Keep traversing
                    head = self.bidPrices[head];
                    last = next;
                } else if (price > next) {
                    if (next == 0) {
                        // if there is only one price left, check if it is the price we are looking for
                        if(head == price) {
                            return true;
                        }
                        // Price does not exist in price list
                        revert PriceOutOfRange(head, price);
                    }
                    // Price does not exist within range of prices
                    revert PriceNoneInRange(head, price);
                } else {
                    // price is already included in the queue as it is equal to next. price exists in the orderbook
                    // End traversal as there is no need to traverse further
                    return true;
                }
            }
        }
        // insert ask price to the linked list
        else {
            uint256 last = 0;
            uint256 head = self.askHead;
            // insert order to the linked list
            // if the list is empty and price is the lowest ask
            if (head == 0 || price < head) {
                revert NoHeadBelow(isBid, head);
            }
            // traverse the list
            while (head != 0) {
                uint256 next = self.askPrices[head];
                // Keep traversing
                if (price > next) {
                    if (next == 0) {
                        // if there is only one price left, check if it is the price we are looking for
                        if(head == price) {
                            return true;
                        }
                        // Price does not exist in price list                       
                        revert PriceOutOfRange(head, price);
                    }
                    head = self.askPrices[head];
                    last = next;
                } else if (price < next) {
                    // Price does not exist within range of prices
                    revert PriceNoneInRange(head, price);
                } else {
                    // price is already included in the queue as it is equal to next
                    // End traversal as there is no need to traverse further
                    return true;
                }
            }
        }

        return true;
    }
}

// File: contracts/safex/libraries/ExchangeOrderbook.sol



// SPDX-License-Identifier: BUSL-1.1

pragma solidity ^0.8.17;

library ExchangeOrderbook {
  // Order struct
  struct Order {
    address owner;
    uint256 depositAmount;
  }

  // Order Linked List
  struct OrderStorage {
    /// Hashmap-style linked list of prices to route orders
    // key: price, value: order indices linked hashmap
    mapping(uint256 => mapping(uint32 => uint32)) list;
    mapping(uint32 => Order) orders;
    mapping(uint32 => bool) canceled;
    // Head of the linked list(i.e. lowest ask price / highest bid price)
    mapping(uint256 => uint32) head;
    // count of the orders, used for array allocation
    uint32 count;
    address engine;
  }

  // for orders, lower depositAmount are next, higher depositAmount comes first
  function _insertId(
    OrderStorage storage self,
    uint256 price,
    uint32 id,
    uint256 amount
  ) internal {
    uint32 last = 0;
    uint32 head = self.head[price];
    mapping(uint32 => uint32) storage list = self.list[price];
    mapping(uint32 => Order) storage orders = self.orders;
    // insert order to the linked list
    // if the list is empty
    if (head == 0 || amount > self.orders[head].depositAmount) {
      self.head[price] = id;
      list[id] = head;
      return;
    }
    // Traverse through list until we find the right spot where id's deposit amount is higher than next
    while (head != 0) {
      // what if order deposit amount is bigger than the next order's deposit amount?
      uint32 next = list[head];
      if (amount < orders[next].depositAmount) {
        // Keep traversing
        head = list[head];
        last = next;
      } else if (amount > orders[next].depositAmount) {
        // This is either order is cancelled or order is at the end of the list
        if (orders[next].depositAmount == 0) {
          // what if next order is canceled and order id still stays in the list?
          // if order is canceled and stays in the list, there is at least a next order in the list
          if (self.canceled[next]) {
            // remove index of cancelled order
            list[head] = list[next];
            delete list[next];
            delete self.canceled[next];
            // skip canceled order
            last = head;
            head = list[head];
          } else {
            // Insert order at the end of the list
            list[head] = id;
            list[id] = 0;
            return;
          }
        }
        // Insert order in the middle of the list
        list[head] = id;
        list[id] = next;
        return;
      }
      // what if there is same order with same deposit amount?
      else if (amount == orders[next].depositAmount) {
        list[id] = list[next];
        list[next] = id;
        return;
      }
    }
  }

  // pop front
  function _fpop(
    OrderStorage storage self,
    uint256 price
  ) internal returns (uint256) {
    uint32 first = self.head[price];
    if (first == 0) {
      return 0;
    }
    uint32 next = self.list[price][first];
    self.head[price] = next;
    delete self.list[price][first];
    return first;
  }

  function _createOrder(
    OrderStorage storage self,
    address owner,
    uint256 depositAmount
  ) internal returns (uint32 id) {
    Order memory order = Order({ owner: owner, depositAmount: depositAmount });
    // prevent order overflow, order id must start from 1
    self.count = self.count == 0 || self.count == type(uint32).max
      ? 1
      : self.count + 1;
    self.orders[self.count] = order;
    return self.count;
  }

  function _decreaseOrder(
    OrderStorage storage self,
    uint256 price,
    uint32 id,
    uint256 amount,
    uint256 dust
  ) internal returns (uint256) {
    uint256 decreased = self.orders[id].depositAmount - amount;
    // remove dust
    if (decreased <= dust) {
      decreased = self.orders[id].depositAmount;
      _deleteOrder(self, price, id);
      return decreased;
    } else {
      self.orders[id].depositAmount = decreased;
      return amount;
    }
  }

  function _deleteOrder(
    OrderStorage storage self,
    uint256 price,
    uint32 id
  ) internal {
    uint32 last = 0;
    uint32 head = self.head[price];
    uint32 next;
    uint16 i;
    mapping(uint32 => uint32) storage list = self.list[price];
    // delete id in the order linked list
    if (head == id) {
      self.head[price] = list[head];
      delete list[id];
    } else {
      // search for the order id in the linked list
      while (head != 0 && i < 30) {
        next = list[head];
        if (next == id) {
          list[head] = list[next];
          delete list[id];
          break;
        }
        last = head;
        head = next;
        ++i;
      }
    }
    // delete order
    delete self.orders[id];
    // add canceled info to see if the order was deleted in the list
    if (i == 30) {
      self.canceled[id] = true;
    }
    return;
  }

  // show n order ids at the price in the orderbook
  function _getOrderIds(
    OrderStorage storage self,
    uint256 price,
    uint32 n
  ) internal view returns (uint32[] memory) {
    uint32 head = self.head[price];
    uint32[] memory orders = new uint32[](n);
    uint32 i = 0;
    while (head != 0 && i < n) {
      orders[i] = head;
      head = self.list[price][head];
      i++;
    }
    return orders;
  }

  function _getOrders(
    OrderStorage storage self,
    uint256 price,
    uint32 n
  ) internal view returns (Order[] memory) {
    uint32 head = self.head[price];
    Order[] memory orders = new Order[](n);
    uint32 i = 0;
    while (head != 0 && i < n) {
      orders[i] = self.orders[head];
      head = self.list[price][head];
      i++;
    }
    return orders;
  }

  function _head(
    OrderStorage storage self,
    uint256 price
  ) internal view returns (uint32) {
    return self.head[price];
  }

  function _isEmpty(
    OrderStorage storage self,
    uint256 price
  ) internal view returns (bool) {
    return self.head[price] == 0;
  }

  function _next(
    OrderStorage storage self,
    uint256 price,
    uint32 curr
  ) internal view returns (uint32) {
    return self.list[price][curr];
  }

  function _getOrder(
    OrderStorage storage self,
    uint32 id
  ) internal view returns (Order memory) {
    return self.orders[id];
  }
}

// File: node_modules/@openzeppelin/contracts-upgradeable/utils/AddressUpgradeable.sol



// SPDX-License-Identifier: MIT
// OpenZeppelin Contracts (last updated v4.9.0) (utils/Address.sol)

pragma solidity ^0.8.1;

/**
 * @dev Collection of functions related to the address type
 */
library AddressUpgradeable {
    /**
     * @dev Returns true if `account` is a contract.
     *
     * [IMPORTANT]
     * ====
     * It is unsafe to assume that an address for which this function returns
     * false is an externally-owned account (EOA) and not a contract.
     *
     * Among others, `isContract` will return false for the following
     * types of addresses:
     *
     *  - an externally-owned account
     *  - a contract in construction
     *  - an address where a contract will be created
     *  - an address where a contract lived, but was destroyed
     *
     * Furthermore, `isContract` will also return true if the target contract within
     * the same transaction is already scheduled for destruction by `SELFDESTRUCT`,
     * which only has an effect at the end of a transaction.
     * ====
     *
     * [IMPORTANT]
     * ====
     * You shouldn't rely on `isContract` to protect against flash loan attacks!
     *
     * Preventing calls from contracts is highly discouraged. It breaks composability, breaks support for smart wallets
     * like Gnosis Safe, and does not provide security since it can be circumvented by calling from a contract
     * constructor.
     * ====
     */
    function isContract(address account) internal view returns (bool) {
        // This method relies on extcodesize/address.code.length, which returns 0
        // for contracts in construction, since the code is only stored at the end
        // of the constructor execution.

        return account.code.length > 0;
    }

    /**
     * @dev Replacement for Solidity's `transfer`: sends `amount` wei to
     * `recipient`, forwarding all available gas and reverting on errors.
     *
     * https://eips.ethereum.org/EIPS/eip-1884[EIP1884] increases the gas cost
     * of certain opcodes, possibly making contracts go over the 2300 gas limit
     * imposed by `transfer`, making them unable to receive funds via
     * `transfer`. {sendValue} removes this limitation.
     *
     * https://consensys.net/diligence/blog/2019/09/stop-using-soliditys-transfer-now/[Learn more].
     *
     * IMPORTANT: because control is transferred to `recipient`, care must be
     * taken to not create reentrancy vulnerabilities. Consider using
     * {ReentrancyGuard} or the
     * https://solidity.readthedocs.io/en/v0.8.0/security-considerations.html#use-the-checks-effects-interactions-pattern[checks-effects-interactions pattern].
     */
    function sendValue(address payable recipient, uint256 amount) internal {
        require(address(this).balance >= amount, "Address: insufficient balance");

        (bool success, ) = recipient.call{value: amount}("");
        require(success, "Address: unable to send value, recipient may have reverted");
    }

    /**
     * @dev Performs a Solidity function call using a low level `call`. A
     * plain `call` is an unsafe replacement for a function call: use this
     * function instead.
     *
     * If `target` reverts with a revert reason, it is bubbled up by this
     * function (like regular Solidity function calls).
     *
     * Returns the raw returned data. To convert to the expected return value,
     * use https://solidity.readthedocs.io/en/latest/units-and-global-variables.html?highlight=abi.decode#abi-encoding-and-decoding-functions[`abi.decode`].
     *
     * Requirements:
     *
     * - `target` must be a contract.
     * - calling `target` with `data` must not revert.
     *
     * _Available since v3.1._
     */
    function functionCall(address target, bytes memory data) internal returns (bytes memory) {
        return functionCallWithValue(target, data, 0, "Address: low-level call failed");
    }

    /**
     * @dev Same as {xref-Address-functionCall-address-bytes-}[`functionCall`], but with
     * `errorMessage` as a fallback revert reason when `target` reverts.
     *
     * _Available since v3.1._
     */
    function functionCall(
        address target,
        bytes memory data,
        string memory errorMessage
    ) internal returns (bytes memory) {
        return functionCallWithValue(target, data, 0, errorMessage);
    }

    /**
     * @dev Same as {xref-Address-functionCall-address-bytes-}[`functionCall`],
     * but also transferring `value` wei to `target`.
     *
     * Requirements:
     *
     * - the calling contract must have an ETH balance of at least `value`.
     * - the called Solidity function must be `payable`.
     *
     * _Available since v3.1._
     */
    function functionCallWithValue(address target, bytes memory data, uint256 value) internal returns (bytes memory) {
        return functionCallWithValue(target, data, value, "Address: low-level call with value failed");
    }

    /**
     * @dev Same as {xref-Address-functionCallWithValue-address-bytes-uint256-}[`functionCallWithValue`], but
     * with `errorMessage` as a fallback revert reason when `target` reverts.
     *
     * _Available since v3.1._
     */
    function functionCallWithValue(
        address target,
        bytes memory data,
        uint256 value,
        string memory errorMessage
    ) internal returns (bytes memory) {
        require(address(this).balance >= value, "Address: insufficient balance for call");
        (bool success, bytes memory returndata) = target.call{value: value}(data);
        return verifyCallResultFromTarget(target, success, returndata, errorMessage);
    }

    /**
     * @dev Same as {xref-Address-functionCall-address-bytes-}[`functionCall`],
     * but performing a static call.
     *
     * _Available since v3.3._
     */
    function functionStaticCall(address target, bytes memory data) internal view returns (bytes memory) {
        return functionStaticCall(target, data, "Address: low-level static call failed");
    }

    /**
     * @dev Same as {xref-Address-functionCall-address-bytes-string-}[`functionCall`],
     * but performing a static call.
     *
     * _Available since v3.3._
     */
    function functionStaticCall(
        address target,
        bytes memory data,
        string memory errorMessage
    ) internal view returns (bytes memory) {
        (bool success, bytes memory returndata) = target.staticcall(data);
        return verifyCallResultFromTarget(target, success, returndata, errorMessage);
    }

    /**
     * @dev Same as {xref-Address-functionCall-address-bytes-}[`functionCall`],
     * but performing a delegate call.
     *
     * _Available since v3.4._
     */
    function functionDelegateCall(address target, bytes memory data) internal returns (bytes memory) {
        return functionDelegateCall(target, data, "Address: low-level delegate call failed");
    }

    /**
     * @dev Same as {xref-Address-functionCall-address-bytes-string-}[`functionCall`],
     * but performing a delegate call.
     *
     * _Available since v3.4._
     */
    function functionDelegateCall(
        address target,
        bytes memory data,
        string memory errorMessage
    ) internal returns (bytes memory) {
        (bool success, bytes memory returndata) = target.delegatecall(data);
        return verifyCallResultFromTarget(target, success, returndata, errorMessage);
    }

    /**
     * @dev Tool to verify that a low level call to smart-contract was successful, and revert (either by bubbling
     * the revert reason or using the provided one) in case of unsuccessful call or if target was not a contract.
     *
     * _Available since v4.8._
     */
    function verifyCallResultFromTarget(
        address target,
        bool success,
        bytes memory returndata,
        string memory errorMessage
    ) internal view returns (bytes memory) {
        if (success) {
            if (returndata.length == 0) {
                // only check isContract if the call was successful and the return data is empty
                // otherwise we already know that it was a contract
                require(isContract(target), "Address: call to non-contract");
            }
            return returndata;
        } else {
            _revert(returndata, errorMessage);
        }
    }

    /**
     * @dev Tool to verify that a low level call was successful, and revert if it wasn't, either by bubbling the
     * revert reason or using the provided one.
     *
     * _Available since v4.3._
     */
    function verifyCallResult(
        bool success,
        bytes memory returndata,
        string memory errorMessage
    ) internal pure returns (bytes memory) {
        if (success) {
            return returndata;
        } else {
            _revert(returndata, errorMessage);
        }
    }

    function _revert(bytes memory returndata, string memory errorMessage) private pure {
        // Look for revert reason and bubble it up if present
        if (returndata.length > 0) {
            // The easiest way to bubble the revert reason is using memory via assembly
            /// @solidity memory-safe-assembly
            assembly {
                let returndata_size := mload(returndata)
                revert(add(32, returndata), returndata_size)
            }
        } else {
            revert(errorMessage);
        }
    }
}

// File: node_modules/@openzeppelin/contracts/utils/math/Math.sol



// SPDX-License-Identifier: MIT
// OpenZeppelin Contracts (last updated v4.9.0) (utils/math/Math.sol)

pragma solidity ^0.8.0;

/**
 * @dev Standard math utilities missing in the Solidity language.
 */
library Math {
    enum Rounding {
        Down, // Toward negative infinity
        Up, // Toward infinity
        Zero // Toward zero
    }

    /**
     * @dev Returns the largest of two numbers.
     */
    function max(uint256 a, uint256 b) internal pure returns (uint256) {
        return a > b ? a : b;
    }

    /**
     * @dev Returns the smallest of two numbers.
     */
    function min(uint256 a, uint256 b) internal pure returns (uint256) {
        return a < b ? a : b;
    }

    /**
     * @dev Returns the average of two numbers. The result is rounded towards
     * zero.
     */
    function average(uint256 a, uint256 b) internal pure returns (uint256) {
        // (a + b) / 2 can overflow.
        return (a & b) + (a ^ b) / 2;
    }

    /**
     * @dev Returns the ceiling of the division of two numbers.
     *
     * This differs from standard division with `/` in that it rounds up instead
     * of rounding down.
     */
    function ceilDiv(uint256 a, uint256 b) internal pure returns (uint256) {
        // (a + b - 1) / b can overflow on addition, so we distribute.
        return a == 0 ? 0 : (a - 1) / b + 1;
    }

    /**
     * @notice Calculates floor(x * y / denominator) with full precision. Throws if result overflows a uint256 or denominator == 0
     * @dev Original credit to Remco Bloemen under MIT license (https://xn--2-umb.com/21/muldiv)
     * with further edits by Uniswap Labs also under MIT license.
     */
    function mulDiv(uint256 x, uint256 y, uint256 denominator) internal pure returns (uint256 result) {
        unchecked {
            // 512-bit multiply [prod1 prod0] = x * y. Compute the product mod 2^256 and mod 2^256 - 1, then use
            // use the Chinese Remainder Theorem to reconstruct the 512 bit result. The result is stored in two 256
            // variables such that product = prod1 * 2^256 + prod0.
            uint256 prod0; // Least significant 256 bits of the product
            uint256 prod1; // Most significant 256 bits of the product
            assembly {
                let mm := mulmod(x, y, not(0))
                prod0 := mul(x, y)
                prod1 := sub(sub(mm, prod0), lt(mm, prod0))
            }

            // Handle non-overflow cases, 256 by 256 division.
            if (prod1 == 0) {
                // Solidity will revert if denominator == 0, unlike the div opcode on its own.
                // The surrounding unchecked block does not change this fact.
                // See https://docs.soliditylang.org/en/latest/control-structures.html#checked-or-unchecked-arithmetic.
                return prod0 / denominator;
            }

            // Make sure the result is less than 2^256. Also prevents denominator == 0.
            require(denominator > prod1, "Math: mulDiv overflow");

            ///////////////////////////////////////////////
            // 512 by 256 division.
            ///////////////////////////////////////////////

            // Make division exact by subtracting the remainder from [prod1 prod0].
            uint256 remainder;
            assembly {
                // Compute remainder using mulmod.
                remainder := mulmod(x, y, denominator)

                // Subtract 256 bit number from 512 bit number.
                prod1 := sub(prod1, gt(remainder, prod0))
                prod0 := sub(prod0, remainder)
            }

            // Factor powers of two out of denominator and compute largest power of two divisor of denominator. Always >= 1.
            // See https://cs.stackexchange.com/q/138556/92363.

            // Does not overflow because the denominator cannot be zero at this stage in the function.
            uint256 twos = denominator & (~denominator + 1);
            assembly {
                // Divide denominator by twos.
                denominator := div(denominator, twos)

                // Divide [prod1 prod0] by twos.
                prod0 := div(prod0, twos)

                // Flip twos such that it is 2^256 / twos. If twos is zero, then it becomes one.
                twos := add(div(sub(0, twos), twos), 1)
            }

            // Shift in bits from prod1 into prod0.
            prod0 |= prod1 * twos;

            // Invert denominator mod 2^256. Now that denominator is an odd number, it has an inverse modulo 2^256 such
            // that denominator * inv = 1 mod 2^256. Compute the inverse by starting with a seed that is correct for
            // four bits. That is, denominator * inv = 1 mod 2^4.
            uint256 inverse = (3 * denominator) ^ 2;

            // Use the Newton-Raphson iteration to improve the precision. Thanks to Hensel's lifting lemma, this also works
            // in modular arithmetic, doubling the correct bits in each step.
            inverse *= 2 - denominator * inverse; // inverse mod 2^8
            inverse *= 2 - denominator * inverse; // inverse mod 2^16
            inverse *= 2 - denominator * inverse; // inverse mod 2^32
            inverse *= 2 - denominator * inverse; // inverse mod 2^64
            inverse *= 2 - denominator * inverse; // inverse mod 2^128
            inverse *= 2 - denominator * inverse; // inverse mod 2^256

            // Because the division is now exact we can divide by multiplying with the modular inverse of denominator.
            // This will give us the correct result modulo 2^256. Since the preconditions guarantee that the outcome is
            // less than 2^256, this is the final result. We don't need to compute the high bits of the result and prod1
            // is no longer required.
            result = prod0 * inverse;
            return result;
        }
    }

    /**
     * @notice Calculates x * y / denominator with full precision, following the selected rounding direction.
     */
    function mulDiv(uint256 x, uint256 y, uint256 denominator, Rounding rounding) internal pure returns (uint256) {
        uint256 result = mulDiv(x, y, denominator);
        if (rounding == Rounding.Up && mulmod(x, y, denominator) > 0) {
            result += 1;
        }
        return result;
    }

    /**
     * @dev Returns the square root of a number. If the number is not a perfect square, the value is rounded down.
     *
     * Inspired by Henry S. Warren, Jr.'s "Hacker's Delight" (Chapter 11).
     */
    function sqrt(uint256 a) internal pure returns (uint256) {
        if (a == 0) {
            return 0;
        }

        // For our first guess, we get the biggest power of 2 which is smaller than the square root of the target.
        //
        // We know that the "msb" (most significant bit) of our target number `a` is a power of 2 such that we have
        // `msb(a) <= a < 2*msb(a)`. This value can be written `msb(a)=2**k` with `k=log2(a)`.
        //
        // This can be rewritten `2**log2(a) <= a < 2**(log2(a) + 1)`
        // → `sqrt(2**k) <= sqrt(a) < sqrt(2**(k+1))`
        // → `2**(k/2) <= sqrt(a) < 2**((k+1)/2) <= 2**(k/2 + 1)`
        //
        // Consequently, `2**(log2(a) / 2)` is a good first approximation of `sqrt(a)` with at least 1 correct bit.
        uint256 result = 1 << (log2(a) >> 1);

        // At this point `result` is an estimation with one bit of precision. We know the true value is a uint128,
        // since it is the square root of a uint256. Newton's method converges quadratically (precision doubles at
        // every iteration). We thus need at most 7 iteration to turn our partial result with one bit of precision
        // into the expected uint128 result.
        unchecked {
            result = (result + a / result) >> 1;
            result = (result + a / result) >> 1;
            result = (result + a / result) >> 1;
            result = (result + a / result) >> 1;
            result = (result + a / result) >> 1;
            result = (result + a / result) >> 1;
            result = (result + a / result) >> 1;
            return min(result, a / result);
        }
    }

    /**
     * @notice Calculates sqrt(a), following the selected rounding direction.
     */
    function sqrt(uint256 a, Rounding rounding) internal pure returns (uint256) {
        unchecked {
            uint256 result = sqrt(a);
            return result + (rounding == Rounding.Up && result * result < a ? 1 : 0);
        }
    }

    /**
     * @dev Return the log in base 2, rounded down, of a positive value.
     * Returns 0 if given 0.
     */
    function log2(uint256 value) internal pure returns (uint256) {
        uint256 result = 0;
        unchecked {
            if (value >> 128 > 0) {
                value >>= 128;
                result += 128;
            }
            if (value >> 64 > 0) {
                value >>= 64;
                result += 64;
            }
            if (value >> 32 > 0) {
                value >>= 32;
                result += 32;
            }
            if (value >> 16 > 0) {
                value >>= 16;
                result += 16;
            }
            if (value >> 8 > 0) {
                value >>= 8;
                result += 8;
            }
            if (value >> 4 > 0) {
                value >>= 4;
                result += 4;
            }
            if (value >> 2 > 0) {
                value >>= 2;
                result += 2;
            }
            if (value >> 1 > 0) {
                result += 1;
            }
        }
        return result;
    }

    /**
     * @dev Return the log in base 2, following the selected rounding direction, of a positive value.
     * Returns 0 if given 0.
     */
    function log2(uint256 value, Rounding rounding) internal pure returns (uint256) {
        unchecked {
            uint256 result = log2(value);
            return result + (rounding == Rounding.Up && 1 << result < value ? 1 : 0);
        }
    }

    /**
     * @dev Return the log in base 10, rounded down, of a positive value.
     * Returns 0 if given 0.
     */
    function log10(uint256 value) internal pure returns (uint256) {
        uint256 result = 0;
        unchecked {
            if (value >= 10 ** 64) {
                value /= 10 ** 64;
                result += 64;
            }
            if (value >= 10 ** 32) {
                value /= 10 ** 32;
                result += 32;
            }
            if (value >= 10 ** 16) {
                value /= 10 ** 16;
                result += 16;
            }
            if (value >= 10 ** 8) {
                value /= 10 ** 8;
                result += 8;
            }
            if (value >= 10 ** 4) {
                value /= 10 ** 4;
                result += 4;
            }
            if (value >= 10 ** 2) {
                value /= 10 ** 2;
                result += 2;
            }
            if (value >= 10 ** 1) {
                result += 1;
            }
        }
        return result;
    }

    /**
     * @dev Return the log in base 10, following the selected rounding direction, of a positive value.
     * Returns 0 if given 0.
     */
    function log10(uint256 value, Rounding rounding) internal pure returns (uint256) {
        unchecked {
            uint256 result = log10(value);
            return result + (rounding == Rounding.Up && 10 ** result < value ? 1 : 0);
        }
    }

    /**
     * @dev Return the log in base 256, rounded down, of a positive value.
     * Returns 0 if given 0.
     *
     * Adding one to the result gives the number of pairs of hex symbols needed to represent `value` as a hex string.
     */
    function log256(uint256 value) internal pure returns (uint256) {
        uint256 result = 0;
        unchecked {
            if (value >> 128 > 0) {
                value >>= 128;
                result += 16;
            }
            if (value >> 64 > 0) {
                value >>= 64;
                result += 8;
            }
            if (value >> 32 > 0) {
                value >>= 32;
                result += 4;
            }
            if (value >> 16 > 0) {
                value >>= 16;
                result += 2;
            }
            if (value >> 8 > 0) {
                result += 1;
            }
        }
        return result;
    }

    /**
     * @dev Return the log in base 256, following the selected rounding direction, of a positive value.
     * Returns 0 if given 0.
     */
    function log256(uint256 value, Rounding rounding) internal pure returns (uint256) {
        unchecked {
            uint256 result = log256(value);
            return result + (rounding == Rounding.Up && 1 << (result << 3) < value ? 1 : 0);
        }
    }
}

// File: node_modules/@openzeppelin/contracts/utils/math/SignedMath.sol



// SPDX-License-Identifier: MIT
// OpenZeppelin Contracts (last updated v4.8.0) (utils/math/SignedMath.sol)

pragma solidity ^0.8.0;

/**
 * @dev Standard signed math utilities missing in the Solidity language.
 */
library SignedMath {
    /**
     * @dev Returns the largest of two signed numbers.
     */
    function max(int256 a, int256 b) internal pure returns (int256) {
        return a > b ? a : b;
    }

    /**
     * @dev Returns the smallest of two signed numbers.
     */
    function min(int256 a, int256 b) internal pure returns (int256) {
        return a < b ? a : b;
    }

    /**
     * @dev Returns the average of two signed numbers without overflow.
     * The result is rounded towards zero.
     */
    function average(int256 a, int256 b) internal pure returns (int256) {
        // Formula from the book "Hacker's Delight"
        int256 x = (a & b) + ((a ^ b) >> 1);
        return x + (int256(uint256(x) >> 255) & (a ^ b));
    }

    /**
     * @dev Returns the absolute unsigned value of a signed value.
     */
    function abs(int256 n) internal pure returns (uint256) {
        unchecked {
            // must be unchecked in order to support `n = type(int256).min`
            return uint256(n >= 0 ? n : -n);
        }
    }
}

// File: node_modules/@openzeppelin/contracts/utils/introspection/IERC165.sol



// SPDX-License-Identifier: MIT
// OpenZeppelin Contracts v4.4.1 (utils/introspection/IERC165.sol)

pragma solidity ^0.8.0;

/**
 * @dev Interface of the ERC165 standard, as defined in the
 * https://eips.ethereum.org/EIPS/eip-165[EIP].
 *
 * Implementers can declare support of contract interfaces, which can then be
 * queried by others ({ERC165Checker}).
 *
 * For an implementation, see {ERC165}.
 */
interface IERC165 {
    /**
     * @dev Returns true if this contract implements the interface defined by
     * `interfaceId`. See the corresponding
     * https://eips.ethereum.org/EIPS/eip-165#how-interfaces-are-identified[EIP section]
     * to learn more about how these ids are created.
     *
     * This function call must use less than 30 000 gas.
     */
    function supportsInterface(bytes4 interfaceId) external view returns (bool);
}