MODERATE-wildcard-match.sleela
lib/examples/regex/MODERATE-wildcard-match.sleela · 71 line(s) · sleela
#sleela 1.7
// MODERATE: glob-style matching with '?' (any one character) and '*' (any run,
// including empty). Implemented on arrays of character codes. We use the code
// -1 inside a pattern to mean '?' and -2 to mean '*', so the matcher stays pure
// arithmetic. This is the recursive-free, two-pointer backtracking algorithm
// that every shell uses for filename globbing.
class ModerateWildcardMatch {
static int ANY1 = -1; // '?'
static int ANYRUN = -2; // '*'
boolean match(int[] text, int[] pat) {
int ti = 0;
int pi = 0;
int starPi = -1; // last '*' position in pattern, or -1
int starTi = 0; // text position when that '*' was taken
while (ti < arrayLength(text)) {
boolean advanced = false;
if (pi < arrayLength(pat)) {
int pc = pat[pi];
if (pc == ANYRUN) {
starPi = pi;
starTi = ti;
pi = pi + 1;
advanced = true;
}
if (!advanced && (pc == ANY1 || pc == text[ti])) {
ti = ti + 1;
pi = pi + 1;
advanced = true;
}
}
if (!advanced) {
// Mismatch: if we saw a '*', let it swallow one more char.
if (starPi >= 0) {
pi = starPi + 1;
starTi = starTi + 1;
ti = starTi;
}
if (starPi < 0) return false;
}
}
// Consume any trailing '*' in the pattern.
while (pi < arrayLength(pat) && pat[pi] == ANYRUN) pi = pi + 1;
return pi == arrayLength(pat);
}
void main() {
// text = "report.txt"
int[] text = new int[10];
text[0]=114; text[1]=101; text[2]=112; text[3]=111; text[4]=114;
text[5]=116; text[6]=46; text[7]=116; text[8]=120; text[9]=116;
// pattern "*.txt" -> [* . t x t]
int[] p1 = new int[5];
p1[0]=ANYRUN; p1[1]=46; p1[2]=116; p1[3]=120; p1[4]=116;
// pattern "re?ort*" -> [r e ? o r t *]
int[] p2 = new int[7];
p2[0]=114; p2[1]=101; p2[2]=ANY1; p2[3]=111; p2[4]=114; p2[5]=116; p2[6]=ANYRUN;
// pattern "*.csv" -> [* . c s v]
int[] p3 = new int[5];
p3[0]=ANYRUN; p3[1]=46; p3[2]=99; p3[3]=115; p3[4]=118;
print("'report.txt' matches '*.txt' ? " + match(text, p1));
print("'report.txt' matches 're?ort*' ? " + match(text, p2));
print("'report.txt' matches '*.csv' ? " + match(text, p3));
}
}