prompt: You will be provided with a partial code base and an issue statement explaining a problem to resolve.
  <issue>
  shapely hook doesn't work on windows
  Using current develop, the shapely hook fails when it runs `binaries += [(os.path.join(lib_dir, f), '') for f in os.listdir(lib_dir)]`. `lib_dir` here equals `Lib/site-packages/shapely/DLLs`. The actual directory on my conda python 3.6 installation is `Library/bin/`. My old spec file uses the following ugly code to copy these libraries over:
  
  ```
      lib_dir = sys.executable.replace("python.exe", os.path.join("Library", "bin"))
      binaries += [(os.path.join(lib_dir, 'geos_c.dll'), '')]
      binaries += [(os.path.join(lib_dir, 'geos.dll'), '')]
      binaries += [(os.path.join(lib_dir, 'mkl_*.dll'), '')]
  ```
  
  Is there a better way to get a hold of this Library directory with some pyinstaller utility function? Does anyone know if other python environments (non-conda) have the directory used in the hook or @durden did you just guess on the Windows path?
  
  Side issue: Shapely 1.6+ doesn't seem to work on at least windows (haven't updated on other platforms). It fails to find the geos libraries mentioned above unless you execute the pyinstaller-made (inno setup packaged) executable from the install directory (`C:\Program Files (x86)\myprgm\bin\`). For now I'm just downgrading to 1.5.17.
  shapely hook doesn't work on windows
  Using current develop, the shapely hook fails when it runs `binaries += [(os.path.join(lib_dir, f), '') for f in os.listdir(lib_dir)]`. `lib_dir` here equals `Lib/site-packages/shapely/DLLs`. The actual directory on my conda python 3.6 installation is `Library/bin/`. My old spec file uses the following ugly code to copy these libraries over:
  
  ```
      lib_dir = sys.executable.replace("python.exe", os.path.join("Library", "bin"))
      binaries += [(os.path.join(lib_dir, 'geos_c.dll'), '')]
      binaries += [(os.path.join(lib_dir, 'geos.dll'), '')]
      binaries += [(os.path.join(lib_dir, 'mkl_*.dll'), '')]
  ```
  
  Is there a better way to get a hold of this Library directory with some pyinstaller utility function? Does anyone know if other python environments (non-conda) have the directory used in the hook or @durden did you just guess on the Windows path?
  
  Side issue: Shapely 1.6+ doesn't seem to work on at least windows (haven't updated on other platforms). It fails to find the geos libraries mentioned above unless you execute the pyinstaller-made (inno setup packaged) executable from the install directory (`C:\Program Files (x86)\myprgm\bin\`). For now I'm just downgrading to 1.5.17.
  
  </issue>
  <code>
  [start of PyInstaller/hooks/hook-shapely.py]
  1 #-----------------------------------------------------------------------------
  2 # Copyright (c) 2017-2020, PyInstaller Development Team.
  3 #
  4 # Distributed under the terms of the GNU General Public License (version 2
  5 # or later) with exception for distributing the bootloader.
  6 #
  7 # The full license is in the file COPYING.txt, distributed with this software.
  8 #
  9 # SPDX-License-Identifier: (GPL-2.0-or-later WITH Bootloader-exception)
  10 #-----------------------------------------------------------------------------
  11 
  12 import os
  13 
  14 from PyInstaller.utils.hooks import get_package_paths
  15 from PyInstaller.utils.hooks import is_module_satisfies
  16 from PyInstaller import compat
  17 
  18 # Necessary when using the vectorized subpackage
  19 hiddenimports = ['shapely.prepared']
  20 
  21 pkg_base, pkg_dir = get_package_paths('shapely')
  22 
  23 
  24 binaries = []
  25 if compat.is_win:
  26     if compat.is_conda:
  27         lib_dir = os.path.join(compat.base_prefix, 'Library', 'bin')
  28     else:
  29         lib_dir = os.path.join(pkg_dir, 'DLLs')
  30     dll_files = ['geos_c.dll', 'geos.dll']
  31     binaries += [(os.path.join(lib_dir, f), '.') for f in dll_files]
  32 elif compat.is_linux:
  33     lib_dir = os.path.join(pkg_dir, '.libs')
  34     dest_dir = os.path.join('shapely', '.libs')
  35 
  36     # This duplicates the libgeos*.so* files in the build.  PyInstaller will
  37     # copy them into the root of the build by default, but shapely cannot load
  38     # them from there in linux IF shapely was installed via a whl file. The
  39     # whl bundles its' own libgeos with a different name, something like
  40     # libgeos_c-*.so.* but shapely tries to load libgeos_c.so if there isn't a
  41     # ./libs directory under its' package. There is a proposed fix for this in
  42     # shapely but it has not been accepted it:
  43     # https://github.com/Toblerity/Shapely/pull/485
  44     if is_module_satisfies('shapely <= 1.6'):
  45         binaries += [(os.path.join(lib_dir, f), dest_dir) for f in os.listdir(lib_dir)]
  46
  [end of PyInstaller/hooks/hook-shapely.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/PyInstaller/hooks/hook-shapely.py b/PyInstaller/hooks/hook-shapely.py
  --- a/PyInstaller/hooks/hook-shapely.py
  +++ b/PyInstaller/hooks/hook-shapely.py
  @@ -10,6 +10,7 @@
   #-----------------------------------------------------------------------------
   
   import os
  +from ctypes.util import find_library
   
   from PyInstaller.utils.hooks import get_package_paths
   from PyInstaller.utils.hooks import is_module_satisfies
  @@ -23,12 +24,25 @@
   
   binaries = []
   if compat.is_win:
  +    # Search conda directory if conda is active, then search standard
  +    # directory. This is the same order of precidence used in shapely.
  +    standard_path = os.path.join(pkg_dir, 'DLLs')
  +    lib_paths = [standard_path, os.environ['PATH']]
       if compat.is_conda:
  -        lib_dir = os.path.join(compat.base_prefix, 'Library', 'bin')
  -    else:
  -        lib_dir = os.path.join(pkg_dir, 'DLLs')
  -    dll_files = ['geos_c.dll', 'geos.dll']
  -    binaries += [(os.path.join(lib_dir, f), '.') for f in dll_files]
  +        conda_path = os.path.join(compat.base_prefix, 'Library', 'bin')
  +        lib_paths.insert(0, conda_path)
  +    original_path = os.environ['PATH']
  +    try:
  +        os.environ['PATH'] = os.pathsep.join(lib_paths)
  +        dll_path = find_library('geos_c')
  +    finally:
  +        os.environ['PATH'] = original_path
  +    if dll_path is None:
  +        raise SystemExit(
  +            "Error: geos_c.dll not found, required by hook-shapely.py.\n"
  +            "Please check your installation or provide a pull request to "
  +            "PyInstaller to update hook-shapely.py.")
  +    binaries += [(dll_path, '.')]
   elif compat.is_linux:
       lib_dir = os.path.join(pkg_dir, '.libs')
       dest_dir = os.path.join('shapely', '.libs')
  
verification_info: {"golden_diff": "diff --git a/PyInstaller/hooks/hook-shapely.py b/PyInstaller/hooks/hook-shapely.py\n--- a/PyInstaller/hooks/hook-shapely.py\n+++ b/PyInstaller/hooks/hook-shapely.py\n@@ -10,6 +10,7 @@\n #-----------------------------------------------------------------------------\n \n import os\n+from ctypes.util import find_library\n \n from PyInstaller.utils.hooks import get_package_paths\n from PyInstaller.utils.hooks import is_module_satisfies\n@@ -23,12 +24,25 @@\n \n binaries = []\n if compat.is_win:\n+    # Search conda directory if conda is active, then search standard\n+    # directory. This is the same order of precidence used in shapely.\n+    standard_path = os.path.join(pkg_dir, 'DLLs')\n+    lib_paths = [standard_path, os.environ['PATH']]\n     if compat.is_conda:\n-        lib_dir = os.path.join(compat.base_prefix, 'Library', 'bin')\n-    else:\n-        lib_dir = os.path.join(pkg_dir, 'DLLs')\n-    dll_files = ['geos_c.dll', 'geos.dll']\n-    binaries += [(os.path.join(lib_dir, f), '.') for f in dll_files]\n+        conda_path = os.path.join(compat.base_prefix, 'Library', 'bin')\n+        lib_paths.insert(0, conda_path)\n+    original_path = os.environ['PATH']\n+    try:\n+        os.environ['PATH'] = os.pathsep.join(lib_paths)\n+        dll_path = find_library('geos_c')\n+    finally:\n+        os.environ['PATH'] = original_path\n+    if dll_path is None:\n+        raise SystemExit(\n+            \"Error: geos_c.dll not found, required by hook-shapely.py.\\n\"\n+            \"Please check your installation or provide a pull request to \"\n+            \"PyInstaller to update hook-shapely.py.\")\n+    binaries += [(dll_path, '.')]\n elif compat.is_linux:\n     lib_dir = os.path.join(pkg_dir, '.libs')\n     dest_dir = os.path.join('shapely', '.libs')\n", "issue": "shapely hook doesn't work on windows\nUsing current develop, the shapely hook fails when it runs `binaries += [(os.path.join(lib_dir, f), '') for f in os.listdir(lib_dir)]`. `lib_dir` here equals `Lib/site-packages/shapely/DLLs`. The actual directory on my conda python 3.6 installation is `Library/bin/`. My old spec file uses the following ugly code to copy these libraries over:\r\n\r\n```\r\n    lib_dir = sys.executable.replace(\"python.exe\", os.path.join(\"Library\", \"bin\"))\r\n    binaries += [(os.path.join(lib_dir, 'geos_c.dll'), '')]\r\n    binaries += [(os.path.join(lib_dir, 'geos.dll'), '')]\r\n    binaries += [(os.path.join(lib_dir, 'mkl_*.dll'), '')]\r\n```\r\n\r\nIs there a better way to get a hold of this Library directory with some pyinstaller utility function? Does anyone know if other python environments (non-conda) have the directory used in the hook or @durden did you just guess on the Windows path?\r\n\r\nSide issue: Shapely 1.6+ doesn't seem to work on at least windows (haven't updated on other platforms). It fails to find the geos libraries mentioned above unless you execute the pyinstaller-made (inno setup packaged) executable from the install directory (`C:\\Program Files (x86)\\myprgm\\bin\\`). For now I'm just downgrading to 1.5.17.\nshapely hook doesn't work on windows\nUsing current develop, the shapely hook fails when it runs `binaries += [(os.path.join(lib_dir, f), '') for f in os.listdir(lib_dir)]`. `lib_dir` here equals `Lib/site-packages/shapely/DLLs`. The actual directory on my conda python 3.6 installation is `Library/bin/`. My old spec file uses the following ugly code to copy these libraries over:\r\n\r\n```\r\n    lib_dir = sys.executable.replace(\"python.exe\", os.path.join(\"Library\", \"bin\"))\r\n    binaries += [(os.path.join(lib_dir, 'geos_c.dll'), '')]\r\n    binaries += [(os.path.join(lib_dir, 'geos.dll'), '')]\r\n    binaries += [(os.path.join(lib_dir, 'mkl_*.dll'), '')]\r\n```\r\n\r\nIs there a better way to get a hold of this Library directory with some pyinstaller utility function? Does anyone know if other python environments (non-conda) have the directory used in the hook or @durden did you just guess on the Windows path?\r\n\r\nSide issue: Shapely 1.6+ doesn't seem to work on at least windows (haven't updated on other platforms). It fails to find the geos libraries mentioned above unless you execute the pyinstaller-made (inno setup packaged) executable from the install directory (`C:\\Program Files (x86)\\myprgm\\bin\\`). For now I'm just downgrading to 1.5.17.\n", "before_files": [{"content": "#-----------------------------------------------------------------------------\n# Copyright (c) 2017-2020, PyInstaller Development Team.\n#\n# Distributed under the terms of the GNU General Public License (version 2\n# or later) with exception for distributing the bootloader.\n#\n# The full license is in the file COPYING.txt, distributed with this software.\n#\n# SPDX-License-Identifier: (GPL-2.0-or-later WITH Bootloader-exception)\n#-----------------------------------------------------------------------------\n\nimport os\n\nfrom PyInstaller.utils.hooks import get_package_paths\nfrom PyInstaller.utils.hooks import is_module_satisfies\nfrom PyInstaller import compat\n\n# Necessary when using the vectorized subpackage\nhiddenimports = ['shapely.prepared']\n\npkg_base, pkg_dir = get_package_paths('shapely')\n\n\nbinaries = []\nif compat.is_win:\n    if compat.is_conda:\n        lib_dir = os.path.join(compat.base_prefix, 'Library', 'bin')\n    else:\n        lib_dir = os.path.join(pkg_dir, 'DLLs')\n    dll_files = ['geos_c.dll', 'geos.dll']\n    binaries += [(os.path.join(lib_dir, f), '.') for f in dll_files]\nelif compat.is_linux:\n    lib_dir = os.path.join(pkg_dir, '.libs')\n    dest_dir = os.path.join('shapely', '.libs')\n\n    # This duplicates the libgeos*.so* files in the build.  PyInstaller will\n    # copy them into the root of the build by default, but shapely cannot load\n    # them from there in linux IF shapely was installed via a whl file. The\n    # whl bundles its' own libgeos with a different name, something like\n    # libgeos_c-*.so.* but shapely tries to load libgeos_c.so if there isn't a\n    # ./libs directory under its' package. There is a proposed fix for this in\n    # shapely but it has not been accepted it:\n    # https://github.com/Toblerity/Shapely/pull/485\n    if is_module_satisfies('shapely <= 1.6'):\n        binaries += [(os.path.join(lib_dir, f), dest_dir) for f in os.listdir(lib_dir)]\n", "path": "PyInstaller/hooks/hook-shapely.py"}]}