function tuplify(obj) {
    var id = obj['_id'] || obj['$id'];
    var type = obj['_type'] || obj['$ref'];
    return [type,id];
}

function is_ref(obj) {
    return obj['$ref'] != null;
}

function is_entry(obj) {
    return obj['_id'] != null;
}

function make_ref(obj) {
    return {'$id': obj['_id'], '$ref': obj['_type']};
}

function internally_reference(obj, entities) {
    if ( ! entities )
        entities = [];
    if ( typeof( obj ) == 'string' )
        return obj;
    if ( is_entry(obj) )
        entities.push(tuplify(obj));

    for ( var k in obj ) {
        var v = obj[k];
        if ( is_entry( v ) ) {
            var t = tuplify(v);
            found = false;

            for ( var i in entities ) {
                var e = entities[i];
                if ( e[0] == t[0] && e[1] == t[1] ) {
                    obj[k] = make_ref(v);
                    found = true;
                    break;
                }
            }

            if ( ! found ) {
                entities.push(t);
                internally_reference(v, entities);
            }

        } else if ( ! is_ref( v ) ) {
            internally_reference(v, entities);
        }
    }

    return obj; // so I can chain
}

function shallow(o) {
    var s = "{";
    for ( var x in o )
        s += "@"+x+", "
    return s+"}";
}

function internally_dereference( obj, mappings, waiting, seen ) {
    var top = false;
    if ( ! mappings ) {
        top = true;
        mappings = {};
    }
    if ( ! waiting )
        waiting = {};
    if ( ! seen )
        seen = [];

    if ( obj == null || typeof(obj) != "object" )
        return;

    var myt = null;

    if ( is_entry(obj) ) {
        myt = tuplify(obj);
        if ( seen.indexOf(myt) != -1 )
            return;
        mappings[myt] = obj;
    } else if ( is_ref(obj) ) {
        return;
    }

    for ( var k in obj ) {
        var v = obj[k];
        if ( v == null ) continue;
        if ( is_ref( v ) ) {
            var t = tuplify(v);
            var x = mappings[t];

            if ( x ) {
                obj[k] = x;

            } else {
                var w = waiting[t] || [];
                w.push([obj,k]);
                waiting[t] = w;
            }

        } else if ( is_entry(v) ) {
            var t = tuplify(v);
            mappings[t] = v;
            var rem = [];
            for ( var wk in waiting ) {
                if ( wk == t ) {
                    rem.push(wk);
                    var waitingForMe = waiting[wk];
                    for ( var i = 0; i < waitingForMe.length; i++ ) {
                        var waiter = waitingForMe[i];
                        var obj = waiter[0];
                        var key = waiter[1];
                        obj[key] = v;
                    }
                }
            }
            for ( var i = 0; i < rem.length; i++ )
                delete waiting[rem[i]];

            internally_dereference(v,mappings,waiting,seen.concat([myt]));

        } else {
            internally_dereference(v,mappings,waiting,seen);
        }
    }
}