Skip to content

Instantly share code, notes, and snippets.

@joshuaebowling
Last active September 28, 2015 19:33
Show Gist options
  • Save joshuaebowling/e3ef015eb47d1056d761 to your computer and use it in GitHub Desktop.
Save joshuaebowling/e3ef015eb47d1056d761 to your computer and use it in GitHub Desktop.
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
Copy link

posita commented Sep 28, 2015

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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment