Tag Archives: Recursion

Embedding Stylesheets in JavaScript

Now Available in YourJS

One of the cool things about JS is that you can do almost anything with it! The only thing is that you need to have the tools to get that “anything” job done. Recently, I had the desire to embed HTML, CSS, and JS all in one file that would be loaded when a specific browser event fired. The common solution is to use a library such as jQuery to load an HTML snippet but I wanted a different solution. I was thinking it would be great to be able to do something like this:

css({
    'div.special-1, span.special-2': {
        fontFamily: 'Trebuchet MS',
        a: {
            textDecoration: null,
            '&:link, &:visited': { color: '#08F' },
            '&:hover, &:active': { color: 'red' }
        }
    }
});

Having this resulting in a stylesheet added to the HEAD with the following CSS:

div.special-1, span.special-2 {
    font-family: Trebuchet MS;
}
div.special-1 a, span.special-2 a {
    text-decoration: none;
}

div.special-1 a:link, span.special-2 a:link,
div.special-1 a:visited, span.special-2 a:visited {
    color: #08F;
}

div.special-1 a:hover, span.special-2 a:hover,
div.special-1 a:active, span.special-2 a:active {
    color: red;
}

After a bit of work to make a few Sass-like features work, I came up with the following JavaScript function:

Brief css(objStyles, opt_ancestors) Documentation

This function takes an object representing CSS rules and adds a stylesheet with those rules to the document.

Parameters

  1. objStyles
    An object representing the CSS rules to be inserted into the document.

    • Property names will be used as media queries if they start with "@media ".
    • Property names will be used as rule selectors if the value is an object.
    • If a property name is to be used as a selector, if any selectors don’t contain &, "& " will be prepended to it.
    • For all selectors, & will be replaced recursively with the selectors found in the parent.
    • CSS property names will be uncamelcased by inserting dashes before each uppercased character and lower casing all characters.
    • If a value is null or undefined, it will be turned into "none".
    • If a value is a number other than 0, "px" will be appended to it.
    • If a value is an array all of the items will be concatenated together, using "," to delimit the values.
    • If a value ends with ! it will be replaced with "!important".
  2. opt_ancestors
    Optional. This can be an element or an array of elements which will get another class added to target all rules to it and its children. This can alternatively be a CSS path (selector) specifying the root on which all CSS rules created should be based.

Returns

The stylesheet that is created and appended to the document is returned.

Future Development

I feel like this function turned out pretty well so I plan on incorporating it into YourJS (whenever I finish up with that :-D ). In the meantime, if I update the code, you will be able to see the updates here or in GitHub. One thing I would like to incorporate is the ability to have variables. Another nice-to-have thing would be the ability to supply more options such as where the stylesheet should be inserted (if it will be inserted at all), pretty-print, and helper functions (eg. darken). Feel free to leave a comment saying what other things may be nice to have. 8-)

JavaScript – Getting All Text Nodes

I have been working on something I am calling JS-Proofs (or jPaq Proofs). While working on the menu I was faced with the annoying issue of either not having whitespaces between my elements in the markup or removing them some other way. Since my favorite language is JS, I decided to write a function that would remove all of the text nodes with whitespaces for me. This evolved into a more general function which retrieves an array of all the text nodes contained by a given element:

/**
 * Gets an array of the matching text nodes contained by the specified element.
 * @param  {!Element} elem
 *     The DOM element which will be traversed.
 * @param  {function(!Node,!Element):boolean} opt_fnFilter
 *     Optional function that if a true-ish value is returned will cause the
 *     text node in question to be added to the array to be returned from
 *     getTextNodesIn().  The first argument passed will be the text node in
 *     question while the second will be the parent of the text node.
 * @return {!Array.}
 *     Array of the matching text nodes contained by the specified element.
 */
function getTextNodesIn(elem, opt_fnFilter) {
  var textNodes = [];
  if (elem) {
    for (var nodes = elem.childNodes, i = nodes.length; i--;) {
      var node = nodes[i], nodeType = node.nodeType;
      if (nodeType == 3) {
        if (!opt_fnFilter || opt_fnFilter(node, elem)) {
          textNodes.push(node);
        }
      }
      else if (nodeType == 1 || nodeType == 9 || nodeType == 11) {
        textNodes = textNodes.concat(getTextNodesIn(node, opt_fnFilter));
      }
    }
  }
  return textNodes;
}

What is kind of cool about the above function is that it not only allows you to get all of the child text nodes, but all descendant text nodes. This function also provides the capability of specifying an optional filtering function to just return text nodes that match a criteria. The function will be passed the text node in question and the parent of that text node. In order to specify that the text node should be added to the array returned from getTextNodesIn you must return a true-ish value.

The following is an example of how to use this function in order to remove all whitespace text nodes from an element:

var menu = document.getElementById('divMenu');
getTextNodesIn(menu, function(textNode, parent) {
  if (/^\s+$/.test(textNode.nodeValue)) {
    parent.removeChild(textNode);
  }
});

In the strictest sense I am actually kind of hacking the new function that I defined but it gets the job done. 8-)

JavaScript – Euclidean Algorithm

One of the things that you often have to learn early on in school after multiplication and division is how to find the GCD (Greatest Common Divisor) of two numbers. It is possible that you know the GCD as the GCF (Greatest Common Factor) or the HCF (Higest Common Factor). Do you know how to calculate this for any two positive integers? Many may simply list all of the positive divisors of both numbers and take the largest shared between the two numbers. On the other hand, at times it isn’t easy to list all of these positive divisors. Therefore you could use Euclid’s Algorithm to find the GCD of two numbers.

What is Euclid’s Algorithm

To use this algorithm, you should do the following:

  1. Find the remainder of dividing the larger number by the smaller one:
    remainder = max % min
  2. If the remainder is equal to 0, you can stop because you have identified the GCD which is the smaller number from the previous step.
  3. Start back at step one, using the smaller number as the larger number and the remainder as the smaller number:
    max = min
    min = remainder

Now let’s try to find the GCD of 462 and 910 using the algorithm outlined above:

  1. Find the remainder of dividing 910 (the larger number) by 462 (the smaller number):
    remainder = 910 % 462 =  448
  2. Since the remainder is not 0, we must now find the remainder of dividing 462 (the new larger number) by 448 (the new smaller number):
    remainder = 462 % 448 = 14
  3. Since the remainder is not 0 we must now find the remainder of dividing 448 (the new larger number) by 14 (the new smaller number):
    remainder = 448 % 14 = 0
  4. We know that 14 is the GCD because that was the last smaller number used that gave a remainder of 0.
Now that we can see how easy that is and how efficient it is, it is now time to implement it as a function on a computer.  Since JavaScript is my favorite language and it is the most widely available action language, I decided to define it in JavaScript:
function gcd(a, b) {
  return b ? gcd(b, a % b) : a;
}

The cool thing about this function definition is the fact that it is actually defined recursively. Although I didn’t have to define it that way, I felt it was the perfect opportunity to show how to think recursively. The following live example proves that this works for all integers:
GCD Implemenetation

That example shows the power of recursion, JavaScript, and old school mathematics! 8)

POW Answer – Explain That SQL #1

To answer last week’s POW, the purpose of the SQL was to generate a random string of letters and numbers. I actually wrote two different JavaScript function that can produce the same results. The following is the slightly more straight-forward solution:

function randomChars(len) {
  for(var n, s = ""; --len;) {
    n = parseInt(Math.random() * 62);
    s = String.fromCharCode(n + (n < 26 ? 65 : n < 52 ? 71 : -4));
  }
  return s;
}

The next version is a bit harder to follow because it involves recursion:

function recRandomChars(len) {
  if(!len){ return ""; }
  var n = parseInt(Math.random() * 62);
  return recRandomChars(--len)
    + String.fromCharCode(n + (n < 26 ? 65 : n < 52 ? 71 : -4));
}

One practical application of this is to generate a password with random characters.

JScript – Recursively Call A Script

Have you ever wondered how you can recursively call a JScript? Here is an example which shows how it can be done:

WshShell = new ActiveXObject("WScript.Shell");
switch(WshShell.Popup("Do you want to run this script again?", 10, "Run Script Again", 4 + 32))
{
  case -1:
    WScript.Echo("I guess you aren't there.  See'ya!!!");
    break;
  case 6:
    WshShell.run('"' + WScript.ScriptFullName + '"');
    break;
  case 7:
    WScript.Echo("Take it easy.");
    break;
}

It is important to note that the above example will not pass any variables that were passed to it. If you want to try this out on your Windows machine, download Recursive Script to your computer and double-click it.

JavaScript – Binary Search

The following is an implementation of a binary search for arrays which gives you the ability to do fuzzy matches (default), exact matches, or specify your own comparison function:

(function() {
  // Use this if the search isn't called with a 2nd param or it
  // is false.
  function fnFuzzy(a, b) {
    return a < b ? -1 : a > b ? 1 : a == b ? 0 : null;
  }
  
  // Use this if the search is called with a 2nd param of true.
  function fnExact(a, b) {
    return a < b ? -1 : a > b ? 1 : a === b ? 0 : null;
  }
  
  // Recursively does a binary search.
  function binarySearch(arr, item, min, max, fnCmp) {
    if(min > max) {
      return -1;
    }
    var mid = parseInt((min + max) / 2);
    var ret = fnCmp(item, arr[mid]);
    if(ret) {
      return binarySearch(arr, item,
        ret > 0 ? mid + 1 : min,
        ret < 0 ? mid - 1 : max, fnCmp);
    }
    else if(ret == 0) {
      return mid;
    }
  }
  
  // Define the prototypal function.
  Array.prototype.binarySearch = function(item, extactMatch) {
    return binarySearch(this, item, 0, this.length - 1,
      extactMatch
        ? typeof extactMatch == "function"
          ? extactMatch
          : fnExact
        : fnFuzzy);
  };
})();

I used the following to test the normal execution of this binary function:

// Create a pre-sorted array of distinct random numbers ranging
// from 0 to 9999 and keep a reverse index to validate what is
// being returned by the binarySearch() function:
var arr = [], reverseIndex = {"-1" : -1};
for(var limit = 10000, i = 0; i < limit; i++) {
  if(Math.random() < 0.5) {
    reverseIndex[i] = arr.length;
    arr.push(i);
  }
  else {
    reverseIndex[i] = -1;
  }
}
reverseIndex[limit] = -1;

// Run through all numbers from -1 to 10000, using the reverse
// index making sure that the binarySearch() function works
// properly:
for(var v1, v2, i = -1; i <= limit; i++) {
  // If the binary search doesn't return the correct thing,
  // let the user know.
  if((v1 = arr.binarySearch(i)) != (v2 = reverseIndex[i])) {
    alert("The search for " + i + " returned an index of "
      + v1 + " when it should have returned " + v2
      + ".");
    break;
  }
}

// If all of the tests were successfully run, tell the user.
if(i == limit + 1) {
  alert("All " + arr.length
    + " numbers that should have been found were found.");
}

POW Answer – Unnamed Function #1

The answer to last week’s Problem of the Week is that the following definitions represent the factorial of the given non-negative integer:

Mathematical Definition

Function Definition Condition
unnamed(n) = 1 if n = 0
n × unnamed(n – 1) if n > 0

JavaScript Definition

function unnamed(n) {
  if(n == 0)
    return 1;
  if(n > 0)
    return n * unnamed(n - 1);
}

Although it may have been easy for some people to follow, for those of you who are not familiar with recursion, it may have been a bit difficult. Let’s use the number 4 as an example to step through the process:

  1. When we pass 4 into unnamed we get the following definition for the output:
    unnamed(4) = 4  × unnamed(4 - 1) = 4 × unnamed(3)
  2. Now we have to find the definition for passing 3 into unnamed:
    unnamed(3) = 3  × unnamed(3 - 1) = 3 × unnamed(2)
  3. Now we have to find the definition for passing 2 into unnamed:
    unnamed(2) = 2  × unnamed(2 - 1) = 2 × unnamed(1)
  4. Now we have to find the definition for passing 1 into unnamed:
    unnamed(1) = 1  × unnamed(1 - 1) = 1 × unnamed(0)
  5. Now we have to find the definition for passing 0 into unnamed:
    unnamed(0) = 1
  6. Now we go back to step 4 and replace unnamed(0) with 1:
    unnamed(1) = 1  × 1 = 1
  7. Now we go back to step 3 and replace unnamed(1) with 1:
    unnamed(2) = 2  × 1 = 2
  8. Now we go back to step 2 and replace unnamed(2) with 2:
    unnamed(3) = 3  × 2 = 6
  9. Now we go back to step 1 and replace unnamed(3) with 6:
    unnamed(4) = 4  × 6 = 24

After stepping through each part of the process, you can more easily see the pattern.

  • unnamed(4) is really equal to 4 × 3 × 2 × 1 × 1
  • unnamed(3) is really equal to 3 × 2 × 1 × 1
  • unnamed(2) is really equal to 2 × 1 × 1
  • unnamed(1) is really equal to 1 × 1
  • unnamed(0) is really equal to 1
    NOTE: The above (0! = 1) is more of a technicality that many people don’t really think about for factorial.

Forcing A Constructor In JavaScript

Did you know that you can force a function to only act as a constructor? The following is an example of a Person pseudo-class which can be defined with or without the new keyword:

// Defines a person object.
function Person(firstName, lastName, age) { 
  // If called without parameters.
  if(!arguments.length) {
    // If this is a recursive call, allow the properties to now be defined.
    if(arguments.callee.caller === arguments.callee) {
      return this;
    }
    // If this is a non-recursive call, throw an error since the constructor
    // can't be called without parameters.
    else {
      throw new Error("No parameters were specified for the Person object.");
    }
  }
  
  // Allows make sure this function acts as a constructor.
  var me = !(this instanceof arguments.callee) ? new Person : this;
    
  // Define the properties.
  me.firstName = firstName;
  me.lastName = lastName;
  me.age = age;
  
  // Return a reference to the new Person instance.
  return me;
}

// Define the prototypal functions.
Person.prototype = {
  toString : function() {
    return this.firstName + " " + this.lastName + " is " + this.age
      + " years old.";
  }
};

One of the things that you may have noticed is the fact that I am throwing an error if the constructor is called without any arguments. If you don’t want that to happen, you can simply remove that else statement. Everything is probably pretty self explanatory.

The following are two examples which prove the above code actually works:

// Create an instance of a person without the "new" keyword.
var p = Person("Chris", "West", 23);
alert(p.firstName);  // display "Chris"
alert(p instanceof Person);  // display true
alert(p);  // use toString() function

// Create an instance of a person with the "new" keyword.
var p = new Person("Tamara", "Thomas", 21);
alert(p.age);  // display 21
alert(p instanceof Person);  // display true
alert(p);  // use toString() function.

Deep Copy of Arrays

With jPaq and many other JavaScript libraries, it is very easy to do a shallow copy of an array. On the other hand, it isn’t as easy to do a deep copy of arrays. For this reason, I plan on replacing the Array.prototype.clone() function with the following:

Array.prototype.clone = function(doDeepCopy) {
    if(doDeepCopy) {
        var encountered = [{
            a : this,
            b : []
        }];

        var item,
            levels = [{a:this, b:encountered[0].b, i:0}],
            level = 0,
            i = 0,
            len = this.length;

        while(i < len) {
            item = levels[level].a[i];
            if(Object.prototype.toString.call(item) === "[object Array]") {
                for(var j = encountered.length - 1; j >= 0; j--) {
                    if(encountered[j].a === item) {
                        levels[level].b.push(encountered[j].b);
                        break;
                    }
                }
                if(j < 0) {
                    encountered.push(j = {
                        a : item,
                        b : []
                    });
                    levels[level].b.push(j.b);
                    levels[level].i = i + 1;
                    levels[++level] = {a:item, b:j.b, i:0};
                    i = -1;
                    len = item.length;
                }
            }
            else {
                levels[level].b.push(item);
            }

            if(++i == len && level > 0) {
                levels.pop();
                i = levels[--level].i;
                len = levels[level].a.length;
            }
        }

        return encountered[0].b;
    }
    else {
        return this.slice(0);
    }
};

The above code can be used to make deep copies of arrays. It is important to note, though, that only sub-arrays are deeply copied, not objects. The reason so much code is used is to even make it possible to make a deep copy of a recursive array structure. The following code exemplifies how to use this function:

// Create a recursive array to prove that the cloning function can handle it.
var arrOriginal = [1,2,3];
arrOriginal.push(arrOriginal);

// Make a shallow copy of the recursive array.
var arrShallowCopy = arrOriginal.clone();

// Prove that the shallow copy isn't the same as a deep copy by showing that
// arrShallowCopy contains arrOriginal.
alert("It is " + (arrShallowCopy[3] === arrOriginal)
    + " that arrShallowCopy contains arrOriginal.");

// Make a deep copy of the recursive array.
var arrDeepCopy = arrOriginal.clone(true);

// Prove that the deep copy really works by showing that the original array is
// not the fourth item in arrDeepCopy but that this new array is.
alert("It is "
    + (arrDeepCopy[3] !== arrOriginal && arrDeepCopy === arrDeepCopy[3])
    + " that arrDeepCopy contains itself and not arrOriginal.");

If you want to use this code right now, there is nothing stopping you. The code doesn’t require any library references and is fully cross-browser compatible. A JSBin example can be found here. It even works in JScript. The only thing that I ask is that you give credit where it is due. :D