PatternSearch.cs

Go to the documentation of this file.

// 
//  Copyright 2010-2015 Deveel
// 
//    Licensed under the Apache License, Version 2.0 (the "License");
//    you may not use this file except in compliance with the License.
//    You may obtain a copy of the License at
// 
//        http://www.apache.org/licenses/LICENSE-2.0
// 
//    Unless required by applicable law or agreed to in writing, software
//    distributed under the License is distributed on an "AS IS" BASIS,
//    WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
//    See the License for the specific language governing permissions and
//    limitations under the License.
//

using System;
using System.Text;

namespace Deveel.Data.Text {
    public static class PatternSearch {
        // Statics for the tokens.
        private const char ZeroOrMoreChars = '%';
        private const char OneChar = '_';

        public static bool IsWildCard(char ch) {
            return (ch == OneChar || ch == ZeroOrMoreChars);
        }

        public static bool FullPatternMatch(string pattern, string str, char escapeChar) {
            StringBuilder start = new StringBuilder();
            String rezt = null;
            int len = pattern.Length;
            int i = 0;
            bool lastEscapeChar = false;
            for (; i < len && rezt == null; ++i) {
                char c = pattern[i];
                if (lastEscapeChar) {
                    lastEscapeChar = false;
                    start.Append(c);
                } else if (c == escapeChar) {
                    lastEscapeChar = true;
                } else if (IsWildCard(c)) {
                    rezt = pattern.Substring(i);
                } else {
                    start.Append(c);
                }
            }

            if (rezt == null)
                rezt = "";

            string st = start.ToString();

            if (str.StartsWith(st)) {
                string strRezt = str.Substring(st.Length); // (i)

                return rezt.Length > 0 ? PatternMatch(rezt, strRezt, escapeChar) : strRezt.Length == 0;
            }

            return false;
        }

        public static bool PatternMatch(string pattern, string expression, char escapeChar) {
            // Look at first character in pattern, if it's a ONE_CHAR wildcard then
            // check expression and pattern match until next wild card.

            if (pattern[0] == OneChar) {

                // Else step through each character in pattern and see if it matches up
                // with the expression until a wild card is found or the end is reached.
                // When the end of the pattern is reached, 'finished' is set to true.

                int i = 1;
                bool finished = (i >= pattern.Length || expression.Length < 1);
                bool lastWasEscape = false;
                int checkd = 0;
                while (!finished) {
                    char c = pattern[i];
                    if (!lastWasEscape && c == escapeChar) {
                        lastWasEscape = true;
                        if (i >= expression.Length) {
                            return false;
                        }
                        ++i;
                    } else if (lastWasEscape || !IsWildCard(c)) {
                        lastWasEscape = false;
                        // If expression and pattern character doesn't match or end of
                        // expression reached, search has failed.
                        if (i >= expression.Length || c != expression[i]) {
                            return false;
                        }
                        ++i;
                        ++checkd;
                    } else {
                        // found a wildcard, so recurse on this wildcard
                        return PatternMatch(pattern.Substring(i), expression.Substring(i), escapeChar);
                    }

                    finished = (i >= pattern.Length);
                }

                // The pattern length minus any escaped characters
                int realPatternLength = 0;
                int sz = pattern.Length;
                for (int n = 0; n < sz; ++n) {
                    if (pattern[n] != escapeChar) {
                        ++realPatternLength;
                    } else {
                        ++n;
                    }
                }

                // If pattern and expression lengths match then we have walked through
                // the expression and found a match, otherwise no match.

                return realPatternLength == expression.Length;
            }

            // Therefore we are doing a ZERO_OR_MORE_CHARS wildcard check.

            // If the pattern is '%' (ie. pattern.Length == 1 because it's only 1
            // character in length (the '%' character)) then it doesn't matter what the
            // expression is, we have found a match.

            if (pattern.Length == 1)
                return true;

            // Look at following character in pattern, and extract all the characters
            // before the next wild card.

            var nextString = new StringBuilder();
            int i1 = 1;
            bool finished1 = (i1 >= pattern.Length);
            bool lastWasEscape1 = false;
            while (!finished1) {
                char nextChar = pattern[i1];
                if (!lastWasEscape1 && nextChar == escapeChar) {
                    lastWasEscape1 = true;
                    ++i1;
                    if (i1 >= pattern.Length) {
                        finished1 = true;
                    }
                } else if (lastWasEscape1 || !IsWildCard(nextChar)) {
                    lastWasEscape1 = false;
                    nextString.Append(nextChar);
                    ++i1;
                    if (i1 >= pattern.Length) {
                        finished1 = true;
                    }
                } else {
                    finished1 = true;
                }
            }

            string findString = nextString.ToString();

            // Special case optimisation if we have found the end of the pattern, all
            // we need to do is check if 'find_string' is on the end of the expression.
            // eg. pattern = "%er", will have a 'find_string' of "er" and it is saying
            // 'does the expression end with 'er''.

            if (i1 >= pattern.Length)
                return (expression.EndsWith(findString));

            // Otherwise we must have finished with another wild card.
            // Try and find 'next_string' in the expression.  If its found then
            // recurse over the next pattern.

            int findStrLength = findString.Length;
            int strIndex = expression.IndexOf(findString, 0);

            while (strIndex != -1) {
                bool matched = PatternMatch(
                                pattern.Substring(1 + findStrLength),
                                expression.Substring(strIndex + findStrLength),
                                escapeChar);

                if (matched)
                    return true;

                strIndex = expression.IndexOf(findString, strIndex + 1);
            }

            return false;
        }
    }
}