Pass everything in first two parts except for DPLoop

1 files changed, 201 insertions, 28 deletions

diff --git a/src/act4e_mcdp_solution/solver_dp.py b/src/act4e_mcdp_solution/solver_dp.py
index d6d1a7a..a95451f 100644
--- a/src/act4e_mcdp_solution/solver_dp.py
+++ b/src/act4e_mcdp_solution/solver_dp.py
@@ -1,6 +1,10 @@
 from typing import Optional, TypeVar
 from act4e_mcdp import *  # type: ignore
 from decimal import Decimal
+from functools import reduce
+from typing import Tuple
+
+import itertools
 
 __all__ = [
     "DPSolver",
@@ -88,7 +92,10 @@ class DPSolver(DPSolverInterface):
 
         # This is the dual of Constant above. Swap functionalities and resources.
 
-        raise NotImplementedError
+        max_f = dp.c.value
+        max_functionality = LowerSet.principal(max_f)
+        return Interval.degenerate(max_functionality)
+
 
     def solve_dp_FixFunMinRes_Limit(
         self, dp: Limit[X], query: FixFunMinResQuery[X]
@@ -99,7 +106,12 @@ class DPSolver(DPSolverInterface):
 
         # This is the dual of Constant above. Swap functionalities and resources.
 
-        raise NotImplementedError
+        if dp.F.geq(dp.c.value, query.functionality):
+            min_r = ()
+            return Interval.degenerate(UpperSet.principal(min_r))
+        else:
+            empty = UpperSet.empty()
+            return Interval.degenerate(empty)
 
     # walkthrough: ceil(f) <= r  DP
 
@@ -179,8 +191,19 @@ class DPSolver(DPSolverInterface):
         # f <= floor(r)
 
         # This is dual to M_Ceil_DP
+        f = query.functionality
+        assert isinstance(f, Decimal)
 
-        raise NotImplementedError
+        R: Numbers = dp.R
+        F: Numbers = dp.F
+
+        if f.is_infinite():
+            min_r = f
+        else:
+            min_r = Decimal(f.__floor__())
+
+        min_resources = R.largest_upperset_above(min_r)
+        return Interval.degenerate(min_resources)
 
     def solve_dp_FixResMaxFun_M_FloorFun_DP(
         self, dp: M_FloorFun_DP, query: FixResMaxFunQuery[Decimal]
@@ -188,8 +211,16 @@ class DPSolver(DPSolverInterface):
         # f <= floor(r)
 
         # This is dual to M_Ceil_DP
+        r = query.resources
+        assert isinstance(r, Decimal), r
 
-        raise NotImplementedError
+        if r.is_infinite():
+            max_f = r
+        else:
+            max_f = Decimal(r.__floor__())
+
+        max_functionalities = dp.F.largest_lowerset_below(max_f)
+        return Interval.degenerate(max_functionalities)
 
     # exercise: catalogue
 
@@ -200,21 +231,36 @@ class DPSolver(DPSolverInterface):
         F = dp.F
 
         # Hint: iterate over the entries of the catalogue
+        min_rs = []
+
         name: str
         entry_info: EntryInfo[FT, RT]
         for name, entry_info in dp.entries.items():
             # Then check if this entry is valid for the functionality
-            # In that case,  the resources of the entry are a valid solution
-            ...
+            # In that case, the resources of the entry are a valid solution
+            if F.leq(f, entry_info.f_max):
+                min_rs.append(entry_info.r_min)
 
-        raise NotImplementedError
+        if not min_rs:
+            return Interval.degenerate(UpperSet.empty())
+
+        min_r = min(min_rs)
+        return Interval.degenerate(UpperSet.principal(min_r))
 
     def solve_dp_FixResMaxFun_CatalogueDP(
         self, dp: CatalogueDP[FT, RT], query: FixResMaxFunQuery[RT]
     ) -> Interval[LowerSet[FT]]:
-        # Same pattern as above, but functionalities and resources are swapped.
 
-        raise NotImplementedError
+        max_fs = []
+        for _, info in dp.entries.items():
+            if dp.R.geq(query.resources, info.r_min):
+                max_fs.append(info.f_max)
+
+        if not max_fs:
+            return Interval.degenerate(LowerSet.empty())
+
+        max_f = max(max_fs)
+        return Interval.degenerate(LowerSet.principal(max_f))
 
     # exercise: series interconnections
 
@@ -233,13 +279,74 @@ class DPSolver(DPSolverInterface):
         # Note 2: the solve_dp_FixFunMinRes_DPSeries() returns an *interval* of upper sets.
         # Just treat the optimistic and pessimistic cases separately and then combine them in an interval.
 
-        raise NotImplementedError
+        def chain_naive(queries, dp):
+            us_res = [self.solve_dp_FixFunMinRes(dp, query)
+                      for query in queries]
+
+            optimistic = (FixFunMinResQuery(functionality=r)
+                          for us_r in us_res for r in us_r.optimistic.minimals)
+
+            pessimistic = (FixFunMinResQuery(functionality=r)
+                           for us_r in us_res for r in us_r.pessimistic.minimals)
+
+            return itertools.chain(optimistic, pessimistic)
+
+        queries = list(reduce(chain_naive, dp.subs, (query,)))
+        
+        if not queries:
+            return Interval.degenerate(UpperSet.empty())
+
+        min_r = queries[0].functionality
+        max_r = queries[0].functionality
+
+        for query in queries:
+            r = query.functionality
+            if r < min_r:
+                min_r = r
+
+            if r > max_r:
+                max_r = r
+
+        return Interval(optimistic=dp.R.largest_upperset_above(min_r),
+                        pessimistic=dp.R.largest_upperset_above(max_r))
 
     def solve_dp_FixResMaxFun_DPSeries(
         self, dp: DPSeries, query: FixResMaxFunQuery[object]
     ) -> Interval[LowerSet[object]]:
         # Hint: same as above, but go the other way...
-        raise NotImplementedError
+
+        def chain_naive(queries, dp):
+            ls_fun = [self.solve_dp_FixResMaxFun(dp, query)
+                      for query in queries]
+
+            optimistic = (FixResMaxFunQuery(resources=f)
+                          for ls_f in ls_fun
+                          for f in ls_f.optimistic.maximals)
+
+            pessimistic = (FixResMaxFunQuery(resources=f)
+                           for ls_f in ls_fun
+                           for f in ls_f.pessimistic.maximals)
+
+            return itertools.chain(optimistic, pessimistic)
+
+        queries = list(reduce(chain_naive, reversed(dp.subs), (query,)))
+        
+        if not queries:
+            return Interval.degenerate(LowerSet.empty())
+
+        max_f = queries[0].resources
+        min_f = queries[0].resources
+
+        for query in queries:
+            f = query.resources
+            if f < min_f:
+                min_f = f
+
+            if f > max_f:
+                max_f = f
+
+        return Interval(optimistic=dp.F.largest_lowerset_below(max_f),
+                        pessimistic=dp.F.largest_lowerset_below(min_f))
 
     # walkthrough: add a constant to functionalities ( f + constant <= r)
 
@@ -297,7 +404,12 @@ class DPSolver(DPSolverInterface):
     ) -> Interval[UpperSet[Decimal]]:
         # f <= r + constant
         # This is dual to the M_Res_AddConstant_DP case above.
-        raise NotImplementedError
+
+        f = query.functionality
+        min_r = f - dp.vu.value
+        us = dp.R.largest_upperset_above(min_r)
+
+        return Interval.degenerate(us)
 
     def solve_dp_FixResMaxFun_M_Fun_AddConstant_DP(
         self, dp: M_Fun_AddConstant_DP, query: FixResMaxFunQuery[Decimal]
@@ -305,7 +417,11 @@ class DPSolver(DPSolverInterface):
         # f <= r + constant
         # This is dual to the M_Res_AddConstant_DP case above.
 
-        raise NotImplementedError
+        r = query.resources
+        max_f = r + dp.vu.value
+        ls = dp.F.largest_lowerset_below(max_f)
+
+        return Interval.degenerate(ls)
 
     # walkthrough: multiplying constants (f * constant <= r)
     def solve_dp_FixFunMinRes_M_Res_MultiplyConstant_DP(
@@ -332,19 +448,33 @@ class DPSolver(DPSolverInterface):
     ) -> Interval[LowerSet[Decimal]]:
         #  (f * constant <= r)
 
-        raise NotImplementedError
+        r = query.resources
+        max_f = r / dp.vu.value
+        ls = dp.F.largest_lowerset_below(max_f)
+
+        return Interval.degenerate(ls)
 
     # exercise: multiply by constant (f  <= r * constant)
 
     def solve_dp_FixFunMinRes_M_Fun_MultiplyConstant_DP(
         self, dp: M_Fun_MultiplyConstant_DP, query: FixFunMinResQuery[Decimal]
     ) -> Interval[UpperSet[Decimal]]:
-        raise NotImplementedError
+
+        f = query.functionality
+        min_r = f / dp.vu.value
+        us = dp.R.largest_upperset_above(min_r)
+
+        return Interval.degenerate(us)
 
     def solve_dp_FixResMaxFun_M_Fun_MultiplyConstant_DP(
         self, dp: M_Fun_MultiplyConstant_DP, query: FixResMaxFunQuery[Decimal]
     ) -> Interval[LowerSet[Decimal]]:
-        raise NotImplementedError
+
+        r = query.resources
+        max_f = r * dp.vu.value
+        ls = dp.F.largest_lowerset_below(max_f)
+
+        return Interval.degenerate(ls)
 
     # walktrough: multiply functionalities
 
@@ -370,8 +500,11 @@ class DPSolver(DPSolverInterface):
         # similar to the above
 
         # this is the easy direction
+        multiply = lambda acc, f: acc * f
+        fun = reduce(multiply, query.functionality, Decimal(1))
 
-        raise NotImplementedError
+        us = dp.R.largest_upperset_above(fun)
+        return Interval.degenerate(us)
 
     # walkthough: add many
 
@@ -399,12 +532,12 @@ class DPSolver(DPSolverInterface):
     def solve_dp_FixResMaxFun_M_Fun_AddMany_DP(
         self, dp: M_Fun_AddMany_DP, query: FixResMaxFunQuery[tuple[Decimal, ...]]
     ) -> Interval[LowerSet[Decimal]]:
-        # this is a relation of the type
-        #  (f1 ≤  r) and (f2 ≤ r) and (f3 ≤ r) and ...
 
-        # This direction is easy, we just add the resources
+        add = lambda acc, r: acc + r
+        res = reduce(add, query.resources, Decimal(0))
 
-        raise NotImplementedError
+        ls = dp.F.largest_lowerset_below(res)
+        return Interval.degenerate(ls)
 
     # exercise: meet
 
@@ -426,7 +559,13 @@ class DPSolver(DPSolverInterface):
     def solve_dp_FixResMaxFun_MeetNDualDP(
         self, dp: MeetNDualDP[X], query: FixResMaxFunQuery[X]
     ) -> Interval[LowerSet[tuple[X, ...]]]:
-        raise NotImplementedError
+
+        max_f = dp.opspace.meet(query.resources)
+        if max_f is None:
+            return Interval.degenerate(LowerSet.empty())
+
+        ls = dp.F.largest_lowerset_below(max_f)
+        return Interval.degenerate(ls)
 
     # exercise: join
 
@@ -441,14 +580,20 @@ class DPSolver(DPSolverInterface):
         f = query.functionality
         min_r: Optional[X] = dp.opspace.join(f)
         if min_r is None:
-            raise NotImplementedError("TODO: join")
+            return Interval.degenerate(UpperSet.empty())
+
         us: UpperSet[X] = dp.R.largest_upperset_above(min_r)
         return Interval.degenerate(us)
 
     def solve_dp_FixResMaxFun_JoinNDP(
         self, dp: JoinNDP[X], query: FixResMaxFunQuery[X]
     ) -> Interval[LowerSet[tuple[X, ...]]]:
-        raise NotImplementedError
+
+        r = query.resources
+        max_f = (r,) * len(dp.F.subs)
+
+        ls = dp.F.largest_lowerset_below(max_f)
+        return Interval.degenerate(ls)
 
     # The above are sufficient for lib1
     #
@@ -466,7 +611,11 @@ class DPSolver(DPSolverInterface):
         # f/c <= r
 
         # Similar to a case above
-        raise NotImplementedError
+        r = query.resources
+        max_f = r * dp.vu.value
+        ls = dp.F.largest_lowerset_below(max_f)
+
+        return Interval.degenerate(ls)
 
     def solve_dp_FixFunMinRes_M_Res_DivideConstant_DP(
         self, dp: M_Res_DivideConstant_DP, query: FixFunMinResQuery[Decimal]
@@ -474,7 +623,11 @@ class DPSolver(DPSolverInterface):
         # f/c <= r
 
         # Similar to a case above
-        raise NotImplementedError
+        f = query.functionality
+        min_r = r / dp.vu.value
+        us = dp.R.largest_upperset_above(min_r)
+
+        return Interval.degenerate(us)
 
     # Exercise: parallel interconnection
 
@@ -499,15 +652,35 @@ class DPSolver(DPSolverInterface):
         # The product of upper sets is the upper set of the cartesian product
         # and it is implemented as UpperSet.product().
 
-        raise NotImplementedError
+        queries = (FixFunMinResQuery(functionality=f)
+                   for f in query.functionality)
+
+        min_res = [self.solve_dp_FixFunMinRes(dp, query)
+                   for dp, query in zip(dp.subs, queries)]
+
+        optimistic = lambda res: res.optimistic
+        pessimistic = lambda res: res.pessimistic
+
+        return Interval(optimistic=UpperSet.product(map(optimistic, min_res)),
+                        pessimistic=UpperSet.product(map(pessimistic, min_res)))
 
     def solve_dp_FixResMaxFun_ParallelDP(
         self, dp: ParallelDP[FT, RT], query: FixResMaxFunQuery[tuple[RT, ...]]
     ) -> Interval[LowerSet[FT]]:
         # Hint: same as above, swapping functionalities and resources
 
+        queries = (FixResMaxFunQuery(resources=r)
+                   for r in query.resources)
+
+        max_fun = [self.solve_dp_FixResMaxFun(dp, query)
+                   for dp, query in zip(dp.subs, queries)]
+
+        optimistic = lambda fun: fun.optimistic
+        pessimistic = lambda fun: fun.pessimistic
+
         # You will need to use LowerSet.product()
-        raise NotImplementedError
+        return Interval(optimistic=LowerSet.product(map(optimistic, max_fun)),
+                        pessimistic=LowerSet.product(map(pessimistic, max_fun)))
 
     # exercise (advanced): loops!