container-avltreelist - npm Package Compare versions

Comparing version 0.1.6 to 0.1.7

index.js

@@ -123,3 +123,5 @@ /**
 
-	this._balance(newNode.parent);
+	if (current.height === 1) {
+		this._balance(newNode.parent, false);
+	}
 
@@ -130,23 +132,34 @@ return newNode;
 AvlTreeList.prototype._balanceLeftRight = function (node) {
-	var left = node.left;
+	var left  = node.left;
+	var right = left.right;
+
 	var a = left.left;
-	var b = left.right.left;
+	var b = right.left;
 
-	left.right.left = left;
-	node.left = left.right;
-	left = node.left;
-	left.parent = node;
+	right.left = left;
+	node.left  = right;
 
-	var leftLeft = left.left;
-	leftLeft.parent = left;
-	leftLeft.left = a;
-	leftLeft.right = b;
+	right.parent = node;
+	left.parent  = right;
+
+	left.left  = a;
+	left.right = b;
+
+	var aHeight = 0;
 	if (a !== null) {
-		a.parent = leftLeft;
+		aHeight = a.height;
+		a.parent = left;
 	}
+
+	var bHeight = 0;
 	if (b !== null) {
-		b.parent = leftLeft;
+		bHeight = b.height;
+		b.parent = left;
 	}
+	
+	var leftHeight = ((aHeight > bHeight) ? aHeight : bHeight) + 1;
+	left.height = leftHeight;
 
-	left.height = leftLeft.height + 1;
+	var rightHeight = (right.right === null) ? 0 : right.right.height;
+	right.height = ((leftHeight > rightHeight) ? leftHeight : rightHeight) + 1;
 };
@@ -158,9 +171,10 @@
 
+	var parent = node.parent;
 	if (node === this.root) {
 		this.root = left;
 	} else {
-		if (node.parent.right === node) {
-			node.parent.right = left;
+		if (parent.right === node) {
+			parent.right = left;
 		} else {
-			node.parent.left = left;
+			parent.left = left;
 		}
@@ -170,10 +184,16 @@ }
 	left.right = node;
-	left.parent = node.parent;
+	left.parent = parent;
 	node.parent = left;
 	node.left = c;
-	if (c !== null) {
+
+	var leftHeight;
+	if (c === null) {
+		leftHeight = 0;
+	} else {
 		c.parent = node;
+		leftHeight = c.height;
 	}
 
-	node.height = node.height - 1;
+	var rightHeight = (node.right === null) ? 0 : node.right.height;
+	node.height = ((leftHeight > rightHeight) ? leftHeight : rightHeight) + 1;
 };
@@ -183,22 +203,33 @@
 	var right = node.right;
+	var left = right.left;
+
 	var a = right.right;
-	var b = right.left.right;
+	var b = left.right;
 
-	right.left.right = right;
-	node.right = right.left;
-	right = node.right;
-	right.parent = node;
+	left.right = right;
+	node.right = left;
 
-	var rightRight = right.right;
-	rightRight.parent = right;
-	rightRight.right = a;
-	rightRight.left = b;
+	left.parent  = node;
+	right.parent = left;
+
+	right.right = a;
+	right.left  = b;
+
+	var aHeight = 0;
 	if (a !== null) {
-		a.parent = rightRight;
+		aHeight = a.height;
+		a.parent = right;
 	}
+
+	var bHeight = 0;
 	if (b !== null) {
-		b.parent = rightRight;
+		bHeight = b.height;
+		b.parent = right;
 	}
+	
+	var rightHeight = ((aHeight > bHeight) ? aHeight : bHeight) + 1;
+	right.height = rightHeight;
 
-	node.right.height = rightRight.height + 1;
+	var leftHeight = (left.left === null) ? 0 : left.left.height;
+	left.height = ((leftHeight > rightHeight) ? leftHeight : rightHeight) + 1;
 };
@@ -225,52 +256,56 @@
 	node.right = c;
-	if (c !== null) {
+
+	var rightHeight;
+	if (c === null) {
+		rightHeight = 0;
+	} else {
 		c.parent = node;
+		rightHeight = c.height;
 	}
 
-	node.height = node.height - 1;
+	var leftHeight = (node.left === null) ? 0 : node.left.height;
+	node.height = ((leftHeight > rightHeight) ? leftHeight : rightHeight) + 1;
 };
 
-AvlTreeList.prototype._balance = function (node) {
+AvlTreeList.prototype._balance = function (node, goAllTheWay) {
 	// Balancing the tree
 	var current = node;
 	while (current !== null) {
-		var leftHeight = (current.left === null) ? 0 : current.left.height;
-		var rightHeight = (current.right === null) ? 0 : current.right.height;
-		var newHeight = 1 + Math.max(leftHeight, rightHeight);
+		var left  = current.left;
+		var right = current.right;
 
-		if (newHeight > current.height) {
-			current.height = newHeight;
-			if (leftHeight - rightHeight > 1) {
-				// Left case
-				if (current.left.right !== null &&
-					(current.left.left === null || current.left.left.height < current.left.right.height)) {
-					// Left Right Case
-					this._balanceLeftRight(current);
-				}
+		var leftHeight  = (left  === null) ? 0 : left.height;
+		var rightHeight = (right === null) ? 0 : right.height;
 
-				// Left Left Case
-				this._balanceLeftLeft(current);
+		if (leftHeight - rightHeight > 1) {
+			// Left case
+			if (left.right !== null && (left.left === null || left.left.height < left.right.height)) {
+				// Left Right Case
+				this._balanceLeftRight(current);
+			}
 
-				// The tree has been balanced
-				break;
-			} else if (rightHeight - leftHeight > 1) {
-				// Right case
-				if (current.right.left !== null &&
-					(current.right.right === null || current.right.right.height < current.right.left.height)) {
-					// Right Left Case
-					this._balanceRightLeft(current);
+			// Left Left Case
+			this._balanceLeftLeft(current);
+		} else if (rightHeight - leftHeight > 1) {
+			// Right case
+			if (right.left !== null && (right.right === null || right.right.height < right.left.height)) {
+				// Right Left Case
+				this._balanceRightLeft(current);
+			}
+
+			// Right Right Case
+			this._balanceRightRight(current);
+		} else {
+			// TreeNode is balanced
+			var newHeight = ((leftHeight > rightHeight) ? leftHeight : rightHeight) + 1;
+			if (!goAllTheWay) {
+				if (newHeight === current.height) {
+					break;
 				}
+			}
 
-				// Right Right Case
-				this._balanceRightRight(current);
+			current.height = newHeight;
+		}
 
-				// The tree has been balanced
-				break;
-			} else {
-				// TreeNode is balanced
-				current = current.parent;
-			}
-		} else {
-			break;
-		}
+		current = current.parent;
 	}
@@ -303,2 +338,6 @@ };
 	if (node.right === null) {
+		if (left !== null) {
+			left.parent = parent;
+		}
+
 		if (parent === null) {
@@ -312,9 +351,12 @@ this.root = left;
 			}
-		}
 
-		if (left !== null) {
-			left.parent = parent;
+			if (left === null) {
+				this._balance(parent, true);
+			} else {
+				if (left.height + 3 <= parent.height) {
+					this._balance(parent, true);
+				}
+			}
 		}
 
-		this._balance(parent);
 		return true;
@@ -324,7 +366,3 @@ }
 	var replacement = node.right;
-	var balanceFrom;
-
 	if (replacement.left === null) {
-		balanceFrom = replacement;
-
 		if (left !== null) {
@@ -346,4 +384,3 @@ left.parent = replacement;
 
-		this._balance(balanceFrom);
-
+		this._balance(replacement, true);
 		return true;
@@ -367,3 +404,2 @@ }
 
-	balanceFrom = replacement.parent;
 
@@ -384,5 +420,7 @@ if (left !== null) {
 	}
+
+	var balanceFrom = replacement.parent;
 	replacement.parent = parent;
 
-	this._balance(balanceFrom);
+	this._balance(balanceFrom, true);
 
@@ -447,3 +485,3 @@ // Removing any reference from the node to any other element
 AvlTreeList.prototype.forEach = function (processingFunc, params) {
-	for (var current = this.first; current; current = current.next) {
+	for (var current = this.first; current !== null; current = current.next) {
 		processingFunc(current.object, params);
@@ -454,3 +492,3 @@ }
 AvlTreeList.prototype.forEachReverse = function (processingFunc, params) {
-	for (var current = this.last; current; current = current.previous) {
+	for (var current = this.last; current !== null; current = current.previous) {
 		processingFunc(current.object, params);
@@ -469,3 +507,3 @@ }
 	nodeB.object = objectA;
-}
+};
 
@@ -492,3 +530,3 @@ AvlTreeList.prototype.reposition = function (node) {
 				cmp = this.cmpFunc(object, previous.object);
-			} while (cmp < 0)
+			} while (cmp < 0);
 			return;
@@ -508,3 +546,3 @@ }
 				cmp = this.cmpFunc(object, next.object);
-			} while (cmp > 0)
+			} while (cmp > 0);
 			return;
@@ -517,3 +555,3 @@ }
 	var objects = [];
-	for (var current = this.first; current; current = current.next) {
+	for (var current = this.first; current !== null; current = current.next) {
 		objects.push(current.object);
@@ -525,6 +563,23 @@ }
 AvlTreeList.prototype.clear = function () {
+	var current = this.first;
+	while (current !== null) {
+		var next = current.next;
+
+		current.container = null;
+		current.left      = null;
+		current.right     = null;
+		current.parent    = null;
+		current.next      = null;
+		current.previous  = null;
+
+		current = next;
+	}
+
 	this.length = 0;
 	this.root = null;
+	this.first = null;
+	this.last = null;
 };
 
+
 module.exports = AvlTreeList;

package.json

 {
   "name": "container-avltreelist",
-  "version": "0.1.6",
+  "version": "0.1.7",
   "description": "AvlTreeList implementation in JavaScript",
   "main": "index.js",
   "scripts": {
-    "test": "echo \"Error: no test specified\" && exit 1"
+    "test": "mocha test/test.js"
   },
+  "devDependencies": {
+    "mocha": "3.2.0"
+  },
   "author": "bchevalier",
   "license": "MIT"
 }

New alerts

License Policy Violation

License

This package is not allowed per your license policy. Review the package's license to ensure compliance.

Found 1 instance in 1 package

Fixed alerts

License Policy Violation

License

This package is not allowed per your license policy. Review the package's license to ensure compliance.

Found 1 instance in 1 package

No tests

Quality

Package does not have any tests. This is a strong signal of a poorly maintained or low quality package.

Found 1 instance in 1 package

Improved metrics

Total package byte prevSize

29282

increased by86.62%

Number of package files

6

increased by50%

Lines of code

933

increased by119.01%

Number of low quality alerts

2

decreased by-33.33%

Worsened metrics

Dev dependency count

1

increased byInfinity%

No dependency changes