Skip to content

1d bin packing solution for suggesting packing data directories and files into DVD or CD sized bins

Notifications You must be signed in to change notification settings

whatdoineed2do/dvdpacking

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

38 Commits
 
 
 
 
 
 
 
 
 
 

Repository files navigation

dvdpacking

This is a simple command line util that solves the (1d bin packing) problem for trying to efficiently organise a set of files/directories so that they use the least amount of DVD/CDs.

The util will accept list of files/directories and recursively sum each of the input - with all data sizes determined, the tool then applies a set of standard 1d bin packing algorithms (first fit, worst fit and best fit along with their descending counterparts) on the input file/directores.

The output is a report of the:

  • total number of required bins (as per capacity ie DVD or CD),
  • each bin's contents
  • packing pattern used.

The util will also report if any file/directory can not fit into the target bin capacity.

The user can also specify one of the inbuilt algorithms (via -p) to use if they wish.

Target bin capacity, via -c, is the only mandatory flag and can be specified in bytes or can use shorthands dvd or cd.

A reserve, via -r, specified in bytes or as a percentage of the overal capacity, can be requested when performing the bin packing; such a reserve would be useful if you intend to add other documents or generate indexing (such as html index page generated from the data set https://github.com/whatdoineed2do/imgcat) to the final output.

Example Usage

Most likely usage

This is my typical usage - allow the util to apply all inbuilt algorithms to determine least / most suitable bin packing suggestions.

$ dvdpacking -r 5% -c dvd _pending 2017*[0-9]
dvdpacking: ttl items=7  ttl size=18542384361 (17.27GiB)  lower bounds=5
dvdpacking:   6119016216  _pending
dvdpacking:   2102344092  2017-02
dvdpacking:   1527565446  2017-03
dvdpacking:   1181908894  2017-04
dvdpacking:   3661438150  2017-05
dvdpacking:   1876670069  2017-06
dvdpacking:   2073441494  2017-07
dvdpacking: ---
dvdpacking: First Fit #bins=4  #unhandled=1 size=6119016216 (5.699GiB)
dvdpacking: [warn] unhandled items = {
dvdpacking: [warn]   6119016216  _pending
dvdpacking: [warn] }
dvdpacking:   bin# 0  size=3629909538 (3.381GiB)  remain=842044280 (803MiB)  {
dvdpacking:     "2017-02"
dvdpacking:     "2017-03"
dvdpacking:   }
dvdpacking:   bin# 1  size=3058578963 (2.849GiB)  remain=1413374855 (1.316GiB)  {
dvdpacking:     "2017-04"
dvdpacking:     "2017-06"
dvdpacking:   }
dvdpacking:   bin# 2  size=3661438150 (3.41GiB)  remain=810515668 (773MiB)  {
dvdpacking:     "2017-05"
dvdpacking:   }
dvdpacking:   bin# 3  size=2073441494 (1.931GiB)  remain=2398512324 (2.234GiB)  {
dvdpacking:     "2017-07"
dvdpacking:   }
dvdpacking: ---
dvdpacking: First Fit Descending #bins=4  #unhandled=1 size=6119016216 (5.699GiB)
dvdpacking: [warn] unhandled items = {
dvdpacking: [warn]   6119016216  _pending
dvdpacking: [warn] }
dvdpacking:   bin# 0  size=2709474340 (2.523GiB)  remain=1762479478 (1.641GiB)  {
dvdpacking:     "2017-04"
dvdpacking:     "2017-03"
dvdpacking:   }
dvdpacking:   bin# 1  size=3950111563 (3.679GiB)  remain=521842255 (497.7MiB)  {
dvdpacking:     "2017-06"
dvdpacking:     "2017-07"
dvdpacking:   }
dvdpacking:   bin# 2  size=2102344092 (1.958GiB)  remain=2369609726 (2.207GiB)  {
dvdpacking:     "2017-02"
dvdpacking:   }
dvdpacking:   bin# 3  size=3661438150 (3.41GiB)  remain=810515668 (773MiB)  {
dvdpacking:     "2017-05"
dvdpacking:   }
dvdpacking: ---
dvdpacking: Worst Fit #bins=4  #unhandled=1 size=6119016216 (5.699GiB)
dvdpacking: [warn] unhandled items = {
dvdpacking: [warn]   6119016216  _pending
dvdpacking: [warn] }
dvdpacking:   bin# 0  size=2073441494 (1.931GiB)  remain=2398512324 (2.234GiB)  {
dvdpacking:     "2017-07"
dvdpacking:   }
dvdpacking:   bin# 1  size=3058578963 (2.849GiB)  remain=1413374855 (1.316GiB)  {
dvdpacking:     "2017-04"
dvdpacking:     "2017-06"
dvdpacking:   }
dvdpacking:   bin# 2  size=3629909538 (3.381GiB)  remain=842044280 (803MiB)  {
dvdpacking:     "2017-02"
dvdpacking:     "2017-03"
dvdpacking:   }
dvdpacking:   bin# 3  size=3661438150 (3.41GiB)  remain=810515668 (773MiB)  {
dvdpacking:     "2017-05"
dvdpacking:   }
dvdpacking: ---
dvdpacking: Worst Fit Descending #bins=4  #unhandled=1 size=6119016216 (5.699GiB)
dvdpacking: [warn] unhandled items = {
dvdpacking: [warn]   6119016216  _pending
dvdpacking: [warn] }
dvdpacking:   bin# 0  size=2102344092 (1.958GiB)  remain=2369609726 (2.207GiB)  {
dvdpacking:     "2017-02"
dvdpacking:   }
dvdpacking:   bin# 1  size=2709474340 (2.523GiB)  remain=1762479478 (1.641GiB)  {
dvdpacking:     "2017-04"
dvdpacking:     "2017-03"
dvdpacking:   }
dvdpacking:   bin# 2  size=3661438150 (3.41GiB)  remain=810515668 (773MiB)  {
dvdpacking:     "2017-05"
dvdpacking:   }
dvdpacking:   bin# 3  size=3950111563 (3.679GiB)  remain=521842255 (497.7MiB)  {
dvdpacking:     "2017-06"
dvdpacking:     "2017-07"
dvdpacking:   }
dvdpacking: ---
dvdpacking: Best Fit #bins=4  #unhandled=1 size=6119016216 (5.699GiB)
dvdpacking: [warn] unhandled items = {
dvdpacking: [warn]   6119016216  _pending
dvdpacking: [warn] }
dvdpacking:   bin# 0  size=2073441494 (1.931GiB)  remain=2398512324 (2.234GiB)  {
dvdpacking:     "2017-07"
dvdpacking:   }
dvdpacking:   bin# 1  size=3058578963 (2.849GiB)  remain=1413374855 (1.316GiB)  {
dvdpacking:     "2017-04"
dvdpacking:     "2017-06"
dvdpacking:   }
dvdpacking:   bin# 2  size=3629909538 (3.381GiB)  remain=842044280 (803MiB)  {
dvdpacking:     "2017-02"
dvdpacking:     "2017-03"
dvdpacking:   }
dvdpacking:   bin# 3  size=3661438150 (3.41GiB)  remain=810515668 (773MiB)  {
dvdpacking:     "2017-05"
dvdpacking:   }
dvdpacking: ---
dvdpacking: Best Fit Descending #bins=4  #unhandled=1 size=6119016216 (5.699GiB)
dvdpacking: [warn] unhandled items = {
dvdpacking: [warn]   6119016216  _pending
dvdpacking: [warn] }
dvdpacking:   bin# 0  size=2102344092 (1.958GiB)  remain=2369609726 (2.207GiB)  {
dvdpacking:     "2017-02"
dvdpacking:   }
dvdpacking:   bin# 1  size=2709474340 (2.523GiB)  remain=1762479478 (1.641GiB)  {
dvdpacking:     "2017-04"
dvdpacking:     "2017-03"
dvdpacking:   }
dvdpacking:   bin# 2  size=3661438150 (3.41GiB)  remain=810515668 (773MiB)  {
dvdpacking:     "2017-05"
dvdpacking:   }
dvdpacking:   bin# 3  size=3950111563 (3.679GiB)  remain=521842255 (497.7MiB)  {
dvdpacking:     "2017-06"
dvdpacking:     "2017-07"
dvdpacking:   }
dvdpacking: ------
dvdpacking: summary:
dvdpacking:     bins= 4  Best Fit
dvdpacking:     bins= 4  Best Fit Descending
dvdpacking:     bins= 4  First Fit
dvdpacking:     bins= 4  First Fit Descending
dvdpacking:     bins= 4  Worst Fit
dvdpacking:     bins= 4  Worst Fit Descending

Alternative usage

No reserve is needed and we only want to consider the results of bestfit bin packing

$ dvdpacking -p bestfit -c dvd _pending 2017*[0-9]
dvdpacking: ttl items=7  ttl size=18542384361 (17.27GiB)  lower bounds=4
dvdpacking:   6119016216  _pending
dvdpacking:   2102344092  2017-02
dvdpacking:   1527565446  2017-03
dvdpacking:   1181908894  2017-04
dvdpacking:   3661438150  2017-05
dvdpacking:   1876670069  2017-06
dvdpacking:   2073441494  2017-07
dvdpacking: ---
dvdpacking: Best Fit #bins=4  #unhandled=1 size=6119016216 (5.699GiB)
dvdpacking: [warn] unhandled items = {
dvdpacking: [warn]   6119016216  _pending
dvdpacking: [warn] }
dvdpacking:   bin# 0  size=2073441494 (1.931GiB)  remain=2633878314 (2.453GiB)  {
dvdpacking:     "2017-07"
dvdpacking:   }
dvdpacking:   bin# 1  size=3058578963 (2.849GiB)  remain=1648740845 (1.536GiB)  {
dvdpacking:     "2017-04"
dvdpacking:     "2017-06"
dvdpacking:   }
dvdpacking:   bin# 2  size=3629909538 (3.381GiB)  remain=1077410270 (1.003GiB)  {
dvdpacking:     "2017-02"
dvdpacking:     "2017-03"
dvdpacking:   }
dvdpacking:   bin# 3  size=3661438150 (3.41GiB)  remain=1045881658 (997.4MiB)  {
dvdpacking:     "2017-05"
dvdpacking:   }

Generate output

Using -o to specify an existing directory, the util can create directories for each considered packing alogirthm, where each created directory would contain symlinks to the files/directories under consideration: the symlinks will refer to the underlying file/directory if symlnks were provided on the command line.

$ dvdpacking -p bestfit -c dvd -o /tmp/foo _pending 2017*[0-9]
dvdpacking: ttl items=7  ttl size=18542384361 (17.27GiB)  lower bounds=4
dvdpacking:   6119016216  _pending
dvdpacking:   2102344092  2017-02
dvdpacking:   1527565446  2017-03
dvdpacking:   1181908894  2017-04
dvdpacking:   3661438150  2017-05
dvdpacking:   1876670069  2017-06
dvdpacking:   2073441494  2017-07
dvdpacking: ---
dvdpacking: Best Fit #bins=4  #unhandled=1 size=6119016216 (5.699GiB)
dvdpacking: [warn] unhandled items = {
dvdpacking: [warn]   6119016216  _pending
dvdpacking: [warn] }
dvdpacking:   bin# 0  size=2073441494 (1.931GiB)  remain=2633878314 (2.453GiB)  {
dvdpacking:     "2017-07"
dvdpacking:   }
dvdpacking:   bin# 1  size=3058578963 (2.849GiB)  remain=1648740845 (1.536GiB)  {
dvdpacking:     "2017-04"
dvdpacking:     "2017-06"
dvdpacking:   }
dvdpacking:   bin# 2  size=3629909538 (3.381GiB)  remain=1077410270 (1.003GiB)  {
dvdpacking:     "2017-02"
dvdpacking:     "2017-03"
dvdpacking:   }
dvdpacking:   bin# 3  size=3661438150 (3.41GiB)  remain=1045881658 (997.4MiB)  {
dvdpacking:     "2017-05"
dvdpacking:   }

This will create, under /tmp/foo, a directory for each of the bins represented

/tmp/foo/Best Fit/bin00/2017-07

/tmp/foo/Best Fit/bin01/2017-04
/tmp/foo/Best Fit/bin01/2017-06

/tmp/foo/Best Fit/bin02/2017-02
/tmp/foo/Best Fit/bin02/2017-03

/tmp/foo/Best Fit/bin03/2017-05

The contents of the generated bin directories are symbolic links to the realpath of the input so the bin dirs or items contents can be moved to other locations for final cdrecord or growisofs commands.

Further Enhancements

If you wish to add other bin packing algorithms to this util, look at the abstract interface Packer.h - create a child and implement the pack(..) method and finally register an instance of the object to the bps and allbps objects in main() and your algorithm will be automatically used.

About

1d bin packing solution for suggesting packing data directories and files into DVD or CD sized bins

Resources

Stars

Watchers

Forks

Packages

No packages published