Next: , Previous: Darray indexing, Up: Dynamic arrays


12.5 Searching and sorting in a darray

Searching and sorting implies an ability to compare data values. Since a darray can store data of any type, the user must supply a comparison function.

— Function pointer: Da_compare_f int (*) (const void *left, const void *right, void *args)

The type of a function pointer used to compare objects in a darray. The function is passed the addresses of two objects, left and right, as well as a user-supplied pointer to parameters, args. (The parameters could be used, for example, for modifying the behaviour of the comparison.) The function should return zero if left and right are equal, a negative value if left is less than right, and a positive value if left is greater than right.

— Function: ssize_t da_find (const Darray *da, ssize_t last_offset, const void *target, Da_compare_f cmp, void *cmp_args)

Finds the first index after last_offset in da of an element comparing equal (with cmp) to target. Returns -1 if no such element exists. cmp_args is passed as the last argument to cmp.

— Function: ssize_t da_rfind (const Darray *da, ssize_t last_offset, const void *target, Da_compare_f cmp, void *cmp_args)

Finds the last index before last_offset in da of an element comparing equal (with cmp) to target. Returns -1 if no such element exists. cmp_args is passed as the last argument to cmp.

— Function: ssize_t da_bsearch (const Darray *da, const void *target, Da_compare_f cmp, void *cmp_args)
— Function: ssize_t da_bsearch_lim (const Darray *da, ssize_t lower, ssize_t upper, const void *target, Da_compare_f cmp, void *cmp_args)
— Function: ssize_t da_bsearch_index (const Darray *da, const void *target, Da_compare_f cmp, void *cmp_args)

da_bsearch’ finds the index in da of an element comparing equal (with cmp) to target. Returns -1 if no such element exists. cmp_args is passed as the last argument to cmp. da should be sorted in ascending order according to cmp.

da_bsearch_lim’ functions identically, with the exception that only those elements with an index between lower and upper (inclusive) are considered; indeed, elements outside these bounds need not be in sorted order. lower and upper must be both non-negative and less than the length of da; lower may not be greater than upper.

da_bsearch_index’ functions similarly to ‘da_bsearch’, but attaches a different meaning to the return value. As before, a non-negative return indicates the index of the found object. A negative return indicates that the object was not found, but it also encodes the index at which such an object should be inserted so that da remain in sorted order. Specifically, if the negative value x is returned, target can be inserted at index -(x + 1).1 Typical usage would be as follows:

          index = da_bsearch_index (da, obj, cmp, 0);
          if (index < 0)
          {
              i = -(index + 1);
              da_insert (da, index, obj);
          }
          /* Now INDEX is the index in DA of OBJ. */
— Function: void da_sort (Darray *da, Da_compare_f cmp, void *cmp_args)

Sorts da in ascending order, performing comparisons by cmp. cmp_args is passed as the last argument to cmp. (As of the current release, C. A. R. Hoare's Quicksort algorithm is used, but this may change at a later date.)

— Function: void da_reheap (Darray *da, Da_compare_f cmp, void *cmp_args)

`Reheaps' da using the comparison function cmp. cmp_args is passed as the last argument to cmp.

I use `heap' in the sense of Software Tools in Pascal (Brian W. Kernighan and P. J. Plauger, 1981, Addison-Wesley, Reading MA): a container with the properties that its smallest entry may be found immediately, and a new element can be put into the proper position in the heap in time O(log n), where n is the number of elements. A heap is conceptually a maximally binary tree where each node is less than or equal to its children. ‘da_reheap’ assumes that a heap is represented as an array of elements in which the children of element k are stored at positions 2k + 1 and 2k + 2. The smallest element is therefore the one at position 0.

So, ‘da_reheap’ assumes that da is a heap (as defined above) except that the zeroth element is not necessarily in the right place. ‘da_reheap’ therefore moves the zeroth element into the right place


Footnotes

[1] The properties of this transformation are worth investigating briefly. Note first that if y = -(x + 1), then x = -(y + 1). Secondly, on a two's complement machine, this calculation can be performed with a one's complement negation. Thirdly, and most importantly, on a sign/magnitude or one's complement machine, this calculation is accurate only on values less than ‘SSIZE_MAX’.