OT: CS education gone wrong (Was: Re: TDD is BS?)

Adam D. Ruppe destructionator at gmail.com
Fri Jun 21 16:20:39 PDT 2013


On Friday, 21 June 2013 at 22:35:55 UTC, Andrei Alexandrescu 
wrote:
> Post it and I'll destroy it.


inout(char)* mystrstr(inout(char)* haystack, const(char*) needle) 
{
     assert(haystack !is null);

     if(needle is null)
         return haystack;

     const(char)* where = needle;
     inout(char)* gotit;

     while(*haystack) {
         if(*haystack == *where) {
             if(gotit is null)
                 gotit = haystack; // store where the match started
             where++;
             haystack++;
             if(*where == 0)
                 return gotit;
         } else {
             // if we were in the middle of a match, we'll want to
             // check the current character again so only advance 
if
             // we're at the beginning
             if(gotit is null)
                 haystack++;
             else {
                 // partial match, but not complete so no good
                 // start over, including the current *haystack
                 where = needle;
                 gotit = null;
             }
         }
     }

     return null;
}


unittest {
     void test(string haystack, string needle, size_t line = 
__LINE__) {
         import core.stdc.string;
         import std.conv;

         // .ptr is fine because the test uses all string 
literals, which are 0 terminated automatically
         assert(strstr(haystack.ptr, needle.ptr) is 
mystrstr(haystack.ptr, needle.ptr), to!string(line));
     }

     test("foobar", "f");
     test("foobar", "ob");
     test("foobar", "o");
     test("foobar", "a");
     test("foobar", "ar");
     test("foobar", "ea");

     test("bedtime bedazzled!", "beda");
}




I've heard of Boyer-Moore but don't actually know it, so I'd have 
to look it up! The brute force loop is simple enough though 
without needing a great deal of thought, though my first run 
through did actually fail the unittest, since I neglected the 
commented section in the else{} part. So if I was doing it on a 
whiteboard, (or didn't immediately use "foo" as a test variable, 
with the repeated o) I might not have actually caught that!


More information about the Digitalmars-d mailing list