Burn It DAO #20400002

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

pragma solidity ^0.8.20;

/**
 * @dev Collection of functions related to the address type
 */
library Address {
    /**
     * @dev The ETH balance of the account is not enough to perform the operation.
     */
    error AddressInsufficientBalance(address account);

    /**
     * @dev There's no code at `target` (it is not a contract).
     */
    error AddressEmptyCode(address target);

    /**
     * @dev A call to an address target failed. The target may have reverted.
     */
    error FailedInnerCall();

    /**
     * @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.20/security-considerations.html#use-the-checks-effects-interactions-pattern[checks-effects-interactions pattern].
     */
    function sendValue(address payable recipient, uint256 amount) internal {
        if (address(this).balance < amount) {
            revert AddressInsufficientBalance(address(this));
        }

        (bool success, ) = recipient.call{value: amount}("");
        if (!success) {
            revert FailedInnerCall();
        }
    }

    /**
     * @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 or custom error, it is bubbled
     * up by this function (like regular Solidity function calls). However, if
     * the call reverted with no returned reason, this function reverts with a
     * {FailedInnerCall} error.
     *
     * 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.
     */
    function functionCall(address target, bytes memory data) internal returns (bytes memory) {
        return functionCallWithValue(target, data, 0);
    }

    /**
     * @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`.
     */
    function functionCallWithValue(address target, bytes memory data, uint256 value) internal returns (bytes memory) {
        if (address(this).balance < value) {
            revert AddressInsufficientBalance(address(this));
        }
        (bool success, bytes memory returndata) = target.call{value: value}(data);
        return verifyCallResultFromTarget(target, success, returndata);
    }

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

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

    /**
     * @dev Tool to verify that a low level call to smart-contract was successful, and reverts if the target
     * was not a contract or bubbling up the revert reason (falling back to {FailedInnerCall}) in case of an
     * unsuccessful call.
     */
    function verifyCallResultFromTarget(
        address target,
        bool success,
        bytes memory returndata
    ) internal view returns (bytes memory) {
        if (!success) {
            _revert(returndata);
        } else {
            // only check if target is a contract if the call was successful and the return data is empty
            // otherwise we already know that it was a contract
            if (returndata.length == 0 && target.code.length == 0) {
                revert AddressEmptyCode(target);
            }
            return returndata;
        }
    }

    /**
     * @dev Tool to verify that a low level call was successful, and reverts if it wasn't, either by bubbling the
     * revert reason or with a default {FailedInnerCall} error.
     */
    function verifyCallResult(bool success, bytes memory returndata) internal pure returns (bytes memory) {
        if (!success) {
            _revert(returndata);
        } else {
            return returndata;
        }
    }

    /**
     * @dev Reverts with returndata if present. Otherwise reverts with {FailedInnerCall}.
     */
    function _revert(bytes memory returndata) 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 FailedInnerCall();
        }
    }
}

// SPDX-License-Identifier: UNLICENSED

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//                                                                                                                    //
//                                                                        #                                           //
//                                                                      ##                                            //
//                                                                    ###                                             //
//                                                               #######                                              //
//                                                            ####%**##                                               //
//                                                         ####*:---##                                                //
//                                                      ###%*:-----###                                                //
//                                                    ###%-----+---##                                                 //
//                                                  ####----====--=##                                                 //
//                                                ####:---======--*##                                                 //
//                                              ####----+===+===--###                                                 //
//                                             ###=---+===**+===--###                                                 //
//                                            ###:--====+***+===--*##                                                 //
//                                          ###=---===+******===--+##                                                 //
//                                         ##%:--====********===--=##                                                 //
//                                        ###---===+*********+==---###                                                //
//                                       ###---+==+**********+===--+##                                                //
//                                      ###---+==+************===--:%##                                               //
//                                     ###:--===+**************===--=##                                               //
//                                    ##%---===+***************+===--*##                                              //
//                                    ##=--===+*****************===---*##                                             //
//                                   ##*---==+*******************==+---*##                                            //
//                                  ##%:--+==*********************===---=###                                          //
//                         #        ##+--===+**********************====---%##                                         //
//                       ###       ##%---+==************************====---+###                                       //
//                     ####        ##*--===+*************************+===---:*###                                     //
//                   ######        #%=--+==****************************====----+%###                                  //
//                  ##%=###       ##%---==+******************************===+----=####                                //
//                 ###-:%##       ###---==+********************************=====---:#####                             //
//               ###+--:%##       ##*--===+**********************************====+----=%###                           //
//              ###=----###       ##*--===+************************************+=====----%###                         //
//             ###---=--+##       ###--===+***************************************=====---:%###                       //
//            ###---==--:%##      ##*--===+**************#####**********************+====----%##                      //
//            ##=--====---%##    ##%---+==********####################****************+====---+###                    //
//           ##*---====+:--+%######---===+****#####%#+:.       ..-*######***************+====---###                   //
//          ###---+==+====----===:---===+***#####:                    =%####**************====--:###                  //
//          #%=--===+**=====-------====*+*###%:                          +%###************++===---*##                 //
//         ###---==+*****+===========+**###%.                              =%###*************===---*##                //
//         ##=--+==**********+++++*****###-                                  *###*************===---*##               //
//        ###---==+******************###%.                                    :%##*************==+---###              //
//        ##*--===+*****************###%                                       .%##************+==+:--%##             //
//        ##=--===******************##%                                         :%##+***********+===--*##             //
//        ##=--===*****************##%.                                          =###************==+---###            //
//        ##---===*****************##+                                            ###************+===--###            //
//        ##---===****************##%:                                            +##*************===--+##            //
//        ##---===****************###.                                            :###************===--=##            //
//        ##=--===****************###                                             :###************===---##            //
//        ##*--===+***************###.         *%###%.            +%###%-         :###************+==---##            //
//        ###---==+***************##%.       .%#######*         .#########        =###************===---##            //
//         ##---+==***************###-       +########%         -########%:       ###*************===---##            //
//         ##*--===+***************##%.      .%########         .%########.      -###*************===--+##            //
//         ##%---+==***************###*       .#####%=     #-    .*%###%+       .###*************+===--*##            //
//          ##*---==+***************###=                  *#%:                 .###**************===---###            //
//          ##%---===+***************###+                +###%.               .####*************+===--+##             //
//           ##%:--+==****************####.             =%%%%%%.             .%##***************==+---###             //
//            ###:--===*****************###=                                %###***************+==---*##              //
//             ###---===*****************####+                           .#####***************+===--=##               //
//              ###---===+*****************####%.                      =%###*****************+===---%##               //
//               ###:--====******************###:  *%%:   ..:.   *%%.  +##******************====---%##                //
//                ##%----===+****************###:  +##:   +#%.   *#%.  +##*****************====--=###                 //
//                 ###+---====+**************###:  +##:   +#%.   *#%.  +##***************===+---+###                  //
//                   ##%----====+************###=::*##-:::*##-:::*##-::*##*************+===----###                    //
//                    ###%----=====**********#############################***********=====---+###                     //
//                      ###%:--:======================================================+----=%##                       //
//                        ###%=----=++++++++++++++++++++++++++++++++++++++++++++++++=---:*###                         //
//                          #####------------------------------------------------------####                           //
//                             ##########################################################                             //
//                                ####################################################                                //
//                                                                                                                    //
//  :::::::::  :::    ::: :::::::::  ::::    :::      ::::::::::: :::::::::::      :::::::::      :::      ::::::::   //
//  :+:    :+: :+:    :+: :+:    :+: :+:+:   :+:          :+:         :+:          :+:    :+:   :+: :+:   :+:    :+:  //
//  +:+    +:+ +:+    +:+ +:+    +:+ :+:+:+  +:+          +:+         +:+          +:+    +:+  +:+   +:+  +:+    +:+  //
//  +#++:++#+  +#+    +:+ +#++:++#:  +#+ +:+ +#+          +#+         +#+          +#+    +:+ +#++:++#++: +#+    +:+  //
//  +#+    +#+ +#+    +#+ +#+    +#+ +#+  +#+#+#          +#+         +#+          +#+    +#+ +#+     +#+ +#+    +#+  //
//  #+#    #+# #+#    #+# #+#    #+# #+#   #+#+#          #+#         #+#          #+#    #+# #+#     #+# #+#    #+#  //
//  #########   ########  ###    ### ###    ####      ###########     ###          #########  ###     ###  ########   //
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

pragma solidity ^0.8.23;

import {ERC721PsiBurnable, ERC721Psi} from "./ERC721Psi/extension/ERC721PsiBurnable.sol";
import {Ownable} from "@openzeppelin/contracts/access/Ownable.sol";
import {ReentrancyGuard} from "@openzeppelin/contracts/utils/ReentrancyGuard.sol";
import {PullPayment} from "./OpenZeppelin4/PullPayment.sol";
import {LibPRNG} from "solady/src/utils/LibPRNG.sol";
import {LibString} from "solady/src/utils/LibString.sol";
import {LibBitSet, ILibBitSet64Filter} from "./LibBitSet.sol";
import {LibShared} from "./LibShared.sol";
import {LibConfig} from "./LibConfig.sol";
import {LibGame, GameStatus} from "./LibGame.sol";
import {LibWinners} from "./LibWinners.sol";
import {LibRefundable} from "./LibRefundable.sol";
import {TimeLock} from "./TimeLock.sol";
import {LibUser} from "./LibUser.sol";
import "./Constants.sol";

/// @dev VERSION: 1.1.0
contract BurnItDAO is
ERC721PsiBurnable,
PullPayment,
Ownable,
ReentrancyGuard,
TimeLock,
ILibBitSet64Filter
{
    using LibPRNG for LibPRNG.PRNG;
    using LibBitSet for LibBitSet.Set;
    using LibGame for LibGame.Game;
    using LibUser for LibUser.User;
    using LibWinners for LibWinners.Winners;
    using LibRefundable for LibRefundable.MintData;
    using LibShared for uint256;
    using LibConfig for uint256;
    using LibGame for uint256;
    using LibString for uint256;
    using LibShared for uint32;
    using LibString for uint8;

    uint256 private immutable _tokenPrice;
    uint256 private immutable _config;

    LibGame.Game private _game;
    LibWinners.Winners private _winners;
    LibRefundable.MintData private _mints;
    mapping(address => LibUser.User) private _users;
    uint256 private _claimSeed;
    address payable private _teamAddress;
    address payable private _drawAddress;
    string private _baseTokenURI;

    event Claim(address indexed from, uint32 indexed gameRound, uint256 indexed tokenId);
    event Commit(address indexed from, uint32 indexed gameRound);
    event Reveal(address indexed from, uint32 indexed gameRound);

    error ErrorClaimInvalidBurn(uint256 tokenId);
    error ErrorClaimInvalidOwner();
    error ErrorClaimInvalidToken(uint256 tokenId);
    error ErrorClaimInvalidUser();
    error ErrorClaimMaxWallet();
    error ErrorClaimPermissionDenied();
    error ErrorClaimRoundClosed();
    error ErrorClaimUnavailable();
    error ErrorCommitInvalidUser();
    error ErrorDoNotSendDirectEth();
    error ErrorDrawAddress();
    error ErrorGameNotRunning();
    error ErrorInvalidTokenURI();
    error ErrorMintComplete();
    error ErrorMintExpired();
    error ErrorMintMaxTokens();
    error ErrorMintMaxWallet();
    error ErrorMintNotActive();
    error ErrorMintResetting();
    error ErrorMintTxAmount();
    error ErrorMintTxPrice();
    error ErrorNonRefundable();
    error ErrorTeamAddress();
    error ErrorTokenPrice();
    error ErrorTransferDenied();
    error ErrorTransferInvalidBalance();
    error ErrorTransferInvalidUser();

    constructor(
        string memory name,
        string memory symbol,
        uint32 contractId,
        uint256 tokenPrice,
        uint16 maxTokens,
        uint16 maxWallet,
        uint16 maxAmount,
        uint8 teamSplit,
        address payable teamAddress,
        address payable drawAddress,
        string memory baseTokenURI
    )
    ERC721Psi(name, symbol)
    Ownable(msg.sender)
    PullPayment()
    TimeLock(MINT_START_LOCK, MINT_LAST_LOCK)
    {
        if (tokenPrice == 0) revert ErrorTokenPrice();
        _tokenPrice = tokenPrice;
        _config = LibConfig.initConfig(
            tokenPrice,
            contractId,
            maxTokens,
            maxWallet,
            maxAmount,
            teamSplit);
        _claimSeed = uint256(uint160(msg.sender));
        _setInternalAddresses(teamAddress, drawAddress);
        _setBaseTokenURI(baseTokenURI);
        _game.initGame(_nextTokenId());
    }

    function setWallets(
        address payable teamAddress,
        address payable drawAddress
    ) external nonReentrant onlyOwner {
        _setInternalAddresses(teamAddress, drawAddress);
    }

    function setBaseURI(
        string memory newURI
    ) external onlyOwner {
        _setBaseTokenURI(newURI);
    }

    fallback() external {
        revert ErrorDoNotSendDirectEth();
    }

    //////////////////////////////////////////////////
    /// Mint
    //////////////////////////////////////////////////
    /// @notice Allows users to mint new tokens for a specific game season.
    /// @dev User can mint multiple tokens, provided the limits for transaction amount and wallet 
    /// size are not exceeded and the game is not expired, in reset state, or already started.
    /// @param amount The number of tokens to mint.
    function mint(
        uint16 amount
    ) external payable nonReentrant {
        uint256 gameData = _game.data;
        uint32 gameRound = gameData.getGameRound();
        GameStatus status = _game.getStatus(gameData);
        if (amount > _config.maxAmount()) revert ErrorMintTxAmount();
        if (msg.value < _tokenPrice * amount) revert ErrorMintTxPrice();
        if (block.timestamp <= _game.virtualResetEndTime(status)) revert ErrorMintResetting();
        if (_isGameExpired(status)) revert ErrorMintExpired();
        if (gameData.gameState() != GAME_STATE_OFFLINE && status > GameStatus.RUNNING) {
            if (gameData.resetEndTime() == 0) {
                _finalizeGame(gameRound);
            }
            gameRound = _game.resetGame(_nextTokenId());
        } else if (status != GameStatus.MINTING) revert ErrorMintNotActive();
        unchecked {
            LibUser.User storage user = _users[msg.sender];
            uint256 userData = user.initUser(msg.sender, gameRound);
            if (userData.getLiveCount() + amount > _config.maxWallet()) revert ErrorMintMaxWallet();
            LibBitSet.Set storage gameTokens = _game.tokens[MINT_LIVE_INDEX];
            uint16 total = uint16(gameTokens.length()) + amount;
            uint16 maxTokens = _config.maxTokens();
            if (total > maxTokens) revert ErrorMintMaxTokens();
            gameTokens.addBatch(_nextTokenId(), amount);
            user.data = userData.addLiveCount(amount);
            _mint(msg.sender, amount);
            uint256 teamAmount = (msg.value * _config.teamSplit()) / 100;
            uint256 userAmount = msg.value - teamAmount;
            _game.prizePool += userAmount;
            _mints.addRefundableAmount(gameRound >> OFFSET_GAME_NUMBER, msg.sender, userAmount);
            _asyncTransfer(_teamAddress, teamAmount);
            if (total == maxTokens) {
                _game.startGame();
                resetTimeLock();
            }
        }
        timeLock();
    }

    //////////////////////////////////////////////////
    /// Commit
    //////////////////////////////////////////////////
    /// @notice Allows users to commit a secret hash to a running or pending game round.
    /// @param hash The hashed secret committed by the user.
    function commit(
        bytes32 hash
    ) external nonReentrant {
        uint256 gameData = _game.data;
        uint32 gameRound = gameData.getGameRound();
        LibUser.User storage user = _users[msg.sender];
        if (user.isInvalid(gameRound)) {
            revert ErrorClaimInvalidUser();
        }
        GameStatus status = _game.getStatus();
        if (status != GameStatus.PENDING && status != GameStatus.RUNNING) {
            revert ErrorGameNotRunning();
        }
        if (status == GameStatus.PENDING) {
            if (gameData.pauseEndTime() != 0) {
                unchecked { gameRound++; }
            }
            _game.startRound(gameRound);
            status = GameStatus.RUNNING;
        }
        user.commit(gameRound, status, hash);
        emit Commit(msg.sender, gameRound);
    }

    //////////////////////////////////////////////////
    /// Reveal
    //////////////////////////////////////////////////
    /// @notice Allows users to reveal their previously committed secret.
    /// @param secret The original secret to be revealed.
    function reveal(
        bytes memory secret
    ) external nonReentrant {
        uint32 gameRound = _game.data.getGameRound();
        _users[msg.sender].reveal(gameRound, _game.getStatus(), secret);
        _randomSeed(bytes32(secret));
        emit Reveal(msg.sender, gameRound);
    }

    //////////////////////////////////////////////////
    /// Claim
    //////////////////////////////////////////////////
    /// @notice Allows a user to claim a token in exchange for burning another random unclaimed token.
    /// @param tokenId The ID of the token to be claimed.
    function claim(
        uint256 tokenId
    ) external nonReentrant {
        LibUser.User storage user = _users[msg.sender];
        LibUser.User memory claimUser = user;
        uint256 claimData = claimUser.data;
        uint256 gameData = _game.data;
        uint32 gameRound = gameData.getGameRound();
        uint256 roundEndTime = gameData.roundEndTime();
        LibBitSet.Set storage liveTokens = _game.tokens[gameRound.liveIndex()];
        uint256 liveCount = liveTokens.length();
        if (ownerOf(tokenId) != msg.sender) revert ErrorClaimInvalidOwner();
        if (liveCount <= 1) revert ErrorClaimUnavailable();
        if (claimData.getSafeCount() >= _config.maxWallet()) revert ErrorClaimMaxWallet();
        if (roundEndTime <= block.timestamp) revert ErrorClaimRoundClosed();
        if (claimData.getGameRound() != gameRound) revert ErrorClaimInvalidUser();
        if (claimUser.lastCommit <= REVEAL_THRESHOLD) revert ErrorClaimPermissionDenied();
        if (!liveTokens.remove(tokenId)) revert ErrorClaimInvalidToken(tokenId);
        uint256 safeCount = _game.tokens[gameRound.safeIndex()].add(tokenId);
        claimData = claimData.subLiveCount(1);
        claimData = claimData.addSafeCount(1);
        unchecked {
            liveCount -= 1;
            uint256 burnId = liveTokens.removeAt(_randomN(tokenId, liveCount));
            if (burnId == LibBitSet.NOT_FOUND) revert ErrorClaimInvalidBurn(burnId);
            address burnAddress = ownerOf(burnId);
            _burn(burnId);
            liveCount -= 1;
            gameData += 1;
            if (burnAddress != msg.sender) {
                uint256 burnData = _users[burnAddress].initUser(burnAddress, gameRound);
                _users[burnAddress].data = burnData.subLiveCount(1) + 1;
            } else {
                claimData = claimData.subLiveCount(1) + 1;
            }
            emit Claim(msg.sender, gameRound, tokenId);
            if (claimData.getSafeCount() != safeCount) {
                gameData = gameData.setMultiUser();
            }
            if (liveCount <= 1) {
                gameData = gameData.clearRoundEndTime();
            }
            if ((liveCount > 1) || (gameData.isMultiUser() && (safeCount > 1))) {
                uint256 pauseTime = LibShared.max(safeCount << TOKEN_DELAY_PAUSE, MIN_PAUSE_TIME);
                gameData = gameData.setPauseEndTime(
                    LibShared.max(gameData.roundEndTime(), block.timestamp) + pauseTime
                );
            }
            else {
                gameData = gameData.clearPauseEndTime() | gameData.setResetEndTime(block.timestamp + MIN_RESET_TIME);
                uint256 prize = _game.prizePool;
                _winners.recordWinner(tokenId, prize, gameRound, msg.sender);
                _asyncTransfer(msg.sender, prize);
                emit LibGame.GameOver(gameRound, msg.sender);
            }
        }
        user.data = claimData;
        _game.data = gameData;
    }

    //////////////////////////////////////////////////
    /// Finalize
    //////////////////////////////////////////////////
    /// @notice Finalizes the current game round.
    function finalize(
    ) external nonReentrant {
        _finalizeGame(_game.data.getGameRound());
    }

    //////////////////////////////////////////////////
    /// Refund
    //////////////////////////////////////////////////
    /// @notice Allows a user to claim a refund for a particular game.
    /// @param gameNumber The ID of the game to claim a refund from.
    function refund(
        uint32 gameNumber,
        address payable owner
    ) external nonReentrant {
        uint256 amount = _mints.removeRefundableAmount(gameNumber, owner);
        if (amount == 0) revert ErrorNonRefundable();
        _asyncTransfer(owner, amount);
    }

    //////////////////////////////////////////////////
    /// Cancel
    //////////////////////////////////////////////////
    /// @notice Allows to cancel the current game once the time lock has expired.
    function cancel(
    ) external nonReentrant timeLocked {
        if (_game.getStatus() != GameStatus.MINTING) revert ErrorMintNotActive();
        if ( _game.liveTokenCount() >= _config.maxTokens()) revert ErrorMintComplete();
        _mints.cancelMint(_game.data.getGameNumber(), _game.prizePool);
        _game.cancelGame(_nextTokenId());
        resetTimeLock();
    }

    function config(
    ) external view returns (uint256 tokenPrice, uint256 data, address drawAddress) {
        return (_tokenPrice, _config, _drawAddress);
    }

    function getRefundAmount(
        uint256 gameNumber,
        address owner
    ) external view returns (uint256) {
        return _mints.getRefundableAmount(gameNumber, owner);
    }

    function canCancelGame(
    ) external view returns (uint256) {
        if (_game.getStatus() != GameStatus.MINTING) return TimeLock.MAX_LOCK;
        return timeLockLeft();
    }

    function cancelledGames(
    ) external view returns (uint256[] memory) {
        return _mints.cancelledMints();
    }

    function totalCancelledGames(
    ) external view returns (uint256) {
        return _mints.totalCancelledMints();
    }

    function cancelledGameAtIndex(
        uint256 index
    ) external view returns (uint256) {
        return _mints.cancelledMintAtIndex(index);
    }

    function isGameFinalized(
    ) external view returns (bool) {
        (, bool finalized) = _isGameFinalized(_game.data.getGameRound());
        return finalized;
    }

    function isGameExpired(
    ) external view returns (bool) {
        return _isGameExpired(_game.getStatus());
    }

    function getGameInfo(
    ) external view returns (uint256) {
        return _game.gameInfo();
    }

    function getUserInfo(
        address userAddress
    ) external view returns (uint256) {
        return _users[userAddress].getUserInfo(_game);
    }

    function getTokenStatus(
        uint256 tokenId
    ) external view returns (uint8) {
        uint8 status = _getVirtualTokenStatus(tokenId);
        if (status == TOKEN_STATUS_SECURE && _game.data.hasPauseExpired()) {
            status = TOKEN_STATUS_ACTIVE;
        } else if ((status & TOKEN_STATUS_BURNED) != 0) {
            status = TOKEN_STATUS_BURNED;
        } else if ((status & TOKEN_STATUS_WINNER) != 0) {
            status = TOKEN_STATUS_WINNER;
        }
        return status;
    }

    function isTokenOwner(
        address owner,
        uint256 idx
    ) external view override returns (bool) {
        return ownerOf(idx) == owner;
    }

    function liveTokenOfOwner(
        address owner
    ) external view returns (uint256) {
        uint256 data = _users[owner].data;
        uint32 gameRound = _game.data.getGameRound();
        if ((gameRound != data.getGameRound()) || (data.getLiveCount() == 0))
            return LibBitSet.NOT_FOUND;
        return _game.tokens[gameRound.liveIndex()].findFirstOfOwner(owner, this);
    }

    function totalWinners(
    ) external view returns (uint256) {
        uint256 total = _winners.totalWinners();
        (uint256 tokenId, bool finalized) = _isGameFinalized(_game.data.getGameRound());
        if (finalized || tokenId == LibBitSet.NOT_FOUND) return total;
        return total + 1;
    }

    function getWinnerAtIndex(
        uint256 index
    ) external view returns (LibWinners.Winner memory) {
        if (index == _winners.totalWinners()) {
            return _virtualWinner(_game.data.getGameRound());
        }
        return _winners.getWinnerAt(index);
    }

    function getWinner(
        uint32 gameNumber
    ) external view returns (LibWinners.Winner memory) {
        uint32 gameRound = _game.data.getGameRound();
        uint32 currentGame = gameRound >> OFFSET_GAME_NUMBER;
        if (gameNumber > currentGame) {
            gameNumber = currentGame;
        }
        LibWinners.Winner memory winner = _winners.getWinner(gameNumber);
        if (winner.data != 0 || gameNumber != currentGame) {
            return winner;
        }
        return _virtualWinner(gameRound);
    }

    function tokenURI(
        uint256 tokenId
    ) public view override returns (string memory) {
        if (!_exists(tokenId)) {
            revert OperatorQueryForNonexistentToken();
        }
        uint8 slug = _getVirtualTokenStatus(tokenId);
        if (slug == TOKEN_STATUS_BANNED || ((slug & TOKEN_STATUS_BURNED) != 0)) {
            slug = TOKEN_STATUS_BURNED;
        }
        if (slug == TOKEN_STATUS_SECURE && _game.data.hasPauseExpired()) {
            slug = TOKEN_STATUS_ACTIVE;
        }
        if ((slug & TOKEN_STATUS_WINNER) != 0) {
            slug = TOKEN_STATUS_WINNER;
            tokenId = _winners.getWinnerId(tokenId);
        } else {
            tokenId %= _config.maxTokens();
        }
        return string(abi.encodePacked(
            _baseTokenURI, slug.toString(), URI_SLASH, tokenId.toString()
        ));
    }

    function transferFrom(
        address from,
        address to,
        uint256 tokenId
    ) public payable override {
        if (!_approveTransfer(from, to, tokenId)) return;
        super._transfer(from, to, tokenId);
    }

    function safeTransferFrom(
        address from,
        address to,
        uint256 tokenId,
        bytes memory _data
    ) public payable override {
        if (!_approveTransfer(from, to, tokenId)) return;
        super._safeTransfer(from, to, tokenId, _data);
    }

    function _setInternalAddresses(
        address payable teamAddress,
        address payable drawAddress
    ) internal {
        if (teamAddress == address(0)) revert ErrorTeamAddress();
        if (drawAddress == address(0)) revert ErrorDrawAddress();
        _teamAddress = teamAddress;
        _drawAddress = drawAddress;
    }

    function _finalizeGame(
        uint32 gameRound
    ) internal returns (bool) {
        (uint256 tokenId, bool finalized) = _isGameFinalized(gameRound);
        if (finalized) return false;
        address winnerAddress = tokenId >= FORFEIT_TOKEN_ID ?
            _drawAddress : ownerOf(tokenId);
        uint256 prize = _game.prizePool;
        _winners.recordWinner(tokenId, prize, gameRound, winnerAddress);
        _asyncTransfer(winnerAddress, prize);
        emit LibGame.GameOver(gameRound, winnerAddress);
        return true;
    }

    function _isGameFinalized(
        uint32 gameRound
    ) internal view returns (uint256, bool) {
        uint256 tokenId = _game.isGameOver(gameRound);
        return (tokenId, tokenId == LibBitSet.NOT_FOUND || _winners.hasWinner(tokenId));
    }

    function _isGameExpired(
        GameStatus status
    ) internal view returns (bool) {
        return (status == GameStatus.MINTING) && timeLockExpired();
    }

    function _getVirtualTokenStatus(
        uint256 tokenId
    ) internal view returns (uint8) {
        if (_winners.hasWinner(tokenId)) return TOKEN_STATUS_WINNER;
        uint8 status = _game.getTokenStatus(tokenId);
        if ((status & (TOKEN_STATUS_ACTIVE | TOKEN_STATUS_SECURE)) != 0) {
            uint256 winnerId = _game.isGameOver(_game.data.getGameRound());
            if (winnerId != LibBitSet.NOT_FOUND) {
                return status | (winnerId == tokenId ? TOKEN_STATUS_WINNER : TOKEN_STATUS_BURNED);
            }
        }
        return status;
    }

    function _approveTransfer(
        address from,
        address to,
        uint256 tokenId
    ) internal returns (bool) {
        if ((from == to) || !_isApprovedOrOwner(msg.sender, tokenId)) revert TransferFromIncorrectOwner();
        uint8 tokenStatus = _getVirtualTokenStatus(tokenId);
        if (tokenStatus == TOKEN_STATUS_BANNED || ((tokenStatus & TOKEN_STATUS_BURNED) != 0)) {
            _burn(tokenId);
            return false;
        }
        if ((tokenStatus & TOKEN_STATUS_WINNER) != 0) return true;
        if (_game.getStatus() == GameStatus.RUNNING) revert ErrorTransferDenied();
        uint32 gameRound = _game.data.getGameRound();
        LibUser.User storage fromUser = _users[from];
        if (fromUser.isInvalid(gameRound)) revert ErrorTransferInvalidUser();
        uint256 fromData = fromUser.initUser(from, gameRound);
        if ((tokenStatus & (TOKEN_STATUS_ACTIVE | TOKEN_STATUS_QUEUED)) != 0) {
            if (fromData.getLiveCount() == 0) revert ErrorTransferInvalidBalance();
            fromData = fromData.subLiveCount(1);
        } else if ((tokenStatus & TOKEN_STATUS_SECURE) != 0) {
            if (fromData.getSafeCount() == 0) revert ErrorTransferInvalidBalance();
            fromData = fromData.subSafeCount(1);
        }
        fromUser.data = fromData;
        LibUser.User storage toUser = _users[to];
        uint256 toData = toUser.initUser(to, gameRound);
        if ((tokenStatus & (TOKEN_STATUS_ACTIVE | TOKEN_STATUS_QUEUED)) != 0) {
            toData = toData.addLiveCount(1);
        } else if ((tokenStatus & TOKEN_STATUS_SECURE) != 0) {
            toData = toData.addSafeCount(1);
        }
        toUser.data = toData;
        return true;
    }

    function _setBaseTokenURI(
        string memory newURI
    ) private {
        if (bytes(newURI).length < 10) revert ErrorInvalidTokenURI();
        _baseTokenURI = newURI;
    }

    function _virtualUserOf(
        address owner
    ) private view returns (LibUser.User storage, uint32) {
        LibUser.User storage user = _users[owner];
        uint32 gameRound =_game.data.getGameRound();
        return (user, user.isExpired(gameRound) ? 0 : gameRound);
    }

    function _virtualWinner(
        uint32 gameRound
    ) private view returns (LibWinners.Winner memory) {
        LibWinners.Winner memory winner;
        uint256 tokenId = _game.isGameOver(gameRound);
        if (tokenId == LibBitSet.NOT_FOUND) return winner;
        bool draw = tokenId >= FORFEIT_TOKEN_ID;
        address winAddress = draw ? _drawAddress : ownerOf(tokenId);
        gameRound ^= (gameRound & uint32(LibShared.MASK_ROUND));
        winner.data = _winners.packWinnerData(gameRound, winAddress);
        winner.tokenId = draw ? 0 : tokenId;
        winner.prize = _game.prizePool;
        return winner;
    }

    function _randomSeed(
        bytes32 seed
    ) private {
        unchecked {
            _claimSeed = uint256(keccak256(abi.encodePacked(
                _claimSeed, block.prevrandao, msg.sender, block.timestamp, seed, tx.gasprice,
                blockhash(block.number - (uint256(seed) % (block.number < 255 ? block.number - 1 : 255) + 1)))));
        }
    }

    function _randomN(
        uint256 nonce,
        uint256 max
    ) private view returns (uint256 result) {
        return LibPRNG.PRNG({state: uint256(keccak256(
            abi.encodePacked(nonce, block.prevrandao, msg.sender, block.timestamp, _claimSeed)
        ))}).uniform(max);
    }
}

// SPDX-License-Identifier: UNLICENSED

pragma solidity ^0.8.23;

uint256 constant FORFEIT_TOKEN_ID = 1e6;
uint256 constant GAME_STATE_OFFLINE = 0x0;
uint256 constant GAME_STATE_STARTED = 0x1;
uint256 constant GAME_STATE_VIRTUAL = 0x2;
uint256 constant DATA_OFFSET_SAFE_COUNT = 16;
uint256 constant DATA_OFFSET_LIVE_COUNT = 32;
uint256 constant DATA_OFFSET_GAME_ROUND = 224;
uint256 constant DATA_OFFSET_ROUND_COUNT = 224;
uint256 constant DATA_OFFSET_GAME_NUMBER = 232;
uint256 constant REVEAL_THRESHOLD = 0xFFFFFFFF;
uint32 constant OFFSET_GAME_NUMBER = 8;
uint32 constant MIN_ROUND_TIME = 60 minutes;
uint32 constant MIN_PAUSE_TIME = 60 minutes;
uint32 constant MIN_RESET_TIME = 24 hours;
uint32 constant MINT_START_LOCK = 365 days;
uint32 constant MINT_LAST_LOCK = 90 days;
uint16 constant TOKEN_DELAY_ROUND = 4;
uint16 constant TOKEN_DELAY_PAUSE = 5;
uint8 constant TOKEN_STATUS_BANNED = 0x00;
uint8 constant TOKEN_STATUS_BURNED = 0x02;
uint8 constant TOKEN_STATUS_QUEUED = 0x04;
uint8 constant TOKEN_STATUS_ACTIVE = 0x08;
uint8 constant TOKEN_STATUS_SECURE = 0x10;
uint8 constant TOKEN_STATUS_WINNER = 0x20;
uint8 constant MINT_LIVE_INDEX = 0;
string constant URI_SLASH = "/";

// SPDX-License-Identifier: MIT
// OpenZeppelin Contracts (last updated v5.0.0) (utils/Context.sol)

pragma solidity ^0.8.20;

/**
 * @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;
    }
}

// SPDX-License-Identifier: MIT
/**
  ______ _____   _____ ______ ___  __ _  _  _ 
 |  ____|  __ \ / ____|____  |__ \/_ | || || |
 | |__  | |__) | |        / /   ) || | \| |/ |
 |  __| |  _  /| |       / /   / / | |\_   _/ 
 | |____| | \ \| |____  / /   / /_ | |  | |   
 |______|_|  \_\\_____|/_/   |____||_|  |_|   

 - github: https://github.com/estarriolvetch/ERC721Psi
 - npm: https://www.npmjs.com/package/erc721psi

 */

pragma solidity ^0.8.0;

import "@openzeppelin/contracts/utils/Strings.sol";
import "@openzeppelin/contracts/utils/Address.sol";
import "solady/src/utils/LibBitmap.sol";
import "./interface/IERC721Psi.sol";

/**
 * @dev Interface of ERC721 token receiver.
 */
interface ERC721Psi__IERC721Receiver {
    function onERC721Received(
        address operator,
        address from,
        uint256 tokenId,
        bytes calldata data
    ) external returns (bytes4);
}

contract ERC721Psi is IERC721Psi {
    
    using Address for address;
    using Strings for uint256;
    using LibBitmap for LibBitmap.Bitmap;

    LibBitmap.Bitmap private _batchHead;

    string private _name;
    string private _symbol;

    // Mapping from token ID to owner address
    mapping(uint256 => address) internal _owners;
    uint256 internal _currentIndex;

    mapping(uint256 => address) private _tokenApprovals;
    mapping(address => mapping(address => bool)) private _operatorApprovals;

    // The mask of the lower 160 bits for addresses.
    uint256 private constant _BITMASK_ADDRESS = (1 << 160) - 1;
    // The `Transfer` event signature is given by:
    // `keccak256(bytes("Transfer(address,address,uint256)"))`.
    bytes32 private constant _TRANSFER_EVENT_SIGNATURE =
        0xddf252ad1be2c89b69c2b068fc378daa952ba7f163c4a11628f55a4df523b3ef;

    /**
     * @dev Initializes the contract by setting a `name` and a `symbol` to the token collection.
     */
    constructor(string memory name_, string memory symbol_) {
        _name = name_;
        _symbol = symbol_;
        _currentIndex = _startTokenId();
    }

    /**
     * @dev Returns the starting token ID.
     * To change the starting token ID, please override this function.
     */
    function _startTokenId() internal view virtual returns (uint256) {
        return 0;
    }

    /**
     * @dev Returns the next token ID to be minted.
     */
    function _nextTokenId() internal view virtual returns (uint256) {
        return _currentIndex;
    }

    /**
     * @dev Returns the total amount of tokens minted in the contract.
     */
    function _totalMinted() internal view virtual returns (uint256) {
        return _currentIndex - _startTokenId();
    }


    /**
     * @dev Returns true if this contract implements the interface defined by
     * `interfaceId`. See the corresponding
     * [EIP section](https://eips.ethereum.org/EIPS/eip-165#how-interfaces-are-identified)
     * to learn more about how these ids are created.
     *
     * This function call must use less than 30000 gas.
     */
    function supportsInterface(bytes4 interfaceId) public view virtual override returns (bool) {
        // The interface IDs are constants representing the first 4 bytes
        // of the XOR of all function selectors in the interface.
        // See: [ERC165](https://eips.ethereum.org/EIPS/eip-165)
        // (e.g. `bytes4(i.functionA.selector ^ i.functionB.selector ^ ...)`)
        return
            interfaceId == 0x01ffc9a7 || // ERC165 interface ID for ERC165.
            interfaceId == 0x80ac58cd || // ERC165 interface ID for ERC721.
            interfaceId == 0x5b5e139f; // ERC165 interface ID for ERC721Metadata.
    }

    /**
     * @dev See {IERC721-balanceOf}.
     */
    function balanceOf(address owner) 
        public 
        view 
        virtual 
        override 
        returns (uint) 
    {
        if(owner == address(0)) revert BalanceQueryForZeroAddress();

        uint count;
        for( uint i = _startTokenId(); i < _nextTokenId(); ++i ){
            if(_exists(i)){
                if( owner == ownerOf(i)){
                    ++count;
                }
            }
        }
        return count;
    }

    /**
     * @dev See {IERC721-ownerOf}.
     */
    function ownerOf(uint256 tokenId)
        public
        view
        virtual
        override
        returns (address)
    {
        (address owner, ) = _ownerAndBatchHeadOf(tokenId);
        return owner;
    }

    function _ownerAndBatchHeadOf(uint256 tokenId) internal view returns (address owner, uint256 tokenIdBatchHead){
        if (!_exists(tokenId)) revert OwnerQueryForNonexistentToken();
        tokenIdBatchHead = _getBatchHead(tokenId);
        owner = _owners[tokenIdBatchHead];
    }

    /**
     * @dev See {IERC721Metadata-name}.
     */
    function name() public view virtual override returns (string memory) {
        return _name;
    }

    /**
     * @dev See {IERC721Metadata-symbol}.
     */
    function symbol() public view virtual override returns (string memory) {
        return _symbol;
    }

    /**
     * @dev See {IERC721Metadata-tokenURI}.
     */
    function tokenURI(uint256 tokenId) public view virtual override returns (string memory) {
        if( !_exists(tokenId)) revert URIQueryForNonexistentToken();
        string memory baseURI = _baseURI();
        return bytes(baseURI).length > 0 ? string(abi.encodePacked(baseURI, tokenId.toString())) : "";
    }

    /**
     * @dev Base URI for computing {tokenURI}. If set, the resulting URI for each
     * token will be the concatenation of the `baseURI` and the `tokenId`. Empty
     * by default, can be overriden in child contracts.
     */
    function _baseURI() internal view virtual returns (string memory) {
        return "";
    }


    /**
     * @dev See {IERC721-approve}.
     */
    function approve(address to, uint256 tokenId) public payable virtual override {
        address owner = ownerOf(tokenId);

        if (_msgSenderERC721Psi() != owner) {
            if (!isApprovedForAll(owner, _msgSenderERC721Psi())) {
                revert ApprovalCallerNotOwnerNorApproved();
            }
        }

        _approve(to, tokenId);
    }

    /**
     * @dev See {IERC721-getApproved}.
     */
    function getApproved(uint256 tokenId)
        public
        view
        virtual
        override
        returns (address) 
    {
        if (!_exists(tokenId)) revert ApprovalQueryForNonexistentToken();

        return _tokenApprovals[tokenId];
    }

    /**
     * @dev See {IERC721-setApprovalForAll}.
     */
    function setApprovalForAll(address operator, bool approved)
        public
        virtual
        override
    {
        _operatorApprovals[_msgSenderERC721Psi()][operator] = approved;
        emit ApprovalForAll(_msgSenderERC721Psi(), operator, approved);
    }

    /**
     * @dev See {IERC721-isApprovedForAll}.
     */
    function isApprovedForAll(address owner, address operator)
        public
        view
        virtual
        override
        returns (bool)
    {
        return _operatorApprovals[owner][operator];
    }

    /**
     * @dev See {IERC721-transferFrom}.
     */
    function transferFrom(
        address from,
        address to,
        uint256 tokenId
    ) public payable virtual override {
        _transfer(from, to, tokenId);
    }

    /**
     * @dev See {IERC721-safeTransferFrom}.
     */
    function safeTransferFrom(
        address from,
        address to,
        uint256 tokenId
    ) public payable virtual override {
        safeTransferFrom(from, to, tokenId, "");
    }

    /**
     * @dev See {IERC721-safeTransferFrom}.
     */
    function safeTransferFrom(
        address from,
        address to,
        uint256 tokenId,
        bytes memory _data
    ) public payable virtual override {
        _safeTransfer(from, to, tokenId, _data);
    }

    /**
     * @dev Safely transfers `tokenId` token from `from` to `to`, checking first that contract recipients
     * are aware of the ERC721 protocol to prevent tokens from being forever locked.
     *
     * `_data` is additional data, it has no specified format and it is sent in call to `to`.
     *
     * This internal function is equivalent to {safeTransferFrom}, and can be used to e.g.
     * implement alternative mechanisms to perform token transfer, such as signature-based.
     *
     * Requirements:
     *
     * - `from` cannot be the zero address.
     * - `to` cannot be the zero address.
     * - `tokenId` token must exist and be owned by `from`.
     * - If `to` refers to a smart contract, it must implement {IERC721Receiver-onERC721Received}, which is called upon a safe transfer.
     *
     * Emits a {Transfer} event.
     */
    function _safeTransfer(
        address from,
        address to,
        uint256 tokenId,
        bytes memory _data
    ) internal virtual {
        _transfer(from, to, tokenId);
        if (!_checkOnERC721Received(from, to, tokenId, 1, _data)) {
            revert TransferToNonERC721ReceiverImplementer();
        }
    }

    /**
     * @dev Returns whether `tokenId` exists.
     *
     * Tokens can be managed by their owner or approved accounts via {approve} or {setApprovalForAll}.
     *
     * Tokens start existing when they are minted (`_mint`).
     */
    function _exists(uint256 tokenId) internal view virtual returns (bool) {
        return tokenId < _nextTokenId() && _startTokenId() <= tokenId;
    }

    error OperatorQueryForNonexistentToken();

    /**
     * @dev Returns whether `spender` is allowed to manage `tokenId`.
     *
     * Requirements:
     *
     * - `tokenId` must exist.
     */
    function _isApprovedOrOwner(address spender, uint256 tokenId)
        internal
        view
        virtual
        returns (bool)
    {
        if (!_exists(tokenId)) revert OperatorQueryForNonexistentToken();
        address owner = ownerOf(tokenId);
        return (spender == owner ||
            getApproved(tokenId) == spender ||
            isApprovedForAll(owner, spender));
    }

    /**
     * @dev Safely mints `quantity` tokens and transfers them to `to`.
     *
     * Requirements:
     *
     * - If `to` refers to a smart contract, it must implement {IERC721Receiver-onERC721Received}, which is called for each safe transfer.
     * - `quantity` must be greater than 0.
     *
     * Emits a {Transfer} event.
     */
    function _safeMint(address to, uint256 quantity) internal virtual {
        _safeMint(to, quantity, "");
    }

    
    function _safeMint(
        address to,
        uint256 quantity,
        bytes memory _data
    ) internal virtual {
        _mint(to, quantity);
        uint256 end = _currentIndex;
        if (!_checkOnERC721Received(address(0), to, end - quantity, quantity, _data)) {
            revert TransferToNonERC721ReceiverImplementer();
        }
        // Reentrancy protection.
        if (_currentIndex != end) revert();
    }


    function _mint(
        address to,
        uint256 quantity
    ) internal virtual {
        uint256 nextTokenId = _nextTokenId();
        
        if (quantity == 0) revert MintZeroQuantity();
        if (to == address(0)) revert MintToZeroAddress();
        
        _beforeTokenTransfers(address(0), to, nextTokenId, quantity);
        _currentIndex += quantity;
        _owners[nextTokenId] = to;
        _batchHead.set(nextTokenId);

        uint256 toMasked;
        uint256 end = nextTokenId + quantity;

        // Use assembly to loop and emit the `Transfer` event for gas savings.
        // The duplicated `log4` removes an extra check and reduces stack juggling.
        // The assembly, together with the surrounding Solidity code, have been
        // delicately arranged to nudge the compiler into producing optimized opcodes.
        assembly {
            // Mask `to` to the lower 160 bits, in case the upper bits somehow aren't clean.
            toMasked := and(to, _BITMASK_ADDRESS)
            // Emit the `Transfer` event.
            log4(
                0, // Start of data (0, since no data).
                0, // End of data (0, since no data).
                _TRANSFER_EVENT_SIGNATURE, // Signature.
                0, // `address(0)`.
                toMasked, // `to`.
                nextTokenId // `tokenId`.
            )

            // The `iszero(eq(,))` check ensures that large values of `quantity`
            // that overflows uint256 will make the loop run out of gas.
            // The compiler will optimize the `iszero` away for performance.
            for {
                let tokenId := add(nextTokenId, 1)
            } iszero(eq(tokenId, end)) {
                tokenId := add(tokenId, 1)
            } {
                // Emit the `Transfer` event. Similar to above.
                log4(0, 0, _TRANSFER_EVENT_SIGNATURE, 0, toMasked, tokenId)
            }
        }

        _afterTokenTransfers(address(0), to, nextTokenId, quantity);
    }


    /**
     * @dev Transfers `tokenId` from `from` to `to`.
     *  As opposed to {transferFrom}, this imposes no restrictions on msg.sender.
     *
     * Requirements:
     *
     * - `to` cannot be the zero address.
     * - `tokenId` token must be owned by `from`.
     *
     * Emits a {Transfer} event.
     */
    function _transfer(
        address from,
        address to,
        uint256 tokenId
    ) internal virtual {

        (address owner, uint256 tokenIdBatchHead) = _ownerAndBatchHeadOf(tokenId);

        if (owner != from) revert TransferFromIncorrectOwner();

        if (!_isApprovedOrOwner(_msgSenderERC721Psi(), tokenId)) {
            revert TransferCallerNotOwnerNorApproved();
        }

        if (to == address(0)) revert TransferToZeroAddress();

        _beforeTokenTransfers(from, to, tokenId, 1);

        // Clear approvals from the previous owner
        _approve(address(0), tokenId);   

        uint256 subsequentTokenId = tokenId + 1;

        if(!_batchHead.get(subsequentTokenId) &&  
            subsequentTokenId < _nextTokenId()
        ) {
            _owners[subsequentTokenId] = from;
            _batchHead.set(subsequentTokenId);
        }

        _owners[tokenId] = to;
        if(tokenId != tokenIdBatchHead) {
            _batchHead.set(tokenId);
        }

        emit Transfer(from, to, tokenId);

        _afterTokenTransfers(from, to, tokenId, 1);
    }

    /**
     * @dev Approve `to` to operate on `tokenId`
     *
     * Emits a {Approval} event.
     */
    function _approve(address to, uint256 tokenId) internal virtual {
        _tokenApprovals[tokenId] = to;
        emit Approval(ownerOf(tokenId), to, tokenId);
    }

    /**
     * @dev Internal function to invoke {IERC721Receiver-onERC721Received} on a target address.
     * The call is not executed if the target address is not a contract.
     *
     * @param from address representing the previous owner of the given token ID
     * @param to target address that will receive the tokens
     * @param startTokenId uint256 the first ID of the tokens to be transferred
     * @param quantity uint256 amount of the tokens to be transfered.
     * @param _data bytes optional data to send along with the call
     * @return r bool whether the call correctly returned the expected magic value
     */
    function _checkOnERC721Received(
        address from,
        address to,
        uint256 startTokenId,
        uint256 quantity,
        bytes memory _data
    ) private returns (bool r) {
        /// @dev removed isContract() in v5.0 but their ERC721 uses this check:
        if (to.code.length > 0) {
            r = true;
            for(uint256 tokenId = startTokenId; tokenId < startTokenId + quantity; tokenId++){
                try ERC721Psi__IERC721Receiver(to).onERC721Received( _msgSenderERC721Psi(), from, tokenId, _data) returns (bytes4 retval) {
                    r = r && retval == ERC721Psi__IERC721Receiver.onERC721Received.selector;
                } catch (bytes memory reason) {
                    if (reason.length == 0) {
                        revert TransferToNonERC721ReceiverImplementer();
                    } else {
                        assembly {
                            revert(add(32, reason), mload(reason))
                        }
                    }
                }
            }
            return r;
        } else {
            return true;
        }
    }

    function _getBatchHead(uint256 tokenId) internal view returns (uint256 tokenIdBatchHead) {
        tokenIdBatchHead = _batchHead.findLastSet(tokenId); 
    }


    function totalSupply() public virtual override view returns (uint256) {
        return _totalMinted();
    }

    /**
     * @dev Returns an array of token IDs owned by `owner`.
     *
     * This function scans the ownership mapping and is O(`totalSupply`) in complexity.
     * It is meant to be called off-chain.
     *
     * This function is compatiable with ERC721AQueryable.
     */
    function tokensOfOwner(address owner) external view virtual returns (uint256[] memory) {
        unchecked {
            uint256 tokenIdsIdx;
            uint256 tokenIdsLength = balanceOf(owner);
            uint256[] memory tokenIds = new uint256[](tokenIdsLength);
            for (uint256 i = _startTokenId(); tokenIdsIdx != tokenIdsLength; ++i) {
                if (_exists(i)) {
                    if (ownerOf(i) == owner) {
                        tokenIds[tokenIdsIdx++] = i;
                    }
                }
            }
            return tokenIds;   
        }
    }

    /**
     * @dev Hook that is called before a set of serially-ordered token ids are about to be transferred. This includes minting.
     *
     * startTokenId - the first token id to be transferred
     * quantity - the amount to be transferred
     *
     * Calling conditions:
     *
     * - When `from` and `to` are both non-zero, ``from``'s `tokenId` will be
     * transferred to `to`.
     * - When `from` is zero, `tokenId` will be minted for `to`.
     */
    function _beforeTokenTransfers(
        address from,
        address to,
        uint256 startTokenId,
        uint256 quantity
    ) internal virtual {}

    /**
     * @dev Hook that is called after a set of serially-ordered token ids have been transferred. This includes
     * minting.
     *
     * startTokenId - the first token id to be transferred
     * quantity - the amount to be transferred
     *
     * Calling conditions:
     *
     * - when `from` and `to` are both non-zero.
     * - `from` and `to` are never both zero.
     */
    function _afterTokenTransfers(
        address from,
        address to,
        uint256 startTokenId,
        uint256 quantity
    ) internal virtual {}


    /**
     * @dev Returns the message sender (defaults to `msg.sender`).
     *
     * If you are writing GSN compatible contracts, you need to override this function.
     */
    function _msgSenderERC721Psi() internal view virtual returns (address) {
        return msg.sender;
    }
}

// SPDX-License-Identifier: MIT
/**
  ______ _____   _____ ______ ___  __ _  _  _ 
 |  ____|  __ \ / ____|____  |__ \/_ | || || |
 | |__  | |__) | |        / /   ) || | \| |/ |
 |  __| |  _  /| |       / /   / / | |\_   _/ 
 | |____| | \ \| |____  / /   / /_ | |  | |   
 |______|_|  \_\\_____|/_/   |____||_|  |_|   
                                              
                                            
 */
pragma solidity ^0.8.0;

import "solady/src/utils/LibBitmap.sol";
import "../ERC721Psi.sol";

abstract contract ERC721PsiBurnable is ERC721Psi {
    using LibBitmap for LibBitmap.Bitmap;
    LibBitmap.Bitmap private _burnedToken;

    /**
     * @dev Destroys `tokenId`.
     * The approval is cleared when the token is burned.
     *
     * Requirements:
     *
     * - `tokenId` must exist.
     *
     * Emits a {Transfer} event.
     */
    function _burn(uint256 tokenId) internal virtual {
        address from = ownerOf(tokenId);
        _beforeTokenTransfers(from, address(0), tokenId, 1);
        _burnedToken.set(tokenId);
        
        emit Transfer(from, address(0), tokenId);

        _afterTokenTransfers(from, address(0), tokenId, 1);
    }

    /**
     * @dev Returns whether `tokenId` exists.
     *
     * Tokens can be managed by their owner or approved accounts via {approve} or {setApprovalForAll}.
     *
     * Tokens start existing when they are minted (`_mint`),
     * and stop existing when they are burned (`_burn`).
     */
    function _exists(uint256 tokenId) internal view override virtual returns (bool){
        if(_burnedToken.get(tokenId)) {
            return false;
        } 
        return super._exists(tokenId);
    }

    /**
     * @dev See {IERC721-ownerOf}.
     */
    function ownerOf(uint256 tokenId)
        public
        view
        virtual
        override
        returns (address)
    {
        if (_burnedToken.get(tokenId)) {
            return address(0);
        }
        else {
            return super.ownerOf(tokenId);
        }
    }

    /**
     * @dev See {IERC721Enumerable-totalSupply}.
     */
    function totalSupply() public view virtual override returns (uint256) {
        return _currentIndex - _burned() - _startTokenId();
    }

    /**
     * @dev Returns number of token burned.
     */
    function _burned() internal view returns (uint256 burned){
        return _burnedToken.popCount( _startTokenId(), _totalMinted());
    }
}

// SPDX-License-Identifier: MIT
// OpenZeppelin Contracts (last updated v5.0.0) (utils/structs/EnumerableMap.sol)
// This file was procedurally generated from scripts/generate/templates/EnumerableMap.js.

pragma solidity ^0.8.20;

import {EnumerableSet} from "./EnumerableSet.sol";

/**
 * @dev Library for managing an enumerable variant of Solidity's
 * https://solidity.readthedocs.io/en/latest/types.html#mapping-types[`mapping`]
 * type.
 *
 * Maps have the following properties:
 *
 * - Entries are added, removed, and checked for existence in constant time
 * (O(1)).
 * - Entries are enumerated in O(n). No guarantees are made on the ordering.
 *
 * ```solidity
 * contract Example {
 *     // Add the library methods
 *     using EnumerableMap for EnumerableMap.UintToAddressMap;
 *
 *     // Declare a set state variable
 *     EnumerableMap.UintToAddressMap private myMap;
 * }
 * ```
 *
 * The following map types are supported:
 *
 * - `uint256 -> address` (`UintToAddressMap`) since v3.0.0
 * - `address -> uint256` (`AddressToUintMap`) since v4.6.0
 * - `bytes32 -> bytes32` (`Bytes32ToBytes32Map`) since v4.6.0
 * - `uint256 -> uint256` (`UintToUintMap`) since v4.7.0
 * - `bytes32 -> uint256` (`Bytes32ToUintMap`) since v4.7.0
 *
 * [WARNING]
 * ====
 * Trying to delete such a structure from storage will likely result in data corruption, rendering the structure
 * unusable.
 * See https://github.com/ethereum/solidity/pull/11843[ethereum/solidity#11843] for more info.
 *
 * In order to clean an EnumerableMap, you can either remove all elements one by one or create a fresh instance using an
 * array of EnumerableMap.
 * ====
 */
library EnumerableMap {
    using EnumerableSet for EnumerableSet.Bytes32Set;

    // To implement this library for multiple types with as little code repetition as possible, we write it in
    // terms of a generic Map type with bytes32 keys and values. The Map implementation uses private functions,
    // and user-facing implementations such as `UintToAddressMap` are just wrappers around the underlying Map.
    // This means that we can only create new EnumerableMaps for types that fit in bytes32.

    /**
     * @dev Query for a nonexistent map key.
     */
    error EnumerableMapNonexistentKey(bytes32 key);

    struct Bytes32ToBytes32Map {
        // Storage of keys
        EnumerableSet.Bytes32Set _keys;
        mapping(bytes32 key => bytes32) _values;
    }

    /**
     * @dev Adds a key-value pair to a map, or updates the value for an existing
     * key. O(1).
     *
     * Returns true if the key was added to the map, that is if it was not
     * already present.
     */
    function set(Bytes32ToBytes32Map storage map, bytes32 key, bytes32 value) internal returns (bool) {
        map._values[key] = value;
        return map._keys.add(key);
    }

    /**
     * @dev Removes a key-value pair from a map. O(1).
     *
     * Returns true if the key was removed from the map, that is if it was present.
     */
    function remove(Bytes32ToBytes32Map storage map, bytes32 key) internal returns (bool) {
        delete map._values[key];
        return map._keys.remove(key);
    }

    /**
     * @dev Returns true if the key is in the map. O(1).
     */
    function contains(Bytes32ToBytes32Map storage map, bytes32 key) internal view returns (bool) {
        return map._keys.contains(key);
    }

    /**
     * @dev Returns the number of key-value pairs in the map. O(1).
     */
    function length(Bytes32ToBytes32Map storage map) internal view returns (uint256) {
        return map._keys.length();
    }

    /**
     * @dev Returns the key-value pair stored at position `index` in the map. O(1).
     *
     * Note that there are no guarantees on the ordering of entries inside the
     * array, and it may change when more entries are added or removed.
     *
     * Requirements:
     *
     * - `index` must be strictly less than {length}.
     */
    function at(Bytes32ToBytes32Map storage map, uint256 index) internal view returns (bytes32, bytes32) {
        bytes32 key = map._keys.at(index);
        return (key, map._values[key]);
    }

    /**
     * @dev Tries to returns the value associated with `key`. O(1).
     * Does not revert if `key` is not in the map.
     */
    function tryGet(Bytes32ToBytes32Map storage map, bytes32 key) internal view returns (bool, bytes32) {
        bytes32 value = map._values[key];
        if (value == bytes32(0)) {
            return (contains(map, key), bytes32(0));
        } else {
            return (true, value);
        }
    }

    /**
     * @dev Returns the value associated with `key`. O(1).
     *
     * Requirements:
     *
     * - `key` must be in the map.
     */
    function get(Bytes32ToBytes32Map storage map, bytes32 key) internal view returns (bytes32) {
        bytes32 value = map._values[key];
        if (value == 0 && !contains(map, key)) {
            revert EnumerableMapNonexistentKey(key);
        }
        return value;
    }

    /**
     * @dev Return the an array containing all the keys
     *
     * WARNING: This operation will copy the entire storage to memory, which can be quite expensive. This is designed
     * to mostly be used by view accessors that are queried without any gas fees. Developers should keep in mind that
     * this function has an unbounded cost, and using it as part of a state-changing function may render the function
     * uncallable if the map grows to a point where copying to memory consumes too much gas to fit in a block.
     */
    function keys(Bytes32ToBytes32Map storage map) internal view returns (bytes32[] memory) {
        return map._keys.values();
    }

    // UintToUintMap

    struct UintToUintMap {
        Bytes32ToBytes32Map _inner;
    }

    /**
     * @dev Adds a key-value pair to a map, or updates the value for an existing
     * key. O(1).
     *
     * Returns true if the key was added to the map, that is if it was not
     * already present.
     */
    function set(UintToUintMap storage map, uint256 key, uint256 value) internal returns (bool) {
        return set(map._inner, bytes32(key), bytes32(value));
    }

    /**
     * @dev Removes a value from a map. O(1).
     *
     * Returns true if the key was removed from the map, that is if it was present.
     */
    function remove(UintToUintMap storage map, uint256 key) internal returns (bool) {
        return remove(map._inner, bytes32(key));
    }

    /**
     * @dev Returns true if the key is in the map. O(1).
     */
    function contains(UintToUintMap storage map, uint256 key) internal view returns (bool) {
        return contains(map._inner, bytes32(key));
    }

    /**
     * @dev Returns the number of elements in the map. O(1).
     */
    function length(UintToUintMap storage map) internal view returns (uint256) {
        return length(map._inner);
    }

    /**
     * @dev Returns the element stored at position `index` in the map. O(1).
     * Note that there are no guarantees on the ordering of values inside the
     * array, and it may change when more values are added or removed.
     *
     * Requirements:
     *
     * - `index` must be strictly less than {length}.
     */
    function at(UintToUintMap storage map, uint256 index) internal view returns (uint256, uint256) {
        (bytes32 key, bytes32 value) = at(map._inner, index);
        return (uint256(key), uint256(value));
    }

    /**
     * @dev Tries to returns the value associated with `key`. O(1).
     * Does not revert if `key` is not in the map.
     */
    function tryGet(UintToUintMap storage map, uint256 key) internal view returns (bool, uint256) {
        (bool success, bytes32 value) = tryGet(map._inner, bytes32(key));
        return (success, uint256(value));
    }

    /**
     * @dev Returns the value associated with `key`. O(1).
     *
     * Requirements:
     *
     * - `key` must be in the map.
     */
    function get(UintToUintMap storage map, uint256 key) internal view returns (uint256) {
        return uint256(get(map._inner, bytes32(key)));
    }

    /**
     * @dev Return the an array containing all the keys
     *
     * WARNING: This operation will copy the entire storage to memory, which can be quite expensive. This is designed
     * to mostly be used by view accessors that are queried without any gas fees. Developers should keep in mind that
     * this function has an unbounded cost, and using it as part of a state-changing function may render the function
     * uncallable if the map grows to a point where copying to memory consumes too much gas to fit in a block.
     */
    function keys(UintToUintMap storage map) internal view returns (uint256[] memory) {
        bytes32[] memory store = keys(map._inner);
        uint256[] memory result;

        /// @solidity memory-safe-assembly
        assembly {
            result := store
        }

        return result;
    }

    // UintToAddressMap

    struct UintToAddressMap {
        Bytes32ToBytes32Map _inner;
    }

    /**
     * @dev Adds a key-value pair to a map, or updates the value for an existing
     * key. O(1).
     *
     * Returns true if the key was added to the map, that is if it was not
     * already present.
     */
    function set(UintToAddressMap storage map, uint256 key, address value) internal returns (bool) {
        return set(map._inner, bytes32(key), bytes32(uint256(uint160(value))));
    }

    /**
     * @dev Removes a value from a map. O(1).
     *
     * Returns true if the key was removed from the map, that is if it was present.
     */
    function remove(UintToAddressMap storage map, uint256 key) internal returns (bool) {
        return remove(map._inner, bytes32(key));
    }

    /**
     * @dev Returns true if the key is in the map. O(1).
     */
    function contains(UintToAddressMap storage map, uint256 key) internal view returns (bool) {
        return contains(map._inner, bytes32(key));
    }

    /**
     * @dev Returns the number of elements in the map. O(1).
     */
    function length(UintToAddressMap storage map) internal view returns (uint256) {
        return length(map._inner);
    }

    /**
     * @dev Returns the element stored at position `index` in the map. O(1).
     * Note that there are no guarantees on the ordering of values inside the
     * array, and it may change when more values are added or removed.
     *
     * Requirements:
     *
     * - `index` must be strictly less than {length}.
     */
    function at(UintToAddressMap storage map, uint256 index) internal view returns (uint256, address) {
        (bytes32 key, bytes32 value) = at(map._inner, index);
        return (uint256(key), address(uint160(uint256(value))));
    }

    /**
     * @dev Tries to returns the value associated with `key`. O(1).
     * Does not revert if `key` is not in the map.
     */
    function tryGet(UintToAddressMap storage map, uint256 key) internal view returns (bool, address) {
        (bool success, bytes32 value) = tryGet(map._inner, bytes32(key));
        return (success, address(uint160(uint256(value))));
    }

    /**
     * @dev Returns the value associated with `key`. O(1).
     *
     * Requirements:
     *
     * - `key` must be in the map.
     */
    function get(UintToAddressMap storage map, uint256 key) internal view returns (address) {
        return address(uint160(uint256(get(map._inner, bytes32(key)))));
    }

    /**
     * @dev Return the an array containing all the keys
     *
     * WARNING: This operation will copy the entire storage to memory, which can be quite expensive. This is designed
     * to mostly be used by view accessors that are queried without any gas fees. Developers should keep in mind that
     * this function has an unbounded cost, and using it as part of a state-changing function may render the function
     * uncallable if the map grows to a point where copying to memory consumes too much gas to fit in a block.
     */
    function keys(UintToAddressMap storage map) internal view returns (uint256[] memory) {
        bytes32[] memory store = keys(map._inner);
        uint256[] memory result;

        /// @solidity memory-safe-assembly
        assembly {
            result := store
        }

        return result;
    }

    // AddressToUintMap

    struct AddressToUintMap {
        Bytes32ToBytes32Map _inner;
    }

    /**
     * @dev Adds a key-value pair to a map, or updates the value for an existing
     * key. O(1).
     *
     * Returns true if the key was added to the map, that is if it was not
     * already present.
     */
    function set(AddressToUintMap storage map, address key, uint256 value) internal returns (bool) {
        return set(map._inner, bytes32(uint256(uint160(key))), bytes32(value));
    }

    /**
     * @dev Removes a value from a map. O(1).
     *
     * Returns true if the key was removed from the map, that is if it was present.
     */
    function remove(AddressToUintMap storage map, address key) internal returns (bool) {
        return remove(map._inner, bytes32(uint256(uint160(key))));
    }

    /**
     * @dev Returns true if the key is in the map. O(1).
     */
    function contains(AddressToUintMap storage map, address key) internal view returns (bool) {
        return contains(map._inner, bytes32(uint256(uint160(key))));
    }

    /**
     * @dev Returns the number of elements in the map. O(1).
     */
    function length(AddressToUintMap storage map) internal view returns (uint256) {
        return length(map._inner);
    }

    /**
     * @dev Returns the element stored at position `index` in the map. O(1).
     * Note that there are no guarantees on the ordering of values inside the
     * array, and it may change when more values are added or removed.
     *
     * Requirements:
     *
     * - `index` must be strictly less than {length}.
     */
    function at(AddressToUintMap storage map, uint256 index) internal view returns (address, uint256) {
        (bytes32 key, bytes32 value) = at(map._inner, index);
        return (address(uint160(uint256(key))), uint256(value));
    }

    /**
     * @dev Tries to returns the value associated with `key`. O(1).
     * Does not revert if `key` is not in the map.
     */
    function tryGet(AddressToUintMap storage map, address key) internal view returns (bool, uint256) {
        (bool success, bytes32 value) = tryGet(map._inner, bytes32(uint256(uint160(key))));
        return (success, uint256(value));
    }

    /**
     * @dev Returns the value associated with `key`. O(1).
     *
     * Requirements:
     *
     * - `key` must be in the map.
     */
    function get(AddressToUintMap storage map, address key) internal view returns (uint256) {
        return uint256(get(map._inner, bytes32(uint256(uint160(key)))));
    }

    /**
     * @dev Return the an array containing all the keys
     *
     * WARNING: This operation will copy the entire storage to memory, which can be quite expensive. This is designed
     * to mostly be used by view accessors that are queried without any gas fees. Developers should keep in mind that
     * this function has an unbounded cost, and using it as part of a state-changing function may render the function
     * uncallable if the map grows to a point where copying to memory consumes too much gas to fit in a block.
     */
    function keys(AddressToUintMap storage map) internal view returns (address[] memory) {
        bytes32[] memory store = keys(map._inner);
        address[] memory result;

        /// @solidity memory-safe-assembly
        assembly {
            result := store
        }

        return result;
    }

    // Bytes32ToUintMap

    struct Bytes32ToUintMap {
        Bytes32ToBytes32Map _inner;
    }

    /**
     * @dev Adds a key-value pair to a map, or updates the value for an existing
     * key. O(1).
     *
     * Returns true if the key was added to the map, that is if it was not
     * already present.
     */
    function set(Bytes32ToUintMap storage map, bytes32 key, uint256 value) internal returns (bool) {
        return set(map._inner, key, bytes32(value));
    }

    /**
     * @dev Removes a value from a map. O(1).
     *
     * Returns true if the key was removed from the map, that is if it was present.
     */
    function remove(Bytes32ToUintMap storage map, bytes32 key) internal returns (bool) {
        return remove(map._inner, key);
    }

    /**
     * @dev Returns true if the key is in the map. O(1).
     */
    function contains(Bytes32ToUintMap storage map, bytes32 key) internal view returns (bool) {
        return contains(map._inner, key);
    }

    /**
     * @dev Returns the number of elements in the map. O(1).
     */
    function length(Bytes32ToUintMap storage map) internal view returns (uint256) {
        return length(map._inner);
    }

    /**
     * @dev Returns the element stored at position `index` in the map. O(1).
     * Note that there are no guarantees on the ordering of values inside the
     * array, and it may change when more values are added or removed.
     *
     * Requirements:
     *
     * - `index` must be strictly less than {length}.
     */
    function at(Bytes32ToUintMap storage map, uint256 index) internal view returns (bytes32, uint256) {
        (bytes32 key, bytes32 value) = at(map._inner, index);
        return (key, uint256(value));
    }

    /**
     * @dev Tries to returns the value associated with `key`. O(1).
     * Does not revert if `key` is not in the map.
     */
    function tryGet(Bytes32ToUintMap storage map, bytes32 key) internal view returns (bool, uint256) {
        (bool success, bytes32 value) = tryGet(map._inner, key);
        return (success, uint256(value));
    }

    /**
     * @dev Returns the value associated with `key`. O(1).
     *
     * Requirements:
     *
     * - `key` must be in the map.
     */
    function get(Bytes32ToUintMap storage map, bytes32 key) internal view returns (uint256) {
        return uint256(get(map._inner, key));
    }

    /**
     * @dev Return the an array containing all the keys
     *
     * WARNING: This operation will copy the entire storage to memory, which can be quite expensive. This is designed
     * to mostly be used by view accessors that are queried without any gas fees. Developers should keep in mind that
     * this function has an unbounded cost, and using it as part of a state-changing function may render the function
     * uncallable if the map grows to a point where copying to memory consumes too much gas to fit in a block.
     */
    function keys(Bytes32ToUintMap storage map) internal view returns (bytes32[] memory) {
        bytes32[] memory store = keys(map._inner);
        bytes32[] memory result;

        /// @solidity memory-safe-assembly
        assembly {
            result := store
        }

        return result;
    }
}

// SPDX-License-Identifier: MIT
// OpenZeppelin Contracts (last updated v5.0.0) (utils/structs/EnumerableSet.sol)
// This file was procedurally generated from scripts/generate/templates/EnumerableSet.js.

pragma solidity ^0.8.20;

/**
 * @dev Library for managing
 * https://en.wikipedia.org/wiki/Set_(abstract_data_type)[sets] of primitive
 * types.
 *
 * Sets have the following properties:
 *
 * - Elements are added, removed, and checked for existence in constant time
 * (O(1)).
 * - Elements are enumerated in O(n). No guarantees are made on the ordering.
 *
 * ```solidity
 * contract Example {
 *     // Add the library methods
 *     using EnumerableSet for EnumerableSet.AddressSet;
 *
 *     // Declare a set state variable
 *     EnumerableSet.AddressSet private mySet;
 * }
 * ```
 *
 * As of v3.3.0, sets of type `bytes32` (`Bytes32Set`), `address` (`AddressSet`)
 * and `uint256` (`UintSet`) are supported.
 *
 * [WARNING]
 * ====
 * Trying to delete such a structure from storage will likely result in data corruption, rendering the structure
 * unusable.
 * See https://github.com/ethereum/solidity/pull/11843[ethereum/solidity#11843] for more info.
 *
 * In order to clean an EnumerableSet, you can either remove all elements one by one or create a fresh instance using an
 * array of EnumerableSet.
 * ====
 */
library EnumerableSet {
    // To implement this library for multiple types with as little code
    // repetition as possible, we write it in terms of a generic Set type with
    // bytes32 values.
    // The Set implementation uses private functions, and user-facing
    // implementations (such as AddressSet) are just wrappers around the
    // underlying Set.
    // This means that we can only create new EnumerableSets for types that fit
    // in bytes32.

    struct Set {
        // Storage of set values
        bytes32[] _values;
        // Position is the index of the value in the `values` array plus 1.
        // Position 0 is used to mean a value is not in the set.
        mapping(bytes32 value => uint256) _positions;
    }

    /**
     * @dev Add a value to a set. O(1).
     *
     * Returns true if the value was added to the set, that is if it was not
     * already present.
     */
    function _add(Set storage set, bytes32 value) private returns (bool) {
        if (!_contains(set, value)) {
            set._values.push(value);
            // The value is stored at length-1, but we add 1 to all indexes
            // and use 0 as a sentinel value
            set._positions[value] = set._values.length;
            return true;
        } else {
            return false;
        }
    }

    /**
     * @dev Removes a value from a set. O(1).
     *
     * Returns true if the value was removed from the set, that is if it was
     * present.
     */
    function _remove(Set storage set, bytes32 value) private returns (bool) {
        // We cache the value's position to prevent multiple reads from the same storage slot
        uint256 position = set._positions[value];

        if (position != 0) {
            // Equivalent to contains(set, value)
            // To delete an element from the _values array in O(1), we swap the element to delete with the last one in
            // the array, and then remove the last element (sometimes called as 'swap and pop').
            // This modifies the order of the array, as noted in {at}.

            uint256 valueIndex = position - 1;
            uint256 lastIndex = set._values.length - 1;

            if (valueIndex != lastIndex) {
                bytes32 lastValue = set._values[lastIndex];

                // Move the lastValue to the index where the value to delete is
                set._values[valueIndex] = lastValue;
                // Update the tracked position of the lastValue (that was just moved)
                set._positions[lastValue] = position;
            }

            // Delete the slot where the moved value was stored
            set._values.pop();

            // Delete the tracked position for the deleted slot
            delete set._positions[value];

            return true;
        } else {
            return false;
        }
    }

    /**
     * @dev Returns true if the value is in the set. O(1).
     */
    function _contains(Set storage set, bytes32 value) private view returns (bool) {
        return set._positions[value] != 0;
    }

    /**
     * @dev Returns the number of values on the set. O(1).
     */
    function _length(Set storage set) private view returns (uint256) {
        return set._values.length;
    }

    /**
     * @dev Returns the value stored at position `index` in the set. O(1).
     *
     * Note that there are no guarantees on the ordering of values inside the
     * array, and it may change when more values are added or removed.
     *
     * Requirements:
     *
     * - `index` must be strictly less than {length}.
     */
    function _at(Set storage set, uint256 index) private view returns (bytes32) {
        return set._values[index];
    }

    /**
     * @dev Return the entire set in an array
     *
     * WARNING: This operation will copy the entire storage to memory, which can be quite expensive. This is designed
     * to mostly be used by view accessors that are queried without any gas fees. Developers should keep in mind that
     * this function has an unbounded cost, and using it as part of a state-changing function may render the function
     * uncallable if the set grows to a point where copying to memory consumes too much gas to fit in a block.
     */
    function _values(Set storage set) private view returns (bytes32[] memory) {
        return set._values;
    }

    // Bytes32Set

    struct Bytes32Set {
        Set _inner;
    }

    /**
     * @dev Add a value to a set. O(1).
     *
     * Returns true if the value was added to the set, that is if it was not
     * already present.
     */
    function add(Bytes32Set storage set, bytes32 value) internal returns (bool) {
        return _add(set._inner, value);
    }

    /**
     * @dev Removes a value from a set. O(1).
     *
     * Returns true if the value was removed from the set, that is if it was
     * present.
     */
    function remove(Bytes32Set storage set, bytes32 value) internal returns (bool) {
        return _remove(set._inner, value);
    }

    /**
     * @dev Returns true if the value is in the set. O(1).
     */
    function contains(Bytes32Set storage set, bytes32 value) internal view returns (bool) {
        return _contains(set._inner, value);
    }

    /**
     * @dev Returns the number of values in the set. O(1).
     */
    function length(Bytes32Set storage set) internal view returns (uint256) {
        return _length(set._inner);
    }

    /**
     * @dev Returns the value stored at position `index` in the set. O(1).
     *
     * Note that there are no guarantees on the ordering of values inside the
     * array, and it may change when more values are added or removed.
     *
     * Requirements:
     *
     * - `index` must be strictly less than {length}.
     */
    function at(Bytes32Set storage set, uint256 index) internal view returns (bytes32) {
        return _at(set._inner, index);
    }

    /**
     * @dev Return the entire set in an array
     *
     * WARNING: This operation will copy the entire storage to memory, which can be quite expensive. This is designed
     * to mostly be used by view accessors that are queried without any gas fees. Developers should keep in mind that
     * this function has an unbounded cost, and using it as part of a state-changing function may render the function
     * uncallable if the set grows to a point where copying to memory consumes too much gas to fit in a block.
     */
    function values(Bytes32Set storage set) internal view returns (bytes32[] memory) {
        bytes32[] memory store = _values(set._inner);
        bytes32[] memory result;

        /// @solidity memory-safe-assembly
        assembly {
            result := store
        }

        return result;
    }

    // AddressSet

    struct AddressSet {
        Set _inner;
    }

    /**
     * @dev Add a value to a set. O(1).
     *
     * Returns true if the value was added to the set, that is if it was not
     * already present.
     */
    function add(AddressSet storage set, address value) internal returns (bool) {
        return _add(set._inner, bytes32(uint256(uint160(value))));
    }

    /**
     * @dev Removes a value from a set. O(1).
     *
     * Returns true if the value was removed from the set, that is if it was
     * present.
     */
    function remove(AddressSet storage set, address value) internal returns (bool) {
        return _remove(set._inner, bytes32(uint256(uint160(value))));
    }

    /**
     * @dev Returns true if the value is in the set. O(1).
     */
    function contains(AddressSet storage set, address value) internal view returns (bool) {
        return _contains(set._inner, bytes32(uint256(uint160(value))));
    }

    /**
     * @dev Returns the number of values in the set. O(1).
     */
    function length(AddressSet storage set) internal view returns (uint256) {
        return _length(set._inner);
    }

    /**
     * @dev Returns the value stored at position `index` in the set. O(1).
     *
     * Note that there are no guarantees on the ordering of values inside the
     * array, and it may change when more values are added or removed.
     *
     * Requirements:
     *
     * - `index` must be strictly less than {length}.
     */
    function at(AddressSet storage set, uint256 index) internal view returns (address) {
        return address(uint160(uint256(_at(set._inner, index))));
    }

    /**
     * @dev Return the entire set in an array
     *
     * WARNING: This operation will copy the entire storage to memory, which can be quite expensive. This is designed
     * to mostly be used by view accessors that are queried without any gas fees. Developers should keep in mind that
     * this function has an unbounded cost, and using it as part of a state-changing function may render the function
     * uncallable if the set grows to a point where copying to memory consumes too much gas to fit in a block.
     */
    function values(AddressSet storage set) internal view returns (address[] memory) {
        bytes32[] memory store = _values(set._inner);
        address[] memory result;

        /// @solidity memory-safe-assembly
        assembly {
            result := store
        }

        return result;
    }

    // UintSet

    struct UintSet {
        Set _inner;
    }

    /**
     * @dev Add a value to a set. O(1).
     *
     * Returns true if the value was added to the set, that is if it was not
     * already present.
     */
    function add(UintSet storage set, uint256 value) internal returns (bool) {
        return _add(set._inner, bytes32(value));
    }

    /**
     * @dev Removes a value from a set. O(1).
     *
     * Returns true if the value was removed from the set, that is if it was
     * present.
     */
    function remove(UintSet storage set, uint256 value) internal returns (bool) {
        return _remove(set._inner, bytes32(value));
    }

    /**
     * @dev Returns true if the value is in the set. O(1).
     */
    function contains(UintSet storage set, uint256 value) internal view returns (bool) {
        return _contains(set._inner, bytes32(value));
    }

    /**
     * @dev Returns the number of values in the set. O(1).
     */
    function length(UintSet storage set) internal view returns (uint256) {
        return _length(set._inner);
    }

    /**
     * @dev Returns the value stored at position `index` in the set. O(1).
     *
     * Note that there are no guarantees on the ordering of values inside the
     * array, and it may change when more values are added or removed.
     *
     * Requirements:
     *
     * - `index` must be strictly less than {length}.
     */
    function at(UintSet storage set, uint256 index) internal view returns (uint256) {
        return uint256(_at(set._inner, index));
    }

    /**
     * @dev Return the entire set in an array
     *
     * WARNING: This operation will copy the entire storage to memory, which can be quite expensive. This is designed
     * to mostly be used by view accessors that are queried without any gas fees. Developers should keep in mind that
     * this function has an unbounded cost, and using it as part of a state-changing function may render the function
     * uncallable if the set grows to a point where copying to memory consumes too much gas to fit in a block.
     */
    function values(UintSet storage set) internal view returns (uint256[] memory) {
        bytes32[] memory store = _values(set._inner);
        uint256[] memory result;

        /// @solidity memory-safe-assembly
        assembly {
            result := store
        }

        return result;
    }
}

// SPDX-License-Identifier: MIT
// OpenZeppelin Contracts (last updated v4.7.0) (utils/escrow/Escrow.sol)

pragma solidity ^0.8.0;

import {Ownable} from "@openzeppelin/contracts/access/Ownable.sol";
import {Address} from "@openzeppelin/contracts/utils/Address.sol";

/**
 * @title Escrow
 * @dev Base escrow contract, holds funds designated for a payee until they
 * withdraw them.
 *
 * Intended usage: This contract (and derived escrow contracts) should be a
 * standalone contract, that only interacts with the contract that instantiated
 * it. That way, it is guaranteed that all Ether will be handled according to
 * the `Escrow` rules, and there is no need to check for payable functions or
 * transfers in the inheritance tree. The contract that uses the escrow as its
 * payment method should be its owner, and provide public methods redirecting
 * to the escrow's deposit and withdraw.
 */
contract Escrow is Ownable {
    using Address for address payable;

    event Deposited(address indexed payee, uint256 weiAmount);
    event Withdrawn(address indexed payee, uint256 weiAmount);

    mapping(address => uint256) private _deposits;

    /// @dev modify this to support Ownable v5.0
    constructor() Ownable(msg.sender) {}

    function depositsOf(address payee) public view returns (uint256) {
        return _deposits[payee];
    }

    /**
     * @dev Stores the sent amount as credit to be withdrawn.
     * @param payee The destination address of the funds.
     *
     * Emits a {Deposited} event.
     */
    function deposit(address payee) public payable virtual onlyOwner {
        uint256 amount = msg.value;
        _deposits[payee] += amount;
        emit Deposited(payee, amount);
    }

    /**
     * @dev Withdraw accumulated balance for a payee, forwarding all gas to the
     * recipient.
     *
     * WARNING: Forwarding all gas opens the door to reentrancy vulnerabilities.
     * Make sure you trust the recipient, or are either following the
     * checks-effects-interactions pattern or using {ReentrancyGuard}.
     *
     * @param payee The address whose funds will be withdrawn and transferred to.
     *
     * Emits a {Withdrawn} event.
     */
    function withdraw(address payable payee) public virtual onlyOwner {
        uint256 payment = _deposits[payee];

        _deposits[payee] = 0;

        payee.sendValue(payment);

        emit Withdrawn(payee, payment);
    }
}

// SPDX-License-Identifier: MIT

pragma solidity ^0.8.0;

/**
 * @dev Interface of ERC721Psi.
 */
interface IERC721Psi {
    /**
     * The caller must own the token or be an approved operator.
     */
    error ApprovalCallerNotOwnerNorApproved();

    /**
     * The token does not exist.
     */
    error ApprovalQueryForNonexistentToken();

    /**
     * Cannot query the balance for the zero address.
     */
    error BalanceQueryForZeroAddress();

    /**
     * Cannot mint to the zero address.
     */
    error MintToZeroAddress();

    /**
     * The quantity of tokens minted must be more than zero.
     */
    error MintZeroQuantity();

    /**
     * The token does not exist.
     */
    error OwnerQueryForNonexistentToken();

    /**
     * The caller must own the token or be an approved operator.
     */
    error TransferCallerNotOwnerNorApproved();

    /**
     * The token must be owned by `from`.
     */
    error TransferFromIncorrectOwner();

    /**
     * Cannot safely transfer to a contract that does not implement the
     * ERC721Receiver interface.
     */
    error TransferToNonERC721ReceiverImplementer();

    /**
     * Cannot transfer to the zero address.
     */
    error TransferToZeroAddress();

    /**
     * The token does not exist.
     */
    error URIQueryForNonexistentToken();


    // =============================================================
    //                         TOKEN COUNTERS
    // =============================================================

    /**
     * @dev Returns the total number of tokens in existence.
     * Burned tokens will reduce the count.
     * To get the total number of tokens minted, please see {_totalMinted}.
     */
    function totalSupply() external view returns (uint256);

    // =============================================================
    //                            IERC165
    // =============================================================

    /**
     * @dev Returns true if this contract implements the interface defined by
     * `interfaceId`. See the corresponding
     * [EIP section](https://eips.ethereum.org/EIPS/eip-165#how-interfaces-are-identified)
     * to learn more about how these ids are created.
     *
     * This function call must use less than 30000 gas.
     */
    function supportsInterface(bytes4 interfaceId) external view returns (bool);

    // =============================================================
    //                            IERC721
    // =============================================================

    /**
     * @dev Emitted when `tokenId` token is transferred from `from` to `to`.
     */
    event Transfer(address indexed from, address indexed to, uint256 indexed tokenId);

    /**
     * @dev Emitted when `owner` enables `approved` to manage the `tokenId` token.
     */
    event Approval(address indexed owner, address indexed approved, uint256 indexed tokenId);

    /**
     * @dev Emitted when `owner` enables or disables
     * (`approved`) `operator` to manage all of its assets.
     */
    event ApprovalForAll(address indexed owner, address indexed operator, bool approved);

    /**
     * @dev Returns the number of tokens in `owner`'s account.
     */
    function balanceOf(address owner) external view returns (uint256 balance);

    /**
     * @dev Returns the owner of the `tokenId` token.
     *
     * Requirements:
     *
     * - `tokenId` must exist.
     */
    function ownerOf(uint256 tokenId) external view returns (address owner);

    /**
     * @dev Safely transfers `tokenId` token from `from` to `to`,
     * checking first that contract recipients are aware of the ERC721 protocol
     * to prevent tokens from being forever locked.
     *
     * Requirements:
     *
     * - `from` cannot be the zero address.
     * - `to` cannot be the zero address.
     * - `tokenId` token must exist and be owned by `from`.
     * - If the caller is not `from`, it must be have been allowed to move
     * this token by either {approve} or {setApprovalForAll}.
     * - If `to` refers to a smart contract, it must implement
     * {IERC721Receiver-onERC721Received}, which is called upon a safe transfer.
     *
     * Emits a {Transfer} event.
     */
    function safeTransferFrom(
        address from,
        address to,
        uint256 tokenId,
        bytes calldata data
    ) external payable;

    /**
     * @dev Equivalent to `safeTransferFrom(from, to, tokenId, '')`.
     */
    function safeTransferFrom(
        address from,
        address to,
        uint256 tokenId
    ) external payable;

    /**
     * @dev Transfers `tokenId` from `from` to `to`.
     *
     * WARNING: Usage of this method is discouraged, use {safeTransferFrom}
     * whenever possible.
     *
     * Requirements:
     *
     * - `from` cannot be the zero address.
     * - `to` cannot be the zero address.
     * - `tokenId` token must be owned by `from`.
     * - If the caller is not `from`, it must be approved to move this token
     * by either {approve} or {setApprovalForAll}.
     *
     * Emits a {Transfer} event.
     */
    function transferFrom(
        address from,
        address to,
        uint256 tokenId
    ) external payable;

    /**
     * @dev Gives permission to `to` to transfer `tokenId` token to another account.
     * The approval is cleared when the token is transferred.
     *
     * Only a single account can be approved at a time, so approving the
     * zero address clears previous approvals.
     *
     * Requirements:
     *
     * - The caller must own the token or be an approved operator.
     * - `tokenId` must exist.
     *
     * Emits an {Approval} event.
     */
    function approve(address to, uint256 tokenId) external payable;

    /**
     * @dev Approve or remove `operator` as an operator for the caller.
     * Operators can call {transferFrom} or {safeTransferFrom}
     * for any token owned by the caller.
     *
     * Requirements:
     *
     * - The `operator` cannot be the caller.
     *
     * Emits an {ApprovalForAll} event.
     */
    function setApprovalForAll(address operator, bool _approved) external;

    /**
     * @dev Returns the account approved for `tokenId` token.
     *
     * Requirements:
     *
     * - `tokenId` must exist.
     */
    function getApproved(uint256 tokenId) external view returns (address operator);

    /**
     * @dev Returns if the `operator` is allowed to manage all of the assets of `owner`.
     *
     * See {setApprovalForAll}.
     */
    function isApprovedForAll(address owner, address operator) external view returns (bool);

    // =============================================================
    //                        IERC721Metadata
    // =============================================================

    /**
     * @dev Returns the token collection name.
     */
    function name() external view returns (string memory);

    /**
     * @dev Returns the token collection symbol.
     */
    function symbol() external view returns (string memory);

    /**
     * @dev Returns the Uniform Resource Identifier (URI) for `tokenId` token.
     */
    function tokenURI(uint256 tokenId) external view returns (string memory);
}

// SPDX-License-Identifier: MIT
pragma solidity ^0.8.4;

/// @notice Library for bit twiddling and boolean operations.
/// @author Solady (https://github.com/vectorized/solady/blob/main/src/utils/LibBit.sol)
/// @author Inspired by (https://graphics.stanford.edu/~seander/bithacks.html)
library LibBit {
    /*´:°•.°+.*•´.*:˚.°*.˚•´.°:°•.°•.*•´.*:˚.°*.˚•´.°:°•.°+.*•´.*:*/
    /*                  BIT TWIDDLING OPERATIONS                  */
    /*.•°:°.´+˚.*°.˚:*.´•*.+°.•°:´*.´•*.•°.•°:°.´:•˚°.*°.˚:*.´+°.•*/

    /// @dev Find last set.
    /// Returns the index of the most significant bit of `x`,
    /// counting from the least significant bit position.
    /// If `x` is zero, returns 256.
    function fls(uint256 x) internal pure returns (uint256 r) {
        /// @solidity memory-safe-assembly
        assembly {
            r := or(shl(8, iszero(x)), shl(7, lt(0xffffffffffffffffffffffffffffffff, x)))
            r := or(r, shl(6, lt(0xffffffffffffffff, shr(r, x))))
            r := or(r, shl(5, lt(0xffffffff, shr(r, x))))
            r := or(r, shl(4, lt(0xffff, shr(r, x))))
            r := or(r, shl(3, lt(0xff, shr(r, x))))
            // forgefmt: disable-next-item
            r := or(r, byte(and(0x1f, shr(shr(r, x), 0x8421084210842108cc6318c6db6d54be)),
                0x0706060506020504060203020504030106050205030304010505030400000000))
        }
    }

    /// @dev Count leading zeros.
    /// Returns the number of zeros preceding the most significant one bit.
    /// If `x` is zero, returns 256.
    function clz(uint256 x) internal pure returns (uint256 r) {
        /// @solidity memory-safe-assembly
        assembly {
            r := shl(7, lt(0xffffffffffffffffffffffffffffffff, x))
            r := or(r, shl(6, lt(0xffffffffffffffff, shr(r, x))))
            r := or(r, shl(5, lt(0xffffffff, shr(r, x))))
            r := or(r, shl(4, lt(0xffff, shr(r, x))))
            r := or(r, shl(3, lt(0xff, shr(r, x))))
            // forgefmt: disable-next-item
            r := add(xor(r, byte(and(0x1f, shr(shr(r, x), 0x8421084210842108cc6318c6db6d54be)),
                0xf8f9f9faf9fdfafbf9fdfcfdfafbfcfef9fafdfafcfcfbfefafafcfbffffffff)), iszero(x))
        }
    }

    /// @dev Find first set.
    /// Returns the index of the least significant bit of `x`,
    /// counting from the least significant bit position.
    /// If `x` is zero, returns 256.
    /// Equivalent to `ctz` (count trailing zeros), which gives
    /// the number of zeros following the least significant one bit.
    function ffs(uint256 x) internal pure returns (uint256 r) {
        /// @solidity memory-safe-assembly
        assembly {
            // Isolate the least significant bit.
            let b := and(x, add(not(x), 1))

            r := or(shl(8, iszero(x)), shl(7, lt(0xffffffffffffffffffffffffffffffff, b)))
            r := or(r, shl(6, lt(0xffffffffffffffff, shr(r, b))))
            r := or(r, shl(5, lt(0xffffffff, shr(r, b))))

            // For the remaining 32 bits, use a De Bruijn lookup.
            // forgefmt: disable-next-item
            r := or(r, byte(and(div(0xd76453e0, shr(r, b)), 0x1f),
                0x001f0d1e100c1d070f090b19131c1706010e11080a1a141802121b1503160405))
        }
    }

    /// @dev Returns the number of set bits in `x`.
    function popCount(uint256 x) internal pure returns (uint256 c) {
        /// @solidity memory-safe-assembly
        assembly {
            let max := not(0)
            let isMax := eq(x, max)
            x := sub(x, and(shr(1, x), div(max, 3)))
            x := add(and(x, div(max, 5)), and(shr(2, x), div(max, 5)))
            x := and(add(x, shr(4, x)), div(max, 17))
            c := or(shl(8, isMax), shr(248, mul(x, div(max, 255))))
        }
    }

    /// @dev Returns whether `x` is a power of 2.
    function isPo2(uint256 x) internal pure returns (bool result) {
        /// @solidity memory-safe-assembly
        assembly {
            // Equivalent to `x && !(x & (x - 1))`.
            result := iszero(add(and(x, sub(x, 1)), iszero(x)))
        }
    }

    /// @dev Returns `x` reversed at the bit level.
    function reverseBits(uint256 x) internal pure returns (uint256 r) {
        /// @solidity memory-safe-assembly
        assembly {
            // Computing masks on-the-fly reduces bytecode size by about 500 bytes.
            let m := not(0)
            r := x
            for { let s := 128 } 1 {} {
                m := xor(m, shl(s, m))
                r := or(and(shr(s, r), m), and(shl(s, r), not(m)))
                s := shr(1, s)
                if iszero(s) { break }
            }
        }
    }

    /// @dev Returns `x` reversed at the byte level.
    function reverseBytes(uint256 x) internal pure returns (uint256 r) {
        /// @solidity memory-safe-assembly
        assembly {
            // Computing masks on-the-fly reduces bytecode size by about 200 bytes.
            let m := not(0)
            r := x
            for { let s := 128 } 1 {} {
                m := xor(m, shl(s, m))
                r := or(and(shr(s, r), m), and(shl(s, r), not(m)))
                s := shr(1, s)
                if eq(s, 4) { break }
            }
        }
    }

    /*´:°•.°+.*•´.*:˚.°*.˚•´.°:°•.°•.*•´.*:˚.°*.˚•´.°:°•.°+.*•´.*:*/
    /*                     BOOLEAN OPERATIONS                     */
    /*.•°:°.´+˚.*°.˚:*.´•*.+°.•°:´*.´•*.•°.•°:°.´:•˚°.*°.˚:*.´+°.•*/

    // A Solidity bool on the stack or memory is represented as a 256-bit word.
    // Non-zero values are true, zero is false.
    // A clean bool is either 0 (false) or 1 (true) under the hood.
    // Usually, if not always, the bool result of a regular Solidity expression,
    // or the argument of a public/external function will be a clean bool.
    // You can usually use the raw variants for more performance.
    // If uncertain, test (best with exact compiler settings).
    // Or use the non-raw variants (compiler can sometimes optimize out the double `iszero`s).

    /// @dev Returns `x & y`. Inputs must be clean.
    function rawAnd(bool x, bool y) internal pure returns (bool z) {
        /// @solidity memory-safe-assembly
        assembly {
            z := and(x, y)
        }
    }

    /// @dev Returns `x & y`.
    function and(bool x, bool y) internal pure returns (bool z) {
        /// @solidity memory-safe-assembly
        assembly {
            z := and(iszero(iszero(x)), iszero(iszero(y)))
        }
    }

    /// @dev Returns `x | y`. Inputs must be clean.
    function rawOr(bool x, bool y) internal pure returns (bool z) {
        /// @solidity memory-safe-assembly
        assembly {
            z := or(x, y)
        }
    }

    /// @dev Returns `x | y`.
    function or(bool x, bool y) internal pure returns (bool z) {
        /// @solidity memory-safe-assembly
        assembly {
            z := or(iszero(iszero(x)), iszero(iszero(y)))
        }
    }

    /// @dev Returns 1 if `b` is true, else 0. Input must be clean.
    function rawToUint(bool b) internal pure returns (uint256 z) {
        /// @solidity memory-safe-assembly
        assembly {
            z := b
        }
    }

    /// @dev Returns 1 if `b` is true, else 0.
    function toUint(bool b) internal pure returns (uint256 z) {
        /// @solidity memory-safe-assembly
        assembly {
            z := iszero(iszero(b))
        }
    }
}

// SPDX-License-Identifier: MIT

pragma solidity ^0.8.23;

import {LibBit} from "solady/src/utils/LibBit.sol";

interface ILibBitSet64Filter {
    function isTokenOwner(address owner, uint256 idx) external view returns (bool);
}

library LibBitSet {

    uint256 public constant NOT_FOUND = type(uint256).max;
    uint256 private constant MAX_MASK = type(uint256).max;
    uint256 private constant MAX_INDEX = 16383;
    uint256 private constant FIXED_LENGTH = 64;
    uint16 public constant MAX_POP_COUNT = 256;
    uint16 private constant MASK_LENGTH = 0xFFFF;
    uint8 private constant MAX_BIT_COUNT = 255;
    uint8 private constant MASK_BIT_COUNT = 0xFF;
    uint8 private constant INDEX_SHIFT = 8;
    uint8 private constant INDEX_MASK = 0xFF;
    uint8 private constant INDEX_NOT_FOUND = 0xFF;
    uint8 private constant OFFSET_BUCKET_FLAGS = 192;

    struct Set {
        uint256 offset;
        uint256 count;
        uint256[2] popCounts;
        uint256[64] map;
    }

    function add(Set storage self,
        uint256 tokenId
    ) internal returns (uint256) {
        uint256 count = self.count;
        unchecked {
            tokenId -= self.offset;
            if (tokenId > MAX_INDEX) return uint16(count);
            uint8 bucket = uint8(tokenId >> INDEX_SHIFT);
            uint256 bitIndex = tokenId & INDEX_MASK;
            uint256 mask = 1 << bitIndex;
            uint256 bitmap = self.map[bucket];
            if ((bitmap & mask) == 0) {
                bitmap |= mask;
                self.map[bucket] = bitmap;
                if (bitmap != MAX_MASK) {
                    _addPopCount(self, bucket, 1);
                }
                count = ((count & ~(1 << (bucket + OFFSET_BUCKET_FLAGS))) ^ (((~(bitmap + 1) & bitmap) >> MAX_BIT_COUNT)
                    << (bucket + OFFSET_BUCKET_FLAGS))) + 1;
                self.count = count;
            }
        }
        return uint16(count);
    }

    function addBatch(Set storage self,
        uint256 startId,
        uint256 amount
    ) internal {
        unchecked {
            startId -= self.offset;
            if (startId > MAX_INDEX) return;
            uint256[2] memory popCounts = self.popCounts;
            uint256 mask = 0;
            uint256 delta = 0;
            uint256 count = self.count + amount;
            uint8 bits = 0;
            uint8 bucket = uint8(startId >> INDEX_SHIFT);
            uint8 shift = uint8(startId & INDEX_MASK);
            while (amount > 0) {
                delta = MAX_POP_COUNT - shift;
                if (amount >= delta) {
                    mask = MAX_MASK << shift;
                    bits = MAX_BIT_COUNT - shift;
                    count |= (1 << (bucket + OFFSET_BUCKET_FLAGS));
                    amount -= delta;
                    shift = 0;
                } else {
                    mask = ((1 << amount) - 1) << shift;
                    bits = uint8(amount);
                    count &= ~(1 << (bucket + OFFSET_BUCKET_FLAGS));
                    amount = 0;
                }
                _addPopCounts(popCounts, bucket, bits);
                self.map[bucket] |= mask;
                bucket++;
            }
            self.popCounts = popCounts;
            self.count = count;
        }
    }

    function remove(Set storage self,
        uint256 tokenId
    ) internal returns (bool) {
        unchecked {
            tokenId -= self.offset;
            uint8 bucket = uint8(tokenId >> INDEX_SHIFT);
            if (bucket >= FIXED_LENGTH) return false;
            uint256 bitmap = self.map[bucket];
            uint256 mask = 1 << (tokenId & INDEX_MASK);
            if ((bitmap & mask) == 0) return false;
            uint256 count = self.count;
            uint256 offset = bucket + OFFSET_BUCKET_FLAGS;
            if (((count >> offset) & 1) == 0) {
                _subPopCount(self, bucket, 1);
            }
            self.count = (count - 1) & ~(1 << offset);
            self.map[bucket] = bitmap & ~mask;
            return true;
        }
    }

    function removeAt(Set storage self,
        uint256 index
    ) internal returns (uint256) {
        uint256 count = self.count;
        if (index >= uint16(count)) return NOT_FOUND;
        uint256[2] memory popCounts = self.popCounts;
        (uint256 bucket, uint16 remaining) = _positionOfIndex(count, popCounts, uint16(index));
        if (bucket == INDEX_NOT_FOUND) return NOT_FOUND;
        uint256 bit;
        uint256 pos;
        uint256 offset;
        uint256 bitmap = self.map[bucket];
        unchecked {
            while (bitmap != 0) {
                bit = bitmap & (~bitmap + 1);
                pos = LibBit.fls(bit);
                if (remaining == 0) {
                    offset = bucket + OFFSET_BUCKET_FLAGS;
                    if (((count >> offset) & 1) == 0) {
                        _subPopCounts(popCounts, uint8(bucket), 1);
                        self.popCounts = popCounts;
                    }
                    self.count = (count - 1) & ~(1 << offset);
                    self.map[bucket] ^= bit;
                    return ((bucket << INDEX_SHIFT) | pos) + self.offset;
                }
                remaining--;
                bitmap ^= bit;
            }
        }
        return NOT_FOUND;
    }

    function contains(Set storage self,
        uint256 tokenId
    ) internal view returns (bool isSet) {
        unchecked {
            tokenId -= self.offset;
            uint256 bucket = tokenId >> INDEX_SHIFT;
            if (bucket >= FIXED_LENGTH) return false;
            uint256 bit = (self.map[bucket] >> (tokenId & INDEX_MASK)) & 1;
            /// @solidity memory-safe-assembly
            assembly {
                isSet := bit
            }
        }
    }

    function at(Set storage self,
        uint256 index
    ) internal view returns (uint256) {
        if (index >= uint16(self.count)) return NOT_FOUND;
        uint256 len = 0;
        uint256 bitmap;
        uint256 bitsCount;
        uint256 remaining;
        uint256 bucket;
        uint256 bit;
        uint256 pos;
        unchecked {
            for (bucket = 0; bucket < FIXED_LENGTH; ++bucket) {
                bitmap = self.map[bucket];
                bitsCount = LibBit.popCount(bitmap);
                if (len + bitsCount > index) {
                    remaining = index - len;
                    while (bitmap != 0) {
                        bit = bitmap & (~bitmap + 1);
                        pos = LibBit.fls(bit);
                        if (remaining == 0) {
                            return ((bucket << INDEX_SHIFT) | pos) + self.offset;
                        }
                        remaining--;
                        bitmap ^= bit;
                    }
                }
                len += bitsCount;
            }
        }
        return NOT_FOUND;
    }

    function findFirst(Set storage self
    ) internal view returns (uint256) {
        if (self.count == 0) return NOT_FOUND;
        uint256 bitmap;
        uint256 lsb;
        unchecked {
            for (uint256 bucket = 0; bucket < FIXED_LENGTH; bucket++) {
                bitmap = self.map[bucket];
                if (bitmap != 0) {
                    lsb = LibBit.ffs(bitmap);
                    return (bucket << INDEX_SHIFT | lsb) + self.offset;
                }
            }
        }
        return NOT_FOUND;
    }

    function findFirstOfOwner(Set storage self,
        address owner,
        ILibBitSet64Filter filter
    ) internal view returns (uint256) {
        uint256 count = self.count;
        if (count == 0) return NOT_FOUND;
        unchecked {
            uint256 offset = self.offset;
            uint256 bitmap;
            uint256 tokenId;
            uint256 pos;
            for (uint256 bucket = 0; bucket < FIXED_LENGTH; bucket++) {
                bitmap = self.map[bucket];
                while (bitmap != 0) {
                    pos = LibBit.ffs(bitmap);
                    tokenId = ((bucket << INDEX_SHIFT) | pos) + offset;
                    if (filter.isTokenOwner(owner, tokenId)) return tokenId;
                    bitmap &= ~(1 << pos);
                }
            }
        }
        return NOT_FOUND;
    }

    function findNearest(Set storage self,
        uint256 index
    ) internal view returns (uint256) {
        if (self.count == 0) return NOT_FOUND;
        unchecked {
            index -= self.offset;
            uint256 bucket = index >> INDEX_SHIFT;
            uint256 bitIndex = index & INDEX_MASK;
            uint256 bitmap = bucket < FIXED_LENGTH ? self.map[bucket] : 0;
            if ((bitmap >> bitIndex) & 1 == 1) {
                return index + self.offset;
            }
            for (uint256 i = bucket; i < FIXED_LENGTH; i++) {
                bitmap = self.map[i];
                if (bitmap != 0) {
                    return (i << INDEX_SHIFT) | LibBit.fls(bitmap) + self.offset;
                }
            }
        }
        return NOT_FOUND;
    }

    function findLast(Set storage self) internal view returns (uint256) {
        if (self.count == 0) return NOT_FOUND;
        for (uint256 bucket = FIXED_LENGTH; bucket > 0; bucket--) {
            if (self.map[bucket - 1] != 0) {
                uint256 bitIndex = LibBit.fls(self.map[bucket - 1]);
                return ((bucket - 1) << INDEX_SHIFT) + bitIndex + self.offset;
            }
        }
        return 0;
    }

    function mapRange(Set storage self
    ) internal view returns (uint256 start, uint256 len) {
        unchecked {
            for (uint256 i = 0; i < FIXED_LENGTH; i++) {
                if (self.map[i] != 0) {
                    start = (i << INDEX_SHIFT) + LibBit.ffs(self.map[i]);
                    break;
                }
            }
            for (uint256 i = FIXED_LENGTH; i > 0; i--) {
                if (self.map[i - 1] != 0) {
                    len = ((i - 1) << INDEX_SHIFT) + LibBit.fls(self.map[i - 1]);
                    break;
                }
            }
            len += 1;
        }
        return (start, len);
    }

    function getRange(Set storage self,
        uint256 start,
        uint256 stop
    ) internal view returns (uint256[] memory) {
        unchecked {
            uint256 count = uint16(self.count);
            stop = (stop > count) ? count : stop;
            uint256 startBucket = (start - self.offset) >> INDEX_SHIFT;
            uint256 endBucket = (stop - self.offset) >> INDEX_SHIFT;
            uint256 arraySize = stop - start + 1;
            uint256[] memory result = new uint256[](arraySize);
            uint256 resultIndex = 0;
            uint256 bucketBits;
            for (uint256 i = startBucket; i <= endBucket && i < FIXED_LENGTH; ++i) {
                bucketBits = self.map[i];
                if (bucketBits == 0) continue;
                for (uint256 j = 0; j < MAX_POP_COUNT; ++j) {
                    uint256 bitIndex = (i << INDEX_SHIFT) + j + self.offset;
                    if (bitIndex < start) continue;
                    if (bitIndex > stop) break;
                    if ((bucketBits & (1 << j)) != 0) {
                        result[resultIndex++] = bitIndex;
                    }
                }
            }
            if (resultIndex < arraySize) {
                assembly {
                    mstore(result, resultIndex)
                }
            }
            return result;
        }
    }

    function rangeLength(Set storage self
    ) internal view returns (uint256) {
        unchecked {
            uint256 bitmap;
            for (uint256 bucket = (FIXED_LENGTH - 1); bucket >= 0; bucket--) {
                bitmap = self.map[bucket];
                if (bitmap != 0) {
                    return (bucket << INDEX_SHIFT) + LibBit.fls(bitmap) + 1;
                }
            }
        }
        return 0;
    }

    function mapLength(Set storage
    ) internal pure returns (uint256) {
        return FIXED_LENGTH;
    }

    function length(Set storage self
    ) internal view returns (uint256) {
        return self.count & MASK_LENGTH;
    }

    function trim(Set storage self
    ) internal {
        uint256 len = self.map.length;
        while (len > 0 && self.map[len - 1] == 0) {
            delete self.map[--len];
        }
    }

    function values(Set storage self
    ) internal view returns (uint256[] memory result) {
        result = new uint256[](uint16(self.count));
        uint256 index = 0;
        uint256 offset = self.offset;
        for (uint256 i = 0; i < FIXED_LENGTH; i++) {
            uint256 bucket = self.map[i];
            if (bucket == 0) continue;
            for (uint256 j = 0; j < MAX_POP_COUNT; j++) {
                if ((bucket & (1 << j)) == 0) continue;
                result[index] = ((i << INDEX_SHIFT) | j) + offset;
                index++;
            }
        }
    }

    function _addPopCount(Set storage self,
        uint8 slot,
        uint8 amount
    ) private {
        unchecked {
            self.popCounts[slot >> 5] += uint256(amount & INDEX_MASK) << ((slot & 31) << 3);
        }
    }

    function _addPopCounts(
        uint256[2] memory popCounts,
        uint8 slot,
        uint8 amount
    ) private pure {
        unchecked {
            popCounts[slot >> 5] += uint256(amount & INDEX_MASK) << ((slot & 31) << 3);
        }
    }

    function _subPopCount(Set storage self,
        uint8 slot,
        uint8 amount
    ) private {
        unchecked {
            self.popCounts[slot >> 5] -= uint256(amount & INDEX_MASK) << ((slot & 31) << 3);
        }
    }

    function _subPopCounts(
        uint256[2] memory popCounts,
        uint8 slot,
        uint8 amount
    ) private pure {
        unchecked {
            popCounts[slot >> 5] -= uint256(amount & INDEX_MASK) << ((slot & 31) << 3);
        }
    }

    function _getPopCount(
        uint256 count,
        uint256[2] memory popCounts,
        uint256 slot
    ) private pure returns (uint16) {
        return ((count >> (slot + OFFSET_BUCKET_FLAGS)) & 1) == 1 ? MAX_POP_COUNT :
            uint16((popCounts[slot >> 5] >> ((slot & 31) << 3)) & MASK_BIT_COUNT);
    }

    function _positionOfIndex(
        uint256 count,
        uint256[2] memory popCounts,
        uint16 index
    ) private pure returns (uint8 bucket, uint16 /*pos*/) {
        unchecked {
            if (index > uint16(count)) return (INDEX_NOT_FOUND, 0);
            uint16 total = 0;
            uint16 popCount = 0;
            uint16 next = 0;
            for (bucket = 0; bucket < FIXED_LENGTH; ++bucket) {
                popCount = _getPopCount(count, popCounts, bucket);
                next = total + popCount;
                if (next > index) return (bucket, index - total);
                total = next;
            }
            return (INDEX_NOT_FOUND, 0);
        }
    }
}

// SPDX-License-Identifier: MIT
pragma solidity ^0.8.4;

import {LibBit} from "./LibBit.sol";

/// @notice Library for storage of packed unsigned booleans.
/// @author Solady (https://github.com/vectorized/solady/blob/main/src/utils/LibBitmap.sol)
/// @author Modified from Solmate (https://github.com/transmissions11/solmate/blob/main/src/utils/LibBitmap.sol)
/// @author Modified from Solidity-Bits (https://github.com/estarriolvetch/solidity-bits/blob/main/contracts/BitMaps.sol)
library LibBitmap {
    /*´:°•.°+.*•´.*:˚.°*.˚•´.°:°•.°•.*•´.*:˚.°*.˚•´.°:°•.°+.*•´.*:*/
    /*                         CONSTANTS                          */
    /*.•°:°.´+˚.*°.˚:*.´•*.+°.•°:´*.´•*.•°.•°:°.´:•˚°.*°.˚:*.´+°.•*/

    /// @dev The constant returned when a bitmap scan does not find a result.
    uint256 internal constant NOT_FOUND = type(uint256).max;

    /*´:°•.°+.*•´.*:˚.°*.˚•´.°:°•.°•.*•´.*:˚.°*.˚•´.°:°•.°+.*•´.*:*/
    /*                          STRUCTS                           */
    /*.•°:°.´+˚.*°.˚:*.´•*.+°.•°:´*.´•*.•°.•°:°.´:•˚°.*°.˚:*.´+°.•*/

    /// @dev A bitmap in storage.
    struct Bitmap {
        mapping(uint256 => uint256) map;
    }

    /*´:°•.°+.*•´.*:˚.°*.˚•´.°:°•.°•.*•´.*:˚.°*.˚•´.°:°•.°+.*•´.*:*/
    /*                         OPERATIONS                         */
    /*.•°:°.´+˚.*°.˚:*.´•*.+°.•°:´*.´•*.•°.•°:°.´:•˚°.*°.˚:*.´+°.•*/

    /// @dev Returns the boolean value of the bit at `index` in `bitmap`.
    function get(Bitmap storage bitmap, uint256 index) internal view returns (bool isSet) {
        // It is better to set `isSet` to either 0 or 1, than zero vs non-zero.
        // Both cost the same amount of gas, but the former allows the returned value
        // to be reused without cleaning the upper bits.
        uint256 b = (bitmap.map[index >> 8] >> (index & 0xff)) & 1;
        /// @solidity memory-safe-assembly
        assembly {
            isSet := b
        }
    }

    /// @dev Updates the bit at `index` in `bitmap` to true.
    function set(Bitmap storage bitmap, uint256 index) internal {
        bitmap.map[index >> 8] |= (1 << (index & 0xff));
    }

    /// @dev Updates the bit at `index` in `bitmap` to false.
    function unset(Bitmap storage bitmap, uint256 index) internal {
        bitmap.map[index >> 8] &= ~(1 << (index & 0xff));
    }

    /// @dev Flips the bit at `index` in `bitmap`.
    /// Returns the boolean result of the flipped bit.
    function toggle(Bitmap storage bitmap, uint256 index) internal returns (bool newIsSet) {
        /// @solidity memory-safe-assembly
        assembly {
            mstore(0x20, bitmap.slot)
            mstore(0x00, shr(8, index))
            let storageSlot := keccak256(0x00, 0x40)
            let shift := and(index, 0xff)
            let storageValue := xor(sload(storageSlot), shl(shift, 1))
            // It makes sense to return the `newIsSet`,
            // as it allow us to skip an additional warm `sload`,
            // and it costs minimal gas (about 15),
            // which may be optimized away if the returned value is unused.
            newIsSet := and(1, shr(shift, storageValue))
            sstore(storageSlot, storageValue)
        }
    }

    /// @dev Updates the bit at `index` in `bitmap` to `shouldSet`.
    function setTo(Bitmap storage bitmap, uint256 index, bool shouldSet) internal {
        /// @solidity memory-safe-assembly
        assembly {
            mstore(0x20, bitmap.slot)
            mstore(0x00, shr(8, index))
            let storageSlot := keccak256(0x00, 0x40)
            let storageValue := sload(storageSlot)
            let shift := and(index, 0xff)
            sstore(
                storageSlot,
                // Unsets the bit at `shift` via `and`, then sets its new value via `or`.
                or(and(storageValue, not(shl(shift, 1))), shl(shift, iszero(iszero(shouldSet))))
            )
        }
    }

    /// @dev Consecutively sets `amount` of bits starting from the bit at `start`.
    function setBatch(Bitmap storage bitmap, uint256 start, uint256 amount) internal {
        /// @solidity memory-safe-assembly
        assembly {
            let max := not(0)
            let shift := and(start, 0xff)
            mstore(0x20, bitmap.slot)
            mstore(0x00, shr(8, start))
            if iszero(lt(add(shift, amount), 257)) {
                let storageSlot := keccak256(0x00, 0x40)
                sstore(storageSlot, or(sload(storageSlot), shl(shift, max)))
                let bucket := add(mload(0x00), 1)
                let bucketEnd := add(mload(0x00), shr(8, add(amount, shift)))
                amount := and(add(amount, shift), 0xff)
                shift := 0
                for {} iszero(eq(bucket, bucketEnd)) { bucket := add(bucket, 1) } {
                    mstore(0x00, bucket)
                    sstore(keccak256(0x00, 0x40), max)
                }
                mstore(0x00, bucket)
            }
            let storageSlot := keccak256(0x00, 0x40)
            sstore(storageSlot, or(sload(storageSlot), shl(shift, shr(sub(256, amount), max))))
        }
    }

    /// @dev Consecutively unsets `amount` of bits starting from the bit at `start`.
    function unsetBatch(Bitmap storage bitmap, uint256 start, uint256 amount) internal {
        /// @solidity memory-safe-assembly
        assembly {
            let shift := and(start, 0xff)
            mstore(0x20, bitmap.slot)
            mstore(0x00, shr(8, start))
            if iszero(lt(add(shift, amount), 257)) {
                let storageSlot := keccak256(0x00, 0x40)
                sstore(storageSlot, and(sload(storageSlot), not(shl(shift, not(0)))))
                let bucket := add(mload(0x00), 1)
                let bucketEnd := add(mload(0x00), shr(8, add(amount, shift)))
                amount := and(add(amount, shift), 0xff)
                shift := 0
                for {} iszero(eq(bucket, bucketEnd)) { bucket := add(bucket, 1) } {
                    mstore(0x00, bucket)
                    sstore(keccak256(0x00, 0x40), 0)
                }
                mstore(0x00, bucket)
            }
            let storageSlot := keccak256(0x00, 0x40)
            sstore(
                storageSlot, and(sload(storageSlot), not(shl(shift, shr(sub(256, amount), not(0)))))
            )
        }
    }

    /// @dev Returns number of set bits within a range by
    /// scanning `amount` of bits starting from the bit at `start`.
    function popCount(Bitmap storage bitmap, uint256 start, uint256 amount)
        internal
        view
        returns (uint256 count)
    {
        unchecked {
            uint256 bucket = start >> 8;
            uint256 shift = start & 0xff;
            if (!(amount + shift < 257)) {
                count = LibBit.popCount(bitmap.map[bucket] >> shift);
                uint256 bucketEnd = bucket + ((amount + shift) >> 8);
                amount = (amount + shift) & 0xff;
                shift = 0;
                for (++bucket; bucket != bucketEnd; ++bucket) {
                    count += LibBit.popCount(bitmap.map[bucket]);
                }
            }
            count += LibBit.popCount((bitmap.map[bucket] >> shift) << (256 - amount));
        }
    }

    /// @dev Returns the index of the most significant set bit before the bit at `before`.
    /// If no set bit is found, returns `NOT_FOUND`.
    function findLastSet(Bitmap storage bitmap, uint256 before)
        internal
        view
        returns (uint256 setBitIndex)
    {
        uint256 bucket;
        uint256 bucketBits;
        /// @solidity memory-safe-assembly
        assembly {
            setBitIndex := not(0)
            bucket := shr(8, before)
            mstore(0x00, bucket)
            mstore(0x20, bitmap.slot)
            let offset := and(0xff, not(before)) // `256 - (255 & before) - 1`.
            bucketBits := shr(offset, shl(offset, sload(keccak256(0x00, 0x40))))
            if iszero(or(bucketBits, iszero(bucket))) {
                for {} 1 {} {
                    bucket := add(bucket, setBitIndex) // `sub(bucket, 1)`.
                    mstore(0x00, bucket)
                    bucketBits := sload(keccak256(0x00, 0x40))
                    if or(bucketBits, iszero(bucket)) { break }
                }
            }
        }
        if (bucketBits != 0) {
            setBitIndex = (bucket << 8) | LibBit.fls(bucketBits);
            /// @solidity memory-safe-assembly
            assembly {
                setBitIndex := or(setBitIndex, sub(0, gt(setBitIndex, before)))
            }
        }
    }
}

// SPDX-License-Identifier: UNLICENSED

pragma solidity ^0.8.23;

import {LibShared} from "./LibShared.sol";
import "./Constants.sol";

library LibConfig {

    uint256 private constant CONFIG_OFFSET_MAX_TOKENS = 0;
    uint256 private constant CONFIG_OFFSET_MAX_WALLET = 16;
    uint256 private constant CONFIG_OFFSET_MAX_AMOUNT = 32;
    uint256 private constant CONFIG_OFFSET_CONTEST_ID = 48;
    uint256 private constant CONFIG_OFFSET_CONFIG_VER = 80;
    uint256 private constant CONFIG_OFFSET_TEAM_SPLIT = 88;
    uint256 private constant CONFIG_OFFSET_PRIZE_POOL = 96;
    uint256 private constant MASK_MAX_TOKENS = 0xFFFF;
    uint256 private constant MASK_MAX_WALLET = 0xFFFF;
    uint256 private constant MASK_MAX_AMOUNT = 0xFFFF;
    uint256 private constant MASK_PRIZE_POOL = 0xFFFF;
    uint256 private constant MASK_CONTEST_ID = 0xFFFF;
    uint256 private constant MASK_TEAM_SPLIT = 0xFF;
    uint256 private constant MASK_CONFIG_VER = 0xFF;
    uint256 private constant SCALAR_GWEI = 1e9;
    uint16 private constant CONTEST_ID_OFFSET_SERIES = 16;
    uint16 private constant MIN_TOKENS = 2;
    uint16 private constant MAX_TOKENS = 2**14;
    uint8 private constant MAX_TEAM_SPLIT = 50;
    uint8 private constant CONFIG_VERSION = 1;

    error ErrorMaxAmount();
    error ErrorMaxTokens();
    error ErrorMaxWallet();
    error ErrorTeamSplit();

    function initConfig(
        uint256 _tokenPrice,
        uint32 _contestId,
        uint16 _maxTokens,
        uint16 _maxWallet,
        uint16 _maxAmount,
        uint8 _teamSplit
    ) internal pure returns (uint256) {
        if ((_maxTokens < MIN_TOKENS) || (_maxTokens > MAX_TOKENS)) revert ErrorMaxTokens();
        if ((_maxWallet == 0) || (_maxWallet > _maxTokens)) revert ErrorMaxWallet();
        if ((_maxAmount == 0) || (_maxAmount > _maxWallet)) revert ErrorMaxAmount();
        if (_teamSplit > MAX_TEAM_SPLIT) revert ErrorTeamSplit();
        uint64 prizePool = uint64(((_tokenPrice * _maxTokens * (100 - _teamSplit)) / 100) / SCALAR_GWEI);
        if (_contestId <= type(uint16).max) {
            _contestId = (uint32(_maxTokens | uint16(prizePool / SCALAR_GWEI)) << CONTEST_ID_OFFSET_SERIES) | _contestId;
        }
        return
            (uint256(_maxTokens)     << CONFIG_OFFSET_MAX_TOKENS) |
            (uint256(_maxWallet)     << CONFIG_OFFSET_MAX_WALLET) |
            (uint256(_maxAmount)     << CONFIG_OFFSET_MAX_AMOUNT) |
            (uint256(_contestId)     << CONFIG_OFFSET_CONTEST_ID)  |
            (uint256(CONFIG_VERSION) << CONFIG_OFFSET_CONFIG_VER) |
            (uint256(_teamSplit)     << CONFIG_OFFSET_TEAM_SPLIT) |
            (uint256(prizePool)      << CONFIG_OFFSET_PRIZE_POOL);
    }

    function teamSplit(uint256 data) internal pure returns (uint8) {
        return uint8((data >> CONFIG_OFFSET_TEAM_SPLIT) & MASK_TEAM_SPLIT);
    }

    function maxAmount(uint256 data) internal pure returns (uint16) {
        return uint16((data >> CONFIG_OFFSET_MAX_AMOUNT) & MASK_MAX_AMOUNT);
    }

    function maxWallet(uint256 data) internal pure returns (uint16) {
        return uint16((data >> CONFIG_OFFSET_MAX_WALLET) & MASK_MAX_WALLET);
    }

    function maxTokens(uint256 data) internal pure returns (uint16) {
        return uint16((data >> CONFIG_OFFSET_MAX_TOKENS) & MASK_MAX_TOKENS);
    }
}

// SPDX-License-Identifier: UNLICENSED

pragma solidity ^0.8.23;

import {LibBitSet} from "./LibBitSet.sol";
import {LibShared} from "./LibShared.sol";
import "./Constants.sol";

enum GameStatus {
    MINTING,
    PAUSING,
    PENDING,
    RUNNING,
    FORFEIT,
    WINNERS
}

library LibGame {
    using LibBitSet for LibBitSet.Set;
    using LibShared for uint256;
    using LibShared for uint32;

    uint256 private constant GAME_OFFSET_RESET_TIME = 112;
    uint256 private constant GAME_OFFSET_PAUSE_TIME = 144;
    uint256 private constant GAME_OFFSET_ROUND_TIME = 176;
    uint256 private constant GAME_OFFSET_MULTI_USER = 208;
    uint256 private constant GAME_OFFSET_GAME_STATE = 216;
    uint256 private constant INFO_OFFSET_GAME_STATE = 0;
    uint256 private constant INFO_OFFSET_BLOCK_TIME = 8;
    uint256 private constant INFO_OFFSET_RESET_TIME = 40;
    uint256 private constant INFO_OFFSET_PAUSE_TIME = 72;
    uint256 private constant INFO_OFFSET_ROUND_TIME = 104;
    uint256 private constant INFO_OFFSET_PRIZE_POOL = 136;
    uint256 private constant INFO_OFFSET_GAMESTATUS = 168;
    uint256 private constant INFO_OFFSET_BURN_COUNT = 176;
    uint256 private constant INFO_OFFSET_SAFE_COUNT = 192;
    uint256 private constant INFO_OFFSET_LIVE_COUNT = 208;
    uint256 private constant INFO_OFFSET_GAME_ROUND = 224;
    uint256 private constant MASK_MULTI = 0xFF;
    uint256 private constant MASK_STATE = 0xFF;
    uint256 private constant MASK_BURNED = 0xFFFF;
    uint256 private constant MASK_TIMESTAMP = 0xFFFFFFFF;
    uint256 private constant MASK_PENDING = 0xFFFFFFFFFFFFFFFFFFFFFFFF;
    uint256 private constant SCALAR_BWEI = 1e14;

     struct Game {
        uint256 data;
        uint256 prizePool;
        LibBitSet.Set[2] tokens;
    }

    event GameStart(uint32 indexed gameRound);
    event GameCancelled(uint32 indexed gameRound, uint256 mintCount);
    event GameOver(uint32 indexed gameRound, address winner);
    event RoundStart(uint32 indexed gameRound);

    function nextGameRound(Game storage self
    ) internal view returns (uint32) {
       return _nextGameRound(self.data);
    }

    function initGame(Game storage self,
        uint256 startTokenId
    ) internal returns (uint32) {
        return _initGame(self, self.data, startTokenId);
    }

    function startGame(Game storage self
    ) internal {
        _startGame(self);
    }

    function startRound(Game storage self,
        uint32 gameRound
    ) internal {
        _startRound(self, gameRound);
    }

    function resetGame(Game storage self,
        uint256 startTokenId
    ) internal returns (uint32) {
        return _resetGame(self, self.data, startTokenId);
    }

    function cancelGame(Game storage self,
        uint256 startTokenId
    ) internal {
        uint256 data = self.data;
        emit GameCancelled(data.getGameRound(), data.getLiveCount());
        _resetGame(self, data, startTokenId);
    }

    function getStatus(Game storage self
    )  internal view returns (GameStatus) {
        return _getStatus(self, self.data);
    }

    function getStatus(Game storage self,
        uint256 data
    )  internal view returns (GameStatus) {
        return _getStatus(self, data);
    }

    function isGameOver(Game storage self,
        uint32 gameRound
    ) internal view returns (uint256) {
        return _isGameOver(self, gameRound);
    }

    function liveTokenCount(Game storage self
    ) internal view returns (uint16) {
        return _liveTokenCount(self, self.data);
    }

    function virtualLiveTokenCount(Game storage self
    ) internal view returns (uint16) {
        return _virtualLiveTokenCount(self, self.data);
    }

    function virtualSafeTokenCount(Game storage self
    ) internal view returns (uint16) {
        return _virtualSafeTokenCount(self, self.data);
    }

    function virtualBurnTokenCount(Game storage self
    ) internal view returns (uint16) {
        return _virtualBurnTokenCount(self, self.data);
    }

    function getTokenStatus(Game storage self,
        uint256 tokenId
    ) internal view returns (uint8) {
        return _getTokenStatus(self, tokenId);
    }

    function virtualResetEndTime(Game storage self,
        GameStatus status
    ) internal view returns (uint32) {
        return _virtualResetEndTime(self.data, status);
    }

    function gameInfo(Game storage self
    ) internal view returns (uint256) {
       return _gameInfo(self);
    }

    function _nextGameRound(
        uint256 data
    ) private pure returns (uint32) {
        unchecked {
            return (data.getGameRound() + (uint32(1) << OFFSET_GAME_NUMBER)) | 1;
        }
    }

    function _initGame(Game storage self,
        uint256 data,
        uint256 startTokenId
    ) private returns (uint32)  {
        uint256 gameRound = _nextGameRound(data);
        self.data = gameRound << DATA_OFFSET_GAME_ROUND;
        self.tokens[0].offset = self.tokens[1].offset = startTokenId;
        return uint32(gameRound);
    }

    function _startGame(Game storage self
    ) private {
        uint256 data = self.data;
        data = _clearEndTimes(data) | (GAME_STATE_STARTED << GAME_OFFSET_GAME_STATE);
        self.data = data;
        emit GameStart(data.getGameRound());
    }

    function _startRound(Game storage self,
        uint32 gameRound
    ) private {
        uint256 data = self.data;
        if (block.timestamp <= roundEndTime(data)) return;
        unchecked {
            LibBitSet.Set[2] storage tokens = self.tokens;
            if (data.getGameRound() != gameRound) {
                uint8 prevIndex = data.getLiveIndex();
                data = data.addBurnCount(uint16(tokens[prevIndex].length()));
                delete tokens[prevIndex];
                tokens[prevIndex].offset = tokens[1 - prevIndex].offset;
                data = data.setGameRound(gameRound);
            }
            data = _clearMultiUser(data);
            self.data = setRoundEndTime(data, block.timestamp +
                LibShared.max(tokens[gameRound.liveIndex()].length() << TOKEN_DELAY_ROUND, MIN_ROUND_TIME));
            emit RoundStart(gameRound);
        }
    }

    function _resetGame(Game storage self,
        uint256 data,
        uint256 startTokenId
    ) private returns (uint32) {
        self.prizePool = 0;
        delete self.tokens;
        self.tokens[0].offset = self.tokens[1].offset = startTokenId;
        return _initGame(self, data.clearRound(), startTokenId);
    }

    function _getStatus(Game storage self,
        uint256 data
    ) private view returns (GameStatus) {
        uint256 pauseTime = pauseEndTime(data);
        uint256 resetTime = resetEndTime(data);
        if (block.timestamp > pauseTime && (resetTime > 0 && block.timestamp <= resetTime)) {
            return GameStatus.WINNERS;
        }
        if (gameState(data) == GAME_STATE_OFFLINE) {
            return GameStatus.MINTING;
        }
        if (_isPending(data)) {
            return GameStatus.PENDING;
        }
        uint256 roundTime = roundEndTime(data);
        if (roundTime != 0 && block.timestamp <= roundTime && self.tokens[data.getLiveIndex()].length() > 1) {
            return GameStatus.RUNNING;
        }
        if (isMultiUser(data)) {
            if ((roundTime == 0 || block.timestamp > roundTime) && (pauseTime > 0 && block.timestamp <= pauseTime)) {
                return GameStatus.PAUSING;
            }
            return (pauseTime > 0 && block.timestamp > pauseTime && roundTime < pauseTime) ?
                GameStatus.PENDING : GameStatus.RUNNING;
        }
        return self.tokens[data.getSafeIndex()].length() == 0 ?
            GameStatus.FORFEIT : GameStatus.WINNERS;
    }

    function _liveTokenCount(Game storage self,
        uint256 data
    ) private view returns (uint16) {
        return uint16(self.tokens[data.getLiveIndex()].length());
    }

    function _safeTokenCount(Game storage self,
        uint256 data
    ) private view returns (uint16) {
        return uint16(self.tokens[data.getSafeIndex()].length());
    }

    function _virtualLiveTokenCount(Game storage self,
        uint256 data
    ) private view returns (uint16) {
        if ((gameState(data) == GAME_STATE_OFFLINE) ||
            (block.timestamp <= roundEndTime(data)) ||
            _isPending(data)) {
            return _liveTokenCount(self, data);
        }
        return 0;
    }

    function _virtualSafeTokenCount(Game storage self,
        uint256 data
    ) private view returns (uint16) {
        if (gameState(data) == GAME_STATE_OFFLINE) {
            return 0;
        }
        return _safeTokenCount(self, data);
    }

    function _virtualBurnTokenCount(Game storage self,
        uint256 data
    ) private view returns (uint16) {
        uint16 burnCount = data.getBurnCount();
        if ((gameState(data) == GAME_STATE_STARTED) &&
            (block.timestamp > roundEndTime(data)) &&
            !_isPending(data)) {
            burnCount += _liveTokenCount(self, data);
        }
        return burnCount;
    }

    function _getTokenStatus(Game storage self,
        uint256 tokenId
    ) private view returns (uint8) {
        if (tokenId < self.tokens[0].offset) return TOKEN_STATUS_BANNED;
        uint256 data = self.data;
        if (gameState(data) == GAME_STATE_OFFLINE) return TOKEN_STATUS_QUEUED;
        if (_virtualLiveTokenCount(self, data) > 1 && self.tokens[data.getLiveIndex()].contains(tokenId)) {
            return TOKEN_STATUS_ACTIVE;
        }
        return (self.tokens[data.getSafeIndex()].contains(tokenId)) ? TOKEN_STATUS_SECURE : TOKEN_STATUS_BURNED;
    }

    function _isGameOver(Game storage self,
        uint32 gameRound
    ) private view returns (uint256) {
        GameStatus status = _getStatus(self, self.data);
        if (status < GameStatus.FORFEIT) return LibBitSet.NOT_FOUND;
        if (status == GameStatus.FORFEIT) return FORFEIT_TOKEN_ID + (gameRound >> OFFSET_GAME_NUMBER);
        return self.tokens[gameRound.safeIndex()].findFirst();
    }

    function _virtualResetEndTime(
        uint256 data,
        GameStatus status
    ) private pure returns (uint32) {
        uint32 resetTime = resetEndTime(data);
        if (status > GameStatus.RUNNING && resetTime == 0) {
            return roundEndTime(data) + MIN_RESET_TIME;
        }
        return resetTime;
    }

    function _gameInfo(Game storage self
    ) private view returns (uint256) {
        uint256 data = self.data;
        GameStatus status = _getStatus(self, data);
        uint256 prizePool = self.prizePool / SCALAR_BWEI;
        uint32 gameRound = data.getGameRound();
        uint256 state = gameState(data);
        uint32 roundTime = roundEndTime(data);
        uint32 pauseTime = pauseEndTime(data);
        uint32 resetTime = resetEndTime(data);
        uint16 liveCount = _virtualLiveTokenCount(self, data);
        uint16 safeCount = _virtualSafeTokenCount(self, data);
        uint16 burnCount = _virtualBurnTokenCount(self, data);
        if (status == GameStatus.RUNNING) {
            pauseTime = resetTime = 0;
        }
        if ((status == GameStatus.PAUSING || status == GameStatus.PENDING) && pauseTime != 0) {
            unchecked { gameRound++; }
            (liveCount, safeCount) = (safeCount, 0);
            roundTime = resetTime = 0;
            if (block.timestamp > pauseTime) {
                pauseTime = 0;
            }
        }
        if (status == GameStatus.PENDING) {
            roundTime = pauseTime = resetTime = 0;
        }
        if (status > GameStatus.RUNNING) {
            roundTime = pauseTime = 0;
            if (resetTime == 0) {
                resetTime = _virtualResetEndTime(data, status);
                state = GAME_STATE_VIRTUAL;
            }
            if (resetTime != 0 && block.timestamp > resetTime) {
                status = GameStatus.MINTING;
                gameRound = _nextGameRound(data);
                prizePool = roundTime = pauseTime = liveCount = safeCount = burnCount = 0;
            }
        }
        uint256 info = (state << INFO_OFFSET_GAME_STATE);
        info |=
            (uint256(block.timestamp) << INFO_OFFSET_BLOCK_TIME) |
            (uint256(resetTime) << INFO_OFFSET_RESET_TIME) |
            (uint256(pauseTime) << INFO_OFFSET_PAUSE_TIME) |
            (uint256(roundTime) << INFO_OFFSET_ROUND_TIME) |
            (prizePool << INFO_OFFSET_PRIZE_POOL) |
            (uint256(status) << INFO_OFFSET_GAMESTATUS);
        info |=
            (uint256(burnCount) << INFO_OFFSET_BURN_COUNT) |
            (uint256(safeCount) << INFO_OFFSET_SAFE_COUNT) |
            (uint256(liveCount) << INFO_OFFSET_LIVE_COUNT) |
            (uint256(gameRound) << INFO_OFFSET_GAME_ROUND);
        return info;
    }

    function gameState(uint256 data) internal pure returns (uint8) {
        return uint8((data >> GAME_OFFSET_GAME_STATE) & MASK_STATE);
    }

    function setMultiUser(uint256 data) internal pure returns (uint256) {
        return _clearMultiUser(data) | (1 << GAME_OFFSET_MULTI_USER);
    }

    function isMultiUser(uint256 data) internal pure returns (bool) {
        return uint8((data >> GAME_OFFSET_MULTI_USER) & MASK_MULTI) == 1;
    }

    function hasPauseExpired(uint256 data) internal view returns (bool) {
        uint32 pauseTime = pauseEndTime(data);
        return (pauseTime > 0 && block.timestamp > pauseTime && roundEndTime(data) < pauseTime);
    }

    function roundEndTime(uint256 data) internal pure returns (uint32) {
        return uint32((data >> GAME_OFFSET_ROUND_TIME) & MASK_TIMESTAMP);
    }

    function setRoundEndTime(uint256 data, uint256 time) internal pure returns (uint256) {
        return clearRoundEndTime(data) | (time << GAME_OFFSET_ROUND_TIME);
    }

    function clearRoundEndTime(uint256 data) internal pure returns (uint256) {
        return (data & ~(MASK_TIMESTAMP << GAME_OFFSET_ROUND_TIME));
    }

    function pauseEndTime(uint256 data) internal pure returns (uint32) {
        return uint32((data >> GAME_OFFSET_PAUSE_TIME) & MASK_TIMESTAMP);
    }

    function setPauseEndTime(uint256 data, uint256 time) internal pure returns (uint256) {
        return clearPauseEndTime(data) | (time << GAME_OFFSET_PAUSE_TIME);
    }

    function clearPauseEndTime(uint256 data) internal pure returns (uint256) {
        return (data & ~(MASK_TIMESTAMP << GAME_OFFSET_PAUSE_TIME));
    }

    function resetEndTime(uint256 data) internal pure returns (uint32) {
        return uint32((data >> GAME_OFFSET_RESET_TIME) & MASK_TIMESTAMP);
    }

    function setResetEndTime(uint256 data, uint256 time) internal pure returns (uint256) {
        return clearPauseEndTime(data) | (time << GAME_OFFSET_RESET_TIME);
    }

    function clearResetEndTime(uint256 data) internal pure returns (uint256) {
        return (data & ~(MASK_TIMESTAMP << GAME_OFFSET_RESET_TIME));
    }

    function _clearMultiUser(uint256 data) private pure returns (uint256) {
        return (data & ~(MASK_MULTI << GAME_OFFSET_MULTI_USER));
    }

    function _clearEndTimes(uint256 data) private pure returns (uint256) {
        return (data & ~(MASK_PENDING << GAME_OFFSET_RESET_TIME));
    }

    function _isPending(uint256 data) private pure returns (bool) {
        return ((data >> GAME_OFFSET_RESET_TIME) & MASK_PENDING) == 0;
    }
}