use itertools::Itertools;
use rusty_money::money;
use rusty_money::Currency;
use rusty_money::Money;
use std::cmp;
use std::collections::HashMap;
use std::error::Error;
use std::fmt;
#[derive(Debug, Eq, Ord, PartialEq, PartialOrd)]
pub struct Transaction {
debtor: String,
creditor: String,
amount: Money,
}
#[macro_export]
macro_rules! transaction {
($x:expr, $y:expr, $z:expr) => {
Transaction::from_tuple($x.to_string(), $y.to_string(), $z).unwrap()
};
}
impl Transaction {
pub fn new(debtor: String, creditor: String, amount: Money) -> Result<Self, ParseAmountError> {
if !amount.is_positive() {
return Err(ParseAmountError { amount });
};
Ok(Transaction {
debtor,
creditor,
amount,
})
}
pub fn from_tuple(
debtor: String,
creditor: String,
amount: (i32, &str),
) -> Result<Self, ParseAmountError> {
let (value, currency) = amount;
let money_amount = Money::from_string(value.to_string(), currency.to_string());
Transaction::new(debtor, creditor, money_amount)
}
}
impl fmt::Display for Transaction {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
write!(f, "{} owes {} {}", self.debtor, self.creditor, self.amount)
}
}
#[derive(Debug, Eq, Ord, PartialEq, PartialOrd)]
pub struct MultiPartyTransaction {
debtors: Vec<String>,
creditors: Vec<String>,
amount: Money,
}
impl MultiPartyTransaction {
pub fn new(
debtors: Vec<String>,
creditors: Vec<String>,
amount: Money,
) -> Result<Self, ParseAmountError> {
if amount.is_negative() {
return Err(ParseAmountError { amount });
};
Ok(MultiPartyTransaction {
debtors,
creditors,
amount,
})
}
}
impl fmt::Display for MultiPartyTransaction {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
write!(
f,
"{} owes {} to {}",
self.debtors.join(","),
self.amount,
self.creditors.join(","),
)
}
}
#[derive(Debug)]
pub struct ParseAmountError {
amount: Money,
}
impl Error for ParseAmountError {}
impl fmt::Display for ParseAmountError {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
write!(
f,
"Transaction amount {} is less than or equal to 0",
self.amount
)
}
}
#[derive(Debug)]
pub struct Ledger {
map: HashMap<String, Money>,
}
impl Ledger {
pub fn new() -> Ledger {
Ledger {
map: HashMap::new(),
}
}
pub fn add_transaction(&mut self, transaction: Transaction) {
*self
.map
.entry(transaction.debtor)
.or_insert_with(|| money!(0, "USD")) -= transaction.amount.clone();
*self
.map
.entry(transaction.creditor)
.or_insert_with(|| money!(0, "USD")) += transaction.amount.clone();
}
pub fn add_multi_party_transaction(&mut self, transaction: MultiPartyTransaction) {
let num_debtors = transaction.debtors.len() as i32;
let mut debt_shares = transaction.amount.allocate_to(num_debtors);
for debtor in transaction.debtors {
*self.map.entry(debtor).or_insert_with(|| money!(0, "USD")) -=
debt_shares.pop().unwrap();
}
let num_creditors = transaction.creditors.len() as i32;
let mut credit_shares = transaction.amount.allocate_to(num_creditors);
for creditor in transaction.creditors {
*self.map.entry(creditor).or_insert_with(|| money!(0, "USD")) +=
credit_shares.pop().unwrap();
}
}
pub fn settle(&mut self) -> Vec<Transaction> {
self.settle_upto(self.map.len() - 1)
}
pub fn settle_upto(&mut self, group_size: usize) -> Vec<Transaction> {
let mut payments: Vec<Transaction> = Vec::new();
if group_size > 0 {
for x in 1..=group_size {
payments.append(&mut self.settle_combinations(x));
}
}
payments.append(&mut self.clear_all_entries());
payments
}
pub fn to_vector(&self) -> Vec<(String, Money)> {
let mut ledger_entries: Vec<(String, Money)> = Vec::new();
for (key, val) in self.map.iter() {
ledger_entries.push((key.clone(), val.clone()));
}
ledger_entries
}
fn panic_unless_empty(&self) {
for (_, val) in self.map.iter() {
if !val.is_zero() {
panic!();
}
}
}
fn settle_combinations(&mut self, combo_size: usize) -> Vec<Transaction> {
let mut payments: Vec<Transaction> = Vec::new();
let settling_combinations = self.find_zero_sum_combinations(combo_size);
for combo in settling_combinations {
let mut debtor_keys: Vec<String> = Vec::new();
let mut creditor_keys: Vec<String> = Vec::new();
for item in combo {
if item.1.is_positive() {
creditor_keys.push(item.0)
} else if item.1.is_negative() {
debtor_keys.push(item.0)
} else {
}
}
payments.append(&mut self.clear_given_keys(debtor_keys, creditor_keys));
}
payments
}
fn clear_all_entries(&mut self) -> Vec<Transaction> {
let (debtor_keys, creditor_keys) = self.debtor_and_creditor_keys();
let transactions = self.clear_given_keys(debtor_keys, creditor_keys);
self.panic_unless_empty();
transactions
}
fn clear_given_keys(
&mut self,
debtors: Vec<String>,
creditors: Vec<String>,
) -> Vec<Transaction> {
let mut payments: Vec<Transaction> = Vec::new();
for debtor in &debtors {
let mut debtor_amount = self.map.get(debtor).unwrap().clone();
for creditor in &creditors {
let mut creditor_amount = self.map.get(creditor).unwrap().clone();
while (creditor_amount.is_positive()) && (debtor_amount.is_negative()) {
let credit_abs = creditor_amount.amount().abs();
let debt_abs = debtor_amount.amount().abs();
let payment_amount = cmp::min(credit_abs, debt_abs);
debtor_amount += Money::new(payment_amount, Currency::new("USD".to_string()));
self.map.insert(debtor.clone(), debtor_amount.clone());
creditor_amount -= Money::new(payment_amount, Currency::new("USD".to_string()));
self.map.insert(creditor.clone(), creditor_amount.clone());
payments.push(
Transaction::new(
debtor.clone(),
creditor.clone(),
money!(payment_amount, "USD"),
)
.unwrap(),
);
}
}
}
payments
}
fn find_zero_sum_combinations(&self, combo_size: usize) -> Vec<Vec<(String, Money)>> {
let mut zero_sum_combinations: Vec<Vec<(String, Money)>> = Vec::new();
let combinations = self.to_vector().into_iter().combinations(combo_size);
for item in combinations {
if item
.iter()
.fold(money!(0, "USD"), |acc, x| acc + x.1.clone())
.is_zero()
{
zero_sum_combinations.push(item);
}
}
zero_sum_combinations
}
fn debtor_and_creditor_keys(&self) -> (Vec<String>, Vec<String>) {
let mut creditors: Vec<String> = Vec::new();
let mut debtors: Vec<String> = Vec::new();
for (person, value) in &self.map {
if value.is_positive() {
creditors.push(person.clone());
} else if value.is_negative() {
debtors.push(person.clone());
} else {
}
}
(debtors, creditors)
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn ledger_settle_matches_equal_debts_and_credits() {
let mut ledger = Ledger::new();
let expected_results = vec![
transaction!("A", "B", (2, "USD")),
transaction!("C", "F", (3, "USD")),
transaction!("D", "F", (5, "USD")),
transaction!("E", "F", (7, "USD")),
];
for _ in 0..5 {
ledger.add_transaction(transaction!("A", "B", (2, "USD")));
ledger.add_transaction(transaction!("C", "F", (3, "USD")));
ledger.add_transaction(transaction!("D", "F", (5, "USD")));
ledger.add_transaction(transaction!("E", "F", (7, "USD")));
let mut payments = ledger.settle();
payments.sort();
assert_eq!(payments, expected_results);
}
}
#[test]
fn ledger_settle_with_size_3_matches_groups_of_3_credits_and_debits() {
let mut ledger = Ledger::new();
let expected_results = vec![
transaction!("A", "D", (3, "USD")),
transaction!("C", "D", (4, "USD")),
transaction!("E", "B", (10, "USD")),
transaction!("F", "B", (17, "USD")),
transaction!("J", "K", (20, "USD")),
transaction!("U", "K", (21, "USD")),
];
for _ in 0..5 {
ledger.add_transaction(transaction!("A", "D", (3, "USD")));
ledger.add_transaction(transaction!("C", "D", (4, "USD")));
ledger.add_transaction(transaction!("E", "B", (10, "USD")));
ledger.add_transaction(transaction!("F", "B", (17, "USD")));
ledger.add_transaction(transaction!("J", "K", (20, "USD")));
ledger.add_transaction(transaction!("U", "K", (21, "USD")));
let mut payments = ledger.settle();
payments.sort();
assert_eq!(payments, expected_results);
}
}
#[test]
#[should_panic]
fn ledger_settle_panics_if_unbalanced() {
let mut ledger = Ledger::new();
ledger
.map
.entry("A".to_string())
.or_insert(money!(10, "USD"));
ledger.settle();
}
#[test]
fn mptx_can_handle_debtor_rounding() {
let transaction = MultiPartyTransaction::new(
vec!["A".to_string(), "B".to_string(), "C".to_string()],
vec!["D".to_string()],
money!(10, "USD"),
)
.unwrap();
let mut ledger = Ledger::new();
ledger.add_multi_party_transaction(transaction);
let remaining = ledger
.to_vector()
.into_iter()
.fold(money!(0, "USD"), |acc, x| acc + x.1);
assert_eq!(remaining, money!(0, "USD"));
}
#[test]
fn mptx_can_handle_creditor_rounding() {
let transaction = MultiPartyTransaction::new(
vec!["A".to_string()],
vec!["B".to_string(), "C".to_string(), "D".to_string()],
money!(10, "USD"),
)
.unwrap();
let mut ledger = Ledger::new();
ledger.add_multi_party_transaction(transaction);
let ledger_balance = ledger
.to_vector()
.into_iter()
.fold(money!(0, "USD"), |acc, x| acc + x.1);
assert_eq!(ledger_balance, money!(0, "USD"));
}
#[test]
fn tx_can_create_positive_transaction() {
match Transaction::new("A".to_string(), "B".to_string(), money!(1, "USD")) {
Ok(_) => assert!(true),
Err(_) => assert!(false),
};
}
#[test]
fn tx_cannot_create_non_positive_transaction() {
match Transaction::new("A".to_string(), "B".to_string(), money!(-1, "USD")) {
Ok(_) => assert!(false),
Err(_) => assert!(true),
};
match Transaction::new("A".to_string(), "B".to_string(), money!(0, "USD")) {
Ok(_) => assert!(false),
Err(_) => assert!(true),
};
}
}