webCollection
/
test.htm

<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<html>
 <head><title>jack</title>
 <meta http-equiv="Content-Type" content="text/html;charset=utf-8"/>
     <script src="lib.js" type="text/javascript"></script>
 </head>
 <body>
 <div style="width:1000px; height:3000px;">
 <div style="width:100%">
<script type="text/javascript">
    //Class
    function VirtualDom(l, t, w, h, vOrR) {//�����DomԪ�ؽṹ.
        var _ = this;
        this.ele = undefined;
        this.clientLeft = l;
        this.clientTop = t;
        this.clientWidth = w;
        this.clientHeight = h;
        this.index = {};
        if (vOrR == 'R') {
            this.flag = 'R';
        }
        else {
            this.flag = 'V';
        }
        this.createDom = function () {
            var ele = document.createElement("div");
            ele.innerHTML = "[]";
            ele.style.backgroundColor = "yellow";
            ele.style.position = "absolute";
            ele.style.left = _.clientLeft + "px";
            ele.style.top = _.clientTop + "px";
            ele.style.width = _.clientWidth + "px";
            ele.style.height = _.clientHeight + "px";
            document.body.appendChild(ele);
        };
        this.clone = function () {
            return new VirtualDom(_.clientLeft, _.clientTop, _.clientWidth, _.clientHeight, _.flag);
        };

        //获取两个矩形的相交部分形成的矩形．
        // @param {VirtualDom} virDom    :a rectangle
        this.createIntersection = function (virDom) {
            var Xarr = lib.mergeArray([_.clientLeft, _.clientLeft + _.clientWidth], [virDom.clientLeft, virDom.clientLeft + virDom.clientWidth]);
            var Xdif = Xarr[3] - Xarr[0];
            if (Xdif == _.clientWidth + virDom.clientWidth) {//如果在x方向不交汇
                return undefined;
            }

            var Yarr = lib.mergeArray([_.clientTop, _.clientTop + _.clientHeight], [virDom.clientTop, virDom.clientTop + virDom.clientHeight]);
            var Ydif = Yarr[3] - Yarr[0];
            if (Ydif == _.clientHeight + virDom.clientHeight) {//如果在y方向不交汇
                return undefined;
            }

            var intersection = new VirtualDom(Xarr[1], Yarr[1], Xarr[2] - Xarr[1], Yarr[2] - Yarr[1]);
            return intersection;
        };

        this.createComplement = function (virDom) {
            var tmpA = [_.clientLeft, _.clientLeft + _.clientWidth];
            var tmpB = [virDom.clientLeft, virDom.clientLeft + virDom.clientWidth];
            var Xs = lib.mergeArray(tmpA, tmpB);
            var Ys = lib.mergeArray([_.clientTop, _.clientTop + _.clientHeight], [virDom.clientTop, virDom.clientTop + virDom.clientHeight]);
            var complementsInThis = [], complementsInVirDom = [], intersectionInBoth = undefined;
            for (var i = 0; i < Xs.length - 1; i++) {
                for (var j = 0; j < Ys.length - 1; j++) {
                    var l = Xs[i];
                    var t = Ys[j];
                    var w = Xs[i + 1] - Xs[i];
                    var h = Ys[j + 1] - Ys[j];
                    var isInVirDom = (virDom.clientLeft <= l && l + w <= virDom.clientLeft + virDom.clientWidth && virDom.clientTop <= t && t + h <= virDom.clientTop + virDom.clientHeight);
                    var isInThis = (_.clientLeft <= l && l + w <= _.clientLeft + _.clientWidth && _.clientTop <= t && t + h <= _.clientTop + _.clientHeight);
                    if (isInThis && !isInVirDom) {
                        complementsInThis.push(new VirtualDom(l, t, w, h));
                    } else if (!isInThis && isInVirDom) {
                        complementsInVirDom.push(new VirtualDom(l, t, w, h));
                    } else {
                        intersectionInBoth = new VirtualDom(l, t, w, h);
                    }
                }
            }
            return { "complementsInThis": complementsInThis, "complementsInVirDom": complementsInVirDom, "intersectionInBoth": intersectionInBoth };
        };
    }//end class


    function Rectange(x, y, width, height,ele) {//
        var _ = this;
        this.x = x;
        this.y = y;
        this.width = width;
        this.height = height;
        this.ele = ele;
        this.getArea = function () {
            return _.width * _.width;
        };
    };

    function Column() {
        var _ = this;
        this.rows = [];

        this.addRow = function (_row) {
            _.rows.push(_row);
        };

        this.getPreRow = function (_row) {
            for (var i = 0, t; t = _.rows[i]; i++) {
                if (t === _row) {
                    return _.rows[i-1];
                }
            }
        };

        this.getNextRow = function () {
            for (var i = 0, t; t = _.rows[i]; i++) {
                if (t === _row) {
                    return _.rows[i + 1];
                }
            }
        };

        this.getRealDoms = function(){
            var _realDoms = [];
            for (var i = 0, t; t = _.rows[i]; i++) {
                lib.pushArray(_realDoms, t.getRealDoms());
            }
            return _realDoms;
        };
    }

    function Row() {
        var _ = this;
        this.Doms = [];

        this.addDom = function (_dom) {
            _.Doms.push(_dom);
        };

        this.getRealDomsLen = function () {//��ȡʵdom�ĸ���
            for (var i = 0, t; t = _.Doms[i]; i++) {
                if (t.flag == "V") {
                    return i;
                }
            }
            return _.Doms.length;
        };

        this.getRealDoms= function(){
            var _realDoms = [];
            for (var i = 0, t; t = _.Doms[i]; i++) {
                if (t.flag == "R") {
                    _realDoms.push(t);
                }
            }
            return _realDoms;
        }

        this.getArrayByRange = function(left, right) {//get the array which area is among the range of 'left' and 'right'
            var newArr = [];
            if (!_) return [];
            var arr = _.Doms;
            if (!arr) return newArr;
            var lenA = 0, lenB = 0;
            for (var i = 0; i < arr.length; i++){
                lenB += (arr[i].clientWidth || arr[i].width);
                if ((lenA >= left && lenA < right) || (lenB > left && lenB < right) || (left > lenA && left < lenB) || (right > lenA && right < lenB)) {
                    newArr.push(arr[i]);
                }
                lenA += arr[i].clientWidth;
            }
            if (!newArr.length) {
                var a = g_column.getPreRow(arr);
                return getArrayByRange(a, left, right);
            }
            return newArr;
        };
        /*
        Case A:
            AAAAAAAAAAAAAAAAAAAAAA    |
            BBBBBBBBBBBB|        |    |
            CCCCCCCCCCCCCCC|     |    |
            ZZZZZZZZZZZZZZZZZ|   |    |

        Case B:
            AAAAAAAAAAAAAAAAAAAAAA    |
            BBBBBBBBBBBB|        |    |
            CCCCCCCCCCCCCCC|     |    |
            ZZZZZZZZZZZZZ| |     |    |

        Case C:
            AAAAAAAAAAAAAAAAAAAAAA    |
            BBBBBBBBBBBB|        |    |
            CCCCCCCCCCCCCCC|     |    |
            ZZZZZZZZZZZZZZZZZZZZZZZ|  |
        */
        this.addVirDoms = function (_preRow) { //��ÿ�еĺ���������Dom.
            var L = _.getRealDomsLen();
            var Last = _.Doms[L - 1];
            //�õ�����ʵDom��ĩ���α�λ��
            var rightVernier = 1.0 * trim(Last.style.left, "px") + Last.clientWidth;
            if (_preRow == undefined) {
                var left = rightVernier;
                var top = 0;
                var width = 700 - left;
                var height = 0;
                var b = new VirtualDom(left, top, width, height);
                _.Doms.push(b);
                return;
            }
            //����ĩ���α�λ��ǰ����Dom��ɾ��
            for (var i = 0, t; t = _preRow.Doms[i]; i++) {
                if (t.flag == "V") {
                    if (getDomLeft(t) < rightVernier) {
                        //do nothing.
                    } else {
                        _.Doms.push(t);
                    }
                }
            }
            //�����µ���Dom.Dom��ǰ��ΪʵDom��ĩ���α�,Dom�ĺ��Ϊ��һ��û�б�ɾ������Dom��ĩ���α�.
            var left = rightVernier;
            var top = getYByX(g_column.getPreRow(_).Doms, left); //X ?

            if (_.Doms[L] == undefined) {
                var width = 700 - left; //��ǰ��һ����Dom��clientLeft �� left�Ĳ�Ϊ���.
                var height = 0;
                var b = new VirtualDom(left, top, width, height);
                //�����µ���Dom.
                _.Doms.push(b);
            } else {
                //getDomLeft(_.Doms[L])Ϊ��ǰ��һ����Dom��clientLeft �� left�Ĳ�Ϊ���.

                var b = _preRow.createVirDoms(left, getDomLeft(_.Doms[L]))
                //�����µ���Dom.
                var k = _.getRealDomsLen();
                for (var i = 0, t; t = b[i]; i++) {
                    _.Doms.splice(k+i, 0, t);
                }
            }
        };

        /*
        AAAAAAAAAAAAA|BBBBBBBBBBBBBB|CCCCCCCCC
        AAAAAAA|BBBBBBBBBBBBBBBBBBBBBBBBB|

        */
        this.createVirDoms = function (left, right) {//�ڴ��е����洴��һ��VirDoms����  left,right�Ȳ���Ϊ�߽�.
            var tmpDoms = _.getArrayByRange(left, right); //��ȡ�߽��ڵ�Doms����.
            var arr = [];
            for (var i = 0, t; t = tmpDoms[i]; i++) {
                var tmpLeft = getDomLeft(t);
                var tmpTop = getDomTop(t) + t.clientHeight;
                var tmpWidth = t.clientWidth;
                if (i == 0) {
                    tmpLeft = Math.max(tmpLeft, left); //left�����ڵ�һ��Dom���м�.
                    tmpWidth = Math.min(tmpWidth, getDomLeft(t) + t.clientWidth - tmpLeft);
                }

                if (i == tmpDoms.length - 1) tmpWidth = Math.min(tmpWidth, right - tmpLeft); //right���������һ��Dom���м�.
                arr.push(new VirtualDom(tmpLeft, tmpTop, tmpWidth, 0));
            }
            return arr;
        };

        this.createUpperVirDoms = function (left, right) {//working
            var tmpDoms = _.getArrayByRange(left, right); //��ȡ�߽��ڵ�Doms����.
            var arr = [];
            for (var i = 0, t; t = tmpDoms[i]; i++) {
                var tmpLeft = getDomLeft(t);
                var tmpTop = getDomTop(t);
                var tmpWidth = t.clientWidth;
                if (i == 0) {
                    tmpLeft = Math.max(tmpLeft, left); //left�����ڵ�һ��Dom���м�.
                    tmpWidth = Math.min(tmpWidth, getDomLeft(t) + t.clientWidth - tmpLeft);
                }

                if (i == tmpDoms.length - 1) tmpWidth = Math.min(tmpWidth, right - tmpLeft); //right���������һ��Dom���м�.
                arr.push(new VirtualDom(tmpLeft, tmpTop, tmpWidth, 0));
            }
            return arr;
        };

        this.getDomByX = function (x) {//��ͨ��[2,5)���ǰ�պ������ȡԪ��.
            for (var i = 0, t; t = _.Doms[i]; i++) {
                var k = getDomLeft(t);
                if (k <= x && x < k + t.clientWidth) {
                    return t;
                }
            }
        };
    }

 function getCurrentGap(_row, _rec) {//��ȡ��϶���������
     var _arr = getArrayByRange(_row.rects, _rec.x, _rec.x + _rec.width);
     for (var i = 0, t; t = _arr[i]; i++) {
         var aa = _rec.y;
         var bb = t.y + t.height;
         if (aa > bb) {
             var b = new Rectange();
             b.x = Math.max(t.x, _rec.x);
             b.y = bb;
             var Y = Math.min(t.x + t.width, _rec.x+_rec.width);
             b.width = Y - b.x;
             b.height = aa - bb;
             emptySpace.push(b);
         }
     }
     return emptySpace;
 }


 function getDomLeft(_dom) {
     if (_dom.flag == "V") {
         return _dom.clientLeft;
     } else {
         return 1*trim(_dom.style.left, "px");
     }
 }

 function getDomTop(_dom) {
     if (_dom.flag == "V") {
         return _dom.clientTop;
     } else {
         return 1*trim(_dom.style.top, "px");
     }
 }

 function getYByX(_arr, x) {//��ȡ_arr��x���ڴ���Y����.
     for (var i = 0, t; t = _arr[i]; i++) {
         if (getDomLeft(t) < x && x < getDomLeft(t) + t.clientWidth) {
             return getDomTop(t) + t.clientHeight;
         }
     }
     return 0;
 }

 function getMaxYAtX(_arr, x) {//
     var a = 0;
     for (var i = 0, t; t = _arr[i]; i++) {
         if (t.x < x && x < t.x + (t.width || t.clientWidth) && getDomTop(t)+t.clientHeight>a) {
             a = getDomTop(t) + t.clientHeight;
         }
     }
     return a;
 }


 function getRight(arr, eleB) {//��ȡ��һԪ�ص�rightֵ. eleB�ǽ�����arr���Ԫ��.
     if ((arr == undefined) || (arr.Doms == undefined) || (arr.Doms.length == 0)) return { "left": 0, "right": eleB.clientWidth };
     var len = 0;
     for (var i = 0, t; t = arr.Doms[i]; i++) {
         len += t.clientWidth;
     }
     return len + eleB.clientWidth;
 }

 function getEnds(arr, eleB) {//��ȡ��һԪ�ص�leftֵ��rightֵ. eleB�ǽ�����arr���Ԫ��.
     if ((arr == undefined) || (arr.Doms == undefined) || (arr.Doms.length == 0)) {
         return { "left": 0, "right": eleB.clientWidth };
     }
     var len = 0;
     for (var i=0,t; t = arr.Doms[i]; i++) {
         len += t.clientWidth;
     }
     return { "left": len, "right": len + eleB.clientWidth };
 }

 function getIndex(arr, ins) {//��ȡԪ���������е����.
     for (var i = 0; i < arr.length; i++) {
         if (arr[i] === ins) {
             return i;
         }
     }
     return -1;
 }

 function getItemByRight(arr, right) {
     var len = 0;
     for (var i = 0; i < arr.length; i++) {
         len += arr[i].clientWidth;
         if (len >= right) {
             return arr[i];
         }
     }
     return undefined;
 }

 function getArrayByRange(row, left, right) {//get the array which area is among the range of 'left' and 'right'
     var newArr = [];
     if (!row) return [];
     var arr = row.Doms;
     if (!arr) return newArr;
     var lenA = 0, lenB = 0;
     for (var i = 0; i < arr.length; i++){
         lenB += (arr[i].clientWidth || arr[i].width);
         if ((lenA >= left && lenA < right) || (lenB > left && lenB < right) || (left > lenA && left < lenB) || (right > lenA && right < lenB)) {
             newArr.push(arr[i]);
         }
         lenA += arr[i].clientWidth;
     }
     if (!newArr.length) {
         var a = g_column.getPreRow(arr);
         return getArrayByRange(a, left, right);
     }
     return newArr;
 }

 function getTopFromArray(arr) {
     if (arr == undefined || arr.length == 0) return 0;
     var lowest = 0;
     for (var i = 0; i < arr.length; i++) {
         var tmpA = getDomTop(arr[i]) + arr[i].clientHeight;
         if (tmpA > lowest) {
             lowest = tmpA;
         }
     }
     if(lowest == 0){
         a = a;
     }
     return lowest;
 }

 function getTop(preRow,/*ǰһ��div*/ currentRow, eleA, eleB) {//����Ԫ�����Ͻǵ�Y����.
     var tmpRight = getDomLeft(eleA) + eleA.clientWidth + eleB.clientWidth;
     if (tmpRight > 300) {
         var clums = [];
         Doms.push(clums);
     } else {
         eleB.style.left = "0px";
         var tmpSum = 0, j = 0, lowest = 0;
         while (tmpSum <= eleB.clientWidth) {
             tmpSum += Doms[Doms.length].Clums[j];
             var tmpA = getDomTop([Doms.length].Clums[j]) + Doms[Doms.length].Clums[j].clientWidth;
             if (tmpA > lowest) {
                 lowest = tmpA;
             }
         }
     }
     return lowest;
 }

 function getRandomText() {//����������ַ���.
     var letters = "qwertyuiopasdfghjklzxcvbnm,";
     var len = Math.random() * 1000;
     len = len.toString();
     len = len.substr(0, len.indexOf("."));
     len = Math.max(100, len % 200);
     var t = "";
     for (var i = 0; i < Number(len); i++) {
         t += letters.charAt(getRandomLen() % 27);
     }
     return t;
 }

 function getRandomLen() {//�����������
     var index = Math.random() * 1000;
     index = index.toString();
     index = index.substr(0, index.indexOf("."));
     return index;
 }

 function copyArray(arrSource) {//��������
     var arrTarget=[];
     for (var i = 0; i < arrSource.length; i++) {
         arrTarget.push(arrSource[i]);
     }
     return arrTarget;
 }

 function trim(source,str) {//ɾ��ǰ׺���׺
     var regex = new RegExp("^(" + str + ")*|(" + str + ")*$", "g");
     return source.replace(regex, '');
 };


//initialize
var g_emptySpace = emptySpace = [];
var g_realSpace = [], g_realSpace_bottom=[];//以左下角的坐标为顺序时行排列，y坐标优先，x坐标其次.
var g_column = new Column();
var Doms = [];
var Divs = [];
for (var i = 0; i < 50; i++) {
    var t = document.createElement("DIV");
    t.innerHTML = getRandomText();
    var tB = getRandomLen();
    t.style.width = Math.max(100, tB % 300) + "px";
    t.style.position = "absolute";
    t.style.wordBreak = "break-all";
    t.style.visibility = "hidden";
    t.style.backgroundColor = (getRandomLen() % 10).toString() + (getRandomLen() % 10).toString() + (getRandomLen() % 10).toString() + (getRandomLen() % 10).toString() + (getRandomLen() % 10).toString() + (getRandomLen() % 10).toString();
    var a = new VirtualDom(0, 0, 0, 0, 'R');
    a.ele = document.body.appendChild(t);
    a.clientWidth = 1 * trim(t.style.width, "px");
    a.clientHeight = t.clientHeight;//还要用style.height,因为它没有值.
    document.body.removeChild(t);
    Divs[i] = a;
}
//end initialize
var g_rangeRect = new VirtualDom(0, 0, 700, 2000, 'V');
g_emptySpace.push(g_rangeRect);
while (true) {
    if (Divs.length == 0) {
        break;
    }
    g_emptySpace.forEach(function (t) {
        if (Divs[0] == undefined) {
            return;
        }
        Divs[0].clientLeft = t.clientLeft;
        Divs[0].clientTop = t.clientTop;
        var tmpA = lib.isRectBlanck(g_realSpace, Divs[0]); //准备放入的长方形是否被空白区覆盖。
        var tmpB = lib.isBeyondRange(g_rangeRect, Divs[0]); //准备放入的长方形是否超出范围。
        if (tmpA == true && tmpB == false) {
            var foreRects = lib.interceptArray(g_realSpace_bottom, new VirtualDom(0, 0, 0, 0, "V"), Divs[0], function (a, b) {
                if (a == undefined || b == undefined) return 0;
                if (a.clientTop + a.clientHeight < b.clientTop + b.clientHeight) return -1;
                if (a.clientTop + a.clientHeight == b.clientTop + b.clientHeight && a.clientLeft < b.clientLeft) {
                    return -1;
                }
                return 1;
            });
            Divs[0].clientTop = lib.getLastBottom(foreRects, Divs[0]);
            var intersects = lib.getRectsIntersect(g_emptySpace, Divs[0]); //获取所有和rect相交的虚rect.   5-5
            var tmpDiv = Divs[0].clone();
            intersects.forEach(function (item) {
                var sRect = lib.getIntersection(item, tmpDiv);
                var complements = lib.getBRecComp(item, sRect);
                lib.arrayRemoveItem(g_emptySpace, item); //把5-5中所涉及的虚rect去掉.
                lib.boxup(g_emptySpace, complements); //把产生的新虚Rect添加到g_emptySpace容器中.

            });
            lib.boxup_bottom(g_realSpace_bottom, Divs[0]);
            g_realSpace.push(Divs[0]); //把刚放置好的Divs[0]添加到实rects容器中.
            lib.removeEleFromArray(Divs, Divs[0]); //把刚放置好的Divs[0]从待置Divs数组中删除.
        }
        else {//恢复到初始状态.
            Divs[0].clientLeft = undefined;
            Divs[0].clientTop = undefined;
        }
    });
}
g_realSpace.forEach(function (a) {
    a.ele.style.left = (150+a.clientLeft) + "px";
    a.ele.style.top = a.clientTop + "px";
    a.ele.style.visibility = "";
    document.body.appendChild(a.ele);
});

//var test = lib.getIntersection((new VirtualDom(0, 0, 700, 2000, 'V')), (new VirtualDom(0, 0, 70, 200, 'V')));
//test:
//var test0 = lib.isRectBlanck([(new VirtualDom(0, 0, 10, 10, 'V')), (new VirtualDom(10, 10, 10, 10, 'V'))], (new VirtualDom(30, 0, 70, 20, 'V')));
//var test1 = lib.isRectBlanck([(new VirtualDom(0, 0, 10, 10, 'V')), (new VirtualDom(15, 15, 10, 10, 'V'))], (new VirtualDom(0, 0, 70, 20, 'V')));
//alert("test0:" + test0 + "; test1:" + test1);
var test2 = lib.getRectsIntersect([(new VirtualDom(0, 0, 100, 288, 'V'))], (new VirtualDom(100, 702, 338, 1298, 'V')));
var test3 = lib.getRectsIntersect([(new VirtualDom(0, 0, 100, 288, 'V'))], (new VirtualDom(50, 7, 338, 1298, 'V')));
var test4 = lib.getRectsIntersect([(new VirtualDom(100, 630, 200, 1370, 'V'))], (new VirtualDom(0, 0, 100, 162, 'V')));
var a = new VirtualDom(0, 0, 6, 9);
var b = new VirtualDom(1, 2, 3, 3);

//var c = lib.isRectsCrossOnX(new VirtualDom(0, 0, 10, 9), new VirtualDom(5, 0, 10, 9));//true
//var c = lib.isRectsCrossOnX(new VirtualDom(0, 0, 10, 9), new VirtualDom(2, 0, 2, 9)); //true
//var c = lib.isRectsCrossOnX(new VirtualDom(0, 0, 10, 9), new VirtualDom(-1, 0, 20, 9)); //true
//var c = lib.isRectsCrossOnX(new VirtualDom(0, 0, 10, 9), new VirtualDom(10, 0, 10, 9)); //false
//var c = lib.isRectsCrossOnX(new VirtualDom(0, 0, 10, 9), new VirtualDom(11, 0, 10, 9)); //false
//var c = lib.isRectsCrossOnX(new VirtualDom(0, 0, 10, 9), new VirtualDom(5, 0, 10, 9));
var a = a;
var a = a;
//end test
</script>
</div>
<!--<input type='button' value='click me' onclick='test()'/>-->

</div>
 </body>
</html>