{"_id":"shelf-pack","_rev":"402647","name":"shelf-pack","description":"A 2D rectangular bin packing data structure that uses the Shelf Best Height Fit heuristic","dist-tags":{"latest":"2.0.1"},"maintainers":[{"name":"bhousel","email":"bryan@mapbox.com"}],"time":{"modified":"2021-08-04T04:36:43.000Z","created":"2016-02-05T20:26:54.942Z","2.0.1":"2016-08-11T18:49:45.412Z","2.0.0":"2016-08-08T13:41:57.504Z","1.1.0":"2016-07-15T20:02:29.004Z","1.0.0":"2016-03-29T15:55:20.465Z","0.0.1":"2016-02-05T20:26:54.942Z"},"users":{},"author":{"name":"Bryan Housel","email":"bryan@mapbox.com"},"repository":{"type":"git","url":"git://github.com/mapbox/shelf-pack.git"},"versions":{"2.0.1":{"name":"shelf-pack","description":"A 2D rectangular bin packing data structure that uses the Shelf Best Height Fit heuristic","version":"2.0.1","main":"index.umd.js","jsnext:main":"index.js","license":"ISC","author":{"name":"Bryan Housel","email":"bryan@mapbox.com"},"repository":{"type":"git","url":"git://github.com/mapbox/shelf-pack.git"},"bugs":{"url":"https://github.com/mapbox/shelf-pack/issues"},"keywords":["bin packing","sprite"],"devDependencies":{"benchmark":"~2.1.0","bin-pack":"1.0.2","coveralls":"^2.11.12","documentation":"4.0.0-beta5","eslint":"~3.2.2","rollup":"0.34.7","tap":"~6.3.0"},"engines":{"node":">=4.0.0"},"scripts":{"bench":"npm run build && node bench/bench.js","build":"rollup -f umd -n ShelfPack index.js --no-indent --no-strict -o index.umd.js","docs":"documentation build index.js --lint --github --format html --output docs/","lint":"eslint index.js test/ bench/","test":"npm run build && npm run lint && tap --cov test/*.js"},"gitHead":"3e1d644b5a693349fc4aad4e5a7da5cd7990f881","homepage":"https://github.com/mapbox/shelf-pack#readme","_id":"shelf-pack@2.0.1","_shasum":"8da0bad21580a6bb7b0dbb683dbf850a83b1b431","_from":".","_npmVersion":"3.3.6","_nodeVersion":"5.0.0","_npmUser":{"name":"bhousel","email":"bryan@mapbox.com"},"dist":{"shasum":"8da0bad21580a6bb7b0dbb683dbf850a83b1b431","size":1804420,"noattachment":false,"key":"/shelf-pack/-/shelf-pack-2.0.1.tgz","tarball":"http://registry.cnpm.dingdandao.com/shelf-pack/download/shelf-pack-2.0.1.tgz"},"maintainers":[{"name":"bhousel","email":"bryan@mapbox.com"}],"_npmOperationalInternal":{"host":"packages-16-east.internal.npmjs.com","tmp":"tmp/shelf-pack-2.0.1.tgz_1470941384100_0.8153139459900558"},"directories":{},"publish_time":1470941385412,"_cnpm_publish_time":1470941385412,"deprecated":"This module is now under the @mapbox namespace: install @mapbox/shelf-pack instead","_hasShrinkwrap":false},"2.0.0":{"name":"shelf-pack","description":"A 2D rectangular bin packing data structure that uses the Shelf Best Height Fit heuristic","version":"2.0.0","main":"index.umd.js","jsnext:main":"index.js","license":"ISC","author":{"name":"Bryan Housel","email":"bryan@mapbox.com"},"repository":{"type":"git","url":"git://github.com/mapbox/shelf-pack.git"},"bugs":{"url":"https://github.com/mapbox/shelf-pack/issues"},"keywords":["bin packing","sprite"],"devDependencies":{"benchmark":"~2.1.0","bin-pack":"1.0.2","documentation":"4.0.0-beta5","eslint":"~3.2.2","rollup":"0.34.7","tap":"~6.3.0"},"engines":{"node":">=4.0.0"},"scripts":{"bench":"npm run build && node bench/bench.js","build":"rollup -f umd -n ShelfPack index.js --no-indent --no-strict -o index.umd.js","docs":"documentation build index.js --lint --github --format html --output docs/","lint":"eslint index.js test/ bench/","test":"npm run build && npm run lint && tap --cov test/*.js"},"gitHead":"1849839d6c21891f4588897026a1dabb4e8f7889","homepage":"https://github.com/mapbox/shelf-pack#readme","_id":"shelf-pack@2.0.0","_shasum":"b90d7c9cae032d34a21544d7c20adbe59bc75073","_from":".","_npmVersion":"3.3.6","_nodeVersion":"5.0.0","_npmUser":{"name":"bhousel","email":"bryan@mapbox.com"},"dist":{"shasum":"b90d7c9cae032d34a21544d7c20adbe59bc75073","size":1804057,"noattachment":false,"key":"/shelf-pack/-/shelf-pack-2.0.0.tgz","tarball":"http://registry.cnpm.dingdandao.com/shelf-pack/download/shelf-pack-2.0.0.tgz"},"maintainers":[{"name":"bhousel","email":"bryan@mapbox.com"}],"_npmOperationalInternal":{"host":"packages-12-west.internal.npmjs.com","tmp":"tmp/shelf-pack-2.0.0.tgz_1470663714765_0.13634227332659066"},"directories":{},"publish_time":1470663717504,"_cnpm_publish_time":1470663717504,"deprecated":"This module is now under the @mapbox namespace: install @mapbox/shelf-pack instead","_hasShrinkwrap":false},"1.1.0":{"name":"shelf-pack","description":"A 2D rectangular bin packing data structure that uses the Shelf Best Height Fit heuristic","version":"1.1.0","main":"index.umd.js","jsnext:main":"index.js","license":"ISC","author":{"name":"Bryan Housel","email":"bryan@mapbox.com"},"repository":{"type":"git","url":"git://github.com/mapbox/shelf-pack.git"},"bugs":{"url":"https://github.com/mapbox/shelf-pack/issues"},"keywords":["bin packing","sprite"],"devDependencies":{"benchmark":"2.1.0","bin-pack":"1.0.2","documentation":"4.0.0-beta5","eslint":"3.0.1","rollup":"0.34.1","tap":"6.1.1"},"engines":{"node":">=4.0.0"},"scripts":{"pretest":"rollup -f umd -n ShelfPack index.js --no-indent --no-strict -o index.umd.js","lint":"eslint index.js test/ bench/","docs":"documentation build index.js --lint --github --format html --output docs/","test":"npm run lint && tap --cov test/*.js","bench":"node bench/bench.js"},"gitHead":"c7ea121077591e236ac2255882bb92cf4b1135cd","homepage":"https://github.com/mapbox/shelf-pack#readme","_id":"shelf-pack@1.1.0","_shasum":"b4679afdd00ad68dfd9bbd2b5a3e819293a74d82","_from":".","_npmVersion":"3.3.6","_nodeVersion":"5.0.0","_npmUser":{"name":"bhousel","email":"bryan@mapbox.com"},"maintainers":[{"name":"bhousel","email":"bryan@mapbox.com"}],"dist":{"shasum":"b4679afdd00ad68dfd9bbd2b5a3e819293a74d82","size":1799541,"noattachment":false,"key":"/shelf-pack/-/shelf-pack-1.1.0.tgz","tarball":"http://registry.cnpm.dingdandao.com/shelf-pack/download/shelf-pack-1.1.0.tgz"},"_npmOperationalInternal":{"host":"packages-16-east.internal.npmjs.com","tmp":"tmp/shelf-pack-1.1.0.tgz_1468612948062_0.7299501388333738"},"directories":{},"publish_time":1468612949004,"_cnpm_publish_time":1468612949004,"deprecated":"This module is now under the @mapbox namespace: install @mapbox/shelf-pack instead","_hasShrinkwrap":false},"1.0.0":{"name":"shelf-pack","description":"A 2D rectangular bin packing data structure that uses the Shelf Best Height Fit heuristic","version":"1.0.0","main":"index.js","license":"ISC","author":{"name":"Bryan Housel","email":"bryan@mapbox.com"},"repository":{"type":"git","url":"git://github.com/mapbox/shelf-pack.git"},"bugs":{"url":"https://github.com/mapbox/shelf-pack/issues"},"keywords":["bin packing","sprite"],"devDependencies":{"benchmark":"^2.1.0","bin-pack":"1.0.2","documentation":"^4.0.0-beta","eslint":"^1.6.0","retire":"*","tap":"^2.1.1"},"scripts":{"retire":"retire -p","lint":"eslint *.js test","docs":"documentation build --lint --github --format html --output docs/","test":"npm run lint && tap --cov test/*.js","bench":"node bench/bench.js"},"gitHead":"fd3a240fcf7034d56d3fb217906bfd61aac12844","homepage":"https://github.com/mapbox/shelf-pack#readme","_id":"shelf-pack@1.0.0","_shasum":"d1ecd83e2374794408dde8ae1cacde2ec1d101bf","_from":".","_npmVersion":"3.3.6","_nodeVersion":"5.0.0","_npmUser":{"name":"bhousel","email":"bryan@mapbox.com"},"maintainers":[{"name":"bhousel","email":"bryan@mapbox.com"}],"dist":{"shasum":"d1ecd83e2374794408dde8ae1cacde2ec1d101bf","size":603691,"noattachment":false,"key":"/shelf-pack/-/shelf-pack-1.0.0.tgz","tarball":"http://registry.cnpm.dingdandao.com/shelf-pack/download/shelf-pack-1.0.0.tgz"},"_npmOperationalInternal":{"host":"packages-16-east.internal.npmjs.com","tmp":"tmp/shelf-pack-1.0.0.tgz_1459266919513_0.48529803892597556"},"directories":{},"publish_time":1459266920465,"_cnpm_publish_time":1459266920465,"deprecated":"This module is now under the @mapbox namespace: install @mapbox/shelf-pack instead","_hasShrinkwrap":false},"0.0.1":{"name":"shelf-pack","description":"A 2D rectangular bin packing data structure that uses the Shelf Best Height Fit heuristic","version":"0.0.1","main":"index.js","license":"ISC","author":{"name":"Bryan Housel","email":"bryan@mapbox.com"},"repository":{"type":"git","url":"git://github.com/mapbox/shelf-pack.git"},"bugs":{"url":"https://github.com/mapbox/shelf-pack/issues"},"keywords":["bin packing","sprite"],"devDependencies":{"documentation":"^2.1.0-alpha2","documentation-readme":"^2.0.0","eslint":"^1.6.0","retire":"*","tap":"^2.1.1"},"scripts":{"retire":"retire -p","lint":"eslint *.js test","docs-page":"documentation --lint --github --format html --output .","docs-readme":"documentation-readme -s API","test":"npm run retire && npm run lint && tap --cov test/*.js"},"gitHead":"9e582bae9699ea92264fe3b8848e93a0c0d1d59d","homepage":"https://github.com/mapbox/shelf-pack#readme","_id":"shelf-pack@0.0.1","_shasum":"2d1d96f6d2e7265584942139f002c69c1042746b","_from":".","_npmVersion":"2.14.9","_nodeVersion":"0.12.9","_npmUser":{"name":"bhousel","email":"bryan@mapbox.com"},"maintainers":[{"name":"bhousel","email":"bryan@mapbox.com"}],"dist":{"shasum":"2d1d96f6d2e7265584942139f002c69c1042746b","size":3092,"noattachment":false,"key":"/shelf-pack/-/shelf-pack-0.0.1.tgz","tarball":"http://registry.cnpm.dingdandao.com/shelf-pack/download/shelf-pack-0.0.1.tgz"},"_npmOperationalInternal":{"host":"packages-5-east.internal.npmjs.com","tmp":"tmp/shelf-pack-0.0.1.tgz_1454704013849_0.8181771140079945"},"directories":{},"publish_time":1454704014942,"_cnpm_publish_time":1454704014942,"deprecated":"This module is now under the @mapbox namespace: install @mapbox/shelf-pack instead","_hasShrinkwrap":false}},"readme":"[![npm version](https://badge.fury.io/js/shelf-pack.svg)](https://badge.fury.io/js/shelf-pack)\n[![Build Status](https://circleci.com/gh/mapbox/shelf-pack/tree/master.svg?style=shield)](https://circleci.com/gh/mapbox/shelf-pack)\n[![Coverage Status](https://coveralls.io/repos/github/mapbox/shelf-pack/badge.svg?branch=master)](https://coveralls.io/github/mapbox/shelf-pack?branch=master)\n\n## shelf-pack\n\nA 2D rectangular [bin packing](https://en.wikipedia.org/wiki/Bin_packing_problem)\ndata structure that uses the Shelf Best Height Fit heuristic.\n\n\n### What is it?\n\n`shelf-pack` is a library for packing little rectangles into a big rectangle.  This sounds simple enough,\nbut finding an optimal packing is a problem with [NP-Complete](https://en.wikipedia.org/wiki/NP-completeness)\ncomplexity.  One useful application of bin packing is to assemble icons or glyphs into a sprite texture.\n\nThere are many ways to approach the bin packing problem, but `shelf-pack` uses the Shelf Best\nHeight Fit heuristic.  It works by dividing the total space into \"shelves\", each with a certain height.\nThe allocator packs rectangles onto whichever shelf minimizes the amount of wasted vertical space.\n\n`shelf-pack` is simple, fast, and works best when the rectangles have similar heights (icons and glyphs\nare like this).  It is not a generalized bin packer, and can potentially waste a lot of space if the\nrectangles vary significantly in height.\n\n\n### How fast is it?\n\nReally fast!  `shelf-pack` is several orders of magnitude faster than the more general\n[`bin-pack`](https://www.npmjs.com/package/bin-pack) library.\n\n```bash\n> npm run bench\n\nShelfPack single allocate fixed size bins x 1,610 ops/sec ±1.21% (90 runs sampled)\nShelfPack single allocate random width bins x 1,475 ops/sec ±1.00% (89 runs sampled)\nShelfPack single allocate random height bins x 1,458 ops/sec ±1.00% (90 runs sampled)\nShelfPack single allocate random height and width bins x 1,346 ops/sec ±0.96% (89 runs sampled)\nShelfPack batch allocate fixed size bins x 1,522 ops/sec ±1.06% (86 runs sampled)\nShelfPack batch allocate random width bins x 1,427 ops/sec ±1.06% (89 runs sampled)\nShelfPack batch allocate random height bins x 1,350 ops/sec ±1.63% (90 runs sampled)\nShelfPack batch allocate random height and width bins x 1,257 ops/sec ±1.02% (89 runs sampled)\nBinPack batch allocate fixed size bins x 2.21 ops/sec ±6.60% (10 runs sampled)\nBinPack batch allocate random width bins x 0.50 ops/sec ±2.25% (6 runs sampled)\nBinPack batch allocate random height bins x 0.51 ops/sec ±1.97% (6 runs sampled)\nBinPack batch allocate random height and width bins x 0.51 ops/sec ±1.37% (6 runs sampled)\n```\n\n\n### Usage\n\n#### Basic Usage\n\n```js\nvar ShelfPack = require('shelf-pack');\n\n// Initialize the sprite with a width and height..\nvar sprite = new ShelfPack(64, 64);\n\n// Pack bins one at a time..\nfor (var i = 0; i < 5; i++) {\n    // packOne() accepts parameters: `width`, `height`, `id`\n    // and returns a single allocated Bin object..\n    // `id` is optional - if you skip it, shelf-pack will make up a number for you..\n    // (Protip: numeric ids are much faster than string ids)\n\n    var bin = sprite.packOne(32, 32);\n    console.log(bin || 'out of space');\n}\n\n/* output:\nBin { id: 1, x: 0, y: 0, w: 32, h: 32, maxw: 32, maxh: 32, refcount: 1 }\nBin { id: 2, x: 32, y: 0, w: 32, h: 32, maxw: 32, maxh: 32, refcount: 1 }\nBin { id: 3, x: 0, y: 32, w: 32, h: 32, maxw: 32, maxh: 32, refcount: 1 }\nBin { id: 4, x: 32, y: 32, w: 32, h: 32, maxw: 32, maxh: 32, refcount: 1 }\nout of space\n*/\n\n// Clear sprite and start over..\nsprite.clear();\n\n// Or, resize sprite by passing larger dimensions..\nsprite.resize(128, 128);   // width, height\n\n```\n\n\n#### Batch packing\n\n```js\nvar ShelfPack = require('shelf-pack');\n\n// If you don't want to think about the size of the sprite,\n// the `autoResize` option will allow it to grow as needed..\nvar sprite = new ShelfPack(10, 10, { autoResize: true });\n\n// Bins can be allocated in batches..\n// Each requested bin should have `w`, `h` (or `width`, `height`) properties..\nvar requests = [\n    { id: 'a', width: 10, height: 10 },\n    { id: 'b', width: 10, height: 12 },\n    { id: 'c', w: 10, h: 12 },\n    { id: 'd', w: 10, h: 10 }\n];\n\n// pack() returns an Array of packed Bin objects..\nvar results = sprite.pack(requests);\n\nresults.forEach(function(bin) {\n    console.log(bin);\n});\n\n/* output:\nBin { id: 'a', x: 0, y: 0, w: 10, h: 10, maxw: 10, maxh: 10, refcount: 1 }\nBin { id: 'b', x: 0, y: 10, w: 10, h: 12, maxw: 10, maxh: 12, refcount: 1 }\nBin { id: 'c', x: 10, y: 10, w: 10, h: 12, maxw: 10, maxh: 12, refcount: 1 }\nBin { id: 'd', x: 10, y: 0, w: 10, h: 10, maxw: 10, maxh: 10, refcount: 1 }\n*/\n\n// If you don't mind letting ShelfPack modify your objects,\n// the `inPlace` option will decorate your bin objects with `x` and `y` properties.\n// Fancy!\nvar myBins = [\n    { id: 'e', width: 12, height: 24 },\n    { id: 'f', width: 12, height: 12 },\n    { id: 'g', w: 10, h: 10 }\n];\n\nsprite.pack(myBins, { inPlace: true });\nmyBins.forEach(function(bin) {\n    console.log(bin);\n});\n\n/* output:\n{ id: 'e', width: 12, height: 24, x: 0, y: 22 }\n{ id: 'f', width: 12, height: 12, x: 20, y: 10 }\n{ id: 'g', w: 10, h: 10, x: 20, y: 0 }\n*/\n\n```\n\n#### Reference Counting\n\n```js\nvar ShelfPack = require('shelf-pack');\n\n// Initialize the sprite with a width and height..\nvar sprite = new ShelfPack(64, 64);\n\n// Allocated bins are automatically reference counted.\n// They start out having a refcount of 1.\n[100, 101, 102].forEach(function(id) {\n    var bin = sprite.packOne(16, 16, id);\n    console.log(bin);\n});\n\n/* output:\nBin { id: 100, x: 0, y: 0, w: 16, h: 16, maxw: 16, maxh: 16, refcount: 1 }\nBin { id: 101, x: 16, y: 0, w: 16, h: 16, maxw: 16, maxh: 16, refcount: 1 }\nBin { id: 102, x: 32, y: 0, w: 16, h: 16, maxw: 16, maxh: 16, refcount: 1 }\n*/\n\n// If you try to pack the same id again, shelf-pack will not re-pack it.\n// Instead, it will increment the reference count automatically..\nvar bin102 = sprite.packOne(16, 16, 102);\nconsole.log(bin102);\n\n/* output:\nBin { id: 102, x: 32, y: 0, w: 16, h: 16, maxw: 16, maxh: 16, refcount: 2 }\n*/\n\n// You can also manually increment the reference count..\nvar bin101 = sprite.getBin(101);\nsprite.ref(bin101);\nconsole.log(bin101);\n\n/* output:\nBin { id: 101, x: 16, y: 0, w: 16, h: 16, maxw: 16, maxh: 16, refcount: 2 }\n*/\n\n// ...and decrement it!\nvar bin100 = sprite.getBin(100);\nsprite.unref(bin100);\nconsole.log(bin100);\n\n/* output:\nBin { id: 100, x: 0, y: 0, w: 16, h: 16, maxw: 16, maxh: 16, refcount: 0 }\n*/\n\n// Bins with a refcount of 0 are considered free space.\n// Next time a bin is packed, shelf-back tries to reuse free space first.\n// See how Bin 103 gets allocated at [0,0] - Bin 100's old spot!\nvar bin103 = sprite.packOne(16, 15, 103);\nconsole.log(bin103);\n\n/* output:\nBin { id: 103, x: 0, y: 0, w: 16, h: 15, maxw: 16, maxh: 16, refcount: 1 }\n*/\n\n// Bin 103 may be smaller (16x15) but it knows 16x16 was its original size.\n// If that space becomes free again, a 16x16 bin will still fit there.\nsprite.unref(bin103)\nvar bin104 = sprite.packOne(16, 16, 104);\nconsole.log(bin104);\n\n/* output:\nBin { id: 104, x: 0, y: 0, w: 16, h: 16, maxw: 16, maxh: 16, refcount: 1 }\n*/\n\n```\n\n\n### Documentation\n\nComplete API documentation is here:  http://mapbox.github.io/shelf-pack/docs/\n\n\n### See also\n\nJ. Jylänky, \"A Thousand Ways to Pack the Bin - A Practical\nApproach to Two-Dimensional Rectangle Bin Packing,\"\nhttp://clb.demon.fi/files/RectangleBinPack.pdf, 2010\n","_attachments":{},"homepage":"https://github.com/mapbox/shelf-pack#readme","bugs":{"url":"https://github.com/mapbox/shelf-pack/issues"},"license":"ISC"}