I'm filling out a programming quiz and run into that old standby, reverse the words of a string in place in linear time. I've done this one at the whiteboard too many times so I did a quick Google search: lots of references to the problem but no reusable code*. So, I write my own. To save some other person the trouble, I'm posting it here. Also, I'm hoping to get mail from someone pointing out how I could do it better. Good advice is a precious commodity.
* I am a big advocate of code reuse. I can't stand to see cut&paste coding and NIH (not invented here) syndrome drives me nuts.
#include <ctype.h> /* * In C++ just use std::swap. This macro uses the XOR hack to avoid * the stack and a temporary. */ #define SWAP(a,b) \ do { (*a) ^= (*b); (*b) ^= (*a); (*a) ^= (*b); } while (0) /* * Although wordrev could be written using strtok(3), many * implementation of strtok run in quadratic time with respect to the * token string and strtok only expresses membership in the token * class rather than non-membership. I contrast, most implementations * optimize isspace(3) very well usually using a table-driven macro * for contant time performance even avoiding the function call cost. * * If wordrev proves to be a hotspot, then unroll the loop: * * switch (b - a) { * case 0: case 1: break; * case 2: SWAP(a[0], a[1]); break; * case 3: SWAP(a[0], a[2]); break; * case 4: SWAP(a[0], a[3]); SWAP(a[1], a[2]); break; * case 5: SWAP(a[0], a[4]); SWAP(a[1], a[3]); break; * default: // use the loop below * } * * I prefer not to unroll it unless a profiler indicates that it * matters and that the unrolling makes a difference. */ int wordrev (char* s, int len) { char* m; /* word boundary marker */ if (! s) return 0; /* protect against a null pointer */ if (len < 0) return 0; /* nonsense argument */ m = s; for (;;) { const char* X = s + len; /* end of search space */ char* a, *b; /* pointers for reversing word */ while (m < X && *m && isspace(*m)) ++m; /* advance m to start of next word */ a = m; /* word start */ while (m < X && *m && ! isspace(*m)) ++m; /* advance m to next word break */ if (m == a) break; // EOS b = m - 1; /* word finish, skipping the space */ for ( ; a < b; a++, --b) SWAP(a, b); } return m - s; }
No comments:
Post a Comment