Unit Testing
Our First Program: Binary Search
Problem Statement: Write a function that consumes (1) a number to search for, and (2) an array of numbers sorted in ascending order. The function should produce true if the array contains the number and false if it does not.
Examples:
Type Signature:
search(5, [2, 5]) // produces true
search(4, [2, 5]) // produces false
search(7, [2, 5, 7]) // produces true
// search(v: number, a: number[]): boolean
function search(v, a) {
// TODO
}
function name
argument name and type
result type
You should write the type of functions in a comment. It helps plan your code.
Step 1: Recursive pattern
// search(v: number, a: number[]): boolean
function search(v, a) {
// Since the length of the array is unknown,
// we will recur on the length of a.
if (a.length === 0) {
// FILL
} else {
// FILL
}
}
Step 2: Fill in base-case
// search(v: number, a: number[]): boolean
function search(v, a) {
// Since the length of the array is unknown,
// we will recur on the length of a.
if (a.length === 0) {
return false;
} else {
// FILL
}
}
If the length of the array is 0, then there are no values in the array.
Step 4: Compare v to the middle element
// search(v: number, a: number[]): boolean
function search(v, a) {
// Since the length of the array is unknown,
// we will recur on the length of a.
if (a.length === 0) {
return false;
} else {
let mid = a.length / 2;
if (a[mid] === v) {
return true;
} else if (a[mid] > v) {
// FILL
} else /* a[mid] < v */ {
// FILL
}
}
}
Three cases: the value in the middle is equal
Step 5: Fill in recursive cases
// search(v: number, a: number[]): boolean
function search(v, a) {
// Since the length of the array is unknown,
// we will recur on the length of a.
if (a.length === 0) {
return false;
} else {
let mid = a.length / 2;
if (a[mid] === v) {
return true;
} else if (a[mid] > v) {
return search(v, a.slice(0, mid));
} else /* a[mid] < v */ {
return search(v, a.slice(mid + 1, a.length));
}
}
}
Note: a.slice method
Testing
// search(v: number, a: number[]): boolean
function search(v, a) {
// Since the length of the array is unknown,
// we will recur on the length of a.
if (a.length === 0) {
return false;
} else {
let mid = a.length / 2;
if (a[mid] === v) {
return true;
} else if (a[mid] > v) {
return search(v, a.slice(0, mid));
} else /* a[mid] < v */ {
return search(v, a.slice(mid + 1, a.length));
}
}
}
Do both these test cases work?
search(5, [2, 5])
search(5, [2, 5, 8])
JavaScript does not have integer division:
> 3 / 2
1.5
Bug fix
// search(v: number, a: number[]): boolean
function search(v, a) {
// Since the length of the array is unknown,
// we will recur on the length of a.
if (a.length === 0) {
return false;
} else {
let mid = Math.floor(a.length / 2);
if (a[mid] === v) {
return true;
} else if (a[mid] > v) {
return search(v, a.slice(0, mid));
} else /* a[mid] < v */ {
return search(v, a.slice(mid + 1, a.length));
}
}
}
Should we write more tests?
Why not? More is better, right?
Better question: do our tests cover all cases?
These tests now work
search(5, [2, 5])
search(5, [2, 5, 8])
Test Coverage
// search(v: number, a: number[]): boolean
function search(v, a) {
// Since the length of the array is unknown,
// we will recur on the length of a.
if (a.length === 0) {
return false;
} else {
let mid = Math.floor(a.length / 2);
if (a[mid] === v) {
return true;
} else if (a[mid] > v) {
return false;
} else /* a[mid] < v */ {
return false;
}
}
}
The problem is that the wrong lines of code are not executed.
Think of length-3 arrays that:
This implementation is obvious broken. But, these tests still work.
search(5, [2, 5])
search(5, [2, 5, 8])
search(5, [1, 2, 3]);
search(5, [1, 2, 5]);
(Some) Lessons About Testing
Testing with Ocelot
test("Empty list", function() {
let a = [];
assert(search(1, a) === false);
});
test("Mid match", function() {
let a = [1, 4, 5];
assert(search(4, a) === true);
});
test("Search upper half", function() {
let a = [1, 4, 5];
assert(search(5, a) === true);
assert(search(4.5, a) === false);
assert(search(7, a) === false);
});
Body of the test
This is an anonymous function. We will study them in detail very soon.
Name of the test
Assertions succeed only if provided a boolean expression that is true
Can have multiple assertions
Mini-Program: Comparing Arrays
Problem Statement: Write a function that consumes two arrays of numbers. The function should produce true if the arrays have exactly the same values in-order, and otherwise false.
Examples:
Type Signature:
arrayEqual([1, 2], [1, 2]) // produces true
arrayEqual([1, 2], [2, 1]) // produces false
arrayEqual([1, 2], [1, 2, 3]) // produces false
// arrayEqual(a1: number[], a2: number[]): boolean
function arrayEqual(a1, a2) {
// TODO
}
Mini-Program: Comparing Arrays
Why? It compares references to the arrays, rather than the contents of the arrays. We will explore this in detail in lecture 7.
Q: What properties should two arrays have, to declare that they are “equal”?
This will not work:
// arrayEqual(a1: number[], a2: number[]): boolean
function arrayEqual(a1, a2) {
return a1 === a2;
}
Mini-Program: Comparing Arrays
// arrayEqual(a1: number[], a2: number[]): boolean
function arrayEqual(a1, a2) {
if (a1.length !== a2.length) {
return false;
}
for (let i = 0; i< a1.length; ++i) {
if (a1[i] !== a2[i]) {
return false;
}
}
return true;
}
Q: What cases should we use to test this?
Mini-Program: Comparing Arrays
test("empty arrays", function() {
assert(arrayEqual([], []) == true);
});
test("unequal lengths", function() {
assert(arrayEqual([1, 2], [1, 2, 3]) == false);
assert(arrayEqual([2, 3], [1, 2, 3]) == false);
});
test("equal lengths", function() {
assert(arrayEqual([1, 2], [1, 2]) == true);
assert(arrayEqual([1, 2], [2, 3]) == false);
});
Mini-Program: rootMagnitude
Problem Statement: Write a function that consumes an array of numbers and produces an array of numbers. Each element of the output array should be the square-root of the corresponding element in the output array, but with the same sign.
Examples:
Type Signature:
rootMagnitude([4, 9]) // produces [2, 3]�rootMagnitude([0.16, 2.56]) // [0.4, 1.6]�rootMagnitude([-16, -25, -100]) // [-4, -5, -10]�rootMagnitude([4, -9]) // [2, -3]
// rootMagnitude(a: number[]): number[]
function rootMagnitude(a1, a2) {
// TODO
}
Warning: Math.sqrt produces NaN when applied to a negative number!
Attempt 1: update the array in-place
// rootMagnitude(a: number[]): number[]
function rootMagnitude(a) {
for (let i = 0; i < a.length; ++i) {
if (a[i] >= 0) {
a[i] = Math.sqrt(a[i]);
} else {
// TODO
}
}
return a;
}
test("Test rootMagnitude", function() {
assert(arrayEqual(rootMagnitude([4, 9]), [2, 3]));
assert(arrayEqual(rootMagnitude([16, 100]), [4, 10]));
});
Note: We use arrayEqual to compare the arrays.
We need a test case to execute this branch.
Attempt 1: update the array in-place
// rootMagnitude(a: number[]): number[]
function rootMagnitude(a) {
for (let i = 0; i < a.length; ++i) {
if (a[i] >= 0) {
a[i] = Math.sqrt(a[i]);
} else {
a[i] = a[i];
}
}
return a;
}
test("negative elements", function() {
assert(arrayEqual(rootMagnitude([4, -1]), [2, -1]));
});
The test passes! But, the implementation in obviously wrong.
The problem is we are updating the array in-place, so the input and output are identically.
Rule of thumb: do not update arrays in-place
Attempt 2: produce a new array
// rootMagnitude(a: number[]): number[]
function rootMagnitude(a) {
let b = [];
for (let i = 0; i < a.length; ++i) {
if (a[i] >= 0) {
b.push(Math.sqrt(a[i]));
} else {
b.push(-Math.sqrt(-a[i]));
}
}
return b;
}
test("negative elements", function() {
assert(arrayEqual(rootMagnitude([4, -1]), [2, -1]));
});
Note: .push method of arrays adds an element to the end. Arrays in JavaScript are similar to ArrayLists in Java.
(Some) Lessons About Testing