JavaScript BST Test Code

JavaScript is Extendable

One of the nice things about Js is that we can extend it.

Js does not support our valued "compareTo" method so we'll extend Js and add the method. We are going to do this in a simple way which serves our purposes by extending "Object" -- in production we may consider something more sophisticated, e.g., extending specific types like String, Number, etc.

Object.prototype.equals = function(o2) {
	return this.valueOf() == o2;
}
	
Object.prototype.compareTo = function(o2) {
	let o1 = this.valueOf();
	if (o1.equals(o2)) return 0;
	if (o1 > o2) return 1;
	return -1;
}

class Customer {
    constructor(anId, aNm) {
		this.id = anId;
		this.name = aNm; }
    getName() { return this.name; }
	toString() { return `Customer -- name=${this.getName()}`; }
}

This code demonstrates how to use the sort and search functions, construct, load, traverse and search.


var c1, c2, c3, sortFct, searchFct;
const prn = console.log;
c1 = new Customer(1001, 'Asha');
c2 = new Customer(1002, 'Kofi');
c3 = new Customer(1003, 'Riya');
prn("\nc1: " + c1);
prn("c2: " + c2);
prn("c3: " + c3);

//Sorting Play
sortFct = (cust1, cust2) => cust1.getName().compareTo(cust2.getName());
prn("\nsortFct(c1, c2): " + sortFct(c1, c2));
prn("sortFct(c2, c1): " + sortFct(c2, c1));
prn("sortFct(c1, c1): " + sortFct(c1, c1));
/*
sortFct(c1, c2): 1
sortFct(c2, c1): -1
sortFct(c1, c1): 0
*/

//Searching Play
searchFct = (custName, cust) => custName.compareTo(cust.getName());
let key = 'Kofi';
prn(`\nkey: ${key}`);
prn("searchFct(key, c1): " + searchFct(key, c1));
prn("searchFct(key, c2): " + searchFct(key, c2));
prn("searchFct(key, c3): " + searchFct(key, c3));
/*
searchFct(key, c1): 0
searchFct(key, c2): 1
searchFct(key, c3): -1
*/

Function Play Output

c1: Asha (1001)
c2: Kofi (1002)
c3: Riya (1003)

sortFct(c1, c2): -1
sortFct(c2, c1): 1
sortFct(c1, c1): 0

key: Kofi
searchFct(key, c1): 1
searchFct(key, c2): 0
searchFct(key, c3): -1

Add one element to tree
Search for element with good key to make sure match is returned
Search for element with bad key to make sure null is returned

//Element type: Employee
//Key type: String (employee name)

var sortFct, searchFct, tree, c, key, match;
sortFct = (cust1, cust2) => cust1.getName().compareTo(cust2.getName());
searchFct = (custName, cust) => custName.compareTo(cust.getName());
tree = new BST.fromSortFctSearchFct(sortFct, searchFct);
c1 = new Customer('Asha');

//Add one element
tree.add(new Employee(101, "Asha"));

goodKey = 'Asha';
match = tree.search(goodKey);
prn(`Match for key "${goodKey}" (expecting match): ${match.toString()}`);

badKey = 'BadKeyHere';
match = tree.search(badKey);
prn(`Match for ${badKey} (expecting null): ${match}`);

Simple Test #1 Output

Match for key "Asha" (expecting match): Customer -- name=Asha
Match for key "BadKeyHere" (expecting null): null

//Element type: Employee
//Key type: String (employee name)

var c1, c2, c3, sortFct, searchFct, tree, key, match;
c1 = new Customer('Asha');
c2 = new Customer('Kofi');
c3 = new Customer('Riya');

//Constrct Tree
sortFct = (cust1, cust2) => cust1.getName().compareTo(cust2.getName());
searchFct = (custName, cust) => custName.compareTo(cust.getName());
tree = new BST.fromSortFctSearchFct(sortFct, searchFct);

//Add three elements
tree.add(new Employee(10, "Kofi"));
tree.add(new Employee(15, "Asha"));
tree.add(new Employee(20, "Riya"));

//Traverse and print while traversing
tree.visitInOrder(elem => prn(elem));
prn("");
tree.visitPreOrder(elem => prn(elem));
prn("");
tree.visitPostOrder(elem => prn(elem));
prn("");

key = 'Riya';
match = tree.search(key);
prn(`Match for ${key}: ${match}`);

Simple Test #2 Output

Asha (15)
Kofi (10)
Riya (20)

Kofi (10)
Asha (15)
Riya (20)

Asha (15)
Riya (20)
Kofi (10)

Match for 'Riya': Riya (20)