library ObservationLib {
    using OverflowSafeComparatorLib for uint32;
    using SafeCast for uint256;

    /// @notice The maximum number of observations
    uint24 public constant MAX_CARDINALITY = 16777215; // 2**24

    /**
    * @notice Observation, which includes an amount and timestamp.
    * @param amount `amount` at `timestamp`.
    * @param timestamp Recorded `timestamp`.
    */
    struct Observation {
        uint224 amount;
        uint32 timestamp;
    }

    /**
    * @notice Fetches Observations `beforeOrAt` and `atOrAfter` a `_target`, eg: where [`beforeOrAt`, `atOrAfter`] is satisfied.
    * The result may be the same Observation, or adjacent Observations.
    * @dev The answer must be contained in the array used when the target is located within the stored Observation.
    * boundaries: older than the most recent Observation and younger, or the same age as, the oldest Observation.
    * @dev  If `_newestObservationIndex` is less than `_oldestObservationIndex`, it means that we've wrapped around the circular buffer.
    *       So the most recent observation will be at `_oldestObservationIndex + _cardinality - 1`, at the beginning of the circular buffer.
    * @param _observations List of Observations to search through.
    * @param _newestObservationIndex Index of the newest Observation. Right side of the circular buffer.
    * @param _oldestObservationIndex Index of the oldest Observation. Left side of the circular buffer.
    * @param _target Timestamp at which we are searching the Observation.
    * @param _cardinality Cardinality of the circular buffer we are searching through.
    * @param _time Timestamp at which we perform the binary search.
    * @return beforeOrAt Observation recorded before, or at, the target.
    * @return atOrAfter Observation recorded at, or after, the target.
    */
    function binarySearch(
        Observation[MAX_CARDINALITY] storage _observations,
        uint24 _newestObservationIndex,
        uint24 _oldestObservationIndex,
        uint32 _target,
        uint24 _cardinality,
        uint32 _time
    ) internal view returns (Observation memory beforeOrAt, Observation memory atOrAfter) {
        uint256 leftSide = _oldestObservationIndex;
        uint256 rightSide = _newestObservationIndex < leftSide
            ? leftSide + _cardinality - 1
            : _newestObservationIndex;
        uint256 currentIndex;

        while (true) {
            // We start our search in the middle of the `leftSide` and `rightSide`.
            // After each iteration, we narrow down the search to the left or the right side while still starting our search in the middle.
            currentIndex = (leftSide + rightSide) / 2;

            beforeOrAt = _observations[uint24(RingBufferLib.wrap(currentIndex, _cardinality))];
            uint32 beforeOrAtTimestamp = beforeOrAt.timestamp;

            // We've landed on an uninitialized timestamp, keep searching higher (more recently).
            if (beforeOrAtTimestamp == 0) {
                leftSide = currentIndex + 1;
                continue;
            }

            atOrAfter = _observations[uint24(RingBufferLib.nextIndex(currentIndex, _cardinality))];

            bool targetAtOrAfter = beforeOrAtTimestamp.lte(_target, _time);

            // Check if we've found the corresponding Observation.
            if (targetAtOrAfter && _target.lte(atOrAfter.timestamp, _time)) {
                break;
            }

            // If `beforeOrAtTimestamp` is greater than `_target`, then we keep searching lower. To the left of the current index.
            if (!targetAtOrAfter) {
                rightSide = currentIndex - 1;
            } else {
                // Otherwise, we keep searching higher. To the left of the current index.
                leftSide = currentIndex + 1;
            }
        }
    }
}
/**
 * @title Observation Library
 * @notice This library allows one to store an array of timestamped values and efficiently binary search them.
 * @dev Largely pulled from Uniswap V3 Oracle.sol: https://github.com/Uniswap/v3-core/blob/c05a0e2c8c08c460fb4d05cfdda30b3ad8deeaac/contracts/libraries/Oracle.sol
 * @author PoolTogether Inc.
 */
function binarySearch(
    Observation[MAX_CARDINALITY] storage _observations,
    uint24 _newestObservationIndex,
    uint24 _oldestObservationIndex,
    uint32 _target,
    uint24 _cardinality,
    uint32 _time
) internal view returns (Observation memory beforeOrAt, Observation memory atOrAfter) {
    uint256 leftSide = _oldestObservationIndex;
    uint256 rightSide = _newestObservationIndex < leftSide
        ? leftSide + _cardinality - 1
        : _newestObservationIndex;
    uint256 currentIndex;

    while (true) {
        // We start our search in the middle of the `leftSide` and `rightSide`.
        // After each iteration, we narrow down the search to the left or the right side while still starting our search in the middle.
        currentIndex = (leftSide + rightSide) / 2;

        beforeOrAt = _observations[uint24(RingBufferLib.wrap(currentIndex, _cardinality))];
        uint32 beforeOrAtTimestamp = beforeOrAt.timestamp;

        // We've landed on an uninitialized timestamp, keep searching higher (more recently).
        if (beforeOrAtTimestamp == 0) {
            leftSide = currentIndex + 1;
            continue;
        }

        atOrAfter = _observations[uint24(RingBufferLib.nextIndex(currentIndex, _cardinality))];

        bool targetAtOrAfter = beforeOrAtTimestamp.lte(_target, _time);

        // Check if we've found the corresponding Observation.
        if (targetAtOrAfter && _target.lte(atOrAfter.timestamp, _time)) {
            break;
        }

        // If `beforeOrAtTimestamp` is greater than `_target`, then we keep searching lower. To the left of the current index.
        if (!targetAtOrAfter) {
            rightSide = currentIndex - 1;
        } else {
            // Otherwise, we keep searching higher. To the left of the current index.
            leftSide = currentIndex + 1;
        }
    }
}

/**
 * @notice Fetches Observations `beforeOrAt` and `atOrAfter` a `_target`, eg: where [`beforeOrAt`, `atOrAfter`] is satisfied.
 * The result may be the same Observation, or adjacent Observations.
 * @dev The answer must be contained in the array used when the target is located within the stored Observation.
 * boundaries: older than the most recent Observation and younger, or the same age as, the oldest Observation.
 * @dev  If `_newestObservationIndex` is less than `_oldestObservationIndex`, it means that we've wrapped around the circular buffer.
 *       So the most recent observation will be at `_oldestObservationIndex + _cardinality - 1`, at the beginning of the circular buffer.
 * @param _observations List of Observations to search through.
 * @param _newestObservationIndex Index of the newest Observation. Right side of the circular buffer.
 * @param _oldestObservationIndex Index of the oldest Observation. Left side of the circular buffer.
 * @param _target Timestamp at which we are searching the Observation.
 * @param _cardinality Cardinality of the circular buffer we are searching through.
 * @param _time Timestamp at which we perform the binary search.
 * @return beforeOrAt Observation recorded before, or at, the target.
 * @return atOrAfter Observation recorded at, or after, the target.
 */