Talking Through A Coding Task

interval.c

/* interval.c
**
** From a coding interview I (OhMeadhbh@gmail.com)
** recently participated in:
**
** Write a function that finds the intersection of two
** intervals. So if you had the intervals 2 - 8 and 5 -
** 12, the intersection would be 5 - 8. */

/* Let's start by defining the function that will
** calculate the interval. Something like:
**
**   tInterval intersection( tInterval a, tInterval b);
**
** But we have to define the tInterval type first: */

typedef struct {
  int begin;
  int end;
} tInterval;

/* But instead of using the function signature above,
** I'm going to do the following: */

int intersection_test \
  ( tInterval a, tInterval b, tInterval * n );

/* I changed the intersection signature to take two
** tInterval's plus a pointer to a tInterval and return
** a status code as an int. Why do this? Old-skool C
** programmers would probably just pass three pointers:
** two for the inputs and one for the result. But modern
** C can reasonably efficiently copy structs to the
** stack and the structs we're copying aren't huge. But
** the benefits of returning a status int will be more
** obvious later on.
**
** The benefits of passing two structs on the stack are:
**   a. It enforces the read-only nature of the inputs
**      better than const can. (Badly written code can
**      evade const restrictions, but the only struct
**      the code knows about is the one that's copied
**      to the stack when the function is called.)
**   b. There are fewer pointers. After decades of
**      denying the simple truth, I've come around to
**      the realization that even smart programmers can
**      do stupid things with pointers. If you don't
**      need them, don't use them.
**
** But in this instance, there are a couple drawbacks to
** mixing structs with pointers to structs as
** parameters:
**   a. You're mixing pointers with direct references.
**      It *might* get confusing when some elements are
**      accessed via dots and others by arrows.
**   b. If we change the code and make tInterval some
**      huge data structure, it could become inefficient
**      to keep copying it to the stack. (But honestly,
**      worrying about this sounds like a premature
**      optimization.) */

/* I'm going to define three different intersection
** routines here: one that does nothing and is used for
** testing, one that is a naive attempt and the last
** that is what you could have figured out if (like me)
** you didn't just rush into coding. */

int intersection_naive \
  ( tInterval a, tInterval b, tInterval * n );
int intersection_better \
  ( tInterval a, tInterval b, tInterval * n );

/* To make it simple, we'll default to using the test
** implementation, but you can use a command line
** argument to select the naive or better
** implementations (like so):
**
**   gcc -o interval -DNS_NAIVE interval.c
**     or
**   gcc -o interval -DNS_BETTER interval.c
**
** And here we test whether these macros are defined
** at compile time and define a macro to be used like
** a function in the main section of the code. */

#if defined( NS_BETTER )
  #define intersection intersection_better
#elif defined( NS_NAIVE )
  #define intersection intersection_naive
#else
  #define intersection intersection_test
#endif

/* So you remember we said we were returning a status
** value from the call to intersection_<whatever>() ?
** I'm going to define three status values:
**
**  S_NOERR    - no error occurred
**  S_BADPARAM - you passed a null pointer
**  S_NONTERS  - the two inputs don't intersect
**
** Why do this? Mostly 'cause we didn't have a detailed
** discussion about whether or not the intervals were
** open or closed (includes or does not include the
** points at the beginning and end of the interval.) If
** they're closed, it means they include the boundary
** points. And if they're closed and you're given the
** interval [0,0] and [-1,1], then the proper response
** is [0,0], which is what I was going to initially use
** as the "no interval" response. Whoops. */

#define S_NOERR     (0)
#define S_BADPARAM  (1)
#define S_NONTERS   (2)

/* And at this point you may be asking yourself why
** we're using a pound-define instead of an enum. Thirty
** years ago there were C compilers that didn't quite
** handle enums properly. I heard one old C programmer
** say it looked too much like Pascal. Modern C
** compilers *should* handle enums at least as well as
** pound-defines for this use case. So the simple answer
** is: inertia.
**
** But if you wanted to use an enum for the return code,
** you could do something like this. Don't forget to
** change the intersection functions to return the enum
** instead of an int, though:
**
**  typedef                                      \
**    enum { S_NOERR, S_BADPARAM, S_NONTERS }    \
**    tStatus;
**
**  tStatus intersection_test                     \
**    ( tInterval a, tInterval b, tInterval * n );
**  tStatus intersection_naive                    \
**    ( tInterval a, tInterval b, tInterval * n );
**  tStatus intersection_better                   \
**    ( tInterval a, tInterval b, tInterval * n );
**
** But... if you're going to use pound-defines, it's
** considered good practice to put parens around the
** constants to avoid problems if they're used
** unhygenically. */

/* I don't know about you, but I'm a fan of Test-First
** development. So let's think about some test
** data. This should also get us to think about things
** like "are the intervals we're given really open or
** closed?" -- This is the magic of test first. The
** sooner you can write code (any code) the sooner you
** may find you have open questions about the
** requirements. And since we all live in an agile
** coding utopia, the cost of redesign is low. (The joke
** here is that's not always the case, so if you can
** detect design flaws *BEFORE* you start coding large
** parts of your program, you don't have to go back to
** to recode them.)
**
** But let's define some test data. First, here's a
** typedef for the test fixtures: two input intervals,
** an expected status return code and the resulting
** intersection. */

typedef struct {
  tInterval a;
  tInterval b;
  int expected_status;
  tInterval n;
} tFixture;

/* And here's the test data: */
  
tFixture fixtures [] = {
  /* Test for the simple identity test case */
  { { 0, 0 }, { 0,  0 }, S_NOERR,    { 0, 0 } },

  /* Test that the interval is closed */
  { { 0, 5 }, { 5, 10 }, S_NOERR,    { 5, 5 } },

  /* Same thing, but flip the parameters*/
  { { 5, 10 },{ 5,  5},  S_NOERR,    { 5, 5 } },

  /* What if one interval is just a point? */
  { { 5, 10 }, { 5, 5 }, S_NOERR,    { 5, 5 } },
  { { 5, 5 }, { 5, 10 }, S_NOERR,    { 5, 5 } },

  /* Here's a simple interval */
  { { 0, 5 }, { 2,  7 }, S_NOERR,    { 2, 5 } },
  { { 2, 7 }, { 0,  5 }, S_NOERR,    { 2, 5 } },

  /* What if there's no intersection? */
  { { 0, 4 }, { 5, 10 }, S_NONTERS,  { 0, 0 } },
  { { 5, 10 }, { 0, 4 }, S_NONTERS,  { 0, 0 } },

  /* S_NONTERS creates meaningless results */
  { { 0, 4 }, { 5, 10 }, S_NONTERS,  { 1, 1 } },
  { { 5, 10 }, { 0, 4 }, S_NONTERS,  { 1, 1 } },

  /* What if one interval encloses the other? */
  { { 0, 9 }, { 3,  7 }, S_NOERR,    { 3, 7 } },
  { { 3, 7 }, { 0,  9 }, S_NOERR,    { 3, 7 } },

  /* What if the start is greater than the end ?*/
  { { 9, 0 }, { 3,  7 }, S_BADPARAM, { 0, 0 } },
  { { 0, 9 }, { 7,  3 }, S_BADPARAM, { 1, 1 } },
  { { 9, 0 }, { 7,  3 }, S_BADPARAM, { 2, 2 } }
};

/* Don't forget to update this if you add or remove
** test fixtures. */

#define FIXTURES_COUNT 16

/* A couple things I realized about the requirements
** when coming up with the test fixtures:
**   a. I'm definitely assuming we're dealing with
**      closed intervals.
**   b. The returned interval is meaningless unless the
**      the return value is S_NOERR. */

/* I guess we can create a main() routine that acts as
** a test driver. */

#include <stdio.h>

int main() {
  int i;
  int success = 0, fail = 0, total = 0;
  int status;
  tInterval result;

  /* First, let's check that giving a null pointer to
  ** the intersection() function results in a
  ** S_BADPARAM */

  status = intersection(
    fixtures[ 0 ].a,
    fixtures[ 0 ].b,
    ( tInterval * ) NULL );

  if( S_BADPARAM == status ) {
    printf( "TEST 1 (NULL PTR): success\n" );
    success++;
  } else {
    printf( "TEST 1 (NULL PTR): failed\n" );
    fail++;
  }

  total++;
  
  for( i = 0; i < FIXTURES_COUNT; i++ ) {
    result.begin = 32767;
    result.end = 16384;
    
    status = intersection(
      fixtures[ i ].a,
      fixtures[ i ].b,
      & result );

    total++;

    /* If the expected status isn't the returned status
    ** then it's a fail. */

    if( fixtures[ i ].expected_status != status ) {
      printf( "TEST %d: failed\n", i + 2 );
      fail++;
    } else {

      /* If the returned status (which is equal to the
      ** expected status at this point) isn't S_NOERR,
      ** we MUST NOT check the returned values */
      
      if( S_NOERR != status ) {
        printf( "TEST %d: success\n", i + 2 );
        success++;        
      } else {

        /* Now we just test that the beginning and end
        ** of the returned interval are the same as
        ** the expected values in the test fixture */

        if( ( fixtures[ i ].n.begin == result.begin ) &&
            ( fixtures[ i ].n.end == result.end ) ) {
          printf( "TEST %d: success\n", i + 2);
          success++;        
        } else {
          printf( "TEST %d: failed\n", i + 2);
          fail++;
        }
      }
    }
  }

  printf( "Results: %d total, %d fail, %d success\n",
          total, fail, success );

  return( 0 );
}

/* And here's a testing mock-up of the intersection
** function. I define things like this frequently so
** I can get a compiled, running program as fast as
** possible. In the modern era, a simple way to disprove
** your assertions that the test fixtures are correct
** is to try to compile the program at this point. If it
** doesn't compile, it may be because you goofed on
** designing the fixtures. Learning this early has
** saved my bacon several times in the past. So yes, it
** will take a little bit more time to do it this way,
** but in the long run it'll pay for itself when you
** don't have to redesign your fixtures and re-code your
** test driver.
**
** And if it compiles, it doesn't mean it's correct (of
** course.) YMMV. Also, I trust you're an adult. If you
** think it's easier to rush forward with implementing
** things, that's fine too. If you're wrong, I'm not
** going to be there to tease you about it. If you're
** wrong, try to think about why you thought it was a
** good idea to do what you did. Maybe you were right
** to think it was a good idea generally and you were
** just wrong this one time. You do you.
**
** Anyway, here's the simplest implementation of the
** test function that will let the program compile. */

#if !defined( NS_BETTER ) && !defined( NS_NAIVE )
int intersection_test \
  ( tInterval a, tInterval b, tInterval * n ) {
  return S_NOERR;
}
#endif

/* Now let's do a naive implementation of the interface
** we defined and proved compiles. Compile with the
** -DNS_NAIVE command line option to use this function.
** Or if you have make installed,
**
**   CFLAGS=-DNS_NAIVE make interval
**
** will probably work.
*/

#if defined( NS_NAIVE )
int intersection_naive \
  ( tInterval a, tInterval b, tInterval * n ) {

  /* Start by checking if we're passed a null pointer */
  if( ( tInterval * ) NULL == n ) {
    return S_BADPARAM;
  }

  /* Interval begin values should be less than or equal
  ** to interval end values. */
  if( ( a.end < a.begin ) || ( b.end < b.begin ) ) {
    return S_BADPARAM;
  }

  /* Do the two intervals not intersect? */
  if( ( a.end < b.begin ) || ( b.end < a.begin ) ) {
    return S_NONTERS;
  }
  
  /* Now, let's calculate the result */

  /* does b start before a? */
  if( b.begin <= a.begin ) {
    n->begin = a.begin;
  } else {
    n->begin = b.begin;
  }

  /* does b end before a? */
  if( a.end <= b.end ) {
    n->end = a.end;
  } else {
    n->end = b.end;
    
  }
  return S_NOERR;
}
#endif

/* And here is an implementation that's a bit better.
** It turns out that the intersection of two overlapping
** intervals is [MAX(begin), MIN(end)]. This avoids all
** the if clauses in the naive implementation and makes
** a slightly easier to read function.
**
** Use these command to build and test it:
**
**   touch interval.c
**   CFLAGS=-DNS_BETTER make interval && ./interval
*/

#if defined( NS_BETTER )
int intersection_better \
  ( tInterval a, tInterval b, tInterval * n ) {

  /* Start by checking if we're passed a null pointer */
  if( ( tInterval * ) NULL == n ) {
    return S_BADPARAM;
  }

  /* Interval begin values should be less than or equal
  ** to interval end values. */
  if( ( a.end < a.begin ) || ( b.end < b.begin ) ) {
    return S_BADPARAM;
  }

  /* Do the two intervals intersect? */
  if( ( a.end < b.begin ) || ( b.end < a.begin ) ) {
    return S_NONTERS;
  }
  
  /* Now, let's calculate the result */
  n->begin = a.begin < b.begin ? b.begin : a.begin;
  n->end   = a.end < b.end ? a.end : b.end;
  
  return S_NOERR;
}
#endif

/* So what did we learn here? When I was stepping
** through this intersection, I had to be reminded that
** the intersection of two intervals was [MAX(begin),
** MIN(end)]. I went straight for a mostly correct, but
** difficult to read solution.
**
** Hopefully I convinced you it's not hard to do
** "test first," and showed one way you could set up a
** C program to conditionally compile various different
** implementations of a function interface. Advanced
** students might suspect it's just as easy to avoid
** using the macro to define the intersection() function
** and just conditionally compile one of three different
** versions of intersection(). Something like this:
**
**   #if defined( NS_BETTER )
**     tStatus intersection( ... ) {
**       ..Better version goes here ..
**     }
**   #elif defined( NS_NAIVE )
**     tStatus intersection( ... ) {
**       .. Naive version goes here ..
**     }
**   #else
**     tStatus intersection( ... ) {
**       .. Test version goes here ..
**     }
**   #endif
**
** This is the typical way people do this, but I think
** explicitly naming different versions of the
** implementation makes the code slightly easier to read
** (and more importantly, easier to debug.)
**
** I think I *could* have broken down things into
** functions a bit more. On reviewing the code, it seems
** the bits in the test driver would definitely be
** easier to read if I hid some of the details behind
** functions. I've started coding in windows that are
** 64 columns wide by 36 columns high (this is the same
** aspect ratio of a paperback book.) A decent rule of
** thumb is to build functions that fill no more than
** one page. But it's a recommendation, not a hard and
** fast rule and YMMV.
**
** And hopefully I've convinced you that writing
** comments in code can be a literary experience.
**
** -Cheers!
** -M
*/