use std::collections::BTreeMap;
use std::error::Error;
use std::fmt::{self, Display, Formatter};
#[derive(Clone, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub struct PartyId(String);
impl PartyId {
pub fn new(value: impl Into<String>) -> Result<Self, KarmaError> {
let value = value.into();
if value.trim().is_empty() {
return Err(KarmaError::EmptyParty);
}
Ok(Self(value))
}
pub fn as_str(&self) -> &str {
&self.0
}
}
impl Display for PartyId {
fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
f.write_str(&self.0)
}
}
impl AsRef<str> for PartyId {
fn as_ref(&self) -> &str {
self.as_str()
}
}
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct KarmaEntry {
giver: PartyId,
receiver: PartyId,
units: u64,
memo: String,
}
impl KarmaEntry {
pub fn new(
giver: impl Into<String>,
receiver: impl Into<String>,
units: u64,
memo: impl Into<String>,
) -> Result<Self, KarmaError> {
let giver = PartyId::new(giver)?;
let receiver = PartyId::new(receiver)?;
if giver == receiver {
return Err(KarmaError::SameParty);
}
if units == 0 {
return Err(KarmaError::ZeroUnits);
}
Ok(Self {
giver,
receiver,
units,
memo: memo.into(),
})
}
pub fn giver(&self) -> &PartyId {
&self.giver
}
pub fn receiver(&self) -> &PartyId {
&self.receiver
}
pub fn units(&self) -> u64 {
self.units
}
pub fn memo(&self) -> &str {
&self.memo
}
}
#[derive(Clone, Debug, Default, PartialEq, Eq)]
pub struct KarmaLedger {
entries: Vec<KarmaEntry>,
}
impl KarmaLedger {
pub const fn new() -> Self {
Self {
entries: Vec::new(),
}
}
pub fn record(
&mut self,
giver: impl Into<String>,
receiver: impl Into<String>,
units: u64,
memo: impl Into<String>,
) -> Result<&KarmaEntry, KarmaError> {
let entry = KarmaEntry::new(giver, receiver, units, memo)?;
self.entries.push(entry);
Ok(self
.entries
.last()
.expect("an entry was inserted immediately before access"))
}
pub fn push(&mut self, entry: KarmaEntry) -> &KarmaEntry {
self.entries.push(entry);
self.entries
.last()
.expect("an entry was inserted immediately before access")
}
pub fn entries(&self) -> &[KarmaEntry] {
&self.entries
}
pub fn is_empty(&self) -> bool {
self.entries.is_empty()
}
pub fn len(&self) -> usize {
self.entries.len()
}
pub fn balances(&self) -> Result<BTreeMap<PartyId, i128>, KarmaError> {
let mut balances = BTreeMap::<PartyId, i128>::new();
for entry in &self.entries {
let units = i128::from(entry.units);
add_balance(&mut balances, &entry.giver, units)?;
add_balance(&mut balances, &entry.receiver, -units)?;
}
Ok(balances)
}
pub fn balance_of(&self, party: &str) -> Result<i128, KarmaError> {
Ok(self
.balances()?
.into_iter()
.find_map(|(id, balance)| (id.as_str() == party).then_some(balance))
.unwrap_or(0))
}
}
fn add_balance(
balances: &mut BTreeMap<PartyId, i128>,
party: &PartyId,
delta: i128,
) -> Result<(), KarmaError> {
let current = balances.entry(party.clone()).or_default();
*current = current.checked_add(delta).ok_or(KarmaError::Overflow)?;
Ok(())
}
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct SettlementTransfer {
from: PartyId,
to: PartyId,
units: u128,
}
impl SettlementTransfer {
pub fn from(&self) -> &PartyId {
&self.from
}
pub fn to(&self) -> &PartyId {
&self.to
}
pub fn units(&self) -> u128 {
self.units
}
}
#[derive(Clone, Debug, Default, PartialEq, Eq)]
pub struct SettlementPlan {
transfers: Vec<SettlementTransfer>,
original_balances: BTreeMap<PartyId, i128>,
}
impl SettlementPlan {
pub fn transfers(&self) -> &[SettlementTransfer] {
&self.transfers
}
pub fn total_units(&self) -> u128 {
self.transfers.iter().map(SettlementTransfer::units).sum()
}
pub fn is_conserved(&self) -> bool {
let mut balances = self.original_balances.clone();
for transfer in &self.transfers {
let Ok(units) = i128::try_from(transfer.units) else {
return false;
};
let Some(from) = balances
.get(&transfer.from)
.and_then(|value| value.checked_add(units))
else {
return false;
};
let Some(to) = balances
.get(&transfer.to)
.and_then(|value| value.checked_sub(units))
else {
return false;
};
balances.insert(transfer.from.clone(), from);
balances.insert(transfer.to.clone(), to);
}
balances.values().all(|&balance| balance == 0)
}
}
#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
pub struct Cocoshiga;
impl Cocoshiga {
pub fn settle(ledger: &KarmaLedger) -> Result<SettlementPlan, KarmaError> {
let balances = ledger.balances()?;
let sum = balances.values().try_fold(0i128, |total, &balance| {
total.checked_add(balance).ok_or(KarmaError::Overflow)
})?;
if sum != 0 {
return Err(KarmaError::Unbalanced);
}
let mut debtors: Vec<(PartyId, u128)> = balances
.iter()
.filter(|&(_, &balance)| balance < 0)
.map(|(party, &balance)| (party.clone(), balance.unsigned_abs()))
.collect();
let mut creditors: Vec<(PartyId, u128)> = balances
.iter()
.filter(|&(_, &balance)| balance > 0)
.map(|(party, &balance)| (party.clone(), balance as u128))
.collect();
let mut transfers = Vec::new();
let (mut debtor_index, mut creditor_index) = (0usize, 0usize);
while debtor_index < debtors.len() && creditor_index < creditors.len() {
let units = debtors[debtor_index].1.min(creditors[creditor_index].1);
transfers.push(SettlementTransfer {
from: debtors[debtor_index].0.clone(),
to: creditors[creditor_index].0.clone(),
units,
});
debtors[debtor_index].1 -= units;
creditors[creditor_index].1 -= units;
if debtors[debtor_index].1 == 0 {
debtor_index += 1;
}
if creditors[creditor_index].1 == 0 {
creditor_index += 1;
}
}
let plan = SettlementPlan {
transfers,
original_balances: balances,
};
if !plan.is_conserved() {
return Err(KarmaError::Unbalanced);
}
Ok(plan)
}
}
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
#[non_exhaustive]
pub enum KarmaError {
EmptyParty,
SameParty,
ZeroUnits,
Overflow,
Unbalanced,
}
impl Display for KarmaError {
fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
f.write_str(match self {
Self::EmptyParty => "party identifiers cannot be empty",
Self::SameParty => "giver and receiver must be different parties",
Self::ZeroUnits => "karma units must be greater than zero",
Self::Overflow => "karma balance overflowed",
Self::Unbalanced => "settlement does not conserve all balances",
})
}
}
impl Error for KarmaError {}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn reciprocal_karma_is_netted() {
let mut ledger = KarmaLedger::new();
ledger.record("alice", "bob", 10, "lunch").unwrap();
ledger.record("bob", "alice", 4, "coffee").unwrap();
let plan = Cocoshiga::settle(&ledger).unwrap();
assert_eq!(
plan.transfers(),
&[SettlementTransfer {
from: PartyId::new("bob").unwrap(),
to: PartyId::new("alice").unwrap(),
units: 6,
}]
);
assert!(plan.is_conserved());
}
#[test]
fn transitive_karma_becomes_one_transfer() {
let mut ledger = KarmaLedger::new();
ledger.record("alice", "bob", 7, "").unwrap();
ledger.record("bob", "carol", 7, "").unwrap();
let plan = Cocoshiga::settle(&ledger).unwrap();
assert_eq!(plan.transfers().len(), 1);
assert_eq!(plan.transfers()[0].from().as_str(), "carol");
assert_eq!(plan.transfers()[0].to().as_str(), "alice");
assert_eq!(plan.transfers()[0].units(), 7);
}
#[test]
fn settlement_is_deterministic_and_conserved() {
let mut ledger = KarmaLedger::new();
ledger.record("d", "a", 8, "").unwrap();
ledger.record("c", "b", 5, "").unwrap();
ledger.record("a", "c", 2, "").unwrap();
let first = Cocoshiga::settle(&ledger).unwrap();
let second = Cocoshiga::settle(&ledger).unwrap();
assert_eq!(first, second);
assert!(first.is_conserved());
}
#[test]
fn invalid_entries_do_not_mutate_the_ledger() {
let mut ledger = KarmaLedger::new();
assert_eq!(
ledger.record("", "bob", 1, "").unwrap_err(),
KarmaError::EmptyParty
);
assert_eq!(
ledger.record("alice", "alice", 1, "").unwrap_err(),
KarmaError::SameParty
);
assert_eq!(
ledger.record("alice", "bob", 0, "").unwrap_err(),
KarmaError::ZeroUnits
);
assert!(ledger.is_empty());
}
#[test]
fn empty_ledger_has_an_empty_valid_plan() {
let plan = Cocoshiga::settle(&KarmaLedger::new()).unwrap();
assert!(plan.transfers().is_empty());
assert_eq!(plan.total_units(), 0);
assert!(plan.is_conserved());
}
}