text: // 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
   */
  var buckets = {};
  (function() {
      'use strict';
  
      /**
       * 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
          };
      };
  
      // Make it a NodeJS module.
      if (typeof module !== 'undefined') {
          module.exports = buckets;
      }
  }());
  