objectShapeId / dedup / same

dedup.js

const transitions = new Map();
let shapeSeqId = 1; // 0 - not an object, 1 - empty object

function transition(shapeId, key) {
    let map;

    if (!transitions.has(key)) {
        transitions.set(key, map = new Map());
    } else {
        map = transitions.get(key);
    }

    if (map.has(shapeId)) {
        return map.get(shapeId);
    }

    map.set(shapeId, ++shapeSeqId);
    return shapeSeqId;
}

function getObjectShapeId(obj, strict) {
    let shapeId = 1;

    if (strict) {
        for (const key in obj) {
            if (hasOwnProperty.call(obj, key)) {
                shapeId = transition(shapeId, key);
            }
        }
    } else {
        for (const key of Object.keys(obj).sort()) {
            shapeId = transition(shapeId, key);
        }
    }

    return shapeId;
}

function createDeduper(fn) {
    const map = new Map();

    return (value) => {
        if (value === null || Array.isArray(value) || typeof value !== 'object') {
            return true;
        }

        const hash = fn(value);

        if (map.has(hash)) {
            next: for (const ref of map.get(hash)) {
                for (const key in value) {
                    if (hasOwnProperty.call(value, key)) {
                        if (value[key] !== ref[key]) {
                            break next;
                        }
                    }
                }

                return false;
            }
            map.get(hash).push(value);
        } else {
            map.set(hash, [value]);
        }

        return true;
    }
}

function dedup(array) {
    return array.filter(createDeduper(getObjectShapeId))
}

// function same(a, b, deep, aRefs = new Map(), bRefs = new Map()) {
//     if (a === b) {
//         return true;
//     }

//     if (Array.isArray(a) && Array.isArray(b)) {
//         if (a.length !== b.length) {
//             return false;
//         }

//         let ret = true;

//         for (let i = 0; i < a.length; i++) {
//             if (deep ? !same(a[i], b[i], deep, aRefs, bRefs) : a[i] !== b[i]) {
//                 ret = false;
//                 break;
//             }
//         }

//         return ret;
//     }

//     if (a !== null && b !== null && typeof a === 'object' && typeof b === 'object') {
//         let ret = true;

//         for (const key in a) {
//             if (hasOwnProperty.call(a, key)) {
//                 if (deep ? !same(a[key], b[key], deep, aRefs, bRefs) : a[key] !== b[key]) {
//                     ret = false;
//                     break;
//                 }
//             }
//         }

//         return ret;
//     }

//     return false;
// }

// function walk(value) {
//     if (Array.isArray(value)) {
//         for (const item of value) {
//             walk(item);
//         }
//     }

//     if (value !== null && typeof value === 'object') {
//         for (const key in obj) {
//             if (hasOwnProperty.call(obj, key)) {
//                 walk(obj[key]);
//             }
//         }
//     }
// }