indexof.js

var indexof, indexofSub;

indexof = function(haystack, needle) {
        // Implementation?
    var hayLen, isCompleteMatch, needleLen, result, match;
    
    result = -1;
    match = '';
    hayLen = haystack['length'];
    needleLen = needle['length'];
    // this is the result when no loops occur
    // if both needle and haystack aren't string-typed, return -1
    if(typeof haystack !== 'string' || typeof needle !== 'string') {
        return -1;
    }
    // if the needle is bigger than the haystack, it has no index
    if(needleLen > hayLen) {
        return -1;
    }
    // if the needle is so small it resides at the beginning
    if(needle === '') {
        return 0;
    }
    // at the first letter if they're identical
    if(needle === haystack) {
        return 0;
    }
    // controls whether loop will break or continue
    isCompleteMatch = false;
    // loop to put each needle letter in play
    for(var needleCount = 0; needleCount < needleLen; needleCount++) {
        // first check to see if our work is done, if so quit procesing
        if(isCompleteMatch) break;
        var isMatch, needleLetter;

        needleLetter = needle[needleCount];
        isMatch = false;
        // loop to put each haystack letter in play against every needle
        for(var hayCount = 0; hayCount < hayLen; hayCount++) {
            var hayLetter;

            hayLetter = haystack[hayCount];
            isMatch = hayLetter === needleLetter;
            if(isMatch) {
               var needleLeft;
               // this sets the loop length for checking for a complete match, since the match has begun
               needleLeft = needleLen - needleCount;

               // loop to check when a possible match is started
               for(var nl = 0; nl < needleLeft; nl++) {
                    // first check to see if our work is done, if so quit procesing
                    if(isCompleteMatch) break;

                    if(needle[needleCount + nl] !== haystack[hayCount + nl]) {
                        // there's no reason to keep looking, break out of loop
                        break;
                    } else {
                        // there is a reason to keep looking
                        // push the current letter to the match
                        match += haystack[hayCount + nl];
                        // if we have a full match
                        // and
                        // we haven't had one so far, then ...
                        if(match === needle && !isCompleteMatch) {
                            // set the result and break out
                            result = hayCount;
                            // set isCompleteMatch so that we don't run this again and the outer loops will break
                            isCompleteMatch = true;
                            break;
                        }
                    }
               }
            } else {
                // if its not then we need to reset match
                match = '';
            }
        }
    }

    return result;
};

indexofSub = function(haystack, needle) {
        // Implementation?
    var hayLen, matched, needleLen, result, substr;
    // this is the result when no loops occur
    // if both needle and haystack aren't string-typed, return -1
    if(typeof haystack !== 'string' || typeof needle !== 'string') {
        return -1;
    }
    // set the length values since I'll use them at least once
    hayLen = haystack['length'];
    needleLen = needle['length'];
    // if the needle is bigger than the haystack, it has no index
    if(needleLen > hayLen) {
        return -1;
    }
    // if the needle is so small it resides at the beginning
    if(needle === '') {
        return 0;
    }
    // set the values that the loop results depends on
    result = -1;
    matched = false;
    for(var hc = 0; hc < hayLen; hc++) {
        substr = haystack.substr(hc, needle.length);
        match = substr === needle;
        if(match) {
            result = hc;
            break;
        }
    }
    
    return result;
};

function testimplharness(impl) {
    console.log('testing impl:');
    console.log(impl);

    function testimpl(haystack, needle, expected) {
        var received = impl(haystack, needle);
        var status = (expected === received)
            ? "PASS"
            : "FAIL";
        console.log("%s: impl(\"%s\", \"%s\") => %d (expected %d)", status, haystack, needle, received, expected);

        return (expected === received);
    }

    var all_passed = true;
    all_passed = (testimpl("hello",     "hel"  ,  0) && all_passed);
    all_passed = (testimpl("hello",     "hello",  0) && all_passed);
    all_passed = (testimpl("foo",       "bar"  , -1) && all_passed);
    all_passed = (testimpl("help",      "hello", -1) && all_passed);
    all_passed = (testimpl("hel",       "hello", -1) && all_passed);
    all_passed = (testimpl("foobar",    "bar"  ,  3) && all_passed);
    all_passed = (testimpl("foobarbaz", "baz"  ,  6) && all_passed);
    all_passed = (testimpl("raaraa",    "raa"  ,  0) && all_passed);
    all_passed = (testimpl("raraa",     "raa"  ,  2) && all_passed);
    all_passed = (testimpl("hello",     ""     ,  0) && all_passed);
    all_passed = (testimpl("",          ""     ,  0) && all_passed);
    all_passed = (testimpl("",          "a"    , -1) && all_passed);
    return all_passed;
};

[indexof, indexofSub].forEach(testimplharness);

@posita,
Please find my responses to your questions below:

1. What is the efficiency ("big-O") of your approach? Can you make it more efficient?

   • I believe it's O(N * (N-1) * (N-2)) or O(N³) depending on desired precision, where N is maximum length of a String in given environment/browser, but I'm not certain of notation here.
   • I'll look into it and push any new implementations. I suspect I may be able to cut out one of those loops. Also, I suspect there may be other ways entirely of accomplishing this altogether.

2. In your current solution, is the following (from line 20) necessary, given the subsequent loop?

   // at the first letter if they're identical
   if(needle === haystack) {
       return 0;
   }

   • No it isn't necessary in the sense that the result of indexof would be same without this block of code, per the tests. My understanding is that doing a strict equality comparison here, ahead of running the loops, would cut down on processing time should needle and haystack turn out to be strictly equivalent.

3. If a match exists, but where needle does not exactly match haystack, what are the performance implications of the above comparison?

   • I'm not perfectly certain of what you mean by "where needle does not exactly match haystack", so I'm interpreting your question as having to do with these variables being type mismatched. If haystack and needle do not match in type, then the for loops will run, potentially missing some of the performance gains of avoiding the loops where possible; however, this would only be relevant if haystack and needle had the same value, but were different types (for example, haystack = 'test'; and needle = ['test'];). Incidentally, if the variables were set to these values, then the for loop wouldn't return a result that would satisfy each test, as both variables need to be String typed. Thus, I observed that doing type checks on both needle and haystack could boost performance and I have implemented this change.

4. Does bracket notation [] work with String types? What is the result in different browsers/environments?

   • To my knowledge, it works in all environments except Internet Explorer 7.

@posita,
I wrote another implementation forsaking two of the loops, I used String.prototype.substr to do this. I'm not sure whether this would be a higher-level function or not vis-a-vis these exercises, but I can state that my code still has to "look for" the match. Thus, this solution has the feeling of extending indexOf functionality from substr, so it would seem that substr is lower level than indexOf, search, etc.

Also, I updated the invocation of the test harness so both implementations are tested.

Here are my results:
testing impl:
[Function]
PASS: impl("hello", "hel") => 0 (expected 0)
PASS: impl("hello", "hello") => 0 (expected 0)
PASS: impl("foo", "bar") => -1 (expected -1)
PASS: impl("help", "hello") => -1 (expected -1)
PASS: impl("hel", "hello") => -1 (expected -1)
PASS: impl("foobar", "bar") => 3 (expected 3)
PASS: impl("foobarbaz", "baz") => 6 (expected 6)
PASS: impl("raaraa", "raa") => 0 (expected 0)
PASS: impl("raraa", "raa") => 2 (expected 2)
PASS: impl("hello", "") => 0 (expected 0)
PASS: impl("", "") => 0 (expected 0)
PASS: impl("", "a") => -1 (expected -1)
testing impl:
[Function]
PASS: impl("hello", "hel") => 0 (expected 0)
PASS: impl("hello", "hello") => 0 (expected 0)
PASS: impl("foo", "bar") => -1 (expected -1)
PASS: impl("help", "hello") => -1 (expected -1)
PASS: impl("hel", "hello") => -1 (expected -1)
PASS: impl("foobar", "bar") => 3 (expected 3)
PASS: impl("foobarbaz", "baz") => 6 (expected 6)
PASS: impl("raaraa", "raa") => 0 (expected 0)
PASS: impl("raraa", "raa") => 2 (expected 2)
PASS: impl("hello", "") => 0 (expected 0)
PASS: impl("", "") => 0 (expected 0)
PASS: impl("", "a") => -1 (expected -1)

@joshuaebowling, substr is okay. Let's hope the VM has some memory copying optimizations to create the sub-strings. Also, be aware that you've probably introduced an implicit loop for the comparison (substr === needle).

I would have preferred to see a two-loop solution using brackets [] or charAt, but this works. 👍