Searching for Insertion Point

The function addToTrie() coordinates the addition of new entries. It accepts two parameters. The newEntry parameter is the new person's name. This parameter is a concatenation between the first name and the last name of the new person. The second parameter, empIndex, is the sequence number of the new entry in the empList array. Here is the function:

function addToTrie(newEntry, empIndex) {
  currentTrie = tree;
  newEntry = newEntry.toUpperCase();
  for (var i = 0; i < newEntry.length; i++) {
    var digit = parseInt(keyMap[newEntry.charAt(i)]);
    descendOneLevel(digit);
  }
  addNameToLeafRecord(empIndex);
}

The function begins with setting the global variable currentTree. This variable points to the current location in the trie data structure that the algorithm has advanced to. Each operation on the trie data structure starts at the top level array of the structure:

currentTrie = tree;

Although we protect the user's entries regarding lower vs upper case, all comparisons are done in upper case:

newEntry = newEntry.toUpperCase();

The core of the algorithm is to go over the name characters and to descend down the trie data structure according these characters, converted into numeric entries of the phone keypad. Each digit is computed as:

var digit = parseInt(keyMap[newEntry.charAt(i)]);

The keyMap array is associative. We isolate each character i by the charAt(i) method and then find the corresponding phone key through the keyMap array. Finally, we also descend:

descendOneLevel(digit);

This function tries to descend to the corresponding array element, and creates a new record if one does not exist:

function descendOneLevel(digit) {
  if (!currentTrie[digit]) {
    var tmpArray = new Array(10);
	currentTrie[digit] = tmpArray;
	currentTrie = tmpArray;
  } 
  else {tmpArrayrentTrie = currentTrie[digit];
  }
}

Notice how we grow the data structure. If the pointer currentTrie[digit] is null (!currentTrie[digit]) we create a new 10-element array object:

var tmpArray = new Array(10);

which we link back to the parent array:

currentTrie[digit] = tmpArray;

And finally we also advance the global variable currentTrie:

currentTrie = tmpArrya;

If a pointer to the child array does exist, we just descend along:

currentTrie = currentTrie[digit];

Once we are done descending we need to place the new entry in the data structure:

addNameToLeafRecord(empIndex);

We'll cover this function on the next page.

Next: How to insert a new record