# trip-split: Trip Expense Splitting ## Intent This package lets an app split a trip's shared expenses among its travelers and show the fewest transfers that settle everyone up in one trip currency. It specifies a Swift library whose caller is the app code using it. It owns accepted currencies, trips, per-trip exchange rates, expenses, splitting, and settlement plans; it does not source exchange rates, persist trips, or present anything to travelers. Its currency rules follow [DR-001](../decisions/001-trip-currency-conversion.md). ## External Behavior ### trip-split-1 The library shall accept as currency codes exactly the codes in its currency table, each with that table's minor unit: - The first release's table holds every code that ISO 4217 [[1]] List One gives a numeric minor unit on the release date; codes without one, such as XAU, XDR, and XXX, are excluded. - A later release may add codes but never removes a code or changes a code's minor unit. ### trip-split-2 When the caller creates a trip with a trip currency code, the library shall return a trip that settles in that currency and holds no exchange rates and no expenses, or reject a code outside its currency table [[trip-split-1](#trip-split-1)] with `unsupportedCurrency`. ### trip-split-3 When the caller sets a trip's exchange rate for a currency, the trip shall apply the first matching case below, where the rate is the number of trip-currency units that one unit of that currency is worth: | Case | Outcome | | --- | --- | | The currency is the trip currency | reject with `tripCurrency` | | The currency is outside the currency table [[trip-split-1](#trip-split-1)] | reject with `unsupportedCurrency` | | The rate is zero or negative | reject with `invalidRate` | | Otherwise | record the rate, replacing any earlier rate for that currency | - A rejection leaves the trip unchanged. ### trip-split-4 When the caller adds an expense to a trip, the trip shall apply the first matching case below: - An expense has a payer, a positive amount in one currency, and an ordered list of participants, each with an optional positive integer share weight that defaults to 1. - A traveler is identified by a caller-supplied, non-empty string compared exactly; the payer need not be a participant. - An expense needs no exchange rate when it is added. | Case | Outcome | | --- | --- | | The payer or a participant is an empty string | reject with `invalidTraveler` | | The participant list is empty | reject with `noParticipants` | | A traveler appears twice in the participant list | reject with `duplicateParticipant` | | A share weight is zero or negative | reject with `invalidShare` | | The currency is outside the currency table [[trip-split-1](#trip-split-1)] | reject with `unsupportedCurrency` | | The amount is zero or negative, or its value is not a whole number of the currency's minor units [[trip-split-1](#trip-split-1)] | reject with `invalidAmount` | | Otherwise | record the expense after the trip's earlier expenses | - For example, 1000.00 JPY is recorded as 1000 JPY, and 10.5 JPY is rejected. - A rejection leaves the trip unchanged. ### trip-split-5 When the trip computes a settlement plan, it shall value each expense in the trip currency as its amount times its currency's current exchange rate [[trip-split-3](#trip-split-3)], or times 1 for the trip currency, computed exactly and rounded to the trip currency's minor unit [[trip-split-1](#trip-split-1)] with ties away from zero: | Trip currency | Rate | Expense | Value | | --- | --- | --- | --- | | EUR | JPY 0.0061 | 12345 JPY | 75.30 EUR | | EUR | USD 0.925 | 1.00 USD | 0.93 EUR | | JPY | EUR 163.5 | 1.00 EUR | 164 JPY | | EUR | KRW 0.00064 | 1 KRW | 0.00 EUR | - Setting a currency's rate again revalues every expense in that currency in later plans. - A value of zero moves no balance. ### trip-split-6 The trip shall split each expense's trip-currency value [[trip-split-5](#trip-split-5)] among its participants in proportion to their share weights, as whole trip-currency minor units that sum exactly to that value: 1. Each participant first receives the value times their weight divided by the total weight, in minor units, rounded down. 2. The remaining minor units go one each to participants in descending order of the fraction dropped in step 1, ties going to the participant earlier in the expense's list. - Example: 75.30 EUR with weights 2, 1, 1 splits into 37.65, 18.83, and 18.82 EUR. ### trip-split-7 When the caller requests a trip's settlement plan, the trip shall apply the first matching case below: | Case | Outcome | | --- | --- | | A recorded expense's currency is not the trip currency and has no exchange rate | reject with `missingRate`, naming every such currency in alphabetical order of code | | More than 20 travelers have a nonzero balance [[trip-split-8](#trip-split-8)] | reject with `groupTooLarge` | | Otherwise | return the settlement plan [[trip-split-8](#trip-split-8)] computed from all recorded expenses and current rates | - A later release may raise the limit of 20 but never lowers it. ### trip-split-8 The trip shall construct a settlement plan in the steps below, which yield the fewest transfers that bring every traveler's balance to exactly zero: 1. Order travelers by first appearance in the recorded expenses, taken in recording order, with each expense's payer before its participants in list order. 2. Compute each traveler's balance as the total value [[trip-split-5](#trip-split-5)] of the expenses they paid minus the total of their split portions [[trip-split-6](#trip-split-6)], and keep the travelers whose balance is not zero. 3. Partition the kept travelers into the largest possible number of groups whose balances each sum to zero. 4. Among such partitions, fix groups one at a time: the group holding the earliest traveler not yet grouped is, of the groups that still allow a largest partition, the one whose ascending list of traveler positions is lexicographically smallest, a proper prefix counting as smaller. 5. Within each group, repeatedly have the earliest traveler who still owes pay the earliest traveler still owed the smaller of their two outstanding amounts, until every balance in the group is zero. 6. List the transfers by the sender's position, then by the recipient's position. - Each transfer runs from a traveler who owes to a traveler who is owed, for a positive amount in whole trip-currency minor units. - A group of k travelers takes exactly k − 1 transfers, so no plan has fewer transfers. - With no kept travelers, the plan is empty. ### trip-split-9 Where a trip has at most 20 travelers with a nonzero balance, when the caller requests its settlement plan on an iPhone SE (3rd generation) running the oldest iOS version the library supports, the library shall return the plan within 0.5 seconds, using at most 64 MB of additional memory. ### trip-split-10 When the caller changes a trip, by adding an expense or setting an exchange rate, after receiving one of its settlement plans, the trip shall leave that plan unchanged and base every later plan on the changed trip: - A transfer already paid is recorded as an expense paid by its sender, of its amount in the trip currency, with its recipient as the only participant, so later plans no longer ask for it and no rate change revalues it. ### trip-split-11 The library shall compute every result from caller-supplied data alone, making no network request. ## Verification ### trip-split-12 When an integration test drives trip creation and exchange rates through the library's public API in the order below, the test shall assert each expected outcome: | Step | Action | Expected outcome | | --- | --- | --- | | 1 | Create a trip in `EUR` | a trip whose settlement plan is empty [[trip-split-2](#trip-split-2)] [[trip-split-8](#trip-split-8)] | | 2 | Create a trip in `QQQ` | `unsupportedCurrency` [[trip-split-2](#trip-split-2)] | | 3 | Create a trip in `XAU` | `unsupportedCurrency`, as XAU has no minor unit [[trip-split-1](#trip-split-1)] [[trip-split-2](#trip-split-2)] | | 4 | On the EUR trip, set `JPY` to 0.61 | recorded [[trip-split-3](#trip-split-3)] | | 5 | Add 1000.00 JPY paid by Pat for Ana | recorded as 1000 JPY [[trip-split-4](#trip-split-4)] | | 6 | Request the settlement plan | exactly Ana → Pat 610.00 EUR [[trip-split-5](#trip-split-5)] [[trip-split-8](#trip-split-8)] | | 7 | Set `JPY` to 0.0061 | recorded, replacing 0.61 [[trip-split-3](#trip-split-3)] | | 8 | Request the settlement plan | exactly Ana → Pat 6.10 EUR, with the step 6 plan still Ana → Pat 610.00 EUR [[trip-split-5](#trip-split-5)] [[trip-split-10](#trip-split-10)] | | 9 | Set `EUR` to 1 | `tripCurrency` [[trip-split-3](#trip-split-3)] | | 10 | Set `XDR` to 1 | `unsupportedCurrency` [[trip-split-1](#trip-split-1)] [[trip-split-3](#trip-split-3)] | | 11 | Set `USD` to 0, then to -0.5 | `invalidRate` each time [[trip-split-3](#trip-split-3)] | | 12 | Request the settlement plan | still exactly Ana → Pat 6.10 EUR, as rejected rates left the trip unchanged [[trip-split-3](#trip-split-3)] | ### trip-split-13 Where a trip in `EUR` has one recorded expense of 30.00 EUR paid by Ana for Ana and Ben, when an integration test adds each expense below — 10.00 EUR paid by Ana for Ben unless the row says otherwise — the test shall assert the stated rejection and that the settlement plan is still exactly Ben → Ana 15.00 EUR [[trip-split-4](#trip-split-4)]: | Expense | Rejection | | --- | --- | | Payer `""` | `invalidTraveler` [[trip-split-4](#trip-split-4)] | | Participants Ben and `""` | `invalidTraveler` [[trip-split-4](#trip-split-4)] | | No participants | `noParticipants` [[trip-split-4](#trip-split-4)] | | Participants Ben and Ben | `duplicateParticipant` [[trip-split-4](#trip-split-4)] | | Ben with weight 0 | `invalidShare` [[trip-split-4](#trip-split-4)] | | Ben with weight -1 | `invalidShare` [[trip-split-4](#trip-split-4)] | | Currency `QQQ` | `unsupportedCurrency` [[trip-split-4](#trip-split-4)] | | Currency `XXX` | `unsupportedCurrency` [[trip-split-1](#trip-split-1)] [[trip-split-4](#trip-split-4)] | | 0.00 EUR | `invalidAmount` [[trip-split-4](#trip-split-4)] | | -5.00 EUR | `invalidAmount` [[trip-split-4](#trip-split-4)] | | 1.234 EUR | `invalidAmount` [[trip-split-4](#trip-split-4)] | | 10.5 JPY | `invalidAmount` [[trip-split-4](#trip-split-4)] | | Payer `""` and 0.00 EUR | `invalidTraveler`, the first matching case [[trip-split-4](#trip-split-4)] | ### trip-split-14 When an integration test records, on a fresh trip per row, one expense paid by Pat, who is not a participant, and requests the settlement plan, the test shall assert the plan is exactly the stated transfers, each equal to a participant's split portion: | Trip currency | Rate | Expense | Expected plan | | --- | --- | --- | --- | | EUR | JPY 0.0061 | 12345 JPY; Ana weight 2, Ben 1, Cal 1 | Ana → Pat 37.65, Ben → Pat 18.83, Cal → Pat 18.82 EUR [[trip-split-5](#trip-split-5)] [[trip-split-6](#trip-split-6)] [[trip-split-8](#trip-split-8)] | | EUR | USD 0.925 | 1.00 USD; Ana, Ben, Cal | Ana, Ben, and Cal → Pat 0.31 EUR each, so the 0.925 tie rounded up to 0.93 [[trip-split-5](#trip-split-5)] [[trip-split-6](#trip-split-6)] | | JPY | EUR 163.5 | 1.00 EUR; Ana, Ben | Ana and Ben → Pat 82 JPY each, so the 163.5 tie rounded up to 164 [[trip-split-5](#trip-split-5)] [[trip-split-6](#trip-split-6)] | | EUR | KRW 0.00064 | 1 KRW; Ana | empty, as the value rounds to 0.00 EUR [[trip-split-5](#trip-split-5)] [[trip-split-8](#trip-split-8)] | | EUR | none | 10.00 EUR; Ana, Ben, Cal | Ana → Pat 3.34, Ben → Pat 3.33, Cal → Pat 3.33 EUR [[trip-split-6](#trip-split-6)] | | EUR | none | 0.10 EUR; Ana weight 1, Ben 2 | Ana → Pat 0.03, Ben → Pat 0.07 EUR [[trip-split-6](#trip-split-6)] | ### trip-split-15 Where a trip in `EUR` has no exchange rates, when an integration test runs the steps below in order, the test shall assert each expected outcome: | Step | Action | Expected outcome | | --- | --- | --- | | 1 | Add Ana paying 90.00 EUR for Ana, Ben, and Cal | recorded [[trip-split-4](#trip-split-4)] | | 2 | Add Ben paying 12345 JPY for Ana weight 2, Ben 1, and Cal 1 | recorded without a JPY rate [[trip-split-4](#trip-split-4)] | | 3 | Add Cal paying 10.00 USD for Ana, Ben, and Cal | recorded without a USD rate [[trip-split-4](#trip-split-4)] | | 4 | Request the settlement plan | `missingRate` naming JPY, then USD [[trip-split-7](#trip-split-7)] | | 5 | Set `JPY` to 0.0061 and request the plan | `missingRate` naming USD [[trip-split-7](#trip-split-7)] | | 6 | Set `USD` to 0.92 and request the plan | exactly Cal → Ana 19.28 EUR, then Cal → Ben 23.40 EUR, with the JPY expense valued 75.30 EUR and the USD expense 9.20 EUR split 3.07, 3.07, 3.06 EUR [[trip-split-5](#trip-split-5)] [[trip-split-6](#trip-split-6)] [[trip-split-8](#trip-split-8)] | ### trip-split-16 When an integration test records each row's expenses in order on a fresh `EUR` trip and requests the settlement plan, the test shall assert the plan is exactly the stated transfers in the stated order [[trip-split-8](#trip-split-8)]: | Expenses | Balances | Expected plan | | --- | --- | --- | | Ana pays 6.00 for Dan and Eve; Ben pays 4.00 for Cal | Ana +6, Dan -3, Eve -3, Ben +4, Cal -4 | Dan → Ana 3.00, Eve → Ana 3.00, Cal → Ben 4.00: two zero-sum groups, three transfers [[trip-split-8](#trip-split-8)] | | Ana pays 30.00 for Ana, Ben, and Cal; Ben pays 30.00 for Ana, Ben, and Cal | Ana +10, Ben +10, Cal -20 | Cal → Ana 10.00, Cal → Ben 10.00 [[trip-split-8](#trip-split-8)] | | Ana pays 10.00 for Ben weight 4 and Dan weight 6; Cal pays 3.00 for Ana | Ana +7, Ben -4, Dan -6, Cal +3 | Ben → Ana 4.00, Dan → Ana 3.00, Dan → Cal 3.00: one group, earliest debtor paying earliest creditor [[trip-split-8](#trip-split-8)] | | Ana pays 20.00 for Ben and Dan; Cal pays 10.00 for Ana | Ana +10, Ben -10, Dan -10, Cal +10 | Ben → Ana 10.00, Dan → Cal 10.00, not the equally short Dan → Ana and Ben → Cal [[trip-split-8](#trip-split-8)] | ### trip-split-17 When a device test on an iPhone SE (3rd generation) running the oldest iOS version the library supports builds a `EUR` trip in which each of C1 to C10 pays 55.00 EUR for D1 to D10, with Dj at weight j, and requests its settlement plan, the test shall assert these outcomes: - The 20 travelers with nonzero balances, C1 to C10 at +55.00 and Dj at -10j EUR, get a plan of exactly 15 transfers, each from a D to a C, that zeroes every balance [[trip-split-8](#trip-split-8)]. - The request returns within 0.5 seconds and uses at most 64 MB of additional memory [[trip-split-9](#trip-split-9)]. - After D1 pays 1.00 EUR for E, making 21 travelers with nonzero balances, a plan request is rejected with `groupTooLarge` [[trip-split-7](#trip-split-7)]. ### trip-split-18 Where the trip of [[trip-split-15](#trip-split-15)] has returned its step 6 plan P1, when an integration test runs the steps below in order, the test shall assert each expected outcome: | Step | Action | Expected outcome | | --- | --- | --- | | 1 | Add Cal paying 19.28 EUR for Ana alone, then Ana paying 30.00 EUR for Ana, Ben, and Cal, and request plan P2 | P2 is exactly Cal → Ana 20.00 EUR, then Cal → Ben 13.40 EUR [[trip-split-10](#trip-split-10)] | | 2 | Set `USD` to 0.93 and request plan P3 | P3 is exactly Cal → Ana 19.97 EUR, then Cal → Ben 13.37 EUR, the paid 19.28 EUR unchanged by the new rate [[trip-split-5](#trip-split-5)] [[trip-split-10](#trip-split-10)] | | 3 | Inspect P1 and P2 | P1 is still Cal → Ana 19.28 EUR and Cal → Ben 23.40 EUR, and P2 is still as in step 1 [[trip-split-10](#trip-split-10)] | ### trip-split-19 When the integration tests [[trip-split-12](#trip-split-12)] through [[trip-split-16](#trip-split-16)] and [[trip-split-18](#trip-split-18)] run in a process whose sandbox denies network access, the test shall assert that every one passes and that the sandbox records no network attempt by the library [[trip-split-11](#trip-split-11)]. ### trip-split-20 When a release candidate is checked against the previous release, the release test shall assert these outcomes: - Its currency table contains every code of the previous release's table with the same minor unit, or, for the first release, exactly the ISO 4217 List One codes with a numeric minor unit on the release date [[trip-split-1](#trip-split-1)]. - Its group limit for settlement plans is no lower than the previous release's, or, for the first release, is 20 [[trip-split-7](#trip-split-7)]. ## References [1]: https://www.iso.org/iso-4217-currency-codes.html "ISO 4217 Currency codes"