prompt: You will be provided with a partial code base and an issue statement explaining a problem to resolve.
  <issue>
  Pareto set: hypervolume
  As a user, I want functionality available to calculate the hypervolume of a Pareto front given the cell bounds, so that I can easily find the hypervolume when defining multi-objective acquisition functionality
  
  </issue>
  <code>
  [start of trieste/utils/pareto.py]
  1 # Copyright 2020 The Trieste Contributors
  2 #
  3 # Licensed under the Apache License, Version 2.0 (the "License");
  4 # you may not use this file except in compliance with the License.
  5 # You may obtain a copy of the License at
  6 #
  7 #     http://www.apache.org/licenses/LICENSE-2.0
  8 #
  9 # Unless required by applicable law or agreed to in writing, software
  10 # distributed under the License is distributed on an "AS IS" BASIS,
  11 # WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  12 # See the License for the specific language governing permissions and
  13 # limitations under the License.
  14 """ This module contains functions and classes for Pareto based multi-objective optimization. """
  15 
  16 from typing import Tuple
  17 
  18 import tensorflow as tf
  19 from typing_extensions import Final
  20 
  21 from ..type import TensorType
  22 
  23 
  24 def non_dominated(observations: TensorType) -> Tuple[TensorType, TensorType]:
  25     """
  26     Computes the non-dominated set for a set of data points.
  27     if there are duplicate point(s) in the non-dominated set, this function will return
  28     as it is without removing the duplicate.
  29 
  30     :param observations: set of points with shape [N,D]
  31     :return: tf.Tensor of the non-dominated set [P,D] and the degree of dominance [N],
  32         P is the number of points in pareto front
  33         dominances gives the number of dominating points for each data point
  34 
  35 
  36     """
  37     extended = tf.tile(observations[None], [len(observations), 1, 1])
  38     swapped_ext = tf.transpose(extended, [1, 0, 2])
  39     dominance = tf.math.count_nonzero(
  40         tf.logical_and(
  41             tf.reduce_all(extended <= swapped_ext, axis=2),
  42             tf.reduce_any(extended < swapped_ext, axis=2),
  43         ),
  44         axis=1,
  45     )
  46 
  47     return tf.boolean_mask(observations, dominance == 0), dominance
  48 
  49 
  50 class BoundedVolumes:
  51     """
  52     A :class:`BoundedVolumes` store the index of the Pareto front to form lower and upper
  53     bounds of the pseudo cells decomposition.
  54     """
  55 
  56     def __init__(self, lower_idx: tf.Tensor, upper_idx: tf.Tensor):
  57         """
  58         Construct bounded volumes.
  59 
  60         :param lower_idx: the lowerbounds index of the volumes
  61         :param upper_idx: the upperbounds index of the volumes
  62         """
  63 
  64         tf.debugging.assert_shapes([(lower_idx, ["N", "D"]), (upper_idx, ["N", "D"])])
  65         self.lower_idx: Final[TensorType] = lower_idx
  66         self.upper_idx: Final[TensorType] = upper_idx
  67 
  68 
  69 class Pareto:
  70     """
  71     A :class:`Pareto` Construct a Pareto set.
  72     Stores a Pareto set and calculates the cell bounds covering the non-dominated region.
  73     The latter is needed for certain multiobjective acquisition functions.
  74     """
  75 
  76     def __init__(self, observations: TensorType):
  77         """
  78         :param observations: The observations for all objectives, with shape [N, 2].
  79         :raise ValueError (or InvalidArgumentError): If ``observations`` has an invalid shape.
  80         """
  81         tf.debugging.assert_shapes([(observations, [None, 2])])
  82 
  83         pf, _ = non_dominated(observations)
  84         self.front: Final[TensorType] = tf.gather_nd(pf, tf.argsort(pf[:, :1], axis=0))
  85         self.bounds: Final[BoundedVolumes] = self._bounds_2d(self.front)
  86 
  87     @staticmethod
  88     def _bounds_2d(front: TensorType) -> BoundedVolumes:
  89 
  90         # this assumes the Pareto set has been sorted in ascending order on the first
  91         # objective, which implies the second objective is sorted in descending order
  92         len_front, number_of_objectives = front.shape
  93 
  94         pf_ext_idx = tf.concat(
  95             [
  96                 tf.zeros([1, number_of_objectives], dtype=tf.int32),
  97                 tf.argsort(front, axis=0) + 1,
  98                 tf.ones([1, number_of_objectives], dtype=tf.int32) * len_front + 1,
  99             ],
  100             axis=0,
  101         )
  102 
  103         range_ = tf.range(len_front + 1)[:, None]
  104         lower = tf.concat([range_, tf.zeros_like(range_)], axis=-1)
  105         upper = tf.concat([range_ + 1, pf_ext_idx[::-1, 1:][: pf_ext_idx[-1, 0]]], axis=-1)
  106 
  107         return BoundedVolumes(lower, upper)
  108
  [end of trieste/utils/pareto.py]
  </code>
  
  I need you to solve this issue by generating a single patch file that I can apply directly to this repository using git apply. Please respond with a single patch file in the following format.
  <patch>
  diff --git a/file.py b/file.py
  --- a/file.py
  +++ b/file.py
  @@ -1,27 +1,35 @@
   def euclidean(a, b):
  -    while b:
  -        a, b = b, a % b
  -    return a
  +    if b == 0:
  +        return a
  +    return euclidean(b, a % b)
   
   
   def bresenham(x0, y0, x1, y1):
       points = []
       dx = abs(x1 - x0)
       dy = abs(y1 - y0)
  -    sx = 1 if x0 < x1 else -1
  -    sy = 1 if y0 < y1 else -1
  -    err = dx - dy
  +    x, y = x0, y0
  +    sx = -1 if x0 > x1 else 1
  +    sy = -1 if y0 > y1 else 1
   
  -    while True:
  -        points.append((x0, y0))
  -        if x0 == x1 and y0 == y1:
  -            break
  -        e2 = 2 * err
  -        if e2 > -dy:
  -            err -= dy
  -            x0 += sx
  -        if e2 < dx:
  -            err += dx
  -            y0 += sy
  +    if dx > dy:
  +        err = dx / 2.0
  +        while x != x1:
  +            points.append((x, y))
  +            err -= dy
  +            if err < 0:
  +                y += sy
  +                err += dx
  +            x += sx
  +    else:
  +        err = dy / 2.0
  +        while y != y1:
  +            points.append((x, y))
  +            err -= dx
  +            if err < 0:
  +                x += sx
  +                err += dy
  +            y += sy
  +
  +    points.append((x, y))
       return points
  
  </patch>
golden_diff: diff --git a/trieste/utils/pareto.py b/trieste/utils/pareto.py
  --- a/trieste/utils/pareto.py
  +++ b/trieste/utils/pareto.py
  @@ -105,3 +105,46 @@
           upper = tf.concat([range_ + 1, pf_ext_idx[::-1, 1:][: pf_ext_idx[-1, 0]]], axis=-1)
   
           return BoundedVolumes(lower, upper)
  +
  +    def hypervolume_indicator(self, reference: TensorType) -> TensorType:
  +        """
  +        Calculate the hypervolume indicator
  +        The hypervolume indicator is the volume of the dominated region.
  +
  +        :param reference: a reference point to use, with shape [D].
  +            Defines the upper bound of the hypervolume.
  +            Should be equal or bigger than the anti-ideal point of the Pareto set.
  +            For comparing results across runs, the same reference point must be used.
  +        :return: hypervolume indicator
  +        :raise ValueError (or `tf.errors.InvalidArgumentError`): If ``reference`` has an invalid
  +            shape.
  +        :raise `tf.errors.InvalidArgumentError`: If ``reference`` is less than the anti-ideal point
  +            in any dimension.
  +        """
  +        tf.debugging.assert_greater_equal(reference, self.front)
  +
  +        tf.debugging.assert_shapes(
  +            [
  +                (self.bounds.lower_idx, ["N", "D"]),
  +                (self.bounds.upper_idx, ["N", "D"]),
  +                (self.front, ["M", "D"]),
  +                (reference, ["D"]),
  +            ]
  +        )
  +
  +        min_pfront = tf.reduce_min(self.front, 0, keepdims=True)
  +        pseudo_pfront = tf.concat((min_pfront, self.front, reference[None]), 0)
  +        N, D = tf.shape(self.bounds.upper_idx)
  +
  +        idx = tf.tile(tf.expand_dims(tf.range(D), -1), [1, N])
  +        upper_idx = tf.reshape(
  +            tf.stack([tf.transpose(self.bounds.upper_idx), idx], axis=2), [N * D, 2]
  +        )
  +        lower_idx = tf.reshape(
  +            tf.stack([tf.transpose(self.bounds.lower_idx), idx], axis=2), [N * D, 2]
  +        )
  +        upper = tf.reshape(tf.gather_nd(pseudo_pfront, upper_idx), [D, N])
  +        lower = tf.reshape(tf.gather_nd(pseudo_pfront, lower_idx), [D, N])
  +        hypervolume = tf.reduce_sum(tf.reduce_prod(upper - lower, 0))
  +
  +        return tf.reduce_prod(reference[None] - min_pfront) - hypervolume
  
verification_info: {"golden_diff": "diff --git a/trieste/utils/pareto.py b/trieste/utils/pareto.py\n--- a/trieste/utils/pareto.py\n+++ b/trieste/utils/pareto.py\n@@ -105,3 +105,46 @@\n         upper = tf.concat([range_ + 1, pf_ext_idx[::-1, 1:][: pf_ext_idx[-1, 0]]], axis=-1)\n \n         return BoundedVolumes(lower, upper)\n+\n+    def hypervolume_indicator(self, reference: TensorType) -> TensorType:\n+        \"\"\"\n+        Calculate the hypervolume indicator\n+        The hypervolume indicator is the volume of the dominated region.\n+\n+        :param reference: a reference point to use, with shape [D].\n+            Defines the upper bound of the hypervolume.\n+            Should be equal or bigger than the anti-ideal point of the Pareto set.\n+            For comparing results across runs, the same reference point must be used.\n+        :return: hypervolume indicator\n+        :raise ValueError (or `tf.errors.InvalidArgumentError`): If ``reference`` has an invalid\n+            shape.\n+        :raise `tf.errors.InvalidArgumentError`: If ``reference`` is less than the anti-ideal point\n+            in any dimension.\n+        \"\"\"\n+        tf.debugging.assert_greater_equal(reference, self.front)\n+\n+        tf.debugging.assert_shapes(\n+            [\n+                (self.bounds.lower_idx, [\"N\", \"D\"]),\n+                (self.bounds.upper_idx, [\"N\", \"D\"]),\n+                (self.front, [\"M\", \"D\"]),\n+                (reference, [\"D\"]),\n+            ]\n+        )\n+\n+        min_pfront = tf.reduce_min(self.front, 0, keepdims=True)\n+        pseudo_pfront = tf.concat((min_pfront, self.front, reference[None]), 0)\n+        N, D = tf.shape(self.bounds.upper_idx)\n+\n+        idx = tf.tile(tf.expand_dims(tf.range(D), -1), [1, N])\n+        upper_idx = tf.reshape(\n+            tf.stack([tf.transpose(self.bounds.upper_idx), idx], axis=2), [N * D, 2]\n+        )\n+        lower_idx = tf.reshape(\n+            tf.stack([tf.transpose(self.bounds.lower_idx), idx], axis=2), [N * D, 2]\n+        )\n+        upper = tf.reshape(tf.gather_nd(pseudo_pfront, upper_idx), [D, N])\n+        lower = tf.reshape(tf.gather_nd(pseudo_pfront, lower_idx), [D, N])\n+        hypervolume = tf.reduce_sum(tf.reduce_prod(upper - lower, 0))\n+\n+        return tf.reduce_prod(reference[None] - min_pfront) - hypervolume\n", "issue": "Pareto set: hypervolume\nAs a user, I want functionality available to calculate the hypervolume of a Pareto front given the cell bounds, so that I can easily find the hypervolume when defining multi-objective acquisition functionality\n", "before_files": [{"content": "# Copyright 2020 The Trieste Contributors\n#\n# Licensed under the Apache License, Version 2.0 (the \"License\");\n# you may not use this file except in compliance with the License.\n# You may obtain a copy of the License at\n#\n#     http://www.apache.org/licenses/LICENSE-2.0\n#\n# Unless required by applicable law or agreed to in writing, software\n# distributed under the License is distributed on an \"AS IS\" BASIS,\n# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.\n# See the License for the specific language governing permissions and\n# limitations under the License.\n\"\"\" This module contains functions and classes for Pareto based multi-objective optimization. \"\"\"\n\nfrom typing import Tuple\n\nimport tensorflow as tf\nfrom typing_extensions import Final\n\nfrom ..type import TensorType\n\n\ndef non_dominated(observations: TensorType) -> Tuple[TensorType, TensorType]:\n    \"\"\"\n    Computes the non-dominated set for a set of data points.\n    if there are duplicate point(s) in the non-dominated set, this function will return\n    as it is without removing the duplicate.\n\n    :param observations: set of points with shape [N,D]\n    :return: tf.Tensor of the non-dominated set [P,D] and the degree of dominance [N],\n        P is the number of points in pareto front\n        dominances gives the number of dominating points for each data point\n\n\n    \"\"\"\n    extended = tf.tile(observations[None], [len(observations), 1, 1])\n    swapped_ext = tf.transpose(extended, [1, 0, 2])\n    dominance = tf.math.count_nonzero(\n        tf.logical_and(\n            tf.reduce_all(extended <= swapped_ext, axis=2),\n            tf.reduce_any(extended < swapped_ext, axis=2),\n        ),\n        axis=1,\n    )\n\n    return tf.boolean_mask(observations, dominance == 0), dominance\n\n\nclass BoundedVolumes:\n    \"\"\"\n    A :class:`BoundedVolumes` store the index of the Pareto front to form lower and upper\n    bounds of the pseudo cells decomposition.\n    \"\"\"\n\n    def __init__(self, lower_idx: tf.Tensor, upper_idx: tf.Tensor):\n        \"\"\"\n        Construct bounded volumes.\n\n        :param lower_idx: the lowerbounds index of the volumes\n        :param upper_idx: the upperbounds index of the volumes\n        \"\"\"\n\n        tf.debugging.assert_shapes([(lower_idx, [\"N\", \"D\"]), (upper_idx, [\"N\", \"D\"])])\n        self.lower_idx: Final[TensorType] = lower_idx\n        self.upper_idx: Final[TensorType] = upper_idx\n\n\nclass Pareto:\n    \"\"\"\n    A :class:`Pareto` Construct a Pareto set.\n    Stores a Pareto set and calculates the cell bounds covering the non-dominated region.\n    The latter is needed for certain multiobjective acquisition functions.\n    \"\"\"\n\n    def __init__(self, observations: TensorType):\n        \"\"\"\n        :param observations: The observations for all objectives, with shape [N, 2].\n        :raise ValueError (or InvalidArgumentError): If ``observations`` has an invalid shape.\n        \"\"\"\n        tf.debugging.assert_shapes([(observations, [None, 2])])\n\n        pf, _ = non_dominated(observations)\n        self.front: Final[TensorType] = tf.gather_nd(pf, tf.argsort(pf[:, :1], axis=0))\n        self.bounds: Final[BoundedVolumes] = self._bounds_2d(self.front)\n\n    @staticmethod\n    def _bounds_2d(front: TensorType) -> BoundedVolumes:\n\n        # this assumes the Pareto set has been sorted in ascending order on the first\n        # objective, which implies the second objective is sorted in descending order\n        len_front, number_of_objectives = front.shape\n\n        pf_ext_idx = tf.concat(\n            [\n                tf.zeros([1, number_of_objectives], dtype=tf.int32),\n                tf.argsort(front, axis=0) + 1,\n                tf.ones([1, number_of_objectives], dtype=tf.int32) * len_front + 1,\n            ],\n            axis=0,\n        )\n\n        range_ = tf.range(len_front + 1)[:, None]\n        lower = tf.concat([range_, tf.zeros_like(range_)], axis=-1)\n        upper = tf.concat([range_ + 1, pf_ext_idx[::-1, 1:][: pf_ext_idx[-1, 0]]], axis=-1)\n\n        return BoundedVolumes(lower, upper)\n", "path": "trieste/utils/pareto.py"}]}