Fix #434 Use the debts lib to solve settlements.

7 files changed, 32 insertions, 61 deletions

diff --git a/.gitignore b/.gitignore
index 4af5baf..52242f6 100644
--- a/.gitignore
+++ b/.gitignore
@@ -7,3 +7,6 @@ docs/_build/
 .tox
 dist
 .cache/
+build
+.vscode
+.env
\ No newline at end of file
diff --git a/CHANGELOG.rst b/CHANGELOG.rst
index d35fe09..bc9dacb 100644
--- a/CHANGELOG.rst
+++ b/CHANGELOG.rst
@@ -7,6 +7,7 @@ This document describes changes between each past release.
 ================
 
 - Add support for espanol latino america (es_419)
+- Use the external debts lib to solve settlements (#476)
 
 
 4.1.3 (2019-09-18)
diff --git a/ihatemoney/budget.db b/ihatemoney/budget.db
new file mode 100644
index 0000000..e69de29
--- /dev/null
+++ b/ihatemoney/budget.db
diff --git a/ihatemoney/models.py b/ihatemoney/models.py
index 3e908fa..325cf57 100644
--- a/ihatemoney/models.py
+++ b/ihatemoney/models.py
@@ -4,6 +4,7 @@ from datetime import datetime
 from flask_sqlalchemy import SQLAlchemy, BaseQuery
 from flask import g, current_app
 
+from debts import settle
 from sqlalchemy import orm
 from itsdangerous import (TimedJSONWebSignatureSerializer, URLSafeSerializer,
                           BadSignature, SignatureExpired)
@@ -106,46 +107,14 @@ class Project(db.Model):
             return pretty_transactions
 
         # cache value for better performance
-        balance = self.balance
-        credits, debts, transactions = [], [], []
-        # Create lists of credits and debts
-        for person in self.members:
-            if round(balance[person.id], 2) > 0:
-                credits.append({"person": person, "balance": balance[person.id]})
-            elif round(balance[person.id], 2) < 0:
-                debts.append({"person": person, "balance": -balance[person.id]})
-
-        # Try and find exact matches
-        for credit in credits:
-            match = self.exactmatch(round(credit["balance"], 2), debts)
-            if match:
-                for m in match:
-                    transactions.append({
-                        "ower": m["person"],
-                        "receiver": credit["person"],
-                        "amount": m["balance"]
-                    })
-                    debts.remove(m)
-                credits.remove(credit)
-        # Split any remaining debts & credits
-        while credits and debts:
-
-            if credits[0]["balance"] > debts[0]["balance"]:
-                transactions.append({
-                    "ower": debts[0]["person"],
-                    "receiver": credits[0]["person"],
-                    "amount": debts[0]["balance"]
-                })
-                credits[0]["balance"] = credits[0]["balance"] - debts[0]["balance"]
-                del debts[0]
-            else:
-                transactions.append({
-                    "ower": debts[0]["person"],
-                    "receiver": credits[0]["person"],
-                    "amount": credits[0]["balance"]
-                })
-                debts[0]["balance"] = debts[0]["balance"] - credits[0]["balance"]
-                del credits[0]
+        members = {person.id: person for person in self.members}
+        settle_plan = settle(self.balance.items()) or []
+
+        transactions = [{
+            'ower': members[ower_id],
+            'receiver': members[receiver_id],
+            'amount': amount
+        } for ower_id, amount, receiver_id in settle_plan]
 
         return prettify(transactions, pretty_output)
 
diff --git a/ihatemoney/tests/tests.py b/ihatemoney/tests/tests.py
index 551af96..9d611d7 100644
--- a/ihatemoney/tests/tests.py
+++ b/ihatemoney/tests/tests.py
@@ -859,7 +859,7 @@ class BudgetTestCase(IhatemoneyTestCase):
             members[t['receiver']] += t['amount']
         balance = models.Project.query.get("raclette").balance
         for m, a in members.items():
-            self.assertEqual(a, balance[m.id])
+            assert abs(a - balance[m.id]) < 0.01
         return
 
     def test_settle_zero(self):
@@ -980,18 +980,23 @@ class BudgetTestCase(IhatemoneyTestCase):
 
         # generate json export of transactions
         resp = self.client.get("/raclette/export/transactions.json")
-        expected = [{"amount": 127.33, "receiver": "fred", "ower": "alexis"},
-                    {"amount": 55.34, "receiver": "fred", "ower": "tata"},
-                    {"amount": 2.00, "receiver": "fred", "ower": "p\xe9p\xe9"}]
+        expected = [
+            {"amount": 2.00, "receiver": "fred", "ower": "p\xe9p\xe9"},
+            {"amount": 55.34, "receiver": "fred", "ower": "tata"},
+            {"amount": 127.33, "receiver": "fred", "ower": "alexis"},
+        ]
+
         self.assertEqual(json.loads(resp.data.decode('utf-8')), expected)
 
         # generate csv export of transactions
         resp = self.client.get("/raclette/export/transactions.csv")
 
-        expected = ["amount,receiver,ower",
-                    "127.33,fred,alexis",
-                    "55.34,fred,tata",
-                    "2.0,fred,pépé"]
+        expected = [
+            "amount,receiver,ower",
+            "2.0,fred,pépé",
+            "55.34,fred,tata",
+            "127.33,fred,alexis",
+        ]
         received_lines = resp.data.decode('utf-8').split("\n")
 
         for i, line in enumerate(expected):
diff --git a/requirements.txt b/requirements.txt
index a4c6627..4b35378 100644
--- a/requirements.txt
+++ b/requirements.txt
@@ -1,8 +1,9 @@
-alembic==1.1.0
+alembic==1.2.0
 aniso8601==8.0.0
 Babel==2.7.0
 blinker==1.4
 Click==7.0
+debts==0.4
 dnspython==1.16.0
 email-validator==1.0.4
 Flask==1.1.1
@@ -12,7 +13,7 @@ Flask-Mail==0.9.1
 Flask-Migrate==2.5.2
 Flask-RESTful==0.3.7
 Flask-Script==2.0.6
-Flask-SQLAlchemy==2.4.0
+Flask-SQLAlchemy==2.4.1
 Flask-WTF==0.14.2
 idna==2.8
 itsdangerous==1.1.0
@@ -23,5 +24,5 @@ python-dateutil==2.8.0
 pytz==2019.2
 six==1.12.0
 SQLAlchemy==1.3.8
-Werkzeug==0.15.6
+Werkzeug==0.16.0
 WTForms==2.2.1
diff --git a/setup.py b/setup.py
index 38acbbd..675e3f9 100644
--- a/setup.py
+++ b/setup.py
@@ -7,14 +7,6 @@ from setuptools import setup, find_packages
 
 here = os.path.abspath(os.path.dirname(__file__))
 
-
-def parse_requirements(filename):
-    """ load requirements from a pip requirements file """
-    with open(filename) as lines:
-        lineiter = (line.strip() for line in lines)
-        return [line for line in lineiter if line and not line.startswith("#")]
-
-
 README = open('README.rst', encoding='utf-8').read()
 CHANGELOG = open('CHANGELOG.rst', encoding='utf-8').read()
 
@@ -31,7 +23,6 @@ ENTRY_POINTS = {
     ],
 }
 
-
 setup(name='ihatemoney',
       version='4.2.dev0',
       description='A simple shared budget manager web application.',
@@ -69,5 +60,6 @@ setup(name='ihatemoney',
           "flask-cors",
           "six",
           "itsdangerous",
-          "email_validator"],
+          "email_validator",
+          "debts"],
       entry_points=ENTRY_POINTS)