diff options
Diffstat (limited to 'packages/taler-wallet-core/src/util')
-rw-r--r-- | packages/taler-wallet-core/src/util/denominations.test.ts | 712 | ||||
-rw-r--r-- | packages/taler-wallet-core/src/util/denominations.ts | 349 |
2 files changed, 1061 insertions, 0 deletions
diff --git a/packages/taler-wallet-core/src/util/denominations.test.ts b/packages/taler-wallet-core/src/util/denominations.test.ts new file mode 100644 index 000000000..653692437 --- /dev/null +++ b/packages/taler-wallet-core/src/util/denominations.test.ts @@ -0,0 +1,712 @@ +/* + This file is part of GNU Taler + (C) 2022 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/> + */ + +/** + * + * @author Sebastian Javier Marchano (sebasjm) + */ + + import { + AbsoluteTime,FeeDescription, FeeDescriptionPair, + Amounts, DenominationInfo +} from "@gnu-taler/taler-util"; +// import { expect } from "chai"; +import { createDenominationPairTimeline, createDenominationTimeline } from "./denominations.js"; +import test, { ExecutionContext } from "ava"; + +/** + * Create some constants to be used as reference in the tests + */ +const VALUES = Array.from({ length: 10 }).map((undef, t) => Amounts.parseOrThrow(`USD:${t}`)) +const TIMESTAMPS = Array.from({ length: 20 }).map((undef, t_s) => ({ t_s })) +const ABS_TIME = TIMESTAMPS.map(m => AbsoluteTime.fromTimestamp(m)) + +function normalize(list: DenominationInfo[]): DenominationInfo[] { + return list.map((e, idx) => ({ ...e, denomPubHash: `id${idx}` })) +} + +//Avoiding to make an error-prone/time-consuming refactor +//this function calls AVA's deepEqual from a chai interface +function expect(t:ExecutionContext, thing: any):any { + return { + deep: { + equal: (another:any) => t.deepEqual(thing,another), + equals: (another:any) => t.deepEqual(thing,another), + } + } +} + +// describe("Denomination timeline creation", (t) => { +// describe("single value example", (t) => { + + test("should have one row with start and exp", (t) => { + + const timeline = createDenominationTimeline(normalize([ + { + value: VALUES[1], + stampStart: TIMESTAMPS[1], + stampExpireDeposit: TIMESTAMPS[2], + feeDeposit: VALUES[1] + } as Partial<DenominationInfo> as DenominationInfo, + ]), "stampExpireDeposit", "feeDeposit"); + + expect(t,timeline).deep.equal([{ + value: VALUES[1], + from: ABS_TIME[1], + until: ABS_TIME[2], + fee: VALUES[1], + } as FeeDescription]) + }); + + test("should have two rows with the second denom in the middle if second is better", (t) => { + const timeline = createDenominationTimeline(normalize([ + { + value: VALUES[1], + stampStart: TIMESTAMPS[1], + stampExpireDeposit: TIMESTAMPS[3], + feeDeposit: VALUES[1] + } as Partial<DenominationInfo> as DenominationInfo, + { + value: VALUES[1], + stampStart: TIMESTAMPS[2], + stampExpireDeposit: TIMESTAMPS[4], + feeDeposit: VALUES[2] + } as Partial<DenominationInfo> as DenominationInfo, + ]), "stampExpireDeposit", "feeDeposit"); + + expect(t,timeline).deep.equal([{ + value: VALUES[1], + from: ABS_TIME[1], + until: ABS_TIME[3], + fee: VALUES[1], + }, { + value: VALUES[1], + from: ABS_TIME[3], + until: ABS_TIME[4], + fee: VALUES[2], + }] as FeeDescription[]) + + }); + + test("should have two rows with the first denom in the middle if second is worse", (t) => { + const timeline = createDenominationTimeline(normalize([ + { + value: VALUES[1], + stampStart: TIMESTAMPS[1], + stampExpireDeposit: TIMESTAMPS[3], + feeDeposit: VALUES[2] + } as Partial<DenominationInfo> as DenominationInfo, + { + value: VALUES[1], + stampStart: TIMESTAMPS[2], + stampExpireDeposit: TIMESTAMPS[4], + feeDeposit: VALUES[1] + } as Partial<DenominationInfo> as DenominationInfo, + ]), "stampExpireDeposit", "feeDeposit"); + + expect(t,timeline).deep.equal([{ + value: VALUES[1], + from: ABS_TIME[1], + until: ABS_TIME[2], + fee: VALUES[2], + }, { + value: VALUES[1], + from: ABS_TIME[2], + until: ABS_TIME[4], + fee: VALUES[1], + }] as FeeDescription[]) + + }); + + test("should add a gap when there no fee", (t) => { + const timeline = createDenominationTimeline(normalize([ + { + value: VALUES[1], + stampStart: TIMESTAMPS[1], + stampExpireDeposit: TIMESTAMPS[2], + feeDeposit: VALUES[2] + } as Partial<DenominationInfo> as DenominationInfo, + { + value: VALUES[1], + stampStart: TIMESTAMPS[3], + stampExpireDeposit: TIMESTAMPS[4], + feeDeposit: VALUES[1] + } as Partial<DenominationInfo> as DenominationInfo, + ]), "stampExpireDeposit", "feeDeposit"); + + expect(t,timeline).deep.equal([{ + value: VALUES[1], + from: ABS_TIME[1], + until: ABS_TIME[2], + fee: VALUES[2], + }, { + value: VALUES[1], + from: ABS_TIME[2], + until: ABS_TIME[3], + + }, { + value: VALUES[1], + from: ABS_TIME[3], + until: ABS_TIME[4], + fee: VALUES[1], + }] as FeeDescription[]) + + }); + + test("should have three rows when first denom is between second and second is worse", (t) => { + const timeline = createDenominationTimeline(normalize([ + { + value: VALUES[1], + stampStart: TIMESTAMPS[2], + stampExpireDeposit: TIMESTAMPS[3], + feeDeposit: VALUES[1] + } as Partial<DenominationInfo> as DenominationInfo, + { + value: VALUES[1], + stampStart: TIMESTAMPS[1], + stampExpireDeposit: TIMESTAMPS[4], + feeDeposit: VALUES[2] + } as Partial<DenominationInfo> as DenominationInfo, + ]), "stampExpireDeposit", "feeDeposit"); + expect(t,timeline).deep.equal([{ + value: VALUES[1], + from: ABS_TIME[1], + until: ABS_TIME[2], + fee: VALUES[2], + }, { + value: VALUES[1], + from: ABS_TIME[2], + until: ABS_TIME[3], + fee: VALUES[1], + }, { + value: VALUES[1], + from: ABS_TIME[3], + until: ABS_TIME[4], + fee: VALUES[2], + }] as FeeDescription[]) + + }); + + test("should have one row when first denom is between second and second is better", (t) => { + const timeline = createDenominationTimeline(normalize([ + { + value: VALUES[1], + stampStart: TIMESTAMPS[2], + stampExpireDeposit: TIMESTAMPS[3], + feeDeposit: VALUES[2] + } as Partial<DenominationInfo> as DenominationInfo, + { + value: VALUES[1], + stampStart: TIMESTAMPS[1], + stampExpireDeposit: TIMESTAMPS[4], + feeDeposit: VALUES[1] + } as Partial<DenominationInfo> as DenominationInfo, + ]), "stampExpireDeposit", "feeDeposit"); + + expect(t,timeline).deep.equal([{ + value: VALUES[1], + from: ABS_TIME[1], + until: ABS_TIME[4], + fee: VALUES[1], + }] as FeeDescription[]) + + }); + + test("should only add the best1", (t) => { + const timeline = createDenominationTimeline(normalize([ + { + value: VALUES[1], + stampStart: TIMESTAMPS[1], + stampExpireDeposit: TIMESTAMPS[3], + feeDeposit: VALUES[2] + } as Partial<DenominationInfo> as DenominationInfo, + { + value: VALUES[1], + stampStart: TIMESTAMPS[2], + stampExpireDeposit: TIMESTAMPS[4], + feeDeposit: VALUES[1] + } as Partial<DenominationInfo> as DenominationInfo, + { + value: VALUES[1], + stampStart: TIMESTAMPS[2], + stampExpireDeposit: TIMESTAMPS[4], + feeDeposit: VALUES[2] + } as Partial<DenominationInfo> as DenominationInfo, + ]), "stampExpireDeposit", "feeDeposit"); + + expect(t,timeline).deep.equal([{ + value: VALUES[1], + from: ABS_TIME[1], + until: ABS_TIME[2], + fee: VALUES[2], + }, { + value: VALUES[1], + from: ABS_TIME[2], + until: ABS_TIME[4], + fee: VALUES[1], + }] as FeeDescription[]) + + }); + + test("should only add the best2", (t) => { + const timeline = createDenominationTimeline(normalize([ + { + value: VALUES[1], + stampStart: TIMESTAMPS[1], + stampExpireDeposit: TIMESTAMPS[3], + feeDeposit: VALUES[2] + } as Partial<DenominationInfo> as DenominationInfo, + { + value: VALUES[1], + stampStart: TIMESTAMPS[2], + stampExpireDeposit: TIMESTAMPS[5], + feeDeposit: VALUES[1] + } as Partial<DenominationInfo> as DenominationInfo, + { + value: VALUES[1], + stampStart: TIMESTAMPS[2], + stampExpireDeposit: TIMESTAMPS[4], + feeDeposit: VALUES[2] + } as Partial<DenominationInfo> as DenominationInfo, + { + value: VALUES[1], + stampStart: TIMESTAMPS[5], + stampExpireDeposit: TIMESTAMPS[6], + feeDeposit: VALUES[3] + } as Partial<DenominationInfo> as DenominationInfo, + ]), "stampExpireDeposit", "feeDeposit"); + + expect(t,timeline).deep.equal([{ + value: VALUES[1], + from: ABS_TIME[1], + until: ABS_TIME[2], + fee: VALUES[2], + }, { + value: VALUES[1], + from: ABS_TIME[2], + until: ABS_TIME[5], + fee: VALUES[1], + }, { + value: VALUES[1], + from: ABS_TIME[5], + until: ABS_TIME[6], + fee: VALUES[3], + }] as FeeDescription[]) + + }); + + test("should only add the best3", (t) => { + const timeline = createDenominationTimeline(normalize([ + { + value: VALUES[1], + stampStart: TIMESTAMPS[2], + stampExpireDeposit: TIMESTAMPS[5], + feeDeposit: VALUES[3] + } as Partial<DenominationInfo> as DenominationInfo, + { + value: VALUES[1], + stampStart: TIMESTAMPS[2], + stampExpireDeposit: TIMESTAMPS[5], + feeDeposit: VALUES[1] + } as Partial<DenominationInfo> as DenominationInfo, + { + value: VALUES[1], + stampStart: TIMESTAMPS[2], + stampExpireDeposit: TIMESTAMPS[5], + feeDeposit: VALUES[2] + } as Partial<DenominationInfo> as DenominationInfo, + ]), "stampExpireDeposit", "feeDeposit"); + + expect(t,timeline).deep.equal([{ + value: VALUES[1], + from: ABS_TIME[2], + until: ABS_TIME[5], + fee: VALUES[1], + }] as FeeDescription[]) + + }) + // }) + + // describe("multiple value example", (t) => { + + //TODO: test the same start but different value + + test("should not merge when there is different value", (t) => { + const timeline = createDenominationTimeline(normalize([ + { + value: VALUES[1], + stampStart: TIMESTAMPS[1], + stampExpireDeposit: TIMESTAMPS[3], + feeDeposit: VALUES[1] + } as Partial<DenominationInfo> as DenominationInfo, + { + value: VALUES[2], + stampStart: TIMESTAMPS[2], + stampExpireDeposit: TIMESTAMPS[4], + feeDeposit: VALUES[2] + } as Partial<DenominationInfo> as DenominationInfo, + ]), "stampExpireDeposit", "feeDeposit"); + + expect(t,timeline).deep.equal([{ + value: VALUES[1], + from: ABS_TIME[1], + until: ABS_TIME[3], + fee: VALUES[1], + }, { + value: VALUES[2], + from: ABS_TIME[2], + until: ABS_TIME[4], + fee: VALUES[2], + }] as FeeDescription[]) + + }); + + test("should not merge when there is different value (with duplicates)", (t) => { + const timeline = createDenominationTimeline(normalize([ + { + value: VALUES[1], + stampStart: TIMESTAMPS[1], + stampExpireDeposit: TIMESTAMPS[3], + feeDeposit: VALUES[1] + } as Partial<DenominationInfo> as DenominationInfo, + { + value: VALUES[2], + stampStart: TIMESTAMPS[2], + stampExpireDeposit: TIMESTAMPS[4], + feeDeposit: VALUES[2] + } as Partial<DenominationInfo> as DenominationInfo, + { + value: VALUES[1], + stampStart: TIMESTAMPS[1], + stampExpireDeposit: TIMESTAMPS[3], + feeDeposit: VALUES[1] + } as Partial<DenominationInfo> as DenominationInfo, + { + value: VALUES[2], + stampStart: TIMESTAMPS[2], + stampExpireDeposit: TIMESTAMPS[4], + feeDeposit: VALUES[2] + } as Partial<DenominationInfo> as DenominationInfo, + ]), "stampExpireDeposit", "feeDeposit"); + + expect(t,timeline).deep.equal([{ + value: VALUES[1], + from: ABS_TIME[1], + until: ABS_TIME[3], + fee: VALUES[1], + }, { + value: VALUES[2], + from: ABS_TIME[2], + until: ABS_TIME[4], + fee: VALUES[2], + }] as FeeDescription[]) + + }); + + // it.skip("real world example: bitcoin exchange", (t) => { + // const timeline = createDenominationTimeline( + // bitcoinExchanges[0].denominations.filter(d => Amounts.cmp(d.value, Amounts.parseOrThrow('BITCOINBTC:0.01048576'))), + // "stampExpireDeposit", "feeDeposit"); + + // expect(t,timeline).deep.equal([{ + // fee: Amounts.parseOrThrow('BITCOINBTC:0.00000001'), + // from: { t_ms: 1652978648000 }, + // until: { t_ms: 1699633748000 }, + // value: Amounts.parseOrThrow('BITCOINBTC:0.01048576'), + // }, { + // fee: Amounts.parseOrThrow('BITCOINBTC:0.00000003'), + // from: { t_ms: 1699633748000 }, + // until: { t_ms: 1707409448000 }, + // value: Amounts.parseOrThrow('BITCOINBTC:0.01048576'), + // }] as FeeDescription[]) + // }) + +// }) + +// }) + +// describe("Denomination timeline pair creation", (t) => { + +// describe("single value example", (t) => { + + test("should return empty", (t) => { + + const left = [] as FeeDescription[]; + const right = [] as FeeDescription[]; + + const pairs = createDenominationPairTimeline(left, right) + + expect(t,pairs).deep.equals([]) + }); + + test("should return first element", (t) => { + + const left = [{ + value: VALUES[1], + from: ABS_TIME[1], + until: ABS_TIME[3], + fee: VALUES[1], + }] as FeeDescription[]; + + const right = [] as FeeDescription[]; + + { + const pairs = createDenominationPairTimeline(left, right) + expect(t,pairs).deep.equals([{ + from: ABS_TIME[1], + until: ABS_TIME[3], + value: VALUES[1], + left: VALUES[1], + right: undefined, + }] as FeeDescriptionPair[]) + } + { + const pairs = createDenominationPairTimeline(right, left) + expect(t,pairs).deep.equals([{ + from: ABS_TIME[1], + until: ABS_TIME[3], + value: VALUES[1], + right: VALUES[1], + left: undefined, + }] as FeeDescriptionPair[]) + } + + }); + + test("should add both to the same row", (t) => { + + const left = [{ + value: VALUES[1], + from: ABS_TIME[1], + until: ABS_TIME[3], + fee: VALUES[1], + }] as FeeDescription[]; + + const right = [{ + value: VALUES[1], + from: ABS_TIME[1], + until: ABS_TIME[3], + fee: VALUES[2], + }] as FeeDescription[]; + + { + const pairs = createDenominationPairTimeline(left, right) + expect(t,pairs).deep.equals([{ + from: ABS_TIME[1], + until: ABS_TIME[3], + value: VALUES[1], + left: VALUES[1], + right: VALUES[2], + }] as FeeDescriptionPair[]) + } + { + const pairs = createDenominationPairTimeline(right, left) + expect(t,pairs).deep.equals([{ + from: ABS_TIME[1], + until: ABS_TIME[3], + value: VALUES[1], + left: VALUES[2], + right: VALUES[1], + }] as FeeDescriptionPair[]) + } + }); + + test("should repeat the first and change the second", (t) => { + + const left = [{ + value: VALUES[1], + from: ABS_TIME[1], + until: ABS_TIME[5], + fee: VALUES[1], + }] as FeeDescription[]; + + const right = [{ + value: VALUES[1], + from: ABS_TIME[1], + until: ABS_TIME[2], + fee: VALUES[2], + }, { + value: VALUES[1], + from: ABS_TIME[2], + until: ABS_TIME[3], + }, { + value: VALUES[1], + from: ABS_TIME[3], + until: ABS_TIME[4], + fee: VALUES[3], + }] as FeeDescription[]; + + { + const pairs = createDenominationPairTimeline(left, right) + expect(t,pairs).deep.equals([{ + from: ABS_TIME[1], + until: ABS_TIME[2], + value: VALUES[1], + left: VALUES[1], + right: VALUES[2], + }, { + from: ABS_TIME[2], + until: ABS_TIME[3], + value: VALUES[1], + left: VALUES[1], + right: undefined, + }, { + from: ABS_TIME[3], + until: ABS_TIME[4], + value: VALUES[1], + left: VALUES[1], + right: VALUES[3], + }, { + from: ABS_TIME[4], + until: ABS_TIME[5], + value: VALUES[1], + left: VALUES[1], + right: undefined, + }] as FeeDescriptionPair[]) + } + + + }); + + // }) + + // describe("multiple value example", (t) => { + + test("should separate denominations of different value", (t) => { + + const left = [{ + value: VALUES[1], + from: ABS_TIME[1], + until: ABS_TIME[3], + fee: VALUES[1], + }] as FeeDescription[]; + + const right = [{ + value: VALUES[2], + from: ABS_TIME[1], + until: ABS_TIME[3], + fee: VALUES[2], + }] as FeeDescription[]; + + { + const pairs = createDenominationPairTimeline(left, right) + expect(t,pairs).deep.equals([{ + from: ABS_TIME[1], + until: ABS_TIME[3], + value: VALUES[1], + left: VALUES[1], + right: undefined, + }, { + from: ABS_TIME[1], + until: ABS_TIME[3], + value: VALUES[2], + left: undefined, + right: VALUES[2], + }] as FeeDescriptionPair[]) + } + { + const pairs = createDenominationPairTimeline(right, left) + expect(t,pairs).deep.equals([{ + from: ABS_TIME[1], + until: ABS_TIME[3], + value: VALUES[1], + left: undefined, + right: VALUES[1], + }, { + from: ABS_TIME[1], + until: ABS_TIME[3], + value: VALUES[2], + left: VALUES[2], + right: undefined, + }] as FeeDescriptionPair[]) + } + }); + + test("should separate denominations of different value2", (t) => { + + const left = [{ + value: VALUES[1], + from: ABS_TIME[1], + until: ABS_TIME[2], + fee: VALUES[1], + }, { + value: VALUES[1], + from: ABS_TIME[2], + until: ABS_TIME[4], + fee: VALUES[2], + }] as FeeDescription[]; + + const right = [{ + value: VALUES[2], + from: ABS_TIME[1], + until: ABS_TIME[3], + fee: VALUES[2], + }] as FeeDescription[]; + + { + const pairs = createDenominationPairTimeline(left, right) + expect(t,pairs).deep.equals([{ + from: ABS_TIME[1], + until: ABS_TIME[2], + value: VALUES[1], + left: VALUES[1], + right: undefined, + }, { + from: ABS_TIME[2], + until: ABS_TIME[4], + value: VALUES[1], + left: VALUES[2], + right: undefined, + }, { + from: ABS_TIME[1], + until: ABS_TIME[3], + value: VALUES[2], + left: undefined, + right: VALUES[2], + }] as FeeDescriptionPair[]) + } + // { + // const pairs = createDenominationPairTimeline(right, left) + // expect(t,pairs).deep.equals([{ + // from: moments[1], + // until: moments[3], + // value: values[1], + // left: undefined, + // right: values[1], + // }, { + // from: moments[1], + // until: moments[3], + // value: values[2], + // left: values[2], + // right: undefined, + // }] as FeeDescriptionPair[]) + // } + }); + // it.skip("should render real world", (t) => { + // const left = createDenominationTimeline( + // bitcoinExchanges[0].denominations.filter(d => Amounts.cmp(d.value, Amounts.parseOrThrow('BITCOINBTC:0.01048576'))), + // "stampExpireDeposit", "feeDeposit"); + // const right = createDenominationTimeline( + // bitcoinExchanges[1].denominations.filter(d => Amounts.cmp(d.value, Amounts.parseOrThrow('BITCOINBTC:0.01048576'))), + // "stampExpireDeposit", "feeDeposit"); + + + // const pairs = createDenominationPairTimeline(left, right) + // }) + +// }) +// }) + diff --git a/packages/taler-wallet-core/src/util/denominations.ts b/packages/taler-wallet-core/src/util/denominations.ts new file mode 100644 index 000000000..cea940f48 --- /dev/null +++ b/packages/taler-wallet-core/src/util/denominations.ts @@ -0,0 +1,349 @@ +/* + 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/> + */ + +import { AbsoluteTime, AmountJson, Amounts, DenominationInfo, FeeDescription, FeeDescriptionPair, TalerProtocolTimestamp, TimePoint } from "@gnu-taler/taler-util"; + +/** + * Given a list of denominations with the same value and same period of time: + * return the one that will be used. + * The best denomination is the one that will minimize the fee cost. + * + * @param list denominations of same value + * @returns + */ +function selectBestForOverlappingDenominations( + list: DenominationInfo[], +): DenominationInfo | undefined { + let minDeposit: DenominationInfo | undefined = undefined; + //TODO: improve denomination selection, this is a trivial implementation + list.forEach((e) => { + if (minDeposit === undefined) { + minDeposit = e; + return; + } + if (Amounts.cmp(minDeposit.feeDeposit, e.feeDeposit) > -1) { + minDeposit = e; + } + }); + return minDeposit; +} + +type PropsWithReturnType<T extends object, F> = Exclude< + { + [K in keyof T]: T[K] extends F ? K : never; + }[keyof T], + undefined +>; + +/** + * Takes two list and create one with one timeline. + * For any element in the position "p" on the left or right "list", then + * list[p].until should be equal to list[p+1].from + * + * @see {createDenominationTimeline} + * + * @param left list denominations @type {FeeDescription} + * @param right list denominations @type {FeeDescription} + * @returns list of pairs for the same time + */ +export function createDenominationPairTimeline(left: FeeDescription[], right: FeeDescription[]): FeeDescriptionPair[] { + //both list empty, discarded + if (left.length === 0 && right.length === 0) return []; + + const pairList: FeeDescriptionPair[] = []; + + let li = 0; + let ri = 0; + + while (li < left.length && ri < right.length) { + const currentValue = Amounts.cmp(left[li].value, right[ri].value) < 0 ? left[li].value : right[ri].value; + + let ll = 0 //left length (until next value) + while (li + ll < left.length && Amounts.cmp(left[li + ll].value, currentValue) === 0) { + ll++ + } + let rl = 0 //right length (until next value) + while (ri + rl < right.length && Amounts.cmp(right[ri + rl].value, currentValue) === 0) { + rl++ + } + const leftIsEmpty = ll === 0 + const rightIsEmpty = rl === 0 + //check which start after, add gap so both list starts at the same time + // one list may be empty + const leftStarts: AbsoluteTime = + leftIsEmpty ? { t_ms: "never" } : left[li].from; + const rightStarts: AbsoluteTime = + rightIsEmpty ? { t_ms: "never" } : right[ri].from; + + //first time cut is the smallest time + let timeCut: AbsoluteTime = leftStarts; + + if (AbsoluteTime.cmp(leftStarts, rightStarts) < 0) { + const ends = + rightIsEmpty ? left[li + ll - 1].until : right[0].from; + + right.splice(ri, 0, { + from: leftStarts, + until: ends, + value: left[li].value, + }); + rl++; + + timeCut = leftStarts + } + if (AbsoluteTime.cmp(leftStarts, rightStarts) > 0) { + const ends = + leftIsEmpty ? right[ri + rl - 1].until : left[0].from; + + left.splice(li, 0, { + from: rightStarts, + until: ends, + value: right[ri].value, + }); + ll++; + + timeCut = rightStarts + } + + //check which ends sooner, add gap so both list ends at the same time + // here both list are non empty + const leftEnds: AbsoluteTime = left[li + ll - 1].until; + const rightEnds: AbsoluteTime = right[ri + rl - 1].until; + + if (AbsoluteTime.cmp(leftEnds, rightEnds) > 0) { + right.splice(ri + rl, 0, { + from: rightEnds, + until: leftEnds, + value: left[0].value, + }); + rl++; + + } + if (AbsoluteTime.cmp(leftEnds, rightEnds) < 0) { + left.splice(li + ll, 0, { + from: leftEnds, + until: rightEnds, + value: right[0].value, + }); + ll++; + } + + //now both lists are non empty and (starts,ends) at the same time + while (li < left.length && ri < right.length && Amounts.cmp(left[li].value, right[ri].value) === 0) { + + if (AbsoluteTime.cmp(left[li].from, timeCut) !== 0 && AbsoluteTime.cmp(right[ri].from, timeCut) !== 0) { + // timeCut comes from the latest "until" (expiration from the previous) + // and this value comes from the latest left or right + // it should be the same as the "from" from one of the latest left or right + // otherwise it means that there is missing a gap object in the middle + // the list is not complete and the behavior is undefined + throw Error('one of the list is not completed: list[i].until !== list[i+1].from') + } + + pairList.push({ + left: left[li].fee, + right: right[ri].fee, + from: timeCut, + until: AbsoluteTime.never(), + value: currentValue, + }); + + if (left[li].until.t_ms === right[ri].until.t_ms) { + timeCut = left[li].until; + ri++; + li++; + } else if (left[li].until.t_ms < right[ri].until.t_ms) { + timeCut = left[li].until; + li++; + } else if (left[li].until.t_ms > right[ri].until.t_ms) { + timeCut = right[ri].until; + ri++; + } + pairList[pairList.length - 1].until = timeCut + + if (li < left.length && Amounts.cmp(left[li].value, pairList[pairList.length - 1].value) !== 0) { + //value changed, should break + //this if will catch when both (left and right) change at the same time + //if just one side changed it will catch in the while condition + break; + } + + } + + } + //one of the list left or right can still have elements + if (li < left.length) { + let timeCut = pairList.length > 0 && Amounts.cmp(pairList[pairList.length - 1].value, left[li].value) === 0 ? pairList[pairList.length - 1].until : left[li].from; + while (li < left.length) { + pairList.push({ + left: left[li].fee, + right: undefined, + from: timeCut, + until: left[li].until, + value: left[li].value, + }) + timeCut = left[li].until + li++; + } + } + if (ri < right.length) { + let timeCut = pairList.length > 0 && Amounts.cmp(pairList[pairList.length - 1].value, right[ri].value) === 0 ? pairList[pairList.length - 1].until : right[ri].from; + while (ri < right.length) { + pairList.push({ + right: right[ri].fee, + left: undefined, + from: timeCut, + until: right[ri].until, + value: right[ri].value, + }) + timeCut = right[ri].until + ri++; + } + } + return pairList +} + +/** + * Create a usage timeline with the denominations given. + * + * If there are multiple denominations that can be used, the list will + * contain the one that minimize the fee cost. @see selectBestForOverlappingDenominations + * + * @param list list of denominations + * @param periodProp property of element of the list that will be used as end of the usage period + * @param feeProp property of the element of the list that will be used as fee reference + * @returns list of @type {FeeDescription} sorted by usage period + */ +export function createDenominationTimeline( + list: DenominationInfo[], + periodProp: PropsWithReturnType<DenominationInfo, TalerProtocolTimestamp>, + feeProp: PropsWithReturnType<DenominationInfo, AmountJson>, +): FeeDescription[] { + const points = list + .reduce((ps, denom) => { + //exclude denoms with bad configuration + if (denom.stampStart.t_s >= denom[periodProp].t_s) { + throw Error(`denom ${denom.denomPubHash} has start after the end`); + // return ps; + } + ps.push({ + type: "start", + moment: AbsoluteTime.fromTimestamp(denom.stampStart), + denom, + }); + ps.push({ + type: "end", + moment: AbsoluteTime.fromTimestamp(denom[periodProp]), + denom, + }); + return ps; + }, [] as TimePoint[]) + .sort((a, b) => { + const v = Amounts.cmp(a.denom.value, b.denom.value); + if (v != 0) return v; + const t = AbsoluteTime.cmp(a.moment, b.moment); + if (t != 0) return t; + if (a.type === b.type) return 0; + return a.type === "start" ? 1 : -1; + }); + + const activeAtTheSameTime: DenominationInfo[] = []; + return points.reduce((result, cursor, idx) => { + const hash = cursor.denom.denomPubHash; + if (!hash) + throw Error( + `denomination without hash ${JSON.stringify( + cursor.denom, + undefined, + 2, + )}`, + ); + + let prev = result.length > 0 ? result[result.length - 1] : undefined; + const prevHasSameValue = + prev && Amounts.cmp(prev.value, cursor.denom.value) === 0; + if (prev) { + if (prevHasSameValue) { + prev.until = cursor.moment; + + if (prev.from.t_ms === prev.until.t_ms) { + result.pop(); + prev = result[result.length - 1]; + } + } else { + // the last end adds a gap that we have to remove + result.pop(); + } + } + + //update the activeAtTheSameTime list + if (cursor.type === "end") { + const loc = activeAtTheSameTime.findIndex((v) => v.denomPubHash === hash); + if (loc === -1) { + throw Error(`denomination ${hash} has an end but no start`); + } + activeAtTheSameTime.splice(loc, 1); + } else if (cursor.type === "start") { + activeAtTheSameTime.push(cursor.denom); + } else { + const exhaustiveCheck: never = cursor.type; + throw new Error(`not TimePoint defined for type: ${exhaustiveCheck}`); + } + + if (idx == points.length - 1) { + //this is the last element in the list, prevent adding + //a gap in the end + if (cursor.type !== "end") { + throw Error( + `denomination ${hash} starts after ending or doesn't have an ending`, + ); + } + if (activeAtTheSameTime.length > 0) { + throw Error( + `there are ${activeAtTheSameTime.length} denominations without ending`, + ); + } + return result; + } + + const current = selectBestForOverlappingDenominations(activeAtTheSameTime); + + if (current) { + if ( + prev === undefined || //is the first + !prev.fee || //is a gap + Amounts.cmp(prev.fee, current[feeProp]) !== 0 // prev has the same fee + ) { + result.push({ + value: cursor.denom.value, + from: cursor.moment, + until: AbsoluteTime.never(), //not yet known + fee: current[feeProp], + }); + } else { + prev.until = cursor.moment; + } + } else { + result.push({ + value: cursor.denom.value, + from: cursor.moment, + until: AbsoluteTime.never(), //not yet known + }); + } + + return result; + }, [] as FeeDescription[]); +} |