contract UniswapV2SlidingOracle {
    using FixedPoint for *;
    using SafeMath for uint;

    struct Observation {
        uint timestamp;
        uint price0Cumulative;
        uint price1Cumulative;
        uint timeElapsed;
    }
    
    modifier keeper() {
        require(KFI.isKeeper(msg.sender), "::isKeeper: keeper is not registered");
        _;
    }
    
    modifier upkeep() {
        require(KFI.isKeeper(msg.sender), "::isKeeper: keeper is not registered");
        _;
        KFI.worked(msg.sender);
    }
    
    address public governance;
    address public pendingGovernance;
    
    /**
     * @notice Allows governance to change governance (for future upgradability)
     * @param _governance new governance address to set
     */
    function setGovernance(address _governance) external {
        require(msg.sender == governance, "setGovernance: !gov");
        pendingGovernance = _governance;
    }

    /**
     * @notice Allows pendingGovernance to accept their role as governance (protection pattern)
     */
    function acceptGovernance() external {
        require(msg.sender == pendingGovernance, "acceptGovernance: !pendingGov");
        governance = pendingGovernance;
    }
    
    IKeeperFi public constant KFI = IKeeperFi(0x4e59DFe7c5D34C498Cfe18f0b6dB10941d6E1A8a);

    address public constant factory = 0x5C69bEe701ef814a2B6a3EDD4B1652CB9cc5aA6f;
    // this is redundant with granularity and windowSize, but stored for gas savings & informational purposes.
    uint public constant periodSize = 1800;
    
    address[] internal _pairs;
    mapping(address => bool) internal _known;
    
    function pairs() external view returns (address[] memory) {
        return _pairs;
    }

    // mapping from pair address to a list of price observations of that pair
    mapping(address => Observation[]) public pairObservations;
    mapping(address => uint) public lastUpdated;
    mapping(address => Observation) public lastObservation;

    constructor() public {
        governance = msg.sender;
    }
    
    function updatePair(address pair) external keeper returns (bool) {
        return _update(pair);
    }
    
    function update(address tokenA, address tokenB) external keeper returns (bool) {
        address pair = UniswapV2Library.pairFor(factory, tokenA, tokenB);
        return _update(pair);
    }
    
    function add(address tokenA, address tokenB) external {
        require(msg.sender == governance, "UniswapV2SlidingOracle::add: !gov");
        address pair = UniswapV2Library.pairFor(factory, tokenA, tokenB);
        require(!_known[pair], "known");
        _known[pair] = true;
        _pairs.push(pair);

        (uint price0Cumulative, uint price1Cumulative,) = UniswapV2SlidingOracleLibrary.currentCumulativePrices(pair);
        lastObservation[pair] = Observation(block.timestamp, price0Cumulative, price1Cumulative, 0);
        pairObservations[pair].push(lastObservation[pair]);
        lastUpdated[pair] = block.timestamp;
    }
    
    function work() public upkeep {
        bool worked = _updateAll();
        require(worked, "UniswapV2SlidingOracle: !work");
    }
    
    function _updateAll() internal returns (bool updated) {
        for (uint i = 0; i < _pairs.length; i++) {
            if (_update(_pairs[i])) {
                updated = true;
            }
        }
    }
    
    function updateFor(uint i, uint length) external keeper returns (bool updated) {
        for (; i < length; i++) {
            if (_update(_pairs[i])) {
                updated = true;
            }
        }
    }
    
    function workable(address pair) public view returns (bool) {
        return (block.timestamp - lastUpdated[pair]) > periodSize;
    }
    
    function workable() external view returns (bool) {
        for (uint i = 0; i < _pairs.length; i++) {
            if (workable(_pairs[i])) {
                return true;
            }
        }
        return false;
    }
    
    function _update(address pair) internal returns (bool) {
        // we only want to commit updates once per period (i.e. windowSize / granularity)
        uint timeElapsed = block.timestamp - lastUpdated[pair];
        if (timeElapsed > periodSize) {
            (uint price0Cumulative, uint price1Cumulative,) = UniswapV2SlidingOracleLibrary.currentCumulativePrices(pair);
            lastObservation[pair] = Observation(block.timestamp, price0Cumulative, price1Cumulative, timeElapsed);
            pairObservations[pair].push(lastObservation[pair]);
            lastUpdated[pair] = block.timestamp;
            return true;
        }
        return false;
    }
    
    function computeAmountOut(
        uint priceCumulativeStart, uint priceCumulativeEnd,
        uint timeElapsed, uint amountIn
    ) private pure returns (uint amountOut) {
        // overflow is desired.
        FixedPoint.uq112x112 memory priceAverage = FixedPoint.uq112x112(
            uint224((priceCumulativeEnd - priceCumulativeStart) / timeElapsed)
        );
        amountOut = priceAverage.mul(amountIn).decode144();
    }
    
    function _valid(address pair, uint age) internal view returns (bool) {
        return (block.timestamp - lastUpdated[pair]) <= age;
    }
    
    function current(address tokenIn, uint amountIn, address tokenOut) external view returns (uint amountOut) {
        address pair = UniswapV2Library.pairFor(factory, tokenIn, tokenOut);
        require(_valid(pair, periodSize.mul(2)), "UniswapV2SlidingOracle::quote: stale prices");
        (address token0,) = UniswapV2Library.sortTokens(tokenIn, tokenOut);
        
        (uint price0Cumulative, uint price1Cumulative,) = UniswapV2SlidingOracleLibrary.currentCumulativePrices(pair);
        uint timeElapsed = block.timestamp - lastObservation[pair].timestamp;
        timeElapsed = timeElapsed == 0 ? 1 : timeElapsed;
        if (token0 == tokenIn) {
            return computeAmountOut(lastObservation[pair].price0Cumulative, price0Cumulative, timeElapsed, amountIn);
        } else {
            return computeAmountOut(lastObservation[pair].price1Cumulative, price1Cumulative, timeElapsed, amountIn);
        }
    }
    
    function quote(address tokenIn, uint amountIn, address tokenOut, uint granularity) external view returns (uint amountOut) {
        address pair = UniswapV2Library.pairFor(factory, tokenIn, tokenOut);
        require(_valid(pair, periodSize.mul(granularity)), "UniswapV2SlidingOracle::quote: stale prices");
        (address token0,) = UniswapV2Library.sortTokens(tokenIn, tokenOut);
        
        uint priceAverageCumulative = 0;
        uint length = pairObservations[pair].length-1;
        uint i = length.sub(granularity);
        
        
        uint nextIndex = 0;
        if (token0 == tokenIn) {
            for (; i < length; i++) {
                nextIndex = i+1;
                priceAverageCumulative += computeAmountOut(
                    pairObservations[pair][i].price0Cumulative, 
                    pairObservations[pair][nextIndex].price0Cumulative, pairObservations[pair][nextIndex].timeElapsed, amountIn);
            }
        } else {
            for (; i < length; i++) {
                nextIndex = i+1;
                priceAverageCumulative += computeAmountOut(
                    pairObservations[pair][i].price1Cumulative, 
                    pairObservations[pair][nextIndex].price1Cumulative, pairObservations[pair][nextIndex].timeElapsed, amountIn);
            }
        }
        return priceAverageCumulative.div(granularity);
    }
}
// sliding oracle that uses observations collected to provide moving price averages in the past
function acceptGovernance() external {
    require(msg.sender == pendingGovernance, "acceptGovernance: !pendingGov");
    governance = pendingGovernance;
}

/**
 * @notice Allows pendingGovernance to accept their role as governance (protection pattern)
 */