contract ERC721NOIDS is Context, ERC165, IERC721, IERC721Metadata {
    using Address for address;
    using Strings for uint256;

    uint256 internal constant MAX_SUPPLY = 5000;
    uint256 internal constant TOKEN_ID_FIRST = 10001;

    struct OwnerData {
        uint48 balance;
        uint48 totalMinted;
        uint48 stageMinted;     // number of tokens minted during current stage
        uint48 stageMax;        // maximum that can be minted during current stage
        uint64 stageTimestamp;  // deadline for current stage
    }

    // Token name
    string private _name;

    // Token symbol
    string private _symbol;

    // Counter for the number of minted tokens
    uint256 internal _totalSupply;

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

    // Mapping owner address to token count
    mapping(address => OwnerData) internal _ownerData;

    // Mapping from token ID to approved address
    mapping(uint256 => address) private _tokenApprovals;

    // Mapping from owner to operator approvals
    mapping(address => mapping(address => bool)) private _operatorApprovals;

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

    /**
     * @dev See {IERC721Enumerable-totalSupply}.
     */
    function totalSupply() public view returns (uint256) {
        return _totalSupply;
    }

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

    /**
     * @dev See {IERC721-balanceOf}.
     */
    function balanceOf(address owner) public view virtual override returns (uint256) {
        require(owner != address(0), "ERC721: balance query for the zero address");
        return _ownerData[owner].balance;
    }

    /**
     * @dev See {IERC721-ownerOf}.
     */
    function ownerOf(uint256 tokenId) public view virtual override returns (address) {
        address owner = _owners[tokenId];
        if (owner == address(0)) {
            require(_exists(tokenId), "ERC721: owner query for nonexistent token");
            unchecked {
                do {
                    owner = _owners[--tokenId];
                } while (owner == address(0));
            }
        }
        return owner;
    }

    /**
     * @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) {
        require(_exists(tokenId), "ERC721Metadata: URI query for nonexistent token");

        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 overridden in child contracts.
     */
    function _baseURI() internal view virtual returns (string memory) {
        return "";
    }

    /**
     * @dev See {IERC721-approve}.
     */
    function approve(address to, uint256 tokenId) public virtual override {
        address owner = ERC721NOIDS.ownerOf(tokenId);
        require(to != owner, "ERC721: approval to current owner");

        require(
            _msgSender() == owner || isApprovedForAll(owner, _msgSender()),
            "ERC721: approve caller is not owner nor approved for all"
        );

        _approve(to, tokenId, owner);
    }

    /**
     * @dev See {IERC721-getApproved}.
     */
    function getApproved(uint256 tokenId) public view virtual override returns (address) {
        require(_exists(tokenId), "ERC721: approved query for nonexistent token");

        return _tokenApprovals[tokenId];
    }

    /**
     * @dev See {IERC721-setApprovalForAll}.
     */
    function setApprovalForAll(address operator, bool approved) public virtual override {
        _setApprovalForAll(_msgSender(), 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 virtual override {
        _transfer(from, to, tokenId);
    }

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

    /**
     * @dev See {IERC721-safeTransferFrom}.
     */
    function safeTransferFrom(
        address from,
        address to,
        uint256 tokenId,
        bytes memory _data
    ) public 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);
        require(_checkOnERC721Received(from, to, tokenId, _data), "ERC721: transfer to non ERC721Receiver implementer");
    }

    /**
     * @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 virtual returns (bool) {
        return tokenId >= TOKEN_ID_FIRST && ((tokenId - TOKEN_ID_FIRST) < _totalSupply);
    }

    /**
     * @dev Mints `quantity` of tokens with consecutive IDs and transfers them to `to`.
     *
     * Requirements:
     *
     * - `quantity` must not be zero.
     * - `to` must not be the zero address.
     *
     * Emits multiple {Transfer} events. ERC-2309 could be used instead 
     */
    function _mint(address to, uint256 quantity, uint256 stageMax, uint256 stageTimestamp) internal virtual {
        unchecked {
            uint256 minted = quantity;
            if (stageTimestamp == _ownerData[to].stageTimestamp) {
                minted += _ownerData[to].stageMinted;
            }
            require(minted <= stageMax, "Cannot mint more than assigned maximum");

            _ownerData[to].balance += uint48(quantity);
            _ownerData[to].totalMinted += uint48(quantity);
            _ownerData[to].stageMinted = uint48(minted);
            _ownerData[to].stageMax = uint48(stageMax);
            _ownerData[to].stageTimestamp = uint64(stageTimestamp);

            uint256 newTotalSupply = _totalSupply + quantity;
            require(newTotalSupply <= MAX_SUPPLY, "Cannot mint more than maximum supply of 5000");
            uint256 tokenIdStart = _totalSupply + TOKEN_ID_FIRST;
            uint256 tokenIdEnd = tokenIdStart + quantity;
            _totalSupply = newTotalSupply;
            
            _owners[tokenIdStart] = to;
            if (quantity > 16) {
                uint256 batchCount = (quantity + 15) >> 4;
                uint256 quantity2 = quantity << 1;
                uint256 i = batchCount + (batchCount * quantity2) - quantity2;
                batchCount <<= 1;
                do {
                    _owners[(i / batchCount) + tokenIdStart] = to;  
                    i -= quantity2;
                } while (i >= batchCount);
            }

            for (uint256 i=tokenIdStart; i<tokenIdEnd; i++) {
                emit Transfer(address(0), to, i);
            }
        }
    }

    /**
     * @dev Transfers `tokenId` from `from` to `to`.
     *
     * 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 {
        require(ERC721NOIDS.ownerOf(tokenId) == from, "ERC721: transfer from incorrect owner");
        require(to != address(0), "ERC721: transfer to the zero address");

        //solhint-disable-next-line max-line-length
        require((_msgSender() == from || getApproved(tokenId) == _msgSender() || isApprovedForAll(from, _msgSender())), "ERC721: transfer caller is not owner nor approved");

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

        unchecked {
            uint48 balance = _ownerData[from].balance - 1;
            _ownerData[from].balance = balance;
            _ownerData[to].balance += 1;

            _owners[tokenId] = to;            

            if (balance > 0) {
                uint256 nextTokenId = tokenId + 1;
                if (_owners[nextTokenId] == address(0) && nextTokenId < (TOKEN_ID_FIRST + _totalSupply)) {
                    _owners[nextTokenId] = from;
                }
            }
        }

        emit Transfer(from, to, tokenId);
    }

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

    /**
     * @dev Approve `operator` to operate on all of `owner` tokens
     *
     * Emits a {ApprovalForAll} event.
     */
    function _setApprovalForAll(
        address owner,
        address operator,
        bool approved
    ) internal virtual {
        require(owner != operator, "ERC721: approve to caller");
        _operatorApprovals[owner][operator] = approved;
        emit ApprovalForAll(owner, operator, approved);
    }

    /**
     * @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 tokenId uint256 ID of the token to be transferred
     * @param _data bytes optional data to send along with the call
     * @return bool whether the call correctly returned the expected magic value
     */
    function _checkOnERC721Received(
        address from,
        address to,
        uint256 tokenId,
        bytes memory _data
    ) private returns (bool) {
        if (to.isContract()) {
            try IERC721Receiver(to).onERC721Received(_msgSender(), from, tokenId, _data) returns (bytes4 retval) {
                return retval == IERC721Receiver.onERC721Received.selector;
            } catch (bytes memory reason) {
                if (reason.length == 0) {
                    revert("ERC721: transfer to non ERC721Receiver implementer");
                } else {
                    assembly {
                        revert(add(32, reason), mload(reason))
                    }
                }
            }
        } else {
            return true;
        }
    }
}
/**
 * @dev Optimized implementation of https://eips.ethereum.org/EIPS/eip-721[ERC721] Non-Fungible Token Standard, including
 * the Metadata extension, but not including the Enumerable extension
 *
 * @author ponky
 * @notice This contract is optimized specifically for the Humanoids use case, do not use as a template
 *
 */
function getApproved(uint256 tokenId) public view virtual override returns (address) {
    require(_exists(tokenId), "ERC721: approved query for nonexistent token");

    return _tokenApprovals[tokenId];
}

/**
 * @dev See {IERC721-getApproved}.
 */