Data Structures and Algorithms with JavaScript

Chapter 1. The JavaScript Programming Environment and Model

This chapter describes the JavaScript programming environment and the programming constructs we’ll use in this book to define the various data structures and algorithms examined.

The JavaScript Environment

JavaScript has historically been a programming language that ran only inside a web browser. However, in the past few years, there has been the development of JavaScript programming environments that can be run from the desktop, or similarly, from a server. In this book we use one such environment: the JavaScript shell that is part of Mozilla’s comprehensive JavaScript environment known as SpiderMonkey.

To download the JavaScript shell, navigate to the Nightly Build web page. Scroll to the bottom of the page and pick the download that matches your computer system.

Once you’ve downloaded the program, you have two choices for using the shell. You can use it either in interactive mode or to interpret JavaScript programs stored in a file. To use the shell in interactive mode, type the command js at a command prompt. The shell prompt, js>, will appear and you are ready to start entering JavaScript expressions and statements.

The following is a typical interaction with the shell:

js> 1
1
js> 1+2
3
js> var num = 1;
js> num*124
124
js> for (var i = 1; i < 6; ++i) {
    print(i);
}
1
2
3
4
5
js>

You can enter arithmetic expressions and the shell will immediately evaluate them. You can write any legal JavaScript statement and the shell will immediately evaluate it as well. The interactive shell is great for exploring JavaScript statements to discover how they work. To leave the shell when you are finished, type the command quit().

The other way to use the shell is to have it interpret complete JavaScript programs. This is how we will use the shell throughout the rest of the book.

To use the shell to intepret programs, you first have to create a file that contains a JavaScript program. You can use any text editor, making sure you save the file as plain text. The only requirement is that the file must have a .js extension. The shell has to see this extension to know the file is a JavaScript program.

Once you have your file saved, you interpret it by typing the js command followed by the full filename of your program. For example, if you saved the for loop code fragment that’s shown earlier in a file named loop.js, you would enter the following:

c:\js>js loop.js

which would produce the following output:

1
2
3
4
5

After the program is executed, control is returned to the command prompt.

JavaScript Programming Practices

In this section we discuss how we use JavaScript. We realize that programmers have different styles and practices when it comes to writing programs, and we want to describe ours here at the beginning of the book so that you’ll understand the more complex code we present in the rest of the book. This isn’t a tutorial on using JavaScript but is just a guide to how we use the fundamental constructs of the language.

Declaring and Initializing Variables

JavaScript variables declared outside of a function are global by default and, strictly speaking, don’t have to be declared before using. When a JavaScript variable is initialized without first being declared, using the var keyword, it becomes a global variable. In this book, however, we follow the convention used with compiled languages such as C++ and Java by declaring all variables before their first use. The added benefit to doing this is that variables declared within function are created as local variables. We will talk more about variable scope later in this chapter.

Note

You can use strict mode to ensure variables are declared before use. Insert the following line exactly before any other statement:

'use strict';

Or

"use strict";

To declare a variable in JavaScript, use the keyword var followed by a variable name, and optionally, an assignment expression. Here are some examples:

var number;
var name;
var rate = 1.2;
var greeting = "Hello, world!";
var flag = false;

Arithmetic and Math Library Functions in JavaScript

JavaScript utilizes the standard arithmetic operators:

• + (addition)

• - (subtraction)

• * (multiplication)

• / (division)

• % (modulo)

JavaScript also has a math library you can use for advanced functions such as square root, absolute value, and the trigonometric functions. The arithmetic operators follow the standard order of operations, and parentheses can be used to modify that order.

Example 1-1 shows some examples of performing arithmetic in JavaScript, as well as examples of using several of the mathematical functions.

Example 1-1. Arithmetic and math functions in JavaScript

var x = 3;
var y = 1.1;
print(x + y);
print(x * y);
print((x+y)*(x-y));
var z = 9;
print(Math.sqrt(z));
print(Math.abs(y/x));

The output from this program is:

4.1
3.3000000000000003
7.789999999999999
3
0.3666666666666667

If you don’t want or need the precision shown above, you can format a number to a fixed precision:

var x = 3;
var y = 1.1;
var z = x * y;
print(z.toFixed(2)); // displays 3.30

Decision Constructs

Decision constructs allow our programs to make decisions on what programming statements to execute based on a Boolean expression. The two decision constructs we use in this book are the if statement and the switch statement.

The if statement comes in three forms:

• The simple if statement

• The if-else statement

• The if-else if statement

Example 1-2 shows how to write a simple if statement.

Example 1-2. The simple if statement

var mid = 25;
var high = 50;
var low = 1;
var current = 13;
var found = -1;
if (current < mid) {
   mid = (current-low) / 2;
}

Example 1-3 demonstrates the if-else statement.

Example 1-3. The if-else statement

var mid = 25;
var high = 50;
var low = 1;
var current = 13;
var found = -1;
if (current < mid) {
   mid = (current-low) / 2;
} else {
   mid = (current+high) / 2;
}

Example 1-4 illustrates the if-else if statement.

Example 1-4. The if-else if statement

var mid = 25;
var high = 50;
var low = 1;
var current = 13;
var found = -1;
if (current < mid) {
   mid = (current-low) / 2;
}
else if (current > mid) {
   mid = (current+high) / 2;
}
else {
   found = current;
}

The other decision structure we use in this book is the switch statement. This statement provides a cleaner, more structured construction when you there’s a set of simple decisions. Example 1-5 demonstrates how the switch statement works.

Example 1-5. The switch statement

putstr("Enter a month number: ");
var monthNum = readline();
var monthName;
switch (monthNum) {
   case "1":
      monthName = "January";
      break;
   case "2":
      monthName = "February";
      break;
   case "3":
      monthName = "March";
      break;
   case "4":
      monthName = "April";
      break;
   case "5":
      monthName = "May";
      break;
   case "6":
      monthName = "June";
      break;
   case "7":
      monthName = "July";
      break;
   case "8":
      monthName = "August";
      break;
   case "9":
      monthName = "September";
      break;
   case "10":
      monthName = "October";
      break;
   case "11":
      monthName = "November";
      break;
   case "12":
      monthName = "December";
      break;
   default:
      print("Bad input");
}
print(monthName);

Is this the most efficient way to solve this problem? No, but it does a great job of demonstrating how the switch statement works.

One major difference between the JavaScript switch statement and switch statements in other programming languages is that the expression that is being tested in the statement can be of any data type, as opposed to an integral data type, as required by languages such as C++ and Java. In fact, you’ll notice in the previous example that we use the month numbers as strings, rather than converting them to numbers, since we can compare strings using the switch statement in JavaScript.

Repetition Constructs

Many of the algorithms we study in this book are repetitive in nature. We use two repetition constructs in this book—the while loop and the for loop.

When we want to execute a set of statements while a condition is true, we use a while loop. Example 1-6 demonstrates how the while loop works.

Example 1-6. The while loop

var number = 1;
var sum = 0;
while (number < 11) {
   sum += number;
   ++number;
}
print(sum); // displays 55

When we want to execute a set of statements a specified number of times, we use a for loop. Example 1-7 uses a for loop to sum the integers 1 through 10.

Example 1-7. Summing integers using a for loop

var number = 1;
var sum = 0;
for (var number = 1; number < 11; number++) {
   sum += number;
}
print(sum); // displays 55

for loops are also used frequently to access the elements of an array, as shown in Example 1-8.

Example 1-8. Using a for loop with an array

var numbers = [3, 7, 12, 22, 100];
var sum = 0;
for (var i = 0; i < numbers.length; ++i) {
   sum += numbers[i];
}
print(sum); // displays 144

Functions

JavaScript provides the means to define both value-returning functions and functions that don’t return values (sometimes called subprocedures or void functions).

Example 1-9 demonstrates how value-returning functions are defined and called in JavaScript.

Example 1-9. A value-returning function

function factorial(number) {
   var product = 1;
   for (var i = number; i >= 1; --i) {
      product *= i;
   }
   return product;
}

print(factorial(4)); // displays 24
print(factorial(5)); // displays 120
print(factorial(10)); // displays 3628800

Example 1-10 illustrates how to write a function that is used not for its return value, but for the operations it performs.

Example 1-10. A subprocedure or void function in JavaScript

function curve(arr, amount) {
   for (var i = 0; i < arr.length; ++i) {
      arr[i] += amount;
   }
}

var grades = [77, 73, 74, 81, 90];
curve(grades, 5);
print(grades); // displays 82,78,79,86,95

All function parameters in JavaScript are passed by value, and there are no reference parameters. However, there are reference objects, such as arrays, which are passed to functions by reference, as was demonstrated in Example 1-10.

Variable Scope

The scope of a variable refers to where in a program a variable’s value can be accessed. The scope of a variable in JavaScript is defined as function scope. This means that a variable’s value is visible within the function definition where the variable is declared and defined and within any functions that are nested within that function.

Note

Newer versions of ECMAScript do provide the capability of scoping variables at the block level, using the let statement. However, the support for let is still limited, and not critical to the core purpose of the book, so we’ll stick with widely supported, basic JavaScript functionality.

When a variable is defined outside of a function, in the main program, the variable is said to have global scope, which means its value can be accessed by any part of a program, including functions. The following short program demonstrates how global scope works:

function showScope() {
   return scope;
}

var scope = "global";
print(scope); // displays "global"
print(showScope()); // displays "global"

The function showScope() can access the variable scope because scope is a global variable. Global variables can be declared at any place in a program, either before or after function definitions.

Now watch what happens when we define a second scope variable within the showScope() function:

function showScope() {
   var scope = "local";
   return scope;
}

var scope = "global";
print(scope); // displays "global"
print(showScope()); // displays "local"

The scope variable defined in the showScope() function has local scope, while the scope variable defined in the main program is a global variable. Even though the two variables have the same name, their scopes are different, and their values are different when accessed within the area of the program where they are defined.

All of this behavior is normal and expected. However, it can all change if you leave off the keyword var in the variable definitions. JavaScript allows you to define variables without using the var keyword, but when you do, that variable automatically has global scope, even if defined within a function.

Example 1-11 demonstrates the ramifications of leaving off the var keyword when defining variables.

Example 1-11. The ramification of overusing global variables

function showScope() {
   scope = "local";
   return scope;
}

scope = "global";
print(scope); // displays "global"
print(showScope()); // displays "local"
print(scope); // displays "local"

In Example 1-11, because the scope variable inside the function is not declared with the var keyword, when the string "local" is assigned to the variable, we are actually changing the value of the scope variable in the main program. You should always begin every definition of a variable with the var keyword to keep things like this from happening.

Earlier, we mentioned that JavaScript has function scope. This means that JavaScript does not have block scope, unlike many other modern programming languages. With block scope, you can declare a variable within a block of code and the variable is not accessible outside of that block, as you typically see with a C++ or Java for loop:

for (int i = 1; i <=10; ++i) {
   cout << "Hello, world!" << endl;
}

Even though JavaScript does not have block scope, we pretend like it does when we write for loops in this book:

for (var i = 1; i <= 10; ++i ) {
   print("Hello, world!");
}

We don’t want to be the cause of you picking up bad programming habits.

Recursion

Function calls can be made recursively in JavaScript. The factorial() function defined earlier can also be written recursively, like this:

function factorial(number) {
   if (number == 1) {
      return number;
   }
   else {
      return number * factorial(number-1);
   }
}

print(factorial(5));

When a function is called recursively, the results of the function’s computation are temporarily suspended while the recursion is in progress. To demonstrate how this works, here is a diagram for the factorial() function when the argument passed to the function is 5:

5 * factorial(4)
5 * 4 * factorial(3)
5 * 4 * 3 * factorial(2)
5 * 4 * 3 * 2 * factorial(1)
5 * 4 * 3 * 2 * 1
5 * 4 * 3 * 2
5 * 4 * 6
5 * 24
120

Several of the algorithms discussed in this book use recursion. For the most part, JavaScript is capable of handling fairly deep recursive calls (this is an example of a relatively shallow recursive call); but in one or two situations, an algorithm requires a deeper recursive call than JavaScript can handle and we instead pursue an iterative solution to the algorithm. You should keep in mind that any function that uses recursion can be rewritten in an iterative manner.

Objects and Object-Oriented Programming

The data structures discussed in this book are implemented as objects. JavaScript provides many different ways for creating and using objects. In this section we demonstrate the techniques used in this book for creating objects and for creating and using an object’s functions and properties.

Objects are created by defining a constructor function that includes declarations for an object’s properties and functions, followed by definitions for the functions. Here is the constructor function for a checking account object:

function Checking(amount) {
   this.balance = amount; // property
   this.deposit = deposit; // function
   this.withdraw = withdraw; // function
   this.toString = toString; // function
}

The this keyword is used to tie each function and property to an object instance. Now let’s look at the function definitions for the preceding declarations:

function deposit(amount) {
   this.balance += amount;
}

function withdraw(amount) {
   if (amount <= this.balance) {
      this.balance -= amount;
   }
   if (amount > this.balance) {
      print("Insufficient funds");
   }
}

function toString() {
   return "Balance: " + this.balance;
}

Again, we have to use the this keyword with the balance property in order for the interpreter to know which object’s balance property we are referencing.

Example 1-12 provides the complete definition for the checking object along with a test program.

Example 1-12. Defining and using the Checking object

function Checking(amount) {
   this.balance = amount;
   this.deposit = deposit;
   this.withdraw = withdraw;
   this.toString = toString;
}

function deposit(amount) {
   this.balance += amount;
}

function withdraw(amount) {
   if (amount <= this.balance) {
      this.balance -= amount;
   }
   if (amount > this.balance) {
      print("Insufficient funds");
   }
}

function toString() {
   return "Balance: " + this.balance;
}

var account = new Checking(500);
account.deposit(1000);
print(account.toString()); // Balance: 1500
account.withdraw(750);
print(account.toString()); // Balance: 750
account.withdraw(800); // displays "Insufficient funds"
print(account.toString()); // Balance: 750

Summary

This chapter provided an overview of the way we use JavaScript throughout the rest of the book. We try to follow a programming style that is common to many programmers who are accustomed to using C-style languages such as C++ and Java. Of course, JavaScript has many conventions that do not follow the rules of those languages, and we certainly point those out (such as the declaration and use of variables) and show you the correct way to use the language. We also follow as many of the good JavaScript programming practices outlined by authors such as John Resig, Douglas Crockford, and others as we can. As responsible programmers, we need to keep in mind that it is just as important that our programs be readable by humans as it is that they be correctly executed by computers.