(function () {
    "use strict";
    var isNode = typeof module === 'object' && module.exports;
    /*node or non-node environment*/

    var util = isNode && require('util'),
        isDbg = isNode ? require("./logger").isDebugEnabled: function(){};

    /**
     * @class BinarySearchTree
     * @classdesc Implementation of a Binary Search Tree Data structure
     * @param compareFn  {userCompareFn=}, fn(a,b) return 1 if b>a, -1 if b<a, 0 otherwise
     */
    function BinarySearchTree(compareFn) {
        this.root = null;
        /**
         *
         * @param key
         * @param parent
         * @param leftChild
         * @param rightChild
         * @return {Object}
         */
        this.mkNode_ = function (key, val, parent, leftChild, rightChild) {
            return {key : key,
                parent : parent || null,
                leftChild : leftChild || null,
                rightChild : rightChild || null,
                height : 0,
                value : val,
                isLeftChild : function () {
                    return this.parent && this.parent.leftChild === this;
                },
                isRightChild : function () {
                    return this.parent && this.parent.rightChild === this;
                },
                inspect : function () {
                    return util && util.inspect({key : this.key, h : this.height,
                        L : this.leftChild, R : this.rightChild, p : (this.parent ? this.parent.key : null)}, {depth : null, colors : true});
                }

            };
        };

        this._compFn = function (node, key) {
            return compareFn ? compareFn.call(this, node.key, key)
                : (node.key < key ? 1 : node.key > key ? -1 : 0);

        };
        /**
         * Private method to find successor node
         * @param item
         * @param node
         * @return {*}
         */
        var successorNode = function (node) {
			if(!node) return null;
			if(node.rightChild)return minNode(node.rightChild);
				var n = node;			
				while (n && n.isRightChild()) {
					 n=n.parent;                  
				}
				return n.parent;
        };
        /**
         * Return the successor key value pair
         * @memberof BinarySearchTree.prototype
         * @instance
         * @function successor
         * @param item {*} key for which successor is needed
         * @returns {Object} {key:successor key,value: value}
         */
        this.successor = function (item) {
            var node = this.get(item, this.root);
            var sc = successorNode(node);
            return sc && {key : sc.key, value : sc.value}

        };

        /**
         * Private method to return min node in tree
         * @param m
         * @return {*}
         */
        var minNode = function (m) {
            while (m.leftChild) {
                m = m.leftChild;
            }
            return m;
        };

        /**
         * Find min key
         * @memberof BinarySearchTree.prototype
         * @instance
         * @function min
         * @returns {Object} {key:minimum key,value: value}
         */
        this.min = function () {
			var mNode = this.root && minNode(this.root);
            return mNode && {key : mNode.key, value : mNode.value};

        };

        /**
         * Private return max node in tree
         * @param max
         * @return {*}
         */
        var maxNode = function (max) {
            while (max.rightChild) {
                max = max.rightChild;
            }
            return max;
        };

        /**
         * Find max key
         * @memberof BinarySearchTree.prototype
         * @instance
         * @function max
         * @returns {Object} {key:maximum key,value: value}
         */
        this.max = function () {
			var mNode = this.root && maxNode(this.root);
            return mNode && {key : mNode.key, value : mNode.value};

        };

        /**
         * Private method to find predecessor node
         * @param node
         * @return {*}
         */
        var predecessorNode = function (node) {
            if(!node) return null;
			if(node.leftChild)return maxNode(node.leftChild);
				var n = node;			
				while (n && n.isLeftChild()) {
					 n=n.parent;                  
				}
				return n.parent;


        };

        /**
         * Return the predecessor key value pair
         * @memberof BinarySearchTree.prototype
         * @instance
         * @function predecessor
         * @param key {*} key for which predecessor is needed
         * @returns {Object} {key:predecessor key,value: value}
         */
        this.predecessor = function (key) {
            var node = this.get(key, this.root);
            var pNode = predecessorNode(node)
            return pNode && {key : pNode.key, value : pNode.value}
        };


    }

    /**
     * Insert a key value pair
     * @memberof BinarySearchTree.prototype
     * @instance
     * @param key
     * @param value
     * @returns {Object}
     */
    BinarySearchTree.prototype.put = function (key, value) {
        if (!this.root) {
            this.root = this.mkNode_(key, value);
            return this;
        }

        var cNode = this.root;
        var pNode = null;
        var isLeft = false;
        while (cNode) {
            pNode = cNode;
            if (this._compFn(cNode, key) == -1) {
                cNode = cNode.leftChild;
                isLeft = true;
            } else if (this._compFn(cNode, key) == 1) {
                cNode = cNode.rightChild;
                isLeft = false;
            } else {//replace
                cNode.value = value;
                break;
            }
        }
        //cNode should be null now
        var iNode = cNode;
        if (!cNode) {
            iNode = this.mkNode_(key, value, pNode);
            pNode[isLeft ? "leftChild" : "rightChild"] = iNode;
            this.reCalcHeight(iNode);
        }
        var tree = this;
        return {
            put : function (key, value) {
                return tree.put(key, value);
            },
            node : iNode

        };
    };

    BinarySearchTree.prototype.reCalcHeight = function (pNode) {
        while (pNode) {
            pNode.height = Math.max((pNode.leftChild ? pNode.leftChild.height : -1),
                (pNode.rightChild ? pNode.rightChild.height : -1)) + 1;
            pNode = pNode.parent;
        }
    };

    /**
     * Inorder traversal, apply provided function on each  visited node
     * @memberOf BinarySearchTree.prototype
     * @instance
     * @param node {Object=} Start at root if not given
     * @param fn {function} Callback function called for every node visited
     */
    BinarySearchTree.prototype.traverse = function (node, fn) {
        var args = Array.prototype.slice.call(arguments);
        if (args.length === 1) {
            if (Object.prototype.toString.call(args[0]) === '[object Function]') {
                console.log('initializing node to root');
                node = this.root;
                fn = args[0];
            } else {
                fn = function (n) {
                    console.log(n.key);
                }
            }
        }

        if (!node)return;
        this.traverse(node.leftChild, fn);
        fn(node);
        this.traverse(node.rightChild, fn);

    }

    /**
     * Get value for a key
     * @memberOf BinarySearchTree.prototype
     * @instance
     * @param key
     * @returns {Object} {key:key used in query,value:value of the key }, null if key was not found
     */
    BinarySearchTree.prototype.get = function (key, node) {
        if (typeof key === 'undefined' || key === null)return null;
        var retKV = (typeof node === "undefined");
        if (retKV)node = this.root;
        var compFn = this._compFn;
        return recFind(key, node);
        function recFind(key, node) {
            if (!node) return null;
            if (compFn(node, key) === -1) return recFind(key, node.leftChild);
            if (compFn(node, key) === 1) return recFind(key, node.rightChild);
            if (compFn(node, key) === 0)return retKV ? {key : node.key, value : node.value} : node;
        }

    };

    /**
     * Delete a key value pair from the Map.
     * @memberof BinarySearchTree.prototype
     * @instance
     * @function delete
     * @param  item {*} key to deleted
     */
    BinarySearchTree.prototype['delete'] = function (item) {
        var node = this.get(item, this.root),
            p,
            lc,
            child;
        if (node) {
            var num = node.leftChild ? (node.rightChild ? 2 : 1) : (node.rightChild ? 1 : 0);
            switch (num) {
                case 0:
                    p = node.parent;
                    if (p) {
                        lc = p.leftChild === node;
                        p[lc ? "leftChild" : "rightChild"] = null;
                        node = null;
                    }
                    break;
                case 1:
                    //single subtree
                    p = node.parent;
                    if (p) {
                        lc = p.leftChild === node;
                        child = node.leftChild || node.rightChild;
                        child.parent = p;
                        p[lc ? "leftChild" : "rightChild"] = child;
                        node = null;
                    } else {
                        //root
                        child = node.leftChild || node.rightChild;
                        lc = node.leftChild === child;
                        child.parent = null;
                    }
                    break;
                case 2:
                    var nextL = this.successor(node.key);
                    this['delete'](nextL.key);
                    node.key = nextL.key;
                    node.value = nextL.value;
            }


        }

    };

    BinarySearchTree.prototype.checkInvariants = function (node) {
        if (typeof node === 'undefined') {
            node = this.root;
        }
        if (!node) return;
        var lc = node.leftChild, rc = node.rightChild;
        if (isDbg()) {
            console.log(util.format("lc=%s, rc=%s, node=%s",
                lc ? lc.key : "null", rc ? rc.key : "null", node.key))
        }
        var ok = (!lc || this._compFn(node, lc.key) === -1) &&
            (!rc || this._compFn(node, rc.key) === 1);

        if (!ok) {
            throw new Error("Invariant check failed at node " + node + " key=" + node.key);
        }
        this.checkInvariants(lc);
        this.checkInvariants(rc);
    };

    BinarySearchTree.prototype.inspect = function () {
        return util.inspect(this.root, {depth : null, colors : true});
    };

    BinarySearchTree.prototype.entrySet = function () {
        var entries = [];
        this.traverse(this.root, function (node) {
            entries.push({key : node.key, value : node.value});
        });
        return entries;
    };

    /**
     * Export the Type so that new instances can be created
     * @type {Function}
     */
    if (isNode) {
        module.exports = BinarySearchTree;//node
    } else {
        this.BinarySearchTree = BinarySearchTree;//global for non node env
    }

}());
