1#ifndef SHELF_PACK_HPP
2#define SHELF_PACK_HPP
3
4#include <algorithm>
5#include <cstdint>
6#include <deque>
7#include <limits>
8#include <map>
9#include <vector>
10
11namespace mapbox {
12
13const char * const SHELF_PACK_VERSION = "2.1.1";
14
15
16
17class Bin {
18 friend class ShelfPack;
19
20public:
21 /**
22 * Create a new Bin.
23 *
24 * @class Bin
25 * @param {int32_t} id Unique bin identifier
26 * @param {int32_t} [w1=-1] Width of the new Bin
27 * @param {int32_t} [h1=-1] Height of the new Bin
28 * @param {int32_t} [maxw1=-1] Maximum Width of the new Bin
29 * @param {int32_t} [maxh1=-1] Maximum Height of the new Bin
30 * @param {int32_t} [x1=-1] X location of the Bin
31 * @param {int32_t} [y1=-1] Y location of the Bin
32 *
33 * @example
34 * Bin b(-1, 12, 16);
35 */
36 explicit Bin(
37 int32_t id1 = -1,
38 int32_t w1 = -1,
39 int32_t h1 = -1,
40 int32_t maxw1 = -1,
41 int32_t maxh1 = -1,
42 int32_t x1 = -1,
43 int32_t y1 = -1
44 ) : id(id1), w(w1), h(h1), maxw(maxw1), maxh(maxh1), x(x1), y(y1), refcount_(0) {
45
46 if (maxw == -1) {
47 maxw = w;
48 }
49 if (maxh == -1) {
50 maxh = h;
51 }
52 }
53
54 int32_t id;
55 int32_t w;
56 int32_t h;
57 int32_t maxw;
58 int32_t maxh;
59 int32_t x;
60 int32_t y;
61
62 int32_t refcount() const { return refcount_; }
63
64private:
65
66 int32_t refcount_;
67};
68
69
70class Shelf {
71public:
72 /**
73 * Create a new Shelf.
74 *
75 * @class Shelf
76 * @param {int32_t} y1 Top coordinate of the new shelf
77 * @param {int32_t} w1 Width of the new shelf
78 * @param {int32_t} h1 Height of the new shelf
79 *
80 * @example
81 * Shelf shelf(64, 512, 24);
82 */
83 explicit Shelf(int32_t y1, int32_t w1, int32_t h1) :
84 x_(0), y_(y1), w_(w1), h_(h1), wfree_(w1) { }
85
86
87 /**
88 * Allocate a single bin into the shelf.
89 * Bin is stored in a `bins_` container.
90 * Returned pointer is stable until the shelf is destroyed.
91 *
92 * @param {int32_t} id Unique bin identifier, pass -1 to generate a new one
93 * @param {int32_t} w1 Width of the bin to allocate
94 * @param {int32_t} h1 Height of the bin to allocate
95 * @returns {Bin*} `Bin` pointer with `id`, `x`, `y`, `w`, `h` members
96 *
97 * @example
98 * Bin* result = shelf.alloc(-1, 12, 16);
99 */
100 Bin* alloc(int32_t id, int32_t w1, int32_t h1) {
101 if (w1 > wfree_ || h1 > h_) {
102 return nullptr;
103 }
104 int32_t x1 = x_;
105 x_ += w1;
106 wfree_ -= w1;
107 bins_.emplace_back(args&: id, args&: w1, args&: h1, args&: w1, args&: h_, args&: x1, args&: y_);
108 return &bins_.back();
109 }
110
111
112 /**
113 * Resize the shelf.
114 *
115 * @param {int32_t} w1 Requested new width of the shelf
116 * @returns {bool} `true` if resize succeeded, `false` if failed
117 *
118 * @example
119 * shelf.resize(512);
120 */
121 bool resize(int32_t w1) {
122 wfree_ += (w1 - w_);
123 w_ = w1;
124 return true;
125 }
126
127 int32_t x() const { return x_; }
128 int32_t y() const { return y_; }
129 int32_t w() const { return w_; }
130 int32_t h() const { return h_; }
131 int32_t wfree() const { return wfree_; }
132
133private:
134 int32_t x_;
135 int32_t y_;
136 int32_t w_;
137 int32_t h_;
138 int32_t wfree_;
139
140 std::deque<Bin> bins_;
141};
142
143
144
145class ShelfPack {
146public:
147
148 struct ShelfPackOptions {
149 inline ShelfPackOptions() : autoResize(false) { };
150 bool autoResize;
151 };
152
153 struct PackOptions {
154 inline PackOptions() : inPlace(false) { };
155 bool inPlace;
156 };
157
158
159 /**
160 * Create a new ShelfPack bin allocator.
161 *
162 * Uses the Shelf Best Height Fit algorithm from
163 * http://clb.demon.fi/files/RectangleBinPack.pdf
164 *
165 * @class ShelfPack
166 * @param {int32_t} [w=64] Initial width of the sprite
167 * @param {int32_t} [h=64] Initial width of the sprite
168 * @param {ShelfPackOptions} [options]
169 * @param {bool} [options.autoResize=false] If `true`, the sprite will automatically grow
170 *
171 * @example
172 * ShelfPack::ShelfPackOptions options;
173 * options.autoResize = false;
174 * ShelfPack sprite = new ShelfPack(64, 64, options);
175 */
176 explicit ShelfPack(int32_t w = 0, int32_t h = 0, const ShelfPackOptions &options = ShelfPackOptions{}) {
177 width_ = w > 0 ? w : 64;
178 height_ = h > 0 ? h : 64;
179 autoResize_ = options.autoResize;
180 maxId_ = 0;
181 }
182
183
184 /**
185 * Batch pack multiple bins into the sprite.
186 *
187 * @param {vector<Bin>} bins Array of requested bins - each object should have `w`, `h` values
188 * @param {PackOptions} [options]
189 * @param {bool} [options.inPlace=false] If `true`, the supplied bin objects will be updated inplace with `x` and `y` values
190 * @returns {vector<Bin*>} Array of Bin pointers - each bin is a struct with `x`, `y`, `w`, `h` values
191 *
192 * @example
193 * std::vector<Bin> moreBins;
194 * moreBins.emplace_back(-1, 12, 24);
195 * moreBins.emplace_back(-1, 12, 12);
196 * moreBins.emplace_back(-1, 10, 10);
197 *
198 * ShelfPack::PackOptions options;
199 * options.inPlace = true;
200 * std::vector<Bin*> results = sprite.pack(moreBins, options);
201 */
202 std::vector<Bin*> pack(std::vector<Bin> &bins, const PackOptions &options = PackOptions{}) {
203 std::vector<Bin*> results;
204
205 for (auto& bin : bins) {
206 if (bin.w > 0 && bin.h > 0) {
207 Bin* allocation = packOne(id: bin.id, w: bin.w, h: bin.h);
208 if (!allocation) {
209 continue;
210 }
211 if (options.inPlace) {
212 bin.id = allocation->id;
213 bin.x = allocation->x;
214 bin.y = allocation->y;
215 }
216 results.push_back(x: allocation);
217 }
218 }
219
220 shrink();
221
222 return results;
223 }
224
225
226 /**
227 * Pack a single bin into the sprite.
228 *
229 * @param {int32_t} id Unique bin identifier, pass -1 to generate a new one
230 * @param {int32_t} w Width of the bin to allocate
231 * @param {int32_t} h Height of the bin to allocate
232 * @returns {Bin*} Pointer to a packed Bin with `id`, `x`, `y`, `w`, `h` members
233 *
234 * @example
235 * Bin* result = sprite.packOne(-1, 12, 16);
236 */
237 Bin* packOne(int32_t id, int32_t w, int32_t h) {
238 int32_t y = 0;
239 int32_t waste = 0;
240 struct {
241 Shelf* pshelf = nullptr;
242 Bin* pfreebin = nullptr;
243 int32_t waste = std::numeric_limits<std::int32_t>::max();
244 } best;
245
246 // if id was supplied, attempt a lookup..
247 if (id != -1) {
248 Bin* pbin = getBin(id);
249 if (pbin) { // we packed this bin already
250 ref(bin&: *pbin);
251 return pbin;
252 }
253 maxId_ = std::max(a: id, b: maxId_);
254 } else {
255 id = ++maxId_;
256 }
257
258 // First try to reuse a free bin..
259 for (auto& freebin : freebins_) {
260 // exactly the right height and width, use it..
261 if (h == freebin->maxh && w == freebin->maxw) {
262 return allocFreebin(bin: freebin, id, w, h);
263 }
264 // not enough height or width, skip it..
265 if (h > freebin->maxh || w > freebin->maxw) {
266 continue;
267 }
268 // extra height or width, minimize wasted area..
269 if (h <= freebin->maxh && w <= freebin->maxw) {
270 waste = (freebin->maxw * freebin->maxh) - (w * h);
271 if (waste < best.waste) {
272 best.waste = waste;
273 best.pfreebin = freebin;
274 }
275 }
276 }
277
278 // Next find the best shelf
279 for (auto& shelf : shelves_) {
280 y += shelf.h();
281
282 // not enough width on this shelf, skip it..
283 if (w > shelf.wfree()) {
284 continue;
285 }
286 // exactly the right height, pack it..
287 if (h == shelf.h()) {
288 return allocShelf(shelf, id, w, h);
289 }
290 // not enough height, skip it..
291 if (h > shelf.h()) {
292 continue;
293 }
294 // extra height, minimize wasted area..
295 if (h < shelf.h()) {
296 waste = (shelf.h() - h) * w;
297 if (waste < best.waste) {
298 best.waste = waste;
299 best.pshelf = &shelf;
300 }
301 }
302 }
303
304 if (best.pfreebin) {
305 return allocFreebin(bin: best.pfreebin, id, w, h);
306 }
307
308 if (best.pshelf) {
309 return allocShelf(shelf&: *best.pshelf, id, w, h);
310 }
311
312 // No free bins or shelves.. add shelf..
313 if (h <= (height_ - y) && w <= width_) {
314 shelves_.emplace_back(args&: y, args&: width_, args&: h);
315 return allocShelf(shelf&: shelves_.back(), id, w, h);
316 }
317
318 // No room for more shelves..
319 // If `autoResize` option is set, grow the sprite as follows:
320 // * double whichever sprite dimension is smaller (`w1` or `h1`)
321 // * if sprite dimensions are equal, grow width before height
322 // * accomodate very large bin requests (big `w` or `h`)
323 if (autoResize_) {
324 int32_t h1, h2, w1, w2;
325
326 h1 = h2 = height_;
327 w1 = w2 = width_;
328
329 if (w1 <= h1 || w > w1) { // grow width..
330 w2 = std::max(a: w, b: w1) * 2;
331 }
332 if (h1 < w1 || h > h1) { // grow height..
333 h2 = std::max(a: h, b: h1) * 2;
334 }
335
336 resize(w: w2, h: h2);
337 return packOne(id, w, h); // retry
338 }
339
340 return nullptr;
341 }
342
343
344 /**
345 *
346 * Shrink the width/height of the sprite to the bare minimum.
347 * Since shelf-pack doubles first width, then height when running out of shelf space
348 * this can result in fairly large unused space both in width and height if that happens
349 * towards the end of bin packing.
350 */
351 void shrink() {
352 if (shelves_.size()) {
353 int32_t w2 = 0;
354 int32_t h2 = 0;
355
356 for (auto& shelf : shelves_) {
357 h2 += shelf.h();
358 w2 = std::max(a: shelf.w() - shelf.wfree(), b: w2);
359 }
360
361 resize(w: w2, h: h2);
362 }
363 }
364
365
366 /**
367 * Return a packed bin given its id, or nullptr if the id is not found
368 *
369 * @param {int32_t} id Unique identifier for this bin,
370 * @returns {Bin*} Pointer to a packed Bin with `id`, `x`, `y`, `w`, `h` members
371 *
372 * @example
373 * Bin* result = sprite.getBin(5);
374 */
375 Bin* getBin(int32_t id) {
376 std::map<int32_t, Bin*>::iterator it = usedbins_.find(x: id);
377 return (it == usedbins_.end()) ? nullptr : it->second;
378 }
379
380
381 /**
382 * Increment the ref count of a bin and update statistics.
383 *
384 * @param {Bin&} bin Bin reference
385 * @returns {int32_t} New refcount of the bin
386 *
387 * @example
388 * Bin* bin = sprite.getBin(5);
389 * if (bin) {
390 * sprite.ref(*bin);
391 * }
392 */
393 int32_t ref(Bin& bin) {
394 if (++bin.refcount_ == 1) { // a new Bin.. record height in stats historgram..
395 int32_t h = bin.h;
396 stats_[h] = (stats_[h] | 0) + 1;
397 }
398
399 return bin.refcount_;
400 };
401
402
403 /**
404 * Decrement the ref count of a bin and update statistics.
405 * The bin will be automatically marked as free space once the refcount reaches 0.
406 * Memory for the bin is not freed, as unreferenced bins may be reused later.
407 *
408 * @param {Bin&} bin Bin reference
409 * @returns {int32_t} New refcount of the bin
410 *
411 * @example
412 * Bin* bin = sprite.getBin(5);
413 * if (bin) {
414 * sprite.unref(*bin);
415 * }
416 */
417 int32_t unref(Bin& bin) {
418 if (bin.refcount_ == 0) {
419 return 0;
420 }
421
422 if (--bin.refcount_ == 0) {
423 stats_[bin.h]--;
424 usedbins_.erase(x: bin.id);
425 freebins_.push_back(x: &bin);
426 }
427
428 return bin.refcount_;
429 }
430
431
432 /**
433 * Clear the sprite and reset statistics.
434 *
435 * @example
436 * sprite.clear();
437 */
438 void clear() {
439 shelves_.clear();
440 freebins_.clear();
441 usedbins_.clear();
442 stats_.clear();
443 maxId_ = 0;
444 }
445
446
447 /**
448 * Resize the sprite.
449 *
450 * @param {int32_t} w Requested new sprite width
451 * @param {int32_t} h Requested new sprite height
452 * @returns {bool} `true` if resize succeeded, `false` if failed
453 *
454 * @example
455 * sprite.resize(256, 256);
456 */
457 bool resize(int32_t w, int32_t h) {
458 width_ = w;
459 height_ = h;
460 for (auto& shelf : shelves_) {
461 shelf.resize(w1: width_);
462 }
463 return true;
464 }
465
466 int32_t width() const { return width_; }
467 int32_t height() const { return height_; }
468
469
470private:
471
472 /**
473 * Called by packOne() to allocate a bin by reusing an existing freebin
474 *
475 * @private
476 * @param {Bin*} bin Pointer to a freebin to reuse
477 * @param {int32_t} w Width of the bin to allocate
478 * @param {int32_t} h Height of the bin to allocate
479 * @param {int32_t} id Unique identifier for this bin
480 * @returns {Bin*} Pointer to a Bin with `id`, `x`, `y`, `w`, `h` properties
481 *
482 * @example
483 * Bin* bin = sprite.allocFreebin(pfreebin, 12, 16, 5);
484 */
485 Bin* allocFreebin(Bin* bin, int32_t id, int32_t w, int32_t h) {
486 freebins_.erase(first: std::remove(first: freebins_.begin(), last: freebins_.end(), value: bin), last: freebins_.end());
487 bin->id = id;
488 bin->w = w;
489 bin->h = h;
490 bin->refcount_ = 0;
491 usedbins_[id] = bin;
492 ref(bin&: *bin);
493 return bin;
494 }
495
496
497 /**
498 * Called by `packOne() to allocate bin on an existing shelf
499 * Memory for the bin is allocated on the heap by `shelf.alloc()`
500 *
501 * @private
502 * @param {Shelf&} shelf Reference to the shelf to allocate the bin on
503 * @param {int32_t} w Width of the bin to allocate
504 * @param {int32_t} h Height of the bin to allocate
505 * @param {int32_t} id Unique identifier for this bin
506 * @returns {Bin*} Pointer to a Bin with `id`, `x`, `y`, `w`, `h` properties
507 *
508 * @example
509 * Bin* bin = sprite.allocShelf(shelf, 12, 16, 5);
510 */
511 Bin* allocShelf(Shelf& shelf, int32_t id, int32_t w, int32_t h) {
512 Bin* pbin = shelf.alloc(id, w1: w, h1: h);
513 if (pbin) {
514 usedbins_[id] = pbin;
515 ref(bin&: *pbin);
516 }
517 return pbin;
518 }
519
520
521 int32_t width_;
522 int32_t height_;
523 int32_t maxId_;
524 bool autoResize_;
525
526 std::deque<Shelf> shelves_;
527 std::map<int32_t, Bin*> usedbins_;
528 std::vector<Bin*> freebins_;
529 std::map<int32_t, int32_t> stats_;
530};
531
532
533} // namespace mapbox
534
535#endif
536

source code of qtlocation/src/3rdparty/mapbox-gl-native/deps/shelf-pack/2.1.1/include/mapbox/shelf-pack.hpp