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

import {ERC20} from "@openzeppelin/contracts/token/ERC20/ERC20.sol";
import {EpochTicketTree} from "./eligibility/EpochTicketTree.sol";

/// @notice A fixed-supply token whose lottery eligibility stays in ordinary wallets.
/// @dev This history requires token integration; arbitrary existing ERC20s are unsupported.
contract CheckpointToken is ERC20, EpochTicketTree {
    uint64 public constant EPOCH_DURATION = 300;
    uint64 public immutable epochZero;
    uint256 public immutable tokensPerTicket;

    struct BalanceCheckpoint {
        uint64 timestamp;
        uint192 balance;
    }

    struct EpochMinimum {
        uint192 balance;
        bool observed;
    }

    struct Holder {
        address account;
        uint64 firstSeen;
    }

    mapping(address => BalanceCheckpoint[]) private _history;
    mapping(uint64 => mapping(address => EpochMinimum)) private _minimum;
    mapping(address => bool) private _registered;
    mapping(address => bool) public isExcluded;
    Holder[] private _holders;

    error InvalidStart();
    error InvalidSupply();
    error EpochNotClosed();
    error EpochNotStarted();
    error InvalidTicketSize();

    constructor(
        string memory name_,
        string memory symbol_,
        address initialHolder,
        uint256 initialSupply,
        uint64 epochZero_,
        address[] memory excludedAddresses,
        uint256 tokensPerTicket_
    ) ERC20(name_, symbol_) EpochTicketTree(tokensPerTicket_ == 0 ? 0 : initialSupply / tokensPerTicket_) {
        if (epochZero_ <= block.timestamp) revert InvalidStart();
        if (initialSupply == 0 || initialSupply > type(uint192).max) revert InvalidSupply();
        if (tokensPerTicket_ == 0 || tokensPerTicket_ > initialSupply) revert InvalidTicketSize();
        epochZero = epochZero_;
        tokensPerTicket = tokensPerTicket_;
        isExcluded[address(0)] = true;
        isExcluded[address(0xdead)] = true;
        isExcluded[address(this)] = true;
        for (uint256 i; i < excludedAddresses.length; ++i) {
            isExcluded[excludedAddresses[i]] = true;
        }
        _mint(initialHolder, initialSupply);
    }

    function holderCount() external view returns (uint256) {
        return _holders.length;
    }

    function holderAt(uint256 index) external view returns (address) {
        return _holders[index].account;
    }

    /// @notice Number of addresses first receiving a positive balance before the cutoff.
    function holderCountBefore(uint64 timestamp) external view returns (uint256) {
        uint256 low;
        uint256 high = _holders.length;
        while (low < high) {
            uint256 middle = low + (high - low) / 2;
            if (_holders[middle].firstSeen < timestamp) low = middle + 1;
            else high = middle;
        }
        return low;
    }

    /// @notice The final balance strictly before a timestamp, excluding that timestamp.
    function balanceStrictlyBefore(address account, uint64 timestamp) public view returns (uint256) {
        BalanceCheckpoint[] storage checkpoints = _history[account];
        uint256 low;
        uint256 high = checkpoints.length;
        while (low < high) {
            uint256 middle = low + (high - low) / 2;
            if (checkpoints[middle].timestamp < timestamp) low = middle + 1;
            else high = middle;
        }
        return low == 0 ? 0 : checkpoints[low - 1].balance;
    }

    /// @notice Immutable eligibility for a completed [start, close) epoch.
    function eligibleBalanceOf(address account, uint64 epoch) external view returns (uint256) {
        uint256 close = uint256(epochZero) + (uint256(epoch) + 1) * EPOCH_DURATION;
        if (block.timestamp < close) revert EpochNotClosed();
        return _eligibleBalance(account, epoch);
    }

    /// @notice Active-epoch eligibility can only decrease before the epoch closes.
    function previewEligibleBalanceOf(address account, uint64 epoch) external view returns (uint256) {
        uint256 start = uint256(epochZero) + uint256(epoch) * EPOCH_DURATION;
        if (block.timestamp < start) revert EpochNotStarted();
        return _eligibleBalance(account, epoch);
    }

    /// @notice Completed-epoch total with no lifetime holder enumeration.
    function totalTickets(uint64 epoch) external view returns (uint256) {
        return _ticketsForEpoch(epoch, _ticketEpochStart(epoch, true));
    }

    /// @notice Current eligibility can only decrease until the epoch closes.
    function previewTotalTickets(uint64 epoch) external view returns (uint256) {
        return _ticketsForEpoch(epoch, _ticketEpochStart(epoch, false));
    }

    /// @notice Selects by cumulative full-epoch ticket weight in historical slot order.
    function winnerAt(uint64 epoch, uint256 ticket) external view returns (address) {
        return _holderForTicket(epoch, _ticketEpochStart(epoch, true), ticket);
    }

    /// @notice Exact zero-based ticket interval for a wallet in a completed epoch.
    /// @dev An empty interval returns firstTicket=0, count=0 and the actual epoch total.
    function getTicketRange(address account, uint64 epoch)
        external view returns (uint256 firstTicket, uint256 count, uint256 total)
    {
        return _ticketRangeForAccount(account, epoch, _ticketEpochStart(epoch, true));
    }

    /// @notice Provisional interval for a started epoch; numbers can shift before close.
    function previewTicketRange(address account, uint64 epoch)
        external view returns (uint256 firstTicket, uint256 count, uint256 total)
    {
        return _ticketRangeForAccount(account, epoch, _ticketEpochStart(epoch, false));
    }

    function _ticketEpochStart(uint64 epoch, bool closed) private view returns (uint64) {
        uint256 start = uint256(epochZero) + uint256(epoch) * EPOCH_DURATION;
        if (closed) {
            if (block.timestamp < start + EPOCH_DURATION) revert EpochNotClosed();
        } else if (block.timestamp < start) revert EpochNotStarted();
        if (start > type(uint64).max) revert InvalidStart();
        return uint64(start);
    }

    function _eligibleBalance(address account, uint64 epoch) private view returns (uint256) {
        if (isExcluded[account]) return 0;
        uint256 start = uint256(epochZero) + uint256(epoch) * EPOCH_DURATION;
        if (start > type(uint64).max) return 0;
        uint256 openingBalance = balanceStrictlyBefore(account, uint64(start));
        EpochMinimum storage minimum = _minimum[epoch][account];
        if (minimum.observed && minimum.balance < openingBalance) return minimum.balance;
        return openingBalance;
    }

    function _update(address from, address to, uint256 value) internal override {
        uint256 fromBefore = from == address(0) ? 0 : balanceOf(from);
        uint256 toBefore = to == address(0) ? 0 : balanceOf(to);
        super._update(from, to, value);
        if (value == 0) return;
        bool ticketChange;
        if (from != address(0)) ticketChange = _syncTickets(from, fromBefore, balanceOf(from));
        if (to != address(0) && to != from) {
            bool recipientChange = _syncTickets(to, toBefore, balanceOf(to));
            ticketChange = ticketChange || recipientChange;
        }
        if (ticketChange) _checkpointTicketRoot();
        if (from != address(0)) _record(from, fromBefore, balanceOf(from));
        if (to != address(0) && to != from) _record(to, toBefore, balanceOf(to));
    }

    function _syncTickets(address account, uint256 beforeBalance, uint256 afterBalance) private returns (bool) {
        if (isExcluded[account]) return false;
        uint192 beforeTickets = uint192(beforeBalance / tokensPerTicket);
        uint192 afterTickets = uint192(afterBalance / tokensPerTicket);
        uint64 epoch;
        uint192 lost;
        if (block.timestamp >= epochZero && afterTickets < beforeTickets) {
            epoch = uint64((block.timestamp - epochZero) / EPOCH_DURATION);
            uint256 eligible = _eligibleBalance(account, epoch) / tokensPerTicket;
            if (eligible > afterTickets) lost = uint192(eligible - afterTickets);
        }
        return _changeTicketBalance(account, beforeTickets, afterTickets, epoch, lost);
    }

    function _record(address account, uint256 beforeBalance, uint256 afterBalance) private {
        uint64 timestamp = uint64(block.timestamp);
        if (!_registered[account] && afterBalance != 0) {
            _registered[account] = true;
            _holders.push(Holder(account, timestamp));
        }

        // Duplicate timestamps are intentional: strict lookup selects the final earlier entry.
        // Always appending also avoids same-timestamp estimates pricing an overwrite instead
        // of the additional checkpoint that a newly mined timestamp would require.
        _history[account].push(BalanceCheckpoint(timestamp, uint192(afterBalance)));

        if (timestamp >= epochZero) {
            uint64 epoch = (timestamp - epochZero) / EPOCH_DURATION;
            uint192 observedMinimum = uint192(beforeBalance < afterBalance ? beforeBalance : afterBalance);
            EpochMinimum storage minimum = _minimum[epoch][account];
            if (!minimum.observed || observedMinimum < minimum.balance) {
                minimum.balance = observedMinimum;
                minimum.observed = true;
            }
        }
    }
}