Last active
September 28, 2015 19:33
-
-
Save joshuaebowling/e3ef015eb47d1056d761 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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); |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
@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
[]
orcharAt
, but this works. 👍