The Doc Dialer, Part 2: A Browser Independent Version: Searching for A Name | WebReference

The Doc Dialer, Part 2: A Browser Independent Version: Searching for A Name


The Doc Dialer, Part 2: A Browser Independent Version

Searching for A Name

The function verifyNewName() takes two parameters: a name and an extension number. It verifies that there is no identical name-extension pair in the trie data structure:


function verifyNewName(checkNewName, phoneExt) {
  currentTrie = tree;
  checkNewName = checkNewName.toUpperCase();
  for (var i = 0; i // (The two lines above should be joined as one line.
  // They have been split for formatting purposes.)
	pushOneLevel(digit);
  }
  return checkLeafRecord(checkNewName, phoneExt);
}

As any other search in the trie data structure, we begin at the top object:

currentTrie = tree;

We then convert the name to upper case for matching purposes:

checkNewName = checkNewName.toUpperCase();

We then loop over all the name's characters, computing the digit corresponding to each character, and descending down the trie data structure according to the digit value at every level:

for (var i = 0; i 

Notice that the function pushOneLevel() does not create new objects, it just goes deeper in the hierarchy, as far as it can:

function pushOneLevel(digit) {
  if (currentTrie[digit]) {
    currentTrie = currentTrie[digit];
  }
}

Once we at the bottom of the trie data structure, we need to go over the link list in index 1. The function checkLeafRecord() takes two parameters: the name and the extension:


function checkLeafRecord(newNameToCheck, phoneExtToCheck) {
  var prevNamePtr, nextNamePtr;
  var nextNamePtr = currentTrie[1];
  if (!nextNamePtr) {
    return false;
  }
  else {
    while (nextNamePtr) {
	  prevNamePtr = nextNamePtr;
	  nextNamePtr = nextNamePtr.next;
	  if (empList[prevNamePtr.empIndex].toUpperCase() ==
      newNameToCheck && empPhone[prevNamePtr.empIndex] ==
      phoneExtToCheck) {
		  return true;
	  }
	}
	return false;
  }
}

First, we check if element at index 1 is null. If it is, we return immediately from the function because we can conclude there are no duplicates in the trie data structure:

var prevNamePtr, nextNamePtr;
var nextNamePtr = currentTrie[1];
if (!nextNamePtr) {
  return false;
}

If the head of the link list is not null, we go over the link list and compare the name (in upper case) and the extension of each record with the name and the extension of the new one. Notice that all names are stored in the empList array. The trie data structure holds just indices into this array. If there is a match we return true (a duplicate has been found):

while (nextNamePtr) {
  prevNamePtr = nextNamePtr;
  nextNamePtr = nextNamePtr.next;
  if (empList[prevNamePtr.empIndex].toUpperCase() == newNameToCheck &&
            empPhone[prevNamePtr.empIndex] == phoneExtToCheck) {
    return true;
  }
}

When we reach the bottom of the function without returning to the caller function, we can conclude that there are no duplicates and return false.

Next: How to update the display

http://www.internet.com

Produced by Yehuda Shiran and Tomer Shiran

Created: February 28, 2000
Revised: April 26, 2000

URL: http://www.webreference.com/js/column58/7.html