1 /**
  2  * Interface for managing a generic data structure.
  3  * @constructor
  4  * @interface
  5  */
  6 function Aggregate() {
  7 
  8 }
  9 
 10 /**
 11  * Returns the iterator relative to the aggregate.
 12  * @abstract
 13  * @return {Iterator} The iterator.
 14  */
 15 Aggregate.prototype.getIterator = function () {
 16 };
 17 
 18 /**
 19  * Interface for managing an iterator for an aggregate.
 20  * @constructor
 21  * @interface
 22  */
 23 function Iterator() {
 24 
 25 }
 26 
 27 /**
 28  * Moves the iterator to the first position of the aggregate.
 29  * @abstract
 30  * @return {void}
 31  */
 32 Iterator.prototype.first = function () {
 33 
 34 };
 35 
 36 /**
 37  * Moves the iterator to the next item.
 38  * @abstract
 39  * @return {void}
 40  */
 41 Iterator.prototype.next = function () {
 42 
 43 };
 44 
 45 /**
 46  * Moves the iterator to the last position of the aggregate.
 47  * @abstract
 48  * @return {void}
 49  */
 50 Iterator.prototype.last = function () {
 51 
 52 };
 53 
 54 /**
 55  * Moves the iterator to the previous item.
 56  * @abstract
 57  * @return {void}
 58  */
 59 Iterator.prototype.previous = function () {
 60 
 61 };
 62 
 63 /**
 64  * Checks if the iterator is out of the bounds of the aggregate.
 65  * @abstract
 66  * @return {boolean} It return true if the iterator is out of the bounds of the aggregate, otherwise false.
 67  */
 68 Iterator.prototype.isDone = function () {
 69 
 70 };
 71 
 72 /**
 73  * Returns the item stored at the position pointed by the iterator.
 74  * @abstract
 75  * @return {*} The item stored or undefined if it's out of the bounds.
 76  */
 77 Iterator.prototype.getItem = function () {
 78 
 79 };
 80 
 81 /**
 82  * Class for managing a binary search tree.
 83  * @constructor
 84  */
 85 function BSTree() {
 86 	/**
 87 	 * The root of the tree.
 88 	 * @type {BSNode|null}
 89 	 */
 90 	this.root = null;
 91 }
 92 
 93 /**
 94  * Returns the iterator relative to the aggregate.
 95  * @return {Iterator} The iterator.
 96  */
 97 BSTree.prototype.getIterator = function () {
 98 	return new BSTreeIterator(this);
 99 };
100 
101 /**
102  * Inserts the item relatives to the key value in the tree.
103  * @param key {number} The key to store.
104  * @param item {*} The item to store.
105  * @return {void}
106  */
107 BSTree.prototype.insert = function (key, item) {
108 	var node = new BSNode(key, item);
109 	var p = this.root;
110 	for (var n = this.root; n;) {
111 		p = n;
112 		if (key < n.key)
113 			n = n.left;
114 		else
115 			n = n.right;
116 	}
117 	node.parent = p;
118 	if (!p)
119 		this.root = node;
120 	else if (key < p.key)
121 		p.left = node;
122 	else
123 		p.right = node;
124 };
125 
126 /**
127  * Searches the item relatives to the key.
128  * @param key {Number} The key to find.
129  * @param [node = root] {BSNode} The node from which start the search.
130  * @return {*} The item found or undefined if there isn't the key in the tree.
131  */
132 BSTree.prototype.search = function (key, node) {
133 	node = node || this.root;
134 	while (node && key !== node.key)
135 		if (key < node.key)
136 			node = node.left;
137 		else
138 			node = node.right;
139 	if (node)
140 		return node.item;
141 	return undefined;
142 };
143 
144 /**
145  * Gets the item relatives to the minimum key stored in the tree.
146  * @param [node = root] {Node} The node from which start the search.
147  * @return {BSNode} The node found.
148  */
149 BSTree.prototype.minimum = function (node) {
150 	node = node || this.root;
151 	while (node && node.left)
152 		node = node.left;
153 	return node;
154 };
155 
156 /**
157  * Gets the item relatives to the maximum key stored in the tree.
158  * @param [node = root] {Node} The node from which start the search.
159  * @return {BSNode} The node found.
160  */
161 BSTree.prototype.maximum = function (node) {
162 	node = node || this.root;
163 	while (node && node.right)
164 		node = node.right;
165 	return node;
166 };
167 
168 /**
169  * Gets the node with the key next to the param node key.
170  * @param node {BSNode} The node of which search the successor.
171  * @return {BSNode} The node found.
172  */
173 BSTree.prototype.successor = function (node) {
174 	if (node.right)
175 		return this.minimum(node.right);
176 	var parent = node.parent;
177 	while (parent && node === parent.right) {
178 		node = parent;
179 		parent = parent.parent;
180 	}
181 	return parent;
182 };
183 
184 /**
185  * Gets the node with the key previous to the param node key.
186  * @param node {BSNode} The node of which search the predecessor.
187  * @return {BSNode} The node found.
188  */
189 BSTree.prototype.predecessor = function (node) {
190 	if (node.left)
191 		return this.maximum(node.left);
192 	var parent = node.parent;
193 	while (parent && node === parent.left) {
194 		node = parent;
195 		parent = parent.parent;
196 	}
197 	return parent;
198 };
199 
200 /**
201  * Deletes the node from the tree.
202  * @param node {BSNode} The node to delete.
203  * @return {void}
204  */
205 BSTree.prototype.deleteNode = function (node) {
206 	if (!node.left && !node.right) {
207 		if (node === this.root)
208 			this.root = null;
209 		else if (node.parent.left === node)
210 			node.parent.left = null;
211 		else
212 			node.parent.right = null;
213 	} else if (node.left && node.right) {
214 		var next = this.successor(node);
215 		node.key = next.key;
216 		node.item = next.item;
217 		if (next.parent.left === next)
218 			next.parent.left = null;
219 		else
220 			next.parent.right = null;
221 	} else {
222 		if (node.right) {
223 			if (node === this.root) {
224 				this.root = node.right;
225 				node.right.parent = null;
226 			} else {
227 				node.parent.right = node.right;
228 				node.right.parent = node.parent;
229 			}
230 		} else {
231 			if (node === this.root) {
232 				this.root = node.left;
233 				node.left.parent = null;
234 			} else {
235 				node.parent.left = node.left;
236 				node.left.parent = node.parent;
237 			}
238 		}
239 	}
240 };
241 
242 /**
243  * Class that implements the iterator for a binary search tree.
244  * @param aggregate {BSTree} The aggregate to scan.
245  * @constructor
246  */
247 function BSTreeIterator(aggregate) {
248 	/**
249 	 * The aggregate relates to this iterator.
250 	 * @type {BSTree}
251 	 */
252 	this.aggregate = aggregate;
253 
254 	/**
255 	 * The pointer to the position.
256 	 * @type {BSNode|null}
257 	 */
258 	this.pointer = null;
259 }
260 
261 /**
262  * Moves the iterator to the first position of the aggregate.
263  * @return {void}
264  */
265 BSTreeIterator.prototype.first = function () {
266 	this.pointer = this.aggregate.minimum();
267 };
268 
269 /**
270  * Moves the iterator to the next item.
271  * @return {void}
272  */
273 BSTreeIterator.prototype.next = function () {
274 	this.pointer = this.aggregate.successor(this.pointer);
275 };
276 
277 /**
278  * Moves the iterator to the last position of the aggregate.
279  * @return {void}
280  */
281 BSTreeIterator.prototype.last = function () {
282 	this.pointer = this.aggregate.maximum();
283 };
284 
285 /**
286  * Moves the iterator to the previous item.
287  * @return {void}
288  */
289 BSTreeIterator.prototype.previous = function () {
290 	this.pointer = this.aggregate.predecessor(this.pointer);
291 };
292 
293 /**
294  * Checks if the iterator is out of the bounds of the aggregate.
295  * @return {boolean} It return true if the iterator is out of the bounds of the aggregate, otherwise false.
296  */
297 BSTreeIterator.prototype.isDone = function () {
298 	return !this.pointer;
299 };
300 
301 /**
302  * Returns the item stored at the position pointed by the iterator.
303  * @return {*} The item stored or undefined if it's out of the bounds.
304  */
305 BSTreeIterator.prototype.getItem = function () {
306 	return this.pointer.item;
307 };
308 
309 /**
310  * Returns the node stored at the position pointed by the iterator.
311  * @return {BSNode|null} The node stored or null if it's out of the bounds.
312  */
313 BSTreeIterator.prototype.getNode = function () {
314 	return this.pointer;
315 };
316 
317 /**
318  * Class for managing a B-Tree.
319  * @param minimumDegree {number} The minimum number of keys of a node.
320  * @constructor
321  */
322 function BTree(minimumDegree) {
323 	/**
324 	 * The root of the tree.
325 	 * @type {BNode}
326 	 */
327 	this.root = new BNode();
328 
329 	/**
330 	 * The minimum number of the keys of a node.
331 	 * @type {number}
332 	 */
333 	this.t = minimumDegree;
334 
335 	/**
336 	 * The number of items stored in the tree.
337 	 * @type {number}
338 	 */
339 	this.size = 0;
340 }
341 
342 /**
343  * Returns the iterator relative to the aggregate.
344  * @return {Iterator} The iterator.
345  */
346 BTree.prototype.getIterator = function () {
347 	return new BTreeIterator(this);
348 };
349 
350 /**
351  * Inserts the item relatives to the key value in the tree.
352  * @param key {number} The key to store.
353  * @param item {*} The item to store.
354  * @return {void}
355  */
356 BTree.prototype.insert = function (key, item) {
357 	var node = this.root;
358 	if (node.keys.length === 2 * this.t - 1) {
359 		var newNode = new BNode();
360 		newNode.childs.push(node);
361 		this.root = newNode;
362 		this.splitChild(newNode, 0);
363 		node = newNode;
364 	}
365 	this.size++;
366 	this.insertNonFull(node, key, item);
367 };
368 
369 /**
370  * Inserts the new node in the right position if the node is not full.
371  * @param node {BNode} The node from which start to check the insertion.
372  * @param key {number} The key to store.
373  * @param item {*} The item to store.
374  * @return {void}
375  */
376 BTree.prototype.insertNonFull = function (node, key, item) {
377 	while (node) {
378 		var i = node.keys.length - 1;
379 		if (!node.childs.length) {
380 			for (; i > -1 && key < node.keys[i]; i--) {
381 				node.keys[i + 1] = node.keys[i];
382 				node.items[i + 1] = node.items[i];
383 			}
384 			node.keys[i + 1] = key;
385 			node.items[i + 1] = item;
386 			return;
387 		} else {
388 			var j = 0;
389 			i++;
390 			while (j < i) {
391 				var m = Math.floor((j + i) / 2);
392 				if (key <= node.keys[m])
393 					i = m;
394 				else
395 					j = m + 1;
396 			}
397 			if (node.childs[j].keys.length === 2 * this.t - 1) {
398 				this.splitChild(node, j);
399 				if (key > node.keys[j])
400 					j++;
401 			}
402 			node = node.childs[j];
403 		}
404 	}
405 };
406 
407 /**
408  * Searches the item relatives to the key that satisfy the condition represented by the callback function.
409  * @param key {Number} The key to find.
410  * @param [node = root] {RBNode} The node from which start the search.
411  * @param [callback = function(node,index){return(node.keys[index]===key);}] The condition to satisfy. The callback must accept the current node to check and optionally the position of the key.
412  * @return {*} The item found or undefined if there isn't the key in the tree.
413  */
414 BTree.prototype.search = function (key, node, callback) {
415 	node = node || this.root;
416 	callback = callback || function (node, index) {
417 		return node.keys[index] === key;
418 	};
419 	while (node) {
420 		var n = node.keys.length;
421 		var i = 0, j = n;
422 		while (i < j) {
423 			var m = Math.floor((i + j) / 2);
424 			if (key <= node.keys[m])
425 				j = m;
426 			else
427 				i = m + 1;
428 		}
429 		if (i < n && callback(node, i))
430 			return node.items[i];
431 		else if (!node.childs.length)
432 			return undefined;
433 		else
434 			node = node.childs[i];
435 	}
436 };
437 
438 /**
439  * Splits the child of the node at the position index.
440  * @param node {BNode} The parent of the child to split.
441  * @param index {number} The position of the child to split.
442  * @return {void}
443  */
444 BTree.prototype.splitChild = function (node, index) {
445 	var newNode = new BNode();
446 	var child = node.childs[index];
447 	//copy of the last t - 1 keys and items in the new node
448 	for (var i = 0; i < this.t - 1; i++) {
449 		newNode.keys[i] = child.keys[i + this.t];
450 		newNode.items[i] = child.items[i + this.t];
451 	}
452 	if (child.childs.length)
453 	//copy of the last t child in the new node
454 		for (var j = 0; j < this.t; j++)
455 			newNode.childs[j] = child.childs[j + this.t];
456 	//shift the children from index + 1 position
457 	for (var l = node.keys.length; l > index; l--)
458 		node.childs[l + 1] = node.childs[l];
459 	//set the index position as the position t of the child
460 	node.childs[index + 1] = newNode;
461 	//shift the keys and the items from index position
462 	for (var k = node.keys.length - 1; k > index - 1; k--) {
463 		node.keys[k + 1] = node.keys[k];
464 		node.items[k + 1] = node.items[k];
465 	}
466 	node.keys[index] = child.keys[this.t - 1];
467 	node.items[index] = child.items[this.t - 1];
468 	//remove keys, items and child in the old node.
469 	child.keys.splice(child.keys.length - this.t);
470 	child.items.splice(child.items.length - this.t);
471 	child.childs.splice(child.childs.length - this.t);
472 };
473 
474 /**
475  * Deletes the key from the tree.
476  * @param key {*} The key to delete.
477  * @return {void}
478  */
479 BTree.prototype.deleteKey = function (key) {
480 	if (this.root.keys.length) {
481 		this.deleteNonMin(this.root, key);
482 		if (!this.root.keys.length && this.root.childs.length)
483 			this.root = this.root.childs[0];
484 		this.size--;
485 	}
486 };
487 
488 /**
489  * Deletes a node that's a number of keys greater than the minimum for a node.
490  * @param node {BNode} The node to delete.
491  * @param key {number} The key to delete.
492  * @return {void}
493  */
494 BTree.prototype.deleteNonMin = function (node, key) {
495 	var i = 0, j = node.keys.length;
496 	while (i < j) {
497 		var m = Math.floor((i + j) / 2);
498 		if (key <= node.keys[m])
499 			j = m;
500 		else
501 			i = m + 1;
502 	}
503 	//key is in the node
504 	if (i < node.keys.length && key === node.keys[i]) {
505 		//the node is a leaf
506 		if (!node.childs.length) {
507 			//remove the key
508 			for (j = i + 1; j < node.keys.length; j++) {
509 				node.keys[j - 1] = node.keys[j];
510 				node.items[j - 1] = node.items[j];
511 			}
512 			node.keys.pop();
513 			node.items.pop();
514 		} else {
515 			//the node is not a leaf
516 			//the node has the minimum number of keys
517 			if (node.childs[i].length === this.t - 1) {
518 				//increase the number of the keys of the node
519 				this.augmentChild(node, i);
520 				if (i === node.keys.length + 1)
521 					i--;
522 			}
523 			//check if the key is moved in the child
524 			if (node.keys[i] !== key)
525 				this.deleteNonMin(node.childs[i], key);
526 			else
527 				this.deleteMax(node, i);
528 		}
529 		//the key is not in the node
530 	} else {
531 		//check if the child i has the minimum number of keys
532 		if (node.childs[i].keys.length === this.t - 1) {
533 			this.augmentChild(node, i);
534 			if (i === node.keys.length + 2)
535 				i--;
536 		}
537 		this.deleteNonMin(node.childs[i], key);
538 	}
539 };
540 
541 /**
542  * Deletes a node that have the maximum number of keys for node.
543  * @param node {BNode} The node to delete.
544  * @param index {number} The key to delete in the node.
545  * @return {void}
546  */
547 BTree.prototype.deleteMax = function (node, index) {
548 	var child = node.childs[index];
549 	var goAhead = true;
550 	while (goAhead) {
551 		if (!child.childs.length) {
552 			node.keys[index] = child.keys[child.keys.length - 1];
553 			node.items[index] = child.items[child.items.length - 1];
554 			child.keys.pop();
555 			child.items.pop();
556 			goAhead = false;
557 		} else {
558 			var last = child.childs[child.keys.length];
559 			if (last.keys.length === this.t - 1)
560 				this.augmentChild(child, child.keys.length);
561 			child = child.childs[child.keys.length];
562 		}
563 	}
564 };
565 
566 /**
567  * Augments the number of keys stored in the node preserving the order.
568  * @param node {BNode} The node to delete.
569  * @param index {number} The index of the position to augment.
570  * @return {void}
571  */
572 BTree.prototype.augmentChild = function (node, index) {
573 	var child = node.childs[index];
574 	var brother;
575 	if (index)
576 		brother = node.childs[index - 1];
577 	if (index && brother.keys.length > this.t - 1) {
578 		if (child.childs.length) {
579 			for (var j = this.keys.length + 1; j > 0; j--)
580 				child.childs[j] = child.childs[j - 1];
581 			child.childs[0] = brother.childs[brother.keys.length];
582 			for (var i = child.keys.length; i > 0; i--) {
583 				child.keys[i] = child.keys[i - 1];
584 				child.items[i] = child.items[i - 1];
585 			}
586 			child.keys[0] = node.keys[index - 1];
587 			child.items[0] = node.items[index - 1];
588 			node.keys[index - 1] = brother.keys[brother.keys.length - 1];
589 			node.items[index - 1] = brother.items[brother.items.length - 1];
590 		}
591 	} else {
592 		if (index < node.keys.length)
593 			brother = node.childs[index + 1];
594 		if (index < node.keys.length && brother.keys.length > this.t - 1) {
595 			if (brother.childs.length) {
596 				child.childs[child.keys.length + 1] = brother.childs[0];
597 				for (var l = 1; l < brother.keys.length + 1; l++)
598 					brother.childs[l - 1] = brother.childs[l];
599 				brother.childs.pop();
600 			}
601 			child.keys[child.keys.length] = node.keys[index];
602 			child.items[child.items.length] = node.items[index];
603 			node.keys[index] = brother.keys[0];
604 			node.items[index] = brother.items[0];
605 			for (var k = 1; k < brother.keys.length; k++) {
606 				brother.keys[k - 1] = brother.keys[k];
607 				brother.items[k - 1] = brother.items[k];
608 			}
609 			brother.keys.pop();
610 			brother.items.pop();
611 		} else {
612 			if (index < node.keys.length) {
613 				child.keys[this.t - 1] = node.keys[index];
614 				child.items[this.t - 1] = node.items[index];
615 				for (var m = index + 2; m < node.keys.length + 1; m++)
616 					node.childs[m - 1] = node.childs[m];
617 				node.childs.pop();
618 				for (var n = index + 1; n < node.keys.length; n++) {
619 					node.keys[n - 1] = node.keys[n];
620 					node.items[n - 1] = node.items[n];
621 				}
622 				node.keys.pop();
623 				node.items.pop();
624 				if (brother.childs.length)
625 					for (var y = 0; y < brother.keys.length + 1; y++)
626 						child.childs[this.t + y] = brother.childs[y];
627 				for (var x = 0; x < brother.keys.length; x++) {
628 					child.keys[x + this.t] = brother.keys[x];
629 					child.items[x + this.t] = brother.items[x];
630 				}
631 			} else {
632 				if (brother.childs.length)
633 					for (var w = 0; w < child.keys.length + 1; w++)
634 						brother.childs[this.t + w] = child.childs[w];
635 				brother.keys[this.t - 1] = node.keys[node.keys.length - 1];
636 				brother.items[this.t - 1] = node.items[node.keys.length - 1];
637 				for (var z = 0; z < child.keys.length; z++) {
638 					brother.keys[z + this.t] = child.keys[z];
639 					brother.items[z + this.t] = child.items[z];
640 				}
641 			}
642 		}
643 	}
644 };
645 
646 /**
647  * Checks if the tree contains the key.
648  * @param key {number} The key to find.
649  * @param [callback = function(node,index){return(node.keys[index]===key);}] The condition to satisfy. The callback must accept the current node to check and optionally the position of the key.
650  * @return {boolean} True if the tree contains the key.
651  */
652 BTree.prototype.contains = function (key, callback) {
653 	return this.search(key, null, callback) !== undefined;
654 };
655 
656 /**
657  * Checks if the tree contains a node that satisfy the condition represented by the callback function.
658  * This method check all the tree avoiding the binary search.
659  * @param callback {function} The condition to satisfy. The callback must accept the current node to check.
660  * @return {boolean} True if the tree contains the node that satisfy the condition, false otherwise.
661  */
662 BTree.prototype.fullContains = function (callback) {
663 	var key = this.minimumKey();
664 	while (key !== null && !callback(this.search(key)))
665 		key = this.successor(key);
666 	return key !== null;
667 };
668 
669 /**
670  * Gets the key next to the param node key.
671  * @param key {number} The key of which search the successor.
672  * @param [node = root] The node from start the search of the successor.
673  * @return {number} The key found.
674  */
675 BTree.prototype.successor = function (key, node) {
676 	node = node || this.root;
677 	var i = 0, j = node.keys.length;
678 	//search the key in the node
679 	while (i < j) {
680 		var m = Math.floor((i + j) / 2);
681 		if (key <= node.keys[m])
682 			j = m;
683 		else
684 			i = m + 1;
685 	}
686 	//check if the key has been found
687 	if (node.keys[i] === key)
688 	//in this case the successor is the next key
689 		i++;
690 	//if it's a leaf
691 	if (!node.childs.length) {
692 		//check if the key hasn't been found
693 		if (i > node.keys.length - 1)
694 			return null;
695 		else
696 			return node.keys[i];
697 	}
698 	//if it's not a leaf check if the successor is in the i-child
699 	var successor = this.successor(key, node.childs[i]);
700 	//if it's not in the child and has been found a key then return it
701 	if (successor === null && i < node.keys.length)
702 		return node.keys[i];
703 	//return the value of the successor even if it's null
704 	return successor;
705 };
706 
707 /**
708  * Gets the key previous to the param key.
709  * @param key {number} The key of which search the predecessor.
710  * @param [node = root] The node from start the search of the predecessor.
711  * @return {number} The key found.
712  */
713 BTree.prototype.predecessor = function (key, node) {
714 	node = node || this.root;
715 	var i = 0, j = node.keys.length;
716 	//search the key in the node
717 	while (i < j) {
718 		var m = Math.floor((i + j) / 2);
719 		if (key <= node.keys[m])
720 			j = m;
721 		else
722 			i = m + 1;
723 	}
724 	i--;
725 	//check if the node is a leaf
726 	if (!node.childs.length) {
727 		//check if a predecessor has been found
728 		if (i < 0)
729 			return null;
730 		else
731 			return node.keys[i];
732 	}
733 	var predecessor = this.predecessor(key, node.childs[i + 1]);
734 	if (predecessor === null && key > node.keys[0]) {
735 		return node.keys[i];
736 	}
737 	return predecessor;
738 };
739 
740 /**
741  * Gets the minimum key stored in the tree.
742  * @return {number} The key found.
743  */
744 BTree.prototype.minimumKey = function () {
745 	var node = this.root;
746 	while (node.childs.length)
747 		node = node.childs[0];
748 	if (node)
749 		return node.keys[0];
750 	return null;
751 };
752 
753 /**
754  * Gets the maximum key stored in the tree.
755  * @return {number} The key found.
756  */
757 BTree.prototype.maximumKey = function () {
758 	var node = this.root;
759 	while (node.childs.length)
760 		node = node.childs[node.childs.length - 1];
761 	if (node)
762 		return node.keys[node.keys.length - 1];
763 	return null;
764 };
765 
766 /**
767  * Gets the item relatives to the minimum key stored in the tree.
768  * @return {number} The item found.
769  */
770 BTree.prototype.minimum = function () {
771 	var node = this.root;
772 	while (node.childs.length)
773 		node = node.childs[0];
774 	return node.items[0];
775 };
776 
777 /**
778  * Gets the item relatives to the maximum key stored in the tree.
779  * @return {node} The item found.
780  */
781 BTree.prototype.maximum = function () {
782 	var node = this.root;
783 	while (node.childs.length)
784 		node = node.childs[node.childs.length - 1];
785 	return node.items[node.items.length - 1];
786 };
787 
788 /**
789  * Returns the size of the tree.
790  * @return {number} The size of the tree.
791  */
792 BTree.prototype.getSize = function () {
793 	return this.size;
794 };
795 
796 /**
797  * Checks if the tree is empty.
798  * @return {boolean} True if the tree is empty, false otherwise.
799  */
800 BTree.prototype.isEmpty = function () {
801 	return !this.size;
802 };
803 
804 /**
805  * Executes the callback function for each item of the tree.
806  * This method modifies the tree so if you don't need to modify it you must return the same item of the array.
807  * @param callback {function} The function to execute for each item. The function must accept the current item on which execute the function.
808  * @return {void}
809  */
810 BTree.prototype.execute = function (callback) {
811 	var node = arguments[1] || this.root;
812 	for (var i = 0; i < node.items.length; i++)
813 		node.items[i] = callback(node.items[i]);
814 	for (var j = 0; j < node.childs.length; j++)
815 		this.execute(callback, node.childs[j]);
816 };
817 
818 /**
819  * Removes all the items stored in the tree.
820  * @return {void}
821  */
822 BTree.prototype.clear = function () {
823 	this.root = null;
824 	this.size = 0;
825 };
826 
827 /**
828  * Returns the items that satisfy the condition determined by the callback.
829  * @param callback {function} The function that implements the condition.
830  * @return {Array<*>} The array that contains the items that satisfy the condition.
831  */
832 BTree.prototype.filter = function (callback) {
833 	var result = [];
834 	var node = arguments[1] || this.root;
835 	for (var i = 0; i < node.items.length; i++) {
836 		if (node.childs.length)
837 			result = result.concat(this.filter(callback, node.childs[i]));
838 		if (callback(node.items[i]))
839 			result.push(node.items[i]);
840 	}
841 	if (node.childs.length)
842 		result = result.concat(this.filter(callback, node.childs[node.childs.length - 1]));
843 	return result;
844 };
845 
846 /**
847  * Clones the tree into a new tree.
848  * @return {BTree} The tree cloned from this tree.
849  */
850 BTree.prototype.clone = function () {
851 	var tree = new BTree(this.t);
852 	var it = this.getIterator();
853 	for (it.first(); !it.isDone(); it.next()) {
854 		var item = it.getItem();
855 		if (item.clone)
856 			item = item.clone();
857 		tree.insert(it.getKey(), item);
858 	}
859 	return tree;
860 };
861 
862 /**
863  * Clones the tree into a new tree without cloning duplicated items.
864  * @return {BTree} The tree cloned from this tree.
865  */
866 BTree.prototype.cloneDistinct = function () {
867 	var tree = new BTree(this.t);
868 	var it = this.getIterator();
869 	for (it.first(); !it.isDone(); it.next()) {
870 		var callback = function (item) {
871 			return item === it.getItem();
872 		};
873 		if (!tree.fullContains(callback)) {
874 			if (it.getItem().cloneDistinct)
875 				tree.insert(it.getKey(), it.getItem().cloneDistinct());
876 			else if (it.getItem().clone)
877 				tree.insert(it.getKey(), it.getItem().clone());
878 			else
879 				tree.insert(it.getKey(), it.getItem());
880 		}
881 	}
882 	return tree;
883 };
884 
885 /**
886  * Transforms the tree into an array without preserving keys.
887  * @return {Array<*>} The array that represents the tree.
888  */
889 BTree.prototype.toArray = function () {
890 	var result = [];
891 	var it = this.getIterator();
892 	for (it.first(); !it.isDone(); it.next())
893 		result.push(it.getItem());
894 	return result;
895 };
896 
897 /**
898  * Returns the first position of the item in the tree.
899  * @param item {*} The item to search.
900  * @param [callback = function(item){return(it===item);}] The condition to satisfy. The callback must accept the current item to check.
901  * @return {number} The first position of the item.
902  */
903 BTree.prototype.indexOf = function (item, callback) {
904 	callback = callback || function (it) {
905 		return it === item;
906 	};
907 	var i = 0, key = this.minimumKey();
908 	while (key !== null) {
909 		if (callback(this.search(key)))
910 			return i;
911 		key = this.successor(key);
912 		i++;
913 	}
914 	return -1;
915 };
916 
917 /**
918  * Returns the last position of the item in the tree.
919  * @param item {*} The item to search.
920  * @param [callback = function(item){return(it===item);}] The condition to satisfy. The callback must accept the current item to check.
921  * @return {number} The last position of the item.
922  */
923 BTree.prototype.lastIndexOf = function (item, callback) {
924 	callback = callback || function (it) {
925 		return it === item;
926 	};
927 	var i = this.size - 1, key = this.maximumKey();
928 	while (key !== null) {
929 		if (callback(this.search(key)))
930 			return i;
931 		i--;
932 		key = this.predecessor(key);
933 	}
934 	return -1;
935 };
936 
937 /**
938  * Returns all the position in which the item has been found in the tree.
939  * @param item {*} The item to search.
940  * @param [callback = function(item){return(it===item);}] The condition to satisfy. The callback must accept the current item to check.
941  * @return {Array<number>} The positions in which the item has been found.
942  */
943 BTree.prototype.allIndexesOf = function (item, callback) {
944 	callback = callback || function (it) {
945 		return it === item;
946 	};
947 	var i = 0, key = this.minimumKey();
948 	var indexes = [];
949 	while (key !== null) {
950 		if (callback(this.search(key)))
951 			indexes.push(i);
952 		i++;
953 		key = this.successor(key);
954 	}
955 	return indexes;
956 };
957 
958 /**
959  * Returns the item at the position index.
960  * @param index {number} The position of the item.
961  * @return {*} The item at the position. It's undefined if index isn't in the tree bounds.
962  */
963 BTree.prototype.getItem = function (index) {
964 	if (index < 0 || index > this.size - 1)
965 		return undefined;
966 	var key = this.minimum();
967 	for (var i = 0; i < index; i++)
968 		key = this.successor(key);
969 	return this.search(key);
970 };
971 
972 /**
973  * Class that implements the iterator for a binary search tree.
974  * @param aggregate {BTree} The aggregate to scan.
975  * @constructor
976  */
977 function BTreeIterator(aggregate) {
978 	/**
979 	 * The aggregate relates to this iterator.
980 	 * @type {BTree}
981 	 */
982 	this.aggregate = aggregate;
983 
984 	/**
985 	 * The pointer to the position.
986 	 * @type {number}
987 	 */
988 	this.pointer = null;
989 }
990 
991 /**
992  * Moves the iterator to the first position of the aggregate.
993  * @return {void}
994  */
995 BTreeIterator.prototype.first = function () {
996 	this.pointer = this.aggregate.minimumKey();
997 };
998 
999 /**
1000  * Moves the iterator to the next item.
1001  * @return {void}
1002  */
1003 BTreeIterator.prototype.next = function () {
1004 	this.pointer = this.aggregate.successor(this.pointer);
1005 };
1006 
1007 /**
1008  * Moves the iterator to the last position of the aggregate.
1009  * @return {void}
1010  */
1011 BTreeIterator.prototype.last = function () {
1012 	this.pointer = this.aggregate.maximumKey();
1013 };
1014 
1015 /**
1016  * Moves the iterator to the previous item.
1017  * @return {void}
1018  */
1019 BTreeIterator.prototype.previous = function () {
1020 	this.pointer = this.aggregate.predecessor(this.pointer);
1021 };
1022 
1023 /**
1024  * Checks if the iterator is out of the bounds of the aggregate.
1025  * @return {boolean} It return true if the iterator is out of the bounds of the aggregate, otherwise false.
1026  */
1027 BTreeIterator.prototype.isDone = function () {
1028 	return this.pointer === null;
1029 };
1030 
1031 /**
1032  * Returns the item stored at the position pointed by the iterator.
1033  * @return {*} The item stored or undefined if it's out of the bounds.
1034  */
1035 BTreeIterator.prototype.getItem = function () {
1036 	return this.aggregate.search(this.pointer);
1037 };
1038 
1039 /**
1040  * Returns the key stored at the position pointed by the iterator.
1041  * @return {number} The key stored or null if it's out of the bounds.
1042  */
1043 BTreeIterator.prototype.getKey = function () {
1044 	return this.pointer;
1045 };
1046 
1047 /**
1048  * Class for managing a circular buffer.
1049  * @param size {Number} The size of the buffer.
1050  * @constructor
1051  */
1052 function CircularBuffer(size) {
1053 	/**
1054 	 * The index of the position of the head of the buffer.
1055 	 * @type {number}
1056 	 */
1057 	this.head = 0;
1058 	/**
1059 	 * The index of the position of the tail of the buffer.
1060 	 * @type {number}
1061 	 */
1062 	this.tail = 0;
1063 	/**
1064 	 * The items stored in the buffer.
1065 	 * @type {Array<*>}
1066 	 */
1067 	this.items = new Array(size);
1068 	/**
1069 	 * Is true if buffer is empty, false otherwise.
1070 	 * @type {boolean}
1071 	 */
1072 	this.empty = true;
1073 	/**
1074 	 * Is false if buffer is full, false otherwise.
1075 	 * @type {boolean}
1076 	 */
1077 	this.full = false;
1078 	/**
1079 	 * The size of the buffer.
1080 	 * @type {Number}
1081 	 */
1082 	this.size = size;
1083 }
1084 
1085 /**
1086  * Returns the iterator relative to the aggregate.
1087  * @return {Iterator} The iterator.
1088  */
1089 CircularBuffer.prototype.getIterator = function () {
1090 	return new CircularBufferIterator(this);
1091 };
1092 
1093 /**
1094  * Writes the item at the head of the buffer.
1095  * @param item {*} The item to write.
1096  * @return {void}
1097  */
1098 CircularBuffer.prototype.write = function (item) {
1099 	this.empty = false;
1100 	if (this.full)
1101 	//if buffer is full tail must be set forward
1102 		this.tail = (this.tail + 1) % this.size;
1103 	this.items[this.head] = item;
1104 	//head is set forward
1105 	this.head = (this.head + 1) % this.size;
1106 	if (this.tail === this.head)
1107 		this.full = true;
1108 };
1109 
1110 /**
1111  * Frees the buffer between indexes from and to.
1112  * If from > to, positions between from and the end of the buffer and between the start and to will be free.
1113  * @param from {Number} The index from which start to free (inclusive index)
1114  * @param to {Number} The index where stop to free (exclusive index)
1115  * @return {void}
1116  */
1117 CircularBuffer.prototype.free = function (from, to) {
1118 	if (from < 0)
1119 		from = 0;
1120 	if (from > this.size - 1)
1121 		from = this.size - 1;
1122 	if (to < 0)
1123 		to = 0;
1124 	if (to > this.size - 1)
1125 		to = this.size - 1;
1126 	//if from < to then will be free allocation between from and to
1127 	//otherwise will be free allocations between from and the end and between the start and to
1128 	for (var i = from; i < to; i = (i + 1) % this.size)
1129 		delete this.items[i];
1130 
1131 	//adjust the position of the tail and of the head
1132 	if (this.tail > from - 1 || this.tail < to)
1133 		if (this.tail < this.head) {
1134 			this.tail = (from - 1) % this.size;
1135 		} else {
1136 			this.tail = to;
1137 		}
1138 	if (this.head > from || this.head < to)
1139 		if (this.tail < this.head) {
1140 			this.head = to;
1141 		} else {
1142 			this.head = from;
1143 		}
1144 	//check if something is free
1145 	if (from !== to)
1146 		this.full = false;
1147 	//free could make buffer empty
1148 	for (var j = 0; j < this.size; j++)
1149 		if (this.items[j] !== undefined) {
1150 			this.empty = false;
1151 			return;
1152 		}
1153 	this.empty = true;
1154 };
1155 
1156 /**
1157  * Frees all the buffer.
1158  * @return {void}
1159  */
1160 CircularBuffer.prototype.freeAll = function () {
1161 	for (var i = 0; i < this.size; i++)
1162 		delete this.items[i];
1163 	this.empty = true;
1164 	this.head = 0;
1165 	this.tail = 0;
1166 };
1167 
1168 /**
1169  * Reads the item stored at the position index.
1170  * @param index {Number} The position of the item to read.
1171  * @return {*} The item read.
1172  */
1173 CircularBuffer.prototype.read = function (index) {
1174 	return this.items[index % this.size];
1175 };
1176 
1177 /**
1178  * Returns true if the buffer is empty, false otherwise.
1179  * @return {boolean}
1180  */
1181 CircularBuffer.prototype.isEmpty = function () {
1182 	return this.empty;
1183 };
1184 
1185 /**
1186  * Returns true if the buffer is full, false otherwise.
1187  * @return {boolean}
1188  */
1189 CircularBuffer.prototype.isFull = function () {
1190 	return this.full;
1191 };
1192 
1193 /**
1194  * Clones the circular buffer into a new circular buffer.
1195  * @return {CircularBuffer} The circular buffer cloned from this circular buffer.
1196  */
1197 CircularBuffer.prototype.clone = function () {
1198 	var buffer = new CircularBuffer(this.size);
1199 	buffer.head = this.head;
1200 	buffer.tail = this.tail;
1201 	for (var i = 0; i < this.items.length; i++)
1202 		buffer.items[i] = this.items[i];
1203 	buffer.empty = this.empty;
1204 	buffer.full = this.full;
1205 	return buffer;
1206 };
1207 
1208 /**
1209  * Resize the buffer.
1210  * @param size {number} The new size of the buffer.
1211  * @return {void}
1212  */
1213 CircularBuffer.prototype.resize = function (size) {
1214 	if (this.size < size) {
1215 		if (this.head < this.tail + 1) {
1216 			for (var i = 0; i < this.head; i++) {
1217 				this.items[(i + this.size) % size] = this.items[i];
1218 				delete this.items[i];
1219 			}
1220 			this.head = (this.head + this.size) % size;
1221 		}
1222 	} else if (this.size > size) {
1223 		if (this.head < this.tail + 1) {
1224 			//check if the tail is after the size
1225 			var start = size;
1226 			if (this.tail > size - 1) {
1227 				start = this.tail;
1228 				this.tail = 0;
1229 			}
1230 			//the items stored must be shift to a valid position
1231 			var step = this.size - start;
1232 			for (var j = this.head - step - 1; j > start - 1 || j < this.head - step; j--) {
1233 				this.items[(j + step) % this.size] = this.items[j];
1234 				if (!j)
1235 					j = this.size;
1236 			}
1237 			this.head = (this.head + step) % this.size;
1238 		}
1239 	}
1240 	this.size = size;
1241 };
1242 
1243 /**
1244  * Class that implements the iterator for a circular buffer.
1245  * @param aggregate {CircularBuffer} The aggregate to scan.
1246  * @constructor
1247  */
1248 function CircularBufferIterator(aggregate) {
1249 	/**
1250 	 * The aggregate relates to this iterator.
1251 	 * @type {CircularBuffer}
1252 	 */
1253 	this.aggregate = aggregate;
1254 
1255 	/**
1256 	 * The pointer to the position.
1257 	 * @type {number|null}
1258 	 */
1259 	this.pointer = null;
1260 	/**
1261 	 * Discriminator for full buffer
1262 	 * @type {bool}
1263 	 */
1264 	this.start = true;
1265 }
1266 
1267 /**
1268  * Moves the iterator to the first position of the aggregate.
1269  * @return {void}
1270  */
1271 CircularBufferIterator.prototype.first = function () {
1272 	this.pointer = this.aggregate.tail;
1273 	this.start = true;
1274 };
1275 
1276 /**
1277  * Moves the iterator to the next item.
1278  * @return {void}
1279  */
1280 CircularBufferIterator.prototype.next = function () {
1281 	this.pointer = (this.pointer + 1) % this.aggregate.size;
1282 	this.start = false;
1283 };
1284 
1285 /**
1286  * Moves the iterator to the last position of the aggregate.
1287  * @return {void}
1288  */
1289 CircularBufferIterator.prototype.last = function () {
1290 	this.pointer = (this.aggregate.head - 1) % this.aggregate.size;
1291 	this.start = true;
1292 };
1293 
1294 /**
1295  * Moves the iterator to the previous item.
1296  * @return {void}
1297  */
1298 CircularBufferIterator.prototype.previous = function () {
1299 	this.pointer = (this.pointer - 1) % this.aggregate.size;
1300 	this.start = false;
1301 };
1302 
1303 /**
1304  * Checks if the iterator is out of the bounds of the aggregate.
1305  * @return {boolean} It return true if the iterator is out of the bounds of the aggregate, otherwise false.
1306  */
1307 CircularBufferIterator.prototype.isDone = function () {
1308 	return (this.pointer === this.aggregate.head && !this.start) || (this.pointer === this.aggregate.tail - 1) % this.aggregate.size || this.aggregate.isEmpty();
1309 };
1310 
1311 /**
1312  * Returns the item stored at the position pointed by the iterator.
1313  * @return {*} The item stored or undefined if it's out of the bounds.
1314  */
1315 CircularBufferIterator.prototype.getItem = function () {
1316 	return this.aggregate.read(this.pointer);
1317 };
1318 
1319 /**
1320  * Class for managing a double linked list.
1321  * @param {...*} [args] The items for initializing the list.
1322  * @constructor
1323  */
1324 function DoubleLinkedList(args) {
1325 	/**
1326 	 * The first node of the list.
1327 	 * @type {DLLNode|null}
1328 	 */
1329 	this.first = null;
1330 	/**
1331 	 * The last node of the list.
1332 	 * @type {DLLNode|null}
1333 	 */
1334 	this.last = null;
1335 	/**
1336 	 * The length of the list.
1337 	 * @type {number}
1338 	 */
1339 	this.length = 0;
1340 	//builds the list from the parameters of the constructor
1341 	this.fromArray(arguments);
1342 }
1343 
1344 /**
1345  * Returns the iterator relative to the aggregate.
1346  * @return {Iterator} The iterator.
1347  */
1348 DoubleLinkedList.prototype.getIterator = function () {
1349 	return new DoubleLinkedListIterator(this);
1350 };
1351 
1352 /**
1353  * Adds an item at the head of the list.
1354  * @param item {*} The item to add.
1355  * @return {void}
1356  */
1357 DoubleLinkedList.prototype.pushFront = function (item) {
1358 	var node = new DLLNode(item);
1359 	node.next = this.first;
1360 	this.first = node;
1361 	//link the next node to the new node
1362 	if (node.next)
1363 		node.next.previous = node;
1364 	else
1365 		this.last = node;
1366 	this.length++;
1367 };
1368 
1369 /**
1370  * Adds an item at the tail of the list.
1371  * @param item {*} The item to add.
1372  * @return {void}
1373  */
1374 DoubleLinkedList.prototype.pushBack = function (item) {
1375 	var node = new DLLNode(item);
1376 	node.previous = this.last;
1377 	this.last = node;
1378 	//link the previous node to the new node
1379 	if (node.previous)
1380 		node.previous.next = node;
1381 	else
1382 		this.first = node;
1383 	this.length++;
1384 };
1385 
1386 /**
1387  * Removes the first item of the list.
1388  * @return {*} The item removed. It's undefined if the list is empty.
1389  */
1390 DoubleLinkedList.prototype.popFront = function () {
1391 	if (this.length) {
1392 		var node = this.first;
1393 		this.first = node.next;
1394 		if (node.next)
1395 			node.next.previous = null;
1396 		this.length--;
1397 		node.next = null;
1398 		return node.item;
1399 	}
1400 	return undefined;
1401 };
1402 
1403 /**
1404  * Removes the last item of the list.
1405  * @return {*} The item removed. It's undefined if the list is empty.
1406  */
1407 DoubleLinkedList.prototype.popBack = function () {
1408 	if (this.length) {
1409 		var node = this.last;
1410 		this.last = node.previous;
1411 		if (node.previous)
1412 			node.previous.next = null;
1413 		this.length--;
1414 		node.previous = null;
1415 		return node.item;
1416 	}
1417 	return undefined;
1418 };
1419 
1420 /**
1421  * Removes the first times items of the list.
1422  * @param times {number} The number of times to repeat the popFront method.
1423  * @return {*} The item removed. It's undefined if the list is empty.
1424  */
1425 DoubleLinkedList.prototype.multiPopFront = function (times) {
1426 	var result = [];
1427 	for (var i = 0; i < times && this.length; i++)
1428 		result.push(this.popFront());
1429 	return result;
1430 };
1431 
1432 /**
1433  * Removes the last times items of the list.
1434  * @param times {number} The number of times to repeat the popBack method.
1435  * @return {*} The items removed.
1436  */
1437 DoubleLinkedList.prototype.multiPopBack = function (times) {
1438 	var result = [];
1439 	for (var i = 0; i < times && this.length; i++)
1440 		result.push(this.popBack());
1441 	return result;
1442 };
1443 
1444 /**
1445  * Returns the first item of the list without remove it.
1446  * @return {*} The item at the top of the list. It's undefined if the list is empty.
1447  */
1448 DoubleLinkedList.prototype.peek = function () {
1449 	if (!this.length)
1450 		return undefined;
1451 	return this.first.item;
1452 };
1453 
1454 /**
1455  * Adds the item at the index position.
1456  * @param item {*} The item to add.
1457  * @param index {number} The position where to add the item. If index is negative, the item won't be added.
1458  * @return {void}
1459  */
1460 DoubleLinkedList.prototype.addAt = function (item, index) {
1461 	if (index < -1)
1462 		return;
1463 	if (!index) {
1464 		this.pushFront(item);
1465 		return;
1466 	}
1467 	if (index === this.length) {
1468 		this.pushBack(item);
1469 		return;
1470 	}
1471 	var node = this.first;
1472 	if (!node && index > 0)
1473 		this.pushBack(undefined);
1474 	for (var i = 0; i < index - 1; i++, node = node.next) {
1475 		if (node === this.last)
1476 			this.pushBack(undefined);
1477 	}
1478 	if (node === this.last)
1479 		this.pushBack(item);
1480 	else if (node === this.first)
1481 		this.pushFront(item);
1482 	else {
1483 		var newNode = new DLLNode(item);
1484 		newNode.next = node.next;
1485 		newNode.previous = node;
1486 		node.next = newNode;
1487 		if (newNode.next)
1488 			newNode.next.previous = newNode;
1489 		this.length++;
1490 	}
1491 };
1492 
1493 /**
1494  * Removes the item at the position index.
1495  * @param index {Number} The position of the item to remove.
1496  * @return {*} The item stored at the position index. It's undefined if the index is out of bounds.
1497  */
1498 DoubleLinkedList.prototype.removeAt = function (index) {
1499 	if (index < 0 || index > this.length - 1)
1500 		return undefined;
1501 	if (index === 0)
1502 		return this.popFront();
1503 	if (index === this.length - 1)
1504 		return this.popBack();
1505 	var node = this.first;
1506 	for (; index > 0; index--)
1507 		node = node.next;
1508 	//now node is the node to remove
1509 	node.previous.next = node.next;
1510 	node.next.previous = node.previous;
1511 	node.next = null;
1512 	node.previous = null;
1513 	this.length--;
1514 	return node.item;
1515 };
1516 
1517 /**
1518  * Removes the item from the list.
1519  * @param item {*} The item to remove.
1520  * @param [callback = function(item){return(it===item);}] The condition to satisfy. The callback must accept the current item to check.
1521  * @return {void}
1522  */
1523 DoubleLinkedList.prototype.remove = function (item, callback) {
1524 	callback = callback || function (it) {
1525 		return it === item;
1526 	};
1527 	var node = this.first;
1528 	var previous = null;
1529 	while (node) {
1530 		if (callback(node.item)) {
1531 			if (node === this.first)
1532 				this.first = node.next;
1533 			if (node === this.last)
1534 				this.last = previous;
1535 			if (previous) {
1536 				previous.next = node.next;
1537 				if (node.next)
1538 					node.next.previous = previous;
1539 			}
1540 			return;
1541 		}
1542 		previous = node;
1543 		node = node.next;
1544 	}
1545 };
1546 
1547 /**
1548  * Removes all the item from the list.
1549  * @param item {*} The item to remove.
1550  * @param [callback = function(item){return(it===item);}] The condition to satisfy. The callback must accept the current item to check.
1551  * @return {void}
1552  */
1553 DoubleLinkedList.prototype.removeAll = function (item, callback) {
1554 	callback = callback || function (it) {
1555 		return it === item;
1556 	};
1557 	var node = this.first;
1558 	var previous = null;
1559 	while (node) {
1560 		if (callback(node.item)) {
1561 			if (node === this.first)
1562 				this.first = node.next;
1563 			if (node === this.last)
1564 				this.last = previous;
1565 			if (previous) {
1566 				previous.next = node.next;
1567 				if (node.next)
1568 					node.next.previous = previous;
1569 			}
1570 		} else
1571 			previous = node;
1572 		node = node.next;
1573 	}
1574 };
1575 
1576 /**
1577  * Removes all the items stored from the from position to the to position.
1578  * If from > to, the method will remove all the items up to the end.
1579  * @param from {number} The position where start to remove the items. The from position is included.
1580  * @param to {number} The position where stop to remove the items. The to position is included.
1581  * @return {Array<*>} The items removed.
1582  */
1583 DoubleLinkedList.prototype.removeSegment = function (from, to) {
1584 	var result = [];
1585 	if (to > -1 && from < this.length) {
1586 		if (from === 0)
1587 			return this.multiPopFront(to + 1);
1588 		if (to === this.length - 1 || from > to)
1589 			return this.multiPopBack(Math.max(to - from, this.length - from)).reverse();
1590 		var node = this.first;
1591 		for (var i = 0; i < from - 1; i++)
1592 			node = node.next;
1593 		//now node is the node before the node to remove
1594 		//node to remove
1595 		var next = node.next;
1596 		for (var j = from; j < to + 1 && j < this.length; j++) {
1597 			result.push(next.item);
1598 			next = next.next;
1599 		}
1600 		this.length -= Math.min(to - from + 1, this.length - from);
1601 		node.next = next;
1602 		next.previous = node;
1603 	}
1604 	return result;
1605 };
1606 
1607 /**
1608  * Changes the item stored in the index position. If the index is out of bound, the node won't be updated.
1609  * @param index {number} The position of the node to modify.
1610  * @param item {*} The new item stored in the node.
1611  * @return {void}
1612  */
1613 DoubleLinkedList.prototype.modifyAt = function (index, item) {
1614 	var node = this.getNode(index);
1615 	if (node)
1616 		node.item = item;
1617 };
1618 
1619 /**
1620  * Removes all the items stored in the list.
1621  * @return {void}
1622  */
1623 DoubleLinkedList.prototype.clear = function () {
1624 	this.first = null;
1625 	this.last = null;
1626 	this.length = 0;
1627 };
1628 
1629 /**
1630  * Checks if the list contains an item that satisfy the condition represented by the callback function.
1631  * @param item {*} The item to find.
1632  * @param [callback = function(item){return(it===item);}] The condition to satisfy. The callback must accept the current item to check.
1633  * @return {boolean} True if the list contains the item that satisfy the condition, false otherwise.
1634  */
1635 DoubleLinkedList.prototype.contains = function (item, callback) {
1636 	callback = callback || function (it) {
1637 		return it === item;
1638 	};
1639 	var i = 0;
1640 	var node = this.first;
1641 	while (i < this.length && !callback(node.item)) {
1642 		i++;
1643 		node = node.next;
1644 	}
1645 	return i < this.length;
1646 };
1647 
1648 /**
1649  * Executes the callback function for each item of the stack.
1650  * This method modifies the list so if you don't need to modify it you must return the same item of the array.
1651  * @param callback {function} The function to execute for each item. The function must accept the current item on which execute the function.
1652  * @return {void}
1653  */
1654 DoubleLinkedList.prototype.execute = function (callback) {
1655 	var node = this.first;
1656 	while (node) {
1657 		node.item = callback(node.item);
1658 		node = node.next;
1659 	}
1660 };
1661 
1662 /**
1663  * Deletes the node from the list.
1664  * @param node {DLLNode} The node to delete.
1665  * @return {void}
1666  */
1667 DoubleLinkedList.prototype.deleteNode = function (node) {
1668 	if (node === this.first) {
1669 		this.popFront();
1670 		return;
1671 	}
1672 	if (node === this.last) {
1673 		this.popBack();
1674 		return;
1675 	}
1676 	node.previous.next = node.next;
1677 	node.next.previous = node.previous;
1678 	this.length--;
1679 };
1680 
1681 /**
1682  * Gets the node at the position index relative from the node.
1683  * @param index {Number} The index, relative to the node, of the node to return.
1684  * @param [node = first] {DLLNode} The node from which start the search.
1685  * @return {DLLNode} The node at the position index.
1686  */
1687 DoubleLinkedList.prototype.getNode = function (index, node) {
1688 	if (index < 0 || index > this.length - 1)
1689 		return undefined;
1690 	var m = Math.floor(this.length / 2);
1691 	//if the index is less than the middle, the search start from the head of the list, otherwise from the tail of the list
1692 	if (index < m || node) {
1693 		node = node || this.first;
1694 		for (; index > 0; index--)
1695 			node = node.next;
1696 	} else
1697 		for (index = this.length - index - 1, node = this.last; index > 0; index--)
1698 			node = node.previous;
1699 	return node;
1700 };
1701 
1702 /**
1703  * Gets the item at the position index.
1704  * @param index {Number} The position of the item.
1705  * @return {*}. It's undefined if index isn't in the queue bounds.
1706  */
1707 DoubleLinkedList.prototype.getItem = function (index) {
1708 	if (index < 0 || index > this.length - 1)
1709 		return undefined;
1710 	var node;
1711 	var m = Math.floor(this.length / 2);
1712 	if (index < m) //if the index is less than the middle, the search start from the head of the list, otherwise from the tail of the list
1713 		for (node = this.first; index > 0; index--)
1714 			node = node.next;
1715 	else
1716 		for (index = this.length - index - 1, node = this.last; index > 0; index--)
1717 			node = node.previous;
1718 	return node.item;
1719 };
1720 
1721 /**
1722  * Sorts the list using web workers.
1723  * Using this method is discouraged. Many web browser set a limit to the maximum number of workers instantiated.
1724  * The items of the list, due to web workers implementation, will be serialized so they will lost own methods.
1725  * @return {void}
1726  */
1727 DoubleLinkedList.prototype.parallelSort = function () {
1728 
1729 	var workers = [];
1730 	var _array = this.toArray();
1731 	console.log(_array);
1732 
1733 	function partialSort(_from, _to, _id) {
1734 		if (_from < _to) {
1735 			var m = Math.floor((_from + _to) / 2);
1736 			var workerLeft = new Worker("DoubleLinkedList/WorkerSort.js");
1737 			var workerRight = new Worker("DoubleLinkedList/WorkerSort.js");
1738 			workers.push(workerLeft);
1739 			workers.push(workerRight);
1740 			var length = workers.length;
1741 			workerLeft.postMessage({cmd: 'start', from: _from, to: m, worker: _id});
1742 			workerRight.postMessage({cmd: 'start', from: m + 1, to: _to, worker: _id});
1743 			partialSort(_from, m, length - 2);
1744 			partialSort(m + 1, _to, length - 1);
1745 			workerLeft.onmessage = function (event) {
1746 				var data = event.data;
1747 				switch (data.cmd) {
1748 					case 'finished':
1749 						workers[data.worker].postMessage({cmd: 'finished', array: _array});
1750 						break;
1751 					case 'replace':
1752 						_array[data.index] = data.value;
1753 						break;
1754 				}
1755 			};
1756 			workerRight.onmessage = function (event) {
1757 				var data = event.data;
1758 				switch (data.cmd) {
1759 					case 'finished':
1760 						workers[data.worker].postMessage({cmd: 'finished', array: _array});
1761 						break;
1762 					case 'replace':
1763 						_array[data.index] = data.value;
1764 						break;
1765 				}
1766 			}
1767 		}
1768 	}
1769 
1770 	var outerThis = this;
1771 
1772 	var mainWorker = new Worker("DoubleLinkedList/WorkerSort.js");
1773 	workers.push(mainWorker);
1774 	mainWorker.postMessage({cmd: 'start', from: 0, to: this.length - 1, worker: -1, array: _array});
1775 	mainWorker.onmessage = function (event) {
1776 		var data = event.data;
1777 		switch (data.cmd) {
1778 			case 'finished':
1779 				outerThis.fromArray(_array);
1780 				console.log(outerThis);
1781 				break;
1782 			case 'replace':
1783 				_array[data.index] = data.value;
1784 		}
1785 	};
1786 	partialSort(0, this.length - 1, 0);
1787 };
1788 
1789 /**
1790  * Sorts the list.
1791  * @param [callback = function(item){return(item);}] {function} The function invoked in order to get the value for the evaluation of the sort criteria.
1792  * @example
1793  * callback = function(item) {return -item.key;}
1794  * This function callback will return the opposite of the attribute key of the item. In this case the list will be sorted in descending order.
1795  * @return {void}
1796  */
1797 DoubleLinkedList.prototype.sort = function (callback) {
1798 
1799 	if (!callback)
1800 		callback = function (item) {
1801 			return item;
1802 		};
1803 
1804 	var outerThis = this;
1805 
1806 	function partialSort(from, to, fromNode, toNode) {
1807 		if (from < to) {
1808 			var m = Math.floor((from + to) / 2);
1809 			var mNode = outerThis.getNode(m - from, fromNode);
1810 			partialSort(from, m, fromNode, mNode);
1811 			partialSort(m + 1, to, mNode.next, toNode);
1812 			merge(from, m, to, fromNode);
1813 		}
1814 	}
1815 
1816 	function merge(from, m, to, fromNode) {
1817 		var left = [];
1818 		var right = [];
1819 		var node = fromNode;
1820 		for (var i = 0; i < m - from + 1; i++, node = node.next)
1821 			left[i] = node.item;
1822 		for (var j = 0; j < to - m; j++, node = node.next)
1823 			right[j] = node.item;
1824 		var x = 0, y = 0;
1825 		for (var k = from; k < to + 1; k++, fromNode = fromNode.next) {
1826 			if (y > to - m - 1 || (callback(left[x]) <= callback(right[y]) && x < m - from + 1)) {
1827 				fromNode.item = left[x];
1828 				x++;
1829 			} else {
1830 				fromNode.item = right[y];
1831 				y++;
1832 			}
1833 		}
1834 	}
1835 
1836 	partialSort(0, this.length - 1, this.first, this.last);
1837 };
1838 
1839 /**
1840  * Transforms the list into an array.
1841  * @return {Array<*>} The array built.
1842  */
1843 DoubleLinkedList.prototype.toArray = function () {
1844 	var array = [];
1845 	for (var node = this.first, i = 0; node; node = node.next, i++)
1846 		array[i] = node.item;
1847 	return array;
1848 };
1849 
1850 /**
1851  * Returns the length of the list.
1852  * @return {Number} The length of the list.
1853  */
1854 DoubleLinkedList.prototype.getLength = function () {
1855 	return this.length;
1856 };
1857 
1858 /**
1859  * Builds the list from the array.
1860  * @param array {Array<*>} The array from which build the list.
1861  * @return {void}
1862  */
1863 DoubleLinkedList.prototype.fromArray = function (array) {
1864 	var node = this.first;
1865 	for (var i = 0; i < Math.min(this.length, array.length); i++, node = node.next)
1866 		node.item = array[i];
1867 	if (this.length < array.length)
1868 		for (var j = this.length; j < array.length; j++)
1869 			this.pushBack(array[j]);
1870 	else
1871 		for (var k = array.length; k < this.length;)
1872 			this.popBack();
1873 };
1874 
1875 /**
1876  * Returns the items that satisfy the condition determined by the callback.
1877  * @param callback {function} The function that implements the condition.
1878  * @return {Array<Object>} The array that contains the items that satisfy the condition.
1879  */
1880 DoubleLinkedList.prototype.filter = function (callback) {
1881 	var result = [];
1882 	for (var node = this.first; node; node = node.next) {
1883 		if (callback(node.item))
1884 			result.push(node.item);
1885 	}
1886 	return result;
1887 };
1888 
1889 /**
1890  * Reverses the list. This method reverses only the items, not the nodes.
1891  * @return {void}
1892  */
1893 DoubleLinkedList.prototype.reverse = function () {
1894 	for (var start = this.first, end = this.last; start !== end && start.previous !== end; start = start.next, end = end.previous) {
1895 		var item = start.item;
1896 		start.item = end.item;
1897 		end.item = item;
1898 	}
1899 };
1900 
1901 /**
1902  * Checks if the list is empty.
1903  * @return {boolean} True if the list is empty, false otherwise.
1904  */
1905 DoubleLinkedList.prototype.isEmpty = function () {
1906 	return !this.length;
1907 };
1908 
1909 /**
1910  * Returns the first position of the item in the list.
1911  * @param item {*} The item to search.
1912  * @param [callback = function(item){return(it===item);}] The condition to satisfy. The callback must accept the current item to check.
1913  * @return {number} The first position of the item.
1914  */
1915 DoubleLinkedList.prototype.indexOf = function (item, callback) {
1916 	callback = callback || function (it) {
1917 		return it === item;
1918 	};
1919 	var i = 0;
1920 	var node = this.first;
1921 	while (node) {
1922 		if (callback(node.item))
1923 			return i;
1924 		i++;
1925 		node = node.next;
1926 	}
1927 	return -1;
1928 };
1929 
1930 /**
1931  * Returns the last position of the item in the list.
1932  * @param item {*} The item to search.
1933  * @param [callback = function(item){return(it===item);}] The condition to satisfy. The callback must accept the current item to check.
1934  * @return {number} The last position of the item.
1935  */
1936 DoubleLinkedList.prototype.lastIndexOf = function (item, callback) {
1937 	callback = callback || function (it) {
1938 		return it === item;
1939 	};
1940 	var i = this.length - 1;
1941 	var node = this.last;
1942 	while (node) {
1943 		if (callback(node.item))
1944 			return i;
1945 		i--;
1946 		node = node.previous;
1947 	}
1948 	return -1;
1949 };
1950 
1951 /**
1952  * Returns all the position in which the item has been found in the list.
1953  * @param item {*} The item to search.
1954  * @param [callback = function(item){return(it===item);}] The condition to satisfy. The callback must accept the current item to check.
1955  * @return {Array<number>} The positions in which the item has been found.
1956  */
1957 DoubleLinkedList.prototype.allIndexesOf = function (item, callback) {
1958 	callback = callback || function (it) {
1959 		return it === item;
1960 	};
1961 	var i = 0;
1962 	var node = this.first;
1963 	var indexes = [];
1964 	while (node) {
1965 		if (callback(node.item))
1966 			indexes.push(i);
1967 		i++;
1968 		node = node.next;
1969 	}
1970 	return indexes;
1971 };
1972 
1973 /**
1974  * Adds the list at the end of this list.
1975  * @param list {DoubleLinkedList} The list to join.
1976  * @return {void}
1977  */
1978 DoubleLinkedList.prototype.join = function (list) {
1979 	if (this.last)
1980 		this.last.next = list.first;
1981 	else
1982 		this.first = list.first;
1983 	if (list.first)
1984 		list.first.previous = this.last;
1985 	this.last = list.last;
1986 	this.length += list.length;
1987 };
1988 
1989 /**
1990  * Divides the list at the index position. The node at the index position is the first new node of the list.
1991  * @param index {number} The position where to divide the list.
1992  * @return {DoubleLinkedList} The list formed by the nodes from the index position then. If the index is out of bound, the list will be empty.
1993  */
1994 DoubleLinkedList.prototype.divide = function (index) {
1995 	var list = new DoubleLinkedList();
1996 	if (index > -1 && index < this.length) {
1997 		var node = this.first;
1998 		var previous = null;
1999 		for (var i = 0; i < index; i++) {
2000 			previous = node;
2001 			node = node.next;
2002 		}
2003 		if (node === this.first) {
2004 			list.first = this.first;
2005 			list.last = this.last;
2006 			this.first = null;
2007 			this.last = null;
2008 		} else {
2009 			list.first = node;
2010 			list.last = this.last;
2011 			this.last = previous;
2012 			previous.next = null;
2013 			node.previous = null;
2014 		}
2015 		list.length = this.length - index;
2016 		this.length = index;
2017 	}
2018 	return list;
2019 };
2020 
2021 /**
2022  * Clones the list into a new list.
2023  * @return {DoubleLinkedList} The list cloned from this list.
2024  */
2025 DoubleLinkedList.prototype.clone = function () {
2026 	var list = new DoubleLinkedList();
2027 	var node = this.first;
2028 	for (var i = 0; i < this.length; i++, node = node.next)
2029 		if (node.item.clone)
2030 			list.pushBack(node.item.clone());
2031 		else
2032 			list.pushBack(node.item);
2033 	return list;
2034 };
2035 
2036 /**
2037  * Clones the list into a new list without cloning duplicated items.
2038  * @return {DoubleLinkedList} The list cloned from this list.
2039  */
2040 DoubleLinkedList.prototype.cloneDistinct = function () {
2041 	var list = new DoubleLinkedList();
2042 	var node = this.first;
2043 	for (var i = 0; i < this.length; i++, node = node.next)
2044 		if (!list.contains(node.item))
2045 			if (node.item.cloneDistinct)
2046 				list.pushBack(node.item.cloneDistinct());
2047 			else if (node.item.clone)
2048 				list.pushBack(node.item.clone());
2049 			else
2050 				list.pushBack(node.item);
2051 	return list;
2052 };
2053 
2054 /**
2055  * Splits the list into lists of desired size.
2056  * @param size {number} The size of the lists.
2057  * @return {Array<DoubleLinkedList>} The lists created by splitting the list.
2058  */
2059 DoubleLinkedList.prototype.split = function (size) {
2060 	var length = this.length;
2061 	var lists = [this];
2062 	for (var i = size; i < length; i += size)
2063 		lists.push(lists[lists.length - 1].divide(size));
2064 	return lists;
2065 };
2066 
2067 /**
2068  * Returns the number of items that satisfy the represented by the callback function.
2069  * @param callback {function} The condition to satisfy.
2070  * @return {number} The number of items that satisfy the condition.
2071  */
2072 DoubleLinkedList.prototype.count = function (callback) {
2073 	var count = 0;
2074 	var node = this.first;
2075 	while (node) {
2076 		if (callback(node.item))
2077 			count++;
2078 		node = node.next;
2079 	}
2080 	return count;
2081 };
2082 
2083 /**
2084  * Class that implements the iterator for a double linked list.
2085  * @param aggregate {DoubleLinkedList} The aggregate to scan.
2086  * @constructor
2087  */
2088 function DoubleLinkedListIterator(aggregate) {
2089 	/**
2090 	 * The aggregate relates to this iterator.
2091 	 * @type {DoubleLinkedList}
2092 	 */
2093 	this.aggregate = aggregate;
2094 
2095 	/**
2096 	 * The pointer to the position.
2097 	 * @type {Node|null}
2098 	 */
2099 	this.pointer = null;
2100 }
2101 
2102 /**
2103  * Moves the iterator to the first position of the aggregate.
2104  * @return {void}
2105  */
2106 DoubleLinkedListIterator.prototype.first = function () {
2107 	this.pointer = this.aggregate.first;
2108 };
2109 
2110 /**
2111  * Moves the iterator to the next item.
2112  * @return {void}
2113  */
2114 DoubleLinkedListIterator.prototype.next = function () {
2115 	this.pointer = this.pointer.next;
2116 };
2117 
2118 /**
2119  * Moves the iterator to the last position of the aggregate.
2120  * @return {void}
2121  */
2122 DoubleLinkedListIterator.prototype.last = function () {
2123 	this.pointer = this.aggregate.last;
2124 };
2125 
2126 /**
2127  * Moves the iterator to the previous item.
2128  * @return {void}
2129  */
2130 DoubleLinkedListIterator.prototype.previous = function () {
2131 	this.pointer = this.pointer.previous;
2132 };
2133 
2134 /**
2135  * Checks if the iterator is out of the bounds of the aggregate.
2136  * @return {boolean} It return true if the iterator is out of the bounds of the aggregate, otherwise false.
2137  */
2138 DoubleLinkedListIterator.prototype.isDone = function () {
2139 	return !this.pointer;
2140 };
2141 
2142 /**
2143  * Returns the item stored at the position pointed by the iterator.
2144  * @abstract
2145  * @return {*} The item stored or undefined if it's out of the bounds.
2146  */
2147 DoubleLinkedListIterator.prototype.getItem = function () {
2148 	return this.pointer.item;
2149 };
2150 
2151 /**
2152  * Returns the node stored at the position pointed by the iterator.
2153  * @abstract
2154  * @return {DLLNode|null} The node stored or null if it's out of the bounds.
2155  */
2156 DoubleLinkedListIterator.prototype.getNode = function () {
2157 	return this.pointer;
2158 };
2159 
2160 /**
2161  * Class for managing an hash table.
2162  * @param size {number} The size of the table.
2163  * @constructor
2164  */
2165 function HashTable(size) {
2166 	/**
2167 	 * The size of the table
2168 	 * @type {number}
2169 	 */
2170 	this.size = size;
2171 
2172 	this.p = 1000;
2173 
2174 	this.a = Math.floor(Math.random() * this.p);
2175 
2176 	this.b = Math.floor(Math.random() * this.p);
2177 
2178 	/**
2179 	 * Calculate the hash of the param key.
2180 	 * @param key {number} The key to hash.
2181 	 * @return {number} The hash of the key.
2182 	 */
2183 	this.hash = function (key) {
2184 		return ((this.a * key + this.b) % this.p) % this.size;
2185 	};
2186 
2187 	/**
2188 	 * The items stored in the hash table.
2189 	 * @type {Array<DoubleLinkedList>}
2190 	 */
2191 	this.items = [];
2192 
2193 	/**
2194 	 * The number of keys stored in the hash table.
2195 	 * @type {number}
2196 	 */
2197 	this.keyLength = 0;
2198 
2199 	this.clear();
2200 }
2201 
2202 /**
2203  * Stores the item with its key.
2204  * @param key {number} The key relatives to the item.
2205  * @param item {*} The item to store.
2206  */
2207 HashTable.prototype.insert = function (key, item) {
2208 	this.keyLength++;
2209 	this.items[this.hash(key)].pushBack({key: key, item: item});
2210 };
2211 
2212 /**
2213  * Deletes the first item relatives to the key value.
2214  * @param key {number} The key to delete.
2215  * @return {void}
2216  */
2217 HashTable.prototype.deleteKey = function (key) {
2218 	var list = this.items[this.hash(key)];
2219 	var it = list.getIterator();
2220 	for (it.first(); !it.isDone() && it.getItem().key !== key;)
2221 		it.next();
2222 	if (!it.isDone()) {
2223 		list.deleteNode(it.getNode());
2224 		this.keyLength--;
2225 	}
2226 };
2227 
2228 /**
2229  * Deletes all the items relative to the key value.
2230  * @param key {number} The key to delete.
2231  * @return {void}
2232  */
2233 HashTable.prototype.deleteAllKey = function (key) {
2234 	var list = this.items[this.hash(key)];
2235 	var it = list.getIterator();
2236 	var keysRemoved = 0;
2237 	for (it.first(); !it.isDone(); it.next())
2238 		if (it.getItem().key === key) {
2239 			list.deleteNode(it.getNode());
2240 			keysRemoved++;
2241 		}
2242 	this.keyLength -= keysRemoved;
2243 };
2244 
2245 /**
2246  * Searches the item relative to the key value.
2247  * @param key {number} The key of the item to search.
2248  * @return {*|undefined} The item found or undefined if the key does not exist.
2249  */
2250 HashTable.prototype.search = function (key) {
2251 	var list = this.items[this.hash(key)];
2252 	var it = list.getIterator();
2253 	for (it.first(); !it.isDone(); it.next())
2254 		if (it.getItem().key === key)
2255 			return it.getItem().item;
2256 	return undefined;
2257 };
2258 
2259 /**
2260  * Checks if the hash table contains a key that satisfy the condition represented by the callback function.
2261  * @param key {number} The key to find.
2262  * @param [callback = function(k){return(k===key);}] The condition to satisfy. The callback must accept the current key to check.
2263  * @return {boolean} True if the hash table contains the key that satisfy the condition, false otherwise.
2264  */
2265 HashTable.prototype.containsKey = function (key, callback) {
2266 	callback = callback || function (k) {
2267 		return k === key;
2268 	};
2269 	var list = this.items[this.hash(key)];
2270 	var it = list.getIterator();
2271 	for (it.first(); !it.isDone(); it.next())
2272 		if (callback(it.getItem().key))
2273 			return true;
2274 	return false;
2275 };
2276 
2277 /**
2278  * Searches all the items relative to the key value.
2279  * @param key {number} The key of the items to search.
2280  * @return {Array.<*>} An array with the items found.
2281  */
2282 HashTable.prototype.searchAll = function (key) {
2283 	var list = this.items[this.hash(key)];
2284 	var it = list.getIterator();
2285 	var array = [];
2286 	for (it.first(); !it.isDone(); it.next())
2287 		if (it.getItem().key === key)
2288 			array.push(it.getItem().item);
2289 	return array;
2290 };
2291 
2292 /**
2293  * Returns the keys stored in the hash table.
2294  * @return {Array<number>} The keys stored in the table.
2295  */
2296 HashTable.prototype.getKeys = function () {
2297 	var keys = [];
2298 	for (var i = 0; i < this.size; i++) {
2299 		var it = this.items[i].getIterator();
2300 		for (it.first(); !it.isDone(); it.next())
2301 			keys.push(it.getItem().key);
2302 	}
2303 	return keys;
2304 };
2305 
2306 /**
2307  * Returns the items stored in the hash table.
2308  * @return {Array<*>} The items stored in the table.
2309  */
2310 HashTable.prototype.getItems = function () {
2311 	var items = [];
2312 	for (var i = 0; i < this.size; i++) {
2313 		var it = this.items[i].getIterator();
2314 		for (it.first(); !it.isDone(); it.next())
2315 			items.push(it.getItem().item);
2316 	}
2317 	return items;
2318 };
2319 
2320 /**
2321  * Removes all the keys and the items stored in the hash table.
2322  * @return {void}
2323  */
2324 HashTable.prototype.clear = function () {
2325 	this.items = [];
2326 	for (var i = 0; i < this.size; i++)
2327 		this.items[i] = new DoubleLinkedList();
2328 	this.keyLength = 0;
2329 };
2330 
2331 /**
2332  * Returns the number of keys stored in the hash table.
2333  * @return {number} The number of keys stored.
2334  */
2335 HashTable.prototype.getNumberOfKeys = function () {
2336 	return this.keyLength;
2337 };
2338 
2339 /**
2340  * Checks if the hash table is empty.
2341  * @return {boolean} True if the hash table is empty, false otherwise.
2342  */
2343 HashTable.prototype.isEmpty = function () {
2344 	return !this.keyLength;
2345 };
2346 
2347 /**
2348  * Executes the callback function for each item of the hash table.
2349  * This method modifies the hash table so if you don't need to modify it you must return the same item stored.
2350  * @param callback {function} The function to execute for each item. The function must accept the current item on which execute the function.
2351  * @return {void}
2352  */
2353 HashTable.prototype.execute = function (callback) {
2354 	for (var i = 0; i < this.size; i++)
2355 		this.items[i].execute(callback);
2356 };
2357 
2358 /**
2359  * Returns the items that satisfy the condition determined by the callback.
2360  * @param callback {function} The function that implements the condition.
2361  * @return {Array<*>} The array that contains the items that satisfy the condition.
2362  */
2363 HashTable.prototype.filter = function (callback) {
2364 	var result = [];
2365 	for (var i = 0; i < this.size; i++)
2366 		result.concat(this.items[i].filter(callback));
2367 	return result;
2368 };
2369 
2370 /**
2371  * Returns the size of the hash table.
2372  * @return {number} The size of the hash table.
2373  */
2374 HashTable.prototype.getSize = function () {
2375 	return this.size;
2376 };
2377 
2378 /**
2379  * Clones the hash table into a new hash table.
2380  * @return {HashTable} The hash table cloned from this hash table.
2381  */
2382 HashTable.prototype.clone = function () {
2383 	var table = new HashTable(this.size);
2384 	for (var i = 0; i < this.size; i++)
2385 		for (var node = this.items[i].first; node; node = node.next)
2386 			table.insert(node.key, node.item);
2387 	return table;
2388 };
2389 
2390 /**
2391  * Class for managing a linked list.
2392  * @param {...*} [args] The items for initializing the list.
2393  * @constructor
2394  */
2395 function LinkedList(args) {
2396 	/**
2397 	 * The first node of the list.
2398 	 * @type {LLNode|null}
2399 	 */
2400 	this.first = null;
2401 	/**
2402 	 * The last node of the list.
2403 	 * @type {LLNode|null}
2404 	 */
2405 	this.last = null;
2406 	/**
2407 	 * The length of the list.
2408 	 * @type {number}
2409 	 */
2410 	this.length = 0;
2411 	//builds the list from the parameters of the constructor
2412 	this.fromArray(arguments);
2413 }
2414 
2415 /**
2416  * Returns the iterator relative to the aggregate.
2417  * @return {Iterator} The iterator.
2418  */
2419 LinkedList.prototype.getIterator = function () {
2420 	return new LinkedListIterator(this);
2421 };
2422 
2423 /**
2424  * Adds an item at the head of the list.
2425  * @param item {*} The item to add.
2426  * @return {void}
2427  */
2428 LinkedList.prototype.pushFront = function (item) {
2429 	var node = new LLNode(item);
2430 	node.next = this.first;
2431 	this.first = node;
2432 	if (!this.last)
2433 		this.last = node;
2434 	this.length++;
2435 };
2436 
2437 /**
2438  * Adds an item at the tail of the list.
2439  * @param item {*} The item to add.
2440  * @return {void}
2441  */
2442 LinkedList.prototype.pushBack = function (item) {
2443 	var node = new LLNode(item);
2444 	if (this.last)
2445 		this.last.next = node;
2446 	else
2447 		this.first = node;
2448 	this.last = node;
2449 	this.length++;
2450 };
2451 
2452 /**
2453  * Removes the first item of the list.
2454  * @return {*} The item removed. It's undefined if the list is empty.
2455  */
2456 LinkedList.prototype.popFront = function () {
2457 	if (this.length) {
2458 		var node = this.first;
2459 		this.first = this.first.next;
2460 		this.length--;
2461 		node.next = null;
2462 		return node.item;
2463 	}
2464 	return undefined;
2465 };
2466 
2467 /**
2468  * Removes the last item of the list.
2469  * @return {*} The item removed. It's undefined if the list is empty.
2470  */
2471 LinkedList.prototype.popBack = function () {
2472 	if (this.length) {
2473 		var node = this.last;
2474 		var next = this.first;
2475 		while (next.next && next.next.next) {
2476 			next = next.next;
2477 		}
2478 		if (node === next)
2479 			this.last = null;
2480 		else
2481 			this.last = next;
2482 		next.next = null;
2483 		this.length--;
2484 		return node.item;
2485 	}
2486 	return undefined;
2487 };
2488 
2489 /**
2490  * Removes the first times items of the list.
2491  * @param times {number} The number of times to repeat the popFront method.
2492  * @return {*} The item removed. It's undefined if the list is empty.
2493  */
2494 LinkedList.prototype.multiPopFront = function (times) {
2495 	var result = [];
2496 	for (var i = 0; i < times && this.length; i++)
2497 		result.push(this.popFront());
2498 	return result;
2499 };
2500 
2501 /**
2502  * Removes the last times items of the list.
2503  * @param times {number} The number of times to repeat the popBack method.
2504  * @return {*} The items removed.
2505  */
2506 LinkedList.prototype.multiPopBack = function (times) {
2507 	var result = [];
2508 	for (var i = 0; i < times && this.length; i++)
2509 		result.push(this.popBack());
2510 	return result;
2511 };
2512 
2513 /**
2514  * Returns the first item of the list without remove it.
2515  * @return {*} The item at the top of the list. It's undefined if the list is empty.
2516  */
2517 LinkedList.prototype.peek = function () {
2518 	if (!this.length)
2519 		return undefined;
2520 	return this.first.item;
2521 };
2522 
2523 /**
2524  * Adds the item at the index position.
2525  * @param item {*} The item to add.
2526  * @param index {number} The position where to add the item. If index is negative, the item won't be added.
2527  * @return {void}
2528  */
2529 LinkedList.prototype.addAt = function (item, index) {
2530 	if (index < -1)
2531 		return;
2532 	if (!index) {
2533 		this.pushFront(item);
2534 		return;
2535 	}
2536 	if (index === this.length) {
2537 		this.pushBack(item);
2538 		return;
2539 	}
2540 	var node = this.first;
2541 	if (!node && index > 0)
2542 		this.pushBack(undefined);
2543 	for (var i = 0; i < index - 1; i++, node = node.next) {
2544 		if (node === this.last)
2545 			this.pushBack(undefined);
2546 	}
2547 	if (node === this.last)
2548 		this.pushBack(item);
2549 	else if (node === this.first)
2550 		this.pushFront(item);
2551 	else {
2552 		var newNode = new LLNode(item);
2553 		newNode.next = node.next;
2554 		node.next = newNode;
2555 		this.length++;
2556 	}
2557 };
2558 
2559 /**
2560  * Removes the item at the index position.
2561  * @param index {number} The position of the item to remove.
2562  * @return {*} The item stored at the position index. It's undefined if the index is out of bounds.
2563  */
2564 LinkedList.prototype.removeAt = function (index) {
2565 	if (index < 0 || index > this.length - 1)
2566 		return undefined;
2567 	if (index === 0)
2568 		return this.popFront();
2569 	if (index === this.length - 1)
2570 		return this.popBack();
2571 	var node = this.first;
2572 	for (; index > 1; index--)
2573 		node = node.next;
2574 	//now node is the node before the node to remove
2575 	//node to remove
2576 	var next = node.next;
2577 	node.next = next.next;
2578 	this.length--;
2579 	return next.item;
2580 };
2581 
2582 /**
2583  * Removes the item from the list.
2584  * @param item {*} The item to remove.
2585  * @param [callback = function(item){return(it===item);}] The condition to satisfy. The callback must accept the current item to check.
2586  * @return {void}
2587  */
2588 LinkedList.prototype.remove = function (item, callback) {
2589 	callback = callback || function (it) {
2590 		return it === item;
2591 	};
2592 	var node = this.first;
2593 	var previous = null;
2594 	while (node) {
2595 		if (callback(node.item)) {
2596 			if (node === this.first)
2597 				this.first = node.next;
2598 			if (node === this.last)
2599 				this.last = previous;
2600 			if (previous)
2601 				previous.next = node.next;
2602 			return;
2603 		}
2604 		previous = node;
2605 		node = node.next;
2606 	}
2607 };
2608 
2609 /**
2610  * Removes all the item from the list.
2611  * @param item {*} The item to remove.
2612  * @param [callback = function(item){return(it===item);}] The condition to satisfy. The callback must accept the current item to check.
2613  * @return {void}
2614  */
2615 LinkedList.prototype.removeAll = function (item, callback) {
2616 	callback = callback || function (it) {
2617 		return it === item;
2618 	};
2619 	var node = this.first;
2620 	var previous = null;
2621 	while (node) {
2622 		if (callback(node.item)) {
2623 			if (node === this.first)
2624 				this.first = node.next;
2625 			if (node === this.last)
2626 				this.last = previous;
2627 			if (previous)
2628 				previous.next = node.next;
2629 		} else
2630 			previous = node;
2631 		node = node.next;
2632 	}
2633 };
2634 
2635 /**
2636  * Removes all the items stored from the from position to the to position.
2637  * If from > to, the method will remove all the items up to the end.
2638  * @param from {number} The position where start to remove the items. The from position is included.
2639  * @param to {number} The position where stop to remove the items. The to position is included.
2640  * @return {Array<*>} The items removed.
2641  */
2642 LinkedList.prototype.removeSegment = function (from, to) {
2643 	var result = [];
2644 	if (to > -1 && from < this.length) {
2645 		if (from === 0)
2646 			return this.multiPopFront(to + 1);
2647 		if (to === this.length - 1 || from > to)
2648 			return this.multiPopBack(Math.max(to - from, this.length - from)).reverse();
2649 		var node = this.first;
2650 		for (var i = 0; i < from - 1; i++)
2651 			node = node.next;
2652 		//now node is the node before the node to remove
2653 		//node to remove
2654 		var next = node.next;
2655 		for (var j = from; j < to + 1 && j < this.length; j++) {
2656 			result.push(next.item);
2657 			next = next.next;
2658 		}
2659 		this.length -= Math.min(to - from + 1, this.length - from);
2660 		node.next = next;
2661 	}
2662 	return result;
2663 };
2664 
2665 /**
2666  * Changes the item stored in the index position. If the index is out of bound, the node won't be updated.
2667  * @param index {number} The position of the node to modify.
2668  * @param item {*} The new item stored in the node.
2669  * @return {void}
2670  */
2671 LinkedList.prototype.modifyAt = function (index, item) {
2672 	var node = this.getNode(index);
2673 	if (node)
2674 		node.item = item;
2675 };
2676 
2677 /**
2678  * Removes all the items stored in the list.
2679  * @return {void}
2680  */
2681 LinkedList.prototype.clear = function () {
2682 	this.first = null;
2683 	this.last = null;
2684 	this.length = 0;
2685 };
2686 
2687 /**
2688  * Checks if the list contains an item that satisfy the condition represented by the callback function.
2689  * @param item {*} The item to find.
2690  * @param [callback = function(item){return(it===item);}] The condition to satisfy. The callback must accept the current item to check.
2691  * @return {boolean} True if the list contains the item that satisfy the condition, false otherwise.
2692  */
2693 LinkedList.prototype.contains = function (item, callback) {
2694 	callback = callback || function (it) {
2695 		return it === item;
2696 	};
2697 	var i = 0;
2698 	var node = this.first;
2699 	while (i < this.length && !callback(node.item)) {
2700 		i++;
2701 		node = node.next;
2702 	}
2703 	return i < this.length;
2704 };
2705 
2706 /**
2707  * Executes the callback function for each item of the stack.
2708  * This method modifies the list so if you don't need to modify it you must return the same item of the array.
2709  * @param callback {function} The function to execute for each item. The function must accept the current item on which execute the function.
2710  * @return {void}
2711  */
2712 LinkedList.prototype.execute = function (callback) {
2713 	var node = this.first;
2714 	while (node) {
2715 		node.item = callback(node.item);
2716 		node = node.next;
2717 	}
2718 };
2719 
2720 /**
2721  * Returns the node at the position index.
2722  * @param index {number} The position of the node.
2723  * @return {LLNode} The node stored at the position index. It's undefined if index isn't in the list bounds.
2724  */
2725 LinkedList.prototype.getNode = function (index) {
2726 	if (index < 0 || index > this.length - 1)
2727 		return undefined;
2728 	var node = this.first;
2729 	for (; index > 0; index--)
2730 		node = node.next;
2731 	return node;
2732 };
2733 
2734 /**
2735  * Returns the item at the position index.
2736  * @param index {number} The position of the item.
2737  * @return {*} The item stored at the position index. It's undefined if index isn't in the list bounds.
2738  */
2739 LinkedList.prototype.getItem = function (index) {
2740 	if (index < 0 || index > this.length - 1)
2741 		return undefined;
2742 	var node = this.first;
2743 	for (; index > 0; index--)
2744 		node = node.next;
2745 	return node.item;
2746 };
2747 
2748 /**
2749  * Transforms the list into an array.
2750  * @return {Array<*>} The array built.
2751  */
2752 LinkedList.prototype.toArray = function () {
2753 	var array = [];
2754 	for (var node = this.first, i = 0; node; node = node.next, i++)
2755 		array[i] = node.item;
2756 	return array;
2757 };
2758 
2759 /**
2760  * Returns the length of the list.
2761  * @return {Number} The length of the list.
2762  */
2763 LinkedList.prototype.getLength = function () {
2764 	return this.length;
2765 };
2766 
2767 /**
2768  * Builds the list from the array.
2769  * @param array {Array<*>} The array from which build the list.
2770  * @return {void}
2771  */
2772 LinkedList.prototype.fromArray = function (array) {
2773 	var node = this.first;
2774 	for (var i = 0; i < Math.min(this.length, array.length); i++, node = node.next)
2775 		node.item = array[i];
2776 	if (this.length < array.length)
2777 		for (var j = this.length; j < array.length; j++)
2778 			this.pushBack(array[j]);
2779 	else
2780 		for (var k = array.length; k < this.length;)
2781 			this.popBack();
2782 };
2783 
2784 /**
2785  * Returns the items that satisfy the condition determined by the callback.
2786  * @param callback {function} The function that implements the condition.
2787  * @return {Array<*>} The array that contains the items that satisfy the condition.
2788  */
2789 LinkedList.prototype.filter = function (callback) {
2790 	var result = [];
2791 	for (var node = this.first; node; node = node.next) {
2792 		if (callback(node.item))
2793 			result.push(node.item);
2794 	}
2795 	return result;
2796 };
2797 
2798 /**
2799  * Checks if the list is empty.
2800  * @return {boolean} True if the list is empty, false otherwise.
2801  */
2802 LinkedList.prototype.isEmpty = function () {
2803 	return !this.length;
2804 };
2805 
2806 /**
2807  * Returns the first position of the item in the list.
2808  * @param item {*} The item to search.
2809  * @param [callback = function(item){return(it===item);}] The condition to satisfy. The callback must accept the current item to check.
2810  * @return {number} The first position of the item.
2811  */
2812 LinkedList.prototype.indexOf = function (item, callback) {
2813 	callback = callback || function (it) {
2814 		return it === item;
2815 	};
2816 	var i = 0;
2817 	var node = this.first;
2818 	while (node) {
2819 		if (callback(node.item))
2820 			return i;
2821 		i++;
2822 		node = node.next;
2823 	}
2824 	return -1;
2825 };
2826 
2827 /**
2828  * Returns the last position of the item in the list.
2829  * @param item {*} The item to search.
2830  * @param [callback = function(item){return(it===item);}] The condition to satisfy. The callback must accept the current item to check.
2831  * @return {number} The last position of the item.
2832  */
2833 LinkedList.prototype.lastIndexOf = function (item, callback) {
2834 	callback = callback || function (it) {
2835 		return it === item;
2836 	};
2837 	var i = 0;
2838 	var node = this.first;
2839 	var index = -1;
2840 	while (node) {
2841 		if (callback(node.item))
2842 			index = i;
2843 		i++;
2844 		node = node.next;
2845 	}
2846 	return index;
2847 };
2848 
2849 /**
2850  * Returns all the position in which the item has been found in the list.
2851  * @param item {*} The item to search.
2852  * @param [callback = function(item){return(it===item);}] The condition to satisfy. The callback must accept the current item to check.
2853  * @return {Array<number>} The positions in which the item has been found.
2854  */
2855 LinkedList.prototype.allIndexesOf = function (item, callback) {
2856 	callback = callback || function (it) {
2857 		return it === item;
2858 	};
2859 	var i = 0;
2860 	var node = this.first;
2861 	var indexes = [];
2862 	while (node) {
2863 		if (callback(node.item))
2864 			indexes.push(i);
2865 		i++;
2866 		node = node.next;
2867 	}
2868 	return indexes;
2869 };
2870 
2871 /**
2872  * Joins the list at the end of this list.
2873  * @param list {LinkedList} The list to join.
2874  * @return {void}
2875  */
2876 LinkedList.prototype.join = function (list) {
2877 	if (this.last)
2878 		this.last.next = list.first;
2879 	else
2880 		this.first = list.first;
2881 	this.last = list.last;
2882 	this.length += list.length;
2883 };
2884 
2885 /**
2886  * Divides the list at the index position. The node at the index position is the first new node of the list.
2887  * @param index {number} The position where to divide the list.
2888  * @return {LinkedList} The list formed by the nodes from the index position then. If the index is out of bound, the list will be empty.
2889  */
2890 LinkedList.prototype.divide = function (index) {
2891 	var list = new LinkedList();
2892 	if (index > -1 && index < this.length) {
2893 		var node = this.first;
2894 		var previous = null;
2895 		for (var i = 0; i < index; i++) {
2896 			previous = node;
2897 			node = node.next;
2898 		}
2899 		if (node === this.first) {
2900 			list.first = this.first;
2901 			list.last = this.last;
2902 			this.first = null;
2903 			this.last = null;
2904 		} else {
2905 			list.first = node;
2906 			list.last = this.last;
2907 			this.last = previous;
2908 			previous.next = null;
2909 		}
2910 		list.length = this.length - index;
2911 		this.length = index;
2912 	}
2913 	return list;
2914 };
2915 
2916 /**
2917  * Clones the list into a new list.
2918  * @return {LinkedList} The list cloned from this list.
2919  */
2920 LinkedList.prototype.clone = function () {
2921 	var list = new LinkedList();
2922 	var node = this.first;
2923 	for (var i = 0; i < this.length; i++, node = node.next)
2924 		if (node.item.clone)
2925 			list.pushBack(node.item.clone());
2926 		else
2927 			list.pushBack(node.item);
2928 	return list;
2929 };
2930 
2931 /**
2932  * Clones the list into a new list without cloning duplicated items.
2933  * @return {LinkedList} The list cloned from this list.
2934  */
2935 LinkedList.prototype.cloneDistinct = function () {
2936 	var list = new LinkedList();
2937 	var node = this.first;
2938 	for (var i = 0; i < this.length; i++, node = node.next)
2939 		if (!list.contains(node.item))
2940 			if (node.item.cloneDistinct)
2941 				list.pushBack(node.item.cloneDistinct());
2942 			else if (node.item.clone)
2943 				list.pushBack(node.item.clone());
2944 			else
2945 				list.pushBack(node.item);
2946 	return list;
2947 };
2948 
2949 /**
2950  * Splits the list into lists of desired size.
2951  * @param size {number} The size of the lists.
2952  * @return {Array<LinkedList>} The lists created by splitting the list.
2953  */
2954 LinkedList.prototype.split = function (size) {
2955 	var length = this.length;
2956 	var lists = [this];
2957 	for (var i = size; i < length; i += size)
2958 		lists.push(lists[lists.length - 1].divide(size));
2959 	return lists;
2960 };
2961 
2962 /**
2963  * Returns the number of items that satisfy the represented by the callback function.
2964  * @param callback {function} The condition to satisfy.
2965  * @return {number} The number of items that satisfy the condition.
2966  */
2967 LinkedList.prototype.count = function (callback) {
2968 	var count = 0;
2969 	var node = this.first;
2970 	while (node) {
2971 		if (callback(node.item))
2972 			count++;
2973 		node = node.next;
2974 	}
2975 	return count;
2976 };
2977 
2978 /**
2979  * Class that implements the iterator for a linked list.
2980  * @param aggregate {LinkedList} The aggregate to scan.
2981  * @constructor
2982  */
2983 function LinkedListIterator(aggregate) {
2984 	/**
2985 	 * The aggregate relates to this iterator.
2986 	 * @type {LinkedList}
2987 	 */
2988 	this.aggregate = aggregate;
2989 
2990 	/**
2991 	 * The pointer to the position.
2992 	 * @type {Node|null}
2993 	 */
2994 	this.pointer = null;
2995 }
2996 
2997 /**
2998  * Moves the iterator to the first position of the aggregate.
2999  * @return {void}
3000  */
3001 LinkedListIterator.prototype.first = function () {
3002 	this.pointer = this.aggregate.first;
3003 };
3004 
3005 /**
3006  * Moves the iterator to the next item.
3007  * @return {void}
3008  */
3009 LinkedListIterator.prototype.next = function () {
3010 	this.pointer = this.pointer.next;
3011 };
3012 
3013 /**
3014  * Moves the iterator to the last position of the aggregate.
3015  * @return {void}
3016  */
3017 LinkedListIterator.prototype.last = function () {
3018 	this.pointer = this.aggregate.last;
3019 };
3020 
3021 /**
3022  * Moves the iterator to the previous item.
3023  * @return {void}
3024  */
3025 LinkedListIterator.prototype.previous = function () {
3026 	var node = this.pointer;
3027 	for (this.pointer = this.first(); this.pointer.next !== node;)
3028 		this.next();
3029 };
3030 
3031 /**
3032  * Checks if the iterator is out of the bounds of the aggregate.
3033  * @return {boolean} It return true if the iterator is out of the bounds of the aggregate, otherwise false.
3034  */
3035 LinkedListIterator.prototype.isDone = function () {
3036 	return !this.pointer;
3037 };
3038 
3039 /**
3040  * Returns the item stored at the position pointed by the iterator.
3041  * @return {*} The item stored or undefined if it's out of the bounds.
3042  */
3043 LinkedListIterator.prototype.getItem = function () {
3044 	return this.pointer.item;
3045 };
3046 
3047 /**
3048  * Returns the node stored at the position pointed by the iterator.
3049  * @abstract
3050  * @return {Node|null} The node stored or null if it's out of the bounds.
3051  */
3052 LinkedListIterator.prototype.getNode = function () {
3053 	return this.pointer;
3054 };
3055 
3056 /**
3057  * Class for managing a priority queue.
3058  * @constructor
3059  */
3060 function PriorityQueue() {
3061 	/**
3062 	 * The list of the items in the queue.
3063 	 * @type {RBTreeList}
3064 	 */
3065 	this.items = new RBTreeList();
3066 	/**
3067 	 * The length of the queue.
3068 	 * @type {number}
3069 	 */
3070 	this.length = 0;
3071 }
3072 
3073 /**
3074  * Returns the iterator relative to the aggregate.
3075  * @return {Iterator} The iterator.
3076  */
3077 PriorityQueue.prototype.getIterator = function () {
3078 	return new PriorityQueueIterator(this);
3079 };
3080 
3081 /**
3082  * Adds the item at the tail of the queue.
3083  * @param priority {number} The priority of the item.
3084  * @param item {*} The item to add.
3085  * @return {void}
3086  */
3087 PriorityQueue.prototype.enqueue = function (priority, item) {
3088 	var queue = this.items.search(priority);
3089 	if (!queue) {
3090 		queue = new Queue();
3091 		this.items.insert(priority, queue);
3092 	}
3093 	queue.enqueue(item);
3094 	this.length++;
3095 };
3096 
3097 /**
3098  * Adds the items with the same priority at the tail of the queue.
3099  * @param priority {number} The priority of the items.
3100  * @param items {Array<*>} The items to add.
3101  * @return {void}
3102  */
3103 PriorityQueue.prototype.multiEnqueue = function (priority, items) {
3104 	for (var i = 0; i < items.length; i++)
3105 		this.enqueue(priority, items[i]);
3106 };
3107 
3108 /**
3109  * Removes the item at the head of the queue.
3110  * @return {*} The item at the head of the queue. It's undefined if the queue is empty.
3111  */
3112 PriorityQueue.prototype.dequeue = function () {
3113 	var node = this.items.maximum();
3114 	var item = undefined;
3115 	if (node) {
3116 		var queue = node.item;
3117 		item = queue.dequeue();
3118 		if (queue.isEmpty())
3119 			this.items.deleteNode(node);
3120 		this.length--;
3121 	}
3122 	return item;
3123 };
3124 
3125 /**
3126  * Removes the items at the head of the queue.
3127  * @param times {number} The number of times to repeat the dequeue method.
3128  * @return {Array<*>} The items at the head of the queue.
3129  */
3130 PriorityQueue.prototype.multiDequeue = function (times) {
3131 	var items = [];
3132 	for (var i = 0; i < times && this.length; i++)
3133 		items.push(this.dequeue());
3134 	return items;
3135 };
3136 
3137 /**
3138  * Removes the first length items from the position index.
3139  * @param index {number} The position where to start to remove the items.
3140  * @param [length = 1] {number} The number of items to remove.
3141  * @return {void}
3142  */
3143 PriorityQueue.prototype.remove = function (index, length) {
3144 	length = length || 1;
3145 	var it = this.items.getIterator();
3146 	for (it.last(); !it.isDone() && length > 0; it.previous()) {
3147 		var queue = it.getItem();
3148 		if (index > -1 && index < queue.getLength()) {
3149 			var oldLength = queue.getLength();
3150 			queue.remove(index, length);
3151 			length -= oldLength - index;
3152 			index = 0;
3153 			if (!queue.getLength())
3154 				this.items.deleteNode(it.getNode());
3155 		} else
3156 			index = index - queue.getLength();
3157 	}
3158 };
3159 
3160 /**
3161  * Returns the item at the position index.
3162  * @param index {number} The index of the item.
3163  * @return {*} The item found. It's undefined if the position index is out of bounds.
3164  */
3165 PriorityQueue.prototype.getItem = function (index) {
3166 	var it = this.items.getIterator();
3167 	for (it.last(); !it.isDone(); it.previous()) {
3168 		var queue = it.getItem();
3169 		if (index > -1 && index < queue.getLength())
3170 			return queue.getItem(index);
3171 		index = index - queue.getLength();
3172 	}
3173 	return undefined;
3174 };
3175 
3176 /**
3177  * Returns the items relatives to the priority.
3178  * @param priority {number} The priority of the items.
3179  * @return {Array<*>} The items found.
3180  */
3181 PriorityQueue.prototype.getItems = function (priority) {
3182 	var items = this.items.search(priority);
3183 	if (items)
3184 		return items.items;
3185 	return [];
3186 };
3187 
3188 /**
3189  * Returns the first item in the queue. The item is not removed.
3190  * @return {*} The first item. It's undefined if the queue is empty.
3191  */
3192 PriorityQueue.prototype.peek = function () {
3193 	return this.items.maximum().item.peek();
3194 };
3195 
3196 /**
3197  * Returns the length of the queue.
3198  * @return {number} The length of the queue.
3199  */
3200 PriorityQueue.prototype.getLength = function () {
3201 	return this.length;
3202 };
3203 
3204 /**
3205  * Checks if the queue is empty.
3206  * @return {boolean} True if the queue is empty, false otherwise.
3207  */
3208 PriorityQueue.prototype.isEmpty = function () {
3209 	return !this.length;
3210 };
3211 
3212 /**
3213  * Removes all the items stored in the queue.
3214  * @return {void}
3215  */
3216 PriorityQueue.prototype.clear = function () {
3217 	this.items = new RBTreeList();
3218 	this.length = 0;
3219 };
3220 
3221 /**
3222  * Checks if the queue contains a priority that satisfy the condition represented by the callback function.
3223  * @param priority {number} The priority to find.
3224  * @param [callback = function(p){return(p===priority);}] The condition to satisfy. The callback must accept the current priority to check.
3225  * @return {boolean} True if the queue contains the priority that satisfy the condition, false otherwise.
3226  */
3227 PriorityQueue.prototype.containsPriority = function (priority, callback) {
3228 	if (callback)
3229 		return this.items.fullContains(callback);
3230 	else
3231 		return this.items.contains(priority);
3232 };
3233 
3234 /**
3235  * Returns the queue created by the priority queue with the items in the same order but without the priority.
3236  * @return {Queue} The queue created.
3237  */
3238 PriorityQueue.prototype.toQueue = function () {
3239 	var queue = new Queue();
3240 	var it = this.items.getIterator();
3241 	for (it.last(); !it.isDone(); it.previous()) {
3242 		var item = it.getItem();
3243 		var itQ = item.getIterator();
3244 		for (itQ.first(); !itQ.isDone(); itQ.next())
3245 			queue.enqueue(itQ.getItem());
3246 	}
3247 	return queue;
3248 };
3249 
3250 /**
3251  * Executes the callback function for each item of the queue.
3252  * This method modifies the queue so if you don't need to modify it you must return the same item of the array.
3253  * @param callback {function} The function to execute for each item. The function must accept the current item on which execute the function.
3254  * @return {void}
3255  */
3256 PriorityQueue.prototype.execute = function (callback) {
3257 	var it = this.items.getIterator();
3258 	for (it.last(); !it.isDone(); it.previous())
3259 		it.getItem().execute(callback);
3260 };
3261 
3262 /**
3263  * Changes the priority of the item at the position index.
3264  * @param index {number} The position of the item of which increase the priority.
3265  * @param newPriority {number} The new priority.
3266  * @return {void}
3267  */
3268 PriorityQueue.prototype.changePriority = function (index, newPriority) {
3269 	var item = this.getItem(index);
3270 	this.remove(index);
3271 	this.enqueue(newPriority, item);
3272 };
3273 
3274 /**
3275  * Returns the items that satisfy the condition determined by the callback.
3276  * @param callback {function} The function that implements the condition.
3277  * @return {Array<*>} The array that contains the items that satisfy the condition.
3278  */
3279 PriorityQueue.prototype.filter = function (callback) {
3280 	var result = [];
3281 	var it = this.items.getIterator();
3282 	for (it.last(); !it.isDone(); it.previous()) {
3283 		var itQ = it.getItem().getIterator();
3284 		for (itQ.first(); !itQ.isDone(); itQ.next()) {
3285 			if (callback(itQ.getItem()))
3286 				result.push(itQ.getItem());
3287 		}
3288 	}
3289 	return result;
3290 };
3291 
3292 /**
3293  * Clones the queue into a new queue.
3294  * @return {PriorityQueue} The queue cloned from this queue.
3295  */
3296 PriorityQueue.prototype.clone = function () {
3297 	var queue = new PriorityQueue();
3298 	queue.items = this.items.clone();
3299 	queue.length = this.length;
3300 	return queue;
3301 };
3302 
3303 /**
3304  * Clones the queue into a new queue without cloning duplicated items.
3305  * @return {PriorityQueue} The queue cloned from this queue.
3306  */
3307 PriorityQueue.prototype.cloneDistinct = function () {
3308 	var queue = new PriorityQueue();
3309 	queue.items = this.items.cloneDistinct();
3310 	queue.length = queue.items.getSize();
3311 	return queue;
3312 };
3313 
3314 /**
3315  * Class that implements the iterator for a priority queue.
3316  * @param aggregate {PriorityQueue} The aggregate to scan.
3317  * @constructor
3318  */
3319 function PriorityQueueIterator(aggregate) {
3320 	/**
3321 	 * The aggregate relates to this iterator.
3322 	 * @type {PriorityQueue}
3323 	 */
3324 	this.aggregate = aggregate;
3325 
3326 	/**
3327 	 * The pointer to the position of the node.
3328 	 * @type {RBLNode|null}
3329 	 */
3330 	this.pointerNode = null;
3331 	/**
3332 	 * The pointer to the position in the node.
3333 	 * @type {number}
3334 	 */
3335 	this.pointerPosition = -1;
3336 }
3337 
3338 /**
3339  * Moves the iterator to the first position of the aggregate.
3340  * @return {void}
3341  */
3342 PriorityQueueIterator.prototype.first = function () {
3343 	this.pointerNode = this.aggregate.items.maximum();
3344 	this.pointerPosition = 0;
3345 };
3346 
3347 /**
3348  * Moves the iterator to the next item.
3349  * @return {void}
3350  */
3351 PriorityQueueIterator.prototype.next = function () {
3352 	this.pointerPosition++;
3353 	if (this.pointerPosition > this.pointerNode.item.getLength() - 1) {
3354 		this.pointerNode = this.pointerNode.previous;
3355 		this.pointerPosition = 0;
3356 	}
3357 };
3358 
3359 /**
3360  * Moves the iterator to the last position of the aggregate.
3361  * @return {void}
3362  */
3363 PriorityQueueIterator.prototype.last = function () {
3364 	this.pointerNode = this.aggregate.items.minimum();
3365 	this.pointerPosition = this.pointerNode.item.getLength() - 1;
3366 };
3367 
3368 /**
3369  * Moves the iterator to the previous item.
3370  * @return {void}
3371  */
3372 PriorityQueueIterator.prototype.previous = function () {
3373 	this.pointerPosition--;
3374 	if (this.pointerPosition < 0) {
3375 		this.pointerNode = this.pointerNode.next;
3376 		if (this.pointerNode)
3377 			this.pointerPosition = this.pointerNode.item.getLength() - 1;
3378 	}
3379 };
3380 
3381 /**
3382  * Checks if the iterator is out of the bounds of the aggregate.
3383  * @return {boolean} It return true if the iterator is out of the bounds of the aggregate, otherwise false.
3384  */
3385 PriorityQueueIterator.prototype.isDone = function () {
3386 	return !this.pointerNode;
3387 };
3388 
3389 /**
3390  * Returns the item stored at the position pointed by the iterator.
3391  * @return {*} The item stored or undefined if it's out of the bounds.
3392  */
3393 PriorityQueueIterator.prototype.getItem = function () {
3394 	return this.pointerNode.item.items[this.pointerPosition];
3395 };
3396 
3397 /**
3398  * Class for managing a queue.
3399  * @param {...*} [args] The items for initializing the queue.
3400  * @constructor
3401  */
3402 function Queue(args) {
3403 	/**
3404 	 * The list of the items in the queue.
3405 	 * @type {Array<*>}
3406 	 */
3407 	this.items = [];
3408 
3409 	//builds the queue from the parameters of the constructor
3410 	this.multiEnqueue(arguments);
3411 }
3412 
3413 /**
3414  * Returns the iterator relative to the aggregate.
3415  * @return {Iterator} The iterator.
3416  */
3417 Queue.prototype.getIterator = function () {
3418 	return new QueueIterator(this);
3419 };
3420 
3421 /**
3422  * Adds the item at the tail of the queue.
3423  * @param item {*} The item to add.
3424  * @return {void}
3425  */
3426 Queue.prototype.enqueue = function (item) {
3427 	this.items.push(item);
3428 };
3429 
3430 /**
3431  * Adds the items at the tail of the queue.
3432  * @param items {Array<*>} The items to add.
3433  * @return {void}
3434  */
3435 Queue.prototype.multiEnqueue = function (items) {
3436 	for (var i = 0; i < items.length; i++)
3437 		this.items.push(items[i]);
3438 };
3439 
3440 /**
3441  * Removes the item at the head of the queue.
3442  * @return {*} The item at the head of the queue. It's undefined if the queue is empty.
3443  */
3444 Queue.prototype.dequeue = function () {
3445 	if (!this.items.length)
3446 		return undefined;
3447 	return this.items.splice(0, 1)[0]; //remove the first item and return it
3448 };
3449 
3450 /**
3451  * Removes the items at the head of the queue.
3452  * @param times {number} The number of times to repeat the dequeue method.
3453  * @return {Array<*>} The items at the head of the queue.
3454  */
3455 Queue.prototype.multiDequeue = function (times) {
3456 	return this.items.splice(0, times); //removes the last times item and returns the array
3457 };
3458 
3459 /**
3460  * Removes the first length items from the position index.
3461  * @param index {number} The position where to start to remove the items.
3462  * @param [length = 1] {number} The number of items to remove.
3463  * @return {void}
3464  */
3465 Queue.prototype.remove = function (index, length) {
3466 	length = length || 1;
3467 	this.items.splice(index, length);
3468 };
3469 
3470 /**
3471  * Returns the item at the position index.
3472  * @param index {number} The position of the item.
3473  * @return {*} The item at the position. It's undefined if index isn't in the queue bounds.
3474  */
3475 Queue.prototype.getItem = function (index) {
3476 	if (index < 0 || index > this.items.length - 1)
3477 		return undefined;
3478 	return this.items[index];
3479 };
3480 
3481 /**
3482  * Returns the first item in the queue. The item is not removed.
3483  * @return {*} The first item. It's undefined if the queue is empty.
3484  */
3485 Queue.prototype.peek = function () {
3486 	if (this.items.length)
3487 		return this.items[0];
3488 	return undefined
3489 };
3490 
3491 /**
3492  * Removes all the items stored in the queue.
3493  * @return {void}
3494  */
3495 Queue.prototype.clear = function () {
3496 	this.items = [];
3497 };
3498 
3499 /**
3500  * Checks if the queue contains an item that satisfy the condition represented by the callback function.
3501  * @param item {*} The item to find.
3502  * @param [callback = function(item){return(it===item);}] The condition to satisfy. The callback must accept the current item to check.
3503  * @return {boolean} True if the queue contains the item that satisfy the condition, false otherwise.
3504  */
3505 Queue.prototype.contains = function (item, callback) {
3506 	callback = callback || function (it) {
3507 		return it === item;
3508 	};
3509 	var i = 0;
3510 	while (i < this.items.length && !callback(this.items[i]))
3511 		i++;
3512 	return i < this.items.length;
3513 };
3514 
3515 /**
3516  * Executes the callback function for each item of the queue.
3517  * This method modifies the queue so if you don't need to modify it you must return the same item of the array.
3518  * @param callback {function} The function to execute for each item. The function must accept the current item on which execute the function.
3519  * @return {void}
3520  */
3521 Queue.prototype.execute = function (callback) {
3522 	for (var i = 0; i < this.items.length; i++)
3523 		this.items[i] = callback(this.items[i]);
3524 };
3525 
3526 /**
3527  * Returns the length of the queue.
3528  * @return {number} The length of the queue.
3529  */
3530 Queue.prototype.getLength = function () {
3531 	return this.items.length;
3532 };
3533 
3534 /**
3535  * Checks if the queue is empty.
3536  * @return {boolean} True if the queue is empty, false otherwise.
3537  */
3538 Queue.prototype.isEmpty = function () {
3539 	return !this.items.length;
3540 };
3541 
3542 /**
3543  * Returns the items that satisfy the condition determined by the callback.
3544  * @param callback {function} The function that implements the condition.
3545  * @return {Array<*>} The array that contains the items that satisfy the condition.
3546  */
3547 Queue.prototype.filter = function (callback) {
3548 	var result = [];
3549 	for (var i = 0; i < this.items.length; i++)
3550 		if (callback(this.items[i]))
3551 			result.push(this.items[i]);
3552 	return result;
3553 };
3554 
3555 /**
3556  * Returns the first position of the item in the queue.
3557  * @param item {*} The item to search.
3558  * @param [callback = function(item){return(it===item);}] The condition to satisfy. The callback must accept the current item to check.
3559  * @return {number} The first position of the item.
3560  */
3561 Queue.prototype.indexOf = function (item, callback) {
3562 	callback = callback || function (it) {
3563 		return it === item;
3564 	};
3565 	var i = 0;
3566 	while (i < this.items.length) {
3567 		if (callback(this.items[i]))
3568 			return i;
3569 		i++;
3570 	}
3571 	return -1;
3572 };
3573 
3574 /**
3575  * Returns the last position of the item in the queue.
3576  * @param item {*} The item to search.
3577  * @param [callback = function(item){return(it===item);}] The condition to satisfy. The callback must accept the current item to check.
3578  * @return {number} The last position of the item.
3579  */
3580 Queue.prototype.lastIndexOf = function (item, callback) {
3581 	callback = callback || function (it) {
3582 		return it === item;
3583 	};
3584 	var i = this.items.length - 1;
3585 	while (i > -1) {
3586 		if (callback(this.items[i]))
3587 			return i;
3588 		i--;
3589 	}
3590 	return -1;
3591 };
3592 
3593 /**
3594  * Returns all the position in which the item has been found in the queue.
3595  * @param item {*} The item to search.
3596  * @param [callback = function(item){return(it===item);}] The condition to satisfy. The callback must accept the current item to check.
3597  * @return {Array<number>} The positions in which the item has been found.
3598  */
3599 Queue.prototype.allIndexesOf = function (item, callback) {
3600 	callback = callback || function (it) {
3601 		return it === item;
3602 	};
3603 	var i = 0;
3604 	var indexes = [];
3605 	while (i < this.items.length) {
3606 		if (callback(this.items[i]))
3607 			indexes.push(i);
3608 		i++;
3609 	}
3610 	return indexes;
3611 };
3612 
3613 /**
3614  * Clones the queue into a new queue.
3615  * @return {Queue} The queue cloned from this queue.
3616  */
3617 Queue.prototype.clone = function () {
3618 	var queue = new Queue();
3619 	for (var i = 0; i < this.items.length; i++)
3620 		if (this.items[i].clone)
3621 			queue.enqueue(this.items[i].clone());
3622 		else
3623 			queue.enqueue(this.items[i]);
3624 
3625 	return queue;
3626 };
3627 
3628 /**
3629  * Clones the queue into a new queue without cloning duplicated items.
3630  * @return {Queue} The queue cloned from this queue.
3631  */
3632 Queue.prototype.cloneDistinct = function () {
3633 	var queue = new Queue();
3634 	for (var i = 0; i < this.items.length; i++)
3635 		if (!queue.contains(this.items[i]))
3636 			if (this.items[i].cloneDistinct)
3637 				queue.enqueue(this.items[i].cloneDistinct());
3638 			else if (this.items[i].clone)
3639 				queue.enqueue(this.items[i].clone());
3640 			else
3641 				queue.enqueue(this.items[i]);
3642 	return queue;
3643 };
3644 
3645 /**
3646  * Class that implements the iterator for a linked list.
3647  * @param aggregate {Queue} The aggregate to scan.
3648  * @constructor
3649  */
3650 function QueueIterator(aggregate) {
3651 	/**
3652 	 * The aggregate relates to this iterator.
3653 	 * @type {Queue}
3654 	 */
3655 	this.aggregate = aggregate;
3656 
3657 	/**
3658 	 * The pointer to the position.
3659 	 * @type {number}
3660 	 */
3661 	this.pointer = -1;
3662 }
3663 
3664 /**
3665  * Moves the iterator to the first position of the aggregate.
3666  * @return {void}
3667  */
3668 QueueIterator.prototype.first = function () {
3669 	this.pointer = 0;
3670 };
3671 
3672 /**
3673  * Moves the iterator to the next item.
3674  * @return {void}
3675  */
3676 QueueIterator.prototype.next = function () {
3677 	this.pointer++;
3678 };
3679 
3680 /**
3681  * Moves the iterator to the last position of the aggregate.
3682  * @return {void}
3683  */
3684 QueueIterator.prototype.last = function () {
3685 	this.pointer = this.aggregate.items.length - 1;
3686 };
3687 
3688 /**
3689  * Moves the iterator to the previous item.
3690  * @return {void}
3691  */
3692 QueueIterator.prototype.previous = function () {
3693 	this.pointer--;
3694 };
3695 
3696 /**
3697  * Checks if the iterator is out of the bounds of the aggregate.
3698  * @return {boolean} It return true if the iterator is out of the bounds of the aggregate, otherwise false.
3699  */
3700 QueueIterator.prototype.isDone = function () {
3701 	return this.pointer < 0 || this.pointer > this.aggregate.items.length - 1;
3702 };
3703 
3704 /**
3705  * Returns the item stored at the position pointed by the iterator.
3706  * @return {*} The item stored or undefined if it's out of the bounds.
3707  */
3708 QueueIterator.prototype.getItem = function () {
3709 	return this.aggregate.getItem(this.pointer);
3710 };
3711 
3712 /**
3713  * Class for managing a red-black tree.
3714  * @constructor
3715  */
3716 function RBTree() {
3717 	/**
3718 	 * The root of the tree.
3719 	 * @type {RBNode|null}
3720 	 */
3721 	this.root = null;
3722 	/**
3723 	 * The number of items stored in the tree.
3724 	 * @type {number}
3725 	 */
3726 	this.size = 0;
3727 }
3728 
3729 /**
3730  * Returns the iterator relative to the aggregate.
3731  * @return {Iterator} The iterator.
3732  */
3733 RBTree.prototype.getIterator = function () {
3734 	return new RBTreeIterator(this);
3735 };
3736 
3737 /**
3738  * Inserts the item relatives to the key value in the tree.
3739  * @param key {number} The key to store.
3740  * @param item {*} The item to store.
3741  * @return {void}
3742  */
3743 RBTree.prototype.insert = function (key, item) {
3744 	var node = new RBNode(key, item);
3745 	this.size++;
3746 	if (!this.root) {
3747 		this.root = node;
3748 		node.type = 'b';
3749 		return;
3750 	}
3751 	var p = this.root;
3752 	for (var n = this.root; n;) {
3753 		p = n;
3754 		if (key < n.key)
3755 			n = n.left;
3756 		else
3757 			n = n.right;
3758 	}
3759 	node.parent = p;
3760 	if (!p)
3761 		this.root = node;
3762 	else if (key < p.key)
3763 		p.left = node;
3764 	else
3765 		p.right = node;
3766 
3767 	this.insertFixUp(node);
3768 };
3769 
3770 /**
3771  * Preserves the properties of the tree after an insert.
3772  * @param node {RBNode} The node to insert.
3773  * @return {void}
3774  */
3775 RBTree.prototype.insertFixUp = function (node) {
3776 	for (var parent = node.parent; parent && parent.type === 'r'; parent = node.parent) {
3777 		if (parent === parent.parent.left) {
3778 			var uncle = parent.parent.right;
3779 			if (uncle && uncle.type === 'r') {
3780 				parent.type = 'b';
3781 				uncle.type = 'b';
3782 				parent.parent.type = 'r';
3783 				node = parent.parent;
3784 			} else if (node === parent.right) {
3785 				node = parent;
3786 				this.leftRotate(node);
3787 			} else {
3788 				parent.type = 'b';
3789 				parent.parent.type = 'r';
3790 				this.rightRotate(parent.parent);
3791 			}
3792 		} else {
3793 			var uncle = parent.parent.left;
3794 			if (uncle && uncle.type === 'r') {
3795 				parent.type = 'b';
3796 				uncle.type = 'b';
3797 				parent.parent.type = 'r';
3798 				node = parent.parent;
3799 			} else if (node === parent.left) {
3800 				node = parent;
3801 				this.rightRotate(node);
3802 			} else {
3803 				parent.type = 'b';
3804 				parent.parent.type = 'r';
3805 				this.leftRotate(parent.parent);
3806 			}
3807 		}
3808 	}
3809 	this.root.type = 'b';
3810 };
3811 
3812 /**
3813  * Deletes the node from the tree.
3814  * @param node {RBNode} The node to delete.
3815  * @return {void}
3816  */
3817 RBTree.prototype.deleteNode = function (node) {
3818 	var successor;
3819 	this.size--;
3820 	if (!node.left || !node.right)
3821 		successor = node;
3822 	else {
3823 		successor = this.successor(node);
3824 		node.key = successor.key;
3825 		node.item = successor.item;
3826 	}
3827 	var child;
3828 	if (!successor.left)
3829 		child = successor.right;
3830 	else
3831 		child = successor.left;
3832 	if (child)
3833 		child.parent = successor.parent;
3834 	if (!successor.parent)
3835 		this.root = child;
3836 	else if (successor === successor.parent.left)
3837 		successor.parent.left = child;
3838 	else
3839 		successor.parent.right = child;
3840 
3841 	if (successor.type === 'b')
3842 		this.deleteFixUp(child, successor.parent);
3843 };
3844 
3845 /**
3846  * Preserves the properties of the tree after a deletion.
3847  * @param node {RBNode} The node to delete.
3848  * @param parent {RBNode} The parent of the node.
3849  * @return {void}
3850  */
3851 RBTree.prototype.deleteFixUp = function (node, parent) {
3852 	while (node !== this.root && (!node || node.type === 'b')) {
3853 		if (node === parent.left) {
3854 			var brother = parent.right;
3855 			if (brother && brother.type === 'r') {
3856 				brother.type = 'b';
3857 				parent.type = 'r';
3858 				this.leftRotate(parent);
3859 				brother = parent.right;
3860 			}
3861 			if (brother && (!brother.left || brother.left.type === 'b') && (!brother.right || brother.right.type === 'b')) {
3862 				brother.type = 'r';
3863 				node = parent;
3864 			} else {
3865 				if (!brother.right || brother.right.type === 'b') {
3866 					brother.left.type = 'b';
3867 					brother.type = 'r';
3868 					this.rightRotate(brother);
3869 					brother = parent.right;
3870 				}
3871 				brother.type = parent.type;
3872 				parent.type = 'b';
3873 				brother.right.type = 'b';
3874 				this.leftRotate(parent);
3875 				node = this.root;
3876 			}
3877 		} else {
3878 			var brother = parent.left;
3879 			if (brother && brother.type === 'r') {
3880 				brother.type = 'b';
3881 				parent.type = 'r';
3882 				this.rightRotate(parent);
3883 				brother = parent.left;
3884 			}
3885 			if (brother && (!brother.left || brother.left.type === 'b') && (!brother.right || brother.right.type === 'b')) {
3886 				brother.type = 'r';
3887 				node = parent;
3888 			} else {
3889 				if (!brother.left || brother.left.type === 'b') {
3890 					brother.right.type = 'b';
3891 					brother.type = 'r';
3892 					this.leftRotate(brother);
3893 					brother = parent.left;
3894 				}
3895 				brother.type = parent.type;
3896 				parent.type = 'b';
3897 				brother.left.type = 'b';
3898 				this.rightRotate(parent);
3899 				node = this.root;
3900 			}
3901 		}
3902 		parent = node.parent;
3903 	}
3904 	if (node)
3905 		node.type = 'b';
3906 };
3907 
3908 /**
3909  * Gets the node with the key next to the param node key.
3910  * @param node {RBNode} The node of which search the successor.
3911  * @return {RBNode} The node found.
3912  */
3913 RBTree.prototype.successor = function (node) {
3914 	if (node.right)
3915 		return this.minimum(node.right);
3916 	var parent = node.parent;
3917 	while (parent && node === parent.right) {
3918 		node = parent;
3919 		parent = parent.parent;
3920 	}
3921 	return parent;
3922 };
3923 
3924 /**
3925  * Gets the node with the key previous to the param node key.
3926  * @param node {RBNode} The node of which search the predecessor.
3927  * @return {RBNode} The node found.
3928  */
3929 RBTree.prototype.predecessor = function (node) {
3930 	if (node.left)
3931 		return this.maximum(node.left);
3932 	var parent = node.parent;
3933 	while (parent && node === parent.left) {
3934 		node = parent;
3935 		parent = parent.parent;
3936 	}
3937 	return parent;
3938 };
3939 
3940 /**
3941  * Searches the item relatives to the key and to the nodes that satisfy the condition represented by the callback function.
3942  * @param key {number} The key to find.
3943  * @param [node = root] {RBNode} The node from which start the search.
3944  * @param [callback = function(node){return(node.key===key);}] The condition to satisfy. The callback must accept the current node to check.
3945  * @return {*} The item found or undefined if there isn't the key in the tree.
3946  */
3947 RBTree.prototype.search = function (key, node, callback) {
3948 	node = node || this.root;
3949 	callback = callback || function (node) {
3950 		return node.key === key;
3951 	};
3952 	while (node && !callback(node))
3953 		if (key < node.key)
3954 			node = node.left;
3955 		else
3956 			node = node.right;
3957 	if (node)
3958 		return node.item;
3959 	return undefined;
3960 };
3961 
3962 /**
3963  * Checks if the tree contains a key or a node that satisfy the condition represented by the callback function.
3964  * This method avoid to search in branches where the key won't be found.
3965  * @param key {*} The key to find.
3966  * @param [callback = function(node){return(node.key===key);}] The condition to satisfy. The callback must accept the current node to check.
3967  * @return {boolean} True if the tree contains the key or a node that satisfy the condition, false otherwise.
3968  */
3969 RBTree.prototype.contains = function (key, callback) {
3970 	return this.search(key, null, callback) !== undefined;
3971 };
3972 
3973 /**
3974  * Checks if the tree contains a node that satisfy the condition represented by the callback function.
3975  * This method check all the tree avoiding the binary search.
3976  * @param callback {function} The condition to satisfy. The callback must accept the current node to check.
3977  * @return {boolean} True if the tree contains the node that satisfy the condition, false otherwise.
3978  */
3979 RBTree.prototype.fullContains = function (callback) {
3980 	var node = this.minimum();
3981 	while (node && !callback(node.key))
3982 		node = this.successor(node);
3983 	return node !== null;
3984 };
3985 
3986 /**
3987  * Gets the item relatives to the minimum key stored in the tree.
3988  * @param [node = root] {Node} The node from which start the search.
3989  * @return {RBNode} The node found.
3990  */
3991 RBTree.prototype.minimum = function (node) {
3992 	node = node || this.root;
3993 	while (node && node.left)
3994 		node = node.left;
3995 	return node;
3996 };
3997 
3998 /**
3999  * Gets the item relatives to the maximum key stored in the tree.
4000  * @param [node = root] {Node} The node from which start the search.
4001  * @return {RBNode} The node found.
4002  */
4003 RBTree.prototype.maximum = function (node) {
4004 	node = node || this.root;
4005 	while (node && node.right)
4006 		node = node.right;
4007 	return node;
4008 };
4009 
4010 /**
4011  * Rotates the node with its right child.
4012  * @param node {RBNode} The node to rotate.
4013  * @return {void}
4014  */
4015 RBTree.prototype.leftRotate = function (node) {
4016 	var child = node.right;
4017 	node.right = child.left;
4018 	if (child.left !== null)
4019 		child.left.parent = node;
4020 	child.parent = node.parent;
4021 	if (node.parent === null)
4022 		this.root = child;
4023 	else if (node === node.parent.left)
4024 		node.parent.left = child;
4025 	else
4026 		node.parent.right = child;
4027 	node.parent = child;
4028 	child.left = node;
4029 };
4030 
4031 /**
4032  * Rotates the node with its left child.
4033  * @param node {RBNode} The node to rotate.
4034  * @return {void}
4035  */
4036 RBTree.prototype.rightRotate = function (node) {
4037 	var child = node.left;
4038 	node.left = child.right;
4039 	if (child.right !== null)
4040 		child.right.parent = node;
4041 	child.parent = node.parent;
4042 	if (node.parent === null)
4043 		this.root = child;
4044 	else if (node === node.parent.left)
4045 		node.parent.left = child;
4046 	else
4047 		node.parent.right = child;
4048 	node.parent = child;
4049 	child.right = node;
4050 };
4051 
4052 /**
4053  * Returns the size of the tree.
4054  * @return {number} The size of the tree.
4055  */
4056 RBTree.prototype.getSize = function () {
4057 	return this.size;
4058 };
4059 
4060 /**
4061  * Clones the queue into a new queue.
4062  * @return {RBTree} The tree cloned from this queue.
4063  */
4064 RBTree.prototype.clone = function () {
4065 	var tree = new RBTree();
4066 	var it = this.getIterator();
4067 	for (it.first(); !it.isDone(); it.next())
4068 		if (it.getNode().item.clone)
4069 			tree.insert(it.getNode().key, it.getNode().item.clone());
4070 		else
4071 			tree.insert(it.getNode().key, it.getNode().item);
4072 
4073 	return tree;
4074 };
4075 
4076 /**
4077  * Clones the tree into a new tree without cloning duplicated items.
4078  * @return {RBTree} The tree cloned from this tree.
4079  */
4080 RBTree.prototype.cloneDistinct = function () {
4081 	var tree = new RBTree();
4082 	var it = this.getIterator();
4083 	for (it.first(); !it.isDone(); it.next()) {
4084 		var callback = function (node) {
4085 			return node.key === it.getNode().key && node.item === it.getNode().item;
4086 		};
4087 		if (!tree.contains(it.getNode().key, callback)) {
4088 			if (it.getNode().item.cloneDistinct)
4089 				tree.insert(it.getNode().key, it.getNode().item.cloneDistinct());
4090 			else if (it.getNode().item.clone)
4091 				tree.insert(it.getNode().key, it.getNode().item.clone());
4092 			else
4093 				tree.insert(it.getNode().key, it.getNode().item);
4094 		}
4095 	}
4096 	return tree;
4097 };
4098 
4099 /**
4100  * Transforms the tree into an array without preserving keys.
4101  * @return {Array<*>} The array that represents the tree.
4102  */
4103 RBTree.prototype.toArray = function () {
4104 	var result = [];
4105 	for (var node = this.minimum(); node; node = this.successor(node))
4106 		result.push(node.item);
4107 	return result;
4108 };
4109 
4110 /**
4111  * Removes all the items stored in the tree.
4112  * @return {void}
4113  */
4114 RBTree.prototype.clear = function () {
4115 	this.root = null;
4116 	this.size = 0;
4117 };
4118 
4119 /**
4120  * Checks if the tree is empty.
4121  * @return {boolean} True if the tree is empty, false otherwise.
4122  */
4123 RBTree.prototype.isEmpty = function () {
4124 	return !this.size;
4125 };
4126 
4127 /**
4128  * Executes the callback function for each item of the tree.
4129  * This method modifies the tree so if you don't need to modify it you must return the same item stored.
4130  * @param callback {function} The function to execute for each item. The function must accept the current item on which execute the function.
4131  * @return {void}
4132  */
4133 RBTree.prototype.execute = function (callback) {
4134 	for (var node = this.minimum(); node; node = this.successor(node))
4135 		node.item = callback(node.item);
4136 };
4137 
4138 /**
4139  * Returns the items that satisfy the condition determined by the callback.
4140  * @param callback {function} The function that implements the condition.
4141  * @return {Array<*>} The array that contains the items that satisfy the condition.
4142  */
4143 RBTree.prototype.filter = function (callback) {
4144 	var result = [];
4145 	for (var node = this.minimum(); node; node = this.successor(node))
4146 		if (callback(node.item))
4147 			result.push(node.item);
4148 	return result;
4149 };
4150 
4151 /**
4152  * Returns the first position of the item in the tree.
4153  * @param item {*} The item to search.
4154  * @param [callback = function(item){return(it===item);}] The condition to satisfy. The callback must accept the current item to check.
4155  * @return {number} The first position of the item.
4156  */
4157 RBTree.prototype.indexOf = function (item, callback) {
4158 	callback = callback || function (it) {
4159 		return it === item;
4160 	};
4161 	var i = 0, node = this.minimum();
4162 	while (node) {
4163 		if (callback(node.item))
4164 			return i;
4165 		node = this.successor(node);
4166 		i++;
4167 	}
4168 	return -1;
4169 };
4170 
4171 /**
4172  * Returns the last position of the item in the tree.
4173  * @param item {*} The item to search.
4174  * @param [callback = function(item){return(it===item);}] The condition to satisfy. The callback must accept the current item to check.
4175  * @return {number} The last position of the item.
4176  */
4177 RBTree.prototype.lastIndexOf = function (item, callback) {
4178 	callback = callback || function (it) {
4179 		return it === item;
4180 	};
4181 	var i = this.size - 1, node = this.maximum();
4182 	while (node) {
4183 		if (callback(node.item))
4184 			return i;
4185 		i--;
4186 		node = this.predecessor(node);
4187 	}
4188 	return -1;
4189 };
4190 
4191 /**
4192  * Returns all the position in which the item has been found in the tree.
4193  * @param item {*} The item to search.
4194  * @param [callback = function(item){return(it===item);}] The condition to satisfy. The callback must accept the current item to check.
4195  * @return {Array<number>} The positions in which the item has been found.
4196  */
4197 RBTree.prototype.allIndexesOf = function (item, callback) {
4198 	callback = callback || function (it) {
4199 		return it === item;
4200 	};
4201 	var i = 0, node = this.minimum();
4202 	var indexes = [];
4203 	while (node) {
4204 		if (callback(node.item))
4205 			indexes.push(i);
4206 		i++;
4207 		node = this.successor(node);
4208 	}
4209 	return indexes;
4210 };
4211 
4212 /**
4213  * Returns the item at the position index.
4214  * @param index {number} The position of the item.
4215  * @return {*} The item at the position. It's undefined if index isn't in the tree bounds.
4216  */
4217 RBTree.prototype.getItem = function (index) {
4218 	if (index < 0 || index > this.size - 1)
4219 		return undefined;
4220 	for (var node = this.minimum(), i = 0; i < index; node = this.successor(node))
4221 		i++;
4222 	return node.item;
4223 };
4224 
4225 /**
4226  * Class that implements the iterator for a red-black tree.
4227  * @param aggregate {RBTree} The aggregate to scan.
4228  * @constructor
4229  */
4230 function RBTreeIterator(aggregate) {
4231 	/**
4232 	 * The aggregate relates to this iterator.
4233 	 * @type {RBTree}
4234 	 */
4235 	this.aggregate = aggregate;
4236 
4237 	/**
4238 	 * The pointer to the position.
4239 	 * @type {RBNode|null}
4240 	 */
4241 	this.pointer = null;
4242 }
4243 
4244 /**
4245  * Moves the iterator to the first position of the aggregate.
4246  * @return {void}
4247  */
4248 RBTreeIterator.prototype.first = function () {
4249 	this.pointer = this.aggregate.minimum();
4250 };
4251 
4252 /**
4253  * Moves the iterator to the next item.
4254  * @return {void}
4255  */
4256 RBTreeIterator.prototype.next = function () {
4257 	this.pointer = this.aggregate.successor(this.pointer);
4258 };
4259 
4260 /**
4261  * Moves the iterator to the last position of the aggregate.
4262  * @return {void}
4263  */
4264 RBTreeIterator.prototype.last = function () {
4265 	this.pointer = this.aggregate.maximum();
4266 };
4267 
4268 /**
4269  * Moves the iterator to the previous item.
4270  * @return {void}
4271  */
4272 RBTreeIterator.prototype.previous = function () {
4273 	this.pointer = this.aggregate.predecessor(this.pointer);
4274 };
4275 
4276 /**
4277  * Checks if the iterator is out of the bounds of the aggregate.
4278  * @return {boolean} It return true if the iterator is out of the bounds of the aggregate, otherwise false.
4279  */
4280 RBTreeIterator.prototype.isDone = function () {
4281 	return !this.pointer;
4282 };
4283 
4284 /**
4285  * Returns the item stored at the position pointed by the iterator.
4286  * @return {Object|undefined} The item stored or undefined if it's out of the bounds.
4287  */
4288 RBTreeIterator.prototype.getItem = function () {
4289 	return this.pointer.item;
4290 };
4291 
4292 /**
4293  * Returns the node stored at the position pointed by the iterator.
4294  * @return {RBNode|null} The node stored or null if it's out of the bounds.
4295  */
4296 RBTreeIterator.prototype.getNode = function () {
4297 	return this.pointer;
4298 };
4299 
4300 /**
4301  * Class for managing a red-black tree where nodes are also in a list.
4302  * @constructor
4303  */
4304 function RBTreeList() {
4305 	/**
4306 	 * The root of the tree.
4307 	 * @type {RBLNode|null}
4308 	 */
4309 	this.root = null;
4310 	/**
4311 	 * The first node of the tree.
4312 	 * @type {RBLNode|null}
4313 	 */
4314 	this.first = null;
4315 	/**
4316 	 * The last node of the tree.
4317 	 * @type {RBLNode|null}
4318 	 */
4319 	this.last = null;
4320 	/**
4321 	 * The size of the tree.
4322 	 * @type {number}
4323 	 */
4324 	this.size = 0;
4325 }
4326 
4327 /**
4328  * Returns the iterator relative to the aggregate.
4329  * @return {Iterator} The iterator.
4330  */
4331 RBTreeList.prototype.getIterator = function () {
4332 	return new RBTreeListIterator(this);
4333 };
4334 
4335 /**
4336  * Inserts the item relatives to the key value in the tree.
4337  * @param key {number} The key to store.
4338  * @param item {*} The item to store.
4339  * @return {void}
4340  */
4341 RBTreeList.prototype.insert = function (key, item) {
4342 	var node = new RBLNode(key, item);
4343 	this.size++;
4344 	if (!this.root) {
4345 		this.root = node;
4346 		this.first = node;
4347 		this.last = node;
4348 		node.type = 'b';
4349 		return;
4350 	}
4351 	var p = this.root;
4352 	for (var n = this.root; n;) {
4353 		p = n;
4354 		if (key < n.key)
4355 			n = n.left;
4356 		else
4357 			n = n.right;
4358 	}
4359 	node.parent = p;
4360 	if (!p)
4361 		this.root = node;
4362 	else if (key < p.key)
4363 		p.left = node;
4364 	else
4365 		p.right = node;
4366 
4367 	node.next = this.successor(node);
4368 	if (node.next) {
4369 		if (node.next.previous)
4370 			node.next.previous.next = node;
4371 		else
4372 			this.first = node;
4373 		node.previous = node.next.previous;
4374 		node.next.previous = node;
4375 	} else {
4376 		this.last = node;
4377 		node.previous = this.predecessor(node);
4378 		if (node.previous)
4379 			node.previous.next = node;
4380 		else
4381 			this.first = node;
4382 	}
4383 
4384 	this.insertFixUp(node);
4385 };
4386 
4387 /**
4388  * Preserves the properties of the tree after an insert.
4389  * @param node {RBLNode} The node to insert.
4390  * @return {void}
4391  */
4392 RBTreeList.prototype.insertFixUp = function (node) {
4393 	for (var parent = node.parent; parent && parent.type === 'r'; parent = node.parent) {
4394 		if (parent === parent.parent.left) {
4395 			var uncle = parent.parent.right;
4396 			if (uncle && uncle.type === 'r') {
4397 				parent.type = 'b';
4398 				uncle.type = 'b';
4399 				parent.parent.type = 'r';
4400 				node = parent.parent;
4401 			} else if (node === parent.right) {
4402 				node = parent;
4403 				this.leftRotate(node);
4404 			} else {
4405 				parent.type = 'b';
4406 				parent.parent.type = 'r';
4407 				this.rightRotate(parent.parent);
4408 			}
4409 		} else {
4410 			var uncle = parent.parent.left;
4411 			if (uncle && uncle.type === 'r') {
4412 				parent.type = 'b';
4413 				uncle.type = 'b';
4414 				parent.parent.type = 'r';
4415 				node = parent.parent;
4416 			} else if (node === parent.left) {
4417 				node = parent;
4418 				this.rightRotate(node);
4419 			} else {
4420 				parent.type = 'b';
4421 				parent.parent.type = 'r';
4422 				this.leftRotate(parent.parent);
4423 			}
4424 		}
4425 	}
4426 	this.root.type = 'b';
4427 };
4428 
4429 /**
4430  * Deletes the node from the tree.
4431  * @param node {RBLNode} The node to delete.
4432  * @return {void}
4433  */
4434 RBTreeList.prototype.deleteNode = function (node) {
4435 	this.size--;
4436 	var successor;
4437 	if (!node.left || !node.right)
4438 		successor = node;
4439 	else {
4440 		successor = this.successor(node);
4441 		node.key = successor.key;
4442 		node.item = successor.item;
4443 	}
4444 	var child;
4445 	if (!successor.left)
4446 		child = successor.right;
4447 	else
4448 		child = successor.left;
4449 	if (child)
4450 		child.parent = successor.parent;
4451 	if (!successor.parent)
4452 		this.root = child;
4453 	else if (successor === successor.parent.left)
4454 		successor.parent.left = child;
4455 	else
4456 		successor.parent.right = child;
4457 
4458 	if (successor.next)
4459 		successor.next.previous = successor.previous;
4460 	else
4461 		this.last = successor.previous;
4462 	if (successor.previous)
4463 		successor.previous.next = successor.next;
4464 	else
4465 		this.first = successor.next;
4466 
4467 	if (successor.type === 'b')
4468 		this.deleteFixUp(child, successor.parent);
4469 };
4470 
4471 /**
4472  * Preserves the properties of the tree after a deletion.
4473  * @param node {RBLNode} The node to delete.
4474  * @param parent {RBLNode} The parent of the node.
4475  * @return {void}
4476  */
4477 RBTreeList.prototype.deleteFixUp = function (node, parent) {
4478 	while (node !== this.root && (!node || node.type === 'b')) {
4479 		if (node === parent.left) {
4480 			var brother = parent.right;
4481 			if (brother && brother.type === 'r') {
4482 				brother.type = 'b';
4483 				parent.type = 'r';
4484 				this.leftRotate(parent);
4485 				brother = parent.right;
4486 			}
4487 			if (brother && (!brother.left || brother.left.type === 'b') && (!brother.right || brother.right.type === 'b')) {
4488 				brother.type = 'r';
4489 				node = parent;
4490 			} else {
4491 				if (!brother.right || brother.right.type === 'b') {
4492 					brother.left.type = 'b';
4493 					brother.type = 'r';
4494 					this.rightRotate(brother);
4495 					brother = parent.right;
4496 				}
4497 				brother.type = parent.type;
4498 				parent.type = 'b';
4499 				brother.right.type = 'b';
4500 				this.leftRotate(parent);
4501 				node = this.root;
4502 			}
4503 		} else {
4504 			var brother = parent.left;
4505 			if (brother && brother.type === 'r') {
4506 				brother.type = 'b';
4507 				parent.type = 'r';
4508 				this.rightRotate(parent);
4509 				brother = parent.left;
4510 			}
4511 			if (brother && (!brother.left || brother.left.type === 'b') && (!brother.right || brother.right.type === 'b')) {
4512 				brother.type = 'r';
4513 				node = parent;
4514 			} else {
4515 				if (!brother.left || brother.left.type === 'b') {
4516 					brother.right.type = 'b';
4517 					brother.type = 'r';
4518 					this.leftRotate(brother);
4519 					brother = parent.left;
4520 				}
4521 				brother.type = parent.type;
4522 				parent.type = 'b';
4523 				brother.left.type = 'b';
4524 				this.rightRotate(parent);
4525 				node = this.root;
4526 			}
4527 		}
4528 		parent = node.parent;
4529 	}
4530 	if (node)
4531 		node.type = 'b';
4532 };
4533 
4534 /**
4535  * Gets the node with the key next to the param node key.
4536  * @param node {RBLNode} The node of which search the successor.
4537  * @return {RBLNode} The node found.
4538  */
4539 RBTreeList.prototype.successor = function (node) {
4540 	if (node.next || node === this.last)
4541 		return node.next;
4542 	if (node.right)
4543 		return this.minimum(node.right);
4544 	var parent = node.parent;
4545 	while (parent && node === parent.right) {
4546 		node = parent;
4547 		parent = parent.parent;
4548 	}
4549 	return parent;
4550 };
4551 
4552 /**
4553  * Gets the node with the key previous to the param node key.
4554  * @param node {RBLNode} The node of which search the predecessor.
4555  * @return {RBLNode} The node found.
4556  */
4557 RBTreeList.prototype.predecessor = function (node) {
4558 	if (node.previous || node === this.first)
4559 		return node.previous;
4560 	if (node.left)
4561 		return this.maximum(node.left);
4562 	var parent = node.parent;
4563 	while (parent && node === parent.left) {
4564 		node = parent;
4565 		parent = parent.parent;
4566 	}
4567 	return parent;
4568 };
4569 
4570 /**
4571  * Searches the item relatives to the key that satisfy the condition represented by the callback function.
4572  * @param key {number} The key to find.
4573  * @param [node = root] {RBNode} The node from which start the search.
4574  * @param [callback = function(k){return(k===key);}] The condition to satisfy. The callback must accept the current key to check.
4575  * @return {*} The item found or undefined if there isn't the key in the tree.
4576  */
4577 RBTreeList.prototype.search = function (key, node, callback) {
4578 	node = node || this.root;
4579 	callback = callback || function (node) {
4580 		return node.key === key;
4581 	};
4582 	while (node && !callback(node))
4583 		if (key < node.key)
4584 			node = node.left;
4585 		else
4586 			node = node.right;
4587 	if (node)
4588 		return node.item;
4589 	return undefined;
4590 };
4591 
4592 /**
4593  * Checks if the tree contains a key or a node that satisfy the condition represented by the callback function.
4594  * This method avoid to search in branches where the key won't be found.
4595  * @param key {*} The key to find.
4596  * @param [callback = function(node){return(node.key===key);}] The condition to satisfy. The callback must accept the current node to check.
4597  * @return {boolean} True if the tree contains the key or a node that satisfy the condition, false otherwise.
4598  */
4599 RBTreeList.prototype.contains = function (key, callback) {
4600 	return this.search(key, null, callback) !== undefined;
4601 };
4602 
4603 /**
4604  * Checks if the tree contains a node that satisfy the condition represented by the callback function.
4605  * This method check all the tree avoiding the binary search.
4606  * @param callback {function} The condition to satisfy. The callback must accept the current node to check.
4607  * @return {boolean} True if the tree contains the node that satisfy the condition, false otherwise.
4608  */
4609 RBTreeList.prototype.fullContains = function (callback) {
4610 	var node = this.first;
4611 	while (node && !callback(node.key))
4612 		node = node.next;
4613 	return node !== null;
4614 };
4615 
4616 /**
4617  * Gets the item relatives to the minimum key stored in the tree.
4618  * @param [node = root] {Node} The node from which start the search.
4619  * @return {RBLNode} The node found.
4620  */
4621 RBTreeList.prototype.minimum = function (node) {
4622 	if (node)
4623 		while (node && node.left)
4624 			node = node.left;
4625 	else
4626 		return this.first;
4627 	return node;
4628 };
4629 
4630 /**
4631  * Gets the item relatives to the maximum key stored in the tree.
4632  * @param [node = root] {Node} The node from which start the search.
4633  * @return {RBLNode} The node found.
4634  */
4635 RBTreeList.prototype.maximum = function (node) {
4636 	if (node)
4637 		while (node && node.right)
4638 			node = node.right;
4639 	else
4640 		return this.last;
4641 	return node;
4642 };
4643 
4644 /**
4645  * Rotates the node with its right child.
4646  * @param node {RBLNode} The node to rotate.
4647  * @return {void}
4648  */
4649 RBTreeList.prototype.leftRotate = function (node) {
4650 	var child = node.right;
4651 	node.right = child.left;
4652 	if (child.left !== null)
4653 		child.left.parent = node;
4654 	child.parent = node.parent;
4655 	if (node.parent === null)
4656 		this.root = child;
4657 	else if (node === node.parent.left)
4658 		node.parent.left = child;
4659 	else
4660 		node.parent.right = child;
4661 	node.parent = child;
4662 	child.left = node;
4663 };
4664 
4665 /**
4666  * Rotates the node with its left child.
4667  * @param node {RBLNode} The node to rotate.
4668  * @return {void}
4669  */
4670 RBTreeList.prototype.rightRotate = function (node) {
4671 	var child = node.left;
4672 	node.left = child.right;
4673 	if (child.right !== null)
4674 		child.right.parent = node;
4675 	child.parent = node.parent;
4676 	if (node.parent === null)
4677 		this.root = child;
4678 	else if (node === node.parent.left)
4679 		node.parent.left = child;
4680 	else
4681 		node.parent.right = child;
4682 	node.parent = child;
4683 	child.right = node;
4684 };
4685 
4686 /**
4687  * Returns the size of the tree.
4688  * @return {number} The size of the tree.
4689  */
4690 RBTreeList.prototype.getSize = function () {
4691 	return this.size;
4692 };
4693 
4694 /**
4695  * Clones the tree into a new tree.
4696  * @return {RBTreeList} The tree cloned from this tree.
4697  */
4698 RBTreeList.prototype.clone = function () {
4699 	var tree = new RBTreeList();
4700 	var it = this.getIterator();
4701 	for (it.first(); !it.isDone(); it.next())
4702 		tree.insert(it.getNode().key, it.getNode().item);
4703 	return tree;
4704 };
4705 
4706 /**
4707  * Clones the tree into a new tree without cloning duplicated items.
4708  * @return {RBTreeList} The tree cloned from this tree.
4709  */
4710 RBTreeList.prototype.cloneDistinct = function () {
4711 	var tree = new RBTreeList();
4712 	var it = this.getIterator();
4713 	for (it.first(); !it.isDone(); it.next()) {
4714 		var callback = function (node) {
4715 			return node.key === it.getNode().key && node.item === it.getNode().item;
4716 		};
4717 		if (!tree.contains(it.getNode().key, callback)) {
4718 			if (it.getNode().item.cloneDistinct)
4719 				tree.insert(it.getNode().key, it.getNode().item.cloneDistinct());
4720 			else if (it.getNode().item.clone)
4721 				tree.insert(it.getNode().key, it.getNode().item.clone());
4722 			else
4723 				tree.insert(it.getNode().key, it.getNode().item);
4724 		}
4725 	}
4726 	return tree;
4727 };
4728 
4729 /**
4730  * Transforms the tree into an array without preserving keys.
4731  * @return {Array<*>} The array that represents the tree.
4732  */
4733 RBTreeList.prototype.toArray = function () {
4734 	var result = [];
4735 	for (var node = this.first; node; node = node.next)
4736 		result.push(node.item);
4737 	return result;
4738 };
4739 
4740 /**
4741  * Removes all the items stored in the tree.
4742  * @return {void}
4743  */
4744 RBTreeList.prototype.clear = function () {
4745 	this.root = null;
4746 	this.first = null;
4747 	this.last = null;
4748 	this.size = 0;
4749 };
4750 
4751 /**
4752  * Checks if the tree is empty.
4753  * @return {boolean} True if the tree is empty, false otherwise.
4754  */
4755 RBTreeList.prototype.isEmpty = function () {
4756 	return !this.size;
4757 };
4758 
4759 /**
4760  * Executes the callback function for each item of the tree.
4761  * This method modifies the tree so if you don't need to modify it you must return the same item stored.
4762  * @param callback {function} The function to execute for each item. The function must accept the current item on which execute the function.
4763  * @return {void}
4764  */
4765 RBTreeList.prototype.execute = function (callback) {
4766 	for (var node = this.first; node; node = node.next)
4767 		node.item = callback(node.item);
4768 };
4769 
4770 /**
4771  * Returns the items that satisfy the condition determined by the callback.
4772  * @param callback {function} The function that implements the condition.
4773  * @return {Array<*>} The array that contains the items that satisfy the condition.
4774  */
4775 RBTreeList.prototype.filter = function (callback) {
4776 	var result = [];
4777 	for (var node = this.first; node; node = node.next)
4778 		if (callback(node.item))
4779 			result.push(node.item);
4780 	return result;
4781 };
4782 
4783 /**
4784  * Returns the first position of the item in the tree.
4785  * @param item {*} The item to search.
4786  * @param [callback = function(item){return(it===item);}] The condition to satisfy. The callback must accept the current item to check.
4787  * @return {number} The first position of the item.
4788  */
4789 RBTreeList.prototype.indexOf = function (item, callback) {
4790 	callback = callback || function (it) {
4791 		return it === item;
4792 	};
4793 	var i = 0, node = this.first;
4794 	while (node) {
4795 		if (callback(node.item))
4796 			return i;
4797 		node = node.next;
4798 		i++;
4799 	}
4800 	return -1;
4801 };
4802 
4803 /**
4804  * Returns the last position of the item in the tree.
4805  * @param item {*} The item to search.
4806  * @param [callback = function(item){return(it===item);}] The condition to satisfy. The callback must accept the current item to check.
4807  * @return {number} The last position of the item.
4808  */
4809 RBTreeList.prototype.lastIndexOf = function (item, callback) {
4810 	callback = callback || function (it) {
4811 		return it === item;
4812 	};
4813 	var i = this.size - 1, node = this.last;
4814 	while (node) {
4815 		if (callback(node.item))
4816 			return i;
4817 		i--;
4818 		node = node.previous;
4819 	}
4820 	return -1;
4821 };
4822 
4823 /**
4824  * Returns all the position in which the item has been found in the tree.
4825  * @param item {*} The item to search.
4826  * @param [callback = function(item){return(it===item);}] The condition to satisfy. The callback must accept the current item to check.
4827  * @return {Array<number>} The positions in which the item has been found.
4828  */
4829 RBTreeList.prototype.allIndexesOf = function (item, callback) {
4830 	callback = callback || function (it) {
4831 		return it === item;
4832 	};
4833 	var i = 0, node = this.first;
4834 	var indexes = [];
4835 	while (node) {
4836 		if (callback(node.item))
4837 			indexes.push(i);
4838 		i++;
4839 		node = node.next;
4840 	}
4841 	return indexes;
4842 };
4843 
4844 /**
4845  * Returns the item at the position index.
4846  * @param index {number} The position of the item.
4847  * @return {*} The item at the position. It's undefined if index isn't in the tree bounds.
4848  */
4849 RBTreeList.prototype.getItem = function (index) {
4850 	if (index < 0 || index > this.size - 1)
4851 		return undefined;
4852 	for (var node = this.first, i = 0; i < index; node = node.next)
4853 		i++;
4854 	return node.item;
4855 };
4856 
4857 /**
4858  * Class that implements the iterator for a red-black tree.
4859  * @param aggregate {RBTreeList} The aggregate to scan.
4860  * @constructor
4861  */
4862 function RBTreeListIterator(aggregate) {
4863 	/**
4864 	 * The aggregate relates to this iterator.
4865 	 * @type {RBTreeList}
4866 	 */
4867 	this.aggregate = aggregate;
4868 	/**
4869 	 * The pointer to the position.
4870 	 * @type {RBLNode|null}
4871 	 */
4872 	this.pointer = null;
4873 }
4874 
4875 /**
4876  * Moves the iterator to the first position of the aggregate.
4877  * @return {void}
4878  */
4879 RBTreeListIterator.prototype.first = function () {
4880 	this.pointer = this.aggregate.first;
4881 };
4882 
4883 /**
4884  * Moves the iterator to the next item.
4885  * @return {void}
4886  */
4887 RBTreeListIterator.prototype.next = function () {
4888 	this.pointer = this.pointer.next;
4889 };
4890 
4891 /**
4892  * Moves the iterator to the last position of the aggregate.
4893  * @return {void}
4894  */
4895 RBTreeListIterator.prototype.last = function () {
4896 	this.pointer = this.aggregate.last;
4897 };
4898 
4899 /**
4900  * Moves the iterator to the previous item.
4901  * @return {void}
4902  */
4903 RBTreeListIterator.prototype.previous = function () {
4904 	this.pointer = this.pointer.previous;
4905 };
4906 
4907 /**
4908  * Checks if the iterator is out of the bounds of the aggregate.
4909  * @return {boolean} It return true if the iterator is out of the bounds of the aggregate, otherwise false.
4910  */
4911 RBTreeListIterator.prototype.isDone = function () {
4912 	return !this.pointer;
4913 };
4914 
4915 /**
4916  * Returns the item stored at the position pointed by the iterator.
4917  * @return {*} The item stored or undefined if it's out of the bounds.
4918  */
4919 RBTreeListIterator.prototype.getItem = function () {
4920 	return this.pointer.item;
4921 };
4922 
4923 /**
4924  * Returns the node stored at the position pointed by the iterator.
4925  * @abstract
4926  * @return {RBNode|null} The node stored or null if it's out of the bounds.
4927  */
4928 RBTreeListIterator.prototype.getNode = function () {
4929 	return this.pointer;
4930 };
4931 
4932 /**
4933  * Class for managing a set.
4934  * @constructor
4935  */
4936 function Set() {
4937 	/**
4938 	 * The parents of the set.
4939 	 * @type {DoubleLinkedList}
4940 	 */
4941 	this.parents = new DoubleLinkedList();
4942 	/**
4943 	 * The elements stored.
4944 	 * @type {DoubleLinkedList}
4945 	 */
4946 	this.elements = new DoubleLinkedList();
4947 	/**
4948 	 * The subsets of this set.
4949 	 * @type {DoubleLinkedList}
4950 	 */
4951 	this.sets = new DoubleLinkedList();
4952 	/**
4953 	 * The size of the set. It's equal to his cardinality.
4954 	 * @type {number}
4955 	 */
4956 	this.size = 0;
4957 }
4958 
4959 /**
4960  * Adds the element to the set.
4961  * @param element {Element} The element to add.
4962  * @return {void}
4963  */
4964 Set.prototype.insert = function (element) {
4965 	this.elements.pushBack(element);
4966 	element.parents.pushBack(this);
4967 	this.size++;
4968 };
4969 
4970 /**
4971  * Adds the elements to the set.
4972  * @param elements {Array<Element>} The elements to add.
4973  * @return {void}
4974  */
4975 Set.prototype.multiInsert = function (elements) {
4976 	for (var i = 0; i < elements.length; i++) {
4977 		this.elements.pushBack(elements[i]);
4978 		elements[i].parents.pushBack(this);
4979 	}
4980 	this.size += elements.length;
4981 };
4982 
4983 /**
4984  * Returns the set that represents the union of two sets.
4985  * @param set {Set} The set with make the union.
4986  * @return {Set} The set that represents the union.
4987  */
4988 Set.prototype.union = function (set) {
4989 	var parent = new Set();
4990 	parent.addSubsets([this, set]);
4991 	this.parents.pushBack(parent);
4992 	set.parents.pushBack(parent);
4993 	//change the parent of the subset
4994 	var that = this;
4995 	var f = function (item) {
4996 		if (item === that)
4997 			return parent;
4998 	};
4999 	var it = this.sets.getIterator();
5000 	for (it.first(); !it.isDone(); it.next())
5001 		it.getItem().parents.execute(f);
5002 	f = function (item) {
5003 		if (item === set)
5004 			return parent;
5005 	};
5006 	it = set.sets.getIterator();
5007 	for (it.first(); !it.isDone(); it.next())
5008 		it.getItem().parents.execute(f);
5009 	return parent;
5010 };
5011 
5012 /**
5013  * Returns the set that represents the intersection of two sets.
5014  * @param set {Set} The set to intersect with this.
5015  * @return {Set} The set that represents the intersection.
5016  */
5017 Set.prototype.intersect = function (set) {
5018 	var intersection = new Set();
5019 	//intersect this set with the set
5020 	var el = this.elements.getIterator();
5021 	for (el.first(); !el.isDone(); el.next())
5022 		if (el.getItem().parents.contains(set))
5023 			intersection.insert(el.getItem());
5024 
5025 	//intersect the subsets with the set
5026 	var it = this.sets.getIterator();
5027 	for (it.first(); !it.isDone(); it.next()) {
5028 		el = it.getItem().getIterator();
5029 		for (el.first(); !el.isDone(); el.next())
5030 			if (el.getItem().parents.contains(set))
5031 				intersection.insert(el.getItem());
5032 	}
5033 	return intersection;
5034 };
5035 
5036 /**
5037  * Returns the set that represents the difference of two sets.
5038  * @param set {Set} The set to difference with this.
5039  * @return {Set} The set that represents the difference.
5040  */
5041 Set.prototype.difference = function (set) {
5042 	var diff = new Set();
5043 	//intersect this set with the set
5044 	var el = this.elements.getIterator();
5045 	for (el.first(); !el.isDone(); el.next())
5046 		if (!el.getItem().parents.contains(set))
5047 			diff.insert(el.getItem());
5048 
5049 	//intersect the subsets with the set
5050 	var it = this.sets.getIterator();
5051 	for (it.first(); !it.isDone(); it.next()) {
5052 		el = it.getItem().getIterator();
5053 		for (el.first(); !el.isDone(); el.next())
5054 			if (!el.getItem().parents.contains(set))
5055 				diff.insert(el.getItem());
5056 	}
5057 	return diff;
5058 };
5059 
5060 /**
5061  * Returns the set that represents the cartesian product of two sets.
5062  * @param set {Set} The set to make the cartesian product with this.
5063  * @return {Set} The set that represents the cartesian product .
5064  */
5065 Set.prototype.cartesianProduct = function (set) {
5066 	var el1 = this.getItems();
5067 	var el2 = set.getItems();
5068 	var product = new Set();
5069 	for (var i = 0; i < el1.length; i++)
5070 		for (var j = 0; j < el2.length; j++)
5071 			product.insert(new Element([el1[i], el2[j]]));
5072 	return product;
5073 };
5074 
5075 /**
5076  * Adds the subset.
5077  * @param set {Set} The subset.
5078  */
5079 Set.prototype.addSubset = function (set) {
5080 	this.sets.pushBack(set);
5081 	this.size += set.size;
5082 };
5083 
5084 /**
5085  * Adds the subsets.
5086  * @param sets {Array<Set>} The subsets.
5087  */
5088 Set.prototype.addSubsets = function (sets) {
5089 	for (var i = 0; i < sets.length; i++)
5090 		this.addSubset(sets[i]);
5091 };
5092 
5093 /**
5094  * Returns the items that are stored in the set.
5095  * @return {Array} The items stored.
5096  */
5097 Set.prototype.getItems = function () {
5098 	var array = [];
5099 	//get the items stored in the set
5100 	var el = this.elements.getIterator();
5101 	for (el.first(); !el.isDone(); el.next())
5102 		array.push(el.getItem().item);
5103 
5104 	//get the items stored in the subsets
5105 	var it = this.sets.getIterator();
5106 	for (it.first(); !it.isDone(); it.next()) {
5107 		el = it.getItem().getIterator();
5108 		for (el.first(); !el.isDone(); el.next())
5109 			array.push(el.getItem().item);
5110 	}
5111 	return array;
5112 };
5113 
5114 /**
5115  * Returns the cardinality of the set.
5116  * @return {number} The cardinality of the set.
5117  */
5118 Set.prototype.getCardinality = function () {
5119 	return this.size;
5120 };
5121 
5122 /**
5123  * Checks if the set is empty.
5124  * @return {boolean} True if the set is empty, false otherwise.
5125  */
5126 Set.prototype.isEmpty = function () {
5127 	return !this.size;
5128 };
5129 
5130 /**
5131  * Clones the set into a new set.
5132  * @return {Set} The set cloned from this set.
5133  */
5134 Set.prototype.clone = function () {
5135 	var s = new Set();
5136 	s.parents = this.parents.clone();
5137 	s.elements = this.elements.clone();
5138 	s.sets = this.sets.clone();
5139 	s.size = this.size;
5140 	return s;
5141 };
5142 
5143 /**
5144  * Class for managing a stack.
5145  * @param {...*} [args] The items for initializing the stack.
5146  * @constructor
5147  */
5148 function Stack(args) {
5149 	/**
5150 	 * The list of the items in the stack.
5151 	 * @type {Array<*>}
5152 	 */
5153 	this.items = [];
5154 
5155 	//builds the stack from the parameters of the constructor
5156 	this.multiPush(arguments);
5157 }
5158 
5159 /**
5160  * Returns the iterator relative to the aggregate.
5161  * @return {Iterator} The iterator.
5162  */
5163 Stack.prototype.getIterator = function () {
5164 	return new StackIterator(this);
5165 };
5166 
5167 /**
5168  * Adds the item at the top of the stack.
5169  * @param item {*} The item to add.
5170  * return {void}
5171  */
5172 Stack.prototype.push = function (item) {
5173 	this.items.push(item);
5174 };
5175 
5176 /**
5177  * Adds the items at the top of the stack.
5178  * @param items {Array<*>} The items to add.
5179  * @return {void}
5180  */
5181 Stack.prototype.multiPush = function (items) {
5182 	for (var i = 0; i < items.length; i++)
5183 		this.push(items[i]);
5184 };
5185 
5186 /**
5187  * Removes the item at the top of the stack.
5188  * @return {*} The item at the top of the stack. It's undefined if the stack is empty.
5189  */
5190 Stack.prototype.pop = function () {
5191 	if (!this.items.length)
5192 		return undefined;
5193 	return this.items.pop();
5194 };
5195 
5196 /**
5197  * Removes the more item at the top of the stack.
5198  * @param times {number} The number of times to repeat the pop method.
5199  * @return {Array<*>} The items at the top of the stack.
5200  */
5201 Stack.prototype.multiPop = function (times) {
5202 	var result = [];
5203 	for (var i = 0; i < times && this.items.length; i++)
5204 		result.push(this.pop());
5205 	return result;
5206 };
5207 
5208 /**
5209  * Returns the item at the top of the stack without remove it.
5210  * @return {*} The item at the top of the stack. It's undefined if the stack is empty.
5211  */
5212 Stack.prototype.peek = function () {
5213 	if (!this.items.length)
5214 		return undefined;
5215 	return this.items[this.items.length - 1];
5216 };
5217 
5218 /**
5219  * Removes all the items stored in the stack.
5220  * @return {void}
5221  */
5222 Stack.prototype.clear = function () {
5223 	this.items = [];
5224 };
5225 
5226 /**
5227  * Checks if the stack contains an item that satisfy the condition represented by the callback function.
5228  * @param item {*} The item to find.
5229  * @param [callback = function(item){return(it===item);}] The condition to satisfy. The callback must accept the current item to check.
5230  * @return {boolean} True if the stack contains the item that satisfy the condition, false otherwise.
5231  */
5232 Stack.prototype.contains = function (item, callback) {
5233 	callback = callback || function (it) {
5234 		return it === item;
5235 	};
5236 	var i = 0;
5237 	while (i < this.items.length && !callback(this.items[i]))
5238 		i++;
5239 	return i < this.items.length;
5240 };
5241 
5242 /**
5243  * Executes the callback function for each item of the stack.
5244  * This method modifies the stack so if you don't need to modify it you must return the same item of the array.
5245  * @param callback {function} The function to execute for each item. The function must accept the current item on which execute the function.
5246  * @return {void}
5247  */
5248 Stack.prototype.execute = function (callback) {
5249 	for (var i = this.items.length - 1; i > -1; i--)
5250 		this.items[i] = callback(this.items[i]);
5251 };
5252 
5253 /**
5254  * Returns the item at the position index.
5255  * @param index The position of the item.
5256  * @return {*} The item at the position. It's undefined if index isn't in the stack bounds.
5257  */
5258 Stack.prototype.getItem = function (index) {
5259 	if (index < 0 || index > this.items.length - 1)
5260 		return undefined;
5261 	return this.items[index];
5262 };
5263 
5264 /**
5265  * Returns the length of the stack.
5266  * @return {Number} The length of the stack.
5267  */
5268 Stack.prototype.getLength = function () {
5269 	return this.items.length;
5270 };
5271 
5272 /**
5273  * Checks if the stack is empty.
5274  * @return {boolean} True if the stack is empty, false otherwise.
5275  */
5276 Stack.prototype.isEmpty = function () {
5277 	return !this.items.length;
5278 };
5279 
5280 /**
5281  * Returns the items that satisfy the condition determined by the callback.
5282  * @param callback {function} The function that implements the condition.
5283  * @return {Array<*>} The array that contains the items that satisfy the condition.
5284  */
5285 Stack.prototype.filter = function (callback) {
5286 	var result = [];
5287 	for (var i = this.items.length - 1; i > -1; i--) {
5288 		if (callback(this.items[i]))
5289 			result.push(this.items[i]);
5290 	}
5291 	return result;
5292 };
5293 
5294 /**
5295  * Returns the first position of the item in the stack.
5296  * @param item {*} The item to search.
5297  * @param [callback = function(item){return(it===item);}] The condition to satisfy. The callback must accept the current item to check.
5298  * @return {number} The first position of the item.
5299  */
5300 Stack.prototype.indexOf = function (item, callback) {
5301 	callback = callback || function (it) {
5302 		return it === item;
5303 	};
5304 	var i = this.items.length - 1;
5305 	while (i > -1) {
5306 		if (callback(this.items[i]))
5307 			return i;
5308 		i--;
5309 	}
5310 	return -1;
5311 };
5312 
5313 /**
5314  * Returns the last position of the item in the stack.
5315  * @param item {*} The item to search.
5316  * @param [callback = function(item){return(it===item);}] The condition to satisfy. The callback must accept the current item to check.
5317  * @return {number} The last position of the item.
5318  */
5319 Stack.prototype.lastIndexOf = function (item, callback) {
5320 	callback = callback || function (it) {
5321 		return it === item;
5322 	};
5323 	var i = 0;
5324 	while (i < this.items.length) {
5325 		if (callback(this.items[i]))
5326 			return i;
5327 		i++;
5328 	}
5329 	return -1;
5330 };
5331 
5332 /**
5333  * Returns all the position in which the item has been found in the stack.
5334  * @param item {*} The item to search.
5335  * @param [callback = function(item){return(it===item);}] The condition to satisfy. The callback must accept the current item to check.
5336  * @return {Array<number>} The positions in which the item has been found.
5337  */
5338 Stack.prototype.allIndexesOf = function (item, callback) {
5339 	callback = callback || function (it) {
5340 		return it === item;
5341 	};
5342 	var i = this.items.length - 1;
5343 	var indexes = [];
5344 	while (i > -1) {
5345 		if (callback(this.items[i]))
5346 			indexes.push(i);
5347 		i--;
5348 	}
5349 	return indexes;
5350 };
5351 
5352 /**
5353  * Clones the stack into a new stack.
5354  * @return {Stack} The stack cloned from this stack.
5355  */
5356 Stack.prototype.clone = function () {
5357 	var stack = new Stack();
5358 	for (var i = 0; i < this.items.length; i++)
5359 		if (this.items[i].clone)
5360 			stack.push(this.items[i].clone());
5361 		else
5362 			stack.push(this.items[i]);
5363 	return stack;
5364 };
5365 
5366 /**
5367  * Clones the stack into a new stack without cloning duplicated items.
5368  * @return {Stack} The stack cloned from this stack.
5369  */
5370 Stack.prototype.cloneDistinct = function () {
5371 	var stack = new Stack();
5372 	for (var i = 0; i < this.items.length; i++)
5373 		if (!stack.contains(this.items[i])) {
5374 			if (this.items[i].cloneDistinct)
5375 				stack.push(this.items[i].cloneDistinct());
5376 			else if (this.items[i].clone)
5377 				stack.push(this.items[i].clone());
5378 			else
5379 				stack.push(this.items[i]);
5380 		}
5381 	return stack;
5382 };
5383 
5384 /**
5385  * Class that implements the iterator for a linked list.
5386  * @param aggregate {Stack} The aggregate to scan.
5387  * @constructor
5388  */
5389 function StackIterator(aggregate) {
5390 	/**
5391 	 * The aggregate relates to this iterator.
5392 	 * @type {Stack}
5393 	 */
5394 	this.aggregate = aggregate;
5395 
5396 	/**
5397 	 * The pointer to the position.
5398 	 * @type {number}
5399 	 */
5400 	this.pointer = -1;
5401 }
5402 
5403 /**
5404  * Moves the iterator to the first position of the aggregate.
5405  * @return {void}
5406  */
5407 StackIterator.prototype.first = function () {
5408 	this.pointer = this.aggregate.items.length - 1;
5409 };
5410 
5411 /**
5412  * Moves the iterator to the next item.
5413  * @return {void}
5414  */
5415 StackIterator.prototype.next = function () {
5416 	this.pointer--;
5417 };
5418 
5419 /**
5420  * Moves the iterator to the last position of the aggregate.
5421  * @return {void}
5422  */
5423 StackIterator.prototype.last = function () {
5424 	this.pointer = 0;
5425 };
5426 
5427 /**
5428  * Moves the iterator to the previous item.
5429  * @return {void}
5430  */
5431 StackIterator.prototype.previous = function () {
5432 	this.pointer++;
5433 };
5434 
5435 /**
5436  * Checks if the iterator is out of the bounds of the aggregate.
5437  * @return {boolean} It return true if the iterator is out of the bounds of the aggregate, otherwise false.
5438  */
5439 StackIterator.prototype.isDone = function () {
5440 	return this.pointer < 0 || this.pointer > this.aggregate.items.length - 1;
5441 };
5442 
5443 /**
5444  * Returns the item stored at the position pointed by the iterator.
5445  * @return {*} The item stored or undefined if it's out of the bounds.
5446  */
5447 StackIterator.prototype.getItem = function () {
5448 	return this.aggregate.getItem(this.pointer);
5449 };