PDG_ValuePattern.h

Go to the documentation of this file.

/*
 * PROPRIETARY INFORMATION.  This software is proprietary to
 * Side Effects Software Inc., and is not to be reproduced,
 * transmitted, or disclosed in any way without written permission.
 *
 * COMMENTS:
 */

#ifndef __PDG_VALUE_PATTERN_H__
#define __PDG_VALUE_PATTERN_H__

#include "PDG_API.h"
#include "PDG_BasePattern.h"

#include <UT/UT_Array.h>
#include <UT/UT_ArrayMap.h>
#include <UT/UT_StringArray.h>
#include <UT/UT_StringHolder.h>
#include <UT/UT_ValArray.h>
#include <UT/UT_VectorTypes.h>
#include <UT/UT_WorkBuffer.h>
#include <SYS/SYS_String.h>

class UT_StringView;

/**
 * Creates a queryable representation of a sequence of values, but does not
 * generate the sequence itself unless requested. For example:
 *
 * `1-10 20 30 40`
 * `1-10:2 !3`
 */
class PDG_API PDG_ValuePattern : public PDG_BasePattern
{
public:
    using StringMap     = UT_ArrayMap<exint, UT_StringArray>;
    using FloatMap      = UT_ArrayMap<exint, UT_FprealArray>;
    using IntMap        = UT_ArrayMap<exint, UT_ExintArray>;

public:
    /// Creates an empty pattern instance that will have it's contents loaded
    /// later.
                                PDG_ValuePattern(char delimiter=' ');

    /// Parses a pattern into a PDG_ValuePattern instance
                                PDG_ValuePattern(
                                    const UT_StringHolder& pattern,
                                    char delimiter=' ');

    /// Checks if the specified string value is in the pattern
    bool                        contains(
                                    const UT_StringHolder& value,
                                    bool inclusive) const
                                    {
                                        if (match(value, inclusive, nullptr))
                                            return true;

                                        int len = value.length();
                                        const char* data = value.c_str();
                                        bool has_digit = false;
                                        while (len--) 
                                        {
                                            if (!SYSisdigit(data[len]))
                                                break;

                                            has_digit = true;
                                        }

                                        if (!has_digit)
                                            return false;

                                        int suffix = atoi(data+len+1);
                                        UT_StringView prefix(data, len+1);
                                        return match(
                                            suffix, prefix, inclusive, nullptr);
                                    }

    /// Checks if the specified float value is in the pattern
    bool                        contains(fpreal value, bool inclusive) const
                                    { return match(value, inclusive, nullptr); }

    /// Checks if the specified integer value is in the pattern
    bool                        contains(exint value, bool inclusive) const
                                    { return match(value, inclusive, nullptr); }


    /// Checks if the specified float value matches the pattern and returns
    /// the range of values from the component that matches
    bool                        containsRange(
                                        UT_FprealArray& range,
                                        fpreal value,
                                        bool inclusive) const
                                    {
                                        return matchRange(
                                            range, value, inclusive);
                                    }

    /// Checks if the specified integer value matches the pattern and returns
    /// the range of values from the component that matches
    bool                        containsRange(
                                        UT_FprealArray& range,
                                        exint value,
                                        bool inclusive) const
                                    {
                                        return matchRange(
                                            range, value, inclusive);
                                    }


    /// Returns the array of string values that match the pattern
    void                        array(
                                    UT_StringArray& values,
                                    bool sorted,
                                    bool inclusive) const
                                    {
                                        return append(
                                            values, sorted, inclusive);
                                    }

    /// Returns the array of float values that match the pattern
    void                        array(
                                    UT_FprealArray& values,
                                    bool sorted,
                                    bool inclusive) const
                                    {
                                        return append(
                                            values, sorted, inclusive);
                                    }

    /// Returns the array of integer values that match the pattern
    void                        array(
                                    UT_ExintArray& values,
                                    bool sorted,
                                    bool inclusive) const
                                    {
                                        return append(
                                            values, sorted, inclusive);
                                    }


    /// Returns a map of component number -> string value array, after
    /// considering exclusions
    void                        arrayMap(
                                    StringMap& values,
                                    bool sorted,
                                    bool inclusive) const
                                    {
                                        return appendMap(
                                            values, sorted, inclusive);
                                    }

    /// Returns a map of component number -> float value array, after
    /// considering exclusions
    void                        arrayMap(
                                    FloatMap& values,
                                    bool sorted,
                                    bool inclusive) const
                                    {
                                        return appendMap(
                                            values, sorted, inclusive);
                                    }

    /// Returns a map of component number -> int value array, after
    /// considering exclusions
    void                        arrayMap(
                                    IntMap& values,
                                    bool sorted,
                                    bool inclusive) const
                                    {
                                        return appendMap(
                                            values, sorted, inclusive);
                                    }


    /// Returns the value range for the specified component number
    bool                        componentRange(
                                    UT_FprealArray& range,
                                    exint index,
                                    bool inclusive) const
                                    {
                                        if (index < 0 ||
                                            index >= myMatches.size())
                                        {
                                            return false;
                                        }

                                        if (myMatches[index].myIsExclusion)
                                            return false;

                                        myMatches[index].setRange(
                                            range, inclusive);

                                        return true;
                                    }

    /// Returns the step value for the specified component number
    fpreal                      componentStep(exint index) const
                                    {
                                        if (index < 0 ||
                                            index >= myMatches.size())
                                        {
                                            return false;
                                        }

                                        return myMatches[index].floatValue(
                                            2, 1);
                                    }

    /// Returns true if the pattern is strictly numeric (has no string
    /// values in it), otherwise returns false
    bool                        isNumeric() const
                                    { return myIsNumeric; }

    /// Returns true if the pattern has segments with different step sizes
    bool                        hasVariableStep() const
                                    { return myHasVariableStep; }

    /// Returns the minimum step size from all components in the pattern
    fpreal                      minimumStep() const
                                    { return myMinimumStep; }

    /// Resets the pattern to an unparsed state
    bool                        reset(
                                    const UT_StringHolder& pattern,
                                    char delimiter=' ');

    /// Updates and reparses the pattern if the supplied pattern string is
    /// different than the current pattern string
    bool                        tryReset(
                                    const UT_StringHolder& pattern,
                                    char delimiter= ' ');

    /// Parses the input string into this pattern -- only valid if no pattern
    /// has been parsed previously
    bool                        parse(const UT_StringView& pattern);

private:
    /// Possible types for a value match
    enum MatchType : uint8
    {
        /// A single constant value
        eMatchTypeConstant,

        /// A simple range with a start and end point, and a step size of 1
        eMatchTypeRange,

        /// A range with a custom step size
        eMatchTypeRangeStep,
    };

    /// Utility to do an inclusive vs. exclusive range end comparison
    template <typename Value, typename Step, typename End>
    static inline bool          inclusiveComp(
                                            bool i,
                                            const Value& v,
                                            const Step& step,
                                            const End& end)
                                    {
                                        if (step > 0)
                                            return i ? (v <= end) : (v < end);
                                        else
                                            return i ? (v >= end) : (v > end);
                                    }

    /// Value containing a float, string and integer part
    struct Value
    {
        /// Appends a constant string, integer or float value from this
        /// match value into the input array
        void            append(UT_StringArray& array) const
                            { array.append(myString); }
        void            append(UT_ExintArray& array) const
                            { if (myHasInteger) array.append(myInteger); }
        void            append(UT_FprealArray& array) const
                            { if (myHasFloat) array.append(myFloat); }


        /// Appends values between start and end to the input array
        static void     append(
                            UT_StringArray& array,
                            const Value& start,
                            const Value& end,
                            bool inclusive)
                            {
                                if (!start.myHasInteger || !end.myHasInteger)
                                    return;

                                for (exint i = start.myInteger;
                                     inclusiveComp(
                                        inclusive, i, 1, end.myInteger);
                                     i++)
                                {
                                    UT_WorkBuffer buffer;
                                    buffer.format("{}{}", start.myPrefix, i);
                                    array.append(buffer.buffer());
                                }
                            }

        static void     append(
                            UT_FprealArray& array,
                            const Value& start,
                            const Value& end,
                            bool inclusive)
                            {
                                if (!start.myHasFloat || !end.myHasFloat)
                                    return;
                                for (fpreal i = start.myFloat;
                                     inclusiveComp(
                                         inclusive, i, 1.0, end.myFloat);
                                     i += 1.0)
                                {
                                    array.append(i);
                                }
                            }

        static void     append(
                            UT_ExintArray& array,
                            const Value& start,
                            const Value& end,
                            bool inclusive)
                            {
                                if (!start.myHasInteger || !end.myHasInteger)
                                    return;
                                for (exint i = start.myInteger;
                                     inclusiveComp(
                                        inclusive, i, 1, end.myInteger);
                                     i++)
                                {
                                    array.append(i);
                                }
                            }


        /// Appends values between start and end, with the specified step
        /// size, to the input array
        static void     append(
                            UT_StringArray& array,
                            const Value& start,
                            const Value& end,
                            const Value& step,
                            bool inclusive)
                            {
                                if (!start.myHasInteger ||
                                    !end.myHasInteger ||
                                    !step.myHasInteger)
                                    return;
                                if (step.myInteger == 0)
                                    return;

                                for (exint i = start.myInteger;
                                     inclusiveComp(
                                        inclusive, i,
                                        step.myInteger, end.myInteger);
                                     i += step.myInteger)
                                {
                                    UT_WorkBuffer buffer;
                                    buffer.format("{}{}", start.myPrefix, i);
                                    array.append(buffer.buffer());
                                }
                            }

        static void     append(
                            UT_FprealArray& array,
                            const Value& start,
                            const Value& end,
                            const Value& step,
                            bool inclusive)
                            {
                                if (!start.myHasFloat ||
                                    !end.myHasFloat ||
                                    !step.myHasFloat)
                                    return;
                                if (SYSequalZero(step.myFloat))
                                    return;

                                for (fpreal i = start.myFloat;
                                     inclusiveComp(
                                        inclusive, i,
                                        step.myFloat, end.myFloat);
                                     i += step.myFloat)
                                {
                                    array.append(i);
                                }
                            }

        static void     append(
                            UT_ExintArray& array,
                            const Value& start,
                            const Value& end,
                            const Value& step,
                            bool inclusive)
                            {
                                if (!start.myHasInteger ||
                                    !end.myHasInteger ||
                                    !step.myHasFloat)
                                    return;
                                if (SYSequalZero(step.myFloat))
                                    return;

                                for (fpreal i = start.myInteger;
                                     inclusiveComp(
                                        inclusive, i,
                                        step.myFloat, end.myInteger);
                                     i += step.myFloat)
                                {
                                    array.append(exint(i));
                                }
                            }


        /// Performs an exact match comparison between an input value and the
        /// constant value in this match value instance
        bool            match(const UT_StringHolder& value) const
                            { return myString == value; }
        bool            match(fpreal value) const
                            {
                                return myHasFloat && SYSalmostEqual(
                                    value, myFloat);
                            }
        bool            match(exint value) const
                            { return myHasInteger && (myInteger == value); }


        /// Checks if the input value is less than the match value in this 
        /// instance
        bool            less(const UT_StringHolder& value, bool inclusive) const
                            { return true; }
        bool            less(exint value, bool inclusive) const
                            {
                                if (!myHasInteger)  return true;
                                else if (inclusive) return value < myInteger;
                                else                return value <= myInteger;
                            }
        bool            less(fpreal value, bool inclusive) const
                            {
                                if (!myHasFloat)    return true;
                                else if (inclusive) return value < myFloat;
                                else                return value <= myFloat;
                            }

        /// Checks if the input value is greater than the match value in this
        /// instance
        bool            greater(
                            const UT_StringHolder& value,
                            bool inclusive) const
                            { return true; }
        bool            greater(exint value, bool inclusive) const
                            {
                                if (!myHasInteger)  return true;
                                else if (inclusive) return value > myInteger;
                                else                return value >= myInteger;
                            }
        bool            greater(fpreal value, bool inclusive) const
                            {
                                if (!myHasFloat)    return true;
                                else if (inclusive) return value > myFloat;
                                else                return value >= myFloat;
                            }


        /// Checks if the input value is in the same value range as this match
        /// value, module the step
        bool            step(
                            const Value& start,
                            const UT_StringHolder& value) const
                            { return false; }
        bool            step(const Value& start, exint value) const
                            {
                                if (!start.myHasInteger || !myHasFloat)
                                    return false;

                                fpreal delta = value - start.myInteger;
                                return SYSalmostEqual(
                                    SYSfmod(delta, myFloat), 0);
                            }
        bool            step(const Value& start, fpreal value) const
                            {
                                if (!start.myHasFloat || !myHasFloat)
                                    return false;

                                fpreal delta = value - start.myFloat;
                                return SYSalmostEqual(
                                    SYSfmod(delta, myFloat), 0);
                            }
                            

        UT_StringHolder myPrefix;
        UT_StringHolder myString;
        fpreal          myFloat;
        exint           myInteger;

        bool            myHasFloat  : 1;
        bool            myHasInteger : 1;
        bool            myHasPrefix : 1;
    };

    /// Value match entry
    struct ValueMatch
    {
        /// Does a full match, including parsing the prefix if the value is a
        /// string
        bool        matchFull(
                            const UT_StringHolder& value,
                            bool inclusive) const
                        {
                            if (match(value, nullptr, inclusive))
                                return true;

                            int len = value.length();
                            const char* data = value.c_str();
                            bool has_digits = false;
                            while (len--) 
                            {
                                if (!SYSisdigit(data[len]))
                                    break;

                                has_digits = true;
                            }

                            if (!has_digits)
                                return false;

                            exint suffix = atoi(data+len+1);
                            if (myHasPrefix)
                            {
                                if (len < 0)
                                    return false;

                                UT_StringView prefix(data, len+1);
                                return match(suffix, &prefix, inclusive);
                            }
                            else
                            {
                                if (len > 0)
                                    return false;
                                return match(suffix, nullptr, inclusive);
                            }
                        }
        bool        matchFull(const exint& value, bool inclusive) const
                        { return match(value, nullptr, inclusive); }
        bool        matchFull(const fpreal& value, bool inclusive) const
                        { return match(value, nullptr, inclusive); }

        /// Matches the pattern with the specified value
        template <typename T>
        bool        match(
                        const T& value,
                        const UT_StringView* prefix,
                        bool inclusive) const
                        {
                            // If the pattern does not have a prefix and we
                            // do, return early
                            if (!myMatchValues[0].myHasPrefix && prefix)
                                return false;

                            // Constants only check the first value
                            if (myMatchType == eMatchTypeConstant)
                            {
                                if (!myMatchValues[0].match(value))
                                    return false;
                            }
                            // Simple range check
                            else
                            {
                                if (myMatchValues[0].less(value, true))
                                    return false;

                                if (myMatchValues[1].greater(value, inclusive))
                                    return false;
                            }

                            // If the pattern has a prefix then we require
                            // a matching one
                            if (myMatchValues[0].myHasPrefix)
                            {
                                if (!prefix)
                                    return false;
                                else if (*prefix !=
                                    myMatchValues[0].myPrefix.c_str())
                                {
                                    return false;
                                }
                            }
                            
                            // At this point, constants and ranges have matched
                            if (myMatchType <= eMatchTypeRange)
                                return true;
                            return myMatchValues[2].step(
                                myMatchValues[0], value);
                        }

        /// Appends the values from the match into the specified array
        template <typename T>
        void        append(T& array, bool inclusive) const
                        {
                            if (myMatchType == eMatchTypeConstant)
                                myMatchValues[0].append(array);
                            else if (myMatchType == eMatchTypeRange)
                            {
                                Value::append(
                                    array,
                                    myMatchValues[0],
                                    myMatchValues[1],
                                    inclusive);
                            }
                            else
                            {
                                Value::append(
                                    array,
                                    myMatchValues[0],
                                    myMatchValues[1],
                                    myMatchValues[2],
                                    inclusive);
                            }
                        }

        /// Returns the nth value from the match as a float
        fpreal      floatValue(int index, fpreal default_value) const
                        {
                            if (index > myMatchType)
                                return default_value;

                            const Value& value = myMatchValues[index];
                            if (value.myHasFloat)
                                return value.myFloat;
                            if (value.myHasInteger)
                                return (fpreal)(value.myInteger);

                            return 0;
                        }

        /// Returns the range of values in the match segment as a float
        /// array
        void        setRange(UT_FprealArray& range, bool inclusive) const
                        {
                            fpreal start = floatValue(0, 0);
                            fpreal end = floatValue(1, start);
                            fpreal step = floatValue(2, 1);

                            fpreal last = SYSfloor((end-start)/step);
                            last = last*step + start;
                            if (!inclusive && SYSalmostEqual(end, last))
                                last -= step;

                            range.clear();
                            range.append(start);
                            range.append(last);
                            range.append(step);
                        }

        /// Values in the match entry
        Value       myMatchValues[3];

        /// The match type
        MatchType   myMatchType;

        /// Whether or not the value sequence is an exclusion
        bool        myIsExclusion;

        /// Whether or not the values in this match have a prefix
        bool        myHasPrefix;

        /// Whether or not the values in this match are all numeric
        bool        myIsNumeric;
    };
    
    /// Array of value matches
    using ValueMatchArray   = UT_Array<ValueMatch>;

    /// Helper struct for parsing string data
    struct ParseState
    {
                        ParseState()
                            { reset(); }

        void            reset()
                            {
                                myValueIndex = 0;
                                myRangeIndex = 0;
                                myLastChar = 0;
                                myIsQuoted = false;
                                myIsSkip = false;
                                myIsExclusion = false;

                                for (int i = 0; i < 3; i++)
                                    myValues[i].clear();
                            }

        UT_WorkBuffer   myValues[3];
        exint           myRangeValues[3];
        int             myValueIndex;
        int             myRangeIndex;
        char            myLastChar;

        bool            myIsQuoted;
        bool            myIsSkip;
        bool            myIsExclusion;
    };

private:
    template <typename T>
    bool                match(
                            const T& value,
                            bool inclusive,
                            const ValueMatch** value_match) const
                            {
                                if (!myIsValid)
                                    return false;

                                bool found = false;
                                for (auto&& match : myMatches)
                                {
                                    if (!match.match(value, nullptr, inclusive))
                                        continue;

                                    if (!myHasExclusion)
                                    {
                                        if (value_match)
                                            *value_match = &match;
                                        return true;
                                    }

                                    if (!match.myIsExclusion)
                                    {
                                        if (value_match)
                                            *value_match = &match;
                                        found = true;
                                    }
                                    else if (found)
                                        return false;
                                }

                                return found;
                            }

    bool                match(
                            exint value,
                            const UT_StringView& prefix,
                            bool inclusive,
                            const ValueMatch** value_match) const
                            {
                                if (!myIsValid)
                                    return false;

                                bool found = false;
                                for (auto&& match : myMatches)
                                {
                                    if (!match.match(value, &prefix, inclusive))
                                        continue;

                                    if (!myHasExclusion)
                                    {
                                        if (value_match)
                                            *value_match = &match;
                                        return true;
                                    }

                                    if (!match.myIsExclusion)
                                    {
                                        if (value_match)
                                            *value_match = &match;
                                        found = true;
                                    }
                                    else if (found)
                                        return false;
                                }

                                return found;
                            }

    template <typename T>
    bool                matchRange(
                            UT_FprealArray& range,
                            const T& value,
                            bool inclusive) const
                            {
                                const ValueMatch* value_match = nullptr;
                                if (!match(value, inclusive, &value_match))
                                    return false;
                                if (!value_match)
                                    return false;

                                value_match->setRange(range, inclusive);
                                return true;
                            }

    template <typename T>
    void                append(
                            T& array,
                            bool sorted,
                            bool inclusive) const
                            {
                                if (!myIsValid)
                                    return;

                                T swap_array;
                                for (auto&& match : myMatches)
                                {
                                    if (!match.myIsExclusion)
                                    {
                                        match.append(array, inclusive);
                                        continue;
                                    }

                                    for (auto&& entry : array)
                                    {
                                        if (match.matchFull(entry, inclusive))
                                            continue;
                                        swap_array.append(entry);
                                    }

                                    std::swap(array, swap_array);
                                    swap_array.clear();
                                }

                                if (sorted)
                                    array.sort();
                            }

    template <typename T>
    void                appendMap(
                            T& map,
                            bool sorted,
                            bool inclusive) const
                            {
                                if (!myIsValid)
                                    return;

                                typename T::mapped_type swap_array;
                                exint i = 0;
                                for (auto&& match : myMatches)
                                {
                                    auto&& array = map[i++];

                                    if (!match.myIsExclusion)
                                    {
                                        match.append(array, inclusive);
                                        continue;
                                    }

                                    for (auto&& array : map)
                                    {
                                        for (auto&& entry : array.second)
                                        {
                                            if (match.matchFull(
                                                    entry, inclusive))
                                            {
                                                continue;
                                            }

                                            swap_array.append(entry);
                                        }

                                        std::swap(array.second, swap_array);
                                        swap_array.clear();
                                    }
                                }

                                if (sorted)
                                {
                                    for (auto&& array : map)
                                        array.second.sort();
                                }
                            }


    bool                parse(const UT_StringHolder& pattern);
    bool                addPattern(ParseState& parse_state);

private:
    /// Array of patterns 
    ValueMatchArray     myMatches;

    /// The minimum step size across all components in the pattern
    fpreal              myMinimumStep;
    
    /// The delimiter between components, if multiple value sequences are 
    /// specified in the same pattern. The default delimiter is a space ' '
    /// character, For example `1-10 20 30`, but this can be changed in the
    /// constructor.
    char                myDelimiter;

    /// Indicates that the pattern has ranges with a variable step size in
    /// different segments, for example 1-10:0.5 and 2-6:0.3
    bool                myHasVariableStep;

    /// Indicates whether or not the match is entirely numeric values, or if
    /// some of the patterns include segments that are non-numeric strings
    bool                myIsNumeric;

    /// Whether or not at least one of the patterns has an exclusion. We store
    /// this so that the `match` method can return early if finds a match and
    /// knows the pattern does not have an exclusion rule in it.
    bool                myHasExclusion;
};

#endif