DevTools: introduce spritesheet assembler.

third_party/WebKit/Source/devtools/scripts/spritesheet_assembler/Packer.js

Index: third_party/WebKit/Source/devtools/scripts/spritesheet_assembler/Packer.js
diff --git a/third_party/WebKit/Source/devtools/scripts/spritesheet_assembler/Packer.js b/third_party/WebKit/Source/devtools/scripts/spritesheet_assembler/Packer.js
new file mode 100644
index 0000000000000000000000000000000000000000..b35d251b0eabcdb27678a258845f1ce501394892
--- /dev/null
+++ b/third_party/WebKit/Source/devtools/scripts/spritesheet_assembler/Packer.js
@@ -0,0 +1,94 @@
+var SVGSpriteSheet = require('./SVGSpriteSheet');
+
+var Packer = {
+  SpriteSortOrder: {
+    // Sort by decreasing of sprite width
+    Width: (a, b) => b.width - a.width || Packer._compareNames(a, b),
+    // Sort by decreasing of sprite height
+    Height: (a, b) => b.height - a.height || Packer._compareNames(a, b),
+    // Sort by decreasing of sprite maxside
+    MaxSide: (a, b) => Math.max(b.width, b.height) - Math.max(a.width, a.height) || Packer._compareNames(a, b),
+    // Sort by decreasing of sprite area
+    Area: (a, b) => b.width * b.height - a.width * a.height || Packer._compareNames(a, b),
+  },
+
+  /**
+   * @param {!SVGSprite} spriteA
+   * @param {!SVGSprite} spriteB
+   * @return {number}
+   */
+  _compareNames: function(spriteA, spriteB) {
+    if (spriteA.filePath < spriteB.filePath)
+      return -1;
+    if (spriteA.filePath > spriteB.filePath)
+      return 1;
+    return 0;
+  },
+
+  /**
+   * @param {!Array<!SVGSprite>} sprites
+   * @param {!Packer.SpriteSortOrder} spriteComparator
+   * @param {number} rightPadding
+   * @param {number} bottomPadding
+   * @return {!SVGSpriteSheet}
+   */
+  packSprites: function(sprites, spriteComparator, rightPadding, bottomPadding) {
+    console.assert(sprites.length, 'cannot create spritesheet with 0 sprites!');
+    sprites.sort(spriteComparator);
+
+    var totalWidth = sprites[0].width + rightPadding;
+    var totalHeight = sprites[0].height + bottomPadding;
+    /** @type {!Map<!SVGSprite, !{x: number, y: number}>} */
+    var positions = new Map();
+
+    var freeSpaces = new Set();
+    freeSpaces.add({x: 0, y: 0, width: totalWidth, height: totalHeight});
+    for (var sprite of sprites) {
+      var spriteWidth = sprite.width + rightPadding;
+      var spriteHeight = sprite.height + bottomPadding;
+      var freeSpace = null;
+      for (var space of freeSpaces) {
+        if (space.width >= spriteWidth && space.height >= spriteHeight) {
+          freeSpace = space;
+          break;
+        }
+      }
+
+      if (!freeSpace) {
+        var canGrowRight = spriteHeight <= totalHeight;
+        var canGrowDown = spriteWidth <= totalWidth;
+        console.assert(canGrowDown || canGrowRight, 'cannot grow spritesheet in either direction!');
+        // Lean towards square sprite sheet.
+        var growRightAspectRatio = Math.abs(totalHeight / (totalWidth + spriteWidth) - 1);
+        var growDownAspectRatio = Math.abs((totalHeight + spriteHeight) / totalWidth - 1);
+        if (!canGrowDown || (canGrowRight && growRightAspectRatio < growDownAspectRatio)) {
+          freeSpace = {x: totalWidth, y: 0, width: spriteWidth, height: totalHeight};
+          totalWidth += spriteWidth;
+        } else {
+          freeSpace = {x: 0, y: totalHeight, width: totalWidth, height: spriteHeight};
+          totalHeight += spriteHeight;
+        }
+      } else {
+        freeSpaces.delete(freeSpace);
+      }
+
+      positions.set(sprite, {x: freeSpace.x, y: freeSpace.y});
+
+      var rightSpace =
+          {x: freeSpace.x + spriteWidth, y: freeSpace.y, width: freeSpace.width - spriteWidth, height: spriteHeight};
+      var downSpace = {
+        x: freeSpace.x,
+        y: freeSpace.y + spriteHeight,
+        width: freeSpace.width,
+        height: freeSpace.height - spriteHeight
+      };
+      if (rightSpace.width && rightSpace.height)
+        freeSpaces.add(rightSpace);
+      if (downSpace.width && downSpace.height)
+        freeSpaces.add(downSpace);
+    }
+    return new SVGSpriteSheet(totalWidth, totalHeight, positions);
+  }
+};
+
+module.exports = Packer;