prompt: You will be provided with a partial code base and an issue statement explaining a problem to resolve.
  <issue>
  Automatic computation of zoom levels for rio overwiew
  Since GDAL 2.3 in gdaladdo it is [possible](https://www.gdal.org/gdaladdo.html) to omit the list of overview factors. But it looks like `rio overwiew` doesn't support this.
  
  </issue>
  <code>
  [start of rasterio/rio/overview.py]
  1 # coding: utf-8
  2 """Manage overviews of a dataset."""
  3 
  4 from functools import reduce
  5 import logging
  6 import operator
  7 
  8 import click
  9 
  10 from . import options
  11 import rasterio
  12 from rasterio.enums import Resampling
  13 
  14 
  15 def build_handler(ctx, param, value):
  16     if value:
  17         try:
  18             if '^' in value:
  19                 base, exp_range = value.split('^')
  20                 exp_min, exp_max = (int(v) for v in exp_range.split('..'))
  21                 value = [pow(int(base), k) for k in range(exp_min, exp_max + 1)]
  22             else:
  23                 value = [int(v) for v in value.split(',')]
  24         except Exception:
  25             raise click.BadParameter(u"must match 'n,n,n,…' or 'n^n..n'.")
  26     return value
  27 
  28 
  29 @click.command('overview', short_help="Construct overviews in an existing dataset.")
  30 @options.file_in_arg
  31 @click.option('--build', callback=build_handler, metavar=u"f1,f2,…|b^min..max",
  32               help="A sequence of decimation factors specied as "
  33                    "comma-separated list of numbers or a base and range of "
  34                    "exponents.")
  35 @click.option('--ls', help="Print the overviews for each band.",
  36               is_flag=True, default=False)
  37 @click.option('--rebuild', help="Reconstruct existing overviews.",
  38               is_flag=True, default=False)
  39 @click.option('--resampling', help="Resampling algorithm.",
  40               type=click.Choice(
  41                   [it.name for it in Resampling if it.value in [0, 1, 2, 3, 4, 5, 6, 7]]),
  42               default='nearest', show_default=True)
  43 @click.pass_context
  44 def overview(ctx, input, build, ls, rebuild, resampling):
  45     """Construct overviews in an existing dataset.
  46 
  47     A pyramid of overviews computed once and stored in the dataset can
  48     improve performance in some applications.
  49 
  50     The decimation levels at which to build overviews can be specified as
  51     a comma separated list
  52 
  53       rio overview --build 2,4,8,16
  54 
  55     or a base and range of exponents.
  56 
  57       rio overview --build 2^1..4
  58 
  59     Note that overviews can not currently be removed and are not
  60     automatically updated when the dataset's primary bands are
  61     modified.
  62 
  63     Information about existing overviews can be printed using the --ls
  64     option.
  65 
  66       rio overview --ls
  67 
  68     """
  69     with ctx.obj['env']:
  70         if ls:
  71             with rasterio.open(input, 'r') as dst:
  72                 resampling_method = dst.tags(
  73                     ns='rio_overview').get('resampling') or 'unknown'
  74 
  75                 click.echo("Overview factors:")
  76                 for idx in dst.indexes:
  77                     click.echo("  Band %d: %s (method: '%s')" % (
  78                         idx, dst.overviews(idx) or 'None', resampling_method))
  79         elif rebuild:
  80             with rasterio.open(input, 'r+') as dst:
  81                 # Build the same overviews for all bands.
  82                 factors = reduce(
  83                     operator.or_,
  84                     [set(dst.overviews(i)) for i in dst.indexes])
  85 
  86                 # Attempt to recover the resampling method from dataset tags.
  87                 resampling_method = dst.tags(
  88                     ns='rio_overview').get('resampling') or resampling
  89 
  90                 dst.build_overviews(
  91                     list(factors), Resampling[resampling_method])
  92 
  93         elif build:
  94             with rasterio.open(input, 'r+') as dst:
  95                 dst.build_overviews(build, Resampling[resampling])
  96 
  97                 # Save the resampling method to a tag.
  98                 dst.update_tags(ns='rio_overview', resampling=resampling)
  99 
  100         else:
  101             raise click.UsageError(
  102                 "Please specify --ls, --rebuild, or --build ...")
  103
  [end of rasterio/rio/overview.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/rasterio/rio/overview.py b/rasterio/rio/overview.py
  --- a/rasterio/rio/overview.py
  +++ b/rasterio/rio/overview.py
  @@ -19,19 +19,52 @@
                   base, exp_range = value.split('^')
                   exp_min, exp_max = (int(v) for v in exp_range.split('..'))
                   value = [pow(int(base), k) for k in range(exp_min, exp_max + 1)]
  -            else:
  +            elif ',' in value:
                   value = [int(v) for v in value.split(',')]
  +            elif value == "auto":
  +                pass
  +            else:
  +                raise Exception
           except Exception:
  -            raise click.BadParameter(u"must match 'n,n,n,…' or 'n^n..n'.")
  +            raise click.BadParameter(u"must match 'n,n,n,…', 'n^n..n', or 'auto'.")
       return value
   
   
  +def get_maximum_overview_level(width, height, minsize=256):
  +    """
  +    Calculate the maximum overview level of a dataset at which
  +    the smallest overview is smaller than `minsize`.
  +
  +    Attributes
  +    ----------
  +    width : int
  +        Width of the dataset.
  +    height : int
  +        Height of the dataset.
  +    minsize : int (default: 256)
  +        Minimum overview size.
  +
  +    Returns
  +    -------
  +    overview_level: int
  +        overview level.
  +
  +    """
  +    overview_level = 0
  +    overview_factor = 1
  +    while min(width // overview_factor, height // overview_factor) > minsize:
  +        overview_factor *= 2
  +        overview_level += 1
  +
  +    return overview_level
  +
  +
   @click.command('overview', short_help="Construct overviews in an existing dataset.")
   @options.file_in_arg
  -@click.option('--build', callback=build_handler, metavar=u"f1,f2,…|b^min..max",
  -              help="A sequence of decimation factors specied as "
  +@click.option('--build', callback=build_handler, metavar=u"f1,f2,…|b^min..max|auto",
  +              help="A sequence of decimation factors specified as "
                      "comma-separated list of numbers or a base and range of "
  -                   "exponents.")
  +                   "exponents, or 'auto' to automatically determine the maximum factor.")
   @click.option('--ls', help="Print the overviews for each band.",
                 is_flag=True, default=False)
   @click.option('--rebuild', help="Reconstruct existing overviews.",
  @@ -52,10 +85,15 @@
   
         rio overview --build 2,4,8,16
   
  -    or a base and range of exponents.
  +    or a base and range of exponents
   
         rio overview --build 2^1..4
   
  +    or 'auto' to automatically determine the maximum decimation level at
  +    which the smallest overview is smaller than 256 pixels in size.
  +
  +      rio overview --build auto
  +
       Note that overviews can not currently be removed and are not
       automatically updated when the dataset's primary bands are
       modified.
  @@ -92,6 +130,9 @@
   
           elif build:
               with rasterio.open(input, 'r+') as dst:
  +                if build == "auto":
  +                    overview_level = get_maximum_overview_level(dst.width, dst.height)
  +                    build = [2 ** j for j in range(1, overview_level + 1)]
                   dst.build_overviews(build, Resampling[resampling])
   
                   # Save the resampling method to a tag.
  
verification_info: {"golden_diff": "diff --git a/rasterio/rio/overview.py b/rasterio/rio/overview.py\n--- a/rasterio/rio/overview.py\n+++ b/rasterio/rio/overview.py\n@@ -19,19 +19,52 @@\n                 base, exp_range = value.split('^')\n                 exp_min, exp_max = (int(v) for v in exp_range.split('..'))\n                 value = [pow(int(base), k) for k in range(exp_min, exp_max + 1)]\n-            else:\n+            elif ',' in value:\n                 value = [int(v) for v in value.split(',')]\n+            elif value == \"auto\":\n+                pass\n+            else:\n+                raise Exception\n         except Exception:\n-            raise click.BadParameter(u\"must match 'n,n,n,\u2026' or 'n^n..n'.\")\n+            raise click.BadParameter(u\"must match 'n,n,n,\u2026', 'n^n..n', or 'auto'.\")\n     return value\n \n \n+def get_maximum_overview_level(width, height, minsize=256):\n+    \"\"\"\n+    Calculate the maximum overview level of a dataset at which\n+    the smallest overview is smaller than `minsize`.\n+\n+    Attributes\n+    ----------\n+    width : int\n+        Width of the dataset.\n+    height : int\n+        Height of the dataset.\n+    minsize : int (default: 256)\n+        Minimum overview size.\n+\n+    Returns\n+    -------\n+    overview_level: int\n+        overview level.\n+\n+    \"\"\"\n+    overview_level = 0\n+    overview_factor = 1\n+    while min(width // overview_factor, height // overview_factor) > minsize:\n+        overview_factor *= 2\n+        overview_level += 1\n+\n+    return overview_level\n+\n+\n @click.command('overview', short_help=\"Construct overviews in an existing dataset.\")\n @options.file_in_arg\n-@click.option('--build', callback=build_handler, metavar=u\"f1,f2,\u2026|b^min..max\",\n-              help=\"A sequence of decimation factors specied as \"\n+@click.option('--build', callback=build_handler, metavar=u\"f1,f2,\u2026|b^min..max|auto\",\n+              help=\"A sequence of decimation factors specified as \"\n                    \"comma-separated list of numbers or a base and range of \"\n-                   \"exponents.\")\n+                   \"exponents, or 'auto' to automatically determine the maximum factor.\")\n @click.option('--ls', help=\"Print the overviews for each band.\",\n               is_flag=True, default=False)\n @click.option('--rebuild', help=\"Reconstruct existing overviews.\",\n@@ -52,10 +85,15 @@\n \n       rio overview --build 2,4,8,16\n \n-    or a base and range of exponents.\n+    or a base and range of exponents\n \n       rio overview --build 2^1..4\n \n+    or 'auto' to automatically determine the maximum decimation level at\n+    which the smallest overview is smaller than 256 pixels in size.\n+\n+      rio overview --build auto\n+\n     Note that overviews can not currently be removed and are not\n     automatically updated when the dataset's primary bands are\n     modified.\n@@ -92,6 +130,9 @@\n \n         elif build:\n             with rasterio.open(input, 'r+') as dst:\n+                if build == \"auto\":\n+                    overview_level = get_maximum_overview_level(dst.width, dst.height)\n+                    build = [2 ** j for j in range(1, overview_level + 1)]\n                 dst.build_overviews(build, Resampling[resampling])\n \n                 # Save the resampling method to a tag.\n", "issue": "Automatic computation of zoom levels for rio overwiew\nSince GDAL 2.3 in gdaladdo it is [possible](https://www.gdal.org/gdaladdo.html) to omit the list of overview factors. But it looks like `rio overwiew` doesn't support this.\n", "before_files": [{"content": "# coding: utf-8\n\"\"\"Manage overviews of a dataset.\"\"\"\n\nfrom functools import reduce\nimport logging\nimport operator\n\nimport click\n\nfrom . import options\nimport rasterio\nfrom rasterio.enums import Resampling\n\n\ndef build_handler(ctx, param, value):\n    if value:\n        try:\n            if '^' in value:\n                base, exp_range = value.split('^')\n                exp_min, exp_max = (int(v) for v in exp_range.split('..'))\n                value = [pow(int(base), k) for k in range(exp_min, exp_max + 1)]\n            else:\n                value = [int(v) for v in value.split(',')]\n        except Exception:\n            raise click.BadParameter(u\"must match 'n,n,n,\u2026' or 'n^n..n'.\")\n    return value\n\n\n@click.command('overview', short_help=\"Construct overviews in an existing dataset.\")\n@options.file_in_arg\n@click.option('--build', callback=build_handler, metavar=u\"f1,f2,\u2026|b^min..max\",\n              help=\"A sequence of decimation factors specied as \"\n                   \"comma-separated list of numbers or a base and range of \"\n                   \"exponents.\")\n@click.option('--ls', help=\"Print the overviews for each band.\",\n              is_flag=True, default=False)\n@click.option('--rebuild', help=\"Reconstruct existing overviews.\",\n              is_flag=True, default=False)\n@click.option('--resampling', help=\"Resampling algorithm.\",\n              type=click.Choice(\n                  [it.name for it in Resampling if it.value in [0, 1, 2, 3, 4, 5, 6, 7]]),\n              default='nearest', show_default=True)\n@click.pass_context\ndef overview(ctx, input, build, ls, rebuild, resampling):\n    \"\"\"Construct overviews in an existing dataset.\n\n    A pyramid of overviews computed once and stored in the dataset can\n    improve performance in some applications.\n\n    The decimation levels at which to build overviews can be specified as\n    a comma separated list\n\n      rio overview --build 2,4,8,16\n\n    or a base and range of exponents.\n\n      rio overview --build 2^1..4\n\n    Note that overviews can not currently be removed and are not\n    automatically updated when the dataset's primary bands are\n    modified.\n\n    Information about existing overviews can be printed using the --ls\n    option.\n\n      rio overview --ls\n\n    \"\"\"\n    with ctx.obj['env']:\n        if ls:\n            with rasterio.open(input, 'r') as dst:\n                resampling_method = dst.tags(\n                    ns='rio_overview').get('resampling') or 'unknown'\n\n                click.echo(\"Overview factors:\")\n                for idx in dst.indexes:\n                    click.echo(\"  Band %d: %s (method: '%s')\" % (\n                        idx, dst.overviews(idx) or 'None', resampling_method))\n        elif rebuild:\n            with rasterio.open(input, 'r+') as dst:\n                # Build the same overviews for all bands.\n                factors = reduce(\n                    operator.or_,\n                    [set(dst.overviews(i)) for i in dst.indexes])\n\n                # Attempt to recover the resampling method from dataset tags.\n                resampling_method = dst.tags(\n                    ns='rio_overview').get('resampling') or resampling\n\n                dst.build_overviews(\n                    list(factors), Resampling[resampling_method])\n\n        elif build:\n            with rasterio.open(input, 'r+') as dst:\n                dst.build_overviews(build, Resampling[resampling])\n\n                # Save the resampling method to a tag.\n                dst.update_tags(ns='rio_overview', resampling=resampling)\n\n        else:\n            raise click.UsageError(\n                \"Please specify --ls, --rebuild, or --build ...\")\n", "path": "rasterio/rio/overview.py"}]}