/*
 This file is part of GNU Taler
 (C) 2021 Taler Systems S.A.

 GNU Taler is free software; you can redistribute it and/or modify it under the
 terms of the GNU General Public License as published by the Free Software
 Foundation; either version 3, or (at your option) any later version.

 GNU Taler is distributed in the hope that it will be useful, but WITHOUT ANY
 WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR
 A PARTICULAR PURPOSE.  See the GNU General Public License for more details.

 You should have received a copy of the GNU General Public License along with
 GNU Taler; see the file COPYING.  If not, see <http://www.gnu.org/licenses/>
 */

/**
 * Selection of coins for payments.
 *
 * @author Florian Dold
 */

/**
 * Imports.
 */
import { GlobalIDB } from "@gnu-taler/idb-bridge";
import {
  AbsoluteTime,
  AgeCommitmentProof,
  AgeRestriction,
  AmountJson,
  AmountResponse,
  Amounts,
  CoinStatus,
  ConvertAmountRequest,
  DenominationInfo,
  DenominationPubKey,
  DenomSelectionState,
  Duration,
  ForcedCoinSel,
  ForcedDenomSel,
  GetAmountRequest,
  GetPlanForOperationRequest,
  j2s,
  Logger,
  parsePaytoUri,
  PayCoinSelection,
  PayMerchantInsufficientBalanceDetails,
  strcmp,
  TransactionAmountMode,
  TransactionType,
} from "@gnu-taler/taler-util";
import {
  AllowedAuditorInfo,
  AllowedExchangeInfo,
  DenominationRecord,
} from "../db.js";
import {
  CoinAvailabilityRecord,
  getExchangeDetails,
  isWithdrawableDenom,
} from "../index.js";
import { InternalWalletState } from "../internal-wallet-state.js";
import { getMerchantPaymentBalanceDetails } from "../operations/balance.js";
import { checkDbInvariant, checkLogicInvariant } from "./invariants.js";

const logger = new Logger("coinSelection.ts");

/**
 * Structure to describe a coin that is available to be
 * used in a payment.
 */
export interface AvailableCoinInfo {
  /**
   * Public key of the coin.
   */
  coinPub: string;

  /**
   * Coin's denomination public key.
   *
   * FIXME: We should only need the denomPubHash here, if at all.
   */
  denomPub: DenominationPubKey;

  /**
   * Full value of the coin.
   */
  value: AmountJson;

  /**
   * Amount still remaining (typically the full amount,
   * as coins are always refreshed after use.)
   */
  availableAmount: AmountJson;

  /**
   * Deposit fee for the coin.
   */
  feeDeposit: AmountJson;

  exchangeBaseUrl: string;

  maxAge: number;
  ageCommitmentProof?: AgeCommitmentProof;
}

export type PreviousPayCoins = {
  coinPub: string;
  contribution: AmountJson;
  feeDeposit: AmountJson;
  exchangeBaseUrl: string;
}[];

export interface CoinCandidateSelection {
  candidateCoins: AvailableCoinInfo[];
  wireFeesPerExchange: Record<string, AmountJson>;
}

export interface SelectPayCoinRequest {
  candidates: CoinCandidateSelection;
  contractTermsAmount: AmountJson;
  depositFeeLimit: AmountJson;
  wireFeeLimit: AmountJson;
  wireFeeAmortization: number;
  prevPayCoins?: PreviousPayCoins;
  requiredMinimumAge?: number;
}

export interface CoinSelectionTally {
  /**
   * Amount that still needs to be paid.
   * May increase during the computation when fees need to be covered.
   */
  amountPayRemaining: AmountJson;

  /**
   * Allowance given by the merchant towards wire fees
   */
  amountWireFeeLimitRemaining: AmountJson;

  /**
   * Allowance given by the merchant towards deposit fees
   * (and wire fees after wire fee limit is exhausted)
   */
  amountDepositFeeLimitRemaining: AmountJson;

  customerDepositFees: AmountJson;

  customerWireFees: AmountJson;

  wireFeeCoveredForExchange: Set<string>;

  lastDepositFee: AmountJson;
}

/**
 * Account for the fees of spending a coin.
 */
function tallyFees(
  tally: Readonly<CoinSelectionTally>,
  wireFeesPerExchange: Record<string, AmountJson>,
  wireFeeAmortization: number,
  exchangeBaseUrl: string,
  feeDeposit: AmountJson,
): CoinSelectionTally {
  const currency = tally.amountPayRemaining.currency;
  let amountWireFeeLimitRemaining = tally.amountWireFeeLimitRemaining;
  let amountDepositFeeLimitRemaining = tally.amountDepositFeeLimitRemaining;
  let customerDepositFees = tally.customerDepositFees;
  let customerWireFees = tally.customerWireFees;
  let amountPayRemaining = tally.amountPayRemaining;
  const wireFeeCoveredForExchange = new Set(tally.wireFeeCoveredForExchange);

  if (!tally.wireFeeCoveredForExchange.has(exchangeBaseUrl)) {
    const wf =
      wireFeesPerExchange[exchangeBaseUrl] ?? Amounts.zeroOfCurrency(currency);
    const wfForgiven = Amounts.min(amountWireFeeLimitRemaining, wf);
    amountWireFeeLimitRemaining = Amounts.sub(
      amountWireFeeLimitRemaining,
      wfForgiven,
    ).amount;
    // The remaining, amortized amount needs to be paid by the
    // wallet or covered by the deposit fee allowance.
    let wfRemaining = Amounts.divide(
      Amounts.sub(wf, wfForgiven).amount,
      wireFeeAmortization,
    );

    // This is the amount forgiven via the deposit fee allowance.
    const wfDepositForgiven = Amounts.min(
      amountDepositFeeLimitRemaining,
      wfRemaining,
    );
    amountDepositFeeLimitRemaining = Amounts.sub(
      amountDepositFeeLimitRemaining,
      wfDepositForgiven,
    ).amount;

    wfRemaining = Amounts.sub(wfRemaining, wfDepositForgiven).amount;
    customerWireFees = Amounts.add(customerWireFees, wfRemaining).amount;
    amountPayRemaining = Amounts.add(amountPayRemaining, wfRemaining).amount;

    wireFeeCoveredForExchange.add(exchangeBaseUrl);
  }

  const dfForgiven = Amounts.min(feeDeposit, amountDepositFeeLimitRemaining);

  amountDepositFeeLimitRemaining = Amounts.sub(
    amountDepositFeeLimitRemaining,
    dfForgiven,
  ).amount;

  // How much does the user spend on deposit fees for this coin?
  const dfRemaining = Amounts.sub(feeDeposit, dfForgiven).amount;
  customerDepositFees = Amounts.add(customerDepositFees, dfRemaining).amount;
  amountPayRemaining = Amounts.add(amountPayRemaining, dfRemaining).amount;

  return {
    amountDepositFeeLimitRemaining,
    amountPayRemaining,
    amountWireFeeLimitRemaining,
    customerDepositFees,
    customerWireFees,
    wireFeeCoveredForExchange,
    lastDepositFee: feeDeposit,
  };
}

export type SelectPayCoinsResult =
  | {
      type: "failure";
      insufficientBalanceDetails: PayMerchantInsufficientBalanceDetails;
    }
  | { type: "success"; coinSel: PayCoinSelection };

/**
 * Given a list of candidate coins, select coins to spend under the merchant's
 * constraints.
 *
 * The prevPayCoins can be specified to "repair" a coin selection
 * by adding additional coins, after a broken (e.g. double-spent) coin
 * has been removed from the selection.
 *
 * This function is only exported for the sake of unit tests.
 */
export async function selectPayCoinsNew(
  ws: InternalWalletState,
  req: SelectPayCoinRequestNg,
): Promise<SelectPayCoinsResult> {
  const {
    contractTermsAmount,
    depositFeeLimit,
    wireFeeLimit,
    wireFeeAmortization,
  } = req;

  const [candidateDenoms, wireFeesPerExchange] = await selectCandidates(
    ws,
    req,
  );

  const coinPubs: string[] = [];
  const coinContributions: AmountJson[] = [];
  const currency = contractTermsAmount.currency;

  let tally: CoinSelectionTally = {
    amountPayRemaining: contractTermsAmount,
    amountWireFeeLimitRemaining: wireFeeLimit,
    amountDepositFeeLimitRemaining: depositFeeLimit,
    customerDepositFees: Amounts.zeroOfCurrency(currency),
    customerWireFees: Amounts.zeroOfCurrency(currency),
    wireFeeCoveredForExchange: new Set(),
    lastDepositFee: Amounts.zeroOfCurrency(currency),
  };

  const prevPayCoins = req.prevPayCoins ?? [];

  // Look at existing pay coin selection and tally up
  for (const prev of prevPayCoins) {
    tally = tallyFees(
      tally,
      wireFeesPerExchange,
      wireFeeAmortization,
      prev.exchangeBaseUrl,
      prev.feeDeposit,
    );
    tally.amountPayRemaining = Amounts.sub(
      tally.amountPayRemaining,
      prev.contribution,
    ).amount;

    coinPubs.push(prev.coinPub);
    coinContributions.push(prev.contribution);
  }

  let selectedDenom: SelResult | undefined;
  if (req.forcedSelection) {
    selectedDenom = selectForced(req, candidateDenoms);
  } else {
    // FIXME:  Here, we should select coins in a smarter way.
    // Instead of always spending the next-largest coin,
    // we should try to find the smallest coin that covers the
    // amount.
    selectedDenom = selectGreedy(
      req,
      candidateDenoms,
      wireFeesPerExchange,
      tally,
    );
  }

  if (!selectedDenom) {
    const details = await getMerchantPaymentBalanceDetails(ws, {
      acceptedAuditors: req.auditors,
      acceptedExchanges: req.exchanges,
      acceptedWireMethods: [req.wireMethod],
      currency: Amounts.currencyOf(req.contractTermsAmount),
      minAge: req.requiredMinimumAge ?? 0,
    });
    let feeGapEstimate: AmountJson;
    if (
      Amounts.cmp(
        details.balanceMerchantDepositable,
        req.contractTermsAmount,
      ) >= 0
    ) {
      // FIXME: We can probably give a better estimate.
      feeGapEstimate = Amounts.add(
        tally.amountPayRemaining,
        tally.lastDepositFee,
      ).amount;
    } else {
      feeGapEstimate = Amounts.zeroOfAmount(req.contractTermsAmount);
    }
    return {
      type: "failure",
      insufficientBalanceDetails: {
        amountRequested: Amounts.stringify(req.contractTermsAmount),
        balanceAgeAcceptable: Amounts.stringify(details.balanceAgeAcceptable),
        balanceAvailable: Amounts.stringify(details.balanceAvailable),
        balanceMaterial: Amounts.stringify(details.balanceMaterial),
        balanceMerchantAcceptable: Amounts.stringify(
          details.balanceMerchantAcceptable,
        ),
        balanceMerchantDepositable: Amounts.stringify(
          details.balanceMerchantDepositable,
        ),
        feeGapEstimate: Amounts.stringify(feeGapEstimate),
      },
    };
  }

  const finalSel = selectedDenom;

  logger.trace(`coin selection request ${j2s(req)}`);
  logger.trace(`selected coins (via denoms) for payment: ${j2s(finalSel)}`);

  await ws.db
    .mktx((x) => [x.coins, x.denominations])
    .runReadOnly(async (tx) => {
      for (const dph of Object.keys(finalSel)) {
        const selInfo = finalSel[dph];
        const numRequested = selInfo.contributions.length;
        const query = [
          selInfo.exchangeBaseUrl,
          selInfo.denomPubHash,
          selInfo.maxAge,
          CoinStatus.Fresh,
        ];
        logger.info(`query: ${j2s(query)}`);
        const coins =
          await tx.coins.indexes.byExchangeDenomPubHashAndAgeAndStatus.getAll(
            query,
            numRequested,
          );
        if (coins.length != numRequested) {
          throw Error(
            `coin selection failed (not available anymore, got only ${coins.length}/${numRequested})`,
          );
        }
        coinPubs.push(...coins.map((x) => x.coinPub));
        coinContributions.push(...selInfo.contributions);
      }
    });

  return {
    type: "success",
    coinSel: {
      paymentAmount: Amounts.stringify(contractTermsAmount),
      coinContributions: coinContributions.map((x) => Amounts.stringify(x)),
      coinPubs,
      customerDepositFees: Amounts.stringify(tally.customerDepositFees),
      customerWireFees: Amounts.stringify(tally.customerWireFees),
    },
  };
}

function makeAvailabilityKey(
  exchangeBaseUrl: string,
  denomPubHash: string,
  maxAge: number,
): string {
  return `${denomPubHash};${maxAge};${exchangeBaseUrl}`;
}

/**
 * Selection result.
 */
interface SelResult {
  /**
   * Map from an availability key
   * to an array of contributions.
   */
  [avKey: string]: {
    exchangeBaseUrl: string;
    denomPubHash: string;
    maxAge: number;
    contributions: AmountJson[];
  };
}

function selectGreedy(
  req: SelectPayCoinRequestNg,
  candidateDenoms: AvailableDenom[],
  wireFeesPerExchange: Record<string, AmountJson>,
  tally: CoinSelectionTally,
): SelResult | undefined {
  const { wireFeeAmortization } = req;
  const selectedDenom: SelResult = {};
  for (const denom of candidateDenoms) {
    const contributions: AmountJson[] = [];

    // Don't use this coin if depositing it is more expensive than
    // the amount it would give the merchant.
    if (Amounts.cmp(denom.feeDeposit, denom.value) > 0) {
      tally.lastDepositFee = Amounts.parseOrThrow(denom.feeDeposit);
      continue;
    }

    for (
      let i = 0;
      i < denom.numAvailable && Amounts.isNonZero(tally.amountPayRemaining);
      i++
    ) {
      tally = tallyFees(
        tally,
        wireFeesPerExchange,
        wireFeeAmortization,
        denom.exchangeBaseUrl,
        Amounts.parseOrThrow(denom.feeDeposit),
      );

      const coinSpend = Amounts.max(
        Amounts.min(tally.amountPayRemaining, denom.value),
        denom.feeDeposit,
      );

      tally.amountPayRemaining = Amounts.sub(
        tally.amountPayRemaining,
        coinSpend,
      ).amount;

      contributions.push(coinSpend);
    }

    if (contributions.length) {
      const avKey = makeAvailabilityKey(
        denom.exchangeBaseUrl,
        denom.denomPubHash,
        denom.maxAge,
      );
      let sd = selectedDenom[avKey];
      if (!sd) {
        sd = {
          contributions: [],
          denomPubHash: denom.denomPubHash,
          exchangeBaseUrl: denom.exchangeBaseUrl,
          maxAge: denom.maxAge,
        };
      }
      sd.contributions.push(...contributions);
      selectedDenom[avKey] = sd;
    }
  }
  return Amounts.isZero(tally.amountPayRemaining) ? selectedDenom : undefined;
}

function selectForced(
  req: SelectPayCoinRequestNg,
  candidateDenoms: AvailableDenom[],
): SelResult | undefined {
  const selectedDenom: SelResult = {};

  const forcedSelection = req.forcedSelection;
  checkLogicInvariant(!!forcedSelection);

  for (const forcedCoin of forcedSelection.coins) {
    let found = false;
    for (const aci of candidateDenoms) {
      if (aci.numAvailable <= 0) {
        continue;
      }
      if (Amounts.cmp(aci.value, forcedCoin.value) === 0) {
        aci.numAvailable--;
        const avKey = makeAvailabilityKey(
          aci.exchangeBaseUrl,
          aci.denomPubHash,
          aci.maxAge,
        );
        let sd = selectedDenom[avKey];
        if (!sd) {
          sd = {
            contributions: [],
            denomPubHash: aci.denomPubHash,
            exchangeBaseUrl: aci.exchangeBaseUrl,
            maxAge: aci.maxAge,
          };
        }
        sd.contributions.push(Amounts.parseOrThrow(forcedCoin.value));
        selectedDenom[avKey] = sd;
        found = true;
        break;
      }
    }
    if (!found) {
      throw Error("can't find coin for forced coin selection");
    }
  }

  return selectedDenom;
}

export interface SelectPayCoinRequestNg {
  exchanges: AllowedExchangeInfo[];
  auditors: AllowedAuditorInfo[];
  wireMethod: string;
  contractTermsAmount: AmountJson;
  depositFeeLimit: AmountJson;
  wireFeeLimit: AmountJson;
  wireFeeAmortization: number;
  prevPayCoins?: PreviousPayCoins;
  requiredMinimumAge?: number;
  forcedSelection?: ForcedCoinSel;
}

export type AvailableDenom = DenominationInfo & {
  maxAge: number;
  numAvailable: number;
};

async function selectCandidates(
  ws: InternalWalletState,
  req: SelectPayCoinRequestNg,
): Promise<[AvailableDenom[], Record<string, AmountJson>]> {
  return await ws.db
    .mktx((x) => [
      x.exchanges,
      x.exchangeDetails,
      x.denominations,
      x.coinAvailability,
    ])
    .runReadOnly(async (tx) => {
      // FIXME: Use the existing helper (from balance.ts) to
      // get acceptable exchanges.
      const denoms: AvailableDenom[] = [];
      const exchanges = await tx.exchanges.iter().toArray();
      const wfPerExchange: Record<string, AmountJson> = {};
      for (const exchange of exchanges) {
        const exchangeDetails = await getExchangeDetails(tx, exchange.baseUrl);
        // 1.- exchange has same currency
        if (exchangeDetails?.currency !== req.contractTermsAmount.currency) {
          continue;
        }
        let wireMethodFee: string | undefined;
        // 2.- exchange supports wire method
        for (const acc of exchangeDetails.wireInfo.accounts) {
          const pp = parsePaytoUri(acc.payto_uri);
          checkLogicInvariant(!!pp);
          if (pp.targetType === req.wireMethod) {
            // also check that wire method is supported now
            const wireFeeStr = exchangeDetails.wireInfo.feesForType[
              req.wireMethod
            ]?.find((x) => {
              return AbsoluteTime.isBetween(
                AbsoluteTime.now(),
                AbsoluteTime.fromProtocolTimestamp(x.startStamp),
                AbsoluteTime.fromProtocolTimestamp(x.endStamp),
              );
            })?.wireFee;
            if (wireFeeStr) {
              wireMethodFee = wireFeeStr;
            }
            break;
          }
        }
        if (!wireMethodFee) {
          break;
        }
        wfPerExchange[exchange.baseUrl] = Amounts.parseOrThrow(wireMethodFee);
        // 3.- exchange is trusted in the exchange list or auditor list
        let accepted = false;
        for (const allowedExchange of req.exchanges) {
          if (allowedExchange.exchangePub === exchangeDetails.masterPublicKey) {
            accepted = true;
            break;
          }
        }
        for (const allowedAuditor of req.auditors) {
          for (const providedAuditor of exchangeDetails.auditors) {
            if (allowedAuditor.auditorPub === providedAuditor.auditor_pub) {
              accepted = true;
              break;
            }
          }
        }
        if (!accepted) {
          continue;
        }
        //4.- filter coins restricted by age
        let ageLower = 0;
        let ageUpper = AgeRestriction.AGE_UNRESTRICTED;
        if (req.requiredMinimumAge) {
          ageLower = req.requiredMinimumAge;
        }
        const myExchangeCoins =
          await tx.coinAvailability.indexes.byExchangeAgeAvailability.getAll(
            GlobalIDB.KeyRange.bound(
              [exchangeDetails.exchangeBaseUrl, ageLower, 1],
              [
                exchangeDetails.exchangeBaseUrl,
                ageUpper,
                Number.MAX_SAFE_INTEGER,
              ],
            ),
          );
        //5.- save denoms with how many coins are available
        // FIXME: Check that the individual denomination is audited!
        // FIXME: Should we exclude denominations that are
        // not spendable anymore?
        for (const coinAvail of myExchangeCoins) {
          const denom = await tx.denominations.get([
            coinAvail.exchangeBaseUrl,
            coinAvail.denomPubHash,
          ]);
          checkDbInvariant(!!denom);
          if (denom.isRevoked || !denom.isOffered) {
            continue;
          }
          denoms.push({
            ...DenominationRecord.toDenomInfo(denom),
            numAvailable: coinAvail.freshCoinCount ?? 0,
            maxAge: coinAvail.maxAge,
          });
        }
      }
      // Sort by available amount (descending),  deposit fee (ascending) and
      // denomPub (ascending) if deposit fee is the same
      // (to guarantee deterministic results)
      denoms.sort(
        (o1, o2) =>
          -Amounts.cmp(o1.value, o2.value) ||
          Amounts.cmp(o1.feeDeposit, o2.feeDeposit) ||
          strcmp(o1.denomPubHash, o2.denomPubHash),
      );
      return [denoms, wfPerExchange];
    });
}

/**
 * Get a list of denominations (with repetitions possible)
 * whose total value is as close as possible to the available
 * amount, but never larger.
 */
export function selectWithdrawalDenominations(
  amountAvailable: AmountJson,
  denoms: DenominationRecord[],
  denomselAllowLate: boolean = false,
): DenomSelectionState {
  let remaining = Amounts.copy(amountAvailable);

  const selectedDenoms: {
    count: number;
    denomPubHash: string;
  }[] = [];

  let totalCoinValue = Amounts.zeroOfCurrency(amountAvailable.currency);
  let totalWithdrawCost = Amounts.zeroOfCurrency(amountAvailable.currency);

  denoms = denoms.filter((d) => isWithdrawableDenom(d, denomselAllowLate));
  denoms.sort((d1, d2) =>
    Amounts.cmp(
      DenominationRecord.getValue(d2),
      DenominationRecord.getValue(d1),
    ),
  );

  for (const d of denoms) {
    const cost = Amounts.add(
      DenominationRecord.getValue(d),
      d.fees.feeWithdraw,
    ).amount;
    const res = Amounts.divmod(remaining, cost);
    const count = res.quotient;
    remaining = Amounts.sub(remaining, Amounts.mult(cost, count).amount).amount;
    if (count > 0) {
      totalCoinValue = Amounts.add(
        totalCoinValue,
        Amounts.mult(DenominationRecord.getValue(d), count).amount,
      ).amount;
      totalWithdrawCost = Amounts.add(
        totalWithdrawCost,
        Amounts.mult(cost, count).amount,
      ).amount;
      selectedDenoms.push({
        count,
        denomPubHash: d.denomPubHash,
      });
    }

    if (Amounts.isZero(remaining)) {
      break;
    }
  }

  if (logger.shouldLogTrace()) {
    logger.trace(
      `selected withdrawal denoms for ${Amounts.stringify(totalCoinValue)}`,
    );
    for (const sd of selectedDenoms) {
      logger.trace(`denom_pub_hash=${sd.denomPubHash}, count=${sd.count}`);
    }
    logger.trace("(end of withdrawal denom list)");
  }

  return {
    selectedDenoms,
    totalCoinValue: Amounts.stringify(totalCoinValue),
    totalWithdrawCost: Amounts.stringify(totalWithdrawCost),
  };
}

export function selectForcedWithdrawalDenominations(
  amountAvailable: AmountJson,
  denoms: DenominationRecord[],
  forcedDenomSel: ForcedDenomSel,
  denomselAllowLate: boolean,
): DenomSelectionState {
  const selectedDenoms: {
    count: number;
    denomPubHash: string;
  }[] = [];

  let totalCoinValue = Amounts.zeroOfCurrency(amountAvailable.currency);
  let totalWithdrawCost = Amounts.zeroOfCurrency(amountAvailable.currency);

  denoms = denoms.filter((d) => isWithdrawableDenom(d, denomselAllowLate));
  denoms.sort((d1, d2) =>
    Amounts.cmp(
      DenominationRecord.getValue(d2),
      DenominationRecord.getValue(d1),
    ),
  );

  for (const fds of forcedDenomSel.denoms) {
    const count = fds.count;
    const denom = denoms.find((x) => {
      return Amounts.cmp(DenominationRecord.getValue(x), fds.value) == 0;
    });
    if (!denom) {
      throw Error(
        `unable to find denom for forced selection (value ${fds.value})`,
      );
    }
    const cost = Amounts.add(
      DenominationRecord.getValue(denom),
      denom.fees.feeWithdraw,
    ).amount;
    totalCoinValue = Amounts.add(
      totalCoinValue,
      Amounts.mult(DenominationRecord.getValue(denom), count).amount,
    ).amount;
    totalWithdrawCost = Amounts.add(
      totalWithdrawCost,
      Amounts.mult(cost, count).amount,
    ).amount;
    selectedDenoms.push({
      count,
      denomPubHash: denom.denomPubHash,
    });
  }

  return {
    selectedDenoms,
    totalCoinValue: Amounts.stringify(totalCoinValue),
    totalWithdrawCost: Amounts.stringify(totalWithdrawCost),
  };
}

function getCoinsFilter(req: GetPlanForOperationRequest): CoinsFilter {
  switch (req.type) {
    case TransactionType.Withdrawal: {
      return {
        exchanges:
          req.exchangeUrl === undefined ? undefined : [req.exchangeUrl],
      };
    }
    case TransactionType.Deposit: {
      const payto = parsePaytoUri(req.account);
      if (!payto) {
        throw Error(`wrong payto ${req.account}`);
      }
      return {
        wireMethod: payto.targetType,
      };
    }
  }
}

/**
 * If the operation going to be plan subtracts
 * or adds amount in the wallet db
 */
export enum OperationType {
  Credit = "credit",
  Debit = "debit",
}

function getOperationType(txType: TransactionType): OperationType {
  const operationType =
    txType === TransactionType.Withdrawal
      ? OperationType.Credit
      : txType === TransactionType.Deposit
      ? OperationType.Debit
      : undefined;
  if (!operationType) {
    throw Error(`operation type ${txType} not yet supported`);
  }
  return operationType;
}

interface RefreshChoice {
  /**
   * Amount that need to be covered
   */
  gap: AmountJson;
  totalFee: AmountJson;
  selected: CoinInfo;
  totalChangeValue: AmountJson;
  refreshEffective: AmountJson;
  coins: { info: CoinInfo; size: number }[];

  // totalValue: AmountJson;
  // totalDepositFee: AmountJson;
  // totalRefreshFee: AmountJson;
  // totalChangeContribution: AmountJson;
  // totalChangeWithdrawalFee: AmountJson;
}

interface AvailableCoins {
  list: CoinInfo[];
  exchanges: Record<string, ExchangeInfo>;
}
interface SelectedCoins {
  totalValue: AmountJson;
  coins: { info: CoinInfo; size: number }[];
  refresh?: RefreshChoice;
}

export interface CoinInfo {
  id: string;
  value: AmountJson;
  denomDeposit: AmountJson;
  denomWithdraw: AmountJson;
  denomRefresh: AmountJson;
  totalAvailable: number | undefined;
  exchangeWire: AmountJson | undefined;
  exchangePurse: AmountJson | undefined;
  duration: Duration;
  exchangeBaseUrl: string;
  maxAge: number;
}
interface ExchangeInfo {
  wireFee: AmountJson | undefined;
  purseFee: AmountJson | undefined;
  creditDeadline: AbsoluteTime;
  debitDeadline: AbsoluteTime;
}

interface CoinsFilter {
  shouldCalculatePurseFee?: boolean;
  exchanges?: string[];
  wireMethod?: string;
  ageRestricted?: number;
}
/**
 * Get all the denoms that can be used for a operation that is limited
 * by the following restrictions.
 * This function is costly (by the database access) but with high chances
 * of being cached
 */
async function getAvailableDenoms(
  ws: InternalWalletState,
  op: TransactionType,
  currency: string,
  filters: CoinsFilter = {},
): Promise<AvailableCoins> {
  const operationType = getOperationType(TransactionType.Deposit);

  return await ws.db
    .mktx((x) => [
      x.exchanges,
      x.exchangeDetails,
      x.denominations,
      x.coinAvailability,
    ])
    .runReadOnly(async (tx) => {
      const list: CoinInfo[] = [];
      const exchanges: Record<string, ExchangeInfo> = {};

      const databaseExchanges = await tx.exchanges.iter().toArray();
      const filteredExchanges =
        filters.exchanges ?? databaseExchanges.map((e) => e.baseUrl);

      for (const exchangeBaseUrl of filteredExchanges) {
        const exchangeDetails = await getExchangeDetails(tx, exchangeBaseUrl);
        // 1.- exchange has same currency
        if (exchangeDetails?.currency !== currency) {
          continue;
        }

        let deadline = AbsoluteTime.never();
        // 2.- exchange supports wire method
        let wireFee: AmountJson | undefined;
        if (filters.wireMethod) {
          const wireMethodWithDates =
            exchangeDetails.wireInfo.feesForType[filters.wireMethod];

          if (!wireMethodWithDates) {
            throw Error(
              `exchange ${exchangeBaseUrl} doesn't have wire method ${filters.wireMethod}`,
            );
          }
          const wireMethodFee = wireMethodWithDates.find((x) => {
            return AbsoluteTime.isBetween(
              AbsoluteTime.now(),
              AbsoluteTime.fromProtocolTimestamp(x.startStamp),
              AbsoluteTime.fromProtocolTimestamp(x.endStamp),
            );
          });

          if (!wireMethodFee) {
            throw Error(
              `exchange ${exchangeBaseUrl} doesn't have wire fee defined for this period`,
            );
          }
          wireFee = Amounts.parseOrThrow(wireMethodFee.wireFee);
          deadline = AbsoluteTime.min(
            deadline,
            AbsoluteTime.fromProtocolTimestamp(wireMethodFee.endStamp),
          );
        }
        // exchanges[exchangeBaseUrl].wireFee = wireMethodFee;

        // 3.- exchange supports wire method
        let purseFee: AmountJson | undefined;
        if (filters.shouldCalculatePurseFee) {
          const purseFeeFound = exchangeDetails.globalFees.find((x) => {
            return AbsoluteTime.isBetween(
              AbsoluteTime.now(),
              AbsoluteTime.fromProtocolTimestamp(x.startDate),
              AbsoluteTime.fromProtocolTimestamp(x.endDate),
            );
          });
          if (!purseFeeFound) {
            throw Error(
              `exchange ${exchangeBaseUrl} doesn't have purse fee defined for this period`,
            );
          }
          purseFee = Amounts.parseOrThrow(purseFeeFound.purseFee);
          deadline = AbsoluteTime.min(
            deadline,
            AbsoluteTime.fromProtocolTimestamp(purseFeeFound.endDate),
          );
        }

        let creditDeadline = AbsoluteTime.never();
        let debitDeadline = AbsoluteTime.never();
        //4.- filter coins restricted by age
        if (operationType === OperationType.Credit) {
          const ds = await tx.denominations.indexes.byExchangeBaseUrl.getAll(
            exchangeBaseUrl,
          );
          for (const denom of ds) {
            const expiresWithdraw = AbsoluteTime.fromProtocolTimestamp(
              denom.stampExpireWithdraw,
            );
            const expiresDeposit = AbsoluteTime.fromProtocolTimestamp(
              denom.stampExpireDeposit,
            );
            creditDeadline = AbsoluteTime.min(deadline, expiresWithdraw);
            debitDeadline = AbsoluteTime.min(deadline, expiresDeposit);
            list.push(
              buildCoinInfoFromDenom(
                denom,
                purseFee,
                wireFee,
                AgeRestriction.AGE_UNRESTRICTED,
                Number.MAX_SAFE_INTEGER, // Max withdrawable from single denom
              ),
            );
          }
        } else {
          const ageLower = filters.ageRestricted ?? 0;
          const ageUpper = AgeRestriction.AGE_UNRESTRICTED;

          const myExchangeCoins =
            await tx.coinAvailability.indexes.byExchangeAgeAvailability.getAll(
              GlobalIDB.KeyRange.bound(
                [exchangeDetails.exchangeBaseUrl, ageLower, 1],
                [
                  exchangeDetails.exchangeBaseUrl,
                  ageUpper,
                  Number.MAX_SAFE_INTEGER,
                ],
              ),
            );
          //5.- save denoms with how many coins are available
          // FIXME: Check that the individual denomination is audited!
          // FIXME: Should we exclude denominations that are
          // not spendable anymore?
          for (const coinAvail of myExchangeCoins) {
            const denom = await tx.denominations.get([
              coinAvail.exchangeBaseUrl,
              coinAvail.denomPubHash,
            ]);
            checkDbInvariant(!!denom);
            if (denom.isRevoked || !denom.isOffered) {
              continue;
            }
            const expiresWithdraw = AbsoluteTime.fromProtocolTimestamp(
              denom.stampExpireWithdraw,
            );
            const expiresDeposit = AbsoluteTime.fromProtocolTimestamp(
              denom.stampExpireDeposit,
            );
            creditDeadline = AbsoluteTime.min(deadline, expiresWithdraw);
            debitDeadline = AbsoluteTime.min(deadline, expiresDeposit);
            list.push(
              buildCoinInfoFromDenom(
                denom,
                purseFee,
                wireFee,
                coinAvail.maxAge,
                coinAvail.freshCoinCount,
              ),
            );
          }
        }

        exchanges[exchangeBaseUrl] = {
          purseFee,
          wireFee,
          debitDeadline,
          creditDeadline,
        };
      }

      return { list, exchanges };
    });
}

function buildCoinInfoFromDenom(
  denom: DenominationRecord,
  purseFee: AmountJson | undefined,
  wireFee: AmountJson | undefined,
  maxAge: number,
  total: number,
): CoinInfo {
  return {
    id: denom.denomPubHash,
    denomWithdraw: Amounts.parseOrThrow(denom.fees.feeWithdraw),
    denomDeposit: Amounts.parseOrThrow(denom.fees.feeDeposit),
    denomRefresh: Amounts.parseOrThrow(denom.fees.feeRefresh),
    exchangePurse: purseFee,
    exchangeWire: wireFee,
    exchangeBaseUrl: denom.exchangeBaseUrl,
    duration: AbsoluteTime.difference(
      AbsoluteTime.now(),
      AbsoluteTime.fromProtocolTimestamp(denom.stampExpireDeposit),
    ),
    totalAvailable: total,
    value: DenominationRecord.getValue(denom),
    maxAge,
  };
}

export async function convertDepositAmount(
  ws: InternalWalletState,
  req: ConvertAmountRequest,
): Promise<AmountResponse> {
  const amount = Amounts.parseOrThrow(req.amount);
  // const filter = getCoinsFilter(req);

  const denoms = await getAvailableDenoms(
    ws,
    TransactionType.Deposit,
    amount.currency,
    {},
  );
  const result = convertDepositAmountForAvailableCoins(
    denoms,
    amount,
    req.type,
  );

  return {
    effectiveAmount: Amounts.stringify(result.effective),
    rawAmount: Amounts.stringify(result.raw),
  };
}

const LOG_REFRESH = false;
const LOG_DEPOSIT = false;
export function convertDepositAmountForAvailableCoins(
  denoms: AvailableCoins,
  amount: AmountJson,
  mode: TransactionAmountMode,
): AmountAndRefresh {
  const zero = Amounts.zeroOfCurrency(amount.currency);
  if (!denoms.list.length) {
    // no coins in the database
    return { effective: zero, raw: zero };
  }
  const depositDenoms = rankDenominationForDeposit(denoms.list, mode);

  //FIXME: we are not taking into account
  // * exchanges with multiple accounts
  // * wallet with multiple exchanges
  const wireFee = Object.values(denoms.exchanges)[0]?.wireFee ?? zero;
  const adjustedAmount = Amounts.add(amount, wireFee).amount;

  const selected = selectGreedyCoins(depositDenoms, adjustedAmount);

  const gap = Amounts.sub(amount, selected.totalValue).amount;

  const result = getTotalEffectiveAndRawForDeposit(
    selected.coins,
    amount.currency,
  );
  result.raw = Amounts.sub(result.raw, wireFee).amount;

  if (Amounts.isZero(gap)) {
    // exact amount founds
    return result;
  }

  if (LOG_DEPOSIT) {
    const logInfo = selected.coins.map((c) => {
      return `${Amounts.stringifyValue(c.info.id)} x ${c.size}`;
    });
    console.log(
      "deposit used:",
      logInfo.join(", "),
      "gap:",
      Amounts.stringifyValue(gap),
    );
  }

  const refreshDenoms = rankDenominationForRefresh(denoms.list);
  /**
   * FIXME: looking for refresh AFTER selecting greedy is not optimal
   */
  const refreshCoin = searchBestRefreshCoin(
    depositDenoms,
    refreshDenoms,
    gap,
    mode,
  );

  if (refreshCoin) {
    const fee = Amounts.sub(result.effective, result.raw).amount;
    const effective = Amounts.add(
      result.effective,
      refreshCoin.refreshEffective,
    ).amount;
    const raw = Amounts.sub(effective, fee, refreshCoin.totalFee).amount;
    //found with change
    return {
      effective,
      raw,
      refresh: refreshCoin,
    };
  }

  // there is a gap, but no refresh coin was found
  return result;
}

export async function getMaxDepositAmount(
  ws: InternalWalletState,
  req: GetAmountRequest,
): Promise<AmountResponse> {
  // const filter = getCoinsFilter(req);

  const denoms = await getAvailableDenoms(
    ws,
    TransactionType.Deposit,
    req.currency,
    {},
  );

  const result = getMaxDepositAmountForAvailableCoins(denoms, req.currency);
  return {
    effectiveAmount: Amounts.stringify(result.effective),
    rawAmount: Amounts.stringify(result.raw),
  };
}

export function getMaxDepositAmountForAvailableCoins(
  denoms: AvailableCoins,
  currency: string,
) {
  const zero = Amounts.zeroOfCurrency(currency);
  if (!denoms.list.length) {
    // no coins in the database
    return { effective: zero, raw: zero };
  }

  const result = getTotalEffectiveAndRawForDeposit(
    denoms.list.map((info) => {
      return { info, size: info.totalAvailable ?? 0 };
    }),
    currency,
  );

  const wireFee = Object.values(denoms.exchanges)[0]?.wireFee ?? zero;
  result.raw = Amounts.sub(result.raw, wireFee).amount;

  return result;
}

export async function convertPeerPushAmount(
  ws: InternalWalletState,
  req: ConvertAmountRequest,
): Promise<AmountResponse> {
  throw Error("to be implemented after 1.0");
}
export async function getMaxPeerPushAmount(
  ws: InternalWalletState,
  req: GetAmountRequest,
): Promise<AmountResponse> {
  throw Error("to be implemented after 1.0");
}
export async function convertWithdrawalAmount(
  ws: InternalWalletState,
  req: ConvertAmountRequest,
): Promise<AmountResponse> {
  const amount = Amounts.parseOrThrow(req.amount);

  const denoms = await getAvailableDenoms(
    ws,
    TransactionType.Withdrawal,
    amount.currency,
    {},
  );

  const result = convertWithdrawalAmountFromAvailableCoins(
    denoms,
    amount,
    req.type,
  );

  return {
    effectiveAmount: Amounts.stringify(result.effective),
    rawAmount: Amounts.stringify(result.raw),
  };
}

export function convertWithdrawalAmountFromAvailableCoins(
  denoms: AvailableCoins,
  amount: AmountJson,
  mode: TransactionAmountMode,
) {
  const zero = Amounts.zeroOfCurrency(amount.currency);
  if (!denoms.list.length) {
    // no coins in the database
    return { effective: zero, raw: zero };
  }
  const withdrawDenoms = rankDenominationForWithdrawals(denoms.list, mode);

  const selected = selectGreedyCoins(withdrawDenoms, amount);

  return getTotalEffectiveAndRawForWithdrawal(selected.coins, amount.currency);
}

/** *****************************************************
 * HELPERS
 * *****************************************************
 */

/**
 *
 * @param depositDenoms
 * @param refreshDenoms
 * @param amount
 * @param mode
 * @returns
 */
function searchBestRefreshCoin(
  depositDenoms: SelectableElement[],
  refreshDenoms: Record<string, SelectableElement[]>,
  amount: AmountJson,
  mode: TransactionAmountMode,
): RefreshChoice | undefined {
  let choice: RefreshChoice | undefined = undefined;
  let refreshIdx = 0;
  refreshIteration: while (refreshIdx < depositDenoms.length) {
    const d = depositDenoms[refreshIdx];

    const denomContribution =
      mode === TransactionAmountMode.Effective
        ? d.value
        : Amounts.sub(d.value, d.info.denomRefresh, d.info.denomDeposit).amount;

    const changeAfterDeposit = Amounts.sub(denomContribution, amount).amount;
    if (Amounts.isZero(changeAfterDeposit)) {
      //this coin is not big enough to use for refresh
      //since the list is sorted, we can break here
      break refreshIteration;
    }

    const withdrawDenoms = refreshDenoms[d.info.exchangeBaseUrl];
    const change = selectGreedyCoins(withdrawDenoms, changeAfterDeposit);

    const zero = Amounts.zeroOfCurrency(amount.currency);
    const withdrawChangeFee = change.coins.reduce((cur, prev) => {
      return Amounts.add(
        cur,
        Amounts.mult(prev.info.denomWithdraw, prev.size).amount,
      ).amount;
    }, zero);

    const withdrawChangeValue = change.coins.reduce((cur, prev) => {
      return Amounts.add(cur, Amounts.mult(prev.info.value, prev.size).amount)
        .amount;
    }, zero);

    const totalFee = Amounts.add(
      d.info.denomDeposit,
      d.info.denomRefresh,
      withdrawChangeFee,
    ).amount;

    if (!choice || Amounts.cmp(totalFee, choice.totalFee) === -1) {
      //found cheaper change
      choice = {
        gap: amount,
        totalFee: totalFee,
        totalChangeValue: change.totalValue, //change after refresh
        refreshEffective: Amounts.sub(d.info.value, withdrawChangeValue).amount, // what of the denom used is not recovered
        selected: d.info,
        coins: change.coins,
      };
    }
    refreshIdx++;
  }
  if (choice) {
    if (LOG_REFRESH) {
      const logInfo = choice.coins.map((c) => {
        return `${Amounts.stringifyValue(c.info.id)} x ${c.size}`;
      });
      console.log(
        "refresh used:",
        Amounts.stringifyValue(choice.selected.value),
        "change:",
        logInfo.join(", "),
        "fee:",
        Amounts.stringifyValue(choice.totalFee),
        "refreshEffective:",
        Amounts.stringifyValue(choice.refreshEffective),
        "totalChangeValue:",
        Amounts.stringifyValue(choice.totalChangeValue),
      );
    }
  }
  return choice;
}

/**
 * Returns a copy of the list sorted for the best denom to withdraw first
 *
 * @param denoms
 * @returns
 */
function rankDenominationForWithdrawals(
  denoms: CoinInfo[],
  mode: TransactionAmountMode,
): SelectableElement[] {
  const copyList = [...denoms];
  /**
   * Rank coins
   */
  copyList.sort((d1, d2) => {
    // the best coin to use is
    // 1.- the one that contrib more and pay less fee
    // 2.- it takes more time before expires

    //different exchanges may have different wireFee
    //ranking should take the relative contribution in the exchange
    //which is (value - denomFee / fixedFee)
    const rate1 = Amounts.divmod(d1.value, d1.denomWithdraw).quotient;
    const rate2 = Amounts.divmod(d2.value, d2.denomWithdraw).quotient;
    const contribCmp = rate1 === rate2 ? 0 : rate1 < rate2 ? 1 : -1;
    return (
      contribCmp ||
      Duration.cmp(d1.duration, d2.duration) ||
      strcmp(d1.id, d2.id)
    );
  });

  return copyList.map((info) => {
    switch (mode) {
      case TransactionAmountMode.Effective: {
        //if the user instructed "effective" then we need to selected
        //greedy total coin value
        return {
          info,
          value: info.value,
          total: Number.MAX_SAFE_INTEGER,
        };
      }
      case TransactionAmountMode.Raw: {
        //if the user instructed "raw" then we need to selected
        //greedy total coin raw amount (without fee)
        return {
          info,
          value: Amounts.add(info.value, info.denomWithdraw).amount,
          total: Number.MAX_SAFE_INTEGER,
        };
      }
    }
  });
}

/**
 * Returns a copy of the list sorted for the best denom to deposit first
 *
 * @param denoms
 * @returns
 */
function rankDenominationForDeposit(
  denoms: CoinInfo[],
  mode: TransactionAmountMode,
): SelectableElement[] {
  const copyList = [...denoms];
  /**
   * Rank coins
   */
  copyList.sort((d1, d2) => {
    // the best coin to use is
    // 1.- the one that contrib more and pay less fee
    // 2.- it takes more time before expires

    //different exchanges may have different wireFee
    //ranking should take the relative contribution in the exchange
    //which is (value - denomFee / fixedFee)
    const rate1 = Amounts.divmod(d1.value, d1.denomDeposit).quotient;
    const rate2 = Amounts.divmod(d2.value, d2.denomDeposit).quotient;
    const contribCmp = rate1 === rate2 ? 0 : rate1 < rate2 ? 1 : -1;
    return (
      contribCmp ||
      Duration.cmp(d1.duration, d2.duration) ||
      strcmp(d1.id, d2.id)
    );
  });

  return copyList.map((info) => {
    switch (mode) {
      case TransactionAmountMode.Effective: {
        //if the user instructed "effective" then we need to selected
        //greedy total coin value
        return {
          info,
          value: info.value,
          total: info.totalAvailable ?? 0,
        };
      }
      case TransactionAmountMode.Raw: {
        //if the user instructed "raw" then we need to selected
        //greedy total coin raw amount (without fee)
        return {
          info,
          value: Amounts.sub(info.value, info.denomDeposit).amount,
          total: info.totalAvailable ?? 0,
        };
      }
    }
  });
}

/**
 * Returns a copy of the list sorted for the best denom to withdraw first
 *
 * @param denoms
 * @returns
 */
function rankDenominationForRefresh(
  denoms: CoinInfo[],
): Record<string, SelectableElement[]> {
  const groupByExchange: Record<string, CoinInfo[]> = {};
  for (const d of denoms) {
    if (!groupByExchange[d.exchangeBaseUrl]) {
      groupByExchange[d.exchangeBaseUrl] = [];
    }
    groupByExchange[d.exchangeBaseUrl].push(d);
  }

  const result: Record<string, SelectableElement[]> = {};
  for (const d of denoms) {
    result[d.exchangeBaseUrl] = rankDenominationForWithdrawals(
      groupByExchange[d.exchangeBaseUrl],
      TransactionAmountMode.Raw,
    );
  }
  return result;
}

interface SelectableElement {
  total: number;
  value: AmountJson;
  info: CoinInfo;
}

function selectGreedyCoins(
  coins: SelectableElement[],
  limit: AmountJson,
): SelectedCoins {
  const result: SelectedCoins = {
    totalValue: Amounts.zeroOfCurrency(limit.currency),
    coins: [],
  };
  if (!coins.length) return result;

  let denomIdx = 0;
  iterateDenoms: while (denomIdx < coins.length) {
    const denom = coins[denomIdx];
    // let total = denom.total;
    const left = Amounts.sub(limit, result.totalValue).amount;

    if (Amounts.isZero(denom.value)) {
      // 0 contribution denoms should be the last
      break iterateDenoms;
    }

    //use Amounts.divmod instead of iterate
    const div = Amounts.divmod(left, denom.value);
    const size = Math.min(div.quotient, denom.total);
    if (size > 0) {
      const mul = Amounts.mult(denom.value, size).amount;
      const progress = Amounts.add(result.totalValue, mul).amount;

      result.totalValue = progress;
      result.coins.push({ info: denom.info, size });
      denom.total = denom.total - size;
    }

    //go next denom
    denomIdx++;
  }

  return result;
}

type AmountWithFee = { raw: AmountJson; effective: AmountJson };
type AmountAndRefresh = AmountWithFee & { refresh?: RefreshChoice };

export function getTotalEffectiveAndRawForDeposit(
  list: { info: CoinInfo; size: number }[],
  currency: string,
): AmountWithFee {
  const init = {
    raw: Amounts.zeroOfCurrency(currency),
    effective: Amounts.zeroOfCurrency(currency),
  };
  return list.reduce((prev, cur) => {
    const ef = Amounts.mult(cur.info.value, cur.size).amount;
    const rw = Amounts.mult(
      Amounts.sub(cur.info.value, cur.info.denomDeposit).amount,
      cur.size,
    ).amount;

    prev.effective = Amounts.add(prev.effective, ef).amount;
    prev.raw = Amounts.add(prev.raw, rw).amount;
    return prev;
  }, init);
}

function getTotalEffectiveAndRawForWithdrawal(
  list: { info: CoinInfo; size: number }[],
  currency: string,
): AmountWithFee {
  const init = {
    raw: Amounts.zeroOfCurrency(currency),
    effective: Amounts.zeroOfCurrency(currency),
  };
  return list.reduce((prev, cur) => {
    const ef = Amounts.mult(cur.info.value, cur.size).amount;
    const rw = Amounts.mult(
      Amounts.add(cur.info.value, cur.info.denomWithdraw).amount,
      cur.size,
    ).amount;

    prev.effective = Amounts.add(prev.effective, ef).amount;
    prev.raw = Amounts.add(prev.raw, rw).amount;
    return prev;
  }, init);
}