/*
 Copyright 2010 James Halliday (mail@substack.net)

 This project is free software released under the MIT/X11 license:
 http://www.opensource.org/licenses/mit-license.php

 Copyright 2010 James Halliday (mail@substack.net)

 Permission is hereby granted, free of charge, to any person obtaining a copy
 of this software and associated documentation files (the "Software"), to deal
 in the Software without restriction, including without limitation the rights
 to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 copies of the Software, and to permit persons to whom the Software is
 furnished to do so, subject to the following conditions:

 The above copyright notice and this permission notice shall be included in
 all copies or substantial portions of the Software.

 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
 THE SOFTWARE.
 */

var traverse;

(function(){
    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;
    };
})();