shrimp2t/GridJS.html

## GridJS.html
<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <title>Test Algorithm </title>

    <script type="text/javascript">
        // http://underscorejs.org/underscore-min.js

        var flag = [], backupFlag = [];
        var maxCol = 12;

        //flag = [0,2,1,1,0,0,2,1,1,1,0,0];
        flag = [0,'A',1,1,'B',1,1,'C',1,1,1,0];
        backupFlag = flag.slice();


        addItemToFlag = function( node ){
            var x = node.x, w = node.w;
            var el = node.el;

            for ( var i = x; i < x+w ; i++ ) {
                 if( i === x ) {
                     flag[ i ] = el; // mean start item item
                 } else {
                     flag[ i ] = 1;
                 }
            }
        };

        removeNode = function( node ){
            var x = node.x, w = node.w;
            var el = node.el;
            for ( var i = x; i < x+w ; i++ ) {
                flag[ i ] = 0;
            }
        };

        function getEmptySlots( ) {
            var emptySlots = 0;
            for( var i = 0; i< maxCol; i++ ) {
                if ( flag[ i ] === 0 ) {
                    emptySlots ++;
                }
            }

            return emptySlots;
        }

        function getRightEmptySlotFromX(x, stopWhenNotEmpty){
            var emptySlots = 0;
            for( var i = x; i < maxCol; i++ ) {
                if ( flag[ i ] === 0 ) {
                    emptySlots ++;
                } else {
                    if ( stopWhenNotEmpty ) {
                        return emptySlots;
                    }
                }
            }
            return emptySlots;
        }

        function getLeftEmptySlotFromX(x, stopWhenNotEmpty ){
            var emptySlots = 0;
            if ( typeof stopWhenNotEmpty === "undefined" ) {
                stopWhenNotEmpty = false;
            }
            for( var i = x; i >= 0; i-- ) {
                if ( flag[ i ] === 0 ) {
                    emptySlots ++;
                } else {
                    if ( stopWhenNotEmpty ) {
                        return emptySlots;
                    }
                }
            }
            return emptySlots;
        }

        function isEmptyX( x ){
            if ( flag[ x ] === 0 ) {
               return true;
            }
            return false;
        }

        function checkEnoughSpaceFromX(x, w){
            var check = true;
            var i = x;
            var j;
            while ( i < x + w && check ) {
                if ( flag[ i ] !== 0 ) {
                    //check = false;
                    return false;
                }
                i++;
            }
            return check;
        }

        function getPrevBlock( x ){
            if ( x < 0 ) {
                return {
                    x: -1,
                    w: 1
                }
            }

            var i, _x = -1, _xw, found;

            if ( flag[x] <= 1  ) {
                i= x;
                found = false;
                while ( i >= 0 && ! found ) {
                    if ( flag[i] !== 1 && flag[i] !== 0 ) {
                        _x = i;
                        found = true;
                    }
                    i--;
                }
            } else {
                _x = x;
            }
            // tìm kiếm độ rộng của chuỗi này
            i = _x + 1;
            _xw = _x; // chiều rộng nhỏ nhất là môt

            while( flag[ i ] === 1 ) {
                _xw ++ ;
                i++;
            }
            return {
                x: _x,
                w: ( _xw + 1 ) - _x
            }
        }

        function getNextBlock( x ){
            var i, _x = -1, _xw, found;

            if ( flag[x] < maxCol  ) {
                i = x;
                found = false;
                while ( i < maxCol && ! found ) {
                    if ( flag[i] !== 1 && flag[i] !== 0 ) {
                        _x = i;
                        found = true;
                    }
                    i++;
                }
            } else {
                _x = x;
            }
            // tìm kiếm độ rộng của chuỗi này
            i = _x + 1;
            _xw = _x; // chiều rộng nhỏ nhất là môt

            while( flag[ i ] === 1 ) {
                _xw ++ ;
                i++;
            }
            return {
                x: _x,
                w: ( _xw + 1 ) - _x
            }
        }


        function moveAllItemsFromXToLeft( x, number ){
            var backupFlag = flag.slice();
            var maxNumber = getLeftEmptySlotFromX( x );

            if ( maxNumber === 0 ) {
                return number;
            }
            var prev=  getPrevBlock( x );
            var newX = prev.x >= 0 ? prev.x + prev.w - 1 : x;
            var nMove = number;
            if ( number > maxNumber ) {
                nMove = maxNumber;
            } else {
                nMove = number;
            }

            // Tim vi tri x trống về bên trái
            var xE = 0, c = 0, i = newX;
            while ( c <= nMove && i >= 0 ) {
                if ( flag[i] === 0 ) {
                    c++;
                    xE = i;
                }
                i--;
            }

            // vị trí cần di chuyển tới là x và loại bỏ mọi khoảng trống trừ x đến xE
            var flagNoEmpty = [], j = 0;
            for ( i =  xE; i <= newX; i++ ) {
                flag[i] =0;
                if ( backupFlag[ i ] !== 0 ) {
                    flagNoEmpty[j] = backupFlag[ i ];
                    j++;
                }
            }

            j = 0;
            for ( i = xE; i<= newX; i++ ){
                if ( typeof flagNoEmpty[ j ] !== "undefined" ) {
                    flag[ i ] = flagNoEmpty[ j ];
                } else {
                    flag[ i ] = 0;
                }
                j++;
            }

            var left = number - nMove;
            return left;

        }

        function moveAllItemsFromXToRight( x, number ){
            var backupFlag = flag.slice();
            var maxNumber = getRightEmptySlotFromX( x );
            if ( maxNumber === 0 ) {
                return number;
            }


            var prev = getPrevBlock( x );
            var newX = prev.x >= 0 ? prev.x : x;
            var nMove = number;
            if ( number <= maxNumber ) {
                nMove = number;
            } else {
                nMove = maxNumber;
            }

            // Tim vi tri x trống về bên trái
            var xE = x, c = 0, i = newX;
            while ( c < nMove && i < maxCol ) {
                if ( flag[i] === 0 ) {
                    c++;
                    xE = i;
                }
                i++;
            }

            // vị trí cần di chuyển tới là x và loại bỏ mọi khoảng trống trừ x đến xE
            var flagNoEmpty = [], j = 0;

            for ( i = newX ; i <= xE; i++ ) {
                flag[i] =0;
                if ( backupFlag[ i ] !== 0 ) {
                    flagNoEmpty[j] = backupFlag[ i ];
                    j++;
                }
            }

            j = flagNoEmpty.length - 1;
            for ( i = xE; i >= newX; i-- ){
                if ( typeof flagNoEmpty[ j ] !== "undefined" ) {
                    flag[ i ] = flagNoEmpty[ j ];
                } else {
                    flag[ i ] = 0;
                }
                j--;
            }

            var left = number - nMove ;
            return left;

        }


        // Chèn vào trong danh sách giới hạn với 1 phẩn tử và có độ vị trí tại X và độ dài là w
        insertToFlag = function( node ){
            var x = node.x, w = node.w;
            var emptySlots = getEmptySlots( );
            // không còn bất kỳ chỗ trống nào có thể thêm dc
            if( emptySlots <= 0 ) {
                return false;
            }

            var remain = moveAllItemsFromXToRight (x, w );
            if (remain > 0) {
                remain = moveAllItemsFromXToLeft(x, remain);
            }

            var newX = x;
            var i;
            var found = false;
            var le = 0 ;
            var re = 0;

            while( w > 1 ) {
                // Nếu số chỗ trống lớn hơn hoặc  = chiều rộng của item
                if ( emptySlots >= w ) {
                    // Nếu tại vị trí hiện tại mà đủ chỗ trống
                    if (checkEnoughSpaceFromX(x, w)) {
                        addItemToFlag(node);
                        return true;
                    }

                    found = false;
                    le = getLeftEmptySlotFromX(x, true);
                   // re = getRightEmptySlotFromX(x, true);
                    // Nếu trỗ trông bên trái nhiều hơn bên phải
                    newX = x - le;
                    // tìm kiếm từ vị trí trống từ new sang bên phải xem có chỗ nào chèn dc ko ?
                    i = newX;
                    while (i < maxCol && !found) {
                        if (checkEnoughSpaceFromX(i, w)) {
                            addItemToFlag({el: node.el, x: i, w: w});
                            return true;
                        }
                        i++;
                    }
                }
                w --;
            }
            return false;
        };

        /**
         * Dổi chỗ 2 item trong 1 hàng
         * @param x Vị trị bắt đầu của item dc thay đổi
         * @param newX Vị trí của item chuyển đến
         */
        function swap( node, newX ){
            var x = node.x;
            var block2 = getPrevBlock( newX );
            backupFlag = flag.slice(); // backup


            removeNode( node );

            console.log( 'Rm' );
            console.log( flag );
            insertToFlag( { el: node.el, x: newX, w: node.w } );
            console.log( 'swap' );
            console.log( flag );

            // Nếu newX có item
            if ( block2.x > -1 ) {

            }


        }

        backupFlag = flag.slice(); // backup before do everything

        console.log( flag );
        // Đổi chỗ
        swap( { el: 'C', x: 7, w: 4 }, 0 );


        /*
        var r = insertToFlag( { el: 'F', x: 5, w: 5 } );
        if ( ! r ) {
            console.log( 'Không đủ chỗ để thêm' );
        } else {
            console.log( 'Có đủ chỗ , đa thêm' );
        }
        */


        console.log( flag );


    </script>
</head>
<body>
Test HTML
</body>
</html>
	<!DOCTYPE html>
	<html lang="en">
	<head>
	<meta charset="UTF-8">
	<title>Test Algorithm </title>

	<script type="text/javascript">
	// http://underscorejs.org/underscore-min.js

	var flag = [], backupFlag = [];
	var maxCol = 12;

	//flag = [0,2,1,1,0,0,2,1,1,1,0,0];
	flag = [0,'A',1,1,'B',1,1,'C',1,1,1,0];
	backupFlag = flag.slice();


	addItemToFlag = function( node ){
	var x = node.x, w = node.w;
	var el = node.el;

	for ( var i = x; i < x+w ; i++ ) {
	if( i === x ) {
	flag[ i ] = el; // mean start item item
	} else {
	flag[ i ] = 1;
	}
	}
	};

	removeNode = function( node ){
	var x = node.x, w = node.w;
	var el = node.el;
	for ( var i = x; i < x+w ; i++ ) {
	flag[ i ] = 0;
	}
	};

	function getEmptySlots( ) {
	var emptySlots = 0;
	for( var i = 0; i< maxCol; i++ ) {
	if ( flag[ i ] === 0 ) {
	emptySlots ++;
	}
	}

	return emptySlots;
	}

	function getRightEmptySlotFromX(x, stopWhenNotEmpty){
	var emptySlots = 0;
	for( var i = x; i < maxCol; i++ ) {
	if ( flag[ i ] === 0 ) {
	emptySlots ++;
	} else {
	if ( stopWhenNotEmpty ) {
	return emptySlots;
	}
	}
	}
	return emptySlots;
	}

	function getLeftEmptySlotFromX(x, stopWhenNotEmpty ){
	var emptySlots = 0;
	if ( typeof stopWhenNotEmpty === "undefined" ) {
	stopWhenNotEmpty = false;
	}
	for( var i = x; i >= 0; i-- ) {
	if ( flag[ i ] === 0 ) {
	emptySlots ++;
	} else {
	if ( stopWhenNotEmpty ) {
	return emptySlots;
	}
	}
	}
	return emptySlots;
	}

	function isEmptyX( x ){
	if ( flag[ x ] === 0 ) {
	return true;
	}
	return false;
	}

	function checkEnoughSpaceFromX(x, w){
	var check = true;
	var i = x;
	var j;
	while ( i < x + w && check ) {
	if ( flag[ i ] !== 0 ) {
	//check = false;
	return false;
	}
	i++;
	}
	return check;
	}

	function getPrevBlock( x ){
	if ( x < 0 ) {
	return {
	x: -1,
	w: 1
	}
	}

	var i, _x = -1, _xw, found;

	if ( flag[x] <= 1 ) {
	i= x;
	found = false;
	while ( i >= 0 && ! found ) {
	if ( flag[i] !== 1 && flag[i] !== 0 ) {
	_x = i;
	found = true;
	}
	i--;
	}
	} else {
	_x = x;
	}
	// tìm kiếm độ rộng của chuỗi này
	i = _x + 1;
	_xw = _x; // chiều rộng nhỏ nhất là môt

	while( flag[ i ] === 1 ) {
	_xw ++ ;
	i++;
	}
	return {
	x: _x,
	w: ( _xw + 1 ) - _x
	}
	}

	function getNextBlock( x ){
	var i, _x = -1, _xw, found;

	if ( flag[x] < maxCol ) {
	i = x;
	found = false;
	while ( i < maxCol && ! found ) {
	if ( flag[i] !== 1 && flag[i] !== 0 ) {
	_x = i;
	found = true;
	}
	i++;
	}
	} else {
	_x = x;
	}
	// tìm kiếm độ rộng của chuỗi này
	i = _x + 1;
	_xw = _x; // chiều rộng nhỏ nhất là môt

	while( flag[ i ] === 1 ) {
	_xw ++ ;
	i++;
	}
	return {
	x: _x,
	w: ( _xw + 1 ) - _x
	}
	}


	function moveAllItemsFromXToLeft( x, number ){
	var backupFlag = flag.slice();
	var maxNumber = getLeftEmptySlotFromX( x );

	if ( maxNumber === 0 ) {
	return number;
	}
	var prev= getPrevBlock( x );
	var newX = prev.x >= 0 ? prev.x + prev.w - 1 : x;
	var nMove = number;
	if ( number > maxNumber ) {
	nMove = maxNumber;
	} else {
	nMove = number;
	}

	// Tim vi tri x trống về bên trái
	var xE = 0, c = 0, i = newX;
	while ( c <= nMove && i >= 0 ) {
	if ( flag[i] === 0 ) {
	c++;
	xE = i;
	}
	i--;
	}

	// vị trí cần di chuyển tới là x và loại bỏ mọi khoảng trống trừ x đến xE
	var flagNoEmpty = [], j = 0;
	for ( i = xE; i <= newX; i++ ) {
	flag[i] =0;
	if ( backupFlag[ i ] !== 0 ) {
	flagNoEmpty[j] = backupFlag[ i ];
	j++;
	}
	}

	j = 0;
	for ( i = xE; i<= newX; i++ ){
	if ( typeof flagNoEmpty[ j ] !== "undefined" ) {
	flag[ i ] = flagNoEmpty[ j ];
	} else {
	flag[ i ] = 0;
	}
	j++;
	}

	var left = number - nMove;
	return left;

	}

	function moveAllItemsFromXToRight( x, number ){
	var backupFlag = flag.slice();
	var maxNumber = getRightEmptySlotFromX( x );
	if ( maxNumber === 0 ) {
	return number;
	}


	var prev = getPrevBlock( x );
	var newX = prev.x >= 0 ? prev.x : x;
	var nMove = number;
	if ( number <= maxNumber ) {
	nMove = number;
	} else {
	nMove = maxNumber;
	}

	// Tim vi tri x trống về bên trái
	var xE = x, c = 0, i = newX;
	while ( c < nMove && i < maxCol ) {
	if ( flag[i] === 0 ) {
	c++;
	xE = i;
	}
	i++;
	}

	// vị trí cần di chuyển tới là x và loại bỏ mọi khoảng trống trừ x đến xE
	var flagNoEmpty = [], j = 0;

	for ( i = newX ; i <= xE; i++ ) {
	flag[i] =0;
	if ( backupFlag[ i ] !== 0 ) {
	flagNoEmpty[j] = backupFlag[ i ];
	j++;
	}
	}

	j = flagNoEmpty.length - 1;
	for ( i = xE; i >= newX; i-- ){
	if ( typeof flagNoEmpty[ j ] !== "undefined" ) {
	flag[ i ] = flagNoEmpty[ j ];
	} else {
	flag[ i ] = 0;
	}
	j--;
	}

	var left = number - nMove ;
	return left;

	}



	// Chèn vào trong danh sách giới hạn với 1 phẩn tử và có độ vị trí tại X và độ dài là w
	insertToFlag = function( node ){
	var x = node.x, w = node.w;
	var emptySlots = getEmptySlots( );
	// không còn bất kỳ chỗ trống nào có thể thêm dc
	if( emptySlots <= 0 ) {
	return false;
	}

	var remain = moveAllItemsFromXToRight (x, w );
	if (remain > 0) {
	remain = moveAllItemsFromXToLeft(x, remain);
	}

	var newX = x;
	var i;
	var found = false;
	var le = 0 ;
	var re = 0;

	while( w > 1 ) {
	// Nếu số chỗ trống lớn hơn hoặc = chiều rộng của item
	if ( emptySlots >= w ) {
	// Nếu tại vị trí hiện tại mà đủ chỗ trống
	if (checkEnoughSpaceFromX(x, w)) {
	addItemToFlag(node);
	return true;
	}

	found = false;
	le = getLeftEmptySlotFromX(x, true);
	// re = getRightEmptySlotFromX(x, true);
	// Nếu trỗ trông bên trái nhiều hơn bên phải
	newX = x - le;
	// tìm kiếm từ vị trí trống từ new sang bên phải xem có chỗ nào chèn dc ko ?
	i = newX;
	while (i < maxCol && !found) {
	if (checkEnoughSpaceFromX(i, w)) {
	addItemToFlag({el: node.el, x: i, w: w});
	return true;
	}
	i++;
	}
	}
	w --;
	}
	return false;
	};

	/**
	* Dổi chỗ 2 item trong 1 hàng
	* @param x Vị trị bắt đầu của item dc thay đổi
	* @param newX Vị trí của item chuyển đến
	*/
	function swap( node, newX ){
	var x = node.x;
	var block2 = getPrevBlock( newX );
	backupFlag = flag.slice(); // backup


	removeNode( node );

	console.log( 'Rm' );
	console.log( flag );
	insertToFlag( { el: node.el, x: newX, w: node.w } );
	console.log( 'swap' );
	console.log( flag );

	// Nếu newX có item
	if ( block2.x > -1 ) {

	}


	}

	backupFlag = flag.slice(); // backup before do everything

	console.log( flag );
	// Đổi chỗ
	swap( { el: 'C', x: 7, w: 4 }, 0 );


	/*
	var r = insertToFlag( { el: 'F', x: 5, w: 5 } );
	if ( ! r ) {
	console.log( 'Không đủ chỗ để thêm' );
	} else {
	console.log( 'Có đủ chỗ , đa thêm' );
	}
	*/


	console.log( flag );




	</script>
	</head>
	<body>
	Test HTML
	</body>
	</html>