How to manipulate sorted lists of objects

Prerequisites

Introduction

In this section, we'll take a look at how to manipulate sorted lists of objects. We shall assume that the domain of the elements in the list is totally ordered, so that any two objects are comparable. If that is the case, we only need one function less that returns a true value if and only if its first argument is strictly smaller than its second argument. From this function, we can determine whether two objects a and b are equal, since if neither a is less than b nor b is less than a then a and b must be equal. If the domain had not been totally ordered, this would not necessarily have been true.

An alternative to less would have been less_or_equal, in which case two objects a and b would be equal if and only if both a is less than or equal to b and b is less than or equal to a. The choice is a matter of taste.

Difference compared to unsorted lists

As we shall see, we will be able to use similar tricks that we used in the unsorted case in order to make the code more readable and maintainable. The main difference is that since the list is sorted, we can stop our search when we find an object on the list that is greater than or equal to the one we are looking for, as opposed to having to scan until the end of the list.

Another difference is that, while insert in the unsorted case did not care exactly where the object was inserted, in the sorted case, it must be inserted in exactly one place. We must make sure that the sorted version of find stops at this exact position in the case where the element is not on the list.

The header file

The header file is similar to the one for the unsorted case:

  #ifndef SLSET_H
  #define SLSET_H

  /* We use unsorted linked lists to implement sets of elements,
     that can handle only equality */

  struct slset;
  typedef struct slset *slset;

  /* create an empty slset */
  extern slset slset_create(int (*less)(void *, void *));

  /* return a true value iff the element is a member of the slset */
  extern int slset_member(slset l, void *element);

  /* insert an element into an slset.  The element must not already
     be a member of the slset. */
  extern void slset_insert(slset l, void *element);

  /* delete an element from an slset.  The element must be
     a member of the slset. */
  extern void slset_delete(slset l, void *element);

  #endif

Notice that we have replaced equal by less. Otherwise, this header file is identical to that of ulset.

The implementation file

We can use the exact same structure definitions as in the unsorted case, except that we should rename the equal field to less and the ulset structure to slset:

  struct slset
  {
    int (*less)(void *, void *);
    list elements;
  };

If we are careful, we should have to make only minor modifications to the interface functions compared to the unsorted case. The only function needing major revision would be the find function. Recall that in the unsorted case, the find function returns pointer to a list (not a pointer to a cell). Dereferencing that pointer gives the information about the presence of the element we were looking for. If dereferencing the pointer gives NULL, then the element is not in the list. If not, then the element is present in the cell obtained by dereferencing the pointer. Here is the find function for the unsorted case:

  list *
  find(list *lp, void *e, int (*equal)(void *, void *))
  {
    for(; *lp && !equal((*lp) -> element, e); lp = &((*lp) -> next))
     ;
    return lp;
  }

For the sorted case, we simply replace that with:

  list *
  find(list *lp, void *e, int (*less)(void *, void *))
  {
    for(; *lp && less((*lp) -> element, e); lp = &((*lp) -> next))
     ;
    return lp;
  }

We loop until either the list is exhausted, meaning that the element we were looking for was greater than or equal to all the elements of the list, or until we found a position such that the element of that position is either greater than or equal to the element we are looking for. This is exactly what we want. If this version of find is called with an element already on the list, then dereferencing the pointer gives a non-NULL value equal to the one we are looking for. If called with an element that is not on the list, find will return a pointer to a place where that element should be inserted.

Now, all we have to do is update the interface functions to take advantage of this new version of find. Here is the entire implementation file:

  #include "slset.h"
  #include "list.h"
  #include < assert.h>
  #include < stdlib.h>

  struct slset
  {
    int (*less)(void *, void *);
    list elements;
  };

  slset
  slset_create(int (*less(void *, void *)))
  {
    slset l = malloc(sizeof(struct slset));
    l -> elements = NULL;
    l -> less = less;
    return l;
  }

  static list *
  find(list *lp, void *e, int (*less)(void *, void *))
  {
    for(; *lp && less((*lp) -> element, e); lp = &((*lp) -> next))
     ;
    return lp;
  }

  static int 
  equal(void *e1, void *e2, int (*less)(void *, void *))
  {
    return !less(e1, e2) && !less(e2, e1);
  }

  static int
  points_to(list *lp, void *e, int (*less)(void *, void *))
  {
    return *lp && equal((*lp) -> element, element, l -> less);
  }

  int
  slset_member(slset l, void *element)
  {
    list *lp = find(&(l -> elements), element, l -> less);
    return points_to(lp, element, l -> less);
  }

  void
  slset_insert(slset l, void *element)
  {
    list *lp = find(&(l -> elements), element, l -> less);
    assert(!points_to(lp, element, l -> less));
    *lp = cons(element, *lp);
  }

  void
  slset_delete(slset l, void *element)
  {
    list *lp = find(&(l -> elements), element, l -> less);
    assert(points_to(lp, element, l -> less));
    *lp = cdr_and_free(*lp);
  }

Here, we have introduced two new local functions, equal and points_to. Given two elements and a less function, the equal function return a true value if and only if the two elements are equal, i.e. neither one is less than the other. Given a pointer to a list, an element, and a less function, the points_to function returns a true value if and only if dereferencing the pointer gives a cell containing an element equal to the one passed as argument. This becomes exactly the condition to test in the interface functions.