From dd0280112a7722ebd8caf7c3e4a33ea6b1d4e141 Mon Sep 17 00:00:00 2001
From: Lars Wirzenius <liw@liw.fi>
Date: Sat, 29 May 2021 21:41:29 +0300
Subject: refactor: make the algorithm for the server more clear

Sponsored-by: author
---
 server.py | 131 ++++++++++++++++++++++++++++++++++++++------------------------
 1 file changed, 80 insertions(+), 51 deletions(-)

diff --git a/server.py b/server.py
index 0d676db..b4be90d 100755
--- a/server.py
+++ b/server.py
@@ -4,73 +4,102 @@ import bottle
 import random
 
 
-def max(answer):
-    return answer
+# Base class for a choosing algorithm.
+class Algorithm:
+    def __init__(self, count):
+        self._count = count
+        self._rid = None
+        self._left = None
+        self._right = None
 
+    def first(self):
+        # Decide first action: return result or first comparison.
+        raise NotImplementedError()
 
-def min(answer):
-    return not answer
+    def decide(self, left_is_smaller):
+        # Given the result of the previous less-than comparison, return new
+        # message to return to client.
+        #
+        # If the right value is past the end of the list, the caller should
+        # end the process.
+        raise NotImplementedError()
 
+    def rid(self):
+        # Return id of latest request.
+        return self._rid
 
-class Find:
-    def __init__(self):
-        self.reset()
+    def done(self, result):
+        return {"type": "done", "result": result}
 
-    def reset(self):
-        self._algo = None
-        self._count = None
-        self._result = 0
-        self._pos = 0
-        self._rid = None
+    def compare(self, left, right):
+        self._rid = random.randint(1, 2 ** 30)
+        self._left = left
+        self._right = right
+        return {
+            "type": "compare",
+            "left": left,
+            "right": right,
+            "request_id": self._rid,
+        }
 
-    def new(self, algo, count):
-        assert count > 0
 
-        if count == 1:
-            # List has length 1: we know the answer.
+class MinOrMax(Algorithm):
+    # Find index of smallest or largest item.
+
+    def first(self):
+        if self._count == 1:
             return self.done(0)
+        return self.compare(0, 1)
 
-        self.reset()
-        self._algo = algo
-        self._count = count
-        return self.next(self._result)
+    def decide(self, left_is_smaller):
+        self._result = self.choose(self._left, self._right, left_is_smaller)
 
-    def decide(self, answer, rid):
-        assert rid == self._rid
-        if self._algo(answer):
-            # use previous "right" item in comparison
-            return self.next(self._pos)
+        right = self._right + 1
+        if right >= self._count:
+            return self.done(self._result)
+        return self.compare(self._result, right)
+
+    def choose(self, left, right, left_is_smaller):
+        raise NotImplementedError()
+
+
+class Max(MinOrMax):
+    # Find index of largest item.
+
+    def choose(self, left, right, left_is_smaller):
+        if left_is_smaller:
+            return right
         else:
-            # use previous result
-            return self.next(self._result)
+            return left
 
-    def next(self, new_result):
-        self._result = new_result
 
-        # Choose next item to compare.
-        self._pos += 1
+class Min(MinOrMax):
+    # Find index of smallest item.
 
-        if self._pos >= self._count:
-            # We have reached the end of the list.
-            return self.done(self._result)
+    def choose(self, left, right, left_is_smaller):
+        if left_is_smaller:
+            return left
+        else:
+            return right
 
-        # Compare newly chosen item with current result.
-        return self.compare(self._result, self._pos)
 
-    def compare(self, left, right):
-        self._rid = random.randint(1, 2 ** 30)
-        return {
-            "type": "compare",
-            "left": left,
-            "right": right,
-            "request_id": self._rid,
-        }
+class Computer:
+    def __init__(self):
+        self.reset(None)
 
-    def done(self, n):
-        return {"type": "done", "result": n}
+    def reset(self, algo):
+        self._algo = algo
+
+    def new(self, algo):
+        self.reset(algo)
+        return self._algo.first()
+
+    def decide(self, answer, rid):
+        assert rid == self._algo.rid()
+        return self._algo.decide(answer)
 
 
-session = Find()
+session = Computer()
 
 
 @bottle.post("/")
@@ -79,15 +108,15 @@ def root():
     print("request", msg)
     msg_type = msg.get("type")
     if msg_type == "compute_max":
-        o = session.new(max, msg["length"])
+        o = session.new(Max(msg["length"]))
     elif msg_type == "compute_min":
-        o = session.new(min, msg["length"])
+        o = session.new(Min(msg["length"]))
     elif msg_type == "comp_result":
         o = session.decide(msg["answer"], msg["request_id"])
     else:
         assert False
 
-    print("result", o, session._pos)
+    print("result", o)
     bottle.response.content_type = "application/json"
     return o
 
-- 
cgit v1.2.1