1use std::collections::BTreeMap;
24use std::error::Error;
25use std::fmt::{self, Display, Formatter};
26
27#[derive(Clone, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
29pub struct PartyId(String);
30
31impl PartyId {
32 pub fn new(value: impl Into<String>) -> Result<Self, KarmaError> {
34 let value = value.into();
35 if value.trim().is_empty() {
36 return Err(KarmaError::EmptyParty);
37 }
38 Ok(Self(value))
39 }
40
41 pub fn as_str(&self) -> &str {
43 &self.0
44 }
45}
46
47impl Display for PartyId {
48 fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
49 f.write_str(&self.0)
50 }
51}
52
53impl AsRef<str> for PartyId {
54 fn as_ref(&self) -> &str {
55 self.as_str()
56 }
57}
58
59#[derive(Clone, Debug, PartialEq, Eq)]
61pub struct KarmaEntry {
62 giver: PartyId,
63 receiver: PartyId,
64 units: u64,
65 memo: String,
66}
67
68impl KarmaEntry {
69 pub fn new(
71 giver: impl Into<String>,
72 receiver: impl Into<String>,
73 units: u64,
74 memo: impl Into<String>,
75 ) -> Result<Self, KarmaError> {
76 let giver = PartyId::new(giver)?;
77 let receiver = PartyId::new(receiver)?;
78 if giver == receiver {
79 return Err(KarmaError::SameParty);
80 }
81 if units == 0 {
82 return Err(KarmaError::ZeroUnits);
83 }
84 Ok(Self {
85 giver,
86 receiver,
87 units,
88 memo: memo.into(),
89 })
90 }
91
92 pub fn giver(&self) -> &PartyId {
94 &self.giver
95 }
96
97 pub fn receiver(&self) -> &PartyId {
99 &self.receiver
100 }
101
102 pub fn units(&self) -> u64 {
104 self.units
105 }
106
107 pub fn memo(&self) -> &str {
109 &self.memo
110 }
111}
112
113#[derive(Clone, Debug, Default, PartialEq, Eq)]
115pub struct KarmaLedger {
116 entries: Vec<KarmaEntry>,
117}
118
119impl KarmaLedger {
120 pub const fn new() -> Self {
122 Self {
123 entries: Vec::new(),
124 }
125 }
126
127 pub fn record(
129 &mut self,
130 giver: impl Into<String>,
131 receiver: impl Into<String>,
132 units: u64,
133 memo: impl Into<String>,
134 ) -> Result<&KarmaEntry, KarmaError> {
135 let entry = KarmaEntry::new(giver, receiver, units, memo)?;
136 self.entries.push(entry);
137 Ok(self
138 .entries
139 .last()
140 .expect("an entry was inserted immediately before access"))
141 }
142
143 pub fn push(&mut self, entry: KarmaEntry) -> &KarmaEntry {
145 self.entries.push(entry);
146 self.entries
147 .last()
148 .expect("an entry was inserted immediately before access")
149 }
150
151 pub fn entries(&self) -> &[KarmaEntry] {
153 &self.entries
154 }
155
156 pub fn is_empty(&self) -> bool {
158 self.entries.is_empty()
159 }
160
161 pub fn len(&self) -> usize {
163 self.entries.len()
164 }
165
166 pub fn balances(&self) -> Result<BTreeMap<PartyId, i128>, KarmaError> {
170 let mut balances = BTreeMap::<PartyId, i128>::new();
171 for entry in &self.entries {
172 let units = i128::from(entry.units);
173 add_balance(&mut balances, &entry.giver, units)?;
174 add_balance(&mut balances, &entry.receiver, -units)?;
175 }
176 Ok(balances)
177 }
178
179 pub fn balance_of(&self, party: &str) -> Result<i128, KarmaError> {
181 Ok(self
182 .balances()?
183 .into_iter()
184 .find_map(|(id, balance)| (id.as_str() == party).then_some(balance))
185 .unwrap_or(0))
186 }
187}
188
189fn add_balance(
190 balances: &mut BTreeMap<PartyId, i128>,
191 party: &PartyId,
192 delta: i128,
193) -> Result<(), KarmaError> {
194 let current = balances.entry(party.clone()).or_default();
195 *current = current.checked_add(delta).ok_or(KarmaError::Overflow)?;
196 Ok(())
197}
198
199#[derive(Clone, Debug, PartialEq, Eq)]
201pub struct SettlementTransfer {
202 from: PartyId,
203 to: PartyId,
204 units: u128,
205}
206
207impl SettlementTransfer {
208 pub fn from(&self) -> &PartyId {
210 &self.from
211 }
212
213 pub fn to(&self) -> &PartyId {
215 &self.to
216 }
217
218 pub fn units(&self) -> u128 {
220 self.units
221 }
222}
223
224#[derive(Clone, Debug, Default, PartialEq, Eq)]
226pub struct SettlementPlan {
227 transfers: Vec<SettlementTransfer>,
228 original_balances: BTreeMap<PartyId, i128>,
229}
230
231impl SettlementPlan {
232 pub fn transfers(&self) -> &[SettlementTransfer] {
234 &self.transfers
235 }
236
237 pub fn total_units(&self) -> u128 {
239 self.transfers.iter().map(SettlementTransfer::units).sum()
240 }
241
242 pub fn is_conserved(&self) -> bool {
244 let mut balances = self.original_balances.clone();
245 for transfer in &self.transfers {
246 let Ok(units) = i128::try_from(transfer.units) else {
247 return false;
248 };
249 let Some(from) = balances
250 .get(&transfer.from)
251 .and_then(|value| value.checked_add(units))
252 else {
253 return false;
254 };
255 let Some(to) = balances
256 .get(&transfer.to)
257 .and_then(|value| value.checked_sub(units))
258 else {
259 return false;
260 };
261 balances.insert(transfer.from.clone(), from);
262 balances.insert(transfer.to.clone(), to);
263 }
264 balances.values().all(|&balance| balance == 0)
265 }
266}
267
268#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
270pub struct Cocoshiga;
271
272impl Cocoshiga {
273 pub fn settle(ledger: &KarmaLedger) -> Result<SettlementPlan, KarmaError> {
278 let balances = ledger.balances()?;
279 let sum = balances.values().try_fold(0i128, |total, &balance| {
280 total.checked_add(balance).ok_or(KarmaError::Overflow)
281 })?;
282 if sum != 0 {
283 return Err(KarmaError::Unbalanced);
284 }
285
286 let mut debtors: Vec<(PartyId, u128)> = balances
287 .iter()
288 .filter(|&(_, &balance)| balance < 0)
289 .map(|(party, &balance)| (party.clone(), balance.unsigned_abs()))
290 .collect();
291 let mut creditors: Vec<(PartyId, u128)> = balances
292 .iter()
293 .filter(|&(_, &balance)| balance > 0)
294 .map(|(party, &balance)| (party.clone(), balance as u128))
295 .collect();
296
297 let mut transfers = Vec::new();
298 let (mut debtor_index, mut creditor_index) = (0usize, 0usize);
299 while debtor_index < debtors.len() && creditor_index < creditors.len() {
300 let units = debtors[debtor_index].1.min(creditors[creditor_index].1);
301 transfers.push(SettlementTransfer {
302 from: debtors[debtor_index].0.clone(),
303 to: creditors[creditor_index].0.clone(),
304 units,
305 });
306 debtors[debtor_index].1 -= units;
307 creditors[creditor_index].1 -= units;
308 if debtors[debtor_index].1 == 0 {
309 debtor_index += 1;
310 }
311 if creditors[creditor_index].1 == 0 {
312 creditor_index += 1;
313 }
314 }
315
316 let plan = SettlementPlan {
317 transfers,
318 original_balances: balances,
319 };
320 if !plan.is_conserved() {
321 return Err(KarmaError::Unbalanced);
322 }
323 Ok(plan)
324 }
325}
326
327#[derive(Clone, Copy, Debug, PartialEq, Eq)]
329#[non_exhaustive]
330pub enum KarmaError {
331 EmptyParty,
333 SameParty,
335 ZeroUnits,
337 Overflow,
339 Unbalanced,
341}
342
343impl Display for KarmaError {
344 fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
345 f.write_str(match self {
346 Self::EmptyParty => "party identifiers cannot be empty",
347 Self::SameParty => "giver and receiver must be different parties",
348 Self::ZeroUnits => "karma units must be greater than zero",
349 Self::Overflow => "karma balance overflowed",
350 Self::Unbalanced => "settlement does not conserve all balances",
351 })
352 }
353}
354
355impl Error for KarmaError {}
356
357#[cfg(test)]
358mod tests {
359 use super::*;
360
361 #[test]
362 fn reciprocal_karma_is_netted() {
363 let mut ledger = KarmaLedger::new();
364 ledger.record("alice", "bob", 10, "lunch").unwrap();
365 ledger.record("bob", "alice", 4, "coffee").unwrap();
366
367 let plan = Cocoshiga::settle(&ledger).unwrap();
368 assert_eq!(
369 plan.transfers(),
370 &[SettlementTransfer {
371 from: PartyId::new("bob").unwrap(),
372 to: PartyId::new("alice").unwrap(),
373 units: 6,
374 }]
375 );
376 assert!(plan.is_conserved());
377 }
378
379 #[test]
380 fn transitive_karma_becomes_one_transfer() {
381 let mut ledger = KarmaLedger::new();
382 ledger.record("alice", "bob", 7, "").unwrap();
383 ledger.record("bob", "carol", 7, "").unwrap();
384
385 let plan = Cocoshiga::settle(&ledger).unwrap();
386 assert_eq!(plan.transfers().len(), 1);
387 assert_eq!(plan.transfers()[0].from().as_str(), "carol");
388 assert_eq!(plan.transfers()[0].to().as_str(), "alice");
389 assert_eq!(plan.transfers()[0].units(), 7);
390 }
391
392 #[test]
393 fn settlement_is_deterministic_and_conserved() {
394 let mut ledger = KarmaLedger::new();
395 ledger.record("d", "a", 8, "").unwrap();
396 ledger.record("c", "b", 5, "").unwrap();
397 ledger.record("a", "c", 2, "").unwrap();
398
399 let first = Cocoshiga::settle(&ledger).unwrap();
400 let second = Cocoshiga::settle(&ledger).unwrap();
401 assert_eq!(first, second);
402 assert!(first.is_conserved());
403 }
404
405 #[test]
406 fn invalid_entries_do_not_mutate_the_ledger() {
407 let mut ledger = KarmaLedger::new();
408 assert_eq!(
409 ledger.record("", "bob", 1, "").unwrap_err(),
410 KarmaError::EmptyParty
411 );
412 assert_eq!(
413 ledger.record("alice", "alice", 1, "").unwrap_err(),
414 KarmaError::SameParty
415 );
416 assert_eq!(
417 ledger.record("alice", "bob", 0, "").unwrap_err(),
418 KarmaError::ZeroUnits
419 );
420 assert!(ledger.is_empty());
421 }
422
423 #[test]
424 fn empty_ledger_has_an_empty_valid_plan() {
425 let plan = Cocoshiga::settle(&KarmaLedger::new()).unwrap();
426 assert!(plan.transfers().is_empty());
427 assert_eq!(plan.total_units(), 0);
428 assert!(plan.is_conserved());
429 }
430}