function isScalar(o){
    if(o==null){
        return false;
    }
    if(typeof o==='object'){
        return false;
    }
    return true;
}

function isEqual(r1,r2){
    var ignoreKeys = ['_type','_matched','_v','_m','key'];
    if(r1==null && r2==null){
        return true;
    }
    if(r1==null || r2==null){
        return false;
    }
    if(isScalar(r1) || isScalar(r2)){
        return r1===r2;
    }
    //now assert a1!=null && r2!=null
    var ks1 = Object.keys(r1);
    var ks2 = Object.keys(r2);

    ks1 = ks1.filter(function(k){
        return ignoreKeys.indexOf(k)===-1;
    });

    ks2 = ks2.filter(function(k){
        return ignoreKeys.indexOf(k)===-1;
    });

    if(ks1.length!==ks2.length){
        return false;
    }
    for(var i=0; i<ks1.length; i++){
        var k = ks1[i];
        if(r1[k]!==r2[k]){
            return false;
        }
    }
    return true;

}

function diffArray(a1, a2,parentKeys){
    //a1是旧的,a2是新的
    // $.log("diffArray,parentKeys=" + parentKeys);

    var temp_matched = [];
    var result = [];
    if(!a1){
        a1 = [];
    }
    if(!a2){
        a2 = [];
    }

    var newa2 = [];
    for(var j=0; j<a2.length; j++){
        if(a2[j]!==null){
            newa2.push(a2[j]);
        }
    }
    a2 = newa2;


    for(var i=0; i<a2.length; i++){
        var r2 = a2[i];
        if(!isScalar(r2)){
            delete r2._matched;
        }
    }

    for(var i=0; i<a1.length; i++){
        var r1 = a1[i];
        var found = false;
        for(var j=0; j<a2.length; j++){
            var r2 = a2[j];
            if(isEqual(r1,r2)){
                found = true;
                if(isScalar(r2)){
                    temp_matched.push(r2);
                }
                else{
                    if(r2){
                        r2._matched = true;
                    }
                    else{
                        //如果r2[j]为空，那么应该删除

                    }
                }

                break;
            }
        }
        if(!found){
            //r1不存在于a2中，说明r1被删除了
            result.push({
                type:'deleted',
                r:r1
            });
        }
    }
    for(var i=0; i<a2.length; i++){
        r2 = a2[i];
        if(isScalar(r2)){
            if(temp_matched.indexOf(r2)==-1){
                result.push({
                    type:'added',
                    r:r2
                });
            }
        }
        else if(!r2._matched){
            delete r2._matched;
            result.push({
                type:'added',
                r:r2
            });
        }
    }
    return result;
}

function isArrayEqual(a1,a2){
    if(a1==null && a2==null){
        return true;
    }

    if(a1==null && a2!=null){
        return false;
    }

    if(a1!=null && a2==null){
        return false;
    }

    if(a1.length!=a2.length){
        return false;
    }
    for(var i=0; i<a1.length; i++){
        if(!isEqual(a1[i],a2[i])){
            return false;
        }
    }
    return true;
}



function diff(obj1, obj2,parentKeys){
    if(!parentKeys){
        parentKeys = [];
    }
    var result = []
    if(!obj1){
        obj1 = {};
    }
    if(!obj2){
        obj2 = {};
    }

    if(typeof obj2==='string'){
        result.push({
            type:'changed',
            fieldKey : parentKeys,
            parentKeys: "",
            oldv : '' + JSON.stringify(obj1),
            newv : '' + obj2
        });
        return result;
    }
    var keys1 = Object.keys(obj1);
    var keys2 = Object.keys(obj2);

    keys1.sort();
    keys2.sort();

    //找到减少的和发生了变化的
    for(var i=0; i<keys1.length; i++){
        var k1 = keys1[i];
        var v1 = obj1[k1];
        var v2 = obj2[k1];


        //如果v1,v2 是scalar,则直接比较
        if(isScalar(v1)){
            if(v1!==v2 && v2!=null && v1!==null){
                result.push({
                    type:'changed',
                    fieldKey : k1,
                    parentKeys: JSON.stringify(parentKeys),
                    oldv : '' +v1,
                    newv : '' + v2
                })
            }
            else{
                if(v2!=null && v1==null){
                    result.push({
                        type:'added',
                        fieldKey : k1,
                        parentKeys: JSON.stringify(parentKeys),
                        oldv : null,
                        newv : ''+v2
                    })
                }
                else if(v1!==null && v2==null){
                    result.push({
                        type:'deleted',
                        fieldKey : k1,
                        parentKeys: JSON.stringify(parentKeys),
                        oldv : v1,
                        newv : v2
                    })
                }

            }
        }
        else{
            //v1 == null 或者 v1是object
            if(v1!=null){
                if(Array.isArray(v1)){
                    var ret = isArrayEqual(v1,v2);
                    if(!ret){
                        result.push({
                            type:'changed',
                            fieldKey : k1,
                            fieldType:'array',
                            parentKeys: JSON.stringify(parentKeys),
                            oldv : '' + JSON.stringify(v1),
                            newv : '' + JSON.stringify(v2)
                        });
                    }
                }
                else{
                    //v1 不是null ,也不是array, 所以是Object
                    if(v2===null){
                        result.push({
                            type:'deleted',
                            fieldKey : k1,
                            parentKeys: JSON.stringify(parentKeys),
                            oldv : '' + v1,
                            newv : ''
                        })
                    }
                    else{
                        var newParentKeys = [].concat(parentKeys,[k1]);
                        var ret1 = diff(v1,v2,newParentKeys);
                        result = [].concat(result,ret1);
                    }

                }
            }
            else{
                //v1 == null;
                if(v2!=null){
                    if(v2!==''){
                        result.push({
                            type:'added',
                            fieldKey : k1,
                            parentKeys: JSON.stringify(parentKeys),
                            oldv : '',
                            newv : JSON.stringify(v2)
                        })
                    }

                }
            }
        }
    }

    for(var i=0; i<keys2.length; i++){
        var k2 = keys2[i];
        if(keys1.indexOf(k2)>-1){
            //在keys1中存在，那么这个k2已经在上一步处理过了
            continue;
        }
        var v2 = obj2[k2];
        if(isScalar(v2)){
            result.push({
                type:'added',
                fieldKey : k2,
                parentKeys: JSON.stringify(parentKeys),
                oldv : '',
                newv : '' +v2
            })
        }
        else{
            if(Array.isArray(v2)){
                result.push({
                    type:'added',
                    fieldKey : k2,
                    fieldType:'array',
                    parentKeys: JSON.stringify(parentKeys),
                    // diff : v2
                    newv:JSON.stringify(v2)
                });
            }
            else {
                if (v2 != null && v2 != '') {
                    result.push({
                        type: 'added',
                        fieldKey: k2,
                        parentKeys: JSON.stringify(parentKeys),
                        oldv: null,
                        newv: '' + v2
                    });
                }
            }
        }
    }
    return result;
}