6
\$\begingroup\$

I have a method I created which is a custom indexOf(). This code seems ugly to me so I was wondering if anyone could recommend a cleaner and perhaps faster implementation of my method.

public static int myIndexOf(char[] str, char[] substr, int index) {
    if (str == null) {
        throw new NullPointerException();
    }
    if (substr.length > str.length) {
        return -1;
    }
    if (substr.length == 0 && index >= str.length) {
        return str.length;
    }
    if (substr.length == 0 && index >= 0) {
        return index;
    }
    if (substr.length == 0 && index < 0) {
        return 0;
    }
    if (substr.length == 0 && str.length == 0 ) {
        return 0;
    }

    int[] found = boyerMoore(str, substr);
    for (int i : found) {
        if (i >= index) {
            return i;
        }
    }
    // can not found substring after index
    return -1;
}

// Don't necessarily need any modification for this method. But for those who are interested
Boyer Moore:

public static int[] boyerMoore(char[] str, char[] substr) { 
    // index array of indexes of found substrings
    // initialize
    int indexCounter = 0;
    int[] subStringIndex = new int[str.length];
    for (int c = 0; c < str.length; c++) {
        subStringIndex[c] = -1;
    }
    // character set ASCII
    int characterSet = 256;
    // initialize
    int[] charSet = new int[characterSet];
    for (int a = 0; a < characterSet; a++) {
        charSet[a] = -1;
    }
    for (int b = 0; b < substr.length; b++) {
        charSet[substr[b]] = b;
    }

    int skip;
    for (int i = 0; i <= (str.length - substr.length); i += skip) {
        //System.out.print(i);
        skip = 0;
        for (int j = substr.length - 1; j >= 0; j--) {
            if (substr[j] != str[i + j]) {
                skip = Math.max(1, j - charSet[str[i + j]]);
                    break;
            }
        }

        if (skip == 0) {
            // increment next value in String
            skip++;
            // add found substring (beginning index)
            subStringIndex[indexCounter] = i;
            indexCounter++;
            // this last bit is used if Boyer Moore stops searching after first instance is found
            // return i;

        }
    }

    return  subStringIndex;
    // This bit is used when Boyer Moore is stops after the first instance in found
    // cannot be found
    // return str.length;
}
\$\endgroup\$
  • \$\begingroup\$ It seems the Boyer Moore part is missing? \$\endgroup\$ – konijn Mar 26 '14 at 1:27
  • \$\begingroup\$ @konijn to boyer Moore part is on the bottom. I modded it to return an in[] if more than one instance of the substring is found \$\endgroup\$ – Liondancer Mar 26 '14 at 1:43
  • \$\begingroup\$ I am a stupid user, I did not see the scroll bar, sorry \$\endgroup\$ – konijn Mar 26 '14 at 2:23
  • \$\begingroup\$ @konijn dont be so hard on yourself =D \$\endgroup\$ – Liondancer Mar 26 '14 at 15:59
5
\$\begingroup\$

Naming

  • Choose an existing idiom such as "find a needle in a haystack" and consider putting the parameters in that order.

  • The name index implies some generic location within haystack. However, start makes it clear why that index is significant.

The rest of my answer assumes these changes.

Validating Input

  • You don't need to manually throw NullPointerException for null values when accessing the length of each string will do it automatically. If not, make sure to check both strings for consistency.

  • Consider how to handle negative values for start, typically by taking it from the end of the haystack. You'll need to decide whether to use modulo arithmetic or constrain overly-negative values to zero.

    if start < 0
        start = Math.max(0, haystack.length + start)
    

Logic Yoga

  • Combine identical prefix expressions in an if chain.

    if (A && R) { X }
    if (A && S) { Y }
    if (A && T) { Z }
    

    This can be simplified and optimized to

    if (A) {
        if (R) { X }
        if (S) { Y }
        if (T) { Z }
    }
    

    It works for || as well, though I can't think of a recent sighting in the wild.

    if (A || R) { X }
    if (A || S) { Y }
    if (A || T) { Z }
    

    becomes

    if (A)
        X Y Z
    else
        // same as "if (A)" above
    
  • Clarify intent by using else if after blocks that should exit. Adding else lets the compiler enforce that intent when they're modified.

    myIndexOf(needle, haystack, start)
        if needle is larger than haystack
            return ...
        else if needle is empty
            return ...
        else
            return ...
    

Extract Methods

  • Move generic helper methods such as constraining an index to a library. Apache Commons probably has one. This way someone doesn't have to read the code three times to infer its intended purpose (versus what it actually does). Here index makes more sense without a context.

    constrain(index, size)
        return Math.max(0, Math.min(index, size))
    
  • Separate parameter checking from the raw search algorithm when either is long enough.

    findBoyerMore(needle, haystack, start)
        for index in boyerMoore(needle, haystack)
            if index >= start
                return index
        return -1
    
  • Extract a method to test if needle can fit inside haystack at start.

    Also, you can fail fast in the case of myIndexOf("foo", "foobar", 5) without calling boyerMoore even though foo is shorter than foobar. Take start into consideration when comparing the length of the two strings.

    canFitAt(needle, haystack, start)
        return start + needle.length <= haystack.length
    

Dead Code

  • Since index >= 0 and index < 0 cannot both fail, if (substr.length == 0 && str.length == 0) cannot succeed and can be removed.

End Result

Combining all of the above gives us a much-simplified method.

myIndexOf(needle, haystack, start)
    if canFitAt(needle, haystack, start)
        return findBoyerMoore(needle, haystack, start)
    else
        return constrain(start, haystack.length)
|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ I would say your || expansion is not an improvement as it is severely not DRY. \$\endgroup\$ – NetMage Jul 26 '19 at 21:25
  • \$\begingroup\$ @NetMage Sometimes violating guidelines like DRY can improve readability. The key is recognizing when to break them. ;) \$\endgroup\$ – David Harkness Jul 28 '19 at 15:52
  • \$\begingroup\$ In this case I would suggest it is asking for a future maintenance error, however, when Y is changed in one place. \$\endgroup\$ – NetMage Jul 29 '19 at 21:46
  • \$\begingroup\$ @NetMage And what about when A is changed in only one place? This is a seriously contrived example no one will encounter in the wild. There's no 100% correct answer to the trade-off of "DRY vs. readablity". That's what makes it a trade-off, and programming is full of them. \$\endgroup\$ – David Harkness Jul 31 '19 at 4:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.