You should be familiar with the concept of [Equivalence Partitioning](/codex/equivalence-partitioning).
When the possible set of values involves multiple arguments, we need to break into equivalence classes based on each of those arguments. In that case we may have a series of partitions resulting in a classification tree. Each leaf of the tree will be its own equivalence class.
### Worked example
This is an advanced example where the input domain is the set of arrays. We will study the OpenZeppelin function for finding the upper bound in a sorted array.
-- CODE language-solidity --
/**
* @dev Searches a sorted `array` and returns the first index that contains
* a value greater or equal to `element`. If no such index exists (i.e. all
* values in the array are strictly less than `element`), the array length is
* returned. Time complexity O(log n).
*
* `array` is expected to be sorted in ascending order, and to contain no
* repeated elements.
*/
function findUpperBound(uint256[] storage array, uint256 element) internal view returns (uint256) {
if (array.length == 0) {
return 0;
}
uint256 low = 0;
uint256 high = array.length;
while (low < high) {
uint256 mid = Math.average(low, high);
// Note that mid will always be strictly less than high (i.e. it will be a valid array index)
// because Math.average rounds down (it does integer division with truncation).
if (array[mid] > element) {
high = mid;
} else {
low = mid + 1;
}
}
// At this point `low` is the exclusive upper bound. We will return the inclusive upper bound.
if (low > 0 && array[low - 1] == element) {
return low - 1;
} else {
return low;
}
}
The function has two arguments: the array and the element. We can use them to set up a classification tree that first looks at the size and type of the array at the first level and looks at the element on the second level:
- Empty array
- Array with a single element `x`
- `x = element`
- `x` < `element`
- `x` > `element`
- Unsorted array (invalid input)
- Sorted array of size ≥ 2
- `element` equal to an element in the array
- `element` larger than smallest element in array, smallest than largest element but not present in array
- `element` larger than all elements in the array
- `element` smaller than all elements in the array.
The resulting Equivalence Classes can be used for testing directly.
