Deveel.Data.Text.PatternSearch Class Reference

This is a static class that performs the operations to do a pattern search on a given column of a table. More...

Static Public Member Functions
static bool	IsWildCard (char ch)
	Returns true if the given character is a wild card (unknown). More...
static bool	FullPatternMatch (string pattern, string str, char escapeChar)
	Matches a pattern against a string and returns true if it matches or false otherwise. More...
static bool	PatternMatch (string pattern, string expression, char escapeChar)
	This is the pattern match recurrsive method. More...

Private Attributes
const char	ZeroOrMoreChars = '%'
const char	OneChar = '_'

Detailed Description

This is a static class that performs the operations to do a pattern search on a given column of a table.

The pattern syntax is very simple and follows that of the SQL standard.

It works as follows: The '' character represents any sequence of characters. The '_' character represents some character.

Therefore, the pattern search Anto% will find all rows that start with the string Anto and end with any sequence of characters. The pattern A% Proven% will find all names starting with A and containing Proven somewhere in the end. The pattern _at will find all three letter words ending with at.

Note A ab% type search is faster than a bc type search. If the start of the search pattern is unknown then the entire contents of the column need to be accessed.

Definition at line 45 of file PatternSearch.cs.

Member Function Documentation

static bool Deveel.Data.Text.PatternSearch.FullPatternMatch ( string  pattern, string  str, char  escapeChar  )

inlinestatic

Matches a pattern against a string and returns true if it matches or false otherwise.

This matches patterns that do not necessarily start with a wild card unlike the PatternMatch method.

Definition at line 67 of file PatternSearch.cs.

                                                                                         {
            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;
        }

static bool Deveel.Data.Text.PatternSearch.IsWildCard ( char  ch )

inlinestatic

Returns true if the given character is a wild card (unknown).

Parameters

ch

Returns

Definition at line 55 of file PatternSearch.cs.

                                               {
            return (ch == OneChar || ch == ZeroOrMoreChars);
        }

static bool Deveel.Data.Text.PatternSearch.PatternMatch ( string  pattern, string  expression, char  escapeChar  )

inlinestatic

This is the pattern match recurrsive method.

It recurses on each wildcard expression in the pattern which makes for slightly better efficiency than a character recurse algorithm. However, patterns such as __a will result in many recursive calls.

Note That __ will be less efficient than __% and will produce the same result.

Note It requires that a wild card character is the first character in the expression.

Issue Pattern optimiser, we should optimize wild cards of type __ to __%, or ____% to ____%. Optimised forms are identical in result and more efficient. This optimization could be performed by the client during parsing of the LIKE statement.

Hacking Issue Badly formed wild cards may result in hogging of server side resources.

Definition at line 129 of file PatternSearch.cs.

                                                                                            {
            // 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;
        }

Member Data Documentation

const char Deveel.Data.Text.PatternSearch.OneChar = '_'

private

Definition at line 48 of file PatternSearch.cs.

const char Deveel.Data.Text.PatternSearch.ZeroOrMoreChars = '%'

private

Definition at line 47 of file PatternSearch.cs.

---

The documentation for this class was generated from the following file:

• /var/calculate/remote/distfiles/egit-src/deveeldb.git/src/deveeldb/Deveel.Data.Text/PatternSearch.cs