Initialization

Initialization of the trie data structure includes loading the eight US presidents and setting the printList array to false. Here is the function that loads the predefined names:

function initializePresidents() {
  for (var i = 1; i <= lastEmp; i++) {
    var newName = empList[i];
    var firstName = extractFirstName(newName);
    var lastName = extractLastName(newName);
    var phoneExt = empPhone[i];
    addToTrie(firstName + lastName, i);
    addToTrie(lastName + firstName, i);
  }
}

For each name in the empList array, we extract the first name and last name and then we add to the trie data structure strings: first name followed by last name and last name followed by first name (without blanks in between). First, let's look at the extractFirstName() function:

function extractFirstName(empName) {
  if (nameCode == 1 && versionCode >= 5.5) {
    var regExp = /(\w+)\s*(\w+)/g;
    return empName.replace(regExp, matchFirstName);
  }
  else {
    blankPos = empName.indexOf(" ");
    firstName = empName.substr(0, blankPos);
    return firstName;
  }
}

This function exemplifies use of Internet Explorer 5.5, as we explained in Column 57. We first assign a regular expression which looks for a combination of a word, followed by blanks, and then another word:

var regExp = /(\w+)\s*(\w+)/g;

We then call the replace() method that calls a matching function, matchFirstName(). It simply retureturns first match out of the regular expression, subMatch1:

function matchFirstName(matchedString, subMatch1, subMatch2,
  matchPos, source) {
  // (The two lines above should be joined as one line.
  // They have been split for formatting purposes.)
  return (subMatch1)
}

For those without Internet Explorer 5.5, we just find the blank position in the name, and then use the substr() method to extract the first name string.

Similarly, to extract the last name, we call extractLastName():

function extractLastName(empName) {
  if (nameCode == 1 && versionCode >= 5.5) {
    var regExp = /(\w+)\s*(\w+)/g;
    return empName.replace(regExp, matchLastName);
  }
  else {
    blankPos = empName.indexOf(" ");
    lastName = empName.substr(blankPos + 1, empName.length -
    blankPos);
  // (The two lines above should be joined as one line.
  // They have been split for formatting purposes.)
    return lastName;
  }
}

Here we used the matchLastName() function in Internet Explorer 5.5:

function matchLastName(matchedString, subMatch1, subMatch2,
  matchPos, source) {
  // (The two lines above should be joined as one line.
  // They have been split for formatting purposes.)
  return (subMatch2);
}

After we extract the first and last names we call the addToTrie() method, one time to add the first name followed by the last name, and a second time to add the last name followed by the first name:

addToTrie(firstName + lastName, i);
addToTrie(lastName + firstName, i);

Besides the name as the first parameter, we send to addToTrie() the sequential number of the entry as a second parameter. We store these indices in the trie data structure, instead of the name itself.

Next: How to find the insertion point