Coverage for moptipyapps / binpacking2d / make_instances.py: 72%
103 statements
« prev ^ index » next coverage.py v7.13.0, created at 2025-12-11 04:40 +0000
1"""
2Obtain Instances of the 2D-dimensional Bin Packing Problem.
4With this program, we can obtain the instances of the two-dimensional bin
5packing problem and convert them to a singular resource file.
6The resource file holds one instance per line.
81. Manuel Iori, Vinícius Loti de Lima, Silvano Martello, and Michele Monaci.
9 *2DPackLib*.
10 https://site.unibo.it/operations-research/en/research/2dpacklib
112. Manuel Iori, Vinícius Loti de Lima, Silvano Martello, and Michele
12 Monaci. 2DPackLib: A Two-Dimensional Cutting and Packing Library.
13 *Optimization Letters* 16(2):471-480. March 2022.
14 https://doi.org/10.1007/s11590-021-01808-y
15"""
17import zipfile
18from io import BytesIO
19from math import isqrt
20from os.path import dirname, exists
21from typing import Any, Callable, Final, Iterable
23# noinspection PyPackageRequirements
24import certifi # type: ignore
26# noinspection PyPackageRequirements
27import urllib3 # type: ignore
28from pycommons.io.path import Path, directory_path, file_path, write_lines
29from pycommons.io.temp import temp_dir
30from pycommons.types import type_error
32import moptipyapps.binpacking2d.instance as inst_mod
33from moptipyapps.binpacking2d.instance import (
34 INSTANCES_RESOURCE,
35 Instance,
36)
38#: the base url for 2DPackLib
39__BASE_URL: str = \
40 "https://site.unibo.it/operations-research/en/research/2dpacklib"
42#: The base URLs of the relevant 2DPackLib instances.
43__BASE_URLS: Final[Iterable[str]] = tuple(
44 f"{__BASE_URL}/{f}.zip" for f in ["a", "beng", "class"])
47def download_2dpacklib_instances(
48 dest_dir: str,
49 source_urls: Iterable[str] = __BASE_URLS,
50 http: urllib3.PoolManager = urllib3.PoolManager(
51 cert_reqs="CERT_REQUIRED", ca_certs=certifi.where())) \
52 -> Iterable[Path]:
53 """
54 Download the instances from 2DPackLib to a folder.
56 This function downloads the instances from 2DPackLib, which are provided
57 as zip archives containing one file per instance. It will extract all the
58 instances into the folder `dest_dir` and return a tuple of the extracted
59 files. You can specify the source URLs of the zip archives if you want,
60 but by default we use the three instance sets `A`, `BENG`, and `CLASS`.
62 :param dest_dir: the destination directory
63 :param source_urls: the source URLs from which to download the zip
64 archives with the 2DPackLib-formatted instances
65 :param http: the HTTP pool
66 :return: the list of unpackaged files
67 """
68 dest: Final[Path] = directory_path(dest_dir)
69 if not isinstance(source_urls, Iterable):
70 raise type_error(source_urls, "source_urls", Iterable)
71 result: Final[list[Path]] = []
73 for i, url in enumerate(source_urls): # iterate over the source URLs
74 if not isinstance(url, str):
75 raise type_error(url, f"source_urls[{i}]", str)
77 response = http.request( # download the zip archive
78 "GET", url, redirect=True, retries=30)
79 with zipfile.ZipFile(BytesIO(response.data), mode="r") as z:
80 # unzip the ins2D files from the archives
81 files: Iterable[str] = [f for f in z.namelist()
82 if f.endswith(".ins2D")]
83 paths: list[Path] = [dest.resolve_inside(f) for f in files]
84 for path in paths:
85 if exists(path):
86 raise ValueError(f"file {path} already exists!")
87 z.extractall(dest, members=files)
88 for path in paths:
89 path.enforce_file()
90 result.append(path)
91 result.sort()
92 return tuple(result)
95def __normalize_2dpacklib_inst_name(instname: str) -> str:
96 """
97 Normalize an instance name.
99 :param instname: the name
100 :return: the normalized name
101 """
102 if not isinstance(instname, str):
103 raise type_error(instname, "name", str)
104 instname = instname.strip().lower()
105 if (len(instname) == 2) and \
106 (instname[0] in "abcdefghijklmnoprstuvwxyz") and \
107 (instname[1] in "123456789"):
108 return f"{instname[0]}0{instname[1]}"
109 if instname.startswith("cl_"):
110 return f"cl{instname[3:]}"
111 return instname
114def append_almost_squares_strings(collector: Callable[[
115 tuple[str, str]], Any]) -> None:
116 """
117 Append the strings of the almost squares instances.
119 :param collector: the instance collector
120 :return: the strings
121 """
122 objects: list[list[int]] = [[2, 1, 1]]
123 size: int = 2
124 for small_side in range(2, 36):
125 big_side = small_side + 1
126 objects.append([big_side, small_side, 1])
127 size += small_side * big_side
129 bin_small = isqrt(size)
130 bin_big = bin_small + 1
131 if (bin_big * bin_small) == size:
132 iname: str = str(small_side)
133 iname = f"asqas{iname}" if len(iname) >= 2 else f"asqas0{iname}"
134 collector((iname, Instance(
135 iname, bin_big, bin_small, objects).to_compact_str()))
138def join_instances_to_compact(
139 binpacklib2d_files: Iterable[str], dest_file: str,
140 normalizer: Callable[[str], str] = __normalize_2dpacklib_inst_name) \
141 -> tuple[Path, Iterable[str]]:
142 """
143 Join all instances from a set of 2DPackLib files to one compact file.
145 :param binpacklib2d_files: the iterable of 2DPackLib file paths
146 :param dest_file: the destination file
147 :param normalizer: the name normalizer, i.e., a function that processes
148 and/or transforms an instance name
149 :return: the canonical destination path and the list of instance names
150 stored
151 """
152 if not isinstance(binpacklib2d_files, Iterable):
153 raise type_error(binpacklib2d_files, "files", Iterable)
154 if not callable(normalizer):
155 raise type_error(normalizer, "normalizer", call=True)
156 dest_path = Path(dest_file)
157 data: Final[list[tuple[str, str]]] = []
158 for file in binpacklib2d_files:
159 inst: Instance = Instance.from_2dpacklib(file_path(file))
160 inst.name = normalizer(inst.name)
161 data.append((inst.name, inst.to_compact_str()))
162 append_almost_squares_strings(data.append) # add the asquas instances
163 data.sort()
164 with dest_path.open_for_write() as wd:
165 write_lines((content for _, content in data), wd)
166 dest_path.enforce_file()
167 return dest_path, [thename for thename, _ in data]
170def make_2dpacklib_resource(
171 dest_file: "str | None" = None,
172 source_urls: Iterable[str] = __BASE_URLS,
173 normalizer: Callable[[str], str] = __normalize_2dpacklib_inst_name)\
174 -> tuple[Path, Iterable[str]]:
175 """
176 Make the resource with all the relevant 2DPackLib instances.
178 :param dest_file: the optional path to the destination file
179 :param source_urls: the source URLs from which to download the zip
180 archives with the 2DPackLib-formatted instances
181 :param normalizer: the name normalizer, i.e., a function that processes
182 and/or transforms an instance name
183 :return: the canonical path to the and the list of instance names stored
184 """
185 dest_path: Final[Path] = directory_path(dirname(inst_mod.__file__))\
186 .resolve_inside(INSTANCES_RESOURCE) if dest_file is None \
187 else Path(dest_file)
188 with temp_dir() as temp:
189 files: Iterable[Path] = download_2dpacklib_instances(
190 dest_dir=temp, source_urls=source_urls)
191 return join_instances_to_compact(
192 files, dest_path, normalizer)
195# create the tables if this is the main script
196if __name__ == "__main__":
197 _, names = make_2dpacklib_resource()
198 rows: list[str] = ["_INSTANCES: Final[tuple[str, ...]] = ("]
199 current = " "
200 has_space: bool = True
201 for name in names:
202 if (len(current) + (3 if has_space else 4) + len(name)) > 78:
203 rows.append(current)
204 current = " "
205 has_space = True
206 current = f'{current}"{name}",' if has_space else \
207 f'{current} "{name}",'
208 has_space = False
209 rows.append(current[:-1] + ")")
211 cmt_strs: list[str] = (
212 "the the list of instance names of the 2DPackLib bin "
213 f"packing set downloaded from {__BASE_URL} ('a*',"
214 "'beng*', 'cl*') as well as the four non-trivial "
215 "'Almost Squares in Almost Squares' instances ('asqas*').").split()
216 cmt_str = "#:"
217 for word in cmt_strs:
218 if len(word) + 1 + len(cmt_str) <= 79:
219 cmt_str = f"{cmt_str} {word}"
220 else:
221 print(cmt_str) # noqa
222 cmt_str = f"#: {word}"
223 if len(cmt_str) > 2:
224 print(cmt_str) # noqa
226 for s in rows:
227 print(s) # noqa