buckets.js

// Copyright 2013 Mauricio Santos. All Rights Reserved.
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
//
// Some documentation is borrowed from the official Java API
// as it serves the same porpose.
/**
 * Top level namespace for Buckets, a JavaScript data structure library.
 * @namespace buckets
 */

(function (root, factory) {
    if (typeof define === "function" && define.amd) {
        define([], factory);
    } else if (typeof exports === "object") {
        module.exports = factory();
    } else {
        root.buckets = factory();
    }
}(this, function() {
    'use strict';
    var buckets = {};

    /**
     * Default function to compare element order.
     * @function
     * @private
     */
    buckets.defaultCompare = function(a, b) {
        if (a < b) {
            return -1;
        }
        if (a === b) {
            return 0;
        }
        return 1;
    };

    /**
     * Default function to test equality.
     * @function
     * @private
     */
    buckets.defaultEquals = function(a, b) {
        return a === b;
    };

    /**
     * Default function to convert an object to a string.
     * @function
     * @private
     */
    buckets.defaultToString = function(item) {
        if (item === null) {
            return 'BUCKETS_NULL';
        }
        if (buckets.isUndefined(item)) {
            return 'BUCKETS_UNDEFINED';
        }
        if (buckets.isString(item)) {
            return item;
        }
        return item.toString();
    };

    /**
     * Checks if the given argument is a function.
     * @function
     * @private
     */
    buckets.isFunction = function(func) {
        return (typeof func) === 'function';
    };

    /**
     * Checks if the given argument is undefined.
     * @function
     * @private
     */
    buckets.isUndefined = function(obj) {
        return (typeof obj === 'undefined');
    };

    /**
     * Checks if the given argument is a string.
     * @function
     * @private
     */
    buckets.isString = function(obj) {
        return Object.prototype.toString.call(obj) === '[object String]';
    };

    /**
     * Reverses a compare function.
     * @function
     * @private
     */
    buckets.reverseCompareFunction = function(compareFunction) {
        if (!buckets.isFunction(compareFunction)) {
            return function(a, b) {
                if (a < b) {
                    return 1;
                }
                if (a === b) {
                    return 0;
                }
                return -1;
            };
        }
        return function(d, v) {
            return compareFunction(d, v) * -1;
        };

    };

    /**
     * Returns an equal function given a compare function.
     * @function
     * @private
     */
    buckets.compareToEquals = function(compareFunction) {
        return function(a, b) {
            return compareFunction(a, b) === 0;
        };
    };

    /**
	 * Contains various functions for manipulating arrays.
     * @namespace buckets.arrays
     */
    buckets.arrays = {};

    /**
     * Returns the index of the first occurrence of the specified item
     * within the specified array.
     * @param {*} array The array to search.
     * @param {*} item The array in which to search the element.
     * @param {function(Object,Object):boolean=} equalsFunction Optional function to
     * check equality between two elements. Receives two arguments and returns true if they are equal.
     * @return {number} The index of the first occurrence of the specified element
     * or -1 if not found.
     */
    buckets.arrays.indexOf = function(array, item, equalsFunction) {
        var equals = equalsFunction || buckets.defaultEquals;
        var length = array.length;
        for (var i = 0; i < length; i++) {
            if (equals(array[i], item)) {
                return i;
            }
        }
        return -1;
    };

    /**
     * Returns the index of the last occurrence of the specified element
     * within the specified array.
     * @param {*} array The array in which to search the element.
     * @param {Object} item The element to search.
     * @param {function(Object,Object):boolean=} equalsFunction Optional function to
     * check equality between two elements. Receives two arguments and returns true if they are equal.
     * @return {number} The position of the last occurrence of the specified element
     * within the specified array or -1 if not found.
     */
    buckets.arrays.lastIndexOf = function(array, item, equalsFunction) {
        var equals = equalsFunction || buckets.defaultEquals;
        var length = array.length;
        for (var i = length - 1; i >= 0; i--) {
            if (equals(array[i], item)) {
                return i;
            }
        }
        return -1;
    };

    /**
     * Returns true if the array contains the specified element.
     * @param {*} array The array in which to search the element.
     * @param {Object} item The element to search.
     * @param {function(Object,Object):boolean=} equalsFunction Optional function to
     * check equality between two elements. Receives two arguments and returns true if they are equal.
     * @return {boolean} True if the specified array contains the specified element.
     */
    buckets.arrays.contains = function(array, item, equalsFunction) {
        return buckets.arrays.indexOf(array, item, equalsFunction) >= 0;
    };


    /**
     * Removes the first ocurrence of the specified element from the specified array.
     * @param {*} array The array in which to remove the element.
     * @param {*} item The element to remove.
     * @param {function(Object,Object):boolean=} equalsFunction Optional function to
     * check equality between two elements. Receives two arguments and returns true if they are equal.
     * @return {boolean} True If the array changed after this call.
     */
    buckets.arrays.remove = function(array, item, equalsFunction) {
        var index = buckets.arrays.indexOf(array, item, equalsFunction);
        if (index < 0) {
            return false;
        }
        array.splice(index, 1);
        return true;
    };

    /**
     * Returns the number of elements in the array equal
     * to the specified item.
     * @param {Array} array The array in which to determine the frequency of the element.
     * @param {Object} item The element whose frequency is to be determined.
     * @param {function(Object,Object):boolean=} equalsFunction Optional function to
     * check equality between two elements. Receives two arguments and returns true if they are equal.
     * @return {number} The number of elements in the specified array.
     * equal to the specified object.
     */
    buckets.arrays.frequency = function(array, item, equalsFunction) {
        var equals = equalsFunction || buckets.defaultEquals;
        var length = array.length;
        var freq = 0;
        for (var i = 0; i < length; i++) {
            if (equals(array[i], item)) {
                freq++;
            }
        }
        return freq;
    };

    /**
     * Returns true if the two arrays are equal to one another.
     * Two arrays are considered equal if both arrays contain the same number
     * of elements, all corresponding pairs of elements in the two
     * arrays are equal and are in the same order.
     * @param {Array} array1
     * @param {Array} array2
     * @param {function(Object,Object):boolean=} equalsFunction Optional function to
     * check equality between two elements. Receives two arguments and returns true if they are equal.
     * @return {boolean} True if the two arrays are equal.
     */
    buckets.arrays.equals = function(array1, array2, equalsFunction) {
        var equals = equalsFunction || buckets.defaultEquals;

        if (array1.length !== array2.length) {
            return false;
        }
        var length = array1.length;
        for (var i = 0; i < length; i++) {
            if (!equals(array1[i], array2[i])) {
                return false;
            }
        }
        return true;
    };

    /**
     * Returns a shallow copy of the specified array.
     * @param {*} array The array to copy.
     * @return {Array} A copy of the specified array.
     */
    buckets.arrays.copy = function(array) {
        return array.concat();
    };

    /**
     * Swaps the elements at the specified positions in the specified array.
     * @param {Array} array The array in which to swap elements.
     * @param {number} i The index of one element to be swapped.
     * @param {number} j The index of the other element to be swapped.
     * @return {boolean} True if the array is defined and the indexes are valid.
     */
    buckets.arrays.swap = function(array, i, j) {
        if (i < 0 || i >= array.length || j < 0 || j >= array.length) {
            return false;
        }
        var temp = array[i];
        array[i] = array[j];
        array[j] = temp;
        return true;
    };

    /**
     * Executes a provided function once per array element.
     * @param {Array} array The array in which to iterate.
     * @param {function(Object):*} callback function to execute, it is
     * invoked with one argument: the element value. To break the iteration you can
     * optionally return false inside the callback.
     */
    buckets.arrays.forEach = function(array, callback) {
        var lenght = array.length;
        for (var i = 0; i < lenght; i++) {
            if (callback(array[i]) === false) {
                return;
            }
        }
    };

    /**
     * Creates an empty Linked List.
     * @class A linked list is a data structure consisting of a group of nodes
     * which together represent a sequence.
     * @constructor
     */
    buckets.LinkedList = function() {

        /**
         * First node in the list
         * @type {Object}
         * @private
         */
        this.firstNode = null;

        /**
         * Last node in the list
         * @type {Object}
         * @private
         */
        this.lastNode = null;

        /**
         * Number of elements in the list
         * @type {number}
         * @private
         */
        this.nElements = 0;
    };


    /**
     * Adds an element to this list.
     * @param {Object} item Element to be added.
     * @param {number=} index Optional index to add the element. If no index is specified
     * the element is added to the end of this list.
     * @return {boolean} True if the element was added or false if the index is invalid
     * or if the element is undefined.
     */
    buckets.LinkedList.prototype.add = function(item, index) {
        if (buckets.isUndefined(index)) {
            index = this.nElements;
        }
        if (index < 0 || index > this.nElements || buckets.isUndefined(item)) {
            return false;
        }
        var newNode = this.createNode(item);
        if (this.nElements === 0) {
            // First node in the list.
            this.firstNode = newNode;
            this.lastNode = newNode;
        } else if (index === this.nElements) {
            // Insert at the end.
            this.lastNode.next = newNode;
            this.lastNode = newNode;
        } else if (index === 0) {
            // Change first node.
            newNode.next = this.firstNode;
            this.firstNode = newNode;
        } else {
            var prev = this.nodeAtIndex(index - 1);
            newNode.next = prev.next;
            prev.next = newNode;
        }
        this.nElements++;
        return true;
    };

    /**
     * Returns the first element in this list.
     * @return {*} The first element of the list or undefined if the list is
     * empty.
     */
    buckets.LinkedList.prototype.first = function() {
        if (this.firstNode !== null) {
            return this.firstNode.element;
        }
        return undefined;
    };

    /**
     * Returns the last element in this list.
     * @return {*} The last element in the list or undefined if the list is
     * empty.
     */
    buckets.LinkedList.prototype.last = function() {
        if (this.lastNode !== null) {
            return this.lastNode.element;
        }
        return undefined;
    };


    /**
     * Returns the element at the specified position in this list.
     * @param {number} index Desired index.
     * @return {*} The element at the given index or undefined if the index is
     * out of bounds.
     */
    buckets.LinkedList.prototype.elementAtIndex = function(index) {

        var node = this.nodeAtIndex(index);
        if (node === null) {
            return undefined;
        }
        return node.element;
    };

    /**
     * Returns the index of the first occurrence of the
     * specified element, or -1 if the List does not contain this element.
     * <p>If the elements inside this list are
     * not comparable with the === operator a custom equals function should be
     * provided to perform searches, the function must receive two arguments and
     * return true if they are equal, false otherwise. Example:</p>
     *
     * <pre>
     * var petsAreEqualByName = function(pet1, pet2) {
     *  return pet1.name === pet2.name;
     * }
     * </pre>
     * @param {Object} item Element to search for.
     * @param {function(Object,Object):boolean=} equalsFunction Optional
     * function used to check if two elements are equal.
     * @return {number} The index in this list of the first occurrence
     * of the specified element, or -1 if this list does not contain the
     * element.
     */
    buckets.LinkedList.prototype.indexOf = function(item, equalsFunction) {

        var equalsF = equalsFunction || buckets.defaultEquals;
        if (buckets.isUndefined(item)) {
            return -1;
        }
        var currentNode = this.firstNode;
        var index = 0;
        while (currentNode !== null) {
            if (equalsF(currentNode.element, item)) {
                return index;
            }
            index++;
            currentNode = currentNode.next;
        }
        return -1;
    };

    /**
     * Returns true if this list contains the specified element.
     * <p>If the elements inside the list are
     * not comparable with the === operator a custom equals function should be
     * provided to perform searches, the function must receive two arguments and
     * return true if they are equal, false otherwise. Example:</p>
     *
     * <pre>
     * var petsAreEqualByName = function(pet1, pet2) {
     *  return pet1.name === pet2.name;
     * }
     * </pre>
     * @param {Object} item Element to search for.
     * @param {function(Object,Object):boolean=} equalsFunction Optional
     * function used to check if two elements are equal.
     * @return {boolean} True if this list contains the specified element, false
     * otherwise.
     */
    buckets.LinkedList.prototype.contains = function(item, equalsFunction) {
        return (this.indexOf(item, equalsFunction) >= 0);
    };

    /**
     * Removes the first occurrence of the specified element in this list.
     * <p>If the elements inside the list are
     * not comparable with the === operator a custom equals function should be
     * provided to perform searches, the function must receive two arguments and
     * return true if they are equal, false otherwise. Example:</p>
     *
     * <pre>
     * var petsAreEqualByName = function(pet1, pet2) {
     *  return pet1.name === pet2.name;
     * }
     * </pre>
     * @param {Object} item Element to be removed from this list, if present.
     * @return {boolean} True if the list contained the specified element.
     */
    buckets.LinkedList.prototype.remove = function(item, equalsFunction) {
        var equalsF = equalsFunction || buckets.defaultEquals;
        if (this.nElements < 1 || buckets.isUndefined(item)) {
            return false;
        }
        var previous = null;
        var currentNode = this.firstNode;
        while (currentNode !== null) {

            if (equalsF(currentNode.element, item)) {

                if (currentNode === this.firstNode) {
                    this.firstNode = this.firstNode.next;
                    if (currentNode === this.lastNode) {
                        this.lastNode = null;
                    }
                } else if (currentNode === this.lastNode) {
                    this.lastNode = previous;
                    previous.next = currentNode.next;
                    currentNode.next = null;
                } else {
                    previous.next = currentNode.next;
                    currentNode.next = null;
                }
                this.nElements--;
                return true;
            }
            previous = currentNode;
            currentNode = currentNode.next;
        }
        return false;
    };

    /**
     * Removes all the elements from this list.
     */
    buckets.LinkedList.prototype.clear = function() {
        this.firstNode = null;
        this.lastNode = null;
        this.nElements = 0;
    };

    /**
     * Returns true if this list is equal to the given list.
     * Two lists are equal if they have the same elements in the same order.
     * @param {buckets.LinkedList} other The other list.
     * @param {function(Object,Object):boolean=} equalsFunction Optional
     * function to check if two elements are equal. If the elements in the lists
     * are custom objects you should provide a function, otherwise
     * the === operator is used to check equality between elements.
     * @return {boolean} true if this list is equal to the given list.
     */
    buckets.LinkedList.prototype.equals = function(other, equalsFunction) {
        var eqF = equalsFunction || buckets.defaultEquals;
        if (!(other instanceof buckets.LinkedList)) {
            return false;
        }
        if (this.size() !== other.size()) {
            return false;
        }
        return this.equalsAux(this.firstNode, other.firstNode, eqF);
    };

    /**
     * @private
     */
    buckets.LinkedList.prototype.equalsAux = function(n1, n2, eqF) {
        while (n1 !== null) {
            if (!eqF(n1.element, n2.element)) {
                return false;
            }
            n1 = n1.next;
            n2 = n2.next;
        }
        return true;
    };

    /**
     * Removes the element at the specified position in this list.
     * @param {number} index Given index.
     * @return {*} Removed element or undefined if the index is out of bounds.
     */
    buckets.LinkedList.prototype.removeElementAtIndex = function(index) {

        if (index < 0 || index >= this.nElements) {
            return undefined;
        }
        var element;
        if (this.nElements === 1) {
            //First node in the list.
            element = this.firstNode.element;
            this.firstNode = null;
            this.lastNode = null;
        } else {
            var previous = this.nodeAtIndex(index - 1);
            if (previous === null) {
                element = this.firstNode.element;
                this.firstNode = this.firstNode.next;
            } else if (previous.next === this.lastNode) {
                element = this.lastNode.element;
                this.lastNode = previous;
            }
            if (previous !== null) {
                element = previous.next.element;
                previous.next = previous.next.next;
            }
        }
        this.nElements--;
        return element;
    };

    /**
     * Executes the provided function once per  element present in this list in order.
     * @param {function(Object):*} callback Function to execute, it is
     * invoked with one argument: the element value, to break the iteration you can
     * optionally return false inside the callback.
     */
    buckets.LinkedList.prototype.forEach = function(callback) {
        var currentNode = this.firstNode;
        while (currentNode !== null) {
            if (callback(currentNode.element) === false) {
                break;
            }
            currentNode = currentNode.next;
        }
    };

    /**
     * Reverses the order of the elements in this linked list (makes the last
     * element first, and the first element last).
     */
    buckets.LinkedList.prototype.reverse = function() {
        var previous = null;
        var current = this.firstNode;
        var temp = null;
        while (current !== null) {
            temp = current.next;
            current.next = previous;
            previous = current;
            current = temp;
        }
        temp = this.firstNode;
        this.firstNode = this.lastNode;
        this.lastNode = temp;
    };


    /**
     * Returns an array containing all of the elements in this list in proper
     * sequence.
     * @return {Array.<*>} An array containing all of the elements in this list,
     * in proper sequence.
     */
    buckets.LinkedList.prototype.toArray = function() {
        var array = [];
        var currentNode = this.firstNode;
        while (currentNode !== null) {
            array.push(currentNode.element);
            currentNode = currentNode.next;
        }
        return array;
    };
    /**
     * Returns the number of elements in this list.
     * @return {number} the number of elements in this list.
     */
    buckets.LinkedList.prototype.size = function() {
        return this.nElements;
    };

    /**
     * Returns true if this list contains no elements.
     * @return {boolean} true if this list contains no elements.
     */
    buckets.LinkedList.prototype.isEmpty = function() {
        return this.nElements <= 0;
    };

    /**
     * @private
     */
    buckets.LinkedList.prototype.nodeAtIndex = function(index) {

        if (index < 0 || index >= this.nElements) {
            return null;
        }
        if (index === (this.nElements - 1)) {
            return this.lastNode;
        }
        var node = this.firstNode;
        for (var i = 0; i < index; i++) {
            node = node.next;
        }
        return node;
    };
    /**
     * @private
     */
    buckets.LinkedList.prototype.createNode = function(item) {
        return {
            element: item,
            next: null
        };
    };


    /**
     * Creates an empty dictionary.
     * @class <p>Dictionaries map keys to values; each key can map to at most one value.
     * This implementation accepts any kind of objects as keys.</p>
     *
     * <p>If the keys are custom objects a function which converts keys to unique
     * strings must be provided. Example:</p>
     * <pre>
     * function petToString(pet) {
     *  return pet.name;
     * }
     * </pre>
     * @constructor
     * @param {function(Object):string=} toStrFunction Optional function used
     * to convert keys to strings. If the keys aren't strings or if toString()
     * is not appropriate, a custom function which receives a key and returns a
     * unique string must be provided.
     */
    buckets.Dictionary = function(toStrFunction) {

        /**
         * Object holding the key-value pairs.
         * @type {Object}
         * @private
         */
        this.table = {};

        /**
         * Number of elements in the list.
         * @type {number}
         * @private
         */
        this.nElements = 0;

        /**
         * Function used to convert keys to strings.
         * @type {function(Object):string}
         * @private
         */
        this.toStr = toStrFunction || buckets.defaultToString;
    };

    /**
     * Returns the value to which this dictionary maps the specified key.
     * Returns undefined if this dictionary contains no mapping for this key.
     * @param {Object} key Key whose associated value is to be returned.
     * @return {*} The value to which this dictionary maps the specified key or
     * undefined if the map contains no mapping for this key.
     */
    buckets.Dictionary.prototype.get = function(key) {

        var pair = this.table[this.toStr(key)];
        if (buckets.isUndefined(pair)) {
            return undefined;
        }
        return pair.value;
    };
    /**
     * Associates the specified value with the specified key in this dictionary.
     * If the dictionary previously contained a mapping for this key, the old
     * value is replaced by the specified value.
     * @param {Object} key Key with which the specified value is to be
     * associated.
     * @param {Object} value Value to be associated with the specified key.
     * @return {*} Previous value associated with the specified key, or undefined if
     * there was no mapping for the key or if the key/value are undefined.
     */
    buckets.Dictionary.prototype.set = function(key, value) {

        if (buckets.isUndefined(key) || buckets.isUndefined(value)) {
            return undefined;
        }

        var ret;
        var k = this.toStr(key);
        var previousElement = this.table[k];
        if (buckets.isUndefined(previousElement)) {
            this.nElements++;
            ret = undefined;
        } else {
            ret = previousElement.value;
        }
        this.table[k] = {
            key: key,
            value: value
        };
        return ret;
    };
    /**
     * Removes the mapping for this key from this dictionary if it is present.
     * @param {Object} key Key whose mapping is to be removed from the
     * dictionary.
     * @return {*} Previous value associated with specified key, or undefined if
     * there was no mapping for key.
     */
    buckets.Dictionary.prototype.remove = function(key) {
        var k = this.toStr(key);
        var previousElement = this.table[k];
        if (!buckets.isUndefined(previousElement)) {
            delete this.table[k];
            this.nElements--;
            return previousElement.value;
        }
        return undefined;
    };
    /**
     * Returns an array containing all of the keys in this dictionary.
     * @return {Array} An array containing all of the keys in this dictionary.
     */
    buckets.Dictionary.prototype.keys = function() {
        var array = [];
        for (var name in this.table) {
            if (this.table.hasOwnProperty(name)) {
                array.push(this.table[name].key);
            }
        }
        return array;
    };
    /**
     * Returns an array containing all of the values in this dictionary.
     * @return {Array} An array containing all of the values in this dictionary.
     */
    buckets.Dictionary.prototype.values = function() {
        var array = [];
        for (var name in this.table) {
            if (this.table.hasOwnProperty(name)) {
                array.push(this.table[name].value);
            }
        }
        return array;
    };

    /**
     * Executes the provided function once per key-value pair
     * present in this dictionary.
     * @param {function(Object,Object):*} callback function to execute, it is
     * invoked with two arguments: key and value. To break the iteration you can
     * optionally return false inside the callback.
     */
    buckets.Dictionary.prototype.forEach = function(callback) {
        for (var name in this.table) {
            if (this.table.hasOwnProperty(name)) {
                var pair = this.table[name];
                var ret = callback(pair.key, pair.value);
                if (ret === false) {
                    return;
                }
            }
        }
    };

    /**
     * Returns true if this dictionary contains a mapping for the specified key.
     * @param {Object} key Key whose presence in this dictionary is to be
     * tested.
     * @return {boolean} True if this dictionary contains a mapping for the
     * specified key.
     */
    buckets.Dictionary.prototype.containsKey = function(key) {
        return !buckets.isUndefined(this.get(key));
    };
    /**
     * Removes all mappings from this dictionary.
     * @this {buckets.Dictionary}
     */
    buckets.Dictionary.prototype.clear = function() {

        this.table = {};
        this.nElements = 0;
    };
    /**
     * Returns the number of keys in this dictionary.
     * @return {number} The number of key-value mappings in this dictionary.
     */
    buckets.Dictionary.prototype.size = function() {
        return this.nElements;
    };

    /**
     * Returns true if this dictionary contains no mappings.
     * @return {boolean} True if this dictionary contains no mappings.
     */
    buckets.Dictionary.prototype.isEmpty = function() {
        return this.nElements <= 0;
    };

    /**
     * Creates an empty multi dictionary.
     * @class <p>A multi dictionary is a special kind of dictionary that holds
     * multiple values against each key. Setting a value into the dictionary will
     * add the value to an array at that key. Getting a key will return an array
     * holding all of the values set to that key.
     * This implementation accepts any kind of objects as keys.</p>
     *
     * <p>If the keys are custom objects a function which converts keys to unique strings must be
     * provided. Example:</p>
     *
     * <pre>
     * function petToString(pet) {
     *  return pet.type + ' ' + pet.name;
     * }
     * </pre>
     * <p>If the values are custom objects a function to check equality between values
     * must be provided. Example:</p>
     *
     * <pre>
     * function petsAreEqualByAge(pet1,pet2) {
     *  return pet1.age===pet2.age;
     * }
     * </pre>
     * @constructor
     * @param {function(Object):string=} toStrFunction optional function
     * to convert keys to strings. If the keys aren't strings or if toString()
     * is not appropriate, a custom function which receives a key and returns a
     * unique string must be provided.
     * @param {function(Object,Object):boolean=} valuesEqualsFunction optional
     * function to check if two values are equal.
     *
     */
    buckets.MultiDictionary = function(toStrFunction, valuesEqualsFunction) {
        // Call the parent's constructor
        this.parent = new buckets.Dictionary(toStrFunction);
        this.equalsF = valuesEqualsFunction || buckets.defaultEquals;
    };

    /**
     * Returns an array holding the values to which this dictionary maps
     * the specified key.
     * Returns an empty array if this dictionary contains no mappings for this key.
     * @param {Object} key Key whose associated values are to be returned.
     * @return {Array} An array holding the values to which this dictionary maps
     * the specified key.
     */
    buckets.MultiDictionary.prototype.get = function(key) {
        var values = this.parent.get(key);
        if (buckets.isUndefined(values)) {
            return [];
        }
        return buckets.arrays.copy(values);
    };

    /**
     * Adds the value to an array associated with the specified key, if
     * it is not already present.
     * @param {Object} key Key which the specified value is to be
     * associated.
     * @param {Object} value The value to add to the array at the key.
     * @return {boolean} True if the value was not already associated with that key.
     */
    buckets.MultiDictionary.prototype.set = function(key, value) {

        if (buckets.isUndefined(key) || buckets.isUndefined(value)) {
            return false;
        }
        if (!this.containsKey(key)) {
            this.parent.set(key, [value]);
            return true;
        }
        var array = this.parent.get(key);
        if (buckets.arrays.contains(array, value, this.equalsF)) {
            return false;
        }
        array.push(value);
        return true;
    };

    /**
     * Removes the specified value from the array of values associated with the
     * specified key. If a value isn't given, all values associated with the specified
     * key are removed.
     * @param {Object} key Key whose mapping is to be removed from the
     * dictionary.
     * @param {Object=} value Optional argument to specify the value to remove
     * from the array associated with the specified key.
     * @return {*} True if the dictionary changed, false if the key doesn't exist or
     * if the specified value isn't associated with the specified key.
     */
    buckets.MultiDictionary.prototype.remove = function(key, value) {
        if (buckets.isUndefined(value)) {
            var v = this.parent.remove(key);
            if (buckets.isUndefined(v)) {
                return false;
            }
            return true;
        }
        var array = this.parent.get(key);
        if (buckets.arrays.remove(array, value, this.equalsF)) {
            if (array.length === 0) {
                this.parent.remove(key);
            }
            return true;
        }
        return false;
    };

    /**
     * Returns an array containing all of the keys in this dictionary.
     * @return {Array} an array containing all of the keys in this dictionary.
     */
    buckets.MultiDictionary.prototype.keys = function() {
        return this.parent.keys();
    };

    /**
     * Returns an array containing all of the values in this dictionary.
     * @return {Array} An array containing all of the values in this dictionary.
     */
    buckets.MultiDictionary.prototype.values = function() {
        var values = this.parent.values();
        var array = [];
        for (var i = 0; i < values.length; i++) {
            var v = values[i];
            for (var j = 0; j < v.length; j++) {
                array.push(v[j]);
            }
        }
        return array;
    };

    /**
     * Returns true if this dictionary has at least one value associatted the specified key.
     * @param {Object} key Key whose presence in this dictionary is to be
     * tested.
     * @return {boolean} True if this dictionary has at least one value associatted
     * the specified key.
     */
    buckets.MultiDictionary.prototype.containsKey = function(key) {
        return this.parent.containsKey(key);
    };

    /**
     * Removes all mappings from this dictionary.
     */
    buckets.MultiDictionary.prototype.clear = function() {
        return this.parent.clear();
    };

    /**
     * Returns the number of keys in this dictionary.
     * @return {number} The number of key-value mappings in this dictionary.
     */
    buckets.MultiDictionary.prototype.size = function() {
        return this.parent.size();
    };

    /**
     * Returns true if this dictionary contains no mappings.
     * @return {boolean} True if this dictionary contains no mappings.
     */
    buckets.MultiDictionary.prototype.isEmpty = function() {
        return this.parent.isEmpty();
    };

    /**
     * Creates an empty Heap.
     * @class
     * <p>A heap is a binary tree, where the nodes maintain the heap property:
     * each node is smaller than each of its children.
     * This implementation uses an array to store elements.</p>
     * <p>If the inserted elements are custom objects a compare function must be provided,
     *  at construction time, otherwise the <=, === and >= operators are
     * used to compare elements. Example:</p>
     *
     * <pre>
     * function compare(a, b) {
     *  if (a is less than b by some ordering criterion) {
     *     return -1;
     *  } if (a is greater than b by the ordering criterion) {
     *     return 1;
     *  }
     *  // a must be equal to b
     *  return 0;
     * }
     * </pre>
     *
     * <p>If a Max-Heap is wanted (greater elements on top) you can a provide a
     * reverse compare function to accomplish that behavior. Example:</p>
     *
     * <pre>
     * function reverseCompare(a, b) {
     *  if (a is less than b by some ordering criterion) {
     *     return 1;
     *  } if (a is greater than b by the ordering criterion) {
     *     return -1;
     *  }
     *  // a must be equal to b
     *  return 0;
     * }
     * </pre>
     *
     * @constructor
     * @param {function(Object,Object):number=} compareFunction Optional
     * function used to compare two elements. Must return a negative integer,
     * zero, or a positive integer as the first argument is less than, equal to,
     * or greater than the second.
     */
    buckets.Heap = function(compareFunction) {

        /**
         * Array used to store the elements od the heap.
         * @type {Array.<Object>}
         * @private
         */
        this.data = [];

        /**
         * Function used to compare elements.
         * @type {function(Object,Object):number}
         * @private
         */
        this.compare = compareFunction || buckets.defaultCompare;
    };
    /**
     * Returns the index of the left child of the node at the given index.
     * @param {number} nodeIndex The index of the node to get the left child
     * for.
     * @return {number} The index of the left child.
     * @private
     */
    buckets.Heap.prototype.leftChildIndex = function(nodeIndex) {
        return (2 * nodeIndex) + 1;
    };
    /**
     * Returns the index of the right child of the node at the given index.
     * @param {number} nodeIndex The index of the node to get the right child
     * for.
     * @return {number} The index of the right child.
     * @private
     */
    buckets.Heap.prototype.rightChildIndex = function(nodeIndex) {
        return (2 * nodeIndex) + 2;
    };
    /**
     * Returns the index of the parent of the node at the given index.
     * @param {number} nodeIndex The index of the node to get the parent for.
     * @return {number} The index of the parent.
     * @private
     */
    buckets.Heap.prototype.parentIndex = function(nodeIndex) {
        return Math.floor((nodeIndex - 1) / 2);
    };
    /**
     * Returns the index of the smaller child node (if it exists).
     * @param {number} leftChild left child index.
     * @param {number} rightChild right child index.
     * @return {number} the index with the minimum value or -1 if it doesn't
     * exists.
     * @private
     */
    buckets.Heap.prototype.minIndex = function(leftChild, rightChild) {

        if (rightChild >= this.data.length) {
            if (leftChild >= this.data.length) {
                return -1;
            } else {
                return leftChild;
            }
        } else {
            if (this.compare(this.data[leftChild], this.data[rightChild]) <= 0) {
                return leftChild;
            } else {
                return rightChild;
            }
        }
    };
    /**
     * Moves the node at the given index up to its proper place in the heap.
     * @param {number} index The index of the node to move up.
     * @private
     */
    buckets.Heap.prototype.siftUp = function(index) {

        var parent = this.parentIndex(index);
        while (index > 0 && this.compare(this.data[parent], this.data[index]) > 0) {
            buckets.arrays.swap(this.data, parent, index);
            index = parent;
            parent = this.parentIndex(index);
        }
    };
    /**
     * Moves the node at the given index down to its proper place in the heap.
     * @param {number} nodeIndex The index of the node to move down.
     * @private
     */
    buckets.Heap.prototype.siftDown = function(nodeIndex) {

        //smaller child index
        var min = this.minIndex(this.leftChildIndex(nodeIndex), this.rightChildIndex(nodeIndex));

        while (min >= 0 && this.compare(this.data[nodeIndex], this.data[min]) > 0) {
            buckets.arrays.swap(this.data, min, nodeIndex);
            nodeIndex = min;
            min = this.minIndex(this.leftChildIndex(nodeIndex), this.rightChildIndex(nodeIndex));
        }
    };
    /**
     * Retrieves but does not remove the root element of this heap.
     * @return {*} The value at the root of the heap. Returns undefined if the
     * heap is empty.
     */
    buckets.Heap.prototype.peek = function() {

        if (this.data.length > 0) {
            return this.data[0];
        } else {
            return undefined;
        }
    };
    /**
     * Adds the given element into the heap.
     * @param {*} element The element.
     * @return True if the element was added or false if it is undefined.
     */
    buckets.Heap.prototype.add = function(element) {
        if (buckets.isUndefined(element)) {
            return undefined;
        }
        this.data.push(element);
        this.siftUp(this.data.length - 1);
        return true;
    };

    /**
     * Retrieves and removes the root element of this heap.
     * @return {*} The value removed from the root of the heap. Returns
     * undefined if the heap is empty.
     */
    buckets.Heap.prototype.removeRoot = function() {

        if (this.data.length > 0) {
            var obj = this.data[0];
            this.data[0] = this.data[this.data.length - 1];
            this.data.splice(this.data.length - 1, 1);
            if (this.data.length > 0) {
                this.siftDown(0);
            }
            return obj;
        }
        return undefined;
    };
    /**
     * Returns true if this heap contains the specified element.
     * @param {Object} element Element to search for.
     * @return {boolean} True if this Heap contains the specified element, false
     * otherwise.
     */
    buckets.Heap.prototype.contains = function(element) {
        var equF = buckets.compareToEquals(this.compare);
        return buckets.arrays.contains(this.data, element, equF);
    };
    /**
     * Returns the number of elements in this heap.
     * @return {number} The number of elements in this heap.
     */
    buckets.Heap.prototype.size = function() {
        return this.data.length;
    };
    /**
     * Checks if this heap is empty.
     * @return {boolean} True if and only if this heap contains no items; false
     * otherwise.
     */
    buckets.Heap.prototype.isEmpty = function() {
        return this.data.length <= 0;
    };
    /**
     * Removes all of the elements from this heap.
     */
    buckets.Heap.prototype.clear = function() {
        this.data.length = 0;
    };

    /**
     * Executes the provided function once per element present in this heap in
     * no particular order.
     * @param {function(Object):*} callback Function to execute, it is
     * invoked with one argument: the element value, to break the iteration you can
     * optionally return false.
     */
    buckets.Heap.prototype.forEach = function(callback) {
        buckets.arrays.forEach(this.data, callback);
    };

    /**
     * Creates an empty Stack.
     * @class A Stack is a Last-In-First-Out (LIFO) data structure, the last
     * element added to the stack will be the first one to be removed. This
     * implementation uses a linked list as a container.
     * @constructor
     */
    buckets.Stack = function() {

        /**
         * List containing the elements.
         * @type buckets.LinkedList
         * @private
         */
        this.list = new buckets.LinkedList();
    };
    /**
     * Pushes an item onto the top of this stack.
     * @param {Object} elem The element to be pushed onto this stack.
     * @return {boolean} True if the element was pushed or false if it is undefined.
     */
    buckets.Stack.prototype.push = function(elem) {
        return this.list.add(elem, 0);
    };
    /**
     * Pushes an item onto the top of this stack.
     * @param {Object} elem The element to be pushed onto this stack.
     * @return {boolean} true If the element was pushed or false if it is undefined.
     */
    buckets.Stack.prototype.add = function(elem) {
        return this.list.add(elem, 0);
    };
    /**
     * Removes the object at the top of this stack and returns that object.
     * @return {*} The object at the top of this stack or undefined if the
     * stack is empty.
     */
    buckets.Stack.prototype.pop = function() {
        return this.list.removeElementAtIndex(0);
    };
    /**
     * Looks at the object at the top of this stack without removing it from the
     * stack.
     * @return {*} The object at the top of this stack or undefined if the
     * stack is empty.
     */
    buckets.Stack.prototype.peek = function() {
        return this.list.first();
    };
    /**
     * Returns the number of elements in this stack.
     * @return {number} The number of elements in this stack.
     */
    buckets.Stack.prototype.size = function() {
        return this.list.size();
    };

    /**
     * Returns true if this stack contains the specified element.
     * <p>If the elements inside this stack are
     * not comparable with the === operator, a custom equals function must be
     * provided to perform searches, the function must receive two arguments and
     * return true if they are equal, false otherwise. Example:</p>
     *
     * <pre>
     * var petsAreEqualByName = function(pet1, pet2) {
     *  return pet1.name === pet2.name;
     * }
     * </pre>
     * @param {Object} elem Element to search for.
     * @param {function(Object,Object):boolean=} equalsFunction Optional
     * function to check if two elements are equal.
     * @return {boolean} True if this stack contains the specified element,
     * false otherwise.
     */
    buckets.Stack.prototype.contains = function(elem, equalsFunction) {
        return this.list.contains(elem, equalsFunction);
    };
    /**
     * Checks if this stack is empty.
     * @return {boolean} True if and only if this stack contains no items; false
     * otherwise.
     */
    buckets.Stack.prototype.isEmpty = function() {
        return this.list.isEmpty();
    };
    /**
     * Removes all of the elements from this stack.
     */
    buckets.Stack.prototype.clear = function() {
        this.list.clear();
    };

    /**
     * Executes the provided function once per element present in this stack in
     * LIFO order.
     * @param {function(Object):*} callback Function to execute, it is
     * invoked with one argument: the element value, to break the iteration you can
     * optionally return false inside the callback.
     */
    buckets.Stack.prototype.forEach = function(callback) {
        this.list.forEach(callback);
    };

    /**
     * Creates an empty queue.
     * @class A queue is a First-In-First-Out (FIFO) data structure, the first
     * element added to the queue will be the first one to be removed. This
     * implementation uses a linked list as a container.
     * @constructor
     */
    buckets.Queue = function() {

        /**
         * List containing the elements.
         * @type buckets.LinkedList
         * @private
         */
        this.list = new buckets.LinkedList();
    };
    /**
     * Inserts the specified element into the end of this queue.
     * @param {Object} elem The element to insert.
     * @return {boolean} True if the element was inserted, or false if it is undefined.
     */
    buckets.Queue.prototype.enqueue = function(elem) {
        return this.list.add(elem);
    };
    /**
     * Inserts the specified element into the end of this queue. Equivalent to enqueue.
     * @param {Object} elem The element to insert.
     * @return {boolean} True if the element was inserted, or false if it is undefined.
     */
    buckets.Queue.prototype.add = function(elem) {
        return this.list.add(elem);
    };
    /**
     * Retrieves and removes the head of this queue.
     * @return {*} The head of this queue, or undefined if this queue is empty.
     */
    buckets.Queue.prototype.dequeue = function() {
        if (this.list.size() !== 0) {
            var el = this.list.first();
            this.list.removeElementAtIndex(0);
            return el;
        }
        return undefined;
    };
    /**
     * Retrieves, but does not remove, the head of this queue.
     * @return {*} The head of this queue, or undefined if this queue is empty.
     */
    buckets.Queue.prototype.peek = function() {

        if (this.list.size() !== 0) {
            return this.list.first();
        }
        return undefined;
    };

    /**
     * Returns the number of elements in this queue.
     * @return {number} The number of elements in this queue.
     */
    buckets.Queue.prototype.size = function() {
        return this.list.size();
    };

    /**
     * Returns true if this queue contains the specified element.
     * <p>If the elements inside this stack are
     * not comparable with the === operator, a custom equals function should be
     * provided to perform searches, the function must receive two arguments and
     * return true if they are equal, false otherwise. Example:</p>
     *
     * <pre>
     * var petsAreEqualByName = function(pet1, pet2) {
     *  return pet1.name === pet2.name;
     * }
     * </pre>
     * @param {Object} elem Element to search for.
     * @param {function(Object,Object):boolean=} equalsFunction Optional
     * function to check if two elements are equal.
     * @return {boolean} True if this queue contains the specified element,
     * false otherwise.
     */
    buckets.Queue.prototype.contains = function(elem, equalsFunction) {
        return this.list.contains(elem, equalsFunction);
    };

    /**
     * Checks if this queue is empty.
     * @return {boolean} True if and only if this queue contains no items; false
     * otherwise.
     */
    buckets.Queue.prototype.isEmpty = function() {
        return this.list.size() <= 0;
    };

    /**
     * Removes all the elements from this queue.
     */
    buckets.Queue.prototype.clear = function() {
        this.list.clear();
    };

    /**
     * Executes the provided function once for each element present in this queue in
     * FIFO order.
     * @param {function(Object):*} callback Function to execute, it is
     * invoked with one argument: the element value, to break the iteration you can
     * optionally return false inside the callback.
     */
    buckets.Queue.prototype.forEach = function(callback) {
        this.list.forEach(callback);
    };

    /**
     * Creates an empty priority queue.
     * @class <p>In a priority queue each element is associated with a "priority",
     * elements are dequeued in highest-priority-first order (the elements with the
     * highest priority are dequeued first). Priority Queues are implemented as heaps.
     * If the inserted elements are custom objects a compare function must be provided,
     * otherwise the <=, === and >= operators are used to compare object priority.</p>
     * <pre>
     * function compare(a, b) {
     *  if (a is less than b by some ordering criterion) {
     *     return -1;
     *  } if (a is greater than b by the ordering criterion) {
     *     return 1;
     *  }
     *  // a must be equal to b
     *  return 0;
     * }
     * </pre>
     * @constructor
     * @param {function(Object,Object):number=} compareFunction Optional
     * function used to compare two element priorities. Must return a negative integer,
     * zero, or a positive integer as the first argument is less than, equal to,
     * or greater than the second.
     */
    buckets.PriorityQueue = function(compareFunction) {
        this.heap = new buckets.Heap(buckets.reverseCompareFunction(compareFunction));
    };

    /**
     * Inserts the specified element into this priority queue.
     * @param {Object} element The element to insert.
     * @return {boolean} True if the element was inserted, or false if it is undefined.
     */
    buckets.PriorityQueue.prototype.enqueue = function(element) {
        return this.heap.add(element);
    };

    /**
     * Inserts the specified element into this priority queue, it is equivalent to enqueue.
     * @param {Object} element the element to insert.
     * @return {boolean} True if the element was inserted, or false if it is undefined.
     */
    buckets.PriorityQueue.prototype.add = function(element) {
        return this.heap.add(element);
    };

    /**
    * Retrieves and removes the highest priority element of this queue.
    * @return {*} The highest priority element of this queue,
    or undefined if this queue is empty.
    */
    buckets.PriorityQueue.prototype.dequeue = function() {
        if (this.heap.size() !== 0) {
            var el = this.heap.peek();
            this.heap.removeRoot();
            return el;
        }
        return undefined;
    };


    /**
     * Retrieves, but does not remove, the highest priority element of this queue.
     * @return {*} The highest priority element of this queue, or undefined if this queue is empty.
     */
    buckets.PriorityQueue.prototype.peek = function() {
        return this.heap.peek();
    };

    /**
     * Returns true if this priority queue contains the specified element.
     * @param {Object} element Element to search for.
     * @return {boolean} True if this priority queue contains the specified element,
     * false otherwise.
     */
    buckets.PriorityQueue.prototype.contains = function(element) {
        return this.heap.contains(element);
    };

    /**
     * Checks if this priority queue is empty.
     * @return {boolean} True if and only if this priority queue contains no items; false
     * otherwise.
     */
    buckets.PriorityQueue.prototype.isEmpty = function() {
        return this.heap.isEmpty();
    };

    /**
     * Returns the number of elements in this priority queue.
     * @return {number} The number of elements in this priority queue.
     */
    buckets.PriorityQueue.prototype.size = function() {
        return this.heap.size();
    };

    /**
     * Removes all elements from this priority queue.
     */
    buckets.PriorityQueue.prototype.clear = function() {
        this.heap.clear();
    };

    /**
     * Executes the provided function once per element present in this queue in
     * no particular order.
     * @param {function(Object):*} callback Function to execute, it is
     * invoked with one argument: the element value, to break the iteration you can
     * optionally return false inside the callback.
     */
    buckets.PriorityQueue.prototype.forEach = function(callback) {
        this.heap.forEach(callback);
    };


    /**
     * Creates an empty set.
     * @class <p>A set is a data structure that contains no duplicate items.</p>
     * <p>If the inserted elements are custom objects a function
     * which converts elements to unique strings must be provided. Example:</p>
     *
     * <pre>
     * function petToString(pet) {
     *  return pet.type + ' ' + pet.name;
     * }
     * </pre>
     *
     * @constructor
     * @param {function(Object):string=} toStringFunction Optional function used
     * to convert elements to unique strings. If the elements aren't strings or if toString()
     * is not appropriate, a custom function which receives a onject and returns a
     * unique string must be provided.
     */
    buckets.Set = function(toStringFunction) {
        this.dictionary = new buckets.Dictionary(toStringFunction);
    };

    /**
     * Returns true if this set contains the specified element.
     * @param {Object} element Element to search for.
     * @return {boolean} True if this set contains the specified element,
     * false otherwise.
     */
    buckets.Set.prototype.contains = function(element) {
        return this.dictionary.containsKey(element);
    };

    /**
     * Adds the specified element to this set if it is not already present.
     * @param {Object} element The element to insert.
     * @return {boolean} True if this set did not already contain the specified element.
     */
    buckets.Set.prototype.add = function(element) {
        if (this.contains(element) || buckets.isUndefined(element)) {
            return false;
        } else {
            this.dictionary.set(element, element);
            return true;
        }
    };

    /**
     * Performs an intersection between this and another set.
     * Removes all values that are not present in this set and the given set.
     * @param {buckets.Set} otherSet Other set.
     */
    buckets.Set.prototype.intersection = function(otherSet) {
        var set = this;
        this.forEach(function(element) {
            if (!otherSet.contains(element)) {
                set.remove(element);
            }
        });
    };

    /**
     * Performs a union between this and another set.
     * Adds all values from the given set to this set.
     * @param {buckets.Set} otherSet Other set.
     */
    buckets.Set.prototype.union = function(otherSet) {
        var set = this;
        otherSet.forEach(function(element) {
            set.add(element);
        });
    };

    /**
     * Performs a difference between this and another set.
     * Removes from this set all the values that are present in the given set.
     * @param {buckets.Set} otherSet other set.
     */
    buckets.Set.prototype.difference = function(otherSet) {
        var set = this;
        otherSet.forEach(function(element) {
            set.remove(element);
        });
    };

    /**
     * Checks whether the given set contains all the elements of this set.
     * @param {buckets.Set} otherSet Other set.
     * @return {boolean} True if this set is a subset of the given set.
     */
    buckets.Set.prototype.isSubsetOf = function(otherSet) {

        if (this.size() > otherSet.size()) {
            return false;
        }

        var isSub = true;
        this.forEach(function(element) {
            if (!otherSet.contains(element)) {
                isSub = false;
                return false;
            }
        });
        return isSub;
    };

    /**
     * Removes the specified element from this set if it is present.
     * @return {boolean} True if this set contained the specified element.
     */
    buckets.Set.prototype.remove = function(element) {
        if (!this.contains(element)) {
            return false;
        } else {
            this.dictionary.remove(element);
            return true;
        }
    };

    /**
     * Executes the provided function once per element
     * present in this set.
     * @param {function(Object):*} callback Function to execute, it is
     * invoked with one argument: the element. To break the iteration you can
     * optionally return false inside the callback.
     */
    buckets.Set.prototype.forEach = function(callback) {
        this.dictionary.forEach(function(k, v) {
            return callback(v);
        });
    };

    /**
     * Returns an array containing all the elements in this set in arbitrary order.
     * @return {Array} An array containing all the elements in this set.
     */
    buckets.Set.prototype.toArray = function() {
        return this.dictionary.values();
    };

    /**
     * Returns true if this set contains no elements.
     * @return {boolean} True if this set contains no elements.
     */
    buckets.Set.prototype.isEmpty = function() {
        return this.dictionary.isEmpty();
    };

    /**
     * Returns the number of elements in this set.
     * @return {number} The number of elements in this set.
     */
    buckets.Set.prototype.size = function() {
        return this.dictionary.size();
    };

    /**
     * Removes all the elements from this set.
     */
    buckets.Set.prototype.clear = function() {
        this.dictionary.clear();
    };

    /**
     * Creates an empty bag.
     * @class <p>A bag is a special kind of set in which members are
     * allowed to appear more than once.</p>
     * <p>If the inserted elements are custom objects a function
     * that maps elements to unique strings must be provided at construction time. Example:</p>
     *
     * <pre>
     * function petToUniqueString(pet) {
     *  return pet.type + ' ' + pet.name;
     * }
     * </pre>
     *
     * @constructor
     * @param {function(Object):string=} toStrFunction Optional function used
     * to convert elements to strings. If the elements aren't strings or if toString()
     * is not appropriate, a custom function which receives an object and returns a
     * unique string must be provided.
     */
    buckets.Bag = function(toStrFunction) {
        this.toStrF = toStrFunction || buckets.defaultToString;
        this.dictionary = new buckets.Dictionary(this.toStrF);
        this.nElements = 0;
    };

    /**
     * Adds nCopies of the specified object to this bag.
     * @param {Object} element Element to add.
     * @param {number=} nCopies The number of copies to add, if this argument is
     * undefined 1 copy is added.
     * @return {boolean} True unless element is undefined.
     */
    buckets.Bag.prototype.add = function(element, nCopies) {

        if (isNaN(nCopies) || buckets.isUndefined(nCopies)) {
            nCopies = 1;
        }
        if (buckets.isUndefined(element) || nCopies <= 0) {
            return false;
        }

        if (!this.contains(element)) {
            var node = {
                value: element,
                copies: nCopies
            };
            this.dictionary.set(element, node);
        } else {
            this.dictionary.get(element).copies += nCopies;
        }
        this.nElements += nCopies;
        return true;
    };

    /**
     * Counts the number of copies of the specified object in this bag.
     * @param {Object} element The object to search for.
     * @return {number} The number of copies of the object, 0 if not found.
     */
    buckets.Bag.prototype.count = function(element) {

        if (!this.contains(element)) {
            return 0;
        } else {
            return this.dictionary.get(element).copies;
        }
    };

    /**
     * Returns true if this bag contains the specified element.
     * @param {Object} element Rlement to search for.
     * @return {boolean} True if this bag contains the specified element,
     * false otherwise.
     */
    buckets.Bag.prototype.contains = function(element) {
        return this.dictionary.containsKey(element);
    };

    /**
     * Removes nCopies of the specified object in this bag.
     * If the number of copies to remove is greater than the actual number
     * of copies in the bag, all copies are removed.
     * @param {Object} element Element to remove.
     * @param {number=} nCopies The number of copies to remove, if this argument is
     * undefined 1 copy is removed.
     * @return {boolean} True if at least 1 element was removed.
     */
    buckets.Bag.prototype.remove = function(element, nCopies) {

        if (isNaN(nCopies) || buckets.isUndefined(nCopies)) {
            nCopies = 1;
        }
        if (buckets.isUndefined(element) || nCopies <= 0) {
            return false;
        }

        if (!this.contains(element)) {
            return false;
        } else {
            var node = this.dictionary.get(element);
            if (nCopies > node.copies) {
                this.nElements -= node.copies;
            } else {
                this.nElements -= nCopies;
            }
            node.copies -= nCopies;
            if (node.copies <= 0) {
                this.dictionary.remove(element);
            }
            return true;
        }
    };

    /**
     * Returns an array containing all of the elements in this bag in arbitrary order,
     * including multiple copies.
     * @return {Array} An array containing all of the elements in this bag.
     */
    buckets.Bag.prototype.toArray = function() {
        var a = [];
        var values = this.dictionary.values();
        var vl = values.length;
        for (var i = 0; i < vl; i++) {
            var node = values[i];
            var element = node.value;
            var copies = node.copies;
            for (var j = 0; j < copies; j++) {
                a.push(element);
            }
        }
        return a;
    };

    /**
     * Returns a set of unique elements in this bag.
     * @return {buckets.Set} A set of unique elements in this bag.
     */
    buckets.Bag.prototype.toSet = function() {
        var set = new buckets.Set(this.toStrF);
        var elements = this.dictionary.values();
        var l = elements.length;
        for (var i = 0; i < l; i++) {
            var value = elements[i].value;
            set.add(value);
        }
        return set;
    };

    /**
     * Executes the provided function once per element
     * present in this bag, including multiple copies.
     * @param {function(Object):*} callback Function to execute, it is
     * invoked with one argument: the element. To break the iteration you can
     * optionally return false inside the callback.
     */
    buckets.Bag.prototype.forEach = function(callback) {
        this.dictionary.forEach(function(k, v) {
            var value = v.value;
            var copies = v.copies;
            for (var i = 0; i < copies; i++) {
                if (callback(value) === false) {
                    return false;
                }
            }
            return true;
        });
    };
    /**
     * Returns the number of elements in this bag.
     * @return {number} The number of elements in this bag.
     */
    buckets.Bag.prototype.size = function() {
        return this.nElements;
    };

    /**
     * Returns true if this bag contains no elements.
     * @return {boolean} true If this bag contains no elements.
     */
    buckets.Bag.prototype.isEmpty = function() {
        return this.nElements === 0;
    };

    /**
     * Removes all the elements from this bag.
     */
    buckets.Bag.prototype.clear = function() {
        this.nElements = 0;
        this.dictionary.clear();
    };

    /**
     * Creates an empty binary search tree.
     * @class <p>Formally, a binary search tree is a node-based binary tree data structure which
     * has the following properties:</p>
     * <ul>
     * <li>The left subtree of a node contains only nodes with elements less
     * than the node's element.</li>
     * <li>The right subtree of a node contains only nodes with elements greater
     * than the node's element.</li>
     * <li>Both the left and right subtrees must also be binary search trees.</li>
     * </ul>
     * <p>If the inserted elements are custom objects a compare function must
     * be provided at construction time, otherwise the <=, === and >= operators are
     * used to compare elements. Example:</p>
     * <pre>
     * function compare(a, b) {
     *  if (a is less than b by some ordering criterion) {
     *     return -1;
     *  } if (a is greater than b by the ordering criterion) {
     *     return 1;
     *  }
     *  // a must be equal to b
     *  return 0;
     * }
     * </pre>
     * @constructor
     * @param {function(Object,Object):number=} compareFunction Optional
     * function used to compare two elements. Must return a negative integer,
     * zero, or a positive integer as the first argument is less than, equal to,
     * or greater than the second.
     */
    buckets.BSTree = function(compareFunction) {
        this.root = null;
        this.compare = compareFunction || buckets.defaultCompare;
        this.nElements = 0;
    };

    /**
     * Adds the specified element to this tree if it is not already present.
     * @param {Object} element the element to insert.
     * @return {boolean} true If this tree did not already contain the specified element.
     */
    buckets.BSTree.prototype.add = function(element) {
        if (buckets.isUndefined(element)) {
            return false;
        }

        if (this.insertNode(this.createNode(element)) !== null) {
            this.nElements++;
            return true;
        }
        return false;
    };

    /**
     * Removes all the elements from this tree.
     */
    buckets.BSTree.prototype.clear = function() {
        this.root = null;
        this.nElements = 0;
    };

    /**
     * Returns true if this tree contains no elements.
     * @return {boolean} True if this tree contains no elements.
     */
    buckets.BSTree.prototype.isEmpty = function() {
        return this.nElements === 0;
    };

    /**
     * Returns the number of elements in this tree.
     * @return {number} The number of elements in this tree.
     */
    buckets.BSTree.prototype.size = function() {
        return this.nElements;
    };

    /**
     * Returns true if this tree contains the specified element.
     * @param {Object} element Element to search for.
     * @return {boolean} True if this tree contains the specified element,
     * false otherwise.
     */
    buckets.BSTree.prototype.contains = function(element) {
        if (buckets.isUndefined(element)) {
            return false;
        }
        return this.searchNode(this.root, element) !== null;
    };

    /**
     * Removes the specified element from this tree if it is present.
     * @return {boolean} True if this tree contained the specified element.
     */
    buckets.BSTree.prototype.remove = function(element) {
        var node = this.searchNode(this.root, element);
        if (node === null) {
            return false;
        }
        this.removeNode(node);
        this.nElements--;
        return true;
    };

    /**
     * Executes the provided function once per element present in this tree in in-order.
     * @param {function(Object):*} callback function to execute, it is invoked with one
     * argument: the element value, to break the iteration you can optionally return false inside the calback.
     */
    buckets.BSTree.prototype.inorderTraversal = function(callback) {
        this.inorderTraversalAux(this.root, callback, {
            stop: false
        });
    };

    /**
     * Executes the provided function once per element present in this tree in pre-order.
     * @param {function(Object):*} callback function to execute, it is invoked with one
     * argument: the element value, to break the iteration you can optionally return false inside the calback.
     */
    buckets.BSTree.prototype.preorderTraversal = function(callback) {
        this.preorderTraversalAux(this.root, callback, {
            stop: false
        });
    };

    /**
     * Executes the provided function once per element present in this tree in post-order.
     * @param {function(Object):*} callback function to execute, it is invoked with one
     * argument: the element value, to break the iteration you can optionally return false.
     */
    buckets.BSTree.prototype.postorderTraversal = function(callback) {
        this.postorderTraversalAux(this.root, callback, {
            stop: false
        });
    };

    /**
     * Executes the provided function once per element present in this tree in
     * level-order.
     * @param {function(Object):*} callback function to execute, it is invoked with one
     * argument: the element value, to break the iteration you can optionally return false inside the calback..
     */
    buckets.BSTree.prototype.levelTraversal = function(callback) {
        this.levelTraversalAux(this.root, callback);
    };

    /**
     * Returns the minimum element of this tree.
     * @return {*} The minimum element of this tree or undefined if this tree is
     * is empty.
     */
    buckets.BSTree.prototype.minimum = function() {
        if (this.isEmpty()) {
            return undefined;
        }
        return this.minimumAux(this.root).element;
    };

    /**
     * Returns the maximum element of this tree.
     * @return {*} The maximum element of this tree or undefined if this tree is
     * is empty.
     */
    buckets.BSTree.prototype.maximum = function() {
        if (this.isEmpty()) {
            return undefined;
        }
        return this.maximumAux(this.root).element;
    };

    /**
     * Executes the provided function once per element present in this tree in in-order.
     * Equivalent to inorderTraversal.
     * @param {function(Object):*} callback function to execute, it is
     * invoked with one argument: the element value, to break the iteration you can
     * optionally return false.
     */
    buckets.BSTree.prototype.forEach = function(callback) {
        this.inorderTraversal(callback);
    };

    /**
     * Returns an array containing all of the elements in this tree in in-order.
     * @return {Array} An array containing all of the elements in this tree in in-order.
     */
    buckets.BSTree.prototype.toArray = function() {
        var array = [];
        this.inorderTraversal(function(element) {
            array.push(element);
        });
        return array;
    };

    /**
     * Returns the height of this tree.
     * @return {number} The height of this tree or -1 if is empty.
     */
    buckets.BSTree.prototype.height = function() {
        return this.heightAux(this.root);
    };

    /**
     * @private
     */
    buckets.BSTree.prototype.searchNode = function(node, element) {
        var cmp = null;
        while (node !== null && cmp !== 0) {
            cmp = this.compare(element, node.element);
            if (cmp < 0) {
                node = node.leftCh;
            } else if (cmp > 0) {
                node = node.rightCh;
            }
        }
        return node;
    };


    /**
     * @private
     */
    buckets.BSTree.prototype.transplant = function(n1, n2) {
        if (n1.parent === null) {
            this.root = n2;
        } else if (n1 === n1.parent.leftCh) {
            n1.parent.leftCh = n2;
        } else {
            n1.parent.rightCh = n2;
        }
        if (n2 !== null) {
            n2.parent = n1.parent;
        }
    };


    /**
     * @private
     */
    buckets.BSTree.prototype.removeNode = function(node) {
        if (node.leftCh === null) {
            this.transplant(node, node.rightCh);
        } else if (node.rightCh === null) {
            this.transplant(node, node.leftCh);
        } else {
            var y = this.minimumAux(node.rightCh);
            if (y.parent !== node) {
                this.transplant(y, y.rightCh);
                y.rightCh = node.rightCh;
                y.rightCh.parent = y;
            }
            this.transplant(node, y);
            y.leftCh = node.leftCh;
            y.leftCh.parent = y;
        }
    };
    /**
     * @private
     */
    buckets.BSTree.prototype.inorderTraversalAux = function(node, callback, signal) {
        if (node === null || signal.stop) {
            return;
        }
        this.inorderTraversalAux(node.leftCh, callback, signal);
        if (signal.stop) {
            return;
        }
        signal.stop = callback(node.element) === false;
        if (signal.stop) {
            return;
        }
        this.inorderTraversalAux(node.rightCh, callback, signal);
    };

    /**
     * @private
     */
    buckets.BSTree.prototype.levelTraversalAux = function(node, callback) {
        var queue = new buckets.Queue();
        if (node !== null) {
            queue.enqueue(node);
        }
        while (!queue.isEmpty()) {
            node = queue.dequeue();
            if (callback(node.element) === false) {
                return;
            }
            if (node.leftCh !== null) {
                queue.enqueue(node.leftCh);
            }
            if (node.rightCh !== null) {
                queue.enqueue(node.rightCh);
            }
        }
    };

    /**
     * @private
     */
    buckets.BSTree.prototype.preorderTraversalAux = function(node, callback, signal) {
        if (node === null || signal.stop) {
            return;
        }
        signal.stop = callback(node.element) === false;
        if (signal.stop) {
            return;
        }
        this.preorderTraversalAux(node.leftCh, callback, signal);
        if (signal.stop) {
            return;
        }
        this.preorderTraversalAux(node.rightCh, callback, signal);
    };
    /**
     * @private
     */
    buckets.BSTree.prototype.postorderTraversalAux = function(node, callback, signal) {
        if (node === null || signal.stop) {
            return;
        }
        this.postorderTraversalAux(node.leftCh, callback, signal);
        if (signal.stop) {
            return;
        }
        this.postorderTraversalAux(node.rightCh, callback, signal);
        if (signal.stop) {
            return;
        }
        signal.stop = callback(node.element) === false;
    };

    /**
     * @private
     */
    buckets.BSTree.prototype.minimumAux = function(node) {
        while (node.leftCh !== null) {
            node = node.leftCh;
        }
        return node;
    };

    /**
     * @private
     */
    buckets.BSTree.prototype.maximumAux = function(node) {
        while (node.rightCh !== null) {
            node = node.rightCh;
        }
        return node;
    };

    /**
     * @private
     */
    buckets.BSTree.prototype.successorNode = function(node) {
        if (node.rightCh !== null) {
            return this.minimumAux(node.rightCh);
        }
        var successor = node.parent;
        while (successor !== null && node === successor.rightCh) {
            node = successor;
            successor = node.parent;
        }
        return successor;
    };

    /**
     * @private
     */
    buckets.BSTree.prototype.heightAux = function(node) {
        if (node === null) {
            return -1;
        }
        return Math.max(this.heightAux(node.leftCh), this.heightAux(node.rightCh)) + 1;
    };

    /**
     * @private
     */
    buckets.BSTree.prototype.insertNode = function(node) {

        var parent = null;
        var position = this.root;
        var cmp = null;
        while (position !== null) {
            cmp = this.compare(node.element, position.element);
            if (cmp === 0) {
                return null;
            } else if (cmp < 0) {
                parent = position;
                position = position.leftCh;
            } else {
                parent = position;
                position = position.rightCh;
            }
        }
        node.parent = parent;
        if (parent === null) {
            // tree is empty
            this.root = node;
        } else if (this.compare(node.element, parent.element) < 0) {
            parent.leftCh = node;
        } else {
            parent.rightCh = node;
        }
        return node;
    };

    /**
     * @private
     */
    buckets.BSTree.prototype.createNode = function(element) {
        return {
            element: element,
            leftCh: null,
            rightCh: null,
            parent: null
        };
    };

    return buckets;
}));