(function () {
    "use strict";
    var isNode = typeof module === 'object' && module.exports;
    /*node or non-node environment*/
    var BST = isNode ? require("./BinarySearchTree.js") : this.BinarySearchTree/*attach to global for non-node*/,
        util = isNode && require("util"),
        isDbg = isNode ? require("./logger").isDebugEnabled: function(){};

    /**
     * @class AVLTree
     * @classdesc
     * Extends BinarySearchTree (see src/BinarySearchTree.js) to provide a Map like functionality
     * backed by a balanced Tree. All functionality of BinarySearchTree is available.
     * In addition Tree is height balanced by rotation whenever an insert is done
     * See rotate(), reBalance() and checkAVLProperty() functions for explanation.
     * Caller doesn't need to invoke these functions,
     * they are internally used when an insert or delete violates the AVL property of the tree.
     * The keys are ordered based on the natural ordering or an optional compare function.
     * @augments BinarySearchTree
     * @param compFn {userCompareFn=} external compare function for ordering keys
     * @desc
     * #### Example -
     * ```js
     * var AVLTree = require("dsjslib").AVLTree
     * var avl=new AVLTree(function(k1,k2){...})
     * ```
     */
    function AVLTree(compFn) {
        BST.call(this, compFn);
    }

    AVLTree.prototype = new BST();
    /**
     * Rotate a node
     * @access private
     * @param node
     * @param rL
     * @return {String}
     */
    AVLTree.prototype.rotate = function (node, rL) {
        if (!rL || !node) {
            return "Insufficient parameters";
        }
        var tree = this,
            mvChild;
        switch (rL) {
            case 'r':
                if (node.leftChild) {
                    mvChild = node.leftChild.rightChild;
                    parentChild(node.parent, node.leftChild, node.isLeftChild() ? 'l' : 'r');
                    parentChild(node.leftChild, node, 'r');
                    parentChild(node, mvChild, 'l');
                    this.reCalcHeight(node);
                }
                break;
            case 'l':
                if (node.rightChild) {
                    mvChild = node.rightChild.leftChild;
                    parentChild(node.parent, node.rightChild, node.isRightChild() ? 'r' : 'l');
                    parentChild(node.rightChild, node, 'l');
                    parentChild(node, mvChild, 'r');
                    this.reCalcHeight(node);
                }
        }

        function parentChild(par, ch, rL) {
            if (par) {
                par[rL === 'r' ? "rightChild" : "leftChild"] = ch;
            } else { //we are rotating at the root
                tree.root = ch;
            }

            if (ch) {
                ch.parent = par;
            }
        }

    };
    /**
     * @access private
     * @param vError
     */
    AVLTree.prototype.rebalance = function (vError) {
        var balance = vError.hdiff, vNode = vError.node;
        var child = balance > 1/*right heavy*/ ? vNode.rightChild : vNode.leftChild;
        //+ve, right heavy, -ve left heavy
        var childBalance = this._nodeHeight(child);
        /**
         * node is right heavy but child is left heavy and vice-versa
         * @type {Boolean}
         */
        var zigzag = balance > 1 ? childBalance < 0 : childBalance > 0;
        if (zigzag/*Requires double rotation*/) {
            //rotate on child first
            this.rotate(child, childBalance > 0 ? 'l' : 'r');
        }
        //rotation on node where violation occurs
        this.rotate(vNode, balance > 1 ? 'l' : 'r');

    };
    /**
     * Insert a key value. It also re-balances the tree
     * @memberof AVLTree.prototype
     * @instance
     * @param key {*}
     * @param value {*}
     * @returns {Object} A closure on the the tree. Calling put() again on this object will
     * insert key value pair in the tree. This is to support easy chaining of put() method.
     * tree.put(k1,v1).put(k2,v2) ...
     */
    AVLTree.prototype.put = function (key, value) {
        var ins = BST.prototype.put.call(this, key, value);
        try {
            this.checkAVLProperty(ins.node);
        } catch (vErr) {
            this.rebalance(vErr);
        }
        return ins;
    };


    /**
     * Delete a key value pair from the Map. Also re-balances the tree
     * @memberof AVLTree.prototype
     * @instance
     * @function delete
     * @param key {*}
     */
    AVLTree.prototype['delete'] = function (key) {
        var node = this.get(key, this.root), p, cNode/*node where violation check should start*/;
        if (node) {
            var num = node.leftChild ? (node.rightChild ? 2 : 1) : (node.rightChild ? 1 : 0);
            switch (num) {
                case 0:
                    p = node.parent;
                    if (p) {
                        var lc = p.leftChild === node;
                        p[lc ? "leftChild" : "rightChild"] = null;
                        node = null;
                        cNode = p;
                    } else {
                        //root
                        this.root = null;
                    }

                    break;
                case 1:
                    //single subtree, the sibling can't have a subtree because
                    // it would have violated the AVL height diff invariant
                    var child = node.leftChild || node.rightChild;
                    node.key = child.key;
                    node.value = child.value;
                    node.leftChild = node.rightChild = null;
                    cNode = node;
                    break;
                case 2:
                    var nextL = this.successor(node.key);
                    var temp = nextL;
                    this['delete'](nextL.key);
                    node.key = temp.key;
                    node.value = temp.value;
            }

            this.reCalcHeight(cNode);
            try {
                this.checkAVLProperty(cNode);
            } catch (vErr) {
                this.rebalance(vErr);
            }

        }

    };

    /**
     * Validates the tree starting at given node (root otherwise)
     * Validates BST as well as AVL properties.
     * @memberof AVLTree.prototype
     * @instance
     * @param node {Object=} Starting node, if not provided start at root
     */
    AVLTree.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("Checking AVL Invariants");
            console.log(util && util.format("lc(h)=%s, rc(h)=%s, node=%s",
                lc ? lc.key + "(" + lc.height + ")" : "null(-1)",
                rc ? rc.key + "(" + rc.height + ")" : "null(-1)",
                node.key + "(" + node.height + ")"))
        }
        var hdiff = Math.abs((lc ? lc.height : -1) - (rc ? rc.height : -1));
        if (hdiff > 1) {
            throw new Error("Invariant check failed at node " + node + " key=" + node.key);
        }
        this.checkInvariants(lc);
        this.checkInvariants(rc);


    };


    AVLTree.prototype._nodeHeight = function (node) {
        var lc = node.leftChild, rc = node.rightChild;
        return (rc ? rc.height : -1) - (lc ? lc.height : -1);

    };

    AVLTree.prototype.checkAVLProperty = function (node) {
        if (!node) return;
        var hdiff = this._nodeHeight(node);
        if (Math.abs(hdiff) > 1) {
            if (isDbg()) {
                console.log("AVL Height violation at Node key" + node.key);
            }
            throw {'node' : node, 'hdiff' : hdiff};
        }
        this.checkAVLProperty(node.parent);


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