4
\$\begingroup\$

The Aim

Since I very rarely write code to do things other than business logic anymore I've set myself a challenge:

Split a string into a list of substrings by splitting on a matching string, without using string.Split() or similar methods of string (substring, indexof, etc) or LINQ methods (edit or regex /edit).

The method must also accept a parameter stating whether the return list is allowed to contain empty strings (only excludes string.Empty, not whitespace).

The Code

private static IList<string> SplitString(string toSplit, string splitOn, bool allowEmptyResults = true)
{
    int cursorPosition = 0;
    int innerCursor = 0;
    var strings = new List<string>();

    while (cursorPosition < toSplit.Length)
    {
        bool match = false;

        for (int i = 0; i < splitOn.Length ; i++)
        {
            match = toSplit[innerCursor] == splitOn[i];

            if ((i < splitOn.Length - 1 && innerCursor == toSplit.Length - 1) || !match)
            {
                match = false;
                break;
            }

            innerCursor++;
        }

        if (match)
        {
            var result = StringFromCursor(toSplit, cursorPosition, innerCursor - splitOn.Length);

            if (result != string.Empty || allowEmptyResults)
            {
                strings.Add(result);
            }

            cursorPosition = innerCursor;
        }
        else
        {
            if (innerCursor < toSplit.Length - 1)
            {
                innerCursor++;
            }
            else
            {
                var result = StringFromCursor(toSplit, cursorPosition, toSplit.Length);

                if (result != string.Empty || allowEmptyResults)
                {
                    strings.Add(result);
                }

                break;
            }
        }
    }

    return strings;
}

private static string StringFromCursor(string toSplit, int cursorPosition, int matchStart)
{
    string result = string.Empty;

    for (int i = cursorPosition; i < matchStart; i++)
    {
        result += toSplit[i].ToString();
    }

    return result;
}

The Problem

This seems hopelessly complicated and prone to "off by 1" errors, I'm more interested in the cleaner logic for accomplishing this task rather than making it cleaner by refactoring into smaller methods.

Also I'm not too concerned about style (inconsistent use of var for example).

The code spends a large number of characters trying to deal with tricky behaviour at the end of a string but seems to work for the following test cases:

var result = SplitString("thetgonceupon the time there was a thing there", "the");
var result = SplitString("thetgonceupon the time there was a thing thereth", "the");
var result = SplitString("thetgonceupon the time there was a thing therethe", "the");
\$\endgroup\$
  • \$\begingroup\$ If you're looking to avoid String.Split, are you also looking to avoid LINQ methods? \$\endgroup\$ – moarboilerplate Apr 16 '15 at 20:00
  • \$\begingroup\$ @moarboilerplate yes, rather tediously of me I'd also like to avoid those if possible, will edit to include that, thanks. \$\endgroup\$ – Underscore Apr 16 '15 at 20:01
  • \$\begingroup\$ Is Regex an acceptable path to take for you? \$\endgroup\$ – Bardicer Apr 16 '15 at 20:15
  • \$\begingroup\$ @Nick sorry, the list of things which I didn't think to prohibit grows, ideally I'm trying to stick to code which would be in the first 2 chapters of a Teach Yourself C# style book, e.g. if/else, for, while, I almost rejected the List<string> in my answer for being too much luxury. However I'd be interested to see the regex approach. \$\endgroup\$ – Underscore Apr 16 '15 at 20:20
  • \$\begingroup\$ The regex would be very simple, but by default would remove whitespaces (and return string.Empty) in its purely simplest form Regex.Split(toSplit, splitOn); however you could build in whether to accept whitespaces or not. I only asked because it wasn't explicitly stated as a constraint. \$\endgroup\$ – Bardicer Apr 16 '15 at 21:46
5
\$\begingroup\$
private static string StringFromCursor(string toSplit, int cursorPosition, int matchStart)
{
    string result = string.Empty;

    for (int i = cursorPosition; i < matchStart; i++)
    {
        result += toSplit[i].ToString();
    }

    return result;
}

This is a bad idea. Since C# string is immutable, the only way to support an append or += operation is to throw the old string away and build a new one. Doing this repeatedly leads to an \$O(n^2)\$ running time. What you really need is a StringBuilder which does support building up strings piece by piece.

\$\endgroup\$
  • 1
    \$\begingroup\$ Thanks, your answer made me look again at that method, I felt sure there must be a way to create a string from a char[] but I didn't consider the string constructors. I rewrote the method body to be: return new string(toSplit.ToCharArray(), cursorPosition, matchStart-cursorPosition); \$\endgroup\$ – Underscore Apr 16 '15 at 22:39
  • \$\begingroup\$ You don't even need to convert it to an array, you can keep it as a string. \$\endgroup\$ – Snowbody May 4 '15 at 1:26
0
\$\begingroup\$

SplitString()

You should always evaluate first the condition which can be evaluated faster. E.g

if ((i < splitOn.Length - 1 && innerCursor == toSplit.Length - 1) || !match)

Why would you want to evaluate (i < splitOn.Length - 1 && innerCursor == toSplit.Length - 1) for the case where match == false ?

The same is true for if (result != string.Empty || allowEmptyResults).

\$\endgroup\$
  • 1
    \$\begingroup\$ (1) Won't the compiler and/or JIT detect this and reorder things, especially in cases like this when simple static analysis (all the methods called are const) can determine it's safe? (2) Even if condition 2 can be evaluated faster, if condition 1 is false most of the time and condition 2 is true most of the time, it may be a speed decrease to switch the order. (3) This is quite clearly a micro-optimization that shouldn't be done unless profiling shows this section of code is a bottleneck and the change improves tihngs. \$\endgroup\$ – Snowbody May 26 '15 at 2:57

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.