namespace Kadet.Quantum.Grover
{
    open Microsoft.Quantum.Canon;
    open Microsoft.Quantum.Math;
    open Microsoft.Quantum.Intrinsic;
    open Microsoft.Quantum.Convert;

    open Kadet.Quantum.Util;

    newtype FlipingOracle = ((Qubit[], Qubit) => Unit);
    newtype Records       = Int[];

    operation IsEqualOracle(state: Qubit[], value: Int, output: Qubit): Unit {
        ApplyIfEquals(state, value, X, output);
    }

    operation GetFromDatabase(database: Records, input: Qubit[], output: Qubit[]): Unit is Adj {
        let max  = Length(database!) - 1;

        for (i in 0..max) {
            let value = database![i];
            ApplyIfEquals(input, i, InitFromInt(_, value), output);
        }
    }

    function PrepareDatabase(database: Records): ((Qubit[], Qubit[]) => Unit is Adj) {
        return GetFromDatabase(database, _, _);
    }

    operation Diffusion(state: Qubit[], scratch: Qubit): Unit {
        ApplyToEach(H, state);
        IsEqualOracle(state, 0, scratch);
        ApplyToEach(H, state);
    }

    operation GroverOperator(oracle: FlipingOracle, state: Qubit[], scratch: Qubit): Unit {
        oracle!(state, scratch);
        Diffusion(state, scratch);
    }

    function GroverLimit(state: Qubit[]): Int {
        return Floor((PI() / 4.0) * PowD(2.0, IntAsDouble(Length(state)) / 2.0));
    }

    operation GroverSearch(state: Qubit[], oracle: FlipingOracle): Unit {
        using (scratch = Qubit()) {
            X(scratch); 
            H(scratch); // make scratch to be in |-> state

            ApplyMultipleTimes(GroverLimit(state), GroverOperator(oracle, _, scratch), state);

            Reset(scratch);
        }
    }
}