Multisplit

Multisplit is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

It is often necessary to split a string into pieces based on several different (potentially multi-character) separator strings, while still retaining the information about which separators were present in the input. This is particularly useful when doing small parsing tasks.

Write code to demonstrate this. The function (or procedure or method, as appropriate) should take an input string and an ordered collection of separator strings, and split the string into pieces representing the various substrings. Note that the order of the separators is significant; where there would otherwise be an ambiguity as to which separator to use at a particular point (e.g., because one separator is a prefix of another) the first separator in the collection should be used. The result of the function should be an ordered sequence of substrings.

Extra Credit: include match information that indicates which separator was matched at each separation point and where in the input string that separator was matched.

Test your code using the input string “a!===b=!=c” and the separators “==”, “!=” and “=”.

D

<lang d>import std.stdio, std.array, std.algorithm, std.string; void main() {

   auto s = `a!===b=!=c==!=d`;
   auto divs = [ `==`, `!=`, `=`, `!` ];
   auto lst = MultiSplit(s, divs);
   foreach(int i, string p; lst) {
       write(p);
       if (i < lst.length-1) write(` <`~ divs[i] ~`> `);
   }

}

string[] MultiSplit(string s, string[] divisors) {

   if (s.empty) return [];
   string[] res;
   char[] rest = s.dup;
   foreach(string div; divisors){
       auto p = findSplit(rest, div);
       res.length = res.length + 1;
       res[$-1] = p[0].idup;
       rest = p[2];
       if (p[1].empty || rest.empty) // divisor is not found OR it was last in string
           break;
   }
   if (!rest.empty) {
       res.length = res.length + 1;
       res[$-1] = rest.idup;
   }
   return res;

}</lang> Output (separators are in angle brackets):

a! <==> =b= <!=> c <=> = <!> =d

F#

This example is incorrect. Please fix the code and remove this message. Details: In the second example, "!=" should not be matched since all "=" chars should be removed by the first separator listed.

If we ignore the "Extra Credit" requirements and skip 'ordered separators' condition (i.e. solving absolute different task), this is exactly what one of the overloads of .NET's String.Split method does. Using F# Interactive: <lang fsharp>> "a!===b=!=c".Split([|"=="; "!="; "="|], System.StringSplitOptions.None);; val it : string [] = [|"a"; ""; "b"; ""; "c"|]

> "a!===b=!=c".Split([|"="; "!="; "=="|], System.StringSplitOptions.None);; val it : string [] = [|"a"; ""; ""; "b"; ""; "c"|]</lang>

System.StringSplitOptions.None specifies that empty strings should be included in the result.

J

<lang j>multisplit=:4 :0

 'sep begin'=.|:t=. y /:~&.:(|."1)@;@(i.@#@[ ,.L:0"0 I.@E.L:0) x
 end=. begin + sep { #@>y
 last=.next=.0
 r=.2 0$0
 while.next<#begin do.
   r=.r,.(last}.x{.~next{begin);next{t
   last=.next{end
   next=.1 i.~(begin>next{begin)*.begin>:last
 end.
 r=.r,.;~last}.x

)</lang>

Explanation:

First find all potentially relevant separator instances, and sort them in increasing order, by starting location and separator index. sep is separator index, and begin is starting location. end is ending location.

Then, loop through the possibilities, skipping over those separators which would overlap with previously used separators.

Example use:

<lang j> S=:'a!===b=!=c'

  S multisplit '==';'!=';'='

┌───┬───┬───┬───┬─┐ │a │ │b │ │c│ ├───┼───┼───┼───┼─┤ │1 1│0 3│2 6│1 7│ │ └───┴───┴───┴───┴─┘

  S multisplit '=';'!=';'=='

┌───┬───┬───┬───┬───┬─┐ │a │ │ │b │ │c│ ├───┼───┼───┼───┼───┼─┤ │1 1│0 3│0 4│0 6│1 7│ │ └───┴───┴───┴───┴───┴─┘

  'X123Y' multisplit '1';'12';'123';'23';'3'

┌───┬───┬─┐ │X │ │Y│ ├───┼───┼─┤ │0 1│3 2│ │ └───┴───┴─┘</lang>

Java

Works with: Java version 1.5+

<lang java5>import java.util.ArrayList; import java.util.Arrays; import java.util.List; import java.util.regex.Pattern;

public class Multisplit { public static List<String> multisplit(String str, String... seps){ List<String> ans = new ArrayList<String>(); ans.add(str); if(seps.length == 0){ return ans; } for(String sep : seps){ //temporary list holding substrings with new separators removed List<String> sepsRemoved = new ArrayList<String>(); for(String substr : ans){ //quote in case they use regex chars as a separator sepsRemoved.addAll(Arrays.asList(substr.split(Pattern.quote(sep)))); } ans.clear(); ans.addAll(sepsRemoved);

//condense places where multiple separators were matched consecutively ans.remove(""); } return ans; }

public static void main(String[] args){ System.out.println(multisplit("a!===b=!=c", "==", "!=", "=")); System.out.println(multisplit("a!===b=!=c", "=", "!=", "==")); System.out.println(multisplit("a!===b=!=c")); } }</lang> Output (the brackets are added as part of the toString for Lists -- they are not part of the results in the list):

[a!, b, c]
[a!, b, !, c]
[a!===b=!=c]

PicoLisp

<lang PicoLisp>(de multisplit (Str Sep)

  (setq Sep (mapcar chop Sep))
  (make
     (for (S (chop Str) S)
        (let L
           (make
              (loop
                 (T (find head Sep (circ S))
                    (link
                       (list
                          (- (length Str) (length S))
                          (pack (cut (length @) 'S)) ) ) )
                 (link (pop 'S))
                 (NIL S (link NIL)) ) )
           (link (pack (cdr (rot L))))
           (and (car L) (link @)) ) ) ) )

(println (multisplit "a!===b=!=c" '("==" "!=" "="))) (println (multisplit "a!===b=!=c" '("=" "!=" "==")))</lang> Output:

("a" (1 "!=") NIL (3 "==") "b" (6 "=") NIL (7 "!=") "c")
("a" (1 "!=") NIL (3 "=") NIL (4 "=") "b" (6 "=") NIL (7 "!=") "c")

Python

Using Regular expressions

<lang python>>>> import re >>> def ms2(txt="a!===b=!=c", sep=["==", "!=", "="]): if not txt or not sep: return [] ans = m = [] for m in re.finditer('(.*?)(?:' + '|'.join('('+re.escape(s)+')' for s in sep) + ')', txt): ans += [m.group(1), (m.lastindex-2, m.start(m.lastindex))] if m and txt[m.end(m.lastindex):]: ans += [txt[m.end(m.lastindex):]] return ans

>>> ms2() ['a', (1, 1), , (0, 3), 'b', (2, 6), , (1, 7), 'c'] >>> ms2(txt="a!===b=!=c", sep=["=", "!=", "=="]) ['a', (1, 1), , (0, 3), , (0, 4), 'b', (0, 6), , (1, 7), 'c']</lang>

Not using RE's

<lang python>>>> def ms(txt="a!===b=!=c", sep=["==", "!=", "="]): if not txt or not sep: return [] size = [len(s) for s in sep] ans, pos0 = [], 0 def getfinds(): return [(-txt.find(s, pos0), -sepnum, size[sepnum]) for sepnum, s in enumerate(sep) if s in txt[pos0:]]

finds = getfinds() while finds: pos, snum, sz = max(finds) pos, snum = -pos, -snum ans += [ txt[pos0:pos], [snum, pos] ] pos0 = pos+sz finds = getfinds() if txt[pos0:]: ans += [ txt[pos0:] ] return ans

>>> ms() ['a', [1, 1], , [0, 3], 'b', [2, 6], , [1, 7], 'c'] >>> ms(txt="a!===b=!=c", sep=["=", "!=", "=="]) ['a', [1, 1], , [0, 3], , [0, 4], 'b', [0, 6], , [1, 7], 'c']</lang>

Alternative version <lang python>def min_pos(List): return List.index(min(List))

def find_all(S, Sub, Start = 0, End = -1, IsOverlapped = 0): Res = [] if End == -1: End = len(S) if IsOverlapped: DeltaPos = 1 else: DeltaPos = len(Sub) Pos = Start while True: Pos = S.find(Sub, Pos, End) if Pos == -1: break Res.append(Pos) Pos += DeltaPos return Res

def multisplit(S, SepList): SepPosListList = [] SLen = len(S) SepNumList = [] ListCount = 0 for i, Sep in enumerate(SepList): SepPosList = find_all(S, Sep, 0, SLen, IsOverlapped = 1) if SepPosList != []: SepNumList.append(i) SepPosListList.append(SepPosList) ListCount += 1 if ListCount == 0: return [S] MinPosList = [] for i in range(ListCount): MinPosList.append(SepPosListList[i][0]) SepEnd = 0 MinPosPos = min_pos(MinPosList) Res = [] while True: Res.append( S[SepEnd : MinPosList[MinPosPos]] ) Res.append([SepNumList[MinPosPos], MinPosList[MinPosPos]]) SepEnd = MinPosList[MinPosPos] + len(SepList[SepNumList[MinPosPos]]) while True: MinPosPos = min_pos(MinPosList) if MinPosList[MinPosPos] < SepEnd: del SepPosListList[MinPosPos][0] if len(SepPosListList[MinPosPos]) == 0: del SepPosListList[MinPosPos] del MinPosList[MinPosPos] del SepNumList[MinPosPos] ListCount -= 1 if ListCount == 0: break else: MinPosList[MinPosPos] = SepPosListList[MinPosPos][0] else: break if ListCount == 0: break Res.append(S[SepEnd:]) return Res

S = "a!===b=!=c" multisplit(S, ["==", "!=", "="]) # output: ['a', [1, 1], , [0, 3], 'b', [2, 6], , [1, 7], 'c'] multisplit(S, ["=", "!=", "=="]) # output: ['a', [1, 1], , [0, 3], , [0, 4], 'b', [0, 6], , [1, 7], 'c']</lang>

Tcl

This simple version does not retain information about what the separators were: <lang tcl>proc simplemultisplit {text sep} {

   set map {}; foreach s $sep {lappend map $s "\uffff"}
   return [split [string map $map $text] "\uffff"]

} puts [simplemultisplit "a!===b=!=c" {"==" "!=" "="}]</lang>

Output:

a {} b {} c

However, to keep the match information a more sophisticated technique is best. Note that the most natural model of result here is to return the split substrings as a separate list to the match information (because the two collections of information are of different lengths). <lang tcl>proc multisplit {text sep} {

   foreach s $sep {lappend sr [regsub -all {\W} $s {\\&}]}
   set sepRE [join $sr "|"]
   set pieces {}
   set match {}
   set start 0
   while {[regexp -indices -start $start -- $sepRE $text found]} {

lassign $found x y lappend pieces [string range $text $start [expr {$x-1}]] lappend match [lsearch -exact $sep [string range $text {*}$found]] $x set start [expr {$y + 1}]

   }
   return [list [lappend pieces [string range $text $start end]] $match]

}</lang> Demonstration code: <lang tcl>set input "a!===b=!=c" set matchers {"==" "!=" "="} lassign [multisplit $input $matchers] substrings matchinfo puts $substrings puts $matchinfo</lang> Output:

a {} b {} c
1 1 0 3 2 6 1 7