GapFreeShuffle

gap-free-shuffle.js

(function(window) {
    'use strict';


    /**
     * Creates new instance of GapFreeShuffle that extends Shuffle (https://vestride.github.io/Shuffle/)
     * Implements a sorting algorithm that tries to fill empty gaps with subsequent blocks
     * See https://github.com/Vestride/Shuffle/issues/189
     *
     * @param {Element} element An element which is the parent container for the grid items.
     * @param {Object} [options=Shuffle.options] Options object.
     *
     *
     * @constructor
     */
    var GapFreeShuffle = function(element, options) {
        this._maxY = 0;
        Shuffle.call(this, element, options);
    };

    GapFreeShuffle.prototype = Object.create(Shuffle.prototype);
    GapFreeShuffle.prototype.constructor = GapFreeShuffle;


    /**
     * Gets the visible elements, sorts them, and passes them to layout.
     * @param {Object} [sortOptions] The options object to pass to `sorter`.
     */
    GapFreeShuffle.prototype.sort = function(sortOptions) {
        if (!this.isEnabled) {
            return;
        }

        this._resetCols();

        var items = this._getFilteredItems();

        // add data order attributes once filtering is finished and sorting is about to start
        items = this._getSortedItems(items);

        this._layout(items);

        // `_layout` always happens after `_shrink`, so it's safe to process the style
        // queue here with styles from the shrink method.
        this._processQueue();

        // Adjust the height of the container.
        this._setContainerSize();

        this.lastSort = sortOptions;
    };

    /**
     * Sets the order of the items and adds the position
     *
     * @param {ShuffleItem[]} items Array of filtered shuffle items
     * @returns {ShuffleItem[]} ordered list of items
     * @private
     */
    GapFreeShuffle.prototype._getSortedItems = function(items) {
        this._maxY = 0;
        var blocks = [];

        // add each item to the blocks to be fitted
        items.forEach(function(item) {
            if (item.isVisible) {
                var size =  Shuffle.getSize(item.element, true);
                blocks.push({width: size.width, height: size.height, item: item});
            }
        });

        // fit all blocks into the container
        var fit = this._fitBlocks(this.containerWidth, Number.MAX_VALUE, blocks);

        var sortedItems = [];
        fit.fittedBlocksOrdered.forEach(function(block){
            sortedItems.push(block.item);
            block.item.position = new Shuffle.Point(block.x, block.y);
            if (block.y + block.height > this._maxY) {
                this._maxY = block.y + block.height;
            }
        }.bind(this));

        return items;
    };

    /**
     * Return an array of Point instances representing the future positions of
     * each item.
     * @param {ShuffleItem[]} items Array of sorted shuffle items.
     * @return {Point[]}
     * @private
     */
    GapFreeShuffle.prototype._getNextPositions = function(items) {
        var positions = [];
        items.forEach(function(item){
            positions.push(item.position);
        });
        return positions;
    };

    /**
     * Based on the column heights, it returns the biggest one.
     * @return {number}
     * @private
     */
    GapFreeShuffle.prototype._getContainerSize = function() {
        return this._maxY;
    };

    /**
     * Fits blocks in a container given by containerWidth and containerHeight.
     *
     * Each block is placed at the first position found at a top right or bottom left corner
     * of already fitted blocks where it does not overlap the already fitted blocks.
     * Therefore, the initial order of the blocks is respected as much as possible.
     *
     * @param containerWidth
     * @param containerHeight
     * @param blocks
     * @returns {{fittedBlocks: block[], fittedBlocksOrdered: block[]}}
     */
    GapFreeShuffle.prototype._fitBlocks = function(containerWidth, containerHeight, blocks) {
        var fittedBlocks = [];
        var tolerance = 0.5;


        /**
         * Returns whether a block overlaps with the fittedBlocks or does not fit whithin the container
         * @param block
         * @param x
         * @param y
         * @returns {boolean}
         */
        var blockOverlaps = function(block,x,y) {
            var blockPositionLimits = {
                x: {
                    min: x,
                    max: x+block.width
                },
                y: {
                    min: y,
                    max: y+block.height
                }
            };
            // if the block exceeds the container dimensions, return true
            if (blockPositionLimits.x.max > containerWidth+tolerance || blockPositionLimits.y.max > containerHeight+tolerance) {
                return true;
            }

            // return whether the block overlaps with any of the fittedBlocks
            return fittedBlocks.some(function(fittedBlock){
                var fittedBlockPositionLimits = {
                    x: {
                        min: fittedBlock.x,
                        max: fittedBlock.x+fittedBlock.width
                    },
                    y: {
                        min: fittedBlock.y,
                        max: fittedBlock.y+fittedBlock.height
                    }
                };
                // check if the min and max blockPositionLimits are whithin the fittedBlockPositionLimits
                // for both x and y coordinates
                return (
                    blockPositionLimits.x.min - (fittedBlockPositionLimits.x.max - tolerance) < 0
                    && blockPositionLimits.x.max - (fittedBlockPositionLimits.x.min + tolerance) > 0
                    && blockPositionLimits.y.min - (fittedBlockPositionLimits.y.max - tolerance) < 0
                    && blockPositionLimits.y.max - (fittedBlockPositionLimits.y.min + tolerance) > 0
                );
            })
        };
        
        
        var blockSorting = function(a, b){
            var ax = Math.round(a.x/10)*10;
            var ay = Math.round(a.y/10)*10;
            var bx = Math.round(b.x/10)*10;
            var by = Math.round(b.y/10)*10;
            if (ay < by) {
                return -1;
            } else if (ay === by && ax < bx) {
                return -1;
            } else if (ay === by && ax > bx) {
                return 1;
            } else if (ay > by) {
                return 1;
            } else {
                return 0;
            }
        };

        // try to fit each block
        blocks.forEach(function(block){
            if (fittedBlocks.length === 0) {
                block.x = 0;
                block.y = 0;
                fittedBlocks.push(block);
                return;
            }

            var possibleNewPositions = [];

            // try to place the block at the top right corner, bottom left corner or beginning of the bottom line
            // of any of fittedBlocks and check the overlap.
            // if it does not overlap, add that position to the possibleNewPositions
            fittedBlocks.forEach(function(fittedBlock) {
                if (!blockOverlaps(block, fittedBlock.x+fittedBlock.width, fittedBlock.y)) {
                    // block does not overlap any of the fittedBlocks if placed at the top right corner of the
                    // current fittedBlock, so we could use this position
                    possibleNewPositions.push({
                        x: fittedBlock.x+fittedBlock.width,
                        y: fittedBlock.y,
                    });
                }
                if (!blockOverlaps(block, fittedBlock.x, fittedBlock.y+fittedBlock.height)) {
                    // block does not overlap any of the fittedBlocks if placed at the bottom left corner of the
                    // current fittedBlock, so we could use this position
                    possibleNewPositions.push({
                        x: fittedBlock.x,
                        y: fittedBlock.y+fittedBlock.height,
                    });
                }
                if (!blockOverlaps(block, 0, fittedBlock.y+fittedBlock.height)) {
                    // block does not overlap any of the fittedBlocks if placed at the beginning of the row
                    // at the bottom of the current fittedBlock, so we could use this position
                    possibleNewPositions.push({
                        x: 0,
                        y: fittedBlock.y+fittedBlock.height,
                    });
                }
                // otherwise, no position found without overlapping any of the fittedBlocks,
                // so continue to next fittedBlock
            });

            if (possibleNewPositions.length > 0) {
                // sort possible new positions by block sorting
                possibleNewPositions.sort(blockSorting);

                // get the first possible position, which is the best one according to the blockSorting function
                var newPosition = possibleNewPositions[0];
                block.x = newPosition.x;
                block.y = newPosition.y;
                fittedBlocks.push(block);
            }
        });

        var fittedBlocksOrdered = fittedBlocks;
        // sort the fitted blocks by y and x position
        // round to 10px
        fittedBlocksOrdered.sort(blockSorting);

        return {
            fittedBlocks: fittedBlocks,
            fittedBlocksOrdered: fittedBlocksOrdered
        };
    };

    /* Make GapFreeShuffle public */
    window.GapFreeShuffle = GapFreeShuffle;
})(window);