red-black trees

Let us use the following notation for red-black trees:

A red tree is noted (left value right).
A black tree is noted [left value right].
A null tree is noted null.

For example, [ [ null 0 null ] 1 [ ( null 2 null ) 3 null ] ] is a valid red-black tree containing the values 0, 1, 2, and 3.

Let us insert several numbers in an empty red-black tree, using two different implementations.

hand-crafted implementation

The hand-crafted implementation (with no pattern matching) is the following:

Tree.prototype.balance2 = function() {
  if(this.color == black && this.left != null && this.left.left != null &&
     this.left.color == red && this.left.left.color == red)
    return new Tree(red, new Tree(black, this.left.left.left, this.left.left.value, 
                                  this.left.left.right), 
		    this.left.value, 
		new Tree(black, this.left.right, this.value, this.right));
  if(this.color == black && this.left != null && this.left.right != null &&
     this.left.color == red && this.left.right.color == red)
    return new Tree(red, new Tree(black, this.left.left, this.left.value, 
			          this.left.right.left), 
		    this.left.right.value, 
		new Tree(black, this.left.right.right, this.value, this.right));
  if(this.color == black && this.right != null && this.right.left != null &&
     this.right.color == red && this.right.left.color == red)
    return new Tree(red, new Tree(black, this.left, this.value, this.right.left.left), 
		    this.right.left.value, 
		new Tree(black, this.right.left.right, this.right.value, 
		         this.right.right));
  if(this.color == black && this.right != null && this.right.right != null &&
     this.right.color == red && this.right.right.color == red)
    return new Tree(red, new Tree(black, this.left, this.value, this.right.left), 
		    this.right.value, 
		new Tree(black, this.right.right.left, this.right.right.value, 
		         this.right.right.right));
  return this;
};

implementation using myPatterns/JS

The pattern-matching version is the following:

Tree.prototype.balance = function() {
  var s = matchAny(this, ["[((%a %x %b) %y %c) %z %d]",
			  "[(%a %x (%b %y %c)) %z %d]",
			  "[%a %x ((%b %y %c) %z %d)]",
			  "[%a %x (%b %y (%c %z %d))]"]);
  if(s)
    return new Tree(red, new Tree(black, s.a, s.x, s.b), 
		    s.y, new Tree(black, s.c, s.z, s.d));
  return this;
};

implementation using parsed myPatterns/JS

The parsed pattern versionis the following (note that we use here unnamed variables for a change, but this is not mandatory for parsed patterns):

named = false;
Tree.prototype.um = [matcher(Tree, "[((% % %) % %) % %]"),
           matcher(Tree, "[(% % (% % %)) % %]"),
           matcher(Tree, "[% % ((% % %) % %)]"),
           matcher(Tree, "[% % (% % (% % %))]")];

Tree.prototype.ubalance3 = function() {
  s = Tree.prototype.um[0](this) || Tree.prototype.um[1](this) || Tree.prototype.um[2](this) || Tree.prototype.um[3](this);
  if(!s) return this;
  return new Tree(red, new Tree(black, s[0], s[1], s[2]), 
	          s[3], new Tree(black, s[4], s[5], s[6]));
};

Example:

comments

Although the hand-crafted implementation is several times faster, the source of the pattern-mactching version is way simpler and easier to write. The implementation complexity factor is of the same order of magnitude as that between using regular expression for string matching and doing string matching by hand (both in JavaScript).

Therefore, everyone using regular expressions in JavaScript may also consider using myPatterns/JS.