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);

@joshuaebowling, try these:

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

        return (expected === received);
    }

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

    return all_passed;
})();

Can you write an implementation without using String.prototype.split (i.e., without using arrays at all)?

@posita, I just saw this. I'm starting it now.

@posita, here's the result

PASS: indexof("hello", "hel") => 0 (expected 0)
PASS: indexof("hello", "hello") => 0 (expected 0)
PASS: indexof("foo", "bar") => -1 (expected -1)
PASS: indexof("help", "hello") => -1 (expected -1)
PASS: indexof("hel", "hello") => -1 (expected -1)
PASS: indexof("foobar", "bar") => 3 (expected 3)
PASS: indexof("foobarbaz", "baz") => 6 (expected 6)
PASS: indexof("raaraa", "raa") => 0 (expected 0)
PASS: indexof("raraa", "raa") => 2 (expected 2)
PASS: indexof("hello", "") => 0 (expected 0)
PASS: indexof("", "") => 0 (expected 0)
PASS: indexof("", "a") => -1 (expected -1)

@posita,

Below are the results for my last push.

PASS: indexof("hello", "hel") => 0 (expected 0)
PASS: indexof("hello", "hello") => 0 (expected 0)
PASS: indexof("foo", "bar") => -1 (expected -1)
PASS: indexof("help", "hello") => -1 (expected -1)
PASS: indexof("hel", "hello") => -1 (expected -1)
PASS: indexof("foobar", "bar") => 3 (expected 3)
PASS: indexof("foobarbaz", "baz") => 6 (expected 6)
PASS: indexof("raaraa", "raa") => 0 (expected 0)
PASS: indexof("raraa", "raa") => 2 (expected 2)
PASS: indexof("hello", "") => 0 (expected 0)
PASS: indexof("", "") => 0 (expected 0)
PASS: indexof("", "a") => -1 (expected -1)

@joshuaebowling, this just tests String.prototype.search, does it not? How about your own indexof implementation? It looks like some of those tests still fail:

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;
}

testimplharness(indexof);

false
testing impl:
function indexof()
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)
FAIL: impl("raraa", "raa") => 3 (expected 2)
FAIL: impl("hello", "") => -1 (expected 0)
FAIL: impl("", "") => -1 (expected 0)
PASS: impl("", "a") => -1 (expected -1)

@posita,
It looks like I may have given you the impression that I had worked out the issue with my first attempt. But I haven't done that. I can rewrite the this attempt to pass these tests if you would like?

The reason I've come to this condsion is this line in your response:
testimplharness(indexof); where indexof was the name assigned to my first attempt.

@posita,
It looks like I may have given you the impression that I had worked out the issue with my first attempt. But I haven't done that. I can rewrite the this attempt to pass these tests if you would like?

@joshuaebowling, that would be ideal. Thanks! My apologies for tweaking the test harness on you.

@posita,
Are you saying that the function named indexofNoSplit:

1. should be renamed to indexof for the requirement to be fulfilled?
2. should not be used as an answer?
3. should be used as an answer along with another answer using the test harness for each?

Please don't apologize, I'll integrate into the gist.
Thanks so much for your responses.

No. 2 is correct for your current implementation. Alternately, you can pretend that, in our "perverse" (make-believe) environment, neither String.prototype.indexOf nor String.prototype.search exist.

When I previously asked:

Can you write an implementation without using String.prototype.split (i.e., without using arrays at all)?

What I meant was:

Can you write an implementation without using String.prototype.split (i.e., without using arrays at all) _and without calling String.prototype.indexOf, String.prototype.search, Array.prototype.indexOf, Array.prototype.find, etc._?

In other words, I'd like see how you handle the low-level iteration, state management, etc. Your stab at indexof was a good start (exactly the kind if direction I was looking for). What I'd like to see is a similar approach, just without calling String.prototype.split.

Please let me know if this makes sense.

@posita,
I've implemented a solution that conforms to your above description. Here are the results from my tests.
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, Thanks for the update. I have a couple questions based on your latest solution:

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

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;
       }

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

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

@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. 👍