(function (root, factory) {
    if (typeof define === 'function' && define.amd) {
        // AMD. Register as an anonymous module.
        define([], factory);
    } else if (typeof exports === 'object') {
        // Node. Does not work with strict CommonJS, but
        // only CommonJS-like environments that support module.exports,
        // like Node.
        module.exports = factory();
    } else {
        // Browser globals (root is window)
        root.traverse = factory();
  }
}(this, function () {

    var traverse = function (obj) {
        return new Traverse(obj);
    };

    function Traverse (obj) {
        this.value = obj;
    }

    Traverse.prototype.get = function (ps) {
        var node = this.value;
        for (var i = 0; i < ps.length; i ++) {
            var key = ps[i];
            if (!node || !hasOwnProperty.call(node, key)) {
                node = undefined;
                break;
            }
            node = node[key];
        }
        return node;
    };

    Traverse.prototype.has = function (ps) {
        var node = this.value;
        for (var i = 0; i < ps.length; i ++) {
            var key = ps[i];
            if (!node || !hasOwnProperty.call(node, key)) {
                return false;
            }
            node = node[key];
        }
        return true;
    };

    Traverse.prototype.set = function (ps, value) {
        var node = this.value;
        for (var i = 0; i < ps.length - 1; i ++) {
            var key = ps[i];
            if (!hasOwnProperty.call(node, key)) node[key] = {};
            node = node[key];
        }
        node[ps[i]] = value;
        return value;
    };

    Traverse.prototype.map = function (cb) {
        return walk(this.value, cb, true);
    };

    Traverse.prototype.forEach = function (cb) {
        this.value = walk(this.value, cb, false);
        return this.value;
    };

    Traverse.prototype.reduce = function (cb, init) {
        var skip = arguments.length === 1;
        var acc = skip ? this.value : init;
        this.forEach(function (x) {
            if (!this.isRoot || !skip) {
                acc = cb.call(this, acc, x);
            }
        });
        return acc;
    };

    Traverse.prototype.paths = function () {
        var acc = [];
        this.forEach(function (x) {
            acc.push(this.path); 
        });
        return acc;
    };

    Traverse.prototype.nodes = function () {
        var acc = [];
        this.forEach(function (x) {
            acc.push(this.node);
        });
        return acc;
    };

    Traverse.prototype.clone = function () {
        var parents = [], nodes = [];
        
        return (function clone (src) {
            for (var i = 0; i < parents.length; i++) {
                if (parents[i] === src) {
                    return nodes[i];
                }
            }
            
            if (typeof src === 'object' && src !== null) {
                var dst = copy(src);
                
                parents.push(src);
                nodes.push(dst);
                
                forEach(objectKeys(src), function (key) {
                    dst[key] = clone(src[key]);
                });
                
                parents.pop();
                nodes.pop();
                return dst;
            }
            else {
                return src;
            }
        })(this.value);
    };

    function walk (root, cb, immutable) {
        var path = [];
        var parents = [];
        var alive = true;
        
        return (function walker (node_) {
            var node = immutable ? copy(node_) : node_;
            var modifiers = {};
            
            var keepGoing = true;
            
            var state = {
                node : node,
                node_ : node_,
                path : [].concat(path),
                parent : parents[parents.length - 1],
                parents : parents,
                key : path.slice(-1)[0],
                isRoot : path.length === 0,
                level : path.length,
                circular : null,
                update : function (x, stopHere) {
                    if (!state.isRoot) {
                        state.parent.node[state.key] = x;
                    }
                    state.node = x;
                    if (stopHere) keepGoing = false;
                },
                'delete' : function (stopHere) {
                    delete state.parent.node[state.key];
                    if (stopHere) keepGoing = false;
                },
                remove : function (stopHere) {
                    if (isArray(state.parent.node)) {
                        state.parent.node.splice(state.key, 1);
                    }
                    else {
                        delete state.parent.node[state.key];
                    }
                    if (stopHere) keepGoing = false;
                },
                keys : null,
                before : function (f) { modifiers.before = f },
                after : function (f) { modifiers.after = f },
                pre : function (f) { modifiers.pre = f },
                post : function (f) { modifiers.post = f },
                stop : function () { alive = false },
                block : function () { keepGoing = false }
            };
            
            if (!alive) return state;
            
            function updateState() {
                if (typeof state.node === 'object' && state.node !== null) {
                    if (!state.keys || state.node_ !== state.node) {
                        state.keys = objectKeys(state.node)
                    }
                    
                    state.isLeaf = state.keys.length == 0;
                    
                    for (var i = 0; i < parents.length; i++) {
                        if (parents[i].node_ === node_) {
                            state.circular = parents[i];
                            break;
                        }
                    }
                }
                else {
                    state.isLeaf = true;
                    state.keys = null;
                }
                
                state.notLeaf = !state.isLeaf;
                state.notRoot = !state.isRoot;
            }
            
            updateState();
            
            // use return values to update if defined
            var ret = cb.call(state, state.node);
            if (ret !== undefined && state.update) state.update(ret);
            
            if (modifiers.before) modifiers.before.call(state, state.node);
            
            if (!keepGoing) return state;
            
            if (typeof state.node == 'object'
            && state.node !== null && !state.circular) {
                parents.push(state);
                
                updateState();
                
                forEach(state.keys, function (key, i) {
                    path.push(key);
                    
                    if (modifiers.pre) modifiers.pre.call(state, state.node[key], key);
                    
                    var child = walker(state.node[key]);
                    if (immutable && hasOwnProperty.call(state.node, key)) {
                        state.node[key] = child.node;
                    }
                    
                    child.isLast = i == state.keys.length - 1;
                    child.isFirst = i == 0;
                    
                    if (modifiers.post) modifiers.post.call(state, child);
                    
                    path.pop();
                });
                parents.pop();
            }
            
            if (modifiers.after) modifiers.after.call(state, state.node);
            
            return state;
        })(root).node;
    }

    function copy (src) {
        if (typeof src === 'object' && src !== null) {
            var dst;
            
            if (isArray(src)) {
                dst = [];
            }
            else if (isDate(src)) {
                dst = new Date(src.getTime ? src.getTime() : src);
            }
            else if (isRegExp(src)) {
                dst = new RegExp(src);
            }
            else if (isError(src)) {
                dst = { message: src.message };
            }
            else if (isBoolean(src)) {
                dst = new Boolean(src);
            }
            else if (isNumber(src)) {
                dst = new Number(src);
            }
            else if (isString(src)) {
                dst = new String(src);
            }
            else if (Object.create && Object.getPrototypeOf) {
                dst = Object.create(Object.getPrototypeOf(src));
            }
            else if (src.constructor === Object) {
                dst = {};
            }
            else {
                var proto =
                    (src.constructor && src.constructor.prototype)
                    || src.__proto__
                    || {}
                ;
                var T = function () {};
                T.prototype = proto;
                dst = new T;
            }
            
            forEach(objectKeys(src), function (key) {
                dst[key] = src[key];
            });
            return dst;
        }
        else return src;
    }

    var objectKeys = Object.keys || function keys (obj) {
        var res = [];
        for (var key in obj) res.push(key)
        return res;
    };

    function toS (obj) { return Object.prototype.toString.call(obj) }
    function isDate (obj) { return toS(obj) === '[object Date]' }
    function isRegExp (obj) { return toS(obj) === '[object RegExp]' }
    function isError (obj) { return toS(obj) === '[object Error]' }
    function isBoolean (obj) { return toS(obj) === '[object Boolean]' }
    function isNumber (obj) { return toS(obj) === '[object Number]' }
    function isString (obj) { return toS(obj) === '[object String]' }

    var isArray = Array.isArray || function isArray (xs) {
        return Object.prototype.toString.call(xs) === '[object Array]';
    };

    var forEach = function (xs, fn) {
        if (xs.forEach) return xs.forEach(fn)
        else for (var i = 0; i < xs.length; i++) {
            fn(xs[i], i, xs);
        }
    };

    forEach(objectKeys(Traverse.prototype), function (key) {
        traverse[key] = function (obj) {
            var args = [].slice.call(arguments, 1);
            var t = new Traverse(obj);
            return t[key].apply(t, args);
        };
    });

    var hasOwnProperty = Object.hasOwnProperty || function (obj, key) {
        return key in obj;
    };

    return traverse


}));
